Cluster — 16384 slots and the client routes

Scene 08 · Cluster — 16384 slots and the client routes

CRC16 mod 16384, MOVED vs ASK (permanent vs transient), hash tags, configEpoch — and why sharding alone is not HA.

Previously

Sentinel buys availability with a single master. But you still only have one master's worth of write throughput. Cluster splits the keyspace across multiple masters — and pushes the routing logic into the client.

Scene 08

Cluster — 16384 slots and the client routes

Watch

Diagram

Three master nodes across the top, each owning a slot range from the 16384-slot space. A client at the bottom hashes a key (CRC16 mod 16384), routes to what it thinks is the slot's owner, and gets back either a hit, a MOVED redirect (slot moved permanently — update your cached map) or an ASK redirect (in-flight migration — try the other node just for this query, do not update the map).

Sources

The slot bar across the top is colored by owning master. The client holds a cached copy of that map. Watch a few queries hash to slots and land on the right master in one round trip.

Implementation

Client.send # MOVED handling

permanent cache heal on -MOVED

1def send(cmd, key):
2    slot = hashSlot(key)
3    node = cachedMap[slot]            # client-side route
4    resp = node.exec(cmd)
5    if resp is -MOVED(slot, newOwner):
6        cachedMap[slot] = newOwner    # heal permanently
7        return newOwner.exec(cmd)     # retry once
8    return resp

Client.send # ASK handling

transient redirect — cache is NOT updated

1def send(cmd, key):
2    slot = hashSlot(key)
3    node = cachedMap[slot]
4    resp = node.exec(cmd)
5    if resp is -ASK(slot, target):
6        # one-shot: prefix ASKING, route to target
7        target.exec(ASKING)            # ONCE
8        return target.exec(cmd)
9        # cachedMap[slot] is left UNCHANGED
10    return resp

hashSlot # CRC16 with hash tag

{tag} forces multi-key commands to one slot

1def hashSlot(key):
2    lo = key.find('{')
3    if lo != -1:
4        hi = key.find('}', lo + 1)
5        if hi > lo + 1:
6            key = key[lo + 1 : hi]   # hash only the tag
7    return crc16(key) % 16384

Master.handleQuery # slot ownership check

MIGRATING → -ASK; not-mine → -MOVED

1def handleQuery(cmd, key):
2    slot = hashSlot(key)
3    if slot not in myOwnedSlots:
4        return -MOVED(slot, owners[slot])
5    if slot in MIGRATING and key not local:
6        return -ASK(slot, migrating[slot].target)
7    if slot in IMPORTING and not asking_flag:
8        return -MOVED(slot, owners[slot])
9    return execute(cmd, key)

PreviousSentinel — quorum detects, majority elects NextDesign your Redis deployment