3 ms·
I read about an interesting technique, an "all-or-nothing tracker" in a blog post from an Apache Spark engineer. You dispatch n jobs, where n is quite large, a
by zaroth 11y ago
I read about an interesting technique, an "all-or-nothing tracker" in a blog post from an Apache Spark engineer.
You dispatch n jobs, where n is quite large, and you want to know; have all n jobs have completed, or has less than n jobs have completed. How to do so with a small fixed number of bytes with very high probability?
Give each job a random 128-bit ID number. XOR each ID number together as you start each job, and XOR into the same value as each job completes. If all the jobs have completed, the result is 0. The chance of zero turning up randomly if all jobs are not complete is negligible.
The technique is mentioned here under 'Lineage Tracking': https://highlyscalable.wordpress.com/2013/08/20/in-stream-big-data-processing/ https://highlyscalable.wordpress.com/2013/08/20/in-stream-bi... but there's a better blog post I remembered reading but can't find at the moment...
- nl 11y agoThis is kinda a Bloom filter: https://en.m.wikipedia.org/wiki/Bloom_filter https://en.m.wikipedia.org/wiki/Bloom_filter
- anonymousDan 11y agoThis is basically how Apache Storm fault tolerance worked. The problem I have with it is what do you do when one of your workers failed and you're not sure if it failed before sending a job completion message? Storm just restarts everything I believe, which is not great. If you just restart that job you could be left with 'dangling' acks.