Skip to main content

Key-Value Stores

Sub-millisecond access with simple get/set semantics and massive scale

TL;DR​

Key-value stores like Redis and DynamoDB provide ultra-fast access with simple get/set/delete operations. Perfect for caching, sessions, real-time leaderboards, and high-throughput scenarios where you don't need complex queries. Trade-off: no complex queries, eventual consistency, typically in-memory (limited by RAM).

Learning Objectives​

  • Understand when key-value access patterns apply
  • Design efficient cache invalidation strategies
  • Recognize distributed KV patterns (sharding, replication)
  • Choose between Redis and DynamoDB for your use case

Motivating Scenario​

Your e-commerce site has 100K concurrent users browsing. Product inventory changes frequently. Reading from PostgreSQL causes 100ms latency. Redis caches hot product data, dropping latency to <1ms. Users see inventory updates within seconds through cache invalidation.

Core Concepts​

Data Structures​

Modern key-value stores support rich data types:

Strings:     get "user:123:name" -> "Alice"
Hashes:      hget "user:123" "email" -> "alice@example.com"
Lists:       lpush "notifications:456" "New message"
Sets:        sadd "users:online" "user:123"
Sorted Sets: zadd "leaderboard" 1000 "user:123"
Streams:     Event log with consumer groups
Bitmaps:     Daily active users tracking
HyperLogLog: Cardinality estimation

Consistency Models​

Redis (In-Memory)
  1. Sub-millisecond latency required
  2. Session storage, caching
  3. Real-time leaderboards
  4. Pub/Sub messaging
  5. Data loss acceptable (cache)
DynamoDB (Managed)
  1. Serverless, fully managed
  2. AWS ecosystem integration
  3. Automatic scaling
  4. Global distribution
  5. Durability guaranteed

Practical Example​

import redis
from datetime import timedelta
import json

# Connect to Redis
r = redis.Redis(host='localhost', port=6379, decode_responses=True)

# Simple caching pattern
def get_user(user_id):
    cache_key = f"user:{user_id}"
    
    # Check cache
    cached = r.get(cache_key)
    if cached:
        return json.loads(cached)
    
    # Cache miss - fetch from database
    user = fetch_from_database(user_id)
    
    # Store in cache with 1 hour TTL
    r.setex(cache_key, timedelta(hours=1), json.dumps(user))
    return user

# Leaderboard using sorted sets
def add_score(user_id, score):
    r.zadd("leaderboard", {f"user:{user_id}": score})

def get_top_10():
    # Get top 10 by descending score
    return r.zrevrange("leaderboard", 0, 9, withscores=True)

# Session storage
def store_session(session_id, user_data, ttl_hours=24):
    r.hset(f"session:{session_id}", mapping=user_data)
    r.expire(f"session:{session_id}", timedelta(hours=ttl_hours))

# Pub/Sub for real-time notifications
def publish_notification(user_id, message):
    r.publish(f"notifications:{user_id}", message)

def subscribe_to_notifications(user_id, callback):
    pubsub = r.pubsub()
    pubsub.subscribe(f"notifications:{user_id}")
    for message in pubsub.listen():
        if message['type'] == 'message':
            callback(message['data'])

When to Use Key-Value Stores / When Not to Use​

Use Key-Value Stores When
  1. Sub-millisecond latency required
  2. Simple get/set/delete access patterns
  3. Session storage, caching needed
  4. Real-time leaderboards, rankings
  5. Rate limiting, throttling
Use RDBMS When
  1. Complex queries with filtering
  2. Multi-table joins needed
  3. Transactional consistency required
  4. Data must be durable by default
  5. Complex reporting

Patterns and Pitfalls​

Design Review Checklist​

  • Access pattern is simple key-based lookup
  • Cache invalidation strategy defined
  • TTL/expiration times appropriate
  • Replication/HA configured (Master-Slave or Sentinel)
  • Memory capacity planned for data growth
  • Eviction policy chosen appropriately
  • Monitoring for hit rate, evictions, memory
  • Backup/persistence strategy documented
  • Connection pooling configured
  • Partition key design prevents hotspots

Self-Check​

  • What's the difference between Redis and DynamoDB?
  • How do you prevent cache stampede?
  • Why should you use hashes in Redis instead of separate string keys?
  • What consistency guarantees does your key-value store provide?
info

Key-value stores excel at simple lookups and caching, trading away complex queries for sub-millisecond latency. Use them as a caching layer in front of RDBMS, never as your primary data store for critical data.

Advanced Key-Value Patterns​

Cache Invalidation Strategies​

# Cache-Aside (most common): App checks cache, on miss loads from DB
def get_user(user_id):
    cache_key = f"user:{user_id}"

    # Check cache first
    user = cache.get(cache_key)
    if user:
        return user

    # Cache miss: load from database
    user = database.get_user(user_id)

    # Store in cache with TTL
    cache.setex(cache_key, 3600, json.dumps(user))
    return user

# Write-Through: Update cache and DB together
def update_user(user_id, updates):
    cache_key = f"user:{user_id}"

    # Update database first
    user = database.update_user(user_id, updates)

    # Update cache (if update succeeded)
    cache.setex(cache_key, 3600, json.dumps(user))
    return user

