Crate yo_kv 

The Redis data structures, as plain Rust types with no protocol attached.

This crate is the answer to a question the design keeps asking: where does INCR actually live. It does not live in the codec, because an embedded caller never speaks RESP and should not have to. It does not live in the typed API either, because the wire has to reach the same code the typed API reaches, or there are two implementations of INCR and one of them is wrong (Y23). So it lives here, one method per command, taking and returning ordinary Rust values, with yo-resp above it turning frames into calls and the typed API above it turning generics into calls.

What that buys is worth being clear about. An embedded program calls Keyspace::incr and gets an i64 or a yo_common::Error. It does not serialise a command, it does not cross a socket, and it does not parse a reply. That is the whole point of P1 and it is why the sub 150 nanosecond number in bench/00 is measured through here and not through a client.

What is here so far

The string type, which is the first row of M2, and all 26 of its commands.

The hash, in both of its representations and with field TTL, which is the HEXPIRE family and the third answer OBJECT ENCODING can give.

The bitmaps, which are the same string values seen a bit at a time. bits is the kernels, popcount and scan and the eight ways of combining two bitmaps and the packed integer fields, and bitmaps is where a key turns into bytes and where Redis’s edges are kept. There is no bitmap type, because in Redis there is not one either: SET k A then GETBIT k 1 answers one.

The HyperLogLogs, which are those same string values again with a documented layout inside them. hll is the sketch, the hash and the two representations and Ertl’s estimator, and hlls is where a key turns into one. It is byte for byte Redis’s format, on purpose: a client can GET a sketch out of a real server and SET it into us, and it has to count the same, so the hash function and the opcodes and the promotion threshold are copied rather than improved on.

The places, which are sorted sets seen as a map. geo is the arithmetic, the 52 bit interleave of longitude and latitude that a score is, the haversine, the eleven character geohash string and the boxes a search covers, and geos is where a key turns into a search. There is no geo type either, for the same reason there is no bitmap one: GEOADD writes a member with a score and ZSCORE reads that score straight back out, so a place is a sorted set entry that somebody has agreed to read as a coordinate. What the search costs is nine score ranges, one for the box the centre falls in and one for each neighbour, at a precision picked so the nine cover the shape, and every candidate is measured properly afterwards so nothing outside the circle or the rectangle reaches the caller.

The set, which is the first row of M3, in all seventeen of its commands: SADD, SREM, SCARD, SISMEMBER, SMISMEMBER, SMEMBERS, SPOP, SRANDMEMBER, SSCAN, SMOVE, SINTER, SINTERCARD, SUNION, SDIFF and the three store forms. A Set is one of three representations and moves between them on the same rules Redis uses, with OBJECT ENCODING saying which one it is on and the five CONFIG thresholds moving the lines. Keyspace is where a key gets to be something other than a string: the record holds a number, the number points into a Slab, and every path that deletes a key or writes over one frees what it was pointing at. That last part is why WRONGTYPE exists as of this milestone. There was no way to trigger it while a string was all there was.

Lists, hashes and the sorted set follow the same shape and land in M3 too.

orderkey is the allocator that decides what sort key a list element gets, which is the piece that stops LINSERT from renumbering everything behind the element it inserted. It is the variable width scheme Y19 settles on, it reproduces K14’s eight inserts per byte, and like aki’s own first slice of this it ships proven and wired to nothing: the representation that stores a list by key rather than by position is the partitioned band below, and the wiring is a later piece of M4 than either of them.

Parts is the partitioned band, which is what a collection becomes once it is too large to be one element table. It is P tables with a member’s partition taken out of its hash, and in front of them the descriptor cache 05 calls mandatory, which is what lets an operation know how the elements are spread without adding up all P of them. What partitioning is really for is the merge, the growth and the reclaim, none of which want to touch a million element table at once. The cache turned out not to be the locality problem it reads as, and benches/parts.rs has the measurement and the module doc has the argument.

