Posts

Overview B-Trees and LSM Trees are the two dominant on-disk index structures used by databases, and they diverge on how they handle writes. A B-Tree performs in-place updates on a balanced page structure to keep reads fast, while an LSM Tree buffers writes in memory and reconciles them later through background compaction, trading read simplicity for write throughput. Comparison Diagram B-TreeLSM Treerootnodenodeleafleafleafleafupdate overwrites herein-place updates, balanced traversalmemtable (in-memory)L0 SSTablesL1 SSTablesL2 SSTablescompaction merges levelssequential writes, background merge Comparison Table Aspect B-Tree LSM Tree Write path Traverses the tree to locate the target page and updates it in place, splitting nodes as needed Appends the entry to an in-memory memtable plus a write-ahead log; no seek to the record’s final location Read path Single root-to-leaf traversal, O(log n) page reads from one location Checks the memtable then potentially multiple SSTables across levels, often aided by bloom filters Update/Delete handling Overwrites the existing value directly at its page Writes a new version or a tombstone; the old entry is only removed later during compaction On-disk structure One mutable, balanced tree of fixed-size pages, always sorted Immutable sorted SSTable files organized into levels of increasing size Background maintenance Node splits and merges happen incrementally as part of each write Periodic compaction merges SSTables across levels and drops stale versions Write amplification Low to moderate; occasional page rewrites and splits Higher; the same record can be rewritten multiple times as it moves through levels Read amplification & space reclaim Minimal read amplification; deleted space is reclaimed immediately Higher read amplification from scanning multiple levels; space reclaimed only after compaction Range scans Efficient via sorted leaf pages linked in order Efficient within a level but requires merging sorted runs across levels Key Differences A B-Tree updates data in place, while an LSM Tree defers changes through append-only writes to a memtable LSM Trees gain higher write throughput by avoiding random disk seeks, at the cost of ongoing compaction B-Trees give more predictable read latency since each key lives in exactly one place LSM read and space overhead comes from having to consult multiple SSTable levels Deletes in an LSM Tree are recorded as tombstones rather than removed immediately When to Use Each B-Tree ...

Overview Range and hash partitioning are two strategies for splitting a table’s rows across multiple partitions or nodes based on a partition key. Range partitioning assigns rows to contiguous key intervals (like date ranges), preserving order for efficient range scans but risking uneven load. Hash partitioning runs the key through a hash function to scatter rows evenly, trading away ordering for balanced, predictable distribution. Comparison Diagram RANGE PARTITIONINGHASH PARTITIONINGincoming keysincoming keys1-3334-6667-1001-3334-6667-100hash(key)P1P2P3P1P2P3Ordered, contiguous rangesScattered, uniform spreadEasy to extend: add a boundaryCostly to resize: rehash keysRisk: skew on hot rangesRisk: no range pruning Comparison Table Aspect Range Partitioning Hash Partitioning Partition key requirement Needs an orderable key with defined boundaries (dates, IDs) Any key works; only needs to be hashable Row-to-partition mapping Explicit boundary rules assign rows to intervals Hash function output (often mod N) selects the bucket Data distribution Can be skewed if key values aren’t uniformly spread Near-uniform if the hash function distributes well Range/scan queries Prunes to only the partitions covering the range Must fan out and scan every partition Point/equality lookups Requires a boundary search to find the right partition Direct O(1) computation locates the partition Adding or removing partitions Cheap: append or split a boundary at the edge Expensive: reshuffles most existing keys unless using consistent hashing Hotspot behavior Sequential writes (recent dates, auto-increment IDs) pile onto one partition Spreads writes evenly but destroys any physical data locality Key Differences Range partitioning preserves order, letting the query planner prune partitions; hash partitioning optimizes purely for even distribution Growing the partition count is a cheap boundary edit in range partitioning but forces a rehash of most keys in hash partitioning Range schemes are exposed to skew when writes cluster in a narrow key window; hash schemes avoid this at the cost of locality Point lookups under hashing are a direct hash computation, while range lookups need a boundary search through ordered intervals When to Use Each Range Partitioning ...

