Live data from Hacker News

Optimistic Locking in B-Trees

cedardb.com

11–20 of 55 posts

Re: Optimistic Locking in B-Trees

#11
post #4
post #3

Earlier quoted context omitted.

The version is just an atomic integer assigned to that btree node which is monotonically increasing. Each writer increases the version when it releases the lock IF it has modified the node. Wraparounds are only a theoretical issue. There would have to be exactly UINT64_MAX writers between a reader first checking the version and verifying the version.

When incrementing the version with 4 GHz, it takes over 100 years non-stop for a 64bit wraparound.

likely even more as it has to be an atomic operation which causes extra latency and coherency traffic

Re: Optimistic Locking in B-Trees

#12
post #3
post #2

[not-author] but found it really fascinating. My open questions - is the version monotonically increasing though? - how would one handle wrap arounds once the versions don't fit a datatype? - who decides the version to be assigned to a thread's attempt?

The version is just an atomic integer assigned to that btree node which is monotonically increasing. Each writer increases the version when it releases the lock IF it has modified the node. Wraparounds are only a theoretical issue. There would have to be exactly UINT64_MAX writers between a reader first checking the version and verifying the version.

"Optimistic locking" is a bad choice of words because no locking is optimistic.

In the well-known access method described here, the writers access the shared data with mutual exclusion, i.e. they use locking.

The readers use no locking, but they access the shared data concurrently and optimistically, hoping that the access will succeed at the first attempt.

When the readers are unlucky, they must retry the access.

So there is locking used by writers for mutual exclusion and there is optimistic access used by the readers.

There is no "optimistic locking", which is a contradiction in terms (locking is pessimistic).

In general, there are only 3 methods for accessing shared data: mutual exclusion (a.k.a. pessimistic access), where locking forces the accesses to be sequential, and 2 methods where accesses may be concurrent, optimistic access (a.k.a. lock-free), where retries may be necessary, and dynamic partitioning of the shared data (typically used for shared arrays or for shared buffers/queues), where neither locking nor retries are needed.

The method described here for accessing B-trees employs a combination of all 3 methods, because the release of the locks at higher levels is a consequence of restricting the future accesses to only a part of the shared data, i.e. the writers that access the shared B-tree start by accessing sequentially the root, but then they partition the tree between themselves, so the next accesses that fall in distinct subtrees may proceed concurrently.

Re: Optimistic Locking in B-Trees

#13
I wonder about the angle of the article, starting with "B-Trees stand the test of time" ending with "everything else has seriously diminishing returns".

I never ask myself why we still use hashmaps or heaps or whatnot, so makes me wonder if this is really an article about why Cedar does not use something else? (LSM-trees the elephant in the room?)

Re: Optimistic Locking in B-Trees

#14

> B-Trees won’t get obsolete > > Among the many reasons that b-trees aren't going away is that they are prefix indices. This means that an index on multiple columns -or on one column the values of whose type can have prefixes, like strings- can be searched with just a prefix of the key, which enables skip-scan type optimizations, and allows the index to be applicable to many more queries than a hash index. It also me…

Also if you have roughly increasing row IDs, theoretically a btree is faster to insert into at a large scale, even if you don't care for prefix lookups or inequalities. And I think faster to read from.

I'm not sure if that's why, but in practice, Postgres doesn't care too much for hash indexes. It technically has them, but they're non-default, not recommended, previously poorly supported, etc. The default is btree (and serial pk).

Re: Optimistic Locking in B-Trees

#15
Something I always wonder about is figuring out the optimal page size. The author seems to use 64KB. This is neither the size of a CPU cache line (often 64 bytes) nor the size of a block on an SSD (often 512KB). So why 64KB?

Re: Optimistic Locking in B-Trees

#16

Something I always wonder about is figuring out the optimal page size. The author seems to use 64KB. This is neither the size of a CPU cache line (often 64 bytes) nor the size of a block on an SSD (often 512KB). So why 64KB?

If your data/leaf/heap pages hold indexed cells PostgreSQL-style [1], 16-bit in-page offset limits your page size to 64KB. On the other hand, physical memory frame size usually is 4KB or larger, so going below that is not really productive.

Having said that, both PostgreSQL and Microsoft SQL has 8KB page size, while original SQLite had 1KB pages, before switching to 4KB, while still supporting 64KB pages. On top of that, Microsoft SQL operates internally on extents of 8 pages (64 KB) instead of a single page, but still pretends to use 4 KB pages [2].

In other words - no idea.

[1] https://www.postgresql.org/docs/current/storage-page-layout....

[2] https://learn.microsoft.com/en-us/sql/relational-databases/p...

Re: Optimistic Locking in B-Trees

#17

Something I always wonder about is figuring out the optimal page size. The author seems to use 64KB. This is neither the size of a CPU cache line (often 64 bytes) nor the size of a block on an SSD (often 512KB). So why 64KB?

Cedar uses a PAX storage layout (hybrid row/column) so I imagine 64KB optimizes well for OLAP workloads while keeping excess disk I/O for point look-ups manageable. Depending on your OLAP load that "excess" I/O could either be a rounding error or a bottleneck.

Re: Optimistic Locking in B-Trees

#18

Something I always wonder about is figuring out the optimal page size. The author seems to use 64KB. This is neither the size of a CPU cache line (often 64 bytes) nor the size of a block on an SSD (often 512KB). So why 64KB?

From the article : « The 64KB root node of our B-Tree fits nicely into the L1/L2 cache of a modern CPU »

Maybe that’s why ?

Re: Optimistic Locking in B-Trees

#19

Something I always wonder about is figuring out the optimal page size. The author seems to use 64KB. This is neither the size of a CPU cache line (often 64 bytes) nor the size of a block on an SSD (often 512KB). So why 64KB?

64KiB also happens to be the largest minimum page size you can configure reasonably common hardware to have (not that this is a common configuration).

Re: Optimistic Locking in B-Trees

#20
post #3

Earlier quoted context omitted.

The version is just an atomic integer assigned to that btree node which is monotonically increasing. Each writer increases the version when it releases the lock IF it has modified the node. Wraparounds are only a theoretical issue. There would have to be exactly UINT64_MAX writers between a reader first checking the version and verifying the version.

"Optimistic locking" is a bad choice of words because no locking is optimistic. In the well-known access method described here, the writers access the shared data with mutual exclusion, i.e. they use locking. The readers use no locking, but they access the shared data concurrently and optimistically, hoping that the access will succeed at the first attempt. When the readers are unlucky, they must retry the access. So…

“Optimistic locking” is a well-established and widespread terminology though, not the least due to its catchiness. The more factual, but unwieldy term is “optimistic concurrency control”.
Post reply on HN