Approach summary:
- Maintain a dict mapping user_id → per-user LRU. Each per-user LRU is an OrderedDict (key→vector) with capacity N.
- For concurrency, use a global dict lock only when creating the per-user structure; each user LRU has its own Lock to allow concurrent access across users (fine-grained locking). get/put operations hold only the per-user lock (O(1) ops).
- This yields O(1) average get/put (hash + linked-list reorder via OrderedDict.move_to_end).
Code (thread-safe, per-user capacity):
python
import threading
from collections import OrderedDict, defaultdict
from typing import Any, Dict
class PerUserLRU:
def __init__(self, capacity: int):
self.capacity = capacity
self.map: Dict[Any, OrderedDict] = {}
self.locks: Dict[Any, threading.Lock] = {}
self.global_lock = threading.Lock() # protects creation of per-user structures
def _ensure_user(self, user_id):
# create per-user LRU and lock lazily
if user_id in self.map:
return
with self.global_lock:
if user_id not in self.map:
self.map[user_id] = OrderedDict()
self.locks[user_id] = threading.Lock()
def get(self, user_id, key):
self._ensure_user(user_id)
lock = self.locks[user_id]
with lock:
od = self.map[user_id]
if key not in od:
return None
od.move_to_end(key) # mark recently used
return od[key]
def put(self, user_id, key, vector):
self._ensure_user(user_id)
lock = self.locks[user_id]
with lock:
od = self.map[user_id]
if key in od:
od.move_to_end(key)
od[key] = vector
else:
od[key] = vector
if len(od) > self.capacity:
# pop least-recently-used (FIFO from left)
od.popitem(last=False)
Key concepts & reasoning:
- OrderedDict.move_to_end and popitem(last=False) provide O(1) reorder/evict operations.
- Fine-grained per-user locks minimize contention when many users are active concurrently.
- Global lock only used for one-time per-user structure creation; optional double-checked pattern avoids overhead.
Concurrency strategies:
- Locks vs lock-free: Python's GIL simplifies some cases but does not eliminate race conditions for mutable data structures. Lock-free designs (lock-free hash maps, atomic CAS) are complex and platform-dependent; for predictable correctness prefer locks. If extreme throughput needed, consider sharded lock-free C-extension or use concurrent runtime (e.g., Java's ConcurrentHashMap) or sharded user buckets to reduce lock granularity.
- Avoid holding global lock during expensive operations (serialization of vectors, network calls).
Memory limits & eviction behavior:
- Memory bounded per user by capacity × size(vector). For many users, total memory = users × capacity × avg_vector_size; monitor and set global limits.
- Strategies: fixed per-user capacity (this design), or dynamic allocation with global budget and eviction across users (maintain global LRU timestamps, or an approximate LFU). Consider compressing vectors, storing floats as float16, or using memory-mapped storage for large-scale.
Unit testing and load testing:
- Unit tests:
- single-thread correctness: put/get ordering, eviction, update existing key.
- multi-thread tests: spawn threads performing random get/put on same and different users; assert invariants (size ≤ capacity, no data corruption).
- edge cases: capacity=0, very large vectors, missing user/key.
- Load tests (production-like):
- Synthetic workloads with realistic user skew (Zipf) to catch hot-user contention.
- Measure throughput, latency, and memory usage; vary number of threads, vector sizes, and user counts.
- Test recovery under GC/backpressure; run with production memory limits and monitor OOM.
- Use stress tools (locust, custom threads) and profiling to find hotspots.
- Observability: expose metrics (hits, misses, evictions per-user/global, memory usage) and tracing for hot keys.
Alternatives & trade-offs:
- Use Redis LRU per-user shards if persistence or cross-process sharing is needed.
- Use C-optimized LRU (LRU cache in C extension) to reduce Python overhead for tight latency SLAs.
- Global LRU across users needed if overall memory is constrained; more complex (requires a global ordering, higher contention).
