From f8ee418d0a89eceb7864e4f3e97886ea90b91967 Mon Sep 17 00:00:00 2001 From: auto-revert-processor Date: Thu, 24 Feb 2022 14:59:00 +0000 Subject: Revert "SERVER-61018 Create a generic histogram type" This reverts commit 1f1d912e1a65a66c6d0f7a0b4e4ec687007ecd44. --- 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, 318 insertions(+), 382 deletions(-) delete mode 100644 src/mongo/util/histogram.h delete mode 100644 src/mongo/util/histogram_test.cpp create mode 100644 src/mongo/util/integer_histogram.h create 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 2c06b081605..c474db95d96 100644 --- a/jstests/sharding/resharding_histogram_metrics.js +++ b/jstests/sharding/resharding_histogram_metrics.js @@ -122,12 +122,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["totalCount"]; + const receivedBatchInserts = collClonerFillBatchForInsertHist["ops"]; assert(expectedBatchInserts == receivedBatchInserts, `expected ${expectedBatchInserts} batch inserts, received ${receivedBatchInserts}`); - firstReshardBatchApplies += oplogApplierApplyBatchHist["totalCount"]; + firstReshardBatchApplies += oplogApplierApplyBatchHist["ops"]; }); assert(firstReshardBatchApplies > 0, @@ -174,8 +174,8 @@ recipientShardNames.forEach(function(shardName) { const collClonerFillBatchForInsertHist = reshardingMetrics[kCollClonerFillBatchForInsertLatencyMillis]; - cumulativeBatchApplies += oplogApplierApplyBatchHist["totalCount"]; - cumulativeBatchInserts += collClonerFillBatchForInsertHist["totalCount"]; + cumulativeBatchApplies += oplogApplierApplyBatchHist["ops"]; + cumulativeBatchInserts += collClonerFillBatchForInsertHist["ops"]; totalDocumentsCopied += reshardingMetrics[kDocumentsCopied]; }); diff --git a/src/mongo/db/s/resharding/resharding_metrics.cpp b/src/mongo/db/s/resharding/resharding_metrics.cpp index 6e4e4e041e9..ff7ba2490eb 100644 --- a/src/mongo/db/s/resharding/resharding_metrics.cpp +++ b/src/mongo/db/s/resharding/resharding_metrics.cpp @@ -37,7 +37,7 @@ #include "mongo/platform/compiler.h" #include "mongo/util/aligned.h" #include "mongo/util/duration.h" -#include "mongo/util/histogram.h" +#include "mongo/util/integer_histogram.h" namespace mongo { @@ -96,6 +96,13 @@ 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); } @@ -223,8 +230,12 @@ public: int64_t chunkImbalanceCount = 0; - Histogram oplogApplierApplyBatchLatencyMillis = getLatencyHistogram(); - Histogram collClonerFillBatchForInsertLatencyMillis = getLatencyHistogram(); + IntegerHistogram oplogApplierApplyBatchLatencyMillis = + IntegerHistogram(kOplogApplierApplyBatchLatencyMillis, + latencyHistogramBuckets); + IntegerHistogram collClonerFillBatchForInsertLatencyMillis = + IntegerHistogram(kCollClonerFillBatchForInsertLatencyMillis, + latencyHistogramBuckets); // The ops done by resharding to keep up with the client writes. ReshardingOpCounters opCounters; @@ -308,11 +319,8 @@ void ReshardingMetrics::OperationMetrics::appendCurrentOpMetrics(BSONObjBuilder* serializeState(recipientState.get_value_or(RecipientStateEnum::kUnused))); bob->append(kOpStatus, ReshardingOperationStatus_serializer(opStatus)); - appendHistogram( - *bob, oplogApplierApplyBatchLatencyMillis, kOplogApplierApplyBatchLatencyMillis); - appendHistogram(*bob, - collClonerFillBatchForInsertLatencyMillis, - kCollClonerFillBatchForInsertLatencyMillis); + appendHistogram(bob, oplogApplierApplyBatchLatencyMillis); + appendHistogram(bob, collClonerFillBatchForInsertLatencyMillis); break; case Role::kCoordinator: bob->append(kCoordinatorState, serializeState(coordinatorState)); @@ -782,11 +790,8 @@ void ReshardingMetrics::serializeCumulativeOpMetrics(BSONObjBuilder* bob) const bob->append(kMaxRemainingOperationTime, getRemainingOperationTime(ops.maxRemainingOperationTime)); - appendHistogram( - *bob, ops.oplogApplierApplyBatchLatencyMillis, kOplogApplierApplyBatchLatencyMillis); - appendHistogram(*bob, - ops.collClonerFillBatchForInsertLatencyMillis, - kCollClonerFillBatchForInsertLatencyMillis); + appendHistogram(bob, ops.oplogApplierApplyBatchLatencyMillis); + appendHistogram(bob, ops.collClonerFillBatchForInsertLatencyMillis); } 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 a6964c9d611..d60eea1177b 100644 --- a/src/mongo/db/s/resharding/resharding_metrics.h +++ b/src/mongo/db/s/resharding/resharding_metrics.h @@ -40,11 +40,14 @@ #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. @@ -171,10 +174,6 @@ 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 4546f227ba3..fdaf9d36739 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/histogram.h" +#include "mongo/util/integer_histogram.h" #include "mongo/util/uuid.h" namespace mongo { @@ -138,13 +138,13 @@ public: void appendExpectedHistogramResult(BSONObjBuilder* bob, std::string tag, const std::vector& latencies) { - Histogram hist = ReshardingMetrics::getLatencyHistogram(); + IntegerHistogram hist(tag, latencyHistogramBuckets); for (size_t i = 0; i < latencies.size(); i++) { hist.increment(latencies[i]); } BSONObjBuilder histogramBuilder; - appendHistogram(histogramBuilder, hist, tag); + hist.append(histogramBuilder, false); BSONObj histogram = histogramBuilder.obj(); bob->appendElements(histogram); } diff --git a/src/mongo/util/SConscript b/src/mongo/util/SConscript index e797a415281..3998716f7f4 100644 --- a/src/mongo/util/SConscript +++ b/src/mongo/util/SConscript @@ -695,7 +695,7 @@ icuEnv.CppUnitTest( 'future_test_promise_void.cpp', 'future_test_shared_future.cpp', 'future_util_test.cpp', - 'histogram_test.cpp', + 'integer_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 deleted file mode 100644 index 0a07c82d9bc..00000000000 --- a/src/mongo/util/histogram.h +++ /dev/null @@ -1,187 +0,0 @@ -/** - * 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 deleted file mode 100644 index 2e883335b6a..00000000000 --- a/src/mongo/util/histogram_test.cpp +++ /dev/null @@ -1,169 +0,0 @@ -/** - * 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 new file mode 100644 index 00000000000..cab7447c26e --- /dev/null +++ b/src/mongo/util/integer_histogram.h @@ -0,0 +1,119 @@ +/** + * 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 new file mode 100644 index 00000000000..1a615cb5078 --- /dev/null +++ b/src/mongo/util/integer_histogram_test.cpp @@ -0,0 +1,169 @@ +/** + * 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