go 74 lines · 7 steps

A rolling Bloom filter deduper in Go

A time-windowed Bloom filter that flags duplicate events while letting old ones expire as the window rotates.

Explained by highlit
Advanced bloom-filter deduplication concurrency double-hashing time-windowing
1package dedup
2 
3import (
4 "hash/fnv"
5 "sync"
6 "time"
7)
8 
9type bloom struct {
10 bits []uint64
11 k uint
12 m uint
13}
14 
15func newBloom(m, k uint) *bloom {
16 return &bloom{bits: make([]uint64, (m+63)/64), k: k, m: m}
17}
18 
19func (b *bloom) offsets(data string) []uint {
20 h := fnv.New64a()
21 h.Write([]byte(data))
22 sum := h.Sum64()
23 h1, h2 := uint(sum), uint(sum>>32)
24 res := make([]uint, b.k)
25 for i := uint(0); i < b.k; i++ {
26 res[i] = (h1 + i*h2) % b.m
27 }
28 return res
29}
30 
31func (b *bloom) test(data string) bool {
32 for _, o := range b.offsets(data) {
33 if b.bits[o/64]&(1<<(o%64)) == 0 {
34 return false
35 }
36 }
37 return true
38}
39 
40func (b *bloom) add(data string) {
41 for _, o := range b.offsets(data) {
42 b.bits[o/64] |= 1 << (o % 64)
43 }
44}
45 
46type RollingDeduper struct {
47 mu sync.Mutex
48 current *bloom
49 previous *bloom
50 m, k uint
51}
52 
53func NewRollingDeduper(m, k uint, window time.Duration) *RollingDeduper {
54 d := &RollingDeduper{current: newBloom(m, k), previous: newBloom(m, k), m: m, k: k}
55 go func() {
56 for range time.Tick(window) {
57 d.mu.Lock()
58 d.previous = d.current
59 d.current = newBloom(d.m, d.k)
60 d.mu.Unlock()
61 }
62 }()
63 return d
64}
65 
66func (d *RollingDeduper) Seen(eventID string) bool {
67 d.mu.Lock()
68 defer d.mu.Unlock()
69 if d.current.test(eventID) || d.previous.test(eventID) {
70 return true
71 }
72 d.current.add(eventID)
73 return false
74}
01 / 01
STEP 01

Walkthrough

Space play ←→ step click any line
Three takeaways
  1. 1Bloom filters trade a controllable false-positive rate for constant-space, constant-time membership checks.
  2. 2Rotating two filters on a timer gives you approximate expiry without ever deleting individual entries.
  3. 3A single mutex plus a background goroutine keeps swap-and-check operations race-free under concurrent access.

Related explainers

go 
package streaming
 
import (
	"bufio"

Streaming NDJSON logs over HTTP in Go

http-streaming channels select
Advanced 10 steps
go 
package api
 
import (
	"crypto/sha256"

ETag conditional requests in Gin

http-caching etag conditional-requests
Intermediate 6 steps
go 
func (w *Watcher) resetDebounce(d time.Duration) {
	if !w.timer.Stop() {
		select {
		case <-w.timer.C:

Debouncing a stream of events in Go

debounce timers channels
Advanced 7 steps
go 
package logging
 
import (
	"context"

Deduplicating log attributes in Go's slog

decorator-pattern structured-logging immutability
Intermediate 8 steps
rust 
use std::collections::VecDeque;
use std::sync::{Arc, Condvar, Mutex};
use std::time::{Duration, Instant};
 

Building a counting semaphore in Rust

concurrency synchronization condition-variable
Advanced 9 steps
go 
package middleware
 
import (
	"net/http"

Per-plan export limits in Gin middleware

middleware rate-limiting authorization
Intermediate 7 steps

Share this explainer

Here's the card — post it anywhere.

A rolling Bloom filter deduper in Go — share card
Made with highlit — turn any snippet into a walkthrough like this in about a minute.
Explain your code