Sled

View Current Viewing Revision #4 from 05/14/2019 10:05 p.m.

Sled is an embedded database management system written in Rust.

Storage Model

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

System Architecture

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

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.

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.

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.

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.

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.

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.

Joins

Not Supported

Sled does not support join.

Foreign Keys

Not Supported

Sled does not support foreign key constraints.

Query Interface

Custom API

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

Logging

Physical Logging

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

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.

Views

Not Supported

Sled does not support views.

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.

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.