Key-Value Stores
The associative store, generalised
A key-value store generalises the associative array (dictionary) from Lecture 1: values are blobs (arbitrary sequences of bytes), not just strings. Any structure inside the blob is opaque to the key-value store — it is the application’s concern, not the DBMS’s.
Store: key ──→ blob
string bytes (opaque)Opaqueness implies the DBMS knows nothing about what is stored. It would not mind if values were encrypted and it never saw the encryption keys. This is both a strength (simplicity, security) and a limitation (no querying within values, no secondary indices without application effort).
Distribution
Many key-value store implementations are distributed: data is spread over all participating machines as shards. The typical mechanism:
- Hash the key to produce a shard identifier.
- Route the read/write to the machine responsible for that shard.
This provides:
| Benefit | Mechanism |
|---|---|
| Load balancing | Hash distributes keys uniformly across shards |
| Redundancy | Each shard may be replicated across multiple machines for durability |
| Scalability | Adding machines increases total capacity; rebalancing redistributes shards |
ACID vs. BASE semantics
Implementations can range between full ACID guarantees and relaxed BASE semantics:
| Property | ACID (traditional RDBMS) | BASE (many K/V stores) |
|---|---|---|
| Atomicity | Full rollback on failure | Best-effort; partial writes possible |
| Consistency | Invariants enforced by DBMS | Application-level, eventual |
| Isolation | Serializable transactions | Often none or read-committed |
| Durability | Write-ahead log, fsync | Replication to N nodes; quorum writes |
A note on redundancy
It is important to distinguish two kinds of redundancy:
| Kind | Meaning |
|---|---|
| Physical redundancy | Multiple copies of the same data for durability (replication across machines) |
| Schema redundancy | The same data stored in multiple places within the logical model (denormalisation) |
Key-value stores provide physical redundancy through replication. Schema redundancy is an application-level choice — the store itself cannot help with or prevent denormalisation, since the blob contents are opaque.
Use cases
- Caching (e.g., Redis, Memcached): fast in-memory lookups with optional persistence.
- Session stores: web session data keyed by session ID.
- Configuration stores: distributed configuration that must be available across a fleet.
- Shopping carts: per-user carts that tolerate eventual consistency.
Summary
- A key-value store maps string keys to opaque blobs.
- Distribution provides load balancing, redundancy, and scalability via hashed sharding.
- ACID vs. BASE is a spectrum; different stores choose different points.
- Physical redundancy (replication) is distinct from schema redundancy (denormalisation).