A hyper-what-now?
A HyperLogLog is a probabilistic data structure used to count unique values — or as it’s referred to in mathematics: calculating the cardinality of a set.
These values can be anything: for example, IP addresses for the visitors of a website, search terms, or email addresses.
Counting unique values with exact precision requires an amount of memory proportional to the number of unique values. The reason for this is that there is no way of determining if a value has already been seen other than by comparing it to the previously seen values.
Since memory is a limited resource, doing this becomes problematic when working with large sets of values.
A HyperLogLog solves this problem by allowing to trade memory consumption for precision making it possible to estimate cardinalities larger than 109 with a standard error of 2% using only 1.5 kilobytes of memory[1].
How to use HyperLogLogs in Redis
HyperLogLogs have been available in Redis since version 2.8.9 and are accessed
using the PFADD, PFCOUNT, and PFMERGE commands.
A Redis HyperLogLog consumes at most 12 kilobytes of memory and produces approximations with a standard error of 0.81%. The 12 kilobytes do not include the bytes required to store the actual key.
Ignoring PFMERGE, using a HyperLogLog is very similar to using a Set for the
same purpose: instead of adding members with SADD, add them with PFADD
and instead of retrieving the cardinality with SCARD, retrieve it with
PFCOUNT.
The example below shows the output of an interactive Redis session. You can
follow along by running redis-cli and entering the commands shown on the lines
beginning with >. Make sure an instance of redis-server is also running.
> PFADD visitors alice bob carol
(integer) 1
> PFCOUNT visitors
(integer) 3
PFADD returns 1 if the approximated cardinality of the HyperLogLog was
changed when adding the element. If not, it returns 0.
After calculating the cardinality, PFCOUNT will store the calculated value
in the last 8 bytes of the HyperLogLog to serve as a cache. This cache is
invalidated on the next PFADD.
The PFMERGE command is used to produce a HyperLogLog that approximates the
cardinality of the union of two or more existing HyperLogLogs:
> PFADD customers alice dan
(integer) 1
> PFMERGE everyone visitors customers
OK
> PFCOUNT everyone
(integer) 4
The same result can be achieved by supplying multiple keys to PFCOUNT. In
this case an on-the-fly merge is performed:
> PFCOUNT visitors customers
(integer) 4
Under the hood, HyperLogLogs are actually stored as strings and can be GET
and SET as such:
> GET visitors
"HYLL\x01\x00\x00\x00\x03\x00\x00\x00\x00\x00\x00\x00E<\x94X\x10\x84Qi\x8cQD"
> SET visitors "HYLL\x01\x00\x00\x00\x03\x00\x00\x00\x00\x00\x00\x00E<\x94X\x10\x84Qi\x8cQD"
OK
> PFCOUNT visitors
(integer) 3
This is useful if the HyperLogLog needs to be persisted elsewhere and later restored.
The PFADD, PFCOUNT, and PFMERGE commands are prefixed with PF in
memory of Philippe Flajolet, the inventor of the HyperLogLog algorithm.
The theory behind HyperLogLogs
To get started, let’s look at something more familiar than HyperLogLogs.
Imagine someone flipping a coin multiple times, while recording the maximum number of heads they get in a row. If they told you this number — would you be able to estimate how many times they’d flipped the coin?
Not with great accuracy, but since a longer run of heads is more probable when flipping the coin many times, the number of consecutive heads or tails in a series of coin flips can indicate how many times the coin was flipped: if the number of heads in a row is low, the number of coin flips is most probably also low. Conversely, if the number of heads in a row is high the number of coin flips is most probably high.
If the same number of coin flips were done and recorded separately, a much more precise estimate could be made by combining these numbers. This can be observed using the following methods:
def coin_flips(n)
Array.new(n) { [:heads, :tails].sample }
end
def heads_in_a_row(flips)
run = max = 0
flips.each do |flip|
if flip == :heads
run += 1
else
max = [run, max].max
run = 0
end
end
max
end
class Array
def average
reduce(:+).to_f / size
end
end
The bigger the number of coin flips, the bigger the number of heads in a row.
heads_in_a_row coin_flips(10) #=> 3
heads_in_a_row coin_flips(100) #=> 5
heads_in_a_row coin_flips(1000) #=> 9
heads_in_a_row coin_flips(10000) #=> 15
The bigger the number of series, the better the stability of the output. With a more stable output, a better estimate can be made:
heads_in_a_row coin_flips(10) #=> 3
heads_in_a_row coin_flips(10) #=> 7
heads_in_a_row coin_flips(10) #=> 4
Array.new(1000) { heads_in_a_row coin_flips(10) }.average #=> 2.449
Array.new(1000) { heads_in_a_row coin_flips(10) }.average #=> 2.442
Array.new(1000) { heads_in_a_row coin_flips(10) }.average #=> 2.469
Similarly to how the number of coin flips can be estimated by observing the number of heads in a row, the calculations of a HyperLogLog are based on the observation that the cardinality of a set of uniformly distributed random numbers can be estimated by counting the maximum number of leading zeros in the binary representation of the numbers.
For there to be leading zeros, the numbers must be represented as integers with the same number of bits, for instance as 64-bit unsigned integers.
If the maximum number of leading zeros is n, the estimated number of unique values in the set is 2n.
To make sure values are uniformly distributed and represented as same-size integers, the HyperLogLog algorithm applies a hash function to all values. This transforms the values into a set of uniformly distributed random numbers with the same cardinality as the original set.
The first few bits of the hashed values are used to divide them into different subsets, much like the separate series of coin flips in the example above. For each subset the maximum number of leading zeros within its values are stored in a register.
To calculate the approximate cardinality of the whole set, the estimates for all the subsets are combined using a harmonic mean.
An example use-case
Here’s an example of how to use a Redis HyperLogLog to count unique visitors of a site built with Sinatra using a custom Rack middleware:
require 'redis'
require 'sinatra'
$redis = Redis.new
class VisitorCounter
def initialize(app)
@app = app
end
def call(env)
$redis.pfadd 'visitors', Rack::Request.new(env).ip
@app.call(env)
end
end
use VisitorCounter
get '/' do
visitors = $redis.pfcount 'visitors'
"This website has been visited by #{visitors} unique visitors."
end
References
- Flajolet, P.; Fusy, E.; Gandouet, O.; Meunier, F. (2007). “HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm”. AOFA ’07: Proceedings of the 2007 International Conference on the Analysis of Algorithms.