jallum / bedrock / b3d7afe336ee9116240479351d7853dd5ed3b645

65%

Build Type

push

github

Committed by web-flow

Commit Message

#37 - Add range-read support (#39)

The Basalt storage driver isn't really as friendly to range-reads as I'd
like. This is a sketch for a new storage driver, Olivine.

Olivine is a multi-version concurrency control (MVCC) storage driver for
Bedrock that implements a page-based B+ tree-like structure with sliding
window version management over a shard. By using a hybrid tree/page
structure, the aim is to be able to quickly find a page or run of pages
that can be passed efficiently to another process for extraction/loading
from external storage. The tree structure is designed to require minimal
changes during mutation (only when pages split or are appended-to). The
use of an indirection-layer (page map) allows maximum sharing of
structure between versions inexpensively.

This hybrid structure allows Olivine to maintain a _complete_ in-memory
index of the shard _for each version_ in the MVCC window, making
operations like range-clear and range-scan _very_ fast and simple.

## Key Architectural Concepts:

1. Page-Based Storage
- [x] Data is organized into pages (max 256 keys each) that form a
linked chain
- [x] Each page contains sorted keys and their corresponding versions
- [x] Pages are to be encoded as binary data with a 16-byte header for
efficient sharing between processes
- [x] Uses simple median split algorithm when pages exceed capacity for
now

2. Multi-Version Concurrency Control (MVCC)
- [x] Lookaside buffer (ETS table) stores recent key-value pairs for
fast access
- [x] Sliding time window (5-second default) retains multiple versions
in memory
- [x] Version filtering allows point-in-time queries within the window
- [x] Older versions are automatically evicted and persisted to DETS

3. Tree-Based Index
- [x] Interval tree (GB-trees) maps key ranges to page IDs for O(log n)
lookups
- [x] Tree stores {last_key → {page_id, first_key}} mappings
- [x] Supports efficient range queries by walking the tree for page ids

4. Hybrid Memory/Disk Architect... (continued)

Run Details

602 of 866 new or added lines in 27 files covered. (69.52%)

1 existing line in 1 file now uncovered.

2968 of 4685 relevant lines covered (63.35%)

883.6 hits per line