Modulo partitioning in a dynamic topology

Mar 19, 25

TL;DR

For modulo-based partitioning, each worker needs two values: its own index and the current number of replicas.

When static configuration is inconvenient or unreliable, workers can derive both values from Redis by registering themselves in time-based counter keys.

When a worker may act on them fits in a sentence: receiving the same index and replicas twice in a row is an exclusive lease on the work for one more interval plus a small gap. Exclusive because a lease is only ever issued on an index two intervals agreed on, and inside one interval a counter gives each index to one worker. A worker issues it to itself; nothing renews it but another matching pair, and nothing has to revoke it — it runs out on its own.

It is an alternative to running a coordinator for this, and the difference is not free: agreement arrives a couple of intervals late, and a change of membership costs the whole group an interval of standing down. What it does not cost is the split itself — no two workers hold the same index at the same moment. A good trade where a pause is cheaper than a coordinator, a poor one where ownership has to move the instant it changes.

nandi npm install n-and-i

Problem

Suppose a group of workers processes tasks with a rule like this:

task.id % replicas === index

This is simple and useful. Every task maps to exactly one worker index, so workers can share the same queue or task source without processing the same task twice.

The difficult part is not the formula. The difficult part is discovering the inputs:

  • replicas: how many workers are currently active
  • index: the current worker’s position inside that set

In elastic environments these values change. Instances start, stop, restart, fail, and scale horizontally. Static configuration quickly becomes stale, and a stale index or replicas value can cause duplicate processing or missed tasks.

Solution

Use Redis as a lightweight, rolling membership index.

Each worker periodically registers itself in a Redis counter key that represents the current time interval. The counter reply is that worker’s index for the interval it registered in. Once an interval has closed, its final value is how many workers took part in it.

Both values must come from the same closed interval. At interval N, a worker:

  1. Computes N from the current time.
  2. Runs INCR {name}:{N}, and keeps the reply as its index for interval N.
  3. Reads {name}:{N-1}, whose value is now final.
  4. Partitions using the index it kept during N-1 together with that count.

INCR counts from one and the formula wants positions from zero, so the index is the reply minus one. After that:

task.id % replicas === index

Everyone that registered during N-1 holds a distinct index in 0..replicas-1, and together they cover the range exactly once. That is what makes the partition complete: no task without an owner, and none with two.

The tempting shortcut is to use the index from the interval currently open, since it is already in hand. It does not work. That interval is still accepting registrations, so its count is not final, and pairing an index from it with the previous interval’s count mixes two different populations. A group that has just grown hands out indexes beyond the old count, and those workers match nothing. A group that has just shrunk leaves part of the range unclaimed, and those tasks are processed by no one. Waiting for an interval to close before using anything from it avoids both.

Membership discovery lags by one interval, but it avoids requiring a separate cluster coordinator. Every interval records who showed up; the next interval uses that completed record.

Joining and Leaving

Nothing in the store identifies a worker. It holds counters and nothing else — no list of members, no names, no heartbeats. A worker’s index is the reply to its own INCR, which no other worker receives, and it keeps that number in memory rather than reading it back.

That is also how a new worker recognises itself as new. It registers into the open interval like everyone else, but it has no index from the closed one, so it has nothing to pair with the count and owns nothing yet. It waits for the interval it registered in to close, and then for a second one to agree with it, and takes part after that. The same check covers a worker that stalled past an interval or restarted: the number it holds no longer belongs to the previous interval, so it stands down rather than acting on a stale mapping.

Leaving needs no announcement either. A worker that stops registering is simply absent from the next count.

Parameters

  • name: worker group name, for example mail-sender
  • interval: time window length
  • gap: timing slack, as a fraction of the interval

The interval should be comfortably larger than a registration round trip and the jitter around it. It also sets the pace of everything else: a new worker waits two intervals before it owns anything, and a departure costs the group an interval of standing down. Short intervals react faster to scaling changes but spend a larger share of themselves in transit. Longer intervals are more stable, but they delay readiness and rebalancing.

The gap trades tolerance for spread, and is described under Clocks and Timing below. Widening it forgives slower round trips and longer pauses, at the cost of bunching registrations toward the middle of the interval. Narrowing it does the reverse, until it is too tight for a worker to recover from a single failed registration inside it and ordinary noise starts costing cycles.

Old interval keys should expire. A key only has to outlive the interval that reads it, so a small multiple of the interval is enough.

Safe Index Transition

Changing index or replicas changes task ownership. A task that belonged to one worker under the old mapping may belong to another worker under the new mapping.

Because of that, workers should not switch immediately while they are actively consuming. A safe transition usually looks like this:

  1. Stop taking new tasks.
  2. Finish or release in-flight tasks.
  3. Apply the new (index, replicas) pair.
  4. Resume consumption.

The exact transition depends on the task system. The important rule is that a worker must not process tasks using two ownership mappings at the same time.

