You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues-all@impala.apache.org by "Surya Hebbar (Jira)" <ji...@apache.org> on 2024/11/20 13:01:00 UTC
[jira] [Comment Edited] (IMPALA-13555) Enhance order and predictability of reported events
[ https://issues.apache.org/jira/browse/IMPALA-13555?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17899743#comment-17899743 ]
Surya Hebbar edited comment on IMPALA-13555 at 11/20/24 1:00 PM:
-----------------------------------------------------------------
Consider the following example, to see some limitations and complications arising from the current aggregation mechanism(i.e. 'labels', 'label_idxs', 'timestamps').
The events are streamed from instances in this exact order.
Instance 1 -
"Open Started" - 2280ms
"Open Finished" - 3270ms
"Last Batch Returned" - 3470ms
"Closed" - 4100ms
Instance 2 -
"Open Started" - 1280ms
"Open Finished" - 1330ms
"First Batch Requested" - 1370ms
"Closed" - 3100ms
Result of aggregation -
labels -
"Open Started" - 0, "Open Finished" - 1, "Last Batch Returned" - 2, "Closed" - 3, "First Batch Requested" - 4
label_idxs -
0 1 2 3
0 1 4 3
timestamps -
2280 3270 3470 4100
1280 1330 1370 3100
Note : The resulting 'labels', 'timestamps' and 'label_idxs' will be consistent as 'SortEvents' is being called before delivering events.
The proper alignment of timestamps (with zeros substituted) is -
(possible to generate using 'label_idxs')
2280 3270 3470 4100 0
1280 1330 0 3100 1370
The proper order and alignment of timestamps(with zeros substituted) is -
(functionally not possible to generate, even after using 'labels'(map), 'label_idxs' and 'timestamps')
2280 3270 0 3470 4100
1280 1330 1370 0 3100
(note: identifying the order of events, through comparison between timestamps across instances is wrong)
In this manner, if the first few instances responsible for generating 'labels' map have missing events, it is functionally not possible to extract the perfect order.
Hence, the current aggregation mechanism, fails to provide an absolute method to align and order the missing events' timestamp in many edge cases.
Although a definite ordering is not always possible, I have come up with the following approach to generate the most probable orderings(using 'label_idxs' from all instances).
1. Consider each index in 'label_idxs' as a node
2. While maintaining a set of visited nodes
3. Add adjacent indexes in 'label_idxs' as parent(or children), if they exist in visited nodes(Add to visited nodes, otherwise)
4. The result will be
-> A degenerate binary tree (a successful definite order was found)
-> A single multi-terminal unrooted tree(definite order, except where there are multiple terminals)
-> A forest of disjoint trees(not functionally possible to find definite order, need to merge all trees in any order)
5. Level-order traversal of the final tree will provide a perfect order / one of the most probable orderings.
I believe this would result in a space and time complexity of O(n).
In addition to the computational overhead, even after such a complex ordering process, still there is a possibility of not finding the perfect order(when it is not functionally definite, i.e. consider indexes [0, 1, 2] [3, 4, 5]).
The proposed alternative is to have a predefined order for event labels (unsure if it is always possible to have a predefined order for events in cases like AsyncCodegen).
After inspecting all these aspects, I have currently decided to go with the first option here.
There might be a much simpler or different way through this.
Currently the following mechanism has been implemented, which handles almost all cases.
[https://gerrit.cloudera.org/c/21683/9/be/src/util/runtime-profile.cc#3040]
was (Author: JIRAUSER299620):
Consider the following example, to see some limitations and complications arising from the current aggregation mechanism(i.e. 'labels', 'label_idxs', 'timestamps').
The events are streamed from instances in this exact order.
Instance 1 -
"Open Started" - 2280ms
"Open Finished" - 3270ms
"Last Batch Returned" - 3470ms
"Closed" - 4100ms
Instance 2 -
"Open Started" - 1280ms
"Open Finished" - 1330ms
"First Batch Requested" - 1370ms
"Closed" - 3100ms
Result of aggregation -
labels -
"Open Started" - 0, "Open Finished" - 1, "Last Batch Returned" - 2, "Closed" - 3, "First Batch Requested" - 4
label_idxs -
0 1 2 3
0 1 4 3
timestamps -
2280 3270 3470 4100
1280 1330 1370 3100
Note : The resulting 'labels', 'timestamps' and 'label_idxs' will be consistent as 'SortEvents' is being called before delivering events.
The proper alignment of timestamps (with zeros substituted) is -
(possible to generate using 'label_idxs')
2280 3270 3470 4100 0
1280 1330 0 3100 1370
The proper order and alignment of timestamps(with zeros substituted) is -
(functionally not possible to generate, even after using 'labels'(map), 'label_idxs' and 'timestamps')
2280 3270 0 3470 4100
1280 1330 1370 0 3100
(note: identifying the order of events, through comparison between timestamps across instances is wrong)
In this manner, if the first few instances responsible for generating 'labels' map have missing events, it is functionally not possible to extract the perfect order.
Hence, the current aggregation mechanism, fails to provide an absolute method to align and order the missing events' timestamp in many edge cases.
Although a definite ordering is not always possible, I have come up with the following approach to generate the most probable orderings(using 'label_idxs' from all instances).
1. Consider each index in 'label_idxs' as a node
2. While maintaining a set of visited nodes
3. Add adjacent indexes in 'label_idxs' as parent(or children), if they exist in visited nodes(Add to visited nodes, otherwise)
4. The result will be
-> A degenerate binary tree (a successful definite order was found)
-> A single multi-terminal unrooted tree(definite order, except where there are multiple terminals)
-> A forest of disjoint trees(not functionally possible to find definite order, need to merge all trees in any order)
5. Level-order traversal of the final tree will provide a perfect order / one of the most probable orderings.
I believe this would result in a space and time complexity of O(n).
In addition to the computational overhead, even after such a complex ordering process, still there is a possibility of not finding the perfect order(when it is not functionally definite, i.e. consider indexes [0, 1, 2] [3, 4, 5]).
The proposed alternative is to have a predefined order for event labels (unsure if it is always possible to have a predefined order for events in cases like AsyncCodegen).
After inspecting all these aspects, I have currently decided to go with the first option here.
There might be a much simpler or different way through this.
Currently the following mechanism has been implemented, which handles almost all cases.
[https://gerrit.cloudera.org/c/21683/9/be/src/util/runtime-profile.cc#3040]
But, it would be great to enhance EventSequence's constructor and the collection mechanism along with a cleanup and performance boost provided by switching to a completed version of profile V2.
> Enhance order and predictability of reported events
> ---------------------------------------------------
>
> Key: IMPALA-13555
> URL: https://issues.apache.org/jira/browse/IMPALA-13555
> Project: IMPALA
> Issue Type: Improvement
> Reporter: Surya Hebbar
> Priority: Major
>
> In some cases, when the instances responsible for generating 'labels' map have missing events, it is functionally not possible to extract the perfect order.
> The current event aggregation mechanism, fails to provide an absolute method to align and order the missing events' timestamp in many edge cases.
--
This message was sent by Atlassian Jira
(v8.20.10#820010)
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-all-unsubscribe@impala.apache.org
For additional commands, e-mail: issues-all-help@impala.apache.org