From bd6447c62a08f3025649803c570250a50c5065c4 Mon Sep 17 00:00:00 2001 From: Caren Thomas Date: Tue, 14 Jun 2016 17:52:36 -0700 Subject: [PATCH] Add constructor for MultiLevelTimeSeries class that uses initializer_list and add stat methods that uses duration as a parameter. Summary: Introduce a constructor that takes in an initializer list of 'TimeType' objects for the durations. New methods for sum/avg/rate/count/countrate are created with a 'TimeType' parameter - this makes it possible to call these methods using the duration that specifies the level. Previously, these methods could only be called using the index of the level in the levels_ vector. These methods first do a linear scan through levels_ using the method getLevelsByDuration to find the corresponding index, and then perform the function they specify on the level. Differential Revision: D3414343 fbshipit-source-id: 8e1fcc16fd013d0b8b855a1eebbeff417e945b07 --- folly/stats/MultiLevelTimeSeries-defs.h | 28 +++- folly/stats/MultiLevelTimeSeries.h | 104 ++++++++++++- folly/test/TimeseriesTest.cpp | 188 ++++++++++++++++++++++++ 3 files changed, 317 insertions(+), 3 deletions(-) diff --git a/folly/stats/MultiLevelTimeSeries-defs.h b/folly/stats/MultiLevelTimeSeries-defs.h index 686dafa6..763aaebe 100644 --- a/folly/stats/MultiLevelTimeSeries-defs.h +++ b/folly/stats/MultiLevelTimeSeries-defs.h @@ -16,6 +16,7 @@ #pragma once +#include #include namespace folly { @@ -43,8 +44,31 @@ MultiLevelTimeSeries::MultiLevelTimeSeries( } template -void MultiLevelTimeSeries::addValue(TimeType now, - const ValueType& val) { +MultiLevelTimeSeries::MultiLevelTimeSeries( + size_t nBuckets, + std::initializer_list durations) + : cachedTime_(0), cachedSum_(0), cachedCount_(0) { + CHECK_GT(durations.size(), 0); + + levels_.reserve(durations.size()); + int i = 0; + TimeType prev; + for (auto dur : durations) { + if (dur == TT(0)) { + CHECK_EQ(i, durations.size() - 1); + } else if (i > 0) { + CHECK(prev < dur); + } + levels_.emplace_back(nBuckets, dur); + prev = dur; + i++; + } +} + +template +void MultiLevelTimeSeries::addValue( + TimeType now, + const ValueType& val) { addValueAggregated(now, val, 1); } diff --git a/folly/stats/MultiLevelTimeSeries.h b/folly/stats/MultiLevelTimeSeries.h index f38b4e9f..f5a9d5a6 100644 --- a/folly/stats/MultiLevelTimeSeries.h +++ b/folly/stats/MultiLevelTimeSeries.h @@ -17,11 +17,13 @@ #pragma once #include +#include #include #include -#include +#include #include +#include namespace folly { @@ -69,6 +71,10 @@ class MultiLevelTimeSeries { size_t numLevels, const TimeType levelDurations[]); + MultiLevelTimeSeries( + size_t numBuckets, + std::initializer_list durations); + /* * Return the number of buckets used to track time series at each level. */ @@ -122,6 +128,26 @@ class MultiLevelTimeSeries { return levels_.back(); } + /* + * Get the BucketedTimeSeries backing the specified level. + * + * Note: you should generally call update() or flush() before accessing the + * data. Otherwise you may be reading stale data if update() or flush() has + * not been called recently. + */ + const Level& getLevelByDuration(TimeType duration) const { + // since the number of levels is expected to be small (less than 5 in most + // cases), a simple linear scan would be efficient and is intentionally + // chosen here over other alternatives for lookup. + for (const auto& level : levels_) { + if (level.duration() == duration) { + return level; + } + } + throw std::out_of_range(folly::to( + "No level of duration ", duration.count(), " found")); + } + /* * Return the sum of all the data points currently tracked at this level. * @@ -185,6 +211,82 @@ class MultiLevelTimeSeries { return getLevel(level).template countRate(); } + /* + * Return the sum of all the data points currently tracked at this level. + * + * This method is identical to sum(int level) above but takes in the + * duration that the user is interested in querying as the parameter. + * + * Note: you should generally call update() or flush() before accessing the + * data. Otherwise you may be reading stale data if update() or flush() has + * not been called recently. + */ + ValueType sum(TimeType duration) const { + return getLevelByDuration(duration).sum(); + } + + /* + * Return the average (sum / count) of all the data points currently tracked + * at this level. + * + * This method is identical to avg(int level) above but takes in the + * duration that the user is interested in querying as the parameter. + * + * Note: you should generally call update() or flush() before accessing the + * data. Otherwise you may be reading stale data if update() or flush() has + * not been called recently. + */ + template + ReturnType avg(TimeType duration) const { + return getLevelByDuration(duration).template avg(); + } + + /* + * Return the rate (sum divided by elaspsed time) of the all data points + * currently tracked at this level. + * + * This method is identical to rate(int level) above but takes in the + * duration that the user is interested in querying as the parameter. + * + * Note: you should generally call update() or flush() before accessing the + * data. Otherwise you may be reading stale data if update() or flush() has + * not been called recently. + */ + template + ReturnType rate(TimeType duration) const { + return getLevelByDuration(duration).template rate(); + } + + /* + * Return the number of data points currently tracked at this level. + * + * This method is identical to count(int level) above but takes in the + * duration that the user is interested in querying as the parameter. + * + * Note: you should generally call update() or flush() before accessing the + * data. Otherwise you may be reading stale data if update() or flush() has + * not been called recently. + */ + int64_t count(TimeType duration) const { + return getLevelByDuration(duration).count(); + } + + /* + * Return the count divided by the elapsed time tracked at this level. + * + * This method is identical to countRate(int level) above but takes in the + * duration that the user is interested in querying as the parameter. + * + * Note: you should generally call update() or flush() before accessing the + * data. Otherwise you may be reading stale data if update() or flush() has + * not been called recently. + */ + template + ReturnType countRate(TimeType duration) const { + return getLevelByDuration(duration) + .template countRate(); + } + /* * Estimate the sum of the data points that occurred in the specified time * period at this level. diff --git a/folly/test/TimeseriesTest.cpp b/folly/test/TimeseriesTest.cpp index 7b1992db..85ec1b89 100644 --- a/folly/test/TimeseriesTest.cpp +++ b/folly/test/TimeseriesTest.cpp @@ -957,3 +957,191 @@ TEST(MinuteHourTimeSeries, QueryByInterval) { EXPECT_EQ(expectedRate, r); } } + +TEST(MultiLevelTimeSeries, Basic) { + // using constructor with initializer_list parameter + folly::MultiLevelTimeSeries mhts( + 60, {seconds(60), seconds(3600), seconds(0)}); + EXPECT_EQ(mhts.numLevels(), 3); + + EXPECT_EQ(mhts.sum(seconds(60)), 0); + EXPECT_EQ(mhts.sum(seconds(3600)), 0); + EXPECT_EQ(mhts.sum(seconds(0)), 0); + + EXPECT_EQ(mhts.avg(seconds(60)), 0); + EXPECT_EQ(mhts.avg(seconds(3600)), 0); + EXPECT_EQ(mhts.avg(seconds(0)), 0); + + EXPECT_EQ(mhts.rate(seconds(60)), 0); + EXPECT_EQ(mhts.rate(seconds(3600)), 0); + EXPECT_EQ(mhts.rate(seconds(0)), 0); + + EXPECT_EQ(mhts.getLevelByDuration(seconds(60)).elapsed().count(), 0); + EXPECT_EQ(mhts.getLevelByDuration(seconds(3600)).elapsed().count(), 0); + EXPECT_EQ(mhts.getLevelByDuration(seconds(0)).elapsed().count(), 0); + + seconds cur_time(0); + + mhts.addValue(cur_time++, 10); + mhts.flush(); + + EXPECT_EQ(mhts.getLevelByDuration(seconds(60)).elapsed().count(), 1); + EXPECT_EQ(mhts.getLevelByDuration(seconds(3600)).elapsed().count(), 1); + EXPECT_EQ(mhts.getLevelByDuration(seconds(0)).elapsed().count(), 1); + + for (int i = 0; i < 299; ++i) { + mhts.addValue(cur_time++, 10); + } + mhts.flush(); + + EXPECT_EQ(mhts.getLevelByDuration(seconds(60)).elapsed().count(), 60); + EXPECT_EQ(mhts.getLevelByDuration(seconds(3600)).elapsed().count(), 300); + EXPECT_EQ(mhts.getLevelByDuration(seconds(0)).elapsed().count(), 300); + + EXPECT_EQ(mhts.sum(seconds(60)), 600); + EXPECT_EQ(mhts.sum(seconds(3600)), 300 * 10); + EXPECT_EQ(mhts.sum(seconds(0)), 300 * 10); + + EXPECT_EQ(mhts.avg(seconds(60)), 10); + EXPECT_EQ(mhts.avg(seconds(3600)), 10); + EXPECT_EQ(mhts.avg(seconds(0)), 10); + + EXPECT_EQ(mhts.rate(seconds(60)), 10); + EXPECT_EQ(mhts.rate(seconds(3600)), 10); + EXPECT_EQ(mhts.rate(seconds(0)), 10); + + for (int i = 0; i < 3600 * 3 - 300; ++i) { + mhts.addValue(cur_time++, 10); + } + mhts.flush(); + + EXPECT_EQ(mhts.getLevelByDuration(seconds(60)).elapsed().count(), 60); + EXPECT_EQ(mhts.getLevelByDuration(seconds(3600)).elapsed().count(), 3600); + EXPECT_EQ(mhts.getLevelByDuration(seconds(0)).elapsed().count(), 3600 * 3); + + EXPECT_EQ(mhts.sum(seconds(60)), 600); + EXPECT_EQ(mhts.sum(seconds(3600)), 3600 * 10); + EXPECT_EQ(mhts.sum(seconds(0)), 3600 * 3 * 10); + + EXPECT_EQ(mhts.avg(seconds(60)), 10); + EXPECT_EQ(mhts.avg(seconds(3600)), 10); + EXPECT_EQ(mhts.avg(seconds(0)), 10); + + EXPECT_EQ(mhts.rate(seconds(60)), 10); + EXPECT_EQ(mhts.rate(seconds(3600)), 10); + EXPECT_EQ(mhts.rate(seconds(0)), 10); + + for (int i = 0; i < 3600; ++i) { + mhts.addValue(cur_time++, 100); + } + mhts.flush(); + + EXPECT_EQ(mhts.sum(seconds(60)), 60 * 100); + EXPECT_EQ(mhts.sum(seconds(3600)), 3600 * 100); + EXPECT_EQ(mhts.sum(seconds(0)), 3600 * 3 * 10 + 3600 * 100); + + EXPECT_EQ(mhts.avg(seconds(60)), 100); + EXPECT_EQ(mhts.avg(seconds(3600)), 100); + EXPECT_EQ(mhts.avg(seconds(0)), 32.5); + EXPECT_EQ(mhts.avg(seconds(0)), 32); + + EXPECT_EQ(mhts.rate(seconds(60)), 100); + EXPECT_EQ(mhts.rate(seconds(3600)), 100); + EXPECT_EQ(mhts.rate(seconds(0)), 32.5); + EXPECT_EQ(mhts.rate(seconds(0)), 32); + + for (int i = 0; i < 1800; ++i) { + mhts.addValue(cur_time++, 120); + } + mhts.flush(); + + EXPECT_EQ(mhts.sum(seconds(60)), 60 * 120); + EXPECT_EQ(mhts.sum(seconds(3600)), 1800 * 100 + 1800 * 120); + EXPECT_EQ(mhts.sum(seconds(0)), 3600 * 3 * 10 + 3600 * 100 + 1800 * 120); + + for (int i = 0; i < 60; ++i) { + mhts.addValue(cur_time++, 1000); + } + mhts.flush(); + + EXPECT_EQ(mhts.sum(seconds(60)), 60 * 1000); + EXPECT_EQ(mhts.sum(seconds(3600)), 1740 * 100 + 1800 * 120 + 60 * 1000); + EXPECT_EQ( + mhts.sum(seconds(0)), + 3600 * 3 * 10 + 3600 * 100 + 1800 * 120 + 60 * 1000); + + mhts.clear(); + EXPECT_EQ(mhts.sum(seconds(0)), 0); +} + +TEST(MultiLevelTimeSeries, QueryByInterval) { + folly::MultiLevelTimeSeries mhts( + 60, {seconds(60), seconds(3600), seconds(0)}); + + seconds curTime(0); + for (curTime = seconds(0); curTime < seconds(7200); curTime++) { + mhts.addValue(curTime, 1); + } + for (curTime = seconds(7200); curTime < seconds(7200 + 3540); curTime++) { + mhts.addValue(curTime, 10); + } + for (curTime = seconds(7200 + 3540); curTime < seconds(7200 + 3600); + curTime++) { + mhts.addValue(curTime, 100); + } + mhts.flush(); + + struct TimeInterval { + seconds start; + seconds end; + }; + + std::array intervals = {{ + {curTime - seconds(60), curTime}, + {curTime - seconds(3600), curTime}, + {curTime - seconds(7200), curTime}, + {curTime - seconds(3600), curTime - seconds(60)}, + {curTime - seconds(7200), curTime - seconds(60)}, + {curTime - seconds(7200), curTime - seconds(3600)}, + {curTime - seconds(50), curTime - seconds(20)}, + {curTime - seconds(3020), curTime - seconds(20)}, + {curTime - seconds(7200), curTime - seconds(20)}, + {curTime - seconds(3000), curTime - seconds(1000)}, + {curTime - seconds(7200), curTime - seconds(1000)}, + {curTime - seconds(7200), curTime - seconds(3600)}, + }}; + + std::array expectedSums = {{6000, + 41400, + 32400, + 35400, + 32130, + 16200, + 3000, + 33600, + 32310, + 20000, + 27900, + 16200}}; + + std::array expectedCounts = { + {60, 3600, 7200, 3540, 7140, 3600, 30, 3000, 7180, 2000, 6200, 3600}}; + + for (size_t i = 0; i < intervals.size(); ++i) { + TimeInterval interval = intervals[i]; + + int s = mhts.sum(interval.start, interval.end); + EXPECT_EQ(expectedSums[i], s); + + int c = mhts.count(interval.start, interval.end); + EXPECT_EQ(expectedCounts[i], c); + + int a = mhts.avg(interval.start, interval.end); + EXPECT_EQ(expectedCounts[i] ? (expectedSums[i] / expectedCounts[i]) : 0, a); + + int r = mhts.rate(interval.start, interval.end); + int expectedRate = + expectedSums[i] / (interval.end - interval.start).count(); + EXPECT_EQ(expectedRate, r); + } +} -- 2.34.1