Struct RawMap 

pub struct RawMap { /* private fields */ }

A single shard’s key value map: bytes in, bytes out, nothing else.

Not Sync, and deliberately so. One of these is inside one stripe, and the lock around the stripe is what decides which thread has it, which is 05 section 1’s whole argument: one owner at a time means no atomics on the hot path.

let mut m = yo_index::RawMap::new();
assert_eq!(m.set(b"k", b"v"), None);
assert_eq!(m.get(b"k"), Some(&b"v"[..]));
assert_eq!(m.set(b"k", b"w").is_some(), true);
assert_eq!(m.get(b"k"), Some(&b"w"[..]));
assert_eq!(m.del(b"k"), true);
assert_eq!(m.get(b"k"), None);

Implementations

impl RawMap

pub fn new() -> RawMap

An empty map.

pub const fn compaction(&self) -> Compaction

What compaction has done to this map since it was made.

A running total and not a rate, so two reads either side of a load say what that load cost. See Compaction for what the three numbers are and why they are not one.

pub const fn writes(&self) -> u64

How many times this map has been written to.

Two reads of this with the same value either side of some work mean nothing in the map moved, so an address or a slot resolved before the first read is still the right one after the second. It never goes backwards, including across RawMap::clear.

pub fn len(&self) -> usize

How many keys are stored.

pub fn is_empty(&self) -> bool

Whether the map is empty.

pub fn clear(&mut self)

Throw everything away and give the memory back.

A fresh index and a fresh arena rather than a walk that deletes each key in turn. Deleting one at a time would leave an arena the size of the data that used to be in it and an index still grown to fit it, and the one thing a client that has just said FLUSHALL is entitled to expect is the memory back.

pub fn hash_of(key: &[u8]) -> u64

The hash this map files key under.

Public because the batch walk in 04 section 3 hashes on the first walk and looks up on the second, and the alternative is hashing every key twice to keep the seed a private detail.

pub fn prefetch(&self, hash: u64)

Ask the cache for the bucket hash will be looked up in.

pub fn get(&self, key: &[u8]) -> Option<&[u8]>

The value stored under key.

pub fn get_hashed(&self, hash: u64, key: &[u8]) -> Option<&[u8]>

The value stored under key, whose hash the caller already has.

The second walk’s entry point. hash has to be RawMap::hash_of of this key: a hash from somewhere else is not unsafe, it just misses.

pub fn find(&self, key: &[u8]) -> Option<Addr>

Where key’s record is, for a caller that has to look at it twice.

A GET has to know whether the key is past its deadline before it can answer, and then has to read the value it just decided about. Asking RawMap::get twice is two hashes and two probes for one record, and a probe is the expensive half of a command. This hands back the address instead, and RawMap::value_at reads it with no probe at all.

The address is good until the next write to this map. Anything that inserts, deletes or compacts can move a record, and an address held across one of those reads whatever is at that spot now. Hold it for the length of one command and no longer.

pub fn find_hashed(&self, hash: u64, key: &[u8]) -> Option<Addr>

RawMap::find for a caller that already hashed the key.

pub fn value_at(&self, addr: Addr) -> &[u8]

The value at an address this map handed out, with no probe.

See RawMap::find for how long an address is worth holding.

pub fn value_at_mut(&mut self, addr: Addr) -> &mut [u8]

The value at an address, to be overwritten in place, without counting as a write.

This is the one method taking a mutable borrow that leaves RawMap::writes where it was, and that is a deliberate exception to the rule stated on the counter rather than an oversight in it.

It is sound because nothing moves. The record already exists, the caller already holds its address, there is no allocation and no index write, so every address and every number read out of a record before the call is still right afterwards. That is a stronger guarantee than the counter is asking about, and it is one this method can actually make.

It exists because the conservative answer costs more here than it protects. The eviction clock is written back on nearly every read, under eight of the ten policies including the default, so counting it as a write would invalidate the caller’s memo on every single command rather than on every write. That is a measured nineteen nanoseconds a command on single key SADD, given up to avoid thinking once about three bytes written inside a record that is not going anywhere.

The length cannot change, for the same reason it cannot in RawMap::value_mut, and an address is only good until the next real write, for the same reason it is in RawMap::find.

