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