Storing a log archive's Bloom filter index in S3 object keys

The expensive part of searching logs archived in S3 is reading the objects. This design prunes with Bloom filters, fixed-size summaries that rule data out for certain, stored inside the keys of zero-byte S3 objects: one paginated LIST returns a time window's filters with no GETs and no index server. The filters fit under S3's 1,024-byte key cap because the 10x engine rewrites each line at ingest as a stable hash of its format string plus the values that varied, so constant words never reach a filter. An exact re-check on fetched bytes makes every returned event a true match.

When logs are archived to S3, the expensive part of a search is reading the objects, so the first job of any query targeting a bucket is deciding which objects not to read. The standard tool for that is a Bloom filter, a small fixed-size summary that can rule a chunk of data out for certain. The filters in this design are ordinary; what is unusual is where they are stored.

Each filter is serialized into the key of its own S3 object, as the last segment of the path, and the object itself is zero bytes. One paginated LIST streams the filters for a time window back, up to a thousand per page, and pruning reads only key names, without a GET and without an index server to run next to a bucket that already solves durability and access.

The catch is that an S3 key holds 1,024 bytes at most. A filter fed every word of every message would overflow it, and splitting it across more keys explodes the number of keys a query has to list. The design has to keep the number of filters per time window low, and each one small enough to fit in a key.

The shrinking happens at ingest. Every log line is printed by a format string somewhere in code, and from one line to the next only the values change. 10x recognizes the format string behind each event and rewrites the event as a stable template hash, a short identifier for the line's constant skeleton, plus the values that filled it:

2025-10-02 00:17:22 +0000 [info]: #0 starting fluentd worker pid=18 ppid=6 worker=0

ships as

~R}>PZj;Jdp,1759364242000,0000,fluentd,18,6,0

That encoded form is what a plain SELECT decodes on ClickHouse. The constant words never reach a filter; what goes into one is the hash plus the few values that varied.

Those events land in an S3 bucket in the account that owns the logs, and this post is about how that archive answers queries by message identity with no log analyzer anywhere in the retrieval path.

The index layer, the writer, the query path, the filter encoding, and the S3 access underneath, every class this post names, is Apache 2.0 at github.com/log-10x/pipeline-extensions. The 10x engine that rewrites raw lines into template hashes is the paid product, and it is not in that repo.

Each filter is written as a zero-byte object

Log events reach S3 through the forwarder that ships them, and the index writer runs beside that forwarder, processing the same events as they are archived.

It gathers elements per time bucket and per byte range of the object being written: the template hash of each event, each variable value as it appeared, and the enrichment values the pipeline attached alongside the event (a service name, a pod), split into tokens. That element set becomes one Bloom filter, built with the orestes-bloomfilter library.

A Bloom filter is a fixed-size bit array that answers a membership question: definitely absent, or possibly present. Elements set bits on the way in; a lookup checks the same bits. Accuracy costs bits: a lower false-positive rate needs a bigger array, which matters once the filter has to fit in a key.

AWS caps an S3 object key at 1,024 bytes of UTF-8; MAX_S3_KEY_BYTES in AWSIndexAccess pins exactly that number.

IndexFilterWriter serializes the filter into a printable string and joins it onto a path that already carries the routing facts a query needs: an app prefix, the time bucket, a short hash naming the archived object, and the index of the byte range this filter covers. The filter string becomes the final path segment, and the writer PUTs the whole thing with a null stream and a content length of zero.

Fitting under the cap is a negotiation with the false-positive rate. The builder encodes the element set at the configured false-positive target, 1% by default, and measures the whole key, path plus filter, against the 1,024 bytes.

At that default there is no accuracy left to trade. 1% is both the rate the builder starts from and the loosest rate it will accept, so the first key that measures over the cap splits the element set in half immediately, and each half is encoded and measured the same way until the pieces fit. A split is what produces sibling filters for one byte range. No element is ever dropped to fit.

One thing is deliberately absent from the filters: the message text. The human-readable skeletons live once each in a template dictionary nearby, deduplicated by template hash and folded into merged snapshots, so the text a person eventually reads is stored once per message type rather than once per filter.

The template is what shrinks a filter into a key

When I wrote about log events carrying class knowledge, I ended on a promise: templates also shrink the Bloom filters that route queries across S3 archives. A keyword index has to answer for every word of every message, so the constant words dominate it: starting, fluentd, worker, repeated across millions of lines, all of it stored so text search can find it. Here those words never reach the filter.

