Redis Integer Set Optimization for Game Recommendation Deduplication: RoaringBitMap vs intset vs Bloom Filter

This article discusses the optimization of integer set storage for game recommendation deduplication in a Redis-based system.

Background: When users browse game center or app store modules, they perform multiple swipe operations within a session (typically less than 10 minutes, with about 15 swipes per session). Each swipe triggers a recommendation request, and the system needs to filter out previously recommended games to avoid duplicates. For a typical session storing 300 game appIds, the challenge is choosing an efficient data structure for memory optimization.

Technical Analysis:

1. intset: Using intset to store 300 game IDs occupies 1.23KB. Each appId uses 4 bytes (int32), and the overhead includes encoding + length + storage for 400 integers.

2. Bloom Filter: Uses bitmap with hash functions. For 10,000 games with a false positive rate requirement of 10^-5, it requires 17 hash functions and 29KB of bitmap space - too large for this use case.

3. RoaringBitMap: Also uses bitmap but stores actual metadata with 100% accuracy. For 300 game IDs, it only uses 0.5KB - smaller than intset (1.23KB) with a compression ratio of 2.4.

Data Structure Details: RoaringBitMap divides 32-bit unsigned integers into buckets based on the high 16 bits (containers), stored in a RoaringArray structure with keys[] and values[]. It uses two compression methods: variable-length compression for sparse distributions and fixed-length compression for continuous distributions.

Conclusion: RoaringBitMap is the optimal choice for this scenario because game IDs are generally auto-incrementing integers with non-sparse distribution, allowing RoaringBitMap's compression to effectively reduce memory usage. This not only saves hardware costs but also reduces fork blocking and call latency, significantly improving system performance.