[IMPALA-11539] Mitigate intra-node skew of HDFS scans with MT_DOP

• Type: Bug
• Status: Resolved
• Priority: Major
• Resolution: Fixed
• Fix Version/s: Impala 4.2.0
• Component/s: Backend
• Epic Color: ghx-label-3
• Assignee: Zoltán Borók-Nagy
• Reporter: Zoltán Borók-Nagy
• Created: 29/Aug/22 13:03
• Updated: 19/Sep/22 11:17
• Resolved: 19/Sep/22 11:17

Description

Before IMPALA-9655 scan ranges were statically assigned to intra-node fragment instances based on Longest-Processing Time algorithm:
https://github.com/apache/impala/blame/a7866a94578be6289bbac31686de4d9032ad9261/be/src/scheduling/scheduler.cc#L499-L501

From IMPALA-9655 we use dynamic intra-node load balancing for HDFS scans. It means fragment instances have a shared queue of scan ranges and the fragment instances grab the next scan range to be read from this queue.

IMPALA-9655 got rid of the LPT-algorithm which means the scan ranges are in a random order in the queue. This can lead to a skew if there are large scan ranges at the end.

We could mix the above two by using a priority queue for the scan ranges, so each fragment instance would grab the largest scan range in the queue. This could further mitigate intra-node skewing.

Issue Links

• breaks: IMPALA-11575 TestHdfsScannerSkew.test_mt_dop_skew_lpt fails in test_scanners.py
• is related to: IMPALA-11561 Improve intra-node scheduling of scan ranges