RSDB
a flash-sympathetic persistent lock-free B+ tree
progress
- lock-free log-structured store with reservable slots
- lock-free page store supporting cache-friendly partial updates
- lock-free b-link tree
- recovery
- zstd compression
- LRU cache
- pagetable snapshotting for faster recovery
- epoch-based gc (LEAKS MEMORY FOR NOW LOLOLOLOLOL)
- multi-key transactions and MVCC using a higher-level
DB
interface
Goals
- don't use so much electricity. our data structures should play to modern hardware's strengths.
- don't surprise users with performance traps.
- bring reliability techniques from academia into real-world practice.
Architecture
Lock-free trees on a lock-free pagecache on a lock-free log. The pagecache scatters partial page fragments across the log, rather than rewriting entire pages at a time as B+ trees for spinning disks historically have. On page reads, we scatter-gather reads across the log to materialize the page from its fragments.
If you want to build a new tree/other structure on the PageCache
, implement the Materializer
trait.