Suppression — Idempotency and Deduplication

Suppression — Idempotency and Deduplication #

Suppression is the coordination mechanism that eliminates duplicates. In distributed systems, duplication is the default — not the exception. Networks retry failed requests. Consumers reprocess events after crashes. Batch jobs rerun after partial failures. The question is not whether duplicates will occur, but how to ensure they produce no observable side effect.

A Suppression mechanism must satisfy:

Idempotency: executing an operation N times produces the same result as executing it once. The second and subsequent executions are no-ops. Deduplication window: how long must the system remember that an operation was already processed? Infinite memory is not practical — every deduplication mechanism has a bound. Duplicate detection: how does the system determine that this execution is a duplicate of a prior execution?

Why Duplication Is Inevitable #

At-least-once delivery: all practical message delivery systems (Kafka, SQS, RabbitMQ) guarantee that a message is delivered at least once — never zero times, possibly more than once. Exactly-once delivery is either impossible (FLP impossibility applied to message delivery) or expensive (requires durable state and coordination at the delivery layer).

Producer sends message M.
Broker delivers M to consumer.
Consumer processes M.
Consumer crashes before acknowledging.
Broker re-delivers M.
Consumer processes M again.

This is not a bug — it is the correct behavior of an at-least-once system. The consumer must be idempotent.

Network retries: a client sends a request. The network times out. The client retries. The first request arrived but the response was lost. The server processes the request twice.

Distributed sagas: a saga step completes, but the orchestrator crashes before recording the completion. On recovery, the orchestrator re-sends the step command. The step is executed twice.

Idempotency Keys #

The most general idempotency mechanism is the idempotency key: a unique, client-generated identifier for each logical operation. The server stores (operation result, idempotency key) and returns the stored result for any duplicate request with the same key.

Design #

Client generates:
  idempotency_key = UUID v4  (or deterministic: hash(user_id, order_id, timestamp))

Client sends:
  POST /charges
  Idempotency-Key: 7f3c9e12-...
  { amount: 2000, currency: "usd", customer: "cus_abc" }

Server behavior (first request):
  1. Check: does (idempotency_key, endpoint) exist in idempotency_store? No.
  2. Execute: charge customer $20.
  3. Store: (idempotency_key, endpoint, response_body, expires_at) in idempotency_store.
  4. Return: 201 Created { charge_id: "ch_xyz" }

Server behavior (duplicate request):
  1. Check: does (idempotency_key, endpoint) exist in idempotency_store? Yes.
  2. Return: stored response 201 Created { charge_id: "ch_xyz" }
  (Charge not re-executed.)

Database Implementation #

-- Idempotency store table
CREATE TABLE idempotency_keys (
    idempotency_key  UUID        NOT NULL,
    endpoint         VARCHAR(64) NOT NULL,
    response_code    INT         NOT NULL,
    response_body    JSONB       NOT NULL,
    created_at       TIMESTAMPTZ NOT NULL DEFAULT NOW(),
    expires_at       TIMESTAMPTZ NOT NULL,
    PRIMARY KEY (idempotency_key, endpoint)
);
CREATE INDEX ON idempotency_keys (expires_at); -- for cleanup job

-- In the handler:
WITH insert_attempt AS (
    INSERT INTO idempotency_keys (idempotency_key, endpoint, response_code, response_body, expires_at)
    VALUES ($1, $2, $3, $4, NOW() + INTERVAL '24 hours')
    ON CONFLICT (idempotency_key, endpoint) DO NOTHING
    RETURNING response_code, response_body
)
SELECT response_code, response_body FROM insert_attempt
UNION ALL
SELECT response_code, response_body FROM idempotency_keys
WHERE idempotency_key = $1 AND endpoint = $2
LIMIT 1;

The ON CONFLICT DO NOTHING handles races: if two threads receive the same idempotency key simultaneously, one inserts and one gets nothing — both then read the stored response.

Critical: Transactional Scope #

The idempotency key insert and the business operation must be in the same database transaction:

