Deduplicating Lineage Events at Scale

Part of: Streaming and Incremental Lineage Capture

Duplicate lineage events arrive from every direction: a retried HTTP call, an at-least-once broker delivery, a job rerun after a transient failure, an operator who ran the backfill twice. Each duplicate inflates counts, creates phantom derivation edges, and makes a graph traversal return the same ancestor several times. This how-to makes duplicates harmless by construction rather than by cleanup, because cleanup at scale is a job that never finishes.

The principle throughout: identity is computed, not assigned. An event whose identifier is generated at emit time is a different event every time it is emitted, no matter how identical its content. An event whose identifier is derived from its content is the same event however many times it arrives.

Prerequisites

  • A stable event schema with a clear separation between semantic content and transport metadata.
  • A store supporting an atomic upsert or a unique constraint.
  • Producers able to compute a hash before emitting.
  • Agreement on what “the same event” means for your system — the hard part.

Deciding What Counts as the Same Event

The identifier is a hash over chosen fields, and choosing them is the entire design. Include too much and genuine duplicates get distinct identifiers; include too little and distinct events collapse into one.

What goes into the identity hash Semantic fields are hashed; transport and observation metadata are excluded; including retry counts causes under-merging and excluding parameters causes over-merging. IN THE HASH run id (the logical run, not the attempt) activity type input entity ids + versions output entity id + version parameter set digest OUT OF THE HASH emit timestamp retry / attempt counter producer hostname, process id broker offset, partition trace / correlation id too much in the hash duplicates survive — counts inflate too little in the hash real events vanish — worse

The asymmetry in the bottom row should drive the choice. Surviving duplicates are visible, annoying and fixable; collapsed distinct events are invisible and unrecoverable, because the second event was discarded and nothing records that it existed. When uncertain, include the field.

Write the field list down somewhere a reader will find it, next to the code that computes the hash. The list is a semantic contract — it states what your system considers to be the same event — and it will be consulted by everyone who later wonders why two records they expected to merge did not. A hash function whose inputs are only discoverable by reading the implementation invites everyone to guess, and the guesses will differ.

Treat changes to the list as breaking changes. Adding a field to the hash means every event emitted afterwards has a different identifier from the equivalent event emitted before, so the same logical event can exist twice across the boundary. That may be acceptable, but it is a migration rather than a tweak, and it needs the version marker that lets a query tell the two eras apart.

The parameter digest is the field most often omitted and most often needed. Two runs of the same activity over the same inputs producing the same output are genuinely distinct events if their parameters differed — that is the case where somebody re-ran with a corrected tolerance, and collapsing it hides the correction.

Timestamps Are the Classic Mistake

Almost every first implementation includes the timestamp, and almost every one has to remove it.

A retry emits at a different instant than the original, so a hash including the emit timestamp gives them different identifiers and the deduplication does nothing at all. The failure is silent — the mechanism is present, the code looks right, and duplicates continue to accumulate.

The fix is to distinguish emit time from occurrence time and hash neither. Occurrence time is a property of the activity, which is already identified by the run identifier; emit time is transport metadata. Store both on the event for querying and keep both out of the identity.

Where an activity genuinely recurs — a scheduled job producing a new event each run over unchanged inputs — the run identifier is what distinguishes them, and it should be a deterministic function of the schedule slot rather than of the wall clock. A daily job’s run identifier should be the same for both attempts on the same day and different across days, which is exactly what a date-derived identifier gives.

Where to Enforce Uniqueness

Enforcement can sit in the producer, the consumer, or the store, and only the last is reliable.

Where uniqueness enforcement actually holds Producer and consumer caches are defeated by restarts and by parallelism; only a constraint in the store holds under every failure mode. producer cache defeated by: restart, a second producer instance partial consumer cache defeated by: rebalance, replay, cache eviction partial store constraint defeated by: nothing in normal operation authoritative Caches are an optimisation: they save work. The constraint is the correctness guarantee. Use both — but never rely on a cache for the guarantee, and never skip the constraint. INSERT … ON CONFLICT (event_id) DO NOTHING — one statement, no coordination

