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

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

Related explainers

package middleware
 
import (
	"crypto/hmac"

Verifying signed URLs with Gin middleware

hmac middleware authentication

Intermediate 8 steps

ruby

require "thread"
 
class ConnectionPool
  class TimeoutError < StandardError; end

Building a thread-safe connection pool in Ruby

concurrency resource-pooling mutex

Advanced 8 steps

java

@Service
@RequiredArgsConstructor
public class ExchangeRateService {

Request-scoped rate caching in Spring

request-scope caching memoization

Advanced 6 steps

package server
 
import (
	"net/http"

Rate limiting HTTP handlers with a token bucket

rate-limiting token-bucket middleware

Advanced 7 steps

java

public final class CircuitBreaker {
 
    private enum State { CLOSED, OPEN, HALF_OPEN }

How a circuit breaker guards failing calls

state-machine resilience concurrency

Advanced 7 steps

ruby

class MailingListDeduplicator
  GMAIL_DOMAINS = %w[gmail.com googlemail.com].freeze
 
  def initialize(subscribers)

Deduplicating a mailing list by canonical email

deduplication normalization service object

Intermediate 8 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