Message ordering: per-key queues and the sequential convoy

Message ordering is the promise that a consumer applies related messages in the order they were produced: an order is PAID before it is SHIPPED, and a wallet is debited before its refund arrives. At scale, brokers rarely offer one global order. They offer per-key order: messages that share a key, such as an order ID, travel in one lane and are handled one at a time, while different keys run in parallel. The sequential convoy is that idea applied to a queue with many consumers.

Picture it first: one nurse per patient

A hospital ward has 30 patients and six nurses. Doctors drop medication slips in a tray: “start drug X”, later “double the dose”, then “stop X, switch to Y”.

On the first night, any free nurse takes the next slip. Nurse 1 takes “double the dose” for bed 12 but is called away. Nurse 2 takes “stop X, switch to Y” and carries it out. Nurse 1 returns and doubles a drug the patient should no longer get. Every slip was handled exactly once, in the wrong order.

The fix is one rule: each patient belongs to one nurse per shift, who works through that patient’s slips in the order they were written. Six nurses still work in parallel. Two side effects follow. When bed 12 has a crisis, that nurse’s other slips wait. And a patient with three times the slips makes one nurse fall behind while others are idle. As a safety net, slips are numbered per patient (12-1, 12-2 …), and a slip older than the last one done is set aside.

Map it back: slips are messages, the patient is the key, and the shared tray is competing consumers. One nurse per patient is per-key ordering: a Kafka partition, an SQS message group, a Service Bus session. The crisis is head-of-line blocking, the busy patient is a hot key, and numbered slips are per-entity sequence numbers.

Why order matters

Most messages describe a change to one thing, and applying two changes to the same thing in the wrong order fails in one of two ways.

Stale overwrite. An order goes PLACED → PAID → SHIPPED. Apply PAID after SHIPPED and the status table ends on PAID: the customer sees “preparing your order” for a parcel already on the truck. Reverse an address change from Pune to Mumbai and the next parcel goes to Pune. Nothing throws an error, so nothing alerts.

Update before create. AccountUpdated arrives before AccountOpened, and the handler fails or creates a half-empty account that the late event overwrites. In a UPI-style wallet, a refund processed before the debit it reverses can push a balance past its limit or be rejected as unknown. On a stock exchange, a cancel that overtakes its own order is rejected, and the order then trades.

Not every message needs order. Thumbnails, independent emails and like counters give the same result in any order. Pay for ordering only where two messages touch the same state and the outcome depends on which goes first.

Total order vs per-key order

Total (global) order means every message is handled in one sequence: one lane, one consumer at a time. At 5 ms per message that is 1 ÷ 0.005 s = 200 messages a second, however many machines you own. A Big Billion Days-style sale producing 40,000 order events a second would need 40,000 ÷ 200 = 200 lanes.

Per-key (partial) order means messages with the same key are handled in the order sent, and different keys have no promised order. Order 17’s events never overtake each other, but orders 17 and 42 interleave freely, so throughput grows with the number of lanes.

Per-key order is almost always what the business needs, because invariants live inside one entity: an order’s lifecycle, an account’s balance, an instrument’s order book. When a rule spans two entities, such as “debit Asha before crediting Ravi”, don’t ask the broker for order across keys: make it one event keyed by the transfer, or use a saga.

Where order gets lost

Order must survive three hops: producer to broker, inside the broker, and broker to the code that applies the change.

On the producer side

• Two producers for one entity. If the order and payment services both publish order-status events, the broker sees arrival order, not real order, and timestamps can’t settle it because clocks on two machines disagree (see clocks and ordering). Give each entity one writer that numbers its events in the same transaction as the change, as the transactional outbox does.
• Retries with several requests in flight. If Kafka batch 1 fails and is retried while batch 2 succeeds, batch 2 lands first. Kafka’s docs say so: with retries on, idempotence off and max.in.flight.requests.per.connection above 1, records can be reordered. With enable.idempotence=true, the default when nothing conflicts, order holds for up to 5 in-flight requests, because the broker remembers the last 5 batches per producer (see the idempotent producer).
• Your own resends. Code that calls send() again after later messages for the key went out has reordered them. Pub/Sub’s client libraries refuse: after a failed publish with an ordering key, later messages for that key fail until you explicitly resume.

