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 #ifndef ROCKSDB_LITE
7
8 #include <vector>
9 #include <string>
10 #include <map>
11 #include <utility>
12
13 #include "file/random_access_file_reader.h"
14 #include "file/writable_file_writer.h"
15 #include "table/cuckoo/cuckoo_table_builder.h"
16 #include "table/meta_blocks.h"
17 #include "test_util/testharness.h"
18 #include "test_util/testutil.h"
19
20 namespace ROCKSDB_NAMESPACE {
21 extern const uint64_t kCuckooTableMagicNumber;
22
23 namespace {
24 std::unordered_map<std::string, std::vector<uint64_t>> hash_map;
25
GetSliceHash(const Slice & s,uint32_t index,uint64_t)26 uint64_t GetSliceHash(const Slice& s, uint32_t index,
27 uint64_t /*max_num_buckets*/) {
28 return hash_map[s.ToString()][index];
29 }
30 } // namespace
31
32 class CuckooBuilderTest : public testing::Test {
33 public:
CuckooBuilderTest()34 CuckooBuilderTest() {
35 env_ = Env::Default();
36 Options options;
37 options.allow_mmap_reads = true;
38 env_options_ = EnvOptions(options);
39 }
40
CheckFileContents(const std::vector<std::string> & keys,const std::vector<std::string> & values,const std::vector<uint64_t> & expected_locations,std::string expected_unused_bucket,uint64_t expected_table_size,uint32_t expected_num_hash_func,bool expected_is_last_level,uint32_t expected_cuckoo_block_size=1)41 void CheckFileContents(const std::vector<std::string>& keys,
42 const std::vector<std::string>& values,
43 const std::vector<uint64_t>& expected_locations,
44 std::string expected_unused_bucket, uint64_t expected_table_size,
45 uint32_t expected_num_hash_func, bool expected_is_last_level,
46 uint32_t expected_cuckoo_block_size = 1) {
47 uint64_t num_deletions = 0;
48 for (const auto& key : keys) {
49 ParsedInternalKey parsed;
50 if (ParseInternalKey(key, &parsed) && parsed.type == kTypeDeletion) {
51 num_deletions++;
52 }
53 }
54 // Read file
55 std::unique_ptr<RandomAccessFile> read_file;
56 ASSERT_OK(env_->NewRandomAccessFile(fname, &read_file, env_options_));
57 uint64_t read_file_size;
58 ASSERT_OK(env_->GetFileSize(fname, &read_file_size));
59
60 // @lint-ignore TXT2 T25377293 Grandfathered in
61 Options options;
62 options.allow_mmap_reads = true;
63 ImmutableCFOptions ioptions(options);
64
65 // Assert Table Properties.
66 TableProperties* props = nullptr;
67 std::unique_ptr<RandomAccessFileReader> file_reader(
68 new RandomAccessFileReader(NewLegacyRandomAccessFileWrapper(read_file),
69 fname));
70 ASSERT_OK(ReadTableProperties(file_reader.get(), read_file_size,
71 kCuckooTableMagicNumber, ioptions,
72 &props, true /* compression_type_missing */));
73 // Check unused bucket.
74 std::string unused_key = props->user_collected_properties[
75 CuckooTablePropertyNames::kEmptyKey];
76 ASSERT_EQ(expected_unused_bucket.substr(0,
77 props->fixed_key_len), unused_key);
78
79 uint64_t value_len_found =
80 *reinterpret_cast<const uint64_t*>(props->user_collected_properties[
81 CuckooTablePropertyNames::kValueLength].data());
82 ASSERT_EQ(values.empty() ? 0 : values[0].size(), value_len_found);
83 ASSERT_EQ(props->raw_value_size, values.size()*value_len_found);
84 const uint64_t table_size =
85 *reinterpret_cast<const uint64_t*>(props->user_collected_properties[
86 CuckooTablePropertyNames::kHashTableSize].data());
87 ASSERT_EQ(expected_table_size, table_size);
88 const uint32_t num_hash_func_found =
89 *reinterpret_cast<const uint32_t*>(props->user_collected_properties[
90 CuckooTablePropertyNames::kNumHashFunc].data());
91 ASSERT_EQ(expected_num_hash_func, num_hash_func_found);
92 const uint32_t cuckoo_block_size =
93 *reinterpret_cast<const uint32_t*>(props->user_collected_properties[
94 CuckooTablePropertyNames::kCuckooBlockSize].data());
95 ASSERT_EQ(expected_cuckoo_block_size, cuckoo_block_size);
96 const bool is_last_level_found =
97 *reinterpret_cast<const bool*>(props->user_collected_properties[
98 CuckooTablePropertyNames::kIsLastLevel].data());
99 ASSERT_EQ(expected_is_last_level, is_last_level_found);
100
101 ASSERT_EQ(props->num_entries, keys.size());
102 ASSERT_EQ(props->num_deletions, num_deletions);
103 ASSERT_EQ(props->fixed_key_len, keys.empty() ? 0 : keys[0].size());
104 ASSERT_EQ(props->data_size, expected_unused_bucket.size() *
105 (expected_table_size + expected_cuckoo_block_size - 1));
106 ASSERT_EQ(props->raw_key_size, keys.size()*props->fixed_key_len);
107 ASSERT_EQ(props->column_family_id, 0);
108 ASSERT_EQ(props->column_family_name, kDefaultColumnFamilyName);
109 delete props;
110
111 // Check contents of the bucket.
112 std::vector<bool> keys_found(keys.size(), false);
113 size_t bucket_size = expected_unused_bucket.size();
114 for (uint32_t i = 0; i < table_size + cuckoo_block_size - 1; ++i) {
115 Slice read_slice;
116 ASSERT_OK(file_reader->Read(i * bucket_size, bucket_size, &read_slice,
117 nullptr));
118 size_t key_idx =
119 std::find(expected_locations.begin(), expected_locations.end(), i) -
120 expected_locations.begin();
121 if (key_idx == keys.size()) {
122 // i is not one of the expected locations. Empty bucket.
123 if (read_slice.data() == nullptr) {
124 ASSERT_EQ(0, expected_unused_bucket.size());
125 } else {
126 ASSERT_EQ(read_slice.compare(expected_unused_bucket), 0);
127 }
128 } else {
129 keys_found[key_idx] = true;
130 ASSERT_EQ(read_slice.compare(keys[key_idx] + values[key_idx]), 0);
131 }
132 }
133 for (auto key_found : keys_found) {
134 // Check that all keys wereReader found.
135 ASSERT_TRUE(key_found);
136 }
137 }
138
GetInternalKey(Slice user_key,bool zero_seqno,ValueType type=kTypeValue)139 std::string GetInternalKey(Slice user_key, bool zero_seqno,
140 ValueType type = kTypeValue) {
141 IterKey ikey;
142 ikey.SetInternalKey(user_key, zero_seqno ? 0 : 1000, type);
143 return ikey.GetInternalKey().ToString();
144 }
145
NextPowOf2(uint64_t num)146 uint64_t NextPowOf2(uint64_t num) {
147 uint64_t n = 2;
148 while (n <= num) {
149 n *= 2;
150 }
151 return n;
152 }
153
GetExpectedTableSize(uint64_t num)154 uint64_t GetExpectedTableSize(uint64_t num) {
155 return NextPowOf2(static_cast<uint64_t>(num / kHashTableRatio));
156 }
157
158
159 Env* env_;
160 EnvOptions env_options_;
161 std::string fname;
162 const double kHashTableRatio = 0.9;
163 };
164
TEST_F(CuckooBuilderTest,SuccessWithEmptyFile)165 TEST_F(CuckooBuilderTest, SuccessWithEmptyFile) {
166 std::unique_ptr<WritableFile> writable_file;
167 fname = test::PerThreadDBPath("EmptyFile");
168 ASSERT_OK(env_->NewWritableFile(fname, &writable_file, env_options_));
169 std::unique_ptr<WritableFileWriter> file_writer(new WritableFileWriter(
170 NewLegacyWritableFileWrapper(std::move(writable_file)), fname,
171 EnvOptions()));
172 CuckooTableBuilder builder(file_writer.get(), kHashTableRatio, 4, 100,
173 BytewiseComparator(), 1, false, false,
174 GetSliceHash, 0 /* column_family_id */,
175 kDefaultColumnFamilyName);
176 ASSERT_OK(builder.status());
177 ASSERT_EQ(0UL, builder.FileSize());
178 ASSERT_OK(builder.Finish());
179 ASSERT_OK(file_writer->Close());
180 CheckFileContents({}, {}, {}, "", 2, 2, false);
181 }
182
TEST_F(CuckooBuilderTest,WriteSuccessNoCollisionFullKey)183 TEST_F(CuckooBuilderTest, WriteSuccessNoCollisionFullKey) {
184 for (auto type : {kTypeValue, kTypeDeletion}) {
185 uint32_t num_hash_fun = 4;
186 std::vector<std::string> user_keys = {"key01", "key02", "key03", "key04"};
187 std::vector<std::string> values;
188 if (type == kTypeValue) {
189 values = {"v01", "v02", "v03", "v04"};
190 } else {
191 values = {"", "", "", ""};
192 }
193 // Need to have a temporary variable here as VS compiler does not currently
194 // support operator= with initializer_list as a parameter
195 std::unordered_map<std::string, std::vector<uint64_t>> hm = {
196 {user_keys[0], {0, 1, 2, 3}},
197 {user_keys[1], {1, 2, 3, 4}},
198 {user_keys[2], {2, 3, 4, 5}},
199 {user_keys[3], {3, 4, 5, 6}}};
200 hash_map = std::move(hm);
201
202 std::vector<uint64_t> expected_locations = {0, 1, 2, 3};
203 std::vector<std::string> keys;
204 for (auto& user_key : user_keys) {
205 keys.push_back(GetInternalKey(user_key, false, type));
206 }
207 uint64_t expected_table_size = GetExpectedTableSize(keys.size());
208
209 std::unique_ptr<WritableFile> writable_file;
210 fname = test::PerThreadDBPath("NoCollisionFullKey");
211 ASSERT_OK(env_->NewWritableFile(fname, &writable_file, env_options_));
212 std::unique_ptr<WritableFileWriter> file_writer(new WritableFileWriter(
213 NewLegacyWritableFileWrapper(std::move(writable_file)), fname,
214 EnvOptions()));
215 CuckooTableBuilder builder(file_writer.get(), kHashTableRatio, num_hash_fun,
216 100, BytewiseComparator(), 1, false, false,
217 GetSliceHash, 0 /* column_family_id */,
218 kDefaultColumnFamilyName);
219 ASSERT_OK(builder.status());
220 for (uint32_t i = 0; i < user_keys.size(); i++) {
221 builder.Add(Slice(keys[i]), Slice(values[i]));
222 ASSERT_EQ(builder.NumEntries(), i + 1);
223 ASSERT_OK(builder.status());
224 }
225 size_t bucket_size = keys[0].size() + values[0].size();
226 ASSERT_EQ(expected_table_size * bucket_size - 1, builder.FileSize());
227 ASSERT_OK(builder.Finish());
228 ASSERT_OK(file_writer->Close());
229 ASSERT_LE(expected_table_size * bucket_size, builder.FileSize());
230
231 std::string expected_unused_bucket = GetInternalKey("key00", true);
232 expected_unused_bucket += std::string(values[0].size(), 'a');
233 CheckFileContents(keys, values, expected_locations, expected_unused_bucket,
234 expected_table_size, 2, false);
235 }
236 }
237
TEST_F(CuckooBuilderTest,WriteSuccessWithCollisionFullKey)238 TEST_F(CuckooBuilderTest, WriteSuccessWithCollisionFullKey) {
239 uint32_t num_hash_fun = 4;
240 std::vector<std::string> user_keys = {"key01", "key02", "key03", "key04"};
241 std::vector<std::string> values = {"v01", "v02", "v03", "v04"};
242 // Need to have a temporary variable here as VS compiler does not currently
243 // support operator= with initializer_list as a parameter
244 std::unordered_map<std::string, std::vector<uint64_t>> hm = {
245 {user_keys[0], {0, 1, 2, 3}},
246 {user_keys[1], {0, 1, 2, 3}},
247 {user_keys[2], {0, 1, 2, 3}},
248 {user_keys[3], {0, 1, 2, 3}},
249 };
250 hash_map = std::move(hm);
251
252 std::vector<uint64_t> expected_locations = {0, 1, 2, 3};
253 std::vector<std::string> keys;
254 for (auto& user_key : user_keys) {
255 keys.push_back(GetInternalKey(user_key, false));
256 }
257 uint64_t expected_table_size = GetExpectedTableSize(keys.size());
258
259 std::unique_ptr<WritableFile> writable_file;
260 fname = test::PerThreadDBPath("WithCollisionFullKey");
261 ASSERT_OK(env_->NewWritableFile(fname, &writable_file, env_options_));
262 std::unique_ptr<WritableFileWriter> file_writer(new WritableFileWriter(
263 NewLegacyWritableFileWrapper(std::move(writable_file)), fname,
264 EnvOptions()));
265 CuckooTableBuilder builder(file_writer.get(), kHashTableRatio, num_hash_fun,
266 100, BytewiseComparator(), 1, false, false,
267 GetSliceHash, 0 /* column_family_id */,
268 kDefaultColumnFamilyName);
269 ASSERT_OK(builder.status());
270 for (uint32_t i = 0; i < user_keys.size(); i++) {
271 builder.Add(Slice(keys[i]), Slice(values[i]));
272 ASSERT_EQ(builder.NumEntries(), i + 1);
273 ASSERT_OK(builder.status());
274 }
275 size_t bucket_size = keys[0].size() + values[0].size();
276 ASSERT_EQ(expected_table_size * bucket_size - 1, builder.FileSize());
277 ASSERT_OK(builder.Finish());
278 ASSERT_OK(file_writer->Close());
279 ASSERT_LE(expected_table_size * bucket_size, builder.FileSize());
280
281 std::string expected_unused_bucket = GetInternalKey("key00", true);
282 expected_unused_bucket += std::string(values[0].size(), 'a');
283 CheckFileContents(keys, values, expected_locations,
284 expected_unused_bucket, expected_table_size, 4, false);
285 }
286
TEST_F(CuckooBuilderTest,WriteSuccessWithCollisionAndCuckooBlock)287 TEST_F(CuckooBuilderTest, WriteSuccessWithCollisionAndCuckooBlock) {
288 uint32_t num_hash_fun = 4;
289 std::vector<std::string> user_keys = {"key01", "key02", "key03", "key04"};
290 std::vector<std::string> values = {"v01", "v02", "v03", "v04"};
291 // Need to have a temporary variable here as VS compiler does not currently
292 // support operator= with initializer_list as a parameter
293 std::unordered_map<std::string, std::vector<uint64_t>> hm = {
294 {user_keys[0], {0, 1, 2, 3}},
295 {user_keys[1], {0, 1, 2, 3}},
296 {user_keys[2], {0, 1, 2, 3}},
297 {user_keys[3], {0, 1, 2, 3}},
298 };
299 hash_map = std::move(hm);
300
301 std::vector<uint64_t> expected_locations = {0, 1, 2, 3};
302 std::vector<std::string> keys;
303 for (auto& user_key : user_keys) {
304 keys.push_back(GetInternalKey(user_key, false));
305 }
306 uint64_t expected_table_size = GetExpectedTableSize(keys.size());
307
308 std::unique_ptr<WritableFile> writable_file;
309 uint32_t cuckoo_block_size = 2;
310 fname = test::PerThreadDBPath("WithCollisionFullKey2");
311 ASSERT_OK(env_->NewWritableFile(fname, &writable_file, env_options_));
312 std::unique_ptr<WritableFileWriter> file_writer(new WritableFileWriter(
313 NewLegacyWritableFileWrapper(std::move(writable_file)), fname,
314 EnvOptions()));
315 CuckooTableBuilder builder(
316 file_writer.get(), kHashTableRatio, num_hash_fun, 100,
317 BytewiseComparator(), cuckoo_block_size, false, false, GetSliceHash,
318 0 /* column_family_id */, kDefaultColumnFamilyName);
319 ASSERT_OK(builder.status());
320 for (uint32_t i = 0; i < user_keys.size(); i++) {
321 builder.Add(Slice(keys[i]), Slice(values[i]));
322 ASSERT_EQ(builder.NumEntries(), i + 1);
323 ASSERT_OK(builder.status());
324 }
325 size_t bucket_size = keys[0].size() + values[0].size();
326 ASSERT_EQ(expected_table_size * bucket_size - 1, builder.FileSize());
327 ASSERT_OK(builder.Finish());
328 ASSERT_OK(file_writer->Close());
329 ASSERT_LE(expected_table_size * bucket_size, builder.FileSize());
330
331 std::string expected_unused_bucket = GetInternalKey("key00", true);
332 expected_unused_bucket += std::string(values[0].size(), 'a');
333 CheckFileContents(keys, values, expected_locations,
334 expected_unused_bucket, expected_table_size, 3, false, cuckoo_block_size);
335 }
336
TEST_F(CuckooBuilderTest,WithCollisionPathFullKey)337 TEST_F(CuckooBuilderTest, WithCollisionPathFullKey) {
338 // Have two hash functions. Insert elements with overlapping hashes.
339 // Finally insert an element with hash value somewhere in the middle
340 // so that it displaces all the elements after that.
341 uint32_t num_hash_fun = 2;
342 std::vector<std::string> user_keys = {"key01", "key02", "key03",
343 "key04", "key05"};
344 std::vector<std::string> values = {"v01", "v02", "v03", "v04", "v05"};
345 // Need to have a temporary variable here as VS compiler does not currently
346 // support operator= with initializer_list as a parameter
347 std::unordered_map<std::string, std::vector<uint64_t>> hm = {
348 {user_keys[0], {0, 1}},
349 {user_keys[1], {1, 2}},
350 {user_keys[2], {2, 3}},
351 {user_keys[3], {3, 4}},
352 {user_keys[4], {0, 2}},
353 };
354 hash_map = std::move(hm);
355
356 std::vector<uint64_t> expected_locations = {0, 1, 3, 4, 2};
357 std::vector<std::string> keys;
358 for (auto& user_key : user_keys) {
359 keys.push_back(GetInternalKey(user_key, false));
360 }
361 uint64_t expected_table_size = GetExpectedTableSize(keys.size());
362
363 std::unique_ptr<WritableFile> writable_file;
364 fname = test::PerThreadDBPath("WithCollisionPathFullKey");
365 ASSERT_OK(env_->NewWritableFile(fname, &writable_file, env_options_));
366 std::unique_ptr<WritableFileWriter> file_writer(new WritableFileWriter(
367 NewLegacyWritableFileWrapper(std::move(writable_file)), fname,
368 EnvOptions()));
369 CuckooTableBuilder builder(file_writer.get(), kHashTableRatio, num_hash_fun,
370 100, BytewiseComparator(), 1, false, false,
371 GetSliceHash, 0 /* column_family_id */,
372 kDefaultColumnFamilyName);
373 ASSERT_OK(builder.status());
374 for (uint32_t i = 0; i < user_keys.size(); i++) {
375 builder.Add(Slice(keys[i]), Slice(values[i]));
376 ASSERT_EQ(builder.NumEntries(), i + 1);
377 ASSERT_OK(builder.status());
378 }
379 size_t bucket_size = keys[0].size() + values[0].size();
380 ASSERT_EQ(expected_table_size * bucket_size - 1, builder.FileSize());
381 ASSERT_OK(builder.Finish());
382 ASSERT_OK(file_writer->Close());
383 ASSERT_LE(expected_table_size * bucket_size, builder.FileSize());
384
385 std::string expected_unused_bucket = GetInternalKey("key00", true);
386 expected_unused_bucket += std::string(values[0].size(), 'a');
387 CheckFileContents(keys, values, expected_locations,
388 expected_unused_bucket, expected_table_size, 2, false);
389 }
390
TEST_F(CuckooBuilderTest,WithCollisionPathFullKeyAndCuckooBlock)391 TEST_F(CuckooBuilderTest, WithCollisionPathFullKeyAndCuckooBlock) {
392 uint32_t num_hash_fun = 2;
393 std::vector<std::string> user_keys = {"key01", "key02", "key03",
394 "key04", "key05"};
395 std::vector<std::string> values = {"v01", "v02", "v03", "v04", "v05"};
396 // Need to have a temporary variable here as VS compiler does not currently
397 // support operator= with initializer_list as a parameter
398 std::unordered_map<std::string, std::vector<uint64_t>> hm = {
399 {user_keys[0], {0, 1}},
400 {user_keys[1], {1, 2}},
401 {user_keys[2], {3, 4}},
402 {user_keys[3], {4, 5}},
403 {user_keys[4], {0, 3}},
404 };
405 hash_map = std::move(hm);
406
407 std::vector<uint64_t> expected_locations = {2, 1, 3, 4, 0};
408 std::vector<std::string> keys;
409 for (auto& user_key : user_keys) {
410 keys.push_back(GetInternalKey(user_key, false));
411 }
412 uint64_t expected_table_size = GetExpectedTableSize(keys.size());
413
414 std::unique_ptr<WritableFile> writable_file;
415 fname = test::PerThreadDBPath("WithCollisionPathFullKeyAndCuckooBlock");
416 ASSERT_OK(env_->NewWritableFile(fname, &writable_file, env_options_));
417 std::unique_ptr<WritableFileWriter> file_writer(new WritableFileWriter(
418 NewLegacyWritableFileWrapper(std::move(writable_file)), fname,
419 EnvOptions()));
420 CuckooTableBuilder builder(file_writer.get(), kHashTableRatio, num_hash_fun,
421 100, BytewiseComparator(), 2, false, false,
422 GetSliceHash, 0 /* column_family_id */,
423 kDefaultColumnFamilyName);
424 ASSERT_OK(builder.status());
425 for (uint32_t i = 0; i < user_keys.size(); i++) {
426 builder.Add(Slice(keys[i]), Slice(values[i]));
427 ASSERT_EQ(builder.NumEntries(), i + 1);
428 ASSERT_OK(builder.status());
429 }
430 size_t bucket_size = keys[0].size() + values[0].size();
431 ASSERT_EQ(expected_table_size * bucket_size - 1, builder.FileSize());
432 ASSERT_OK(builder.Finish());
433 ASSERT_OK(file_writer->Close());
434 ASSERT_LE(expected_table_size * bucket_size, builder.FileSize());
435
436 std::string expected_unused_bucket = GetInternalKey("key00", true);
437 expected_unused_bucket += std::string(values[0].size(), 'a');
438 CheckFileContents(keys, values, expected_locations,
439 expected_unused_bucket, expected_table_size, 2, false, 2);
440 }
441
TEST_F(CuckooBuilderTest,WriteSuccessNoCollisionUserKey)442 TEST_F(CuckooBuilderTest, WriteSuccessNoCollisionUserKey) {
443 uint32_t num_hash_fun = 4;
444 std::vector<std::string> user_keys = {"key01", "key02", "key03", "key04"};
445 std::vector<std::string> values = {"v01", "v02", "v03", "v04"};
446 // Need to have a temporary variable here as VS compiler does not currently
447 // support operator= with initializer_list as a parameter
448 std::unordered_map<std::string, std::vector<uint64_t>> hm = {
449 {user_keys[0], {0, 1, 2, 3}},
450 {user_keys[1], {1, 2, 3, 4}},
451 {user_keys[2], {2, 3, 4, 5}},
452 {user_keys[3], {3, 4, 5, 6}}};
453 hash_map = std::move(hm);
454
455 std::vector<uint64_t> expected_locations = {0, 1, 2, 3};
456 uint64_t expected_table_size = GetExpectedTableSize(user_keys.size());
457
458 std::unique_ptr<WritableFile> writable_file;
459 fname = test::PerThreadDBPath("NoCollisionUserKey");
460 ASSERT_OK(env_->NewWritableFile(fname, &writable_file, env_options_));
461 std::unique_ptr<WritableFileWriter> file_writer(new WritableFileWriter(
462 NewLegacyWritableFileWrapper(std::move(writable_file)), fname,
463 EnvOptions()));
464 CuckooTableBuilder builder(file_writer.get(), kHashTableRatio, num_hash_fun,
465 100, BytewiseComparator(), 1, false, false,
466 GetSliceHash, 0 /* column_family_id */,
467 kDefaultColumnFamilyName);
468 ASSERT_OK(builder.status());
469 for (uint32_t i = 0; i < user_keys.size(); i++) {
470 builder.Add(Slice(GetInternalKey(user_keys[i], true)), Slice(values[i]));
471 ASSERT_EQ(builder.NumEntries(), i + 1);
472 ASSERT_OK(builder.status());
473 }
474 size_t bucket_size = user_keys[0].size() + values[0].size();
475 ASSERT_EQ(expected_table_size * bucket_size - 1, builder.FileSize());
476 ASSERT_OK(builder.Finish());
477 ASSERT_OK(file_writer->Close());
478 ASSERT_LE(expected_table_size * bucket_size, builder.FileSize());
479
480 std::string expected_unused_bucket = "key00";
481 expected_unused_bucket += std::string(values[0].size(), 'a');
482 CheckFileContents(user_keys, values, expected_locations,
483 expected_unused_bucket, expected_table_size, 2, true);
484 }
485
TEST_F(CuckooBuilderTest,WriteSuccessWithCollisionUserKey)486 TEST_F(CuckooBuilderTest, WriteSuccessWithCollisionUserKey) {
487 uint32_t num_hash_fun = 4;
488 std::vector<std::string> user_keys = {"key01", "key02", "key03", "key04"};
489 std::vector<std::string> values = {"v01", "v02", "v03", "v04"};
490 // Need to have a temporary variable here as VS compiler does not currently
491 // support operator= with initializer_list as a parameter
492 std::unordered_map<std::string, std::vector<uint64_t>> hm = {
493 {user_keys[0], {0, 1, 2, 3}},
494 {user_keys[1], {0, 1, 2, 3}},
495 {user_keys[2], {0, 1, 2, 3}},
496 {user_keys[3], {0, 1, 2, 3}},
497 };
498 hash_map = std::move(hm);
499
500 std::vector<uint64_t> expected_locations = {0, 1, 2, 3};
501 uint64_t expected_table_size = GetExpectedTableSize(user_keys.size());
502
503 std::unique_ptr<WritableFile> writable_file;
504 fname = test::PerThreadDBPath("WithCollisionUserKey");
505 ASSERT_OK(env_->NewWritableFile(fname, &writable_file, env_options_));
506 std::unique_ptr<WritableFileWriter> file_writer(new WritableFileWriter(
507 NewLegacyWritableFileWrapper(std::move(writable_file)), fname,
508 EnvOptions()));
509 CuckooTableBuilder builder(file_writer.get(), kHashTableRatio, num_hash_fun,
510 100, BytewiseComparator(), 1, false, false,
511 GetSliceHash, 0 /* column_family_id */,
512 kDefaultColumnFamilyName);
513 ASSERT_OK(builder.status());
514 for (uint32_t i = 0; i < user_keys.size(); i++) {
515 builder.Add(Slice(GetInternalKey(user_keys[i], true)), Slice(values[i]));
516 ASSERT_EQ(builder.NumEntries(), i + 1);
517 ASSERT_OK(builder.status());
518 }
519 size_t bucket_size = user_keys[0].size() + values[0].size();
520 ASSERT_EQ(expected_table_size * bucket_size - 1, builder.FileSize());
521 ASSERT_OK(builder.Finish());
522 ASSERT_OK(file_writer->Close());
523 ASSERT_LE(expected_table_size * bucket_size, builder.FileSize());
524
525 std::string expected_unused_bucket = "key00";
526 expected_unused_bucket += std::string(values[0].size(), 'a');
527 CheckFileContents(user_keys, values, expected_locations,
528 expected_unused_bucket, expected_table_size, 4, true);
529 }
530
TEST_F(CuckooBuilderTest,WithCollisionPathUserKey)531 TEST_F(CuckooBuilderTest, WithCollisionPathUserKey) {
532 uint32_t num_hash_fun = 2;
533 std::vector<std::string> user_keys = {"key01", "key02", "key03",
534 "key04", "key05"};
535 std::vector<std::string> values = {"v01", "v02", "v03", "v04", "v05"};
536 // Need to have a temporary variable here as VS compiler does not currently
537 // support operator= with initializer_list as a parameter
538 std::unordered_map<std::string, std::vector<uint64_t>> hm = {
539 {user_keys[0], {0, 1}},
540 {user_keys[1], {1, 2}},
541 {user_keys[2], {2, 3}},
542 {user_keys[3], {3, 4}},
543 {user_keys[4], {0, 2}},
544 };
545 hash_map = std::move(hm);
546
547 std::vector<uint64_t> expected_locations = {0, 1, 3, 4, 2};
548 uint64_t expected_table_size = GetExpectedTableSize(user_keys.size());
549
550 std::unique_ptr<WritableFile> writable_file;
551 fname = test::PerThreadDBPath("WithCollisionPathUserKey");
552 ASSERT_OK(env_->NewWritableFile(fname, &writable_file, env_options_));
553 std::unique_ptr<WritableFileWriter> file_writer(new WritableFileWriter(
554 NewLegacyWritableFileWrapper(std::move(writable_file)), fname,
555 EnvOptions()));
556 CuckooTableBuilder builder(file_writer.get(), kHashTableRatio, num_hash_fun,
557 2, BytewiseComparator(), 1, false, false,
558 GetSliceHash, 0 /* column_family_id */,
559 kDefaultColumnFamilyName);
560 ASSERT_OK(builder.status());
561 for (uint32_t i = 0; i < user_keys.size(); i++) {
562 builder.Add(Slice(GetInternalKey(user_keys[i], true)), Slice(values[i]));
563 ASSERT_EQ(builder.NumEntries(), i + 1);
564 ASSERT_OK(builder.status());
565 }
566 size_t bucket_size = user_keys[0].size() + values[0].size();
567 ASSERT_EQ(expected_table_size * bucket_size - 1, builder.FileSize());
568 ASSERT_OK(builder.Finish());
569 ASSERT_OK(file_writer->Close());
570 ASSERT_LE(expected_table_size * bucket_size, builder.FileSize());
571
572 std::string expected_unused_bucket = "key00";
573 expected_unused_bucket += std::string(values[0].size(), 'a');
574 CheckFileContents(user_keys, values, expected_locations,
575 expected_unused_bucket, expected_table_size, 2, true);
576 }
577
TEST_F(CuckooBuilderTest,FailWhenCollisionPathTooLong)578 TEST_F(CuckooBuilderTest, FailWhenCollisionPathTooLong) {
579 // Have two hash functions. Insert elements with overlapping hashes.
580 // Finally try inserting an element with hash value somewhere in the middle
581 // and it should fail because the no. of elements to displace is too high.
582 uint32_t num_hash_fun = 2;
583 std::vector<std::string> user_keys = {"key01", "key02", "key03",
584 "key04", "key05"};
585 // Need to have a temporary variable here as VS compiler does not currently
586 // support operator= with initializer_list as a parameter
587 std::unordered_map<std::string, std::vector<uint64_t>> hm = {
588 {user_keys[0], {0, 1}},
589 {user_keys[1], {1, 2}},
590 {user_keys[2], {2, 3}},
591 {user_keys[3], {3, 4}},
592 {user_keys[4], {0, 1}},
593 };
594 hash_map = std::move(hm);
595
596 std::unique_ptr<WritableFile> writable_file;
597 fname = test::PerThreadDBPath("WithCollisionPathUserKey");
598 ASSERT_OK(env_->NewWritableFile(fname, &writable_file, env_options_));
599 std::unique_ptr<WritableFileWriter> file_writer(new WritableFileWriter(
600 NewLegacyWritableFileWrapper(std::move(writable_file)), fname,
601 EnvOptions()));
602 CuckooTableBuilder builder(file_writer.get(), kHashTableRatio, num_hash_fun,
603 2, BytewiseComparator(), 1, false, false,
604 GetSliceHash, 0 /* column_family_id */,
605 kDefaultColumnFamilyName);
606 ASSERT_OK(builder.status());
607 for (uint32_t i = 0; i < user_keys.size(); i++) {
608 builder.Add(Slice(GetInternalKey(user_keys[i], false)), Slice("value"));
609 ASSERT_EQ(builder.NumEntries(), i + 1);
610 ASSERT_OK(builder.status());
611 }
612 ASSERT_TRUE(builder.Finish().IsNotSupported());
613 ASSERT_OK(file_writer->Close());
614 }
615
TEST_F(CuckooBuilderTest,FailWhenSameKeyInserted)616 TEST_F(CuckooBuilderTest, FailWhenSameKeyInserted) {
617 // Need to have a temporary variable here as VS compiler does not currently
618 // support operator= with initializer_list as a parameter
619 std::unordered_map<std::string, std::vector<uint64_t>> hm = {
620 {"repeatedkey", {0, 1, 2, 3}}};
621 hash_map = std::move(hm);
622 uint32_t num_hash_fun = 4;
623 std::string user_key = "repeatedkey";
624
625 std::unique_ptr<WritableFile> writable_file;
626 fname = test::PerThreadDBPath("FailWhenSameKeyInserted");
627 ASSERT_OK(env_->NewWritableFile(fname, &writable_file, env_options_));
628 std::unique_ptr<WritableFileWriter> file_writer(new WritableFileWriter(
629 NewLegacyWritableFileWrapper(std::move(writable_file)), fname,
630 EnvOptions()));
631 CuckooTableBuilder builder(file_writer.get(), kHashTableRatio, num_hash_fun,
632 100, BytewiseComparator(), 1, false, false,
633 GetSliceHash, 0 /* column_family_id */,
634 kDefaultColumnFamilyName);
635 ASSERT_OK(builder.status());
636
637 builder.Add(Slice(GetInternalKey(user_key, false)), Slice("value1"));
638 ASSERT_EQ(builder.NumEntries(), 1u);
639 ASSERT_OK(builder.status());
640 builder.Add(Slice(GetInternalKey(user_key, true)), Slice("value2"));
641 ASSERT_EQ(builder.NumEntries(), 2u);
642 ASSERT_OK(builder.status());
643
644 ASSERT_TRUE(builder.Finish().IsNotSupported());
645 ASSERT_OK(file_writer->Close());
646 }
647 } // namespace ROCKSDB_NAMESPACE
648
main(int argc,char ** argv)649 int main(int argc, char** argv) {
650 ::testing::InitGoogleTest(&argc, argv);
651 return RUN_ALL_TESTS();
652 }
653
654 #else
655 #include <stdio.h>
656
main(int,char **)657 int main(int /*argc*/, char** /*argv*/) {
658 fprintf(stderr, "SKIPPED as Cuckoo table is not supported in ROCKSDB_LITE\n");
659 return 0;
660 }
661
662 #endif // ROCKSDB_LITE
663