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