From 2c49a73a91cadd788b987671939f60f292bf693f Mon Sep 17 00:00:00 2001 From: Jess Balint Date: Fri, 22 Apr 2022 17:40:40 +0000 Subject: SERVER-61018 Create a generic histogram type (cherry picked from commit 3d65993807a72ce07aa54fe257887561ebb63809) --- jstests/sharding/resharding_histogram_metrics.js | 8 +- src/mongo/db/s/resharding/resharding_metrics.cpp | 31 ++-- src/mongo/db/s/resharding/resharding_metrics.h | 9 +- .../db/s/resharding/resharding_metrics_test.cpp | 6 +- src/mongo/util/SConscript | 2 +- src/mongo/util/histogram.h | 187 +++++++++++++++++++++ src/mongo/util/histogram_test.cpp | 169 +++++++++++++++++++ src/mongo/util/integer_histogram.h | 119 ------------- src/mongo/util/integer_histogram_test.cpp | 169 ------------------- 9 files changed, 382 insertions(+), 318 deletions(-) create mode 100644 src/mongo/util/histogram.h create mode 100644 src/mongo/util/histogram_test.cpp delete mode 100644 src/mongo/util/integer_histogram.h delete mode 100644 src/mongo/util/integer_histogram_test.cpp diff --git a/jstests/sharding/resharding_histogram_metrics.js b/jstests/sharding/resharding_histogram_metrics.js index 2f93ac17ca1..8f563cb7832 100644 --- a/jstests/sharding/resharding_histogram_metrics.js +++ b/jstests/sharding/resharding_histogram_metrics.js @@ -123,12 +123,12 @@ reshardingTest.withReshardingInBackground( // We expect 1 batch insert per document on each shard, plus 1 empty batch // to discover no documents are left. const expectedBatchInserts = reshardingMetrics[kDocumentsCopied] + 1; - const receivedBatchInserts = collClonerFillBatchForInsertHist["ops"]; + const receivedBatchInserts = collClonerFillBatchForInsertHist["totalCount"]; assert(expectedBatchInserts == receivedBatchInserts, `expected ${expectedBatchInserts} batch inserts, received ${receivedBatchInserts}`); - firstReshardBatchApplies += oplogApplierApplyBatchHist["ops"]; + firstReshardBatchApplies += oplogApplierApplyBatchHist["totalCount"]; }); assert(firstReshardBatchApplies > 0, @@ -175,8 +175,8 @@ recipientShardNames.forEach(function(shardName) { const collClonerFillBatchForInsertHist = reshardingMetrics[kCollClonerFillBatchForInsertLatencyMillis]; - cumulativeBatchApplies += oplogApplierApplyBatchHist["ops"]; - cumulativeBatchInserts += collClonerFillBatchForInsertHist["ops"]; + cumulativeBatchApplies += oplogApplierApplyBatchHist["totalCount"]; + cumulativeBatchInserts += collClonerFillBatchForInsertHist["totalCount"]; totalDocumentsCopied += reshardingMetrics[kDocumentsCopied]; }); diff --git a/src/mongo/db/s/resharding/resharding_metrics.cpp b/src/mongo/db/s/resharding/resharding_metrics.cpp index 31a454cf3c3..2f7f99f186b 100644 --- a/src/mongo/db/s/resharding/resharding_metrics.cpp +++ b/src/mongo/db/s/resharding/resharding_metrics.cpp @@ -36,7 +36,7 @@ #include "mongo/logv2/log.h" #include "mongo/platform/compiler.h" #include "mongo/util/duration.h" -#include "mongo/util/integer_histogram.h" +#include "mongo/util/histogram.h" #include "mongo/util/with_alignment.h" namespace mongo { @@ -96,13 +96,6 @@ Milliseconds remainingTime(Milliseconds elapsedTime, double elapsedWork, double return Milliseconds(Milliseconds::rep(remainingMsec)); } -void appendHistogram(BSONObjBuilder* bob, - const IntegerHistogram& hist) { - BSONObjBuilder histogramBuilder; - hist.append(histogramBuilder, false); - bob->appendElements(histogramBuilder.obj()); -} - static StringData serializeState(boost::optional e) { return RecipientState_serializer(*e); } @@ -230,12 +223,8 @@ public: int64_t chunkImbalanceCount = 0; - IntegerHistogram oplogApplierApplyBatchLatencyMillis = - IntegerHistogram(kOplogApplierApplyBatchLatencyMillis, - latencyHistogramBuckets); - IntegerHistogram collClonerFillBatchForInsertLatencyMillis = - IntegerHistogram(kCollClonerFillBatchForInsertLatencyMillis, - latencyHistogramBuckets); + Histogram oplogApplierApplyBatchLatencyMillis = getLatencyHistogram(); + Histogram collClonerFillBatchForInsertLatencyMillis = getLatencyHistogram(); // The ops done by resharding to keep up with the client writes. ReshardingOpCounters opCounters; @@ -319,8 +308,11 @@ void ReshardingMetrics::OperationMetrics::appendCurrentOpMetrics(BSONObjBuilder* serializeState(recipientState.get_value_or(RecipientStateEnum::kUnused))); bob->append(kOpStatus, ReshardingOperationStatus_serializer(opStatus)); - appendHistogram(bob, oplogApplierApplyBatchLatencyMillis); - appendHistogram(bob, collClonerFillBatchForInsertLatencyMillis); + appendHistogram( + *bob, oplogApplierApplyBatchLatencyMillis, kOplogApplierApplyBatchLatencyMillis); + appendHistogram(*bob, + collClonerFillBatchForInsertLatencyMillis, + kCollClonerFillBatchForInsertLatencyMillis); break; case Role::kCoordinator: bob->append(kCoordinatorState, serializeState(coordinatorState)); @@ -784,8 +776,11 @@ void ReshardingMetrics::serializeCumulativeOpMetrics(BSONObjBuilder* bob) const bob->append(kMaxRemainingOperationTime, getRemainingOperationTime(ops.maxRemainingOperationTime)); - appendHistogram(bob, ops.oplogApplierApplyBatchLatencyMillis); - appendHistogram(bob, ops.collClonerFillBatchForInsertLatencyMillis); + appendHistogram( + *bob, ops.oplogApplierApplyBatchLatencyMillis, kOplogApplierApplyBatchLatencyMillis); + appendHistogram(*bob, + ops.collClonerFillBatchForInsertLatencyMillis, + kCollClonerFillBatchForInsertLatencyMillis); } Date_t ReshardingMetrics::_now() const { diff --git a/src/mongo/db/s/resharding/resharding_metrics.h b/src/mongo/db/s/resharding/resharding_metrics.h index 480dd25ed8a..a92ba12ca5d 100644 --- a/src/mongo/db/s/resharding/resharding_metrics.h +++ b/src/mongo/db/s/resharding/resharding_metrics.h @@ -40,14 +40,11 @@ #include "mongo/s/resharding/common_types_gen.h" #include "mongo/util/clock_source.h" #include "mongo/util/duration.h" +#include "mongo/util/histogram.h" #include "mongo/util/uuid.h" namespace mongo { -static const size_t kLatencyHistogramBucketsCount = 5; -static const std::array latencyHistogramBuckets = { - 0, 11, 101, 1001, 10001}; - /* * Maintains the metrics for resharding operations. * All members of this class are thread-safe. @@ -172,6 +169,10 @@ public: // Reports the estimated remaining time for the active resharding operation, or `boost::none`. boost::optional getOperationRemainingTime() const; + static Histogram getLatencyHistogram() { + return Histogram({10, 100, 1000, 10000}); + } + private: class OperationMetrics; diff --git a/src/mongo/db/s/resharding/resharding_metrics_test.cpp b/src/mongo/db/s/resharding/resharding_metrics_test.cpp index 3f8d5545c29..025047d4198 100644 --- a/src/mongo/db/s/resharding/resharding_metrics_test.cpp +++ b/src/mongo/db/s/resharding/resharding_metrics_test.cpp @@ -40,7 +40,7 @@ #include "mongo/unittest/unittest.h" #include "mongo/util/clock_source_mock.h" #include "mongo/util/duration.h" -#include "mongo/util/integer_histogram.h" +#include "mongo/util/histogram.h" #include "mongo/util/uuid.h" namespace mongo { @@ -134,13 +134,13 @@ public: void appendExpectedHistogramResult(BSONObjBuilder* bob, std::string tag, const std::vector& latencies) { - IntegerHistogram hist(tag, latencyHistogramBuckets); + Histogram hist = ReshardingMetrics::getLatencyHistogram(); for (size_t i = 0; i < latencies.size(); i++) { hist.increment(latencies[i]); } BSONObjBuilder histogramBuilder; - hist.append(histogramBuilder, false); + appendHistogram(histogramBuilder, hist, tag); BSONObj histogram = histogramBuilder.obj(); bob->appendElements(histogram); } diff --git a/src/mongo/util/SConscript b/src/mongo/util/SConscript index 9bf11a149e3..3b87b12e024 100644 --- a/src/mongo/util/SConscript +++ b/src/mongo/util/SConscript @@ -669,7 +669,7 @@ icuEnv.CppUnitTest( 'future_test_promise_void.cpp', 'future_test_shared_future.cpp', 'future_util_test.cpp', - 'integer_histogram_test.cpp', + 'histogram_test.cpp', 'hierarchical_acquisition_test.cpp', 'icu_test.cpp', 'static_immortal_test.cpp', diff --git a/src/mongo/util/histogram.h b/src/mongo/util/histogram.h new file mode 100644 index 00000000000..0a07c82d9bc --- /dev/null +++ b/src/mongo/util/histogram.h @@ -0,0 +1,187 @@ +/** + * Copyright (C) 2022-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 + * . + * + * 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 +#include +#include +#include + +#include "mongo/bson/bsonobjbuilder.h" +#include "mongo/db/commands.h" +#include "mongo/platform/atomic_word.h" +#include "mongo/util/assert_util.h" + +namespace mongo { + +/** + * Generic histogram that supports data collection into intervals based on user-specified partitions + * over any continuous type. A binary predicate that establishes a strict weak ordering over the + * template parameter type `T` may be specified, otherwise `std::less` is used. (read + * more here: https://en.cppreference.com/w/cpp/named_req/Compare). + * + * For some provided lowermost partition x and uppermost partition y, a value z will be counted + * in the (-inf, x) interval if z < x, and in the [y, inf) interval if z >= y. If no partitions are + * provided, z will be counted in the sole (-inf, inf) interval. + */ +template > +class Histogram { + struct AtEnd {}; + +public: + explicit Histogram(std::vector partitions, Cmp comparator = {}) + : _partitions{std::move(partitions)}, + _counts(_partitions.size() + 1), + _comparator{std::move(comparator)} { + + auto ordered = + std::adjacent_find(_partitions.begin(), _partitions.end(), [&](const T& a, const T& b) { + return !_comparator(a, b); + }) == _partitions.end(); + if (!ordered) { + iasserted(6101800, "Partitions must be strictly monotonically increasing"); + } + } + + void increment(const T& data) { + auto i = std::upper_bound(_partitions.begin(), _partitions.end(), data, _comparator) - + _partitions.begin(); + + _counts[i].addAndFetch(1); + } + + const std::vector& getPartitions() const { + return _partitions; + } + + std::vector getCounts() const { + std::vector r(_counts.size()); + std::transform( + _counts.begin(), _counts.end(), r.begin(), [](auto&& x) { return x.load(); }); + return r; + } + + /** + * An input iterator over the Histogram class that provides access to histogram buckets, each + * containing the count, lower and upper bound values. The `lower` data member set to nullptr + * signifies the lowermost extremity of the distribution. nullptr similarly represents the + * uppermost extremity when assigned to the `upper` data member. + */ + class iterator { + public: + struct Bucket { + int64_t count; + const T* lower; + const T* upper; + }; + + using difference_type = void; + using value_type = Bucket; + using pointer = const Bucket*; + using reference = const Bucket&; + using iterator_category = std::input_iterator_tag; + + explicit iterator(const Histogram* hist) : _h{hist}, _pos{0} {} + iterator(const Histogram* hist, AtEnd) : _h{hist}, _pos{_h->_counts.size()} {} + + reference operator*() const { + _b.count = _h->_counts[_pos].load(); + _b.lower = (_pos == 0) ? nullptr : &_h->_partitions[_pos - 1]; + _b.upper = (_pos == _h->_counts.size() - 1) ? nullptr : &_h->_partitions[_pos]; + return _b; + } + + pointer operator->() const { + return &**this; + } + + iterator& operator++() { + ++_pos; + return *this; + } + + iterator operator++(int) { + iterator orig = *this; + ++*this; + return orig; + } + + friend bool operator==(const iterator& a, const iterator& b) { + return a._pos == b._pos; + } + + friend bool operator!=(const iterator& a, const iterator& b) { + return !(a == b); + } + + private: + const Histogram* _h; + size_t _pos; // position into _h->_counts + mutable Bucket _b; + }; + + iterator begin() const { + return iterator(this); + } + + iterator end() const { + return iterator(this, AtEnd{}); + } + +private: + std::vector _partitions; + std::vector> _counts; + Cmp _comparator; +}; + +/** + * Appends data (i.e. count and lower/upper bounds of all buckets) of a histogram to the provided + * BSON object builder. `histKey` is used as the field name for the appended BSON object containing + * the data. + */ +template +void appendHistogram(BSONObjBuilder& bob, const Histogram& hist, const StringData histKey) { + BSONObjBuilder histBob(bob.subobjStart(histKey)); + long long totalCount = 0; + + using namespace fmt::literals; + for (auto&& [count, lower, upper] : hist) { + std::string bucketKey = "{}{}, {})"_format(lower ? "[" : "(", + lower ? "{}"_format(*lower) : "-inf", + upper ? "{}"_format(*upper) : "inf"); + + BSONObjBuilder(histBob.subobjStart(bucketKey)) + .append("count", static_cast(count)); + totalCount += count; + } + histBob.append("totalCount", totalCount); +} + +} // namespace mongo diff --git a/src/mongo/util/histogram_test.cpp b/src/mongo/util/histogram_test.cpp new file mode 100644 index 00000000000..2e883335b6a --- /dev/null +++ b/src/mongo/util/histogram_test.cpp @@ -0,0 +1,169 @@ +/** + * Copyright (C) 2022-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 + * . + * + * 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/util/histogram.h" + +#include + +#include "mongo/unittest/assert_that.h" +#include "mongo/unittest/unittest.h" + +namespace mongo { + +namespace { + +using namespace unittest::match; +using namespace std::literals; + +class HistogramTest : public unittest::Test { +public: + template + struct BucketSpec { + int64_t count; + boost::optional lower, upper; + + friend bool operator==(const BucketSpec& a, const BucketSpec& b) { + auto lens = [](auto&& x) { return std::tie(x.count, x.lower, x.upper); }; + return lens(a) == lens(b); + } + + friend std::ostream& operator<<(std::ostream& os, const BucketSpec& b) { + os << "count: " << b.count; + if (b.lower) + os << ", lower: " << *b.lower; + if (b.upper) + os << ", upper: " << *b.upper; + return os; + } + }; + + template + boost::optional ptrToOpt(const T* p) { + return p ? boost::optional(*p) : boost::none; + } + + template + auto snapshot(const Histogram& h) { + std::vector> r; + std::transform(h.begin(), h.end(), std::back_inserter(r), [&](auto&& b) { + return BucketSpec{b.count, ptrToOpt(b.lower), ptrToOpt(b.upper)}; + }); + return r; + } +}; + +TEST_F(HistogramTest, CountsIncrementedAndStored) { + Histogram hist({0, 5, 8, 12}); + for (int64_t i = 0; i < 15; ++i) + hist.increment(i); + std::vector> expected = { + {0, {}, 0}, {5, 0, 5}, {3, 5, 8}, {4, 8, 12}, {3, 12, {}}}; + + ASSERT_THAT(snapshot(hist), Eq(expected)); +} + +TEST_F(HistogramTest, CountsIncrementedInSmallestBucket) { + Histogram hist({5, 8, 12}); + for (int64_t i = 0; i < 5; ++i) + hist.increment(i); + std::vector> expected = {{5, {}, 5}, {0, 5, 8}, {0, 8, 12}, {0, 12, {}}}; + + ASSERT_THAT(snapshot(hist), Eq(expected)); +} + +TEST_F(HistogramTest, CountsIncrementedAtPartition) { + std::vector origPartitions = {5, 8, 12}; + Histogram hist(origPartitions); + for (auto& p : origPartitions) + hist.increment(p); + std::vector> expected = {{0, {}, 5}, {1, 5, 8}, {1, 8, 12}, {1, 12, {}}}; + + ASSERT_THAT(snapshot(hist), Eq(expected)); +} + +TEST_F(HistogramTest, NegativeValuesIncrementBuckets) { + Histogram hist({-12, -8, 5}); + for (int64_t i = -15; i < 10; ++i) + hist.increment(i); + std::vector> expected = { + {3, {}, -12}, {4, -12, -8}, {13, -8, 5}, {5, 5, {}}}; + + ASSERT_THAT(snapshot(hist), Eq(expected)); +} + +TEST_F(HistogramTest, DurationCountsIncrementedAndStored) { + Histogram hist( + {Milliseconds{0}, Milliseconds{5}, Milliseconds{8}, Milliseconds{12}}); + for (int64_t i = 0; i < 15; ++i) + hist.increment(Milliseconds{i}); + std::vector> expected = {{0, {}, Milliseconds{0}}, + {5, Milliseconds{0}, Milliseconds{5}}, + {3, Milliseconds{5}, Milliseconds{8}}, + {4, Milliseconds{8}, Milliseconds{12}}, + {3, Milliseconds{12}, {}}}; + + ASSERT_THAT(snapshot(hist), Eq(expected)); +} + +TEST_F(HistogramTest, StringCountsIncrementedAndStoredByLength) { + Histogram hist({"", "aa", "aaaaa", "aaaaaaaaa"}); + for (int64_t i = 0; i < 12; ++i) + hist.increment(std::string(i, 'a')); + std::vector> expected = {{0, {}, ""s}, + {2, ""s, "aa"s}, + {3, "aa"s, "aaaaa"s}, + {4, "aaaaa"s, "aaaaaaaaa"s}, + {3, "aaaaaaaaa"s, {}}}; + + ASSERT_THAT(snapshot(hist), Eq(expected)); +} + +TEST_F(HistogramTest, StringCountsIncrementedAndStoredByChar) { + Histogram hist({"a", "h", "r", "z"}); + for (char c = 'a'; c < 'a' + 25; ++c) { + hist.increment(std::string{c}); + } + std::vector> expected = { + {0, {}, "a"s}, {7, "a"s, "h"s}, {10, "h"s, "r"s}, {8, "r"s, "z"s}, {0, "z"s, {}}}; + + ASSERT_THAT(snapshot(hist), Eq(expected)); +} + +TEST_F(HistogramTest, SizeTCountsIncrementedAndStored) { + Histogram hist({0, 5, 8, 12}); + for (size_t i = 0; i < 15; ++i) + hist.increment(i); + std::vector> expected = { + {0, {}, 0}, {5, 0, 5}, {3, 5, 8}, {4, 8, 12}, {3, 12, {}}}; + + ASSERT_THAT(snapshot(hist), Eq(expected)); +} + +} // namespace +} // namespace mongo diff --git a/src/mongo/util/integer_histogram.h b/src/mongo/util/integer_histogram.h deleted file mode 100644 index cab7447c26e..00000000000 --- a/src/mongo/util/integer_histogram.h +++ /dev/null @@ -1,119 +0,0 @@ -/** - * Copyright (C) 2021-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 - * . - * - * 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 "mongo/bson/bsonobjbuilder.h" -#include "mongo/db/commands.h" -#include - -namespace mongo { - -/** - * Generalized version of OperationLatencyHistogram that can track latencies for any operation type - * with custom lower bounds. For some provided lower bounds {x,y} a number z will be counted in the - * x-y bucket if z ∈ [x, y). in the y-inf bucket if z ∈ [y, inf). and in the (-inf, x) bucket if z < - * x. - */ -template -class IntegerHistogram { -public: - const std::string kKey; - - IntegerHistogram(std::string key, std::array lowerBounds) - : kKey(std::move(key)) { - invariant(!lowerBounds.empty(), "Lower bounds must not be empty"); - _lowerBoundBuckets[0].lowerBound = std::numeric_limits::min(); - int64_t prevVal = std::numeric_limits::min(); - for (size_t i = 1; i < _lowerBoundBuckets.size(); ++i) { - auto lowerBoundVal = lowerBounds.at(i - 1); - invariant(lowerBoundVal > prevVal, - "Lower bounds must be strictly monotonically increasing"); - - _lowerBoundBuckets[i].lowerBound = lowerBoundVal; - prevVal = lowerBoundVal; - } - } - - void append(BSONObjBuilder& builder, bool shouldAppendAdditionalInfo) const { - BSONObjBuilder histogramBuilder(builder.subobjStart(kKey)); - auto offsetToString = [this](size_t offset) { - if (offset == 0) - return std::string("-inf"); - if (offset < _lowerBoundBuckets.size()) - return std::to_string(_lowerBoundBuckets[offset].lowerBound); - return std::string("inf"); - }; - - for (size_t i = 0; i < _lowerBoundBuckets.size(); i++) { - auto count = _lowerBoundBuckets[i].count.load(); - if (count == 0) - continue; - - auto key = fmt::format("{} - {}", offsetToString(i), offsetToString(i + 1)); - BSONObjBuilder entryBuilder(histogramBuilder.subobjStart(key)); - entryBuilder.append("count", (long long)(count)); - entryBuilder.doneFast(); - } - - auto totalCount = _entryCount.load(); - histogramBuilder.append("ops", (long long)totalCount); - if (shouldAppendAdditionalInfo && totalCount != 0) { - auto sum = _sum.load(); - histogramBuilder.append("sum", (long long)sum); - histogramBuilder.append("mean", static_cast(sum) / totalCount); - } - histogramBuilder.doneFast(); - } - - void increment(int64_t data) { - auto insertionIndex = std::upper_bound(_lowerBoundBuckets.begin(), - _lowerBoundBuckets.end(), - data, - [](const int64_t a, const LowerBoundBucket& b) { - return a < b.lowerBound; - }) - - 1; - - insertionIndex->count.addAndFetch(1); - _entryCount.addAndFetch(1); - _sum.addAndFetch(data); - } - -private: - struct LowerBoundBucket { - int64_t lowerBound; - AtomicWord count; - }; - - std::array _lowerBoundBuckets; - AtomicWord _entryCount; - AtomicWord _sum; -}; -} // namespace mongo diff --git a/src/mongo/util/integer_histogram_test.cpp b/src/mongo/util/integer_histogram_test.cpp deleted file mode 100644 index 1a615cb5078..00000000000 --- a/src/mongo/util/integer_histogram_test.cpp +++ /dev/null @@ -1,169 +0,0 @@ -/** - * Copyright (C) 2021-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 - * . - * - * 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/platform/basic.h" -#include "mongo/unittest/death_test.h" -#include "mongo/unittest/unittest.h" -#include "mongo/util/integer_histogram.h" - -namespace mongo { - -namespace { - -TEST(IntegerHistogram, EnsureCountsIncrementedAndStored) { - std::array lowerBounds{0, 5, 8, 12}; - IntegerHistogram<4> hist("testKey", lowerBounds); - int64_t sum = 0; - int64_t numInserts = 15; - for (int64_t i = 0; i < numInserts; i++) { - hist.increment(i); - sum += i; - } - - auto out = [&] { - BSONObjBuilder builder; - hist.append(builder, true); - return builder.obj(); - }(); - - auto buckets = out["testKey"]; - ASSERT_EQUALS(buckets["0 - 5"]["count"].Long(), 5); - ASSERT_EQUALS(buckets["5 - 8"]["count"].Long(), 3); - ASSERT_EQUALS(buckets["8 - 12"]["count"].Long(), 4); - ASSERT_EQUALS(buckets["12 - inf"]["count"].Long(), 3); - ASSERT_EQUALS(buckets["ops"].Long(), numInserts); - ASSERT_EQUALS(buckets["sum"].Long(), sum); - ASSERT_EQUALS(buckets["mean"].Double(), static_cast(sum) / numInserts); -} - -TEST(IntegerHistogram, EnsureCountsIncrementedInSmallestBucket) { - std::array lowerBounds{5, 8, 12}; - IntegerHistogram<3> hist("testKey2", lowerBounds); - int64_t sum = 0; - int64_t numInserts = 5; - for (int64_t i = 0; i < numInserts; i++) { - hist.increment(i); - sum += i; - } - - auto out = [&] { - BSONObjBuilder builder; - hist.append(builder, true); - return builder.obj(); - }(); - - auto buckets = out["testKey2"]; - ASSERT_EQUALS(buckets["-inf - 5"]["count"].Long(), 5); - ASSERT_EQUALS(buckets["ops"].Long(), numInserts); - ASSERT_EQUALS(buckets["sum"].Long(), sum); - ASSERT_EQUALS(buckets["mean"].Double(), static_cast(sum) / numInserts); -} - -TEST(IntegerHistogram, EnsureCountsCorrectlyIncrementedAtBoundary) { - std::array lowerBounds{5, 8, 12}; - IntegerHistogram<3> hist("testKey3", lowerBounds); - int64_t sum = 0; - int64_t numInserts = 3; - for (auto& boundary : lowerBounds) { - hist.increment(boundary); - sum += boundary; - } - - auto out = [&] { - BSONObjBuilder builder; - hist.append(builder, true); - return builder.obj(); - }(); - - auto buckets = out["testKey3"]; - ASSERT_EQUALS(buckets["5 - 8"]["count"].Long(), 1); - ASSERT_EQUALS(buckets["8 - 12"]["count"].Long(), 1); - ASSERT_EQUALS(buckets["12 - inf"]["count"].Long(), 1); - ASSERT_EQUALS(buckets["ops"].Long(), numInserts); - ASSERT_EQUALS(buckets["sum"].Long(), sum); - ASSERT_EQUALS(buckets["mean"].Double(), static_cast(sum) / numInserts); -} - -TEST(IntegerHistogram, EnsureNegativeCountsIncrementBucketsCorrectly) { - std::array lowerBounds{-12, -8, 5}; - IntegerHistogram<3> hist("testKey4", lowerBounds); - int64_t sum = 0; - int64_t numInserts = 25; - for (int64_t i = -15; i < 10; i++) { - hist.increment(i); - sum += i; - } - - auto out = [&] { - BSONObjBuilder builder; - hist.append(builder, true); - return builder.obj(); - }(); - - auto buckets = out["testKey4"]; - ASSERT_EQUALS(buckets["-inf - -12"]["count"].Long(), 3); - ASSERT_EQUALS(buckets["-12 - -8"]["count"].Long(), 4); - ASSERT_EQUALS(buckets["-8 - 5"]["count"].Long(), 13); - ASSERT_EQUALS(buckets["5 - inf"]["count"].Long(), 5); - ASSERT_EQUALS(buckets["ops"].Long(), numInserts); - ASSERT_EQUALS(buckets["sum"].Long(), sum); - ASSERT_EQUALS(buckets["mean"].Double(), static_cast(sum) / numInserts); -} - -TEST(IntegerHistogram, SkipsEmptyBuckets) { - std::array lowerBounds{0, 5}; - IntegerHistogram<2> hist("testKey6", lowerBounds); - hist.increment(6); - - auto out = [&] { - BSONObjBuilder builder; - hist.append(builder, true); - return builder.obj(); - }(); - - auto buckets = out["testKey6"]; - ASSERT_THROWS(buckets["0 - 5"]["count"].Long(), DBException); - ASSERT_EQ(buckets["5 - inf"]["count"].Long(), 1); -} - -DEATH_TEST(IntegerHistogram, - FailIfFirstLowerBoundIsMin, - "Lower bounds must be strictly monotonically increasing") { - std::array lowerBounds{std::numeric_limits::min(), 5}; - IntegerHistogram<2> hist("testKey5", lowerBounds); -} - -DEATH_TEST(IntegerHistogram, - FailsWhenLowerBoundNotMonotonic, - "Lower bounds must be strictly monotonically increasing") { - std::array lowerBounds{5, 0}; - IntegerHistogram<2>("testKey7", lowerBounds); -} -} // namespace -} // namespace mongo -- cgit v1.2.1