Serverless search: a Lambda fan-out over S3

When a client asks for search in their SaaS application I want to know about two things before making a call on the technology: the data being searched, and the pattern of search by users - why users need search and what they are looking for. Is it a handful of common queries arriving at a steady rate, or an unpredictable stream of specific, unusual terms? The inverted index I built in part two suits the first shape well, since you pay once to structure the data and every query after that is a cheap key lookup. The second shape is a different proposition, because if most searches are for terms nobody has searched before, an index is a standing cost built largely for queries that never arrive.

This article covers the strategy at the opposite extreme, the second of the five I sketched in the series introduction: no index at all. The text sits in S3 as plain files, and when a search arrives a fleet of Lambda functions reads it and looks, each scanning its own slice in parallel. Between searches there is nothing provisioned, nothing running and nothing billed. It sounds too crude to work, so I built it and measured it - the functions, the test data generators and the benchmark harness are all in a companion repository on GitHub.

The record-boundary problem

The mechanics are simple to describe. A parent Lambda receives the search terms, asks S3 how big the file is with a HEAD request, splits it into byte ranges, and invokes a child Lambda for each range. Each child fetches only its own slice using a ranged GET, parses the records inside it, scores them against the search terms, and hands its matches back to the parent, which merges and ranks the lot.

The awkward part is deciding where one range ends and the next begins. Split a file at an arbitrary byte offset and you will slice a record in half mid-word, leaving one child holding "Edinburgh Ca" and its neighbour "stle Morning", and neither will match a search for castle. S3 Select used to solve this for you with its ScanRange parameter, under a tidy rule: a record that started inside your range was processed even where it ran past the end, so every record belonged to exactly one range. AWS closed S3 Select to new customers in July 2024, which means anyone building this today gets to solve the boundary problem themselves.

My implementation aligns the ranges before any child is invoked: the parent makes a small ranged GET around each proposed split point and nudges the boundary along to the next record delimiter, so every child receives whole records. For one-record-per-line data the delimiter is simply a newline. For long-form documents spanning many lines - I built a test corpus from twelve public-domain novels from Project Gutenberg - a newline can't mark the boundary, so the tooling separates documents with the ASCII record-separator character (0x1E) and the splitter aligns to that instead, scanning forward when a single document turns out to be bigger than a whole chunk. This probing is sequential, one small request per boundary before the fan-out begins, and that cost comes back into the story later.

What the parallelism buys

Does tearing the scan into pieces actually pay? I generated a catalogue of 50,000 records - 7.5 MB of pipe-delimited rows, the sort of flattened file you would get by dumping a few joined SQL tables out of a database - deployed the two functions to eu-west-2, and timed warm searches for the word "castle" while varying the number of ranges.

ranges    median search time
1         12.1 s
8         3.3 s
15        2.9 s
30        3.1 s
59        3.9 s
118       5.5 s

One child scanning the whole file alone took twelve seconds, which is no use whatsoever behind a search box. Fifteen children brought the same search down to 2.9 seconds, a little over four times faster. Beyond that, more parallelism made things worse: every extra child adds an invocation round trip and its own S3 request, the slices become too small to justify their setup cost, and by 118 ranges the search had climbed back up to 5.5 seconds. The curve is a U, and the tuning job is finding the bottom of it for your corpus and chunk size.

The money side is what makes the architecture interesting for the right client. A search of this file consumes a burst of Lambda-seconds costing a fraction of a penny, and between searches the entire system is a bucket of files - no cluster idling overnight, no minimum monthly spend, nothing to patch. For a search feature that gets used in bursts, or hardly at all some weeks, that shape of bill is hard to argue with.

Where the bottleneck actually sits

Scaling the corpus up to 500,000 records (76 MB) told a more interesting story. The best configuration there was 150 larger ranges, at eight seconds; 299 smaller ranges took twelve. The obvious suspect for that slowdown is the concurrency cap, since the parent invokes at most 64 children at a time and 299 children therefore run in waves - but raising the cap to 128 workers and then 256 made no difference at all: 12.0 seconds, 11.8, 11.9.

