System Design Starts with a Library, Not a Server

Guide 1 of 5 · Foundations and data

Series overview · Next: Networking and APIs

1. What are we designing?

A school library wants an app. Students should search for a book, reserve it, and see whether it is ready.

Before choosing a database, ask what a successful library visit looks 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 includes data, communication, speed, failures, security, and cost.

High-level design, or HLD, chooses the big parts and their relationships. Low-level design, or LLD, explains the objects, interfaces, rules, and algorithms inside those parts. HLD might choose a reservation service. LLD explains how that service prevents an invalid reservation.

2. Separate features from qualities

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

Kind	Library example	Question to ask
Feature	Search books	By title, author, or both?
Feature	Reserve a copy	Can a student reserve the last copy?
Feature	Cancel a reservation	Until which stage?
Speed	Search feels quick	What latency percentile and measurement boundary?
Correctness	One copy has at most one active reservation	Which database rule enforces this?
Availability	Students can search during opening hours	What downtime is acceptable?
Durability	Accepted reservations survive failures	Which failures and how much data loss?
Security	Students see only their own reservations	How is ownership checked?

A useful design makes the qualities measurable. For a teaching exercise, we might 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 remain true. Our central invariant is: one physical copy cannot have two active reservations.

3. Latency, throughput, and capacity

At a library desk, latency is how long one student waits for help. Throughput is how many students the desk helps in a minute.

Adding another librarian may increase throughput. It does not necessarily make one complicated request quicker.

Term	Plain meaning	Example
Latency	Time for one operation	A search takes 120 ms
Throughput	Work completed per unit of time	500 searches each second
Capacity	Sustainable work under agreed conditions	800 requests/s while meeting the latency target
Concurrency	Work in progress at once	100 requests waiting or running
Bottleneck	The part limiting progress	All requests wait for one database lock

The average can hide slow users. If p99 latency is two seconds, roughly 99% of observed requests complete within that time. Tail latency means the slow end of the distribution.

For a stable system, a useful estimate 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. Keep units consistent and use matching boundaries. This estimate is not a substitute for load testing.

4. Make estimates that change the design

Suppose our library network has these invented planning numbers:

Assumption	Value
Daily active students	100,000
Searches per student per day	20
Reservations per day	10,000
Stored bytes per reservation	1,000 bytes
Retention	365 days
Assumed peak multiplier	10

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, using decimal gigabytes. Three full copies would hold about 10.95 GB before indexes, logs, backups, and other overhead.

If a search response averages 20 KB, response traffic at that peak is about 231 × 20 KB = 4.62 MB/s, or roughly 37 Mb/s before protocol overhead.

School opening hours can create a much sharper peak than a daily average suggests. Ask for measurements if available. These numbers suggest beginning with a simple application and indexed database, then measuring performance.

5. Grow the smallest useful design

A first version can have a web app, one application deployment, and a database. Separate concerns in the code even when they run together.

As use grows, the application might evolve like this:

flowchart TD
    U[Students] --> L[Load balancer]
    L --> A[App instance A]
    L --> B[App instance B]
    A --> D[(Reservation database)]
    B --> D
    A --> C[(Catalog cache)]
    B --> C

Both app instances can handle requests. They share durable reservation data. The optional cache stores frequently requested catalog information. The diagram shows roles, not a complete production failover design.

Vertical scaling gives one machine more memory or processing power. It is like moving to a larger library desk. It can be simple, but the machine has a size limit.

Horizontal scaling adds machines. It is like opening more desks. It needs a way to distribute work and coordinate shared data.

Elasticity is the ability to grow and shrink with demand. Autoscaling is an automated mechanism for doing so.

An app is easier to scale when it does not keep essential user state only in one instance's memory. This does not mean the whole system has no state. It means requests can reach another instance and still work.

6. Pick storage by the questions it must answer

A database is not chosen just because the product is popular. Start with access patterns: which data is read together, changed together, and searched together?

Storage style	Everyday picture	Fits well when	Main cost
Relational	Related tables in a carefully managed register	Transactions, relationships, constraints, flexible queries matter	Schema and query tuning require care
Key-value	Numbered lockers	You usually know the exact lookup key	Complex queries need extra design
Document	One folder per item	Nested records are commonly read together	Relationships and duplication need care
Wide-column	Large sorted groups of records	High-volume queries follow planned keys and ranges	Query freedom is limited by the model
Graph	A map of connections	Traversing relationships is central	Not automatically best for simple lookups
Search index	A word index for many books	Text search and relevance ranking matter	Index freshness and rebuilding matter
Object storage	A warehouse of labeled packages	Covers, videos, exports, or backups are large	It is not a general transaction engine

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

