1/*
2 * Copyright 2013-present Facebook, Inc.
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17#include <folly/stats/detail/BufferedStat-defs.h>
18
19#include <folly/Range.h>
20#include <folly/portability/GTest.h>
21
22using namespace folly;
23using namespace folly::detail;
24
25const size_t kDigestSize = 100;
26
27struct MockClock {
28 public:
29 using duration = std::chrono::steady_clock::duration;
30 using time_point = std::chrono::steady_clock::time_point;
31
32 static time_point now() {
33 return Now;
34 }
35
36 static time_point Now;
37};
38
39class SimpleDigest {
40 public:
41 explicit SimpleDigest(size_t sz) {
42 EXPECT_EQ(kDigestSize, sz);
43 }
44
45 SimpleDigest merge(Range<const double*> r) const {
46 SimpleDigest digest(100);
47
48 digest.values_ = values_;
49 for (auto it = r.begin(); it != r.end(); ++it) {
50 digest.values_.push_back(*it);
51 }
52 return digest;
53 }
54
55 static SimpleDigest merge(Range<const SimpleDigest*> r) {
56 SimpleDigest digest(100);
57 for (auto it = r.begin(); it != r.end(); ++it) {
58 for (auto value : it->values_) {
59 digest.values_.push_back(value);
60 }
61 }
62 return digest;
63 }
64
65 std::vector<double> getValues() const {
66 return values_;
67 }
68
69 bool empty() const {
70 return values_.empty();
71 }
72
73 private:
74 std::vector<double> values_;
75};
76
77MockClock::time_point MockClock::Now = MockClock::time_point{};
78
79class BufferedDigestTest : public ::testing::Test {
80 protected:
81 std::unique_ptr<BufferedDigest<SimpleDigest, MockClock>> bd;
82 const size_t nBuckets = 60;
83 const size_t bufferSize = 1000;
84 const std::chrono::milliseconds bufferDuration{1000};
85
86 void SetUp() override {
87 MockClock::Now = MockClock::time_point{};
88 bd = std::make_unique<BufferedDigest<SimpleDigest, MockClock>>(
89 bufferDuration, bufferSize, kDigestSize);
90 }
91};
92
93TEST_F(BufferedDigestTest, Buffering) {
94 bd->append(0);
95 bd->append(1);
96 bd->append(2);
97
98 auto digest = bd->get();
99 EXPECT_TRUE(digest.empty());
100}
101
102TEST_F(BufferedDigestTest, PartiallyPassedExpiry) {
103 bd->append(0);
104 bd->append(1);
105 bd->append(2);
106
107 MockClock::Now += bufferDuration / 10;
108
109 auto digest = bd->get();
110
111 auto values = digest.getValues();
112 EXPECT_EQ(0, values[0]);
113 EXPECT_EQ(1, values[1]);
114 EXPECT_EQ(2, values[2]);
115}
116
117TEST_F(BufferedDigestTest, ForceUpdate) {
118 bd->append(0);
119 bd->append(1);
120 bd->append(2);
121
122 // empty since we haven't passed expiry
123 auto digest = bd->get();
124 EXPECT_TRUE(digest.empty());
125
126 // force update
127 bd->flush();
128 digest = bd->get();
129 auto values = digest.getValues();
130 EXPECT_EQ(0, values[0]);
131 EXPECT_EQ(1, values[1]);
132 EXPECT_EQ(2, values[2]);
133
134 // append 3 and do a normal get; only the previously
135 // flushed values should show up and not 3 since we
136 // haven't passed expiry
137 bd->append(3);
138 digest = bd->get();
139 values = digest.getValues();
140 EXPECT_EQ(0, values[0]);
141 EXPECT_EQ(1, values[1]);
142 EXPECT_EQ(2, values[2]);
143
144 // pass expiry; 3 should now be visible
145 MockClock::Now += bufferDuration;
146 digest = bd->get();
147 values = digest.getValues();
148 EXPECT_EQ(0, values[0]);
149 EXPECT_EQ(1, values[1]);
150 EXPECT_EQ(2, values[2]);
151 EXPECT_EQ(3, values[3]);
152}
153
154class BufferedSlidingWindowTest : public ::testing::Test {
155 protected:
156 std::unique_ptr<BufferedSlidingWindow<SimpleDigest, MockClock>> bsw;
157 const size_t nBuckets = 60;
158 const size_t bufferSize = 1000;
159 const std::chrono::milliseconds windowDuration{1000};
160
161 void SetUp() override {
162 MockClock::Now = MockClock::time_point{};
163 bsw = std::make_unique<BufferedSlidingWindow<SimpleDigest, MockClock>>(
164 nBuckets, windowDuration, bufferSize, kDigestSize);
165 }
166};
167
168TEST_F(BufferedSlidingWindowTest, Buffering) {
169 bsw->append(0);
170 bsw->append(1);
171 bsw->append(2);
172
173 auto digests = bsw->get();
174 EXPECT_EQ(0, digests.size());
175}
176
177TEST_F(BufferedSlidingWindowTest, PartiallyPassedExpiry) {
178 bsw->append(0);
179 bsw->append(1);
180 bsw->append(2);
181
182 MockClock::Now += windowDuration / 10;
183
184 auto digests = bsw->get();
185
186 EXPECT_EQ(1, digests.size());
187 EXPECT_EQ(3, digests[0].getValues().size());
188
189 for (double i = 0; i < 3; ++i) {
190 EXPECT_EQ(i, digests[0].getValues()[i]);
191 }
192}
193
194TEST_F(BufferedSlidingWindowTest, ForceUpdate) {
195 bsw->append(0);
196 bsw->append(1);
197 bsw->append(2);
198
199 // empty since we haven't passed expiry
200 auto digests = bsw->get();
201 EXPECT_EQ(0, digests.size());
202
203 // flush
204 bsw->flush();
205 digests = bsw->get();
206 EXPECT_EQ(1, digests.size());
207 EXPECT_EQ(3, digests[0].getValues().size());
208 for (double i = 0; i < 3; ++i) {
209 EXPECT_EQ(i, digests[0].getValues()[i]);
210 }
211
212 // append 3 and flush again; 3 will be merged with
213 // current window
214 bsw->append(3);
215 bsw->flush();
216 digests = bsw->get();
217 EXPECT_EQ(1, digests.size());
218 EXPECT_EQ(4, digests[0].getValues().size());
219 for (double i = 0; i < 4; ++i) {
220 EXPECT_EQ(i, digests[0].getValues()[i]);
221 }
222
223 // append 4 and do a regular get. previous values
224 // show up but not 4
225 bsw->append(4);
226 digests = bsw->get();
227 EXPECT_EQ(1, digests.size());
228 EXPECT_EQ(4, digests[0].getValues().size());
229 for (double i = 0; i < 4; ++i) {
230 EXPECT_EQ(i, digests[0].getValues()[i]);
231 }
232
233 // pass expiry
234 MockClock::Now += windowDuration;
235 digests = bsw->get();
236 EXPECT_EQ(2, digests.size());
237
238 EXPECT_EQ(1, digests[0].getValues().size());
239 EXPECT_EQ(4, digests[0].getValues().front());
240
241 EXPECT_EQ(4, digests[1].getValues().size());
242 for (double i = 0; i < 4; ++i) {
243 EXPECT_EQ(i, digests[1].getValues()[i]);
244 }
245}
246
247TEST_F(BufferedSlidingWindowTest, BufferingAfterSlide) {
248 MockClock::Now += std::chrono::milliseconds{1};
249
250 bsw->append(1);
251
252 auto digests = bsw->get();
253 EXPECT_EQ(0, digests.size());
254}
255
256TEST_F(BufferedSlidingWindowTest, TwoSlides) {
257 bsw->append(0);
258
259 MockClock::Now += windowDuration;
260
261 bsw->append(1);
262
263 MockClock::Now += windowDuration;
264
265 auto digests = bsw->get();
266
267 EXPECT_EQ(2, digests.size());
268 EXPECT_EQ(1, digests[0].getValues().size());
269 EXPECT_EQ(1, digests[0].getValues()[0]);
270 EXPECT_EQ(1, digests[1].getValues().size());
271 EXPECT_EQ(0, digests[1].getValues()[0]);
272}
273
274TEST_F(BufferedSlidingWindowTest, MultiWindowDurationSlide) {
275 bsw->append(0);
276
277 MockClock::Now += windowDuration * 2;
278
279 auto digests = bsw->get();
280 EXPECT_EQ(1, digests.size());
281}
282
283TEST_F(BufferedSlidingWindowTest, SlidePastWindow) {
284 bsw->append(0);
285
286 MockClock::Now += windowDuration * (nBuckets + 1);
287
288 auto digests = bsw->get();
289
290 EXPECT_EQ(0, digests.size());
291}
292