The pieces of M3 that are here already are the ones every collection shares. Elements is the element table a hash, a set and a sorted set are all built out of, and Cursor is the scan cursor they all hand back to a client. Neither is a set or a hash on its own, and both are where the decisions that make those fast were made.

Listpack is the band underneath both of them. A collection of a few dozen elements does not want an index at all, so up to a hundred and twenty eight it is one packed blob walked linearly, in Redis’s own byte layout so that an RDB export is a copy and OBJECT ENCODING can honestly say listpack.

The four commands Redis added in 8.4 and 8.8 are the interesting ones and they were checked against a real 8.8 rather than written from the documentation. Keyspace::digest is the XXH3 of a value, and it is bit for bit Redis’s number, which is what makes Compare::DigestEqual worth anything: a client comparing against a large value sends eight bytes instead of the value. Keyspace::increx is not the rate limiter it looks like at first, it is a counter with a bound, a saturation policy and four things it can do to the deadline, and the rate limiter is one setting of it.

Divergences

Four, all recorded in divergences.toml rather than left to be discovered.

A string is capped at strings::STRING_MAX rather than Redis’s 512 MiB, because a value lives in one arena segment until the log backed band lands in M5. Expiry is lazy only: a key past its deadline is dropped when something touches it, and the active cycle that would reclaim a key nobody ever touches again is maintenance slice work in M5. And LCS refuses a table over LCS_MAX_CELLS, where Redis has no explicit limit and fails on the allocation instead, which on a server that has overcommitted is a kill rather than an error. And the float counters count in f64 where Redis counts in the C long double, which is eighty bit on x86-64 and a hundred and twenty eight bit on aarch64, so Redis does not agree with itself across machines and we agree with ourselves everywhere.

Re-exports

pub use array::Array;

pub use array::Element as ArrayElement;

pub use array::INDEX_MAX;

pub use array::SLICE_SIZE;

pub use blob::Blob;

pub use blob::Span;

pub use clock::Clock;

pub use cond::Compare;

pub use counter::Counted;

pub use counter::IncrEx;

pub use counter::IncrExpire;

pub use counter::Num;

pub use db::Db;

pub use db::Holds;

pub use db::MAX_STRIPES;

pub use elem::Elements;

pub use elem::Full;

pub use elem::MAX_ROWS;

pub use elem::NAME_MAX;

pub use foreign::Foreign;

pub use hash::Hash;

pub use hash::Limits as HashLimits;

pub use intset::Intset;

pub use intset::Walk;

pub use keys::Moved;

pub use keys::Record;

pub use keyspace::Keyspace;

pub use lcs::Idx as LcsIdx;

pub use lcs::LCS_MAX_CELLS;

pub use lcs::Match as LcsMatch;

pub use list::Limits as ListLimits;

pub use list::List;

pub use listpack::Entry;

pub use listpack::Listpack;

pub use listpack::Malformed;

pub use lists::End;

pub use lists::Movem;

pub use lists::Order;

pub use parts::PART_MIN;

pub use parts::PARTITION_AT;

pub use parts::Parts;

pub use rank::Rank;

pub use scan::Cursor;

pub use scan::MAX_PARTS;

pub use set::Limits as SetLimits;

pub use set::Member;

pub use set::Set;

pub use setops::Plan;

pub use slab::MAX_SLOTS;

pub use slab::Slab;

pub use snapshot::Snapshot;

pub use strings::Exists;

pub use strings::Expire;

pub use strings::KEY_MAX;

pub use strings::STRING_MAX;

pub use strings::SetOptions;

pub use strings::SetOutcome;

pub use ttl::Applied;

pub use ttl::Ask;

pub use ttl::Cond;

pub use ttl::Deadlines;

pub use ttl::MAX_AT;

pub use value::EMBSTR_MAX;

pub use value::Encoding;

pub use value::Kind;

pub use value::Str;

pub use zset::Bound as ZBound;

pub use zset::Lex;

