Databases

1. Fundamentals of Databases

A. Relational (SQL) vs. Non-Relational (NoSQL)

Before evaluating how a database writes bits to a disk or shards data across networks, a system designer must choose the data modeling paradigm. The database world is broadly split into SQL (Relational) and NoSQL (Non-Relational) systems. This choice dictates how your application scales, its query flexibility, and its data integrity guarantees.

Relational Databases (SQL)

SQL databases store data in structured, fixed tables consisting of rows and columns. They rely on strict schemas and enforce relationships between tables using foreign keys.

• The Core Mechanics: Data is highly normalized to eliminate redundancy. If a user has multiple orders, the user data lives in a users table, the order data lives in an orders table, and they are linked via a user_id foreign key. To read this data together, the engine performs a resource-heavy JOIN operation at runtime.
• Scaling Paradigm: Traditionally optimized for Vertical Scaling (Scale-Up)—adding more CPU, RAM, or SSD speed to a single monolithic database server. While horizontal scaling is possible via sharding or read-replicas, it adds massive architectural complexity.
• Primary Advantage: Strict data integrity and predictability. Ideal for complex transactional queries.
• Popular Implementations: PostgreSQL, MySQL, MariaDB, Oracle, Microsoft SQL Server.

Non-Relational Databases (NoSQL)

NoSQL is an umbrella term for databases that move away from the traditional tabular, relational model. They do not enforce strict schemas, rarely support native cross-table joins, and are designed from day one to scale horizontally across clusters of commodity hardware.

Instead of a single tabular format, NoSQL databases are split into four distinct data models, each optimized for highly specialized system design workloads:

A. Key-Value Stores

Data is stored as an arbitrary collection of key-value pairs. The database treats the value as a completely opaque blob; it only knows how to look up the data using the explicit key.

• Performance: True $O(1)$ read and write latency.
• Best For: User session states, caching tiers, shopping carts, and configuration management.
• Examples: Redis, Memcached, Amazon DynamoDB.

B. Document Databases

Data is stored as semi-structured documents, typically in JSON or BSON formats. Unlike key-value stores, the database can parse the document structure, allowing you to index and query fields deep inside the nested payload.

• Performance: High read/write throughput for denormalized data. If an article has 50 comments, the comments are nested directly inside the single article document, eliminating the need for relational joins.
• Best For: Content management systems (CMS), product catalogs, user profiles, and rapidly changing application features.
• Examples: MongoDB, CouchDB.

C. Wide-Column (Column-Family) Stores

Instead of grouping columns together into a fixed row on disk, wide-column stores group data into dynamic column families. Rows are highly flexible—one row can have 3 columns, while the next row in the same table can have 3,000 columns.

• Performance: Engineered for massive write volume and highly efficient data compression across hundreds of distributed nodes.
• Best For: Time-series logging, IoT sensor streams, high-volume telemetry, and web analytics.
• Examples: Apache Cassandra, ScyllaDB, HBase.

D. Graph Databases

Optimized for data structures where the relationships (edges) between data points (nodes) are just as important as the data points themselves.

• Performance: Bypasses the devastating performance degradation that SQL databases experience when executing deeply nested recursive joins (e.g., finding "friends of friends of friends").
• Best For: Social networks, fraud detection networks, knowledge graphs, and recommendation algorithms.
• Examples: Neo4j, Amazon Neptune.

Paradigm Summary Reference

When designing a system, use this matrix to guide your high-level architectural decision:

B. Transaction Guarantees: ACID vs. BASE

When data is read, written, or updated, databases group these operations into transactions. A transaction is a single, logical unit of work (like transferring money from Account A to Account B).

How a database handles these transactions during server crashes, simultaneous user requests, or network failures is defined by two competing design philosophies: ACID and BASE.

The ACID Properties (Strict & Predictable)

ACID is the gold standard for relational databases (SQL). It prioritizes absolute data correctness and strict consistency above all else, making it essential for financial systems, inventory management, and billing.

