Deduplication

Deduplication in Queen is exact: the verdict is always computed in PostgreSQL, with no sampling and no “best effort” qualifier. Within a partition and within the configured window, a transactionId that has already been stored writes nothing and returns status: "duplicate" with the original message’s id. Probabilistic structures appear only where they make an exact answer arrive faster, never where they could change it.

It is also on by default. queen.queues.dedup_window_seconds defaults to 3600, and only an explicit 0 disables it.

Here is the observable behaviour:

const first = await client
  .queue('payments')
  .partition('customer-42')
  .push([{ transactionId: 'order-9137-paid', data: { orderId: 9137, amount: 99.5 } }])

const retry = await client
  .queue('payments')
  .partition('customer-42')
  .push([{ transactionId: 'order-9137-paid', data: { orderId: 9137, amount: 99.5 } }])
// retry[0].status is 'duplicate': the second push wrote nothing
// and answers with the first message's id.

The rest of this page is how that is made true and, more usefully, why the fast paths cannot break it.

Three layers, one authority

Layers 1 and 2 exist because a duplicate that never reaches SQL costs nothing. Layer 3 is the verdict. Layers 1 and 2 both take the first occurrence and make later ones followers that inherit the leader’s final result, including the case where the leader itself turns out to be a duplicate of something already stored, in which case the followers report the pre-existing message id too.

Layer 1 compares queue \x1f partition \x1f transactionId. Layer 2 compares the 16-byte xxh3_128 hash of the transactionId, the same identity SQL compares, so a broker-local collision behaves exactly like a SQL one.

The probe: before allocation, under the lock

Layer 3 is a probe that runs before an offset is allocated, while the partition row lock is held. That ordering is the whole correctness argument.

SELECT last_offset, txns_start INTO v_last, v_txns_start
FROM queen.log_partitions WHERE id = v_pid
FOR UPDATE;

v_now := clock_timestamp();
v_from := GREATEST(COALESCE(p_verified, -1), v_txns_start - 1);

IF v_last > v_from THEN
    SELECT jsonb_agg(jsonb_build_object('i', d.idx, 'off', d.off) ORDER BY d.idx)
    INTO v_dups
    FROM (
        SELECT ih.idx AS idx, MIN(t.base_offset + th.idx) AS off
        FROM queen.log_txns t
        CROSS JOIN LATERAL queen.log_unnest_hashes(t.hashes) th
        JOIN queen.log_unnest_hashes(p_hashes) ih ON ih.h = th.h
        WHERE t.partition_id = v_pid
          AND t.end_offset > v_from
          AND t.created_at >= v_now - make_interval(secs => v_window)
        GROUP BY ih.idx
    ) d;
    ...

Read it as four claims:

1. The row lock is the per-partition write serializer. No concurrent pusher can commit new rows into the probed span while it is held, so probe-then-allocate is race-free. This is why the lock is taken with an explicit SELECT ... FOR UPDATE before the probe rather than left to the allocator UPDATE that follows.
2. A duplicate writes nothing. No allocator bump, no segment insert, no log_txns insert. So the duplicate verdict needs no rollback, and therefore no savepoint. That matters in a bundle: the other partitions’ writes commit untouched. The retired engine detected duplicates through a unique-index violation, which forced a per-segment subtransaction to contain the rollback.
3. MIN picks the original occurrence. One incoming hash can match several historical rows (for instance if data was pushed while deduplication was off), and the response must carry the first one.
4. The span has two lower bounds. txns_start - 1 is the purge watermark: rows below it are gone, so there is nothing to compare against, and a redelivery of a hash older than the sidecar window is accepted as new. p_verified is the broker’s vouched watermark, described below.

log_txns is written on every push regardless of the window, because ack-by-transactionId resolves through it. Turning deduplication off skips the probe, not the write. See the storage model.

Sharded per-partition locks

Two distinct locks carry the word “per-partition” in this path, and it is worth separating them.

In PostgreSQL, the log_partitions row lock. It is per partition by construction, so two partitions never contend, and the probe of one partition never blocks a push to another. The bundle pre-lock takes them all in ascending id order, which is the one global lock order shared with acks and retention.

In the broker, the dedup cache’s map is a RwLock<HashMap<pid, Arc<Mutex<Entry>>>>. The common path read-locks the map only long enough to look up and clone the handle, then does all its work under the per-entry mutex. This replaced one global mutex around the whole map, which under uniform load serialized every flush behind whichever partition happened to be resizing. The sharding is effectively free because the fusion layer already flushes a given partition single-flight and partitions are shard-affine: the only cross-thread contention on a partition’s entry is eviction, driven by other partitions’ flushes.