Overview Synchronous and asynchronous replication differ in exactly one moment: when the primary tells the client a write succeeded. Sync replication waits for the replica to confirm before acknowledging, while async replication acknowledges immediately and copies the data afterward. That single timing difference cascades into everything else — latency, throughput, and how much data you can lose on failover. Comparison Diagram Sync ReplicationAsync ReplicationClientPrimaryReplica1. write2. replicate3. ack4. commitClient waits for step 3ClientPrimaryReplica1. write2. commit3. replicate laterClient returns at step 2 Comparison Table Aspect Sync Replication Async Replication Write acknowledgment Waits for replica confirmation before committing Commits on primary alone, replicates after Commit latency Includes network round-trip to replica Bound only by primary’s local write Data consistency Replica is always up to date at commit time Replica can lag behind primary momentarily Throughput under load Degrades as replica distance or count grows Unaffected by replica speed or distance Replica or network failure Writes block or fail until replica responds Writes continue uninterrupted on primary Failover data loss None — replica always has the committed write Possible — unreplicated writes are lost Replication lag monitoring Not applicable — lag is structurally zero Critical — must track and alert on lag Key Differences Commit timing is the root difference: sync waits, async doesn’t Sync trades latency for a zero-data-loss guarantee on failover Async trades durability for consistently fast local commits Multi-region setups favor async since round-trip time would make sync commits too slow Async requires active lag monitoring that sync simply doesn’t need When to Use Each Sync Replication ...

Overview Both are techniques for scaling a database beyond a single node, but they solve different problems: replication copies the entire dataset onto multiple nodes to boost availability and read capacity, while sharding splits the dataset into disjoint partitions across nodes to boost storage and write capacity. Large-scale systems typically use both together — sharding for horizontal scale, replication within each shard for durability. Comparison Diagram Replication Sharding Primary A B C D Replica A A B C D Replica B A B C D full dataset, copied to every node Router key lookup Shard 1 keys A-M Shard 2 keys N-Z dataset split into disjoint subsets Comparison Table Aspect Replication Sharding Primary goal Increase availability and read capacity Increase storage and write capacity Data distribution Full dataset copied to every node Dataset split into disjoint partitions across nodes Write path Writes go to primary, then propagate to replicas Writes routed to the single shard owning the key Read path Any replica (or primary) can serve any read Read must be routed to the shard holding the key Node failure impact Data survives since other copies exist That shard’s data becomes unavailable unless also replicated Consistency concern Replication lag between primary and replicas Cross-shard transactions and joins are hard to coordinate Scaling ceiling Bounded by primary’s write throughput Bounded by cross-shard coordination and key hotspots Operational overhead Failover and leader election Shard key design, rebalancing, and resharding Key Differences Replication duplicates the same data everywhere; sharding partitions it so each node holds only a slice Replication scales reads and durability; sharding scales writes and total storage Sharding introduces a routing layer that must know which shard owns a given key Losing a replica is harmless, but losing an unreplicated shard causes real data loss Production systems commonly combine both: shard for scale, replicate each shard for resilience When to Use Each Replication ...

Overview Normalization organizes data into separate, related tables to eliminate redundancy and protect integrity, while denormalization intentionally merges and duplicates data to boost read speed. The right choice depends on whether your workload is dominated by frequent writes or by heavy, complex reads. Comparison Diagram NormalizationDenormalizationUsersid, nameOrdersid, user_id, product_idProductsid, name, price3 linked tables, zero duplicationorder_id | customer | product101 | Alice | Widget102 | Alice | Gadget103 | Bob | Widget104 | Bob | Gizmo1 wide table, repeated values Comparison Table Aspect Normalization Denormalization Design goal Eliminate redundancy by decomposing data into logical entities Optimize for fast retrieval by pre-combining related data Table structure Many narrow, related tables linked by foreign keys Fewer, wider tables that embed related data directly Data redundancy Minimal; each fact stored in exactly one place Deliberate; the same fact may appear in many rows Write operations Single-row updates ripple correctly since data lives once Updates must touch every duplicated copy or drift occurs Read operations Requires assembling data from multiple tables Data is already co-located, so reads are direct Joins needed Frequent, often multi-table joins for common queries Rare or none, since data is flattened in advance Data integrity risk Low; constraints enforce a single source of truth Higher; duplicate copies can become inconsistent Storage requirements Compact, no duplicated values Larger footprint due to stored redundancy Key Differences Normalization removes redundancy by splitting data into related tables; denormalization reintroduces it deliberately for speed Normalized schemas need more joins at read time, while denormalized ones avoid them by pre-joining data Denormalization trades update simplicity for risk of anomalies when duplicated copies fall out of sync Normalization favors write-heavy transactional workloads; denormalization favors read-heavy analytical ones Storage cost is lower under normalization but query complexity is lower under denormalization When to Use Each Normalization ...

