hesela.devBourbon
Bourbon is a research LSM storage engine that uses learned models over immutable sorted files to accelerate key lookup.
Models predict a candidate position range, not whether a key exists. The lookup checks the candidate block filter and searches for the exact key; files without an available model use the baseline lookup path. Fixed-size keys and value references make positions addressable even when separately stored values vary in size. [1]
Admission: the original cost-benefit code tracks positive and negative lookup savings separately, normalizes expected benefit by average file size, and uses sample-count gates. A model can therefore be omitted rather than trained for every file. [2]
The 2020 design does not support general string keys or key compression. Its evaluation mostly uses memory-resident data; storage and limited-memory cases are separate experiments. [1]
Internal lookups are candidate-file probes, not application requests. A negative probe can precede a successful probe of another file. If the model's range crosses data-block boundaries, the index block still selects the data block. [1]
Relations
Citations
- Dai et al. From WiscKey to Bourbon: A Learned Index for Log-Structured Merge Trees. OSDI 2020, 155-171, sections 4-5.
- Original Bourbon artifact, revision dfbf4f39: mod/CBMode_Learn.cpp, CalculateCB.
Further reading
Sources & caveats
- Full-paper and pinned-source review, not benchmark reproduction. The author-linked Bitbucket artifact is distinct from the later edydfang/Bourbon modification.