3 ms·
It would have been cool to see a discussion about algorithmic solutions, rather than solutions based on tools like MySQL. There are three basic approaches: sor
by bo1024 8y ago
It would have been cool to see a discussion about algorithmic solutions, rather than solutions based on tools like MySQL.
There are three basic approaches: sort and remove duplicates (the original bash script); insert all items into a set (e.g. hash table) that only keeps unique copies, and count its size; or probabilistic solutions like Count-Min-Sketch or HyperLogLog. But the problem with the latter is that they are approximate, which doesn't sound ideal when billing customers.
The problem with both of the first two approaches is that they require all items to be stored in memory at the same time. As long as that's true, either the sort or hashtable approach will work fine. But once you run out of RAM on a single machine, it's going to slow way way down as it swaps to and from disk constantly.
To me, the natural solution is to just split the dataset alphabetically into, say, 10 or 100 equal-size jobs, and run these either sequentially or in parallel on 10 or 100 machines. So for example if the unique IDs are random strings of digits, then everything starting with 00 is in the first job, everything starting with 01 is in the second, up to 99. For each job, apply either the sort or the set approach; shouldn't matter much.
(edit) For example, here's sequential pseudocode; the second step is embarrassingly parallel.
# split the records
for each record in records_list:
prefix := record[0:2]
write record to file "records"+prefix
# count
total = 0
for each records_prefix_file:
initialize hash_table
for each record in this records_prefix_file:
insert record into hash_table, ignoring if already present
total += size of hash_table
(second edit) I'm a theorist, not a practicioner, so I'm ignoring many practical issues about where to store and back up the data, etc.
- enedil 8y agoSo you're proposing distributed radix tree?
- bo1024 8y agoYou can think of it that way, but much simpler. Only one layer really.
- jerf 8y agoSo, yes, the article is an interesting war story and I don't want to diminish the pain of the writer, who inherited a system he didn't particularly want to touch. But yes, the solution is basically "sharding". Personally I'd start with per-customer sharding, and hope that A: that holds for long enough that I'm much bigger before it's a problem and B: that if I'm already sharding by customer, when the day comes that one customer is too big for a single instance of whatever I'm using that the architecture won't get too offended if we shard a single customer multiple times. (If I were doing both of the things, I'd certainly architect the former so the latter was possible at a later date. It's not that difficult, really; you've already got the "split problem -> process subprobems -> combine results" architecture in place, you just have to make sure not to accidentally grind in the nature of the subproblems too deeply into the system, which is just boring ol' software engineering. It doesn't even cost you much since you're not going to win that much by assuming the nature of the subproblems; it really just would be sloppy programming.) The main challenge here was lack of resources and the importance of getting it right, rather than the challenge of the problem itself, which I don't think is anything the author doesn't know and didn't acknowledge already.
- asgionio 8y agoI think approximate solutions would be fine as long as they're an underestimate. As long as the estimate is close enough, the company shouldn't be bothered by the lost revenue. As long as it never overestimates, the customer can't complain. HyperLogLog is too inaccurate to be practical. But, if these files are smaller than a few billion lines, a Bloom Filter could get 0.0001% accuracy while still fitting in main memory on a single node.