# Exercise 2: Consistent Hashing by Hand, Then Redis Cluster Slots

Work these by hand (a calculator is fine), then optionally verify with code.

## Part A — A Tiny Ring

Use a ring of size 100 (positions 0–99). A key belongs to the first node position **≥** the key's position, wrapping from 99 back to 0.

Nodes (one point each, no vnodes yet):

| Node | Position |
|---|---|
| A | 10 |
| B | 45 |
| C | 80 |

Keys and their hash positions:

| Key | Pos | Key | Pos |
|---|---|---|---|
| k1 | 3 | k6 | 50 |
| k2 | 12 | k7 | 66 |
| k3 | 27 | k8 | 79 |
| k4 | 44 | k9 | 81 |
| k5 | 46 | k10 | 97 |

1. Assign every key to a node. How many keys does each node own?
2. Node **D joins at position 60**. Which keys move, and from which node to which?
3. Instead, node **B fails** (from the original 3-node ring). Which keys move, and where?
4. Repeat question 2 using **modulo hashing** with `node = pos % N` (A=0, B=1, C=2 for N=3; add D=3 for N=4). How many of the 10 keys change owner? Compare with your answer to question 2.
5. In question 3, all of B's keys landed on a single node. Explain how **virtual nodes** change that, and why it matters for a cache under load.

## Part B — Redis Cluster

A 3-primary Redis Cluster splits the 16,384 slots evenly:

| Primary | Slots |
|---|---|
| P1 | 0 – 5460 |
| P2 | 5461 – 10922 |
| P3 | 10923 – 16383 |

Given these computed slots (`CRC16(hashed part) mod 16384`):

| Hashed string | Slot |
|---|---|
| `user:42:cart` | 3101 |
| `user:42:profile` | 12950 |
| `42` | 8000 |

6. Which primary owns `user:42:cart` and which owns `user:42:profile`? What happens if the app runs `MGET user:42:cart user:42:profile`?
7. Rename the keys with a **hash tag** so both always live together. What exact key names do you use, and which primary owns them now?
8. Why would tagging *every* key in the app as `{app}:...` be a disaster?
9. A client sends `GET user:{42}:cart` to P1. Write the reply P1 sends, and describe what a smart client does next.
10. While slots are being migrated from P2 to a new P4, a client gets an `ASK` reply instead of `MOVED`. What's the difference, and why must the client *not* update its slot map on `ASK`?

## Requirements Checklist

- [ ] Q1: A owns {k1, k2?…} — every key assigned with the clockwise rule, including the wrap-around for k10 (97 → A at 10).
- [ ] Q2: only keys in the arc (45, 60] — k6 (50) — move, from C to D. Everything else stays.
- [ ] Q3: B's keys (positions 11–45: k2, k3, k4) all move to C; nothing else moves.
- [ ] Q4: modulo hashing changes the owner of a large fraction of the 10 keys (count them), versus 1 key with the ring.
- [ ] Q5: vnodes scatter a failed node's arcs across many successors, spreading both data and the miss storm.
- [ ] Q6/Q7: identifies the `CROSSSLOT` error, then uses names like `user:{42}:cart` / `user:{42}:profile`, both hashing `42` → slot 8000 → P2.
- [ ] Q8: one tag for everything puts every key in one slot on one node — no distribution at all.
- [ ] Q9: `-MOVED 8000 <P2 host:port>`; the client retries on P2 and updates its cached slot map.
- [ ] Q10: `ASK` is a one-time redirect during migration (send `ASKING` then the command to the target); the slot still officially belongs to the source until migration finishes.