SD8.4 · LESSON 4 OF 6

Ordering and partitions

Design asynchronous processing with explicit acknowledgment, ordering, replay and duplicate-handling rules.

THE IDEA

Ordering and partitions

A partition is an ordered sequence; several partitions let several consumers work at once. Route by key, so all events for one key land in one partition and stay in order. But there is no order between partitions: two consumers can interleave their events in C(5,2) = 10 ways for a 3 + 2 split, and only one of those matches the arrival order. A global order needs extra structure and limits parallelism.

Arrival order: a1, b1, a2, b2, a3. Key a goes to partition 0 (a1, a2, a3), key b to partition 1 (b1, b2). Pick how two parallel consumers interleave:

consumed: a1, b1, a2, b2, a3 within partition 0: a1 < a2 < a3 (original order kept) within partition 1: b1 < b2 (original order kept) global arrival order reproduced: yes (one of 10 possible) possible interleavings of 3 + 2 events: C(5,2) = 10

A partition gives an ordered sequence, so several partitions let consumers work in parallel. Order across partitions is not defined; global ordering needs extra structure (one partition, or sequence numbers) and limits parallelism.

Choose an interleaving.

Predict first. Does per-partition ordering automatically order all events from every partition?

Chapter context

Asynchronous work decouples when a request is accepted from when its side effects finish. Queues and logs buffer differences in timing, but they do not remove processing cost or guarantee globally unique effects by themselves.

TRY IT YOURSELF

Part 1. Do it hands-on

Partition and count interleavings by hand, then write the routing and the order checks.

Arrival order: a1, b1, a2, b2, a3. Key a goes to partition 0 (a1, a2, a3), key b to partition 1 (b1, b2). Pick how two parallel consumers interleave:

events in partition 0 events in partition 1 possible interleavings per-partition order orders everything? (yes/no)

To do: Events by key arrive: a1, b1, a2, b2, a3. Key a goes to partition 0 and key b to partition 1. Events in partition 0?
To do: Events in partition 1?
To do: Two consumers read the partitions independently. In how many different orders can the 5 events be seen overall (keeping each partition's own order)? C(5,2)
To do: Does per-partition ordering automatically order all events from every partition? Type yes or no

Part 2. Do it in code

partition_for(key, n): sum(ord(c) for c in key) % n.
assign(events, n): events is a list of (key, seq). Return a list of n lists: each partition's events in ARRIVAL order.
interleavings(p0, p1): every merged sequence of two lists that keeps each list's own order (list of lists).
key_order_ok(consumed, events): True if, for every key, the events of that key appear in `consumed` in their original arrival order.
count_interleavings(len_a, len_b): how many such merges exist: C(len_a + len_b, len_a).
global_order_preserved(consumed, events): True if consumed equals the arrival order exactly.

import itertools
from math import comb

def partition_for(key, n):
    pass

def assign(events, n):
    pass

def interleavings(p0, p1):
    pass

def key_order_ok(consumed, events):
    pass

def count_interleavings(len_a, len_b):
    pass

def global_order_preserved(consumed, events):
    pass

Ctrl/⌘ + Enter runs it

Stuck, or something not working? You can come back to it any time.

CHECK YOUR UNDERSTANDING

Does per-partition ordering automatically order all events from every partition?

ANoBYes

Chapter reference: math, worked example & code

This section belongs to the whole chapter, so it is the same on every lesson in it and may cover a different lesson's topic. The code for the experiment you just ran is inside the experiment itself.

Math and notation

A fluid approximation for backlog B is

\Delta B\approx(\lambda-\mu)\Delta t

while the queue is nonempty, where lambda is arrival rate and mu processing rate. Backlog cannot go below zero. Delivery guarantees must specify which system boundary and side effects they cover.

Worked example

Arrivals at 120 jobs/s and processing at 100 jobs/s grow the queue by 20 jobs/s, reaching 1200 after one minute. If arrivals then drop to 80 jobs/s, net drain rate is 20 jobs/s and clearing that backlog takes 60 seconds under the constant-rate model.

Reference code

The following example uses the Python standard library and does not call a remote service.

arrival,service,seconds=120,100,60
backlog=max(0,(arrival-service)*seconds)
assert backlog == 1200
new_arrival=80
drain=service-new_arrival
assert drain == 20 and backlog/drain == 60

Python examples are provided for study and local execution; this page does not execute Python.

Common mistakes

Exactly-once terminology must state its scope. Retrying can duplicate external effects. A partition's order is not a universal order across an entire system.