Deduplicating 10 Billion Orders: Bloom Filter + Redis Architecture Deep Dive
This article details a production-grade solution for deduplicating 10 billion order numbers using a sharded Redis Bloom filter with database fallback, covering parameter calculations, cold-start loading, scaling strategies, consistency guarantees, and interview-focused comparisons with offline batch and real-time stream approaches.
Core Constraints
Data volume: 10 billion order numbers (64-bit each ≈ 80 GB raw). Core requirement: fast existence check (<10 ms latency, 100k+ QPS). Business constraint: order numbers never change, high eventual consistency, zero false negatives allowed.
Solution Evolution
HashSet : Java native hash table. Memory >800 GB (object overhead). O(1) query. Applicable to million-level. Fatal flaw: memory explosion.
MySQL Unique Index : DB unique constraint. Disk storage. Query ~100 ms+. Applicable to ten-million-level. Fatal flaw: disk I/O bottleneck, cannot handle high concurrency.
Redis Set : In-memory hash set. Memory ≈160 GB (Redis encoding). O(1) query. Applicable to hundred-million-level. Fatal flaw: high cost (~$2k/month for 160 GB cloud Redis).
Bloom Filter : Probabilistic data structure. Memory ≈11.5 GB (0.01% false positive). O(k) query (k=hash functions). Applicable to ten-billion-level+. Fatal flaw: tiny false positive rate.
Optimal Architecture: Bloom Filter + Database Fallback
Key Parameter Calculations
For 10B items, false positive rate p=0.01%:
Bit array size: m ≈ -n * ln(p) / (ln2)² ≈ 10B * 9.21 ≈ 92.1B bits ≈ 11.5 GB
Optimal hash functions: k ≈ m/n * ln2 ≈ 7
Core Code Implementations
1. RedisBloom Distributed Bloom Filter (Production-Grade)
Technical highlight: Based on official Redis module, supports clustering, persistence, dynamic scaling, avoids Guava local Bloom filter distributed consistency issues.
import org.redisson.api.RBloomFilter;
import org.redisson.api.RedissonClient;
import org.springframework.stereotype.Component;
import javax.annotation.PostConstruct;
import javax.annotation.Resource;
@Component
public class RedisBloomOrderDeduplicator {
private static final String BLOOM_FILTER_KEY = "order:id:bloom";
private static final long EXPECTED_INSERTIONS = 10_000_000_000L;
private static final double FPP = 0.0001; // 0.01% false positive
@Resource
private RedissonClient redissonClient;
@Resource
private OrderRepository orderRepository;
private RBloomFilter<Long> bloomFilter;
@PostConstruct
public void init() {
// Get or create Bloom filter, only effective on first creation
bloomFilter = redissonClient.getBloomFilter(BLOOM_FILTER_KEY);
bloomFilter.tryInit(EXPECTED_INSERTIONS, FPP);
}
/**
* Core deduplication method
* @return true: duplicate, false: not duplicate
*/
public boolean isDuplicate(Long orderId) {
// 1. Check Bloom filter first (pure in-memory, microseconds)
if (!bloomFilter.contains(orderId)) {
// 2. Bloom says not exists → definitely not exists, write directly
bloomFilter.add(orderId);
return false;
}
// 3. Bloom says exists → verify with database (only 0.01% requests reach here)
return orderRepository.existsById(orderId);
}
/**
* Batch add historical order IDs (cold start)
* Technical highlight: Uses Redis pipeline for 100x+ performance boost
*/
public void batchAdd(List<Long> orderIds) {
bloomFilter.add(orderIds); // Redisson internally wraps pipeline batch ops
}
}2. Sharded Bloom Filter Optimization (Solves Single-Instance Large Memory)
Technical highlight: Shard by order ID prefix, each shard an independent Bloom filter, splits 11.5 GB into 10 × 1.15 GB instances, solves Redis big key and single-instance memory bottleneck.
@Component
public class ShardedBloomOrderDeduplicator {
private static final int SHARD_COUNT = 10; // 10 shards
private final List<RBloomFilter<Long>> shards = new ArrayList<>(SHARD_COUNT);
@PostConstruct
public void init() {
for (int i = 0; i < SHARD_COUNT; i++) {
RBloomFilter<Long> shard = redissonClient.getBloomFilter("order:id:bloom:shard:" + i);
shard.tryInit(EXPECTED_INSERTIONS / SHARD_COUNT, FPP);
shards.add(shard);
}
}
private RBloomFilter<Long> getShard(Long orderId) {
// Shard by last digit of order ID for uniform distribution
int shardIndex = (int) (orderId % SHARD_COUNT);
return shards.get(shardIndex);
}
public boolean isDuplicate(Long orderId) {
RBloomFilter<Long> shard = getShard(orderId);
if (!shard.contains(orderId)) {
shard.add(orderId);
return false;
}
return orderRepository.existsById(orderId);
}
}3. Historical Data Cold-Start Batch Loading Optimization
Technical highlight: Multi-threaded paginated query + Redis pipeline batch write, reduces 10B data load time from days to hours.
@Component
public class BloomFilterInitializer {
private static final int PAGE_SIZE = 10000; // 10k per query
private static final int THREAD_COUNT = 20; // 20 parallel threads
@Resource
private ShardedBloomOrderDeduplicator deduplicator;
@Resource
private OrderRepository orderRepository;
@Resource
private ThreadPoolTaskExecutor taskExecutor;
public void initAllHistoryOrders() {
// 1. Get min/max order ID to avoid full table scan
Long minId = orderRepository.findMinId();
Long maxId = orderRepository.findMaxId();
long totalPages = (maxId - minId) / PAGE_SIZE + 1;
// 2. Multi-threaded parallel loading
CountDownLatch latch = new CountDownLatch((int) totalPages);
for (long page = 0; page < totalPages; page++) {
long startId = minId + page * PAGE_SIZE;
long endId = Math.min(startId + PAGE_SIZE - 1, maxId);
taskExecutor.execute(() -> {
try {
List<Long> orderIds = orderRepository.findIdsBetween(startId, endId);
if (!orderIds.isEmpty()) {
deduplicator.batchAdd(orderIds);
}
} finally {
latch.countDown();
}
});
}
// 3. Wait for all threads
latch.await();
log.info("Bloom filter historical data load complete, loaded {} orders", maxId - minId + 1);
}
}Core Technical Challenges & Solutions
Slow historical cold start : System startup takes days, cannot launch quickly. Solution: 1. ID-range paginated query 2. Multi-threaded parallel load 3. Redis pipeline batch write 4. Pre-generate Bloom filter files. Highlight: Load speed 100x+, 10B data loaded in 4 hours.
Bloom filter scaling difficulty : Capacity full → false positive rate spikes, cannot write. Solution: 1. Dual-write cutover: create larger filter, write to both 2. Shard scaling: add shards, reassign hash slots 3. Rolling scaling: migrate shard-by-shard, zero downtime. Highlight: Zero-downtime, business unaware, no perf degradation during scaling.
Distributed consistency : Multi-instance local Bloom filters inconsistent → missed duplicates. Solution: 1. Unified RedisBloom distributed filter 2. Eventual consistency model, DB unique index fallback 3. Periodic full validation of Bloom vs DB. Highlight: Guarantees zero missed duplicates, eventual consistency.
False positive control : High false positive → massive DB penetration. Solution: 1. Precise Bloom parameter calculation 2. Monitor actual false positive rate, scale when threshold exceeded 3. Tiered Bloom: hot data low false positive, cold data higher. Highlight: Actual false positive stable <0.01%, DB pressure reduced 99.99%.
Redis big key problem : 11.5 GB big key causes cluster migration/backup failures. Solution: 1. Shard by order ID prefix into multiple small Blooms 2. Each shard <2 GB 3. Hot/cold separation: hot in memory, cold on disk. Highlight: Solves all Redis big key issues, cluster stability greatly improved.
High-concurrency performance : High-concurrent writes make Bloom filter bottleneck. Solution: 1. Local cache hot Bloom shards 2. Read/write separation: read local, write Redis 3. Batch async writes to Redis. Highlight: Supports 1M+ QPS, latency stable <1 ms.
Production Advanced Optimizations
Hot/Cold Separation : Last 3 months hot data in local Guava Bloom filter, cold data in Redis Bloom filter.
Monitoring & Alerting : Monitor Bloom fill rate, false positive rate, query latency, Redis memory usage.
Disaster Recovery : Periodic backup of Redis Bloom data for fast recovery.
Stress Testing : Full-chain stress test before launch, validate performance/stability at 10B scale.
Interview Q&A Key Points
Q: What if Bloom filter false positive?
A: No business correctness impact because DB unique index is fallback. False positive only causes tiny extra DB queries; 0.01% rate has negligible performance impact.
Q: What when 10B orders fill Bloom filter?
A: Plan scaling ahead. At 70% fill rate, trigger dual-write cutover: create 2x capacity new filter, write to both, switch read traffic after new filter sync completes.
Q: Why not Roaring Bitmap?
A: Roaring Bitmap suits contiguous integers; order IDs are typically Snowflake-generated distributed IDs (sparse). 10B sparse IDs in Roaring Bitmap would consume 50+ GB vs Bloom's 11.5 GB.
Real Interview Simulation
Scenario 1: Offline Batch Exact Deduplication
Core idea: "Divide and conquer". Single machine can't hold 80 GB → hash same order IDs to same machine/file, then local deduplication.
Hash Sharding : hash(id) % N into N small files (e.g., N=1000). Same ID always lands in same file; each file ~80 MB, fits in memory.
Single-File Exact Deduplication : Load each file into memory HashSet or sort-deduplicate.
Aggregate Output : Output deduplicated results per file; no cross-file duplicates due to sharding isolation.
Scenario 2: Real-Time Stream Exact Deduplication
Architecture: External storage + fast judgment . Use Bloom filter + distributed KV store combo: "Bloom as high-speed gate, KV as exact judge".
Bloom filter in memory: quickly judges "definitely never seen". If Bloom says "no", definitely absent → allow, then write to Bloom and downstream.
If Bloom says "maybe exists" (false positive possible), query HBase / RocksDB persistent KV. If exists → discard; if not → insert, completing exact deduplication.
Bloom intercepts 99.9% queries; only few penetrate to disk.
Real-time order ID → [Bloom Filter] → (maybe exists) → [HBase/RocksDB Exact Check]
│ definitely not │
↓ ↓
Allow + write to Bloom Exists → Discard
Not exist → Insert + AllowMemory/false positive trade-off: at 0.01% false positive, formula -n*ln(p)/(ln2)^2 yields ~18 GB for 10B items. Acceptable on high-end machine or distributed via Redis cluster Bitmap. False positive penetration negligible for HBase pressure.
If no external KV or ultra-low latency needed: consider RoaringBitmap if IDs have local continuity (e.g., timestamp portion in Snowflake). For fully random IDs, RoaringBitmap compression limited; fallback to "Bloom+KV" or sharded state storage. Flink KeyedState with RocksDB backend + TTL auto-expiry is another solid real-time exact solution.
Final Comparison Summary
Hash Sharding + File Sort Dedupe : Accuracy 100%, Memory/Resources: shard files, low memory, Latency: high (minutes), Applicable: Offline T+1 batch.
Bloom Filter + HBase Fallback : Accuracy 100% (Bloom false positive → penetrate), Memory/Resources: Bloom ~18 GB + HBase cluster, Latency: low (ms), Applicable: Real-time high throughput.
Flink State (RocksDB) : Accuracy 100%, Memory/Resources: Distributed state backend, Latency: low, Applicable: Stateful stream processing.
Single-Machine Bitmap : Accuracy 100%, Memory/Resources: Contiguous IDs ~2.5 GB, Latency: ultra-low, Applicable: Dense order IDs.
Core Code: Bloom + Redis Deduplication with Lua Atomicity
Java implementation of Bloom pre-check + Redis exact deduplication with Lua script for atomicity.
// Bloom filter (Guava-based)
BloomFilter<String> bloomFilter = BloomFilter.create(
Funnels.stringFunnel(Charset.forName("UTF-8")),
10_000_000_000L, // Expected insertions: 10B
0.0001 // False positive 0.01%
);
// Redis Lua script: atomic check-and-insert
String luaScript =
"local exists = redis.call('GET', KEYS[1]) " +
"if exists then " +
" return 0 " + // Already exists → duplicate
"else " +
" redis.call('SET', KEYS[1], '1', 'EX', ARGV[1]) " +
" return 1 " + // Not exists → insert success
"end";
// Main deduplication flow
public boolean isDuplicate(String orderId) {
// Step 1: Bloom fast intercept
if (!bloomFilter.mightContain(orderId)) {
// Definitely not exists → insert into Bloom and allow
bloomFilter.put(orderId);
return false;
}
// Step 2: Bloom returns "maybe exists" → penetrate to Redis exact check
try (Jedis jedis = jedisPool.getResource()) {
// Lua ensures GET+SET atomic, avoids concurrent duplicate inserts
long result = (long) jedis.eval(luaScript,
Collections.singletonList(orderId),
Collections.singletonList("604800") // TTL 7 days
);
if (result == 1) {
// Truly not duplicate → sync update Bloom
bloomFilter.put(orderId);
return false;
}
return true; // Duplicate
}
}Technical Highlights
Bloom + Redis Dual-Layer : Bloom blocks 99.99% requests; Redis handles final exact verification.
Lua Atomicity : GET + SET in Redis single-threaded execution, prevents two concurrent requests both judging "not exists" and both inserting.
TTL Auto-Expiry : Order deduplication usually time-bound (e.g., 7 days); Redis keys auto-expire, controlling memory.
Offline Sharding Deduplication with Spark
Spark shuffle deduplication is ideal hash-sharding + local-dedupe model; one-liner core code:
// Spark exact deduplication: distinct operator, underlying reduceByKey shuffle
Dataset<String> orders = spark.read().textFile("hdfs://input/orders");
Dataset<String> uniqueOrders = orders.distinct();
uniqueOrders.write().text("hdfs://output/unique_orders");Principle: distinct() triggers shuffle, uses order ID as key for reduceByKey, same IDs go to same partition, then each partition deduplicates internally. This is distributed implementation of "sharding + local dedupe"; minimal code, mature shuffle engine.
For finer control, manual hash partitioning:
Dataset<String> unique = orders
.map((MapFunction<String, Tuple2<String, Void>>) s -> new Tuple2<>(s, null),
Encoders.tuple(Encoders.STRING(), Encoders.kryo(Void.class)))
.groupByKey(orders.sparkSession().sparkContext().defaultParallelism()) // hash sharding
.mapGroups((MapGroupsFunction<String, Tuple2<String, Void>, String>) (key, it) -> key,
Encoders.STRING());Technical highlight: Leverages Spark distributed shuffle, no manual file splitting; data skew handled via salting, two-phase aggregation.
Technical Challenges Deep Dive
Data Skew : Offline sharding: some order IDs (hot merchants) concentrate after hash, causing oversized shards, long-tail tasks, OOM. Solution: 1. Two-phase aggregation: add random prefix to scatter, local dedupe then strip prefix; 2. Custom partitioner dynamic adjustment; 3. Adaptive execution like Spark AQE auto-handles skew partitions.
Bloom Filter Non-Resizable : Bit array size fixed at creation; exceeding expected volume spikes false positive rate. Solution: 1. Pre-estimate capacity with 20-30% headroom; 2. Multi-layer Bloom: historical stable layer + incremental new layer, query checks all; 3. Scalable Bloom Filter auto-appends new Blooms.
Redis Memory Pressure & Penetration : 10B orders long-term in Redis → memory explosion; hot keys cause penetration under high concurrency. Solution: 1. Strict TTL (e.g., 7 days) ensures expiry cleanup; 2. Hot key local cache (Caffeine) + Bloom blocks most; 3. Redis cluster sharding disperses single key; 4. Persistence fallback: Redis only hot data, full data in HBase, hot/cold separation.
State Consistency : Real-time stream: checkpoint failure or restart may cause missed duplicates or duplicate inserts. Solution: 1. Flink two-phase commit + Checkpoint for exactly-once; 2. RocksDB state backend, incremental checkpoint fast persistence; 3. Idempotent design: even on replay, Lua atomic insert guarantees eventual consistency.
Bloom Filter Persistence After Service Restart
Bloom filter is in-memory; restart loses data. Solutions:
Periodic Snapshot Persistence : Serialize Bloom BitSet to local disk or HDFS periodically; reload on restart. Guava supports writeTo / readFrom.
Redis-Managed Bloom : Use RedisBloom module; Bloom data lives in Redis, service stateless, restart-safe.
Cold-Start Prewarm : Replay recent (e.g., 7 days) order IDs from HBase to rebuild Bloom; slower but guarantees full consistency.
Production typically chooses RedisBloom or In-memory + periodic snapshots .
Signed-in readers can open the original source through BestHub's protected redirect.
This article has been distilled and summarized from source material, then republished for learning and reference. If you believe it infringes your rights, please contactand we will review it promptly.
How this landed with the community
Was this worth your time?
0 Comments
Thoughtful readers leave field notes, pushback, and hard-won operational detail here.
