Eliminating Bates Collisions Across Parallel Endorsement Workers

The moment a single-worker endorsement job is scaled to a pool, Bates collisions appear: two workers stamp the same number onto different pages, and the production now contains two pages with identical citations. This is the defining failure of the Bates Numbering & Endorsement stage under concurrency, and it is catastrophic because a Bates number is supposed to be a unique key for the life of the matter — a collision means a brief that cites PROD0000481 no longer identifies a single page. The failure violates the uniqueness guarantee a production must hold, and it typically slips past a casual export check to surface only when the receiving party’s load fails on a duplicate key. This guide isolates the concurrency root cause and delivers a distributed allocator that makes collisions structurally impossible.

Diagnostic Log Signatures

The collision surfaces either at QC or at the receiving platform’s import. Capture the signature verbatim — the repeated number and the two document ids are the whole incident.

[INFO] Endorsement pool: 12 workers, 512044 pages, target PROD0000001..
[WARN] worker-07 claimed start=480441 from local counter
[WARN] worker-03 claimed start=480441 from local counter
[ERROR] QC defect bates_collision on DOC-092210: expected > 480882, found 480441
[ERROR] Import rejected by review platform: duplicate BEGDOC PROD0000480441
[CRITICAL] Volume PROD is not sealable: 6 colliding ranges across 4 workers

Symptom checklist — two or more confirm a concurrency collision rather than a data error:

• The same Bates number appears in two manifest rows with different document ids.
• Collisions cluster at values where multiple workers started or resumed at once (batch boundaries, a restart, a rebalance).
• The number of distinct colliding ranges scales with worker count — more workers, more collisions.
• The receiving platform rejects the load on a duplicate BEGDOC/BEGBATES key.
• The defect is not reliably reproducible single-threaded — it appears only under parallel execution, the hallmark of a race.

Root-Cause Breakdown

Every collision traces to a counter that is not linearizable across workers.

1. Local counters. The most common cause: each worker holds its own copy of the “next number,” seeded from the same start value, and increments independently. Two workers therefore hand out the same numbers. Any design where the counter lives in worker memory collides the instant there is more than one worker.
2. Read-modify-write races on a shared counter. Even with a shared counter, a non-atomic read → add → write sequence races: worker A reads 480440, worker B reads 480440 before A writes back, and both compute 480441. The counter has to advance in a single atomic step, or the read and the write have to be fenced by a lock that spans both.
3. Non-transactional claim-and-record. A subtler variant: the counter advance and the ledger write happen in separate operations, so a crash between them either double-consumes (advance persisted, claim lost, worker retries and advances again) or loses the mapping needed for idempotent retry. The claim and its record must commit together.
4. Range reuse after a rebalance. When a job rebalances work across a resized pool, a worker that inherits a partially processed batch re-claims numbers the previous owner already used, unless claims are idempotent on document id.

Remediation Architecture

Make the counter the single linearizable source of truth, claim ranges atomically, and bind the claim to the document id so retries and rebalances are safe.

1. One atomic counter, range claims. Replace every local counter with a single linearizable primitive — a database sequence, a Redis INCRBY, or an atomic UPDATE-RETURNING — and have each worker claim its document’s whole page range in one call.
2. Transactional claim + ledger. Advance the counter and record the doc_id → range mapping in the same transaction, so the claim is durable exactly when the counter moves.
3. Idempotency on document id. A retry or a rebalanced worker looks up the document’s existing claim before allocating; if a range is already recorded, it reuses it. Numbers are consumed once per document, ever.

The diagram contrasts the colliding local-counter design with the correct atomic-claim design.

Distributed atomic allocator

The implementation uses PostgreSQL’s atomic UPDATE ... RETURNING to advance a shared counter and record the claim in one transaction. The same shape works with a Redis INCRBY plus a claims hash. Claims are idempotent on document id, so retries and rebalances never double-consume.

import logging
from dataclasses import dataclass
from typing import Optional

logger = logging.getLogger("ediscovery.bates.dist")


class CollisionError(Exception):
    pass


@dataclass
class Range:
    doc_id: str
    start: int
    end: int


