Bloom Filters in Postgres
One typical use case for sign-up forms is validating whether a username is available as you type. Every keystroke sends a request to the backend, which makes a request to the database. That’s normally just one index lookup and doesn’t usually come up in scaling discussions.
Once you start sharding your users table on user ID, those usernames can live on any shard, making each keystroke check a scatter and gather to all nodes. Typing a twelve-character username across sixteen Postgres shards can result in nearly two hundred queries.
Debouncing the username field helps reduce the number of queries, but each request still hits all the shards and waits for the slowest one to respond. That gets worse with every shard you add.
A Bloom filter can tell you a name is free without querying any shards, and you can build one in Postgres out of a table and a function.
Bloom filters
A Bloom filter, described by Burton Bloom in 1970, is a bit array that probabilistically tests whether an element is in a set. It starts out as all 0s. To insert an element, hash it k ways and set the bit at each of those locations to 1. To query an element, hash it the same way and check each of those bits. If any of those bits is 0, the element has definitely not been inserted. If they’re all 1, the element probably has been inserted.
All of those k hashes could come from the same hash function. Here’s how. Consider a 16-bit filter with k = 3. We’ll insert the username ada. We want three hashes of ada, but hashing ada will always give the same hash, so prepend a counter: 0:ada, 1:ada and 2:ada.
Each hash evaluates to a very large number. With md5, it’s 128 bits long, up to 39 decimal digits. But there are only 16 positions in the array. Taking it modulo 16 gives a value between 0 and 15, a position in the array. A good hash scatters its outputs uniformly, so the bits get used evenly too. Here are ada’s three:
input md5 in hex % 16
0:ada 2d0adfba24320bd14abdb38aa02ff6fe 14
1:ada e4d0f800ff16f1b94c8ce1de8bb8fefd 13
2:ada cf0c119c0624d173d6d86cdbfda09965 5
Pieced together in Python, the entire filter looks like this:
from hashlib import md5
SIZE = 16
K = 3
bits = [0] * SIZE
def positions(item):
for i in range(K):
h = md5(f"{i}:{item}".encode()).hexdigest()
yield int(h, 16) % SIZE
def add(item):
for p in positions(item):
bits[p] = 1
def check(item):
return all(bits[p] for p in positions(item))
Here’s what happens after adding two names and checking three:
add ada bits 5, 13, 14
add grace bits 2, 3, 8
position 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
bits 0 0 1 1 0 1 0 0 1 0 0 0 0 1 1 0
check ada bits 5, 13, 14 all set, and ada was added
check alan bits 2, 8, 10 bit 10 is 0, definitely not added
check bjarne bits 3, 5, 8 all set, but bjarne was never added
alan is definitely not in the filter. bjarne returns the same result as ada, even though we never added it. This is because ada and grace set all three of bjarne’s bits between them. False positives like this are indistinguishable from real hits by the filter.
In a Bloom filter, a “no” is always correct, but a “yes” is only probably correct. How often a “yes” is wrong depends on the size of the bit array ( bits) divided by the number of items in the set ( items). The optimal k value is given by:
About half the bits will be set at that k. For a false-positive rate of 1%, the smallest filter you can make uses ~9.6 bits per item, with a k of ~7.
As far as usernames go, that solid “no” is perfect. You know it’s available, and didn’t have to query any shards.
Storing it in Postgres
Since the filter is a single bit array covering every username, it can live entirely in one Postgres table. With 100 million users, a 1% false-positive rate needs at least 960 million bits. To make every position calculable directly from the hash bits, round up to the nearest power of two (2^30 bits, or 128 MiB). That works out to 10.7 bits per name, so the best k is:
k must be an integer, and since 7 and 8 have nearly identical false-positive rates, we choose 7 so that there is one fewer bit to set and check per name.
The entire array shouldn’t go in one row, though. PostgreSQL doesn’t overwrite existing values, so toggling just one bit would write an entire new copy of that value. This would cause 128 MiB to be written to disk on every signup, and every write would have to serialize on the same row lock.
Dividing it into chunks solves both problems. Here it’s split into 131,072 rows of 8,192 bits each:
create table username_filter (
chunk int primary key,
bits bit(8192) not null
);
insert into username_filter
select n, 0::bit(8192) from generate_series(0, 131071) as n;
That will take up about 150 MiB on disk once Postgres stores its row headers and the primary key.
In an ordinary Bloom filter, a name’s seven bits could end up anywhere in the array. Here, that would mean seven different rows. Adding a name would change seven rows, and checking it would have to read seven. To avoid that, each name first picks a single chunk, and all seven of its bits get stored inside that chunk. This is called a blocked Bloom filter. Adding a name to the filter now only updates one 1 KiB row, and checking it only reads one.
Retaining each name in a single chunk comes at a slight accuracy penalty because names don’t spread perfectly evenly across chunks. Some chunks become more full than others and the fuller chunks produce more false positives. Using 8,192 bits per chunk only incurs a tiny penalty of 0.585% false positives versus 0.578% for a standard Bloom filter of the same size.
This function converts a name into two values: the chunk that holds the name, and a mask. The mask is an 8,192-bit value (one bit for each position in a row), with just the seven bits belonging to that name turned on:
create function username_bits(name text, out chunk int, out mask bit(8192))
language plpgsql as $$
declare
h bit(128) := ('x' || md5(lower(name)))::bit(128);
begin
chunk := substring(h from 1 for 17)::int;
mask := 0::bit(8192);
for i in 0..6 loop
mask := set_bit(mask, substring(h from 18 + i * 13 for 13)::int, 1);
end loop;
end
$$;
Invoking it with ada returns chunk 71962 and a mask with seven bits set. We can’t print out the mask directly, as it’s too long, but we can step through all 8,192 bits with generate_series, filtering with get_bit to only return those that are set:
select chunk,
array(select i from generate_series(0, 8191) i where get_bit(mask, i) = 1) as set_bits
from username_bits('ada');
chunk | set_bits
-------+-------------------------------------
71962 | {619,1835,3259,3422,5396,5977,6900}
It only hashes the name once. md5 returns 32 hex digits, and prepending an x tells Postgres to interpret them as a string of 128 bits. Lowercasing the name first means that Ada and ada use the same bits. Here’s where ada’s chunk and bits come from:
md5('ada') 8c8d357b5e872bbacd45197626bd5759
bits 1-17 10001100100011010 chunk 71962
bits 18-30 0110101011110 bit 3422
bits 31-43 1101011110100 bit 6900
bits 44-56 0011100101011 bit 1835
bits 57-69 1011101011001 bit 5977
bits 70-82 1010100010100 bit 5396
bits 83-95 0110010111011 bit 3259
bits 96-108 0001001101011 bit 619
Bits 1 through 17 select the chunk. They form a number from 0 to 131,071 inclusive, which can address every chunk. Each of the following seven 13-bit sections is a number from 0 to 8,191 inclusive, and selects a single bit within that chunk. So that’s eight positions total selected from one hash, using 108 of the 128 bits.
Adding a name ORs its mask into its chunk:
update username_filter f
set bits = f.bits | b.mask
from username_bits('ada') b
where f.chunk = b.chunk;
OR returns a 1 wherever either side has a 1. So ada’s seven bits are turned on, and the bits other names set are unchanged. Here it is with 8 bits instead of 8,192:
row 0 1 0 0 1 0 0 0
mask 0 0 1 0 1 0 0 1
row | mask 0 1 1 0 1 0 0 1
Testing a name ANDs its chunk with its mask and compares the result to the mask:
select bits & mask = mask as maybe_taken
from username_filter
join username_bits('ada') using (chunk);
AND returns only the bits which are set on both sides. So it throws away anything outside of the mask. If the result matches the mask, then all seven bits were set and it could already be taken. If even one bit is missing, it’s free for sure:
mask 0 0 1 0 1 0 0 1
row 0 1 1 0 1 0 0 1
row & mask 0 0 1 0 1 0 0 1 equals the mask, might be taken
row 0 1 0 0 1 0 0 1
row & mask 0 0 0 0 1 0 0 1 bit 2 is missing, definitely free
In both queries, username_bits('ada') is pretending to be a table with one row that has the chunk and the mask, and joining on chunk hits that one row via the primary key. If the table is resident in memory, this check takes less than a millisecond.
Checking while typing
Now a check gets directed to the filter first, and only hits the shards if the filter can’t eliminate the name:
flowchart LR
K["<strong>keystroke</strong><br/><span class='mermaid-detail'>is ada free?</span>"]
F["<strong>username_filter</strong><br/><span class='mermaid-detail'>one row</span>"]
A["<strong style='color:#16181a'>free</strong><br/><span class='mermaid-detail' style='color:#16181a'>no shards asked</span>"]
S["<strong>16 shards</strong><br/><span class='mermaid-detail'>scatter and gather</span>"]
K --> F
F -->|"definitely not"| A
F -.->|"maybe"| S
classDef free fill:#5eff6c,stroke:#5eff6c,color:#16181a
classDef fanout stroke:#5ea1ff,stroke-width:2px
class A free
class S fanout
A “definitely not” is authoritative, and none of the shards learn of it. A “maybe” degrades to the scatter and gather for the true answer. That still occurs for names that truly are taken, plus about 1 in 170 free ones (the false-positive rate with 100 million users), but almost every free name now requires one row read instead of sixteen queries.
If you’re okay with occasionally seeing a free name displayed as taken, you can eliminate the fallback and treat all “maybes” as taken. That way the shards aren’t even queried until the form is submitted.
Adding at sign-up
But if a name is taken it has to be in the filter, or its “no” result can’t be believed. Therefore when creating an account, you need to add the username to the filter prior to inserting the user.
If the insert fails later, you have bits set for someone who doesn’t exist. The cost is a marginally higher false positive rate, and all results are still correct because a “maybe” still has to check against all the shards.
The reverse order is worse. If you insert the user before updating the filter, a crash between them would leave a taken name that the filter claims is free. You can’t use a transaction to fix that, because the filter and the shard the user is inserted into are on different nodes, and begin and commit only cover a single database. Writing to the filter first keeps it correct without one.
Submitting the form still has one scatter and gather before the account is created because that answer needs to be exact. The filter also does not affect how the system prevents two people from simultaneously grabbing the same name.
Tradeoffs
This filter incurs two costs.
The first is deleted accounts. They remain in the filter because their bits may also be part of other names, and clearing them might turn an in-use name into a “definitely not”. Deleted names keep coming back as “maybe” and the fallback finds them free, so the answer is still correct, but it wastes a scatter and gather each time.
That’s only a cost if deleting an account frees up its name, though. Many services soft-delete accounts or reserve the name so nobody else can use it, so the name is still taken and the “maybe” is accurate.
The second is that the filter’s size is fixed when you create the table, so its false-positive rate grows as new users sign up. With that same 128 MiB, 1 in 170 free names gets flagged as “maybe” at 100 million users. At 150 million users, it’s 1 in 27. At 200 million users, it’s 1 in 9.
That’s why the rate is worth watching, and it’s easy to read off the table. If a free name lands in one chunk, the probability that each of its seven bits is already set is equal to that chunk’s proportion of set bits. So the probability that all seven are set is that proportion to the seventh power. Averaging that over chunks yields the false-positive rate:
select avg(power(bit_count(bits) / 8192.0, 7)) as false_positive_rate
from username_filter;
I inserted 100 million generated names to test. The query gave 0.0059, and sampling a million names that I never inserted revealed 5,924 false positives, near enough to its prediction of 5,900.
If the rate gets too high, you can rebuild the filter using more chunks:
- Export all usernames from all shards and construct a new filter table out of them, which
bit_orcan do for every chunk in onegroup by. - Include names that signed up during the export.
- Swap in the new table and its matching
username_bitsin one transaction, since both live in the same database.
A rebuild also purges deleted names and captures any accounts made without going through sign-up.
Only one answer from a Bloom filter is ever known for certain, and in a sign-up form, that’s the answer people are hoping for. The shards still have the final say on who gets a name, but they’re no longer asked about every name someone tries along the way.