System Design Starts with a Library, Not a Server

The one problem this whole series solves

Meera is the librarian at a school with 1,200 students. Every morning, a student runs to the desk asking for a book, and it has already gone to someone else. Meera wants one simple thing:

A student searches for a book on their phone, reserves it, and sees when it is ready at the desk.

Arjun, the computer-science teacher, offers to build it. (Meera, Arjun, the school and every number here are made up for teaching.)

This is guide 1 of 5. All five follow Meera and Arjun as the app grows from one school to forty. This guide covers the foundations and data: what to build, how big it will get, where data lives and what happens when copies disagree. Guide 3 picks up the same app when it needs messaging and workflows.

The rule for the whole series is the rule for an interview: nothing is added until a real problem forces it. Each section starts with the problem.

1. "What exactly are we building?": requirements first

Arjun's first instinct is to pick a database. Meera stops him: "What does a good library visit look like?" A student finding the right book quickly matters more than how many technology names appear in the diagram.

System design is the plan for how software parts work together to meet a need. It covers data, communication, speed, failures, security and cost.

• High-level design (HLD) chooses the big parts and how they relate. HLD might decide "there is a reservation service."
• Low-level design (LLD) explains the objects, interfaces, rules and algorithms inside those parts. LLD explains how that service prevents an invalid reservation.

Separate features from qualities

Functional requirements say what users can do. Non-functional requirements say how well the system must do it.

A useful design makes the qualities measurable. For this exercise we propose that 95% of searches finish within 300 milliseconds under the expected peak load. That is an assumption to discuss, not a universal target.

An invariant is a rule that must always remain true. Our central invariant, which every chapter protects, is: one physical copy can't have two active reservations.

Day one: the smallest design that works

For one school, Arjun's first version is one app server and one database:

Reading the figure. There are three parts and two arrows.

The legend at the bottom is used in every figure in this series. A coloured tile is a service (code that runs), a cylinder is a data store, and a line icon is a person, app or outside system.

The database is labelled Leader even though it is alone. That's the name it will keep when copies are added in chapter 6.

2. "Is it fast enough? For whom?": latency, throughput, capacity

The PE teacher complains that search "feels slow." Meera asks what "slow" means, and Arjun realises he needs words for it.

At a library desk, latency is how long one student waits for help. Throughput is how many students the desk helps per minute. Adding a second librarian may raise throughput, but it doesn't make one complicated request any quicker.

Averages hide slow users. If the p99 latency is two seconds, roughly 99% of requests finish within two seconds, and the slowest 1% take longer. Tail latency means that slow end of the distribution. The PE teacher was in the tail.

