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

41–50 of 55 posts

Re: Optimistic Locking in B-Trees

#41

Post by msanlop »

senderista wrote: post #30
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...

Indeed, generally delegation has become to mean that there is a dedicated server thread that executes critical sections. Where as combining indicates that any thread can become a combiner while acquiring a lock, for a certain period of time. For the project, we used queue-based combining, which seems to be similar to the the lock in the paper.

Re: Optimistic Locking in B-Trees

#42

Post by dspillett »

cryptonector wrote: post #31
hot_gril wrote: post #14

Earlier quoted context omitted.

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 (a…

But tables in PG are heaps, so appending to them is even faster than in b-trees.

This is specifically taking about indexed structures though, so inserting data in a way that means it can be efficiently searched afterwards. Comparing heaps to b-trees, hash tables, and other ones structures in this context isn't really a Granny Smith Vs Golden Delicious style comparison.

Many (though not all) databases allow the base data to be a heap for those situations where a pure heap or a heap with small supporting indexes is more efficient (very wide data for instance, particularly in intermediate structures for ETL processes (a longer process acronym might better describe this, say, ELTEL)).

Re: Optimistic Locking in B-Trees

#44

Post by avinassh »

cryptonector wrote: post #31
hot_gril wrote: post #14

Earlier quoted context omitted.

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 (a…

But tables in PG are heaps, so appending to them is even faster than in b-trees.

> But tables in PG are heaps, so appending to them is even faster than in b-trees.

elaborate? how it is different, than say, MySQL?

Re: Optimistic Locking in B-Trees

#45

Post by koverstreet »

foota wrote: post #28
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?

> 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?

Updates to the b-tree in memory require locks too :)

> 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?

https://evilpiepirate.org/git/bcachefs.git/tree/fs/bcachefs/...

This is the code for btree node locks, as you can see there's a mode where the reader count is stored in a percpu counter. It makes it more expensive to take a write lock, but it means there's zero cacheline contention when just taking read locks (which is by far the common case for interior nodes!).

Re: Optimistic Locking in B-Trees

#46

Post by hinkley »

cryptonector wrote: post #10

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

Software architecture is dominated by a few inequalities that tend to remain in the same order most of the time, get closer or farther away from each other, and only occasionally reorder themselves because some big breakthrough in one kind of hardware has no equivalence in another and things get out of whack.

When they get out of whack we try some really crazy algorithms that make sense when the inequalities invert, and then disappear when order is restored.

One of the first times networking got faster than local storage, John Ousterhout (of Raft fame) and his group at Berkeley introduced a distributed operating system called Sprite (which featured heavily in the Distributed Computing class I took) that could not only run processes on different machines but could also do live process migration - in the 1980's. NICs getting faster than disk also brought us in-memory and disk-backed, in-memory KV stores, which haven't really gone away even with the introduction of NVMe storage.

B-trees fit well with the dominant equation, so they never really go away.

Re: Optimistic Locking in B-Trees

#47

Post by twotwotwo »

hinkley wrote: post #46
cryptonector wrote: post #10

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

Software architecture is dominated by a few inequalities that tend to remain in the same order most of the time, get closer or farther away from each other, and only occasionally reorder themselves because some big breakthrough in one kind of hardware has no equivalence in another and things get out of whack. When they get out of whack we try some really crazy algorithms that make sense when the inequalities invert,…

> in-memory and disk-backed, in-memory KV stores, which haven't really gone away even with the introduction of NVMe storage

If we're talking caches and Redis, one thought about why they haven't gone away--

In practice I think sharing is part of what keeps them network services, not only access to a cluster's RAM. As a dev you reach for something shared and 'shaped' like a cache, and the in-RAM aspect may be vestigial but still comes with the package.

We use Redis when e.g. tracking stats on active client IPs to see which are up to shenanigans, a maybe common use where you want cluster-wide stats. When caching, we may still want one DB query per expiry period app-wide, not one per webserver.

We would probably be fine 'caching' some stuff in the DB; Django's cache package has supported it for a while! I'm sure one of the disk-using successors of an in-RAM store could hit perf targets (DragonflyDB looks cool!). Just not a priority to change stuff that's working. (Corollary: I bet some folks unhappy with their Redis RAM needs are more than happy to try Dragonfly.)

Re: Optimistic Locking in B-Trees

#48

Post by hot_gril »

dspillett wrote: post #42
cryptonector wrote: post #31

Earlier quoted context omitted.

But tables in PG are heaps, so appending to them is even faster than in b-trees.

This is specifically taking about indexed structures though, so inserting data in a way that means it can be efficiently searched afterwards. Comparing heaps to b-trees, hash tables, and other ones structures in this context isn't really a Granny Smith Vs Golden Delicious style comparison. Many (though not all) databases allow the base data to be a heap for those situations where a pure heap or a heap with small supp…

It was unclear of me to say "row IDs." I meant primary keys, not something like ctid https://www.postgresql.org/docs/current/ddl-system-columns.h...

Re: Optimistic Locking in B-Trees

#49

Post by foota »

koverstreet wrote: post #45
foota wrote: post #28

Earlier quoted context omitted.

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?

> 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? Updates to the b-tree in memory require locks too :) > 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 so…

Interesting, I'm not certain, but I think the same thing (e.g., no contention on cache lines) would be achieved through the versions used in optimistic lock coupling, since reads don't need to take a lock?

Re: Optimistic Locking in B-Trees

#50

Post by cryptonector »

avinassh wrote: post #44
cryptonector wrote: post #31

Earlier quoted context omitted.

But tables in PG are heaps, so appending to them is even faster than in b-trees.

> But tables in PG are heaps, so appending to them is even faster than in b-trees. elaborate? how it is different, than say, MySQL?

In SQLite3 tables are b-trees.
Post reply on HN