ceph/src/rocksdb/table/cuckoo_table_builder_test.cc

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