diff options
Diffstat (limited to 'searchcore')
9 files changed, 493 insertions, 75 deletions
diff --git a/searchcore/CMakeLists.txt b/searchcore/CMakeLists.txt index c0353747e80..36ef347b7ac 100644 --- a/searchcore/CMakeLists.txt +++ b/searchcore/CMakeLists.txt @@ -54,6 +54,7 @@ vespa_define_module( src/apps/vespa-transactionlog-inspect TESTS + src/tests/bmcluster/estimate_moved_docs_ratio src/tests/grouping src/tests/proton/attribute src/tests/proton/attribute/attribute_aspect_delayer diff --git a/searchcore/src/apps/vespa-redistribute-bm/vespa_redistribute_bm.cpp b/searchcore/src/apps/vespa-redistribute-bm/vespa_redistribute_bm.cpp index e5c3959d2d4..0227d9539d2 100644 --- a/searchcore/src/apps/vespa-redistribute-bm/vespa_redistribute_bm.cpp +++ b/searchcore/src/apps/vespa-redistribute-bm/vespa_redistribute_bm.cpp @@ -17,6 +17,8 @@ #include <vespa/searchcore/bmcluster/bm_node_stats_reporter.h> #include <vespa/searchcore/bmcluster/bm_range.h> #include <vespa/searchcore/bmcluster/bucket_selector.h> +#include <vespa/searchcore/bmcluster/calculate_moved_docs_ratio.h> +#include <vespa/searchcore/bmcluster/estimate_moved_docs_ratio.h> #include <vespa/searchcore/bmcluster/spi_bm_feed_handler.h> #include <vespa/searchlib/index/dummyfileheadercontext.h> #include <vespa/vespalib/io/fileutil.h> @@ -51,6 +53,8 @@ using search::bmcluster::BmNode; using search::bmcluster::BmNodeStatsReporter; using search::bmcluster::BmRange; using search::bmcluster::BucketSelector; +using search::bmcluster::CalculateMovedDocsRatio; +using search::bmcluster::EstimateMovedDocsRatio; using search::index::DummyFileHeaderContext; using storage::lib::State; @@ -100,76 +104,6 @@ vespalib::string& get_mode_name(Mode mode) { return (i < mode_names.size()) ? mode_names[i] : bad_mode_name; } -double -estimate_lost_docs_base_ratio(uint32_t redundancy, uint32_t lost_nodes, uint32_t num_nodes) -{ - if (redundancy > lost_nodes) { - return 0.0; - } - double loss_ratio = 1.0; - for (uint32_t i = 0; i < redundancy; ++i) { - loss_ratio *= ((double) (lost_nodes - i)) / (num_nodes - i); - } - LOG(info, "estimated lost docs base ratio: %4.2f", loss_ratio); - return loss_ratio; -} - -double -estimate_moved_docs_ratio_grow(uint32_t redundancy, uint32_t added_nodes, uint32_t num_nodes) -{ - double new_redundancy = redundancy; - double new_per_node_doc_ratio = new_redundancy / num_nodes; - double moved_ratio = new_per_node_doc_ratio * added_nodes; - LOG(info, "estimated_moved_docs_ratio_grow(%u,%u,%u)=%4.2f", redundancy, added_nodes, num_nodes, moved_ratio); - return moved_ratio; -} - -double -estimate_moved_docs_ratio_shrink(uint32_t redundancy, uint32_t retired_nodes, uint32_t num_nodes) -{ - double old_redundancy = redundancy; - double old_per_node_doc_ratio = old_redundancy / num_nodes; - uint32_t new_nodes = num_nodes - retired_nodes; - double new_redundancy = std::min(redundancy, new_nodes); - double new_per_node_doc_ratio = new_redundancy / new_nodes; - double moved_ratio = (new_per_node_doc_ratio - old_per_node_doc_ratio) * new_nodes; - LOG(info, "estimated_moved_docs_ratio_shrink(%u,%u,%u)=%4.2f", redundancy, retired_nodes, num_nodes, moved_ratio); - return moved_ratio; -} - -double -estimate_moved_docs_ratio_crash(uint32_t redundancy, uint32_t crashed_nodes, uint32_t num_nodes) -{ - double old_redundancy = redundancy; - double old_per_node_doc_ratio = old_redundancy / num_nodes; - uint32_t new_nodes = num_nodes - crashed_nodes; - double new_redundancy = std::min(redundancy, new_nodes); - double new_per_node_doc_ratio = new_redundancy / new_nodes; - double lost_docs_ratio = estimate_lost_docs_base_ratio(redundancy, crashed_nodes, num_nodes) * new_redundancy; - double moved_ratio = (new_per_node_doc_ratio - old_per_node_doc_ratio) * new_nodes - lost_docs_ratio; - LOG(info, "estimated_moved_docs_ratio_crash(%u,%u,%u)=%4.2f", redundancy, crashed_nodes, num_nodes, moved_ratio); - return moved_ratio; -} - -double -estimate_moved_docs_ratio_replace(uint32_t redundancy, uint32_t added_nodes, uint32_t retired_nodes, uint32_t num_nodes) -{ - uint32_t old_nodes = num_nodes - added_nodes; - double old_redundancy = std::min(redundancy, old_nodes); - double old_per_node_doc_ratio = old_redundancy / old_nodes; - uint32_t new_nodes = num_nodes - retired_nodes; - double new_redundancy = std::min(redundancy, new_nodes); - double new_per_node_doc_ratio = new_redundancy / new_nodes; - double moved_ratio = new_per_node_doc_ratio * added_nodes; - uint32_t stable_nodes = num_nodes - added_nodes - retired_nodes; - // Account for extra documents moved from retired nodes to stable nodes - double extra_per_stable_node_doc_ratio = new_per_node_doc_ratio * added_nodes / old_nodes; - double extra_moved_ratio = (std::min(1.0, new_per_node_doc_ratio + extra_per_stable_node_doc_ratio) - old_per_node_doc_ratio) * stable_nodes; - moved_ratio += extra_moved_ratio; - LOG(info, "estimated_moved_docs_ratio_replace(%u,%u,%u,%u)=%4.2f, (of which %4.2f extra)", redundancy, added_nodes, retired_nodes, num_nodes, moved_ratio, extra_moved_ratio); - return moved_ratio; -} - class BMParams : public BmClusterParams, public BmFeedParams { @@ -391,7 +325,7 @@ Benchmark::estimate_lost_docs() case Mode::TEMP_CRASH: { double new_redundancy = std::min(_params.get_redundancy(), _params.get_num_nodes() - _params.get_flip_nodes()); - auto lost_docs_ratio = estimate_lost_docs_base_ratio(_params.get_redundancy(), _params.get_flip_nodes(), _params.get_num_nodes()) * new_redundancy; + auto lost_docs_ratio = EstimateMovedDocsRatio().estimate_lost_docs_base_ratio(_params.get_redundancy(), _params.get_flip_nodes(), _params.get_num_nodes()) * new_redundancy; return _params.get_documents() * lost_docs_ratio; } default: @@ -404,14 +338,21 @@ Benchmark::estimate_moved_docs() { switch(_params.get_mode()) { case Mode::GROW: - return _params.get_documents() * estimate_moved_docs_ratio_grow(_params.get_redundancy(), _params.get_flip_nodes(), _params.get_num_nodes()); + return _params.get_documents() * EstimateMovedDocsRatio().estimate_moved_docs_ratio_grow(_params.get_redundancy(), _params.get_flip_nodes(), _params.get_num_nodes()); case Mode::SHRINK: - return _params.get_documents() * estimate_moved_docs_ratio_shrink(_params.get_redundancy(), _params.get_flip_nodes(), _params.get_num_nodes()); + return _params.get_documents() * EstimateMovedDocsRatio().estimate_moved_docs_ratio_shrink(_params.get_redundancy(), _params.get_flip_nodes(), _params.get_num_nodes()); case Mode::PERM_CRASH: case Mode::TEMP_CRASH: - return _params.get_documents() * estimate_moved_docs_ratio_crash(_params.get_redundancy(), _params.get_flip_nodes(), _params.get_num_nodes()); + return _params.get_documents() * EstimateMovedDocsRatio().estimate_moved_docs_ratio_crash(_params.get_redundancy(), _params.get_flip_nodes(), _params.get_num_nodes()); case Mode::REPLACE: - return _params.get_documents() * estimate_moved_docs_ratio_replace(_params.get_redundancy(), _params.get_flip_nodes(), _params.get_flip_nodes(), _params.get_num_nodes()); + if (_params.get_num_nodes() < 10) { + // Calculate better estimate for moved docs ratio with brute force + auto scanner = CalculateMovedDocsRatio::make_replace_calculator(_params.get_redundancy(), _params.get_flip_nodes(), _params.get_flip_nodes(), _params.get_num_nodes()); + scanner.scan(); + return _params.get_documents() * scanner.get_moved_docs_ratio(); + } else { + return _params.get_documents() * EstimateMovedDocsRatio().estimate_moved_docs_ratio_replace(_params.get_redundancy(), _params.get_flip_nodes(), _params.get_flip_nodes(), _params.get_num_nodes()); + } default: return 0.0; } diff --git a/searchcore/src/tests/bmcluster/estimate_moved_docs_ratio/CMakeLists.txt b/searchcore/src/tests/bmcluster/estimate_moved_docs_ratio/CMakeLists.txt new file mode 100644 index 00000000000..23f72e4f1fa --- /dev/null +++ b/searchcore/src/tests/bmcluster/estimate_moved_docs_ratio/CMakeLists.txt @@ -0,0 +1,11 @@ +# Copyright Yahoo. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. +vespa_add_executable(searchcore_bmcluster_estimate_moved_docs_ratio_test_app TEST + SOURCES + estimate_moved_docs_ratio_test.cpp + DEPENDS + searchcore_bmcluster + GTest::GTest +) + +vespa_add_test(NAME searchcore_bmcluster_estimate_moved_docs_ratio_test_app + COMMAND searchcore_bmcluster_estimate_moved_docs_ratio_test_app) diff --git a/searchcore/src/tests/bmcluster/estimate_moved_docs_ratio/estimate_moved_docs_ratio_test.cpp b/searchcore/src/tests/bmcluster/estimate_moved_docs_ratio/estimate_moved_docs_ratio_test.cpp new file mode 100644 index 00000000000..79af31e3247 --- /dev/null +++ b/searchcore/src/tests/bmcluster/estimate_moved_docs_ratio/estimate_moved_docs_ratio_test.cpp @@ -0,0 +1,134 @@ +// Copyright Yahoo. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. + +#include <vespa/vespalib/gtest/gtest.h> +#include <vespa/searchcore/bmcluster/calculate_moved_docs_ratio.h> +#include <vespa/searchcore/bmcluster/estimate_moved_docs_ratio.h> +#include <iostream> + +#include <vespa/log/log.h> +LOG_SETUP("estimate_moved_docs_ratio_test"); + +using search::bmcluster::CalculateMovedDocsRatio; +using search::bmcluster::EstimateMovedDocsRatio; + +namespace { + +bool verbose; + +TEST(EstimateMovedDocsRatioTest, estimate_lost_docs_ratio) +{ + for (uint32_t nodes = 1; nodes < 2; ++nodes) { + for (uint32_t redundancy = 1; redundancy <= nodes; ++redundancy) { + for (uint32_t lost_nodes = 0; lost_nodes <= nodes; ++lost_nodes) { + auto scanner = CalculateMovedDocsRatio::make_crash_calculator(redundancy, lost_nodes, nodes); + scanner.scan(); + double lost_docs_base_ratio = scanner.get_lost_docs_base_ratio(); + double estimated_lost_docs_base_ratio = EstimateMovedDocsRatio().estimate_lost_docs_base_ratio(redundancy, lost_nodes, nodes); + EXPECT_DOUBLE_EQ(lost_docs_base_ratio, estimated_lost_docs_base_ratio); + } + } + } +} + +TEST(EstimateMovedDocsRatioTest, estimate_moved_docs_ratio_grow) +{ + for (uint32_t nodes = 1; nodes < 10; ++nodes) { + for (uint32_t redundancy = 1; redundancy <= nodes; ++redundancy) { + for (uint32_t added_nodes = 0; added_nodes <= nodes; ++added_nodes) { + auto scanner = CalculateMovedDocsRatio::make_grow_calculator(redundancy, added_nodes, nodes); + scanner.scan(); + double moved_docs_ratio = scanner.get_moved_docs_ratio(); + double estimated_moved_docs_ratio = EstimateMovedDocsRatio().estimate_moved_docs_ratio_grow(redundancy, added_nodes, nodes); + EXPECT_DOUBLE_EQ(moved_docs_ratio, estimated_moved_docs_ratio); + } + } + } +} + +TEST(EstimateMovedDocsRatioTest, estimate_moved_docs_ratio_shrink) +{ + for (uint32_t nodes = 1; nodes < 10; ++nodes) { + for (uint32_t redundancy = 1; redundancy <= nodes; ++redundancy) { + for (uint32_t retired_nodes = 0; retired_nodes <= nodes; ++retired_nodes) { + auto scanner = CalculateMovedDocsRatio::make_shrink_calculator(redundancy, retired_nodes, nodes); + scanner.scan(); + double moved_docs_ratio = scanner.get_moved_docs_ratio(); + double estimated_moved_docs_ratio = EstimateMovedDocsRatio().estimate_moved_docs_ratio_shrink(redundancy, retired_nodes, nodes); + EXPECT_DOUBLE_EQ(moved_docs_ratio, estimated_moved_docs_ratio); + } + } + } +} + +TEST(EstimateMovedDocsRatioTest, estimate_moved_docs_ratio_crash) +{ + double epsilon = 1e-15; + for (uint32_t nodes = 1; nodes < 10; ++nodes) { + for (uint32_t redundancy = 1; redundancy <= nodes; ++redundancy) { + for (uint32_t crashed_nodes = 0; crashed_nodes <= nodes; ++crashed_nodes) { + auto scanner = CalculateMovedDocsRatio::make_crash_calculator(redundancy, crashed_nodes, nodes); + scanner.scan(); + double moved_docs_ratio = scanner.get_moved_docs_ratio(); + double estimated_moved_docs_ratio = EstimateMovedDocsRatio().estimate_moved_docs_ratio_crash(redundancy, crashed_nodes, nodes); + EXPECT_NEAR(moved_docs_ratio, estimated_moved_docs_ratio, epsilon); + } + } + } +} + +TEST(EstimateMovedDocsRatioTest, estimate_moved_docs_ratio_replace) +{ + uint32_t bad_cases = 0; + uint32_t really_bad_cases = 0; + if (verbose) { + std::cout << "Summary: HDR Red A Ret N Act Est ScaleMv ScaleEs States" << std::endl; + } + for (uint32_t nodes = 1; nodes < 6; ++nodes) { + for (uint32_t redundancy = 1; redundancy <= nodes; ++redundancy) { + for (uint32_t retired_nodes = 0; retired_nodes <= nodes; ++retired_nodes) { + for (uint32_t added_nodes = 0; added_nodes <= nodes - retired_nodes; ++added_nodes) { + // std::cout << "Estimate moved docs ratio replace " << retired_nodes << " of " << nodes << " retired, added " << added_nodes << " nodes ,redundancy " << redundancy << std::endl; + auto scanner = CalculateMovedDocsRatio::make_replace_calculator(redundancy, added_nodes, retired_nodes, nodes); + scanner.scan(); + double moved_docs_ratio = scanner.get_moved_docs_ratio(); + double estimated_moved_docs_ratio = EstimateMovedDocsRatio(verbose).estimate_moved_docs_ratio_replace(redundancy, added_nodes, retired_nodes, nodes); + double error_ratio = abs(moved_docs_ratio - estimated_moved_docs_ratio); + bool bad = error_ratio > 1e-8; + bool really_bad = error_ratio > 0.2 * estimated_moved_docs_ratio + 1e-8; + if (bad) { + ++bad_cases; + } + if (really_bad) { + ++really_bad_cases; + } + if (verbose) { + double scaled_moved = moved_docs_ratio * scanner.get_checked_states(); + double scaled_estimated_moved = estimated_moved_docs_ratio * scanner.get_checked_states(); + std::cout << "Summary: " << (bad ? "BAD" : "OK ") << std::setw(4) << redundancy << std::setw(4) << added_nodes << std::setw(4) << retired_nodes << std::setw(4) << nodes << " " << std::setw(12) << std::setprecision(5) << std::fixed << moved_docs_ratio << " " << std::setw(12) << std::setprecision(5) << std::fixed << estimated_moved_docs_ratio << " " << std::setw(12) << std::setprecision(5) << std::fixed << scaled_moved << " " << std::setw(12) << std::setprecision(5) << std::fixed << scaled_estimated_moved << std::setw(8) << scanner.get_checked_states(); + std::cout << " ["; + for (uint32_t node_idx = 0; node_idx < nodes; ++node_idx) { + std::cout << std::setw(8) << scanner.get_moved_docs_per_node()[node_idx]; + } + std::cout << " ]" << std::endl; + } + // TODO: Fix calculation so we get zero bad cases. + // EXPECT_DOUBLE_EQ(moved_docs_ratio, estimated_moved_docs_ratio); + } + } + } + } + EXPECT_LE(6, bad_cases); + EXPECT_LE(1, really_bad_cases); +} + +} // namespace + +int +main(int argc, char* argv[]) +{ + ::testing::InitGoogleTest(&argc, argv); + if (argc > 1 && std::string("--verbose") == argv[1]) { + verbose = true; + } + return RUN_ALL_TESTS(); +} diff --git a/searchcore/src/vespa/searchcore/bmcluster/CMakeLists.txt b/searchcore/src/vespa/searchcore/bmcluster/CMakeLists.txt index d2ab8b0c2a9..0de021a9514 100644 --- a/searchcore/src/vespa/searchcore/bmcluster/CMakeLists.txt +++ b/searchcore/src/vespa/searchcore/bmcluster/CMakeLists.txt @@ -19,7 +19,9 @@ vespa_add_library(searchcore_bmcluster STATIC bm_storage_link.cpp bm_storage_message_addresses.cpp bucket_info_queue.cpp + calculate_moved_docs_ratio.cpp document_api_message_bus_bm_feed_handler.cpp + estimate_moved_docs_ratio.cpp pending_tracker.cpp pending_tracker_hash.cpp spi_bm_feed_handler.cpp diff --git a/searchcore/src/vespa/searchcore/bmcluster/calculate_moved_docs_ratio.cpp b/searchcore/src/vespa/searchcore/bmcluster/calculate_moved_docs_ratio.cpp new file mode 100644 index 00000000000..63f23476a95 --- /dev/null +++ b/searchcore/src/vespa/searchcore/bmcluster/calculate_moved_docs_ratio.cpp @@ -0,0 +1,142 @@ +// Copyright Yahoo. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. + +#include "calculate_moved_docs_ratio.h" +#include <cassert> + +namespace search::bmcluster { + +namespace { + +uint32_t make_bit_range(uint32_t low, uint32_t high) +{ + return (1u << high) - (1u << low); +} + +} + +struct CalculateMovedDocsRatio::Placements +{ + uint32_t _mask; + uint32_t _count; + + Placements() + : _mask(0u), + _count(0u) + { + } + + Placements(uint32_t mask, uint32_t count) noexcept + : _mask(mask), + _count(count) + { + } + + Placements add(uint32_t idx) const noexcept { + return Placements(_mask | (1u << idx), _count + 1); + } + + Placements add(uint32_t idx, uint32_t mask, uint32_t redundancy) const noexcept { + return (((_count < redundancy) && ((1u << idx) & mask) != 0)) ? Placements(_mask | (1u << idx), _count + 1) : *this; + } +}; + + +CalculateMovedDocsRatio::CalculateMovedDocsRatio(uint32_t nodes, uint32_t redundancy, uint32_t old_placement_mask, uint32_t new_placement_mask, uint32_t new_up_mask) + : _num_states(nodes + 1), + _nodes(nodes), + _old_placement_mask(old_placement_mask), + _new_placement_mask(new_placement_mask), + _new_up_mask(new_up_mask), + _moved_docs(0u), + _moved_docs_per_node(nodes), + _checked_states(0u), + _lost_docs_base(0u), + _redundancy(redundancy), + _old_redundancy(std::min(redundancy, (uint32_t)__builtin_popcount(old_placement_mask))), + _new_redundancy(std::min(redundancy, (uint32_t)__builtin_popcount(new_placement_mask))) +{ + assert((new_placement_mask & ~new_up_mask) == 0u); + uint32_t states = 1; + for (uint32_t level = nodes; level > 0; --level) { + states *= std::max(1u, nodes - level); + _num_states[level] = states; + } + _num_states[0] = states * nodes; +} + +CalculateMovedDocsRatio::~CalculateMovedDocsRatio() = default; + +CalculateMovedDocsRatio +CalculateMovedDocsRatio::make_grow_calculator(uint32_t redundancy, uint32_t added_nodes, uint32_t nodes) +{ + uint32_t old_placement_mask = make_bit_range(added_nodes, nodes); + uint32_t new_placement_mask = make_bit_range(0, nodes); + return CalculateMovedDocsRatio(nodes, redundancy, old_placement_mask, new_placement_mask, new_placement_mask); +} + +CalculateMovedDocsRatio +CalculateMovedDocsRatio::make_shrink_calculator(uint32_t redundancy, uint32_t retired_nodes, uint32_t nodes) +{ + uint32_t old_placement_mask = make_bit_range(0, nodes); + uint32_t new_placement_mask = make_bit_range(retired_nodes, nodes); + return CalculateMovedDocsRatio(nodes, redundancy, old_placement_mask, new_placement_mask, old_placement_mask); +} + +CalculateMovedDocsRatio +CalculateMovedDocsRatio::make_crash_calculator(uint32_t redundancy, uint32_t crashed_nodes, uint32_t nodes) +{ + uint32_t old_placement_mask = make_bit_range(0, nodes); + uint32_t new_placement_mask = make_bit_range(crashed_nodes, nodes); + return CalculateMovedDocsRatio(nodes, redundancy, old_placement_mask, new_placement_mask, new_placement_mask); + +} + +CalculateMovedDocsRatio +CalculateMovedDocsRatio::make_replace_calculator(uint32_t redundancy, uint32_t added_nodes, uint32_t retired_nodes, uint32_t nodes) +{ + uint32_t old_placement_mask = make_bit_range(added_nodes, nodes); + uint32_t new_placement_mask = make_bit_range(added_nodes + retired_nodes, nodes) | make_bit_range(0, added_nodes); + uint32_t new_up_mask = make_bit_range(0, nodes); + return CalculateMovedDocsRatio(nodes, redundancy, old_placement_mask, new_placement_mask, new_up_mask); +} + +void +CalculateMovedDocsRatio::scan(Placements selected, Placements old_placement, Placements new_placement) +{ + if (old_placement._count >= _old_redundancy) { + if ((old_placement._mask & _new_up_mask) == 0) { + _lost_docs_base += _num_states[selected._count]; + _checked_states += _num_states[selected._count]; + return; + } + if (new_placement._count >= _new_redundancy) { + _checked_states += _num_states[selected._count]; + uint32_t only_new_mask = new_placement._mask & ~old_placement._mask; + if (only_new_mask != 0) { + _moved_docs += _num_states[selected._count] * (uint32_t)__builtin_popcount(only_new_mask); + for (uint32_t node_idx = 0; node_idx < _nodes; ++node_idx) { + if ((only_new_mask & (1u << node_idx)) != 0) { + _moved_docs_per_node[node_idx] += _num_states[selected._count]; + } + } + } + return; + } + } + assert(selected._count < _nodes); + for (uint32_t node_idx = 0; node_idx < _nodes; ++node_idx) { + if ((selected._mask & (1u << node_idx)) != 0) { + continue; + } + scan(selected.add(node_idx), old_placement.add(node_idx, _old_placement_mask, _old_redundancy), new_placement.add(node_idx, _new_placement_mask, _new_redundancy)); + } +} + +void +CalculateMovedDocsRatio::scan() +{ + scan(Placements(), Placements(), Placements()); + assert(_checked_states == _num_states[0]); +} + +} diff --git a/searchcore/src/vespa/searchcore/bmcluster/calculate_moved_docs_ratio.h b/searchcore/src/vespa/searchcore/bmcluster/calculate_moved_docs_ratio.h new file mode 100644 index 00000000000..cd161177246 --- /dev/null +++ b/searchcore/src/vespa/searchcore/bmcluster/calculate_moved_docs_ratio.h @@ -0,0 +1,48 @@ +// Copyright Yahoo. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. + +#pragma once + +#include <cstdint> +#include <vector> + +namespace search::bmcluster { + +/* + * Class for calculating moved docs ratio during + * document redistribution. + */ +class CalculateMovedDocsRatio +{ + class Placements; + std::vector<uint32_t> _num_states; + uint32_t _nodes; + uint32_t _old_placement_mask; + uint32_t _new_placement_mask; + uint32_t _new_up_mask; + uint32_t _moved_docs; + std::vector<uint32_t> _moved_docs_per_node; + uint32_t _checked_states; + uint32_t _lost_docs_base; + uint32_t _redundancy; + uint32_t _old_redundancy; + uint32_t _new_redundancy; + + void scan(Placements selected, Placements old_placement, Placements new_placement); +public: + CalculateMovedDocsRatio(uint32_t nodes, uint32_t redundancy, uint32_t old_placement_mask, uint32_t new_placement_mask, uint32_t new_up_mask); + ~CalculateMovedDocsRatio(); + static CalculateMovedDocsRatio make_grow_calculator(uint32_t redundancy, uint32_t added_nodes, uint32_t nodes); + static CalculateMovedDocsRatio make_shrink_calculator(uint32_t redundancy, uint32_t retired_nodes, uint32_t nodes); + static CalculateMovedDocsRatio make_crash_calculator(uint32_t redundancy, uint32_t crashed_nodes, uint32_t nodes); + static CalculateMovedDocsRatio make_replace_calculator(uint32_t redundancy, uint32_t added_nodes, uint32_t retired_nodes, uint32_t nodes); + void scan(); + uint32_t get_lost_docs_base() const noexcept { return _lost_docs_base; } + uint32_t get_checked_states() const noexcept { return _checked_states; } + uint32_t get_new_redundancy() const noexcept { return _new_redundancy; } + uint32_t get_moved_docs() const noexcept { return _moved_docs; } + const std::vector<uint32_t>& get_moved_docs_per_node() const noexcept { return _moved_docs_per_node; } + double get_lost_docs_base_ratio() const noexcept { return ((double) _lost_docs_base) / _checked_states; } + double get_moved_docs_ratio() const noexcept { return ((double) _moved_docs) / _checked_states; } +}; + +} diff --git a/searchcore/src/vespa/searchcore/bmcluster/estimate_moved_docs_ratio.cpp b/searchcore/src/vespa/searchcore/bmcluster/estimate_moved_docs_ratio.cpp new file mode 100644 index 00000000000..cffa6fc79e9 --- /dev/null +++ b/searchcore/src/vespa/searchcore/bmcluster/estimate_moved_docs_ratio.cpp @@ -0,0 +1,114 @@ +// Copyright Yahoo. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. + +#include "estimate_moved_docs_ratio.h" + +#include <vespa/log/log.h> +LOG_SETUP(".bmcluster.estimate_moved_docs_ratio"); + +namespace search::bmcluster { + +EstimateMovedDocsRatio::EstimateMovedDocsRatio() + : EstimateMovedDocsRatio(false) +{ +} + +EstimateMovedDocsRatio::EstimateMovedDocsRatio(bool verbose) + : _verbose(verbose) +{ +} + +double +EstimateMovedDocsRatio::estimate_lost_docs_base_ratio(uint32_t redundancy, uint32_t lost_nodes, uint32_t num_nodes) +{ + if (redundancy > lost_nodes) { + return 0.0; + } + double loss_ratio = 1.0; + for (uint32_t i = 0; i < redundancy; ++i) { + loss_ratio *= ((double) (lost_nodes - i)) / (num_nodes - i); + } + if (_verbose) { + LOG(info, "estimated lost docs base ratio: %4.2f", loss_ratio); + } + return loss_ratio; +} + +double +EstimateMovedDocsRatio::estimate_moved_docs_ratio_grow(uint32_t redundancy, uint32_t added_nodes, uint32_t num_nodes) +{ + if (added_nodes == num_nodes) { + return 0.0; + } + double new_redundancy = redundancy; + double new_per_node_doc_ratio = new_redundancy / num_nodes; + double moved_ratio = new_per_node_doc_ratio * added_nodes; + if (_verbose) { + LOG(info, "estimated_moved_docs_ratio_grow(%u,%u,%u)=%4.2f", redundancy, added_nodes, num_nodes, moved_ratio); + } + return moved_ratio; +} + +double +EstimateMovedDocsRatio::estimate_moved_docs_ratio_shrink(uint32_t redundancy, uint32_t retired_nodes, uint32_t num_nodes) +{ + if (retired_nodes == num_nodes) { + return 0.0; + } + double old_redundancy = redundancy; + double old_per_node_doc_ratio = old_redundancy / num_nodes; + uint32_t new_nodes = num_nodes - retired_nodes; + double new_redundancy = std::min(redundancy, new_nodes); + double new_per_node_doc_ratio = new_redundancy / new_nodes; + double moved_ratio = (new_per_node_doc_ratio - old_per_node_doc_ratio) * new_nodes; + if (_verbose) { + LOG(info, "estimated_moved_docs_ratio_shrink(%u,%u,%u)=%4.2f", redundancy, retired_nodes, num_nodes, moved_ratio); + } + return moved_ratio; +} + +double +EstimateMovedDocsRatio::estimate_moved_docs_ratio_crash(uint32_t redundancy, uint32_t crashed_nodes, uint32_t num_nodes) +{ + if (crashed_nodes == num_nodes) { + return 0.0; + } + double old_redundancy = redundancy; + double old_per_node_doc_ratio = old_redundancy / num_nodes; + uint32_t new_nodes = num_nodes - crashed_nodes; + double new_redundancy = std::min(redundancy, new_nodes); + double new_per_node_doc_ratio = new_redundancy / new_nodes; + double lost_docs_ratio = estimate_lost_docs_base_ratio(redundancy, crashed_nodes, num_nodes) * new_redundancy; + double moved_ratio = (new_per_node_doc_ratio - old_per_node_doc_ratio) * new_nodes - lost_docs_ratio; + if (_verbose) { + LOG(info, "estimated_moved_docs_ratio_crash(%u,%u,%u)=%4.2f", redundancy, crashed_nodes, num_nodes, moved_ratio); + } + return moved_ratio; +} + +double +EstimateMovedDocsRatio::estimate_moved_docs_ratio_replace(uint32_t redundancy, uint32_t added_nodes, uint32_t retired_nodes, uint32_t num_nodes) +{ + if (added_nodes == num_nodes || retired_nodes == num_nodes) { + return 0.0; + } + uint32_t old_nodes = num_nodes - added_nodes; + double old_redundancy = std::min(redundancy, old_nodes); + [[maybe_unused]] double old_per_node_doc_ratio = old_redundancy / old_nodes; + uint32_t new_nodes = num_nodes - retired_nodes; + double new_redundancy = std::min(redundancy, new_nodes); + double new_per_node_doc_ratio = new_redundancy / new_nodes; + double moved_ratio = new_per_node_doc_ratio * added_nodes; + uint32_t stable_nodes = num_nodes - added_nodes - retired_nodes; + // Account for extra documents moved from retired nodes to stable nodes + // TODO: Fix calculation + double baseline_per_node_doc_ratio = ((double) redundancy) / num_nodes; + double extra_per_stable_node_doc_ratio = std::min(baseline_per_node_doc_ratio * retired_nodes / new_nodes, 1.0 - old_per_node_doc_ratio); + double extra_moved_ratio = extra_per_stable_node_doc_ratio * stable_nodes; + moved_ratio += extra_moved_ratio; + if (_verbose) { + LOG(info, "estimated_moved_docs_ratio_replace(%u,%u,%u,%u)=%4.2f, (of which %4.2f extra)", redundancy, added_nodes, retired_nodes, num_nodes, moved_ratio, extra_moved_ratio); + } + return moved_ratio; +} + +} diff --git a/searchcore/src/vespa/searchcore/bmcluster/estimate_moved_docs_ratio.h b/searchcore/src/vespa/searchcore/bmcluster/estimate_moved_docs_ratio.h new file mode 100644 index 00000000000..fb14e80098d --- /dev/null +++ b/searchcore/src/vespa/searchcore/bmcluster/estimate_moved_docs_ratio.h @@ -0,0 +1,25 @@ +// Copyright Yahoo. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. + +#pragma once + +#include <cstdint> + +namespace search::bmcluster { + +/* + * Class for estimating moved docs ratio during + * document redistribution. + */ +class EstimateMovedDocsRatio { + bool _verbose; +public: + EstimateMovedDocsRatio(); + explicit EstimateMovedDocsRatio(bool verbose); + double estimate_lost_docs_base_ratio(uint32_t redundancy, uint32_t lost_nodes, uint32_t num_nodes); + double estimate_moved_docs_ratio_grow(uint32_t redundancy, uint32_t added_nodes, uint32_t num_nodes); + double estimate_moved_docs_ratio_shrink(uint32_t redundancy, uint32_t retired_nodes, uint32_t num_nodes); + double estimate_moved_docs_ratio_crash(uint32_t redundancy, uint32_t crashed_nodes, uint32_t num_nodes); + double estimate_moved_docs_ratio_replace(uint32_t redundancy, uint32_t added_nodes, uint32_t retired_nodes, uint32_t num_nodes); +}; + +} |