Crate kv_index 

Radix tree implementations for prefix matching and cache-aware routing.

This module provides radix tree data structures that mirror SGLang’s scheduler memory management patterns. Two implementations are available:

• StringTree: Character-based tree for HTTP router (text input)
• TokenTree: Token-based tree for gRPC router (pre-tokenized input)

Both implementations support:

• Multi-tenant prefix tracking with LRU eviction
• Concurrent access via DashMap and RwLock
• Efficient prefix matching with match counts

Modules

snapshot

Compact serializable snapshot of a radix tree.

Structs

ContentHash

Position-independent content hash of tokens within a single block. Computed via XXH3-64 from token IDs. Same tokens always produce the same hash regardless of their position in the sequence.

OverlapScores

Overlap scores: how many consecutive blocks each worker has cached.

PositionalIndexer

Positional indexer for cache-aware routing.

PrefixMatchResult

Result of a prefix match operation, including char counts to avoid recomputation.

SequenceHash

Position-aware block hash from backend (sequence hash). Matches the block_hash field in KvBlock proto (i64, bitwise reinterpreted as u64). Different from ContentHash because it encodes the full prefix history.

StoredBlock

A block from a store event, carrying both hash representations.

StringMatchResult

Result of a prefix match operation, including char counts to avoid recomputation.

StringTree

TokenMatchResult

Result of a prefix match operation with token counts.

TokenTree

Token-based radix tree for cache-aware routing.

Tree

Enums

ApplyError

Error returned by PositionalIndexer::apply_stored when the event cannot be applied.

Constants

GLOBAL_EVICTION_HASH

Sentinel hash meaning “evict this tenant from ALL nodes” in the tenant-eviction wire format. Real prefixes never hash to this value: hash_node_path and hash_token_path remap 0 to 1 if Blake3 lands there.

Traits

MatchResult

Trait for prefix match results.

RadixTree

Trait for radix tree implementations.

Functions

compute_content_hash

Compute content hash from token IDs (position-independent). Uses XXH3-64 streaming hasher with standard seed — avoids intermediate allocation.

compute_request_content_hashes

Chunk request tokens by block size and compute a ContentHash per full block.

hash_node_path

Compute a compact 8-byte hash of a prefix path. Returns a non-zero hash; 0 is reserved for GLOBAL_EVICTION_HASH.

hash_token_path

Compute a compact 8-byte hash of a token-id sequence. Returns a non-zero hash; 0 is reserved for GLOBAL_EVICTION_HASH. Streams into the hasher to avoid an intermediate Vec<u8> (~128 KB at 32K tokens).

Type Aliases

TenantId

Interned tenant identifier for efficient comparison and storage.

WorkerBlockMap

Per-worker reverse lookup: backend_seq_hash → (position, content_hash, prefix_hash). The prefix_hash is the router-computed rolling hash used as the SeqEntry key.

WorkerId

Internal worker identifier used in OverlapScores.