3 ms·
I recently implemented the Bitcask paper in Golang and shared my learnings: https://mrkaran.dev/posts/barreldb/ https://mrkaran.dev/posts/barreldb/ https://gi
by mr-karan 4y ago
I recently implemented the Bitcask paper in Golang and shared my learnings:
https://mrkaran.dev/posts/barreldb/ https://mrkaran.dev/posts/barreldb/
https://github.com/mr-karan/barreldb/ https://github.com/mr-karan/barreldb/
Bitcask is an excellent paper that is not overwhelming to understand and offers a great stepping stone in building your own data stores. The simple yet powerful design of an append only file is eloquent and performant.
I’d love to read about more such implementations, if anyone has any recommendations.
- whartung 4y agoIs there an elegant solution to the garbage collection problem that append only DBs have to deal with?
- mr-karan 4y agoI think what bitcask proposes (to routinely collect datafiles and mark them as stale and GC them later) is quite a simple solution. It would work for a lot of usecases.
- yencabulator 4y agoThis is most exhaustively talked about in the context of Log-Structured Merge Trees, like LevelDB and RocksDB. They essentially structure the append-only/write-once chunks into tiers of generations (each compaction shifting the still-alive data to a more long-lived tier), reminiscent of generational GC except now shaped like a tree. https://en.wikipedia.org/wiki/Log-structured_merge-tree https://en.wikipedia.org/wiki/Log-structured_merge-tree https://en.wikipedia.org/wiki/Tracing_garbage_collection#Generational_GC_(ephemeral_GC) https://en.wikipedia.org/wiki/Tracing_garbage_collection#Gen...