For a stable system, a useful estimate (Little's law) is:

average work in progress = average arrival rate × average time in the system

At 500 requests/s and 0.2 seconds average response time, about 100 requests are in progress at once. That's like 100 students standing at the desks. Keep the units consistent and the measurement boundaries matching. This estimate is no substitute for a load test.

3. "How big will this get?": estimates that change the design

The district hears about the app and wants it for all forty schools. Before Arjun builds anything bigger, he estimates. These planning numbers are invented:

• Daily searches: 100,000 × 20 = 2,000,000.
• Average search rate: 2,000,000 / 86,400 ≈ 23.1 searches/s.
• Assumed peak: 23.1 × 10 ≈ 231 searches/s.
• Raw reservation storage: 10,000 × 1,000 × 365 = 3.65 GB (decimal gigabytes). Three full copies would hold about 10.95 GB, before indexes, logs, backups and other overhead.
• Response traffic at peak: if a search response averages 20 KB, that is about 231 × 20 KB = 4.62 MB/s, or roughly 37 Mb/s before protocol overhead.

What the numbers tell Arjun. School opening hours create much sharper peaks than a daily average suggests (all forty schools ring the bell at 8 am). Ask for real measurements if they exist. Even so, these numbers are small. They suggest starting simple, with one application and an indexed database, then measuring. An estimate that says "you don't need anything fancy yet" is a useful estimate.

4. "Exam week made the app crawl": scaling out

In exam week, every student searches for the same revision guides at once. The single app server runs at 100% CPU, and searches take eight seconds.

There are two ways to grow:

flowchart LR
    subgraph V["Vertical scaling: a bigger desk"]
        V1@{ icon: "algomi:ext-device", label: "App on a small machine", pos: "b", h: 52 }
        V2@{ icon: "algomi:ext-device", label: "Same app on a larger machine, which still has a size limit", pos: "b", h: 52 }
        V1 -->|"more memory and processing power"| V2
    end
    subgraph H["Horizontal scaling: more desks"]
        LB@{ icon: "algomi:sec-lb", label: "Load balancer", pos: "b", h: 52 }
        H1@{ icon: "algomi:ext-device", label: "App copy 1", pos: "b", h: 52 }
        LB --> H1
        H2@{ icon: "algomi:ext-device", label: "App copy 2", pos: "b", h: 52 }
        LB --> H2
        H3@{ icon: "algomi:ext-device", label: "App copy 3", pos: "b", h: 52 }
        LB --> H3
    end

Reading the diagram.

• Vertical scaling (left) is moving Meera to a bigger desk. It's the same single deployment with a higher ceiling, but the ceiling still exists: there is a largest machine you can buy.
• Horizontal scaling (right) is opening more desks. The ceiling goes away, but now something, the load balancer, has to send each student to a desk. All the desks also have to share the same ledger.

Two more terms:

• Elasticity is the ability to grow and shrink with demand.
• Autoscaling is an automated mechanism for doing so, such as adding desks in exam week and closing them in the holidays.

An app is easier to scale horizontally when it doesn't keep essential user state only in one instance's memory. That doesn't mean the whole system has no state. It means a request can reach any desk and still work, because the ledger, not the desk, remembers the reservation.

Arjun also notices that most exam-week requests are the same catalogue lookups, over and over. So he adds a catalogue cache: a small, fast copy of popular entries (chapter 9 explains how it stays correct).

Reading the figure. The four parts marked NEW are this chapter's additions. Step 1's parts are unchanged.

Follow the arrows. spread goes from the load balancer to the copies. read first goes from an app to the cache, so the cache is tried before the database. write still goes only to the Leader. The cache never takes writes, so the ledger stays the single source of truth.

5. "Two students got the last copy": choosing storage

During exam week, two students tap Reserve on the last copy of a chemistry guide at the same moment, and both are told "Reserved." Meera has one book and two angry students. The invariant from chapter 1 was broken.

Pick storage by the questions it must answer

Arjun first asks whether his database was even the right kind. A database shouldn't be chosen just because it's popular. Start with access patterns: which data is read together, changed together and searched together?

SQL versus NoSQL is not the same thing as strong versus eventual consistency. Guarantees depend on the product, the operation, the topology and the configuration.

For the library, a relational database is a reasonable choice for reservations, because the core rule is a transaction rule. A search index can be added if text search outgrows the database. Cover images can live in object storage, with only their keys stored in the database.

Indexes and duplicate data

• An index is like the alphabetical index at the back of a book. It finds matching rows without scanning everything, at the cost of extra space and extra work on every write.
• Normalisation stores each fact in one clear home.
• Denormalisation keeps selected extra copies to speed up reads. If a read model stores an author's name beside every book, then a name change must update every copy, or tolerate a delay.

The fix: transactions and isolation

A transaction groups changes into one unit. ACID describes atomicity, consistency, isolation and durability. Here, consistency means preserving defined database rules. That's a different use of the word from replica consistency in chapter 7.

What went wrong:

sequenceDiagram
    participant A as Student A
    participant B as Student B
    participant D as Database
    A->>D: read copy 17: available = 1
    B->>D: read copy 17: available = 1
    A->>D: set available = 0, create reservation
    B->>D: set available = 0, create reservation
    Note over D: two reservations for one copy: invariant broken

Reading the diagram. Both students read before either one wrote, so both saw "available = 1" and both went ahead. The read and the write were two separate operations, and the other student slipped in between them. That gap is the bug.

The fix is to make "check and reserve" one indivisible step:

• A conditional update: UPDATE copies SET available = 0 WHERE id = 17 AND available = 1. Exactly one of the two updates can match a row.
• A transaction with appropriate locking.
• A database constraint, such as at most one active reservation per copy.

Isolation controls how concurrent transactions interact:

• Read Committed can let repeated statements see different committed values.
• Stronger isolation levels restrict more anomalies.
• Serializable execution behaves like some serial ordering, but applications may need to retry transactions that get aborted.

Exact behaviour varies by database (PostgreSQL isolation documentation). The fully worked example is in guide 5.

6. "Forty schools: one database isn't enough": replication and sharding

All forty schools are now live. Read traffic is heavy, and Arjun worries about what happens if the single database machine dies. He has two different tools, and they solve two different problems.

• Replication copies the same data. Two librarians each have a copy of the catalogue. This helps availability and read capacity, but copies can lag.
• Sharding divides the data. One cabinet holds some records, and another holds the rest. This spreads storage and write work, but queries across cabinets get harder.

flowchart TD
    R@{ icon: "algomi:svc-cube", label: "Request router", pos: "b", h: 52 }
    S1@{ icon: "algomi:data-cylinder", label: "Shard 1: schools A to M", pos: "b", h: 52 }
    R --> S1
    S2@{ icon: "algomi:data-cylinder", label: "Shard 2: schools N to Z", pos: "b", h: 52 }
    R --> S2
    P1@{ icon: "algomi:data-cylinder", label: "Replica of shard 1", pos: "b", h: 52 }
    S1 --> P1
    P2@{ icon: "algomi:data-cylinder", label: "Replica of shard 2", pos: "b", h: 52 }
    S2 --> P2

Reading the diagram. Read it in two directions.

• Across is sharding. The router sends each request to the cabinet that holds that school's records. A school's data lives in exactly one shard.
• Down is replication. Each shard has its own copy, for safety and extra reads.

The two tools combine: shards for size, replicas for resilience.

The alphabet ranges here only explain the idea. Real shard boundaries come from traffic, data size and query needs. One huge school could overload a shard on its own.

A partition is a logical division of data. A shard usually means a partition placed on a separate database node or group. The terms are used differently across products.

How copies are kept. Leader-follower replication accepts writes only at the leader, which copies them to followers.

• Asynchronous replication can acknowledge a write before any follower has it.
• Synchronous replication waits for a defined set of acknowledgments, which need not be every replica.

Watch one write:

Multi-leader writes bring conflict resolution with them. More writable copies don't remove coordination or correctness problems.

The design Arjun ends up with

Here is the reference design for forty schools, in one picture. Every part in it was added in one of the chapters above.

Reading the figure: follow the numbers. Each number is one hop of a student reserving a book.

There are two parts off the numbered path:

• Follower replicas ("copies, may lag") serve extra reads. Chapter 7 shows why "may lag" matters.
• Shards ("only when one leader is too small") are drawn as a later step. They are not needed at forty schools, but this is where they would go. The figure is honest about what's built and what's planned.

The legend: solid arrows are requests, and dotted arrows are replication.

7. "I reserved it, but my page says I didn't": consistency

Riya reserves a book and gets "Confirmed." She opens My reservations, and it's not there. She panics and reserves another copy.

sequenceDiagram
    participant S as Student
    participant L as Leader
    participant F as Follower
    S->>L: Reserve the last copy
    L-->>S: Confirmed
    L-)F: Copy the change (asynchronous, may lag)
    S->>F: Show my reservations
    F-->>S: Not there yet (stale read)
    Note over S,F: Read-your-writes fix: read this student's own change from the leader, or wait until the follower has caught up

