Skip to content
TheChatArchiveThe Chat Archive
Step 3.5 Flash· unknownHugging Face Frontier Reasoning Traces

Design a persistent cache layer with invalidation and fairness.

  1. User

    Design a persistent cache layer with invalidation and fairness.

  2. Assistant

    We are asked: "Design a persistent cache layer with invalidation and fairness." This is an open-ended design question likely for an interview or system design. We need to design a cache that is persistent (data survives restarts), supports invalidation (removing or updating stale entries), and fairness (perhaps fairness in eviction, or fairness among multiple clients? Possibly fairness in access, like preventing starvation? Need to interpret.

    Given the context: persistent cache layer. Could be like a disk-backed cache, or using a database. Invalidation: when underlying data changes, cache entries should be invalidated. Fairness: maybe to ensure that cache evictions are fair, or that multiple clients get fair access, or that the cache doesn't starve some keys? Possibly it's about "fairness" in the sense of cache replacement policy: e.g., not just LRU but also consider fairness across different clients or key types. Or maybe fairness refers to the fact that the cache should be fair in its resource usage among different tenants or users.

    We need to provide a design: components, APIs, algorithms, data structures, trade-offs, etc. Also consider persistence: need to store cache entries durably, so that after restart the cache can be restored. Invalidation: need mechanisms to invalidate entries when they become stale, possibly through TTL, explicit invalidation, or using versioning. Fairness: could be about ensuring that no single client or key monopolizes the cache, maybe through quota or weighted fair queuing? Or maybe fairness in eviction: e.g., LRU can be unfair to less frequently accessed items; maybe we need to use an algorithm like LFU or ARC that is more fair? Or maybe fairness is about read/write operations from multiple clients, ensuring no starvation.

    Given the wording: "persistent cache layer with invalidation and fairness." It might be referring to a cache layer that sits between an application and a database, persistently caching query results or objects, and needs to handle invalidation when data changes, and fairness possibly in terms of resource allocation among different services or clients.

    We need to define the goals, requirements, high-level architecture, key components, detailed design of cache storage (memory + disk), persistence mechanism (e.g., write-ahead logs, snapshots), invalidation strategies (TTL, manual, event-driven), and fairness policies (e.g., per-client quotas, eviction fairness). Also discuss trade-offs, scalability, fault tolerance.

    Let's structure the response:

    1. Introduction and goals: what is this cache for? A persistent cache layer that stores data durably, provides low-latency access, and ensures that stale data is invalidated appropriately, while also ensuring fairness among clients or keys in terms of resource usage.

    2. Requirements:

      • Functional: cache put/get, persistence across restarts, invalidation (automatic via TTL or explicit via API), fairness (maybe per-client rate limiting or eviction fairness).
      • Non-functional: low latency, high availability, scalability, durability, consistency (maybe eventual?), fairness guarantees.
    3. High-level architecture:

      • Cache nodes (in-memory store) with disk-backed persistence (e.g., using a write-ahead log and periodic snapshots).
      • Possibly a distributed cache if scaling out, with consistent hashing.
      • Metadata: for each entry, store key, value, version, expiration time, access metadata (LRU, LFU), client/tenant ID if fairness based on clients.
      • Invalidation manager: could be central or distributed. Could use versioning, vector clocks, or a pub/sub system to receive invalidation events from the source of truth (database).
      • Fairness module: tracks resource usage per client (e.g., number of entries, memory usage, request rate) and enforces policies (e.g., limit on cache size per client, eviction priority, rate limiting).
    4. Persistence design:

      • Use a combination of in-memory index and on-disk storage (e.g., Log-Structured Merge-tree, or simple append-only log).
      • For durability: write-ahead log (WAL) for all mutations (puts, deletes). On restart, replay WAL and reconstruct in-memory state. Also periodic snapshots for faster recovery.
      • Data format: store serialized values on disk, with key and metadata in the index.
      • Consider using existing storage engines (RocksDB, LevelDB) or build custom.
    5. Invalidation design:

      • Options: a) Time-based invalidation (TTL): set expiration time per entry; background thread purges expired entries. b) Explicit invalidation: API to delete keys, or invalidation messages from external systems (e.g., database triggers, change data capture). Could use message queue. c) Versioning: each entry stores a version or timestamp; on get, check if version is still valid by comparing with a central version store or by evaluating dependencies. d) Write-through/Write-behind: when writing to DB, also invalidate relevant cache entries.
      • Choose a combination: TTL as safety net, plus explicit invalidation events for strong consistency.
    6. Fairness design:

      • Define fairness: prevent any single client or tenant from consuming disproportionate cache resources. Could be memory footprint, number of entries, request rate.
      • Implement per-client quotas: each client has a max allowed cache size (memory or number of entries) and/or max request rate (QPS). Cache should track usage.
      • Eviction fairness: when evicting due to memory pressure, consider not only LRU but also client quotas; evict from clients exceeding quotas first, or use a weighted eviction policy where entry eviction priority = LRU score * weight based on client's current usage.
      • Admission control: reject put requests if client quota exceeded.
      • Rate limiting: at request level, token bucket per client.
      • For distributed cache, fairness metrics need to be aggregated across nodes or handled per node with global coordination (e.g., using a central quota manager or distributed counters).
    7. API design:

      • put(key, value, ttl, client_id?, options)
      • get(key, client_id?) -> returns value or miss; possibly updates access metadata.
      • invalidate(key) or invalidate(prefix) or invalidate_by_client(client_id)
      • maybe admin APIs for quotas.
    8. Detailed algorithms:

      • Cache eviction: use a combination of LRU and LFU or ARC? But we need fairness: could maintain per-client LRU lists, and when evicting, first evict from clients over quota; else evict global LRU.
      • Memory management: total memory capacity; when exceeding, trigger eviction.
      • Persistence: WAL writes; snapshotting; recovery procedure.
      • Invalidation message handling: async consumer; lock or atomic operations to update entries.
    9. Trade-offs:

      • Strong consistency vs performance: invalidation events might cause delays; TTL might cause stale data.
      • Persistence overhead: WAL writes impact latency; batching can mitigate.
      • Fairness complexity: tracking per-client stats adds overhead; distributed coordination overhead.
    10. Scalability and fault tolerance:

      • Sharding: partition keyspace across nodes; each node handles its own persistence and invalidation for its shard. Invalidation events must be routed accordingly.
      • Replication: for HA, each shard could have replicas; writes go to primary and replicate; reads from any.
      • Failure recovery: from WAL and snapshots.
    11. Additional considerations:

      • Cache warming on startup.
      • Monitoring metrics: hit rate, eviction count, per-client usage.
      • Security: authenticate clients for fairness tracking.
    12. Summary.

    We need to produce a coherent answer. The user likely expects a textual description, possibly with diagrams? But as text we can describe.

    Given the open-endedness, we should make reasonable assumptions. Possibly the "fairness" refers to "fair cache eviction" meaning that all keys get a fair chance to stay in cache, not just hot ones. That's like using a policy that prevents starvation of cold keys, such as LRU/K, or using a randomized eviction, but that's not exactly fairness. Maybe it's about fairness across different applications sharing the cache.

    Given the phrase "persistent cache layer with invalidation and fairness", it might be a specific design pattern: e.g., a cache that is persistent (disk-backed) and has mechanisms for invalidating cached data and ensuring fairness (i.e., equitable distribution of cache resources among clients). Could be in the context of a service that caches user data and needs to be fair to users.

    Maybe we can draw inspiration from existing systems: Apache Ignite, Redis with persistence, Ehcache, etc. They have invalidation via TTL, pub/sub, and maybe fairness via maxmemory policies.

    We need to be creative but also logical.

    Let's craft a comprehensive design.

    I'll assume the cache is used by multiple applications or tenants (multi-tenant). Fairness ensures that no tenant can starve others by consuming all cache resources. So we implement per-tenant quotas and weighted eviction.

    Also, persistence: the cache must survive process restarts, so we need to store data on disk and recover. But also we need to consider performance: memory for hot data, disk for warm/cold.

    We could design a two-tier cache: an in-memory LRU for fast access, and a disk-based persistent store (like RocksDB) for durability. The in-memory tier holds a subset of entries (hot). Eviction from memory writes to disk if we want to keep it? Actually if we want persistence, we need to store everything on disk anyway, but we might keep a write-back cache: writes go to memory and are persisted to disk asynchronously. On restart, we load from disk. So effectively, the entire dataset is on disk, but we keep hot entries in memory for speed. That's a typical design.

    In this design, persistence is achieved by writing all puts to a persistent log (WAL) that is fsynced periodically, and maybe using a key-value store on disk. In-memory cache is a materialized view of the disk data, with eviction policy.

    Now invalidation: When the source of truth (e.g., a database) changes, the cache must be notified to invalidate relevant entries. Could use a change data capture (CDC) stream, or application-level calls to invalidate. We'll design an invalidation service that receives invalidation messages (key or pattern) and marks entries as invalid (deletes them immediately or marks them stale and fetches fresh on next get). To ensure consistency, we might use a version number: each entry has a version from the source; on invalidation we know the new version; if the cached version is older, invalidate.

    Alternatively, we could use a time-based TTL as a fallback.

    Fairness: As said, per-tenant quotas. Tenants register with a quota (max memory bytes, max number of entries). The cache enforces these on admission (when putting) and during eviction. Tracking memory per tenant: need to known value size; approximate. Also track number of entries. When memory limit reached, eviction uses a policy that considers both recency and tenant usage. For example, define a score for each entry: score = recency_score * (1 + alpha * (tenant_usage / tenant_quota)). Or evict first from tenants that are over quota. Or use a weighted LRU where each tenant has a weight inversely proportional to their remaining quota.

    We need to design the eviction algorithm precisely. Could maintain a global LRU list but also track per-tenant LRU. When evicting, we can scan for the least recently used entry among tenants that are over quota, or if none, then the global LRU. Or we could adjust the eviction priority: compute a composite score: recency + fairness penalty.

    Simplify: use a variant of LRU with a fairness factor: each entry has a "priority" = (global LRU rank) + (tenant_usage_ratio * C). When tenant usage is high, its entries get higher priority (i.e., more likely to be evicted). Actually we want to evict from high usage tenants first, so we boost their eviction priority. So we can define eviction priority = LRU age + lambda * (tenant_usage_ratio). The oldest LRU age is high priority? Actually in LRU we evict the least recently used, i.e., the one with the smallest recency. To incorporate fairness, we want to evict entries from over-quota tenants even if they are more recent, so we need to adjust the ordering. So we could define a combined score: recency_score (e.g., timestamp of last access) and usage_score. Then evict the entry with the smallest combined score if we want to prioritize older and high usage. But careful: we want to evict entries that are both old and from high-usage tenants. We could compute: evict_score = recency_timestamp + penalty * (tenant_usage_ratio). The smallest recency_timestamp means oldest. But adding a positive penalty to entries from high-usage tenants increases their score, making them less likely to be evicted? That would be opposite. Actually if we want to evict high-usage tenants more readily, we want their entries to have lower priority (i.e., be evicted first). So we could subtract a factor: evict_score = recency_timestamp - penalty * (tenant_usage_ratio). But that could become negative and we might evict recent entries from high-usage tenants even if they are recent. That might be acceptable if the tenant is over quota; we want to force them out. So we can make penalty large enough to outweigh recency. But we must ensure that we don't evict a recently used entry from a tenant under quota in favor of an old entry from an over-quota tenant? Actually we want to protect under-quota tenants. So entries from under-quota tenants should be safe unless they are very old. So we can define: if tenant is over quota, their entries get a large negative boost (making them high eviction priority). Or we could use a two-tier: first evict from over-quota tenants based on their own LRU, before evicting from under-quota. That simpler: maintain global LRU, but also maintain per-tenant LRU lists. When eviction needed, check if any over-quota tenant exists; if yes, evict the least recently used entry from the most over-quota tenant (or any over-quota). If none, evict global LRU. That's simpler and more deterministic.

    We'll go with that: per-tenant tracking, during eviction, preferentially evict from tenants that exceed their quota. This ensures fairness over time: tenants that use more will lose entries faster, freeing space for others.

    Now the invalidation: We'll have an invalidation subsystem that can receive invalidate(key) or invalidate(prefix). It will delete the entry from memory and also from disk (or mark as invalid on disk to be cleaned later). Or if using versioning, we can store a version and on invalidation we update a central version store; but simpler: just delete.

    But if we want to be able to recover after restart, we need to ensure that invalidated entries are removed from disk as well, otherwise they'll be reloaded. So we need a mechanism to delete from persistent store. Could be a tombstone marker.

    We'll design: The cache uses a persistent key-value store (e.g., RocksDB) as the source of truth for the entire dataset (persistent). The in-memory cache holds a subset. The persistent store supports put and delete. When we put, we write to WAL and update RocksDB. When we invalidate, we delete from RocksDB and also remove from memory. On recovery, we load from RocksDB. That's consistent.

    But if we want to support high write throughput, we might batch deletes.

    Now fairness in terms of invalidation: If a tenant sends many invalidate requests, could that affect others? Probably not.

    Now let's outline the components:

    • CacheNode: each node responsible for a subset of keys (sharded). Contains:

      • MemoryCache: in-memory map (ConcurrentHashMap) of key -> Entry (value, metadata). Also a LRU list (or linked hash map) to track recency.
      • DiskStore: embedded key-value store (RocksDB) for persistence.
      • WAL: for durability (could be part of RocksDB, but we might have separate for fast recovery).
      • QuotaManager: tracks per-tenant usage (memory, count) stored in memory and maybe persisted? Quotas may be configured via admin. Could be stored in a config service.
      • EvictionManager: background thread that monitors memory usage and triggers eviction according to policy.
      • InvalidationListener: subscribes to an invalidation bus (e.g., Kafka topic) to receive invalidation events from data sources. Routes events to appropriate shard.
      • FairnessEnforcer: works with EvictionManager; decides which entries to evict based on quotas.
      • StatsCollector: metrics.
    • Coordination: For distributed, we need a membership service (e.g., ZooKeeper) for sharding and failover.

    Now elaborate on persistence:

    Use RocksDB as the persistent store. It's an embedded LSM-tree, provides durability with WAL. When we put a key, we write to RocksDB which flushes to disk. This gives persistence. In-memory cache can be a separate layer: we maintain a small in-memory LRU cache that stores hot entries. On get: check in-memory, if miss, read from RocksDB, then put in memory. On put: write to RocksDB and update in-memory (if key exists, update; else insert). On invalidation: delete from RocksDB and in-memory.

    We need to ensure that the in-memory cache stays consistent with RocksDB. On restart, we start with empty in-memory; as gets come, we populate from RocksDB. That's fine.

    But we also need to ensure that the in-memory cache size is bounded. That's where eviction comes in. The in-memory cache has a max size (e.g., 10% of total memory). When it exceeds, evict entries (write-back? No, since RocksDB already has the data, we just evict from memory; no need to write back because RocksDB is the source of truth. So eviction only removes from memory, not from RocksDB. That means if an entry is evicted from memory but still exists in RocksDB, a subsequent get will fetch from RocksDB and bring it back to memory. That's fine. But then eviction policy only affects memory usage; the persistent store grows unbounded? That could be a problem: we need to also have a way to evict from persistent store to prevent unlimited growth. But if we want a persistent cache, maybe we want to keep everything? But typical caches have limited capacity; we need to bound total storage (memory + disk). Since the cache is persistent, we might want to bound disk size too. So we need a disk eviction policy as well, or use RocksDB's compaction to drop old data? But RocksDB doesn't automatically evict based on LRU; it's a log-structured store that accumulates data; we need to set a size limit and let RocksDB's compaction handle it by dropping older versions? Actually RocksDB supports a range of configurations: it can be set with a total size limit via set_db_write_buffer_size and set_max_background_jobs, but it doesn't inherently evict based on LRU; it uses a combination of level-based compaction and TTL if configured. We could set a TTL on keys in RocksDB (using ColumnFamily options with ttl), or we could implement our own eviction from the persistent store by deleting keys when the disk usage exceeds a threshold. That would be a disk eviction policy. But then the cache might evict from disk based on some policy (e.g., LRU across all entries). That's complex.

    Alternative: The persistent cache layer might not need to be a full persistent store; it could be that the persistence is just for recovery of the in-memory cache after restart. That is, we want to avoid cold start; we want to persist the in-memory cache state to disk so that on restart we can quickly load it back. In that case, we don't keep all data permanently; we just store the in-memory cache contents durably. Then the capacity is still bounded by memory. The disk storage is just a snapshot + WAL to reconstruct the in-memory state. There's no independent persistent store; the cache is a cache of some backing store (like a database). So on restart, we load the entire in-memory state from disk; any data that was in memory before restart is restored. If some data was not in memory (i.e., evicted), it's not on disk either. That's typical for a persistent memory cache like Redis with AOF or RDB. Redis uses RDB snapshots and AOF for persistence; the dataset is kept in memory, and on disk we store a representation of it. So the persistent storage holds the entire in-memory dataset (the cache). That seems plausible: "persistent cache layer" meaning the cache itself is persistent across restarts. So the data in the cache is what we have in memory, and we persist that state to disk so we can recover. The underlying data source (database) is the source of truth for all data; the cache only holds a subset. So on restart, we recover the cache state (the subset) from disk; if some data changed in the database while the cache was down, we might have stale data; but we have invalidation to handle that: either TTL or explicit invalidation events that might be missed during downtime, but we can do a full refresh or rely on TTL.

    Thus, simpler: The cache is an in-memory LRU (or other) with a maximum size. For persistence, we write all mutations (put/delete) to an append-only log (WAL) and periodically take a snapshot of the in-memory state. On restart, we replay the log after the latest snapshot (or just load the snapshot if log truncated). This is like Redis AOF. This ensures that the cache's in-memory contents are durable. The size on disk is bounded by the log growth; we can compact it into snapshots.

    Now invalidation: We need to invalidate entries when they become stale in the backing store. We can have a mechanism: either the backing store sends invalidation events (e.g., via a message bus) to the cache nodes; or the cache uses a lease/TTL approach; or we can use a versioning scheme: each cache entry has a version (timestamp or sequence number) from the source; on get, we can optionally check with the source if the version is still current (but that would be a roundtrip, defeating cache). So better to proactively invalidate.

    Thus, the cache subscribes to an invalidation topic. When an invalidation message arrives (key or pattern), it removes the entry from memory and also records the deletion in the WAL so that on restart it stays deleted. So the WAL records deletes as well. That ensures consistency.

    Now fairness: Since it's an in-memory cache with fixed capacity, we need to ensure fair distribution among clients. Tenants are identified by a client_id (or tenant_id) on each put/get request. The cache enforces per-tenant quotas: maximum memory usage, maximum number of entries, maybe maximum QPS. For memory quotas, we need to track approximate memory footprint per tenant. On put, if adding the entry would exceed the tenant's quota, we may either reject the put or evict some of that tenant's existing entries to make room. But we also need to consider global capacity. So the eviction policy should consider both global capacity and per-tenant quotas. For example, when the cache is full and a new entry arrives, we need to evict something. Instead of evicting the global LRU, we could first try to evict from the same tenant if that tenant is over quota? But the new entry might be from a different tenant. We need a policy that ensures no tenant exceeds quota over time. One approach: on each put, we check if the tenant's current usage plus the new entry's size exceeds quota. If so, we may need to evict some of that tenant's entries (maybe the least recently used among that tenant) to bring usage under quota before inserting the new one. If after that the total cache size still exceeds global limit, we then evict globally (preferably from over-quota tenants). This ensures that quotas are respected. However, we also need to consider that a tenant might be under quota but the global cache is full; then we evict some entry (likely the global LRU) which might be from a tenant that is already under quota, potentially making them go under further under quota, but that's okay as long as overall fairness is maintained? Actually fairness may mean that each tenant gets a minimum guaranteed share? Possibly we want to guarantee that each tenant can use up to their quota, but not more. And we want to avoid that a heavy tenant evicts entries of light tenants. So we can prioritize evicting from tenants that are over their quota, and if none, evict the global LRU regardless of tenant? But if we evict from a tenant that is under quota, we might reduce their cache hit rate, but that's acceptable if we have to make space. However, to be fair, we might want to implement a weighted eviction: entries from tenants that are using a larger fraction of their quota have higher eviction priority. That's like the composite score earlier.

    Simplify: Use a variant of the "adaptive replacement cache" but with quotas? Probably simpler to implement as: maintain per-tenant LRU lists. Global eviction: find the tenant with the highest (usage / quota) ratio that is above 1 (i.e., over quota). Among those, evict their least recently used entry. If no tenant over quota, evict the globally least recently used entry (from any tenant). That's straightforward.

    We need to track usage per tenant: sum of entry sizes or count. We'll approximate memory usage by counting number of entries and average size? Simpler: count entries, quotas in number of entries (since memory sizes can vary). But if we want fairness in memory, we need to know individual entry sizes. Could track bytes. We'll assume entries have sizes; we track per-tenant byte usage. For simplicity, we could ignore sizes and use counts.

    Now we need to integrate this with the in-memory LRU. We can use a data structure that maintains a global LRU order (like a linked list) and also per-tenant LRU lists (maybe as separate linked lists). When evicting, we need to quickly find the least recently used entry from a specific tenant. We can maintain for each tenant a LinkedHashSet (ordered by access) of its entries. The global LRU can be a separate list. On access (get or put), we need to move the entry to the front of the global LRU and its tenant's LRU. That's O(1) with doubly linked lists if we have pointers.

    Alternatively, we could use a single global LRU but compute eviction priority on the fly: traverse from least recently used upwards until we find an entry from a tenant that is over quota or the oldest overall. That could be expensive if many entries are not over quota. Better to maintain separate lists.

    We can maintain a global LRU list and also for each tenant a list. But we must maintain consistency: when an entry is accessed, it is moved to the front of both lists. That's doable if we have node objects that are part of two doubly linked lists (global and tenant). That's more complex but manageable.

    Alternatively, we could maintain a priority queue of entries with a score based on last access and tenant usage ratio. We update scores on access and on quota changes. That might be easier: each entry has a score = last_access_time (for LRU) or we could use a heap keyed by access time. But to incorporate fairness, we need to adjust priority. But we need to quickly find the minimum. A heap would be O(log n) for updates. Acceptable.

    But we also need to evict multiple entries at once when a big put comes. Could batch.

    Given the complexity, maybe we can describe conceptually without going into too much code.

    Now let's design the API:

    • CacheClient (for applications):

      • connect(tenant_id, auth_token)
      • get(key) -> value (or null)
      • put(key, value, ttl_seconds?) -> status
      • invalidate(key) -> status (maybe admin only)
      • maybe delete(key)
    • Admin API:

      • set_quota(tenant_id, max_entries or max_bytes)
      • get_stats(tenant_id) -> usage, hits, misses, etc.
      • flush() -> clear cache

    The cache nodes expose these APIs over network (e.g., gRPC).

    Now flow for get:

    • Client sends get(key) with tenant_id (or tenant is derived from auth token).
    • Cache checks in-memory: if hit: update access time (move to front of LRU), return value. else: read from persistent store (RocksDB). If found, put in in-memory cache (if capacity allows, else evict first), update access time, return value. else: return miss.
    • Record metrics.

    For put:

    • Client sends put(key, value, ttl) with tenant_id.
    • Check quota: current usage for tenant + size(value) > quota? If yes, either reject (if strict) or evict some of tenant's entries to make room. We can proceed by first ensuring tenant has enough free space: if not, evict tenant's LRU entries until enough space (or until no more entries). If still not enough (maybe tenant's quota is less than the entry size itself), reject.
    • Then check global capacity: if adding this entry would exceed global memory limit, evict entries globally according to fairness policy (over-quota tenants first) until enough space.
    • Then write to persistent store (RocksDB, also WAL if separate), and insert into in-memory cache. Record TTL if provided (store expiration time, and background cleanup thread will delete expired entries).

    For invalidation (from external source):

    • Cache subscribes to invalidation messages (key, tenant_id? maybe just key). When received:
      • If key in memory, remove it.
      • Issue delete to persistent store (RocksDB) and log the delete.
    • Also, we might receive bulk invalidations (prefix), so process accordingly.

    Now persistence: The persistent store (RocksDB) holds the current state of the cache. But we need to ensure that writes are durable. RocksDB writes to WAL and then to memtable, flush to SST. We can configure to sync on every write for durability, but that impacts performance. Could batch. For cache, maybe we can tolerate some loss on crash? But the requirement says persistent, so likely need durability. We can use sync on every write, or use group commit. We'll mention WAL with fsync at intervals, but risk losing recent writes. Trade-off.

    Alternatively, we could use a separate WAL log that we fsync per operation (like AOF every second or every write). We'll describe both.

    Now fairness implementation in detail:

    We maintain:

    • tenantQuotas: map tenant_id -> Quota (max_bytes or max_entries, maybe both)
    • tenantUsage: map tenant_id -> Usage (bytes, count)

    On each put:

    • Compute entry_size = serialized size of value + overhead.
    • Check if tenant's current usage + entry_size > quota_max_bytes (if that quota is set). If so, need to free space from that tenant. We can evict some of that tenant's entries. Which ones? Use tenant's LRU order. So we need to maintain per-tenant LRU list. We'll evict the least recently used entries from that tenant until usage + entry_size <= quota_max_bytes or no entries left. Track usage decrement.
    • After ensuring tenant quota, we check global capacity: if total_cache_bytes + entry_size > global_max_bytes, we need to evict globally. We'll use the fairness-aware eviction: First, identify tenants that are over their quota (usage > quota). Among them, find the one with highest usage ratio (or just any over-quota). Evict its least recently used entry. Repeat until global capacity is satisfied or no over-quote tenants left. If still need space, evict the global LRU entry (from any tenant). This ensures that over-quota tenants are penalized (their entries evicted first), thus encouraging them to stay within quota. Under-quota tenants are protected unless absolutely necessary.
    • After evictions, we have enough space. Then allocate entry, update tenant usage, total usage, and insert into in-memory and persistent store.

    On delete (due to invalidation or TTL expiration):

    • Remove entry, update tenant usage, total usage, remove from LRU lists.

    On get: no changes to usage (only access time). But might be used for metrics.

    Now we need to ensure that eviction happens promptly. Could be synchronous during put (as above) or asynchronous background. For simplicity, synchronous eviction ensures immediate consistency with quotas. But it might add latency. We could also allow over-quota temporarily and correct asynchronously, but then we might exceed quotas momentarily. That could be acceptable. But we need to be careful with memory: we cannot exceed total capacity, so we must enforce globally. So synchronous global eviction is needed to keep memory bounded. However, we could have a background thread that monitors and evicts if usage exceeds a threshold, but then a put might temporarily cause over-limit before background runs. To guarantee we don't OOM, we need to check before insert. So eviction before insert is required. So we implement a method: ensureFreeSpace(requiredBytes) that performs evictions until enough free space (or fails). This method also respects tenant quotas for the upcoming put: we may want to free space from the tenant that is inserting if they are over quota, else globally. But we also need to consider that the put itself might push the tenant over quota; we should free from that tenant first.

    Thus, algorithm for put(tenant, key, value, size):

    1. Lock (or use concurrency control) to prevent concurrent modifications that could break quota calculations. We'll need locking per tenant and global.
    2. If tenant has quota and (tenant.usage + size > tenant.quota): needed = tenant.usage + size - tenant.quota evictFromTenant(tenant, needed) // evicts until freed at least needed bytes or tenant empty. If cannot free enough (e.g., all entries are too big), then reject.
    3. If total.usage + size > global_max: needed = total.usage + size - global_max evictGlobally(needed) // using fairness policy. If after evicting all we cannot free enough (shouldn't happen if we maintain invariants), reject.
    4. Insert entry: add to RocksDB (persist), add to in-memory structures: global LRU, tenant LRU, update usage counts.
    5. Persist metadata (maybe in WAL) for recovery.

    Now evictFromTenant(tenant, needed): while needed > 0 and tenant has entries: entry = tenant.lru.getOldest() // tail of LRU list if entry is null: break remove entry from memory and persistent store? Wait, we are evicting from memory only? But if we evict from memory, we keep it in persistent store? That's fine because persistent store is separate; we are evicting from in-memory cache to free RAM. However, if we are evicting because tenant is over quota, we might want to also remove from persistent store? Not necessarily; the persistent store holds the cache's dataset, which we want to keep? But if we are evicting to free memory, we only remove from memory. However, consider: The persistent store's size may also be bounded; but we haven't discussed that. In our design, the persistent store is just a durable copy of the in-memory state. Actually if we only evict from memory but keep in persistent store, then on restart we will load that entry back into memory. That means the entry remains in the cache's dataset, just not in memory. That's fine; the quota is about memory usage, not persistent storage. So evictFromTenant frees memory but not persistent storage. However, if the persistent store itself has a size limit, we might need to evict from it as well. But we can treat persistent store as having separate capacity; but to keep it simple, we could not have a separate persistent store capacity; the persistent storage is not considered in quotas. The quota is about in-memory footprint. That makes sense: persistent storage is disk, which is larger and cheaper; we can allow it to grow, but we might also want to bound it to avoid disk full. But perhaps we can treat it as unbounded for simplicity, or we can have a separate eviction for disk. However, typical persistent caches like Redis use RDB/AOF to store the entire dataset, and the dataset size is bounded by memory, not disk. The on-disk size is similar to memory size because it's a serialized copy. So if memory is 10GB, disk usage is also about 10GB. So disk size is bound by memory size because we only persist what's in memory. In our design, if we evict from memory but keep persistent store, then the persistent store will contain entries that are not in memory, which means disk size > memory size. On restart, we would load those entries back into memory, so memory would be refilled. That suggests we cannot evict from memory without also evicting from persistent store, because otherwise the persistent store would contain stale entries that are not part of the current cache state? But the cache state is what's in memory at any given time. The persistent store is a durable copy of the in-memory state. If we evict from memory but keep the record on disk, then on restart the cache would load that entry, so the entry would reappear in memory. But that entry might have been evicted because of quota; after restart, it would come back, possibly causing the tenant to exceed quota again. That's not necessarily a problem; the quota enforcement will happen on new puts, but existing entries would be loaded. That might temporarily exceed quota after restart, but we can run a quota compliance check after loading to evict over-quota entries. That's okay. However, the purpose of eviction is to keep memory usage within limit. If we keep all entries on disk, we could have unlimited number of entries, but memory is limited; we load on demand. That's essentially a disk-backed cache where the disk is a backing store. That's a typical design: in-memory cache of a persistent store. In that case, the persistent store is the authoritative data, and the in-memory cache is just a hot subset. The quotas would then be about the in-memory cache size, not the disk size. But the question says "persistent cache layer", which suggests the cache itself is persistent, i.e., the data in the cache survives restarts. It doesn't necessarily mean the cache is a cache of some other store; it might be its own store that is both fast and durable. So we need to decide.

    Let's interpret: "persistent cache layer" could mean a caching layer that provides persistence (i.e., data survives process restarts), but still functions as a cache (i.e., it stores a subset of data from a backing database, and data may be evicted). The persistence is for recovery, not for storing the entire dataset. So the on-disk storage holds only the data that is currently in memory (the cache) plus maybe some metadata for recovery. So if we evict an entry from memory, we should also remove it from the persistent log? Not necessarily; we could keep it in the log for historical recovery? But if we want to reconstruct the exact state of the cache at crash time, we need to have records of all entries that were in memory at that time. If we evict an entry from memory but don't delete it from the persistent log, then upon replay, that entry would be resurrected, which would be incorrect because it was evicted before crash. So we need to reflect evictions in the persistent log. Typically, in AOF, every operation (set, delete) is logged. When we evict an entry due to LRU, we don't log a delete; we just remove it from memory. But on restart, we replay all writes (sets) and we would end up with the entire history of sets, which would reconstruct the state as if no evictions happened. But that's not correct because evictions are not logged. In Redis, if you use AOF, you cannot evict data without also logging the deletion? Actually Redis uses RDB snapshots to capture the state at points in time. The AOF logs every write operation. When you restart, Redis loads the RDB (or the AOF if no RDB) to get the dataset. But evictions (due to maxmemory) are not logged to AOF because they are not considered writes. However, when using AOF, if you set maxmemory and eviction policy, on restart Redis loads the dataset from the AOF (which contains all sets, no deletes for evictions). That means the dataset after restart could be larger than maxmemory because evictions are not persisted. To avoid that, Redis uses RDB snapshots to capture the state after evictions. The typical approach: periodically create an RDB snapshot which captures the current in-memory state (after evictions). On restart, load the RDB, then replay any AOF entries that occurred after the snapshot. That reconstructs the state correctly. So evictions are reflected in the RDB because it's a snapshot of memory. So in our design, we could have periodic snapshots of the in-memory cache to disk. The WAL only records writes (puts/deletes) that occurred since the last snapshot. Evictions are not explicitly logged, but they are captured in the next snapshot. That works.

    Thus, persistence: we maintain an in-memory cache with a max size. We also maintain a write-ahead log (or append-only log) of all mutating operations (puts, deletes from explicit invalidations or TTL expirations). And we periodically take a snapshot of the entire in-memory state (i.e., all entries currently in cache). On restart, we load the latest snapshot, then replay the log to apply any operations after the snapshot. This recovers the exact state, including which entries were present at crash time. Evictions due to memory pressure are not logged; they are reflected in the snapshot as missing entries. So we need to ensure that the snapshot is taken at a time when we have a consistent view, and that we can flush pending writes. So this is a classic design.

    Now, the invalidation mechanism: We receive invalidation events. When we get an invalidation for a key, we remove it from in-memory cache and also log a delete operation. That delete will be in the log, and eventually in a snapshot. So after restart, that entry won't come back. Good.

    Now fairness: Quotas are about in-memory usage. Since the snapshot reflects what's in memory, the in-memory state after restart will be within quotas? Possibly not, because quotas may change, or we might have loaded entries that now exceed quotas. But we can enforce quotas after load by running a compliance eviction pass: after loading snapshot and replay, we may exceed quotas if they were increased? Actually if quotas are reduced, we might need to evict. But typically quotas are static or increased. If they are static, after loading we should be within quotas because before crash we were within quotas (assuming we enforce strictly). However, if we crash before completing an eviction, we might be over quota after replay? Possibly, but we can re-check after recovery.

    Now we need to detail the snapshot: We can serialize all entries (key, value, metadata like access time, TTL, tenant, etc.) to a file. The snapshot includes the in-memory map and the LRU lists. We might need to store the LRU order to preserve recency after restart? For cache behavior, we want to preserve access recency to some extent. After restart, we could initialize LRU order based on last access times stored in snapshot, or we could start with LRU empty (all entries have same recency). But if we store last access time, we could reorder accordingly. That's optional. Simpler: after restart, we load all entries into memory but do not have LRU order; we can treat them as all newly added, which might cause different eviction order initially but that's okay. Or we could store a sequence number for each access and reconstruct LRU. Might be overkill.

    Now let's produce a final answer with these components.

    We should also discuss the consistency model: The cache may be eventually consistent with the backing store. Invalidation events aim to keep it strongly consistent, but there could be delays or missed events during downtime. TTL provides a bound on staleness.

    Now, the question likely expects a high-level design with some specifics on data structures and algorithms. We'll produce a structured answer.

    We'll start with an overview, then break down into:

    • Goals and scope
    • System architecture
    • Persistence mechanism
    • Invalidation subsystem
    • Fairness subsystem
    • API
    • Failure handling and recovery
    • Scalability considerations
    • Trade-offs and alternatives

    We'll also add diagrams in text? Probably not needed.

    Let's write.

    We need to be careful about the "fairness" interpretation. Could also be about fairness in serving requests (e.g., not starving slower clients). But more likely it's about fair resource allocation among tenants. We'll assume multi-tenancy.

    Alternatively, "fairness" could refer to "fair cache eviction" where we don't wantcache pollution" by a few hot items; we want to give a chance to less popular items. That's like using an algorithm like "LRU with a fairness factor" or "FIFO with reinsertion". But we can incorporate that by using per-tenant quotas? That's not exactly fairness among items. But the phrase "fairness" might be ambiguous. Could also be about fairness between read and write operations? Or fairness in invalidation (e.g., all keys get invalidated fairly)? Not likely.

    I think multi-tenant fairness is a common requirement in shared caching systems. We'll go with that.

    Let's craft the answer.

    We'll include:

    • Introduction: We design a persistent, multi-tenant cache that provides low-latency access, ensures data durability across restarts, invalidates stale entries promptly, and enforces fairness among tenants via quotas and eviction policies.

    • Components:

      1. Cache Node: Each node holds a portion of the keyspace (sharding). Contains:

        • In-memory index: Hash map for key -> CacheEntry.
        • LRU list(s): To track recency.
        • Per-tenant LRU lists: For fairness.
        • Persistent storage: RocksDB (or similar) for durability.
        • Write-Ahead Log (WAL): For fast recovery (or rely on RocksDB's WAL).
        • Snapshot manager: Periodically snapshots in-memory state.
        • Invalidation consumer: Subscribes to invalidation channel.
        • Quota manager: Tracks usage per tenant.
        • Eviction controller: Applies policies.
      2. Coordination Service: For shard allocation, leader election (if replicated).

      3. Invalidation Bus: A message queue (Kafka) that carries invalidation events produced by data sources.

    • Data Structures:

      CacheEntry:

      • key
      • value (byte array)
      • tenant_id
      • size (approx)
      • ttl (optional)
      • last_access_time (for LRU)
      • pointers (next, prev for global LRU and tenant LRU)

      Global LRU: Doubly linked list, head = most recent, tail = least recent. Per-tenant LRU: Map tenant_id -> Doubly linked list of entries for that tenant.

      Quota usage: Map tenant_id -> {used_bytes, entry_count}.

    • Persistence:

      We use a combination of in-memory state and on-disk storage. The on-disk storage is a log-structured store (RocksDB) that holds the authoritative copy of the cache's contents. All put/delete operations are written to RocksDB with durability (WAL + fsync as configured). Additionally, we periodically take snapshots of the entire in-memory map (including LRU order if desired) to a separate file for faster recovery: on startup we can load the snapshot then replay the RocksDB WAL for any mutations after the snapshot. This is similar to Redis RDB+AOF.

      We must ensure that evictions (removal from memory due to capacity) are also reflected in the persistent store? No, because evictions mean the entry is no longer in the cache's dataset; they should be removed from the persistent store to keep it consistent. However, we previously argued that if we evict from memory but not from persistent store, on restart the entry would reappear. To avoid that, we need to either: a) Evict from persistent store as well (i.e., delete from RocksDB). This would mean that the persistent store only contains entries currently in memory. That aligns with the idea that the cache's persistent copy is exactly the in-memory state. So when we evict from memory, we must also delete from RocksDB. But that could cause a lot of delete writes. That's okay; RocksDB handles deletes. b) Alternatively, we could keep persistent store as a log of all writes and rely on snapshots to capture state. Then we don't need to delete on eviction; we just stop including the entry in the snapshot. After restart, we load snapshot (which doesn't contain evicted entries) and replay log only for entries that were inserted after the snapshot and not evicted? But entries that were evicted before the snapshot would not be in snapshot. However, if they were inserted before the snapshot and then evicted before the snapshot, the snapshot won't have them. Good. But what about entries that were inserted before the snapshot and evicted after the snapshot but before crash? The snapshot has them. On restart, we load snapshot and then replay log for operations after snapshot. If an entry was evicted after snapshot but before crash, there would be no log entry for the eviction (since eviction is not logged). So it would be loaded from snapshot and remain in memory, violating the eviction that occurred. To fix this, we must either log evictions or not evict from memory without also deleting from the persistent store. Therefore, option (a) is simpler: treat eviction as a delete operation that is logged and reflected in the persistent store. That means the persistent store always mirrors the in-memory cache contents exactly. So we need to delete from RocksDB on eviction. That's acceptable; RocksDB can handle high delete rates.

      So we choose: eviction = remove from memory + delete from persistent store (with durability). That ensures consistency.

      However, we must consider that evictions might be many; we need to batch deletes? Could be okay.

      Alternatively, we could have the persistent store be the source of truth and we only keep hot entries in memory, and we don't evict from persistent store. That would mean the persistent store holds the entire dataset we've ever cached, which might grow large. That's not typical for a cache; caches are bounded. So we'll go with eviction deletes.

    • Invalidation:

      Sources of truth (e.g., primary database) publish invalidation events to a message bus. Events include key and possibly tenant/namespace. Cache nodes subscribe and upon receiving an event for a key they own, they perform:

      • If key in memory: remove it, record delete in persistent store, update usage.
      • If key not in memory: still issue a delete to persistent store to ensure it's removed if present (to handle case where entry is on disk but not in memory? But our design says persistent store mirrors memory, so if not in memory it shouldn't be in store either? Actually if an entry evicted from memory but we also deleted from store, it's not there. So maybe unnecessary. But it's safe to issue delete; it's idempotent. Also, we may receive TTL expirations: a background thread scans for expired entries (based on stored ttl) and performs eviction (delete from memory and store). TTL is stored per entry.

      Invalidation events might be high volume; we need to handle them asynchronously and possibly batch.

    • Fairness:

      As described, per-tenant quotas. Implementation:

      • On each put, check tenant usage. If over quota, evict tenant's own entries (starting from LRU) until under quota. If cannot, reject.
      • On global capacity pressure, evict from tenants that are over their quota first. Then if still needed, evict global LRU. This ensures that no tenant can monopolize the cache beyond its quota, and that over-quota tenants are penalized by losing their entries even if they are recently used.

      We also consider fairness in request handling: to prevent a single client from saturating the cache's CPU, we could apply rate limiting per tenant at the API gate. That's out of scope.

    • Concurrency:

      Need to handle concurrent gets/puts/evictions. Use fine-grained locking: per-tenant lock and global lock? Could use a read-write lock for the whole cache, but that hurts scalability. Better: use lock striping or lock-free structures. For simplicity, we can use a single lock for the entire cache node (coarse-grained) because cache operations are fast and we want atomic updates to usage and LRU. But high scalability might need lock-free. We'll mention use of concurrent data structures: ConcurrentHashMap for key->entry, and using atomic operations for counters. For LRU updates, we can use synchronized blocks on the entry node. Or we can use a lock per entry? Complex. We'll abstract: use a global lock for all mutating operations (put, delete, eviction) to keep consistency of usage counters and LRU lists. This serializes writes but reads (gets) can be lock-free if we use atomic snapshots or read-copy-update? Actually gets need to move entry to front of LRU, which modifies the LRU list. So they need to lock as well. We could use a read-write lock: many gets can proceed concurrently if we allow concurrent reads that update LRU by moving nodes? But moving nodes in a linked list requires exclusive access to the list. Could use a lock-free LRU? There are lock-free queues but not typical. Simpler: use a single ReentrantLock for all operations; given that cache is fast, contention might be low if we have enough nodes. We'll note that.

      Alternatively, we can separate: the in-memory map is concurrent, but the LRU list is protected by a lock. We'll use a lock for LRU operations and for usage updates. Ggets need to lock to move entry to front. That could be a bottleneck. We can use an opportunistic approach: if entry recently moved, we might skip? But need guarantee. We'll say we use a striped lock per shard to reduce contention. For distributed, each node is independent.

    • Recovery:

      On node restart:

      1. Load the latest snapshot file (if exists) into memory: reconstruct map, LRU (if order saved), per-tenant lists, usage counters.
      2. Replay the persistent store's WAL (RocksDB's WAL or our own) from the snapshot's LSN to apply all writes (puts, deletes) that occurred after snapshot. This brings memory state to consistent state at crash time.
      3. Start processing requests. We also need to ensure that after recovery, the node re-joins the cluster and starts receiving invalidation events.
    • Scalability:

      • Horizontal scaling by sharding keyspace. Use consistent hashing to assign keys to nodes. Each node is responsible for a subset of keys; invalidation events must be routed to the correct node (based on key). The invalidation bus includes key; each node consumes events and checks if the key belongs to its shard; if not, ignore or forward.
      • Each node persists its own data; no cross-node replication for simplicity. For high availability, we could add replicas with synchronous replication, but that's extra complexity.
      • The persistent store (RocksDB) resides on local SSD for each node.
    • Trade-offs:

      • Durability vs latency: fsync on every write ensures no data loss but high latency; we can batch or use group commit. We may accept a small window of loss (e.g., 1 second) for performance.
      • Fairness vs hit rate: Aggressive eviction of over-quota tenants may reduce overall hit rate if those tenants have hot data, but that's intentional to enforce quotas.
      • Complexity: per-tenant LRU and quota tracking adds overhead in memory and CPU. Could use approximate counters (e.g., using probabilistic data structures) to reduce overhead.
      • Invalidation latency: Events might be delayed; stale data may be served until invalidation arrives or TTL expires.
    • Alternatives considered:

      • Use time-based invalidation only (TTL) and no explicit events. Simpler but less consistent.
      • Use LFU instead of LRU for better hit rate; but fairness is harder.
      • Use token bucket for fairness on request rate rather than memory.
    • Conclusion: We present a design that meets requirements.

    Now write in a clear, organized manner.

    We'll produce a fairly detailed answer. Since it's a design question, we can include pseudo-code snippets? Not needed, but can describe algorithms.

    Let's produce final answer.

    1. Overview

    We design a persistent, multi‑tenant cache layer that provides low‑latency access to cached data, survives process restarts, automatically invalidates stale entries, and enforces fairness among tenants (i.e., no tenant can monopolize memory resources). The system is built as a distributed cluster of cache nodes; each node is responsible for a shard of the keyspace and persists its own state durably.

    Key properties:

    • Persistence: Cache contents survive crashes and restarts.
    • Invalidation: Stale data is removed promptly via explicit events and/or TTL.
    • Fairness: Per‑tenant quotas (memory / entry count) are enforced; eviction policy favors over‑quota tenants.
    • Scalability: Horizontal scaling by sharding; each node operates independently.
    • High performance: In‑memory lookups with a small in‑memory LRU; durability via efficient write‑ahead logging and periodic snapshots.

    2. System Architecture

    +----------------+       +----------------+       +----------------+
    |   Client       | ----> |   Router       | ----> |  Cache Node 1 |
    | (tenant aware) |       | (consistent    |       | (shard A)      |
    +----------------+       |  hashing)      |       +----------------+
                            +----------------+       |  In-Memory LRU |
                                                   |  Per‑tenant LRU|
                                                   |  RocksDB (disk)|
                                                   |  Inv. Consumer |
                                                   |  Quota Manager |
                                                   +----------------+
                                                    ...
    
    • Client: Sends GET/PUT/INVALIDATE requests with a tenant identifier (authenticated).
    • Router: A thin layer (e.g., HAProxy, Envoy, or a custom client library) that computes the target shard via consistent hashing on the key and forwards the request.
    • Cache Node: The core component. Multiple nodes form the cluster. Each node owns a disjoint key range (shard).

    3. Cache Node Internal Design

    A node consists of the following modules:

    3.1 In‑Memory Cache

    • Hash Map (ConcurrentHashMap<String, CacheEntry>) for O(1) key lookup.
    • Global LRU List: Doubly linked list ordering entries from most to least recently used. Used when evicting globally.
    • Per‑tenant LRU Lists: Map<TenantId, LinkedHashSet<CacheEntry>> (or custom doubly linked lists) to quickly identify the least recently used entry for a specific tenant.
    • Quota Tracking: Map<TenantId, QuotaInfo> storing used_bytes, entry_count, and configured max_bytes / max_entries.

    CacheEntry fields:

    key: String
    value: byte[]        // serialized data
    tenant_id: String
    size: int            // approx. memory footprint (value length + overhead)
    ttl: long?           // expiration epoch millis (optional)
    last_access: long    // for LRU (wall‑clock or logical tick)
    node_global_next/prev: pointers for global LRU
    node_tenant_next/prev: pointers for tenant‑specific LRU
    

    All mutating operations (PUT, DELETE, EVICT) acquire a node‑wide lock (or finer‑grained stripes) to keep usage counters and LRU lists consistent. Reads (GET) also need to update the LRU, therefore they also acquire the lock (or use a read‑write lock where multiple readers can move nodes concurrently with careful coordination). For simplicity we assume a single ReentrantLock per node; contention is acceptable because most workloads are read‑heavy and the node’s CPU is not saturated.

    3.2 Persistent Store

    • RocksDB (or any embedded LSM‑tree KV store) is used as the durable backing store.
    • The on‑disk state exactly mirrors the in‑memory cache at any point (i.e., every entry present in memory is also stored in RocksDB; evicted entries are deleted from RocksDB).
    • RocksDB’s own WAL (write‑ahead log) guarantees durability. We can configure sync on each write for full durability, or batch for higher throughput and accept a bounded window of loss (e.g., 1 s). The exact policy is tunable.

    3.3 Snapshots (for fast recovery)

    • Periodically (or when the WAL reaches a size threshold) the node creates a snapshot:
      • Serialize the entire in‑memory map (keys, values, tenant, ttl, and optionally LRU order) to a file (e.g., using protobuf or Java serialization).
      • Truncate the WAL up to the snapshot’s LSN.
    • On startup:
      • Load the latest snapshot (if any) into memory.
      • Replay the WAL from the snapshot’s LSN to apply all subsequent PUT/DELETE operations.
      • Re‑establish the LRU lists and quota counters from the loaded state.
    • This is analogous to Redis’s RDB + AOF approach.

    3.4 Invalidation Subsystem

    • The backing data sources (e.g., primary databases) publish invalidation events to a message bus (Kafka, Pulsar, etc.). Each event contains:
      • key (or key prefix)
      • Optional tenant_id
      • Reason (e.g., “update”, “delete”)
    • Each cache node runs a consumer that subscribes to the bus. Messages are partitioned by key so that a given key is always delivered to the node that owns its shard.
    • Upon receiving an event:
      1. Check if the key belongs to this shard; if not, ignore.
      2. If present in memory, remove it (also delete from RocksDB and log the delete).
      3. If not in memory, still issue a delete to RocksDB to guarantee removal (idempotent).
    • TTL‑based expiration is handled by a background sweeper that scans the in‑memory map for expired entries (using a min‑heap of expiration times) and evicts them.

    3.5 Quota & Fairness Manager

    Each tenant may have a quota:

    • max_entries (number of items) OR
    • max_bytes (total memory used by cached values).

    The Fairness Eviction Policy ensures that tenants cannot exceed their quotas and that over‑quota tenants are penalized first when global memory pressure occurs.

    Algorithms:

    put(tenant, key, value, ttl?)

    lock(node):
      size = value.length + overhead
    
      // 1. Enforce tenant quota
      if tenant.hasQuota:
        while (tenant.used_bytes + size > tenant.max_bytes) and (tenant has entries):
          evictFromTenant(tenant)   // removes LRU entry of this tenant
    
        if tenant.used_bytes + size > tenant.max_bytes:
          unlock(node)
          return QUOTA_EXCEEDED   // cannot make room
    
      // 2. Enforce global capacity
      needed = (total_used_bytes + size) - global_max_bytes
      while needed > 0:
        // Prefer evicting from over‑quota tenants
        victimTenant = findHighestUsageRatioTenantExceedingQuota()
        if victimTenant != null:
          victim = victimTenant.lru.getOldest()
          evictEntry(victim)   // removes from memory & RocksDB
          needed -= victim.size
        else:
          // No over‑quota tenant: evict global LRU
          victim = global_lru.getOldest()
          if victim == null: break   // should not happen if global full
          evictEntry(victim)
          needed -= victim.size
    
      // 3. Insert the new entry
      entry = new CacheEntry(key, value, tenant, size, ttl)
      insertIntoMemory(entry)   // add to hash map, global LRU head, tenant LRU head
      RocksDB.put(key, serialized(entry))   // durable
      tenant.used_bytes += size
      total_used_bytes += size
      unlock(node)
    

    evictFromTenant and evictEntry also delete from RocksDB and update counters.

    evictFromTenant(tenant)

    entry = tenant.lru.getOldest()
    if entry != null:
      removeFromMemory(entry)
      RocksDB.delete(entry.key)
      tenant.used_bytes -= entry.size
      total_used_bytes -= entry.size
    

    The per‑tenant LRU list is updated accordingly.

    Global eviction loop

    The loop runs until total_used_bytes <= global_max_bytes.
    If after evicting all entries of over‑quota tenants we still need space, we fall back to the global LRU (which may include entries of under‑quota tenants). This protects well‑behaved tenants as long as possible.

    Note on fairness: Over‑quota tenants lose their least recently used entries first, even if those entries are relatively fresh. This creates a strong incentive to stay within quota and prevents a “rich tenant” from crowding out others.

    3.6 Statistics & Monitoring

    • Counters: hits, misses, evictions_total, evictions_tenant[tenant], quota_violations.
    • Gauges: memory_used_bytes, tenant_used_bytes[tenant], queue_depth.
    • Exposed via Prometheus endpoint or similar.

    4. API Specification

    All APIs are tenant‑aware; the tenant identifier is derived from authentication tokens (e.g., JWT) and injected by the router.

    MethodSignatureDescription
    GETbyte[] get(String key)Return cached value or null on miss. Updates LRU.
    PUTvoid put(String key, byte[] value, Optional<Long> ttl_sec)Insert or update. May trigger eviction.
    DELETEvoid delete(String key)Remove a specific key (admin or owner).
    INVALIDATE(admin only) void invalidate(String key)Force removal (used by data sources).
    ADMIN SET_QUOTAvoid setQuota(String tenant_id, Quota quota)Configure per‑tenant limits.

    Errors: QUOTA_EXCEEDED, NODE_UNAVAILABLE, etc.


    5. Failure Handling & Recovery

    5.1 Node Crash and Restart

    1. Load the latest snapshot (if any) into memory, reconstructing hash map, LRU lists, and quota counters.
    2. Replay the WAL (RocksDB’s WAL) from the snapshot’s LSN forward, applying all PUT/DELETE operations. This brings the in‑memory state to exactly what it was at the moment of the crash.
    3. Re‑open RocksDB (it already contains the durable data; replaying the WAL ensures its state is consistent).
    4. Re‑join the cluster (announce shard ownership to the router).
    5. Resume consuming invalidation messages (starting from latest offset).

    The recovery time is dominated by the snapshot size. Snapshots can be taken incrementally (copy‑on‑write) to minimize impact.

    5.2网络分区或节点故障

    • Router detects node failure via heartbeats and redirects requests to other nodes if shard replication is enabled.
    • For high availability we can add replicas: each shard has a primary and one or more secondaries. Writes are synchronously or asynchronously replicated. The basic design above can be extended with a consensus protocol (e.g., Raft) to keep replicas consistent.

    5.3 Invalidation Bus Outage

    • If the invalidation channel is temporarily unavailable, the cache may serve stale data until the channel recovers or TTL expires.
    • The cache still uses TTL as a safety net; all entries can have a reasonable maximum TTL (e.g., 24 h) to bound staleness.

    6. Scalability and Sharding

    • Keyspace Partitioning: Use consistent hashing (e.g., MurmurHash3) to assign each key to one of N shards (nodes). The router knows the mapping; nodes only handle keys belonging to their range.
    • Scaling out: Add new nodes; the router redistributes ranges. Rebalancing can be done online with minimal disruption (moving only keys in the affected range).
    • Local Persistence: Each node stores its own data on local SSDs; no cross‑node storage dependencies.
    • Invalidation Routing: The invalidation bus is keyed; consumers filter by shard responsibility. This ensures each node only processes events for its own keys.

    7. Trade‑offs and Design Decisions

    DecisionReasoningTrade‑off
    In‑memory + RocksDB (mirrored)Guarantees that the on‑disk state exactly reflects the in‑memory cache, simplifying recovery and eviction.Extra write amplification: every eviction generates a delete to RocksDB.
    Per‑tenant LRU + Quota‑aware evictionSimple to implement, provides strong fairness guarantees.Additional memory overhead for per‑tenant lists and counters.
    Global lock on nodeCorrectness of LRU and counters is critical; a single lock avoids subtle races.Potential contention on very high QPS nodes; can be mitigated by lock striping or shard‑level locks.
    WAL + SnapshotsFast recovery (snapshot) and durability (WAL).Sn creation pauses writes or requires copy‑on‑write; WAL replay can be expensive after long intervals.
    Explicit invalidation via message busLow latency invalidation, strong consistency.Requires reliable bus; additional operational component.
    TTL as safety netBounds staleness even if invalidation is lost.May evict still‑fresh data, causing extra load on backend.
    No cross‑node replication (by default)Simpler, lower write latency.Single node failure loses its shard’s data. Can be added as an optional feature.

    8. Summary

    The presented design delivers a persistent, fair, and invalidation‑aware cache layer:

    • Persistence is achieved by mirroring all in‑memory entries to an embedded RocksDB with a write‑ahead log and periodic snapshots, enabling fast restart and crash recovery.
    • Invalidation is handled via an external message bus that delivers delete events; TTL provides a fallback to bound staleness.
    • Fairness is enforced through per‑tenant quotas and an eviction policy that first removes entries from over‑quota tenants, then falls back to global LRU. This prevents any tenant from monopolizing the cache.
    • Scalability is obtained by sharding the keyspace across independent nodes, each with its own local persistence and invalidation consumer.
    • The system can be extended with replication for high availability, rate limiting for request fairness, and more sophisticated LRU variants (e.g., segmented LRU) if needed.

    This design balances performance, durability, consistency, and fairness, making it suitable for multi‑tenant environments where cached data must survive restarts and resource usage must be equitably shared.

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.