plain_table_db_test.cc 39.6 KB
Newer Older
1
//  Copyright (c) 2011-present, Facebook, Inc.  All rights reserved.
Siying Dong's avatar
Siying Dong committed
2
3
4
//  This source code is licensed under both the GPLv2 (found in the
//  COPYING file in the root directory) and Apache 2.0 License
//  (found in the LICENSE.Apache file in the root directory).
Siying Dong's avatar
Siying Dong committed
5
6
7
8
//
// Copyright (c) 2011 The LevelDB Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file. See the AUTHORS file for names of contributors.
9
10
11

#ifndef ROCKSDB_LITE

Siying Dong's avatar
Siying Dong committed
12
13
14
15
16
17
18
19
#include <algorithm>
#include <set>

#include "db/db_impl.h"
#include "db/version_set.h"
#include "db/write_batch_internal.h"
#include "rocksdb/cache.h"
#include "rocksdb/compaction_filter.h"
kailiu's avatar
kailiu committed
20
#include "rocksdb/db.h"
Siying Dong's avatar
Siying Dong committed
21
#include "rocksdb/env.h"
kailiu's avatar
kailiu committed
22
23
24
#include "rocksdb/filter_policy.h"
#include "rocksdb/slice_transform.h"
#include "rocksdb/table.h"
25
#include "table/bloom_block.h"
26
#include "table/meta_blocks.h"
kailiu's avatar
kailiu committed
27
#include "table/plain_table_factory.h"
28
#include "table/plain_table_key_coding.h"
29
#include "table/plain_table_reader.h"
30
31
#include "table/table_builder.h"
#include "util/filename.h"
Siying Dong's avatar
Siying Dong committed
32
33
34
#include "util/hash.h"
#include "util/logging.h"
#include "util/mutexlock.h"
35
#include "util/string_util.h"
Siying Dong's avatar
Siying Dong committed
36
37
38
39
40
41
42
#include "util/testharness.h"
#include "util/testutil.h"
#include "utilities/merge_operators.h"

using std::unique_ptr;