Reading the diagram. The reservation itself was correct, and the leader confirmed it. The open-headed arrow from Leader to Follower means asynchronous: the copy is still travelling. Riya's next read went to the follower, which hadn't received it yet. Only the copy she read from was behind.

Consistency has several distinct guarantees, so say which one you mean:

• "Strong consistency" is an umbrella phrase. Linearizability is not the same as serializable transactions: one is about real-time behaviour, the other about transaction ordering.
• Eventual consistency doesn't promise any fixed maximum delay, unless the system adds a separate bound. It also doesn't mean corrupt data is acceptable.
• For the library: a slightly stale search page is fine. Riya's own reservations page needs read-your-writes, and the reservation itself must always check authoritative state before confirming.

8. "The link between campuses went down": CAP and PACELC

The district's network link between the north and south campuses fails for an hour. Each side can still reach its own database replica, but not the other side's. Should the south campus keep accepting reservations?

A network partition means groups of machines can't reliably communicate. CAP says that during a partition, a system can't guarantee both linearizable consistency and successful completion of every request at non-failing nodes. An error response doesn't count as success (Gilbert and Lynch's CAP paper).

flowchart TD
    P@{ icon: "algomi:data-cylinder", label: "Replica communication breaks", pos: "b", h: 52 }
    R@{ icon: "algomi:svc-decision", label: "What does this operation require?", pos: "b", h: 52 }
    P --> R
    C@{ icon: "algomi:svc-cube", label: "Allow only the side able to coordinate", pos: "b", h: 52 }
    R -->|No conflicting reservation| C
    A@{ icon: "algomi:svc-cube", label: "Serve available local catalog data", pos: "b", h: 52 }
    R -->|Stale catalog is acceptable| A
    W@{ icon: "algomi:svc-cube", label: "Some requests wait or fail", pos: "b", h: 52 }
    C --> W
    M@{ icon: "algomi:async-gear", label: "Reconcile replicas after recovery", pos: "b", h: 52 }
    A --> M

