Deduplicating Noisy Log Lines Before Indexing

A retry loop that logs on every attempt can produce a million identical lines in a minute. Storing all of them costs money and hides everything else in the index, and dropping them without care destroys the one thing they were telling you, which is the rate.

What deduplication is actually for

Three distinct problems get called deduplication and they want different solutions. Exact duplicates from delivery — the same line shipped twice because an agent retried after an acknowledgement was lost — are a correctness problem, and the answer is an idempotency key: a hash of (host, file, byte offset) or a producer-assigned id, checked against a set. Repetition from the application — the same statement firing ten thousand times because a dependency is down — is a volume problem, and the answer is collapse-with-a-counter. Near-duplicates that differ only in values — the same statement with different request ids — are a density problem, and the answer is sampling.

Conflating them is how pipelines lose data. Applying collapse-with-a- counter to delivery duplicates hides a shipping bug; applying idempotency-key dedup to application repetition drops nine thousand genuine occurrences of a real event. Decide which you have before choosing a mechanism. This page is about the second and third, which are the ones that dominate cost — the storage arithmetic is in what it costs to store and query event logs.

Choosing the dedup key

The key determines what “the same line” means, and the natural key for application repetition is the template id from template extraction, not the raw string. Raw-string dedup catches almost nothing, because the request id differs every time. Template dedup catches almost everything, because that is exactly what the template abstracts away.

But the template alone is too coarse. A timeout template firing for one downstream host is a different fact from the same template firing for forty, and a key of template alone collapses those into one record and loses the distinction that would have identified the cause. The workable key is the template id plus a small, deliberately chosen set of dimensions — typically service, host, severity and one or two identifiers with low cardinality such as the downstream service name. Never include anything unbounded: putting the request id in the key means every line is unique, and you have built an expensive identity function.

The second half of the key is the window. Dedup within a fixed window — one minute is a common choice — emits at most one record per key per window, which bounds the output rate at (number of active keys) ÷ (window) regardless of what the application does. That bound is the property you are buying, and it is what makes the cost of a log storm predictable.

A worked window

One service, 60-second windows, key = (template, service, downstream).

raw lines arriving (times in s within the window)

 t=0.4   T_timeout  svc=api  downstream=payments  req=8a2f
 t=0.9   T_timeout  svc=api  downstream=payments  req=91cd
 t=1.1   T_timeout  svc=api  downstream=payments  req=44b0
 ...     (7,412 more of the same shape)
 t=31.2  T_timeout  svc=api  downstream=search    req=c1e0
 t=31.9  T_timeout  svc=api  downstream=search    req=7f21
 ...     (203 more)
 t=44.0  T_pool_exhausted  svc=api                (first ever occurrence)
 t=58.7  T_timeout  svc=api  downstream=payments  req=e004

emitted at window close (t=60)

 key                                  count  first   last    samples
 T_timeout|api|payments               7,416   0.4    58.7    3 kept
 T_timeout|api|search                   205  31.2    47.4    3 kept
 T_pool_exhausted|api                     1  44.0    44.0    1 kept

 output: 3 records instead of 7,622 lines — a 2,540x reduction

Notice what survived. The count is exact, so the rate is preserved. First and last timestamps are preserved, so the shape within the window is partially recoverable. A small number of full raw samples are kept, so somebody can still read an actual line with an actual request id and go and trace it. And the single-occurrence T_pool_exhausted line was not diluted — it is one of three records rather than one line among 7,622, which is the second benefit of deduplication and often the larger one. Reducing volume raises the visibility of everything rare.

What you destroy, and how to not

• Sub-window shape. Seven thousand events uniformly spread over a minute and seven thousand in a two-second spike produce the same record. If the difference matters, keep a coarse histogram — twelve five-second sub-buckets is 12 small integers and preserves almost all of the shape for almost no cost.
• The distribution of the variable parts. The 7,416 timeouts had 7,416 request ids and you kept three. If you later need to know how many distinct users were affected, that is gone. A HyperLogLog sketch per key gives a distinct count within a few percent in a couple of kilobytes and is the right thing to add when “how many were affected” is a question anyone will ask.
• Correlation with other lines. Collapsing removes the interleaving, so you can no longer see that every timeout was immediately preceded by a specific warning. Keeping raw lines for a short retention alongside the deduplicated long retention is the usual compromise: full fidelity for 48 hours, collapsed records for a year.
• Exactness at the window edge. A storm spanning a window boundary produces two records, and anything reading records as “incidents” counts it twice. This is the same tumbling-window boundary artefact described in windowing strategies, and the same mitigation applies: treat consecutive records for one key as one episode when they abut.

Bounding the memory

The deduplicator holds one entry per active key per window. With 4,000 templates, 300 services and a handful of dimension values, the worst-case key space is large but the active key count in any one minute is much smaller — this is the same distinction as cardinality versus active cardinality in a metrics system, and it is the number to measure before sizing.

Two failure modes are worth guarding explicitly. First, a key explosion: an unbounded value accidentally included in the key — someone adds a customer id — turns the state from thousands of entries into millions, and the process dies at 03:00 on the busiest day. Cap the number of tracked keys and emit an explicit “dedup-overflow” record when the cap is hit, so the failure is visible rather than silent. Second, latency: dedup by definition delays every line until its window closes, so a 60-second window means your logs are a minute old. If a fast path matters — and it does for incident detection — run detection on the raw stream and deduplication only on the path to the index.

For exact-duplicate suppression across a longer horizon, a rolling Bloom filter is the standard structure: two filters, each covering half the retention, rotated so that the older one is dropped and the newer continues. It gives constant memory and a controllable false-positive rate, and a false positive means dropping a genuine line — which is why it belongs on delivery duplicates, where a drop is harmless, and not on application events, where it is data loss.