namespace rocksdb {
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
class PlainTableKeyDecoderTest : public testing::Test {};

TEST_F(PlainTableKeyDecoderTest, ReadNonMmap) {
  std::string tmp;
  Random rnd(301);
  const uint32_t kLength = 2222;
  Slice contents = test::RandomString(&rnd, kLength, &tmp);
  test::StringSource* string_source =
      new test::StringSource(contents, 0, false);

  unique_ptr<RandomAccessFileReader> file_reader(
      test::GetRandomAccessFileReader(string_source));
  unique_ptr<PlainTableReaderFileInfo> file_info(new PlainTableReaderFileInfo(
      std::move(file_reader), EnvOptions(), kLength));

  {
    PlainTableFileReader reader(file_info.get());

    const uint32_t kReadSize = 77;
    for (uint32_t pos = 0; pos < kLength; pos += kReadSize) {
      uint32_t read_size = std::min(kLength - pos, kReadSize);
      Slice out;
      ASSERT_TRUE(reader.Read(pos, read_size, &out));
      ASSERT_EQ(0, out.compare(tmp.substr(pos, read_size)));
    }

Dmitri Smirnov's avatar
Dmitri Smirnov committed
69
    ASSERT_LT(uint32_t(string_source->total_reads()), kLength / kReadSize / 2);
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
  }

  std::vector<std::vector<std::pair<uint32_t, uint32_t>>> reads = {
      {{600, 30}, {590, 30}, {600, 20}, {600, 40}},
      {{800, 20}, {100, 20}, {500, 20}, {1500, 20}, {100, 20}, {80, 20}},
      {{1000, 20}, {500, 20}, {1000, 50}},
      {{1000, 20}, {500, 20}, {500, 20}},
      {{1000, 20}, {500, 20}, {200, 20}, {500, 20}},
      {{1000, 20}, {500, 20}, {200, 20}, {1000, 50}},
      {{600, 500}, {610, 20}, {100, 20}},
      {{500, 100}, {490, 100}, {550, 50}},
  };

  std::vector<int> num_file_reads = {2, 6, 2, 2, 4, 3, 2, 2};

  for (size_t i = 0; i < reads.size(); i++) {
    string_source->set_total_reads(0);
    PlainTableFileReader reader(file_info.get());
    for (auto p : reads[i]) {
      Slice out;
      ASSERT_TRUE(reader.Read(p.first, p.second, &out));
      ASSERT_EQ(0, out.compare(tmp.substr(p.first, p.second)));
    }
    ASSERT_EQ(num_file_reads[i], string_source->total_reads());
  }
}
Siying Dong's avatar
Siying Dong committed
96

97
98
class PlainTableDBTest : public testing::Test,
                         public testing::WithParamInterface<bool> {
Kai Liu's avatar
Kai Liu committed
99
100
 protected:
 private:
Siying Dong's avatar
Siying Dong committed
101
102
103
104
  std::string dbname_;
  Env* env_;
  DB* db_;

105
  bool mmap_mode_;
Siying Dong's avatar
Siying Dong committed
106
107
  Options last_options_;

Kai Liu's avatar
Kai Liu committed
108
 public:
109
  PlainTableDBTest() : env_(Env::Default()) {}
Siying Dong's avatar
Siying Dong committed
110
111
112

  ~PlainTableDBTest() {
    delete db_;
113
    EXPECT_OK(DestroyDB(dbname_, Options()));
Siying Dong's avatar
Siying Dong committed
114
115
  }

116
117
118
119
120
121
122
123
  void SetUp() override {
    mmap_mode_ = GetParam();
    dbname_ = test::TmpDir() + "/plain_table_db_test";
    EXPECT_OK(DestroyDB(dbname_, Options()));
    db_ = nullptr;
    Reopen();
  }

Siying Dong's avatar
Siying Dong committed
124
125
126
  // Return the current option configuration.
  Options CurrentOptions() {
    Options options;
Stanislau Hlebik's avatar
Stanislau Hlebik committed
127
128
129
130
131
132
133
134
135

    PlainTableOptions plain_table_options;
    plain_table_options.user_key_len = 0;
    plain_table_options.bloom_bits_per_key = 2;
    plain_table_options.hash_table_ratio = 0.8;
    plain_table_options.index_sparseness = 3;
    plain_table_options.huge_page_tlb_size = 0;
    plain_table_options.encoding_type = kPrefix;
    plain_table_options.full_scan_mode = false;
136
    plain_table_options.store_index_in_file = false;
Stanislau Hlebik's avatar
Stanislau Hlebik committed
137
138

    options.table_factory.reset(NewPlainTableFactory(plain_table_options));
139
    options.memtable_factory.reset(NewHashLinkListRepFactory(4, 0, 3, true));
Stanislau Hlebik's avatar
Stanislau Hlebik committed
140

141
    options.prefix_extractor.reset(NewFixedPrefixTransform(8));
142
    options.allow_mmap_reads = mmap_mode_;
143
    options.allow_concurrent_memtable_write = false;
Siying Dong's avatar
Siying Dong committed
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
    return options;
  }

  DBImpl* dbfull() {
    return reinterpret_cast<DBImpl*>(db_);
  }

  void Reopen(Options* options = nullptr) {
    ASSERT_OK(TryReopen(options));
  }

  void Close() {
    delete db_;
    db_ = nullptr;
  }

  void DestroyAndReopen(Options* options = nullptr) {
    //Destroy using last options
    Destroy(&last_options_);
    ASSERT_OK(TryReopen(options));
  }

  void Destroy(Options* options) {
    delete db_;
    db_ = nullptr;
    ASSERT_OK(DestroyDB(dbname_, *options));
  }

  Status PureReopen(Options* options, DB** db) {
    return DB::Open(*options, dbname_, db);
  }

  Status TryReopen(Options* options = nullptr) {
    delete db_;
    db_ = nullptr;
    Options opts;
    if (options != nullptr) {
      opts = *options;
    } else {
      opts = CurrentOptions();
      opts.create_if_missing = true;
    }
    last_options_ = opts;

    return DB::Open(opts, dbname_, &db_);
  }

  Status Put(const Slice& k, const Slice& v) {
    return db_->Put(WriteOptions(), k, v);
  }

  Status Delete(const std::string& k) {
    return db_->Delete(WriteOptions(), k);
  }

  std::string Get(const std::string& k, const Snapshot* snapshot = nullptr) {
200
    ReadOptions options;
Siying Dong's avatar
Siying Dong committed
201
202
203
204
205
206
207
208
209
210
211
212
213
214
    options.snapshot = snapshot;
    std::string result;
    Status s = db_->Get(options, k, &result);
    if (s.IsNotFound()) {
      result = "NOT_FOUND";
    } else if (!s.ok()) {
      result = s.ToString();
    }
    return result;
  }


  int NumTableFilesAtLevel(int level) {
    std::string property;
215
216
    EXPECT_TRUE(db_->GetProperty(
        "rocksdb.num-files-at-level" + NumberToString(level), &property));
Siying Dong's avatar
Siying Dong committed
217
218
219
220
221
222
    return atoi(property.c_str());
  }

  // Return spread of files per level
  std::string FilesPerLevel() {
    std::string result;
223
    size_t last_non_zero_offset = 0;
Siying Dong's avatar
Siying Dong committed
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
    for (int level = 0; level < db_->NumberLevels(); level++) {
      int f = NumTableFilesAtLevel(level);
      char buf[100];
      snprintf(buf, sizeof(buf), "%s%d", (level ? "," : ""), f);
      result += buf;
      if (f > 0) {
        last_non_zero_offset = result.size();
      }
    }
    result.resize(last_non_zero_offset);
    return result;
  }

  std::string IterStatus(Iterator* iter) {
    std::string result;
    if (iter->Valid()) {
      result = iter->key().ToString() + "->" + iter->value().ToString();
    } else {
      result = "(invalid)";
    }
    return result;
  }
};

248
TEST_P(PlainTableDBTest, Empty) {
Kai Liu's avatar
Kai Liu committed
249
  ASSERT_TRUE(dbfull() != nullptr);
Siying Dong's avatar
Siying Dong committed
250
251
252
  ASSERT_EQ("NOT_FOUND", Get("0000000000000foo"));
}

253
254
extern const uint64_t kPlainTableMagicNumber;

255
256
class TestPlainTableReader : public PlainTableReader {
 public:
Lei Jin's avatar
Lei Jin committed
257
  TestPlainTableReader(const EnvOptions& env_options,
258
                       const InternalKeyComparator& icomparator,
259
260
261
                       EncodingType encoding_type, uint64_t file_size,
                       int bloom_bits_per_key, double hash_table_ratio,
                       size_t index_sparseness,
262
                       const TableProperties* table_properties,
263
                       unique_ptr<RandomAccessFileReader>&& file,
Lei Jin's avatar
Lei Jin committed
264
                       const ImmutableCFOptions& ioptions,
265
266
267
                       bool* expect_bloom_not_match, bool store_index_in_file,
                       uint32_t column_family_id,
                       const std::string& column_family_name)
Lei Jin's avatar
Lei Jin committed
268
      : PlainTableReader(ioptions, std::move(file), env_options, icomparator,
269
                         encoding_type, file_size, table_properties),
270
        expect_bloom_not_match_(expect_bloom_not_match) {
271
    Status s = MmapDataIfNeeded();
272
    EXPECT_TRUE(s.ok());
273
274
275
276

    s = PopulateIndex(const_cast<TableProperties*>(table_properties),
                      bloom_bits_per_key, hash_table_ratio, index_sparseness,
                      2 * 1024 * 1024);
277
    EXPECT_TRUE(s.ok());
278
279

    TableProperties* props = const_cast<TableProperties*>(table_properties);
280
281
    EXPECT_EQ(column_family_id, static_cast<uint32_t>(props->column_family_id));
    EXPECT_EQ(column_family_name, props->column_family_name);
282
283
284
    if (store_index_in_file) {
      auto bloom_version_ptr = props->user_collected_properties.find(
          PlainTablePropertyNames::kBloomVersion);
285
286
      EXPECT_TRUE(bloom_version_ptr != props->user_collected_properties.end());
      EXPECT_EQ(bloom_version_ptr->second, std::string("1"));
Lei Jin's avatar
Lei Jin committed
287
      if (ioptions.bloom_locality > 0) {
288
289
        auto num_blocks_ptr = props->user_collected_properties.find(
            PlainTablePropertyNames::kNumBloomBlocks);
290
        EXPECT_TRUE(num_blocks_ptr != props->user_collected_properties.end());
291
292
      }
    }
293
294
295
296
297
298
299
  }

