---
marp: true
---
# [Columnar](https://github.com/frankmcsherry/columnar)
High-throughput columnar serialization in Rust
[`https://github.com/frankmcsherry/columnar`](https://github.com/frankmcsherry/columnar)
Frank McSherry
---
## Intro: I am Frank
I have done many Rust things.
This was the first thing I published in Rust (10+ years ago).
---
## Sequences of complex data types
Imagine some non-trivial types you have many of, and would like to efficiently maintain.
```rust
enum Group<T> {
Solo(T),
Team(Vec<T>),
Void,
}
struct Person {
name: String,
age: u8,
}
```
You could use `Vec<Group<Person>>`. You *should* start with `Vec<Group<Person>>`!
There are some reasons you might not want to, though.
We're going to dial in some significant performance, for some specific use cases.
---
## Cloudflare Benchmark ("goser" via Erick Tryzelaar)
```rust
impl Log {
pub fn new() -> Log {
Log {
timestamp: 2837513946597,
zone_id: 123456,
zone_plan: ZonePlan::FREE,
http: Http {
protocol: HttpProtocol::HTTP11,
status: 200,
host_status: 503,
up_status: 520,
method: HttpMethod::GET,
content_type: "text/html".to_owned(),
user_agent: "Mozilla/5.0 (X11; Linux x86_64) ...
referer: "https://www.cloudflare.com/".to_owned(),
request_uri: "/cdn-cgi/trace".to_owned(),
},
origin: Origin {
ip: "1.2.3.4".to_owned(),
port: 8000,
...
}
}
```
---
## Cloudflare Benchmark ("goser" via Erick Tryzelaar)
| `Log::new()` | 407,710 | | expensive |
| `push_clone` | 444,288 | | expensive |
| `push_columnar` | 49,624 | 7,392 | |
| `encode_bincode` | 50,289 | 7,656 | |
| `encode_columnar` | 6,980 | 52,558 | `memcpy` |
| `decode_bincode` | 531,051 | 725 | expensive |
| `decode_columnar` | 50 | 7,337,120 | zero-copy |
---
## A Transformation via Structural Recursion
We are going to transform `Vec<T>` into a few `Vec<_>`s over "simpler" types than `T`.
1. **Primitive types**. `u8, .., u128`, `i8, .., i128`, `f32, f64`, `()`.
This is our base case; these will stay as `Vec`.
2. **Product types**. User structs, tuples, enum variants with data, ...
`Vec<(A, .., Z)>` turns in to `(Vec<A>, .., Vec<Z>)`. ([AoS to SoA](https://en.wikipedia.org/wiki/AoS_and_SoA))
3. **Sum types**. User enums, `Option`, `Result`, ...
`Vec<Enum>` turns in to `(Vec<Tag>, Vec<Var0>, .. Vec<VarK>)`.
4. **List types**. `Vec` itself, `String`, boxed slices, maps, ...
`Vec<Vec<T>>` turns in to `(Vec<usize>, Vec<T>)` of bounds and values.
---
## Trade-offs: Primitive Types
I mean, none really. Let's unpack some benefits instead.
Everywhere I said `Vec<_>` for primitive types I *also* meant `&[_]`.
For the listed primitive types, you can go to and from `&[u8]` at zero cost, if aligned.
This enables zero-copy de-serialization. E.g. bouncing in to, out of WASM, `mmap`.
---
## Trade-offs: Product Types (SoA to AoS)
Recall: `Vec<(A, B, C)>` turns in to `(Vec<A>, Vec<B>, Vec<C>)`.
### Bad news:
1. References `&(A, B, C)` turn in to `(&A, &B, &C)`. Can be fatal.
2. Row locality; inserting `(a, b, c)` writes at three different locations.
### Good news:
1. Dense packing: `((u64, u8), u8)` takes 6 bytes per entry, not 24.
2. Column locality: scanning `Vec<A>` can be faster than `Vec<(A, B, C)>`. SIMD.
3. Can cheaply *reshape* as `(A, (B, C))` or `(C, A)`, or `(A, B, C, D)`.
---
## Trade-offs: Sum Types
Recall: `Vec<Result<S, T>>` turns in to `(Vec<bool>, Vec<S>, Vec<T>)`.
### Bad news:
1. References `&Result<S, T>` turn in to `Result<&S, &T>`. Can be fatal.
2. Without some thinking, random access seems harder (hold that thought).
3. Conditional logic on the random access look-up path (sequenced memory accesses).
4. In-place mutation seems unlikely (cannot change the variant easily).
### Good news:
1. Dense packing again. `Result<(), Error>` only needs space for errors.
2. Reshaping: can demux into `Vec<R>` and `Vec<S>` very cheaply. Bulk `.unwrap()`.
3. [Succinct data structures](https://en.wikipedia.org/wiki/Succinct_data_structure) get random access with teensy memory, some computation.
---
## Trade-offs: List Types
Recall: `Vec<Vec<T>>` turns in to `(Vec<usize>, Vec<T>)`.
### Bad news
1. References `&Vec<T>` turn in to "`&[T]`". Shrug.
2. Can't modify, take the allocation.
### Good news
1. No per-element allocations.
2. Per element overhead at most one `usize`. Can get smaller.
3. Reshaping again: the `flatten()` operation is essentially free.
---
## Traits: `Push`
Hat tip to Moritz Hoffmann for the `Push<T>` framing; very general.
```rust
/// A type that can accept items of type `T`.
pub trait Push<T> {
/// Pushes an item onto `self`.
fn push(&mut self, item: T);
}
```
```rust
// Blanket `Push` implementation for pairs.
impl<A, CA, B, CB> Push<(A, B)> for (CA, CB)
where
CA: Push<A>,
CB: Push<B>,
fn push(&mut self, (a, b): (A, B)) {
self.0.push(a);
self.1.push(b);
}
```
---
## Traits: `Index`
You might have expected GATs here (I did). They will show up later.
```rust
/// A type that can be accessed by `usize` but without borrowing `self`.
pub trait Index {
/// The type returned by the `get` method.
type Ref;
/// Returns a reference of the indicated type.
fn get(&self, index: usize) -> Self::Ref;
}
```
```rust
// Blanket `Index` implementation for pairs.
impl<CA: Index, CB: Index> Index for (CA, CB) {
type Ref = (CA::Ref, CB::Ref);
fn get(&self, index: usize) -> Self::Ref {
(self.0.get(index), self.1.get(index))
}
}
```
---
## Traits: `AsBytes<'a>` and `FromBytes<'a>`
Allow efficient translation to and from, respectively, correctly aligned byte slices.
```rust
/// A type that can be viewed as byte slices with lifetime `'a`.
pub trait AsBytes<'a> {
/// Presents `self` as a sequence of byte slices, with their required alignment.
fn as_bytes(&self) -> impl Iterator<Item=(u64, &'a [u8])>;
}
```
```rust
/// A type that can be reconstituted from byte slices with lifetime `'a`.
pub trait FromBytes<'a> {
/// Reconstructs `self` from a sequence of correctly aligned and sized bytes slices.
fn from_bytes(bytes: &mut impl Iterator<Item=&'a [u8]>) -> Self;
}
```
---
## Traits: `Columnar`
Finally! A type that can be columnarized, and its opinions about related types.
```rust
/// A type that can be represented in columnar form.
pub trait Columnar : 'static {
/// For each lifetime, a reference with that lifetime.
type Ref<'a>;
/// Produce an instance of `Self` from `Self::Ref<'a>`.
fn into_owned<'a>(other: Self::Ref<'a>) -> Self;
/// The type that stores the columnar representation.
type Container : Len + Clear + Default
+ for<'a> Push<&'a Self>
+ for<'a> Push<Self::Ref<'a>>
+ Container<Self>;
}
```
---
## Traits: `Container<C: Columnar>`
A bundle of opinions about borrowed forms of an owning container.
```rust
/// A container that can hold `C`, and provide its preferred references.
pub trait Container<C: Columnar + ?Sized> {
/// The type of a borrowed container.
type Borrowed<'a> : Copy + Len
+ AsBytes<'a>
+ FromBytes<'a>
+ Index<Ref = C::Ref<'a>> where Self: 'a;
/// Converts a reference to the type to a borrowed variant.
fn borrow<'a>(&'a self) -> Self::Borrowed<'a>;
}
```
---
## Bonus: `#[derive(Columnar)]`
The patterns we've seen up above apply to user `struct` and `enum` (sorry `union`).
```rust
#[derive(Columnar)]
enum Group<T> {
Solo(T),
Team(Vec<T>),
Void,
}
#[derive(Columnar)]
struct Person {
name: String,
age: u8,
}
```
---
## Bonus: Adaptive Dictionary Encoding
Recall `Result<S, T>` as `(Vec<bool>, Vec<S>, Vec<T>)`.
Each position `index` can be directed to the corresponding `S` or `T`, based on its variant.
It could *also* be directed to the *other* variant that was most recent when it was inserted.
Let's think about storing a sequence of `T` using a `Result<T, u8>`, where
1. `Ok(item)` corresponds to an inserted item.
2. `Err(back)` indicates to look `back` steps backwards through the `Ok` values.
At insertion, we look for `item` in the previous `256` distinct insertions (the `Ok`s).
If we find it, we only spend a `u8`, plus a bit, instead of a whole `T`.
Great for JSON object key compression.
---
## Bonus: JSON
Self-referential. Both `Array` and `Object` variants may contain `Json`.
```rust
/// Stand in for JSON, from `serde_json`.
pub enum Json {
Null,
Bool(bool),
Number(serde_json::Number),
String(String),
Array(Vec<Json>),
Object(Vec<(String, Json)>),
}
```
Instances of `Json` turn in to `usize`, and .. it mostly kinda works out.