Skip to content

Blog

The Long Division

An arbitrary-precision integer, and why division is the part everyone gets wrong.

Sixty-four bits runs out. A 256-bit hash, a base conversion, a counter that must never wrap, and suddenly you want a number with no ceiling that still reads like a * b + c. The sixth familiar is that number. Addition is easy and multiplication has a famous trick, but division is the operation that separates a bignum that works from one that is wrong on inputs no random test will ever find, and you will never know which.

The Planet as a Prefix

Turning the whole Earth into search terms a plain text index can answer.

'Find documents within 5 km of here' is not a text query, and you cannot scan your way to it. The trick Xapiand uses is to turn the surface of the Earth into a hierarchy of triangles, give every point a name whose prefix is its neighborhood, and let the text index do the rest. The fifth familiar tiles a planet so a search engine that only knows words can answer questions about space.

The Fork in the Path

Matching a URL to one of a thousand routes in time that ignores how many there are.

Every request that reaches a server is a URL, and something has to decide which of a thousand handlers owns it before any real work starts. The obvious router gets slower with every endpoint you add. A radix tree does not: it walks the path, not the table, and stays flat at a thousand routes. The fourth familiar, and the forks in its tree are where it gets interesting.

The Sparse Wheel

A lock-free timer from Xapiand whose insert never stalls another thread.

One thread in Xapiand sleeps while every other thread drops timed work onto its schedule: log lines, fsyncs, commits, replication. The drop can never take a lock, and more than that, it can never stall. The little data structure that makes both true is the strangest, best thing in the whole codebase, and the familiar I would keep if I could keep only one.

The Haunted Handler

Walking every thread's stack, portably, from inside a signal handler.

Sometimes the only useful question about a stuck server is 'what is every thread doing, right now?' traceback answers it by signalling every thread at once and having each photograph its own stack. The hard part is that the stack walk is one idea spelled nine different ways across Linux, macOS, and FreeBSD, run inside a signal handler where the wrong call deadlocks the process. The second familiar out of Xapiand, written half by reasoning and half by waiting for a red build on a machine I'll never log into.