Ordering vs parallelism — partition the keyspace — Build a Message Queue (RabbitMQ / SQS)

Build a Message Queue (RabbitMQ / SQS) (14 scenes)

Scene 10 · Ordering vs parallelism — partition the keyspace

Globally ordered + competing consumers is impossible. FIFO preserves order WITHIN a message group; many groups = parallelism. Kafka's partition-by-key in queue costume.

Previously

Throughput is tuned: timeout, prefetch, worker count. But everywhere we've scaled out, we've also scrambled order — messages 1, 2, 3 land on different workers and finish in whatever order they finish. If order matters, we have to pay for it.

Scene 10

Ordering vs parallelism — partition the keyspace

Watch

Diagram

Three lanes stacked: STANDARD competing-consumers, FIFO with a single MessageGroupId, and FIFO with MessageGroupId = key. Each lane has its own event strip (head on the left), worker row (green = active, gray = idle), throughput badge, and a finish-order tracer above the strip.

Watch all three lanes drain in parallel. Standard finishes fast but the tracer is scrambled. FIFO-single keeps perfect order — at the cost of 7 idle workers. FIFO-keyed stripes work across 4 colored groups: ordered within each color, parallel across them.

Implementation

Broker.handOutFifo(cell)

ordering scope: at most one in-flight cell per group

1def handOutFifo(cell):
2    g = cell.MessageGroupId
3    # the ordering invariant: one worker per group at a time
4    if g in in_flight_groups:
5        return  # head-of-line block for this group only
6    w = pick_free_worker()
7    if w is None:
8        return  # all workers busy — try next tick
9    in_flight_groups.add(g)
10    w.deliver(cell, on_done=lambda:
11        in_flight_groups.discard(g))

Broker.assignByGroup(cell, groupId)

partition the keyspace — each group is its own sub-strip

1def assignByGroup(cell, groupId):
2    # hash-route to a sub-strip; sticky per group
3    subStripIx = stable_hash(groupId) % numSubStrips
4    subStrips[subStripIx].append(cell)
5 
6def drainSubStrips():
7    # every tick: one head per sub-strip, in parallel
8    for strip in subStrips:
9        head = strip.peek()
10        if head and head.MessageGroupId not in in_flight_groups:
11            handOutFifo(head)
12            strip.pop()

Producer.routeToPartition # Kafka's identical move

literally the same trick, different vocabulary

1# Kafka producer side — same idea, different name
2def routeToPartition(record, numPartitions):
3    if record.key is None:
4        return round_robin()  # like Standard: order-free
5    # MessageGroupId here is spelled `record.key`
6    return murmur2(record.key) % numPartitions
7 
8# Each partition is consumed by exactly ONE consumer in
9# the group at a time — that's the ordering scope.
10# Scale ordered work by adding partitions == adding groups.

PreviousPrefetch — how many in flight per worker NextRouting — one queue per consumer group