pub fn value_mut(&mut self, key: &[u8]) -> Option<&mut [u8]>

The value stored under key, to be overwritten where it lies.

The length cannot change, which is the whole reason this is safe to offer. INCR on an integer encoded string is a probe, an add and a store, and the store is eight bytes back into the record it came from (08 section 2). Going through RawMap::set instead would write a fresh record and free the old one on every increment, which is an arena append and a dead byte per operation for a value whose size never moves.

There is no reader to tear. A map belongs to one shard thread and is not Sync, so the only code that can observe a half written value is the code doing the writing. When a replica stream or a snapshot reader starts walking the arena from another thread, this becomes an epoch question and the write becomes an install rather than an overwrite.

pub fn value_mut_hashed(&mut self, hash: u64, key: &[u8]) -> Option<&mut [u8]>

RawMap::value_mut for a caller that already hashed the key.

pub fn set(&mut self, key: &[u8], val: &[u8]) -> Option<usize>

Store val under key, returning the length of the value it replaced.

pub const fn max_record() -> usize

The largest record this map can store, key and value and header together.

A value past this belongs in the log region rather than the arena, which is 06 section 2’s business and not this crate’s.

pub const fn header_len() -> usize

Bytes of record header in front of the key.

pub fn set_with<P, F>( &mut self, key: &[u8], vlen: usize, peek: P, fill: F, ) -> Option<usize>

where P: FnOnce(&[u8]), F: FnOnce(&mut [u8]) -> bool,

Store a vlen byte value under key, written by fill.

The same thing RawMap::set does, except that the caller writes straight into the record instead of building the value somewhere else first and having it copied in. A string with a one byte encoding tag in front of it would otherwise be assembled in a scratch buffer and then memcpy’d again, and two copies for one SET is one too many on a path that is trying to be ten times faster than Redis.

fill is handed exactly vlen bytes of uninitialised-looking storage. It is arena memory that has been handed out before and freed, so its contents are arbitrary and every byte of it must be written. What it answers is whether this record should be marked, which is what RawMap::sample_tagged later draws from. A caller with no use for that answers false and pays a branch.

peek is handed the value that was already under key, if there was one, before anything is written over it. It exists because the caller keeps counts that depend on what the old value was, and this is the only place those bytes can be read for free: both paths through here have already loaded the old record’s header to find out how long it is, so the value is in cache and would otherwise cost a second lookup to see. A caller with nothing to ask passes an empty closure and pays nothing.

Panics

If the whole record would exceed RawMap::max_record.

pub fn del(&mut self, key: &[u8]) -> bool

Remove key, returning whether it was there.

pub fn del_with<P: FnOnce(&[u8])>(&mut self, key: &[u8], peek: P) -> bool

Remove key, showing its value to peek first, and return whether it was there.

The sibling of RawMap::set_with, and it exists for the same reason. This already reads the record’s header to find out how long it is before handing the bytes back to the arena, so the value is in cache and a caller who keeps a count that depends on what was removed can read it here for the price of a closure call. Asking with a RawMap::get first would be a second lookup for a question this one already knows the answer to. peek is not called when the key was not there.

pub fn contains(&self, key: &[u8]) -> bool

Whether key is present.

pub fn entry_at(&self, addr: Addr) -> (&[u8], &[u8])

The key and the value at an address this map handed out.

The pair rather than either one alone, because they are one contiguous read: the header says how long the key is and the value starts where the key ends, so asking for both costs what asking for one costs.

pub fn scan( &self, from: Cursor, budget: usize, out: impl FnMut(&[u8], &[u8]), ) -> Cursor

Walk a batch of the map, and say where the next batch starts.

This is SCAN. budget is how many entries the caller would like, and it is a floor and not a ceiling: the walk stops at the first bucket boundary past it, so a batch of ten can come back with fifteen. Redis’s COUNT behaves the same way and for the same reason, which is that a bucket is the smallest unit a cursor can name.

A budget of zero still does one bucket, so a caller that keeps passing the cursor back always finishes rather than spinning on the same number.

The guarantee, in full: a key that is present for the whole walk is handed to out at least once. A key added or removed partway through may or may not appear, and a key may appear twice. The reasoning is in Cursor, and the part worth knowing here is that none of it depends on the map holding still between calls.

