]>
Commit | Line | Data |
---|---|---|
7c673cae | 1 | // Copyright (c) 2011-present, Facebook, Inc. All rights reserved. |
11fdf7f2 TL |
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). | |
7c673cae FG |
5 | // |
6 | #include <stdio.h> | |
7 | #include <algorithm> | |
8 | #include <set> | |
9 | #include <string> | |
10 | #include <unordered_set> | |
11 | #include <utility> | |
12 | #include <vector> | |
13 | ||
14 | #include "db/dbformat.h" | |
7c673cae | 15 | #include "db/memtable.h" |
494da23a | 16 | #include "db/write_batch_internal.h" |
7c673cae FG |
17 | #include "rocksdb/db.h" |
18 | #include "rocksdb/env.h" | |
19 | #include "rocksdb/iterator.h" | |
7c673cae | 20 | #include "rocksdb/slice_transform.h" |
494da23a | 21 | #include "rocksdb/table.h" |
7c673cae FG |
22 | #include "table/block.h" |
23 | #include "table/block_builder.h" | |
24 | #include "table/format.h" | |
25 | #include "util/random.h" | |
26 | #include "util/testharness.h" | |
27 | #include "util/testutil.h" | |
28 | ||
29 | namespace rocksdb { | |
30 | ||
494da23a | 31 | static std::string RandomString(Random *rnd, int len) { |
7c673cae FG |
32 | std::string r; |
33 | test::RandomString(rnd, len, &r); | |
34 | return r; | |
35 | } | |
36 | std::string GenerateKey(int primary_key, int secondary_key, int padding_size, | |
37 | Random *rnd) { | |
38 | char buf[50]; | |
39 | char *p = &buf[0]; | |
40 | snprintf(buf, sizeof(buf), "%6d%4d", primary_key, secondary_key); | |
41 | std::string k(p); | |
42 | if (padding_size) { | |
43 | k += RandomString(rnd, padding_size); | |
44 | } | |
45 | ||
46 | return k; | |
47 | } | |
48 | ||
49 | // Generate random key value pairs. | |
50 | // The generated key will be sorted. You can tune the parameters to generated | |
51 | // different kinds of test key/value pairs for different scenario. | |
52 | void GenerateRandomKVs(std::vector<std::string> *keys, | |
53 | std::vector<std::string> *values, const int from, | |
54 | const int len, const int step = 1, | |
55 | const int padding_size = 0, | |
56 | const int keys_share_prefix = 1) { | |
57 | Random rnd(302); | |
58 | ||
59 | // generate different prefix | |
60 | for (int i = from; i < from + len; i += step) { | |
61 | // generating keys that shares the prefix | |
62 | for (int j = 0; j < keys_share_prefix; ++j) { | |
63 | keys->emplace_back(GenerateKey(i, j, padding_size, &rnd)); | |
64 | ||
65 | // 100 bytes values | |
66 | values->emplace_back(RandomString(&rnd, 100)); | |
67 | } | |
68 | } | |
69 | } | |
70 | ||
11fdf7f2 TL |
71 | // Same as GenerateRandomKVs but the values are BlockHandle |
72 | void GenerateRandomKBHs(std::vector<std::string> *keys, | |
73 | std::vector<BlockHandle> *values, const int from, | |
74 | const int len, const int step = 1, | |
75 | const int padding_size = 0, | |
76 | const int keys_share_prefix = 1) { | |
77 | Random rnd(302); | |
78 | uint64_t offset = 0; | |
79 | ||
80 | // generate different prefix | |
81 | for (int i = from; i < from + len; i += step) { | |
82 | // generate keys that shares the prefix | |
83 | for (int j = 0; j < keys_share_prefix; ++j) { | |
84 | keys->emplace_back(GenerateKey(i, j, padding_size, &rnd)); | |
85 | ||
86 | uint64_t size = rnd.Uniform(1024 * 16); | |
87 | BlockHandle handle(offset, size); | |
88 | offset += size + kBlockTrailerSize; | |
89 | values->emplace_back(handle); | |
90 | } | |
91 | } | |
92 | } | |
93 | ||
7c673cae FG |
94 | class BlockTest : public testing::Test {}; |
95 | ||
96 | // block test | |
97 | TEST_F(BlockTest, SimpleTest) { | |
98 | Random rnd(301); | |
99 | Options options = Options(); | |
100 | std::unique_ptr<InternalKeyComparator> ic; | |
101 | ic.reset(new test::PlainInternalKeyComparator(options.comparator)); | |
102 | ||
103 | std::vector<std::string> keys; | |
104 | std::vector<std::string> values; | |
105 | BlockBuilder builder(16); | |
106 | int num_records = 100000; | |
107 | ||
108 | GenerateRandomKVs(&keys, &values, 0, num_records); | |
109 | // add a bunch of records to a block | |
110 | for (int i = 0; i < num_records; i++) { | |
111 | builder.Add(keys[i], values[i]); | |
112 | } | |
113 | ||
114 | // read serialized contents of the block | |
115 | Slice rawblock = builder.Finish(); | |
116 | ||
117 | // create block reader | |
118 | BlockContents contents; | |
119 | contents.data = rawblock; | |
7c673cae FG |
120 | Block reader(std::move(contents), kDisableGlobalSequenceNumber); |
121 | ||
122 | // read contents of block sequentially | |
123 | int count = 0; | |
11fdf7f2 TL |
124 | InternalIterator *iter = |
125 | reader.NewIterator<DataBlockIter>(options.comparator, options.comparator); | |
494da23a | 126 | for (iter->SeekToFirst(); iter->Valid(); count++, iter->Next()) { |
7c673cae FG |
127 | // read kv from block |
128 | Slice k = iter->key(); | |
129 | Slice v = iter->value(); | |
130 | ||
131 | // compare with lookaside array | |
132 | ASSERT_EQ(k.ToString().compare(keys[count]), 0); | |
133 | ASSERT_EQ(v.ToString().compare(values[count]), 0); | |
134 | } | |
135 | delete iter; | |
136 | ||
137 | // read block contents randomly | |
11fdf7f2 TL |
138 | iter = |
139 | reader.NewIterator<DataBlockIter>(options.comparator, options.comparator); | |
7c673cae | 140 | for (int i = 0; i < num_records; i++) { |
7c673cae FG |
141 | // find a random key in the lookaside array |
142 | int index = rnd.Uniform(num_records); | |
143 | Slice k(keys[index]); | |
144 | ||
145 | // search in block for this key | |
146 | iter->Seek(k); | |
147 | ASSERT_TRUE(iter->Valid()); | |
148 | Slice v = iter->value(); | |
149 | ASSERT_EQ(v.ToString().compare(values[index]), 0); | |
150 | } | |
151 | delete iter; | |
152 | } | |
153 | ||
11fdf7f2 TL |
154 | TEST_F(BlockTest, ValueDeltaEncodingTest) { |
155 | Random rnd(301); | |
156 | Options options = Options(); | |
157 | std::unique_ptr<InternalKeyComparator> ic; | |
158 | ic.reset(new test::PlainInternalKeyComparator(options.comparator)); | |
159 | ||
160 | std::vector<std::string> keys; | |
161 | std::vector<BlockHandle> values; | |
162 | const bool kUseDeltaEncoding = true; | |
163 | const bool kUseValueDeltaEncoding = true; | |
164 | BlockBuilder builder(16, kUseDeltaEncoding, kUseValueDeltaEncoding); | |
165 | int num_records = 100; | |
166 | ||
167 | GenerateRandomKBHs(&keys, &values, 0, num_records); | |
168 | // add a bunch of records to a block | |
169 | BlockHandle last_encoded_handle; | |
170 | for (int i = 0; i < num_records; i++) { | |
171 | auto block_handle = values[i]; | |
172 | std::string handle_encoding; | |
173 | block_handle.EncodeTo(&handle_encoding); | |
174 | std::string handle_delta_encoding; | |
175 | PutVarsignedint64(&handle_delta_encoding, | |
176 | block_handle.size() - last_encoded_handle.size()); | |
177 | last_encoded_handle = block_handle; | |
178 | const Slice handle_delta_encoding_slice(handle_delta_encoding); | |
179 | builder.Add(keys[i], handle_encoding, &handle_delta_encoding_slice); | |
180 | } | |
181 | ||
182 | // read serialized contents of the block | |
183 | Slice rawblock = builder.Finish(); | |
184 | ||
185 | // create block reader | |
186 | BlockContents contents; | |
187 | contents.data = rawblock; | |
11fdf7f2 TL |
188 | Block reader(std::move(contents), kDisableGlobalSequenceNumber); |
189 | ||
190 | const bool kTotalOrderSeek = true; | |
191 | const bool kIncludesSeq = true; | |
192 | const bool kValueIsFull = !kUseValueDeltaEncoding; | |
193 | IndexBlockIter *kNullIter = nullptr; | |
194 | Statistics *kNullStats = nullptr; | |
195 | // read contents of block sequentially | |
196 | int count = 0; | |
197 | InternalIteratorBase<BlockHandle> *iter = reader.NewIterator<IndexBlockIter>( | |
198 | options.comparator, options.comparator, kNullIter, kNullStats, | |
199 | kTotalOrderSeek, kIncludesSeq, kValueIsFull); | |
200 | for (iter->SeekToFirst(); iter->Valid(); count++, iter->Next()) { | |
201 | // read kv from block | |
202 | Slice k = iter->key(); | |
203 | BlockHandle handle = iter->value(); | |
204 | ||
205 | // compare with lookaside array | |
206 | ASSERT_EQ(k.ToString().compare(keys[count]), 0); | |
207 | ||
208 | ASSERT_EQ(values[count].offset(), handle.offset()); | |
209 | ASSERT_EQ(values[count].size(), handle.size()); | |
210 | } | |
211 | delete iter; | |
212 | ||
213 | // read block contents randomly | |
214 | iter = reader.NewIterator<IndexBlockIter>( | |
215 | options.comparator, options.comparator, kNullIter, kNullStats, | |
216 | kTotalOrderSeek, kIncludesSeq, kValueIsFull); | |
217 | for (int i = 0; i < num_records; i++) { | |
218 | // find a random key in the lookaside array | |
219 | int index = rnd.Uniform(num_records); | |
220 | Slice k(keys[index]); | |
221 | ||
222 | // search in block for this key | |
223 | iter->Seek(k); | |
224 | ASSERT_TRUE(iter->Valid()); | |
225 | BlockHandle handle = iter->value(); | |
226 | ASSERT_EQ(values[index].offset(), handle.offset()); | |
227 | ASSERT_EQ(values[index].size(), handle.size()); | |
228 | } | |
229 | delete iter; | |
230 | } | |
7c673cae FG |
231 | // return the block contents |
232 | BlockContents GetBlockContents(std::unique_ptr<BlockBuilder> *builder, | |
233 | const std::vector<std::string> &keys, | |
234 | const std::vector<std::string> &values, | |
11fdf7f2 | 235 | const int /*prefix_group_size*/ = 1) { |
7c673cae FG |
236 | builder->reset(new BlockBuilder(1 /* restart interval */)); |
237 | ||
238 | // Add only half of the keys | |
239 | for (size_t i = 0; i < keys.size(); ++i) { | |
240 | (*builder)->Add(keys[i], values[i]); | |
241 | } | |
242 | Slice rawblock = (*builder)->Finish(); | |
243 | ||
244 | BlockContents contents; | |
245 | contents.data = rawblock; | |
7c673cae FG |
246 | |
247 | return contents; | |
248 | } | |
249 | ||
250 | void CheckBlockContents(BlockContents contents, const int max_key, | |
251 | const std::vector<std::string> &keys, | |
252 | const std::vector<std::string> &values) { | |
253 | const size_t prefix_size = 6; | |
254 | // create block reader | |
494da23a | 255 | BlockContents contents_ref(contents.data); |
7c673cae FG |
256 | Block reader1(std::move(contents), kDisableGlobalSequenceNumber); |
257 | Block reader2(std::move(contents_ref), kDisableGlobalSequenceNumber); | |
258 | ||
259 | std::unique_ptr<const SliceTransform> prefix_extractor( | |
260 | NewFixedPrefixTransform(prefix_size)); | |
261 | ||
262 | std::unique_ptr<InternalIterator> regular_iter( | |
11fdf7f2 TL |
263 | reader2.NewIterator<DataBlockIter>(BytewiseComparator(), |
264 | BytewiseComparator())); | |
7c673cae FG |
265 | |
266 | // Seek existent keys | |
267 | for (size_t i = 0; i < keys.size(); i++) { | |
268 | regular_iter->Seek(keys[i]); | |
269 | ASSERT_OK(regular_iter->status()); | |
270 | ASSERT_TRUE(regular_iter->Valid()); | |
271 | ||
272 | Slice v = regular_iter->value(); | |
273 | ASSERT_EQ(v.ToString().compare(values[i]), 0); | |
274 | } | |
275 | ||
276 | // Seek non-existent keys. | |
277 | // For hash index, if no key with a given prefix is not found, iterator will | |
278 | // simply be set as invalid; whereas the binary search based iterator will | |
279 | // return the one that is closest. | |
280 | for (int i = 1; i < max_key - 1; i += 2) { | |
281 | auto key = GenerateKey(i, 0, 0, nullptr); | |
282 | regular_iter->Seek(key); | |
283 | ASSERT_TRUE(regular_iter->Valid()); | |
284 | } | |
285 | } | |
286 | ||
287 | // In this test case, no two key share same prefix. | |
288 | TEST_F(BlockTest, SimpleIndexHash) { | |
289 | const int kMaxKey = 100000; | |
290 | std::vector<std::string> keys; | |
291 | std::vector<std::string> values; | |
292 | GenerateRandomKVs(&keys, &values, 0 /* first key id */, | |
293 | kMaxKey /* last key id */, 2 /* step */, | |
294 | 8 /* padding size (8 bytes randomly generated suffix) */); | |
295 | ||
296 | std::unique_ptr<BlockBuilder> builder; | |
297 | auto contents = GetBlockContents(&builder, keys, values); | |
298 | ||
299 | CheckBlockContents(std::move(contents), kMaxKey, keys, values); | |
300 | } | |
301 | ||
302 | TEST_F(BlockTest, IndexHashWithSharedPrefix) { | |
303 | const int kMaxKey = 100000; | |
304 | // for each prefix, there will be 5 keys starts with it. | |
305 | const int kPrefixGroup = 5; | |
306 | std::vector<std::string> keys; | |
307 | std::vector<std::string> values; | |
308 | // Generate keys with same prefix. | |
309 | GenerateRandomKVs(&keys, &values, 0, // first key id | |
310 | kMaxKey, // last key id | |
311 | 2, // step | |
312 | 10, // padding size, | |
313 | kPrefixGroup); | |
314 | ||
315 | std::unique_ptr<BlockBuilder> builder; | |
316 | auto contents = GetBlockContents(&builder, keys, values, kPrefixGroup); | |
317 | ||
318 | CheckBlockContents(std::move(contents), kMaxKey, keys, values); | |
319 | } | |
320 | ||
321 | // A slow and accurate version of BlockReadAmpBitmap that simply store | |
322 | // all the marked ranges in a set. | |
323 | class BlockReadAmpBitmapSlowAndAccurate { | |
324 | public: | |
325 | void Mark(size_t start_offset, size_t end_offset) { | |
326 | assert(end_offset >= start_offset); | |
7c673cae FG |
327 | marked_ranges_.emplace(end_offset, start_offset); |
328 | } | |
329 | ||
11fdf7f2 TL |
330 | void ResetCheckSequence() { iter_valid_ = false; } |
331 | ||
7c673cae | 332 | // Return true if any byte in this range was Marked |
11fdf7f2 TL |
333 | // This does linear search from the previous position. When calling |
334 | // multiple times, `offset` needs to be incremental to get correct results. | |
335 | // Call ResetCheckSequence() to reset it. | |
336 | bool IsPinMarked(size_t offset) { | |
337 | if (iter_valid_) { | |
338 | // Has existing iterator, try linear search from | |
339 | // the iterator. | |
340 | for (int i = 0; i < 64; i++) { | |
341 | if (offset < iter_->second) { | |
342 | return false; | |
343 | } | |
344 | if (offset <= iter_->first) { | |
345 | return true; | |
346 | } | |
347 | ||
348 | iter_++; | |
349 | if (iter_ == marked_ranges_.end()) { | |
350 | iter_valid_ = false; | |
351 | return false; | |
352 | } | |
353 | } | |
354 | } | |
355 | // Initial call or have linear searched too many times. | |
356 | // Do binary search. | |
357 | iter_ = marked_ranges_.lower_bound( | |
358 | std::make_pair(offset, static_cast<size_t>(0))); | |
359 | if (iter_ == marked_ranges_.end()) { | |
360 | iter_valid_ = false; | |
7c673cae FG |
361 | return false; |
362 | } | |
11fdf7f2 TL |
363 | iter_valid_ = true; |
364 | return offset <= iter_->first && offset >= iter_->second; | |
7c673cae FG |
365 | } |
366 | ||
367 | private: | |
368 | std::set<std::pair<size_t, size_t>> marked_ranges_; | |
11fdf7f2 TL |
369 | std::set<std::pair<size_t, size_t>>::iterator iter_; |
370 | bool iter_valid_ = false; | |
7c673cae FG |
371 | }; |
372 | ||
373 | TEST_F(BlockTest, BlockReadAmpBitmap) { | |
11fdf7f2 TL |
374 | uint32_t pin_offset = 0; |
375 | SyncPoint::GetInstance()->SetCallBack( | |
494da23a TL |
376 | "BlockReadAmpBitmap:rnd", [&pin_offset](void *arg) { |
377 | pin_offset = *(static_cast<uint32_t *>(arg)); | |
378 | }); | |
11fdf7f2 | 379 | SyncPoint::GetInstance()->EnableProcessing(); |
7c673cae | 380 | std::vector<size_t> block_sizes = { |
11fdf7f2 TL |
381 | 1, // 1 byte |
382 | 32, // 32 bytes | |
383 | 61, // 61 bytes | |
384 | 64, // 64 bytes | |
385 | 512, // 0.5 KB | |
386 | 1024, // 1 KB | |
387 | 1024 * 4, // 4 KB | |
388 | 1024 * 10, // 10 KB | |
389 | 1024 * 50, // 50 KB | |
390 | 1024 * 1024 * 4, // 5 MB | |
7c673cae FG |
391 | 777, |
392 | 124653, | |
393 | }; | |
394 | const size_t kBytesPerBit = 64; | |
395 | ||
396 | Random rnd(301); | |
397 | for (size_t block_size : block_sizes) { | |
398 | std::shared_ptr<Statistics> stats = rocksdb::CreateDBStatistics(); | |
399 | BlockReadAmpBitmap read_amp_bitmap(block_size, kBytesPerBit, stats.get()); | |
400 | BlockReadAmpBitmapSlowAndAccurate read_amp_slow_and_accurate; | |
401 | ||
402 | size_t needed_bits = (block_size / kBytesPerBit); | |
403 | if (block_size % kBytesPerBit != 0) { | |
404 | needed_bits++; | |
405 | } | |
7c673cae | 406 | |
11fdf7f2 | 407 | ASSERT_EQ(stats->getTickerCount(READ_AMP_TOTAL_READ_BYTES), block_size); |
7c673cae FG |
408 | |
409 | // Generate some random entries | |
410 | std::vector<size_t> random_entry_offsets; | |
411 | for (int i = 0; i < 1000; i++) { | |
412 | random_entry_offsets.push_back(rnd.Next() % block_size); | |
413 | } | |
414 | std::sort(random_entry_offsets.begin(), random_entry_offsets.end()); | |
415 | auto it = | |
416 | std::unique(random_entry_offsets.begin(), random_entry_offsets.end()); | |
417 | random_entry_offsets.resize( | |
418 | std::distance(random_entry_offsets.begin(), it)); | |
419 | ||
420 | std::vector<std::pair<size_t, size_t>> random_entries; | |
421 | for (size_t i = 0; i < random_entry_offsets.size(); i++) { | |
422 | size_t entry_start = random_entry_offsets[i]; | |
423 | size_t entry_end; | |
424 | if (i + 1 < random_entry_offsets.size()) { | |
425 | entry_end = random_entry_offsets[i + 1] - 1; | |
426 | } else { | |
427 | entry_end = block_size - 1; | |
428 | } | |
429 | random_entries.emplace_back(entry_start, entry_end); | |
430 | } | |
431 | ||
432 | for (size_t i = 0; i < random_entries.size(); i++) { | |
11fdf7f2 | 433 | read_amp_slow_and_accurate.ResetCheckSequence(); |
7c673cae FG |
434 | auto ¤t_entry = random_entries[rnd.Next() % random_entries.size()]; |
435 | ||
436 | read_amp_bitmap.Mark(static_cast<uint32_t>(current_entry.first), | |
437 | static_cast<uint32_t>(current_entry.second)); | |
438 | read_amp_slow_and_accurate.Mark(current_entry.first, | |
439 | current_entry.second); | |
440 | ||
441 | size_t total_bits = 0; | |
11fdf7f2 TL |
442 | for (size_t bit_idx = 0; bit_idx < needed_bits; bit_idx++) { |
443 | total_bits += read_amp_slow_and_accurate.IsPinMarked( | |
494da23a | 444 | bit_idx * kBytesPerBit + pin_offset); |
7c673cae FG |
445 | } |
446 | size_t expected_estimate_useful = total_bits * kBytesPerBit; | |
447 | size_t got_estimate_useful = | |
494da23a | 448 | stats->getTickerCount(READ_AMP_ESTIMATE_USEFUL_BYTES); |
7c673cae FG |
449 | ASSERT_EQ(expected_estimate_useful, got_estimate_useful); |
450 | } | |
451 | } | |
11fdf7f2 TL |
452 | SyncPoint::GetInstance()->DisableProcessing(); |
453 | SyncPoint::GetInstance()->ClearAllCallBacks(); | |
7c673cae FG |
454 | } |
455 | ||
456 | TEST_F(BlockTest, BlockWithReadAmpBitmap) { | |
457 | Random rnd(301); | |
458 | Options options = Options(); | |
459 | std::unique_ptr<InternalKeyComparator> ic; | |
460 | ic.reset(new test::PlainInternalKeyComparator(options.comparator)); | |
461 | ||
462 | std::vector<std::string> keys; | |
463 | std::vector<std::string> values; | |
464 | BlockBuilder builder(16); | |
465 | int num_records = 10000; | |
466 | ||
467 | GenerateRandomKVs(&keys, &values, 0, num_records, 1); | |
468 | // add a bunch of records to a block | |
469 | for (int i = 0; i < num_records; i++) { | |
470 | builder.Add(keys[i], values[i]); | |
471 | } | |
472 | ||
473 | Slice rawblock = builder.Finish(); | |
474 | const size_t kBytesPerBit = 8; | |
475 | ||
476 | // Read the block sequentially using Next() | |
477 | { | |
478 | std::shared_ptr<Statistics> stats = rocksdb::CreateDBStatistics(); | |
479 | ||
480 | // create block reader | |
481 | BlockContents contents; | |
482 | contents.data = rawblock; | |
7c673cae FG |
483 | Block reader(std::move(contents), kDisableGlobalSequenceNumber, |
484 | kBytesPerBit, stats.get()); | |
485 | ||
486 | // read contents of block sequentially | |
487 | size_t read_bytes = 0; | |
11fdf7f2 TL |
488 | DataBlockIter *iter = |
489 | static_cast<DataBlockIter *>(reader.NewIterator<DataBlockIter>( | |
490 | options.comparator, options.comparator, nullptr, stats.get())); | |
7c673cae FG |
491 | for (iter->SeekToFirst(); iter->Valid(); iter->Next()) { |
492 | iter->value(); | |
493 | read_bytes += iter->TEST_CurrentEntrySize(); | |
494 | ||
495 | double semi_acc_read_amp = | |
496 | static_cast<double>(read_bytes) / rawblock.size(); | |
497 | double read_amp = static_cast<double>(stats->getTickerCount( | |
498 | READ_AMP_ESTIMATE_USEFUL_BYTES)) / | |
499 | stats->getTickerCount(READ_AMP_TOTAL_READ_BYTES); | |
500 | ||
501 | // Error in read amplification will be less than 1% if we are reading | |
502 | // sequentially | |
503 | double error_pct = fabs(semi_acc_read_amp - read_amp) * 100; | |
504 | EXPECT_LT(error_pct, 1); | |
505 | } | |
506 | ||
507 | delete iter; | |
508 | } | |
509 | ||
510 | // Read the block sequentially using Seek() | |
511 | { | |
512 | std::shared_ptr<Statistics> stats = rocksdb::CreateDBStatistics(); | |
513 | ||
514 | // create block reader | |
515 | BlockContents contents; | |
516 | contents.data = rawblock; | |
7c673cae FG |
517 | Block reader(std::move(contents), kDisableGlobalSequenceNumber, |
518 | kBytesPerBit, stats.get()); | |
519 | ||
520 | size_t read_bytes = 0; | |
11fdf7f2 TL |
521 | DataBlockIter *iter = |
522 | static_cast<DataBlockIter *>(reader.NewIterator<DataBlockIter>( | |
523 | options.comparator, options.comparator, nullptr, stats.get())); | |
7c673cae FG |
524 | for (int i = 0; i < num_records; i++) { |
525 | Slice k(keys[i]); | |
526 | ||
527 | // search in block for this key | |
528 | iter->Seek(k); | |
529 | iter->value(); | |
530 | read_bytes += iter->TEST_CurrentEntrySize(); | |
531 | ||
532 | double semi_acc_read_amp = | |
533 | static_cast<double>(read_bytes) / rawblock.size(); | |
534 | double read_amp = static_cast<double>(stats->getTickerCount( | |
535 | READ_AMP_ESTIMATE_USEFUL_BYTES)) / | |
536 | stats->getTickerCount(READ_AMP_TOTAL_READ_BYTES); | |
537 | ||
538 | // Error in read amplification will be less than 1% if we are reading | |
539 | // sequentially | |
540 | double error_pct = fabs(semi_acc_read_amp - read_amp) * 100; | |
541 | EXPECT_LT(error_pct, 1); | |
542 | } | |
543 | delete iter; | |
544 | } | |
545 | ||
546 | // Read the block randomly | |
547 | { | |
548 | std::shared_ptr<Statistics> stats = rocksdb::CreateDBStatistics(); | |
549 | ||
550 | // create block reader | |
551 | BlockContents contents; | |
552 | contents.data = rawblock; | |
7c673cae FG |
553 | Block reader(std::move(contents), kDisableGlobalSequenceNumber, |
554 | kBytesPerBit, stats.get()); | |
555 | ||
556 | size_t read_bytes = 0; | |
11fdf7f2 TL |
557 | DataBlockIter *iter = |
558 | static_cast<DataBlockIter *>(reader.NewIterator<DataBlockIter>( | |
559 | options.comparator, options.comparator, nullptr, stats.get())); | |
7c673cae FG |
560 | std::unordered_set<int> read_keys; |
561 | for (int i = 0; i < num_records; i++) { | |
562 | int index = rnd.Uniform(num_records); | |
563 | Slice k(keys[index]); | |
564 | ||
565 | iter->Seek(k); | |
566 | iter->value(); | |
567 | if (read_keys.find(index) == read_keys.end()) { | |
568 | read_keys.insert(index); | |
569 | read_bytes += iter->TEST_CurrentEntrySize(); | |
570 | } | |
571 | ||
572 | double semi_acc_read_amp = | |
573 | static_cast<double>(read_bytes) / rawblock.size(); | |
574 | double read_amp = static_cast<double>(stats->getTickerCount( | |
575 | READ_AMP_ESTIMATE_USEFUL_BYTES)) / | |
576 | stats->getTickerCount(READ_AMP_TOTAL_READ_BYTES); | |
577 | ||
578 | double error_pct = fabs(semi_acc_read_amp - read_amp) * 100; | |
579 | // Error in read amplification will be less than 2% if we are reading | |
580 | // randomly | |
581 | EXPECT_LT(error_pct, 2); | |
582 | } | |
583 | delete iter; | |
584 | } | |
585 | } | |
586 | ||
587 | TEST_F(BlockTest, ReadAmpBitmapPow2) { | |
588 | std::shared_ptr<Statistics> stats = rocksdb::CreateDBStatistics(); | |
589 | ASSERT_EQ(BlockReadAmpBitmap(100, 1, stats.get()).GetBytesPerBit(), 1); | |
590 | ASSERT_EQ(BlockReadAmpBitmap(100, 2, stats.get()).GetBytesPerBit(), 2); | |
591 | ASSERT_EQ(BlockReadAmpBitmap(100, 4, stats.get()).GetBytesPerBit(), 4); | |
592 | ASSERT_EQ(BlockReadAmpBitmap(100, 8, stats.get()).GetBytesPerBit(), 8); | |
593 | ASSERT_EQ(BlockReadAmpBitmap(100, 16, stats.get()).GetBytesPerBit(), 16); | |
594 | ASSERT_EQ(BlockReadAmpBitmap(100, 32, stats.get()).GetBytesPerBit(), 32); | |
595 | ||
596 | ASSERT_EQ(BlockReadAmpBitmap(100, 3, stats.get()).GetBytesPerBit(), 2); | |
597 | ASSERT_EQ(BlockReadAmpBitmap(100, 7, stats.get()).GetBytesPerBit(), 4); | |
598 | ASSERT_EQ(BlockReadAmpBitmap(100, 11, stats.get()).GetBytesPerBit(), 8); | |
599 | ASSERT_EQ(BlockReadAmpBitmap(100, 17, stats.get()).GetBytesPerBit(), 16); | |
600 | ASSERT_EQ(BlockReadAmpBitmap(100, 33, stats.get()).GetBytesPerBit(), 32); | |
601 | ASSERT_EQ(BlockReadAmpBitmap(100, 35, stats.get()).GetBytesPerBit(), 32); | |
602 | } | |
603 | ||
604 | } // namespace rocksdb | |
605 | ||
606 | int main(int argc, char **argv) { | |
607 | ::testing::InitGoogleTest(&argc, argv); | |
608 | return RUN_ALL_TESTS(); | |
609 | } |