Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Optimistic Locking in B-Trees

cedardb.com

Post reply on HN
Print view View original

21–30 of 55 posts

Re: Optimistic Locking in B-Trees

#21

Post by msanlop »

Nice! I actually worked on this recently for my bachelor project. We got some promising preliminary results that showed performance gains on B-trees by using "delegation" on top of optimistic lock coupling.

The way delegation locks work is by having threads delegate their critical function instead of getting exclusive access to shared memory. Think of a client/server model, where the server executes other core's critical sections. For machines with very high core counts, the result is that the shared memory remains valid in the delegate's cache, instead of each new lock holder getting cache misses and fetching memory from other cores (or worse, other sockets).

Re: Optimistic Locking in B-Trees

#22

Post by msanlop »

magnat wrote: post #16
jrockway wrote: post #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?

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 t…

I tried looking for papers on the subject but couldn't find much. There recent research about in-memory B-tree, and there is has been shown that smaller pages (sizes as low as 256/512B) are more performant due to better cache behavior[0]. The general wisdom seems to be that disk-based databases' IO performance is the main bottleneck—but again I couldn't find any concrete data/benchmarks about why those higher sizes were chosen.

[0] There's even some cool research about B-trees that have the layout depend on the probabilistic distribution of the lookups: https://dl.acm.org/doi/10.1145/3592980.3595316

Re: Optimistic Locking in B-Trees

#23

Post by sroussey »

magnat wrote: post #16
jrockway wrote: post #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?

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 t…

The default macOS page size is currently 16KB, and various (Apple) stuff is optimized for it, and I think SQLite is among them (not 100%). I think their server optimized builds for internal use are 64.

Re: Optimistic Locking in B-Trees

#24

Post by nullpoint420 »

koverstreet wrote: post #7

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.

bcachefs may use zero lock contention, but does anyone use bcachefs?

(kidding of course, i do)

edit: just realized this is _the_ Kent Overstreet!

Although my original post was in jest, thank you so much for all your hard work on bcachefs.

bcachefs has personally saved me so much time with its copy-on-write functionality, and for that i am very grateful

Re: Optimistic Locking in B-Trees

#25

Post by ianbutler »

Ah optimistic locking. I implemented that on top of a radix tree to make a concurrent disk backed adaptive radix tree for text search in Rust.

I was looking at a blog post talking about the early days of Algolia’s search engine when I decided I wanted to try my own implementation of their algorithm.

https://github.com/iantbutler01/dart

dart = disk backed adaptive radix tree

The idea being hot paths stay in memory and cold paths get shunted to disk and since text search tends to have a pretty regular set of queries people make you get a really nice trade off for speed and storage.

Re: Optimistic Locking in B-Trees

#26

Post by jrockway »

shinycode wrote: post #18
jrockway wrote: post #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?

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 ?

I'm just looking for more depth. Like, is that all loaded in 1 load operation when the page is touched and is therefore optimal? Does disk access / writing dirty pages not matter?

Re: Optimistic Locking in B-Trees

#27

Post by foota »

emmanueloga_ wrote: post #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?)

This is primarily for in-memory data. You need something for the base layer of a LSM-tree no matter how you do it.

Re: Optimistic Locking in B-Trees

#28

Post by foota »

koverstreet wrote: post #7

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.

I'm not familiar with bcachefs, so maybe I'm misunderstanding, but the b-tree discussed here also doesn't need to talk locks except for when data is written?

I'm curious about the per-CPU locks you mention though, do you mean that e.g., nodes are owned by certain CPUs and can only be written from those CPUs (and hence can get away with a CPU local lock?), or something else?

Re: Optimistic Locking in B-Trees

#29

Post by foota »

nullpoint420 wrote: post #24
koverstreet wrote: post #7

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.

bcachefs may use zero lock contention, but does anyone use bcachefs? (kidding of course, i do) edit: just realized this is _the_ Kent Overstreet! Although my original post was in jest, thank you so much for all your hard work on bcachefs. bcachefs has personally saved me so much time with its copy-on-write functionality, and for that i am very grateful

My new hobby, labelling my unused code as zero contention, because if it's not running there's zero contention :-)

Re: Optimistic Locking in B-Trees

#30

Post by senderista »

msanlop wrote: post #21

Nice! I actually worked on this recently for my bachelor project. We got some promising preliminary results that showed performance gains on B-trees by using "delegation" on top of optimistic lock coupling. The way delegation locks work is by having threads delegate their critical function instead of getting exclusive access to shared memory. Think of a client/server model, where the server executes other core's crit…

Sounds a bit like flat combining?

https://people.csail.mit.edu/shanir/publications/Flat%20Comb...

Post reply on HN