Repository: impala Updated Branches: refs/heads/master 421af4e40 -> 84e30700f
IMPALA-6694: fix "buffer pool" child profile order The bug is that child profiles can be re-ordered when being sent between an executor and a coordinator. This occurs if child profile A is present in one update, then another child profile B is inserted at a position before A and is sent to the coordinator in a subsequent update. The algorithm for merging profiles did not preserve the order in that case. The algorithm is fixed to preserve order when the relative order of child profiles is consistent between all updates. Testing: Added a targeted unit test. Change-Id: I230f0673edf20a846fdb13191b7a292d329c1bb8 Reviewed-on: http://gerrit.cloudera.org:8080/9749 Reviewed-by: Lars Volker <[email protected]> Tested-by: Impala Public Jenkins Project: http://git-wip-us.apache.org/repos/asf/impala/repo Commit: http://git-wip-us.apache.org/repos/asf/impala/commit/84e30700 Tree: http://git-wip-us.apache.org/repos/asf/impala/tree/84e30700 Diff: http://git-wip-us.apache.org/repos/asf/impala/diff/84e30700 Branch: refs/heads/master Commit: 84e30700f1a510e53bda852ec498fcc2690426d8 Parents: 421af4e Author: Tim Armstrong <[email protected]> Authored: Wed Mar 21 17:01:45 2018 -0700 Committer: Impala Public Jenkins <[email protected]> Committed: Wed Mar 28 21:21:36 2018 +0000 ---------------------------------------------------------------------- be/src/util/runtime-profile-test.cc | 72 ++++++++++++++++++++++++++++++++ be/src/util/runtime-profile.cc | 38 ++++++++++++++--- 2 files changed, 104 insertions(+), 6 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/impala/blob/84e30700/be/src/util/runtime-profile-test.cc ---------------------------------------------------------------------- diff --git a/be/src/util/runtime-profile-test.cc b/be/src/util/runtime-profile-test.cc index d3394b2..0955203 100644 --- a/be/src/util/runtime-profile-test.cc +++ b/be/src/util/runtime-profile-test.cc @@ -16,7 +16,9 @@ // under the License. #include <stdlib.h> +#include <algorithm> #include <iostream> + #include <boost/bind.hpp> #include "common/object-pool.h" @@ -222,6 +224,76 @@ TEST(CountersTest, MergeAndUpdate) { profile2->PrettyPrint(&dummy); } +// Regression test for IMPALA-6694 - child order isn't preserved if a child +// is prepended between updates. +TEST(CountersTest, MergeAndUpdateChildOrder) { + ObjectPool pool; + // Add Child2 first. + RuntimeProfile* profile1 = RuntimeProfile::Create(&pool, "Parent"); + RuntimeProfile* p1_child2 = RuntimeProfile::Create(&pool, "Child2"); + profile1->AddChild(p1_child2); + TRuntimeProfileTree tprofile1_v1, tprofile1_v2, tprofile1_v3; + profile1->ToThrift(&tprofile1_v1); + + // Update averaged and deserialized profiles from the serialized profile. + RuntimeProfile* averaged_profile = RuntimeProfile::Create(&pool, "merged", true); + RuntimeProfile* deserialized_profile = RuntimeProfile::Create(&pool, "Parent"); + averaged_profile->UpdateAverage(profile1); + deserialized_profile->Update(tprofile1_v1); + + std::vector<RuntimeProfile*> tmp_children; + averaged_profile->GetChildren(&tmp_children); + EXPECT_EQ(1, tmp_children.size()); + EXPECT_EQ("Child2", tmp_children[0]->name()); + deserialized_profile->GetChildren(&tmp_children); + EXPECT_EQ(1, tmp_children.size()); + EXPECT_EQ("Child2", tmp_children[0]->name()); + + // Prepend Child1 and update profiles. + RuntimeProfile* p1_child1 = RuntimeProfile::Create(&pool, "Child1"); + profile1->PrependChild(p1_child1); + profile1->ToThrift(&tprofile1_v2); + averaged_profile->UpdateAverage(profile1); + deserialized_profile->Update(tprofile1_v2); + + averaged_profile->GetChildren(&tmp_children); + EXPECT_EQ(2, tmp_children.size()); + EXPECT_EQ("Child1", tmp_children[0]->name()); + EXPECT_EQ("Child2", tmp_children[1]->name()); + deserialized_profile->GetChildren(&tmp_children); + EXPECT_EQ(2, tmp_children.size()); + EXPECT_EQ("Child1", tmp_children[0]->name()); + EXPECT_EQ("Child2", tmp_children[1]->name()); + + // Test that changes in order of children is handled gracefully by preserving the + // order from the previous update. + profile1->SortChildren([]( + const pair<RuntimeProfile*, bool>& p1, const pair<RuntimeProfile*, bool>& p2) { + return p1.first->name() > p2.first->name(); + }); + profile1->GetChildren(&tmp_children); + EXPECT_EQ("Child2", tmp_children[0]->name()); + EXPECT_EQ("Child1", tmp_children[1]->name()); + profile1->ToThrift(&tprofile1_v3); + averaged_profile->UpdateAverage(profile1); + deserialized_profile->Update(tprofile1_v2); + + // The previous order of children that were already present is preserved. + averaged_profile->GetChildren(&tmp_children); + EXPECT_EQ(2, tmp_children.size()); + EXPECT_EQ("Child1", tmp_children[0]->name()); + EXPECT_EQ("Child2", tmp_children[1]->name()); + deserialized_profile->GetChildren(&tmp_children); + EXPECT_EQ(2, tmp_children.size()); + EXPECT_EQ("Child1", tmp_children[0]->name()); + EXPECT_EQ("Child2", tmp_children[1]->name()); + + // Make sure we can print the profiles. + stringstream dummy; + averaged_profile->PrettyPrint(&dummy); + deserialized_profile->PrettyPrint(&dummy); +} + TEST(CountersTest, HighWaterMarkCounters) { ObjectPool pool; RuntimeProfile* profile = RuntimeProfile::Create(&pool, "Profile"); http://git-wip-us.apache.org/repos/asf/impala/blob/84e30700/be/src/util/runtime-profile.cc ---------------------------------------------------------------------- diff --git a/be/src/util/runtime-profile.cc b/be/src/util/runtime-profile.cc index c057cac..5f205a7 100644 --- a/be/src/util/runtime-profile.cc +++ b/be/src/util/runtime-profile.cc @@ -202,19 +202,33 @@ void RuntimeProfile::UpdateAverage(RuntimeProfile* other) { { lock_guard<SpinLock> l(children_lock_); lock_guard<SpinLock> m(other->children_lock_); - // Recursively merge children with matching names + // Recursively merge children with matching names. + // Track the current position in the vector so we preserve the order of children + // if children are added after the first Update()/UpdateAverage() call (IMPALA-6694). + // E.g. if the first update sends [B, D] and the second update sends [A, B, C, D], + // then this code makes sure that children_ is [A, B, C, D] afterwards. + ChildVector::iterator insert_pos = children_.begin(); for (int i = 0; i < other->children_.size(); ++i) { RuntimeProfile* other_child = other->children_[i].first; ChildMap::iterator j = child_map_.find(other_child->name_); RuntimeProfile* child = NULL; if (j != child_map_.end()) { child = j->second; + // Search forward until the insert position is either at the end of the vector + // or after this child. This preserves the order if the relative order of + // children in all updates is consistent. + bool found_child = false; + while (insert_pos != children_.end() && !found_child) { + found_child = insert_pos->first == child; + ++insert_pos; + } } else { child = Create(pool_, other_child->name_, true); child->metadata_ = other_child->metadata_; bool indent_other_child = other->children_[i].second; child_map_[child->name_] = child; - children_.push_back(make_pair(child, indent_other_child)); + insert_pos = children_.insert(insert_pos, make_pair(child, indent_other_child)); + ++insert_pos; } child->UpdateAverage(other_child); } @@ -329,6 +343,11 @@ void RuntimeProfile::Update(const vector<TRuntimeProfileNode>& nodes, int* idx) ++*idx; { lock_guard<SpinLock> l(children_lock_); + // Track the current position in the vector so we preserve the order of children + // if children are added after the first Update()/UpdateAverage() call (IMPALA-6694). + // E.g. if the first update sends [B, D] and the second update sends [A, B, C, D], + // then this code makes sure that children_ is [A, B, C, D] afterwards. + ChildVector::iterator insert_pos = children_.begin(); // Update children with matching names; create new ones if they don't match. for (int i = 0; i < node.num_children; ++i) { const TRuntimeProfileNode& tchild = nodes[*idx]; @@ -336,11 +355,20 @@ void RuntimeProfile::Update(const vector<TRuntimeProfileNode>& nodes, int* idx) RuntimeProfile* child = NULL; if (j != child_map_.end()) { child = j->second; + // Search forward until the insert position is either at the end of the vector + // or after this child. This preserves the order if the relative order of + // children in all updates is consistent. + bool found_child = false; + while (insert_pos != children_.end() && !found_child) { + found_child = insert_pos->first == child; + ++insert_pos; + } } else { child = Create(pool_, tchild.name); child->metadata_ = tchild.metadata; child_map_[tchild.name] = child; - children_.push_back(make_pair(child, tchild.indent)); + insert_pos = children_.insert(insert_pos, make_pair(child, tchild.indent)); + ++insert_pos; } child->Update(nodes, idx); } @@ -462,9 +490,7 @@ RuntimeProfile* RuntimeProfile::CreateChild(const string& name, bool indent, void RuntimeProfile::GetChildren(vector<RuntimeProfile*>* children) { children->clear(); lock_guard<SpinLock> l(children_lock_); - for (ChildMap::iterator i = child_map_.begin(); i != child_map_.end(); ++i) { - children->push_back(i->second); - } + for (const auto& entry : children_) children->push_back(entry.first); } void RuntimeProfile::GetAllChildren(vector<RuntimeProfile*>* children) {
