Optimistic Locking in B-Trees
cedardb.com
Optimistic Locking in B-Trees
1–10 of 55 posts
Re: Optimistic Locking in B-Trees
#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?
Re: Optimistic Locking in B-Trees
#3[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.
Re: Optimistic Locking in B-Trees
#4[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.
When incrementing the version with 4 GHz, it takes over 100 years non-stop for a 64bit wraparound.
Re: Optimistic Locking in B-Trees
#5Funny 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.
Re: Optimistic Locking in B-Trees
#6Funny 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.
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.
Re: Optimistic Locking in B-Trees
#7kids 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.
Re: Optimistic Locking in B-Trees
#8Funny 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.
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.
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?
Re: Optimistic Locking in B-Trees
#9[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.
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.
Re: Optimistic Locking in B-Trees
#10 > B-Trees won’t get obsolete
>
>