System Design Interview: Replicated and Strongly Consistent Key-Value Store

Designing a replicated and strongly consistent key-value store, which sounds seemingly simple, is actually quite a tricky interview question. You’d need to have a good understanding of some of the distributed systems concepts to be able to answer this question well. If you’re not in a domain specific interview, for this kind of questions, chances are that the interviewer just wants to observe how well you can navigate through a complex design problem. In that case, the discussion itself is usually more important than the final solution. So rather than just giving you the straight answer, I think it’d be more fruitful to walk through the thought process of arriving at various solutions. That’s what I plan to do in this blog post.

Analyze the Question

First and foremost, let’s unpack the question. There are 3 key phrases in the question:

1. Key-value store. It’s a store of key-value pairs. The canonical interface includes a Put(key, value) to write a new pair and a Get(key) to retrieve the value of a given key.
2. Replicated. The key-value store is replicated in multiple machines for high availability. Put and Get can be invoked on any machine, though the machine could proxy to other machines under the hood.
3. Strongly consistent. The client-observed behavior is strongly consistent. This is a key concept. More on this later.