Binary chunk scanning

[fmbenhassine]

Problem

Chunk scanning is a great feature to isolate faulty items in fault-tolerant chunk-oriented steps. However, the current implementation of this feature is quite "naive" and performs poorly. In fact, if an item is erroneous, the chunk is scanned item by item where each item is reprocessed in its own transaction. This means for a chunk size of 1000, if an item is faulty, there will be 1001 transaction (the first transaction that failed for the entire chunk + 1000 transactions, one for each item).

Suggested solution

Chunk scanning is similar to searching an item in a list. The idea of "binary chunk scanning" is to apply the same principle of binary search to look for the faulty item, with one difference: instead of applying a transaction for each item, we would apply a transaction for each half of the chunk on each iteration.

Here is an example: Let's say we have a chunk of 8 items [A, B, C, D, E, F, G, H] and that C is the faulty item we are looking for. The binary chunk scanning implementation would apply the following transactions:

So for a chunk size of 1000, there will be only 21 transactions compared to 1001 with the current approach. This is two orders of magnitude faster and should greatly improve the performance of fault-tolerant chunk-oriented steps.

Thoughts / feedback / ideas are welcome!

[seonWKim]

I believe your idea is great. I've been thinking of how to implement this feature without changing too much code and came into an idea of doing binary search by moving it in forward direction. For example, we want to find a faulty element(51) in 100 elements, we can do:

1. (1) - scan 1 elements
2. (2, 3) - scan 2 elements
3. (4, 7) - scan 4 elements
4. (8, 15) - scan 8 elements
5. (16, 31) - scan 16 elements
6. (32, 63) - scan 32 elements but fails
7. (32, 47) - scan 16 elements
8. (48, 63) - scan 16 elements but fails
9. (48, 55) - scan 8 elements but fails
10. (48, 51) - scan 4 elements but fails
11. (48, 49) - scan 2 elements
12. (50, 53) - scan 4 elements but fails
13. (50, 51) - scan 2 elements but fails
14. (50) - scan 1 element
15. (51, 52) - scan 2 elemetns but fails
16. (51) - scan 1 element but fails
17. (52) - scan 1 element
18. (53, 54) - scan 2 element
19. (55, 58) - scan 4 elements
20. (59, 56) - scan 8 elements
21. (57, 72) - scan 16 elements
22. (73, 100) - scan remaining elements

Because current chunk scanning is using iterators to find faulty elements, I think we can still use the iterators of current implementation and do binary search(because doing binary search by moving forward doesn't jump between elements which iterators can't do), thereby minimizing code changes.