Rethinking Sanakirja

https://pijul.org/posts/2021-02-06-rethinking-sanakirja/

by lelf • 5 years ago

71 16 5 years ago

hans0l074• 5 years ago

On a side note, "sanakirja" is the Finnish word for "dictionary". My casual glance seems to indicate that it is indeed a K-V store backed by B-trees [1] 1: https://pijul.org/2017/03/16/sanakirja/

pmeunier6• 5 years ago

Good point. As this is a technical post following up on discussions in the Rust community (on Reddit and IRL in France), I forgot to add that word of background (I've fixed this now, thanks!).

marton78• 5 years ago

Funny. I thought it must be a Sanskrit word, it doesn't sound too Finnish to my untrained (albeit Hungarian) ears.

pmeunier6• 5 years ago

The "Finno-Hugric" family is a bit controversial. That said, I speak several indo-european languages, and Farsi still sounds very exotic to me.

rasjani• 5 years ago

Sanakirja is compound word: sana meaning word and kirja meaning book.

CodesInChaos2• 5 years ago

1. When talking about BTreeMaps with zero sized values, I'd instead talk about BTreeSets

2. Where does the 500 tables thing come from?

3. I don't fully understand why the importance of copy-on-write forks is much less important now

pmeunier6• 5 years ago

1. Correct, my point was to emphasise that the implementation is the same. I've just updated it, thanks!

2. We often make the assumption that pages can be flushed to disk atomically, which is not very far from true on modern disks. Because the only update that really needs to be atomic is for these tables, they're all stored on one page. Since these pointers are all 64 bits in size (since 4k = 2^12, 12 bits in each of these are 0s), after a header of a few bytes, that leaves about 500 positions. The first few are probably more often atomic than the last ones, especially on very old disks.

3. It's still very important, but less so, because the Pijul repositories are much lighter on disk. Copying 1Mb is fast, but copying 100Mb is 100 times slower. I still like this feature, because (1) it costs almost nothing extra and (2) I really like the implementation.

CodesInChaos2• 5 years ago

So you're assuming native 4KiB sector support (which requires both modern disks and operating systems)? Traditional 512 byte sectors only allow for 61 tables to be updated atomically.

What happens when you exceed the limit? Does it silently become non-atomic?

Also, I find it a bit strange you're talking about pages, not (disk) sectors.

jarym• 5 years ago

One thing I’ve learned is that spending time building, benchmarking and profiling basic blocks may seem like it can delay the overall plan; however, in this case, exploring different designs for the basic parts made it clear which features of the basic blocks were varying, and which were necessary, yielding a more modular design in the end, which was key to the performance improvements I got.

This. I try point this out so often and am challenged with the 'premature optimisation...' mantra but in my view this is in no way a premature optimisation but an essential part of the design process.

Thanks to the author for an enlightening article.

pmeunier6• 5 years ago

Thanks to the author for an enlightening article.

Thanks, I'm glad it was useful!

Rethinking Sanakirja

Related Stories