[HN Gopher] Optimistic Locking in B-Trees
___________________________________________________________________
Optimistic Locking in B-Trees
Author : uds5501
Score : 85 points
Date : 2025-03-07 17:23 UTC (5 hours ago)
(HTM) web link (cedardb.com)
(TXT) w3m dump (cedardb.com)
| uds5501 wrote:
| [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?
| lvogel wrote:
| 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.
| pfent wrote:
| When incrementing the version with 4 GHz, it takes over 100
| years non-stop for a 64bit wraparound.
| xxs wrote:
| likely even more as it has to be an atomic operation which
| causes extra latency and coherency traffic
| xxs wrote:
| I chuckle every time anyone has tried to handle long(64bit)
| overflows while incrementing by one.
|
| Other than that, the version checks + retries have been a
| thing since forever (they are the most bog standard way to do
| any lock-free datastructures, along with database updates in
| the same manner). They do need a back off, though.
| adrian_b wrote:
| "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.
| foota wrote:
| Funny timing, I've been looking at this recently. Some other well
| performing concurrent ordered data structures are ART (adaptive
| radix trees) and masstree. Skiplists are common since they're
| easier to implement lock free, but they don't seem to perform
| well relative to these alternatives.
| judofyr wrote:
| You should check out Height-Oriented Tries as well. Their
| benchmarks shows that it outperforms both ART and masstree.
|
| EDIT: Oops, yes, I meant Height-Optimized Trie! Sorry about
| that.
| foota wrote:
| Will take a look, thanks! I think you meant height-optimized
| tries, since I had a tough time giving it at first :)
|
| Ideally I'd like to find a way to store a non overlapping
| ordered list of intervals while being able to atomically (wrt
| other insertions) avoid inserting overlaps. This is part of a
| data structure tracking locked ranges, so being able to
| update them in parallel would be nice, since it today takes a
| lock over the whole tree while inserting new locked ranges.
|
| Probably, this would require something with next value
| pointers. Maybe I could do some kind of scheme where to
| insert you have to first optimistically lock the predecessor
| with the to be inserted node, and then insert the new node
| where it belongs?
| koverstreet wrote:
| kids stuff :)
|
| bcachefs uses shared/intent/exclusive locks on nodes, so we only
| have to take write locks during transaction commit when we're
| doing the final update, and percpu read locks for interior nodes
| (and others).
|
| this means that there's basically zero lock contention on
| interior nodes, or even cacheline bouncing. lock contention only
| comes up when you've got different keys in the same leaf nodes.
| cryptonector wrote:
| > B-Trees won't get obsolete > > <reaons>
|
| 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 means that you can have covering indices as the actual table
| where the primary key columns are the prefix for the rest -- look
| ma'! no rowids!
| hot_gril wrote:
| 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).
| emmanueloga_ wrote:
| 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?)
| jrockway wrote:
| 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?
| magnat wrote:
| 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...
| tomnipotent wrote:
| 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.
| shinycode wrote:
| 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 ?
___________________________________________________________________
(page generated 2025-03-07 23:00 UTC)