HyperLogLog: Counting Unique Values in Terabytes of Data Without Storing Them

Imagine a high-load service that processes a continuous stream of data, such as logs, IP addresses, and user IDs, generating billions of entries daily. The challenge is to determine the number of unique visitors over a week. A common initial approach might be to use a HashSet to store these keys and check the size at the end. While this method seems reasonable, it quickly becomes impractical with billions of entries due to memory constraints. Each IP address, requiring 4 bytes, incurs significant overhead from nodes, pointers, and hashes, leading to a memory consumption of at least 50-100 bytes per element. Consequently, tracking a billion unique entries could demand nearly a hundred gigabytes of RAM, which is costly and unfeasible with multiple instances. However, there is an algorithm that can tackle this problem using approximately 1.5 kilobytes of memory with about 2% error margin, avoiding the need to store the actual data or maintain large clusters. This is where HyperLogLog comes into play, a statistical algorithm that revolutionizes the way we count unique items in Big Data. HyperLogLog is utilized in platforms like Redis, BigQuery, ClickHouse, and Presto. This article will delve into the workings of this algorithm, its implementation in C, and its historical context.