9 ms·
On Counting (2017)
- saagarjha 8y ago> The oddly named wc is a command used to count things. It’s named after word count.
- AstralStorm 8y agoStill oddly named. Why isn't it called count or cnt?
- saagarjha 8y agoTo keep with the Unix tradition of short command names, I guess?
- LukeShu 8y ago`wc` was in 1st edition Unix. It was setting the tradition, not keeping with it!
- rotten 8y agoI suspect the ability to count things other than words was added later.
- Ensorceled 8y agowc shares an environment with grep, awk, sed and vi; wc is NOT oddly named.
- tpm 8y agoalso with at, bc, cd, cp, dd, df, du and so on
- pgl 8y agoI'm not sure about that - I think you could argue that they're all oddly named.
- Sir_Cmpwn 8y agoFor those interested in the etymology of these: grep is from the ed command (which itself is short for editor, the original Unix text editor) g/re/p, which Globally searches for a Regular Expression and Prints it. sed is Stream EDitor. vi is VIsual editor, which is so named because it's like ed but shows you what you're editing. Not sure where the name awk comes from. All of these tools are closely related to the venerable ed(1) command.
- lainga 8y agoalso - not pointing any fingers - I suspect for the same reason hexadecimal (which programmers shortened to hex) was used over the proper Latin sexadecimal.
- wodenokoto 8y agoAnd overlap with a common abbreviation that refers to a toilet, WC (water closet)[1] So yes, it has an odd name, and I'm sure the inventor of the wc command thought it funny. [1] https://en.wikipedia.org/wiki/Flush_toilet https://en.wikipedia.org/wiki/Flush_toilet
- Alex63 8y agoI wonder if the author might have thought it was an odd name because "wc" is also used in some English-speaking countries as an abbreviation for "water closet", a synonym for a flush toilet.
- mfontani 8y agoReminds me quite a bit of https://adamdrake.com/command-line-tools-can-be-235x-faster-than-your-hadoop-cluster.html https://adamdrake.com/command-line-tools-can-be-235x-faster-... … in which, though, the author at least parallelises the counting.
- ILMostro7 8y agoBash 5.0? Parallel execution
- lmilcin 8y agoCounting unique occurences isn't easy if you are given data the way it was described in the article and you have a requirement for exact count. But there are things you can do to help if you are willing to redesign it a bit. You could partition the data up front, as it is being written. Then you could send partitions to be processed in parallel (and you still could do this with the shell command!)
- zxcmx 8y agoThere is a nearly-as-simple solution involving lambda (which would not require running a kafka cluster) but meh.
- jdironman 8y agoThis person writes quiet well. Few articles draw me in and keep me there until the end. His use of language and story telling really flows and it also made me reminisce of when I used to be passionate about programming myself. Great writing.
- nyc111 8y agoI thought the same thing. Probably because he writes the way he speaks. Or I would like the secret of it.
- jdironman 8y agoRight. I never felt like it 'drawn on and on' like some do. It threw the technical details in while still keeping you reading. I'm curious now about his book on learning Go. If it reads the same way it would probably be worth a read.
- halayli 8y agoaws S3 Select might be a good fit. https://docs.aws.amazon.com/AmazonS3/latest/dev/s3-glacier-select-sql-reference-select.html https://docs.aws.amazon.com/AmazonS3/latest/dev/s3-glacier-s...
- monochromatic 8y agoIs there a fast way to detect duplicates when you first generate the records? If so, could just keep a continuously updated counter for each client, incrementing it every time you add a record, and decrementing on duplicates to avoid double counting.
- dswalter 8y agoBloom filters could do it. https://en.wikipedia.org/wiki/Bloom_filter https://en.wikipedia.org/wiki/Bloom_filter
- amelius 8y agoAre you pulling that joke every time someone asks something you think you know the answer to? It's kind of contradictory.
- dswalter 8y agoI've edited my response, but I think you misunderstand the comic.
- reificator 8y agoWas it the XKCD Ten Thousand comic?
- dswalter 8y agoIndeed.
- repsilat 8y agoIt's possible with hash tables too... Also, the Unix approach can do something like this by spitting out days at a time and sorting them, and then doing a sort -m "$month/*" | uniq -c on the individual files. `sort -m` takes basically no memory, and should chew through data fast enough.
- 8y ago
- bo1024 8y agoIt 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.
- thanatropism 8y agoIt's worth mentioning that counting machines are way older than computers and the Census used to be done with "dumb" punched car munchers. https://en.wikipedia.org/wiki/Tabulating_machine https://en.wikipedia.org/wiki/Tabulating_machine
- msteffen 8y agoSharding a simple bash script across multiple nodes is one of the original (and still one of the most common) uses of Pachyderm. We actually have a tutorial based on it: https://github.com/pachyderm/pachyderm/blob/master/doc/examples/fruit_stand/README.md https://github.com/pachyderm/pachyderm/blob/master/doc/examp... (disclosure: I work at Pachyderm. https://pachyderm.io/ https://pachyderm.io/)
- hinkley 8y agoOr the bland and boring version: bucket sort and xargs.
- Radim 8y agoIf you're into fast cardinality estimation (HyperLogLog) and item counting (Count-min sketch, Bloom filters, hash tables), check out Bounter: https://github.com/RaRe-Technologies/bounter/ https://github.com/RaRe-Technologies/bounter/ (Pythonic interface on top of highly optimized algorithms, faster than dict but using limited memory, MIT license)
- djhworld 8y agoAWS Athena is pretty good at tackling this problem, or PrestoDB running on EMR. As long as your S3 data is reasonably partitioned, and you don't have millions of small files, it does a reasonable job -even on count(distinct) It even support approx_distinct for hyperloglog estimation too
- ikeboy 8y agoWhy not count daily and incrementally? No reason to wait for the last day and then have to meet a deadline, do most of the processing in advance and only need to do a small amount of work each day to update.
- cdoxsey 8y agoWhat if you receive the same tweet 3 days later? It should only be counted once.
- ikeboy 8y agoYou dedup against the old data. Easier than deduping a month's worth all at once, since the old data is sorted.
- Jupe 8y agoOr just don't record it until it's successful. Logging attempts (and billing for them) doesn't seem like a good idea.
- hinkley 8y agoMore precisely: logging attempts might have business value, but not to the billing department. Log your confirmations too.
- cdoxsey 8y agoSorry what I'm getting at is you can't do this problem incrementally. You can't calculate the count on day 1 and add it to the count on day 2. The count of each day is intertwined with all the others. But yes I suppose if at the end of each day you deduped that days records against the rest of the month you could then add them all together. Unfortunately day 30 would still be just as bad as doing the whole month, since removing duplicates is as expensive as counting uniques.
- ikeboy 8y ago
- tomtimtall 8y agoRather than first building up a huge pile of logs and then counting them, move the count to the location that generates the logs or the location that stores them. Easily done, no need for algorithms or special case solutions, just a simple set and count. Added bonus, the “task” is axiomatically done when the month ends no difficulties or special considerations needed there.