Skip to content

familiars

38 posts with the tag “familiars”

Sorted as Bytes

A number codec whose bytes compare like the numbers they hold.

An index compares keys as raw bytes, and it does not care that some of those bytes were an integer and some were a double. The thirty-seventh familiar makes that blindness safe: any number, in any of three types, becomes a short string whose byte order is the numeric order, exact down to the last bit of a 64-bit integer.

Everything but the Views

An HTTP server assembled from the familiars, with the defaults already chosen.

A table of routes is not a server. Before anyone can use it, something has to open a port, spread the work over the cores, shrink the replies, write down what came in and what went out, and explain a crash instead of hiding it. The thirty-third familiar is that something, assembled from the familiars before it, with every one of those decisions already made.

A Tree Made of Types

A word lookup the compiler builds letter by letter, and why it lost the race.

A dictionary does not make you read every word to find one; you follow the letters. The thirty-second familiar builds that path out of the compiler's own type system, one letter at a time, so a fixed word list becomes a tree that exists only while the program compiles. It is exact, simple, and slower than a perfect hash, and the numbers say by how much.

A Map of Blocks

How a search engine keeps every word it knows in a few bytes each.

A search engine has to remember every word it has ever seen, keep them in order, and find any one of them in a fraction of a microsecond, often from a file it has not even read yet. The thirtieth familiar is really two: a tiny machine that spells out a whole vocabulary in about six bytes a word, and the dictionary that uses it as a table of contents.

The Bag of Holding

The small, honest tools too little for a post of their own, and a look back at the whole party.

Not every tool earns its own chapter. This is the last of the campaign: the bag of small, honest libraries too little for a post apiece, tipped out onto the table so none of them is lost, and then a look back at the whole party we assembled from one search engine, and what it meant to take it apart.

The Names Enums Throw Away

Getting an enum's name back at compile time, which the language keeps refusing to give you.

The compiler knows the names of your enum members, you just wrote them, and then it throws them away, leaving you to hand-maintain a switch that maps each value back to its own name for every log line and every parse. The twenty-eighth familiar gives the names back, at compile time, through a perfect hash, so an enum and its strings are one constexpr mapping you can even check in a static_assert.

No Collisions, Ever

A hash table for a fixed key set, built entirely at compile time, that never collides and never branches.

An ordinary hash table has bad days: two keys collide, the lookup degrades to a probe or a chain, and worst-case is worse than average. If you know all your keys at compile time, you can eliminate the bad day entirely. The twenty-seventh familiar builds a minimal perfect hash over a fixed key set while the program compiles, so every lookup is a fixed handful of arithmetic and two array reads, forever, with no collision possible.

Before the Program Runs

Switching on a string, classifying a character, and coloring a terminal, all resolved at compile time.

The cheapest work is the work you do before the program starts. This is the compile-time chapter, and it opens with three small libraries that each move a runtime cost to zero: a way to switch on a string, a way to classify a character without the standard library's locale baggage, and a way to color a terminal with a single portable constant. All of it resolved by the compiler, none of it paid at runtime.

Work, Not Threads

Why a thread pool stops being enough, and what a work pool does instead.

A thread pool is the least surprising thing in a concurrent program, until thousands of owners share it. The twenty-fifth familiar started life as a thread pool and grew into a work pool: the same threads, but shared by owners instead of handed out by arrival, so a query never waits behind somebody else's housekeeping, and an idle pool costs nothing.

Sometimes a Mutex Is Right

A blocking channel that is not trying to be fast, only correct, with timeouts and a shutdown that actually drains.

After a chapter of lock-free structures that avoid mutexes at all costs, here is the honest counterweight: a queue that reaches straight for one. The twenty-fourth familiar is not chasing throughput. It is chasing the two things fast queues are bad at, waiting with a timeout and shutting down without losing or hanging on the items still in flight, and for those, a mutex and two condition variables are simply the right tool.

Built to Disappear

An atomic shared_ptr that becomes a one-line alias the moment the standard library grows its own.

You want to atomically swap a shared_ptr, publish a new version of some shared state without a lock of your own, and read it safely from other threads. C++20 finally standardized that, but not every compiler shipped it. The twenty-third familiar fills the gap where it is missing and, more interestingly, is written to delete itself the moment the standard library grows the feature, so the dependency has a built-in expiry date.

Many Ways to Be Similar

A family of string-distance metrics behind one interface, because there is no single answer to 'how close.'

There is no such thing as the string-similarity metric. A typo wants edit distance; a name wants prefix weighting; a jumbled word wants shared letters; a misspelling wants sound. The twenty-second familiar admits this and ships a whole family, edit distance, Jaro-Winkler, Jaccard, Dice, and more, all behind one interface, so choosing the right notion of close is a matter of picking a class.

Smith and Schmidt

Matching names by how they sound, not how they are spelled.

Smith and Schmidt are the same name, spelled two ways. Any system that matches on exact spelling will never connect them, which is a problem if you are searching for people, whose names arrive spelled every possible way. The twenty-first familiar reads a word the way it is said, not written, and emits two keys so that a name and its foreign cousin finally meet.

The Earth Is Not a Ball

Turning latitude and longitude into vectors you can do geometry on, on an Earth that is lumpier than a sphere.

Latitude and longitude are angles on a curved surface, and you cannot take the dot product of two angles. To do real geometry on the Earth, measure an angle between two cities, feed a region to a spatial index, you first turn each point into a vector in space. The twentieth familiar does that conversion, honestly, across an Earth that is neither round nor drawn on a single map.

Asking the Machine

Reading a host's own limits, on systems that each hide the answer somewhere different.