  virtual ~TestPlainTableReader() {}

 private:
  virtual bool MatchBloom(uint32_t hash) const override {
    bool ret = PlainTableReader::MatchBloom(hash);
300
    if (*expect_bloom_not_match_) {
301
      EXPECT_TRUE(!ret);
302
    } else {
303
      EXPECT_TRUE(ret);
304
    }
305
306
307
308
309
310
311
312
313
    return ret;
  }
  bool* expect_bloom_not_match_;
};

extern const uint64_t kPlainTableMagicNumber;
class TestPlainTableFactory : public PlainTableFactory {
 public:
  explicit TestPlainTableFactory(bool* expect_bloom_not_match,
314
315
316
                                 const PlainTableOptions& options,
                                 uint32_t column_family_id,
                                 std::string column_family_name)
Stanislau Hlebik's avatar
Stanislau Hlebik committed
317
318
319
320
      : PlainTableFactory(options),
        bloom_bits_per_key_(options.bloom_bits_per_key),
        hash_table_ratio_(options.hash_table_ratio),
        index_sparseness_(options.index_sparseness),
321
        store_index_in_file_(options.store_index_in_file),
322
323
324
        expect_bloom_not_match_(expect_bloom_not_match),
        column_family_id_(column_family_id),
        column_family_name_(std::move(column_family_name)) {}
325

326
327
328
329
  Status NewTableReader(
      const TableReaderOptions& table_reader_options,
      unique_ptr<RandomAccessFileReader>&& file, uint64_t file_size,
      unique_ptr<TableReader>* table,
330
      bool prefetch_index_and_filter_in_cache) const override {
331
    TableProperties* props = nullptr;
332
333
    auto s =
        ReadTableProperties(file.get(), file_size, kPlainTableMagicNumber,
334
                            table_reader_options.ioptions, &props);
335
    EXPECT_TRUE(s.ok());
336

337
338
339
    if (store_index_in_file_) {
      BlockHandle bloom_block_handle;
      s = FindMetaBlock(file.get(), file_size, kPlainTableMagicNumber,
340
                        table_reader_options.ioptions,
341
                        BloomBlockBuilder::kBloomBlock, &bloom_block_handle);
342
      EXPECT_TRUE(s.ok());
343
344

      BlockHandle index_block_handle;
345
      s = FindMetaBlock(file.get(), file_size, kPlainTableMagicNumber,
346
                        table_reader_options.ioptions,
347
348
                        PlainTableIndexBuilder::kPlainTableIndexBlock,
                        &index_block_handle);
349
      EXPECT_TRUE(s.ok());
350
351
    }

352
353
354
355
356
357
358
    auto& user_props = props->user_collected_properties;
    auto encoding_type_prop =
        user_props.find(PlainTablePropertyNames::kEncodingType);
    assert(encoding_type_prop != user_props.end());
    EncodingType encoding_type = static_cast<EncodingType>(
        DecodeFixed32(encoding_type_prop->second.c_str()));

359
    std::unique_ptr<PlainTableReader> new_reader(new TestPlainTableReader(
360
361
        table_reader_options.env_options,
        table_reader_options.internal_comparator, encoding_type, file_size,
362
        bloom_bits_per_key_, hash_table_ratio_, index_sparseness_, props,
363
        std::move(file), table_reader_options.ioptions, expect_bloom_not_match_,
364
        store_index_in_file_, column_family_id_, column_family_name_));
365
366
367
368
369
370
371
372
373

    *table = std::move(new_reader);
    return s;
  }

