How To Count A Billion Objects Using Only 1.5KB Of Memory [Probabilistically]
> These 16 characters represent 128 bytes. 8192 IDs would require 1 megabyte of space.  We receive over 3 billion events per day... Even if we assume that only 1 in 3 records are unique the hash set would still take 119 gigs of RAM, not including the overhead Java requires to store objects in memory.<p>The math seems wrong here.  You can actually fit 16 characters in 16 bytes!  In this case they can do it in 8 since it looks like it's a hex string.<p>That would mean that the hash table would fit in 8 GB of RAM.<p>In any case, it's a neat trick.  Here's an algorithm for counting arbitrarily sized input, assuming the data is too big to fit in memory:<p>1) Walk through the data, writing out the IDs to a different file based on the first n digits.  Split it into enough buckets that each individual bucket is small enough to fit comfortably in RAM.<p>2) Count the number of unique items in each bucket using a hash table.<p>This requires three times the disk I/O as the original but gives exact answers.