It’s been a while. February was the last entry in this Quamina Diary; I never stopped working on it but there hasn’t been much blogworthy. This piece offers a progress update for those who’ve been entertained by Quamina, and also a pleasing (well, to me anyhow) dip into finite-automata theory and practice. With numbers and graphs and a bluesman!

Since it’s been so long, here’s what Quamina, a Go-language library, does: You can add “Patterns” to a Quamina instance, they match the values of fields in JSON objects, and then you show Quamina a JSON “Event” and it’ll tell you which Patterns matched it. It’s pleasingly fast and in many cases the speed is not strongly affected by the number of Patterns you’re trying to match.

The last release, V2.0.2 back in March, marked the arrival of a reasonably-full regular-expression dialect into Quamina’s pattern language, so you can say, for example, that the Filename field has to match map-[0-9]+.(png|pdf|jpe?g). Regular expressions were a lot of work and a lot of fun.

Finite-automaton wrangling · Quamina works by compiling the Patterns into finite automata, then matching the Event fields by traversing them. To handle multiple Patterns, Quamina merges the automata together, a technique that’s been well-studied in Computer Science for decades. From a set-theoretic point of view it’s a union; an OR through Boolean lenses. There’s really no limit in theory for how many patterns you can merge, and Quamina has no problem at all with thousands.

There are two flavors of finite automata: Deterministic (DFAs) and Nondeterministic (NFAs). If you have a university degree in CS they probably made you study this at some point. Weirdly, many people find the subject boring.

I’m not going to explain the differences, if you want to know it’s easy to look up, and anyhow the story I want to tell doesn’t need it. Here’s what the story needs:

1. To implement wildcards and regular expressions, you need NFAs.

2. Matching data with DFAs is generally a whole lot faster than with NFAs.

3. There’s a well-known algorithm for transforming any NFA into a DFA that matches exactly the same data. It’s really a lovely algorithm, you want to tickle it under its adorable little chin.

4. In some cases, the algorithm can be brutally expensive, along the lines of O(2N).

The benchmark from Hell · I found a data file in the Wordle source code with 13K or so 5-letter words. I inserted a * at a random location in each. To illustrate, here are the first five results: aah*ed, aalii*, *aargh, aar*ti, and abaca*.

The benchmark is, you load these into a Quamina instance and measure how fast it is to load them, how much memory the merged NFA consumes, and how many Patterns per second you can match. Then you repeat the exercise, converting each NFA into a DFA.

I loaded 10K Patterns in NFA form, but the NFA-to-DFA conversion got so brutal my patience only allowed me to load and measure 300 in DFA form. (Which kind of gives away this article’s punchline but stick with me, the details are fun).

Willie Dixon · He was a famous bluesman and I need help from him to explain my APIs.

Quamina’s latest PR adds APIs to turn the NFA-to-DFA conversion on and off; it’s off by default. There are two MatcherBuildMode values, BuiltForComfort and BuiltForSpeed. Which are out-takes from Willie’s 1959 song Built For Comfort, and the lyrics go like this:

Some people built like this, some people built like that,
The way I’m built, don’t you call me fat
Cause I’m built for comfort, I ain’t built for speed
…

Willie was a big guy, way over six feet and not exactly slender. I know this because I interviewed him once, but that’s another story. Lots of others have covered this tune, most of whom are, um, well-rounded.

Speaking of which… here is Quamina’s memory consumption in NFA mode.

The memory cost is pretty well linear in the number of patterns. For 10K patterns Quamina uses something over 25M which feels kind of reasonable to me.

Here’s the story for DFAs.

I haven’t run regressions or anything and I don’t think that’s actually O(2N), but the second derivative is solidly positive, which in simple English means “doesn’t scale”.

Now let’s look at the Pattern-addition time for NFAs and then DFAs.

· · ·

Once again, the NFA cost increases more or less linearly (albeit interestingly jaggedly), while for DFAs, look at that second derivative. This was what eventually made my patience give out and limit the DFA run to 300 Patterns.

Now let’s look at the payoff, the number of Event matches/second in NFA- and DFA-land.

· · ·

The NFA performance degrades at something like O(N-1), but DFAs just don’t care. After a few lurches it rolls along at between 500 and 600K/second. Not bad, and based on experience with huge DFAs that were built from exact string matches, my belief is that the matching speed would eventually drift down, but slowly, not remotely a linear function of the number of Patterns.

Not just pictures but numbers too · It was maybe a little unfair to compare 10K NFAs against only 300 DFAs, so let’s focus in. (This is on a 2023 M2 MacBook Pro.)

That’s pretty shocking stuff. 10K NFAs occupy less memory than the DFAs equivalent to 300 NFAs. And the Add-Pattern time, which is totally dominated by the NFA-to-DFA logic, is getting into intractable territory. So why would anyone mess with the DFA conversion? Because it matches data twice as fast!

Practical advice for Quamina users · First, if you’re a normal human being and only matching a handful of patterns against a few Events/second, ignore all this and just take the defaults, Quamina latency will vanish in the static. If you’re matching lots of numeric and string values against many Events/second, don’t lose any sleep, keep on packing in the Patterns and Quamina probably won’t slow down enough for you to even notice.

In theory you’d eventually get into memory trouble but in my considerable experience with Quamina and its AWS-built predecessor Event Ruler, you have to be venturing into extreme-craziness territory for that to happen. (It did happen. An Amazon group added literally a million Patterns. It still ran way faster than anything else they could find.)

If you need to match wildcards or regexps, adding Patterns stops being free. The slowdown is roughly linear in the number of Patterns and isn’t actually terrible, see the data above. But if you’re using a relatively small number of regexp Patterns, go right ahead and turn on DFA conversion with “BuiltForSpeed” mode.

What next? · There’s one minor Quamina feature that’s disabled in BuiltForSpeed mode, so I’ll need to fix that and do a release.

I bet there are still low-hanging fruits that could speed up the Hell benchmark, but anyone looking for those should bear in mind that they’re fighting settled Computer Science, you’re never going to make NFA-to-DFA conversion reliably linear.

But to be honest, Quamina is starting to feel fairly feature-complete. I’d like to see a few adapters so you could use Quamina with Protobufs and Thrift and CBOR and other formats that aren’t JSON.

But in fact Quamina doesn’t have that many users; I’ve only heard from a handful. Who knows, maybe the problems you learn to solve when you’re working at AWS, and most of the groups think millions of events per seconds is an ordinary workload, aren’t widely applicable in the broader world of Open Source?

Which is to say, me working on Quamina isn’t helping that many people. At one level, I don’t care, because it’s been fun and instructive. I’d probably enjoy turning this “Quamina Diary” series into a monograph or small book if there were an interested publisher.

And thanks to everyone who’s been reading along.