NoSQL Databases

NoSQL (non-relational) databases store data in flexible formats rather than fixed tables, and are designed to scale horizontally. They typically favor availability and partition tolerance (BASE) over strict consistency, making them a fit for large-scale, fast-changing, or unstructured data.

1. Learning Objectives

By the end of this lesson, you will be able to:

• Differentiate between the four primary NoSQL database models (Key-Value, Document, Wide-Column, and Graph stores) and identify their optimal workloads.
• Apply the CAP and PACELC theorems to analyze and justify architectural choices in distributed data systems.
• Explain the internal storage mechanics of write-optimized Log-Structured Merge (LSM) Trees and read-optimized B-Trees.
• Design horizontal partitioning schemas using consistent hashing and virtual nodes (vnodes) to prevent hotspots.
• Calculate quorum write and read configurations ($R + W > N$) to tune consistency vs. availability.

2. Prerequisites

Before diving into NoSQL database internals, you should be familiar with:

• Relational Database Management Systems (RDBMS): ACID transactions, normal forms (1NF, 2NF, 3NF), and indexes.
• Network Partitioning and Sharding: The core challenges of splitting databases across multiple machines.
• Basic Data Structures: Binary Search Trees, Hash Maps, and Directed/Undirected Graphs.

3. Why This Topic Matters

Traditional SQL databases were built for single-node systems where data fits on a single hard drive and transactional integrity is paramount. In contrast, modern web scale systems process petabytes of data, require sub-second worldwide latencies, and must stay operational 24/7. Scaling an RDBMS horizontally is notoriously complex, requiring manual application-level sharding, breaking foreign key relations, and introducing single points of failure.

NoSQL databases offer a path forward by intentionally sacrificing certain RDBMS features (like complex joins and multi-row ACID transactions) in exchange for automated horizontal scaling, high write throughput, and schema flexibility. As a system designer, choosing between NoSQL and relational architectures is one of the most critical decisions you will make. Getting it wrong can lead to costly database migration projects, performance bottlenecks, or catastrophic data loss.

4. Real-world Analogy

To understand NoSQL database structures, imagine a massive warehouse where different inventory managers organize items differently:

• Key-Value Store: A coat check system. You exchange a token (key) for a coat (value). The staff does not inspect the coat; they simply return it instantly when you hand them the matching token.
• Document Store: A cabinet of patient folders in a doctor's office. Each patient has their own folder. Some folders have insurance forms, lab reports, and allergy lists; others contain only a basic name and phone number. There is no rigid structure, and all details about a patient are stored together.
• Wide-Column Store: A huge spreadsheet ledger where each row represents a customer account. One row might have columns for name, address, and email, while another row might only have columns for name and transaction history. New columns can be created dynamically on any row.
• Graph Database: A detective's evidence board. Pins represent suspects, phone numbers, and bank accounts (nodes). Strings of different colors connect the pins (edges) representing actions like "called", "sent money to", or "lives with". Finding relationships is as simple as following the strings directly.

5. Core Concepts

1. Horizontal Scalability (Sharding)

Rather than upgrading to larger, more expensive servers (vertical scaling), NoSQL scales out by partitioning data across a cluster of commodity nodes. Partitioning is handled automatically via hashing algorithms, allowing nodes to be added or removed without downtime.

2. Schema Flexibility

Unlike relational databases that enforce strict column and data type constraints per table, NoSQL databases support dynamic schemas. Rows or documents in the same collection can contain entirely different fields, which simplifies working with rapidly evolving data models.

3. BASE vs. ACID

To achieve high scale and availability, NoSQL databases trade strict ACID (Atomicity, Consistency, Isolation, Durability) guarantees for the BASE model:

• Basically Available: The database guarantees that reads and writes are serviced even if portions of the cluster are unreachable.
• Soft State: The values stored in replicas can change dynamically without user intervention as updates propagate asynchronously.
• Eventual Consistency: Replicas will eventually converge to the same state when no further writes are applied.

4. CAP and PACELC Theorems

The CAP Theorem states that in the event of a network partition (P), a distributed database must choose between Availability (A) and Consistency (C). The PACELC theorem expands this definition:

