jonnifyechomq
EchoMQ / The Protocol / The owned keyspace / The hashtag & the slot

The owned keyspace · dive 02 · the slot

The hashtag & the slot

The brace is the routing key. The slot is one CRC16, computed before the wire is touched.

The braces in emq:{q}:<type> are the cluster hashtag. A Valkey cluster routes a key by a CRC16 of the substring inside its first {...} — so every key that shares a hashtag shares a slot. EchoMQ.Keyspace computes that slot client-side, with the cluster specification's exact algorithm: CRC16-XMODEM over the hashtag, modulo 16384, pinned by the vector slot("123456789") == 12739.

Why one slot matters hashtag/1 slot/1 & the CRC16 Compute a slot Pattern → implementation References

16384 slots · one queue lands on one

0 4096 8192 12288 105 {orders}

Why one slot matters

A Valkey cluster splits the keyspace into 16384 slots and assigns each slot to a shard. It routes a key by a CRC16 of the substring inside its first {...} — not the whole key. So every key that shares a hashtag is guaranteed to live on the same shard. By wrapping the queue name in braces, EchoMQ makes one queue's keys all co-resident: emq:{orders}:pending, emq:{orders}:active, and emq:{orders}:job:<id> all hash on orders, so they land together.

That co-residence is the precondition for the protocol's atomic transitions. A Lua script that moves a job from pending to active — deleting from one set, adding to another, updating the row — must touch keys that are all on one shard, or the cluster refuses it. The hashtag is what guarantees that. Without the brace, three keys of one queue could scatter across three shards and no single atomic script could span them.

hashtag/1 — the substring inside the first braces

The slot is computed over the hashtag, so the first job is to extract it. hashtag/1 returns the substring inside the first {...}, and falls back to the whole key when the braces are absent or empty — that fallback is the cluster rule, not a convenience.

# echo_mq — EchoMQ.Keyspace
# The hashtag is the substring inside the first {...}. When the braces are
# absent, or empty, the whole key is hashed — the cluster rule. For an
# EchoMQ key the tag is always the queue name (emq:{orders}:* -> "orders").
def hashtag(key) do
  with [_, rest] <- :binary.split(key, "{"),
       [tag, _] when tag != "" <- :binary.split(rest, "}") do
    tag
  else
    _ -> key
  end
end

For any EchoMQ key the tag is always the queue name, because the grammar puts the queue — and only the queue — inside the braces. So hashtag("emq:{orders}:pending") is "orders", and computing the slot of the full key gives exactly the same answer as computing it of the bare queue name. The brace is the routing key; the rest of the string does not move it.

slot/1 — CRC16-XMODEM, modulo 16384

slot/1 is the hashtag fed through CRC16-XMODEM, modulo 16384. It is computed client-side so the connector can route and partition without a server round trip — the slot of a key is knowable before the key is ever sent.

# echo_mq — EchoMQ.Keyspace
# The cluster slot, computed client-side so the connector routes without a
# server round trip. CRC16-XMODEM over the hashtag (not the whole key),
# modulo 16384 — the cluster specification's algorithm. Known vector:
# slot("123456789") == 12739 (CRC16 0x31C3).
def slot(key) when is_binary(key), do: rem(crc16(hashtag(key), 0), 16384)

The CRC16 itself is the standard cluster variant — polynomial 0x1021, initial value 0, no reflection. One byte at a time: XOR the byte into the high half of the running value, then eight rounds of shift-and-conditional-XOR, masked to 16 bits.

# echo_mq — EchoMQ.Keyspace
# CRC16-XMODEM: poly 0x1021, init 0, no reflection. XOR the byte into the
# high half, then eight shift-and-conditional-XOR rounds, masked to 16 bits.
defp crc16(<<>>, crc), do: crc

defp crc16(<<b, rest::binary>>, crc) do
  crc = Bitwise.band(Bitwise.bxor(crc, Bitwise.bsl(b, 8)), 0xFFFF)

  crc =
    Enum.reduce(1..8, crc, fn _, c ->
      shifted = Bitwise.band(Bitwise.bsl(c, 1), 0xFFFF)
      if Bitwise.band(c, 0x8000) != 0, do: Bitwise.bxor(shifted, 0x1021), else: shifted
    end)

  crc16(rest, crc)
end

The vector pins the implementation: slot("123456789") == 12739. This is what makes the slot part of the protocol. Any speaker — in any language — must compute the same slot for the same hashtag, or its keys would route to a different shard than every other speaker's, and the queue would split. The algorithm and its constants are the wire, not an implementation choice.

Compute a slot — the same CRC16 the connector runs

Type a queue name. The page extracts the hashtag the way hashtag/1 does — the name itself, since a bare queue carries no braces — and runs the same CRC16-XMODEM modulo 16384 that slot/1 runs. The check chip 123456789 must read 12739: that is the vector that proves the port. (The computation is over the ASCII bytes of the name, matching the byte-wise Elixir.)

slot/1 · type a queue name

The slot is one CRC16 of the hashtag, knowable before the wire is touched. One queue, one hashtag, one slot — so one atomic script can move a job across the queue's sets and rows in a single round.

Pattern → implementation

the pattern (Redis Patterns Applied)

Hash-tag co-location: wrap the shared part of a key in {...} so a group of keys routes to one slot, where an atomic multi-key operation is legal. Redis Patterns Applied — the tag mechanic shows the slot computation.

the implementation (echo_mq)

EchoMQ.Keyspace.slot/1 computes that slot client-side from the queue hashtag — CRC16 modulo 16384 — so the connector routes and partitions with no round trip, and the Lua scripts can declare a single-slot key set.

The pattern says "co-locate by hashtag"; slot/1 is the exact, pinned arithmetic that makes the co-location real and the same for every speaker.

Recap — the brace, the CRC16, the slot

The {q} brace is the cluster hashtag. hashtag/1 extracts the substring inside the first {...}; slot/1 runs it through CRC16-XMODEM modulo 16384, client-side, pinned by slot("123456789") == 12739. One queue hashes to one slot, so its keys co-locate — the precondition for atomic multi-key Lua. The next dive reads the space that sits beside every queue: the reserve.

Next in this module: The reserve — {emq}:, the core's first-byte-disjoint cross-queue space, and why emq cannot be a queue.

References

Where the slot algorithm and the hashtag routing rule are specified.

Sources

Related in this course