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…
Beyond the Matrix — Scale, Customization, and Real-World Exceptions
Database Type Taxonomy — clarifying the confusing labels
Before real-world architectures, fix a vocabulary problem interviews trip on constantly. These labels sound similar but refer to fundamentally different engines: | Type | What it means | Examples | Sweet spot | |---|---|---|---| | Key-va…
Real-World Hybrid Architectures — Case Studies
Every production system of any scale is a hybrid — no single engine handles all workloads well. The interview signal isn't "which database do I pick" but "which workloads exist in this product, and what engine fits each one." Below: six…
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
Note that the "queue" above is the pool library's own in-process wait queue — not Kafka, SQS, or anything external. It's an in-memory FIFO inside HikariCP / pgbouncer / pg-pool that parks waiting threads until a connection is returned.
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. ---