SQLite: 92 million lines of tests Dijkstra: Tests can only prove the presence of bugs, never their absence!
It can prove absence of specific bugs though.
no it can't. what if this bug is still there but the timing window is now one CPU instruction?
Tracking down the 16-year-old WAL-reset SQLite bug
131–140 of 263 posts
Re: Tracking down the 16-year-old WAL-reset SQLite bug
#132SQLite: 92 million lines of tests Dijkstra: Tests can only prove the presence of bugs, never their absence!
I admit to curiosity as to whether static analysis could have caught this. E.g., Rust's type system (yeah yeah I know) catches all data races, unless they originate in unsafe code, which this one might or might not have; a hypothetical Rust SQLite would probably need a lot of unsafe ( https://github.com/tursodatabase/turso has 556 unsafe blocks in the core), and I don't have a sense of whether the particular part tha…
I don't think they could. This is probably a memory-mapped file, which would be unsafe.
Re: Tracking down the 16-year-old WAL-reset SQLite bug
#133>In our control plane, we take manual control of the checkpoint process so we can run fast and consistent backups. > running boring technology in a non-standard way is a risk. It was a good read and reminder that the industry is loosing experts gradually. I am not a DBA and yet I have heard about this behavior at least couple times in the past as something to avoid. Its just one of those things which didnt get a chan…
I've never heard of any reliability reason you shouldn't run checkpoints whenever you want - only performance reasons. Can you elaborate?
Backing up sqlite by copying the file (e.g. rsync) while it's open is a surefire way to eventually get corruption caused by a race condition, but it seems like tailscale wasn't doing that. They were probably using the proper sqlite backup API.
But you don't need checkpoints for consistency and I think the backup API will not copy both the old and new versions of pages just because they're in the WAL, in other words I think checkpointing then backing up should give you the same pages as backing up without checkpointing. So the whole thing seems unnecessary.
Re: Tracking down the 16-year-old WAL-reset SQLite bug
#134Maybe it's just me, but the explanations of the cause don't align. One clue was that during corruption incidents, our metrics showed that SQLite would report copying more pages from the WAL file than were actually available. If there are 10 pages in the WAL file and 20 pages get copied to the database, something is clearly wrong. vs it thinks some of the pages have been copied from the WAL into the main database file…
Those seem consistent to me. Some pages weren't written to the WAL (yet?), but something else referenced them or otherwise indicated they existed, so then the other process tried to read them, resulting in the issue in the first quote.
The explanation says they were written to the WAL and then not written to the main database file.
Re: Tracking down the 16-year-old WAL-reset SQLite bug
#135What a brutal bug. I'd never entertain a that bug in SQLite could be causing problems in code I wrote.
That is the correct mentality, but sometimes, you’re wrong. I found (not entirely true; someone else [0] found it first, but my report from my company got traction [1] on it) a weird bug in ProxySQL several months ago involving mirroring and fast routing, where if you had a configuration that was illogical from the standpoint of documented behavior, it would duplicate queries, which led to super fun times for writes.
I spent hours empirically trying various scenarios before concluding that no, it was a ProxySQL bug.
Re: Tracking down the 16-year-old WAL-reset SQLite bug
#136> This investigation is a useful reminder: running boring technology in a non-standard way is a risk. The common paths and standard configurations are incredibly well-tested and reliable. Most people use SQLite in a standard configuration and never face this sort of issue. Everything we were doing was a public, documented, supported configuration—but by taking manual control of the checkpointing process and running a…
We have very good reasons for our checkpointing model, related to our backup + disaster recover strategy, along with resource cost. It might be worth writing about one day, so I'll not give away all the details, but in very short form, we organize a backup strategy that has minimal pause time, avoids doubling the page cache cost of the database, and enables extremely fast byte-copy restores in disaster recovery.
okay but explain why you are using sqlite and copying the file to S3 instead of using any client/server DB and its online backup feature?
Re: Tracking down the 16-year-old WAL-reset SQLite bug
#137Block device upfuckery layers are powerful against databases. Years ago some colleagues wrote one that provides most of the hazards described by "Parity Lost and Parity Regained"[1] to test FoundationDB, which immediately uncovered several flaws in a project that described itself as well-tested. It's easy to do this with all the probing features that Linux (and others) provide today. 1: https://www.usenix.org/legacy/…
With opus 4.7-ish to fable 5, immediately after release - before they locked it down, it was shockingly easy to find crash bugs in a lot of very heavily used DBs and other software.
Did you personally find them?
Re: Tracking down the 16-year-old WAL-reset SQLite bug
#138Earlier quoted context omitted.
There was a post recently using TLA to model this issue and (re)discover the bug: https://news.ycombinator.com/item?id=48730953 .
Interesting. I don't think this kind of technique could realistically have caught the bug in advance, though; you're not going to model the entire codebase in TLA+, so the investigation in that post modeled just the parts that turned out in hindsight to be relevant.
> you're not going to model the entire codebase in TLA+
Not by hand in the olden days but with AI to help with it, why not?
Re: Tracking down the 16-year-old WAL-reset SQLite bug
#139While technically true as written, it seems to downplay the significance: > The bug is a data race with tight timing constraints. It is unlikely to occur in common use. A large customer did experience this corruption, so it's important for people with tailscale's setup update immediately. > The developers have never been able to reproduce the bug organically and had to add special testing logic to SQLite that deliber…
Odd not to highlight the sentence where they answer the obvious question "Why Tailscale in particular?": > They also explained why we were more likely to hit the bug than other SQLite users: we take manual control of the checkpointing process, and we checkpoint very aggressively. Even a bug triggered by a rare condition was bound to hit us eventually.
The bug requires two checkpoints in very quick succession, which presumably isn't something sqlite would do on its own, as it would be a pointless waste of performance.
Re: Tracking down the 16-year-old WAL-reset SQLite bug
#140Was curious so we checked and yep, Antithesis finds this bug in about 15 minutes. Will post a repro/writeup here soon.
Discussion here: https://news.ycombinator.com/item?id=49277799
Wait, it's AI? AI probably has information about this bug by now, since it was discovered and fixed in March.