Ordering Guarantees and Head-of-Line Blocking

A topic with sixteen partitions has sixteen orders, not one. Records for a given key land on one partition and are appended in arrival order there; records for different keys have no defined relationship at all. That is the guarantee brokers actually offer, and most ordering bugs come from assuming it is stronger than it is.

The restriction is not an implementation shortcut. Total order across a partition is what makes a single reader sufficient, and a single reader is what makes the offset model work. Spreading order across a partition boundary would require the broker to coordinate between partitions on every append, which is the cost the design exists to avoid.

What the append order actually orders

The broker appends records in the order it accepts them. For one producer with one connection and no retries, that is the order in which the producer called send. With retries enabled and multiple requests in flight, it is not: a failed batch is retried while later batches may already have been accepted, so the log order can differ from the send order.

Kafka’s idempotent producer closes this by tagging each record with a per-partition sequence number. The broker tracks the last five batches per producer per partition and rejects a sequence gap, which forces the client to resend in order. Without that mechanism, preserving order requires setting the in-flight request limit to one, which serializes the producer’s connection and gives up the pipelining benefit described in producer batching and acknowledgment pipelining.

There is a second producer-side source of disorder that no broker setting can fix: two producers writing the same key. Broker order is the order of arrival, so two processes sending updates for the same entity can interleave unpredictably. Making that deterministic requires a single writer per key, or record content that makes the order irrelevant, such as a version number that the consumer uses to reject stale writes.

On the consumer side, order is preserved only if one consumer thread processes a partition’s records in offset order and does not process offsets 5 and 6 concurrently. Handing a partition’s records to a thread pool breaks the guarantee immediately, whatever the broker promised. The order of effects, not the order of receipt, is what applications care about.

Keys pin records to partitions, until the count changes

A keyed producer computes a partition from a hash of the key, modulo the partition count. The mapping is deterministic, which is the whole point: all records with the same key go to the same partition, and therefore share an order.

import zlib

def partition_for(key: bytes, count: int) -> int:
    # Any stable hash works; the property that matters is determinism.
    return zlib.crc32(key) % count

mapping = {k: partition_for(k, 4) for k in (b"user:1", b"user:2", b"user:3")}

The fragility is in the modulus. Adding a partition changes the divisor, and almost every key moves. A topic that grows from four to five partitions remaps four fifths of its keys, and during the changeover records for the same key can be appended to two different partitions, destroying the per-key order the key was supposed to provide. The same applies to any scheme that reduces the partition count, including a topic recreation.

This is why partition count is chosen for the lifetime of a topic rather than adjusted casually, and why repartitioning is usually a new topic plus a migration rather than an in-place change. Kafka’s partitioner.ignore.keys setting abandons key-based placement altogether: when it is enabled, a keyed record goes wherever the open batch is, which trades per-key order for batching efficiency.

Unkeyed records take a different path. Kafka’s default partitioner fills one partition with unkeyed records until the batch is full or the linger expires, then switches to another, which improves batching efficiency and deliberately gives up ordering between unkeyed records.

Head-of-line blocking is the price of the guarantee

A partition is read in order. If record 317 fails processing and the consumer refuses to skip it, records 318 onward cannot be applied, because applying them first would reorder effects for that partition. The consumer has three options, and all of them are costly in some dimension.

It can retry in place, blocking the partition until the record succeeds. Order is preserved, latency for everything behind it grows without bound, and a record that never succeeds stalls the partition forever. It can skip and continue, which preserves throughput and breaks order; this is only safe if later records do not depend on the skipped one. Or it can route the record aside to a separate destination and continue, which preserves progress and order among the remaining records while acknowledging that this record’s position in the sequence is lost.

The choice interacts with the acknowledgement protocol. On a log, committing offset 318 asserts that 317 is done, so skipping requires either committing past it — a loss — or committing an offset that does not advance, which makes every restart re-read the stuck record. Lease-based queues avoid the prefix problem entirely: each message is acknowledged independently, so a failed message can be left unacknowledged while its neighbours are deleted. That is a real advantage for heterogeneous work items, and it comes with a corresponding loss of any global order.

Head-of-line blocking also appears below the application. A partition has one leader broker and one replication path; a slow follower delays acknowledgement of everything in the partition under acks=all. And within a consumer, a single connection carrying many partitions multiplexes frames, so a large batch on one partition competes for bandwidth with the others, though the logical processing order per partition is unaffected.

Concurrency that respects keys

When a single consumer thread cannot keep up, the usual remedy is to process records concurrently. The safe form is to shard by key: a fixed set of in-memory queues, each served by one worker, with records routed by hash(key) % workers. Records for a key then stay ordered and records for different keys proceed independently. The failure mode of this design is a hot key that pins one worker while the rest idle, which is a load-balancing problem rather than an ordering one.

The unsafe form is a shared thread pool with no key affinity. It increases throughput and produces interleaved effects, and the symptoms appear later as out-of-order state, missed updates, or a “last write” that is neither the last sent nor the last received. Detecting it requires instrumenting the effect ordering, because the message flow itself looks perfectly ordered.

Ordering across partitions can be recovered, partially, by carrying sequence numbers in the payload. A consumer that buffers by key and applies records in sequence order can tolerate some reordering, at the cost of holding records whose predecessors have not arrived. Lamport’s observation applies: without a shared clock or a total order broadcast, only causal order can be recovered from message contents, and recovering it requires buffering. The buffer is unbounded in the worst case, which is why practical versions bound it and treat a gap that persists as a failure.

Choosing how much order to pay for

Ordering is not free and not binary. The useful questions are which operations actually require a sequence, what the unit of that sequence is, and what the system does when the sequence stalls. Payment updates for one account require order; updates for different accounts do not. If the required unit is small and the keys are many, partition-level order is close to free. If the unit is “all events”, the partition count collapses to one and with it all consumer parallelism, which is a throughput decision disguised as a correctness one.

A last trap is assuming that ordering survives retention. A consumer resuming from an old offset sees the retained records in order, but records that were deleted by retention or compaction are simply absent, so the sequence it observes has gaps. Order among what remains is preserved; completeness is not, which is the subject of log compaction, retention, and replay.