• If there is a Partition, how does the system choose between Availability and Consistency?
• Else (when the system is running normally), how does the system choose between Latency and Consistency?

6. Visualization

The following Mermaid diagrams illustrate the Consistent Hashing Ring topology and a structural comparison of the four main NoSQL database families:

Consistent Hashing Ring with Virtual Nodes

Comparison of NoSQL Data Layouts

7. How It Works

The lifecycle of a write or read request in a distributed, leaderless NoSQL database operates through the following steps:

1. Request Ingestion: A client driver sends a write or read request. In a leaderless database (like Apache Cassandra), this request can be sent to any node in the cluster, which takes on the role of the Coordinator Node for that specific request.
2. Consistent Hashing: The Coordinator hashes the request's partition key using a hashing algorithm (e.g., Murmur3) to compute a token. The Coordinator compares this token against its internal partition map to identify which physical nodes own that token's range on the hash ring.
3. Replication & Routing: The Coordinator forwards the request to the primary node and $N-1$ replica nodes (where $N$ is the database's replication factor). The replication routes are typically determined clockwise along the hash ring.
4. Quorum Evaluation:
   • For writes, the Coordinator waits until $W$ replica nodes acknowledge that the write has been successfully committed to their memory and disk log before returning success to the client.
   • For reads, the Coordinator requests data from $R$ replicas, compares their timestamps, and returns the newest version to the client.
5. Read Repair & Convergence: If a read quorum query reveals that one of the replica nodes returned stale data (based on version timestamps or vector clocks), the Coordinator responds to the client immediately with the correct value and schedules an asynchronous "read repair" task in the background to update the stale replica.

8. Internal Architecture

NoSQL databases designed for high write throughput utilize Log-Structured Merge (LSM) Trees rather than B-Trees. Below is a detailed mapping of the internal components involved in these systems:

Component	Responsibility	Failure Point / Risk	Mitigation Strategy
Write-Ahead Log (WAL)	Ensures durability by appending write requests to an on-disk sequential log before confirming.	I/O bottleneck if forced to sync to disk synchronously for every write.	Perform asynchronous sequential writes, batching disk syncs periodically.
Memtable	An in-memory, sorted write buffer (usually implemented as a Skip List or Red-Black Tree).	Data loss on sudden server crash before the buffer is flushed.	Replay the Write-Ahead Log (WAL) on startup to reconstruct the Memtable.
SSTable (Sorted String Table)	Immutable sorted files on disk containing data flushed from Memtables.	Read amplification: reads must scan multiple SSTables to resolve the latest version of a key.	Run background compactions to merge files and discard overwritten values/tombstones.
Bloom Filter	A space-efficient probabilistic data structure used to check if an SSTable does not contain a key.	High false positive rate if memory allocated is too small, increasing disk seek counts.	Optimize bloom filter bit array size configurations based on workload profiles.
Gossip Protocol	A decentralized peer-to-peer protocol for discovering cluster topology, sharing node status, and schema versions.	Slow propagation of node-down events or network partitions mimicking node failure.	Use phi-accrual failure detectors to estimate state changes dynamically.

9. Request Lifecycle

1. Detailed Write Path Lifecycle

1. The database client invokes a write API (e.g., INSERT INTO users (id, name) VALUES ('u1', 'Alex')).
2. The client driver routes the request to a Coordinator node using token-aware routing.
3. The Coordinator identifies the $N$ replica nodes on the hash ring that should store this key.
4. The Coordinator simultaneously forwards the write to all $N$ replicas.
5. Each replica node performs the write locally:
   • Appends the write transaction to the Write-Ahead Log (WAL) on disk (ensuring durability).
   • Inserts the record into the sorted in-memory Memtable.
6. Once a replica successfully writes to both WAL and Memtable, it returns a success confirmation to the Coordinator.
7. After the Coordinator gathers $W$ acknowledgments (where $W$ is the write quorum), it returns a success code to the client.

2. Detailed Read Path Lifecycle

1. A client requests a record (e.g., querying by partition key 'u1').
2. The client driver forwards the read query to the Coordinator.
3. The Coordinator identifies the replicas holding the key on the hash ring and polls $R$ of them.
4. Each replica searches for the key:
   • Checks the sorted Memtable. If found, this is the most recent copy.
   • Consults the Bloom filters of its disk-based SSTables. If the filter returns false, the SSTable is skipped.
   • If the filter returns true, the replica searches the SSTable indexes (cached in memory) to find the block on disk and reads the record.
5. The replicas return the data and their corresponding timestamps.
6. The Coordinator matches the values:
   • If the values are identical, the Coordinator returns the record to the client.
   • If there is a conflict, the Coordinator resolves it (typically Last-Write-Wins), responds to the client with the resolved record, and issues an asynchronous background read repair to write the resolved value to the stale replicas.

10. Deep Dive

1. Storage Engine Mechanics: B-Trees vs. LSM Trees

Storage engine design determines a database's optimal workloads.

• B-Trees (Read-Optimized): B-Trees split data into fixed-size pages (typically 4KB to 16KB) and maintain sorted balances. An update requires reading a page into memory, modifying it, and writing it back to disk. This involves random disk writes, which can be highly inefficient at scale. They are ideal for read-heavy systems with sparse updates (e.g., MongoDB, PostgreSQL).
• LSM Trees (Write-Optimized): LSM trees defer disk writes. They buffer all inserts, updates, and deletes in a memory queue (Memtable). When the Memtable fills up, its contents are written out to disk sequentially as a Sorted String Table (SSTable). Since SSTables are immutable, there is no random write overhead. Over time, background processes run compaction, merging multiple SSTables into a single file and removing overwritten data or tombstoned deletes.

2. Tunable Quorums and Mathematical Consistency

Quorums allow system administrators to dynamically trade off consistency, availability, and latency.

• Strong Consistency Formula ($R + W > N$): Ensuring the read quorum $R$ and write quorum $W$ overlap guarantees that at least one node in the read quorum contains the latest write. For example, if $N = 3$, setting $W = 2$ and $R = 2$ guarantees strong consistency because $2 + 2 = 4 > 3$.
• Weak / Eventual Consistency ($R + W \le N$): If we configure $N = 3, W = 1, R = 1$, we optimize for latency and availability. Writes return immediately after hitting a single replica, and reads do the same. However, a read may retrieve stale data if the replica has not yet synced with the node that received the write.

3. Conflict Resolution Internals

In leaderless NoSQL databases, network splits or concurrent writes inevitably cause replicas to diverge. Databases resolve these conflicts using three primary strategies:

• Last-Write-Wins (LWW): Uses physical microsecond wall-clock timestamps. Simple and performant, but highly vulnerable to physical clock drift.
• Vector Clocks: Tracks logical time increments per replica. When two nodes accept divergent writes, the vector clock flags a conflict, which must be resolved by application logic.
• Conflict-Free Replicated Data Types (CRDTs): Data structures whose merge operation is mathematically proven to converge to the same value regardless of the order of operations. Common CRDTs include PN-Counters (positive/negative counters) and OR-Sets (observed-remove sets).

11. Production Example

1. Netflix Catalog & Viewing History (Apache Cassandra)

Netflix generates billions of telemetry and user tracking events every day. To scale writes, Netflix uses Apache Cassandra. They configure a multi-datacenter active-active cluster topology. When a user in Virginia pauses a video, the write hits the nearest AWS datacenter with $W = \text{LOCAL_QUORUM}$ to guarantee sub-millisecond write times. The updates are asynchronously replicated to Frankfurt and Singapore in the background. If a fiber optic link breaks, the European and Asian nodes continue to serve reads and writes locally. Once connectivity is restored, the clusters synchronize via hinted handoffs and read repair.

2. Amazon Shopping Cart (DynamoDB)

During shopping holidays like Prime Day, database availability is directly tied to revenue. Amazon DynamoDB uses consistent hashing and Paxos consensus groups to replicate data partitions across multiple Availability Zones. If one AZ experiences a power outage, the shopping cart writes are seamlessly redirected to another partition group member, maintaining low latency and high availability.

12. Advantages

• Seamless Horizontal Scaling: Nodes can be added to the hash ring to scale writes and storage linearly without central bottlenecking.
• Dynamic Data Modeling: The schema-less nature allows teams to store semi-structured JSON objects without running slow database migrations.
• Write Throughput Optimization: Databases utilizing LSM Trees append writes sequentially to disk, maximizing write speeds.
• High Availability & Fault Tolerance: Leaderless clusters operate without single points of failure, maintaining service availability through node outages.
• Optimized Latency: Direct lookups based on partition keys skip expensive joins and secondary index lookups.

13. Limitations

• No Native Multi-Table JOINs: Joining tables requires denormalization or complex application-level logic.
• Eventual Consistency Risks: Reading stale data shortly after a write can lead to race conditions.
• Lack of Multi-Row ACID Transactions: While most NoSQL systems guarantee single-row transaction safety, they do not support multi-row transactions across shards.
• Poor Secondary Index Performance: Secondary indexes are local to each node. Searching by secondary attributes requires polling all nodes, which degrades read throughput.
• Lack of Query Standardization: There is no universal querying language, which increases learning curves and vendor lock-in risks.

14. Trade-offs

1. Normalization vs. Denormalization

In relational databases, you normalize data to eliminate redundancy, using JOINs to assemble views. In NoSQL, storage is cheap, but compute is expensive. You duplicate data (denormalization) across multiple tables optimized for specific query paths. The trade-off is faster reads at the cost of higher storage footprints and complex update operations when shared attributes change.

2. PACELC: Consistency vs. Latency

Under normal operating conditions (no partitions), a NoSQL database can prioritize low latency (responding with the first returned value from any replica) or consistency (waiting for all replicas to agree). Tuning for strong consistency ($R + W > N$) increases query latencies and reduces system availability during network hiccups.

3. Storage Layout: LSM Trees vs. B-Trees

LSM Trees maximize write throughput at the cost of read performance (reads must scan multiple SSTables). B-Trees offer fast, single-page read performance at the cost of slower writes (which require random disk page modifications).

15. Performance Considerations

• Choosing Partition Keys: Avoid low-cardinality attributes (e.g., status) which force all writes to a single physical node, creating hotspots. Use high-cardinality keys like user_id.
• Compaction Tuning: Select the correct compaction strategy for your workload:
  • Size-Tiered Compaction Strategy (STCS): Optimizes writes by merging SSTables of similar sizes. However, it requires up to 50% free disk space for compaction.
  • Leveled Compaction Strategy (LCS): Optimizes reads by keeping SSTables non-overlapping within levels. Increases write amplification but reduces read latency.
• Tombstone Saturation: Deleting a row in an LSM database creates a "tombstone" marker. Over-deleting results in reads scanning millions of tombstones before finding active data, leading to severe latency spikes and JVM Out-Of-Memory (OOM) errors.
• Token-Aware Driver Routing: Ensure your application clients are configured to query target storage nodes directly, skipping coordinator hop latency.

16. Failure Scenarios

1. Split-Brain Divergence

When a network partition splits a cluster, if both sides continue accepting writes independently, the database state will diverge. If quorums are configured incorrectly ($W=1$), reconciling the divergent history after the partition heals is extremely difficult and often results in lost data.

2. Clock Drift Silent Data Corruption

Systems using Last-Write-Wins (LWW) conflict resolution rely on physical clocks. If Node A's physical clock drifts 5 seconds into the future, all writes handled by Node A will be stamped with this future time. When Node B subsequently receives updates with a correct clock, they will be discarded because they appear "older" than Node A's future-stamped records.

3. Cascading Failures during Re-balancing

If Node A crashes, its virtual node ranges are redistributed to Node B and Node C. If the cluster is already running near resource limits, the added read/write load will overload Node B and Node C, causing them to crash. This triggers a chain reaction that can take down the entire cluster.

4. Hinted Handoff Storage Exhaustion

If a node goes offline, the coordinator holds writes for it as "hints" on disk. If the node remains down longer than the hint window configuration (e.g., 3 hours), the coordinator will stop saving hints. If the window is misconfigured to be infinite, the coordinator's disk will eventually fill up, causing it to crash as well.

17. Best Practices

• Design Tables for Queries: In NoSQL, design your tables specifically around your application's query patterns. Do not normalize first; build one table per query pattern if necessary.
• Bound Partition Sizes: Keep partition sizes below 100MB to avoid JVM heap pressure and long compaction times. Use composite keys (e.g., (user_id, bucket_day)) to split growing partitions.
• Define TTLs for Temporary Records: Set Time-To-Live values on transient data (like login tokens or session caches) to ensure they are cleaned up automatically without creating manual background delete queries.
• Monitor Compaction Lag: Ensure your compaction threads are keeping pace with your write rates. If compaction falls behind, read performance will degrade quickly.
• Utilize Read Repair and Active Anti-Entropy: Run regular background repairs (e.g., using Merkle trees) to resolve cold-data replica mismatches.

18. Common Mistakes

• Treating NoSQL like an RDBMS: Writing highly normalized schemas and relying on the application layer to run loop queries (e.g., N+1 queries) to perform joins.
• Selecting Low-Cardinality Partition Keys: Choosing partition keys like gender or status, which groups massive amounts of data onto single physical nodes, causing hotspots.
• Ignoring Clock Drift: Failing to configure Network Time Protocol (NTP) or Chrony on database instances when using Last-Write-Wins (LWW) resolution.
• Failing to Provision Disk for Compaction: Under-allocating disk space. Size-tiered compaction requires up to 50% free disk capacity to merge files.

19. Implementation

The following TypeScript implementation demonstrates a Consistent Hashing Ring with Virtual Nodes. This illustrates how distributed NoSQL databases route data to nodes based on partition key hashes:

20. Interview Questions

Easy Question

Question: What are ACID and BASE, and how do they differ in practice?

Answer:

• ACID (Atomicity, Consistency, Isolation, Durability) is the traditional relational model. It guarantees that the database state is always consistent. A write will block or fail if it violates data constraints.
• BASE (Basically Available, Soft State, Eventual Consistency) is the model adopted by NoSQL. It prioritizes availability. The system accepts writes even if replicas cannot communicate immediately. Replicas temporarily hold a "soft state" until they eventually converge.
• In practice: An ACID system guarantees that once a write is confirmed, all readers see the update immediately. A BASE system allows readers to retrieve stale data briefly to maximize availability and throughput.

Medium Question

Question: How does consistent hashing prevent hotspots, and what role do virtual nodes play?

Answer:

Consistent hashing maps physical servers and data keys to a 360-degree hash ring. When a key is inserted, it moves clockwise to the first node it encounters. This design ensures that when nodes are added or removed, only $K/N$ keys need to be rebalanced (where $K$ is total keys, $N$ is nodes), preventing cluster-wide hashing rehashing.

Virtual Nodes (vnodes): If physical nodes are directly placed on the ring, hashing distribution is rarely uniform, resulting in data skew. By mapping a single physical server to multiple virtual points (e.g., 256 vnodes per server), data is spread evenly across all physical hosts, mitigating hotspots and balancing load during replication and failovers.

Hard Question

Question: Detail how Cassandra resolves conflicts without a central leader node. Discuss LWW, vector clocks, and CRDTs along with their failure modes.

Answer:

Without a single leader, nodes accept writes independently. Conflicts are resolved via:

• Last-Write-Wins (LWW): Resolves conflicts using physical wall-clock timestamps.
  • Failure Mode: Physical clock drift. If Node A's clock drifts ahead, its stale writes will permanently overwrite newer data written to Node B with a correct clock.
• Vector Clocks: Tracks logical time increments.
  • Failure Mode: High write throughput creates "sibling explosion" where thousands of concurrent divergent states consume excessive RAM and slow down reads.
• CRDTs (Conflict-Free Replicated Data Types): Mathematical convergence structures (like PN-Counters).
  • Failure Mode: Limited expressiveness. They cannot represent complex transactions or relational operations.

21. Practice Exercises

Easy Exercise

Design a key-value store schema in Redis to cache user profiles. The profile must expire automatically after 2 hours. Detail the key syntax and Redis commands needed to store and update this profile.

Medium Exercise

Design a wide-column Cassandra schema for a global news publishing site. The query pattern is: "Retrieve the last 20 articles published in a specific category (e.g., 'technology') sorted by publication date." Define the partition key, clustering key, and sorting direction.

Hard Exercise

Design a multi-region active-active wide-column store cluster spanning London, New York, and Tokyo. The goal is to support an e-commerce inventory count where writes must succeed locally under 20ms, but total inventory across all datacenters must converge eventually without double-spending or counting errors. Propose the quorums and replication mechanisms.

22. Challenge Problem

System Design: Ingesting Smart Grid Telemetry at Scale

Scenario: You are the lead architect for a national power company. There are 100 million smart meters deployed, each sending electric consumption telemetry every 10 seconds. Each telemetry payload consists of: meter_id, timestamp, voltage, and current_usage_kw. This translates to an average ingestion rate of 10 million write events per second.

Requirements & Constraints:

• Writes must return success with sub-15ms latency.
• Grid operators must query a specific meter's usage history for the last 24 hours in under 50ms.
• Daily analytical aggregation queries (e.g., computing hourly total usage grouped by city) must run without impacting raw write ingestion performance.

Design Task:

Draft a design covering:

1. The selected NoSQL database type and write/read storage engine (LSM vs B-Tree).
2. The schema design, partition key, and clustering columns chosen to prevent partition size skew and hot partitions.
3. How write and read quorums are configured to support the target ingestion latencies.
4. The scaling and isolation mechanisms used to run background analytical aggregates without impacting frontend performance.

23. Summary

NoSQL databases represent a paradigm shift in system design, trading relational simplicity and strict consistency for horizontal scalability, high write throughput, and schema flexibility. By choosing between key-value, document, wide-column, and graph architectures, designers align physical storage and routing models (LSM trees, consistent hashing rings, adjacency lists) directly to their application's query patterns, enabling performant systems that scale to billions of users.

24. Cheat Sheet

NoSQL Family	Storage Layout	Best Use Cases	Primary Strength	Primary Weakness
Key-Value	In-memory / disk hash maps (Redis, Memcached)	Session cache, shopping carts, rate limiters	Sub-millisecond latencies for direct key lookups	Cannot query values without keys; no structural index
Document	JSON/BSON trees (MongoDB, CouchDB)	E-commerce product catalogs, user profiles	Flexible, hierarchical, nested schemas	High indexing overhead at write-heavy scale
Wide-Column	LSM Trees, SSTables (Cassandra, ScyllaDB)	IoT telemetry, log aggregation, time-series data	Massive, linear sequential write throughput	Compaction overhead; read amplification
Graph	Adjacency lists and pointers (Neo4j, Amazon Neptune)	Social graphs, recommendation engines, fraud detection	Fast multi-hop traversal without joins	Extremely difficult to shard horizontally across cluster nodes

25. Quiz

1. In the PACELC theorem, what does the 'E' stand for?
   • A) Elasticity
   • B) Eventual Consistency
   • C) Else (when there is no network partition)
   • D) Execution time

   Correct Answer: C

   Explanation: PACELC is an extension of the CAP theorem. If there is a Partition (P), trade-off Availability (A) vs Consistency (C); Else (E), trade-off Latency (L) vs Consistency (C).

