Design a Distributed Storage System

Understanding the prompt

A Nutanix interviewer writes one line on the board: design a distributed storage system. Sometimes it arrives as a distributed key-value store, sometimes as a replicated database, sometimes as write-heavy storage that must not lose data. It's the same problem underneath. You are being handed what the company builds: a layer that spreads data across a cluster of machines and keeps it alive when those machines fail. The round grades how you reason about that. Requests per second matter much less.

So start by saying what "storage system" means here in one honest sentence, then bound it. Treat it as a store that accepts a write for a key, puts the value on more than one machine so a single failure never loses it, and serves a read back with a consistency guarantee you can name. Everything the round cares about hangs off that sentence: partitioning, replication, consistency, failure handling, durability. State it, then start bounding. A minute spent scoping keeps the design coherent when the interviewer starts pushing.

The Nutanix angle

Design is offer-gating at Nutanix, and this prompt is where it gets decided. Strong coders get turned down here on a weak design conversation. This prompt carries the round because it puts every axis the interviewer probes on one board: partition the keyspace, replicate it, choose a consistency model, survive a dead node, guarantee durability. Miss any of them and there is nowhere to hide. So don't sketch a happy path and wait for questions. Lead with the data and its durability, pick a CAP position and defend it, and reason out loud the whole way. A candidate who talks fluently about quorums, write-ahead logs, and what happens when the cluster splits sounds like someone who could own a piece of a Nutanix system.

Scoping the requirements first

Pin the functional surface plainly, because it is small and that is a feature. A client writes a value for a key. A client reads the value back for a key. The value is replicated so a machine dying does not lose it, and the cluster grows by adding machines without a rewrite. Delete and update fold into write. That is the whole API, and keeping it that small is what lets the conversation go deep on the hard part instead of sprawling across features.

The non-functional bar is the real content, so ask for it before you draw. Is the workload read-heavy or write-heavy, because Nutanix loves the write-heavy shape and it changes what you optimize. How much data, so you know whether one machine could ever hold it (it cannot, which is why the thing is distributed at all). And the question that decides everything downstream: when a network partition splits the cluster in two, do you keep serving writes and reconcile later, or refuse writes to stay consistent? Name that trade-off out loud. Hand-waving past it is the fastest way to read as shallow on a storage loop.

• Durability is non-negotiable: never lose an acked write. This is a storage company, so a lost write is the cardinal sin, not an annoyance the user redoes. Once the system tells a client "written," that value survives a node dying. Every later choice, the write-ahead log, the replication factor, the quorum, exists to honor that one promise.
• Consistency is a dial: pick a point on CAP. You cannot have perfect consistency and full availability during a partition, and the interviewer knows it. Decide whether a read always sees the latest acked write or whether stale reads are acceptable for higher availability, and justify the choice against the workload rather than defaulting to "strong" by reflex.
• Availability under failure: nodes die, the cluster does not. A single machine failing must be a shrug, not an outage. Reads and writes keep flowing while a node is down and while its data is being re-replicated elsewhere. The design has to name what a client sees during that window.
• Scale by adding machines: partition, do not vertically grow. The dataset outgrows any single box, so the keyspace is split across nodes and the cluster scales by adding more. Rebalancing when a node joins or leaves must move a small fraction of the data, which is exactly why consistent hashing shows up.

Estimation, with illustrative numbers

Do the arithmetic out loud, and flag every number as a back-of-envelope illustration rather than a real spec. The interviewer is checking whether you can reason from an assumed workload to a cluster size and a durability budget, not whether you memorized a benchmark. Keep the numbers round and let them drive the decisions. A candidate might reason like this.

Assume:
  logical dataset            ~100 TB of key-value data
  average value size         ~10 KB  -> ~10 billion keys
  replication factor         3 copies of every partition
  physical footprint         ~100 TB x 3 = ~300 TB stored
 
Nodes:
  usable capacity per node   ~10 TB
  -> ~30-40 data nodes to hold it, plus headroom for growth
 
Throughput (illustrative):
  writes    ~100k / sec sustained, bursty
  reads     ~500k / sec  (read-heavy variant) or ~roughly equal (write-heavy)
  -> single machine cannot serve this: spread load across the cluster

Two conclusions fall straight out of the math, so say them. First, no single node holds the data or serves the load, so the keyspace has to be partitioned across the cluster, which is the next section. Second, at replication factor three the durability story becomes concrete. The system survives losing any one node with room to spare, and can be tuned to survive two, at the cost of storing three copies. Say that the copies triple the raw storage bill, and that this is the deliberate price of never losing an acked write. The round rewards that honesty about cost.

The high-level architecture

With the scale named, the architecture is the wiring, so draw it and read it by role. Blue is the actor at the edge, the client that writes and reads keys. Violet is the services that route and repair. Green is the state the system owns: the ring and membership metadata, the replicas that hold the data, and the write-ahead log that makes a write durable. Follow a write top to bottom: the client hits the coordinator, which hashes the key against the ring to find the partition's replicas. It forwards the write to the partition leader, which logs it durably and replicates it to its followers. A read resolves the same replica set and gathers a quorum. Off to the side, a failure detector watches the nodes and re-replicates data when one dies.

