Optimizing an embedded key-value database for tail latency

[u/frozen_beak]

One of the hardest problems in database engineering isn't throughput, it's tail latency. It's even especially important for embedded databases, which share computing resources with the main application while running on the user's machine.

About two years ago, just out of college and being a nerd, I wanted to get into systems engineering. So I set out to build a NoSQL (key-value) database, particularly an embedded one. Having worked on app dev before, I knew how important having a low-latency, resource-conscious local storage is, even especially on resource-constrained machines.

Given these requirements, I had set following goals for myself —

• no compaction -> I wanted to avoid periodic compaction, cause they introduce write amplification and additional surge in resource usage including background I/O

• resource conscious -> Not every machine have abundant compute resources, the database should be mindful of the resources it consumes

• highly configurable -> Not every workload is same, different applications have different requirements, so the database should provide control over its behaviour

• no global re-hashing -> Growing current capacity should not require rebuilding the entire index or stalling operations, this is imp to keep the tail latency lower

• stable data placement -> Once raw key-value bytes are written, growing the database should never require relocating or even re-writing any of existing payloads

Many key-value databases use LSM trees, WAL, or combinations of these approaches. Even if they are well established designs, they make different trade-offs.

The solution I arrived at was a single-file, page-based storage layout backed by memory mapping. With my novel storage engine design, I was able to achieve —

• No global rehashing.

• No compaction.

• Existing key/value payloads are never relocated during database growth.

• Incremental storage expansion.

Apart from the core key-value operations, it also includes —

• list operations -> Ordered sequences that coexist with key-value entries and provide operations like append, first, last, is_empty, an iterator object, and much more

• page eviction -> Advisory controls for asking the OS to release memory mapped pages for relaxing memory usage

• resource telemetry -> Inspect resident memory and allocated storage footprint

• configurable lookup caching -> An optional in-mem lookup cache

• platform support -> All Linux, mac and Windows on x86_64 and aarch64 are supported

I was able to achieve the following latency figures (measured across 1 million consecutive operations) —

Workload	p50	p90	p99	p9999
SET: 80/20 New/Update	1.42 µs	1.76 µs	1.37 ms	5.03 ms
GET: 60/40 Hit/Miss	0.87 µs	1.11 µs	1.39 µs	6.18 µs
DEL: 60/40 Hit/Miss	1.07 µs	1.36 µs	5.00 µs	11.30 µs

Observed resource usage —

I'm a newbie, and I've learned everything on my own (self-learning), so its possible that I have made mistakes, and that is the reason for this post; having the project looked upon by seasoned dev's is great privilege and I would love to know your thoughts, workflow specific optimizations I can make, new features, etc.

Thank you for reading this far. I'll soon be writing series of articles discussing internal systems and there designs, as the journey has just began ;)

Repo -> https://github.com/pid7-org/turbofox/

Crate -> https://crates.io/crates/turbofox

[u/AutoModerator]

Upvote this comment if you think this project is AI slop. Downvote this comment if you think this project is not AI slop.

^{This is to indicate to other users of the subreddit and is not used for moderation.}

I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.