A single hash maps to multiple partitions, delivering the same coverage as multiple independent hashes.
ONE-HASH BLOOM FILTERS SLASH DEPLOY TIME AT BLUESKY
*Bluesky cut deployment from 90 minutes to 15 by swapping mutexes for atomic operations. The new one‑hash bloom filter runs with a 1% false‑positive rate, saving 99% of database queries.*
Bluesky’s backend relies on bloom filters to keep its massive social graph responsive. By pre‑checking keys in memory, the service avoids costly disk reads for 99% of queries. The platform reports a roughly 1% positive hit rate, meaning almost every lookup is filtered out before hitting Scylla. This efficiency is not optional; it underpins the site’s ability to serve millions of users cheaply. However, the original double‑hash implementation suffered from a hidden cost: a mutex that serialized access and stretched deployments to 90 minutes. A swift rewrite to atomic operations cut that time to 15 minutes, unlocking faster releases. Building on that win, Jim Calabro introduced a one‑hash bloom filter that retains a 1% false‑positive rate while further simplifying the computation chain.
Why bloom filters matter to Bluesky
Bluesky stores blocks, mutes, labels and other relational data in a Scylla database. A bloom filter answers "is key X in this set?" with "definitely not" or "probably". The service runs a bloom filter in memory before each disk lookup. Recent hit‑rate data shows a roughly 1% positive rate, meaning 99% of lookups skip the database entirely. Skipping disk I/O saves substantial latency and cost. The filter lets Bluesky answer "does user X block user Y" without a single query to Scylla. This efficiency is the backbone of the platform’s ability to scale to millions of users while keeping operating expenses low.
How did mutex contention stall deployments?
Bluesky originally used the bits‑and‑blooms library, a double‑hash bloom filter written in Go. The library is not thread‑safe, so every access was wrapped in a mutex. Profiling showed the mutex as the bottleneck. A full deploy took 90 minutes because each process launch had to lock and unlock millions of times. Jasmine, a colleague, forked the code into atomic‑bloom, replacing mutexes with atomic CPU instructions. The change eliminated contention, dropping deploy time to about 15 minutes. Faster rollouts mean quicker feature delivery and higher confidence in production changes.
Can a single hash replace multiple hashes in bloom filters?
Research by Lu et al. shows a bloom filter can operate with a single hash if the bit array is split into k partitions of pairwise‑coprime sizes. The single hash is reduced modulo each partition size to produce k bit positions. Those positions serve the same role as k independent hashes. Jim Calabro built jcalabro/gloom, a Go implementation of this one‑hash bloom filter (OHBF). The code creates a thread‑safe atomic filter with an expected capacity of 1 000 000 items and an approximate false‑positive rate of 1%. The filter has run live in Bluesky’s backend for nine months, handling block, mute and label checks without degradation.
What performance gains have been observed after nine months?
During the past nine months, the OHBF has handled high‑throughput queries in both Bluesky and Jetstream, the platform’s sync service. The positive hit rate remains around 1%, preserving the 99% skip‑rate for database reads. The atomic implementation continues to avoid mutex contention, keeping deploy windows at roughly 15 minutes. No new bottlenecks have surfaced, indicating the single‑hash design scales with the workload. The stability of the filter validates the theoretical claim that a single hash can match the false‑positive rate of traditional multi‑hash designs when partition sizes are chosen correctly.
Frequently asked questions
What is the false positive rate of Bluesky's one‑hash bloom filter?
The filter is configured for an approximate false positive rate of 1%.
How much did deploy time improve after replacing mutexes?
Deploy time dropped from 90 minutes to about 15 minutes.
How long has the one‑hash bloom filter been live in Bluesky?
It has been running in the Bluesky backend for nine months.
The one‑hash bloom filter proves that theoretical advances can translate into real‑world gains. Bluesky now runs a leaner, faster, and cheaper backend, and the design is already powering Jetstream’s sync layer. As data volumes grow, the ability to shave minutes off deployments and keep database traffic near zero will become a competitive edge. The next frontier will be testing the limits of single‑hash designs under even heavier loads.
Sources: Hacker News – One Hash Bloom Filters (https://calabro.io/ohbf)