Design a Distributed Set (Probabilistic)

To design a distributed structure for checking item presence with low false positives, I would recommend a Distributed Bloom Filter. This is ideal for scenarios like tracking unique vehicle IDs or sensor readings where exact storage is too expensive. First, we establish the parameters. If we expect billions of items with a 1% false positive rate, we calculate the optimal bit array size and number of hash functions using the formula m = -n * ln(p) / (ln(2)^2). We then initialize a shared bit array across the cluster. For insertion, we apply k distinct hash functions to the item. Each hash maps to an index in the bit array, which we set to 1. Crucially, we never clear bits, only set them. For a query, we run the same k hashes. If any bit is 0, the item definitely does not exist. If all are 1, it likely exists, though there is a probability of collision. In a distributed setting, we partition the bit array using consistent hashing based on the item key. This ensures that the same item always hits the same shard, maintaining consistency without requiring global synchronization. While false positives increase slightly with more shards due to independent filtering, the memory savings are substantial. At Tesla, where real-time processing of vast telemetry data is critical, this approach offers the necessary speed and space efficiency, accepting a negligible error rate for the sake of system performance.