Key-Value Stores

Redis and Memcached are excellent for caching and real-time features, but what happens when your key-value workload exceeds what fits in memory? When you need durability guarantees? When you need to serve billions of requests per day across multiple geographic regions?

This is where distributed key-value stores enter the picture. Unlike in-memory caches, these systems are designed for persistence, horizontal scalability, and high availability at scales that would overwhelm traditional databases.

Two of the most influential distributed key-value stores are:

• Amazon DynamoDB: A fully managed, serverless key-value and document database that scales automatically to handle trillions of requests per day.
• Riak: An open-source, Dynamo-inspired database designed for fault tolerance and operational simplicity.

Both trace their lineage to Amazon's groundbreaking 2007 Dynamo paper, which introduced concepts like consistent hashing, vector clocks, and quorum-based replication that now underpin many distributed systems.

In 2007, Amazon published the Dynamo paper, describing the key-value store powering Amazon.com's shopping cart and other critical services. The paper introduced and combined several distributed systems techniques that have become foundational:

Core Dynamo concepts:

The availability-first philosophy:

Dynamo was designed for always-on services where unavailability directly costs money (shopping carts). Its philosophy:

"It is better to occasionally return stale or conflicting data than to block the customer's request."

This led to eventual consistency as the default, with techniques to detect and resolve conflicts rather than prevent them.

Systems influenced by Dynamo:

• Apache Cassandra: Combines Dynamo's distribution with BigTable's data model
• Riak: Close implementation of Dynamo concepts, open source
• Voldemort: LinkedIn's Dynamo-style store (predecessor to Venice)
• Amazon DynamoDB: AWS managed service, evolved beyond original paper

DynamoDB is AWS's flagship NoSQL database service. It's fully managed—no servers to provision, no software to install, no replication to configure. You create a table, and AWS handles the rest.

Core concepts:

• Tables: Top-level containers for items (like a table in a relational database)
• Items: Individual records (like rows), identified by primary key
• Attributes: Name-value pairs within items (like columns, but schema-less)
• Primary Key: Uniquely identifies each item; either simple (partition key only) or composite (partition key + sort key)

Partition key (hash key):

DynamoDB uses the partition key to determine which partition stores an item:

Partition = hash(partition_key) mod number_of_partitions

Good partition key design is the most important factor in DynamoDB performance. Keys should:

• Have high cardinality (many distinct values)
• Distribute access evenly across values
• Match your access patterns

Sort key (range key):

Optional second component of a composite primary key. Items with the same partition key are stored together, sorted by sort key:

Table: OrderItems
Partition Key: order_id
Sort Key: item_id

# All items for order stored together, sorted by item_id
# Enables queries like: "Get all items for order 123"

Partitions and scaling:

DynamoDB automatically partitions data based on:

1. Size: Each partition holds up to 10GB
2. Throughput: Each partition handles ~3000 RCU or ~1000 WCU

As data grows, DynamoDB adds partitions. But here's the critical insight: throughput is divided among partitions. If you provision 1000 WCU with 10 partitions, each partition gets ~100 WCU.

The hot partition problem:

If access concentrates on one partition key value (a 'hot key'), that single partition becomes a bottleneck while others sit idle. Classic examples:

