Live data from Hacker News

Optimistic Locking in B-Trees

cedardb.com

31–40 of 55 posts

Re: Optimistic Locking in B-Trees

#31

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

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

Re: Optimistic Locking in B-Trees

#32
post #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 t…

16-bit offsets doesn't limit you to 64K unless you require byte-alignment. 128K or 256K is usually trivial and even 512K or 1M is often viable.

Re: Optimistic Locking in B-Trees

#33

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?

a u16 can address it, which is nice. it's also the minimum virtual address allocation on windows. not sure if either of those are the reason, in this case

Re: Optimistic Locking in B-Trees

#34
Talking of trees and caches, back in school I remember learning about splay trees. I’ve never actually seen one used in a production system though, I assume because of the poor concurrency. Has anyone heard of any systems with tree rebalancing based on the workload (ie reads too not just writes)?

Re: Optimistic Locking in B-Trees

#35
post #8
post #6

Earlier quoted context omitted.

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…

You should also check out the Maple Tree (https://docs.kernel.org/core-api/maple_tree.html).

It's the data structure used to track non-overlapping intervals in the Linux kernel's virtual memory subsystem.

If you don't mind sharing, what's your use case for such a data structure?

Re: Optimistic Locking in B-Trees

#36
post #20

Earlier quoted context omitted.

"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”.

I agree that it is widespread, but whenever you see such illogical terms you have to wonder whether the authors who use them do not understand what they are really doing or they understand, but they succumb to conforming with a widespread inappropriate usage in the hope to be better understood by naive readers.

Understanding the difference between pessimistic access (mutual exclusion implemented by locking) and optimistic access (concurrent accesses with retries when necessary) is absolutely critical for the correct and efficient implementation of algorithms that use shared data structures.

It is frequent to combine both methods in an algorithm, like here, but in English that is not "optimistic locking", but at most "locking and optimistic access" or "optimism and locking".

Pessimistic access means that you expect that another process will attempt to access concurrently the shared data, so you must use a lock to prevent this. Optimistic access means that you expect that no other process will attempt to access concurrently the shared data, so you may proceed to access it immediately, but then you must have some means to detect that your assumption has been wrong and another process has interfered, when the transaction must be retried.

Depending on the application, either pessimistic access or optimistic access results in a better performance, neither is always better than the other. Optimistic access (lock-free access) makes better the best case, but it makes much worse the worst case. Depending on the frequency distribution of such cases optimistic access increases or decreases the performance.

Pessimistic access and optimistic access have the advantage of being applicable to any kind of shared data structure, but dynamic data partitioning, where applicable, like for this shared B-tree example, which can be partitioned in sub-trees accessed concurrently, normally results in better performance than both pessimistic access and optimistic access, by being deterministic and avoiding both locking and retries. Dynamic data partitioning may require locking for a very short time in order to partition the shared resource before accessing the allocated part, though the mutual exclusion provided by atomic instructions may be sufficient for this purpose. It is frequent that an atomic fetch-and-add instruction is enough to partition a shared data structure, like a shared array or a shared message queue, between concurrent processes attempting to access it.

Re: Optimistic Locking in B-Trees

#37

Earlier quoted context omitted.

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?

No, 64K is definitely not loaded in 1 load operation. Maximum amount of load operations modern CPUs can do is 2x512-bit or 128 bytes per cycle or around ~600 GB of L1 bandwidth.

That said, there is no universal page size one can choose from. Some workloads will benefit from smaller page size while others will benefit from larger page size but 512K is not the size you will want to choose. Read-, write-, space-amplification, CPU cache thrashing etc.

Re: Optimistic Locking in B-Trees

#38

Talking of trees and caches, back in school I remember learning about splay trees. I’ve never actually seen one used in a production system though, I assume because of the poor concurrency. Has anyone heard of any systems with tree rebalancing based on the workload (ie reads too not just writes)?

maybe weighted trees? hot paths are lower weight so it will be more close the root.

splay tree are good if you are not accessing concurrently and ordered items. next item always be in root

Re: Optimistic Locking in B-Trees

#40

How do you implement a concurrency-safe copy operation? Especially if data structure you copy is 64Kb.

The first question I always ask about concurrency is: can I exploit immutability?

Once something doesn't change, your copy is a no-op, so size doesn't really matter.

Post reply on HN