Chapter 11: NoSQL Database Taxonomy

11.1 Why NoSQL Exists

The Relational Database Wall

By the mid-2000s, web-scale companies hit fundamental limits with traditional RDBMS:

The CAP Theorem Trade-off

Reality: Network partitions are inevitable in distributed systems (fiber cuts, switch failures, datacenter splits). So the real choice is CP vs AP.

Polyglot Persistence

Modern architectures use multiple database types within the same application, each optimized for specific access patterns:

11.2 Key-Value Stores

Conceptual Model

The simplest NoSQL data model: a distributed hash map. Every item has a unique key, and the value is an opaque blob (or typed data structure in advanced stores).

Redis

The Swiss Army Knife of KV stores. Single-threaded (no lock contention), in-memory with optional persistence, rich data structures beyond simple key-value.

Architecture

Persistence Strategies

Redis Cluster Partitioning

Key Routing:

slot = CRC16(key) % 16384
# Client contacts any node; if wrong slot, server returns MOVED redirect
# Smart clients cache slot-to-node mapping for direct routing

Memcached

Pure LRU cache. Simpler than Redis (no persistence, fewer data structures), multi-threaded (better for massive read-heavy workloads).

DynamoDB

AWS managed key-value + document store. Fully managed (no servers), single-digit millisecond latency, unlimited scale, pay-per-request or provisioned capacity.

Architecture

Data Model

Each item (row) must have a partition key (hash key). Optionally, a sort key (range key) for ordering items within a partition.

// Table: Users
{
  "userId": "user123",        // Partition key (PK)
  "name": "Alice",
  "email": "alice@example.com",
  "createdAt": 1620000000
}

// Table: OrderItems (composite key)
{
  "orderId": "order456",      // Partition key (PK)
  "itemId": "item789",        // Sort key (SK)
  "quantity": 2,
  "price": 29.99
}

// Query: Get all items for order456, sorted by itemId
GET orderId = "order456"

Secondary Indexes

Consistency Models

Adaptive Capacity

DynamoDB automatically redistributes capacity to hot partitions. If one partition gets 10x traffic, DynamoDB boosts its throughput temporarily (borrowing from unused capacity elsewhere).

etcd

Distributed KV store for configuration and coordination. Built on Raft consensus algorithm; used by Kubernetes for cluster state.

When to Use Key-Value Stores

11.3 Document Databases

Conceptual Model

Store documents (JSON, BSON, XML) as first-class entities. Unlike KV stores, documents have internal structure that the database can index and query.

MongoDB

The dominant document database. BSON format (binary JSON), rich query language, aggregation framework, sharding and replication built-in.

Architecture

Data Model

// Collection: users
{
  "_id": ObjectId("507f1f77bcf86cd799439011"),  // Auto-generated 12-byte ID
  "name": "Alice",
  "email": "alice@example.com",
  "age": 30,
  "address": {
    "street": "123 Main St",
    "city": "NYC",
    "zip": "10001"
  },
  "interests": ["hiking", "photography"],
  "createdAt": ISODate("2023-01-15T10:30:00Z")
}

// Collection: orders (reference to user)
{
  "_id": ObjectId("507f1f77bcf86cd799439012"),
  "userId": ObjectId("507f1f77bcf86cd799439011"),  // Reference
  "items": [
    { "productId": "prod123", "quantity": 2, "price": 29.99 },
    { "productId": "prod456", "quantity": 1, "price": 49.99 }
  ],
  "total": 109.97,
  "status": "shipped"
}

Embedding vs Referencing

Example Decision:

• Embed user's address (1:1, always accessed together)
• Reference user's orders (1:many, unbounded, orders queried separately)

Indexing

// Single-field index
db.users.createIndex({ email: 1 })  // 1 = ascending, -1 = descending

// Compound index
db.orders.createIndex({ userId: 1, createdAt: -1 })

// Multikey index (array fields)
db.users.createIndex({ interests: 1 })  // Indexes each array element

// Text index (full-text search)
db.products.createIndex({ description: "text" })