pub use zset::Limits as ZsetLimits;

pub use zset::Zset;

pub use zsetops::Aggregate;

pub use zsetops::Op as ZOp;

pub use zsetops::Operand;

pub use zsets::By;

pub use zsets::Gate;

pub use zsets::Move;

pub use zsets::Query;

pub use zsets::Window;

pub use zsets::ZAdd;

pub use zsets::From as ZEnd;

Modules

access

How recently a key was used, and how often, in twenty four bits.

array

A sparse array: a sequence indexed by a u64, with holes.

arrays

The array commands.

bitmaps

The bitmap commands, which are string commands wearing a different hat.

bits

Bit level kernels: counting, searching, combining and packed fields.

blob

Variable length bytes belonging to one collection, back to back.

chunk

A run of packed elements with a cursor at each end.

clock

The coarse clock expiry compares against.

cold

A value that is too big to hold, cut into chunks that are addressed rather than walked.

cond

The conditional write comparisons Redis 8.4 added.

counter

INCREX, which is a counter with a policy attached.

db

One database, cut into stripes.

demote

Choosing which entry leaves memory next.

elem

The element table, which is what a hash, a set and a sorted set are all made of underneath.

evict

Choosing which key to throw away.

expiry

The active expiry cycle, which is what reclaims a key nobody asks for again.

foreign

A body this crate holds without knowing what it is.

frozen

The bytes a collection body turns into on its way out of memory.

geo

The geohash arithmetic, which lives one crate down so that the search index and the geo commands cover a circle in exactly the same way. The geospatial kernels, which are Redis’s geohash arithmetic.

geos

The geospatial commands.

grow

How the arrays underneath a collection get bigger.

hash

A hash, in whichever of the two representations currently fits it.

hashes

The hash commands.

hll

The HyperLogLog sketch, byte for byte the one Redis writes.

hlls

The HyperLogLog commands, which are string commands over a documented value.

intset

A set of integers as sorted packed arrays, which is Redis’s intset in runs.

keys

Moving a key, copying one, and touching one.

keyspace

One database, and the parts of it that are not about any particular type.

lcs

LCS, the longest common subsequence of two strings.

list

A list, in whichever of the two representations currently fits it.

listpack

The inline band: one packed blob, walked linearly.

lists

The list commands.

lookups

Whether the lookups happening on this thread are a client reading a key.

news

Telling somebody what happened to a key when no command reported it.

orderkey

Order keys for a list, so that an insert between two elements never has to move a third one.

parts

The partitioned band: one collection held as several element tables, with a two level summary of their lengths in front so that finding the one that owns a given position is not a walk over all of them.

rank

A counted B+ tree, which is the ordered index a sorted set ranks with.

rdb

The RDB payload that DUMP hands out and RESTORE takes back.

scan

The scan cursor, and what it has to survive.

set

A set, in whichever representation currently fits it.

setops

Set algebra, and the choice between probing and merging.

sets

The set commands.

slab

Somewhere to keep a value that is not bytes, addressed by a small number.

snapshot

A whole dataset written out as one RDB file.

sort

SORT and SORT_RO, the one keyspace command that reads keys nobody named.

stream

A stream, as a log of listpack nodes in ID order (08 section 7).

streams

The stream commands.

strings

The string type and its commands.

tier

Moving a value out to the file and getting it back, which is WiscKey’s idea with the tag from 06 section 6 doing the bookkeeping.

ttl

Deadlines on individual fields, which is the HEXPIRE family.

value

How a string value sits in a record, and what comes back out of one.

walk

Walking the keyspace: SCAN, KEYS and RANDOMKEY.

zset

A sorted set: an element table for the score of a member, and a counted tree for the rank of a score.

zsetops

Sorted set algebra, and how a result gets into order without a descent per member.

zsets

The sorted set commands.

Structs

Compaction

What compaction has done to a map over its life.

KeyCursor

How far a scan has got, and the number the client holds between calls.