Allowable Errors: Bloom Filters and Their Successors

Deep End Era. Engineering with Sankalp · Oct 28, 2026 · 51m

At a Singapore CDN, Priyanka Rao finds that three quarters of the files her edge servers cache are never requested again, and her colleague Marcus suggests caching only on the second request, which means remembering billions of URLs in a few hundred megabytes. In part ten of The Deep End's Data Structures series we follow Burton Bloom's 1970 idea of allowable errors from a hyphenation dictionary to every LSM tree, run a sixteen-bit filter by ear and catch it lying about a mango, and meet the successors that close the gap to the theoretical minimum: cuckoo, quotient, XOR and ribbon filters…