Partitioning with consistent hashing

The data does not fit on one machine, so the keyspace gets split. The naive split, hash the key and take it modulo the node count, is a trap, and saying why out loud scores points. The moment you add or remove a node the modulus changes, so almost every key now maps to a different node and nearly the whole dataset has to move. That is a cluster-wide reshuffle every time the topology changes, which at a storage company is a non-starter.

Consistent hashing fixes it. Map both keys and nodes onto the same hash ring, and a key belongs to the first node clockwise from where it lands. Adding a node now only steals the slice of the ring between it and its neighbor, so only a small fraction of keys move. Removing a node hands its slice to the next node along, again touching only that slice. Give each physical machine many virtual nodes scattered around the ring. Load then spreads evenly, and a departing machine's data is rebuilt from many sources in parallel instead of dumped on one unlucky neighbor. The replicas for a partition are the next few distinct nodes clockwise, so placement and replication use the same ring.

Replication and consistency: the graded core

This section carries most of the round. Every partition lives on the replication factor's worth of nodes, three in our sizing, and the design turns on how those copies stay in agreement and what a client is promised. There are two families of answer. Name both, pick one for the stated workload, and defend the pick. Presenting a single architecture as the only option reads as weak.

The first family is leader-based, sometimes called master-replica. One replica per partition is the leader, all writes go through it, it orders them and ships them to the followers. Ordering through a single leader makes strong consistency clean, because there is one authority on what happened and in what sequence. The cost is that the leader is a write bottleneck and a failure point, so you need fast, correct failover. The second family is leaderless and quorum-based, in the Dynamo mold. There is no leader; a write is sent to all replicas and succeeds once W of them acknowledge, and a read gathers R of them. When W plus R is greater than the replication factor N, any read is guaranteed to overlap the latest write and see it. Set W and R to tune the balance: a high W gives durable, strongly consistent writes at the cost of write availability, a low W with a high R flips it.

N = 3 replicas per partition
 
Strong-ish, balanced:
  W = 2, R = 2   ->  W + R = 4 > 3   read overlaps latest write
  survives 1 node down for both reads and writes
 
Write-optimized (higher availability for writes):
  W = 1, R = 3   ->  fast acks, but a read must consult all copies
Read-optimized:
  W = 3, R = 1   ->  every copy current, but a write needs all 3 up
 
Rule of thumb:
  W + R > N  gives read-your-writes consistency
  W + R <= N gives higher availability, weaker guarantees (stale reads)

Now place the design on the CAP triangle deliberately, because a partition forces the choice and the interviewer will introduce one. When the network splits the cluster and a replica set straddles the divide, you get exactly one of two behaviors. Refuse writes that cannot reach a quorum, and you have chosen consistency over availability: no client ever reads stale data, but some writes fail during the split. Accept writes on whichever side is reachable and reconcile afterward, and you have chosen availability: writes always succeed, but two sides can diverge and a later read might be stale until they merge. Neither is wrong. The judgment is picking the one that fits the workload, a config store leans consistent, a shopping cart leans available, and saying which and why.

The Nutanix angle

Don't default to "strong consistency" by reflex; earn the choice. The weak answer picks strong consistency because it sounds safe, then can't explain what the system does when a partition makes it impossible to keep serving. The strong answer treats consistency as a dial, says where it set the dial for this workload, and names the price. Say the prompt is a config or metadata store where a stale read is dangerous. Choose consistency, route writes through a leader or demand a write quorum, and accept that a partition can block some writes. For a high-write, availability-first store, choose a quorum with room to stay available and accept eventual convergence. Then explain how conflicts resolve: last-writer-wins by version, vector clocks, or a merge function. Own the trade-off openly, and the design bends under the interviewer's partition instead of snapping.

The write path and the read path

Walk a single write end to end, in order, because the order is the durability guarantee. The client sends put(key, value) to a coordinator. The coordinator hashes the key on the ring and finds the replica set. It routes to the leader (or fans out to all replicas in the leaderless design). The receiving replica appends the record to its write-ahead log and flushes it to disk before anything else, so the write survives a crash from this instant on. Only then does it apply the change to its in-memory structures. The write is replicated to the other copies, and once the required number of acknowledgments arrives, W of them, the coordinator tells the client the write succeeded. Log first, apply second, acknowledge only after enough durable copies exist: that sequence is what lets the system promise it never loses an acked write.

The read path is shorter but has its own honesty. The coordinator resolves the replica set and, in the quorum design, asks R replicas for their copy along with a version. If the copies agree, it returns the value. If one replica lagged or missed a write during a blip, it returns the newest version by the versioning scheme and starts a read repair, writing the fresh value back to the stale replica so the divergence heals. In the leader-based design, a read can go to the leader for the freshest value or to a follower for a cheaper, possibly stale one. Which you allow is a consistency knob you should name, since under replication lag a follower read can be behind. If the use case needs read-your-writes, route those reads to the leader or require the overlapping quorum.

