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
Push: a developer pushes commits and gets 200 once the update is committed on at least two of the repository's three replicas. Two scenarios:
"All replicas commit": all three file servers are up.
"One replica down": one of the three does not answer; the other two form a quorum and the push still succeeds.
After the commit, the replicas' new checksums are recorded in routes before the developer hears back.
Fetch: a developer fetches or clones a repository and gets 200 with a packfile. The proxy looks up which replicas are up to date and reads one of them.
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
Spokes holds over 38 million repositories and 36 million gists.
In this exercise, one slice of the fleet takes 1k pushes and 20k fetches per second at peak: most Git traffic is reads. One push in a thousand finds a replica down.
Constraints
Every repository on three file servers (fs with three replicas; add shards for more sets of three).
Nothing but the proxy talks to the file servers or to routes.
A push is durable on a quorum before the developer hears back, and still succeeds when one of its three servers is down.
p99 of Push under 100 ms, of Fetch under 75 ms; both available 99.99% of the time.
Losing any single machine, a file server included, must not break a latency limit.
At most $6,800 / month, routes included.
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
Patrick Reynolds, Introducing DGit, GitHub blog, April 2016: three copies of every repository on three servers, replication at the Git level instead of RAID and DRBD, reads load-balanced over the replicas without synchronisation, and new copies made automatically when a server fails.
Patrick Reynolds, Building resilience in Spokes, GitHub blog, September 2016: over 38 million repositories and 36 million gists, at least three copies of each, writes refused unless a majority of replicas (always at least two) can commit them, and routing that returns the replicas that are up to date.
Michael Haggerty, Stretching Spokes, GitHub blog, October 2017: Spokes across data centers, the three-phase commit and the quorum, a checksum computed for every replica after every update, and reads routed to the closest replica that is in sync.
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.
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:
Push: the developer gets 200 once the update is committed on at least two of three replicas. Scenarios: "All replicas commit" and "One replica down", where the push still succeeds on the other two. The new checksums are recorded in routes before the developer hears back.
Fetch: a developer fetches or clones. The proxy looks up which replicas are current, reads one, and returns a packfile (Git's compressed bundle of objects).
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.
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
Quantity
Arithmetic
Result
Requests at the proxy
1k + 20k
21k rps
Fetch reads on fs
20k × 1 replica
20k rps
Push prepares on fs
1k × 3 replicas
3k rps (writes)
Push commits on fs
1k × 3 replicas
3k rps (writes)
Total on fs
20k + 3k + 3k
26k rps
Same, if a fetch read all three
60k + 6k
66k rps
routes reads / writes
20k lookups / 1k checksum updates
25% / 20%
Proxy replicas at 100%
21k ÷ 2k
11
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.
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.
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] x2store "Replicas"[NoSQL Database] x3client -> coord : HTTPScoord -> store : replicateusecase"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}
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.
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.)
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:
Alternative
Why it loses
The old active/standby pair
The standby does no work, and a failover stops pushes
Acknowledge after one replica, copy the rest asynchronously
Fast, but a push acknowledged by one server dies with it
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.
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.
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.
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:
What if two replicas are down? No quorum, so the push fails rather than accept a write that exists on one server. Reads still work from the remaining current replica while new copies are made on other servers.
How does a replica that missed pushes catch up? A repair process finds it by checksum and syncs it from a current one with Git's own fetch before marking it current.
Why not R + W > N with R = 2? It doubles read load to get a guarantee the checksums already provide with one cheap lookup.
What if routes is down? It is replicated (four replicas here) and on every request's path, so its availability bounds the system's. A proxy cache of recent checksums could serve reads during a short outage, risking a stale read.
How do you spread across data centers? Replicas in different data centers, so a site loss leaves a quorum, and reads from the closest current replica ("Stretching Spokes").
Introducing DGit, GitHub blog, 2016: why GitHub moved from DRBD pairs to three Git-level replicas.
Building resilience in Spokes, GitHub blog, 2016: the two-replica minimum for every write, how a failed or lagging replica is detected and repaired, and routing to the replicas that are up to date.
Stretching Spokes, GitHub blog, 2017: the three-phase commit, the per-replica checksums, Spokes across data centers and reads from the closest in-sync replica.
awesome-scalability: "Distributed Repositories, Dependencies, and Configurations Management" lists the DGit post among related designs.
System Design Interview – An Insider's Guide, Vol. 1 (Alex Xu): "Design A Key-value Store", which covers replication, quorum consensus and handling failures.