It was interesting to see that the bottleneck at this scale isn't the parallelism, but everything around it: the fixed overhead of making hundreds of Lambda invocations, and the parent itself, a single function left collecting, merging and sorting 299 result sets while the children sit finished. Brute-force parallelism doesn't remove the bottleneck so much as move it, and it lands wherever the results converge - the concurrency setting, the obvious knob, turned out to be connected to nothing.

Making the brute force less brutish

Scanning everything on every search is wasteful in an obvious way: a search for "vampire" reads every record in the corpus to find matches that live in one small corner of it. A Bloom filter gives you a way of knowing which corners to bother with. It's a fingerprint a few kilobytes in size, built for each chunk of the corpus, that can answer "is this word in this chunk?" with either a certain no or a maybe. Building one is cheap: every distinct word in the chunk sets a handful of bits in a bit array, about ten bits per word. At query time the search term is hashed the same way, and if any of its bits is unset then the word is definitely not in that chunk, and the chunk can be skipped without reading it.

The full index for my test corpora came to between 1.4% and 3.5% of the size of the data itself. The parent loads it, tests each chunk's filter against the search terms, and fans out only to the survivors. On the novels corpus the effect was dramatic. "Vampire" appears only in Dracula, the filters ruled out 39 of 43 chunks, and the live search dropped from 3.9 seconds to 1.6 while returning identical results. "Darcy" pruned 93% of the chunks; "whale" 79%.

The same trick on the 50,000-row catalogue pruned precisely nothing. That dataset has a small, shared vocabulary, so every place name and keyword appears somewhere in every chunk, every filter answers maybe, and every chunk gets scanned anyway. Bloom filters pay off when the vocabulary is localised - when the words being searched for cluster in particular parts of the corpus - and do nothing when common terms saturate it. There was one result I didn't predict, though: even with nothing pruned, searches through the filter index were around half a second faster, because the index already records where every chunk boundary sits, and the parent skips the sequential boundary-probing described earlier.

The filters do need keeping fresh, because one built last night knows nothing about a record added this afternoon, and would cheerfully skip a chunk that now matches. My answer in the proof of concept is a schedule: rebuild the index periodically - about two seconds of work for the 76 MB corpus - and have searches scan anything newer than the index directly, so fresh data is findable the moment it lands. I suspect doing this properly on a big, busy dataset is a discipline of its own, and from a bit of reading it looks close to what database engines like Cassandra do under the bonnet, but for this experiment the schedule and the tail scan cover it.

Choosing the right tool for the job

Which brings the two questions from the top back around. If your users' searches are a steady stream of the same common terms, this strategy is the wrong shape twice over: common terms live in most chunks, so the filters prune nothing, and you are paying to repeat the same scan for the same answer all day. The right tools for that pattern are the inverted index from part two, and a cache in front of repeated queries. If the searches are rare, specific and unpredictable - a compliance officer hunting one supplier name through years of documents, a support engineer looking for an error string nobody has seen before - then an index is maintenance spent on queries that mostly never come, and a filtered fan-out that reads a twentieth of the corpus and costs nothing between searches fits genuinely well. Most real products sit somewhere between the two patterns, which is exactly why I'd want the data and the usage understood before any technology gets chosen.

If I were taking this beyond a proof of concept, the other lever worth pulling is the runtime. The children's work - tokenising, matching, scoring - is pure CPU, and Python is a slow way to do CPU work; the same scan in Rust or Go would run many times faster and cold-start quicker too, though neither would touch the S3 requests or the invocation overhead, which are fixed. Python was the right choice here because the architecture is the thing being demonstrated, and it's the language most readers can skim.

Everything in this post, index or no index, matches the exact words the user typed. Quite often that isn't what they meant: they wanted the documents about the thing they typed, whatever words those documents happen to use. That's where the series goes next, with S3 Vectors and searching by meaning. And if you're weighing up how search should work in your own product, the two questions at the top of this article are where I would start - I'm always happy to talk them through.