class DistributedBatesAllocator:
    """Atomic, idempotent Bates allocation over a shared SQL counter.
    `conn` is a DB-API connection to a store with transactional guarantees."""

    def __init__(self, conn, counter_name: str):
        self.conn = conn
        self.counter_name = counter_name
        with self.conn:  # DDL in its own transaction
            cur = self.conn.cursor()
            cur.execute("""
                CREATE TABLE IF NOT EXISTS bates_counter (
                    name TEXT PRIMARY KEY, high BIGINT NOT NULL)""")
            cur.execute("""
                CREATE TABLE IF NOT EXISTS bates_claims (
                    doc_id TEXT PRIMARY KEY, start BIGINT NOT NULL, "end" BIGINT NOT NULL)""")

    def claim(self, doc_id: str, pages: int) -> Range:
        if pages < 1:
            raise CollisionError(f"{doc_id}: pages must be >= 1")
        with self.conn:  # single transaction: claim + record commit together
            cur = self.conn.cursor()
            # Idempotency: reuse an existing claim for this document id.
            cur.execute('SELECT start, "end" FROM bates_claims WHERE doc_id=%s', (doc_id,))
            row = cur.fetchone()
            if row:
                return Range(doc_id, row[0], row[1])
            # Atomic advance: one statement reads and writes the counter.
            cur.execute("""
                UPDATE bates_counter SET high = high + %s
                WHERE name = %s RETURNING high""", (pages, self.counter_name))
            new_high = cur.fetchone()[0]
            start, end = new_high - pages + 1, new_high
            cur.execute('INSERT INTO bates_claims (doc_id, start, "end") VALUES (%s,%s,%s)',
                        (doc_id, start, end))
        logger.info("Claimed %d-%d for %s", start, end, doc_id)
        return Range(doc_id, start, end)


def initialize_counter(conn, name: str, start: int) -> None:
    """Seed the shared counter once, before any worker starts claiming."""
    with conn:
        conn.cursor().execute(
            "INSERT INTO bates_counter (name, high) VALUES (%s, %s) ON CONFLICT (name) DO NOTHING",
            (name, start - 1))

Verification Checklist

Confirm the pool cannot collide before releasing it on a production:

• Every Bates number in the manifest is unique — a GROUP BY bates HAVING count(*) > 1 returns zero rows.
• The counter is a single shared linearizable primitive; no worker holds a local copy of the next number.
• The counter advance and the claim record commit in one transaction, verified by killing a worker mid-claim and confirming no double-consume.
• Re-running a document (retry or rebalance) reuses its recorded range rather than claiming a new one.
• A stress run at the target worker count produces disjoint contiguous ranges and the receiving platform accepts the load with no duplicate-key rejection.

Conclusion

Bates collisions under parallelism are always a counter-linearizability defect: local counters, unfenced read-modify-write, or a non-transactional claim-and-record. The fix is structural, not defensive — one shared atomic counter, range claims that advance and record in a single transaction, and idempotency keyed on document id so retries and rebalances consume each document’s numbers exactly once. With the ordered resource centralized and the parallel work fanned out around it, the pool scales throughput while the uniqueness guarantee holds, and every produced page keeps a citation that resolves to one and only one page.

Frequently Asked Questions

Can I avoid a shared counter by giving each worker a pre-assigned block?

Yes, static partitioning works and avoids runtime contention: assign worker A numbers 1–1,000,000, worker B 1,000,001–2,000,000, and so on. The trade-off is gaps — a worker that finishes its documents without exhausting its block leaves the unused tail as a gap you must document — and inflexibility under rebalancing. A shared atomic counter with range claims gives gap-free numbering and tolerates a resized pool, which is why it is the more common production choice, but pre-assigned blocks are a legitimate alternative when documented.

Is a Redis INCRBY safe enough for Bates allocation?

The increment itself is atomic and collision-free, but INCRBY alone does not record the doc_id → range mapping needed for idempotent retries, and Redis durability must be configured (AOF with a suitable fsync) so a crash does not lose the high-water mark. Pair the INCRBY with a claims hash written in the same logical operation and enable persistence, and it is a solid allocator. Without the claims record, a retry after a crash can double-consume.

Why do collisions cluster at batch boundaries and restarts?

Because those are the moments multiple workers initialize or resume at the same counter value. With local counters, every worker that starts a fresh batch seeds from the same “next number,” so the first claims of each batch collide. Centralizing the counter removes the shared seed entirely — there is only one next number, and only one worker can advance past it at a time.

Related

• Bates Numbering & Endorsement — the endorsement subsystem this allocator drives.
• Diagnosing Bates Gaps & Family Breaks — reconciling gaps that block-partitioning or holds leave behind.
• Async Batch Processing Design — the concurrency model whose worker pool this serializes access for.
• Production Validation & QC — the gate that proves uniqueness after the fact.

For distributed-counter semantics, see the PostgreSQL sequence documentation and the Redis INCR documentation.

Up one level: Bates Numbering & Endorsement — the subsystem that stamps every produced page.