The broker cache, and what it is allowed to do

The cache has exactly one load-bearing output: the p_verified watermark sent with a push. It means “the broker vouches that none of this bundle’s hashes occurs at or below offset p_verified”, which lets SQL shrink its probe to (p_verified, last_offset].

p_verified = -1 means “cannot vouch: probe the whole window”, and that answer is always sound. So:

The validity rule the cache must satisfy to vouch: it knows every hash in (hydrated_from, verified_upto], and hydrated_from is at or below the window start. Three structural properties keep that true rather than merely intended:

• Entries are only born complete. Hydration is always a full-window fetch: SELECT base_offset, end_offset, created_at, hashes FROM queen.log_txns WHERE partition_id = $1 AND created_at >= now() - $2, with five seconds of clock-skew slack added on the safe side (extra old rows only widen coverage).
• An interleave gap immediately disqualifies the entry. After a successful push returning base B, if B == verified_upto + 1 the bundle’s hashes are appended and the watermark advances. If B > verified_upto + 1, another broker interleaved: the push itself was still correct, because SQL probed past our watermark, but the cache no longer knows everything below B, so it records the gap and answers -1 until it is rebuilt. An overlap (B <= verified_upto) is impossible under a monotone allocator and marks the entry for a full rebuild defensively.
• Expiry raises hydrated_from only past provably pre-window data. See the block model below.

Positive membership goes the other way. A hash present in the cache was committed within the window, but the caller never short-circuits on it. It routes the segment to SQL with p_verified = -1 for the authoritative verdict, because that is also the only way to obtain the original offsets the wire response needs. A local hit is therefore a hint that steers a segment to the full-window probe, never a decision. A hint that is a shade stale costs one extra SQL probe.

The cache also memoises each partition’s id, deduplication window and allocator watermark with a 30-second TTL. That TTL bounds how long a /configure window change can go unnoticed; a detected change forces a full rehydration, sticky until one succeeds, because the entry’s expiry bookkeeping was computed under the old window.

The steady-state consequence is easy to miss. A committed push advances verified_upto to its own last offset, so when the cache is warm p_verified equals the partition’s current last_offset, v_last > v_from is false, and the probe does not run at all: SQL takes the row lock and goes straight to the allocator UPDATE, the same write it would have performed with deduplication off. Only an offset gap left by another broker, a cold or rebuilding entry, a suppressed partition or a local hit routed at -1 reopens the probe, and then only across the span the cache cannot vouch for. Deduplication is not a per-push query; it is a per-push comparison the broker already made in memory.

How the hashes are stored

Not as a hash map. Each partition’s in-window hashes live in a time-ordered ring of immutable, sorted blocks plus one mutable arrival-order buffer. There is no per-hash membership map at all: on the exact path membership means “present in some surviving block”, found by binary search in each sealed block and a linear scan of the hot buffer. That path is reached only when the bloom front described below answers “maybe”.

Three invariants make that correct and cheap:

No refcounting. Two in-window segments carrying the same hash are a real case (after a window reconfiguration, or across brokers), and a refcount map existed to stop the first one’s expiry from un-knowing the second. Immutable blocks give that for free: a hash lives independently in every block containing it, and expiry drops whole blocks, so a cross-block duplicate stays known until its last containing block is dropped.

Block-granular expiry is sound. Blocks are time-ordered front to back, and a front block is dropped only when its entire span is stale. Every in-window hash therefore sits in a retained block, so the resident set is a superset of the in-window hashes. A superset can only produce a false local duplicate (which costs one extra probe), never a false “no duplicate”. And because a dropped block is entirely pre-window, raising hydrated_from to its highest offset discards only pre-window offsets.

Allocation is bounded. The hot buffer grows by ordinary doubling but is sealed the instant it reaches the block capacity, which is a power of two (4096 hashes, a 64 KiB block), so the seal is a no-copy hand-off. The largest allocation the cache can ever make is one block. The previous HashMap doubled its table toward the full window size, so enough uniformly loaded partitions crossing that threshold in lockstep produced synchronised, very large rehash bursts. A capped 64 KiB buffer, sealed on a staggered per-partition schedule, cannot.

The byte accounting is deliberately coarse but dominated by the real 16 bytes per hash, so the LRU budget (QUEEN_DEDUP_CACHE_MB, default 512) reflects the true footprint.

The bloom front

