Where should the information for skipping files live?
- the problem
- A search should open only the log files that can hold the answer. Knowing which ones means storing each file's time range and word summary somewhere, and reading it costs time on every search.
- what I considered
- Keep the summary inside each file and read just that part from storage. A separate database like Postgres. A SQLite file inside the server.
- what I picked
- A SQLite file with one row per log file: time range, size, and its bloom filter. A search reads it first and opens only what it can't rule out.
- what I'd change
- On 196 files, a one-hour search for a common word opened 2 or 3 files in 55 ms. Across all time it opened 171 in 2.1 s. The cost: one file the server can't lose.
Where I was
I had the log file format working. Strata stores logs in files called segments. A segment holds a few thousand lines sorted by time, a word index, and a bloom filter. A bloom filter is a small table of bits that can say a word is definitely not in the segment, or that it might be. Segments get uploaded to S3.
I knew a search had to skip most segments to be fast. I had not decided where the data for skipping would be kept.
What made it hard
Skipping only helps if checking a segment is much cheaper than reading it.
The first thing to skip on is time. If a segment covers 09:00 to 09:05 and the search asks for 14:00 to 15:00, it can be dropped. That range was already in the segment's header, so the obvious move was to read the header. On S3 every read is its own network request. With 196 segments that is 196 requests before the real work starts, and the number grows with every segment added.
The bloom filter is worse. It is bigger than the header, and every search that contains a word needs it.
What I weighed
Read the summary out of each file
Keep everything inside the segment. Ask S3 for just the header and the bloom section instead of the whole file. There is no extra system to run. The cost is one request per segment on every search. I never built this, so I have no numbers for it.
A separate database such as Postgres
A proper catalogue, with replication available later. The cost is another service to run, configure and back up, in a project that is supposed to be one binary and a bucket. I would have been taking on that cost for replication I did not need yet.
A SQLite file inside the server
I called it the manifest. It has one table, one row per segment: id, storage key, oldest and newest timestamp, line count, size, status, and the bloom filter bytes. SQLite gives real transactions without a second service. The cost is that it is one file on one machine. If it is lost, the server can't tell which files in the bucket are real.
Anything I tried and dropped
Nothing was dropped. I built the manifest with time ranges only and added the bloom column in the next phase, as a schema change, when I wrote the search code. A bloom filter you have to download before you can check it saves nothing.
What tipped it
A search that has to fetch something per segment before it can skip that segment has not skipped anything. The answer to "can I skip this one" had to be available without touching S3.
The manifest does that. One query on a local file returns every segment, whether its time range overlaps the search, and the bloom filter for the ones that do. Postgres could have done the same. I didn't want to run it.
How it turned out
These numbers are from the BGL log dataset: 4,747,963 lines, 709 MiB, stored as 196 segments with compaction turned off. Each query ran 100 times on a laptop, with the server and a local S3-compatible store (RustFS) on the same machine.
| Query | Segments opened | Data read | Median time |
|---|---|---|---|
| a rare word, all time | 3 of 196 | 15 MiB | 89 ms |
| "error", one-hour window | 2.5 of 196, on average | 13 MiB | 55 ms |
| "error", all time | 171 of 196 | 886 MiB | 2.1 s |
| a word that is not in the data | 0 of 196 | 0 | 27 ms |
The one-hour search found 40 matching lines. The all-time search stopped at its 100-line limit. So they are not doing identical work. A real S3 bucket would be slower per segment than my local one.
Skipping only helps when most segments can be ruled out. On the logs my generator produces, a rare word was in 11 of 13 segments, and a five-minute window still kept 13 of 29. Little can be skipped there.
The decision also caused a bug I had not planned for. The manifest decides which files are real, so a manifest that is lost or replaced makes every file in the bucket look like leftover junk, and the cleanup job would delete them. I added a check at startup. The manifest has a random id, the same id is written into the bucket, and the server refuses to start if they don't match.
Code: internal/manifest/manifest.go, and internal/query/query.go for how a search uses it.
What I still don't know
- How it behaves with many thousands of segments. Every search loads and decodes the bloom filter of every segment in its time range. I only measured 196. Bloom filters never change once written, so a cache would work. I have not built one or measured whether it is needed.
- Whether reading just the header and bloom from S3 would have been fast enough. I never tested it. It may be fine at small scale.
- How big the manifest gets. A bloom filter costs about 10 bits per distinct word per segment by design, but I have not measured the file on the full dataset.
- Recovery. If the manifest is lost, the server stops, but it can't rebuild it. Each segment has its time range and count in its header, so a rebuild tool should be possible. It does not exist.
- SQLite's write-ahead mode only works when every process is on the same machine. A second server would need a different catalogue. I would revisit this decision then.
What I read
- SQLite: Write-Ahead Logging: readers and writers don't block each other, which is why the manifest uses it. It also only works on one host, which is part of why the server is single-node.
- LogHub: where the BGL logs behind the numbers above come from.