Design a Key-Value Store (Distributed Cache)

To design a distributed key-value store like Redis at Amazon scale, I first clarify that we likely need high write throughput with eventual consistency for user session data. I propose an architecture where clients compute hash rings to route requests directly to specific nodes, eliminating a central bottleneck. For data distribution, I will use consistent hashing. Unlike simple modulo hashing, consistent hashing places keys on a virtual ring, ensuring that when a node fails or is added, only a small fraction of keys need to move to adjacent nodes, maintaining stability during scaling events. Regarding the CAP theorem, given Amazon's global footprint, I prioritize Availability and Partition Tolerance over strong consistency. We will implement asynchronous replication across multiple nodes within a region, allowing reads to proceed even if some nodes are unreachable. To handle node failures, each key is replicated to N neighbors on the ring. If a primary node fails, the system automatically promotes a replica to primary using a lightweight consensus protocol or vector clocks to resolve conflicts. This approach ensures the system remains operational during network partitions while keeping latency low for customers reading their session data.