System design practice

Replicated Git Storage

medium Based on a system published by GitHub replication consistency availability read-heavy real-world

GitHub's Spokes: three replicas per repository, quorum pushes, reads from any in-sync copy.

Solve it in your browser Read the lesson first

GitHub used to store each repository on a file server with a hot standby next to it, mirrored disk block by block with DRBD. The standby served nothing, a failover took the repository offline until it finished, and losing both servers of a pair took hundreds of thousands of repositories down.

DGit, later renamed Spokes, replicates at the Git level instead. Every repository lives on three file servers as three ordinary Git repositories. A proxy in front of them sends each push to all three, runs a three-phase commit and acknowledges it once at least two replicas have applied the same update. Each replica's checksum says whether it is up to date, so a fetch can go to any replica that is, usually the closest.

Functional requirements

After the commit, the replicas' new checksums are recorded in routes before the developer hears back.

Name the file servers fs: the tests in problem.proschi refer to them, to routes, and to the use case and scenario names above.

Scale

Constraints

What is given

problem.proschi declares the dev client and routes, a MySQL table of which file servers hold each repository and each replica's checksum (four replicas). Add the proxy, the file servers, the connections and the two use cases.

The simulation does not count copies: one write step with an x3 fan-out stands for the three replicas each taking the update, and a node's replicas share its load evenly. Replication lag, repair of a replica that fell behind and the choice of the closest replica are not modelled.

Based on

How your design is checked

You write the design as text in Proschi. Tests run in your browser: a simulation of the traffic above checks latency, availability, cost and what happens when a machine fails. How the simulation works.

Start designing

Lesson · 12 min read

Learn it: Replicated Git Storage #

Replicated Git Storage: three copies, a quorum, and reads from any of them #

What you'll learn #

The problem, explained #

GitHub stores every repository as a Git repository on a file server. For years each file server had a hot standby, its disk mirrored block by block with DRBD (a Linux tool that replicates a block device over the network). The standby served nothing, a failover took the repository offline until it finished, and losing both servers of a pair took many repositories down.

DGit, later renamed Spokes, replicates at the Git level instead: each repository is three ordinary Git repositories on three file servers. A proxy sends every push to all three, runs a commit protocol, and acknowledges once at least two have applied it. A checksum per replica tells which copies are up to date, so a fetch can go to any of them.

Two use cases:

Requirements. p99 (the latency that 99% of requests beat) under 100 ms for Push and 75 ms for Fetch; 99.99% availability for both; durable pushes; survival of any single machine, a file server included; $6,800 a month, routes included.

What is given. dev, the developer client, and routes, a MySQL table (four replicas) of which servers hold each repository and each replica's checksum. Such metadata usually already lives in a company's main database; the design is about the file servers.

What the tests check: the node fs has at least three replicas, and only the proxy reaches fs or routes. A push sends PREPARE and COMMIT to fs and then writes routes before responding, handles the failure of fs, and still answers 2xx in the "One replica down" scenario. A fetch SELECTs from routes before it reads fs.

The model simplifies: an x3 write stands for three replicas each taking the update, a node's replicas share its load evenly, and replication lag, repair and "closest replica" choice are not modelled.

Back-of-the-envelope #

The traffic is one slice of the fleet: 1k pushes and 20k fetches per second, one push in a thousand finding a replica down. Spokes as a whole holds over 38 million repositories and 36 million gists, each stored at least three times: the fleet's disk is three times its data.

at the proxy
21k rps
on the file servers
26k rps
file-server calls per push
6
one set of three, then with a server lost
43% → 65%
left for proxy and file servers
$5,200
QuantityArithmeticResult
Requests at the proxy1k + 20k21k rps
Fetch reads on fs20k × 1 replica20k rps
Push prepares on fs1k × 3 replicas3k rps (writes)
Push commits on fs1k × 3 replicas3k rps (writes)
Total on fs20k + 3k + 3k26k rps
Same, if a fetch read all three60k + 6k66k rps
routes reads / writes20k lookups / 1k checksum updates25% / 20%
Proxy replicas at 100%21k ÷ 2k11

