CSE Roadmap

Core tier · about 3 hours · 8 parts

Part 7 of 8 · 4 min read

A way to decide, and common answers

A short procedure for the choice and a table of answers for well-known systems.

A way to decide, and common answers

Think of choosing a vehicle. Most days a bicycle is enough. A van is for loads. A lorry is for a different kind of job. The wrong choice shows in the cost of every trip.

A procedure that works in an interview:

  1. Write the access patterns with rates and speed targets.
  2. Look for rules that span records. Money, stock, booking: relational with transactions, or a clear plan for the gap.
  3. Look for the relationships. Many-to-many and flexible filters favour relational. Whole-record reads favour documents. Deep paths favour graph.
  4. Estimate the scale. Compute reads and writes per second and the data size. Check whether one node, a cache and read copies are enough.
  5. Default to relational unless step 2, 3 or 4 points elsewhere.
  6. Say what is given up. Name the cost of your choice and how you will handle it.

Some common answers (each of these returns as a case study in Levels 10 to 12):

System Main access pattern Common choice Reason
URL shortener Get long URL by short code Key-value or relational with an index on the code One lookup by key, huge read rate
Chat messages Newest messages of one conversation Wide-column Huge write rate, read by conversation and time
Payments and orders Several rows saved together, audit Relational Transactions and constraints
User sessions Get by session id Key-value in memory Very fast key lookup
Social feed Posts of followed users, newest first Mixed: relational or wide-column for posts, cache for feeds Read-heavy, precomputed lists
Metrics and logs Append, then read by time range Wide-column or a time series store Sorted by time, huge writes
Friend recommendations Paths between people Graph Multi-step links

A worked example, a URL shortener. The system must handle 100 million new links a month and 100 times as many redirects (made up).

  • Writes: 100,000,000 ÷ (30 × 86,400 s) ≈ 39 per second.
  • Reads: 100 times that, about 3,900 per second.
  • Data: 100 million links a month × 500 bytes = 50 GB a month; over 5 years 3 TB.
  • One lookup by short code, no joins.
  • Result: a relational table with a unique index on the code would serve 3,900 reads per second easily with a cache. A key-value store is also natural, and the 3 TB over 5 years is a reason to plan for partitioning by key. Either is defensible if the reasons are stated.

That last sentence is the point. Interviewers rarely look for one correct database. They look for the reasoning.

For the curious For the curious

The newest hybrid databases promise both: SQL with transactions, spread over many machines. They are sometimes called NewSQL. They remove some trade-offs and bring others, such as higher latency on writes that cross machines. Knowing they exist is useful. Relying on one without understanding the trade-off is not.

Interview angle

Answer in your head first, then open it.

Which database would you use, and why?

Name the main access pattern with a rate, name the rule or relationship that matters, estimate the scale, then choose and state the cost.

Why not NoSQL for everything?

Without joins and transactions, rules must move into code. Most data has some of both.

Why not relational for everything?

A very high write rate, a simple key access pattern or a sorted time series may cost less in a store built for it. Show the arithmetic.

When would you split the data over several stores?

When access patterns differ sharply. Say how the stores are kept in step.

Check yourself:

  • What is the first step of the decision procedure?
  • For a URL shortener, why is either a relational table or a key-value store defensible?

Words you will meet

Word Plain meaning
NoSQL A loose name for non-relational databases
Access pattern One way the application reads or writes data, with its rate
Transaction Several operations treated as one all-or-nothing unit
ACID The four promises of transactions: atomic, consistent, isolated, durable
Constraint A rule the database enforces on the data
Eventual consistency All copies agree after a while, not at once
Vertical scaling A bigger machine
Horizontal scaling More machines
Read copy A copy of the database that serves reads
Partitioning Splitting data over several machines
Schema-on-write, schema-on-read Structure checked on writing, or on reading
Migration A planned change of the stored structure