So… I’ve had the most unreal week of coding. Zero exaggeration, I’ve halved the
RAM requirements of the search engine, removed the need to take the system
offline during an upgrade, removed hard limits on how many documents can be indexed,
and quadrupled soft limits on how many keywords can be in the corpus.
It’s been a long term goal to keep it possible to run and operate the system
on low-powered hardware, and so far improvements have been made, to the point
where my 32 Gb RAM developer machine feels spacey rather than cramped, but this
set of changes takes it several notches further.
But to roll back the tape to more somber times.
Marginalia Search went offline for almost a week due to some problems
with the latest release.
I won’t go into the details too much here, it was a string of fairly trivial
scaling problems in a process with a run time of 1 day when it works well
and 2-3 days when it doesn’t. Had to restart it a few times, mostly because
it ran out of RAM.
The cause of the outage was the fact that the system needs to go offline
during an index switch in the first place. If it could have staid online while
all this went on, nobody would have been the wiser…
The reason for this is that the URL database is wiped during an upgrade.
Inserting and updating rows in a database table rapidly approaching a billion rows
is slow, and the processes involved in loading the new data uses a crap-ton of RAM
and can’t co-run with the index service which does the same; and the primary key for
the table is also a 32 bit integer so … you can’t really go beyond 2 billion in the
first place.
While the processes to get the system up and kicking again were ticking along,
I had a moment to reflect on the problems, came up a plan to slay the dragons
responsible for needing any sort of outage, while at the same time drastically
reducing the system requirements.
The First Dragon: The URL database.
The URL database is one of the oldest components of the search engine and a
lot of the design decisions that went into it made sense at the time, but that
hasn’t been the case for years since. Everything about the system is alien
to how it looked back when the tables were first drawn up.
Migrating the data has been such a nasty prospect that it’s mostly been left to
be as-is modulo some fairly small changes (ALTER TABLE … takes a few hours in prod).
At the heart of the URL database is two tables that are only ever written to while loading a new
index, and only ever read via primary key lookups. There’s an additional index keeping paths
unique within domains, and it is just absurdly large for what it does.
There’s a URL table mostly responsible for assigning an unique numeric ID to each URL, and a PAGE_DATA table, where each PAGE_DATA entry contains information such as the title and description of a link, if we’ve indexed it.
So what if we smack these two tables together into a single table sqlite database,
keep the data real simple, make the loader process responsible for generating unique IDs,
and have some other table for enumerating URLs we aren’t indexing… yeah that’s pretty doable.
It’s an unconventional choice to mix sqlite and mariadb like this, but the two serve different needs.
The system needs a persistent view of the world, but that view is relatively small, like sub 1 GB most likely,
but also plug-and-play state changes (with state in the terabytes). It does fly in the face of every
conventional wisdom, but has real benefits.
So, something like this:
We’re still softly relating the DOCUMENT and DOMAIN tables across databases, but we never actually need to join
the two; in fact in a disaster scenario, the most important bits of the DOMAIN table can be re-constructed from the DOCUMENT table.
I’m glossing over some details…
Generate unique URL IDs with no index
The URLs table was using 32 bit IDs, and it was always on the brink of integer rollover
and a known scaling issue. Part of why the URL database is wiped is to keep the ID
column from overflowing.
This doesn’t really work if we want to generate unique IDs in a way that won’t require us
to keep a collection of each URL we’ve seen in memory. URLs are sometimes repeated so we
can’t just use a counter and increment each time.
Each record also had a DOMAIN ID, but each URL only has a single domain. In the old solution
there was a unique constraint on URL ID and DOMAIN ID. That’s not really desirable, as indices
get very expensive for tables this large.
So let’s construct a 64 bit ID instead of letting the database assign one for us. Say the lower
26 bits are an ordinal, bits 26-56 are a document ID, and the highest most bits are reserved for the
index to do sorting tricks with.
This permits about 67,000,000 documents per domain (~10x English Wikipedia), and 2 billion domains,
which is nearly 100 times as many domains as the number of domains Marginalia has seen referenced
anywhere on the web. Nice and future proof.
We’re moving a lot of data sanity responsibility out of the database and into the process that
generates the data, but they are a lot cheaper to enforce on that end so that’s a feature, if a
bit unconventional.
Unexpected Benefits
So getting rid of all these humongous indices and large tables mixing hot and cold URL data means
the MariaDB server doesn’t need 36 Gb of RAM anymore. The hot data left in MariaDB is a few hundred
megabyteas at most, and the server most likely won’t need more than 2 Gb assigned to it.
The SQLite data needs an index too, but only for its primary key, and the actual hot part of
the index should be sub-gigabyte. It’s this much smaller because we’re indexing an order of
magnitude less data, and the index is of a single 64 bit long. There is no additional unique
constraint!
Additionally, since the output from the loader is now just a bunch of files, it turned out to
be pretty easy to create an automatic backup of these files. That means that in the case of
a bad deployment, the system can recover from a disaster within a few hours as contrasted with almost
a week like before.
If I had stopped there, it would be a pretty sweet change, but I felt emboldened by the success
and decided to turn to the other piece of ancient technical debt.
The Second Dragon: Reverse index construction
The previous changes mostly affected the loader. It outputs a urls database and a (document,words[])-oriented
journal of document data. We need to transpose that data into something that is not only on the shape (word,documents[]),
but then make it indexable.
To help do this, a lexicon is used to map from keyword strings to a dense mapping of term ids. The first word you insert
gets id 0, the next word id 1, etc. This is basically a long->int open hash map. The system maps from string to long using
a 64 bit hash function.
The problem with this is that it gets full. This is mostly a Java problem, since Java doesn’t permit arrays with more than 2
billion entries; and the implementation used chokes all the way back at 1 billion. You can work around it, but even if you do,
the next problem is that at 1 billion entries, it uses 12 Gb of RAM.
The index service sits at a well-endowed 60 Gb RAM in production right now, most of which is off-heap memory so it could do with
going on a bit of a diet. It’s on-heap (i.e. within-JVM) size somewhat exceeds 32 Gb wich is especially unfortunate, as it prevents
the use of CompressedOOPs, which is something you really want in Java.
The old reverse index construction has, like the URLs table, been around for a hot minute. It’s mostly been around due to how
unpleasant it is to work with. I was really struggling to find a good abstraction while I originally built it, and it’s been
append only code since. It’s not made better by this inherently being very finicky programming. If anything is even the slightest
bit off, everything falls apart in deeply inscrutable ways.
Very loosely, the shape of the algorithm was something like this:
highestWordId = findHighestWordId();
long[] counts = new long[highestWordId];
for each word in each document:
counts[word]++;
// offsets[i] = sum(counts, 0, i);
long[] offsets = turnCountsToOffsets(counts);
write offsets to file
long[] documents = memory map max(offsets) longs in a file
for each word in each document:
documents[offsets[word]++] = document
// draw the rest of the owl
constructIndices(documents, offsetsfile)
We need a lexicon because of this part. We’re relying on the domain of word ids to be densely packed.
long[] counts = new long[highestWordId];
Other than requiring an absurd amount of RAM, there’s a subtle farther down in the code:
for each word in each document:
documents[offsets[word]++] = document
This part writes about a terabyte of data out of order to a memory mapped file. Since it is almost completely
out of order, most of these changes are constantly being committed to disk. You may have heard
that SSDs deal with random access much better than mechanical hard drives. For read access this is largely
true, for small writes it is not, due to an effect called write amplification.
In brief, every time an SSD updates a single byte anywhere on disk, it needs to erase and
re-write that entire page. To avoid this it has caches that gather adjacent writes into a single operation,
but these caches aren’t terabyte sized, and do nothing in this scenario.
So while we’re writing a terabyte, the hard drive is writing something like half a petabyte. This is understandably slow and puts an insane amount of wear on the disk.
For a long time a stopgap has been in placed called a RandomWriteFunnel, which buckets the writes
into smaller files first, and then writes the larger file in-order. This is very slow, but not
as slow as spraying and praying like the original algorithm did.
I’ve understood for a long time that this is not the civilized way of transposing index data. What you do instead is
to create a series of smaller indexes where everything fits in memory, and then you merge them. Merging sorted lists
is fast and even mechanical hard drives agree with the operation. Still a bit finicky though, especially since we’ll
merge sorted lists of sorted lists that need merging.
If you construct the index this way, you no longer need the lexicon! It’s possible to use the 64 bit string hashes
for term ids instead!
Initially a few head-scratchers cropped up:
-
The input to the index construction is compressed. How can parts of it be read quickly? — Don’t. Create multiple smaller files instead, and read them one by one.
-
What is a good way to merge indexes? — Don’t. Merge the data before the indexes are created.
An abstraction called a preindex is introduced, which is basically what was constructed in the
code sample above. Two arrays, one with wordIds, and one with counts; both indexing a third array
with document data.
- index-reverse/…/ReversePreindex
- index-reverse/…/ReversePreindexDocuments
- index-reverse/…/ReversePreindexWordSegments
Since the inputs are small, these preindexes are easy to construct as we can do most of it in RAM. It’s so much easier when you can do you can assume the data fits in RAM. We can then commit them to disk as we generate them, and add a subsequent merging step to construct one final preindex.
The preindex is finally turned into the reverse index by adding static btree indices to the words
table and each document block like before. This is a relatively quick process.
This does not only require much less RAM since the lexicon is out, it’s also quite a bit
faster than the original algorithm. But wait, there’s more! The lexicon had the unfortunate
side-effect of giving each set of processed data its own dialect, a word might be given one ID
in one run, but probably another ID in another run. This meant that you needed to process all data
at the same time. Foregoing the lexicon, it’s possible to merge disparate sets of data, and e.g.
reuse the output of processing a large set of seldom-changing data (say Wikipedia), and join it with
more frequently changing index data.
In closing
This set of changes has been absurdly successful. The system RAM requirement has been halved,
almost every single known scaling problem and operational paper cut has been addressed. It’s also
had unexpected benefits I’ve only begun to consider.
I wish I knew what happened, or how to replicate it. It’s involved more upfront design than I
normally do, by necessity. I like feeling my way forward in general, but there are problems where
the approach just doesn’t work. This is squarely within that domain.
Sometimes you just tug at the right yarn I guess, and then problems unravel one by one.