# Write-Behind (write-back): Write to cache, async to DB
def update_user_async(user_id, updates):
    cache_key = f"user:{user_id}"

    # Update cache immediately (fast response)
    cache.setex(cache_key, 3600, json.dumps(updates))

    # Queue async write to database
    async_queue.put(('update_user', user_id, updates))

    return {'status': 'pending'}

# Pros/Cons:
# Cache-Aside: Simple, but risk of stale reads
# Write-Through: Always consistent, slower writes
# Write-Behind: Fast, but risk of data loss if cache crashes

Distributed Caching with Redis Cluster​

# Redis Cluster handles sharding and replication
import redis

# Single node (for development)
r_single = redis.Redis(host='localhost', port=6379)

# Redis Cluster (for production)
r_cluster = redis.RedisCluster(
    startup_nodes=[
        {"host": "node1", "port": 6379},
        {"host": "node2", "port": 6379},
        {"host": "node3", "port": 6379},
    ],
    decode_responses=True,
    skip_full_coverage_check=True
)

# Consistent hashing automatically distributes keys
# Same key always goes to same node
for user_id in range(1000000):
    key = f"user:{user_id}"
    r_cluster.set(key, json.dumps({'id': user_id}))

# Rebalancing happens automatically when nodes added/removed
# Data is automatically replicated to replica nodes
# If a node fails, replicas take over automatically

Rate Limiting with Redis​

# Token bucket algorithm for rate limiting
class RateLimiter:
    def __init__(self, redis_client, max_requests=100, window_seconds=60):
        self.redis = redis_client
        self.max_requests = max_requests
        self.window_seconds = window_seconds

    def is_allowed(self, user_id: str) -> bool:
        key = f"rate_limit:{user_id}"

        # Increment counter
        current = self.redis.incr(key)

        # Set expiration on first request in window
        if current == 1:
            self.redis.expire(key, self.window_seconds)

        # Check if over limit
        return current <= self.max_requests

    def get_remaining(self, user_id: str) -> int:
        key = f"rate_limit:{user_id}"
        current = self.redis.get(key) or 0
        return max(0, self.max_requests - int(current))

# Usage in middleware
def rate_limit_middleware(request):
    limiter = RateLimiter(redis_client)
    user_id = request.user.id

    if not limiter.is_allowed(user_id):
        remaining = limiter.get_remaining(user_id)
        return Response(
            status=429,
            headers={
                'Retry-After': str(limiter.window_seconds),
                'X-RateLimit-Remaining': str(remaining)
            }
        )
    return request

Distributed Locks with Redis​

# Mutex pattern for critical sections
import uuid
import time

class DistributedLock:
    def __init__(self, redis_client, resource: str, timeout_seconds=30):
        self.redis = redis_client
        self.resource = resource
        self.timeout = timeout_seconds
        self.lock_id = str(uuid.uuid4())

    def acquire(self, blocking=True) -> bool:
        key = f"lock:{self.resource}"

        # Try to set key (NX = only if not exists)
        acquired = self.redis.set(
            key,
            self.lock_id,
            ex=self.timeout,  # Expiration prevents deadlock
            nx=True  # Only set if doesn't exist
        )

        if acquired or not blocking:
            return bool(acquired)

        # Wait for lock (blocking)
        deadline = time.time() + 10
        while time.time() < deadline:
            acquired = self.redis.set(key, self.lock_id, ex=self.timeout, nx=True)
            if acquired:
                return True
            time.sleep(0.1)

        return False

    def release(self):
        key = f"lock:{self.resource}"

        # Only release if we own it (prevent releasing others' locks)
        current = self.redis.get(key)
        if current == self.lock_id:
            self.redis.delete(key)

    def __enter__(self):
        self.acquire()
        return self

    def __exit__(self, *args):
        self.release()

# Usage
with DistributedLock(redis, "checkout_inventory") as lock:
    # Critical section: only one process can execute this at a time
    inventory = db.get_inventory(product_id)
    if inventory > 0:
        db.update_inventory(product_id, inventory - 1)

Comparison: When to Use Each​

Use Redis When:
- Sub-millisecond latency required
- Bounded dataset (fits in memory)
- Session storage
- Real-time leaderboards
- Pub/Sub messaging
- Rate limiting

Use DynamoDB When:
- Serverless/managed preference
- Unbounded data size
- AWS ecosystem integration
- Multi-region replication needed
- Compliance requirements (fully audited)
- Pay-per-request pricing works for workload

Use Memcached When:
- Simple key-value (no data structures)
- Horizontal scaling is priority
- Extremely high throughput needed
- Simpler operations than Redis

Use Application Memory When:
- Single-instance application
- Data fits in process memory
- No need for distributed access
- Testing/development only

Next Steps​

  • Explore Caching Patterns for strategies like cache-aside, write-through
  • Learn In-Memory Caches and Data Grids for Memcached and Hazelcast
  • Study Read Replicas for scaling beyond single instance
  • Dive into Sharding Strategies for partitioning across nodes
  • Implement Cache Warming for predictable workloads
  • Design Eviction Policies for memory-constrained environments

References​

  • Redis Official Documentation (redis.io)
  • "Designing Data-Intensive Applications" by Martin Kleppmann
  • AWS DynamoDB Design Patterns (docs.aws.amazon.com)
  • "The Art of Multiprocessor Programming" by Herlihy & Shavit
  • Redis Cluster Tutorial: https://redis.io/topics/cluster-tutorial