This series is an excuse to build a writing habit while exploring a codebase I’ve wanted to understand better.

Pattern matchers need to handle pattern lifecycles like adding new patterns to expand matching capabilities and removing patterns that are no longer needed. If an automata excels at the first operation through shared-state compilation, it can struggle with the second. You can extend an automaton by adding new states and transitions, but there’s no clean way to “un-add” a pattern without potentially breaking other patterns that share the same states.

Quamina addresses this asymmetry with two matcher implementations. The coreMatcher supports fast, concurrent pattern addition but no deletion. The prunerMatcher wraps a coreMatcher and adds deletion support through lazy filtering and periodic full rebuilds. The choice between them is a deliberate trade-off as deletions are rare. In fact for ruler, it was faster to rebuild everything because addition performance than introduce additional deletion capability that happened rarely.

Adding Patterns: Copy-on-Write Atomicity Link to heading

The coreMatcher uses atomic.Pointer[coreFields] to enable lock-free reads during pattern addition. The data structure in core_matcher.go separates the updateable state from the concurrency control:

type coreMatcher struct {
    updateable atomic.Pointer[coreFields]
    lock       sync.Mutex
}

Pattern addition follows a copy-on-write protocol. The addPattern method in core_matcher.go locks to ensure only one writer at a time, builds a complete new automaton state, then atomically swaps it in. Matching operations running in parallel never see partial updates. They either see the state before the addition or after, but never during.

The process starts by loading the current state and creating a fresh copy. The segments tree (which tracks which field paths appear in patterns) gets copied, while the automaton state itself is shared initially. The method then walks through the pattern’s sorted field list, extending the automaton by adding transitions for each field name and value matcher. When all fields are processed, the final states get marked with the pattern’s identifier. Only then does the atomic store operation make the new automaton visible to matching threads.

Consider adding pattern {"x":[1],"y":[2]} to an empty matcher. The addition creates a chain. Starting state transitions on field “x” to state1, which transitions on value [1] to state2, that then transitions on field “y” to state3 before transitioning on value [2] to state4. Here, state4 becomes terminal, marked with this pattern’s identifier (in ruler, called as a “rule name”). If another pattern later adds {"x":[1],"y":[3]}, states 0-2 are shared between both patterns—only state3 branches to add a new terminal state for the second pattern.

The atomic pointer means multiple threads can call MatchesForFields while addPattern is executing. Matchers call m.fields() which loads the pointer without any lock. They either see the automaton before the update or after, but its always see a complete, consistent automaton.

Concurrent Matching via Copy() Link to heading

A single Quamina instance is not thread-safe for simultaneous use across goroutines. Instead, the Copy() method in quamina.go creates instances that share the underlying matcher but maintain separate per-goroutine scratch space:

func (q *Quamina) Copy() *Quamina {
    return &Quamina{
        matcher: q.matcher,
        flattener: q.flattener.Copy(),
        bufs: newNfaBuffers()
    }
}

The matcher pointer is shared because reads are atomic and writes are serialized. The flattener gets copied because it maintains internal parsing state that isn’t thread-safe. The NFA buffers are always fresh because they’re scratch space for traversal operations, storing intermediate state lists during matching.

This design means patterns added through any copy become visible to all copies. Call AddPattern on copy A, and the new pattern immediately becomes available to matchers running on copies B, C, and D. The atomic pointer swap in the underlying coreMatcher ensures this visibility happens cleanly without races.

The Deletion Problem Link to heading

Why can’t automata support direct pattern deletion? The issue is state sharing. When multiple patterns share prefixes, they share states and transitions. Consider two patterns:

Pattern 1: {"x":[1],"y":[2]}
Pattern 2: {"x":[1],"y":[3]}

Both patterns create a transition from the start state on field “x” to state1, and from state1 on value 1 to state2. Only at state2 do they diverge with one path leads to a terminal for pattern 1, another for pattern 2. To delete pattern 1, you’d need to remove its terminal state, which is straightforward. But what if you delete pattern 2 as well? Now the transition on field “x” and value 1 serves no pattern. Should it be removed? What if another pattern was added that shares that prefix?

Tracking reference counts per transition could work, but it’s complex and error-prone in a multi-threaded environment. The alternative Quamina chooses is simpler don’t modify the automaton at all.

Lazy Deletion with Filtering Link to heading

The prunerMatcher in pruner.go wraps a coreMatcher and maintains a separate set of live patterns:

type prunerMatcher struct {
    Matcher *coreMatcher
    live    LivePatternsState
    stats   prunerStats
    rebuildTrigger rebuildTrigger
    lock    sync.RWMutex
}

When you add a pattern, it goes into both the automaton and the live set. When you delete a pattern via deletePatterns in pruner.go, it’s removed only from the live set. The automaton continues to contain the deleted pattern’s states and transitions.

Matching with a prunerMatcher runs the underlying coreMatcher to get candidates, then filters the results in matchesForFields at pruner.go. For each match returned by the automaton, the code checks m.live.Contains(x). If the pattern identifier is still in the live set, it’s included in results. If not, it’s filtered out and counted in stats as a filtered match.

This filtering is lazy deletion. The pattern is functionally deleted. It never appears in match results but the automaton still contains its structure. Over time, as patterns get deleted, the automaton fills with dead states that waste matching effort. That’s where rebuilding comes in.

