This series is an excuse to build a writing habit while exploring a codebase I’ve wanted to understand better.
Finite state automata excel at processing sequential input. They transition from state to state based on the current symbol in a linear stream. JSON events though present a fundamental challenge because field order is non-deterministic, there’s hierarchy, and arrays create special edge-cases (more on this later). The same logical object can serialize with fields in any order, making direct automaton processing impractical. An automaton would need exponentially many states to handle all possible field orderings, and there’s no deterministic way to build transitions for hierarchical paths when field order varies.
Quamina solves this by flattening JSON into a normalized representation: a sorted list of pathname/value pairs. This transformation enables automaton-based matching against unordered, hierarchical data structures. The flattening process converts every JSON object into Field structures, each containing a newline-separated path from root to leaf, the value as text, and an ArrayTrail that tracks position in arrays to prevent incorrect cross-element matches.
From JSON to Pathname/Value Pairs Link to heading
Consider a JSON event representing a user action with nested context. The flattening algorithm transforms the hierarchical structure into a flat sequence that an automaton can process deterministically. Given this input:
{
"a": 1,
"b": "two",
"e": {
"e1": 2,
"e2": 3.02e-5
},
"f": [33, "x"]
}
The flattener produces these sorted pathname/value pairs:
Path: "a" Val: "1" ArrayTrail: []
Path: "b" Val: "\"two\"" ArrayTrail: []
Path: "e\ne1" Val: "2" ArrayTrail: []
Path: "e\ne2" Val: "3.02e-5" ArrayTrail: []
Path: "f" Val: "33" ArrayTrail: [{Array: 1, Pos: 0}]
Path: "f" Val: "\"x\"" ArrayTrail: [{Array: 1, Pos: 1}]
Path construction uses the newline character as a separator for nested objects (flattener.go). The path e.e1 becomes "e\ne1" with each nesting level adding one segment. This choice eliminates a fundamental ambiguity present in Ruler, Quamina’s spiritual predecessor. Ruler uses dot (.) as its path separator, which creates structural confusion because dots are valid in JSON keys. For example, {"detail": {"c.count": 5}} and {"detail.c.count": 5} are treated as equivalent, with both producing the path detail.c.count even though they represent different JSON structures. As newline do not typically appear unescaped in JSON keys, it makes a path like "a\nb" to nearly always represent the nested structure {"a": {"b": ...}}. This unambiguous path representation comes at the cost of using a non-printable character that’s harder to debug, but ensures that every path maps to exactly one JSON structure. String values retain their quotes from the original JSON to distinguish them from numbers and other types, while numeric values are preserved as text to maintain precision during matching.
Array handling reveals an important design decision that was another learning from Ruler. Each array element becomes a separate field with the same path, distinguished only by the ArrayTrail. The array "f": [33, "x"] produces two fields both with path "f", but different trail markers: {Array: 1, Pos: 0} for the first element and {Array: 1, Pos: 1} for the second. Each array in an event receives a unique sequential identifier, and each element gets a position index. This tracking prevents matching fields from different elements of the same array. A pattern looking for {"a": {"b": 1, "c": 4}} will not match an event containing {"a": [{"b": 1, "c": 2}, {"b": 3, "c": 4}]} even though both values appear somewhere in the array.
Lexicographic Ordering and Deterministic Matching Link to heading
Before the automaton can process fields, both pattern fields and event fields must be sorted lexicographically. The implementation performs a straightforward byte comparison, as shown in core_matcher.go:
func (a fieldsList) Less(i, j int) bool {
return bytes.Compare(a[i].Path, a[j].Path) < 0
}
This sorting serves several purposes. It enables deterministic automaton construction since patterns always present fields in the same order. The matching algorithm can process both lists linearly without backtracking. Multiple patterns with the same field prefixes can share automaton states, reducing memory overhead and improving performance. Without sorted fields, the automaton would need to account for all possible permutations of field orderings, creating an exponential state explosion.
The sorting cost is O(n log n) where n is the number of fields extracted from the event. This flattening and sorting process exceeds 50% of total execution time for typical workloads in real world, making optimization of the extraction phase critical. The segments tree optimization, detailed below, addresses this by reducing the number of fields that need to be extracted and sorted in the first place.
The Custom JSON Parser Link to heading
Quamina implements a custom JSON parser rather than using Go’s standard encoding/json library. The original implementation did use the standard library however profiling revealed 99% of time spent parsing events and so less than 1% spent on actual matching. The performance bottleneck stemmed primarily from excessive memory allocation.
The custom parser implements several key optimizations. Values are represented as byte slices into the original event buffer rather than copied into new allocations. This a zero-copy approach that assumes events are immutable during processing, a typical assumption in event-driven systems. The exception are strings containing JSON escape sequences which must be rewritten into newly allocated memory to work with the actual UTF-8 bytes. The parser uses an explicit state machine rather than reflection to have full control over the parsing flow and allocation patterns. It can selectively skip unused fields entirely via the skipBlock function, jumping over subtrees without parsing their contents:
func (fj *flattenJSON) skipBlock(openSymbol byte, closeSymbol byte) error {
level := 0
for fj.eventIndex < len(fj.event) {
ch := fj.event[fj.eventIndex]
switch ch {
case '"':
err := fj.skipStringValue()
if err != nil {
return err
}
case openSymbol:
level++
case closeSymbol:
level--
if level == 0 {
return nil
}
}
fj.eventIndex++
}
return fj.error("truncated block")
}
This function tracks only brace depth and string boundaries without parsing any values, allowing it to skip large subtrees efficiently. The flattener object itself is reusable across events via a reset() method that clears state while preserving the backing arrays for fields and other structures, avoiding per-event allocations.
Performance Optimization: The Segments Tree Link to heading
The most significant performance optimization addresses a key insight that I’m pretty sure Ruler is missing. Many patterns only care about a small subset of fields in an event. A pattern matching {"context": {"user_id": [1]}} doesn’t need to parse an entire multi-kilobyte payload if the user_id field appears early in the event. The segments tree tracks which paths appear in any registered pattern, enabling two powerful optimizations.
The segmentsTree implements a trie-like structure where each node represents a path segment. For patterns with paths "a", "e\ne1", and "e\ne2", the tree structure looks like this:
[root]
├─ fields: {"a" → []byte("a")}
└─ nodes: {"e" → [node]}
└─ fields: {"e1" → []byte("e\ne1"),
"e2" → []byte("e\ne2")}
During object traversal, the parser checks pathNode.IsSegmentUsed(memberName) before processing each field’s value. If a field isn’t used in any pattern, skipBlock jumps over the entire subtree without parsing. The implementation tracks two counters as it processes the event: fieldsCount for remaining leaf fields and nodesCount for remaining nested objects. When both reach zero, all pattern-relevant fields have been found, as shown in flatten_json.go:
if nodesCount == 0 && fieldsCount == 0 {
if pathNode.IsRoot() {
return errEarlyStop
} else {
return fj.leaveObject()
}
}
The errEarlyStop is not an actual error but a control flow signal indicating successful early termination. When the root node reaches this condition, the entire flattening process stops. So, no further bytes need to be read from the event.
The performance impact depends heavily on where pattern-relevant fields appear in events. For events where pattern fields appear early, the JsonFlattener_ContextFields benchmark improved from 9.06 microseconds to 0.21 microseconds (a whopping 43x speedup representing 97.7% time reduction). Events with pattern fields in the middle showed 83.5% reduction, while events where pattern fields appeared last showed no benefit since the entire document must be traversed regardless. Current benchmarks on M3 Max hardware show even better absolute numbers: 194.2 nanoseconds for early-field extraction with zero allocations, confirming the zero-copy optimization is fully effective for non-array fields.
Array Position Tracking and Correctness Link to heading
The ArrayTrail mechanism prevents subtle correctness bugs that would otherwise arise from array flattening. Consider an event containing band information with nested member arrays:
{
"bands": {
"members": [
{ "given": "Mick", "surname": "Jones", "role": "guitar" },
{ "given": "Joe", "surname": "Strummer", "role": "guitar" }
]
}
}
Without position tracking, a pattern looking for {"bands": {"members": {"given": "Mick", "surname": "Strummer"}}} would incorrectly match this event because both values exist somewhere in the members array. The ArrayTrail prevents this by marking each field with its array identifier and position. The matching algorithm checks for array trail conflicts before allowing state transitions, as implemented in core_matcher.go:
func noArrayTrailConflict(from []ArrayPos, to []ArrayPos) bool {
for _, fromAPos := range from {
for _, toAPos := range to {
if fromAPos.Array == toAPos.Array && fromAPos.Pos != toAPos.Pos {
return false
}
}
}
return true
}
If two fields come from the same array (same Array ID) but different positions, they cannot both contribute to a pattern match. The test suite includes comprehensive array correctness tests that verify this behavior prevents cross-element matches.
The array tracking does impose a performance cost. Code comments in flatten_json.go note that profiling identified storeArrayElementField as one of the most expensive functions, because it must allocate a new ArrayTrail slice for each array element field. The implementation accepts this overhead as a necessary cost for correctness as was the case within Ruler.
What This Enables Link to heading
Flattening transforms JSON’s flexible, hierarchical structure into a normalized form that automata can process efficiently. By converting unordered objects into sorted pathname/value sequences, Quamina gains the ability to use deterministic finite automata for pattern matching while maintaining the expressiveness of matching against structured events. The segments tree optimization ensures this transformation remains practical even for large events with complex schemas, achieving sub-microsecond flattening times when pattern fields appear early in events.
This foundation enables the core innovation in Quamina: compiling patterns into automata that share structure. When thousands of patterns need to match against each event, the flattening process runs once per event while the automaton processes the resulting fields in a single linear pass. The next post in this series will examine how patterns compile into automata and how multiple patterns share states to achieve constant-time matching regardless of pattern count.