syncprefixcacheindexer

Sync Prefix Cache Indexer Package

This package provides a high-performance, thread-safe indexing system for KV cache prefix matching in distributed LLM inference.

Overview

The syncprefixcacheindexer implements a two-level hash table structure optimized for:

• Fast prefix matching across multiple pods
• Efficient memory usage with configurable limits
• Automatic eviction of stale entries
• Thread-safe concurrent operations

Architecture

Two-Level Hash Structure

1. First Level: Model context (model name + LoRA ID)
2. Second Level: Prefix hash to pod mapping

This design enables efficient isolation between different models and adapters while supporting fast lookups.

Key Components

SyncPrefixHashTable (sync_hash.go)

The main data structure providing:

• ProcessBlockStored: Index new KV cache blocks
• ProcessBlockRemoved: Remove specific blocks
• ProcessAllBlocksCleared: Clear all blocks for a pod
• MatchPrefix: Find pods with matching token prefixes

Usage:

// Create indexer
indexer := NewSyncPrefixHashTable()

// Process a block stored event
event := BlockStored{
    BlockHashes: []int64{12345},
    Tokens:      [][]byte{tokenBytes},
    ModelName:   "llama-2-7b",
    LoraID:      -1,
    SourcePod:   "10.0.0.1",
}
err := indexer.ProcessBlockStored(event)

// Match prefix
matches, hashes := indexer.MatchPrefix(
    "llama-2-7b",
    -1,
    queryTokens,
    readyPods,
)

Event Types (events.go)

• BlockStored: New blocks added to cache
• BlockRemoved: Blocks removed from cache
• AllBlocksCleared: All blocks cleared for a source

Configuration

Environment variables:

• AIBRIX_SYNC_MAX_CONTEXTS: Max model contexts (default: 1000)
• AIBRIX_SYNC_MAX_PREFIXES_PER_CONTEXT: Max prefixes per context (default: 10000)
• AIBRIX_SYNC_EVICTION_INTERVAL_SECONDS: Eviction check interval (default: 60)
• AIBRIX_SYNC_EVICTION_DURATION_MINUTES: Time before eviction (default: 20)
• AIBRIX_PREFIX_CACHE_BLOCK_SIZE: Token block size (default: 16)

Performance

Optimizations

• Lock-free reads for hot paths
• Batch eviction to reduce lock contention
• XXHash for fast, high-quality hashing
• Memory pooling for reduced allocations

Benchmarks

go test -bench=. -benchmem ./pkg/utils/syncprefixcacheindexer/

Key metrics:

• Insert: ~200ns per operation
• Lookup: ~150ns per operation
• Memory: ~64 bytes per prefix entry

Thread Safety

All operations are thread-safe through:

• Read-write mutexes for each model context
• Atomic operations for statistics
• Safe iteration during eviction

Testing

Comprehensive test coverage including:

• Unit tests for all operations
• Concurrent operation stress tests
• Memory leak detection
• Performance benchmarks

Run tests:

go test ./pkg/utils/syncprefixcacheindexer/

Example Use Case

In a distributed LLM serving system:

1. vLLM pods report their cached token prefixes
2. The indexer maintains a global view of prefix availability
3. The router queries the indexer to find pods with matching prefixes
4. Requests are routed to pods with the highest prefix match

This significantly reduces computation by reusing cached KV states.