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 Definitions

Result

A convenient Result type