Learn

Architecture & pattern guides

Read the idea, build it on a Grid, prove it in a challenge. Short, practical guides — illustrated with RodGrid's own nodes — on system design, design patterns, flow modeling, and how to get the most out of the app.

All articles

Data structures behind big systems

A store is fast at what its internal structure makes cheap. One logging platform meets the LSM tree, the Bloom filter, the inverted index and HyperLogLog, and each buys its speed or its small size by giving something up: read cost, write cost or exactness.

Three questions, four structures

"Show me every line of request 7f3a91." That is the question an engineer types most often into a logging platform, and two others follow close behind: find yesterday's lines that say connection reset, and tell me how many different customers hit an error at checkout this morning. The platform takes in about 300,000 lines a second from 2,000 services, and at that volume no single structure answers all three cheaply. A store is fast at what its internal structure makes cheap, and each structure buys that speed, or its small size, by giving something up.

Three hundred thousand writes a second

Start with the writes. Index the lines by request id with a B-tree (Indexing & query optimisation covers how one works) and each insert lands at a random place in the index, because request ids are random. That is cheap while the index fits in memory. A day of lines, around 26 billion, does not fit, and then many inserts need a page read from disk and written back: small random I/O, the kind storage does worst.

A log-structured merge tree, or LSM tree, never updates in place. Each write goes into an in-memory table, the memtable, kept sorted by key: here the request id, the line's timestamp and a per-line sequence number, so one request's lines sit together and no two lines share a key. When it reaches its size limit, tens of megabytes say, it is written out in one sequential pass as an immutable sorted file, and a fresh memtable takes over. In the background, compaction merges sorted files into fewer, larger ones and drops entries that were overwritten or deleted. Random writes have become sequential ones, which is why Cassandra, RocksDB and LevelDB swallow write-heavy loads that would grind a B-tree. (Memory does not survive a crash, so each write is first appended to a log on disk; Write-Ahead Log explains how that makes a crash recoverable.)

Reads pay for it. A request's lines arrive over a few seconds, during which the memtable may be flushed more than once, so a read of 7f3a91 checks the memtable and then sorted files, newest first, since any of them might hold some of its lines. One logical read becomes several file reads: read amplification. Compaction costs too, rewriting the same bytes several times as files merge, I/O that competes with incoming writes. For a platform that writes far more than it reads, the trade is right; for a read-heavy workload it can be the wrong one.

Most files do not hold the request

Most of those file reads find nothing: the request's lines sit in one or two of perhaps twenty files, and the lookup cannot tell which without asking each one "could you hold this key?"

A Bloom filter answers exactly that. It is a bit array, all zeros at first, plus k hash functions. Adding a key sets the k bits its hashes point to. Checking a key reads the same k bits. If any is zero, the key was never added: definitely not. If all are one, the key is only possibly there, because other keys may have set those bits. So false positives are possible and false negatives are not, provided every key was added and none removed. Clearing bits to remove one key could clear bits another key relies on, which is why a standard Bloom filter cannot delete; counting variants can, with more memory.

The LSM store builds one filter per sorted file, over the request ids in it, as it writes the file, and since the file never changes, nothing ever leaves its filter. A lookup skips every file whose filter says definitely not. The size is fixed up front from the number of keys and the false-positive rate you accept: about 10 bits per key, with around seven hash functions, gives roughly 1%. A file with a million keys needs about 1.2 MB of filter, small enough for memory, and the lookup that checked twenty files now opens the one or two holding the request, plus about 0.2 of a file on average wasted on false positives.

The filter answers "is this exact key here?", so it helps a lookup by request id and does nothing for a scan over a time range. And a possibly is only a maybe: treat it as a yes and every false positive becomes a wrong answer, so the filter only ever lets you skip work and the real lookup still decides. The same move guards expensive checks outside databases: skip the disk read, the cache miss or the "is this username taken?" query when the answer is definitely no. A crawler's check for URLs it has already seen is the classic case (Worked design: a web crawler).

A word, not a key

The second question is a search: yesterday's lines containing connection reset. The log store is sorted by request id and the words could be anywhere, so against it this is a scan. In SQL it would be WHERE message LIKE '%connection reset%', and with a wildcard in front an ordinary B-tree index cannot help, so the query reads every row in the time range.

An inverted index turns the question around: for each term, the list of documents containing it, its posting list. A query intersects the lists of its terms; for a phrase it also checks the word positions stored in them, so the terms must sit side by side. A search engine ranks what is left. That is the heart of Elasticsearch and of full-text search generally.

This time writes pay: each new line is split into terms and added to the posting list of every one of them, and many engines apply those updates in batches, so a line becomes searchable shortly after it arrives rather than at once. The index answers only this question, so the ingest worker writes each line twice, to the log store and to a search index beside it. For splitting text into terms, ranking, and keeping the index in step with the store of record, read Full-text search.

Counting people, not lines

The third question sounds like counting and is not quite: how many different customers hit an error at checkout this morning? SELECT COUNT(DISTINCT user_id) has to remember every id it has seen in order not to count it twice, so the space it needs grows with the answer, and over billions of rows behind a dashboard tile that refreshes every minute, that is the expensive part.

HyperLogLog estimates the number of distinct items without storing them. It hashes each item, lets part of the hash pick one of many small registers, and keeps in that register the longest run of zeros seen before the first 1 bit in the rest of the hash; long runs are rare, so they reveal how many distinct hashes went past, and the same customer seen twice changes nothing. Redis exposes it as PFADD and PFCOUNT: up to about 12 KB per key, with a standard error of 0.81%, whether the key has seen a thousand ids or billions.

The ingest worker runs PFADD with the user id of each checkout error, into one key per hour, and the tile runs PFCOUNT over the morning's keys, which estimates the size of their union; merging sketches adds no error of its own. An error of a percent or two is invisible on a chart, which is when a 12-kilobyte sketch beats a 12-terabyte table. What HyperLogLog cannot do is say who: it cannot list the customers, tell whether one of them is included, or take an id back out, and an intersection (customers who failed both today and yesterday) can only be estimated from unions, with much larger error. When every item must be counted exactly, Counting at scale has the techniques.

One stream of lines, three structures

The ingest worker writes each line to the log store and the search index, and the user id of each checkout error to the distinct-user counter; the query service asks each one only the question its structure answers cheaply.

Skip the store, on a Grid

The Bloom Filter Challenge takes the middle of this article on its own: a filter in front of a slow store. A good design makes the definitely-not path visibly bypass the store, sends the possibly path on to the real lookup, and says next to the filter what a false positive costs (one wasted read) and why a false negative cannot happen while nothing is removed from the set. The Web Crawler Challenge puts the same filter on URLs already seen, billions of them, where a false positive means a page that is never crawled; whether the frontier can live with that is the question to settle there.

Practice this