Real-Time Deduplication in Flink: State, Redis, or Bitmap?

Deduplication needs a more precise definition than “drop this ID if we have seen it.” Whose ID is it? How long do we remember it? Does the guarantee span jobs? After a crash, are duplicates acceptable, or is loss acceptable? This article uses Flink 1.15 DataStream as its baseline and discusses exact deduplication within a finite retention period.

Write down the business boundary first

Suppose a producer guarantees that event_id is unique within its source and duplicates arrive no more than a day late. (source, event_id) is a possible logical key. But should replaying a week-old input count as a duplicate? A one-day TTL cannot provide deduplication across an arbitrary historical range.

Estimate capacity before implementation. At 100,000 unique events per second and one day of retention, there are about 8.64 billion active keys. Even an assumed 32 bytes per key gives roughly 276 GB in decimal units, before serialization, indexes, timestamps, and backend overhead. This is an order-of-magnitude example, not a production benchmark.

Keyed State: recover state with the job

For a single Flink pipeline, keyBy on the complete deduplication key and one seen flag per key is often the most direct design. Once checkpointed, source positions and deduplication state can recover consistently. End-to-end exactly-once output still depends on the sink’s transaction or idempotency protocol.

onEvent(event):
  if seen.value() is absent:
    seen.update(true)
    emit(event)

This pseudocode describes only the decision. In Flink 1.15, State TTL is based on processing time. Visibility of expired values, TTL refresh behavior, and background cleanup are separate choices. Logical expiration does not immediately shrink state files. Flink 1.15: Working with State

If the contract requires event-time retention, design time buckets and timers explicitly, including stalled watermarks, late data, and bucket boundaries. Processing-time TTL is not an event-time window. Retention planning must also account for records replayed after recovery, the latest permitted arrival, and clock boundaries.

Redis: shared decisions introduce an external consistency problem

Redis is convenient when several services need a shared deduplication decision. SET key 1 NX EX 86400 combines conditional insertion and expiration in one command, avoiding a separate check-then-write race. Redis SET

An atomic Redis command does not atomically complete business processing:

1. The Redis write succeeds.
2. The job crashes before sending the event downstream.
3. Recovery replays the event, finds the Redis marker, and drops it.

This failure window can lose the business outcome. Reversing the order can create duplicate output, so ordering must be designed together with the recovery protocol. If reliable delivery happens before recording completion, the sink needs event-key idempotency to absorb retries before the completion marker is written. If the design reserves the event first, persist distinct pending and completed states, then retry delivery or reconcile after recovery. Pending must not be treated as completed and discarded.

Adding an idempotent sink alone does not repair the loss window above: the event never reached the sink. Calling a Redis key “completed” requires evidence of completion, not merely receipt.

Also decide what happens on a Redis timeout: block, quarantine, or allow processing. Unbounded retries can amplify tail latency; allowing processing weakens deduplication; dropping the event risks data loss. The choice depends on the data’s use. Billing events and exploratory metrics should not inherit the same policy by accident.

Bitmap: compression does not solve identity

RoaringBitmap represents integer sets and uses compressed representations suited to different distributions. Its memory benefit depends on the distribution of IDs, not just their count. RoaringBitmap repository

When input already has stable, collision-free integer IDs, time-bucketed bitmaps can be useful. Hashing strings into 32-bit integers introduces collisions and may classify distinct events as duplicates. A longer hash reduces the probability; it does not make the mapping mathematically exact. Strict use cases need collision-free mapping or a secondary verification step.

Daily buckets also create a midnight boundary: a retry today may refer to yesterday’s event. Query the buckets required by the business retention interval, then delete those no longer needed. Coarse buckets retain data longer; fine buckets increase metadata, lookup, and serialization overhead.

Choose a design and test its guarantees

Load tests should go beyond steady-state throughput. Include hot sources, duplicate bursts, replay beyond retention, state recovery, and sink failures. For correctness, use a known set of unique events and count duplicate and missing outputs separately. For performance, measure processing latency, checkpoint size, recovery time, and external request volume together.

When approaches behave differently under failure, first choose one that meets the delivery contract, then optimize its cost. An incorrectly discarded legitimate event is harder to spot in a report than a slightly larger state footprint.

References

• Flink 1.15: State and TTL .
• Redis: SET command .
• RoaringBitmap implementation and documentation .