Module array_route 

Routing bucket and vShard of an array tile.

A tile key orders tiles on a space-filling curve, so its top bits carry little entropy when tile indices are small. Routing therefore takes the top bits of a bijective mix of the key. Stored keys stay unchanged. The cluster router, the Data Plane shard filter and the snapshot paths use these functions, so a tile has one bucket and one vShard everywhere.

The router uses at most VShardId::BITS bucket bits. Bucket b of R routing bits owns the vShards [b * stride, (b + 1) * stride), with stride = VShardId::COUNT >> R. Its primary vShard is b * stride.

Structs

PrefixBitsOutOfRange

An array routing granularity outside 1..=MAX_PREFIX_BITS.

ShardBucket

The bucket one shard serves. A shard read keeps only the tiles whose key falls in this bucket, so shards that share one Data Plane never return the same tile twice.

Constants

MAX_PREFIX_BITS

The largest routing granularity an array declares.

Functions

array_vshard_for_tile

The primary vShard that owns the tile with key tile_key.

bucket_to_vshard

The primary vShard of bucket at bits routing bits. bits comes from routing_bits, so it is at most VShardId::BITS.

fmix64

MurmurHash3 64-bit finalizer. A bijection on u64: distinct keys keep distinct values, and every input bit affects every output bit.

prefix_bucket

The routing bucket of tile key tile_key: the top prefix_bits bits of fmix64(tile_key). Returns a value in [0, 2^prefix_bits). With prefix_bits == 0 every key maps to bucket 0.

routing_bits

The bucket bits the router uses for prefix_bits: at most VShardId::BITS, since a finer bucket has no vShard of its own.

shard_bucket_admits

Whether tile_key passes the optional shard filter. None keeps every tile.