The engine collapsed them to a single element, the template hash, back at ingest, and what remains per event is the handful of values that varied. Fewer elements need fewer bits for the same false-positive rate, and fewer bits is the difference between a filter that requires an object body and one that fits in what a 1,024-byte key has left after its own routing path.

That only works because the hash never changes. Each hash is computed from the format string's fixed words and the punctuation around them, never from runtime values, so the same message type produces the same hash on every host and every deploy; why that holds is its own post.

An index keyed on a grouping that drifts would strand every filter written before the drift. This one is keyed on the message's format string.

A query is one LIST, then ranged reads only where filters survive

IndexQueryWriter opens with ListObjectsV2 against the index prefix, a start-after cursor dropping the scan at the query window's first time bucket. Keys come back in lexicographic order, and the time bucket at the front of the variable path makes lexicographic mean chronological.

Each key parses back into routing facts plus a filter: EncodedBloomFilter serialized the bit array into the key on write, and DecodedBloomFilter rebuilds the same filter from the key string at query time.

Two tests run against that in-memory filter. The identity test asks whether the filter could contain the queried template hash. A value clause evaluates against the same already-decoded filter, one more membership lookup by QueryFilterEvaluator, so it costs memory reads on data the LIST already delivered and adds zero S3 requests.

A filter that survives names its target: which archived object, and which byte range within it. Each surviving object then costs a small read of its byte-range index, an object that does have a body, to turn a matched filter into byte offsets.

Surviving ranges against the same object collapse into a single ranged GET spanning the start of the earliest range to the end of the last, and the reader consumes the wanted ranges while skipping the gaps in-stream. On those fetched bytes the query's predicate runs once more, exactly this time.

That re-check is the correctness story, stated precisely. A Bloom filter never denies an element it holds; at the level of a single filter there are no false negatives, only false positives, and a false positive costs a wasted fetch rather than a wrong result. The exact match on fetched bytes is what makes every returned event a true match. A query for one message type misses no range that holds it, because that hash lives wholly inside a single filter.

The pruning bill is the LIST itself, a page per thousand filters paged in sequence, so the width of the query window sets both the wait and the request count. A byte range full of unique values, request IDs and the like, splits into more sibling filters, which the LIST pays for as more keys.

An index service would have been a second database

The alternative was an index service: an OpenSearch cluster over the archive, or a small database of postings per prefix, something with an endpoint. I refused, because each of those is a second stateful system whose durability, replication, and access control have to be re-solved next to a storage service that already solves them.

A filter stored in a key inherits every guarantee the bucket already has, and its read API is LIST, which any process holding the bucket owner's credentials can call. Between queries this index consumes no compute anywhere.

Cribl Search is the obvious comparison: it does query logs sitting in object storage. Cribl Search stands up search compute, wherever it runs, and answers by reading the objects' contents.

This design needs neither piece: pruning is a LIST issued with the bucket owner's credentials, and retrieval is by stable message identity. Identity means a query for a message type finds every instance of it, whether or not anyone remembers the exact words the developer chose.

The choice of a Bloom filter over an inverted index came down to cost. An inverted index gives exact term-to-location answers and pays for them in size and merge machinery, which is to say in a server.

A Bloom filter is a fixed-budget summary allowed to be wrong in exactly one direction, and the ranged-GET re-check absorbs that direction entirely. Grepr overlaps more, because it also reduces log volume and brings detail back on demand. Its data lake is an S3 bucket, either one Grepr hosts or one in the customer's own account, and its grouping is a pattern rule set that adapts to the incoming stream.

The difference worth naming is not where the bytes sit. It is what the retrieval key is made of. Here the key is computed from the message's format string, never learned from traffic, so the same message type resolves to the same key on every node and after every restart, and no amount of re-clustering moves it. A six-month-old archive answers to the identifier a query uses today.

What is in the open repo, and what is not

Everything this post walked through is in the open repo: IndexFilterWriter and the key encoding on the write side, IndexQueryWriter, QueryFilterEvaluator, and the filter decode on the read side, AWSIndexAccess beneath both.

What is not there is the thing being indexed. The engine that recognizes format strings and emits template hash plus values is what we sell, priced per node, and without it the index layer has nothing stable to key on.

A filter stored in an object body would cost one GET per filter before a query learned anything. Stored in the key, it arrives in bulk, already in memory, as a side effect of asking S3 what exists.

Related: what else attaches to a template, how far runtime cluster IDs drift, and the same hash decoding logs in plain SQL on ClickHouse.