func (s *PaymentService) Charge(ctx context.Context, req ChargeRequest) (*ChargeResponse, error) {
    tx, _ := s.db.Begin(ctx)
    defer tx.Rollback(ctx)

    // 1. Check and reserve idempotency key (within transaction)
    existing, err := tx.QueryRow(ctx,
        `INSERT INTO idempotency_keys (idempotency_key, endpoint, status, expires_at)
         VALUES ($1, $2, 'processing', NOW() + INTERVAL '24h')
         ON CONFLICT (idempotency_key, endpoint) DO UPDATE SET status = idempotency_keys.status
         RETURNING status, response_body`,
        req.IdempotencyKey, "/charges")
    if existing.Status == "complete" {
        return existing.ResponseBody, nil // Duplicate — return cached response
    }
    if existing.Status == "processing" {
        return nil, ErrConcurrentRequest // Race: another thread is processing
    }

    // 2. Execute business logic (within same transaction)
    charge, err := s.stripe.CreateCharge(ctx, req.Amount, req.Customer)
    if err != nil {
        return nil, err // tx.Rollback releases idempotency key
    }

    // 3. Record result and mark key as complete (within same transaction)
    tx.Exec(ctx,
        `UPDATE idempotency_keys SET status = 'complete', response_body = $1
         WHERE idempotency_key = $2`,
        charge, req.IdempotencyKey)

    tx.Commit(ctx)
    return charge, nil
}

If the transaction rolls back (business logic fails), the idempotency key insert also rolls back. The key is not marked as “complete.” A retry with the same key will re-execute the business logic. This is correct: only successful operations should be deduplicated.

Key Design: Client-Generated vs Server-Assigned #

Client-generated (UUID): the client is responsible for generating a new UUID for each new logical request and reusing the same UUID for retries. Simple, requires no server round-trip before the first attempt.

Deterministic (hash-based): key = hash(user_id + operation_type + entity_id + timestamp_day). Allows the client to reconstruct the idempotency key after a crash, without storing it locally. Useful for batch retry scenarios.

Server-assigned (token): the client first calls POST /idempotency-tokens to get a token, then uses the token for the actual request. Adds a round-trip but allows the server to reserve capacity before the operation starts.

Stripe uses client-generated idempotency keys. They recommend UUIDs, with a retention window of 24 hours (if the same key is not seen within 24 hours, it is garbage-collected from the idempotency store).

Database-Level Idempotency #

For operations that map to database inserts, unique constraints provide idempotency without an explicit idempotency key store:

-- Payment records: charge_id is unique per successful payment
CREATE TABLE payments (
    id          SERIAL PRIMARY KEY,
    charge_id   VARCHAR(64) UNIQUE NOT NULL,  -- Stripe charge ID
    user_id     UUID        NOT NULL,
    amount      INT         NOT NULL,
    created_at  TIMESTAMPTZ NOT NULL DEFAULT NOW()
);

-- Idempotent insert: second insert with same charge_id is a no-op
INSERT INTO payments (charge_id, user_id, amount)
VALUES ('ch_xyz', $user_id, $amount)
ON CONFLICT (charge_id) DO NOTHING;

This is simpler than an explicit idempotency key table when the natural key of the resource (Stripe charge ID, event UUID, order ID) is available and unique.

For upserts (create or update):

INSERT INTO seat_holds (seat_id, user_id, expires_at)
VALUES ($seat_id, $user_id, NOW() + INTERVAL '10 min')
ON CONFLICT (seat_id) DO UPDATE
SET user_id = EXCLUDED.user_id,
    expires_at = EXCLUDED.expires_at
WHERE seat_holds.user_id = EXCLUDED.user_id;  -- Only update if same user

ON CONFLICT DO UPDATE combined with a WHERE clause implementing business rules turns any insert into an idempotent upsert.

Bloom Filters for Deduplication #

When the deduplication set is large (billions of URLs for a web crawler, billions of event IDs for an analytics pipeline), storing every seen ID in a database table is impractical. Bloom filters provide space-efficient approximate membership testing with a controlled false positive rate.

