implementing the drain algorithm in rust

picture the scene: something is on fire in production, you ssh into the box, tail a log file, and you’re greeted by forty thousand lines that all look almost the same but not quite. your eyes glaze over. you grep error, then grep -v the noise, then pipe the whole thing into sort | uniq -c and pray.

there’s a better way, and it’s older than you’d think.

lately i’ve been building a little log-analysis cli called logmole ↗ : point it at a log file, it auto-detects the format, lets you filter with a tiny query language, and flags anomalies. today i want to talk about the part that turns those forty thousand lines into a dozen shapes.

the fancy term is log template extraction. the algorithm is called drain. and porting it to rust taught me more about the distance between a research paper and a shipping tool than i expected.

logs are structured data pretending to be prose

here’s the thing nobody tells you: your logs are not text. they’re a database that got printed to a stream. every line like

Connection from 192.168.1.1 accepted
Connection from 10.0.0.5 accepted
Connection from 172.16.0.1 accepted

is really one template — Connection from <*> accepted — with a variable slot. if a tool can recover that template automatically, suddenly forty thousand lines collapse into “oh, it’s these fifteen things, and this one weird new one i’ve never seen before.”

that last part — the one i’ve never seen before — is the whole game for anomaly detection. but first you need the templates.

what drain actually does

drain comes from a 2017 paper by pinjia he, jieming zhu, zibin zheng and michael r. lyu — “drain: an online log parsing approach with fixed depth tree” ↗ (icws 2017, pp. 33–40). there’s a well-known reference implementation in the logpai/logparser ↗ project if you want the canonical version.

the two words that matter are online and fixed depth.

online means single-pass and streaming. you don’t get to load every line, cluster them, and think hard. each line walks in, gets matched to an existing template (or spawns a new one), and you move on. constant work per line, no going back.

fixed depth is the trick that keeps it fast. instead of comparing a new line against every known template, drain organises templates in a shallow tree:

1. first you branch on the number of tokens in the line,
2. then on the first few tokens,
3. and only the handful of candidates in that leaf get a real similarity check.

no unbounded search. that’s what makes it viable on a firehose.

the data structure

here’s what a template looks like in logmole. nothing clever — an id, the tokens (with variable slots already replaced by <*>), and how many lines matched it:

logmole-core/src/analysis/drain.rs

/// A log template extracted by the Drain algorithm.
#[derive(Debug, Clone)]
pub struct Template {
    /// Unique identifier (sequential).
    pub id: u32,
    /// The template tokens (variable parts replaced with `<*>`).
    pub tokens: Vec<String>,
    /// Number of log lines matching this template.
    pub count: u64,
}

and the extractor itself:

pub struct DrainTree {
    /// Depth of the prefix tree (default: 4). Reserved for full trie implementation.
    #[allow(dead_code)]
    depth: usize,
    /// Similarity threshold for merging (default: 0.5).
    similarity_threshold: f64,
    /// Maximum clusters to track.
    max_clusters: usize,
    /// All known templates, keyed by ID.
    templates: HashMap<u32, Template>,
    /// Prefix tree: length -> first_token -> list of template IDs.
    tree: HashMap<usize, HashMap<String, Vec<u32>>>,
    /// Next template ID.
    next_id: u32,
}

keep an eye on that depth field with the #[allow(dead_code)] on it. we’ll come back to it, and it’s the most honest line in the whole file.

the tree is the fixed-depth idea in its most stripped-down form: a map from token count to a map from first token to a list of candidate template ids. two levels, that’s it.

step 1: tokenise (badly, on purpose)

pub fn process(&mut self, message: &str) -> u32 {
    let tokens: Vec<&str> = message.split_whitespace().collect();
    if tokens.is_empty() {
        return 0;
    }
    // ...
}

that’s the entire tokeniser. split_whitespace ↗ and go home.

the paper preprocesses lines with user-supplied regexes first — mask out ip addresses, timestamps, numbers, that kind of thing — before tokenising. i don’t. i lean on a cheaper trick later instead. is this worse? yes. does it matter for a cli triaging a log file? mostly no. hold that thought.

note also that empty messages return template 0. 0 is my reserved “no template” id — real templates start at 1. small decision, saves a lot of Option juggling downstream.

step 2: find candidates without scanning everything

this is where the tree earns its keep:

fn find_candidates(&self, tokens: &[&str]) -> Vec<u32> {
    let token_len = tokens.len();
    let Some(length_group) = self.tree.get(&token_len) else {
        return Vec::new();
    };

    // Try exact first token match
    let first_key = prefix_key(tokens[0]);
    if let Some(ids) = length_group.get(&first_key) {
        return ids.clone();
    }

    // Try wildcard group
    if let Some(ids) = length_group.get("<*>") {
        return ids.clone();
    }

    Vec::new()
}

a line with seven tokens can only ever match a template with seven tokens, so we jump straight to the seven-token bucket. within it, we look up templates that share a first token. anything in another bucket is, by construction, not a candidate — we never even look at it.

now, that cheaper trick i promised. what’s prefix_key?

/// Normalize the prefix key: digits become `<*>` (numbers are variable).
fn prefix_key(token: &str) -> String {
    if token
        .chars()
        .all(|c| c.is_ascii_digit() || c == '.' || c == '-')
    {
        "<*>".to_string()
    } else {
        token.to_string()
    }
}

