Introduction
Ever wondered why your backend slows to a crawl when comparing massive sets of strings? Here’s how we turned a bottleneck into a lightning-fast operation using bitsets.
Efficiently checking for overlaps between large sets of strings is a common challenge in high-throughput backend services. Traditional approaches — such as nested loops or hash-based comparisons — can quickly become performance bottlenecks, especially as data volumes scale and both memory and response time are critical.
This is particularly true in environments like Walmart’s, where backend systems routinely process millions of records per second to power search, recommendation, and fraud detection features. As our applications grew, we observed that even well-optimized hash set operations struggled to keep up with the demands of real-time processing.
In this blog, I’ll share how we leveraged bitset optimization to transform our string set overlap checks.
The Problem: When “Fast Enough” Isn’t Enough
Our service is designed to handle high volumes of requests, each containing multiple sets of strings mapped to unique keys — such as user IDs, product SKUs, or transaction identifiers. For every incoming key, we must efficiently retrieve the corresponding set of strings from our backend database and determine if there is any overlap with the provided set in the request.
This overlap check is a critical step in workflows like deduplication, access control, and real-time validation. However, as the number of keys and the size of each string set grow, the computational and memory demands of these operations can escalate rapidly.
The Memory Bottleneck
To mitigate performance bottlenecks, we initially explored caching the database string sets locally within each pod. While this approach did improve lookup speed, it introduced a new challenge: memory consumption. As our dataset grew, the memory footprint of these in-memory caches ballooned, reaching as high as an unsustainable level in the worst-case scenarios. This strained our infrastructure resources and increased the risk of out-of-memory errors.
The Naive Approach
Traditional approaches, such as iterating through sets or leveraging hash-based comparisons, often struggle to keep pace under heavy load.
Each comparison required iterating through potentially thousands of strings, resulting in operations with time complexity proportional to the product of the set sizes. Under peak load, this led to noticeable spikes in response times. Even with optimized algorithms, the sheer scale of data made it difficult to achieve the low-latency guarantees required by our backend systems.
// Traditional Hash-based approach
public boolean overlap(Set<String> setA, Set<String> setB) {
// This often involves iterating over the smaller set
// and checking for existence in the larger set.
for (String s : setA) {
if (setB.contains(s)) {
return true;
}
}
return false;
}
While accurate, this approach struggles under heavy load13. Each comparison requires iterating through potentially thousands of strings14. The time complexity is roughly proportional to the product of the set sizes O(N * M) or best case O(N) with hash sets), which quickly becomes a nightmare at scale15. Under peak load, this caused noticeable spikes in response times16.
Enter Bitsets: The “Secret Weapon”
To address these challenges, we implemented a bitset-based optimization.
How It Works
- Unique String Mapping: Assign a unique integer index to every distinct string across all sets (e.g., “xxxxx” → 1).
- Bitset Representation: Represent each set of strings as a bitset, where the bit at position i is set to 1 if the string with index i is present in the set.
Universe: ["apple", "banana", "carrot"]
Index: { "apple": 0, "banana": 1, "carrot": 2 }
Set A: {"apple", "carrot"} -> Bits: 1 0 1
Set B: {"banana"} -> Bits: 0 1 0
Set C: {"apple"} -> Bits: 1 0 0
// Set A and Set C can easily got intersection of "apple"The Implementation
Here is the core logic for converting strings to bitsets and checking for overlaps:
import java.util.*;
public class BitSetStringOverlap {
// Map each string in the universe to a unique bit position
private static Map<String, Integer> buildUniverseIndex(List<String> universe) {
Map<String, Integer> indexMap = new HashMap<>();
for (int i = 0; i < universe.size(); i++) {
indexMap.put(universe.get(i), i);
}
return indexMap;
}// Convert a set of strings to a BitSet
private static BitSet stringsToBitSet(Set<String> strings, Map<String, Integer> universeIndex) {
BitSet bitSet = new BitSet(universeIndex.size());
for (String s : strings) {
Integer idx = universeIndex.get(s);
if (idx != null) {
bitSet.set(idx);
}
}
return bitSet;
}
// Check if two BitSets overlap
private static boolean overlap(BitSet a, BitSet b) {
BitSet clone = (BitSet) a.clone();
clone.and(b);
return !clone.isEmpty();
}
}
With bitsets, overlap checks are reduced to a single bitwise AND operation. If the result is non-zero, an overlap exists. This approach is orders of magnitude faster than traditional set intersection algorithms.
Architecture: Decoupling for Speed
We didn’t just change the code; we changed the architecture to decouple latency-sensitive operations from heavy string processing.
- Centralized Index: We maintain a consistent mapping between each unique string and its corresponding bit position, stored centrally in a SQL database.
- Offline Storage: We shifted from storing raw string arrays in the database to storing their compact bitset representations. When a new string set is persisted, we encode it as a bitset immediately.
- On-the-fly Processing: For incoming requests, we apply the same index mapping on-the-fly, converting the provided string sets into bitsets in real time.
The Impact: Crunching the Numbers
Switching to bitsets delivered tangible benefits to our backend systems. The contrast between the old approach and the new bitset optimization is stark:
In our application we observe following optimization
We drastically reduced the memory footprint required for both caching and storage, preventing the “Ouch!” moments of hitting memory limits.
Practical Considerations
While bitsets are powerful, there are a few things to keep in mind when implementing them:
- The Universe Index: You need a consistent “universe” of strings. We maintain a centralized index mapping in a SQL database to ensure all services speak the same “bit language”.
- Decoupling: This architecture allows us to decouple latency-sensitive operations. Heavy string processing is done offline, while the live request path only handles fast bitwise math.
- When NOT to use: If your universe of strings is infinitely growing with no central management, or if the sets are extremely sparse over a massive range without compression, standard bitsets might need tuning (like Roaring Bitmaps) to remain efficient.
Conclusion
By transforming string set overlap checks into bitset operations, we achieved substantial improvements in both performance and resource utilization. This strategy is particularly effective for large-scale, high-frequency set operations typical in distributed systems like ours.
If you’re building high-throughput systems and struggling with memory or latency during set comparisons, bitsets might just be your secret weapon.
How Bitsets Supercharged Our Backend: Faster String Overlap Checks at Scale was originally published in Walmart Global Tech Blog on Medium, where people are continuing the conversation by highlighting and responding to this story.
Introduction to Malware Binary Triage (IMBT) Course
Looking to level up your skills? Get 10% off using coupon code: MWNEWS10 for any flavor.
Enroll Now and Save 10%: Coupon Code MWNEWS10
Note: Affiliate link – your enrollment helps support this platform at no extra cost to you.