Top-100 Request IDs in 4.1 Billion Log Lines
An analytics team must report the 100 most frequent request IDs seen in one day of gateway logs. A day is 4.1 billion lines and about 900 million distinct request IDs, averaging 36 bytes each; each line also carries a timestamp and a latency. The job runs on one worker with a 2 GB heap and 500 GB of local disk and must finish within 90 minutes. The first attempt used a HashMap<String, Long> keyed by request ID and died with OutOfMemoryError after 11 minutes. A teammate proposes a Count-Min Sketch with width 2^24 and depth 5 (about 640 MB of 32-bit counters) and says it 'returns the exact top 100 in a single pass'. From a 1% sample, the item ranked 100th is estimated to occur about 2.1 million times in the full day. The product owner wants a defensible statement about accuracy, not just a job that completes.
1. Show by arithmetic why the HashMap approach cannot fit in 2 GB, and state the order of magnitude of the shortfall.
Read the worked answer
Estimate the retained size of one entry in a HashMap<String, Long> on a 64-bit JVM with compressed oops:
- String object header + fields: about 24 bytes.
- Backing byte[] for a 36-character Latin-1 ID: 16-byte header + 36 bytes + padding, about 56 bytes. So roughly 80 bytes per key.
- Long value: 16 bytes.
- HashMap.Node: 16-byte header + int hash + references to key, value and next, about 32 bytes.
- Table slot amortised at a 0.75 load factor: about 11 bytes.
Total is about 140 bytes per distinct ID, before any GC headroom. 900 million x 140 bytes is about 126 GB. Against a 2 GB heap the shortfall is roughly 60x, and even the 11-minute failure is optimistic because the JVM dies as soon as live data approaches the heap limit, not when the full dataset is loaded.
Two useful sanity checks for the candidate:
- A primitive long[] plus a compact byte-offset index still needs the 36-byte keys, so it saves maybe 40% - nowhere near the factor of 60 required.
- Compressing IDs to 8-byte hashes reduces the key cost, but introduces collisions that must be resolved before reporting exact counts, which is a second pass anyway.
The correct conclusion is that exact global counting cannot be done in one pass in memory on this machine; the constraint is memory, and the fix must move work to disk or give up exactness somewhere.
2. Design an exact algorithm that meets the 2 GB and 90-minute constraints, with the numbers that show it fits.
Read the worked answer
Use a hash-partitioned two-pass external count. Exactness is preserved because a given ID always hashes to exactly one partition.
Pass 1 - partition:
- Stream the 4.1 billion lines, compute h = hash(id) mod 256, and append the raw ID to one of 256 files on local disk.
- 900 million distinct IDs x 36 bytes, plus one record per line, is roughly 150-165 GB written. At a conservative 500 MB/s sequential write that is about 5.5 minutes.
Pass 2 - count per partition:
- Read one partition at a time. 900 million / 256 is about 3.5 million distinct IDs per partition.
- At about 140 bytes per HashMap entry that is roughly 500 MB of live data inside a 2 GB heap - comfortably fits, and leaves room for GC.
- Count with a HashMap<String, Integer>. While counting, maintain a min-heap of the top 100 for that partition.
- Because each ID lives entirely in one partition, its count there is its true global count, so keeping the local top 100 per partition is safe: the global top 100 must be the top 100 of its own partition.
- 256 partitions x 100 candidates = 25,600 candidates, merged in memory without difficulty.
- Re-reading about 165 GB at 500 MB/s is another 5.5 minutes.
Total is roughly 15-25 minutes of I/O plus hashing and counting CPU, well inside 90 minutes. The alternatives worth mentioning and rejecting: a full external sort works but costs O(N log N) with far more I/O; a single-pass in-memory map fails on memory; a sketch is not exact and needs a second pass anyway, so it buys nothing here.
3. Evaluate the Count-Min Sketch proposal. Is it exact, what is the error bound, and does it miss true heavy hitters?
Read the worked answer
It is not exact, and the 'one pass, exact top 100' claim is false on two separate grounds.
Error bound. For width w = 2^24 and depth d = 5 over N = 4.1 billion increments, the guarantee is that the estimate is at least the true count and exceeds it by at most epsilon*N with probability at least 1 - delta, where epsilon = e/w and delta = (1/e)^d. Numerically:
- epsilon*N = 2.718 x 4.1e9 / 1.68e7, about 663.
- delta = e^-5, about 0.7%, so the bound holds with roughly 99.3% probability.
Against a 100th-ranked item of about 2.1 million, an absolute overestimate of up to 663 is about 0.03% - small, but it is not zero, and two items separated by less than ~1,300 in true count cannot be ordered reliably. The ranking near the cutoff is exactly where the error matters.
Second, and more important: a sketch does not store IDs. Even with perfect estimates you cannot enumerate candidates from counters alone. You must keep a separate candidate set, for example a min-heap of IDs whose current estimate exceeds a running threshold.
Does it miss true heavy hitters? No, if the threshold is chosen correctly. Count-Min only ever overestimates, so the true 100th item's estimate is >= its true count of ~2.1 million; any candidate filter set below that value keeps every true top-100 item. The failure mode is the opposite - false positives: items below the cutoff whose estimates are inflated by collisions survive the filter.
So the honest design is a hybrid: stream with the sketch plus a candidate heap in pass 1, then verify the surviving candidates (a few tens of thousands) with a second scan using exact counting. That is accurate and cheap, but note it is the same two passes as the partitioned exact algorithm, so the sketch only wins if pass 1 must stay in memory.