For our library, a relational database is a reasonable starting choice for reservations. A search index can be added if text search outgrows the database's capabilities. Cover images can live in object storage, with their object keys stored in the database.

Indexes and duplicate data

An index is like the alphabetical index at the back of a book. It helps locate matching rows without scanning everything. It uses space and adds work on writes.

Normalization stores each fact in a clear home. Denormalization keeps selected extra copies to speed reads. If a read model stores an author's name beside every book, a name change must update those copies or tolerate a delay.

Transactions and isolation

A transaction groups changes into one unit. ACID describes atomicity, consistency, isolation, and durability. Here, consistency means preserving defined database rules, which is a different use of the word from replica consistency.

Isolation controls how concurrent transactions interact. Read Committed can let repeated statements see different committed values. Stronger isolation restricts more anomalies; serializable execution behaves like some serial ordering, but applications may need to retry aborted transactions. Exact behavior varies by database. PostgreSQL isolation documentation

Reading "available = 1" and then updating it in a later operation is unsafe: two requests can read the same value. Use a transaction with appropriate locking, a conditional update, or a database constraint. The worked example is in guide 5.

7. Replication and sharding solve different problems

Replication copies data. Two librarians have copies of the same catalog. This can help availability and read capacity, but copies may lag.

Sharding divides data across machines. One cabinet holds one set of records; another holds a different set. This can spread storage and write work, but queries across cabinets become harder.

flowchart TD
    R[Request router] --> S1[(Shard 1: schools A to M)]
    R --> S2[(Shard 2: schools N to Z)]
    S1 --> P1[(Replica of shard 1)]
    S2 --> P2[(Replica of shard 2)]

This diagram uses alphabet ranges only to explain the idea. Real shard boundaries should be chosen from traffic, data size, and query needs. One huge school could overload one shard.

A partition is a logical division of data. A shard usually refers to a partition distributed to a separate database node or group. Usage varies across products.

Leader-follower replication accepts writes at a leader and copies them to followers. Asynchronous replication can acknowledge a write before a follower receives it. Synchronous replication waits for a defined set of acknowledgments. It need not wait for every replica.

Multi-leader writes introduce conflict resolution. More writable copies do not remove coordination or correctness problems.

8. Consistency: which version does a reader see?

Imagine two library desks. One marks a book as reserved. The other still shows it as available.

Guarantee	Simple explanation	Library use
Linearizability	Operations behave as if they take effect one at a time, respecting real-time order	A completed reservation is reflected by a later authoritative check
Eventual consistency	With no new writes and successful propagation, replicas converge	Search results catch up with catalog edits
Read-your-writes	A user can see their own successful changes	The reservation page shows the student's new reservation
Causal consistency	Effects follow the operations that caused them	A reply is not shown before the message it answers

"Strong consistency" is an umbrella phrase. Say which guarantee you mean. Linearizability is not the same as serializable transactions: one concerns real-time behavior, the other transaction ordering.

Eventual consistency does not promise a fixed maximum delay unless the system offers an additional bound. It also does not mean corrupt data is acceptable. Business rules still matter.

For the library, a stale search page can be acceptable. The actual reservation must check authoritative state before confirming success.

9. CAP and PACELC without the slogans

A network partition means groups of machines cannot reliably communicate. CAP tells us that during such a partition, a system cannot guarantee both linearizable consistency and successful completion of every request at non-failing nodes. An error response is not success for the requested operation. Gilbert and Lynch's CAP paper

flowchart TD
    P[Replica communication breaks] --> R{What does this operation require?}
    R -->|No conflicting reservation| C[Allow only the side able to coordinate]
    R -->|Stale catalog is acceptable| A[Serve available local catalog data]
    C --> W[Some requests wait or fail]
    A --> M[Reconcile replicas after recovery]

These are choices for particular operations. They are not permanent personality labels for every part of a database product.

PACELC adds a useful second question: if there is a partition, consider availability versus consistency; else, consider latency versus consistency. Even on a healthy network, waiting for distant coordination takes time. This is a model for discussing trade-offs, not a claim that every system offers only two fixed modes. Abadi's PACELC paper