Overview SQL and NoSQL databases differ in how they structure, store, and query data: SQL enforces a fixed schema of related tables joined by keys, while NoSQL favors a flexible schema optimized for scale and varied data shapes. The choice affects everything from how you model relationships to how the system behaves under heavy write load or schema change. Comparison Diagram SQLNoSQLUsersidname1AliceOrdersiduser_iditem91Bookforeign key join{"id": 1,"name": "Alice","orders": [{ "item": "Book" },{ "item": "Pen" }]}embedded, self-contained document Comparison Table Aspect SQL NoSQL Data model Rows in normalized tables with fixed columns Documents, key-value pairs, wide columns, or graphs with flexible fields Schema definition Defined upfront; changes require migrations (ALTER TABLE) Schema-on-read; fields can vary per record without migration Relationships Modeled explicitly via foreign keys and JOINs Modeled by embedding related data or denormalizing across documents Query language Standardized SQL across most vendors Vendor-specific APIs or query languages (e.g. MongoDB query, CQL) Transactions & consistency ACID guarantees across multi-row/multi-table operations Often eventual consistency; ACID typically limited to single-document scope Scaling approach Primarily vertical scaling; sharding is possible but complex Built for horizontal scaling via native partitioning/sharding Best-fit workload Structured data with complex, ad-hoc relational queries High-volume, high-velocity data with evolving or hierarchical structure Key Differences SQL requires a fixed schema agreed on before writing data; NoSQL allows each record to carry its own shape Relational databases resolve relationships through JOINs, while NoSQL typically resolves them through embedding SQL guarantees ACID transactions across tables; most NoSQL systems trade that for eventual consistency SQL systems scale primarily by scaling up hardware; NoSQL systems are designed to scale out across nodes Query language is a standardized across SQL vendors, whereas NoSQL query APIs are largely proprietary When to Use Each SQL ...

Overview Vertical scaling grows capacity by adding more CPU/RAM to a single machine, while horizontal scaling grows capacity by adding more nodes behind a load balancer. The choice shapes your application’s architecture, failure model, and cost curve as it grows. Comparison Diagram VerticalHorizontalServerServer+CPU +RAMServer++CPU ++RAMLoad BalancerNodeNodeNode+NodeSingle node, growingMany nodes, distributed Comparison Table Aspect Vertical Scaling Horizontal Scaling Scaling mechanism Add CPU, RAM, or faster disks to one machine Add more machines/nodes to a shared pool Architecture requirement Works with any app, no code changes needed Requires stateless design, load balancing, and shared state (session store, distributed cache) Upper limit Capped by the largest hardware SKU available Effectively unbounded, limited only by orchestration and cost Downtime during scale-up Often requires reboot or migration to bigger instance New nodes join the pool live, no downtime Fault tolerance Single point of failure — one box, one crash Node failures are absorbed by the remaining pool Cost curve Price rises non-linearly at the high end (diminishing returns) Roughly linear cost per added unit of capacity Operational complexity Low — one server to patch, monitor, and secure Higher — needs service discovery, distributed monitoring, data consistency handling Typical use case Monolithic apps, relational databases, legacy systems Stateless web services, microservices, cloud-native workloads Key Differences Vertical scaling upgrades a single machine; horizontal scaling adds more machines to a pool Horizontal scaling demands stateless services, while vertical scaling needs no architectural change Vertical scaling has a hard hardware ceiling; horizontal scaling scales near-linearly A single oversized server is a single point of failure, unlike a distributed node pool Horizontal scaling trades simplicity for operational complexity in orchestration and consistency When to Use Each Vertical Scaling ...

Overview Strong and eventual consistency describe how distributed systems handle replicated data after a write. Strong consistency guarantees every read reflects the latest write by blocking until replicas agree, while eventual consistency returns immediately and lets replicas converge in the background. The choice trades write latency and availability against read freshness. Comparison Diagram Strong ConsistencyEventual ConsistencyClientPrimaryReplica 1Replica 2write blocks untilall replicas ackAny read, any replica,always returns latest valueClientNodeReplica 1Replica 2ACK immediateasync, delayedRead from Replica 1 mayreturn stale value until t+Δ Comparison Table Aspect Strong Consistency Eventual Consistency Write acknowledgment Ack returned only after write is durably applied to all (or a quorum of) replicas Ack returned as soon as the write hits the local/primary node Replication propagation Synchronous — write blocks until replicas confirm Asynchronous — replication happens in the background Read guarantee Every read reflects the most recent write (linearizable) Reads may return stale data until replicas converge Conflict handling Prevented upfront via consensus/locking that serializes writes Resolved after the fact via LWW, vector clocks, or CRDTs Write latency Higher — pays network round-trip cost to replicas/quorum Lower — commits locally before propagating Behavior under partition Unavailable or degraded if quorum can’t be reached (CP) Stays available, serving from whichever replica is reachable (AP) Typical mechanism Consensus protocols like Paxos/Raft, synchronous quorum writes Gossip protocols, anti-entropy repair, background sync Typical use cases Banking ledgers, inventory counts, leader election Social feeds, DNS, shopping carts, CDN caches Key Differences Strong consistency blocks the write until a quorum confirms; eventual consistency acks after a local commit. This is the classic CAP tradeoff: strong favors consistency during a partition, eventual favors availability. Strong relies on consensus protocols like Raft; eventual relies on background anti-entropy repair. Only strong consistency guarantees read-after-write; eventual consistency allows a stale-read window. When to Use Each Strong Consistency ...