Fetches dominate. Twenty fetches for every push: anything that multiplies read cost (reading every replica, reading routes many times) multiplies the biggest number in the table.

A push costs six calls: a prepare and a commit to every replica. given.proschi declares both PREPARE and COMMIT as writes on the file servers, so 1k pushes put 6k writes a second on fs, next to the 20k reads from fetches.

Sizing the file servers. The model gives a file server 20k reads or 20k writes a second. Both share the machine, so utilisation is the sum of the two shares. One set of three takes 26k of 60k, about 43%.

Proxy. At 2k rps per replica, 21k needs 11 replicas just to keep up; the p99 decides how many more.

Cost. routes costs $1,600 (4 × $400), a file server replica $500, a proxy replica $100. That leaves about $5,200 for proxy and file servers.

Deep dive The failure scenario, p99 and availability

p99. In "One replica down" the proxy's call to the dead server fails with -x, which the simulation charges as a 1,000 ms timeout. Only 0.1% of pushes take that path, so it sits beyond p99 and shows up at p99.9. That is realistic: a down replica costs a few slow pushes until the proxy marks it bad.

Availability. A push writes routes, a single-primary MySQL store. With replicas, failover keeps its writes available 99.995% of the time in the model. Three file server replicas make fs itself effectively always up.

Concepts #

Disk replication versus application-level replication #

Block-level replication (DRBD, RAID 1 across machines) copies bytes on disk without knowing what they mean. It is simple and works for any software, but the standby cannot serve traffic: its filesystem is not mounted while the primary writes to it. Failover means detecting the failure, promoting the standby, mounting and restarting services, with the data offline meanwhile.

Application-level replication copies meaningful operations. Git is ideal: a repository is immutable objects plus a few references (branch names pointing at commits), and Git already copies objects between repositories. If three servers each hold a full repository and agree on the references, all three serve reads, and any one can die without a failover.

Trade-offs. You build the replication logic (coordination, repair of a replica that fell behind, placement of replicas), and it only works for data whose semantics you control. Do not reach for it when an off-the-shelf replicated store (a database with built-in replication) already fits.

Quorums #

With N copies, a write quorum W means a write succeeds once W copies have it; a read quorum R means a read consults R copies. When R + W > N, every read overlaps at least one copy with the latest write. Dynamo-style stores use this rule directly.

Spokes uses N = 3, W = 2. A push succeeds on any two servers, so it survives one failure, and is never acknowledged on fewer than two, so one disk failure cannot lose it. Reads use R = 1, breaking the overlap rule (1 + 2 is not more than 3), but not blindly: the checksums in routes say which replicas have the latest state, and that lookup replaces the extra read.

To make the two-of-three commit atomic, the proxy runs a commit protocol: first ask every replica whether it can apply the update (a vote), then tell them to commit or roll back. GitHub calls its protocol a three-phase commit; this problem models the two steps that matter for load and latency, PREPARE and COMMIT.

When not to use quorums. When one primary with synchronous standbys is simpler and good enough, or when you cannot afford the extra latency of a round of votes.

Deep dive A quorum write in Proschi
title "Quorum write"

client "Client"   [Actor]
coord  "Coordinator" [Service] x2
store  "Replicas" [NoSQL Database] x3

client -> coord : HTTPS
coord  -> store : replicate

usecase "Write" {
  client -> coord : PUT /items/1
  alt "All up" {
    coord  -> store : x3 WRITE item 1
    store --> coord : 3 acks
  } alt "One down" {
    coord  -x store : WRITE item 1 on the failed replica
    coord  -> store : x2 WRITE item 1
    store --> coord : 2 acks, quorum
  }
  coord --> client : 200
}

Version metadata for safe reads #