The caches remain worth having for volume reasons. A producer-side cache that suppresses the obvious back-to-back retry saves a round trip, and at high event rates that is most of the traffic. It just must not be where correctness lives.

Use DO NOTHING rather than DO UPDATE unless there is a specific reason to prefer late arrivals. Updating on conflict means a duplicate silently rewrites the stored event, which turns an idempotent operation into a last-writer-wins one and reintroduces ordering sensitivity through the back door.

Detecting the Duplicates You Are Still Getting

A deduplication scheme that works produces no visible output, which is indistinguishable from one that is not running.

Count conflicts. Every suppressed duplicate is an observable event, and the rate is a genuinely useful operational signal — a sudden rise means a producer is retrying more than it used to, which usually means something upstream is failing intermittently.

Run a periodic scan for semantic duplicates that the hash did not catch: events with different identifiers but identical semantic content. A non-zero result means a field is in the hash that should not be, and this scan is the only way that mistake surfaces.

Distinguish the two kinds of conflict in the counter. A conflict where the incoming event is byte-identical to the stored one is a harmless retry; a conflict where the identifiers match but the payloads differ is a genuine problem, because it means two semantically different events collided under your field selection. The second should be rare and should be alerted on individually rather than counted, since each occurrence is evidence that the hash inputs are wrong.

Record both figures over time rather than alerting on a threshold. Duplicate rates are naturally spiky, and the useful reading is the trend and the correlation with deployments, not any individual day’s number.

Keeping the Index Affordable

A unique constraint on a high-cardinality identifier is an index that grows without bound, and at sustained event rates that index becomes the cost centre.

Bounding the deduplication index An unbounded unique index grows forever; partitioning by time and keeping only recent partitions indexed bounds the cost at the price of a finite dedup horizon. one unbounded unique index protects against duplicates at any age grows forever · writes slow steadily correct, eventually unaffordable time-partitioned, bounded horizon protects within the horizon only index size stays flat · writes stay fast the practical choice above ~10⁸ events Set the horizon from your maximum plausible retry delay, then double it. Backfills exceed any horizon — dedup them explicitly, not by constraint.

The horizon is the honest name for what a bounded index gives you. Duplicates arriving inside it are suppressed; duplicates arriving outside it are not, and the design must state that rather than implying an absolute guarantee it no longer provides.

The backfill caveat is the one that catches people. Reprocessing a year of history against a thirty-day horizon will duplicate everything older than thirty days, because the constraint that would have caught it no longer covers those partitions. Run backfills through an explicit reconciliation that compares against the existing rows rather than relying on the insert path.

Detach rather than delete old partitions where the store supports it. A detached partition retains the data for querying while dropping the index maintenance cost, which is the expensive half.

Verification

Emit the same event a thousand times concurrently from several processes and assert the store holds exactly one. Concurrency matters here — a scheme that works serially can still race on a check-then-insert implementation, and the race only appears under parallelism.

Assert the negative: two events differing only in a parameter value must produce two rows. This is the assertion that catches an over-aggressive hash, and it is the one that protects against the unrecoverable failure mode.

Assert stability of the hash across producer versions by checking a fixture event’s identifier against a recorded constant. A serialisation change that reorders fields silently changes every identifier and makes the entire history re-duplicate on the next emit.

Gotchas & edge cases

  • Field order in the hash input matters. Serialising a map in iteration order gives different identifiers on different runtimes. Sort keys explicitly, or hash a canonical form.
  • Floating-point parameters do not hash stably. A tolerance of 0.1 may serialise differently across languages. Round and format explicitly before hashing.
  • Unicode normalisation bites on names. The same dataset name in two normalisation forms hashes differently. Normalise strings before hashing, or use identifiers rather than names.
  • A backfill is not a duplicate. Reprocessing history legitimately re-emits events that should collapse onto the originals — which is what you want — but a backfill that also changes content will silently do nothing under DO NOTHING. Backfills that correct data need an explicit supersession, not an upsert.
  • Hash collisions are not the risk. With a modern hash the collision probability is negligible; every real failure in this area is a field-selection mistake. Do not spend design effort on collisions.