Log Parsing and Template Extraction Explained

Ten million log lines are usually a few hundred distinct sentences with different values substituted in. Recovering those sentences is the step every other piece of log analysis is built on, and there is a standard algorithm for doing it in one pass.

What a template is, and why you need one

A log template is the constant part of a log statement with its variable parts replaced by a placeholder. These three lines

Received block blk_7382 of size 67108864 from /10.251.42.9
Received block blk_1029 of size 67108864 from /10.251.31.5
Received block blk_5561 of size 33554432 from /10.250.14.224

are one template, Received block <*> of size <*> from <*>, with three parameter lists. That reduction is what makes the rest of the field possible. You cannot count occurrences of an event that is never written the same way twice; you cannot say “this message appeared 40 times a minute all week and 4,000 times at 03:12” until the thing being counted has an identity. Template extraction gives every log statement a stable id without requiring the developers who wrote it to have emitted structured output.

The naive approach — cluster the raw strings by edit distance — is quadratic in the number of lines and therefore unusable at log volumes. The naive alternative — write a regular expression per message — works until the next deploy adds a message nobody told you about. The algorithms in this area exist to get template identity in one streaming pass, with bounded memory, without a schema.

Drain: the standard online algorithm

Drain, published by Pinjia He, Jieming Zhu, Zibin Zheng and Michael Lyu at ICWS 2017, is the algorithm most log tooling either uses or imitates. Its idea is that you do not need to compare a new line against every known template — you need a cheap tree that narrows the candidates to a handful first, and only then does a similarity comparison. Read the original in He et al., “Drain: An Online Log Parsing Approach with Fixed Depth Tree”; the maintained Python implementation is logpai/Drain3.

A line goes through four stages. First, masking: a small set of domain regexes rewrite the values you already know are variable — IP addresses, hex ids, numbers, paths — into named placeholders. This is not a shortcut around the algorithm, it is a requirement, because a variable in the first token position would otherwise send every occurrence down a different branch of the tree.

Second, the length layer. The tokenised message is routed by its token count, so a five-token message never gets compared against an eleven-token one. Third, the token layers: the tree descends on the first token, then the second, and so on, for a fixed number of levels set by the depth parameter. Fixed depth is the whole trick — the tree cannot degenerate into something deep and unbalanced, so lookup is a constant number of hops regardless of how many templates exist.

Fourth, the leaf. Each leaf holds a list of log groups, each with a template and a count. The new line is scored against each group’s template by simple positional agreement: the number of token positions where the line and the template hold the same token, divided by the token count. If the best score reaches the similarity threshold sim_th, the line joins that group, and every position where they disagree is rewritten to the wildcard <*> in the stored template. If no group clears the threshold, the line becomes a new group whose template is itself. That last step is why the template set converges: it starts specific and erodes toward the constant part as more examples arrive.

A worked extraction

Take the three lines above, with numbers and IPs masked. Tokenised, each is eight tokens, so all three land in the same length bucket, and the first two tokens — Received, block — walk them to the same leaf at depth 4.

line 1  Received block ID of size NUM from IP
        leaf empty -> new group
        template := Received block ID of size NUM from IP   (count 1)

line 2  Received block ID of size NUM from IP
        vs template: 8 of 8 positions agree -> sim = 1.00 >= 0.4
        matches; template unchanged                          (count 2)

line 3  Received block ID of size NUM from IP
        identical after masking                              (count 3)

Masking did most of the work there, which is realistic. Now add a line the masks do not fully flatten:

line 4  Received block ID of size NUM from datanode IP
        9 tokens -> different length bucket -> new group

line 5  PacketResponder NUM for block ID terminating
        first token differs -> different subtree -> new group

And a case where the similarity step earns its keep. Suppose two lines reach the same leaf as Deleting block ID file /path and Deleting block ID dir /path. Five tokens, four agree, so sim = 0.80. That clears 0.4, they merge, and the stored template becomes Deleting block ID <*> /path. The parser has discovered a variable position that no mask knew about, from two examples. That is the behaviour you are buying, and it is also the behaviour that goes wrong when the threshold is set badly.

The three parameters that matter

• sim_th — default 0.4 in Drain3. The single most consequential knob. Too low and unrelated messages merge: at 0.2, a five-token message needs only one matching position to join a group, and you end up with a template that is almost all wildcards and means nothing. Too high and templates fragment, so the same log statement is tracked as six ids and every frequency signal over it is split six ways. Fragmentation is the safer failure — you can merge afterwards; you cannot unmerge.
• depth — default 4, minimum 3. How many leading tokens the tree branches on before reaching a leaf. Deeper means fewer candidates per leaf and faster matching, but it also means that any variability in the leading tokens splits groups that should be one. Log formats that lead with a component name and then a verb suit a shallow tree; formats that lead with a variable need better masking, not more depth.
• max_children — default 100. The cap on branches at an internal node. When a node is full, further distinct tokens are routed to a catch-all wildcard child rather than growing the tree without bound. This is the memory guarantee, and it means an unmasked high-cardinality token in a leading position degrades matching quality rather than exhausting RAM.

Drain3 also exposes max_clusters, unlimited by default, which turns the template store into an LRU cache when set. On a long-running stream with template churn, leaving it unlimited is a slow memory leak dressed as a feature.

Where template mining breaks

Multi-line messages. A Java stack trace is one logical event and forty physical lines. Fed line by line, a parser mines forty templates from each distinct stack, and the template count explodes. Multi-line joining has to happen before parsing, usually by treating a line that does not start with a timestamp as a continuation.

Variable-length variables. The length layer assumes a template has a fixed token count. A message that interpolates a list — evicted peers [a, b, c] — produces a different token count per occurrence and therefore one template per list length. Mask bracketed lists to a single token before parsing.

Template drift across deploys. A developer changes “Received block” to “Received chunk” and every count series built on the old id goes to zero while a new id appears from nothing. Any anomaly detector reading those counts will fire, and it is not wrong exactly — something did change — but it is not the incident anyone wanted to be paged for. This is why template stores are worth persisting and versioning alongside the build that produced them.

Free-text user content. A message that embeds a search query or an exception message from a third-party library has natural language in the constant position. Nothing in the algorithm can tell that apart from a legitimately varying template, and it is the most common source of runaway template counts in practice. Cap the parameter at a token count and truncate.

With templates in hand, the natural next steps are grouping lines for triage, collapsing repeats before they hit an index in log deduplication, and modelling template frequency in log anomaly detection. The benchmark datasets most of this literature is evaluated on — HDFS, BGL, Thunderbird and thirteen others — are published as loghub.