• Partition key = date (all today's traffic hits one partition)
• Partition key = tenant_id with one huge tenant
• Partition key = status (most items are 'active')

Understanding DynamoDB's capacity models and secondary indexes is essential for cost optimization and query flexibility.

Capacity modes:

Capacity unit costs:

Read Capacity Unit (RCU):
- 1 strongly consistent read of item up to 4KB per second
- 2 eventually consistent reads of items up to 4KB per second

Write Capacity Unit (WCU):
- 1 write of item up to 1KB per second

Larger items consume more capacity. A 10KB write uses 10 WCUs.

Secondary indexes:

DynamoDB's primary key limitation (only access by partition key or partition+sort key) is addressed with secondary indexes:

Global Secondary Index (GSI):

• New partition key (and optional sort key) from any attribute
• Stored separately from base table (separate capacity)
• Eventually consistent only
• Can project subset of attributes (reduce costs)

Base table: Users
  PK: user_id

GSI: EmailIndex
  PK: email
  
# Now you can query: "Find user by email"

Local Secondary Index (LSI):

• Same partition key as base table, different sort key
• Must be created at table creation
• Shares capacity with base table
• Supports strong consistency

Base table: Orders
  PK: user_id, SK: order_date

LSI: StatusIndex
  PK: user_id, SK: status  
  
# Query: "Find pending orders for user" (same user, different sort)

DynamoDB offers configurable consistency models and multi-region replication—essential features for global applications.

Consistency options:

Eventually Consistent Reads (default):

• Read might not reflect recent writes
• Half the cost of strongly consistent reads
• Lower latency (can read from any replica)
• Suitable for most read workloads

Strongly Consistent Reads:

• Guaranteed to return the most recent write
• Double the capacity cost
• Higher latency (must contact leader)
• Required when correctness depends on freshness

# Eventually consistent (default, cheaper)
response = table.get_item(Key={'user_id': '123'})

# Strongly consistent (guaranteed fresh)
response = table.get_item(
    Key={'user_id': '123'},
    ConsistentRead=True
)

Transactions:

DynamoDB supports ACID transactions across multiple items and tables:

# Atomic transfer between accounts
client.transact_write_items(
    TransactItems=[
        {
            'Update': {
                'TableName': 'Accounts',
                'Key': {'account_id': 'A'},
                'UpdateExpression': 'SET balance = balance - :amt',
                'ExpressionAttributeValues': {':amt': 100}
            }
        },
        {
            'Update': {
                'TableName': 'Accounts',
                'Key': {'account_id': 'B'},
                'UpdateExpression': 'SET balance = balance + :amt',
                'ExpressionAttributeValues': {':amt': 100}
            }
        }
    ]
)

Transactions cost 2x regular operations but provide serializability across up to 100 items.

Global Tables:

For multi-region deployments, DynamoDB Global Tables provide active-active replication:

• Replicas in multiple AWS regions
• Writes to any region, replicated to others
• ~1 second replication latency
• Conflict resolution: Last Writer Wins (by timestamp)

┌─────────────┐     ┌─────────────┐     ┌─────────────┐
│  us-east-1  │◄───►│  eu-west-1  │◄───►│ ap-south-1  │
│   Replica   │     │   Replica   │     │   Replica   │
└─────────────┘     └─────────────┘     └─────────────┘
       ▲                   ▲                   ▲
       │                   │                   │
    Users in            Users in           Users in
    Americas            Europe              Asia

Riak is an open-source distributed key-value store that closely follows the Dynamo paper's architecture. It's designed for high availability, fault tolerance, and operational simplicity—with no single point of failure.

Riak's core principles:

• Masterless: Every node is equal; no leader election, no coordination
• Highly available: Continues operating during network partitions and node failures
• Eventually consistent: Trades consistency for availability and performance
• Operationally simple: Add/remove nodes without downtime or coordination
• Predictable latency: Consistent performance at scale

Ring-based architecture:

Riak distributes data using consistent hashing with a ring structure:

                        Ring (2^160 positions)
                              ┌───┐
                         ┌────┤ 0 ├────┐
                     ┌───┘    └───┘    └───┐
                   Node 3              Node 1
                     │                    │
                  ┌──┴──┐              ┌──┴──┐
                  │     │              │     │
                 ...   ...            ...   ...
                  │     │              │     │
                  └──┬──┘              └──┬──┘
                   Node 2              Node 4
                     └───┐    ┌───┐    ┌───┘
                         └────┤Max├────┘
                              └───┘

Each node owns a portion of the ring. Data is replicated to N consecutive nodes (default N=3).

Tunable consistency:

Riak allows configuring quorum parameters per operation:

• N — Number of replicas (copies of each value)
• R — Number of replicas that must respond to a read
• W — Number of replicas that must acknowledge a write

Common configurations:

Data types:

Riak supports conflict-free replicated data types (CRDTs) that automatically merge concurrent updates:

• Counters: Increment/decrement without conflict
• Sets: Add/remove elements, automatic merge on concurrent updates
• Maps: Nested structures with type-specific merge
• Flags: Boolean with deterministic merge (enable beats disable)
• Registers: Last-write-wins strings

% Increment counter (no read-modify-write needed)
riakc_counter:increment(100, Counter),
UpdateOp = riakc_counter:to_op(Counter),
riakc_pb_socket:update_type(Pid, Bucket, Key, UpdateOp).

CRDTs are powerful for high-concurrency scenarios where traditional locks would be too expensive.

Operating Riak requires understanding its consistency model and failure behavior.

Read repair:

When a read returns data from multiple replicas, Riak compares versions. If replicas have diverged:

1. The most recent/merged value is returned
2. Stale replicas are updated in the background
3. This 'repairs' inconsistency opportunistically

Anti-entropy:

Background processes (active anti-entropy) continuously compare data across replicas using Merkle trees:

1. Build hash tree of all data on each node
2. Compare trees to find divergent ranges
3. Synchronize only divergent data
4. Efficient even with billions of keys

Handling node failures:

Bucket types and properties:

Riak organizes data into buckets with configurable properties:

riak-admin bucket-type create session_store 
    '{"props": {
        "n_val": 3,
        "allow_mult": false,
        "last_write_wins": true,
        "backend": "leveldb_backend"
    }}'

riak-admin bucket-type activate session_store

When to use Riak:

With multiple key-value stores available, choosing the right one depends on your specific requirements.

Decision framework:

                      Need persistence?
                           │
              ┌────────────┴────────────┐
              No                        Yes
              │                         │
         Memcached/Redis         Need strong consistency?
              │                         │
     Need data structures?      ┌───────┴───────┐
              │                 No             Yes
     ┌────────┴────────┐        │               │
     No               Yes    DynamoDB        PostgreSQL
     │                 │     (eventual)     or Spanner
  Memcached         Redis                        │
                                        Need managed service?
                                                │
                                        ┌───────┴───────┐
                                        No             Yes
                                        │               │
                                    Riak/Cassandra  DynamoDB
                                                   (strong)

We've explored DynamoDB and Riak—two approaches to distributed key-value storage that solve different problems. Let's consolidate the key concepts:

What's next:

With our exploration of key-value stores complete—from Redis and Memcached to DynamoDB and Riak—we'll conclude this module with a comprehensive look at use cases and trade-offs. You'll learn how to choose the right key-value store for specific scenarios and understand the fundamental trade-offs in key-value database design.