Reading the diagram. The key box is the diamond, and it asks about the operation, not the database:

• Reserving a copy must never create a conflict (the chapter 1 invariant). So only the side that can still coordinate, the one with the leader, accepts reservations, and the other side's students see "try again shortly." That is choosing consistency.
• Searching the catalogue can tolerate staleness. So both sides keep answering from what they have, and the replicas reconcile when the link returns. That is choosing availability.

One system makes both choices at once, per operation. These are not permanent personality labels for a database product.

PACELC adds a second question. If there is a Partition, choose between Availability and Consistency. Else, choose between Latency and Consistency. Even on a healthy network, waiting for a distant replica to confirm takes time. This is a model for discussing trade-offs, not a claim that every system has exactly two modes (Abadi's PACELC paper).

9. "The catalogue shows yesterday's title": caching done carefully

Meera fixes a typo in a book's title. Students keep seeing the old title for an hour, because the catalogue cache from chapter 4 still holds it.

If a student asks for the opening hours every minute, the librarian shouldn't search the records each time. A small note on the desk is a cache. With cache-aside, the application checks the cache first. On a miss, it reads the database and stores the result for later.

flowchart TD
    Q@{ icon: "algomi:svc-cube", label: "Catalog request", pos: "b", h: 52 }
    C@{ icon: "algomi:svc-decision", label: "Fresh cached result?", pos: "b", h: 52 }
    Q --> C
    R@{ icon: "algomi:svc-cube", label: "Return catalog result", pos: "b", h: 52 }
    C -->|Yes| R
    D@{ icon: "algomi:data-cylinder", label: "Read database", pos: "b", h: 52 }
    C -->|No| D
    S@{ icon: "algomi:data-bolt", label: "Cache result with expiry", pos: "b", h: 52 }
    D --> S
    S --> R

Reading the diagram. There are two paths. Yes is the fast path: the note on the desk is still fresh, so answer from it. No is the slow path: read the database, then write a new note with an expiry, so that it eventually gets thrown away. The stale title came from a note whose expiry was an hour.

The same idea as movement:

1. ask the cache for the catalog entry
2. miss: nothing stored
3. read the entry from the database
4. the database returns the entry
5. store the entry in the cache with an expiry

Fixing the stale title. When a catalogue entry is edited, commit the database change and invalidate the cache entry. Concurrent reads can still repopulate stale data in a narrow race, so stricter needs may require version checks or stronger coordination. The caching deep dive shows that race.

Two more things went wrong on the day a famous fantasy novel was released:

• A cache stampede. The popular entry expired, and hundreds of requests tried to refill it at once. The fix is to coalesce them, so that one refill does the work while the others wait. Also spread expiry times, and serve a briefly stale result where that's allowed.
• A hot key. That one book got enormous traffic. More shards don't help a single key. Local copies, request coalescing or a different representation do.

10. "Adding a server moved everything": tools for large data sets

As the district's data grows, Arjun meets three classic tools.

Consistent hashing

Arjun's first design placed each school's data with hash(school) mod number_of_servers. Adding a fifth server changed the answer for most schools, so almost everything moved at once.

Consistent hashing places keys and servers on an imagined ring. A key belongs to the next server position in the chosen direction. Adding a server moves only the keys in the slice it takes over. Under a balanced model, adding one server to N moves roughly 1/(N+1) of the keys, though the actual movement depends on layout and weights.

• Virtual nodes give each physical server several positions on the ring, which improves distribution. They can't make one hot key less hot.
• Placement isn't replication. The system must add a replica policy on top.

Bloom filters

Every night, a job checks millions of student IDs against the reservations store, and most of them have no reservations at all. A Bloom filter is a compact "might be present" checker.

flowchart TD
    Q@{ icon: "algomi:sec-key", label: "Is this key in the store?", pos: "b", h: 52 }
    B@{ icon: "algomi:svc-decision", label: "Bloom filter", pos: "b", h: 52 }
    Q --> B
    N@{ icon: "algomi:svc-cube", label: "Skip the storage read", pos: "b", h: 52 }
    B -->|"Definitely not present"| N
    S@{ icon: "algomi:data-cylinder", label: "Check the real store", pos: "b", h: 52 }
    B -->|"Might be present"| S
    R@{ icon: "algomi:svc-spark", label: "The real store gives the final answer", pos: "b", h: 52 }
    S --> R

Reading the diagram. The filter gives one of two answers, and they aren't equally trustworthy:

• "Definitely not present" is certain, assuming the filter is maintained correctly. So the expensive storage read is skipped. That's where the saving comes from.
• "Might be present" means "go and check." Occasionally the real store says no. That's a false positive, and it costs one extra read, never a wrong answer.

That's why a Bloom filter must never be the final authority on whether a student already reserved a book. The ordinary form also doesn't support safe deletion of arbitrary items.

Merkle trees

The north and south replicas from chapter 8 disagree after the outage. Comparing every record would take hours. A Merkle tree combines small fingerprints (hashes) into larger ones.

flowchart TD
    R@{ icon: "algomi:svc-cube", label: "Root hash", pos: "b", h: 52 }
    L@{ icon: "algomi:svc-cube", label: "Hash of left group", pos: "b", h: 52 }
    R --> L
    H@{ icon: "algomi:svc-cube", label: "Hash of right group", pos: "b", h: 52 }
    R --> H
    A@{ icon: "algomi:svc-cube", label: "Hash of catalog block 1", pos: "b", h: 52 }
    L --> A
    B@{ icon: "algomi:svc-cube", label: "Hash of catalog block 2", pos: "b", h: 52 }
    L --> B
    C@{ icon: "algomi:svc-cube", label: "Hash of catalog block 3", pos: "b", h: 52 }
    H --> C
    D@{ icon: "algomi:svc-cube", label: "Hash of catalog block 4", pos: "b", h: 52 }
    H --> D

Reading the diagram. The arrows mean "is built from," not network calls.

1. Compare the roots. If the two replicas' root hashes match, everything matches, and they're done.
2. Narrow down. If the roots differ, compare the two children. If only the right-group hashes differ, the left half is skipped entirely.
3. Keep going. Repeat down the tree until the differing block (say, block 3) is found. Only that block needs repair.

Comparing roots is cheap once the tree is built, but building and updating the tree takes work. Several differences need several branch checks. The tree detects differences, but it doesn't decide which value is correct. Dynamo used this approach for replica repair (Dynamo paper).

Gossip is a related technique: machines exchange information with a few peers, who pass it on, so knowledge spreads without one broadcaster. By itself, it is not an agreement protocol for choosing one authoritative value.

Where the library picture stops being accurate

• A real librarian can see that two students are reaching for the same book. Software only sees two requests a millisecond apart, which is why the invariant must be enforced by the database, not by hoping.
• Paper ledgers don't lag behind each other. Replicas do, and that is the whole reason chapters 7 and 8 exist.

Trade-offs and edge cases

Top 3 interview questions (the follow-ups that separate answers)

1. "Two students press Reserve on the last copy within the same millisecond. Walk me through exactly what your design does." Both requests reach application instances, which both send a conditional update to the database: mark copy 42 as reserved for this student only if it is still available. The database executes them one after the other on that row; the first changes one row and commits, and the second changes zero rows. The second student is told the copy has just gone and is offered the waitlist. No cache, replica or application memory takes part in the decision. That is the invariant the whole design protects.

2. "Meera's app is slow at 8:55 every morning. Would you shard the database?" Not first. Measure where the time goes. Usually the cheaper fixes come first: an index for the slow query, caching the catalogue pages everyone opens, read replicas for browsing, connection pooling, and moving reports off the primary. Shard only when writes on the primary are the bottleneck after those, and then choose a key, such as school id, that keeps each reservation inside one shard. State what sharding costs: cross-shard reports and rebalancing.

3. "Explain CAP using the library, then tell me what you would choose." If the network splits between two library branches' servers, each branch must either keep accepting reservations (available, but both might give away the same copy) or refuse reservations until the link returns (consistent, but unavailable). Most of the time there is no partition, and the real trade is latency against consistency. For the library: browsing stays available everywhere; reserving a copy is decided in one place and pauses rather than double-booking. Choose per operation.

11. Interview practice

Each answer is tagged with the chapter where Arjun hit the problem.

Q01. What is system design? (Chapter 1)

Planning components, data and interactions to satisfy user needs and operational constraints. I begin with requirements and invariants, then justify each component against them.

Q02. How is throughput different from latency? (Chapter 2)

Throughput counts completed work per unit of time. Latency measures the time for one operation. More concurrency can raise throughput while also increasing queueing delay.

Q03. Would you immediately shard a slow database? (Chapters 3 and 6)

No. I would inspect queries, indexes, locks, connection pools and resource use first. Sharding helps when distribution addresses a measured limit, and it adds routing and cross-shard complexity.

Q04. What is the difference between replication and sharding? (Chapter 6)

Replication keeps copies of the data, and sharding divides it. Systems often replicate each shard for resilience.

Q05. Can a cache be the authority for reserving the last copy? (Chapters 5 and 9)

Only if it provides durable, coordinated state semantics, which a typical disposable cache does not. I would enforce the reservation rule in the authoritative store, with a conditional update or a constraint.

Q06. Explain CAP using the library. (Chapter 8)

Disconnected campuses can't both independently confirm the same last copy while guaranteeing one reservation. A coordinating design must make some requests wait or fail. A stale catalogue read can follow a different policy.

Q07. Does eventual consistency mean the latest value appears within one second? (Chapter 7)

No. It promises convergence under the required conditions, not a time bound. A one-second requirement needs an explicit freshness objective, and a design that handles violations.

Q08. Why choose a relational database here? (Chapter 5)

The reservation data has relationships and a clear transactional invariant. A relational store lets us express constraints and atomic changes. I would still validate performance with the expected workload.

Q09. What does consistent hashing improve? (Chapter 10)

It reduces how many keys are reassigned when servers are added or removed. It doesn't automatically solve hot keys, replication or failure recovery.

Q10. Why use a Bloom filter if it can be wrong? (Chapter 10)

Its compact negative checks save expensive lookups. Positive results still go to the real store, so a false positive costs an extra read, never a wrong final answer.

Quick revision: the problems, in order

1. What are we building? Start with user actions and invariants. One copy, one active reservation.
2. Fast enough? Latency isn't throughput. Watch the tail, not the average.
3. How big? Estimate, and let small numbers justify a simple start.
4. Exam week? Scale out with stateless app copies behind a load balancer, and cache repeated reads.
5. The last copy? Make check-and-reserve one atomic step, with a conditional update, a lock or a constraint.
6. Forty schools? Replicate for copies and shard for size. They solve different problems.
7. "Not on my page"? Name the guarantee you need. Read-your-writes fixes Riya's page.
8. The broken link? CAP choices are per operation: reservations favour consistency, search favours availability.
9. Stale title? Invalidate on write, coalesce refills, and handle hot keys separately.
10. Moving everything? Use consistent hashing for placement, Bloom filters to skip reads and Merkle trees for repair.

Conclusion

Meera wanted one thing: a book on the shelf when a student comes for it, and never promised to two students at once. Every idea in this guide, requirements as numbers, one source of truth, indexes, replicas, caches, sharding and consistency, is a way of keeping that promise as the library grows from one school to forty. Start with the simplest design that keeps the invariant, measure, and add each new part only when a real number says you need it.

Change history