Fuzzing - the gift that keeps on giving

It's been almost a year since I started fuzz testing Suneido database queries and it's still finding bugs. I assumed it would find bugs at first, and then peter out. But we set them up to run for an hour every night to catch any regressions and that has turned out to be very worthwhile. Of course, I'm sure I've fixed the last bug now :-)

I have a bunch of Go tests for the query code, and they have decent coverage. But they barely scratch the surface in terms of combinations of query operations. Passing these tests gives me little confidence that changes are correct.

We also have lots of application tests that do a lot of queries. But all the queries are written by humans and follow similar styles and approaches. The bugs found by fuzzing were not detected by the application tests. That's probably partly because I used those application tests to initially develop and debug the gSuneido query implementation. So those types of queries have been well tested and debugged.

It might seem obvious, but one thing the fuzz testing has hammered home is that making something work for "normal" cases can be quite different from making it work for every bizarre unreasonable case. I look at the failing queries from fuzzing and I think "no one would ever write a query like that". And yet, they are bugs nonetheless.

In most cases when the nightly fuzzing would find an error (a difference between the results from gSuneido and jSuneido) I could easily reproduce it. But occasionally it would depend on the randomly generated data. (e.g. that a certain value did or didn't exist) That could make it hard to reproduce the error to debug it. We tried saving the data from each run, but that was awkward. We ended up saving the seed for generating the random data. We could include that with the results and use it to recreate the data.

The data dependency made me realize that we weren't testing many sets of data, just one per night. Rather than generate more sets of data (slow relative to running queries) I changed the fuzzing to try several variations of the constant values in each query. That had a similar effect to trying different sets of data.

It wasn't entirely surprising, but it was interesting that the fuzzing didn't find any errors in the jSuneido query implementation. The fuzzing only detects differences between the implementations, it didn't tell me which was right and which was wrong. Several times I convinced myself that it was jSuneido that was wrong, but it always turned out to be gSuneido. The gSuneido query implementation started out very similar to jSuneido. But over the years it got refactored and improved and optimized. gSuneido's query optimization is now quite a bit more sophisticated, which means more complex, which means more bugs unfortunately. jSuneido has also been around longer so maybe that helped work out the bugs. It's also much more stable - I've barely touched the code for several years whereas the gSuneido code has been changing constantly.

Another aspect that was surprising was how "rare" some of these failing queries were. We are running about a million queries per night. I would have thought that would explore the possibilities fairly well. But some of the bugs were only caught once after weeks of running. In hindsight that shouldn't be surprising - there are an infinite number of possible queries, and when you add in the data dependencies, the failing cases are even more rare.

Like other fuzz testing systems, I accumulate the failing queries in a "corpus" and run them every time along with new random queries. Quite often these are the ones that fail again. They obviously are "tricky" queries as far as my query implementation goes.

One concern I had was whether my ad hoc random query generation would generate "all" the possible queries. There could be bugs that could not be "reached" by the possible range of queries I was generating. Obviously, I don't know if there are bugs it's missing. But judging by the bugs it has found, it seems to have quite good coverage. In theory it should probably be based on the query grammar (the reverse of parsing). I ended up using a random sequence of additions and substitutions. One of the challenges is to ensure that the query is still valid e.g. that the columns referenced actually exist in the sub-query.

When I get a failure, the first thing I try to do is simplify the query. Most of the time there are parts of the query that can be removed and it will still fail. It's a lot easier to debug if e.g. there is only one join in the query. This is a fairly mechanical process and could probably be automated. (More easily from the parse tree than from the query text.) But it only takes a few minutes to do manually so it's not worth the effort to automate. (As long as there aren't too many bugs!)

One issue with my current approach is that it depends on using jSuneido for comparison. But we have replaced jSuneido with gSuneido and we're not using it any more. It's also awkward to have to run two processes and compare the results. I decided to write a "simplest possible query implementation" within gSuneido. I procrastinated on this for a while because I thought it would be a lot of work. But it only took me a few hours. I have to remember that the complexity is not inherent in the operations, it's almost all from the optimization. It still uses the same parser, but that seems ok because that's not where the problems are. It doesn't use any of the normal query optimization or execution. And in a way it's better than using jSuneido since it's not at all the same approach. And it's easier to be sure the simple implementation is correct. The alternate implementation is quite slow and isn't suitable for large results but it's sufficient for the fuzzing. And to get around the slower speed, with it all being within one gSuneido process, it's easy to run multiple threads.

Poisoning Workers

As in worker threads, not people.

gSuneido uses an unbounded thread pool to handle client requests to the server. Most Go thread pools are intended to limit the number of goroutines e.g. to match the number of hardware threads. But in this case I want all the requests to execute in parallel, even if it wasn't the most efficient, so that all the requests made progress. Normally in Go you don't need an unbounded thread pool, goroutines are usually fast enough that you can just start a goroutine for each request. However, if the goroutine will need to allocate memory, either for the stack or for other things, then creating new ones every time becomes more expensive. One option is to use a sync.Pool to avoid the allocation. But that doesn't solve the cost of stack growth. (e.g. issue 1838)

In the old version of my code, each worker was responsible for terminating itself if it was idle. This was implemented with a timer that was reset by each request.

This seemed straightforward. I tested it and it worked fine. But then recently I added some metrics, including the number of workers, and I noticed the number of workers rarely went down. Definitely not dependably after the 5 second timeout. I puzzled over this for a while before I realized what was happening. If multiple worker goroutines are waiting to receive from the same channel, it's unpredictable which worker will receive the message. This doesn't seem to be defined in the language spec so I'm not sure if it's random (as the select statement is defined to be) or if the receivers are queued and processed first-in-first-out. It doesn't really matter for my issue. The bottom line is that tasks end up distributed over workers. So even with a low level of activity, workers tend to get at least one task per 5 seconds, and therefore they don't terminate.

I could dream up lots of complicated approaches but it seemed like there should be a simple solution. I could probably get away with just not ever killing workers. But then if a spike in load creates a bunch of workers, they will hang around forever, which isn't the best behavior. Searching the web, I found a lot of introductory material about goroutines and channels, and a lot of bounded thread pools, but not much on unbounded ones. I found lnquy/elastic-worker-pool, but that seemed more complicated than I needed.

Eventually I realized I could make the pool a "leaky bucket" i.e. just periodically kill a worker. That would ensure the pool would eventually shrink. This is very simple and doesn't require anything complex like trying to measure the load. The downside is that even if you're in a steady state with the correct number of workers, it's still going to kill workers and they'll end up being recreated. But a worker pool is really just a cache and a cache doesn't need to have 100% hit rate to be effective. I made a slight improvement by preventing killing too soon after creating a new worker goroutine.

I implemented this by having a killer goroutine that sends a "poison pill" to the same channel as the tasks. One of the workers would receive this and terminate itself.

The killClock and nworkers are atomic since they are accessed from multiple threads. The workers just needed to recognize the poison pill and terminate. The submit code just need to reset the killClock to zero whenever it created a new worker goroutine.

For example, if the interval is 1 second and the delay 10 seconds, in a steady state a worker would be killed and then recreated every 10 seconds. Given that creating a worker is almost fast enough to do on every task, that's very minor overhead.

Hopefully I haven't overlooked any flaws in this solution. It seems simple and fast.

As usual the code is on Github

A gSuneido Database Optimization

While working on the recent gSuneido database issue I had an idea for optimizing the transaction conflict checking code.

The current code kept a list of outstanding transactions and for each a list of tables and their reads and writes. To check a new read or write meant a linear search through all the transactions for other activity on that table. If the data was organized by table rather than by transaction, it would eliminate the linear search. An action on a "rare" table wouldn't have to look at so much data. Some tables would be common to many transactions, but still normally not all of them. And even in a situation where all the outstanding transactions included a particular table it wouldn't be any slower than before.

At a high level it was a small change, but I wasn't sure how it would fit with the code. I knew I'd still need to keep a list of transactions and the tables they had accessed. It turned out to be relatively straightforward to modify the code. (A few hours work.) One of the questions was where to embed data and where to use pointers to separately allocated data. Embedding tends to be faster, but embedding in maps or slices can use more memory because empty slots are larger.

Before starting the changes I wrote a Go benchmark so I could see what effect the changes had on performance. As usual, it was hard to know what a "typical" pattern of activity was. For this benchmark the new version was over twice as fast. That was a bigger difference than I'd expected. Sadly, but not surprisingly, the change made no difference to the speed of our application test suite. It doesn't do many concurrent transactions so it wouldn't benefit. However, the stress test I'd used to investigate the "too many outstanding transactions" issue did show big improvements. When I collected the same measurements as before and graphed them, it looked even better. Up to three threads it didn't make much difference but after that it was substantially better. And performance didn't drop off under load like it had before. (Or at least, not until much higher load.)

The conventional wisdom for optimization would be to profile the code and find the hot spots. That wouldn't have helped in this case. The impact of the data structure was spread over the code. Nor would profiling have given any insight into a better data structure. As I commonly find, what is required is to have good mental models of the problem, the code, the programming language, and the hardware. Then you need to find an approach that is a good fit between all of these. Of course, the hardware performance model is a moving target. These days it's mostly about cache misses and branch prediction.

I'm always happy to improve performance, especially by significant amounts. But in the back of my mind I can't help thinking I should have written it better the first time around. Of course, that doesn't make sense because you can't write the "perfect" version. There's always going to be room for improvement.

A gSuneido Database Issue

We've been gradually converting our customers' servers from jSuneido to gSuneido. Recently we converted a larger customer and they started to get "too many outstanding transactions" errors. Unfortunately, we'd changed multiple things at once with this customer, so it wasn't immediately clear whether this issue was because of the switch to gSuneido, but I suspected it was.

I had set the limit in gSuneido to the same value as jSuneido - 200 outstanding transactions. "outstanding" in this case either means uncompleted in progress, or completed but overlapping with an uncompleted one.

It seemed a little counterintuitive. gSuneido is faster than jSuneido. So why should it run into this more? My theory is that because it's faster, more transactions get processed and if some of them are slow this will mean more overlapping transactions, even though they completed quickly.

One of my first thoughts was to look at optimizing the gSuneido code. But if my theory was right, this could actually make the problem worse rather than better.

We temporarily solved the problem by adding slight delays to code that was using a lot of transactions. (i.e. we throttled or rate limited them). This worked but it seemed a little ugly to slow it down all the time, just to avoid a problem that only occurred occasionally.

That led me to add throttling to gSuneido, but only when the outstanding transactions got high (e.g. 100). Throttling would prevent hitting the limit (200). I wrote a stress test and this did solve the problem. And it was better than adding delays in the application code. But the problem was that once it throttled, it got really slow. If you throttled enough to prevent hitting the limit e.g to 10 transactions per second, then 1000 transactions would go from maybe .1 seconds to 100 seconds - ouch! And because throttling slowed things down so much, it increased the chances of transactions hitting the 20 second time limit. The cure seemed worse than the disease, it won the battle but lost the war. (Sorry for the proverbs.)

I started to wonder what the right limit was. 200 was an arbitrary value. The reason to have a limit was to prevent it from "falling over" under heavy load. But at what point would that happen? So I removed the limit and tested under different loads.

threads	time	tran/sec	conflicts	max trans
1	2 sec	5000	100	70
2	2 sec	10000	150	110
3	3 sec	10000	200	150
4	4 sec	10000	200	180
5	4 sec	12500	200	200
6	5 sec	12000	300	230
8	8 sec	10000	300	270
10	10 sec	10000	300	300
16	20 sec	8000	400	450
20	30 sec	7000	500	490
30	50 sec	7000	600	580

I was quite happy with the results. Performance did drop off with more than 5 or 6 threads, but not that badly. The maximum outstanding got well above the old limit of 200, but that didn't seem to be a major problem. The number of transactions aborting due to conflicts increased with load, but that's expected with that much concurrent activity. To some extent it seemed to be self limiting. i.e. the load itself slowed things down and effectively did its own throttling.

Of course, this is completely dependent on what my test is doing. Is it "typical"? No, probably not. For starters, it's doing continuous activity on multiple transactions as fast as it can, with no other work. Real application code is not going to be doing that. Our applications never do 10,000 transactions per second for long periods. The test does result in shorter and longer transactions, but the longest are only around 1 second, whereas in production we do see transactions taking much longer and sometimes hitting the 20 second limit (usually as a result of external factors). And my workstation only has 8 cores / 16 threads, so it's not really 30 threads.

Out of curiosity, I removed the limit from jSuneido to see how it would perform. 10 threads took 15 seconds or about 50% slower. That wasn't bad. But roughly half the transactions (5000) failed due to conflicts. Ouch! That wasn't so good. Even with only one thread, roughly 10% (1000) conflicted. As opposed to 1% (100) with gSuneido. The usual method of dealing with conflicts is to retry, but that would just increase the load and make things worse.

So what is the correct limit for gSuneido? Or should there be no limit? Should it ever throttle, and if so, at what point? Honestly, I still don't know the answers to those questions. But it does appear the limit could be considerably higher e.g. 500 instead of 200, which would likely eliminate the problem, other than rare extreme cases.

Keyword Recognition

Daniel Lemire's recent blog post Recognizing string prefixes with SIMD instructions and one he linked to Modern perfect hashing for strings prompted me to revisit how I was recognizing keywords in gSuneido. Although I find it interesting how you can use advanced processor instructions, I didn't really want to get into that. But like most things, even without looking at my code, I figured it could probably be improved.

I found that I was recognizing language keywords (28) with a linear search, sorted by frequency of occurrence. For query keywords I was using a Go map. Both were quite fast, certainly not a bottleneck.

The reason I hadn't used a Go map for language keywords was that I wanted to "intern" the strings. And there's no way to retrieve the key of a Go map (unless you loop through all of them). Normally it doesn't matter since you need the key to do a lookup in the first place. But the key I'm doing a lookup with is a slice from the source code. If I hold onto that key, it will keep the entire source code in memory (because the reference prevents garbage collection).

One of the first things I tried (Compile-time switches from the Modern article) was one of the fastest (4x faster than the old linear search) - switch on the length, and then switch on the i'th character (chosen for each length). For example:

switch len(s) {
case 2:
    switch s[1] {
    case 'f':
        if s == "if" {
            return tok.If, "if"
        }
    case 's':
        if s == "is" {
            return tok.Is, "is"
        }

I find it a little surprising that this turned out to be the fastest since it has quite a few branches - two switches plus a string comparison. Using Compiler Explorer to look at the assembler, I found the code was quite good. I was expecting a call to a string comparison function, but it is unrolled inline. It may actually be beneficial that the switches are explicit so each branch can get its own prediction.

Based on the assembler, I simplified the code. This was just as fast, smaller source code, and smaller machine code.

switch len(s) {
case 2:
    if s == "if" {
        return tok.If, "if"
    }
    if s == "is" {
        return tok.Is, "is"
    }

Because it was comparing constant strings and it knew the length matched, it compared them as multi-byte integers instead of strings. 2, 4, and 8 bytes matched int16, int32, and int64. For lengths of 3, 5, 6, and 7 it used a combination e.g. 6 characters was an int32 and an int16.

I did try various other approaches.

I tried finding "perfect" hash functions and table sizes, which turned out to be trickier than I thought. It was almost as fast as the switch version.

I tried another hash table implementation, but it was slower than the Go map.

I tried switching on the length and then doing a linear search.

In the end I went with the switch version since it was fastest. It was a little more verbose, but Tabnine handled most of the code generation.

Did this micro-optimization make any difference to the overall speed? No, not that I saw from a quick test. But it was an interesting investigation. And yes, premature optimization can be a mistake. But ignoring speed is also a mistake.

New Regular Expression Implementation for gSuneido

Suneido has its own regular expression implementation. 25 years ago, when I wrote the original C++ cSuneido implementation, there weren't a lot of regular expression libraries, and I already had an implementation from a previous product, so that's what I used. With the Java version, I initially tried to use the Java standard regular expressions. But it was too hard to get exactly the same behavior, so I ended up using my own implementation. And I did the same thing with the Go version of Suneido.

But I haven't been totally happy with my implementation. It uses backtracking (like many other implementations) which means it has some bad worst cases. I had to put limits on the backtracking, which meant we couldn't use regular expressions in some places, which meant hand writing code to replace them. To make it worse, there was no easy explanation of what kinds of regular expressions were ok.

Recently I re-encountered this series of articles about implementing regular expressions.

Regular Expression Matching Can Be Simple And Fast
Regular Expression Matching: the Virtual Machine Approach
Regular Expression Matching in the Wild

I'd read them before but at that point I'd been satisfied with what I had. The articles made it seem easy to implement a non-backtracking approach to avoid the worst case behavior. Of course, it didn't turn out to be quite that easy to write a full implementation. Naturally, the articles didn't cover all the details.

It started out as a weekend project, but it ended up taking me longer than that, partly because I implemented optimizations for literal strings and single pass expressions.

Because Suneido is ASCII only (due to its age), the code is a little simpler and faster than the Go standard library version which handles UTF-8.

The Go regular expression package compiles to linked structs that are relatively large. I chose to compile to byte code stored in a string. I like to use strings because they are one of the few constant immutable types in Go. And string references are only 16 bytes compared to 24 bytes for byte slices. There's probably a bit more overhead processing the byte code, but it's a more compact chunk of memory so it'll be more cache friendly.

Humorously (to me) when I was fuzz testing my implementation against the Go standard library implementation I discovered a bug in the Go code. As expected, one of the initial responses was denial, blaming it on my lack of understanding. Thankfully, someone else (not on the Go team) confirmed the problem and even located a possible location of the bug. I thought a bug in something like regular expressions would be treated fairly seriously, but over a month later it's still just labeled as "NeedsInvestigation" rather than "NeedsFix". It was put under the Go1.21 milestone at least.

The new implementation is about 2000 lines of Go code. Probably half of that I was able to reuse from the previous version. As usual the code is on GitHub

Full Text Search

Suneido uses full text search for its help and wiki. jSuneido used Lucene, a natural fit for Java. I needed something different for gSuneido. I looked at Bleve which seems to be the most common Go full text search. But it was big and slow, and the indexes were large. I had used Lunr.js on a previous project and it had worked well. It's small and fast and easy to use. It's JavaScript, but we display our help and wiki in a browser window so that seemed ok.

We (thanks Jatin) got it working, but it was a little ugly. Our customer systems have different combinations of applications and options so we built custom indexes on each system. But for Lunr we were using Node.js to build the indexes and we didn't want to install Node on all our customer systems. So we had to build an index containing "everything", ship that to our customers (every time we updated the help), and then filter the search results based on their configuration.

We only use our Wiki in-house, but with it there was another issue. People edit the wiki all the time. With Lucene, we could update the index with changes, but Lunr.js doesn't support that, you have to rebuild the whole index.

Eventually I got frustrated with the "friction" of using Lunr and decided to continue my long tradition of re-implementing the wheel. I'd considered writing my own full text index/search previously but had resisted the urge. But I had a weekend, and nothing urgent to do, so I decided to give it a try. I started with Let's build a Full-Text Search engine, which makes it sound easy, but mostly because the simple version it describes isn't complete.

Tokenizing is easy, although there are questions about exactly what constitutes a token. Obviously, sequences of letters, but what length? I decided to ignore single letters and also ignore anything over a certain length (e.g. 32 characters). Especially in our wiki we also wanted to search on numbers. There's also the issue of punctuation, which I'm currently ignoring.

I used the Go Snowball (Porter2) stemmer mentioned in the article. A stemmer simplifies words. For example, fishing, fished and fisher are reduced to the base form (stem) fish. That reduces the number of terms in the index and makes searching more forgiving.

I got sidetracked into looking at bitmap data structures like roaring bitmaps (as suggested in the article), but then I started looking at how to implement search scoring and found that bitmaps weren't sufficient, I needed counts per term per document, not just true/false.

I decided to use BM25 scoring like Lucene and Lunr. I found a good article that explained it and even gave some examples I could check my results against.

It came together surprisingly easily and by the end of the weekend I had about 1000 lines of Go code that could create indexes and search them. It was fast and the indexes were small (compared to Lunr). The results seemed comparable. I felt a little guilty because it meant throwing out all the work that went into trying to use Lunr. For a change I felt like I should have written my own version sooner.

Java 20

I don't program much in Java these days, just minimal maintenance on jSuneido. But I still have an interest in what's happening with the language.

Once upon a time, Java had a problem - no new releases for a long time. They solved that by switching to a fixed release every six months. For a while we got all kinds of new features. It was great. But lately it's been a new problem, the releases have been on time, but they haven't "released" much. Here's the complete list of features for the latest release:

Features

429:	Scoped Values (Incubator)
432:	Record Patterns (Second Preview)
433:	Pattern Matching for switch (Fourth Preview)
434:	Foreign Function & Memory API (Second Preview)
436:	Virtual Threads (Second Preview)
437:	Structured Concurrency (Second Incubator)
438:	Vector API (Fifth Incubator)

Every feature is either incubator or preview. I understand the need for incubator and preview. But "Fourth Preview" and "Fifth Incubator"? Yes, you want to get it "right", but if you wait for perfect in the eyes of committees, you could be waiting a long time.

I wonder if this is partly a matter of Java's "enterprise" association. Let's face it, the hip kids aren't using Java. They don't care if e.g. Java Virtual Threads are ever released. On the other hand the enterprise customers don't really want new features. They're still running Java 8. But they do want to be reassured that Java is alive and well. Previews and incubators serve that purpose just fine.

Maybe I'm just impatient. I'm excited about some of the new features (and others, like Valhalla that have been "coming soon" for many years but haven't even made it to incubation). But I don't have that many decades left.

Go Telemetry

There has been a big debate recently over the proposal to add telemetry to Go. 

It started with Russ Cox's multi-part Transparent Telemetry

I read the proposal and it seemed well thought out. I could understand the need to get more information about how Go was actually being used. Collecting a few anonymous counters seemed relatively benign compared to the "big" (i.e. invasive) data being collected by seemingly everyone these days.

Naively, I didn't foresee the big push back in the discussion at telemetry in the Go toolchain which was eventually locked after 506 comments. (518 thumbs down to 118 thumbs up)

I must admit I have a few qualms myself because it's Google. Go is it's own team, and I would say they have a good track record, but it's still Google paying their salaries and running their servers.

One point I missed until reading the discussion was that they would "temporarily" collect traffic logs with IP addresses. Supposedly this data would just be discarded, but how long until someone at Google decides they could "use" this data?

I think part of the knee jerk reaction was because it's a compiler. That seems wrong somehow. It's a bit reminiscent of the Ken Thompson hack. We may not like it, but these days we accept that Facebook and Apple etc. are going to track us. VS Code is one of the most popular editors, and it sends large amounts of telemetry. (I keep meaning to switch to VSCodium) I used to always opt in to sending telemetry because I wanted to help the developers. Nowadays I opt out of everything I can because it seems that most of it is just spying.

I don't have a lot to add to the debate. But I do have an idea/proposal that might help. How about if the telemetry was collected and published by a third party, someone with a vested interest in not abusing it. Perhaps someone like the Electronic Frontier Foundation. The proposal was already saying the data would be public. The Go team could access it from the public source just like anyone else. The Go team would still control the actual telemetry code, but since they wouldn't be collecting the data, it would be pointless to "sneak in" extra information.

It's a bit sad that it's almost impossible to collect legitimate data because so many big companies have abused data collection.

A Go Generics Technique

Say you want to make a generic hash map in Go. One of the questions is whether hash and equals should be methods on the key type, or whether they should be functions supplied when creating an instance. In general Go recommends passing functions. One of the advantages of this approach is that the functions can be closures which then have access to context.

In my cases I had a mix of uses. In several cases I already had hash and equals methods (from a previous incarnation). In several other cases I need context so closures would be better.

After a certain amount of head scratching I came up with a way to handle both.

Normally a generic hash map would be parameterized by key and value types. I added a third "helper" type. This type supplies the hash and equals functions. I created two helpers - one that calls methods on the key, and one that stores references to supplied hash and equals functions.

To use this the helper type you need an instance. A neat Go trick is that the helper that calls the methods can be struct{} - a valid type that is zero size, so no space overhead.

Getting the type constraints right took some experimentation. The key and value types do not have any constraints (any). The helper is parameterized by the key type. The helper that calls methods obviously is constrained by an interface with those methods. It confused me that the constraints that would normally be on the key type get moved to the helper, but I guess that makes sense because it is specific helpers that have requirements.

PS. Go has a built-in map type that is "generic" (but predates generics in the language). The problem is that it only works with types that have built-in hash and equals. If you need to write your own hash and equals, you can't use it.

Fuzz Testing Database Queries

The gSuneido database was ready for production, as far as I could tell. All our tests passed.

But there was a steady trickle of bugs showing up. Sure, they were obscure cases, but they were showing up in actual application code, so they weren't that obscure.

Every time I'd think it was ready to deploy further, another bug would show up.

I finally decided I had to do something to flush out these obscure bugs. Waiting for them to show up in production was not the way to go.

I had thought about trying to fuzz test database queries before, but it always seemed too hard. Even if I could figure out a way to generate random but legal queries, how would I check the results? Then I realized I could compare jSuneido and gSuneido. It wasn't a perfect test since they were roughly the same design and therefore could have matching bugs. But I had made enough changes and improvements to gSuneido that they were now significantly different. And even if it wasn't a perfect test, it was a heck of a lot better than nothing.

I puzzled over how to generate valid random queries. And what kind of data to use. I started with a simple set of four tables with obvious joins between them. The joins seemed to be the most constrained element, so I started with simply picking randomly from a fixed list of joins.

e.g. cus join ivc

I represented the query as a tree of nested objects and wrote a function to randomly pick a sub-expression branch.

unions are added by randomly picking a branch and replacing it with: branch union branch

e.g. (cus join ivc) union (cus join ivc)

leftjoins are added by randomly replacing some of the join's.

Then where, rename, extend, and remove (project) are added at random spots.

(((cus where ck = 12) join ivc) union ((cus leftjoin ivc) extend x1)) remove c1

Finally it optionally adds a sort.

The resulting queries aren't necessarily realistic, but they seemed to cover most of the variations.

It's a little more ad-hoc than I originally hoped. You could generate random queries from the grammar, and they would be valid syntax, but queries also have to have valid semantics, and that isn't represented in the grammar.

First I just parsed and optimized the queries, no execution. This soon triggered some assertion failures which uncovered a few bugs.

The next step was to compare the actual results between gSuneido and jSuneido. I decided the simplest approach was to calculate a checksum of the result and output queries and their result checksums to a text file. Then I could re-run those queries on jSuneido and compare the checksums.

In the end I found about a dozen bugs. Several of them were in jSuneido, which is a little surprising since it has been in production with thousands of users for about 10 years.

The problem with finding a bug through fuzzing, is that the inputs it finds are often messy. Some fuzzing systems will try to simplify the inputs for you. I just did it manually, starting the debugging of each failure by simplifying the query as much as possible while still retaining the failure. Fuzzing can make finding bugs easier, but it doesn't really help with fixing them. And the more you fuzz, the more obscure the bugs get. On the other hand, by the end I got pretty good at tracking them down, inserting prints or assertions or using the debugger.

I added all the failed queries to a "corpus" that gets run every time, along with new random queries as a defense against regressions. In theory they would get generated randomly again, but that could potentially take a long time.

I called it success when I ran about 500,000 queries (roughly two hours of processing) with no differences. The plan is to add this to our continuous test system and fuzz for an hour or so per night when we have spare compute power. That should prevent regressions and possibly find even more obscure bugs.

I'm pretty happy with how this turned out. It only took me a few days work to write the fuzzing system (not counting the time to actually fix the bugs), and it flushed out a bunch of bugs that I'm sure would have haunted me for a long time otherwise.

Of course, in hindsight I should have done this 20 years ago, or at least 10 years ago when I wrote a second implementation (jSuneido). Sometimes I'm a little slow! But better now than never.

Maybe the counterpart to Eric Raymond's "given enough eyeballs, all bugs are shallow" is "given enough fuzzing, all bugs are visible". (Of course, it's never "all", but you get the idea.)

AI

I used to think AI (when it finally "arrived") would help compensate for the many irrationalities of Homo sapiens. What can I say, I grew up on a steady diet of science fiction.

And now AI is arriving in the form of ChatGPT. And it successfully duplicates the failings of human brains. I could already get all kinds of biases, misconceptions, confabulations, and outright lies from humans, amplified by the internet. Now I can get it from AI too.

Even in the specialized area of programming assistance, I'm somewhat skeptical. Tabnine is a good, helpful tool. It claims it wrote 15% of my code in the last month. But when I review the highlights, they're one or two short lines of code. Not much 'I' in that AI. To me, the challenge in coding is writing coherent well organized code. Copying and pasting snippets will never achieve that. It seems to me it's just going to encourage even more boilerplate. Why not, when it's generated for you. Think how many lines a day you can "write". Most code is crap (including mine), and that's what these models are trained on. Even if you wanted to train it on "good" code, where do you find that? Who is going to judge it?

Perhaps this is just a temporary situation and AI will solve these problems. I'm not optimistic for the near future because it seems inherent in the current approach.

Although, there is perhaps some cause for hope: https://writings.stephenwolfram.com/2023/01/wolframalpha-as-the-way-to-bring-computational-knowledge-superpowers-to-chatgpt/

Meanwhile, after billions of dollars worth of research, self driving cars are currently a flop. I suspect that's a temporary setback.

Interesting times.

Three Weeks for Three Tweaks

It started with reports of slow database queries. At first I didn't pay too much attention, after all, some queries are slow. We're dealing with quite large data (in a small business sense, not in Google terms) and customers are choosing what to select on and how to sort.

It progressed to the same query being slow sometimes and fast other times. That seemed a little more suspicious, but there were still a lot of factors that might have explained it.

Finally someone came up with a simple example where the same query, ran on the same data, was 1000 times slower when you ran it slightly differently. That was bad news for me, since it definitely meant there was a problem with the query optimization. Why was it picking such a slow strategy sometimes, when there was an obviously better strategy. Especially when it was such an extreme difference. The optimization shouldn't have to be very accurate when there is a 1000 times difference!

It didn't turn out to be a bug, the code was working as designed. It was just a particular scenario that wasn't handled well by the current design.

After 20 years, the easy improvements have been made and I'm into the realm of diminishing returns. I ended up needing to "tweak" three aspects of the code in order to fix the issue. And all three were required before I could see if it was going to work. TL;DR - it did solve the problem.

One way of looking at the issue was that the optimization was getting caught by a local minimum. It wasn't smart enough to use a sub-optimal strategy in one spot in order to allow a better strategy overall. (It doesn't explore every possible strategy, for a complex query that would be far to slow.)

None of the changes were difficult, but they were all somewhat invasive, requiring changes to all the query operations.

Background

In case you actually want to try to follow what I'm talking about, here's a little background on how Suneido implements queries.

A query like:

(table1 join table2) union table3

gets parsed into a tree like:

where the leaves are database tables and the other nodes are operations. Each node has one or more strategies for execution, plus some parameters like choice of index.

Optimization starts with calling the optimize method on the root operation (union in this case) which then calls optimize on each of its sub-queries.

Execution works similarly by calling the get method on the root operation, which then "pulls" data from its sub-queries.

Tweak #1

Lets say we have a query like:  

table1 join table2 where id=1

During optimization, query operations can ask their children for their estimated number of rows. In this case join would get the table size from table1 e.g. 1000 and one (1) from the where since it's selecting on a unique id. But that information isn't sufficient to estimate the fan-out of the join.

So the first change I made was to return the "population" count in addition to the row count. The where could return 1 for the result count and e.g. 10,000 for the population i.e. table2 size. This allows the join to estimate a more realistic fan-out of 1:10.

Tweak #2

The next problem is when a temporary index is required, there are two costs - the "fixed" cost of building the index, and the "variable" cost of reading from it. But until now these had been combined into a single "cost". Other operations usually have only a variable cost.

Continuing the example from Problem #1, now the join can estimate the fan-out is 1:10, it can estimate it's only going to read 10 records from table2. So the variable cost will be low, but we'll still incur the entire fixed cost. So in this case we want to minimize the fixed cost. But to do that, I needed to separate the cost into fixed and variable parts everywhere.

Tweak #3

The remaining problem was that join didn't have any way to tell the sub-query that only a small part of the result would be read. To address this, I added a "fraction" argument to allow queries to tell their sub-queries how much of the result they estimated they would read.

In the running example, 10 rows from 10,000 would be a fraction of .001 Where before it would choose a strategy with e.g. a fixed cost of 1000 and a variable cost of 1000 (total 2000) over one with a fixed cost of 0 and a variable cost of 5000 (total 5000). Now the 5000 be multiplied by .001 giving 5, which is obviously preferable to 2000.

This allowed the optimization to avoid the local minimum.

Conclusion

I'm not sure how common the problem scenario is. It was only because we ran into such an extreme case (1000 times slower) that I got motivated to investigate. Perhaps less extreme cases also occur and will be improved by these changes. As far as I can reason, the changes should not make any cases worse.

Go Tip

Lets say you have a function:

func ShouldNotReachHere() {
    panic("should not reach here")
}

And you try to use it like:

func Fn(x int) int {
    switch x {
    case 1:
        ... return ...
    case 2:
        ... return ...
    default:
        ShouldNotReachHere()
    }
}

Unfortunately, that won't work. You'll get a "missing return" error when you try to compile. That's because the compiler doesn't know that ShouldNotReachHere never returns. (Actually, it does know that when it's compiling ShouldNotReachHere, but it doesn't keep track of that information.) C++ has [[noreturn]] to specify that but currently Go doesn't have an equivalent.

You could add a dummy return statement but I find that misleading since it will never actually return anything.

What I tend to do is add a dummy return type to ShouldNotReachHere (it's not critical what type since you're not actually using it).

func ShouldNotReachHere() int {
    panic("should not reach here")
}

and then use it like:

panic(ShouldNotReachHere())

If that was the only way you used it, then ShouldNotReachHere could just be a string constant. But defining it this way means you're not forced to use panic. (And if it was a function returning the string, then you could forget to use panic.)

Blogging, Suneido, and Programming Languages

Another blogger I follow has announced they are stopping blogging. It's sad (to me) how the world has shifted away from blogging. Of course, there are still active blogs, but far fewer than there were. I thought maybe the pandemic would give people time to do more blogging but it didn't seem to work that way. Of course, it always surprised me that smart productive busy people would take the time to write good blog posts.

I'm no exception. I post less and less often, other than photographs on my non-work blog. But even that is a shift from my past longer text posts. Readers have dwindled too. (Not that I ever had a big audience.)

But looking back through some of my blog posts, I'm glad I wrote them even if hardly anyone read them. It's a bit like a sporadic diary, but more thoughtfully written than a personal diary would be. I started blogging in 2005. It would have been interesting to go back farther but even in 2005 the tech world was a different place than today.

Thinking about this led me back here. I was writing a document for my staff, and some of it seemed of slightly more general interest so I thought I'd write about it.

Here's roughly when the versions of Suneido went into "production" (used by customers)

• 2000 cSuneido (C++)
• 2010 jSuneido (Java)
• 2020 gSuneido client (Go)
• 2022 gSuneido server
• 2022 suneido.js (browser client)

Two data points doesn't mean much, but it's interesting that it was roughly 10 years between the major versions. The concurrent release of suneido.js is because another programmer did the development. (I started it, but developing both gSuneido and suneido.js at the same time was too much.)

All three implementation languages (C++, Java, Go) were in their early stages when I started using them. I was lucky that all went on to become mainstream. Some of the other languages I considered, such as C#/.Net and Kotlin have also been successful. Scala and D not as much, although they're still around.

C++ is a fascinating language. But it's too complex and it's unsafe. Life is too short. (gSuneido does have some unsafe code to interface with Windows and it has been the source of the hardest bugs.)

Java has a world class runtime with a great garbage collector and JIT compiler. But the language itself is not really a good fit for low level systems programming. gSuneido, with a simple byte code interpreter and no JIT still manages to outperform jSuneido. If Project Valhalla ever gets released that will help. But it's been "coming soon" since 2014.

Go felt like a bit of a gamble at the time. The garbage collector wasn't very good and neither was performance. But the language was a good fit for implementing Suneido. And it seemed like Google was committed to it. Although I wish it was a little less of a one-company language.

One of the things that bugged me about Go was its lack of generics. But now that it has them, I don't really use them that much. The people that resisted generics would say "I told you so". But it did simplify certain kinds of code and I'm still glad to have it when I need it. 

I wish Go had better support for immutability. C++ and Java aren't much better but at least they have a little bit. Immutability (and pure functions) are one of the best tools to handle concurrency, and concurrency is supposed to be Go's strong point. I think there's potential for a conventional mainstream language with strong immutability. I realize there are functional languages with strong immutability, but so far they're not really mainstream.

The big thing these days is Rust, but Suneido is garbage collected, and unless you want to write your own garbage collector (no thanks, been there, done that) the implementation language also needs to be garbage collected.

As far as the Suneido language itself, I think it has stood the test of time reasonably well. It was never intended to be especially novel or original, although at the time object-oriented programming and dynamic languages were leading edge. There have been a few minor adjustments to the language, a bit of syntactic sugar here and there, but for the most part code written 20 years ago would still run today. There are a few things I'd change but overall, when I program in Suneido, there's not a lot I wish was different.

The Value of Fuzz Testing

Coincidentally after my Go Fuzz post yesterday, today I see:

Why Did the OpenSSL Punycode Vulnerability Happen

Buffer overruns aren't a problem with Go (unless you're using unsafe) but the lesson still applies. I should spend more time writing fuzz tests. Especially when the Go tools make it easy.

Go Fuzz

Go 1.18 included a new fuzz testing facility. (overshadowed by generics.) I haven't used it a lot but it has been helpful in a few cases. For example, I used it to test gSuneido's regular expression code and found a number of obscure bugs.

A few days ago, one of our customers got a runtime bounds error from parsing a date. This code has been running in production for years without seeing this error so presumably it was something obscure. The date parsing code is a little complicated because dates can be written many different ways. The error log didn't have the bad input, but it did have a call stack, so it probably wouldn't have been too hard to find the issue manually. But I was curious whether fuzzing would find it. And if there was one bug, maybe there were more.

To keep it simple, I didn't check for correct results, so the test was just looking for panics.

One of the things that should be simple, but I found confusing, was how to actually run fuzz tests. I'm not sure if it's the simplest, but this seems to work:

go test -fuzz=FuzzParseDate -run=FuzzParseDate

Within a few seconds the fuzz test found an input that would cause a panic.

"0A0A0A0A0A0A0A0A0A00000000"

That's probably not what the customer entered, but it was the same bug, and easily fixed once I could recreate it.

I let it run until it was no longer finding "interesting" inputs which took a few minutes. It didn't find any more bugs.

Ideally the test would be checking for correct output, not just lack of panics. But that requires a second implementation, which I don't have. Sometimes you can round-trip e.g. encode/decode but that wouldn't work in this case.

Git + Windows + Parallels + make + msys sh + Go

Git recently made a security fix. Unfortunately, it broke things for a lot of people, including me. Just in case anyone else has a similar obscure setup (and for my own notes), here's how I solved my issue.

My configuration is a bit off the beaten path.

• I am working on a Mac
• I have my git repos in Dropbox
• I use Parallels to build and test on Windows
• I use make to run my go build
• make is using msys sh as its shell

As of 1.18 Go includes vcs info in builds. So when I ran a Go build on Windows, it would fail with:

# cd x:\gsuneido; git status --porcelain
fatal: unsafe repository ('//Mac/Dropbox/gsuneido' is owned by someone else)
To add an exception for this directory, call:
        git config --global --add safe.directory '%(prefix)///Mac/Dropbox/gsuneido'
error obtaining VCS status: exit status 128
        Use -buildvcs=false to disable VCS stamping.

Adding -buildvcs=false did get the builds working, but it seemed ugly to disable a Go feature to work around a Git issue. It also didn't help if I wanted to do other Git commands.

I struggled with adding the safe.directory. I wasn't sure if %(prefix) was literal or was a variable. I also wasn't sure about whether it should be forward slashes or back slashes and how many (a perpetual issue on Windows). And I wasn't sure about the quoting. Eventually, I just edited my .gitconfig with a text editor.

Here's what worked:

[safe]
	directory = %(prefix)///Mac/Dropbox/gsuneido

Now I could do git commands.

But my build still failed with the same error!?

make is using msys sh as its shell. And sure enough, from within sh, I was back to the same error. git config --global --list didn't show my safe directory. That turned out to be because my home directory from inside sh was different. If I ran git config --global --add safe.directory from within sh, then it created another .gitconfig in /home/andrew. Now I could run git commands from sh, and now my build works.

I'm a little nervous about having multiple .gitconfig files, one on Mac, one for Windows, and one for sh on Windows but I don't have anything critical in there, so hopefully it'll be ok.

I'm all for security fixes, and I try to keep up to date, but it's definitely frustrating when it breaks stuff.

A Better LRU Cache for gSuneido

When I was working on gSuneido performance I discovered that the LRU cache in the standard library was one of the hot spots.

It was a simple design - a hash map of keys to values, plus an array of keys to track which was least recently used. When I wrote it, many years ago, it was just a quick addition. I had no idea it would be a heavily used bottleneck. Usage increased a lot when we added the easy ability to memoize a function.

I actually had to work backwards to find that LruCache was a bottleneck. What I first discovered (with the Go memory profiler) was that deepEqual was doing the majority of allocation. It was being called by SuObject Equal. The allocation was to track which comparisons were in progress to avoid handle self referential data. I was able to tweak deepEqual to greatly reduce the allocation. That removed the majority of the bottleneck.

But why were there so many object comparisons? I added debugging to print the Suneido call stack every 100 comparisons. It was coming from object.Remove which was being called by LruCache. To maintain its LRU list, it would move items to the most-recently-used end of the list by removing them and re-adding them. Since this was just an array, to find the item to remove it, it did a linear search. i.e. a lot of comparisons. Originally, caches had mostly been small, as you could tell from the default size of 10. But now the most common size was 200. 10 is reasonable for linear search, 200 is not so good.

In addition, originally keys were simple values like strings. But keys often ended up being several values in an object. The combination of linear searches through long arrays of composite values is what led to the bottleneck.

I decided to make LruCache built-in i.e. written in Go. But I also needed a new design that would avoid the linear searches. The normal way to track LRU is with a double linked list. I started in that direction but linked lists are not a good fit for modern CPU’s. Because the entries are individually allocated they are scattered in memory which leads to CPU cache misses. Contiguous arrays are much better because memories are optimized for sequential access. You could store the linked list entries in a contiguous block, but you still have the overhead of pointers (or indexes) and you still don't have locality or sequential access.

I ended up with the following design.

• an unordered array of key, value pairs (entries)
• a hash map of keys to entry indexes (hmap)
  
• an array of entry indexes in LRU order

A successful lookup becomes slightly more complex - look in the hash table for the entry index, and then get the value from the entries array. Finally, we have to find that entry index in the lru array (a linear search but of small integers) and move it to the most recently used end.

The hash table lookup will still require comparing multiple argument objects, but much fewer than a linear search.

To replace the oldest item, we take the entry index from the least recently used end of the lru array. From that entry we get the key to remove it from the hash table. And we reuse that slot in the entries array to store the new key and value.

The new built-in LruCache was about 100 times faster than the old one. Overall, it improved the speed of our application test suite by about 5%. That’s pretty good for a couple days work.

ASIDE: There are two main aspects to a cache. The focus is usually on which items to evict i.e. least recently used or least frequently used. The other aspect is which items to add. The normal assumption is that you add everything. But actually, you really only want to add items you’re going to be asked for again. Otherwise you’re evicting potentially useful items. We can’t predict the future, but we can assume that items we see twice are more likely to be seen again. One approach is to use a bloom filter to track which keys you’ve seen and only add to the cache ones you’ve seen before.

Checking Immutable Data

The database implementation in the Go version of Suneido relies a lot on immutable data that is shared between threads without locking.

The problem is that Go has no support for immutability. It doesn’t have const like C++ or even final like Java. (Go has const but only for simple numbers and strings.)

I was seeing some sporadic crashes and corruption. One possible cause was something accidentally modifying the theoretically immutable data. The immutable database state is a large complex set of linked structures processed by a lot of complex code. As with a lot of immutable persistent data structures you don’t copy the entire structure to make a new version, you basically path copy from each spot you want to change up the tree to the root. It's easy to miss copying something and end up mistakenly modifying the original.

I had recently been using checksums (hashes) to verify that the data read from the database file was identical to the data before it was written. (To verify the reading and writing code, not to check for hardware errors.)

I realized I could use the same checksums to detect erroneous changes to the immutable state. I ran a background go routine that looped forever, fetched the state (atomically), computed its checksum, waited a short time (e.g. 100 ms) and then computed the hash again (on the same state). If something had incorrectly mutated the state the checksum would be different.

And I actually found a few bugs that way :-)

Although unfortunately they were not the ones that were causing the crashes :-(