diff options
| -rw-r--r-- | src/mongo/db/SConscript | 16 | ||||
| -rw-r--r-- | src/mongo/db/mirroring_sampler.cpp | 99 | ||||
| -rw-r--r-- | src/mongo/db/mirroring_sampler.h | 66 | ||||
| -rw-r--r-- | src/mongo/db/mirroring_sampler_test.cpp | 208 |
4 files changed, 389 insertions, 0 deletions
diff --git a/src/mongo/db/SConscript b/src/mongo/db/SConscript index b571f307f06..08e9800be1c 100644 --- a/src/mongo/db/SConscript +++ b/src/mongo/db/SConscript @@ -1773,6 +1773,19 @@ env.Library( ], ) +env.Library( + target='mirroring_sampler', + source=[ + 'mirroring_sampler.cpp', + ], + LIBDEPS=[ + "$BUILD_DIR/mongo/base", + "$BUILD_DIR/mongo/db/repl/replica_set_messages", + "$BUILD_DIR/mongo/rpc/protocol", + "$BUILD_DIR/mongo/util/net/network", + ], +) + envWithAsio = env.Clone() envWithAsio.InjectThirdParty(libraries=['asio']) @@ -1797,6 +1810,7 @@ envWithAsio.CppUnitTest( 'logical_session_cache_test.cpp', 'logical_session_id_test.cpp', 'logical_time_test.cpp', + 'mirroring_sampler_test.cpp', 'multi_key_path_tracker_test.cpp', 'namespace_string_test.cpp', 'op_observer_impl_test.cpp', @@ -1823,6 +1837,7 @@ envWithAsio.CppUnitTest( ], LIBDEPS=[ '$BUILD_DIR/mongo/base', + "$BUILD_DIR/mongo/bson/util/bson_extract", '$BUILD_DIR/mongo/client/read_preference', '$BUILD_DIR/mongo/db/auth/auth', '$BUILD_DIR/mongo/db/catalog/catalog_test_fixture', @@ -1859,6 +1874,7 @@ envWithAsio.CppUnitTest( 'logical_session_id', 'logical_session_id_helpers', 'logical_time', + 'mirroring_sampler', 'namespace_string', 'op_observer', 'op_observer_impl', diff --git a/src/mongo/db/mirroring_sampler.cpp b/src/mongo/db/mirroring_sampler.cpp new file mode 100644 index 00000000000..83afb2a19d2 --- /dev/null +++ b/src/mongo/db/mirroring_sampler.cpp @@ -0,0 +1,99 @@ +/** + * Copyright (C) 2020-present MongoDB, Inc. + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the Server Side Public License, version 1, + * as published by MongoDB, Inc. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * Server Side Public License for more details. + * + * You should have received a copy of the Server Side Public License + * along with this program. If not, see + * <http://www.mongodb.com/licensing/server-side-public-license>. + * + * As a special exception, the copyright holders give permission to link the + * code of portions of this program with the OpenSSL library under certain + * conditions as described in each individual source file and distribute + * linked combinations including the program with the OpenSSL library. You + * must comply with the Server Side Public License in all respects for + * all of the code used other than as permitted herein. If you modify file(s) + * with this exception, you may extend this exception to your version of the + * file(s), but you are not obligated to do so. If you do not wish to do so, + * delete this exception statement from your version. If you delete this + * exception statement from all source files in the program, then also delete + * it in the license file. + */ + +#include <cmath> +#include <cstdlib> + +#include "mongo/db/mirroring_sampler.h" + +namespace mongo { + +std::vector<HostAndPort> MirroringSampler::getMirroringTargets( + std::shared_ptr<const repl::IsMasterResponse> isMaster, + const double ratio, + RandomFunc rnd, + const int rndMax) noexcept { + + invariant(ratio >= 0 && ratio <= 1); + invariant(isMaster); + if (!isMaster->isMaster()) { + return {}; + } + + /** + * `ratio == 0` disables mirroring + * Also, mirroring requires at least one active secondary. + */ + if (ratio == 0 || isMaster->getHosts().size() < 2) { + return {}; + } + + /** + * The goal is to mirror every request to approximately `ratio x secondariesCount`. + */ + const auto secondariesCount = isMaster->getHosts().size() - 1; + const auto secondariesRatio = ratio * secondariesCount; + + // Mirroring factor is the number of secondaries that will receive the command. + auto mirroringFactor = std::ceil(secondariesRatio); + invariant(mirroringFactor > 0 && mirroringFactor <= secondariesCount); + + size_t randVar = rnd(); + const auto normalizedRatio = static_cast<size_t>(secondariesRatio * rndMax / mirroringFactor); + + if (randVar > normalizedRatio) { + return {}; + } + + auto getEligibleSecondaries = [](auto isMaster) noexcept->std::vector<HostAndPort> { + auto self = isMaster->getPrimary(); + auto hosts = isMaster->getHosts(); + invariant(hosts.size() > 1); + + std::vector<HostAndPort> potentialTargets; + for (auto host : hosts) { + if (host != self) { + potentialTargets.push_back(host); + } + } + + return potentialTargets; + }; + + auto eligibleSecondaries = getEligibleSecondaries(isMaster); + invariant(!eligibleSecondaries.empty()); + + std::mt19937 twisterEngine(randVar); + std::shuffle(eligibleSecondaries.begin(), eligibleSecondaries.end(), twisterEngine); + + auto it = eligibleSecondaries.begin(); + return std::vector<HostAndPort>(it, it + mirroringFactor); +} + +} // namespace mongo diff --git a/src/mongo/db/mirroring_sampler.h b/src/mongo/db/mirroring_sampler.h new file mode 100644 index 00000000000..cdda905692e --- /dev/null +++ b/src/mongo/db/mirroring_sampler.h @@ -0,0 +1,66 @@ +/** + * Copyright (C) 2020-present MongoDB, Inc. + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the Server Side Public License, version 1, + * as published by MongoDB, Inc. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * Server Side Public License for more details. + * + * You should have received a copy of the Server Side Public License + * along with this program. If not, see + * <http://www.mongodb.com/licensing/server-side-public-license>. + * + * As a special exception, the copyright holders give permission to link the + * code of portions of this program with the OpenSSL library under certain + * conditions as described in each individual source file and distribute + * linked combinations including the program with the OpenSSL library. You + * must comply with the Server Side Public License in all respects for + * all of the code used other than as permitted herein. If you modify file(s) + * with this exception, you may extend this exception to your version of the + * file(s), but you are not obligated to do so. If you do not wish to do so, + * delete this exception statement from your version. If you delete this + * exception statement from all source files in the program, then also delete + * it in the license file. + */ + +#pragma once + +#include <functional> +#include <memory> +#include <random> +#include <vector> + +#include "mongo/db/repl/is_master_response.h" +#include "mongo/util/net/hostandport.h" + +namespace mongo { + +/** + * Populates a random subset of eligible secondaries (using `IsMasterResponse` + * and a ratio) for mirroring. An empty subset for eligible secondaries indicates + * no mirroring is necessary/possible. + */ +class MirroringSampler final { +public: + using RandomFunc = std::function<int()>; + + /** + * Sampler function for mirroring commands to eligible secondaries. + * The caller must be the primary node of the replica-set. + * @arg isMaster replica-set topology that determines mirroring targets. + * @arg ratio the mirroring ratio (must be between 0 and 1 inclusive). + * @arg rnd the random generator function (default is `std::rand()`). + * @arg rndMax the maximum value that `rnd()` returns (default is `RAND_MAX`). + */ + static std::vector<HostAndPort> getMirroringTargets( + std::shared_ptr<const repl::IsMasterResponse> isMaster, + const double ratio, + RandomFunc rnd = std::rand, + const int rndMax = RAND_MAX) noexcept; +}; + +} // namespace mongo diff --git a/src/mongo/db/mirroring_sampler_test.cpp b/src/mongo/db/mirroring_sampler_test.cpp new file mode 100644 index 00000000000..d8ccff3d4d5 --- /dev/null +++ b/src/mongo/db/mirroring_sampler_test.cpp @@ -0,0 +1,208 @@ +/** + * Copyright (C) 2020-present MongoDB, Inc. + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the Server Side Public License, version 1, + * as published by MongoDB, Inc. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * Server Side Public License for more details. + * + * You should have received a copy of the Server Side Public License + * along with this program. If not, see + * <http://www.mongodb.com/licensing/server-side-public-license>. + * + * As a special exception, the copyright holders give permission to link the + * code of portions of this program with the OpenSSL library under certain + * conditions as described in each individual source file and distribute + * linked combinations including the program with the OpenSSL library. You + * must comply with the Server Side Public License in all respects for + * all of the code used other than as permitted herein. If you modify file(s) + * with this exception, you may extend this exception to your version of the + * file(s), but you are not obligated to do so. If you do not wish to do so, + * delete this exception statement from your version. If you delete this + * exception statement from all source files in the program, then also delete + * it in the license file. + */ + +#include "mongo/bson/util/bson_extract.h" +#include "mongo/db/mirroring_sampler.h" +#include "mongo/stdx/unordered_map.h" +#include "mongo/unittest/death_test.h" +#include "mongo/unittest/unittest.h" + +namespace mongo { + +DEATH_TEST(MirroringSamplerTest, ValidateNegativeRatio, "invariant") { + auto dummyIsMaster = std::make_shared<mongo::repl::IsMasterResponse>(); + MirroringSampler::getMirroringTargets(dummyIsMaster, -1); +} + +DEATH_TEST(MirroringSamplerTest, ValidateLargeRatio, "invariant") { + auto dummyIsMaster = std::make_shared<mongo::repl::IsMasterResponse>(); + MirroringSampler::getMirroringTargets(dummyIsMaster, 1.1); +} + +DEATH_TEST(MirroringSamplerTest, ValidateMissingIsMaster, "invariant") { + MirroringSampler::getMirroringTargets(nullptr, 1); +} + +TEST(MirroringSamplerTest, ValidateHostIsPrimary) { + auto isMaster = std::make_shared<mongo::repl::IsMasterResponse>(); + isMaster->setIsMaster(false); + + auto targets = MirroringSampler::getMirroringTargets(isMaster, 1); + ASSERT_EQ(targets.size(), 0); +} + +TEST(MirroringSamplerTest, NoEligibleSecondary) { + auto isMaster = std::make_shared<mongo::repl::IsMasterResponse>(); + isMaster->setIsMaster(true); + isMaster->setIsSecondary(false); + isMaster->addHost(mongo::HostAndPort("primary", 12345)); + isMaster->setPrimary(isMaster->getHosts()[0]); + isMaster->setMe(isMaster->getPrimary()); + + auto targets = MirroringSampler::getMirroringTargets(isMaster, 1.0); + ASSERT_EQ(targets.size(), 0); +} + +class MirroringSamplerFixture : public unittest::Test { +public: + void init(size_t secondariesCount) { + _isMaster = std::make_shared<mongo::repl::IsMasterResponse>(); + _isMaster->setIsMaster(true); + _isMaster->setIsSecondary(false); + for (size_t i = 0; i < secondariesCount + 1; i++) { + std::string hostName = "node-" + std::to_string(i); + _isMaster->addHost(mongo::HostAndPort(hostName, 12345)); + } + + _isMaster->setPrimary(_isMaster->getHosts()[0]); + _isMaster->setMe(_isMaster->getPrimary()); + + _hitCounts.clear(); + for (size_t i = 1; i < secondariesCount + 1; i++) { + _hitCounts[_isMaster->getHosts()[i].toString()] = 0; + } + } + + void resetPseudoRandomSeed() { + _pseudoRandomSeed = 0.0; + } + + int nextPseudoRandom() { + const auto stepSize = static_cast<double>(RAND_MAX) / repeats; + _pseudoRandomSeed += stepSize; + return static_cast<int>(_pseudoRandomSeed) % RAND_MAX; + } + + void resetHitCounts() { + for (auto pair : _hitCounts) { + _hitCounts[pair.first] = 0; + } + } + + void populteHitCounts(std::vector<HostAndPort>& targets) { + for (auto host : targets) { + auto it = _hitCounts.find(host.toString()); + invariant(it != _hitCounts.end()); + it->second++; + } + } + + size_t getHitCountsSum() { + return std::accumulate( + _hitCounts.begin(), + _hitCounts.end(), + 0, + [](int value, const std::pair<std::string, size_t>& p) { return value + p.second; }); + } + + double getHitCounsMean() { + return static_cast<double>(getHitCountsSum()) / _hitCounts.size(); + } + + double getHitCountsSTD() { + const auto mean = getHitCounsMean(); + double standardDeviation = 0.0; + for (auto pair : _hitCounts) { + standardDeviation += std::pow(pair.second - mean, 2); + } + + return std::sqrt(standardDeviation / _hitCounts.size()); + } + + auto getIsMaster() const { + return _isMaster; + } + + const size_t repeats = 100000; + +private: + std::shared_ptr<repl::IsMasterResponse> _isMaster; + + double _pseudoRandomSeed; + + stdx::unordered_map<std::string, size_t> _hitCounts; +}; + +TEST_F(MirroringSamplerFixture, SamplerFunction) { + + std::vector<size_t> secondariesCount = {1, 2, 3, 4, 5, 6, 7}; + std::vector<double> ratios = { + 0.01, 0.02, 0.05, 0.10, 0.15, 0.20, 0.25, 0.30, 0.40, 0.50, 0.60, 0.70, 0.80, 0.90}; + for (auto secondaryQ : secondariesCount) { + // Set number of secondaries + init(secondaryQ); + auto isMaster = getIsMaster(); + + for (auto ratio : ratios) { + resetPseudoRandomSeed(); + resetHitCounts(); + + auto pseudoRandomGen = [&]() -> int { return this->nextPseudoRandom(); }; + + for (size_t i = 0; i < repeats; i++) { + auto targets = + MirroringSampler::getMirroringTargets(isMaster, ratio, pseudoRandomGen); + populteHitCounts(targets); + } + + // The number of mirrored commands is at least 95% of the promise + const double observedMirroredCmds = getHitCountsSum(); + const double expectedMirroredCmds = repeats * ratio * secondaryQ; + ASSERT_GT(observedMirroredCmds / expectedMirroredCmds, 0.95); + + /** + * Relative standard deviation (a metric for distribution of mirrored + * commands among secondaries) must be less than 7%. + */ + const auto relativeSTD = getHitCountsSTD() / getHitCounsMean(); + ASSERT_LT(relativeSTD, 0.07); + } + } +} + +TEST_F(MirroringSamplerFixture, MirrorAll) { + std::vector<size_t> secondariesCount = {1, 2, 3, 4, 5, 6, 7}; + for (auto secondaryQ : secondariesCount) { + // Set number of secondaries + init(secondaryQ); + auto isMaster = getIsMaster(); + + for (size_t i = 0; i < repeats; i++) { + auto targets = MirroringSampler::getMirroringTargets(isMaster, 1.0); + populteHitCounts(targets); + } + + const double observedMirroredCmds = getHitCountsSum(); + const double expectedMirroredCmds = repeats * secondaryQ; + ASSERT_EQ(getHitCountsSTD(), 0); + ASSERT_EQ(observedMirroredCmds, expectedMirroredCmds); + } +} + +} // namespace mongo |