Sled

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.

History

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.

Checkpoints

Non-Blocking Fuzzy

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.

Compression

Naïve (Record-Level)

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.

Concurrency Control

Not Supported

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.

Data Model

Key/Value

Sled is a key-value store where keys and values are raw byte strings. It supports atomic single-key operations, including compare and swap operation.

Foreign Keys

Not Supported

Sled does not support foreign key constraints.

Indexes

Bw-Tree

Currently, Sled only supports Bw-Tree index. Experiments with an Adaptive Radix Tree or Height Optimized Trie index are left as future work.

Isolation Levels

Not Supported

Currently, Sled does not support transactions and no isolation level is supported yet. It is an aim of Sled to support serializable isolation in the future.

Joins

Not Supported

Sled does not support join.

Logging

Physical Logging

Sled does physical logging. It logs any update to pages in a sequential log on disk.

Query Compilation

Not Supported

Sled does not support any form of query compilation.

Query Execution

Tuple-at-a-Time Model

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.

Query Interface

Custom API

Sled is an embedded key-value store. User applications call the Rust API of this library to execute queries.

Storage Architecture

Disk-oriented

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.

Storage Model

N-ary Storage Model (Row/Record)

Sled simply stores the key-value pairs in the Bw-Tree.

Storage Organization

Log-structured

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.

Stored Procedures

Not Supported

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.

System Architecture

Embedded

Sled is an embedded key-value store, which is designed to be used as a construction component in larger stateful systems.

Views

Not Supported

Sled does not support views.

Sled Logo
Website

https://github.com/spacejam/sled

Source Code

https://github.com/spacejam/sled

Tech Docs

https://docs.rs/sled

Former Name

rsdb

Developer

Tyler Neely

Country of Origin

US , DE

Start Year

2016

Project Type

Open Source

Written in

Rust

Supported languages

Rust

Inspired By

etcd, HBase, LMDB, MySQL, Redis, RocksDB

Operating Systems

Android, Linux, OS X, Windows

Licenses

Apache v2, MIT