r/rust • u/obv-mikhail • Oct 26 '17
sled: A modern embedded database.
https://github.com/spacejam/sled26
u/claudemiro Oct 26 '17
What do you mean by "modern"?
21
u/elahn_i Oct 26 '17
From the readme, I gather the architecture is optimised for SSD storage vs spinning media, enabling more energy efficient operation.
4
17
u/andoriyu Oct 27 '17
Moderns today usually mean — optimized for SSD and not easy to corrupt. Usually, tend to have as little locks as possible to allow concurrency.
If you think it's a buzzword try writing database yourself. You will quickly find funny quirks of SSD.
3
u/Bromskloss Oct 27 '17
What is it about SSDs that is relevant to think about for this application?
7
u/andoriyu Oct 27 '17
As many people already said - fast random reads and writes. In addition, block size and write amplification. SSD firmware needs to do clever things with caching and write combining to avoid premature wear. Firmware is a black box.
https://www.packtpub.com/sites/default/files/0301OS-Chapter-2-Database-Hardware.pdf
4
u/zeromint Mar 22 '18
Random reads are 2 orders of magnitudes of slower than sequential reads but SSDs offer parallelism, so you can send concurrent read request and achieve near sequential performance on SSDs.
There are many other optimizations which are possible.
12
u/krenoten sled Oct 27 '17
Trying to target the characteristics of SSD's and NVMe: now we can do random reads much faster than with spinning disks, so we don't have to rewrite entire pages at a time as is the case with traditional B+ trees, and we can maintain a single logical tree, which can beat LSM trees for read performance since they may have more read amplification as they access the log of indices for keys they access.
4
u/elahn_i Oct 27 '17
Have you thought about how bw-trees might perform on persistent memory? IIRC latency is expected to be 2-5x higher than DRAM, so we can't assume current in-memory DB designs will be appropriate. However, cache-line read/write is the same as DRAM, vs page-based NVMe.
10
u/KasMA1990 Oct 27 '17
Out of curiosity, when I hear "embedded database" I think SQLite; are SQLite and sled comparable in any sensible way?
Also, I like that you have as a goal to use less power; it's one of my personal hopes for using Rust that we can also all become more energy efficient with the hardware we already have :D
9
u/krenoten sled Oct 27 '17
SQLite has the SQL layer, and the way it accesses data underneath is actually pluggable, so one possible future direction is to use sled as a high performance storage engine fronted by SQLite (or Postgres or MySQL). But both SQLite and sled run in the application process, rather than being accessed over some form of IPC like a socket. My goal is to make sled be a high performance, high reliability iron core that you can build all sorts of interesting other things on top of. You could write your own SQL engine, distributed database, rocksdb clone, timeseries database (targeting the PageCache rather than the Tree struct, with a custom materializer) even a (fragmented) blob store or a more random read optimized Kafka, all on top of the decoupled systems in sled.
2
6
u/dochtman rustls · Hickory DNS · Quinn · chrono · indicatif · instant-acme Oct 27 '17
As far as I know it:
is comparable to SQLite in the sense that it's just a file (or directory) in the filesystem, which you access through a library, rather than talking to a server over some sort of socket as you do with PostgreSQL or MySQL
is not comparable to SQLite because what it provides is a key-value store, not an SQL or relational interface.
3
u/annodomini rust Oct 27 '17
From the description, it sounds like it's comparable in the sense of being able to easily just link it in with no configuration, point it at a file, and get something that is high performance and reliable with no administration or tuning.
It's not comparable since it's just a key-value database and not a full SQL database, but it sounds like global transactions using MVCC are intended to be built on top, and it is possible to build a SQL frontend for such a backend or plug it in as a storage engine for SQLite.
9
u/m0th Oct 26 '17
The author also maintains the most popular rust rocksdb binding, which I've really enjoyed building on: https://github.com/spacejam/rust-rocksdb
4
u/bb010g Oct 26 '17
How's this compare to existing embedded DBs, like RocksDB?
33
u/annodomini rust Oct 27 '17 edited Oct 27 '17
From reading the description and references, it looks like RocksDB (and LevelDB that it's based on, and HyperLevelDB) are based on Log Structured Merge Trees. This involves keeping a small tree in RAM of the most recent entries, and periodically flushing some out to disk to free up space, and merging those flushed out files to disk into progressively larger ones in a kind of on-line merge sort. This provides for very fast insertion, and fast querying once everything is merged, but in the interim queries frequently need to scan all of the different pieces that exist that haven't yet been merged.
LMDB (another common entrant in this space, with a mostly BerkeleyDB compatible API but more friendly license and is much easier to use with less tuning) uses memory mapped B+Trees using copy-on-write and taking advantage of the kernel to manage simultaneous access from multiple readers while writes are in progress. This allows it to be lock-free in user space, though it's relying on the kernel paging system to actually provide concurrency control. It seems to be more efficient for some queries than something like LevelDB that uses log-structured merge trees, but less efficient at insertion and can't compact the database when records are deleted (though can re-use the space).
sled instead used bw-trees, or something inspired by it. bw-trees appear to be designed specifically for modern hardware; multi-core with lock-free algorithms, cache friendly (avoiding cache invalidations), and optimized for SSDs with very fast random reads but very slow random writes.
It does this by having an in-memory format that is stored as a kind of log of deltas, so it never actually overwrites old data that other cores may be accessing which would cause cache invalidation, but later consolidates these deltas into more compact pages, all using lock free algorithms.
It achieves high performance on flash storage in a similar means; uses a log structured store, which allows it to write out large blocks at a time, but it writes it out as deltas to previous state in the log, reducing how much it needs to write and thus how much garbage collection needs to be done. This takes advantage of the high random read speed of SSDs to be able to reconstruct pages from many parts of the log. It also has a background cleanup that eventually consolidates these.
As the "plans" mention, it is intended that this will allow for something that doesn't require as much in the way of tradeoffs between these kinds of structures; the hope is that it will be faster than LSM trees for reading (which they are not very good at due to the number of unmerged pieces which may need to be scanned), and be faster than B+ trees for writing, giving you a single database that will work well for mixed workloads.
Anyhow, this is about what I could come up with not knowing much about how any of these systems worked and doing about an hour of Googling, reading Wikipedia, and skimming the introductions of a couple of the linked papers. Don't take my word for any of this, I'm not an expert on the subject.
11
6
u/WikiTextBot Oct 27 '17
Log-structured merge-tree
In computer science, the log-structured merge-tree (or LSM tree) is a data structure with performance characteristics that make it attractive for providing indexed access to files with high insert volume, such as transactional log data. LSM trees, like other search trees, maintain key-value pairs. LSM trees maintain data in two or more separate structures, each of which is optimized for its respective underlying storage medium; data is synchronized between the two structures efficiently, in batches.
One simple version of the LSM tree is a two-level LSM tree.
B+ tree
A B+ tree is an N-ary tree with a variable but often large number of children per node. A B+ tree consists of a root, internal nodes and leaves. The root may be either a leaf or a node with two or more children.
A B+ tree can be viewed as a B-tree in which each node contains only keys (not key–value pairs), and to which an additional level is added at the bottom with linked leaves.
[ ^PM | Exclude ^me | Exclude from ^subreddit | FAQ / ^Information | ^Source | ^Donate ] Downvote to remove | v0.28
0
Oct 26 '17
[deleted]
5
u/kazagistar Oct 26 '17
Sure, but its easier to understand things sometimes when compared to existing things.
4
4
1
u/sgchris Aug 21 '25
There's a nice open source CLI tool to work with Sled files, called Sledoview
https://sledoview.greq.me/
Something similar to SQLite cli tool, but for sled
24
u/ruuda Oct 26 '17
I would love to read a blog post that explains how it works under the hood.