Part of my notebook. Terse by design.
ACID, and scaling the relational database
- Atomicity: each transaction is all or nothing.
- Consistency: every transaction moves the database from one valid state to another.
- Isolation: concurrent execution gives the same result as serial execution.
- Durability: committed means committed.
The scaling toolbox, roughly in the order you should reach for it:
master-slave replication, master-master replication, federation, sharding,
denormalization (redundant copies to avoid expensive joins; materialized
views are the managed version), and plain SQL tuning. Benchmark with tools
like ab, profile with the slow query log. Citus shards Postgres when you
get there.
How indexes actually work
- B-Tree vs B+Tree: B+Trees store all data at linked leaf nodes, optimizing range scans and sequential access; B-Trees keep data in internal nodes too, occasionally faster for point lookups but messier to maintain and less space-efficient. Modern databases and filesystems default to B+Trees. Excellent deep dive: PlanetScale on B-Trees and database indexes.
- B+Tree vs hash index: B+Tree is the flexible default, logarithmic lookup, roughly 4 disk IOs for an 8 TB index, supports
<,>,=,!=and range scans. A hash index is O(1) but equality-only. Comparison. - Bitmap index: one bit per row per value; great for low-cardinality analytical filters. Dgraph’s writeup.
- Radix tree: more space, faster search; adaptive radix trees mitigate the space cost.
- Partial indexes: index only the rows you query. Underused.
- How joins and aggregates work inside: QuestDB on building fast hash tables for SQL joins.
- How Postgres lays data on disk, a genuinely fun read: drew’s dev blog.
LSM vs B-Tree, the short version
My condensed notes; the concepts come from the Bigtable paper and a very good walkthrough, A Closer Look at a Key-Value Storage Engine, which builds the whole thing up from a hashmap plus an append-only log.
The write path of an LSM engine:
- Append to the WAL (durability; append-only, so fast).
- Insert into the memtable, an in-memory sorted structure.
- When the memtable fills, flush it to disk as an immutable SSTable (sorted string table). The WAL segment is then discarded.
- Background compaction merges SSTables level by level, dropping overwritten values and deletion tombstones.
Reads check the memtable, then SSTables newest-first. Bloom filters skip SSTables that definitely don’t contain the key (this is why Cassandra can avoid disk lookups for missing keys); a manifest file tracks each table’s key range so usually only one file per level is a candidate.
Why bother: it’s hard to beat appending to a file as a write operation. Sequential writes beat random writes so thoroughly that buffering in memory and flushing sorted runs wins for write-heavy workloads, at the cost of read amplification and background compaction competing for I/O. The known failure mode: sustained write throughput outruns compaction, unmerged segments pile up, reads degrade, disk fills.
B-Trees update in place: find the page, modify, write back, occasionally split pages (with WAL protection for crash safety). One copy of each key, so transactional locking is simpler; reads are generally faster; writes carry amplification (every index touched on every update).
Rule of thumb: B-Tree for read-heavy and transactional, LSM for write-heavy and append-mostly.
The LSM family tree
| Engine | What it is | Notes |
|---|---|---|
| Cassandra | Distributed column-family store, Dynamo-inspired | Commit log → memtable → SSTables; consistent hashing; gossip; tunable consistency; millions of writes/sec |
| ScyllaDB | Cassandra-compatible, C++ | Thread-per-core, NUMA-aware shard-per-core design, no GC; much better hardware utilization |
| LevelDB | Embedded KV store (Google) | Memtable + WAL + SSTables, single-threaded compaction; phones, IoT, small local stores |
| RocksDB | Meta’s feature-rich LevelDB fork | SSD-optimized, multi-core, column families, tunable compaction; the default embedded engine everywhere |
| CockroachDB | Distributed SQL | Storage engine Pebble (replaced RocksDB), LSM-based, Raft per range |
Spanner is the odd one out: globally distributed, strongly consistent, and not exactly LSM (paper).
Replication
Primary handles writes; replicas sync and serve reads. Three sync modes:
- Asynchronous: primary doesn’t wait; replicas can lag.
- Semi-synchronous: primary waits for at least one replica ack.
- Synchronous: primary waits for all; consistency at the price of latency.
Postgres vs MySQL, the parts that matter:
| Topic | PostgreSQL | MySQL |
|---|---|---|
| Sync mechanism | WAL streaming | Binlog (+ GTID for position) |
| Initial setup | pg_basebackup + standby.signal |
CHANGE MASTER TO + START SLAVE |
| Lag detection | pg_stat_replication: write_lag, replay_lag |
SHOW SLAVE STATUS: Seconds_Behind_Master |
| Multi-primary | Not native (BDR, Citus, logical replication) | Group Replication / Galera |
| Failover tooling | Patroni, Repmgr | Orchestrator, InnoDB Cluster |
| Sharding path | Citus | Vitess |
Problems actually seen in production: replica lag under heavy writes, binlog/WAL disks filling up and breaking replication (replicas then need a full re-bootstrap), GTID inconsistencies in MySQL. Shopify’s shard balancing at terabyte scale shows what mature binlog tooling enables: moving shards without downtime.
Multi-primary (write-write)
Trickier than read replicas, warts and all. Used in multi-region deployments, leaderless HA setups, and systems like Cassandra, CouchDB, Galera, CockroachDB.
Core mechanics you must get right:
- Conflict resolution: last-write-wins timestamps, app-defined handlers, or consensus (Paxos/Raft).
- Transaction identity: GTIDs or UUIDs+sequence so nodes don’t re-apply their own changes.
- Ordering: Galera uses certification-based replication (no conflict → commit); CockroachDB runs distributed transactions over Raft.
- Write-set propagation instead of log shipping.
Real options: MySQL + Galera (synchronous, every write certified on all nodes, latency spikes under contention), MySQL Group Replication (Paxos-like group coordination, built-in conflict detection), CockroachDB (always multi-primary, Raft per data range, true distributed ACID). AWS later released pgactive for Postgres active-active.
Never trust naive write-write replication for high-write, high-conflict workloads. The strategies that actually survive high write volume:
| Strategy | Best for | Example stack |
|---|---|---|
| Sharding | Horizontal write scaling | Vitess, Citus, Cassandra |
| Partitioned writes w/ per-partition leader | Avoiding cross-shard conflict | DynamoDB, Cassandra, ScyllaDB |
| Queued/eventual writes | Burst-heavy, async-safe | Kafka → PostgreSQL |
| Batched ingest | Analytics, time series | ClickHouse, TimescaleDB, BigQuery |
| Append-only, never update | Immutable logs, audit | Event stores |
| Multi-region single-writer | Strong consistency + availability | Spanner, Aurora Global |
| CQRS | High write, eventual read sync | Kafka + read-model DBs |
| LSM engines | Massive inserts | RocksDB, ClickHouse |
Sharding
Split data into shards across servers when one machine can’t hold or serve
it. Neither Postgres nor MySQL shards natively; the ecosystem answers are
Citus (Postgres extension, coordinator node, range/hash sharding,
limited cross-shard joins; used by Microsoft, Heap, Mixpanel) and Vitess
(sits between app and MySQL, vtgate routes queries, auto-rebalancing,
declarative cross-shard schema changes; battle-tested at YouTube, Slack,
GitHub).
When to shard: dataset in the hundreds of GB and write-heavy, writes need to scale horizontally, a natural shard key exists (tenant_id, region), and you can live with weaker cross-shard transaction guarantees.
Before you shard, remember: choose the shard key to avoid hotspots, avoid cross-shard transactions entirely if you can, schema changes get hard, and read scaling is cheaper (just add replicas per shard). Grab’s order storage writeup is a good worked example (DynamoDB GSIs; also: Aurora bills storage + IOPS while RDS GP-SSD gives you 16k IOPS free, which changes the math).
Decision matrix from my notes:
| If you need… | Go with… |
|---|---|
| Simple scaling, high throughput | Vitess / Citus sharding |
| Analytics/event-heavy writes | ClickHouse, TimescaleDB, BigQuery |
| Multi-region strong writes | CockroachDB, Spanner |
| Burst-write ingestion | Kafka → consumers → DB |
| Extreme scale, no updates | Cassandra, ScyllaDB |
SQL vs NoSQL, pragmatically
If Postgres or MySQL is already embedded in the company ecosystem, keep using it; don’t introduce a second database stack for the sake of it. Postgres pushed properly goes a very long way: Zerodha’s working-with-PostgreSQL writeup is the reference I send people. Reach for NoSQL when you’re starting fresh with genuinely huge, known-access-pattern data. When comparing candidates, read their replication internals and write-failover story first; that’s where they differ, not the query language.
Query optimization
Pipeline: SQL → parser → query planner → execution. Learn to read your database’s execution plans; everything else follows.
- Index the columns in JOINs and WHERE clauses.
- Write SARGable predicates (Search ARGument-able):
WHERE YEAR(order_date) >= 2023can’t use an index;WHERE order_date > '2023-01-01'can. Don’t wrap indexed columns in functions; if you must, create a computed column or function-based index. - SELECT only what you need; the select list is processed last anyway.
ORDER BY ... LIMIT nbeats sorting the whole table.- For large aggregations, CTEs can beat join pyramids: one team’s 80% query-time cut.
Case studies worth remembering
Uber’s Postgres → MySQL move (summary source):
Postgres updates write new row versions (ctid), so every update touched
every secondary index (write amplification) and left bloat that needed
REINDEX downtime; WAL-based replication was chatty; a replication bug
corrupted data; replicas paused under long queries. MySQL’s primary-key
clustered indexes and row-based replication fit their write pattern better.
Worth knowing the fine print: later Postgres versions (logical replication,
hot standby, pg_rewind, zero-downtime upgrades) fixed most of this list.
Discord storing trillions of messages: Cassandra degraded as data grew; migrated to ScyllaDB (C++, GC-free), fronted by Rust data services that coalesce concurrent requests for the same resource into one DB call. 72 nodes, trillions of messages, migrated in nine days.
Stack Overflow: a monolith with 1.5 TB of RAM on the SQL Server boxes, keeping a third of the entire database in memory. Not the latest tech, a deep understanding of their specific problem.
Analytics: warehouse → lake → lakehouse
| Era | Stack | Character |
|---|---|---|
| Data warehouse | Oracle, Teradata, SQL Server | Centralized, structured, expensive |
| Hadoop | HDFS + Hive + MapReduce | Cheap storage, batch at scale, painful ops |
| Cloud + columnar | BigQuery, Redshift, Snowflake, ClickHouse | Fast SQL over huge data, serverless; lock-in and cost |
| Lakehouse | S3/HDFS + Iceberg/Delta/Hudi + Spark/Trino + Kafka/Flink + Airflow/dbt | Unified batch+streaming, open formats, ACID, time travel, decoupled compute/storage |
| AI-native | Feature stores, vector DBs, HTAP | Analytics feeding ML in real time |
A data lake stores raw structured/semi/unstructured data at any scale; the lakehouse layers table formats (Delta, Iceberg) over object storage to get ACID and schema evolution. Catalogs (Unity Catalog, AWS Glue, Hive metastore) translate table metadata for whichever engine is asking. Data lineage (origin, transformations, movement) is what lets you trace a bad number to its root cause: modern data lineage 101.
Two specialists worth knowing: Apache Druid, OLAP for near-real-time slice-and-dice (Salesforce uses it for product analytics, Netflix for infra anomalies; weekly reports can stay in BigQuery/Snowflake), and Apache Beam, a unified batch+streaming definition model that runs on external engines like Spark or Flink (LinkedIn: 4T daily events through 3k pipelines).
Small data structures behind big systems
- Bloom filter: probabilistic set membership, “definitely no / probably yes.” ~1.2 GB for a billion usernames at 1% false positives. No deletes, never forgets. Used by LSM stores to skip disk for absent keys, by Akamai to skip caching one-hit wonders (75% of requests!), by Chrome historically for malicious URLs. Space efficiency erodes as many filters share one dictionary; an inverted index stores the dictionary once instead.
- HyperLogLog: cardinality estimation without storing members; the social-media view counter. In Redis:
PFADD,PFCOUNT. - Inverted index: word → documents mapping, the heart of Elasticsearch; strip stopwords, hash keywords to document IDs; distribute with map-reduce (distributed search).
- Skip list: probabilistic sorted structure, Redis’s choice for sorted sets; fast lookups and range queries without tree rebalancing.
- SSTable + memtable: see the LSM section above.
- Suffix tree / trie: substring search.
- R-Tree: spatial indexing over rectangles/polygons; PostGIS, MongoDB, Elasticsearch geo queries.