• Atomicity ("All or Nothing"): A transaction often contains multiple steps. Atomicity guarantees that either all steps succeed, or none of them do. If a database crashes halfway through transferring $100 from Alice to Bob, the transaction aborts and Alice's account is rolled back to its original state.
• Consistency ("Data Validity"): The database must move from one valid state to another. All constraints, triggers, and cascades must be fully satisfied. You cannot write a string into a database column that enforces an integer constraint.
• Isolation ("No Interference"): When multiple users read and write to the database simultaneously, their transactions act as if they are the only transaction occurring. If Alice and Bob both try to buy the last seat on a flight at the exact same millisecond, Isolation ensures only one succeeds and the other gets an error, preventing a double-booking.
• Durability ("Permanent"): Once a transaction is successfully committed and acknowledged, it is written to non-volatile memory (like the Write-Ahead Log). Even if someone unplugs the database server a millisecond later, the data will still be there when it reboots.

The BASE Properties (Flexible & Available)

As distributed NoSQL databases emerged to handle massive, global internet scale, engineers realized that adhering to strict ACID properties created terrible bottlenecks. To scale horizontally across thousands of servers, they adopted BASE, which trades immediate consistency for high availability.

• Basically Available: The system guarantees a response for every request (read or write), even if there is a partial system failure. It achieves this by reading and writing to replicated nodes across the network, rather than waiting for a single locked "master" node.
• Soft state: Because the system doesn't enforce immediate consistency across all global nodes at once, the state of the data might change over time, even without direct user input, as nodes sync with one another in the background.
• Eventual consistency: The system stops promising that a read will instantly return the most recent write. Instead, it promises that if you stop writing to the system, eventually all nodes will synchronize and hold the exact same data.

The Real-World Trade-off

Imagine you post a photo on Instagram.

• If Instagram used ACID, your app would freeze and load until the photo was successfully copied to every single database server worldwide. (Terrible user experience).
• Because Instagram uses BASE, the photo uploads to your local server instantly (High Availability). If your friend in Japan refreshes their feed 1 second later, they might not see your photo yet (Soft State). However, after a few seconds, the databases sync globally and your friend sees the post (Eventual Consistency).

Transaction Paradigm Reference

C. Concurrency Control & Isolation Levels

When thousands of users interact with a database simultaneously, they will inevitably try to read, modify, or delete the exact same data records at the exact same millisecond.

Without proper Concurrency Control, simultaneous operations can cause catastrophic data corruption. To manage this chaos, databases rely on locking strategies and strict Isolation Levels to draw the boundary between absolute data correctness and high-performance throughput.

The Three Concurrency Phenomenons (The Monsters)

To understand why isolation levels exist, you must first understand the three classic data anomalies that occur when databases lack proper isolation:

1. Dirty Read ($G_1$): Transaction A modifies a row's value. Before Transaction A commits (saves), Transaction B reads that modified value. If Transaction A subsequently aborts and rolls back, the data Transaction B read is now a ghost that technically never existed.
2. Non-Repeatable Read (${G_{2a}}$): Transaction A reads a row. Transaction B then modifies or deletes that same row and commits. Transaction A reads the exact same row again, but the data has changed or vanished. The data was not repeatable within the same transaction.
3. Phantom Read (${A_3}$): Transaction A executes a query reading a range of rows matching a condition (e.g., WHERE salary > 50000). Transaction B inserts a brand new row that happens to match that exact condition and commits. When Transaction A runs the exact same range query again, new "phantom" rows mysteriously appear.

The 4 ANSI SQL Isolation Levels

To combat these anomalies, the SQL standard defines four isolation levels. Each level acts as a dial: turning it up increases data consistency (by making transactions wait in line), but slows down performance.

• Read Uncommitted: The wild west. Transactions can read uncommitted "dirty" changes from other transactions. Almost never used in production.
• Read Committed (PostgreSQL/SQL Server Default): A transaction can only read data that has been officially saved to disk. It completely eliminates dirty reads by keeping track of the old and new states of a row.
• Repeatable Read (MySQL InnoDB Default): Guarantees that if a transaction reads a row once, it will see the exact same values if it reads it again, even if another transaction updates and commits that row in the background.
• Serializable: The ultimate isolation level. It forces transactions to execute as if they were running completely in a single-file, sequential line ($O(1)$ sequence). It eliminates all anomalies but destroys application concurrency at scale.

Implementation Mechanics: How Databases Do It

