Struct Index 

pub struct Index { /* private fields */ }

The shard’s index.

Implementations

impl Index

pub fn new() -> Index

A new index with one segment.

pub fn len(&self) -> usize

How many entries the index holds.

pub fn is_empty(&self) -> bool

Whether the index holds nothing.

pub fn segment_count(&self) -> usize

How many segments exist.

pub fn global_depth(&self) -> u8

The current global depth.

pub fn splits(&self) -> u64

How many segment splits have happened over the life of this index.

pub fn doublings(&self) -> u64

How many times the directory has doubled.

pub fn memory_bytes(&self) -> usize

Bytes of index structure, for INFO memory.

pub fn prefetch(&self, hash: u64)

Ask the cache for the bucket hash is going to land in.

The first of the two walks in 04 section 3. It costs one instruction, it reads nothing, and it is the difference between a batch of 64 lookups paying 64 serial cache misses and paying them overlapped. Only the first bucket is asked for: the directory entry and the segment header are on the way to it anyway, and an overflow bucket is a 1 in a few hundred event that is not worth a second hint.

Calling this and then never doing the lookup is allowed and wastes a little bandwidth. Calling it with a hash from a different key is also allowed and does the same, which is the whole reason a hint is a hint.

pub fn get<K: Keys>(&self, hash: u64, key: &[u8], keys: &K) -> Option<Addr>

Find the address stored under key.

The hot path, and the one M0’s four nanosecond gate measures. One load of the bucket, one SWAR compare of seven tags, and a key comparison per surviving match, which is one comparison in the overwhelming majority of probes because a tag collision is a 1 in 256 event.

pub fn contains<K: Keys>(&self, hash: u64, key: &[u8], keys: &K) -> bool

Whether key is present.

pub fn insert<K: Keys>( &mut self, hash: u64, key: &[u8], addr: Addr, keys: &K, ) -> Option<Addr>

Insert or replace the address stored under key.

Returns the address that was there before, if any. The caller owns what that address points at, so freeing it is the caller’s job. The index does not know how big a record is and will not guess.

pub fn remove<K: Keys>( &mut self, hash: u64, key: &[u8], keys: &K, ) -> Option<Addr>

Remove key.

Returns the address that was stored, if any. Tombstone free: the tag goes back to zero. A probe stops at the first empty tag in the chain rather than in the bucket, so nothing has to be pulled back.

pub fn addresses(&self) -> impl Iterator<Item = Addr> + '_

Every address in the index, in no particular order.

For compaction, which walks the index rather than the arena because an allocation has exactly one referent and that referent is an index entry (05 section 3.2).

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

Addresses from one segment picked at random, until out says stop.

Eviction does not need a fair sample and it cannot afford a real one. It needs a handful of keys that are not correlated with each other, quickly, and it runs again in a moment if the handful was a bad one. Redis picks a random slot in its table and takes a run of consecutive ones from there. This is the same idea against a different shape: one segment, then a run of consecutive buckets from a random start inside it.

r is one draw from the caller’s generator and both coordinates come out of it, the segment from the top half and the bucket from the bottom. Splitting one number rather than asking for two is worth it because this is called in a loop and the generator is the same one SPOP uses.

The segment is picked uniformly rather than by walking in from a random prefix, and that is the whole reason this is not just Index::scan from a made up cursor. A prefix picked uniformly lands in a segment in proportion to how much of the prefix space that segment covers, and a segment that has never split covers a great deal of it while holding no more keys than any other. Sampling that way would look at the keys in shallow segments over and over and barely ever look at the rest. Segments all split at the same fullness, so picking between them evenly is close to picking between keys evenly, which is as close as this needs to get.

Walking forward through the segment rather than stopping at the first bucket is what makes this work on a sparse map. A bucket holds seven entries and a segment holds sixty four buckets, so a database with two keys in it has two buckets that are worth looking in and sixty two that are not, and a sampler that gave up after one would come back with nothing almost every time. Walking on costs nothing when the map is full, because the first bucket already answers.

How many it hands over is the caller’s decision and not an argument, which is what out answering false is for. A count here would be the wrong number: the caller is filtering, and under a volatile policy on a database of mostly permanent keys it may have to look at forty of them to find five it can use. Counting entries handed over rather than entries kept would stop the walk at the first bucket and report that there is nothing to evict, on a database that has plenty.

The bound is the segment. Whatever the caller does, this looks in each of the sixty four buckets at most once and then stops, so a caller that never says stop still terminates. It can hand back nothing, when the segment it picked is empty, and the caller decides whether that is worth another draw.

pub fn scan(&self, from: Cursor, out: impl FnMut(Addr)) -> Cursor

Walk one bucket and its overflow chain, and say where to go next.

This is the step Cursor exists for, and the reasoning behind the number it hands back is in that module rather than here. The short of it is that the walk goes in increasing prefix order, a segment covers a contiguous run of prefixes, and a key’s prefix is a function of its hash and does not change when the directory doubles or a segment splits.

One bucket a call and not one segment, because a segment is 64 buckets and up to 448 entries, and a client that asked for ten of them should not get all of those in one reply. The caller decides how many steps make a batch.

A cursor a client made up resumes at whatever it points at, which is what Redis does. The alternative is remembering every cursor ever handed out.

pub fn relocate<K: Keys>( &mut self, hash: u64, key: &[u8], to: Addr, keys: &K, ) -> bool

Replace the address of an entry that is being moved by compaction.

Since the shard owns both the arena and the index, rewriting an index entry is a store, which is the whole reason compaction is affordable.

Trait Implementations

impl Debug for Index

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl Default for Index

fn default() -> Index

Returns the “default value” for a type.