// Geospatial index
db.stores.createIndex({ location: "2dsphere" })

// Unique index
db.users.createIndex({ email: 1 }, { unique: true })

Aggregation Pipeline

Multi-stage data transformation (like Unix pipes):

db.orders.aggregate([
  // Stage 1: Filter
  { $match: { status: "shipped", createdAt: { $gte: ISODate("2023-01-01") } } },

  // Stage 2: Join with users collection
  { $lookup: {
      from: "users",
      localField: "userId",
      foreignField: "_id",
      as: "user"
  }},

  // Stage 3: Unwind array
  { $unwind: "$user" },

  // Stage 4: Group and aggregate
  { $group: {
      _id: "$user.city",
      totalRevenue: { $sum: "$total" },
      orderCount: { $sum: 1 }
  }},

  // Stage 5: Sort
  { $sort: { totalRevenue: -1 } },

  // Stage 6: Limit
  { $limit: 10 }
]);

Sharding Strategy

Elasticsearch

Document store + full-text search engine. Built on Apache Lucene; inverted index for fast text search; also used for log analytics (ELK stack).

Architecture

Inverted Index

Core data structure for full-text search:

// Documents
Doc1: "The quick brown fox jumps"
Doc2: "Quick brown dogs"
Doc3: "The lazy fox sleeps"

// Inverted Index (after tokenization + stemming)
Term        → Document IDs
"quick"     → [Doc1, Doc2]
"brown"     → [Doc1, Doc2]
"fox"       → [Doc1, Doc3]
"jump"      → [Doc1]
"dog"       → [Doc2]
"lazy"      → [Doc3]
"sleep"     → [Doc3]

// Query: "quick fox" → Match Doc1 (contains both terms)

Search Query DSL

POST /products/_search
{
  "query": {
    "bool": {
      "must": [
        { "match": { "description": "laptop" } }  // Full-text search
      ],
      "filter": [
        { "range": { "price": { "gte": 500, "lte": 1500 } } },
        { "term": { "brand": "Apple" } }
      ]
    }
  },
  "aggs": {
    "price_ranges": {
      "histogram": {
        "field": "price",
        "interval": 100
      }
    }
  },
  "sort": [
    { "_score": "desc" },  // Relevance score
    { "price": "asc" }
  ]
}

Use Cases

Firestore

Google's managed document database. Real-time sync, offline support, automatic scaling, tight integration with Firebase ecosystem.

When to Use Document Databases

11.4 Wide-Column Stores

Conceptual Model

Data organized into rows and column families. Each row can have arbitrary columns; optimized for high write throughput and time-series data.

Cassandra

Masterless, AP-focused wide-column store. Inspired by Amazon DynamoDB paper + Google Bigtable; tunable consistency, linear scalability, no single point of failure.

Architecture

Gossip Protocol

Nodes exchange cluster state information every second (peer-to-peer). No central coordinator; eventually all nodes learn about cluster changes (new nodes, failures).

// Node 1 gossips to Node 2:
{
  "Node1": { "status": "UP", "load": 45%, "version": 123 },
  "Node3": { "status": "UP", "load": 60%, "version": 122 },
  "Node4": { "status": "DOWN", "last_seen": 1620000000 }
}

// Node 2 merges with its own state and gossips to Node 3...
// Within seconds, all nodes agree on cluster state

Tunable Consistency

Specify consistency level per query (trade-off latency vs consistency):

Example: For strong consistency, use QUORUM for both reads and writes (with RF=3, require 2 nodes to agree). This ensures read always sees latest write.

Data Model

// CQL (Cassandra Query Language, SQL-like)
CREATE TABLE user_activity (
  user_id UUID,
  activity_date DATE,
  activity_time TIMESTAMP,
  action TEXT,
  PRIMARY KEY ((user_id), activity_date, activity_time)
);

// Partition Key: user_id (determines which node stores data)
// Clustering Columns: activity_date, activity_time (order within partition)

// Query: Get all activities for user on 2024-01-15
SELECT * FROM user_activity
WHERE user_id = 123e4567-e89b-12d3-a456-426614174000
  AND activity_date = '2024-01-15';