Failure handling

A design that only runs when every node is up is not a distributed storage design. Name the failure modes and show the machinery that absorbs each, because at a storage company this is the part the interviewer leans on hardest.

Split-brain deserves its own beat, because it is the classic trap. A network partition can leave two sides each convinced the other is dead. If both elect a leader for the same partition and both accept writes, the copies diverge and you have corrupted the single source of truth. The defense is to require a majority quorum for any leadership or write decision. Only the side holding a majority of replicas can make progress; the minority side refuses writes instead of inventing a second reality. That is the CAP choice made concrete. During a partition the minority side gives up availability to protect consistency, and when the partition heals, its replicas catch up from the side that stayed authoritative.

Durability: write-ahead log and checkpoints

Durability is the headline requirement at a storage company, so make it explicit instead of assuming replication covers it. Two mechanisms work together. Across machines, the replication factor means an acked write already lives on multiple nodes in separate failure domains, so losing one machine loses no data. Within a machine, the write-ahead log means a write survives a crash before it has been folded into the main data structures. The record is appended to an append-only on-disk log and flushed before the write is acknowledged. A node that crashes and restarts replays its log and recovers every acked write.

Checkpoints keep the log from growing without bound. Periodically the node flushes its applied state to disk as a checkpoint and truncates the log up to that point, so crash recovery replays only the tail since the last checkpoint. This is the standard log-structured pattern: fast sequential writes to the log on the hot path, with background compaction and checkpointing to keep reads and recovery bounded. Say plainly that the log flush makes an acknowledgment trustworthy. Replication is what lets durability survive the loss of a whole machine as well as a process. You need both for the durability story.

Bottlenecks and trade-offs

Name where the design strains and what you traded to relieve it. Calling out the pressure points before the interviewer does reads as senior. On a storage loop these are specific worries, well beyond generic web scale.

• Consistency vs availability: the trade you cannot escape. CAP is not a footnote here, it is the spine. Stronger consistency (higher write quorum, leader routing) means some writes fail during a partition; higher availability means reads can go stale and copies can diverge until they reconcile. The design names its choice per workload instead of pretending it can have both.
• Write amplification: the price of durability. Replication factor three plus a write-ahead log means every logical write becomes several physical writes across nodes and disks. That triples storage and multiplies write IO. It is the deliberate cost of never losing an acked write, and stating it shows you know durability is not free.
• Hot partitions and skew: even hashing, uneven keys. A popular key or a hot range can overload the one replica set that owns it, and consistent hashing spreads keys, not access. Virtual nodes smooth capacity but not a single blazing-hot key, so name the real fixes: split the hot partition, add caching in front, or replicate the hot key more widely for reads.
• Leader as a bottleneck: the cost of clean ordering. Routing every write for a partition through one leader buys clean ordering and easy strong consistency, but the leader caps that partition's write throughput and is a failure point needing fast election. The leaderless quorum design removes the bottleneck at the cost of conflict resolution. Which you pick follows from the consistency choice.

What the interviewer probes

The round escalates by pushing on the pressure points, and the strong answers are already latent in the design if you built it in the order above. The pushes cluster into a few predictable places, and each one has an answer you have already laid the groundwork for.

On consistency: "a partition splits the cluster, what does a client see?" Answer with the CAP choice you already made: the majority side keeps serving, the minority refuses or degrades, and reconciliation heals it. On durability: "a node crashes right after acking a write, is it lost?" No, because the write was in the flushed log and on a quorum before the ack, and recovery replays the log. On failure, "the leader dies mid-write, now what?", leader election promotes a caught-up replica, the unacked write is retried, and nothing acked is lost. On scale: "you add ten nodes, how much data moves?" Only the ring slices the new nodes claim, a small fraction, thanks to consistent hashing. On the hard follow-up, "two replicas disagree on a read," read repair returns the newest version and writes it back, and anti-entropy heals the rest. If the interviewer morphs the prompt toward a neighboring shape (the pub/sub bus, the backup service, the active-replica router, config propagation), the same primitives carry them all: partitioning, replication, quorum, leader election, and a durable log.

The Nutanix angle

Build from the data up, and the design answers the questions for you. Nutanix runs this round to see whether you reason about distributed systems from first principles or recite a rehearsed diagram, and the tell is what happens when the design is pushed. So construct it in the order the constraints demand. Start with the data and its durability, the write-ahead log and the replication factor. Decide the consistency the workload truly needs and set the quorum or the leader to honor it. Partition with consistent hashing so growth is cheap. Add the failure machinery, detection, election, re-replication, anti-entropy, so a dead node is a shrug. Do that, and when the interviewer kills a node or splits the network, you are not scrambling for a new idea; you are reading a consequence off a design that already accounts for it. That composure, built on fundamentals rather than a template, is what turns this offer-gating round into an offer.