A long-running server should know its own limits: how many file descriptors it is burning against the cap, how much RAM the process holds, how much disk is left before writes start failing. None of those numbers has a portable source. The nineteenth familiar is the small, unglamorous library that asks each operating system for them in its own dialect, so the rest of the engine can just ask once.

The Syscalls That Lie

The EINTR retry, the fsync that isn't, and the one call you must never retry.

The POSIX calls at the bottom of every server are not as honest as they look. A read can be cut short by a signal and return having done nothing wrong. An fsync on macOS returns success without actually putting your data on the platter. And retrying a close() that was interrupted can silently destroy a file descriptor another thread just reused. The eighteenth familiar is the thin layer that knows all of this and does the boring, correct thing so the rest of the engine never has to.

Down the Flume

Streaming a whole database over a wire, compressed and checked, without holding it in memory.

Replicating a database means moving a file bigger than memory across a link, and doing it so that it arrives smaller, intact, and without ever loading the whole thing into RAM at either end. The seventeenth familiar is named after the wooden channel that floats logs downstream: you feed a file in one end and it comes out the other, compressed and checked, in bounded memory, at a ratio that turns bandwidth into headroom.

Who Owns the Tree

A JSON-shaped MessagePack value whose copies share nothing.

A search engine moves documents around all day, and in C++ the way you hand one over decides what it costs. The sixteenth familiar is the document value itself, and every document lives in an arena of its own: a reference reaches into it, a move hands it over, and a copy builds a whole new one. When Xapiand needed many threads to share one document, it froze it and shared a pointer instead.

Append Only

A blob store that never overwrites a record, so a crash can only ever cost you the last write.

The scariest moment for a datastore is the one where the power goes out mid-write. If your store overwrites data in place, that moment can shred a record that was already safe. The fifteenth familiar refuses to overwrite a record, ever: it only appends. A crash can lose the write in flight, and nothing else, and that single discipline turns crash safety from a hope into a guarantee of the format.

The Seam

An HTTP/1.1 framework that streams requests in, and buffers replies out unless asked to stream.

Most HTTP frameworks make you think about the server. This one gives you exactly one thing to implement, a handler that takes a request and writes a response, and hides the socket, the parser, and the event loop behind that seam. The fourteenth familiar streams where it has to, on the way in, so a multi-gigabyte restore never sits in memory, and buffers on the way out by default, which is what gives a reply its ETag, its byte ranges and its compression. A reply too big to hold can stream too.

One Loop Per Core

The part of every TCP server you keep rewriting, written once.

Every TCP server re-implements the same three unglamorous things: a pool of event loops across the cores, the accept loop that fans connections out to them, and the shutdown dance that tears it down without hanging. None of that is your protocol, and all of it is where the concurrency bugs live. The thirteenth familiar owns exactly that and nothing else, so a new protocol is a coroutine, not a runtime.

Interchangeable Parts

Three compression formats behind one interface, swapped by changing a single word.

Compression is a set of tradeoffs, interop versus speed versus ratio, and the honest answer is 'it depends,' which is useless if switching backends means rewriting your call sites. The twelfth familiar puts three incompatible formats behind one identical shape, so choosing between deflate, lz4, and zstd is a matter of changing a single word in your code, and nothing else.

The Shunting Yard

Turning a boolean query into something a machine can walk, in one pass over two stacks.

Infix is how people write boolean queries and the worst way to evaluate them, because precedence and parentheses mean you cannot just read left to right. Dijkstra's shunting-yard algorithm fixes that in a single pass with two stacks, reshuffling 'a OR (b AND NOT c)' into a form a machine walks without ever recursing. The eleventh familiar is that algorithm, and the query language it feeds never needs the parse tree at all.

Bytes You Can Type

A binary blob, rewritten as one big number in an alphabet a human can actually type.

Sooner or later a pile of bytes has to face a human: an id in a URL, a hash in a log line, a key read off a screen and typed into another. Hex is twice too long, base64 carries characters that break in URLs and look alike on paper. The tenth familiar makes bytes typeable by treating the whole blob as one enormous number and rewriting it in a friendlier base.

Packing a UUID

Shrinking a 128-bit id by noticing how much of it is not random.

A UUID is sixteen bytes, and we treat them as sixteen bytes of pure randomness. A time-based UUID is nothing of the sort: it is a timestamp and a clock and a machine id wearing a hex costume, and a stream of them from one server repeats itself enormously. The ninth familiar reads that structure and packs the same id into eight bytes, decoded in nanoseconds and sortable by time.

Sixteen Bytes Too Far

A streaming HTTP parser that never copies, and the one place it read past the buffer.

Bytes arrive off a socket in whatever sizes the network felt like: a whole request in one read, or one byte at a time, or a header split down the middle. A streaming parser has to produce the same result regardless, without copying and without ever reading a byte it was not handed. The eighth familiar does exactly that, except for the one line where it reached sixteen bytes past the end of the buffer, and only the sanitizer noticed.

The Line You Usually Cancel

Arming a 'this is taking too long' log on every operation, and paying only for the one that fires.

You want to know which operations are slow, but logging every operation is noise you pay for on the hot path. So you invert it: arm a 'log this if it is still running in 200 ms' line on every single operation, and cancel it, free, the instant the operation finishes, which is almost always. The seventh familiar logs the exceptions by speculating on everything, and it is the reason the sparse wheel was built at all.

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.

Session Zero

Sixty small libraries, one search engine, and the campaign to open them.

I spent years building a distributed search engine, and when I came back to it years later, the tools were what I most wanted to keep. Sixty-odd small, sharp libraries fell out of Xapiand, each one a self-contained idea worth knowing on its own. This is the campaign to open them, one familiar at a time.