From 5caf48396c72885613f7ed98630faa2c5d902964 Mon Sep 17 00:00:00 2001 From: Xinyu Huang Date: Wed, 17 Aug 2022 04:19:24 +0000 Subject: [PATCH] crimson/os/seastore/omap: optimize merge policy in some corner cases on single key erase sence, for e.g. we have three nodes which are brothers: 1 2 3 4 5 | 6 7 8 | 9 10 11, node min size is 3. When erasing 11 will trigger balance instead of merge, the middle nodes will adjust to 6 7, this will not ensure the all nodes above min size. This corner case might not be harmful but if we want to erase 10,11 at one time (range remove wip need this), this will trigger balance in past policy which will make both two nodes below min size and we might need at least one more merge. This is actually because we cannot ensure a node to merge in tree is above min size. Signed-off-by: Xinyu Huang --- .../os/seastore/omap_manager/btree/omap_btree_node.h | 1 + .../omap_manager/btree/omap_btree_node_impl.cc | 2 +- .../seastore/omap_manager/btree/omap_btree_node_impl.h | 6 ++++++ .../omap_manager/btree/string_kv_node_layout.h | 10 ++++++++++ 4 files changed, 18 insertions(+), 1 deletion(-) diff --git a/src/crimson/os/seastore/omap_manager/btree/omap_btree_node.h b/src/crimson/os/seastore/omap_manager/btree/omap_btree_node.h index 5280e73c496..496baffd4a8 100644 --- a/src/crimson/os/seastore/omap_manager/btree/omap_btree_node.h +++ b/src/crimson/os/seastore/omap_manager/btree/omap_btree_node.h @@ -101,6 +101,7 @@ struct OMapNode : LogicalCachedExtent { virtual bool extent_will_overflow( size_t ksize, std::optional vsize) const = 0; + virtual bool can_merge(OMapNodeRef right) const = 0; virtual bool extent_is_below_min() const = 0; virtual uint32_t get_node_size() = 0; diff --git a/src/crimson/os/seastore/omap_manager/btree/omap_btree_node_impl.cc b/src/crimson/os/seastore/omap_manager/btree/omap_btree_node_impl.cc index cfe9a2f4755..890dd923249 100644 --- a/src/crimson/os/seastore/omap_manager/btree/omap_btree_node_impl.cc +++ b/src/crimson/os/seastore/omap_manager/btree/omap_btree_node_impl.cc @@ -367,7 +367,7 @@ OMapInnerNode::merge_entry( std::make_pair(donor, entry) : std::make_pair(entry, donor); auto [liter, riter] = is_left ? std::make_pair(donor_iter, iter) : std::make_pair(iter, donor_iter); - if (donor->extent_is_below_min()) { + if (l->can_merge(r)) { DEBUGT("make_full_merge l {} r {}", oc.t, *l, *r); assert(entry->extent_is_below_min()); return l->make_full_merge(oc, r diff --git a/src/crimson/os/seastore/omap_manager/btree/omap_btree_node_impl.h b/src/crimson/os/seastore/omap_manager/btree/omap_btree_node_impl.h index a26b9af9e88..8a344f06a7d 100644 --- a/src/crimson/os/seastore/omap_manager/btree/omap_btree_node_impl.h +++ b/src/crimson/os/seastore/omap_manager/btree/omap_btree_node_impl.h @@ -40,6 +40,9 @@ struct OMapInnerNode bool extent_will_overflow(size_t ksize, std::optional vsize) const { return is_overflow(ksize); } + bool can_merge(OMapNodeRef right) const { + return !is_overflow(*right->cast()); + } bool extent_is_below_min() const { return below_min(); } uint32_t get_node_size() { return get_size(); } @@ -154,6 +157,9 @@ struct OMapLeafNode size_t ksize, std::optional vsize) const { return is_overflow(ksize, *vsize); } + bool can_merge(OMapNodeRef right) const { + return !is_overflow(*right->cast()); + } bool extent_is_below_min() const { return below_min(); } uint32_t get_node_size() { return get_size(); } diff --git a/src/crimson/os/seastore/omap_manager/btree/string_kv_node_layout.h b/src/crimson/os/seastore/omap_manager/btree/string_kv_node_layout.h index 06a1dcb6465..7d449d01822 100644 --- a/src/crimson/os/seastore/omap_manager/btree/string_kv_node_layout.h +++ b/src/crimson/os/seastore/omap_manager/btree/string_kv_node_layout.h @@ -660,6 +660,11 @@ public: bool is_overflow(size_t ksize) const { return free_space() < (sizeof(omap_inner_key_le_t) + ksize); } + + bool is_overflow(const StringKVInnerNodeLayout &rhs) const { + return free_space() < rhs.used_space(); + } + bool below_min() const { return free_space() > (capacity() / 2); } @@ -1267,6 +1272,11 @@ public: bool is_overflow(size_t ksize, size_t vsize) const { return free_space() < (sizeof(omap_leaf_key_le_t) + ksize + vsize); } + + bool is_overflow(const StringKVLeafNodeLayout &rhs) const { + return free_space() < rhs.used_space(); + } + bool below_min() const { return free_space() > (capacity() / 2); } -- 2.39.5