docs/architecture/encoding.md
The key/value store uses binary Vec<u8> keys and values, so we need an encoding scheme to
translate between in-memory Rust data structures and the on-disk binary data. This is provided by
the encoding
module, with separate schemes for key and value encoding.
Bincode Value EncodingValues are encoded using Bincode, a third-party binary encoding scheme for Rust. Bincode is convenient because it can easily encode any arbitrary Rust data type. But we could also have chosen e.g. JSON, Protobuf, MessagePack, or any other encoding.
We won't dwell on the actual binary format here, see the Bincode specification for details.
To use a consistent configuration for all encoding and decoding, we provide helper functions in
the encoding::bincode
module which use bincode::config::standard().
Bincode uses the very common Serde framework for its API. toyDB also provides an
encoding::Value helper trait for value types which adds automatic encode() and decode()
methods:
Here's an example of how this can be used to encode and decode an arbitrary Dog data type:
#[derive(serde::Serialize, serde::Deserialize)]
struct Dog {
name: String,
age: u8,
good_boy: bool,
}
impl encoding::Value for Dog {}
let pluto = Dog { name: "Pluto".into(), age: 4, good_boy: true };
let bytes = pluto.encode();
println!("{bytes:02x?}");
// Outputs [05, 50, 6c, 75, 74, 6f, 04, 01]:
//
// * Length of string "Pluto": 05.
// * String "Pluto": 50 6c 75 74 6f.
// * Age 4: 04.
// * Good boy: 01 (true).
let pluto = Dog::decode(&bytes)?; // gives us back Pluto
Keycode Key EncodingUnlike values, keys can't just use any binary encoding like Bincode. As mentioned in the storage section, the storage engine sorts data by key to enable range scans. The key encoding must therefore preserve the lexicographical order of the encoded values: the binary byte slices must sort in the same order as the original values.
As an example of why we can't just use Bincode, consider the strings "house" and "key". These should be sorted in alphabetical order: "house" before "key". However, Bincode encodes strings prefixed by their length, so "key" would be sorted before "house" in binary form:
03 6b 65 79 ← 3 bytes: key
05 68 6f 75 73 65 ← 5 bytes: house
For similar reasons, we can't just encode numbers in their native binary form: the little-endian representation will order very large numbers before small numbers, and the sign bit will order positive numbers before negative numbers. This would violate the ordering of natural numbers.
We also have to be careful with value sequences, which should be ordered element-wise. For example, the pair ("a", "xyz") should be ordered before ("ab", "cd"), so we can't just encode the strings one after the other like "axyz" and "abcd" since that would sort ("ab", "cd") first.
toyDB provides an order-preserving encoding called "Keycode" in the encoding::keycode
module. Like Bincode, the Keycode encoding is not self-describing: the binary data does not say what
the data type is, the caller must provide a type to decode into. It only supports a handful of
primitive data types, and only needs to order values of the same type.
Keycode is implemented as a Serde (de)serializer, which requires a lot of boilerplate code to satisfy the trait, but we'll just focus on the actual encoding. The encoding scheme is as follows:
bool: 00 for false and 01 for true.
u64: the big-endian binary encoding.
i64: the big-endian binary encoding, but with the
sign bit flipped to order negative numbers before positive ones.
f64: the big-endian IEEE 754
binary encoding, but with the sign bit flipped, and all bits flipped for negative numbers, to
order negative numbers correctly.
Vec<u8>: terminated by 00 00, with 00 escaped as 00 ff to disambiguate it.
String: like Vec<u8>.
Vec<T>, [T], (T,): the concatenation of the inner values.
enum: the variant's numerical index as a u8, then the inner values (if any).
Like encoding::Value, there is also an encoding::Key helper trait:
Different kinds of keys are usually represented as enums. For example, if we wanted to store cars and video games, we could use:
#[derive(serde::Serialize, serde::Deserialize)]
enum Key {
Car(String, String, u64), // make, model, year
Game(String, u64, Platform), // name, year, platform
}
#[derive(serde::Serialize, serde::Deserialize)]
enum Platform {
PC,
PS5,
Switch,
Xbox,
}
impl encoding::Key for Key {}
let returnal = Key::Game("Returnal".into(), 2021, Platform::PS5);
let bytes = returnal.encode();
println!("{bytes:02x?}");
// Outputs [01, 52, 65, 74, 75, 72, 6e, 61, 6c, 00, 00, 00, 00, 00, 00, 00, 00, 07, e5, 01].
//
// * Key::Game: 01
// * Returnal: 52 65 74 75 72 6e 61 6c 00 00
// * 2021: 00 00 00 00 00 00 07 e5
// * Platform::PS5: 01
let returnal = Key::decode(&bytes)?;
Because the keys are sorted in element-wise order, this would allow us to e.g. perform a prefix scan to fetch all platforms which Returnal (2021) was released on, or perform a range scan to fetch all models of Nissan Altima released between 2010 and 2015.