Scrolls
7 min read
On this page

Databases & Storage

Choosing the right database is one of the highest-leverage decisions in system design. The wrong choice creates friction for years; the right choice makes scaling feel natural. This file covers the major database families, their trade-offs, and the operational techniques that keep them running at scale.

Relational Databases

Relational databases store data in tables with rows and columns. Relationships are expressed through foreign keys and enforced through constraints. SQL is the query language.

Strengths

  • ACID transactions guarantee correctness for complex operations
  • Joins let you query across tables efficiently
  • Mature tooling, broad community knowledge
  • Schema enforcement catches data quality issues early

When to Use

  • Data has clear structure and relationships (users, orders, inventory)
  • You need multi-row transactions (transfer money between accounts)
  • Complex queries with joins, aggregations, and subqueries
  • Correctness is more important than raw write throughput

Examples

  • PostgreSQL — feature-rich, extensible, strong community
  • MySQL — widely deployed, good replication ecosystem
  • Amazon Aurora — managed, MySQL/PostgreSQL-compatible, auto-scaling storage

NoSQL Databases

NoSQL is a broad category covering any database that does not use the traditional relational model. The main families are:

Key-Value Stores

Data is a simple mapping from key to value. Fastest possible reads and writes when access is by primary key.

  • Use for: session storage, shopping carts, feature flags
  • Examples: Redis, DynamoDB, Memcached

Document Stores

Data is stored as JSON-like documents. Each document can have a different structure. Queries can reach into nested fields.

  • Use for: content management, user profiles, catalogs with varied attributes
  • Examples: MongoDB, Couchbase, Firestore

Column-Family Stores

Data is organized by column families rather than rows. Optimized for write-heavy workloads and time-series data with wide rows.

  • Use for: event logging, IoT telemetry, analytics
  • Examples: Cassandra, HBase, ScyllaDB

Graph Databases

Data is modeled as nodes and edges. Queries traverse relationships, which is far more natural and efficient than multi-table joins for graph-shaped data.

  • Use for: social networks, recommendation engines, fraud detection
  • Examples: Neo4j, Amazon Neptune, JanusGraph

ACID vs BASE

ACID

Atomicity, Consistency, Isolation, Durability. The gold standard for correctness.

  • Atomicity: A transaction either fully commits or fully rolls back.
  • Consistency: Data moves from one valid state to another.
  • Isolation: Concurrent transactions don't interfere with each other.
  • Durability: Committed data survives crashes.

Relational databases provide ACID. Some NoSQL databases offer it per-partition (DynamoDB transactions, MongoDB multi-document transactions).

BASE

Basically Available, Soft state, Eventually consistent. A pragmatic relaxation of ACID.

  • The system is always available for reads and writes.
  • State may be stale for a window of time.
  • Given enough time with no new writes, all replicas converge.

Distributed NoSQL systems often default to BASE because strong consistency across nodes is expensive in terms of latency and availability (see the CAP theorem).

Choosing Between Them

If a stale read causes financial loss or data corruption, you need ACID. If a user seeing a 2-second-old follower count is acceptable, BASE is fine and lets you scale further.

Indexing

An index is a data structure that speeds up reads at the cost of slower writes and additional storage.

B-Tree Indexes

The default index type in most relational databases. Good for equality lookups, range queries, and sorting.

CREATE INDEX idx_users_email ON users(email);

Query: SELECT * FROM users WHERE email = 'alice@example.com';
Without index: full table scan (O(n))
With index: B-tree lookup (O(log n))

Hash Indexes

Exact-match lookups only. O(1) average case. No range queries.

Composite Indexes

Index on multiple columns. Column order matters — the index is useful only for queries that filter on a left prefix of the columns.

CREATE INDEX idx_orders_user_date ON orders(user_id, created_at);

Useful for: WHERE user_id = 42 AND created_at > '2025-01-01'
Useful for: WHERE user_id = 42
NOT useful for: WHERE created_at > '2025-01-01' (skips leading column)

Full-Text Indexes

Inverted indexes that map words to the documents containing them. Essential for search features. PostgreSQL has built-in full-text search; for heavy workloads, use Elasticsearch or Solr.

Over-Indexing

Every index slows down writes (the index must be updated) and uses disk space. Index only the columns that appear in frequent queries. Monitor slow query logs to find missing indexes.