if the first token is all digits, dots and dashes — a timestamp, an ip, a request id — we normalise it to <*> so that

192.168.1.1 - connection accepted
10.0.0.5 - connection accepted

still land in the same bucket instead of exploding into one bucket per address. it’s a one-line stand-in for the paper’s whole regex-masking preprocessing step. cheap, and it covers the single most common case: lines that start with a variable.

step 3: score, then generalise

we’ve got a short list of candidates. now we score similarity — the fraction of positions that match, with wildcards counting as free matches:

/// Token-level similarity: fraction of matching tokens (excluding wildcards).
fn similarity(&self, tokens: &[&str], template: &[String]) -> f64 {
    if tokens.len() != template.len() {
        return 0.0;
    }
    let total = tokens.len();
    if total == 0 {
        return 1.0;
    }
    let matching = tokens
        .iter()
        .zip(template.iter())
        .filter(|(tok, tmpl)| tmpl.as_str() == "<*>" || **tok == tmpl.as_str())
        .count();

    matching as f64 / total as f64
}

the best candidate above the similarity_threshold (default 0.5) wins. and here’s the part that makes drain online rather than just a fancy grouping — when a line matches an existing template, the template generalises itself in place:

if let Some(template) = self.templates.get_mut(&template_id) {
    template.count += 1;
    // Merge: replace differing tokens with <*>
    for (i, token) in tokens.iter().enumerate() {
        if i < template.tokens.len()
            && template.tokens[i] != "<*>"
            && template.tokens[i] != *token
        {
            template.tokens[i] = "<*>".to_string();
        }
    }
}

walk the line against the template token by token. wherever they disagree — and the slot isn’t already a wildcard — burn it down to <*>. so the template gets more general every time it meets a line that almost-but-not-quite fits. the first Connection from 192.168.1.1 accepted is stored literally; the moment Connection from 10.0.0.5 accepted shows up, position three becomes <*> forever.

no match above threshold, and we’re not at capacity? mint a new template, drop it into the tree, and carry on.

does it work?

this is the test i trust most, because it’s the one that would’ve caught me lying:

#[test]
fn extract_template_from_similar_lines() {
    let mut drain = DrainTree::default_params();

    let id1 = drain.process("Connection from 192.168.1.1 accepted");
    let id2 = drain.process("Connection from 10.0.0.5 accepted");
    let id3 = drain.process("Connection from 172.16.0.1 accepted");

    assert_eq!(id1, id2);
    assert_eq!(id2, id3);

    let template = drain.get_template(id1).unwrap();
    assert_eq!(template.count, 3);
    assert_eq!(template.pattern(), "Connection from <*> accepted");
}

three lines in, one template out, variable slot correctly identified. same story with Request took 150 ms and Request took 3500 ms collapsing to Request took <*> ms. it does the thing.

the honest part: what i cut

the blog rule around here is that i don’t get to pretend. so:

it isn’t actually a fixed-depth tree. the paper’s entire title is fixed depth tree, and my depth field is #[allow(dead_code)]. i bucket by token count and first token and call it a day — two hashmap levels wearing a trench coat. the real thing traverses depth levels of tokens to keep leaves small when you have thousands of templates. i haven’t needed it yet, so the field sits there as a promise to future-me rather than a lie to present-me.

similarity is naive. matching / total, wildcards free. it’s fine for well-behaved logs and gets confused by high-variability messages where half the line is variable. the paper is more careful about this.

back-pressure is a guillotine. at max_clusters i just stop:

if self.templates.len() >= self.max_clusters {
    return 0; // At capacity
}

no eviction, no lru, no nothing. a burst of unique garbage fills the table and you quietly stop learning. that’s an acceptable failure mode for a cli chewing through a bounded file. it would not be acceptable for something long-running, and i know it.

none of these are bugs. they’re scope. the point of shipping was to get templates out of real logs, and it does.

why the templates matter

remember “the one i’ve never seen before”? templates get sequential ids, so novelty is almost free:

/// Check if a template ID was created after a given ID threshold.
pub fn is_novel(&self, template_id: u32, baseline_max_id: u32) -> bool {
    template_id > baseline_max_id
}

/// Get the current max template ID (snapshot for baseline).
pub fn max_id(&self) -> u32 {
    self.next_id.saturating_sub(1)
}

snapshot max_id() at the end of a “known good” window. after that, any line whose template id is higher than the snapshot is, by definition, a shape you didn’t see while things were healthy. that’s a genuine novel-pattern signal for the cost of an integer comparison — no model, no training, no embeddings. sometimes the boring answer is the right one.

lessons learned

• the value of a paper is usually the idea, not the implementation. “group log lines by their shape, online, in one pass” is the idea, and you can ship a crude version of it in an afternoon and capture most of the benefit. the fixed-depth tree is an optimisation for a scale i don’t have yet.
• write your shortcuts down. an #[allow(dead_code)] with a // reserved for full trie note costs nothing and turns “why is this here?” into “ah, right, that’s the upgrade path.”
• test the claim, not the code. the test that asserts "Connection from <*> accepted" is testing the behaviour i promised the reader, not the shape of my hashmaps. that’s the one that keeps me honest when i refactor.

next in the logmole series: how it flags error-rate spikes without storing a single sample — welford’s online variance, and why i never keep the numbers around.

the code is on github ↗ if you want to poke at it. it’s a work in progress, like everything here.