One Hash Bloom Filters
// Create a thread-safe atomic bloom filter with:
以下正文同步自 Hacker News 最新,版权归原站所有,已转换为易读排版。
package main
import ( "fmt" "sync"
"github.com/jcalabro/gloom" )
func main() { // Create a thread-safe atomic bloom filter with: // - Expected capacity of 1 million items // - Approximate false positive rate of 1% f := gloom.NewAtomic(1_000_000, 0.01)
var wg sync.WaitGroup defer wg.Wait()
for i := range 8 { wg.Go(func() { for j := range 100000 { str := fmt.Sprintf("key-%d-%d", i, j)
if f.TestString(str) { // always a false positive since the key isn't in the set fmt.Printf("found a false positive: %s\n", str) }
f.AddString(str) } }) } }
In addition to being a single hash, it also does some fun performance optimization techniques.
First, we split the bloom filter into many 64-byte blocks to match common CPU cache line size. Then, each block is split into k prime-sized partitions. The high bits of the hash indicate which block we should use, and the low bits find the locations within the block.
Next, since go's allocator doesn't ensure that those allocations are cache aligned, we slightly over-allocate and use unsafe to ensure alignment. See here for the implementation.
These two techniques combined guarantee that in the worst case, a bloom filter lookup only takes one cache miss. Nice!
There's another fun optimization from Daniel Lemire that allows you to select which block to check with a single MUL instruction rather than modulo, which requires an expensive division instruction.
The final interesting optimization I'll talk about is the ShardedAtomicFilter. At Bluesky, I managed a large fleet of top of the line bare metal servers. In order to eke the most performance out of those systems, it's good to avoid having multiple cores fight over the same data. ShardedAtomicFilter spreads writes over many backing filter shards, which reduces the likelihood of contention.
Bloom filters (and roaring bitmaps) make the world go around.
Hopefully this was an interesting little exploration in to how they work. If you're interested in fun low-level engineering details, consider following me on Bluesky or subscribing to this blog via atproto, RSS or similar.
Side note: I've been working on a novel observability suite that pushes the state of the art. Star it on github and keep an eye out for more discussion in the near future!
正文由 探How 从来源站点 RSS 同步,内容未经改写;遇到排版缺失或需要图片、视频时请以原文为准。