In the broker and the consumer

• Competing consumers. m1 and m2 for one order go to two workers and m2 finishes first. Service Bus’s docs draw the line: sequence numbers give delivery order, only sessions give processing order.
• Retries and redelivery. A failed message comes back after newer messages for its key were applied (Figure 2).
• Dead-letter queues. Moving a failing message aside lets the next one go first; redriving it puts an old change on top of a newer one. AWS advises against a DLQ on a FIFO queue if order must hold exactly.
• Thread pools inside a consumer. Hand 500 records from one partition to 16 threads and the partition’s order is gone.
• Rebalances and expired leases. A Kafka consumer that misses max.poll.interval.ms (5 minutes by default) loses its partitions, but if it was only slow it may still be applying a batch while the new owner restarts from the last committed offset: two processes on one key. An SQS visibility timeout expiring mid-job does the same.
• Repartitioning. Kafka places a keyed record at hash(key) % partitions and, as its operations guide warns, never moves existing data. Going from 12 to 16 partitions moves about 75% of keys: a key stays only when h mod 12 = h mod 16, true for 12 of every 48 hash values. A moved key has old events in one partition and new ones in another, read at different speeds. RabbitMQ’s consistent-hash exchange can also send a routing key to a different queue after a node restart.

Per-key ordering: one lane per key, one reader per lane

Every per-key mechanism rests on three rules: same key, same lane (usually by hashing); each lane is FIFO; and one message per key in flight, so one consumer reads a lane and doesn’t start a key’s next message until the previous one is settled. Most real ordering bugs break the third rule while the first two hold.

Kafka: partitions

Each partition is a totally ordered log. With a key, the default partitioner hashes it to pick the partition; without one, records are spread for batching and lose per-key order. In a consumer group each partition has exactly one reader, so a 12-partition topic keeps at most 12 consumers busy. You gain cheap, high-throughput order plus replay. You pay with order only as fine as a partition and a parallelism cap set at creation. Kafka’s newer share groups put several consumers on one partition, queue-style, so records no longer complete in partition order; keep them for unordered work. More in Kafka.

Amazon SQS FIFO: message groups

Every FIFO message carries a required MessageGroupId, and a group is delivered in send order. While any message from a group is in flight (received, not deleted, visibility timeout not expired), SQS returns no more from that group, so two workers never hold it at once; other groups go to other consumers. Without high-throughput mode a FIFO queue allows 300 calls a second per API action (3,000 messages a second in batches of 10). High-throughput mode allows up to 70,000 calls a second in the largest regions and 9,000 in Mumbai, if load is spread over many group IDs. You gain millions of tiny lanes with nothing to manage; you pay with lower ceilings than a standard queue.

Azure Service Bus: sessions

A sender sets a SessionId. A receiver accepts a session and holds an exclusive lock on its messages, including later arrivals, until it closes the session or the lock expires. Only one receiver can hold a session, and session state (up to 256 KB on Standard, 100 MB on Premium) lets the next receiver resume after a crash. Sessions need the Standard or Premium tier, and once enabled every message must carry a session ID. A message abandoned more than MaxDeliveryCount times (10 by default) is dead-lettered while the session carries on, and if resubmitted it gets a new sequence number, so order for that session is broken.

RabbitMQ: one queue, one active consumer

A queue keeps publish order even after requeues, but with several consumers each can see messages out of order. Declaring the queue with x-single-active-consumer makes the broker deliver to one consumer at a time and fail over automatically. It can’t be set by policy, so nobody can switch it off under a running system. A queue runs on one CPU core, so to scale, spread routing keys over N queues with the consistent-hash exchange, each with a single active consumer: N ordered lanes, like partitions.

