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 | |
22 | using namespace folly; |
23 | using namespace folly::detail; |
24 | |
25 | const size_t kDigestSize = 100; |
26 | |
27 | struct 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 | |
39 | class 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 | |
77 | MockClock::time_point MockClock::Now = MockClock::time_point{}; |
78 | |
79 | class 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 | |
93 | TEST_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 | |
102 | TEST_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 | |
117 | TEST_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 | |
154 | class 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 | |
168 | TEST_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 | |
177 | TEST_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 | |
194 | TEST_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 | |
247 | TEST_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 | |
256 | TEST_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 | |
274 | TEST_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 | |
283 | TEST_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 | |