Chapter 10 · Key-Value Databases and Data-Structure Stores
Use Cases: Sessions, Caches, Feature State, Rate Limits, Idempotency, and Coordination
Apply key-value primitives to sessions, feature state, rate limiting, idempotency, and lightweight coordination, identifying exactly where stronger durability, auditing, CAS, or fencing is required.
Learning outcomes
AtlasMart now has several tempting “small-state” problems: web sessions, a checkout feature flag, API rate limits, payment idempotency, and a background worker lease. They all fit in key-value records, but they do not have identical correctness requirements. This lesson builds a per-use-case contract before choosing a primitive.
Model sessions, cache entries, feature state, rate limits, idempotency records, and coordination leases with explicit atomicity and expiry requirements.
Use token-bucket and deduplication state to show where single-key atomic transitions are sufficient.
Explain why idempotency needs a stable request identity and retained result/decision—not merely a short lock.
Produce a stale-owner double action when using a lease without fencing and reject it with a monotonically increasing fencing token.
Identify which use cases require stronger durability, auditing, multi-key invariants, or external authorization than a simple key-value primitive supplies.
The mandatory labs use Python 3.13+ standard library only in one deterministic process with a logical clock; there is no database server, client driver, container, cloud account, network fault injection, or paid feature. Optional implementation references were rechecked against Redis Open Source 8.10.0 (GA July 2026; Redis 8+ is offered under the user's choice of AGPLv3, RSALv2, or SSPLv1) and Valkey 9.1.1 (released 21 July 2026; predominantly BSD-3-Clause). Product commands/defaults are examples only; later Stage 03 product courses teach product-specific operations in depth.
1. Sessions: expiration is product behavior
A session record typically needs a strong random identifier, user/tenant identity, authorization context, creation/last-activity time, and expiry. Decide whether session loss is tolerable, whether logout/revocation must be immediate, whether TTL slides on activity, and whether failover can expose an old authorization snapshot. Sensitive session values require encryption in transit, least-privilege access, and careful logging.
2. Feature state: simple reads, but changes may require governance
A boolean feature flag looks trivial, yet high-impact flags need versioning, actor/time audit, staged rollout dimensions, rollback, and sometimes strongly ordered writes. A local cached copy may be intentionally stale for seconds while a payment-kill switch may require tighter propagation. “Store it in a key-value database” does not answer the governance or freshness requirement.
3. Rate limits: atomic accounting at the chosen scope
A token bucket has capacity, current tokens, refill rate, and last-update time. The consume/refill transition must be atomic at the rate-limit scope. If traffic for one user is routed to independent counters on multiple nodes without coordination/merge semantics, each node can admit up to the full limit. Decide whether the limit is exact, approximate, regional, or global and how failover/retry affects the count.
4. Idempotency: same request identity, same effect/result
An idempotency record maps a stable request identifier to processing state/result for a defined retention window. A duplicate request should discover the original outcome instead of repeating the side effect. The key must be scoped to the caller/operation, inputs may need a fingerprint to reject accidental reuse with different payloads, and the record must live long enough to cover plausible retries.
A “set if absent” claim is only the beginning. Crash after the side effect but before recording success creates ambiguity unless the side effect and idempotency decision share an atomic boundary or reconciliation protocol.
5. Coordination: a lease without fencing can corrupt state
A distributed lease says an owner may act until expiry/renewal conditions fail. A paused owner can resume after its lease expired while a new owner has already acquired the resource. If the downstream storage accepts both, two owners act. A fencing token is a monotonically increasing generation number attached to operations; the resource rejects tokens older than the highest it has accepted. This turns stale ownership into a verifiable downstream rejection rather than trusting the old process to behave.
Simple key-value locks are not substitutes for consensus, transactions, or fencing when the protected resource cannot detect stale owners. Chapter 17 returns to consensus; Chapter 08 already established fencing/epoch reasoning.
6. AtlasMart lab: five use cases, five contracts
The lab uses a logical TTL session, versioned feature state, token bucket, idempotency registry, and a coordination example. The unsafe lease path performs a duplicate shipment; the fenced resource accepts generation 42 and rejects stale generation 41.
from dataclasses import dataclass
class LogicalTTL:
def __init__(self): self.now=0; self.items={}
def tick(self,n=1): self.now += n
def put(self,key,value,ttl): self.items[key]=(value,self.now+ttl)
def get(self,key):
item=self.items.get(key)
if not item or self.now >= item[1]: return None
return item[0]
class TokenBucket:
def __init__(self, capacity, refill_per_tick):
self.capacity=capacity; self.tokens=capacity; self.refill=refill_per_tick; self.last=0
def allow(self, now, cost=1):
elapsed=max(0,now-self.last)
self.tokens=min(self.capacity,self.tokens+elapsed*self.refill); self.last=now
if self.tokens < cost: return False
self.tokens -= cost; return True
class IdempotencyRegistry:
def __init__(self): self.results={}; self.charge_count=0
def charge(self, request_id, amount):
if request_id in self.results:
return "replay", self.results[request_id]
self.charge_count += 1
result={"charge_id":f"ch-{self.charge_count:03d}","amount":amount}
self.results[request_id]=result
return "created", result
@dataclass
class Lease:
owner: str
token: int
class FencedResource:
def __init__(self): self.last_token=0; self.value=[]
def write(self, token, payload):
if token < self.last_token:
return False
self.last_token=token; self.value.append((token,payload)); return True
print("SESSION WITH TTL")
sessions=LogicalTTL(); sessions.put("session:s1", {"user":"u42"}, ttl=3)
print("t0", sessions.get("session:s1")); sessions.tick(4); print("t4", sessions.get("session:s1"))
print("\nFEATURE STATE NEEDS VERSION/AUDIT WHEN CONSEQUENCES MATTER")
feature={"checkout-v2":{"enabled":False,"version":7}}
expected=7
if feature["checkout-v2"]["version"]==expected:
feature["checkout-v2"]={"enabled":True,"version":8}
print("feature", feature["checkout-v2"])
print("\nTOKEN BUCKET RATE LIMIT")
b=TokenBucket(capacity=3, refill_per_tick=1)
for t in [0,0,0,0,1,1,2]:
print("t",t,"allow",b.allow(t),"tokens",b.tokens)
print("\nIDEMPOTENCY RECORD")
idem=IdempotencyRegistry()
print(idem.charge("req-777", 50))
print(idem.charge("req-777", 50))
print("physical charges", idem.charge_count)
print("\nCOORDINATION: LOCK WITHOUT FENCING IS UNSAFE")
resource=[]
old_owner="worker-A"; new_owner="worker-B"
# A pauses; lease expires; B acquires and writes; then stale A resumes.
resource.append((new_owner,"ship order"))
resource.append((old_owner,"ship order AGAIN"))
print("without fencing", resource)
print("\nFENCING REJECTS STALE OWNER")
f=FencedResource()
lease_a=Lease("worker-A", 41)
lease_b=Lease("worker-B", 42)
print("B write", f.write(lease_b.token, "ship order"))
print("stale A write", f.write(lease_a.token, "ship order AGAIN"))
print("resource history", f.value)
SESSION WITH TTL
t0 {'user': 'u42'}
t4 None
FEATURE STATE NEEDS VERSION/AUDIT WHEN CONSEQUENCES MATTER
feature {'enabled': True, 'version': 8}
TOKEN BUCKET RATE LIMIT
t 0 allow True tokens 2
t 0 allow True tokens 1
t 0 allow True tokens 0
t 0 allow False tokens 0
t 1 allow True tokens 0
t 1 allow False tokens 0
t 2 allow True tokens 0
IDEMPOTENCY RECORD
('created', {'charge_id': 'ch-001', 'amount': 50})
('replay', {'charge_id': 'ch-001', 'amount': 50})
physical charges 1
COORDINATION: LOCK WITHOUT FENCING IS UNSAFE
without fencing [('worker-B', 'ship order'), ('worker-A', 'ship order AGAIN')]
FENCING REJECTS STALE OWNER
B write True
stale A write False
resource history [(42, 'ship order')]
| Use case | Atomicity / expiry | Where simple KV becomes unsafe |
|---|---|---|
| Session | Single session record; TTL/revocation | Authorization freshness, cross-region failover, secret leakage, or state that cannot be reconstructed. |
| Feature state | Versioned update; optional local cache TTL | High-impact changes need audit, ordered rollout, rollback, or strict propagation. |
| Rate limit | Atomic bucket/window update | Multiple independent counters over-admit a supposedly global limit. |
| Idempotency | Conditional claim + durable result window | Side effect commits but result record does not; payload reused under same key. |
| Coordination | Lease/CAS plus generation | Paused stale owner can act unless downstream resource enforces fencing. |
Check your understanding
- Why should an idempotency record often store the result?
- Why can a global rate limit be violated by per-node counters?
- What does fencing add beyond a lease?
- Can session TTL alone implement logout?
- What is the chapter-wide rule for choosing a KV pattern?
Review the answers
1. A retry can return the original outcome and avoid repeating a side effect; a bare lock does not explain whether the original request committed.
2. Each node may independently admit its full allowance unless counters share atomic/merge semantics at the intended scope.
3. A monotonically increasing token that the protected resource can use to reject operations from stale owners.
4. Not necessarily. Immediate revocation may require deleting/versioning the session or checking an authoritative revocation state rather than waiting for TTL.
5. Start from identity, atomicity, expiry, durability, consistency, recovery, audit, and failure requirements; then select the smallest primitive that actually satisfies them.
7. Chapter synthesis and production decision record
Chapter 10 began with the key as an address/routing/atomicity contract, then moved through value representations and server-side operations, ephemeral lifetime semantics, authority/recovery boundaries, and finally common application patterns. The unifying principle is small API does not mean small correctness problem. Key-value systems are powerful when the invariant fits their atomic boundary and the loss/recovery contract is explicit.
| Production dimension | Questions to record before using the pattern |
|---|---|
| Correctness / atomicity | What is the atomic boundary: one key, one structure, one shard, one transaction, or a broader invariant? Which races remain possible around reads, retries, expiration, failover, and multiple keys? |
| Consistency / topology | Which node owns or coordinates the key, how are replicas acknowledged, what stale reads are allowed, and what changes during partition/failover? |
| Durability / recovery | Is the state disposable, reconstructable, or authoritative? What persistence, replication, backup, restore, and reconciliation evidence supports that claim? |
| Latency / hot keys | Measure p50/p95/p99, queueing, value size, key distribution, per-key operation rate, serialization cost, fan-in/fan-out, and hot-key concentration. |
| TTL / memory | Differentiate logical expiration from physical reclamation and memory-pressure eviction. Define refresh rules, jitter, capacity headroom, and acceptable disappearance. |
| Security / tenancy | Namespace tenant data, authorize keys/operations, protect secrets, prevent cross-tenant scans/collisions, limit abusive large values/structures, and audit privileged coordination actions. |
| Operations / testing | Test ambiguous retries, duplicate requests, eviction, restart, replica lag, failover, clock shifts where relevant, hot keys, schema evolution, restore, and cache rebuild. |
| Version / license / cost | Pin product/client versions when used; verify license/edition/feature status; price memory, replicas, persistence I/O, network egress, backup retention, and operational skill. |
Bridge to Chapter 11: The next chapter treats document databases as aggregate-oriented stores, where nested objects and arrays move more related state behind one document boundary but introduce new size, indexing, growth, embedding/reference, and schema-evolution tradeoffs.
Authoritative references
- Redis data types — current implementation examples for sessions/counters/sets/sorted sets/streams
- Redis transactions / WATCH — optimistic conditional-update example
- Redis keyspace / expiration — TTL and key naming example
- Redis sorted sets — current example including rate-limiter use cases
- Redis licenses — current Redis Open Source license options
- Valkey releases — current alternative implementation release reference