Key-Value Stores

---

The key-value store is the simplest database model there is — and one of the most used: almost every larger web application has one, usually as a cache or session store. This scriptum answers:

1. How does a key-value store work?
2. Redis or Valkey — what happened there?
3. Which data types and commands are the most important?
4. How consistent and how scalable is it?
5. How do we classify it?

---

1. The idea: one big hash table

---

• Every entry is a pair: key → value.
• The key is a string, unique in the whole database.
• The value is (for the database) a black box — it cannot search inside it.
• Only three basic operations: SET key value, GET key, DEL key.
• Lookup by key is O(1) — no matter if there are 10 or 10 million keys.
• Usually kept in RAM → answers in well under a millisecond.

---

The price of this speed: you can only find data by its key. “Give me all carts that contain a Mouse” is impossible without reading every cart.

---

2. Redis or Valkey?

Redis (2009) was the open-source key-value store for 15 years. Then:

When	What happened
March 2024	Redis Ltd. changes the licence from open-source BSD to source-available licences (RSALv2/SSPL), starting with Redis 7.4. Cloud providers may no longer offer it freely.
days later	The Linux Foundation forks the last open version (7.2.4) as Valkey — backed by AWS, Google, Oracle and others. BSD licence.
May 2025	Redis 8 adds the AGPLv3 — open source again, but with strict obligations.
2025/26	Many Linux distributions (Fedora, Ubuntu, Arch) ship Valkey by default; all big clouds offer managed Valkey.

---

What this means for you:

• Valkey and Redis speak the same protocol and the same commands. Everything in this scriptum works on both.
• redis-cli can talk to Valkey and valkey-cli to Redis; most client libraries (e.g. StackExchange.Redis for C#) work with both.
• We use Valkey in class: BSD licence, no strings attached.

The same story happened before: MongoDB switched to the SSPL licence in 2018, Elasticsearch in 2021 (→ fork OpenSearch). Licences matter when you build a product on top of a database.

---

3. Data types and commands

Valkey is more than “string → string”. The value can have one of several types:

Type	Think of it as	Important commands	Typical use
String	a single value (text, number, binary)	SET, GET, INCR, DECR	cache entries, counters
Hash	a small object: field → value	HSET, HGET, HGETALL, HINCRBY, HDEL	shopping cart, user profile
List	ordered list (queue)	LPUSH, RPUSH, LPOP, LRANGE, LTRIM	”last viewed products”, job queues
Set	unordered, no duplicates	SADD, SMEMBERS, SISMEMBER, SINTER	tags, “who liked this”
Sorted set	set with a score, sorted by score	ZADD, ZINCRBY, ZREVRANGE	leaderboards, top-10 products

---

3.1 Expiry: TTL

Every key can get a time to live. When it expires, the key deletes itself.

SET session:8f3a "user:42" EX 1800    # lives for 30 minutes
TTL session:8f3a                      # → 1799 (seconds left)
EXPIRE cart:anna 86400                # cart disappears after one day

This is why key-value stores are the standard for sessions and caches.

---

3.2 Key design

Because keys are the only way to find data, their names are your “schema”. Convention: object-type:id :field, separated by colons.

user:42                → hash with name, email, …
user:42:cart           → hash productId → quantity
product:7:views        → counter
session:8f3a           → string with TTL
top:products           → sorted set

Designing keys and values for real use cases is a topic of its own — we will come back to it in a later block.

---

4. Consistency and durability

4.1 Every command is atomic

Valkey executes commands one after another (single-threaded command execution). So INCR can never produce a lost update — remember the stock problem from Exercise_Transactions_Isolation:

Client A: INCR likes:post:7   → 1204
Client B: INCR likes:post:7   → 1205    ✓ no update lost

For several commands as one unit there is MULTI … EXEC (all commands run together, nothing in between — but no rollback if one of them fails).

---

4.2 RAM is volatile — persistence

Mode	How it works	Risk
none	pure cache	everything lost on restart
RDB snapshots	the whole dataset is written to disk every few minutes	changes since the last snapshot are lost on a crash
AOF (append-only file)	every write command is appended to a log file	slower; with fsync every second at most ~1 s is lost

Durability (“D” in ACID) is therefore configurable — and by default weaker than in MySQL.

---

4.3 CAP

• Replication primary → replicas is asynchronous: a confirmed write can be lost if the primary crashes before replicating. Reads from replicas can be stale.
• → Valkey/Redis behave AP-like (availability and speed first).
• Exception: etcd (the key-value store behind Kubernetes) uses the Raft consensus protocol and is strictly CP.
• DynamoDB (Amazon) lets you choose per read: eventually consistent or strongly consistent.

---

5. Scaling: hash the key

• Cluster mode splits the key space into 16 384 hash slots: slot = CRC16(key) mod 16384.
• Every node is responsible for a range of slots → every key lives on exactly one node (Z-axis, sharding).
• Add a node → move some slots to it.
• Because every request only touches one key, there is no cross-node JOIN — scaling out is easy.

---

6. Classification: key-value stores

Criterion	Key-value
Data model	key → value (value opaque; in Valkey: string, hash, list, set, sorted set)
Schema	none — the key naming convention is the “schema”
Query language	simple commands (GET, SET, …), access only by key
Relationships	none — at most a key name stored inside a value
Transactions	each command atomic; MULTI/EXEC without rollback
CAP (default)	AP (async replication); etcd is CP
Scaling	horizontal by hashing keys (hash slots)
Strengths	extremely fast (RAM, O(1)), simple, TTL, atomic counters
Weaknesses	no queries by value, no relationships, data size limited by RAM, weaker durability
Typical use	cache, sessions, shopping carts, counters, rate limiting, leaderboards, queues
Examples	Valkey, Redis, Memcached, DynamoDB, etcd

---

7. Summary

• A key-value store is a giant hash table: lightning-fast access by key, nothing else.
• Valkey is the BSD-licensed fork of Redis; both use the same commands.
• Values can be strings, hashes, lists, sets and sorted sets; every key can have a TTL.
• Every command is atomic (single-threaded execution); durability depends on RDB/AOF.
• Default behaviour is AP; scaling out works by hashing the key to a slot.

---

8. Self-check questions

1. Why is a lookup in a key-value store O(1)?
2. Why can’t a key-value store answer “all carts containing product 7”?
3. What is Valkey, and why does it exist?
4. Which data type would you use for (a) a shopping cart, (b) a top-10 product list, (c) the last 5 viewed products?
5. What happens to a key with EX 60 after one minute?
6. Why is INCR safe against lost updates?
7. Your server crashes. Which data is lost with RDB snapshots, which with AOF (fsync every second)?
8. Why are Valkey/Redis classified as AP?
9. How does Valkey cluster decide on which node a key is stored?
10. Name three typical use cases for a key-value store.

---

Short answers

1. The key is hashed directly to its storage position — no searching through other entries.
2. The values are black boxes and can only be found by their key; the store would have to read every single cart.
3. A fork of Redis 7.2.4 by the Linux Foundation, created in 2024 after Redis left its open-source BSD licence. Valkey stays BSD-licensed.
4. (a) hash, (b) sorted set, (c) list (LPUSH + LTRIM).
5. It is deleted automatically.
6. Commands run one after another, so read-increment-write happens inside the server as one step.
7. RDB: everything since the last snapshot (minutes). AOF: at most about one second.
8. Replication is asynchronous: the primary answers immediately, replicas may be behind and a confirmed write can be lost on failover.
9. CRC16(key) mod 16384 gives the hash slot; each node owns a range of slots.
10. e.g. sessions, caching, counters, shopping carts, leaderboards, rate limiting.