Standing down is the same transition with nothing at the end of it, which makes shutdown a special case of a change of ownership rather than a separate mechanism.

A worker following those steps still cannot make the group safe on its own. Workers do not adopt a new pair at the same moment — each applies it as its own registration returns — so for a fraction of an interval two mappings are live across the group, and a task that has changed hands can be picked up twice. Every worker can be draining correctly and the group still doubles up.

Making the switch simultaneous is one answer, and an expensive one: it wants a shared instant to switch at, which is the coordination the scheme set out to do without. There is a cheaper one. A worker owns a pair only once two consecutive closed intervals have implied the same pair, and owns nothing while they disagree. Two matching answers in a row are what issue the lease; a disagreement is what withholds it.

That is what makes the lease exclusive, and it is enough by itself. At any moment the group spans two consecutive intervals at most, since a worker has either registered in the current one or not yet. Owning an index through the later interval now means having held that same index through the earlier one as well — and every worker that registered in the earlier interval holds a distinct index in it, because a counter hands out each value once. Two workers claiming the same index would have to be the same worker. Nothing is compared between workers, and nothing has to happen at the same time.

What it costs is a stand-down. Any change to replicas changes every pair, so the whole group lets go for an interval and comes back together. It comes back onto the indexes it already had: a worker that owns nothing goes on registering, so it keeps its place in the ordering, and the arrangement that had settled is the one that re-forms.

One thing that argument takes for granted is worth making explicit — that the group really does span no more than two intervals. A worker that lost contact with the store and kept its last pair would be a third, acting on a mapping two intervals old while everyone else has moved on. So losing contact has to be noticed on a clock, not on an error. A registration that fails is easy to see; one that hangs — a connection dropped without being closed, a store that stopped answering — produces nothing to react to, and a worker waiting on it waits indefinitely. Whatever the reason, a worker that has not completed a registration by a bounded margin past the slot it was due in has to stand down and drop what it holds. That is the lease running out, and the useful part is that nothing has to be reachable for it to happen — not the store, not another worker. The worker is then in the position a restart would leave it in, and it comes back the same way.

Clocks and Timing

There are two separate questions of time here: which interval a worker is in, and when inside that interval it registers.

The first should not be left to local clocks. If workers disagree about the current interval they write into different keys and count separate groups. Letting the store decide settles it — computing N from the store’s own clock, in a server-side script, puts every worker in the same interval by construction, whatever its own clock says.

The second question remains. If every worker registers at the same moment, the order of the replies is decided by whatever noise is in the network, so indexes are reshuffled every interval even when membership has not changed at all. Each reshuffle is real work: ownership moves and consumers have to drain.

Spreading registrations across the interval settles the ordering. A worker holding index i of n can register at (i + 0.5) / n of the interval. The arrangement reinforces itself — the worker that registers third is handed the third index, which puts it third again next time. A settled group then keeps its assignment indefinitely. A join shifts only the workers after the point it lands, a departure only those after the place it left, and two workers that do collide are handed different indexes and separate on the following interval.

Registrations should stay clear of the boundaries. A worker firing at the very end of an interval needs only a little jitter to land in the next one, which skips an interval and costs it a cycle. So the spread covers interval - 2 * gap, leaving a gap at either end — a fraction of the interval somewhere around a tenth to a sixth, wide enough to swallow a round trip and a stalled process, narrow enough to leave the group spread out.

That same gap is the margin for standing down, and it is one number rather than two for a reason. The two have to agree. A worker that missed a registration was due by 1 - gap into its interval at the latest, and the earliest anyone can take up a newer mapping is gap into the interval after — so a stand-down that is one gap late always lands in time, whatever the gap is set to. Two numbers chosen independently would not, and nothing would say so: the group would look healthy and quietly double up.

Before any count is known there is nothing to space against, and a random offset per instance is the fallback. It is also what keeps a fleet that starts all at once from registering in a single burst.

Caveat

The first stable (index, replicas) pair needs two closed intervals that agree on it, so initial readiness is delayed by about interval * 2 to interval * 3. Membership changes are paid for the same way: a change to replicas moves every pair at once, so the whole group stands down for an interval and comes back together.

The partition is guaranteed at the moment ownership is handed over, and no further. Work already in flight is the worker’s own problem: a consumer that keeps going after it has been told to stand down, instead of draining first, can still finish a task that now belongs to someone else. The scheme decides who owns what, and the drain is what makes that mean anything.

A worker that registers and then goes away stays counted in the interval it last registered in, so its share of the range goes unowned until that interval has passed. The count is a record of who was present, not of who still is, and no amount of bookkeeping in the store changes that — only a shorter interval narrows the window.

This approach is useful when eventual membership is acceptable and workers can tolerate controlled rebalancing. It is not a replacement for a stronger coordination protocol when the system needs immediate, strongly consistent ownership changes, and a group that has to keep serving straight through a rebalance wants a different scheme — one that fences the work rather than pausing it.