 private:
  int bloom_bits_per_key_;
  double hash_table_ratio_;
  size_t index_sparseness_;
374
  bool store_index_in_file_;
375
  bool* expect_bloom_not_match_;
376
377
  const uint32_t column_family_id_;
  const std::string column_family_name_;
378
};
Siying Dong's avatar
Siying Dong committed
379

380
TEST_P(PlainTableDBTest, Flush) {
381
382
  for (size_t huge_page_tlb_size = 0; huge_page_tlb_size <= 2 * 1024 * 1024;
       huge_page_tlb_size += 2 * 1024 * 1024) {
383
    for (EncodingType encoding_type : {kPlain, kPrefix}) {
384
385
    for (int bloom_bits = 0; bloom_bits <= 117; bloom_bits += 117) {
      for (int total_order = 0; total_order <= 1; total_order++) {
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
        for (int store_index_in_file = 0; store_index_in_file <= 1;
             ++store_index_in_file) {
          Options options = CurrentOptions();
          options.create_if_missing = true;
          // Set only one bucket to force bucket conflict.
          // Test index interval for the same prefix to be 1, 2 and 4
          if (total_order) {
            options.prefix_extractor.reset();

            PlainTableOptions plain_table_options;
            plain_table_options.user_key_len = 0;
            plain_table_options.bloom_bits_per_key = bloom_bits;
            plain_table_options.hash_table_ratio = 0;
            plain_table_options.index_sparseness = 2;
            plain_table_options.huge_page_tlb_size = huge_page_tlb_size;
            plain_table_options.encoding_type = encoding_type;
            plain_table_options.full_scan_mode = false;
            plain_table_options.store_index_in_file = store_index_in_file;

            options.table_factory.reset(
                NewPlainTableFactory(plain_table_options));
          } else {
            PlainTableOptions plain_table_options;
            plain_table_options.user_key_len = 0;
            plain_table_options.bloom_bits_per_key = bloom_bits;
            plain_table_options.hash_table_ratio = 0.75;
            plain_table_options.index_sparseness = 16;
            plain_table_options.huge_page_tlb_size = huge_page_tlb_size;
            plain_table_options.encoding_type = encoding_type;
            plain_table_options.full_scan_mode = false;
            plain_table_options.store_index_in_file = store_index_in_file;

            options.table_factory.reset(
                NewPlainTableFactory(plain_table_options));
          }
          DestroyAndReopen(&options);
422
423
424
425
426
          uint64_t int_num;
          ASSERT_TRUE(dbfull()->GetIntProperty(
              "rocksdb.estimate-table-readers-mem", &int_num));
          ASSERT_EQ(int_num, 0U);

427
428
429
430
431
          ASSERT_OK(Put("1000000000000foo", "v1"));
          ASSERT_OK(Put("0000000000000bar", "v2"));
          ASSERT_OK(Put("1000000000000foo", "v3"));
          dbfull()->TEST_FlushMemTable();

432
433
434
435
          ASSERT_TRUE(dbfull()->GetIntProperty(
              "rocksdb.estimate-table-readers-mem", &int_num));
          ASSERT_GT(int_num, 0U);

436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
          TablePropertiesCollection ptc;
          reinterpret_cast<DB*>(dbfull())->GetPropertiesOfAllTables(&ptc);
          ASSERT_EQ(1U, ptc.size());
          auto row = ptc.begin();
          auto tp = row->second;

          if (!store_index_in_file) {
            ASSERT_EQ(total_order ? "4" : "12",
                      (tp->user_collected_properties)
                          .at("plain_table_hash_table_size"));
            ASSERT_EQ("0", (tp->user_collected_properties)
                               .at("plain_table_sub_index_size"));
          } else {
            ASSERT_EQ("0", (tp->user_collected_properties)
                               .at("plain_table_hash_table_size"));
            ASSERT_EQ("0", (tp->user_collected_properties)
                               .at("plain_table_sub_index_size"));
          }
          ASSERT_EQ("v3", Get("1000000000000foo"));
          ASSERT_EQ("v2", Get("0000000000000bar"));
        }
457
        }
458
459
460
461
462
      }
    }
  }
}

463
TEST_P(PlainTableDBTest, Flush2) {
464
465
  for (size_t huge_page_tlb_size = 0; huge_page_tlb_size <= 2 * 1024 * 1024;
       huge_page_tlb_size += 2 * 1024 * 1024) {
466
    for (EncodingType encoding_type : {kPlain, kPrefix}) {
467
468
    for (int bloom_bits = 0; bloom_bits <= 117; bloom_bits += 117) {
      for (int total_order = 0; total_order <= 1; total_order++) {
469
470
471
472
473
474
475
476
477
        for (int store_index_in_file = 0; store_index_in_file <= 1;
             ++store_index_in_file) {
          if (encoding_type == kPrefix && total_order) {
            continue;
          }
          if (!bloom_bits && store_index_in_file) {
            continue;
          }
          if (total_order && store_index_in_file) {
478
479
          continue;
        }
480
481
482
483
484
        bool expect_bloom_not_match = false;
        Options options = CurrentOptions();
        options.create_if_missing = true;
        // Set only one bucket to force bucket conflict.
        // Test index interval for the same prefix to be 1, 2 and 4
485
        PlainTableOptions plain_table_options;
486
        if (total_order) {
487
          options.prefix_extractor = nullptr;
Stanislau Hlebik's avatar
Stanislau Hlebik committed
488
489
          plain_table_options.hash_table_ratio = 0;
          plain_table_options.index_sparseness = 2;
490
        } else {
Stanislau Hlebik's avatar
Stanislau Hlebik committed
491
492
          plain_table_options.hash_table_ratio = 0.75;
          plain_table_options.index_sparseness = 16;
493
        }
494
495
496
497
498
499
        plain_table_options.user_key_len = kPlainTableVariableLength;
        plain_table_options.bloom_bits_per_key = bloom_bits;
        plain_table_options.huge_page_tlb_size = huge_page_tlb_size;
        plain_table_options.encoding_type = encoding_type;
        plain_table_options.store_index_in_file = store_index_in_file;
        options.table_factory.reset(new TestPlainTableFactory(
500
501
            &expect_bloom_not_match, plain_table_options,
            0 /* column_family_id */, kDefaultColumnFamilyName));
502

503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
        DestroyAndReopen(&options);
        ASSERT_OK(Put("0000000000000bar", "b"));
        ASSERT_OK(Put("1000000000000foo", "v1"));
        dbfull()->TEST_FlushMemTable();

        ASSERT_OK(Put("1000000000000foo", "v2"));
        dbfull()->TEST_FlushMemTable();
        ASSERT_EQ("v2", Get("1000000000000foo"));

        ASSERT_OK(Put("0000000000000eee", "v3"));
        dbfull()->TEST_FlushMemTable();
        ASSERT_EQ("v3", Get("0000000000000eee"));

        ASSERT_OK(Delete("0000000000000bar"));
        dbfull()->TEST_FlushMemTable();
        ASSERT_EQ("NOT_FOUND", Get("0000000000000bar"));

        ASSERT_OK(Put("0000000000000eee", "v5"));
        ASSERT_OK(Put("9000000000000eee", "v5"));
        dbfull()->TEST_FlushMemTable();
        ASSERT_EQ("v5", Get("0000000000000eee"));

        // Test Bloom Filter
        if (bloom_bits > 0) {
          // Neither key nor value should exist.
          expect_bloom_not_match = true;
          ASSERT_EQ("NOT_FOUND", Get("5_not00000000bar"));
          // Key doesn't exist any more but prefix exists.
          if (total_order) {
            ASSERT_EQ("NOT_FOUND", Get("1000000000000not"));
            ASSERT_EQ("NOT_FOUND", Get("0000000000000not"));
          }
          expect_bloom_not_match = false;
536
537
        }
      }
538
      }
539
    }
540
    }
541
  }
Siying Dong's avatar
Siying Dong committed
542
543
}

544
TEST_P(PlainTableDBTest, Iterator) {
545
546
  for (size_t huge_page_tlb_size = 0; huge_page_tlb_size <= 2 * 1024 * 1024;
       huge_page_tlb_size += 2 * 1024 * 1024) {
547
    for (EncodingType encoding_type : {kPlain, kPrefix}) {
548
549
    for (int bloom_bits = 0; bloom_bits <= 117; bloom_bits += 117) {
      for (int total_order = 0; total_order <= 1; total_order++) {
550
551
552
        if (encoding_type == kPrefix && total_order == 1) {
          continue;
        }
553
554
555
556
557
558
559
        bool expect_bloom_not_match = false;
        Options options = CurrentOptions();
        options.create_if_missing = true;
        // Set only one bucket to force bucket conflict.
        // Test index interval for the same prefix to be 1, 2 and 4
        if (total_order) {
          options.prefix_extractor = nullptr;
Stanislau Hlebik's avatar
Stanislau Hlebik committed
560
561
562
563
564
565
566
567
568

          PlainTableOptions plain_table_options;
          plain_table_options.user_key_len = 16;
          plain_table_options.bloom_bits_per_key = bloom_bits;
          plain_table_options.hash_table_ratio = 0;
          plain_table_options.index_sparseness = 2;
          plain_table_options.huge_page_tlb_size = huge_page_tlb_size;
          plain_table_options.encoding_type = encoding_type;

569
          options.table_factory.reset(new TestPlainTableFactory(
570
571
              &expect_bloom_not_match, plain_table_options,
              0 /* column_family_id */, kDefaultColumnFamilyName));
572
        } else {
Stanislau Hlebik's avatar
Stanislau Hlebik committed
573
574
575
576
577
578
579
580
          PlainTableOptions plain_table_options;
          plain_table_options.user_key_len = 16;
          plain_table_options.bloom_bits_per_key = bloom_bits;
          plain_table_options.hash_table_ratio = 0.75;
          plain_table_options.index_sparseness = 16;
          plain_table_options.huge_page_tlb_size = huge_page_tlb_size;
          plain_table_options.encoding_type = encoding_type;

581
          options.table_factory.reset(new TestPlainTableFactory(
582
583
              &expect_bloom_not_match, plain_table_options,
              0 /* column_family_id */, kDefaultColumnFamilyName));
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
        }
        DestroyAndReopen(&options);

        ASSERT_OK(Put("1000000000foo002", "v_2"));
        ASSERT_OK(Put("0000000000000bar", "random"));
        ASSERT_OK(Put("1000000000foo001", "v1"));
        ASSERT_OK(Put("3000000000000bar", "bar_v"));
        ASSERT_OK(Put("1000000000foo003", "v__3"));
        ASSERT_OK(Put("1000000000foo004", "v__4"));
        ASSERT_OK(Put("1000000000foo005", "v__5"));
        ASSERT_OK(Put("1000000000foo007", "v__7"));
        ASSERT_OK(Put("1000000000foo008", "v__8"));
        dbfull()->TEST_FlushMemTable();
        ASSERT_EQ("v1", Get("1000000000foo001"));
        ASSERT_EQ("v__3", Get("1000000000foo003"));
        Iterator* iter = dbfull()->NewIterator(ReadOptions());
        iter->Seek("1000000000foo000");
        ASSERT_TRUE(iter->Valid());
        ASSERT_EQ("1000000000foo001", iter->key().ToString());
        ASSERT_EQ("v1", iter->value().ToString());
604

605
606
607
608
        iter->Next();
        ASSERT_TRUE(iter->Valid());
        ASSERT_EQ("1000000000foo002", iter->key().ToString());
        ASSERT_EQ("v_2", iter->value().ToString());
609

610
611
612
613
        iter->Next();
        ASSERT_TRUE(iter->Valid());
        ASSERT_EQ("1000000000foo003", iter->key().ToString());
        ASSERT_EQ("v__3", iter->value().ToString());
614

615
616
617
618
        iter->Next();
        ASSERT_TRUE(iter->Valid());
        ASSERT_EQ("1000000000foo004", iter->key().ToString());
        ASSERT_EQ("v__4", iter->value().ToString());
619

620
621
622
623
        iter->Seek("3000000000000bar");
        ASSERT_TRUE(iter->Valid());
        ASSERT_EQ("3000000000000bar", iter->key().ToString());
        ASSERT_EQ("bar_v", iter->value().ToString());
624

625
626
627
628
        iter->Seek("1000000000foo000");
        ASSERT_TRUE(iter->Valid());
        ASSERT_EQ("1000000000foo001", iter->key().ToString());
        ASSERT_EQ("v1", iter->value().ToString());
629

630
631
632
633
        iter->Seek("1000000000foo005");
        ASSERT_TRUE(iter->Valid());
        ASSERT_EQ("1000000000foo005", iter->key().ToString());
        ASSERT_EQ("v__5", iter->value().ToString());
634

635
636
637
638
        iter->Seek("1000000000foo006");
        ASSERT_TRUE(iter->Valid());
        ASSERT_EQ("1000000000foo007", iter->key().ToString());
        ASSERT_EQ("v__7", iter->value().ToString());
639

640
        iter->Seek("1000000000foo008");
641
        ASSERT_TRUE(iter->Valid());
642
643
        ASSERT_EQ("1000000000foo008", iter->key().ToString());
        ASSERT_EQ("v__8", iter->value().ToString());
644

645
646
647
648
        if (total_order == 0) {
          iter->Seek("1000000000foo009");
          ASSERT_TRUE(iter->Valid());
          ASSERT_EQ("3000000000000bar", iter->key().ToString());
649
650
        }

651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
        // Test Bloom Filter
        if (bloom_bits > 0) {
          if (!total_order) {
            // Neither key nor value should exist.
            expect_bloom_not_match = true;
            iter->Seek("2not000000000bar");
            ASSERT_TRUE(!iter->Valid());
            ASSERT_EQ("NOT_FOUND", Get("2not000000000bar"));
            expect_bloom_not_match = false;
          } else {
            expect_bloom_not_match = true;
            ASSERT_EQ("NOT_FOUND", Get("2not000000000bar"));
            expect_bloom_not_match = false;
          }
        }

        delete iter;
      }
669
    }
670
    }
671
672
673
  }
}

Igor Canadi's avatar
Igor Canadi committed
674
namespace {
675
676
677
std::string MakeLongKey(size_t length, char c) {
  return std::string(length, c);
}
Igor Canadi's avatar
Igor Canadi committed
678
}  // namespace
679

680
TEST_P(PlainTableDBTest, IteratorLargeKeys) {
681
  Options options = CurrentOptions();
Stanislau Hlebik's avatar
Stanislau Hlebik committed
682
683
684
685
686
687
688

  PlainTableOptions plain_table_options;
  plain_table_options.user_key_len = 0;
  plain_table_options.bloom_bits_per_key = 0;
  plain_table_options.hash_table_ratio = 0;

  options.table_factory.reset(NewPlainTableFactory(plain_table_options));
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
  options.create_if_missing = true;
  options.prefix_extractor.reset();
  DestroyAndReopen(&options);

  std::string key_list[] = {
      MakeLongKey(30, '0'),
      MakeLongKey(16, '1'),
      MakeLongKey(32, '2'),
      MakeLongKey(60, '3'),
      MakeLongKey(90, '4'),
      MakeLongKey(50, '5'),
      MakeLongKey(26, '6')
  };

  for (size_t i = 0; i < 7; i++) {
704
    ASSERT_OK(Put(key_list[i], ToString(i)));
705
706
707
708
  }

  dbfull()->TEST_FlushMemTable();

709
  Iterator* iter = dbfull()->NewIterator(ReadOptions());
710
711
712
713
714
  iter->Seek(key_list[0]);

  for (size_t i = 0; i < 7; i++) {
    ASSERT_TRUE(iter->Valid());
    ASSERT_EQ(key_list[i], iter->key().ToString());
715
    ASSERT_EQ(ToString(i), iter->value().ToString());
716
717
718
719
720
721
722
723
    iter->Next();
  }

  ASSERT_TRUE(!iter->Valid());

  delete iter;
}

724
725
726
727
728
729
namespace {
std::string MakeLongKeyWithPrefix(size_t length, char c) {
  return "00000000" + std::string(length - 8, c);
}
}  // namespace

730
TEST_P(PlainTableDBTest, IteratorLargeKeysWithPrefix) {
731
  Options options = CurrentOptions();
Stanislau Hlebik's avatar
Stanislau Hlebik committed
732
733
734
735
736
737
738
739
740
741

  PlainTableOptions plain_table_options;
  plain_table_options.user_key_len = 16;
  plain_table_options.bloom_bits_per_key = 0;
  plain_table_options.hash_table_ratio = 0.8;
  plain_table_options.index_sparseness = 3;
  plain_table_options.huge_page_tlb_size = 0;
  plain_table_options.encoding_type = kPrefix;

  options.table_factory.reset(NewPlainTableFactory(plain_table_options));
742
743
744
745
746
747
748
749
750
751
  options.create_if_missing = true;
  DestroyAndReopen(&options);

  std::string key_list[] = {
      MakeLongKeyWithPrefix(30, '0'), MakeLongKeyWithPrefix(16, '1'),
      MakeLongKeyWithPrefix(32, '2'), MakeLongKeyWithPrefix(60, '3'),
      MakeLongKeyWithPrefix(90, '4'), MakeLongKeyWithPrefix(50, '5'),
      MakeLongKeyWithPrefix(26, '6')};

  for (size_t i = 0; i < 7; i++) {
752
    ASSERT_OK(Put(key_list[i], ToString(i)));
753
754
755
756
757
758
759
760
761
762
  }

  dbfull()->TEST_FlushMemTable();

  Iterator* iter = dbfull()->NewIterator(ReadOptions());
  iter->Seek(key_list[0]);

  for (size_t i = 0; i < 7; i++) {
    ASSERT_TRUE(iter->Valid());
    ASSERT_EQ(key_list[i], iter->key().ToString());
763
    ASSERT_EQ(ToString(i), iter->value().ToString());
764
765
766
767
768
769
770
771
    iter->Next();
  }

  ASSERT_TRUE(!iter->Valid());

  delete iter;
}

772
TEST_P(PlainTableDBTest, IteratorReverseSuffixComparator) {
773
774
775
776
  Options options = CurrentOptions();
  options.create_if_missing = true;
  // Set only one bucket to force bucket conflict.
  // Test index interval for the same prefix to be 1, 2 and 4
777
  test::SimpleSuffixReverseComparator comp;
778
779
780
  options.comparator = &comp;
  DestroyAndReopen(&options);

Siying Dong's avatar
Siying Dong committed
781
782
783
784
785
786
787
788
789
790
791
792
  ASSERT_OK(Put("1000000000foo002", "v_2"));
  ASSERT_OK(Put("0000000000000bar", "random"));
  ASSERT_OK(Put("1000000000foo001", "v1"));
  ASSERT_OK(Put("3000000000000bar", "bar_v"));
  ASSERT_OK(Put("1000000000foo003", "v__3"));
  ASSERT_OK(Put("1000000000foo004", "v__4"));
  ASSERT_OK(Put("1000000000foo005", "v__5"));
  ASSERT_OK(Put("1000000000foo007", "v__7"));
  ASSERT_OK(Put("1000000000foo008", "v__8"));
  dbfull()->TEST_FlushMemTable();
  ASSERT_EQ("v1", Get("1000000000foo001"));
  ASSERT_EQ("v__3", Get("1000000000foo003"));
793
  Iterator* iter = dbfull()->NewIterator(ReadOptions());
794
  iter->Seek("1000000000foo009");
Siying Dong's avatar
Siying Dong committed
795
  ASSERT_TRUE(iter->Valid());
796
797
  ASSERT_EQ("1000000000foo008", iter->key().ToString());
  ASSERT_EQ("v__8", iter->value().ToString());
Siying Dong's avatar
Siying Dong committed
798
799
800

  iter->Next();
  ASSERT_TRUE(iter->Valid());
801
802
  ASSERT_EQ("1000000000foo007", iter->key().ToString());
  ASSERT_EQ("v__7", iter->value().ToString());
Siying Dong's avatar
Siying Dong committed
803
804
805

  iter->Next();
  ASSERT_TRUE(iter->Valid());
806
807
  ASSERT_EQ("1000000000foo005", iter->key().ToString());
  ASSERT_EQ("v__5", iter->value().ToString());
Siying Dong's avatar
Siying Dong committed
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825

  iter->Next();
  ASSERT_TRUE(iter->Valid());
  ASSERT_EQ("1000000000foo004", iter->key().ToString());
  ASSERT_EQ("v__4", iter->value().ToString());

  iter->Seek("3000000000000bar");
  ASSERT_TRUE(iter->Valid());
  ASSERT_EQ("3000000000000bar", iter->key().ToString());
  ASSERT_EQ("bar_v", iter->value().ToString());

  iter->Seek("1000000000foo005");
  ASSERT_TRUE(iter->Valid());
  ASSERT_EQ("1000000000foo005", iter->key().ToString());
  ASSERT_EQ("v__5", iter->value().ToString());

  iter->Seek("1000000000foo006");
  ASSERT_TRUE(iter->Valid());
826
827
  ASSERT_EQ("1000000000foo005", iter->key().ToString());
  ASSERT_EQ("v__5", iter->value().ToString());
Siying Dong's avatar
Siying Dong committed
828
829
830
831
832
833

  iter->Seek("1000000000foo008");
  ASSERT_TRUE(iter->Valid());
  ASSERT_EQ("1000000000foo008", iter->key().ToString());
  ASSERT_EQ("v__8", iter->value().ToString());

834
  iter->Seek("1000000000foo000");
Siying Dong's avatar
Siying Dong committed
835
836
837
838
839
840
  ASSERT_TRUE(iter->Valid());
  ASSERT_EQ("3000000000000bar", iter->key().ToString());

  delete iter;
}

841
TEST_P(PlainTableDBTest, HashBucketConflict) {
842
843
844
845
846
847
848
  for (size_t huge_page_tlb_size = 0; huge_page_tlb_size <= 2 * 1024 * 1024;
       huge_page_tlb_size += 2 * 1024 * 1024) {
    for (unsigned char i = 1; i <= 3; i++) {
      Options options = CurrentOptions();
      options.create_if_missing = true;
      // Set only one bucket to force bucket conflict.
      // Test index interval for the same prefix to be 1, 2 and 4
Stanislau Hlebik's avatar
Stanislau Hlebik committed
849
850
851
852
853
854
855
856
857
858

      PlainTableOptions plain_table_options;
      plain_table_options.user_key_len = 16;
      plain_table_options.bloom_bits_per_key = 0;
      plain_table_options.hash_table_ratio = 0;
      plain_table_options.index_sparseness = 2 ^ i;
      plain_table_options.huge_page_tlb_size = huge_page_tlb_size;

      options.table_factory.reset(NewPlainTableFactory(plain_table_options));

859
860
861
862
863
864
865
866
      DestroyAndReopen(&options);
      ASSERT_OK(Put("5000000000000fo0", "v1"));
      ASSERT_OK(Put("5000000000000fo1", "v2"));
      ASSERT_OK(Put("5000000000000fo2", "v"));
      ASSERT_OK(Put("2000000000000fo0", "v3"));
      ASSERT_OK(Put("2000000000000fo1", "v4"));
      ASSERT_OK(Put("2000000000000fo2", "v"));
      ASSERT_OK(Put("2000000000000fo3", "v"));
867

868
      dbfull()->TEST_FlushMemTable();
869

870
871
872
873
      ASSERT_EQ("v1", Get("5000000000000fo0"));
      ASSERT_EQ("v2", Get("5000000000000fo1"));
      ASSERT_EQ("v3", Get("2000000000000fo0"));
      ASSERT_EQ("v4", Get("2000000000000fo1"));
874

875
876
877
878
      ASSERT_EQ("NOT_FOUND", Get("5000000000000bar"));
      ASSERT_EQ("NOT_FOUND", Get("2000000000000bar"));
      ASSERT_EQ("NOT_FOUND", Get("5000000000000fo8"));
      ASSERT_EQ("NOT_FOUND", Get("2000000000000fo8"));
879

880
881
      ReadOptions ro;
      Iterator* iter = dbfull()->NewIterator(ro);
882

883
884
885
886
887
888
889
890
891
892
      iter->Seek("5000000000000fo0");
      ASSERT_TRUE(iter->Valid());
      ASSERT_EQ("5000000000000fo0", iter->key().ToString());
      iter->Next();
      ASSERT_TRUE(iter->Valid());
      ASSERT_EQ("5000000000000fo1", iter->key().ToString());

      iter->Seek("5000000000000fo1");
      ASSERT_TRUE(iter->Valid());
      ASSERT_EQ("5000000000000fo1", iter->key().ToString());
893

894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
      iter->Seek("2000000000000fo0");
      ASSERT_TRUE(iter->Valid());
      ASSERT_EQ("2000000000000fo0", iter->key().ToString());
      iter->Next();
      ASSERT_TRUE(iter->Valid());
      ASSERT_EQ("2000000000000fo1", iter->key().ToString());

      iter->Seek("2000000000000fo1");
      ASSERT_TRUE(iter->Valid());
      ASSERT_EQ("2000000000000fo1", iter->key().ToString());

      iter->Seek("2000000000000bar");
      ASSERT_TRUE(iter->Valid());
      ASSERT_EQ("2000000000000fo0", iter->key().ToString());

      iter->Seek("5000000000000bar");
      ASSERT_TRUE(iter->Valid());
      ASSERT_EQ("5000000000000fo0", iter->key().ToString());
912

913
914
915
      iter->Seek("2000000000000fo8");
      ASSERT_TRUE(!iter->Valid() ||
                  options.comparator->Compare(iter->key(), "20000001") > 0);
916

917
918
      iter->Seek("5000000000000fo8");
      ASSERT_TRUE(!iter->Valid());
919

920
921
      iter->Seek("1000000000000fo2");
      ASSERT_TRUE(!iter->Valid());
922

923
924
      iter->Seek("3000000000000fo2");
      ASSERT_TRUE(!iter->Valid());
925

926
927
928
929
930
      iter->Seek("8000000000000fo2");
      ASSERT_TRUE(!iter->Valid());

      delete iter;
    }
931
932
  }
}
Siying Dong's avatar
Siying Dong committed
933

934
TEST_P(PlainTableDBTest, HashBucketConflictReverseSuffixComparator) {
935
936
937
938
939
  for (size_t huge_page_tlb_size = 0; huge_page_tlb_size <= 2 * 1024 * 1024;
       huge_page_tlb_size += 2 * 1024 * 1024) {
    for (unsigned char i = 1; i <= 3; i++) {
      Options options = CurrentOptions();
      options.create_if_missing = true;
940
      test::SimpleSuffixReverseComparator comp;
941
942
943
      options.comparator = &comp;
      // Set only one bucket to force bucket conflict.
      // Test index interval for the same prefix to be 1, 2 and 4
Stanislau Hlebik's avatar
Stanislau Hlebik committed
944
945
946
947
948
949
950
951
952

      PlainTableOptions plain_table_options;
      plain_table_options.user_key_len = 16;
      plain_table_options.bloom_bits_per_key = 0;
      plain_table_options.hash_table_ratio = 0;
      plain_table_options.index_sparseness = 2 ^ i;
      plain_table_options.huge_page_tlb_size = huge_page_tlb_size;

      options.table_factory.reset(NewPlainTableFactory(plain_table_options));
953
954
955
956
957
958
959
960
      DestroyAndReopen(&options);
      ASSERT_OK(Put("5000000000000fo0", "v1"));
      ASSERT_OK(Put("5000000000000fo1", "v2"));
      ASSERT_OK(Put("5000000000000fo2", "v"));
      ASSERT_OK(Put("2000000000000fo0", "v3"));
      ASSERT_OK(Put("2000000000000fo1", "v4"));
      ASSERT_OK(Put("2000000000000fo2", "v"));
      ASSERT_OK(Put("2000000000000fo3", "v"));
961

962
      dbfull()->TEST_FlushMemTable();
963

964
965
966
967
      ASSERT_EQ("v1", Get("5000000000000fo0"));
      ASSERT_EQ("v2", Get("5000000000000fo1"));
      ASSERT_EQ("v3", Get("2000000000000fo0"));
      ASSERT_EQ("v4", Get("2000000000000fo1"));
968

969
970
971
972
      ASSERT_EQ("NOT_FOUND", Get("5000000000000bar"));
      ASSERT_EQ("NOT_FOUND", Get("2000000000000bar"));
      ASSERT_EQ("NOT_FOUND", Get("5000000000000fo8"));
      ASSERT_EQ("NOT_FOUND", Get("2000000000000fo8"));
973

974
975
      ReadOptions ro;
      Iterator* iter = dbfull()->NewIterator(ro);
976

977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
      iter->Seek("5000000000000fo1");
      ASSERT_TRUE(iter->Valid());
      ASSERT_EQ("5000000000000fo1", iter->key().ToString());
      iter->Next();
      ASSERT_TRUE(iter->Valid());
      ASSERT_EQ("5000000000000fo0", iter->key().ToString());

      iter->Seek("5000000000000fo1");
      ASSERT_TRUE(iter->Valid());
      ASSERT_EQ("5000000000000fo1", iter->key().ToString());

      iter->Seek("2000000000000fo1");
      ASSERT_TRUE(iter->Valid());
      ASSERT_EQ("2000000000000fo1", iter->key().ToString());
      iter->Next();
      ASSERT_TRUE(iter->Valid());
      ASSERT_EQ("2000000000000fo0", iter->key().ToString());
994

995
996
997
      iter->Seek("2000000000000fo1");
      ASSERT_TRUE(iter->Valid());
      ASSERT_EQ("2000000000000fo1", iter->key().ToString());
998

999
1000
      iter->Seek("2000000000000var");
      ASSERT_TRUE(iter->Valid());
For faster browsing, not all history is shown. View entire blame