Google Cloud Pub/Sub: ordering keys

Publishers set an ordering key, the subscription must be created with ordering on, and related messages must be published in one region. Each key takes up to 1 MBps, and Google expects keys to number in the billions, not like partitions. Push subscriptions allow one outstanding message per key. The surprise: if message 2 for a key is redelivered, every later message for that key is redelivered too, even acknowledged ones, so handlers must be idempotent.

The sequential convoy pattern

Azure’s Architecture Center calls this shape the Sequential Convoy: tag each message with a category key, process each category one message at a time in FIFO order, and process categories in parallel. Each key’s messages move like a convoy, only as fast as the front vehicle, while many convoys share the road.

Step by step, each consumer in a convoy:

1. Asks the broker for any group that has messages and no owner, and gets an exclusive lock on it.
2. Receives that group’s messages in FIFO order, settling each one before taking the next.
3. Releases the group when it is empty, or loses it when the lock expires, and the group returns to the pool for any consumer.

The key difference is how lanes are assigned. With sessions or message groups the lane is the key and any free consumer takes any idle key, so unrelated keys never share a lane. With partitions, keys hash into a fixed set of lanes, so a slow key holds up every key in its partition.

The limits follow from arithmetic. Per-key throughput is one handler: at 20 ms per message, a key moves at most 1 ÷ 0.02 s = 50 messages a second, however many consumers you add. So speed up the handler (batch writes, async I/O) before adding machines. Azure’s guidance adds three operational points: size the lock for the slowest legitimate message and renew it, since an expired lock means reprocessing; watch backlog per key, not just queue depth; and validate the key at the producer, because a wrong session ID corrupts another entity’s sequence.

Head-of-line blocking: poison messages and hot keys

Strict per-key order has a built-in failure mode, head-of-line blocking: the front message must finish before anything behind it starts. If it can’t, the lane stops.

The poison message dilemma

A message that always fails, say a RefundIssued the ledger rejects because of a bug, leaves three options.

Block the key and retry with backoff and page someone. Order is safe. With sessions or groups only that key waits; in Kafka the whole partition does: at 500 messages a second, 5 minutes of retries leaves 500 × 300 = 150,000 messages from thousands of innocent keys behind it.

Dead-letter the message and move on. The lane flows, but the key’s later events are applied without the skipped one. Fine for a notification feed; for a wallet, the skipped refund and a later debit now land in the wrong order. Service Bus does this by default after 10 deliveries.

Park the key. Move the failed message and every later message with the same key to a parking store and mark the key parked; other keys keep flowing. Once fixed, replay the parked messages in order and unpark. The consumer loop gains one check (“is this key parked? then append, don’t process”), plus a parked-keys table and a replay tool.

A merely slow message, such as a 30-second call to a payment gateway, blocks the same way for a while. Put a timeout on every downstream call shorter than the lock or lease, so a hung call fails and retries instead of holding the lane.

Hot keys

When one key gets far more traffic than the rest, its lane is the bottleneck. A live cricket match keyed by match ID might see 2,000 score and commentary events a second in a tense chase; a 2 ms handler tops out at 500, so the backlog grows by 1,500 events every second while other consumers idle. In Kafka the hot key also overloads its partition: one key with 5% of traffic on a 100-partition topic puts about 5% + 1% = 6% of all traffic on its partition, six times a fair share.

• Split the key if order is only needed at a finer grain, such as per innings. You gain lanes and lose order across the split.
• Batch per key: apply 50 queued events in one write. You gain throughput and pay with latency.
• Conflate: if only the latest state matters, like a live score or a rider’s location, keep the newest message and drop the rest. Never for a ledger.

Pub/Sub’s docs suggest watching the age of the oldest unacknowledged message; a rising age on steady traffic is the signature of a hot or stuck key. See also backpressure and load shedding and hot keys.

Going deeper: more parallelism than partitions