Periodic Rebuilds Link to heading

The prunerMatcher tracks statistics in pruner.go like how many patterns are live, how many matches were emitted vs filtered, when the last rebuild occurred. After each AddPattern, DeletePattern, or MatchesForFields call, the code consults a rebuild trigger to decide whether to rebuild.

The default trigger in pruner.go implements a filtering ratio policy:

var defaultRebuildTrigger = newTooMuchFiltering(0.2, 1000)

The policy triggers a rebuild when the ratio of filtered-to-emitted matches exceeds 0.2 (20% filtering) and total traffic has exceeded 1000 matches. The logic avoids rebuilding on pattern additions (which can’t increase filtering) and checks that some matches have been emitted (to avoid divide-by-zero).

When a rebuild triggers, rebuildWhileLocked in pruner.go creates a fresh coreMatcher and iterates through the live pattern set, re-adding each pattern to the new matcher. Once complete, it atomically swaps the new matcher for the old one and resets the statistics counters. The old automaton becomes unreachable and gets garbage collected.

Rebuilds are stop-the-world operations. The calling thread—whether from AddPattern, DeletePattern, or MatchesForFields holds a write lock for the entire rebuild duration. All other operations on the pruner block until the rebuild completes.

I am guessing that the synchronous rebuild choice likely favors simplicity and determinism over background complexity. A background rebuild would need coordination to safely swap matchers, handle queries during rebuild, and manage memory for two concurrent matchers. The synchronous approach is more predictable. The rebuild cost is paid exactly when the threshold is reached, making behavior easier to reason about and test.

Multiple Patterns Per Identifier Link to heading

The live pattern storage in live_pattern_state.go uses a map from identifiers to sets of pattern strings:

type memState struct {
    lock sync.RWMutex
    m    map[X]stringSet
}

This structure supports multiple patterns sharing the same identifier. You might call AddPattern twice with the same ID but different pattern JSON:

m.addPattern(1, `{"x":["a"]}`)
m.addPattern(1, `{"y":["b"]}`)

Both patterns get added to the automaton and both are stored in the live set under identifier 1. When you later call deletePatterns(1), both patterns are removed from the live set. The Delete method in live_pattern_state.go returns the count of removed patterns, updating the pruner’s statistics accordingly.

This design supports use cases where one logical entity maps to multiple match conditions. An alerting system might represent “alert for user 123” as several patterns covering different event types, all identified by the user ID. Deleting that user’s subscription removes all their patterns in one operation.

Lock Granularity Link to heading

The prunerMatcher uses an RWMutex to protect the matcher pointer and statistics. Read lock is held during the brief window when updating stats after a match. Write lock is held during pattern addition, deletion, and rebuilds. The underlying coreMatcher has its own mutex protecting its state updates, but only writers (pattern additions) contend for that lock.

The live pattern set has its own RWMutex in the memState implementation. Operations like Contains (called for each match during filtering) take a read lock. Add and Delete take write locks. During a rebuild, the write lock on the pruner prevents concurrent modifications, but the live set’s lock is separate. live_pattern_state.go explains more on how rebuilt and live-set lock interactions happen.

Rebuild Cost and Policy Link to heading

The 0.2 filtering threshold feels like an empirically chosen balance. Low enough that filtering overhead doesn’t dominate, high enough that rebuilds aren’t too frequent. Twenty percent waste means one in five automaton matches is discarded, which seems like a reasonable point to pay the rebuild cost and reclaim efficiency.

The minimum traffic threshold of 1000 matches prevents rebuilding based on early, possibly unrepresentative traffic. If you delete one pattern after adding two, filtering would be 50%, well over the 0.2 threshold. But rebuilding for such minimal state seems wasteful. The 1000 minimum ensures the matcher has seen enough real workload to justify rebuild cost.

Rebuild duration scales with the number of live patterns, as each must be re-added via the compilation process. For a few thousand patterns, rebuilds are quick. For tens or hundreds of thousands, rebuilds could take noticeable time. The stop-the-world nature means all operations block during that period. Applications with strict latency requirements might need to control rebuild timing. This could be done by manual triggering rebuilds during controlled windows but its generally faster to build another automata externally and swap it in. It takes a memory hit, but if automatas are built at a regular cadence and are rate-limited, you rarely come across anything odd in real-world usage.

Choosing Deletion Support Link to heading

The choice between coreMatcher and prunerMatcher happens at construction via WithPatternDeletion in quamina.go. Pass false (the default) and you get a coreMatcher with no deletion support but also no filtering overhead. Pass true and you get a prunerMatcher with deletion support, filtering on every match, and periodic rebuilds.

For applications that only add patterns—perhaps building a static matcher from configuration at startup the coreMatcher is simpler and faster. For applications that need dynamic pattern management—adding and removing subscriptions as users come and go; the prunerMatcher provides deletion capability at the cost of filtering overhead and occasional rebuild pauses.

What This Enables Link to heading

The state management design reflects Quamina’s automaton foundation. Automata make matching fast by precomputing transitions, but that precomputation makes modification expensive. Rather than fight the data structure’s nature, Quamina embraces it by optimizing the common case (matching) with lock-free atomic reads, serialize the update case (pattern addition) with atomic swap, and handle the hard case (deletion) with lazy filtering and full reconstruction. The approach turns a theoretical weakness of automata into a practical trade-off between performance and flexibility.