2. Which NoSQL data structure is specifically optimized to maximize sequential write throughput by avoiding random disk write I/O?
   • A) B-Tree
   • B) Log-Structured Merge (LSM) Tree
   • C) Red-Black Tree
   • D) Skip List

   Correct Answer: B

   Explanation: LSM Trees buffer updates in memory (Memtable) and write them sequentially to disk as SSTables, completely avoiding random page updates on disk.

3. If a leaderless NoSQL cluster is configured with Replication Factor $N = 3$, Write Quorum $W = 2$, and Read Quorum $R = 2$, what consistency guarantee is achieved?
   • A) Weak Consistency
   • B) Eventual Consistency only
   • C) Strong Consistency
   • D) Causal Consistency only

   Correct Answer: C

   Explanation: Strong consistency is guaranteed because $R + W > N$ ($2 + 2 > 3$). The write and read quorums overlap by at least one replica node, guaranteeing that the read retrieves the latest write.

4. What is the primary function of a Bloom Filter in the read path of an LSM database?
   • A) To cache hot records in memory.
   • B) To compress the sorted index on disk.
   • C) To verify the cryptographic integrity of files.
   • D) To quickly determine if an SSTable definitely does not contain a key, skipping unnecessary disk I/O.

   Correct Answer: D

   Explanation: Bloom filters are space-efficient probabilistic data structures that can verify with 100% certainty if a key is not present in a given SSTable file, preventing expensive disk reads.