Overview When a distributed system suffers a network partition, it must choose between consistency (every node sees the same data, even if that means rejecting requests) and availability (every request gets a response, even if the data might be stale). This CAP theorem tradeoff shapes how databases behave under failure and directly affects correctness guarantees versus uptime. Comparison Diagram Consistency (CP)Availability (AP)ClientClient503 blocked200 OK (stale)Node ANode BpartitionNode ANode BpartitionWaits for quorum, rejects requestGuarantee: no stale readsAnswers immediately from local dataGuarantee: no downtime Comparison Table Aspect Consistency (CP) Availability (AP) Normal operation (no partition) Behaves identically to any healthy cluster; all replicas agree Behaves identically to any healthy cluster; all replicas agree Behavior when a partition occurs Nodes that cannot confirm quorum stop responding All nodes keep responding regardless of quorum status Write handling during partition Writes are rejected or queued until enough replicas are reachable Writes are accepted locally and replicated once the partition heals Read handling during partition Reads are blocked or errored if the latest value can’t be confirmed Reads are served from whatever local replica is reachable, even if stale Client-facing failure mode Client sees a timeout or explicit error (e.g. 503) Client sees a successful response that may contain outdated data Data guarantee provided Linearizability - no two nodes ever disagree on current state Liveness - the system always answers, correctness may lag Recovery after partition heals Resumes cleanly; no conflicting writes existed since they were blocked Must reconcile diverging writes via vector clocks, LWW, or CRDTs Representative systems HBase, Zookeeper, MongoDB (default majority writes) Cassandra, DynamoDB, Riak Key Differences The tradeoff only bites during an actual network partition - outside of that, both behave the same. Consistency requires a quorum agreement before answering, which can mean refusing requests. Availability guarantees a response but risks returning stale data to the client. The choice determines whether you need a conflict resolution strategy for divergent writes after recovery. Many production databases offer tunable consistency, letting you pick per-operation rather than a single global stance. When to Use Each Consistency (CP) ...

Overview Latency and throughput are two orthogonal measures of system performance: latency is the time a single request takes to complete, while throughput is the volume of work a system finishes per unit of time. The distinction matters because architectures optimized for one can quietly degrade the other. Comparison Diagram Latency Client Server Time for ONE request to complete Throughput Client Server Total requests completed per second Comparison Table Aspect Latency Throughput Definition Time elapsed for one request to travel and complete Amount of work completed across all requests per unit time What is measured A single request’s round trip or processing delay Aggregate output of the system over an observation window Unit of measurement Milliseconds, microseconds, or seconds Requests/sec, transactions/sec, or Mbps Primary driver Network round-trip time, serialization, and processing delay Available bandwidth, parallel capacity, and resource pool size Effect of concurrency Individual request latency can rise as queueing builds up Throughput rises with more parallel workers, up to a capacity limit Behavior under overload Tail latency spikes as queues grow (p95/p99 degrade) Throughput plateaus or drops once the system saturates Typical optimization Reduce round trips, cache results, shorten the critical path Batch requests, add parallel workers, scale out capacity Measurement method Ping, request timers, percentile latency (p50/p95/p99) Requests-per-second counters, load testing, capacity benchmarks Key Differences Latency measures the time for one request; throughput measures the volume processed per unit time. Batching to raise throughput can increase tail latency for individual requests. Latency is bounded by physical round-trip time; throughput is bounded by system capacity. Under heavy load, latency spikes from queueing while throughput plateaus at a ceiling. Little’s Law links the two: average latency times concurrency roughly equals throughput. When to Use Each Latency ...