Hacker News Reader

Comment by thechao | Hacker News Reader

I am immediately nerd-sniped by this. Is there any code out there you know of I can see? The dual meta-data pages sounds precisely like double-buffering (from graphics; my domain of expertise). I am also drawn to append-only-like and persistent data-structures.

View on HN

LMDB works like this. The MDB_env struct keeps pointers to both meta pages:

https://github.com/LMDB/lmdb/blob/30288c72573ceac719627183f1...

Which meta-page used is determined by the transaction ID (even IDs use first, odd IDs second).

This is the earliest description I can find of the "shadow paging" concept: https://dl.acm.org/doi/10.1145/320521.320540

And I believe its first implementation was in IBM's System R.

LMDB is the poster child of COW btree implementation. That paper is a good find. Thanks.

I had never read any papers on shadow paging when I wrote LMDB. I refer to it as double-buffering in the original LMDB paper because of my own prior experience writing graphics code. You can find the (L)MDB paper here https://openldap.org/pub/

Other commenters noting that append-only isn't efficient enough for general use are correct. We found this as well in the early days of testing LMDB with append-only behavior; 99% of pages were obsolete after only 5 transactions. That's why LMDB is CoW but not append-only, and that's why it uses a double-buffered meta page.

Bzero's work on append-only Btree was educational and illuminating, but not usable in the real world.

Reply on news.ycombinator.com