Design a Distributed Cache (Memcached/Redis)

A custom distributed key-value store provides high-throughput, low-latency in-memory data cache serving.

1. High-Level Design

To scale an in-memory database beyond a single machine's RAM, data must be partitioned across clusters.

Client App ---> Consistent Hashing Ring (routes to Shard Master)
                        |
            [Cache Shard 1] [Cache Shard 2] [Cache Shard 3]

Components

1. Consistent Hashing Client: Routes keys to specific server nodes based on virtual node mapping rings.

2. In-Memory Cache Node: Stores data in memory. Written in Rust or C++.

3. Eviction Handler: Prunes memory keys using Least Recently Used (LRU) algorithms.

4. Cluster Coordinator: Uses ZooKeeper or Raft to manage node heartbeats and cluster mappings.

2. Potential Deep Dives

• LRU Cache Implementation Details:

Implement LRU using a combination of a Doubly Linked List (to keep track of access ordering in O(1)) and a Hash Map (to lookup items in O(1)).

• Cache Eviction Policies:
• LRU: Evicts least recently accessed items.
• LFU: Evicts least frequently used items.
• TTL: Evicts keys that exceed their configured Time-To-Live.

3. References & Tech Blogs

• Redis Documentation: Eviction Policies and Key Allocations
• Facebook Engineering: Scaling Memcache in Facebook Infrastructure