A Bloom filter is a bit array of m bits with k hash functions. To add an item:

1. Hash the item with all k hash functions.
2. Set the bits at each of the k positions to 1.

To check membership:

1. Hash the item with all k hash functions.
2. If all k bits are set to 1, the item may be in the set (false positive possible).
3. If any bit is 0, the item is definitely not in the set (no false negatives).

from bitarray import bitarray
import hashlib

class BloomFilter:
    def __init__(self, m, k):
        self.m = m
        self.k = k
        self.bits = bitarray(m)
        self.bits.setall(0)

    def _hash_positions(self, item):
        positions = []
        for i in range(self.k):
            h = hashlib.sha256(f"{i}:{item}".encode()).hexdigest()
            positions.append(int(h, 16) % self.m)
        return positions

    def add(self, item):
        for pos in self._hash_positions(item):
            self.bits[pos] = 1

    def might_contain(self, item):
        return all(self.bits[pos] for pos in self._hash_positions(item))

False positive rate: with m bits and n items inserted, the false positive rate is approximately:

p ≈ (1 - e^(-kn/m))^k

For p = 1% and n = 1 billion URLs: m ≈ 9.6 billion bits = 1.2 GB. A Redis BITFIELD holding 1.2 GB for deduplication of 1 billion items — orders of magnitude more efficient than storing all URLs.

Practical parameters:

• Target p = 0.1% → m/n ≈ 14.4 bits/item
• Target p = 1% → m/n ≈ 9.6 bits/item
• Target p = 5% → m/n ≈ 6.2 bits/item

Limitation: Bloom filters cannot remove items (setting bits back to 0 would affect other items sharing those bit positions). Use a Counting Bloom filter if deletion is required.

Bloom Filter in Web Crawler #

class URLFrontier:
    def __init__(self, redis_client, expected_urls=1_000_000_000):
        self.redis = redis_client
        # Pre-sized Bloom filter: 9.6 bits/URL for 1% false positive rate
        self.bloom_size = int(expected_urls * 9.6)
        self.bloom_key = "crawler:seen_urls"
        self.queue_key = "crawler:url_queue"

    def add_url(self, url: str) -> bool:
        """Returns True if URL was added (not seen before), False if duplicate."""
        # Bloom filter check (fast, in-memory, approximate)
        positions = self._hash_positions(url)
        if self._all_bits_set(positions):
            return False  # Probably duplicate (may be false positive)

        # Set bits (add to bloom filter)
        pipe = self.redis.pipeline()
        for pos in positions:
            pipe.setbit(self.bloom_key, pos, 1)
        pipe.rpush(self.queue_key, url)
        pipe.execute()
        return True

For a small fraction of URLs, the Bloom filter returns a false positive (URL appears seen when it has not been). These URLs are missed. For a web crawler, this is acceptable — the false positive rate is configurable, and missing 1% of URLs does not significantly affect crawl quality.

For a payment deduplication system, false positives would cause charges to be silently dropped — unacceptable. Use a database unique constraint with 100% accuracy instead.

The Outbox Pattern: Exactly-Once Event Publishing #

The outbox pattern solves a specific Suppression problem: how to publish an event to a message broker exactly once when the event is triggered by a database write.

The naïve approach fails:

// BROKEN: not atomic
func (s *OrderService) CreateOrder(ctx context.Context, order Order) error {
    _, err := s.db.Insert(ctx, "orders", order)
    if err != nil {
        return err
    }
    // If this crashes, the order exists in DB but the event is never published
    return s.kafka.Publish(ctx, "order.created", OrderCreatedEvent{OrderID: order.ID})
}

If the service crashes after the database write but before the Kafka publish, the order exists in the database but no event was published. The order state is inconsistent with the event stream.

The Pattern #

