2 Database
Timo Kösters edited this page 3 weeks ago

What’s sled?

Sled is a modern embedded database. It’s written in Rust and usable on servers and phones with any C-compatible language. It’s low level to the degree that its API is basically a BTreeMap<[u8], [u8]> (a binary tree with key and value as raw bytes).

Why sled?

  • It’s simple. No need to work with an external database.
  • It’s fast. Because it’s low level, it’s easy to reason about performance.

Trees

A single sled database can contain many trees, each of which can store key-value pairs.

In Conduit we have a high level overview over all database parts and their trees in src/database.rs. For example the users part of the database contains the userid_password and todeviceid_events trees. The naming scheme for the trees is <key type> + underscore + <value type>. The types are explained in more detail in their respective module.

For example the key type for todeviceid_events is todeviceid which is explained in src/database/users.rs as UserId + DeviceId + Count. This means that the key is built by taking the user id bytes, followed by a 0xff byte as a separator, followed by the device id bytes and so on.

Useful methods on trees

Tree::scan_prefix

Create an iterator over tuples of keys and values, where the all the keys starts with the given prefix.

This is useful for trees with keys that are split into multiple parts, like in our example above todeviceid_events. If we want to get all todevice events for a user, we run scan_prefix with the user id + 0xff (delimiter) as the argument. If we want to limit these events to a particular device, you append the device id + 0xff to that key.

Tree::range

Create a double-ended iterator over tuples of keys and values, where the keys fall within the specified range.

This might seem like a rare usecase at first, but when you realize that open ranges are supported and it returns an iterator (very efficient), you can use it for many things like getting the last 10 events in a room or all EDUs before a timestamp (when the tree’s key starts with the timestamp).

This is also the reason why Conduit has a global counter which is always increasing for each new event (also referred to as since, count or batch token).