Replication

Replication copies data across multiple database nodes for availability and read scalability.

Single-Leader Replication

One primary node accepts all writes. Replicas asynchronously (or synchronously) receive a copy of every write.

Client writes -> Primary -> Replication log -> Replica 1
                                            -> Replica 2
Client reads  -> Replica 1 or Replica 2
  • Simple model, easy to reason about
  • Writes are limited to one node's capacity
  • Async replication means replicas can lag (replication lag)

Multi-Leader Replication

Multiple nodes accept writes. Used in multi-region setups so each region has a local writer.

  • Lower write latency for geographically distributed users
  • Conflict resolution is hard (last-write-wins, custom merge logic)

Leaderless Replication

Any node accepts reads and writes. Uses quorum-based consistency (read from R nodes, write to W nodes, where R + W > N).

  • High availability — no single point of failure for writes
  • Requires careful quorum configuration
  • Examples: Cassandra, DynamoDB

Sharding

Sharding splits data across multiple database instances (shards) so that no single instance holds everything.

When to Shard

Shard when a single database instance cannot handle the write throughput, storage volume, or query load. Sharding adds significant operational complexity, so exhaust simpler options first (indexing, read replicas, caching, vertical scaling).

Shard Key Selection

The shard key determines which shard holds a given row. A good shard key:

  • Distributes data evenly across shards
  • Aligns with the most common query patterns (queries that filter by shard key hit one shard)
  • Avoids hot spots (a celebrity user_id receiving all traffic)

Sharding Strategies

  • Hash-based: Hash the shard key, mod by number of shards. Even distribution but range queries span all shards.
  • Range-based: Assign key ranges to shards (A-M on shard 1, N-Z on shard 2). Supports range queries but risks uneven distribution.
  • Geographic: Shard by region. US data on US shard, EU data on EU shard. Good for data residency compliance.

Cross-Shard Queries

Queries that span shards are expensive. They require a scatter-gather pattern: query all relevant shards, merge results. Design your shard key to minimize these.

Choosing the Right Database

Decision Framework

Structured data + complex queries + transactions?
  -> Relational (PostgreSQL, MySQL)

Simple key-based access at massive scale?
  -> Key-value (DynamoDB, Redis)

Flexible schema + document-oriented access?
  -> Document store (MongoDB)

Write-heavy + time-series + wide rows?
  -> Column-family (Cassandra)

Highly connected data + traversal queries?
  -> Graph (Neo4j)

Full-text search + ranking?
  -> Search engine (Elasticsearch)

Real-World: Uber

Uber migrated from PostgreSQL to a custom system built on MySQL and Schemaless (a document-like layer on top of MySQL shards). The primary access pattern was key-based lookup of trip data, which didn't need PostgreSQL's advanced features but did need extreme write throughput and horizontal sharding.

Real-World: Discord

Discord stores billions of messages in Cassandra, chosen for its write throughput and ability to handle wide partitions (all messages in a channel). Metadata like guilds and users lives in PostgreSQL, where relational integrity matters more.

Common Pitfalls

  • Premature sharding. Sharding adds operational cost (backups, migrations, cross-shard queries). Try read replicas, caching, and better indexing first.
  • Choosing NoSQL because it's trendy. Most applications are well-served by a relational database. Reach for NoSQL when you have a specific access pattern or scale requirement that demands it.
  • Missing indexes on frequently queried columns. Check slow query logs regularly.
  • Ignoring replication lag. If you write to the primary and immediately read from a replica, you may get stale data. Use read-your-writes consistency where it matters.
  • No backup strategy. Replication is not backup. A bad DELETE statement replicates to all replicas instantly. Maintain point-in-time recovery.
  • Over-normalizing. In high-read systems, denormalization (storing precomputed data) can eliminate expensive joins. Accept some data redundancy for performance.

Key Takeaways

  • Relational databases are the safe default. Move to NoSQL when a specific workload demands it.
  • ACID guarantees correctness; BASE trades consistency for availability and scalability.
  • Indexes are the single biggest lever for read performance. Composite index column order matters.
  • Replication provides read scalability and availability. Understand the consistency trade-offs of async replication.
  • Shard only when you must, and choose a shard key that matches your primary access pattern.
  • Polyglot persistence — using multiple databases for different workloads — is common and practical at scale.