Reading "any replica" is safe only if you know which are current: one may have missed a push while down, or still be catching up. Spokes keeps a checksum per replica over the repository's references; equal checksums mean equal state. The proxy records new checksums after every commit and asks which replicas match before every read.

The general pattern: a small, strongly consistent metadata store (here MySQL) guards a large replicated data store. It gives read-your-writes (you always see your own latest write): a developer who pushes then fetches is sent to a replica that has the push. The cost is one lookup per read, so it must be cheap and the metadata store well replicated.

Designing it step by step #

1. Scope the problem #

Clarify: how many copies? (Three.) What does a push promise? (Durable on a quorum before 200.) Is a stale read acceptable? (No: a fetch must see the latest pushed state.) The read:write ratio? (20:1.) Which failures must be tolerated? (Any single server, without interrupting pushes.)

2. High-level design #

Developer → proxy → file servers, with the proxy also reading and writing routes. The proxy is the only thing that knows where repositories live; developers never address a file server.

Push: send the update to all three replicas, collect votes, commit, record checksums, answer. Fetch: ask routes which replicas are current, read one, answer.

Name the alternatives and why they lose:

AlternativeWhy it loses
The old active/standby pairThe standby does no work, and a failover stops pushes
Acknowledge after one replica, copy the rest asynchronouslyFast, but a push acknowledged by one server dies with it
Read all three and compareCorrect, but triples the dominant load

3. Deep dive #

Write the failure scenario explicitly. "One replica down" proves the quorum: one -x call to the dead server, the prepare and commit to the other two (x2), and still a 200. Steps after the alt (the routes update, the response) apply to both branches.

Size the file servers from the fan-out. A fetch is one read, a push three prepares and three commits. Remove one server from a set of three and check the push p99. If it breaks 100 ms, add sets with capacity { fs shards N }, not replicas per set: the problem fixes three copies per repository.

Size the proxy. From 21k requests at 2k per replica, add headroom until the latency limits hold with one replica gone. Most of the budget after routes goes to file servers, so do not overprovision it.

Budget check. Replicas times shards times $500 for the file servers, plus proxy replicas at $100, plus $1,600 for routes.

4. Wrap-up #

Summarise: three Git-level replicas per repository, a two-of-three commit, checksums so a fetch reads one current replica, and enough sets of three that losing a server does not hurt latency. Next: automatic repair of a stale replica, replicas across racks or data centers (GitHub's "Stretching Spokes"), and reads from the closest current replica.

Common mistakes #

The active/standby pair (wrong/active-standby-pair.proschi). GitHub's design before DGit: one active file server per repository with a DRBD standby that serves no reads; during a failover, pushes return 503. It fails "Every repository lives on three file servers behind a proxy" (fs has one replica) and "A push commits on a quorum of replicas" (the down scenario does not succeed).

Acknowledge after one replica (wrong/ack-after-one-replica.proschi). A primary takes the push and answers; the other two copy it asynchronously. With the primary down, pushes fail until someone takes over, and a push it alone acknowledged is lost if it dies before copying. It fails "A push commits on a quorum of replicas".

Read any replica blindly (wrong/read-any-replica-blindly.proschi). Fetches go to the nearest replica without checking routes, and one that missed a push serves old references: a developer pushes, fetches, and does not see their own commit. It fails "A fetch reads one replica that is up to date", which checks that the fetch consults routes before fs.

Read every replica and compare (wrong/read-every-replica.proschi). Correct answers, tripled cost: an x3 fetch turns 20k fetches into 60k reads. It passes with every server up but fails survive any node failure: a set that loses a server can no longer carry the tripled reads within the latency limits.

In the interview #

Lead with the insight, then draw the push with its quorum and the fetch with its metadata lookup, and do the fan-out arithmetic.

Expected follow-ups:

Further reading #

Now design it

Review cards for this problem

Short questions on the ideas it needs, from the review cards. Review them daily so they stick.

More system design problems