1 // Copyright (c) 2011-present, Facebook, Inc. All rights reserved.
2 // This source code is licensed under both the GPLv2 (found in the
3 // COPYING file in the root directory) and Apache 2.0 License
4 // (found in the LICENSE.Apache file in the root directory).
5 //
6 #include "monitoring/histogram.h"
7
8 #include <cmath>
9
10 #include "monitoring/histogram_windowing.h"
11 #include "rocksdb/system_clock.h"
12 #include "test_util/mock_time_env.h"
13 #include "test_util/testharness.h"
14 #include "util/random.h"
15
16 namespace ROCKSDB_NAMESPACE {
17
18 class HistogramTest : public testing::Test {};
19
20 namespace {
21 const double kIota = 0.1;
22 const HistogramBucketMapper bucketMapper;
23 std::shared_ptr<MockSystemClock> clock =
24 std::make_shared<MockSystemClock>(SystemClock::Default());
25 }
26
PopulateHistogram(Histogram & histogram,uint64_t low,uint64_t high,uint64_t loop=1)27 void PopulateHistogram(Histogram& histogram,
28 uint64_t low, uint64_t high, uint64_t loop = 1) {
29 Random rnd(test::RandomSeed());
30 for (; loop > 0; loop--) {
31 for (uint64_t i = low; i <= high; i++) {
32 histogram.Add(i);
33 // sleep a random microseconds [0-10)
34 clock->SleepForMicroseconds(rnd.Uniform(10));
35 }
36 }
37 // make sure each data population at least take some time
38 clock->SleepForMicroseconds(1);
39 }
40
BasicOperation(Histogram & histogram)41 void BasicOperation(Histogram& histogram) {
42 PopulateHistogram(histogram, 1, 110, 10); // fill up to bucket [70, 110)
43
44 HistogramData data;
45 histogram.Data(&data);
46
47 ASSERT_LE(fabs(histogram.Percentile(100.0) - 110.0), kIota);
48 ASSERT_LE(fabs(data.percentile99 - 108.9), kIota); // 99 * 110 / 100
49 ASSERT_LE(fabs(data.percentile95 - 104.5), kIota); // 95 * 110 / 100
50 ASSERT_LE(fabs(data.median - 55.0), kIota); // 50 * 110 / 100
51 ASSERT_EQ(data.average, 55.5); // (1 + 110) / 2
52 }
53
MergeHistogram(Histogram & histogram,Histogram & other)54 void MergeHistogram(Histogram& histogram, Histogram& other) {
55 PopulateHistogram(histogram, 1, 100);
56 PopulateHistogram(other, 101, 250);
57 histogram.Merge(other);
58
59 HistogramData data;
60 histogram.Data(&data);
61
62 ASSERT_LE(fabs(histogram.Percentile(100.0) - 250.0), kIota);
63 ASSERT_LE(fabs(data.percentile99 - 247.5), kIota); // 99 * 250 / 100
64 ASSERT_LE(fabs(data.percentile95 - 237.5), kIota); // 95 * 250 / 100
65 ASSERT_LE(fabs(data.median - 125.0), kIota); // 50 * 250 / 100
66 ASSERT_EQ(data.average, 125.5); // (1 + 250) / 2
67 }
68
EmptyHistogram(Histogram & histogram)69 void EmptyHistogram(Histogram& histogram) {
70 ASSERT_EQ(histogram.min(), bucketMapper.LastValue());
71 ASSERT_EQ(histogram.max(), 0);
72 ASSERT_EQ(histogram.num(), 0);
73 ASSERT_EQ(histogram.Median(), 0.0);
74 ASSERT_EQ(histogram.Percentile(85.0), 0.0);
75 ASSERT_EQ(histogram.Average(), 0.0);
76 ASSERT_EQ(histogram.StandardDeviation(), 0.0);
77 }
78
ClearHistogram(Histogram & histogram)79 void ClearHistogram(Histogram& histogram) {
80 for (uint64_t i = 1; i <= 100; i++) {
81 histogram.Add(i);
82 }
83 histogram.Clear();
84 ASSERT_TRUE(histogram.Empty());
85 ASSERT_EQ(histogram.Median(), 0);
86 ASSERT_EQ(histogram.Percentile(85.0), 0);
87 ASSERT_EQ(histogram.Average(), 0);
88 }
89
TEST_F(HistogramTest,BasicOperation)90 TEST_F(HistogramTest, BasicOperation) {
91 HistogramImpl histogram;
92 BasicOperation(histogram);
93
94 HistogramWindowingImpl histogramWindowing;
95 BasicOperation(histogramWindowing);
96 }
97
TEST_F(HistogramTest,BoundaryValue)98 TEST_F(HistogramTest, BoundaryValue) {
99 HistogramImpl histogram;
100 // - both should be in [0, 1] bucket because we place values on bucket
101 // boundaries in the lower bucket.
102 // - all points are in [0, 1] bucket, so p50 will be 0.5
103 // - the test cannot be written with a single point since histogram won't
104 // report percentiles lower than the min or greater than the max.
105 histogram.Add(0);
106 histogram.Add(1);
107
108 ASSERT_LE(fabs(histogram.Percentile(50.0) - 0.5), kIota);
109 }
110
TEST_F(HistogramTest,MergeHistogram)111 TEST_F(HistogramTest, MergeHistogram) {
112 HistogramImpl histogram;
113 HistogramImpl other;
114 MergeHistogram(histogram, other);
115
116 HistogramWindowingImpl histogramWindowing;
117 HistogramWindowingImpl otherWindowing;
118 MergeHistogram(histogramWindowing, otherWindowing);
119 }
120
TEST_F(HistogramTest,EmptyHistogram)121 TEST_F(HistogramTest, EmptyHistogram) {
122 HistogramImpl histogram;
123 EmptyHistogram(histogram);
124
125 HistogramWindowingImpl histogramWindowing;
126 EmptyHistogram(histogramWindowing);
127 }
128
TEST_F(HistogramTest,ClearHistogram)129 TEST_F(HistogramTest, ClearHistogram) {
130 HistogramImpl histogram;
131 ClearHistogram(histogram);
132
133 HistogramWindowingImpl histogramWindowing;
134 ClearHistogram(histogramWindowing);
135 }
136
TEST_F(HistogramTest,HistogramWindowingExpire)137 TEST_F(HistogramTest, HistogramWindowingExpire) {
138 uint64_t num_windows = 3;
139 int micros_per_window = 1000000;
140 uint64_t min_num_per_window = 0;
141
142 HistogramWindowingImpl
143 histogramWindowing(num_windows, micros_per_window, min_num_per_window);
144 histogramWindowing.TEST_UpdateClock(clock);
145 PopulateHistogram(histogramWindowing, 1, 1, 100);
146 clock->SleepForMicroseconds(micros_per_window);
147 ASSERT_EQ(histogramWindowing.num(), 100);
148 ASSERT_EQ(histogramWindowing.min(), 1);
149 ASSERT_EQ(histogramWindowing.max(), 1);
150 ASSERT_EQ(histogramWindowing.Average(), 1);
151
152 PopulateHistogram(histogramWindowing, 2, 2, 100);
153 clock->SleepForMicroseconds(micros_per_window);
154 ASSERT_EQ(histogramWindowing.num(), 200);
155 ASSERT_EQ(histogramWindowing.min(), 1);
156 ASSERT_EQ(histogramWindowing.max(), 2);
157 ASSERT_EQ(histogramWindowing.Average(), 1.5);
158
159 PopulateHistogram(histogramWindowing, 3, 3, 100);
160 clock->SleepForMicroseconds(micros_per_window);
161 ASSERT_EQ(histogramWindowing.num(), 300);
162 ASSERT_EQ(histogramWindowing.min(), 1);
163 ASSERT_EQ(histogramWindowing.max(), 3);
164 ASSERT_EQ(histogramWindowing.Average(), 2.0);
165
166 // dropping oldest window with value 1, remaining 2 ~ 4
167 PopulateHistogram(histogramWindowing, 4, 4, 100);
168 clock->SleepForMicroseconds(micros_per_window);
169 ASSERT_EQ(histogramWindowing.num(), 300);
170 ASSERT_EQ(histogramWindowing.min(), 2);
171 ASSERT_EQ(histogramWindowing.max(), 4);
172 ASSERT_EQ(histogramWindowing.Average(), 3.0);
173
174 // dropping oldest window with value 2, remaining 3 ~ 5
175 PopulateHistogram(histogramWindowing, 5, 5, 100);
176 clock->SleepForMicroseconds(micros_per_window);
177 ASSERT_EQ(histogramWindowing.num(), 300);
178 ASSERT_EQ(histogramWindowing.min(), 3);
179 ASSERT_EQ(histogramWindowing.max(), 5);
180 ASSERT_EQ(histogramWindowing.Average(), 4.0);
181 }
182
TEST_F(HistogramTest,HistogramWindowingMerge)183 TEST_F(HistogramTest, HistogramWindowingMerge) {
184 uint64_t num_windows = 3;
185 int micros_per_window = 1000000;
186 uint64_t min_num_per_window = 0;
187
188 HistogramWindowingImpl
189 histogramWindowing(num_windows, micros_per_window, min_num_per_window);
190 HistogramWindowingImpl
191 otherWindowing(num_windows, micros_per_window, min_num_per_window);
192 histogramWindowing.TEST_UpdateClock(clock);
193 otherWindowing.TEST_UpdateClock(clock);
194
195 PopulateHistogram(histogramWindowing, 1, 1, 100);
196 PopulateHistogram(otherWindowing, 1, 1, 100);
197 clock->SleepForMicroseconds(micros_per_window);
198
199 PopulateHistogram(histogramWindowing, 2, 2, 100);
200 PopulateHistogram(otherWindowing, 2, 2, 100);
201 clock->SleepForMicroseconds(micros_per_window);
202
203 PopulateHistogram(histogramWindowing, 3, 3, 100);
204 PopulateHistogram(otherWindowing, 3, 3, 100);
205 clock->SleepForMicroseconds(micros_per_window);
206
207 histogramWindowing.Merge(otherWindowing);
208 ASSERT_EQ(histogramWindowing.num(), 600);
209 ASSERT_EQ(histogramWindowing.min(), 1);
210 ASSERT_EQ(histogramWindowing.max(), 3);
211 ASSERT_EQ(histogramWindowing.Average(), 2.0);
212
213 // dropping oldest window with value 1, remaining 2 ~ 4
214 PopulateHistogram(histogramWindowing, 4, 4, 100);
215 clock->SleepForMicroseconds(micros_per_window);
216 ASSERT_EQ(histogramWindowing.num(), 500);
217 ASSERT_EQ(histogramWindowing.min(), 2);
218 ASSERT_EQ(histogramWindowing.max(), 4);
219
220 // dropping oldest window with value 2, remaining 3 ~ 5
221 PopulateHistogram(histogramWindowing, 5, 5, 100);
222 clock->SleepForMicroseconds(micros_per_window);
223 ASSERT_EQ(histogramWindowing.num(), 400);
224 ASSERT_EQ(histogramWindowing.min(), 3);
225 ASSERT_EQ(histogramWindowing.max(), 5);
226 }
227
228 } // namespace ROCKSDB_NAMESPACE
229
main(int argc,char ** argv)230 int main(int argc, char** argv) {
231 ::testing::InitGoogleTest(&argc, argv);
232 return RUN_ALL_TESTS();
233 }
234