3 ms·

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 g

• hyc_symas 3y ago
  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/ 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.
• hoytech 3y ago
  LMDB works like this. The MDB_env struct keeps pointers to both meta pages: https://github.com/LMDB/lmdb/blob/30288c72573ceac719627183f1058cad1dd08b74/libraries/liblmdb/mdb.c#L1520 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 https://dl.acm.org/doi/10.1145/320521.320540 And I believe its first implementation was in IBM's System R.
  • ww520 3y ago
    LMDB is the poster child of COW btree implementation. That paper is a good find. Thanks.