Crate ordcode

A set of primitives and Serde serializers for fast, prefix-free encoding which preserves lexicographic ordering of values.

It is intended for encoding keys and values in key-value databases.

OMG! Yet another serialization format?

In most existing designs, prefix-free encoding of byte sequences is performed by escaping “end-of-sequence” bytes. This takes extra space, and makes it difficult to know sequence length without processing the whole input buffer; this also complicates memory allocation for deserialized data. Instead, we take advantage of the fact that exact record size is always known in key-value databases. This implementation relies on “two-sided” buffer design: sequence lengths are varint-encoded and pushed to the tail end of the buffer, so it is possible to get original length of serialized byte sequence(s) by deserializing a few bytes only. For serialization, this implementation provides (very fast) calculation of exact size of serialized data length before serialization itself. These features enable effective and predictable buffer management for repetitive scans and no-heap (#[no-std]) targets.

Features

• encodings in both ascending and descending lexicographic orderings are supported
• encoding puts lengths of variable-size sequences to the end of serialized data, so resulting encoding is prefix-free and friendly to lexicographic ordering
• zero allocations, supports #[no_std] environments
• method to cheaply get exact size of serialized data without doing actual serialization, for effective buffer management
• space-efficient varint encoding for sequence lengths and discriminants
• easily customizable (endianness, encoding of primitive types etc.), with useful pre-sets
• reader/writer traits for double-ended buffers, so you can implement your own or use implementations provided by the crate
• no unsafe code

Cargo.toml features and dependencies

• serde (on by default): include serde serializer and deserializer. If you need only primitives, you can opt out.
• std (on by default): opt out for #[no-std] use, you will lose some convenience methods which use Vec<u8>

Stability guarantees

The underlying encoding format is simple and unlikely to change. As a safeguard, Serializer and Deserializer implement FormatVersion trait for all serializer parameter pre-sets (params::AscendingOrder, params::PortableBinary, params::NativeBinary).

Note: serializing with descending lexicographic order is particularly useful for key-value databases like rocksdb, where reverse iteration is slower than forward iteration.

Re-exports

pub use buf::DeBytesReader;

pub use buf::DeBytesWriter;

pub use buf::ReadFromTail;

pub use buf::WriteToTail;

Modules

buf

Types and traits for working with serialization and deserialization buffers

bytes_esc

Prefix-free encoding and decoding of byte sequences, with escaping

params

Serialization parameters traits and types

primitives

Ordered serialization/deserialization for primitive types and byte arrays.

varint

Fast variable length serialization of unsigned integers with VarUInt trait.

Structs

Deserializer

serde deserializer for binary data format which may preserve lexicographic ordering of values

Serializer

serde serializer for binary data format which may preserve lexicographic ordering of values

SizeCalc

Serialized object size calculator

Enums

Error

Serialization and deserialization errors

Order

lexicographic ordering for serialization

Traits

FormatVersion

Current version of data encoding format for Serializer parametrized with some params::SerializerParams.

Functions

calc_size

Calculate exact size of serialized data for a serde::Serialize value.

calc_size_asc

Convenience method: same as calc_size(), with params::AscendingOrder

de_from_bytes_asc

Deserialize value from byte slice with params::AscendingOrder

de_from_bytes_ordered

Deserialize value from mutable byte slice.

new_de_asc

Create new default deserializer instance (with params::AscendingOrder)

new_ser_asc

Create new default serializer instance (with params::AscendingOrder)

ser_to_buf_asc_exact

Serialize value into pre-allocated, exact size byte buffer

ser_to_buf_ordered

Serialize value into pre-allocated byte buffer.

ser_to_vec_ordered

Serialize value into byte vector

Type Aliases

Result

A convenient Result type