Databases implement these isolation levels using two primary engineering patterns:

1. Two-Phase Locking (2PL)

A pessimistic approach where transactions must acquire physical locks on rows or entire tables before reading or writing.

• Shared Lock (S-Lock): Multiple transactions can hold a shared lock to read a row simultaneously.
• Exclusive Lock (X-Lock): A transaction must acquire an exclusive lock to write or modify a row. While held, no other transaction can read or write to that row.
• The Problem: Readers block writers, and writers block readers. This leads to massive latency degradation and "Deadlocks" under heavy scale.

2. Multi-Version Concurrency Control (MVCC)

An optimistic, modern approach used by PostgreSQL, MySQL (InnoDB), and Oracle. Instead of locking a row and blocking readers, MVCC treats data as immutable versions.

• How it works: When a transaction updates a row, the database does not overwrite the old data. Instead, it leaves the old row intact and appends a brand new version of that row to the disk with a transaction timestamp ($T_{id}$).
• The Magic: When a reader transaction comes along, the database checks the reader's start timestamp and serves them the newest version of the row that was committed before the reader started.
• The Result: Readers never block writers, and writers never block readers. Old, dead row versions are quietly swept away by a background process (like PostgreSQL's VACUUM thread) once no active transactions need them anymore.

D. Database Indexing Strategies

An index is a separate, highly optimized data structure that the database maintains alongside your actual table data.

Think of a database index exactly like the index at the back of a textbook: instead of flipping through all 800 pages of the book to find where "Load Balancers" are mentioned (a full table scan), you look at the index alphabetically, find the page number, and jump directly to that page ($O(1)$ lookup).

While indexes drastically speed up read queries, they introduce a massive trade-off: every index slows down write operations (INSERT, UPDATE, DELETE) because the database must update both the raw table pages and the index trees simultaneously.

1. Primary Indexes (Clustered Index)

The primary index is automatically created based on the table's Primary Key. In most modern storage engines (like MySQL's InnoDB), the primary index is a Clustered Index.

• The Mechanics: In a clustered index, the leaf nodes of the B-Tree index structure are the actual data rows. The physical data on the disk is sorted and arranged in the exact alphabetical or numerical order of the primary key.
• The Constraint: Because physical files can only be sorted in one way at a time, a database table can have exactly one clustered index.
• Best For: Direct primary key lookups (WHERE id = 502) and sequential primary key range scans (WHERE id BETWEEN 100 AND 200).

2. Secondary Indexes (Non-Clustered Index)

If you have a users table sharded or indexed by user_id (Primary Key), but your application frequently queries users by their email address (WHERE email = 'alice@example.com'), the database would be forced to look at every single page on the disk to find that user. To prevent this, you create a Secondary Index on the email column.

• The Mechanics: A secondary index is an entirely separate B-Tree file. Unlike the clustered index, its leaf nodes do not contain the actual table rows. Instead, they contain the indexed value (e.g., the email string) mapped to a pointer or the Primary Key value of that row.
• The "Double Lookup" Penalty: When you query by email, the database searches the secondary index B-Tree to find the email, extracts the matching Primary Key (e.g., user_id = 45), and then traverses the Primary Clustered Index B-Tree to fetch the actual row data. This process is called Index Lookup / Row Pointer Dereferencing.

3. Composite Indexes (Multi-Column)

A composite index is an index built on multiple columns simultaneously (e.g., an index on both last_name and first_name).

CREATE INDEX idx_user_name ON users(last_name, first_name);

• The Critical Law: The Left-to-Right Prefix Rule. A composite index is structured like a phonebook: it is sorted strictly by the first column first, and then by the second column within the matches of the first.

