Note di Matteo

I bloom filter, una struttura dati per determinare in modo efficiente ma probabilistico la presenza/assenza di un elemento in una collezione, sembravano inizialmente relegati ai corsi di algoritmi dell'università ma con la scala di Internet si sono iniziati a vedere in implementazioni reali.

Esempio recente, da How we made global routing faster with Bloom filters (Vercel):

When you make a request to a Vercel deployment, our routing service first checks whether the requested path exists before attempting to serve it. [...] We do this by generating a JSON file on build that contains a tree of every path in your project's build outputs, including static assets, pages, API routes, webpack chunks, and Next.js route segments.

In alcuni casi questo file JSON era diventato un collo di bottiglia, specialmente perché il servizio di routing è single-threaded (Node.js, presumo):

These sites can create 1.5+ megabyte lookup files that take dramatically longer to parse. At the 99th percentile, parsing this JSON file takes about 100 milliseconds; at the 99.9th percentile, it takes about 250 milliseconds.

Qui entrano in gioco i Bloom filter:

A Bloom filter is a probabilistic data structure that can be used to test whether an element, or key, is a member of a set. [...] Bloom filters can return false positives, but never false negatives. For path lookups, this property is valuable. If the Bloom filter says a path does not exist, we can safely return a 404; if it says a path might exist, we fall back to checking the build outputs.

Il risultato: miglioramento della velocità di lookup fino a 200 volte. I dettagli nell'articolo.

Vercel ha annunciato di aver implementato il request collapsing per impedire valanghe di richieste contemporanee in caso di cache miss.

Raramente si conoscono i dettagli implementativi di una CDN, quindi è interessante leggere l'approccio basato su lock distribuiti:

Request collapsing works through a two-level distributed locking system.

At the node level, each CDN node maintains an in-memory lock. When multiple requests for the same uncached path arrive at that node, the lock ensures that only one proceeds. Others wait until the cache fills. This prevents a single node from firing multiple function invocations for the same path.

At the regional level, every region enforces its own lock across all nodes. After acquiring the node lock, a request tries to get the regional lock. Only one request per region can hold both locks simultaneously, meaning only one function invocation per region can regenerate a page.

This design makes collapsing scalable. Without the node-level grouping, hundreds of concurrent requests could all compete for the regional lock simultaneously. This would create a thundering herd problem where the lock coordination itself becomes a bottleneck.

TIL il firewall di Cloudflare era inizialmente fatto con nginx + PHP (!):

[...] the first version of FL was implemented based on the NGINX webserver, with product logic implemented in PHP. After 3 years, the system became too complex to manage effectively, and too slow to respond, and an almost complete rewrite of the running system was performed.

E poi fino al 2024 nginx (openresty) con scripting Lua:

From this point on, FL was implemented using NGINX, the OpenResty framework, and LuaJIT. While this was great for a long time, over the last few years it started to show its age. We had to spend increasing amounts of time fixing or working around obscure bugs in LuaJIT. The highly dynamic and unstructured nature of our Lua code, which was a blessing when first trying to implement logic quickly, became a source of errors and delay when trying to integrate large amounts of complex product logic.

Da quest'anno è in rollout la nuova versione scritta in Rust.