You often have 12 partitions and 100,000 keys. You can run different keys concurrently inside one consumer, as long as each key stays sequential: send each record to worker hash(key) % W, each with its own FIFO, and commit a partition’s offset only up to the first unfinished record.

# Per-key order with W workers inside one consumer (confluent-kafka, sketch)
workers = [Worker() for _ in range(W)]   # each: one thread draining its own FIFO

while True:
    for msg in consumer.consume(num_messages=500, timeout=1.0):
        tracker.started(msg.partition(), msg.offset())
        workers[hash(msg.key()) % W].submit(msg)   # same key, same worker
    # a worker calls tracker.done(partition, offset) after each message;
    # commit, per partition, the lowest offset that is not done yet
    consumer.commit(offsets=tracker.safe_offsets(), asynchronous=True)

Confluent Parallel Consumer packages this: one Kafka consumer with partition, key or unordered modes. In key mode it never runs two records with the same key at once or out of order, commits only the highest offset below which everything is done, and records later finished offsets in the commit metadata so a restart doesn’t replay them. Its README’s example: 10 partitions with a 50 ms handler give 1 s ÷ 50 ms × 10 = 200 messages a second, while key-level concurrency over 100,000 keys gives a theoretical 2,000,000, so the downstream service becomes the limit. You gain parallelism without repartitioning, and a slow key stops blocking its neighbours. You pay with in-memory state and far more load on downstream systems.

When order slips anyway: consumer defences

Assume order will slip sometimes. These defences turn a reordering into a skipped stale update instead of a wrong final state.

Version every entity’s events

The single writer stamps each event with the entity’s version, incremented in the same transaction as the change. The consumer stores the last applied version per entity:

• Version ≤ stored: duplicate or stale. Acknowledge and skip.
• Version = stored + 1: the next one. Apply it and store the version.
• Version > stored + 1: something is missing. A full-state event can be applied, since newer state wins; a delta (“add ₹500”) must wait, so hold it or park the key.

The atomic conditional UPDATE is in effectively-once consumers; it is optimistic locking with the producer supplying the version.

Use the producer’s version, never a timestamp: clocks drift, events tie within a millisecond, and only a sequence gap tells you something is missing.

Resequence or make the update order-insensitive

The Resequencer from Enterprise Integration Patterns buffers out-of-sequence messages until the gap fills, then releases them in order. Bound it, say 1,000 messages or 30 seconds per key, then alert and fetch current state, or one lost message becomes unbounded memory.

Cheaper still is not needing order:

• Forward-only state machines. Rank PLACED < PAID < SHIPPED < DELIVERED and never move backwards, so a late PAID is ignored. Branches like CANCELLED need an explicit rule.
• Commutative operations. Increments and set-unions give the same result in any order; pair them with deduplication.
• Event as notification. The event says only “order 42 changed” and the consumer fetches current state from the owner. Order stops mattering; you pay a read per event and depend on the owner being up.

Choosing the key

1. Key by the entity whose invariant you protect: order ID, wallet ID, instrument symbol, booking ID. Messages that must apply in order must share a key.
2. Coarser keys buy order; finer keys buy parallelism. Keying by customer orders all of a customer’s orders against each other, which you rarely need, and turns a corporate customer with 50,000 orders a day into one hot lane. Keying by tenant makes your biggest tenant your slowest lane.
3. Keep cardinality far above the lane count. Hash 1,000 keys into 100 partitions and the busiest typically gets about twice the average; with a million keys the spread is within a few percent. Country or status is almost never the right key.
4. Fix the lane count early. Over-provision Kafka partitions. To change them later, create a new topic, switch producers at a cutover, and finish the old topic before reading the new one.

For a stock exchange, each symbol’s order book is strictly sequential, so the symbol is the key and a hot symbol gets its own lane. For food delivery, order events key by order ID and rider pings by rider ID with conflation. And remember that order holds only within one topic: OrderPlaced on orders and PaymentCaptured on payments have no relative order, even with the same key.