• Query Match Examples:

  • WHERE last_name = 'Smith' AND first_name = 'John' ──► Perfect match (Uses full index).
  • WHERE last_name = 'Smith' ──► Match (Uses left-most prefix).
  • WHERE first_name = 'John' ──► FATAL FAILURE (The index is completely useless because the phonebook isn't sorted by first name first. The engine falls back to a slow full-table scan).

E. Advanced Storage Layer Caching

To scale read performance past the constraints of physical disk limits, databases implement complex in-memory caching directly inside the storage layers:

1. Database Buffer Pools

Databases do not read from disk on every single query. Instead, they allocate a massive pool of system RAM (e.g., PostgreSQL's Shared Buffers or MySQL's InnoDB Buffer Pool) to cache frequently accessed 4KB/8KB pages.

• When a query requests a row, the engine checks the Buffer Pool. If there is a Cache Hit, data is served instantly from RAM, completely bypassing disk I/O.

2. Materialized Views

A standard view is just a saved SQL query shortcut. A Materialized View is a saved query whose result is physically calculated and written out as a concrete table on disk or in memory.

• Best For: Heavy, complex analytical queries or dashboard metrics that crunch millions of rows (e.g., calculating total global revenue per region). Instead of re-running the heavy aggregate query every time a user refreshes the page, the application reads the pre-computed results instantly.
• Trade-off: The data becomes stale until the materialized view is explicitly refreshed via a background cron or event trigger (REFRESH MATERIALIZED VIEW).

Indexing Strategy Reference

2. Storage Engines: B-Trees vs. LSM-Trees

Do watch the simulation on B-Tree vs LSM-Tree after reading this section for an intuitive understanding.

Scaling the application layer is simple—you spin up more stateless servers behind a load balancer. However, scaling the data layer is one of the most difficult challenges in distributed systems. Databases must maintain state, ensure consistency, and prevent data loss, even during hardware crashes and network partitions.

At its core, a database is just software that writes data to a storage disk and reads it back later. How the database organizes that data on the physical disk is called the Storage Engine.

To understand storage engines, you must understand one fundamental law of computer hardware: Sequential I/O is vastly faster than Random I/O. Writing data sequentially (appending to the end of a file) is orders of magnitude faster than jumping around the disk to update random bytes, even on modern NVMe SSDs.

The two dominant storage engine architectures—B-Trees and LSM-Trees—represent the ultimate trade-off between optimizing for fast reads (Random I/O) versus optimizing for fast writes (Sequential I/O).

A. B-Trees (Read-Optimized)

B-Trees (technically B+ Trees in most databases) are the standard, battle-tested storage engine used by traditional relational databases since the 1970s.

How it Works

A B-Tree organizes data into fixed-size blocks or pages (typically 4KB or 8KB). These pages are structured as a highly branched, balanced tree.

• Internal Nodes: Contain keys and pointers to child pages. They act as a roadmap.
• Leaf Nodes: Contain the actual row data (or pointers to the data). In a B+ Tree, leaf nodes are linked sequentially so you can easily scan a range of values.

When you query a B-Tree, the engine starts at the root and follows pointers down to the leaf node. Because the tree is balanced and highly branched (high "fanout"), finding a specific row out of billions takes a very predictable 3 or 4 disk jumps: $O(log N)$.

The Write Path (In-Place Updates)

B-Trees modify data in-place. If you update a user's name, the engine must:

1. Traverse the tree to find the specific 4KB page containing that user.
2. Load that page into memory.
3. Modify the data.
4. Write the entire 4KB page back to the exact same spot on the disk.

Why write the entire 4KB page for a 1-byte update? Physical storage hardware (SSDs/HDDs) are block storage devices. They are physically incapable of reading or writing single bytes. Even if you change a single letter in a user's name, the database must read the entire 4KB block into RAM, change the byte in memory, and write all 4,096 bytes back to the disk. This hardware constraint is known as Write Amplification.

Why Page Split is Expensive?

If you insert a new row and the target 4KB page is already full, the database must perform a Page Split. It splits the page into two half-full pages and updates the parent pointers. This is an expensive, slow operation that scatters data randomly across the disk.

The Page Split Example

If you insert a new row and the target 4KB page (let's call it Node A) is already full, the database must perform a Page Split:

• It creates a brand new 4KB page (Node B).
• It keeps half the data in Node A and moves the other half into Node B (resulting in two half-full pages).
• It goes up one level to the parent node and updates it to point to both Node A and Node B.

The ripple effect: If the parent node was also full and didn't have room to add the new pointer for Node B, the parent node must also split! This can cascade all the way up to the root of the tree. This is an expensive, slow operation that scatters data randomly across the disk.

Summary

• Pros: Blazing fast, highly predictable reads. Excellent for exact-match lookups and range scans. Supports strong ACID transactions easily because a record exists in exactly one place.
• Cons: Slower writes. Every write requires random disk I/O to locate the page and write it back. High Write Amplification (changing 10 bytes forces the DB to rewrite a full 4KB page).
• Used By: PostgreSQL, MySQL (InnoDB), Oracle, SQL Server.

B. Log-Structured Merge-Trees (LSM-Trees)

As the internet exploded, companies like Google and Facebook needed databases that could ingest massive firehoses of data (logs, clicks, sensor metrics) without locking up. The LSM-Tree was adopted to solve the slow write problem of B-Trees by turning all writes into sequential appends.

The Anatomy of an LSM-Tree

An LSM-Tree never updates data in-place. Once a file is written to disk, it is immutable (it can never be changed). The engine relies on three main components:

1. Write-Ahead Log (WAL): A strictly append-only file on disk used solely for crash recovery.
2. MemTable: An in-memory, sorted data structure (like a Red-Black tree).
3. SSTables (Sorted String Tables): Immutable, sorted files saved on the physical disk.

The Write Path (Write-Optimized)

When a write request arrives, the database simply writes it to the WAL (for safety) and inserts it into the MemTable in RAM. Because it is just writing to memory and appending to a log, the write is instantaneously fast. Writes are so fast in fact, they can often be served immediately from memory, which is why LSM-Tree databases often boast "infinite write throughput".

When the MemTable gets full (e.g., reaches 32MB), it is sequentially flushed to disk as a brand new SSTable.

How do you delete or update data if files are immutable? If you want to delete a record, you don't go find it on disk. You simply insert a new "Delete" marker (called a Tombstone) into the MemTable. When reading, if the system sees the Tombstone, it knows the data is dead.

The Read Path

Reading is where LSM-Trees struggle. To find a key, the database must check multiple places from newest to oldest:

1. Check the MemTable.
2. If not found, check the newest SSTable on disk.
3. If not found, check the next SSTable, and so on...

To prevent reads from becoming painfully slow, LSM-Trees use Bloom Filters—a highly efficient, memory-based data structure that can definitively tell the database if a key does not exist in an SSTable, allowing it to skip unnecessary disk reads.

Compaction (The Cleanup Crew)

Because every update and delete creates a new entry, the disk would eventually fill up with outdated junk, and reads would have to scan thousands of files. To fix this, a background process called Compaction runs constantly.

Compaction reads multiple small SSTables, merges them together, throws away the overwritten data and Tombstones, and writes out a single, clean, new SSTable.

NOTE:

• The larger the SSTables (more keys per file), the less frequent the compaction is needed, which improves read performance. How? If you have lots of small SSTables, a single read query might force the database to check many different files. That means lots of separate, slow disk seek operations. If you have a few large SSTables, the database might only need to check 2 or 3 files. Fewer files = fewer places to look = faster reads. However, if the SSTables get too large, the compaction process becomes too expensive and slow.

• Compaction is the Achilles' Heel of LSM-Trees. It is a CPU and IO intensive process that can slow down the database during heavy write loads.

Summary

• Pros: Incredible write throughput. Zero random disk I/O during ingestion. Highly compressible data.
• Cons: Slower, less predictable reads (you might have to check 5 different files). Read Amplification (reading more data than necessary) and CPU overhead from constant background compaction.
• Used By: Cassandra, ScyllaDB, RocksDB, DynamoDB, LevelDB.

C. Comparison Matrix

When designing a system, choosing the right storage engine dictates the limits of your architecture.

3. Database Replication Models

Replication is the practice of keeping identical copies of your data across multiple physical machines or regions. We replicate data for three primary reasons:

1. High Availability: If a server crashes, the system remains operational by failing over to a replica.
2. Scalability (Read Throughput): Distributing read queries across multiple machines prevents a single database from bottlenecking.
3. Latency Reduction: Placing replicas geographically closer to users reduces network round-trip time.

There are three primary architectural models for replicating data.

A. Leader-Follower (Master-Slave) Replication

This is the most common replication architecture (used by default in PostgreSQL, MySQL, and MongoDB). One node is designated as the Leader, and all other nodes are Followers.

How it works:

• All write operations (INSERT, UPDATE, DELETE) must go to the Leader.
• The Leader writes the data to its local storage and sends a stream of these data changes (the replication log) to all Followers.
• Followers apply these changes to their own local storage in the exact same order as the Leader.
• Clients can query read operations from any node, drastically increasing read capacity.

The Synchronization Trade-off

When configuring a Leader-Follower system, you must choose how strictly the leader waits for followers.

• Synchronous Replication: The Leader waits for the Follower to confirm it has written the data to disk before sending a "Success" response to the client.
  • Pros: Zero data loss. If the leader dies, the follower is guaranteed to have an exact, up-to-date copy.
  • Cons: Slow. A single network hiccup or slow follower will block the entire system from accepting writes.
• Asynchronous Replication: The Leader responds to the client immediately after writing to its own disk, without waiting for the followers.
  • Pros: Maximum write throughput and speed.
  • Cons: Replication Lag. If the leader crashes before the data propagates, any data not yet sent to the followers is permanently lost. Users might write data, immediately refresh the page, and not see their update because they read from a lagging follower (Eventual Consistency).
• Semi-Synchronous (Best Practice): One follower is synchronous, and all others are asynchronous. This guarantees at least two nodes always have the data, balancing safety and speed.

Handling Leader Failure

If the Leader node dies, the system must perform a Failover:

1. Detect the failure (usually via heartbeats/timeouts).
2. Elect a new leader (followers vote, or a consensus system like ZooKeeper promotes the most up-to-date follower).
3. Reroute client traffic to the new leader.

• The Danger (Split-Brain): If a network partition occurs and the original leader isn't actually dead but just unreachable, both the old leader and the new leader might try to accept writes simultaneously. This corrupts the database. Modern systems use "fencing tokens" to forcefully shut down the old leader to prevent this.

B. Multi-Leader (Active-Active) Replication

In a Multi-Leader setup, there is more than one node that can accept write operations. Each leader acts as a leader to the clients, but also acts as a follower to the other leaders.

Use Cases:

• Multi-Datacenter Operation: You place one leader in the US and one in Europe. Users write to their local leader for zero latency, and the leaders sync asynchronously across the ocean.
• Offline Clients: Apps (like calendar apps or Notion) have a local database on your phone (a "leader") that accepts writes offline, then syncs with the cloud leader when internet is restored.

The Ultimate Challenge: Conflict Resolution What happens if User A updates a record in the US datacenter, and User B updates the exact same record in the EU datacenter at the exact same millisecond? When the databases sync, you have a conflict.

Multi-Leader systems must implement conflict resolution strategies:

• Last Write Wins (LWW): Every write gets a timestamp. The write with the highest timestamp overwrites the others. (Prone to data loss if clocks are not perfectly synchronized).
• Version Vectors: The database tracks the lineage and version history of the data, allowing the application code to manually resolve the conflict (used in CouchDB).
• CRDTs (Conflict-Free Replicated Data Types): Advanced data structures that mathematically guarantee automatic, conflict-free merges (used in Redis Enterprise and collaborative apps like Figma).

C. Leaderless (Dynamo-Style) Replication

Popularized by Amazon's Dynamo paper (used in Cassandra, Riak, and DynamoDB), this architecture abandons the concept of a leader entirely. Any client can send a read or write request to any replica in the cluster.

Because there is no leader to dictate the official "truth", the system relies on Quorums (voting) to ensure data consistency.

The Quorum Formula

To guarantee that a read operation always returns the most up-to-date data, the system must satisfy the quorum equation:

$W + R > N$

Where:

• $N$ = Total number of replicas storing the data.
• $W$ = Write Quorum (The number of nodes that must acknowledge a write for it to be considered successful).
• $R$ = Read Quorum (The number of nodes you must read from simultaneously).

Example: If $N = 3$, you can set $W = 2$ and $R = 2$. When writing, the database sends the data to all 3 nodes, but as soon as 2 nodes confirm it, the write is successful. When reading, the database queries 2 nodes in parallel. Because $2 + 2 > 3$, math dictates that at least one of the nodes you read from must have been part of the successful write quorum, guaranteeing you see the freshest data (resolved using version numbers).

Handling Node Failures (Self-Healing)

If nodes go offline or miss updates, Leaderless databases use two mechanisms to catch up:

1. Read Repair: When a client reads from multiple nodes to achieve a quorum, it might notice that Node 3 has stale data. The database automatically pushes the fresh data to Node 3 in the background before returning the result to the client.
2. Anti-Entropy Process: A continuous background process that uses Merkle Trees to scan nodes, compare their data chunks, and silently copy missing data to lagging nodes to ensure total synchronization.

4. Distributed Consistency: CAP vs. PACELC Theorems

When you distribute a database across multiple servers, you are governed by the laws of network physics.

A. The CAP Theorem

The CAP theorem states that in a distributed data store, you can guarantee at most two of the following three characteristics:

• Consistency (C): Every read receives the most recent write or an error.
• Availability (A): Every non-failing node returns a non-error response (without guarantee that it contains the latest write).
• Partition Tolerance (P): The system continues to operate despite arbitrary packet loss or network splits.

[!IMPORTANT] Network partitions are inevitable. Therefore, in system design, you must choose between Consistency (CP) or Availability (AP) during a network partition:

• CP (Choose Consistency): Reject writes or delay reads to guarantee data correctness across nodes. Used in financial systems (e.g., Spanner, etcd).
• AP (Choose Availability): Accept writes on any reachable node. Replicas will sync when the partition heals. Used in social media feeds (e.g., DynamoDB, Cassandra).

B. The PACELC Theorem

The CAP theorem only applies when there is a partition. PACELC expands CAP to describe normal operations:

• If there is a Partition, choose between Availability or Consistency.
• Else (during normal operations), choose between Latency or Consistency.

5. Horizontal Partitioning: Database Sharding

When your database size exceeds the storage of a single machine, or when write traffic saturates the disk controller, you must partition your database horizontally across multiple servers (Shards).

A. Sharding Strategies

1. Range-Based Sharding

Data is partitioned based on ranges of a key value (e.g., Shard A stores users starting with A-G, Shard B stores H-P, etc.).

• Pros: Easy to query ranges of data sequentially.
• Cons: Severe hot-spot issues. If 80% of users have last names starting with S, Shard C will crash under load while Shards A and B sit idle.

2. Hash-Based Sharding

A hash function is applied to the shard key, and the modulo of the number of shards determines the target database.

Shard ID = Hash(Shard Key) % Number of Shards

• Pros: Even data distribution; prevents hot spots.
• Cons: Adding or removing a shard invalidates the modulo calculation, requiring you to migrate up to 90% of your data to new servers (solved by Consistent Hashing).

3. Directory-Based Sharding

A lookup service (or routing registry) stores the mapping between shard keys and physical database servers.

• Pros: Complete flexibility. You can move individual user records between shards without rehashing.
• Cons: The directory database is a single point of failure and adds network latency to every query.

B. Major Challenges of Sharded Databases

Sharding is an architectural one-way street. Once you shard, operations that were simple in a monolithic database become highly complex:

1. Cross-Shard Joins: You cannot perform a JOIN query across tables located on different shards. You must fetch the data from each shard separately and join them in application memory, which is slow and resource-intensive.
2. Distributed Transactions: Maintaining ACID transactions across multiple databases requires protocols like 2-Phase Commit (2PC) or Saga patterns, which introduce significant latency and network overhead.
3. Resharding: When database size grows, you must split an existing shard into two. This requires copying gigabytes of data over the network while the database is live, causing CPU spikes and latency degradation.

C. How to Select a Shard Key

The choice of the shard key determines the success of your architecture. A bad shard key is nearly impossible to change later.

• High Cardinality: Choose a key with millions of unique values (e.g., user_id, tenant_id). Do not shard by status (e.g., active/inactive) or gender, as you will end up with only two unbalanced shards.
• Even Distribution: Avoid keys that create hot spots. For example, using a timestamp as a shard key means 100% of today's writes will hit the newest shard, while yesterday's shards remain idle.
• Matches Query Patterns: Shard by the field most frequently used in your query filters. If 99% of your queries are SELECT * WHERE user_id = ?, then user_id is your ideal shard key. Every query will hit a single database instead of broadcasting to all shards (Scatter-Gather query).