Ranked Cache System

Problem and Scope

Design and implement a ranked cache system.

Primary goal: store key-value pairs with efficient reads/writes and evict items based on a rank metric (e.g., popularity/frequency/custom). Support Put(key,value,rank), Get(key), Evict(), UpdateRank(key,newRank). Consider both single-instance and distributed modes, with high throughput, low latency, and scalable design.

Start by confirming the core user journey, exclusions, success criteria, and the constraints that materially affect the architecture.

Requirements to Clarify

A strong answer should establish scope before choosing components.

Functional requirements:

• Put(key, value, rank): insert/update entry with rank
• Get(key): return value if present
• Evict(): when full, remove lowest-ranked item
• UpdateRank(key, newRank): change rank efficiently

Non-functional requirements:

• Low latency lookups (≈O(1))
• High throughput for reads/writes
• Scalable across nodes for large datasets
• Thread-safe concurrent operations
• Support optional TTL/expiration and metrics

Scale and Capacity

Use the workload to justify storage, partitioning, caching, and reliability decisions. Clarify or challenge these assumptions rather than treating them as unquestionable facts:

• Single shard: 1M items, reads 50k/s, writes 5k/s as a baseline.
• Cluster: 100 shards → 100M total items, reads 5M/s.
• Memory per entry: key 50B, value avg 200B, metadata 32B → ~282B/entry.
• Network: expect cross-shard traffic only for routing/replication; item reads should be local to shard.
• Eviction rate depends on write arrival and capacity; design for O(log n) rank ops.

Architecture Discussion

Walk through the important read and write paths, identify ownership boundaries, and explain how the design behaves when dependencies fail. Cover these areas explicitly:

• Definition, ownership, and update frequency of the rank function
• Hash-map and ordered-index data structures with complexity guarantees
• Concurrent GET, PUT, rank update, expiration, and eviction semantics
• Byte capacity, admission control, rank aging, pinned entries, and TTL interaction
• Sharding, routing, replication, and the limits of global ranking across shards
• Crash recovery, backing-store integration, hot keys, metrics, and rebalancing

Follow-up Questions

Expect the interviewer to test the consequences of your choices. Practise answering these questions with a concrete decision, its benefit, and its cost:

• What does "rank" represent? (frequency, score from external system, TTL-weighted score)
  • Focus: Assess the candidate's answer to "What does "rank" represent? (frequency, score from external system, TTL-weighted score)" for explicit assumptions, a workable mechanism, failure behavior, and consequential trade-offs.
• Is rank monotonic or can it decrease?
  • Focus: Assess the candidate's answer to "Is rank monotonic or can it decrease" for explicit assumptions, a workable mechanism, failure behavior, and consequential trade-offs.
• Should rank be updated on every Get or batched?
  • Focus: Assess the candidate's answer to "Should rank be updated on every Get or batched" for explicit assumptions, a workable mechanism, failure behavior, and consequential trade-offs.
• Capacity unit: number of items or bytes?
  • Focus: Assess the candidate's answer to "Capacity unit: number of items or bytes" for explicit assumptions, a workable mechanism, failure behavior, and consequential trade-offs.
• Consistency model across replicas: eventual or strong?
  • Focus: Assess the candidate's answer to "Consistency model across replicas: eventual or strong" for explicit assumptions, a workable mechanism, failure behavior, and consequential trade-offs.
• Required SLAs for latency (e.g., 1ms lookup)?
  • Focus: Assess the candidate's answer to "Required SLAs for latency (e.g., 1ms lookup)" for explicit assumptions, a workable mechanism, failure behavior, and consequential trade-offs.
• Support weighted rank combining frequency and recency (e.g., rank = alphafreq + betarecency).
  • Focus: Assess the candidate's answer to "Support weighted rank combining frequency and recency (e.g., rank = alphafreq + betarecency)." for explicit assumptions, a workable mechanism, failure behavior, and consequential trade-offs.
• Support size-aware eviction (evict by lowest rank/byte ratio).
  • Focus: Assess the candidate's answer to "Support size-aware eviction (evict by lowest rank/byte ratio)." for explicit assumptions, a workable mechanism, failure behavior, and consequential trade-offs.
• Global ranking across shards: design aggregator and migration plan.
  • Focus: Assess the candidate's answer to "Global ranking across shards: design aggregator and migration plan." for explicit assumptions, a workable mechanism, failure behavior, and consequential trade-offs.
• Integrate with write-through to backing store with crash recovery.
  • Focus: Assess the candidate's answer to "Integrate with write-through to backing store with crash recovery." for explicit assumptions, a workable mechanism, failure behavior, and consequential trade-offs.
• Allow per-key eviction policies (some keys pinned or protected).
  • Focus: Assess the candidate's answer to "Allow per-key eviction policies (some keys pinned or protected)." for explicit assumptions, a workable mechanism, failure behavior, and consequential trade-offs.

Evaluation Rubric

MockMe evaluates the answer across the following dimensions. A complete answer should connect claims to requirements and explain consequential trade-offs.

• Requirements and scope (15%): Clarifies and prioritizes the required behavior for Put(key, value, rank): insert/update entry with rank; Get(key): return value if present; Evict(): when full, remove lowest-ranked item. Establishes the constraints that materially affect Ranked Cache System, including Low latency lookups (≈O(1)); High throughput for reads/writes. Strong evidence includes Separates the critical path from secondary features and resolves ambiguous requirements before choosing components.
• Architecture and interfaces (20%): Presents coherent ownership boundaries and end-to-end flows covering Definition, ownership, and update frequency of the rank function; Hash-map and ordered-index data structures with complexity guarantees; Concurrent GET, PUT, rank update, expiration, and eviction semantics; Byte capacity, admission control, rank aging, pinned entries, and TTL interaction. Strong evidence includes Defines interfaces and traces important success, retry, and failure paths across the proposed components.
• Data and scaling (25%): Uses workload assumptions such as Single shard: 1M items, reads 50k/s, writes 5k/s as a baseline; Cluster: 100 shards → 100M total items, reads 5M/s to justify capacity and partitioning decisions. Explains the data, state, or model strategy for Definition, ownership, and update frequency of the rank function; Hash-map and ordered-index data structures with complexity guarantees; Concurrent GET, PUT, rank update, expiration, and eviction semantics. Strong evidence includes Quantifies a dominant workload, identifies the first bottleneck, and explains how the design evolves as that workload grows.
• Reliability, correctness, and safety (20%): Explains concrete failure behavior, recovery, and operational safeguards for Crash recovery, backing-store integration, hot keys, metrics, and rebalancing. Strong evidence includes States the required correctness or consistency boundary and covers retries, partial failure, observability, and safe degradation.
• Communication and trade-offs (20%): Drives a structured discussion and compares consequential alternatives for Byte capacity, admission control, rank aging, pinned entries, and TTL interaction; Sharding, routing, replication, and the limits of global ranking across shards; Crash recovery, backing-store integration, hot keys, metrics, and rebalancing. Strong evidence includes Makes assumptions explicit, answers the question asked, and explains both the benefit and cost of major decisions.