A Bloom filter swap for Vercel's path lookup bottleneck
Vercel recently shipped an optimization to its global routing service that cut memory use by 15%, shaved 10% off time-to-first-byte (TTFB) from the 75th percentile upward, and dramatically improved routing speeds for sites with many static paths. The culprit was a small set of websites with hundreds of thousands of static paths, which created a bottleneck that slowed the entire routing service. The fix: replace a slow JSON parsing operation with a Bloom filter, bringing path lookup latency close to zero.
Why path lookup was slow
When a request hits a Vercel deployment, the routing service first checks whether the requested path exists before attempting to serve it. This early check prevents unnecessary storage requests and guards against enumeration attacks, where attackers guess URLs to discover hidden files.
The routing service relies on a JSON file generated at build time that contains a tree of every path in the project's build outputs — static assets, pages, API routes, webpack chunks, and Next.js route segments. Before serving a request, the service consults this file and returns a 404 if the path isn't present, ensuring storage is only hit when the document actually exists.
For most applications this works well. The majority of apps have small path lists that parse in under a millisecond, and the 90th percentile of lookups averages 4 milliseconds — no noticeable impact on performance.
But some sites generate massive path lists: e-commerce platforms with large product catalogs, documentation sites with thousands of pages, and applications with dynamic routing. These can produce lookup files over 1.5 megabytes, which take dramatically longer to parse. At the 99th percentile, parsing the JSON file takes about 100 milliseconds; at the 99.9th percentile, roughly 250 milliseconds.
Because the routing service is single-threaded, parsing this JSON blocks the event loop. For those heavy sites, a 250-millisecond path lookup means the site takes 250 milliseconds longer to serve while the operation finishes.
How a Bloom filter fits
A Bloom filter is a probabilistic data structure that tests whether an element is a member of a set. Inserting a key hashes it multiple times and sets the corresponding bit indices to 1. Querying hashes the key the same way and checks each index; if any is 0, the key is not in the filter.
Bloom filters can produce false positives but never false negatives. For path lookups that property is valuable: if the filter says a path doesn't exist, the service can safely return a 404; if it says the path might exist, the service falls back to checking the build outputs. False positives only trigger an extra storage request that finds the file doesn't exist. Bloom filters are also dramatically smaller and faster than storing the full path list.
Coordinating two services
The main challenge was keeping Bloom filter implementations in sync across two services written in different languages. The build service generates the Bloom filter from all deployment paths, while the routing service queries it for incoming requests. Both needed identical logic, so matching Bloom filter algorithms were implemented in both codebases.
The deploy process
The build service now uploads a JSON Lines (JSONL) file with two lines:
{"version":"test","bloom":{"n":10,"p":1e-7,"m":336,"k":23,"s":0}}
"0kxC4anU4awVOYSs54vsAL7gBNGK/PrLjKrAJRil64mMxmiig1S+jqyC"
The first line is a JSON object containing the Bloom filter parameters: n for the number of elements, p for the desired error rate, m for the bit array size, k for the number of hash functions, and s for the seed of the first hash function. The second line is the Bloom filter buffer encoded as Base64. Even encoded, the filter is 70–80% smaller than the previous JSON file, speeding up uploads during builds and parsing in the routing service.
Serving routes
The routing service fetches the paths file, builds a Bloom filter from it, and checks membership against the requested path. Although the filter is stored as a Base64 string in the file, the service deliberately avoids treating it as a string — string operations are expensive and were the reason the previous approach was slow. Instead, it ignores the double quotes and treats the Base64 data as the Bloom filter directly, decoding each byte only as needed during membership checks.
-- Fast lookup table for translating Base64 characters to their values
-- This is used to decode the Base64 encoded bit array in the Bloom filter
local b64 = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/'
local decode_table = ffi.new 'uint8_t[256]'
for i = 1, #b64 do
decode_table[str_byte(b64, i)] = i - 1 -- Base64 values start from 0
end
function BloomFilter:has(key)
local ptr = self.ptr -- uint8_t* pointer to start of Base64 string
for byte_offset, bit_offset in self:iterator(key) do
local sextet = decode_table[ptr[byte_offset]]
if band(sextet, lshift(1, bit_offset)) == 0 then
return false
end
end
return true
end
This makes Bloom filter creation bound by file reading speed, which is orders of magnitude faster than string creation. Very large Bloom filters can now be constructed nearly instantly.
Results: near-zero latency, faster routing for everyone
The numbers improved dramatically. The 99th percentile duration for path lookup dropped to about 0.5 milliseconds — roughly 200x faster than the JSON parsing approach. The 99.9th percentile is now 2.4 milliseconds, about 100x faster than before.
The heaviest websites, previously bottlenecked by path lookup, saw the largest gains. But the benefits rippled across the entire routing service. Those few heavy sites were disproportionately consuming memory and CPU, slowing routing service-wide. After the rollout, heap size and memory usage dropped by 15%.
The smaller heap reduced garbage collection pressure, which had been a primary bottleneck in JSON parsing. Even the old path lookup file — still parsed for projects that haven't redeployed since the change — now parses dramatically faster at every percentile.
Together, these improvements made TTFB from the 75th to 99th percentile across all requests 10% faster.
By bringing path lookup duration effectively to zero, Vercel eliminated an entire class of memory- and CPU-intensive operations in the routing service — making serving faster across the board and dramatically faster for the heaviest sites.