10. Caching: keep a useful copy nearby

If a student asks for the opening hours every minute, the librarian should not 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[Catalog request] --> C{Fresh cached result?}
    C -->|Yes| R[Return catalog result]
    C -->|No| D[Read database]
    D --> S[Cache result with expiry]
    S --> R

Pattern or policy	Meaning	Watch for
Cache-aside	App fills missing entries	Stale entries and concurrent refills
Write-through	Write path updates through a cache layer to storage	Added write latency and failure handling
Write-behind	Store in cache, persist later	Loss risk before durable persistence
TTL	Entry expires after a chosen time	Expiry is not a complete consistency strategy
LRU	Evict the least recently used entry	Large scans can displace useful entries
LFU	Evict less frequently used entries	Old popularity may outlive usefulness

For a catalog edit, commit the database change and invalidate the cache entry. Concurrent reads can still repopulate stale data, so stricter needs may require version checks or stronger coordination.

A cache stampede happens when many requests refill the same missing entry together. Coalesce those requests so one refill does the work. Spread expiry times and consider serving a briefly stale result where allowed.

A hot key gets unusually heavy traffic. More shards may not help one extremely popular key. Local copies, request coalescing, or a different representation may help.

11. Three tools for large data sets

Consistent hashing

Using hash(key) mod number_of_servers changes many assignments when the server count changes. Consistent hashing places keys and server positions on an imagined ring. A key belongs to the next server position in the chosen direction.

Adding a server moves only the portion assigned to it. Under a balanced model, adding one server to N servers moves roughly 1/(N+1) of the keys. Actual movement depends on layout and weights.

Virtual nodes give a physical server several positions to improve distribution. They cannot make one hot key less hot by themselves. Hash placement does not automatically provide replication; the system must add a replica policy.

Bloom filters

A Bloom filter is a compact "might be present" checker. A negative result means the item was not inserted, assuming the filter is correctly maintained. A positive result means "check the real store." False positives are possible.

It can avoid unnecessary storage reads. It must not be the final authority for whether a student already reserved a book. The ordinary form does not support arbitrary deletion safely.

Merkle trees

A Merkle tree combines small fingerprints, called hashes, into larger fingerprints. Two replicas compare their root hashes. If they differ, they compare branches to narrow down which data needs repair.

flowchart TD
    R[Root hash] --> L[Hash of left group]
    R --> H[Hash of right group]
    L --> A[Hash of catalog block 1]
    L --> B[Hash of catalog block 2]
    H --> C[Hash of catalog block 3]
    H --> D[Hash of catalog block 4]

The arrows show composition, not network calls. Root comparison is cheap after construction; building or updating the tree takes work. Multiple differences need multiple branch checks. The tree detects differences; it does not decide which value is correct. Dynamo's paper describes this use for replica repair. Dynamo paper

Gossip is another distribution technique: machines exchange information with selected peers, which pass it onward. It spreads knowledge without one broadcaster. It is not, by itself, an agreement protocol that selects one authoritative value.

12. Interview practice: questions 1–10

Q01. What is system design?

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

Q02. How is throughput different from latency?

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

Q03. Would you immediately shard a slow database?

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

Q04. What is the difference between replication and sharding?

Replication keeps copies of data. Sharding divides the data. A system often replicates each shard for resilience.

Q05. Can a cache be the authority for reserving the last copy?

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

Q06. Explain CAP using the library.

Disconnected desks cannot both independently confirm the same last copy while guaranteeing one reservation. A coordinating design must make some requests wait or fail; a stale catalog read can have a different policy.

Q07. Does eventual consistency mean the latest value appears within one second?

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

Q08. Why choose a relational database here?

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

Q09. What does consistent hashing improve?

It reduces key reassignment when membership changes. It does not automatically solve hot keys, replication, or failure recovery.

Q10. Why use a Bloom filter if it can be wrong?

Its compact negative checks save expensive lookups. Positive results still go to the real store, so a false positive costs extra work rather than an incorrect final answer.

Quick revision

Start with user actions and invariants. Use estimates to choose a reasonable starting size. Index before adding distribution without evidence. Keep cache freshness separate from business correctness. Define consistency per operation. Explain both the benefit and the new failure mode of each component.