Caching Strategies & In-Memory Optimization Questions

Approach: Use a dict for O(1) lookup and a doubly-linked list to track recency (head = most recent, tail = least recent). On get/put move node to head. Protect all mutations and reads with a single re-entrant lock (threading.RLock) to ensure correctness under concurrent access; this keeps complexity simple and avoids races. For higher read concurrency, a read-write lock could be used.

import threading

class _Node:
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None

class ThreadSafeLRUCache:
    def __init__(self, capacity):
        assert capacity > 0
        self.capacity = capacity
        self.map = {}               # key -> _Node
        self.head = None            # most recent
        self.tail = None            # least recent
        self.lock = threading.RLock()

    def _remove(self, node):
        # unlink node from list
        if node.prev:
            node.prev.next = node.next
        else:
            self.head = node.next
        if node.next:
            node.next.prev = node.prev
        else:
            self.tail = node.prev
        node.prev = node.next = None

    def _add_to_head(self, node):
        node.next = self.head
        node.prev = None
        if self.head:
            self.head.prev = node
        self.head = node
        if self.tail is None:
            self.tail = node

    def get(self, key):
        with self.lock:
            node = self.map.get(key)
            if not node:
                return None
            # mark as most recently used
            self._remove(node)
            self._add_to_head(node)
            return node.value

    def put(self, key, value):
        with self.lock:
            if key in self.map:
                node = self.map[key]
                node.value = value
                self._remove(node)
                self._add_to_head(node)
                return
            node = _Node(key, value)
            self.map[key] = node
            self._add_to_head(node)
            if len(self.map) > self.capacity:
                # evict tail
                old = self.tail
                if old:
                    self._remove(old)
                    del self.map[old.key]

Locking strategy: RLock serializes get/put operations so list and dict remain consistent. Using a single lock avoids subtle race conditions (e.g., moving/removing nodes). Complexity: get and put are O(1) time, O(n) space for storing entries. Edge cases: None returns for missing keys; you can adjust to raise KeyError or return default. For high-concurrency read-heavy workloads consider reader-writer locks or sharded caches to reduce contention.

Requirements:

• Low-latency concurrent lookups/insertions for high QPS inference.
• Eviction: LRU or segmented LRU (S-LRU).
• Minimize lock contention, safe memory visibility across threads, bounded memory.

High-level design:

• Sharded cache: partition keyspace (consistent hashing) into N shards (e.g., 64). Each shard owns a subset of keys and has its own eviction structures and locks to limit contention.
• Read-path: optimistic lock-free reads using atomic pointer or versioned hashmap (read-copy-update style).
  • Each shard maintains an atomic pointer to an immutable hashmap/bucket array (or use concurrent_hash_map). Reads read the pointer, lookup without locking. If found and embedding valid, return immediately.
• Write-path / inserts / eviction: writers take a shard-local write lock (fine-grained mutex) to create a new modified bucket map (copy-on-write) or update in-place if using concurrent structure. After mutation, publish via atomic store to shard pointer and ensure a memory fence so other threads see updated data.

Eviction (S-LRU):

• Maintain per-shard hot and cold LRU lists. Accesses that hit promote entries to hot list.
• To avoid LRU list lock during reads: on cache hit, update a per-entry atomic "accessed" flag or increment approximate access counter; background thread periodically scans and performs actual list promotions under shard lock (batched promotions).
• On insertion when capacity exceeded, eviction runs under shard lock, evict cold entries first.

Memory consistency and safety:

• Use atomic operations and release/acquire semantics when publishing new pointers or changing entry states.
• Ensure deleted entries are not freed until all readers finish: implement epoch-based reclamation (EBR) or hazard pointers, or use reference counting for entries to avoid use-after-free.
• For copy-on-write maps, old versions are reclaimed after all readers exit (tracked by epochs).

Performance trade-offs:

• More shards → less lock contention but higher memory overhead.
• Copy-on-write gives lock-free reads but higher write cost and GC complexity.
• Background batched LRU updates reduce write path latency but make recency approximate.

Metrics and tuning:

• Measure hit rate, P99 latency, lock wait times; tune shard count, background interval, and S-LRU size ratio.

This design gives near lock-free reads, bounded-contention writes, and safe memory reclamation suitable for a multi-threaded inference server.