Cheat sheet

How to say it in the interview

“I need order per entity, not globally. Payment events are keyed by payment ID and written by one service through an outbox, with a version per payment. In Kafka that key maps to one partition, the producer has idempotence on, and each consumer handles one message per key at a time. For more parallelism than partitions I add key-level concurrency in the consumer rather than repartitioning. The cost is head-of-line blocking, so a message that keeps failing parks its key instead of going to a DLQ, and other keys keep flowing. And consumers check versions, so a stale event can never move a payment backwards.”

Why not just use one partition? One partition means the throughput of one handler: at 5 ms a message, 200 a second. Per-key order gives the same business guarantee with as many lanes as you have keys or partitions.

What happens if you add partitions to a keyed topic? Most keys’ new records go to a different partition (12 → 16 moves about 75%) while older records stay put, so new events can overtake old ones. Drain first or migrate to a new topic, and keep version checks as the backstop.

Can’t the consumer just sort by timestamp? Only inside a buffer, and producers’ clocks disagree. A per-entity sequence number from the single writer makes gaps detectable; a timestamp never does.

SQS FIFO or Kafka for ordered work? SQS FIFO when you want a lane per entity with nothing to manage, a stuck message should block only its group, and the quotas fit. Kafka when you need very high throughput, replay and several consumer groups, and can accept keys sharing partitions.

Where to go next

• Message queues: leases, visibility timeouts and competing consumers.
• Delivery guarantees and DLQs: the idempotent producer and dead-letter queues.
• Effectively-once consumers: the versioned update in SQL.
• Transactional outbox: one writer per aggregate, in order.
• Publish/subscribe: no order across subscriptions.
• Kafka: partitions, consumer groups and offsets.
• Clocks, ordering and conflict resolution: why timestamps can’t order events.
• Consistent hashing: mapping keys to lanes with less movement.
• Event sourcing and CQRS: per-entity order as the data model.
• Design a digital wallet: ordered balance changes end to end.

References and further reading

1. Azure Architecture Center: Sequential Convoy patternlearn.microsoft.comGroup messages by a category key, process each group in FIFO order and groups in parallel; per-group throughput, key correctness, lock tuning and poison messages.
2. Azure Service Bus: Message sessionslearn.microsoft.comExclusive session locks, session state size, MaxDeliveryCount of 10, lost order on DLQ resubmission, and sequence numbers versus processing order.
3. Amazon SQS Developer Guide: FIFO queue delivery logicdocs.aws.amazon.comOrder per message group ID, no further messages from a group while one is in flight, batches of up to 10 and no way to request a specific group.
4. Amazon SQS Developer Guide: Message quotasdocs.aws.amazon.comFIFO throughput of 300 calls per second per action, high-throughput mode limits by region, and the 30-second default visibility timeout.
5. Apache Kafka 4.2 documentation: Producer configskafka.apache.orgHow retries with more than one in-flight request reorder records, and why idempotence preserves order for up to 5 in-flight requests.
6. RabbitMQ: Broker semantics, message ordering guaranteesrabbitmq.comQueues keep publication order even with requeues, but consumers on a shared queue can observe messages out of order.
7. RabbitMQ: Consumers (single active consumer and concurrency)rabbitmq.comSingle active consumer with automatic failover, why it cannot be set by policy, concurrent dispatch races, and one core per queue.
8. Google Cloud Pub/Sub: Order messagescloud.google.comOrdering keys, same-region publishing, 1 MBps per key, redelivery of all later messages for a key, push and pull limits, and hot keys.
9. Enterprise Integration Patterns: Resequencer (Hohpe and Woolf)enterpriseintegrationpatterns.comA stateful buffer that holds out-of-sequence messages until the sequence is complete, then releases them in order.
10. Confluent Parallel Consumer (GitHub README)github.comKey-level concurrency inside one Kafka consumer, offset tracking beyond the highest committable offset, and the 200 versus 2,000,000 messages-a-second example.