pub fn sample(&self, r: u64, out: impl FnMut(&[u8], &[u8], Addr) -> bool)

Entries picked at random, for eviction sampling, until out says stop.

The key, the value and the address of each, because a caller choosing a victim needs all three: the value to score it, the key to delete it, and the address to delete it by without a second probe. out answers whether to keep going. Index::sample is where the argument for all of it lives, including why the budget is the caller’s and why this can hand back nothing at all.

pub fn index(&self) -> &Index

The index, for stats and for compaction.

pub fn arena(&self) -> &Arena

The arena, for stats and for compaction.

pub fn memory_bytes(&self) -> usize

Bytes held by index structure plus arena segments.

pub fn tagged_len(&self) -> usize

How many records are marked.

Exact, and kept exact by every write path, so a caller can branch on a zero here rather than starting a sweep that was never going to find anything.

pub fn is_tagged(&self, addr: Addr) -> bool

Whether the record at addr is marked.

For a test and for a debug assertion. Nothing on a hot path asks this: the mark is written from the record’s own bytes, so anything holding the record already knows.

pub fn sample_tagged(&self, r: u64, out: impl FnMut(&[u8], &[u8], Addr) -> bool)

Walk marked records from wherever r lands, until out says stop.

RawMap::sample for the marked subset, and the reason the subset exists. A database of ten million keys where a thousand carry a deadline gives the expire cycle a thousand candidates to draw from instead of ten million, and the cycle stops costing anything at all in the case that matters most, which is the one where the answer is that there is nothing to do.

pub fn compact_segment(&mut self, seg: usize) -> usize

Move every live record out of seg and into the current segment, then put the segment back on the arena’s free list.

Copy, rewrite the index entry, done. No forwarding pointers and no read barrier, which is the F2 shape from 05 section 3.2 and is what an allocation having exactly one referent buys.

The walk is over the segment and not over the index. Both find the same records, and the index walk is the one written in the spec, but it reads the whole index to compact two megabytes: fine when this only ran in a test, wrong once the event loop calls it, because the pause would then grow with the size of the database rather than with the size of a segment. Walking the segment costs one index probe per record in it and does not care how many keys exist elsewhere.

Records sit back to back from the header to the segment’s bump, each one rounded up to the arena’s alignment, and every arena allocation is a record, so the next one is always a known distance away. A record is live when the index still points at this copy of it, and dead when it points somewhere else or at nothing, which is exactly what an overwrite and a delete leave behind.

The reclaim at the end is the part that makes the space usable again. Moving the records out only makes a segment empty, and an empty segment that nothing ever bumps through again is still two megabytes the process is holding.

pub fn compact_step(&mut self) -> Option<usize>

Do one bounded slice of compaction, and say how many records moved.

None means there was no candidate and there is nothing in flight. It is not the same as Some(0), which is a slice that walked only records that had already been overwritten: that one made progress and cost something, and a caller deciding whether to go round again needs to be told so.

This is the whole maintenance contract: a bounded amount of work per call, so a caller that runs it once per batch never pays for a full pass over the arena and never pays for a whole segment either. Finding out there is nothing to do is one comparison against the running dead byte total.

A segment takes as many calls as it takes. Each one picks up where the last stopped and only the call that reaches the end gives the two megabytes back, so the space comes back in one lump at the end while the cost of getting it back is spread over the batches in between. That is the trade: a segment stays around a little longer than it used to, and no single command waits for the whole of it.

The segment in flight is finished before another is chosen, rather than asking which segment is worst on every call. Otherwise a segment that is three quarters evacuated could be put down in favour of a worse one and never picked up, and the arena would fill with segments that are nearly empty and never reclaimed.

pub fn compact_hard(&mut self) -> Option<usize>

One slice of compaction for a store that has run out of room.

The same work, choosing between segments the way Arena::any_candidate chooses rather than the way Arena::worst_candidate does, so a store that is clean overall still collects the parts of it that are not. The reason is written on any_candidate.

A segment already in flight is finished first either way, so switching between this and RawMap::compact_step cannot leave a segment half evacuated forever.

Trait Implementations

impl Default for RawMap

fn default() -> RawMap

Returns the “default value” for a type.