Algorithms

Pipeline

line -> format parser -> Record(ts, level, message) -> mask -> Drain -> cluster (+ stats)

Only the message is templated; timestamp and level are kept as metadata for the per-template statistics.

Masking

Variable-looking substrings are replaced by typed placeholders before Drain sees the line, so that "lines differing only in parameters" really are identical. Rules run in this order (user masks first):

A number is masked when it is a whole token or follows punctuation (count=42, and db-3 becomes db-<NUM>); numbers glued to letters (job42, v1.2.3) are left alone so identifiers stay readable. Each rule is guarded by a cheap substring or tiny-regex check so the hot path skips rules that cannot match.

Extra rules come from [[mask]] entries in the TOML config and take priority.

Drain

Drain (He et al., ICWS 2017) is an online log parser. Clusters live in a fixed-depth tree:

root
 `- token count (length)
     `- first token   (level 1)
         `- second token   (level 2)      <- depth 4 means 2 routing tokens
             `- leaf: list of clusters (templates)

With depth = d, the first d - 2 tokens route a line (the root and the length level are the other two). A routing token that contains a digit or is a placeholder (<NUM>, <*>) is not used literally; it goes to the shared <*> branch. A node holds at most max_children literal children; further distinct tokens go to <*>.

Worked example

Depth 4, similarity threshold 0.4. Input (already masked):

1  Connection closed by peer <IP>
2  Connection closed by peer <IP>
3  Connection reset by peer <IP>
4  Disk usage at high level now
5  Disk usage at critical level now

1. Line 1 has 5 tokens. Tree: 5 -> Connection -> closed -> [ ]. The leaf is empty, so a new cluster Connection closed by peer <IP> is created.
2. Line 2 follows the same path; the best cluster has similarity 5/5 = 1.0 >= 0.4, so it joins it (no template change).
3. Line 3 routes via Connection -> reset, a new leaf: new cluster Connection reset by peer <IP>.
4. Line 4 has 6 tokens, so it goes under a different length node: 6 -> Disk -> usage -> [ ], a new cluster.
5. Line 5 also has 6 tokens and the same routing tokens, so it lands in the same leaf. Similarity = equal tokens / length = 5/6 = 0.83 >= 0.4, so it joins the cluster. The one position that differs (high vs critical) becomes a wildcard.

Result: five lines become three templates:

Connection closed by peer <IP>
Connection reset by peer <IP>
Disk usage at <*> level now

Similarity

For a line with n tokens and a candidate template of the same length,

sim = (number of positions where template token == line token) / n

Template wildcards (<*>) never count as matches (as in the original Drain). The best-scoring cluster in the leaf is chosen; if sim >= sim_threshold the line joins it and any differing non-wildcard positions become <*>; otherwise a new cluster starts. Typed placeholders such as <NUM> match only an identical placeholder, so a position holding <NUM> in one line and <IP> in another becomes <*>.

A cache from masked message to cluster makes repeated message shapes skip the tree walk entirely. Clusters are never deleted, so a cached cluster remains valid when its template later generalises.

Template ids

id = sha1(template text)[:8]. The id changes when a template generalises (the text changes); persisted models store the final ids. Clusters that converge to identical text are merged on save.

Choosing parameters

• Lower sim_threshold merges more aggressively; higher keeps near-duplicates apart.
• Larger depth separates lines by more leading tokens (more, more specific templates); the minimum is 2 (route by length only).
• A variable in the first depth - 2 tokens explodes into one branch per value until max_children; mask it instead.

Parameter extraction

grep aligns the unmasked message token-by-token with the template (masking never changes the token count unless a user regex contains whitespace). A token that is exactly <*> yields the raw token; a token such as host=db-<NUM> is turned into a regex (host=db-(.*?)) and the captured part is the value. Values are counted per slot for --params.

diff: significance of frequency changes

Let a, b be a template's counts in baseline/target, and N_a, N_b the total line counts. Rates are normalised by volume, so doubling traffic with the same mix is not a change:

p_a = a / N_a        p_b = b / N_b

The statistic is the two-proportion z-test with pooled variance:

p = (a + b) / (N_a + N_b)
z = (p_b - p_a) / sqrt( p (1 - p) (1/N_a + 1/N_b) )

The two-sided p-value is erfc(|z| / sqrt 2). For readability the effect size is the smoothed log ratio

log2 ratio = log2( ((b + 0.5) / N_b) / ((a + 0.5) / N_a) )

(the half count keeps it finite for new and vanished templates).

Worked example: baseline 19,414 lines, target 21,705 lines; "Database connection timeout" has a = 9, b = 1207:

p_a = 0.000464   p_b = 0.05561   p = 1216 / 41119 = 0.02957
se  = sqrt(0.02957 * 0.97043 * (1/19414 + 1/21705)) = 0.001674
z   = (0.05561 - 0.000464) / 0.001674 = +33.0
log2 ratio = log2((1207.5/21705) / (9.5/19414)) = +6.83

Classification: a = 0 is new, b = 0 is vanished, otherwise up/down by the sign of z. New and vanished templates need a + b >= min_count (default 5); up/down also need |z| >= min_z (default 3). Everything is ranked by |z|. Because Drain templates are mined over both sides together, the same ids appear on both sides even though generalisation happens as more lines arrive.

A z-test treats lines as independent, which logs are not (bursts); use it for ranking, not for literal p-value claims.

spikes: robust baseline

Each template gets a series x_0 .. x_{T-1} of counts per bucket over the full time range of the input (zero filled, so sparklines align across templates).

Median + MAD (default)

m     = median(x)
MAD   = median(|x_i - m|)
sigma = max(1.4826 * MAD, sqrt(m), 1)
flag bucket i if x_i > m + k * sigma  and  x_i >= min_count
score = (x_i - m) / sigma

1.4826 * MAD estimates the standard deviation for normal data. For sparse or flat series MAD is 0, so sigma falls back to the Poisson floor sqrt(m) (and at least 1). Median and MAD are not moved by a few extreme buckets, so the spike itself does not hide in the baseline.

Worked example: series [10, 12, 9, 11, 10, 13, 10, 11, 9, 10, 80, 10, 11]: m = 10, deviations [0,2,1,1,0,3,0,1,1,0,70,0,1] give MAD = 1, sigma = max(1.48, 3.16, 1) = 3.16, threshold 10 + 5*3.16 = 25.8; only the 80 is flagged (score 22).

EWMA (--method ewma)

sigma_i = max(sqrt(var_{i-1}), sqrt(mean_{i-1}), 1)
flag bucket i if i >= 5 and x_i > mean_{i-1} + k * sigma_i and x_i >= min_count
mean_i  = mean_{i-1} + alpha * (x_i - mean_{i-1})
var_i   = (1 - alpha) * (var_{i-1} + alpha * (x_i - mean_{i-1})^2)

with alpha = 0.3. A flagged bucket is clipped to the threshold before updating the state so a long incident does not teach the baseline that spikes are normal. EWMA adapts to drifting levels; MAD is better for stable periodic series.

Sparkline

Series are down-sampled to --width by taking the max in each group (spikes must survive), then each value maps to one of ▁▂▃▄▅▆▇█ by ceil(8 * x / max).