Each entry fronts the exact ring with a temporal ring of generational blocked bloom filters: 16 bits per hash, k = 7, with all seven probe bits inside one 64-byte block. A definitive miss therefore costs one cache line per live generation and touches neither the hot buffer nor any sealed block. A “maybe” falls through to the exact path, which stays the only authority: a false positive costs one exact check, and a local hit is still routed to SQL as before.

Blooms have no false negatives, and a generation is dropped from the front only when its whole max_created_ms watermark is pre-window, so the soundness argument is the same whole-block expiry rule as the exact ring. Generation capacities tier up by a factor of eight from the 4096-hash block capacity to a ceiling of one million hashes, so an idle partition carries one small filter and a full-rate window settles at three or four live generations.

Before the front existed, probing absent cost a linear scan of the hot buffer plus one binary search per sealed block, thousands of memory touches per hash once a high-rate window had accumulated hundreds of blocks: measured on 2026-07-31 at 60% of broker CPU at 1M msg/s with a 300 s window. The filter costs about 2 bytes per hash on top of the exact 16.

Under memory pressure

The naive behaviour at the cap is a thrash loop: a push to an evicted partition re-hydrates its whole window, which evicts a hot partition, which re-hydrates, and so on. Multi-megabyte hydrations in a cycle collapsed throughput.

So a full rehydration is gated, and a partition that fails the gate enters a suppressed state where it simply answers -1:

• A fit test with hysteresis. A rebuild is admitted only if everything except this partition’s own resident bytes, plus the estimated footprint, stays under 90% of the cap. The headroom is what stops an admission from immediately forcing eviction of the set it just joined: it converts ping-pong into a stable resident set plus suppressed overflow.
• A 30-second cooldown. A suppressed partition is not re-tested on every flush; it serves the cooldown first. Long enough not to re-thrash a resident set churning at the cap, short enough to recover within seconds once pressure eases: a window shrinks via /configure, offered load drops, or a peer leaves and frees the shared budget.
• A recent-use eviction guard. A partition used within the last five seconds is never evicted to admit another; the newcomer is suppressed instead.
• One warning per minute, process-wide, plus a gauge for how many partitions are suppressed.

Brand-new partitions estimate an empty window and are therefore never suppressed on first contact. Cheap admissions (a resident entry that is vouching, or a resident entry with an interleave gap) are always allowed and never gated.

Suppression is purely a broker-resource trade. It cannot change a verdict, because the server-side probe is authoritative for every partition, suppressed or not. The auxiliary bookkeeping maps (cooldown deadlines, last-footprint hints) are soft-capped at 100,000 entries and pruned beyond that, so a workload churning through unboundedly many partition names cannot leak them; the only cost of a reset is a re-measured footprint estimate.

Multi-broker behaviour

Nothing about deduplication needs coordination between brokers. Two brokers pushing the same transactionId to the same partition serialize on the same PostgreSQL row lock, and whichever probes second sees the first one’s committed log_txns row. The broker cache is per process and its worst case (an interleave it did not observe) degrades it to -1, which is the full probe.

The edges

The /configure row is the one that used to catch people, and it changed direction in 1.6.0. Until then omitting a key reset it, so a queue deliberately created with deduplication off got a one-hour window back the next time anyone called /configure without naming it. Now an omitted key is left alone. The reset survives in two places, both of them deliberate: a create, where there is nothing to keep, and a body carrying "mode": "replace", which is what queenctl apply -f sends because a manifest means the whole configuration.

The fire of a timer does not probe the window

A timer carries a fixed txn, minted when it was scheduled, and it is tempting to read that as a deduplication net across the fire. It is not one, and the distinction matters because it decides where the guarantee actually comes from.

The exactly-once property of a fire is that the DELETE of the staging row and the push of the frame are one transaction. If it commits, the row is gone and the message is in the log; if it rolls back, neither happened. Nothing about that argument mentions a window, a hash or a probe, which is why correctness never depends on how dedupWindowSeconds is configured on the destination queue.

The fixed txn is at most a secondary net, and today it is not even that. The fire calls the allocator with the partition’s own last-verified marker rather than with -1, so the probe described above does not run for it: queen.log_txns keeps its hashes in a BYTEA column with no index, so looking for one txn costs the same unrolling of the partition’s retained window as looking for all of them, and paying that inside the serializer would charge it to ordinary producers.

The consequence is stated rather than hidden. Re-scheduling or re-publishing a timer whose fire has already committed produces a second message in the log, and no layer below you stops it. A cancel that answers absent may mean exactly that case, which is why absent is documented as “no longer pending” and never as “not delivered”.