Sled is an embedded key-value store written in Rust. It provides atomic single-key operations, including compare and swap operation. It is designed to be used as a construction component to build larger stateful systems. Sled is optimized for modern hardware. It uses lock-free data structures to improve scalability and organizes storage on disk in a log-structured way optimized for SSDs.
In 2016, Tyler Neely created the rsdb project. In 2017, the project was renamed to Sled in order to avoid associations with the racial slur database on Google. The name Sled is a recursive acronym of "sled likes eating data". Currently, Sled is still at an early stage and should be considered unstable. It is under active development. Its APIs and the on-disk format are changing rapidly and in non-forward compatible ways.
Sled does non-blocking, fuzzy checkpoints. Sled takes a new checkpoint periodically. Sled makes new checkpoints by taking the last checkpoint and replay log records after the last checkpoint on it. If two log records modify the same key-value pair, the one with the larger log sequence number wins.
Sled supports the ability to use the zstd compression algorithm to compress blobs and snapshots. They have to be decompressed first before processing them during query execution.
Currently, Sled does not support transactions and concurrency control is not supported, too. A Cicada style MVCC is planned to be implemented in the future.
Currently, Sled only supports Bw-Tree index. Experiments with an Adaptive Radix Tree or Height Optimized Trie index are left as future work.
Sled does physical logging. It logs any update to pages in a sequential log on disk.
Sled uses tuple-at-a-time model for query execution. Most of its APIs do atomic operations on a single key-value pair. For range scan, it returns an iterator, which is used in Volcano style: The user operates on the current key-value pair and then calls next() to move to the next key-value pair after finishing.
Sled is disk-oriented. It uses LLAMA storage architecture. Sled organizes pages on the disk in a log-structured manner. Sled also has a pagecache in memory.
Sled simply stores the key-value pairs in the Bw-Tree.
Sled organizes pages on the disk in a log-structured manner, which is similar to a log-structured file system. Each page flush appends a sequential log on disk and changes the position of that page in the in-memory mapping table. This structure allows Sled to write small updates without rewriting the entire page, which leads to low write amplification and is good for SSDs. Sled can read multiple fragments of a logical page in parallel, which takes advantage of the parallelism provided by SSDs.
Sled does not support stored procedures. However, it provides merge operators. Merge operators are functions whose parameters are the key, the old value and the value to be merged. Merge operators return a new value for the input key or indicate the key-value pair should be deleted. Merge operators are written in Rust. Users can provide a merge operator to a database and then invoke the merge method of a database with a key and the value to be merged. Sled calls that merge operator to generate the instruction about what to do with this key-value pair. In this way, Sled supports users to embedded some custom logic into the database.
Sled is an embedded key-value store, which is designed to be used as a construction component in larger stateful systems.
Android, Linux, OS X, Windows
Apache v2, MIT