5. Which category of NoSQL databases is typically the most difficult to shard horizontally across physical nodes?
   • A) Key-Value Store
   • B) Document Store
   • C) Wide-Column Store
   • D) Graph Database

   Correct Answer: D

   Explanation: Graph databases represent highly connected nodes and relationships. Sharding nodes across servers requires constant network hops (traversal cuts) to resolve query relations, making them hard to scale horizontally.

6. What type of metadata protocol is used in Cassandra to discover node statuses and manage membership without a single leader?
   • A) Raft Consensus Protocol
   • B) Paxos Consensus Protocol
   • C) Gossip Protocol
   • D) ZooKeeper Coordination Protocol

   Correct Answer: C

   Explanation: The Gossip protocol is a peer-to-peer decentralized metadata protocol used to discover and share cluster state and node health statistics in leaderless rings.

7. What is a "tombstone" in an LSM-tree database storage engine?
   • A) A record marking a node as permanently dead.
   • B) A marker written to signify a deletion without instantly modifying immutable SSTables.
   • C) The metadata block containing partition boundaries.
   • D) The last block of a write-ahead log.

   Correct Answer: B

   Explanation: Since SSTables are immutable on disk, a delete cannot modify them. Instead, a "tombstone" marker is written to mark the record as deleted. The actual record is deleted during compaction.