// CORRECT: outbox pattern
func (s *OrderService) CreateOrder(ctx context.Context, order Order) error {
    tx, _ := s.db.Begin(ctx)
    defer tx.Rollback(ctx)

    // 1. Write order to database
    _, err := tx.Insert(ctx, "orders", order)
    if err != nil {
        return err
    }

    // 2. Write event to outbox table (same transaction)
    _, err = tx.Insert(ctx, "outbox_events", OutboxEvent{
        AggregateType: "order",
        AggregateID:   order.ID,
        EventType:     "order.created",
        Payload:       json.Marshal(OrderCreatedEvent{OrderID: order.ID}),
        CreatedAt:     time.Now(),
    })
    if err != nil {
        return err
    }

    // Both writes commit atomically, or neither does
    return tx.Commit(ctx)
}

// Outbox poller (separate goroutine/process)
func (s *OutboxPoller) Poll(ctx context.Context) {
    for {
        events := s.db.Query(ctx,
            `SELECT id, event_type, payload FROM outbox_events
             WHERE published = false ORDER BY created_at LIMIT 100`)

        for _, event := range events {
            if err := s.kafka.Publish(ctx, event.EventType, event.Payload); err != nil {
                continue // Retry next poll cycle
            }
            s.db.Exec(ctx, `UPDATE outbox_events SET published = true WHERE id = $1`, event.ID)
        }

        time.Sleep(100 * time.Millisecond)
    }
}

Why the outbox pattern provides exactly-once semantics:

1. The order write and the outbox write are atomic — both succeed or neither does.
2. The poller reads unpublished events and publishes them to Kafka.
3. If the poller crashes after publishing but before marking as published, it re-publishes on next run. Kafka receives a duplicate.
4. Kafka consumers must be idempotent (using Kafka’s offset tracking or consumer-side deduplication with the event’s unique ID).

The outbox pattern converts the at-least-once delivery guarantee of Kafka into effectively-once semantics when combined with idempotent consumers.

Alternatives: CDC (Change Data Capture) #

Instead of a poller, use database CDC (e.g., Debezium for PostgreSQL via logical replication) to stream changes from the outbox table to Kafka:

# Debezium connector config
{
  "connector.class": "io.debezium.connector.postgresql.PostgresConnector",
  "database.hostname": "postgres",
  "table.include.list": "public.outbox_events",
  "transforms": "outbox",
  "transforms.outbox.type": "io.debezium.transforms.outbox.EventRouter",
  "transforms.outbox.table.field.event.key": "aggregate_id",
  "transforms.outbox.route.by.field": "event_type"
}

Debezium reads the PostgreSQL WAL (write-ahead log) and publishes changes to Kafka. No polling latency (sub-second delivery). No poller to maintain. The CDC connector provides exactly-once delivery if configured with Kafka Connect’s exactly-once support.

Kafka Idempotent Producer #

Kafka’s idempotent producer (KIP-98) implements exactly-once message delivery at the broker level:

Each producer is assigned a producer ID (PID) by the broker. Each message is tagged with (PID, sequence_number):

producer, _ := kafka.NewProducer(&kafka.ConfigMap{
    "bootstrap.servers": "kafka:9092",
    "enable.idempotence": true,  // Enables PID + sequence numbers
})

The broker maintains a state machine per (PID, partition): the last committed sequence number. If a message arrives with sequence number ≤ last committed, it is a duplicate and is dropped. If a message arrives with sequence number = last_committed + 1, it is accepted.

Exactly-once semantics (EOS) for Kafka Streams: Kafka transactions extend the idempotent producer to atomic multi-partition writes and consumer offset commits:

producer.BeginTransaction()
producer.Produce(&kafka.Message{
    TopicPartition: kafka.TopicPartition{Topic: &"output", Partition: 0},
    Value:          processedValue,
})
producer.SendOffsetsToTransaction(consumerOffsets, consumerGroupMetadata)
producer.CommitTransaction()

This atomically:

• Publishes the output message to output topic.
• Commits the consumer offset for the input message.

If the transaction aborts (application crash, broker unavailability), both the output message and the offset commit are rolled back. The consumer reprocesses the input message on restart and re-publishes the output. The output topic consumer sees the message exactly once because aborted transactions are invisible.

Suppression Summary #