Foundations: The Long Memory — Data & Storage
High Level Design·beginner·~30 min read
- basics
- database
- sharding
- indexing
- storage-engines
- Database Selection - Storage Engine Internals (How Databases Actually Work) - OLTP vs OLAP (When Your Analytics Kill Your App) - Sharding (Data Partitioning) - Consistent Hashing - Connection Pool Sizing - Partitioning Decision Factors…
What you'll learn
Database Selection
Relational vs NoSQL Decision Matrix
| Criterion | Choose Relational (Postgres) | Choose NoSQL (DynamoDB/Cassandra) | |-----------|------------------------------|----------------------------------| | Data relationships | Complex joins needed | No relationships | | Consisten…
ACID Guarantees and Their Resource Costs
ACID isn't "free" — each guarantee consumes specific resources: | Property | What It Means | Resource Cost | |----------|---------------|---------------| | Atomicity | All-or-nothing transactions | Memory — must maintain undo log to roll…
BASE Model (NoSQL Philosophy)
Where SQL databases offer ACID, NoSQL systems typically follow BASE: | Principle | Meaning | |-----------|---------| | Basically Available | System guarantees availability (per CAP: responds to every request) | | Soft State | State may c…
NoSQL Database Subtypes
| Type | Data Model | Examples | Best For | |------|-----------|----------|----------| | Key-Value | Simple hash map: key → blob | Redis, DynamoDB, Riak | Session data, caching, simple lookups | | Document | JSON/BSON documents, nested f…
MongoDB vs DynamoDB — Detailed Comparison
| Aspect | MongoDB | DynamoDB | |--------|---------|----------| | Deployment | Deploy anywhere: on-prem, hybrid, multi-cloud (Atlas on AWS/Azure/GCP) | AWS only — fully managed, serverless | | Query Language | Rich: complex queries, join…
DynamoDB Indexes: LSI vs GSI
| Feature | LSI (Local Secondary Index) | GSI (Global Secondary Index) | |---------|----------------------------|------------------------------| | Partition Key | Same as base table | Independent (can be any attribute) | | Sort Key | Dif…
Choosing NoSQL for Specific Use Cases
Choose NoSQL when: - Non-relational data (no complex joins needed) - Dynamic or flexible schema - Storing many TB or PB of data - Very data-intensive workload (high IOPS) - Need easy horizontal scaling Still use SQL (Postgres/MySQL) for:…
CockroachDB vs Cassandra — When Distributed SQL Beats NoSQL
Both scale horizontally, but they solve fundamentally different problems: | Aspect | CockroachDB | Cassandra | |--------|-------------|-----------| | Model | Distributed SQL (relational) | Distributed NoSQL (wide-column) | | Consistency…
Database Engine Architecture (Internal Layers)
Understanding how a DB engine processes a query helps reason about performance: Key insight for interviews: "CPU cannot process data on disk directly — it must load data into RAM first, process it, then write back." All DB optimizations…
Why Indexes Matter (Concrete Math)
Problem: Find 1 record in 1 million records. Without index (full table scan): - 1M records × 400 bytes each = 400 MB - Disk block = 4 KB → 10 records per block - Need to read 100,000 blocks - At 1 ms per block read → 100 seconds total Wi…
B-Tree vs B+-Tree
| Feature | B-Tree | B+-Tree | |---------|--------|---------| | Data storage | Internal AND leaf nodes store key+value | Only leaf nodes store data; internal nodes store keys only | | Leaf linking | Leaves are NOT linked | Leaves form a…
Database Indexing
| Index Type | Supports | Best For | |-----------|----------|----------| | B-tree | Exact + range queries | Most common default (ordered traversal) | | Hash | Exact matches only | Faster point lookups (O(1) average) | | Full-text (GIN) |…
Transaction Isolation Levels
Controls the degree to which concurrent transactions can see each other's uncommitted changes: | Isolation Level | Dirty Reads | Non-Repeatable Reads | Phantom Reads | Performance | |----------------|-------------|---------------------|-…
MVCC (Multi-Version Concurrency Control) — How Snapshot Isolation Actually Works
MVCC is the mechanism behind snapshot isolation in PostgreSQL, MySQL/InnoDB, Oracle, and SQL Server: How it works: 1. Each row has createdby and deletedby transaction ID fields 2. An UPDATE = mark old version deleted + insert new version…
Preventing Lost Updates (The Read-Modify-Write Problem)
The lost update occurs when two transactions both read a value, modify it, and write back — the second write clobbers the first: Solutions (from simplest to most complex): | Solution | How It Works | When to Use | |---|---|---| | Atomic…
Write Skew and Phantoms (The Subtle Concurrency Bug)
Write skew is harder to detect than lost updates. It occurs when two transactions read the same data, make decisions based on it, then write to different rows — violating a constraint that depends on both: Real-world write skew examples:…
Implementing Serializability — Three Approaches
| Approach | Mechanism | Performance | Used By | |---|---|---|---| | Actual Serial Execution | Single-threaded transaction processing | Fast (no lock overhead) but limited to one CPU core throughput | VoltDB, Redis, Datomic | | Two-Phase…
How Indexes Transform Performance (Quantitative Example)
Setup: 1 million records, 400 bytes each, 4KB disk blocks (10 records/block). This is why B-Trees (multi-level balanced index) are the default: they reduce 100 second scans to 3ms lookups for million-row tables.
B-Tree vs B+ Tree
| Feature | B-Tree | B+ Tree | |---------|--------|---------| | Data location | Internal + leaf nodes | Leaf nodes only | | Leaf linking | Not linked | Doubly linked list | | Range queries | Slower (must traverse tree) | Fast (follow lea…
Storage Engine Internals (How Databases Actually Work)
Understanding storage engines isn't academic — it directly impacts production decisions: why your writes are slow, when to add an index, when to reach for a column store, and how your database handles crashes.
DBMS Architecture (Layers)
Key insight for practitioners: Storage engines are pluggable. MySQL supports InnoDB (default), MyISAM, RocksDB. MongoDB uses WiredTiger. Choosing the right engine (or tuning it) has more impact than most application-level optimizations.
Two Families of Storage Engines
| | B-Tree (Page-Oriented) | LSM-Tree (Log-Structured) | |---|---|---| | Write mechanism | Overwrite page in place | Append to sequential log | | Read speed | Fast (one tree traversal) | Slower (check memtable + multiple SSTables) | | Wr…
B-Trees In Depth
B-Trees break the database into fixed-size pages (typically 4 KB), matching the underlying disk block size: Key properties: - Branching factor: ~500 per page (depending on key size) → 4-level tree stores 256 TB - Balanced: Always O(log n…
LSM-Trees In Depth
SSTables (Sorted String Tables): - Key-value pairs stored sorted by key (immutable once written) - Merging is efficient: merge-sort of already-sorted files - Sparse in-memory index: don't need every key in memory, just one per block - En…
Comparing B-Trees and LSM-Trees (Practical Decision)
| Factor | B-Tree Wins | LSM-Tree Wins | |--------|-------------|---------------| | Read latency (point) | ✓ (one path through tree) | | | Read latency (range) | ✓ (B+ tree leaf chain) | | | Write throughput | | ✓ (sequential I/O) | | Sp…
Index Types and When They Matter
| Index Type | Data Structure | Supports | Production Use Case | |---|---|---|---| | Primary (clustered) | B+ Tree on PK | All queries on PK | Row lookup by ID | | Secondary | B+ Tree on other column | Queries on non-PK columns | WHERE c…
Memory vs Disk-Based Databases
| Aspect | Disk-Based (PostgreSQL, MySQL) | In-Memory (Redis, VoltDB, MemSQL) | |---|---|---| | Primary store | Disk (SSD/HDD) | RAM | | Performance advantage | Not from avoiding disk reads (OS page cache handles hot data anyway) | From…
OLTP vs OLAP (When Your Analytics Kill Your App)
This matters in real work: running analytics queries on your production database can saturate I/O and starve transaction processing.
The Core Difference
| Property | OLTP (Transactional) | OLAP (Analytical) | |---|---|---| | Read pattern | Small number of rows by key | Aggregate over large number of rows | | Write pattern | Random-access, low-latency from user input | Bulk import (ETL) o…
Data Warehousing
ETL (Extract-Transform-Load): - Extract: Pull data from production OLTP databases - Transform: Clean, denormalize, convert to analysis-friendly schema - Load: Bulk insert into warehouse Why not run analytics on OLTP? Analytic queries sca…
Star Schema (Dimensional Modeling)
- Fact table: Center of the star. Each row = one event (sale, click, transaction). Can have billions of rows - Dimension tables: The who/what/where/when/why. Usually millions of rows max - Star schema: Dimension tables referenced directl…
Column-Oriented Storage (Why Analytics Are Fast in Warehouses)
The problem with row storage for analytics: Row storage must load ALL columns of each row (100+ columns in fact tables) just to read 3 columns. Wasted I/O. Column-oriented solution: Why this is fast for analytics: - Query touches only th…
Kafka Internals (for System Design)
| Concept | How It Works | |---------|-------------| | Topics | Named stream of data; immutable once written; split into partitions | | Partitions | Ordered log; messages get incremental offset; unit of parallelism | | Brokers | Cluster…
Why Kafka is Fast
Kafka achieves millions of messages/second through multiple complementary optimizations: Broker Performance: - Log-structured persistence — append-only writes to disk (sequential I/O, no random seeks) - Record batching — producers accumu…
Kafka vs Message Broker Comparison
| Aspect | Kafka (Log-Based) | Traditional Broker (e.g., RabbitMQ) | |--------|-------------------|--------------------------------------| | Model | Append-only log | Message queue with routing | | Delivery | Pull-based consumers | Push-…
Kafka Delivery Semantics
Delivery semantics define the contract between broker, producer, and consumer about message guarantees: | Semantic | Producer Behavior | Consumer Behavior | Trade-off | |----------|------------------|------------------|-----------| | At…
Consumer Offsets
Kafka tracks where each consumer group has read up to via a special internal topic consumeroffsets: Key rules: - Offsets are committed per-partition per-consumer-group - If consumer crashes before committing → messages reprocessed (at-le…
Idempotent Producer
Solves the duplicate-on-retry problem: producer sends a batch, broker writes it, but the acknowledgment is lost. Producer retries → duplicate in log. How idempotent mode works: 1. Producer gets assigned a Producer ID (PID) from broker 2.…
Kafka Transactions (Exactly-Once Across Partitions)
Transactions allow atomic writes across multiple topics and partitions. A selected message can be consumed, transformed, and written to output topics — all atomically. Abort case: If producer calls abortTransaction(), an ABORT marker is…
Message Ordering with Retries
When max.in.flight.requests.per.connection > 1, out-of-order delivery is possible if a batch fails and is retried while the next batch succeeds: Fix: With idempotent producer enabled, the broker reorders based on sequence numbers even wi…
Broker Discovery (Bootstrap)
Every Kafka broker is a "bootstrap server" — connecting to any single broker gives full cluster metadata: Clients don't need to know all brokers upfront — just one bootstrap address. The metadata response includes which broker is the lea…
ZooKeeper's Role in Kafka
| Function | How | |----------|-----| | Broker registry | Tracks which brokers are alive (ephemeral znodes) | | Leader election | Coordinates partition leader election on broker failure | | Topic config | Stores topic metadata (partition…
Kafka Guarantees Summary
- Messages appended to a partition in the order they are sent - Consumers read in the order stored in a partition - With replication factor N, system tolerates N-1 broker failures - Same key always maps to same partition (as long as part…
Networking Fundamentals for System Design
ElasticSearch Internals
Why it's fast: - Sequential I/O for indexing operations - Clustering across nodes for horizontal scale - Inverted indices — maps tokens to document IDs - Write-once indexing supported (immutable segments) - Simple purging of old indexes…
Graph Databases (When Relationships Are First-Class)
When to use: When your queries are dominated by traversing relationships — social networks, recommendation engines, route planning, fraud detection. Model: Example — Train Booking System: Vertices: Station (code, id, lat/lng, city), Trai…
Optimistic vs Pessimistic Locking — Detailed Comparison
| Aspect | Optimistic Locking | Pessimistic Locking | |--------|-------------------|---------------------| | Strategy | Allow conflicts, detect on write | Prevent conflicts by locking early | | Mechanism | Version column in WHERE clause…
Redis Internals (for System Design)
Data structures beyond simple strings: - Sorted Sets — elements with scores; backed by skip list + hash map; O(log N) insert; perfect for leaderboards and sliding windows - Hashes — field-value maps per key; up to 4B fields; efficient fo…
Consistent Hashing — Bounded Load Extension
Standard consistent hashing can still create hot spots. Bounded-load consistent hashing adds a capacity constraint: - Define balancing factor c (e.g., 1.25 means no server gets >125% of average load) - When a request's target server is a…
Leader Election with ZooKeeper
ZooKeeper provides distributed coordination primitives: - Znodes — tree-structured data nodes (like files that can also be directories) - Persistent — survives session disconnect - Ephemeral — auto-deleted when creator disconnects (failu…
Partitioning Methods
| Method | How It Works | Use Case | |--------|-------------|----------| | Horizontal | Different rows on different servers | Most common — distribute users across shards | | Vertical | Different columns on different servers | Separate h…
Partitioning Criteria (How to Assign Data)
| Criteria | Method | Trade-off | |----------|--------|-----------| | Hash-Based | hash(key) % N | Uniform distribution; adding servers remaps most data | | List-Based | Explicit mapping (e.g., country → shard) | Logical grouping; possib…
Directory-Based Partitioning (Locator Service)
Instead of computing shard location, maintain a lookup table: Advantage: Adding/moving shards requires only updating the directory — no data-aware routing logic in application code. Resharding becomes a directory update + data migration,…
When to Shard (Do the Math First!)
- A well-tuned single database with read replicas handles more than most think - Single Postgres: handles a few TB comfortably — don't shard at 500GB - Shard when: storage exceeds TB range, writes exceed 10K+ TPS, reads overwhelm replica…
Problems Introduced by Sharding
| Problem | Why It Happens | Mitigation | |---------|---------------|------------| | Cross-shard joins | Data needed from multiple shards | Denormalize; application-level joins | | Referential integrity | Foreign keys can't span shards |…
Secondary Indexes with Partitioned Data
Secondary indexes don't map neatly to partitions. Two approaches: Document-Partitioned (Local) Index: - Writes are fast (update one partition's local index) - Reads require scatter/gather to all partitions (expensive, tail latency prone)…
Rebalancing Strategies (How to Add/Remove Nodes)
| Strategy | Mechanism | Used By | Trade-off | |---|---|---|---| | Fixed partitions | Create many more partitions than nodes (e.g., 1000 partitions for 10 nodes). Adding node → steal partitions from others | Riak, Elasticsearch, Couchbas…
Request Routing (How Clients Find the Right Partition)
Three approaches to service discovery for partitioned data: | Approach | Pros | Cons | Used By | |---|---|---|---| | Any node (gossip) | No external dependency | Every node must know full mapping; gossip protocol adds complexity | Cassan…
Consistent Hashing
The Problem
hash(key) % N — adding/removing a server changes N, causing ~90% of data to remap.
The Solution
- Servers and keys placed on a virtual ring (via hashing) - Each key belongs to next server encountered clockwise - Adding server: only keys between new and previous server move (~10% with 10 servers) - Virtual nodes: each physical serve…
Where Used
Distributed caches, databases (Cassandra, DynamoDB), CDNs, some load balancers. ---
Connection Pool Sizing
Connection pools reuse pre-established TCP connections between application servers and databases, avoiding the overhead of 3-way handshake per request (3 network hops to create, 2 to close).
How Connection Pools Work
Sizing Strategy
There is no formula for the "right" pool size. Use percentile monitoring: 1. Deploy with initial guess — start with cores x 2 or a conservative default 2. Monitor in production — track connections in use via Prometheus or application-lev…
Connection Pools in Single-Threaded Runtimes
Python and Node.js are single-threaded but still benefit from connection pools through event loops. While one query awaits a response (I/O wait), the event loop can issue the next query on a different pooled connection. The pool manages…
Partitioning Decision Factors
Before deciding to partition (shard) a database, identify which resource is the actual bottleneck: | Factor | Symptom | Indicates | |--------|---------|-----------| | QPS (Queries/sec) | Connection exhaustion, timeout errors | Too many c…
Soft Delete Pattern
When a user deletes data, instead of physically removing the record (DELETE FROM), update a flag column:
Why Use Soft Delete
| Reason | Explanation | |--------|-------------| | Recoverability | Users can request data restoration via support | | Analytics / Archival | Deleted data may be needed for ML training, analytics, or legal purposes | | Audit Trail | Con…
Implementation Notes
- The isdeleted column should have a NOT NULL constraint with DEFAULT FALSE - Without NOT NULL, queries filtering isdeleted = FALSE will miss rows where isdeleted IS NULL (this is a subtle bug in many systems) - Some databases (e.g., Pos…
GDPR Considerations
GDPR gives users the right to request complete deletion of their personal data. However, there is a practical workaround: anonymize the user's identity while preserving their content. Dissociate the content from the user by replacing use…
When to Hard Delete
Run periodic batch cleanup jobs that physically remove soft-deleted records older than a retention period. This is preferable to individual hard deletes because: - Batch operations minimize I/O disruption - Reduces rebalancing overhead -…
Datetime Storage Strategies
Three approaches for storing timestamps in databases, each with different trade-offs: | Approach | Storage Size | Human Readable | Range Precision | Best For | |----------|-------------|----------------|-----------------|----------| | Na…
Epoch Integer Advantages
- Lightweight and efficient for indexes (4 bytes vs 20 bytes) - Universal across timezones (epoch is timezone-agnostic by definition) - Arithmetic is trivial: last30days = nowepoch - (30 86400) - Monotonically increasing (good for B-Tre…
Custom Format (YYYYMMDD) Use Case
Store as integer 20220402 — starts with year for automatic monotonic ordering. Useful when: - You only need date-level precision (no time component) - You want human-readable values without parsing - You want integer efficiency with read…
Timezone Handling Best Practices
1. Always store UTC in the database — never store local time 2. Convert to local timezone on the client side — server never needs to know user's timezone for storage 3. Epoch values are inherently UTC — they represent seconds since Jan 1…
Storing Dates Before 1970
For dates before the Unix epoch: use negative epoch values (limited range), or store as native DATETIME if the volume is low enough that storage efficiency doesn't matter. ---