8. What is the purpose of virtual nodes (vnodes) in consistent hashing?
   • A) To virtualize operating system processes.
   • B) To cache client read requests on secondary indexes.
   • C) To balance the keyspace and load distribution evenly across physical hosts.
   • D) To elect partition group leaders.

   Correct Answer: C

   Explanation: vnodes map a single physical host to hundreds of virtual hash ring locations, distributing storage partitions evenly and avoiding load imbalance.

9. Under what condition can Last-Write-Wins (LWW) conflict resolution discard a newer write?
   • A) When write quorum $W$ is set to 1.
   • B) When physical clock drift causes a node to write an older wall-clock time stamp on a newer update.
   • C) When two client writes have identical UUIDs.
   • D) When compaction occurs before the client reads the update.

   Correct Answer: B

   Explanation: LWW resolves conflicts using physical microsecond timestamps. If clocks drift, a newer write may get timestamped with an older value, causing the database to drop it.

10. Which compaction strategy is optimized specifically for time-series workloads?
    • A) Size-Tiered Compaction Strategy (STCS)
    • B) Leveled Compaction Strategy (LCS)
    • C) Time-Window Compaction Strategy (TWCS)
    • D) Date-Range Compaction Strategy (DRCS)

    Correct Answer: C

    Explanation: TWCS groups SSTables into time windows and merges them, ensuring time-series data of similar ages is stored together and keeping older windows read-only to optimize compaction efficiency.

26. Further Reading

• The Dynamo Paper: "Dynamo: Amazon's Highly Available Key-value Store" (DeCandia et al., 2007)
• The Bigtable Paper: "Bigtable: A Distributed Storage System for Structured Data" (Chang et al., 2006)
• Designing Data-Intensive Applications by Martin Kleppmann (Chapters 3, 5, and 6 on storage models, replication, and partitioning).

27. Next Lesson Preview

Now that we understand how NoSQL databases achieve global horizontal scale, how do we speed up our read paths and protect databases from resource exhaustion? In the next lesson, we will cover Caching Strategies, analyzing how look-aside caches, write-through caches, eviction policies (LRU, LFU), and cache stampede mitigations work to keep systems stable under high loads.