Database Concepts

ACID is the contract a single transaction signs with the database. Atomicity means all writes commit or none do; consistency means the transaction leaves the database in a state that satisfies all declared constraints (foreign keys, checks, triggers); isolation means concurrent transactions don't see each other's partial work (the exact strength depends on the isolation level); durability means once the commit returns success, the data survives a crash. Note that the 'C' in ACID is NOT the 'C' in CAP (Consistency, Availability, Partition-tolerance) — ACID consistency is about constraint preservation inside a transaction, CAP consistency is about all nodes seeing the same value.

BASE describes systems that prioritize availability over strong consistency. 'Basically available' means the system always responds, even with stale or partial data. 'Soft state' means the system's state may change over time without input, as replicas converge. 'Eventually consistent' means that given no new writes, all replicas will eventually return the last written value — but there's no bound on 'eventually', and reads in the meantime may return stale or out-of-order values. It's the explicit opposite of ACID.

CAP states that a distributed system can provide at most two of: Consistency (every read sees the most recent write — specifically linearizability), Availability (every request gets a non-error response), and Partition tolerance (the system keeps working when the network drops messages between nodes). Since partitions are not optional in real networks, the real choice is CP or AP. The common misreading 'pick any two' is wrong — P is forced on you.

PACELC, proposed by Daniel Abadi, fixes CAP's biggest blind spot: CAP only describes behavior during a partition, but partitions are rare. The interesting daily tradeoff is between latency and consistency in normal operation. PACELC classifies a system with two letters: PA/EL (Dynamo, Cassandra — available under partition, low latency normally) or PC/EC (Spanner, HBase — consistent under partition, consistent normally) or hybrids like PA/EC.

Relational databases store data as rows in tables with a fixed schema, related through foreign keys. You query with SQL (Structured Query Language) — a declarative language where the query planner decides how to execute joins, filters, and aggregations using statistics and indexes. Relational engines (Postgres, MySQL, SQL Server, Oracle) provide full ACID (Atomicity, Consistency, Isolation, Durability) transactions, mature query optimizers, and decades of operational tooling. The data model is normalized by default to eliminate redundancy.

Key-value stores expose the simplest possible interface: a single key maps to an opaque value (bytes, JSON (JavaScript Object Notation), or a structured record depending on the system). There are no joins, no secondary indexes by default, and queries are restricted to key lookups and (sometimes) prefix scans. The simplicity is the point — it lets the system shard trivially by hashing the key, and reads/writes are O(1) on a single node. Examples range from Redis (in-memory) to DynamoDB (durable, distributed) to etcd (consistent, small).

Document stores keep records as semi-structured documents (JSON (JavaScript Object Notation), BSON, XML), where each document is a self-contained tree. Unlike pure KV stores, document stores support querying on arbitrary fields via secondary indexes, and the documents themselves can be deeply nested. There's no enforced schema, though most engines support optional validation. The mental model is 'a collection of JSON objects with indexes'.

Wide-column stores (Cassandra, ScyllaDB, HBase, BigTable) organize data as rows where each row can have a different set of columns, grouped into column families. The data is partitioned by a hash of the partition key and sorted within partitions by clustering columns. The storage engine is typically an LSM (Log-Structured Merge-tree), optimized for high write throughput. The query model is restricted: you can only efficiently query by partition key and range-scan within a partition. Despite the name, it's not really a column store (those are analytical — Parquet, ClickHouse).

Isolation levels define which concurrency anomalies a transaction is protected from. The SQL (Structured Query Language) standard defines four levels (read uncommitted, read committed, repeatable read, serializable) plus snapshot isolation as a common extension. Each level prevents specific anomalies: dirty reads (seeing uncommitted data), non-repeatable reads (same query returns different rows in the same transaction), phantom reads (range query returns new rows on re-execution), and write skew (concurrent transactions each read a consistent snapshot but together violate a constraint). Higher levels cost more in throughput and contention.

Pessimistic locking acquires a lock (SELECT ... FOR UPDATE) before doing work, preventing anyone else from modifying the row until the transaction commits or rolls back. Optimistic concurrency control (OCC) reads without locking, then at commit time checks whether the row changed since the read (via a version column or MVCC (Multi-Version Concurrency Control) snapshot) and aborts if so, requiring the app to retry. MVCC enables OCC because each transaction has its own snapshot — no locking needed for reads.

Two-Phase Commit (2PC) coordinates a transaction across multiple databases or services in two phases: prepare (everyone votes yes/no) and commit (coordinator tells everyone to commit or abort). It provides ACID (Atomicity, Consistency, Isolation, Durability) across the participants but blocks if the coordinator fails between phases. The Saga pattern instead breaks the transaction into a sequence of local transactions, each with a compensating action; if step 3 fails, you run compensations for steps 1 and 2. Sagas trade atomicity for availability and partition tolerance.

Sharding partitions data across multiple nodes so each node owns a subset. The shard key determines placement. Range sharding (ranges of key values) preserves locality for range queries but risks hot shards at the ends. Hash sharding spreads writes evenly but kills range queries. Geographic sharding co-locates data with users for latency. Consistent hashing minimizes rebalancing when nodes are added or removed. The choice of shard key is the most consequential design decision in a sharded system — it's nearly impossible to change later.

Replication keeps copies of data on multiple nodes for availability, read scaling, and disaster recovery. Single-leader (Postgres streaming, MySQL primary-replica) routes all writes to one node which streams a log to followers; simple and consistent but the leader is a bottleneck and SPOF until failover. Multi-leader allows writes to multiple nodes which sync to each other; handles multi-region writes but introduces conflict resolution. Leaderless (Cassandra, Dynamo) lets any node accept writes with quorum-based consistency. Each replica can sync (block on commit until replicas ack) or async (fire and forget, replication lag).

An index is an auxiliary data structure that speeds up lookups at the cost of write overhead and storage. B-trees are the default in every relational engine — they support equality and range queries on sorted keys. Hash indexes are O(1) for equality but useless for ranges. Postgres-specific GIN (Generalized Inverted Index) supports full-text and JSONB array containment; GIST supports geometric and full-text with custom operators; BRIN (Block Range Index) is tiny and great for large naturally-sorted tables. Partial indexes index only rows matching a WHERE clause; covering (INCLUDE) indexes let queries be answered from the index alone without hitting the heap.

Normalization decomposes tables to eliminate redundancy and update anomalies. 1NF requires atomic columns (no comma-separated lists); 2NF eliminates partial dependencies on composite keys; 3NF (Third Normal Form) eliminates transitive dependencies; BCNF is a stricter 3NF. Denormalization is the deliberate reintroduction of redundancy — duplicating a column across tables, pre-computing aggregates, or storing materialized join results — to avoid expensive joins on hot read paths. The choice is workload-driven: OLTP normalizes, OLAP denormalizes (star/snowflake schemas), and most real systems sit in between.

Database connections are expensive: TCP (Transmission Control Protocol) handshake, TLS (Transport Layer Security) negotiation, authentication, and (for Postgres) a forked backend process per connection. A connection pool maintains a fixed-size pool of open connections that app code borrows and returns. The pool can live in-process (HikariCP, pgx) or as a separate proxy (PgBouncer, RDS Proxy). Pooling modes vary: session pooling assigns one connection per client for the session's life (compatible but limits multiplexing); transaction pooling assigns connections per transaction (much higher concurrency but breaks features like prepared statements and SET LOCAL); statement pooling per statement (rare, most restrictive).