> 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.

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.

That would mean that the hash table would fit in 8 GB of RAM.

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:

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.

2) Count the number of unique items in each bucket using a hash table.

This requires three times the disk I/O as the original but gives exact answers.