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