LSM Tree Storage

Write Path:

1. Write to commit log (append-only, fast sequential I/O)
2. Write to memtable (in-memory sorted structure)
3. Acknowledge write immediately (no disk read)
4. When memtable full, flush to SSTable (immutable on-disk file)

Read Path:

1. Check memtable (recent writes)
2. Check SSTables (use bloom filters to skip files that definitely don't have key)
3. Merge results from multiple SSTables (tombstones mark deletions)

Compaction: Background process merges SSTables, removes deleted data (tombstones), and reduces read amplification (fewer files to check).

When to Use Cassandra

HBase

Hadoop's wide-column store. Built on HDFS; strong consistency (CP); tight integration with Hadoop ecosystem (MapReduce, Spark).

Architecture

ScyllaDB

Cassandra-compatible, rewritten in C++. Shard-per-core architecture; 10x throughput of Cassandra; drop-in replacement (uses CQL).

Key Optimizations:

• Shard-per-Core: Each CPU core owns a shard (partition of data); no locks, no context switching
• User-Space I/O: Bypass kernel for disk/network I/O (DPDK, io_uring)
• No GC Pauses: Manual memory management (C++); predictable latency
• Automatic Tuning: Self-tunes cache sizes, compaction schedules, etc.

11.5 Graph Databases

Property Graph Model

Store nodes (entities) and relationships (edges) as first-class citizens. Each can have properties (key-value pairs).

Neo4j

The leading graph database. Native graph storage (index-free adjacency); Cypher query language; ACID transactions.

Index-Free Adjacency

Each node physically contains pointers to its relationships (like a linked list). Traversing relationships is O(1) (follow pointer), not O(log n) (index lookup).

Cypher Query Language

ASCII-art syntax for pattern matching:

// Find Alice's friends
MATCH (alice:Person {name: "Alice"})-[:FRIEND_OF]->(friend)
RETURN friend.name

// Find friends-of-friends (2 hops)
MATCH (alice:Person {name: "Alice"})-[:FRIEND_OF*2]-(foaf)
RETURN DISTINCT foaf.name

// Shortest path between Alice and Carol
MATCH path = shortestPath(
  (alice:Person {name: "Alice"})-[:FRIEND_OF*]-(carol:Person {name: "Carol"})
)
RETURN path

// Recommend products (friends who purchased)
MATCH (alice:Person {name: "Alice"})-[:FRIEND_OF]-(friend)
     -[:PURCHASED]->(product)
WHERE NOT (alice)-[:PURCHASED]->(product)
RETURN product.name, count(friend) AS friendCount
ORDER BY friendCount DESC
LIMIT 5

// Create new data
CREATE (alice:Person {name: "Alice", age: 30})
CREATE (bob:Person {name: "Bob", age: 25})
CREATE (alice)-[:FRIEND_OF {since: 2020}]->(bob)

Use Cases

Amazon Neptune

AWS managed graph database. Supports both property graph (Gremlin) and RDF (SPARQL); multi-AZ replication, automated backups.

When to Use Graph Databases

Rule of thumb: If your queries involve 3+ joins or recursive traversals in a relational database, consider a graph database.

11.6 Time-Series Databases

Characteristics

Optimized for append-only data with timestamps. Common in monitoring, IoT, financial data.

InfluxDB

Purpose-built time-series database. InfluxQL (SQL-like) + Flux (functional query language); clustering in Enterprise edition.

Data Model

// Measurement (like table)
// Tags: indexed, low-cardinality dimensions
// Fields: values, not indexed
// Timestamp: nanosecond precision

cpu_usage,host=server1,region=us-east value=45.2 1620000000000000000
cpu_usage,host=server2,region=us-west value=62.8 1620000001000000000
memory_usage,host=server1,region=us-east value=8192 1620000000000000000

// Query: Average CPU usage per region in last hour
SELECT MEAN(value) FROM cpu_usage
WHERE time > now() - 1h
GROUP BY region, time(5m)

Storage Engine

Compression: Delta encoding (store differences), run-length encoding (repeated values), dictionary encoding (strings).

TimescaleDB

PostgreSQL extension for time-series. Full SQL support; combines relational + time-series capabilities; automatic partitioning.

Hypertables

Automatic partitioning into "chunks" (time ranges):

-- Create hypertable
CREATE TABLE metrics (
  time TIMESTAMPTZ NOT NULL,
  device_id INT,
  temperature DOUBLE PRECISION,
  humidity DOUBLE PRECISION
);

SELECT create_hypertable('metrics', 'time');

-- Behind the scenes: TimescaleDB creates chunks
-- _hyper_1_1_chunk (2024-01-01 to 2024-01-08)
-- _hyper_1_2_chunk (2024-01-08 to 2024-01-15)
-- ...

-- Query transparently spans chunks
SELECT AVG(temperature) FROM metrics
WHERE time > NOW() - INTERVAL '7 days'
  AND device_id = 42;

Features

Prometheus

Monitoring system + time-series DB. Pull model (scrapes metrics); PromQL query language; integrates with Grafana for dashboards.

Architecture

Metric Types

# PromQL Examples

# CPU usage over 80% in last 5 minutes
avg(cpu_usage) > 80

# Request rate (requests/sec)
rate(http_requests_total[5m])

# 95th percentile latency
histogram_quantile(0.95, rate(http_request_duration_seconds_bucket[5m]))

# Disk space running out (predicts when disk full)
predict_linear(disk_free_bytes[1h], 4*3600) < 0

When to Use Time-Series Databases

11.7 NewSQL

The Best of Both Worlds

NewSQL databases aim to provide NoSQL scalability + RDBMS ACID guarantees. They achieve this through modern distributed systems techniques (Raft/Paxos, distributed transactions, snapshot isolation).

CockroachDB

Distributed SQL inspired by Spanner. PostgreSQL-compatible; multi-region; automatic rebalancing; survivable zone/region failures.

Architecture

Key Features

-- Standard PostgreSQL-compatible SQL
CREATE TABLE users (
  id UUID PRIMARY KEY DEFAULT gen_random_uuid(),
  email STRING UNIQUE,
  name STRING,
  region STRING
);

-- Geo-partition: Keep EU users in EU
ALTER TABLE users PARTITION BY LIST (region) (
  PARTITION eu VALUES IN ('eu'),
  PARTITION us VALUES IN ('us')
);

ALTER PARTITION eu CONFIGURE ZONE USING constraints='[+region=eu-west]';
ALTER PARTITION us CONFIGURE ZONE USING constraints='[+region=us-east]';

-- Transaction (serializable across nodes)
BEGIN;
UPDATE accounts SET balance = balance - 100 WHERE id = 'alice';
UPDATE accounts SET balance = balance + 100 WHERE id = 'bob';
COMMIT;

TiDB

MySQL-compatible NewSQL. Separates compute (TiDB servers) from storage (TiKV); Raft-based replication; HTAP (hybrid transactional/analytical).

Google Spanner

The original NewSQL. Global scale (used by Gmail, Google Ads); TrueTime API for external consistency; serializable isolation.

TrueTime

Spanner's secret sauce: TrueTime API provides a time interval with bounded uncertainty (typically < 7ms).

// TrueTime API
earliest, latest = TT.now()  // e.g., [t-3ms, t+3ms]

// Spanner uses this to order transactions globally
// Wait out the uncertainty before committing (commit-wait)
// Ensures transaction T1 committed before T2 starts → T1's timestamp < T2's timestamp

YugabyteDB

Distributed SQL with PostgreSQL compatibility. Built on Raft + RocksDB; multi-API (SQL, Cassandra CQL, Redis).

When to Use NewSQL

11.8 Selection Decision Framework

Use this flowchart to narrow down database type based on access patterns and requirements:

Key Decision Factors

Common Scenarios

11.9 Master Comparison Matrix

Comprehensive comparison of all NoSQL and NewSQL databases covered:

CAP Theorem Classification