In the comment thread of the post “Using Redis as an external index for surfacing interesting content“, Micha Gorelick pointed to a post covering a similar solution used at Bitly:
We store the categorical distribution as a set of event counts, along with a
‘normalising constant’ which is simply the number of all the events we’ve
All this lives in a Redis sorted set where the key describes the variable
which, in this case, would simply be bitly_country and the value would be a
categorical distribution. Each element in the set would be a country and the
score of each element would be the number of clicks from that country. We
store a separate element in the set (traditionally called z) that records
the total number of clicks stored in the set. When we want to report the
categorical distribution, we extract the whole sorted set, divide each count
by z, and report the result.
Storing the categorical distribution in this way allows us to make very
rapid writes (simply increment the score of two elements of the sorted set)
and means we can store millions of categorical distributions in memory.
Storing a large number of these is important, as we’d often like to know the
normal behavior of a particular key phrase, or the normal behavior of a
topic, or a bundle, and so on.
The Bitly team has open sources their solution named Forget Table and the code is available on GitHub.
Original title and link: Bitly Forget Table - Building Categorical Distributions in Redis ( ©myNoSQL)