5 ms·
> 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
by jewel 15y ago
> 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.
- deleted 15y ago[deleted]
- jandrewrogers 15y agoI believe they meant 128 bits (16 characters * 8 bits).
- iclelland 15y agoYou'd think so, but then every other calculation in that paragraph is based on bytes: 1MB for 8192 identifiers (as opposed to 128K as strings, or 64K as ints) 384GB for 3 billion identifiers (rather than 38GB strings, or 19GB ints) 119GiB if 1 in 3 is unique (rather than 12GiB strings, or 6GiB ints) 6GiB is not a lot of RAM anymore.
- VMG 15y ago> 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. That is the same as saying "count all id's starting with 'aa', add all id's starting with 'ab', add all id's starting with 'ac'...", isn't it?
- jewel 15y agoNo, you don't want a count, you actually want a list of those IDs so that you can later reopen each file and count how many distinct entries there are in it, aka. divide and conquer.