ceph/src/rocksdb/db/file_indexer_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 // Copyright (c) 2011 The LevelDB Authors. All rights reserved.
   7 // Use of this source code is governed by a BSD-style license that can be
   8 // found in the LICENSE file. See the AUTHORS file for names of contributors.
   9
  10 #include <string>
  11 #include "db/file_indexer.h"
  12 #include "db/dbformat.h"
  13 #include "db/version_edit.h"
  14 #include "port/stack_trace.h"
  15 #include "rocksdb/comparator.h"
  16 #include "util/testharness.h"
  17 #include "util/testutil.h"
  18
  19 namespace rocksdb {
  20
  21 class IntComparator : public Comparator {
  22  public:
  23   int Compare(const Slice& a, const Slice& b) const override {
  24     assert(a.size() == 8);
  25     assert(b.size() == 8);
  26     int64_t diff = *reinterpret_cast<const int64_t*>(a.data()) -
  27                    *reinterpret_cast<const int64_t*>(b.data());
  28     if (diff < 0) {
  29       return -1;
  30     } else if (diff == 0) {
  31       return 0;
  32     } else {
  33       return 1;
  34     }
  35   }
  36
  37   const char* Name() const override { return "IntComparator"; }
  38
  39   void FindShortestSeparator(std::string* start,
  40                              const Slice& limit) const override {}
  41
  42   void FindShortSuccessor(std::string* key) const override {}
  43 };
  44
  45 class FileIndexerTest : public testing::Test {
  46  public:
  47   FileIndexerTest()
  48       : kNumLevels(4), files(new std::vector<FileMetaData*>[kNumLevels]) {}
  49
  50   ~FileIndexerTest() {
  51     ClearFiles();
  52     delete[] files;
  53   }
  54
  55   void AddFile(int level, int64_t smallest, int64_t largest) {
  56     auto* f = new FileMetaData();
  57     f->smallest = IntKey(smallest);
  58     f->largest = IntKey(largest);
  59     files[level].push_back(f);
  60   }
  61
  62   InternalKey IntKey(int64_t v) {
  63     return InternalKey(Slice(reinterpret_cast<char*>(&v), 8), 0, kTypeValue);
  64   }
  65
  66   void ClearFiles() {
  67     for (uint32_t i = 0; i < kNumLevels; ++i) {
  68       for (auto* f : files[i]) {
  69         delete f;
  70       }
  71       files[i].clear();
  72     }
  73   }
  74
  75   void GetNextLevelIndex(const uint32_t level, const uint32_t file_index,
  76       const int cmp_smallest, const int cmp_largest, int32_t* left_index,
  77       int32_t* right_index) {
  78     *left_index = 100;
  79     *right_index = 100;
  80     indexer->GetNextLevelIndex(level, file_index, cmp_smallest, cmp_largest,
  81                                left_index, right_index);
  82   }
  83
  84   int32_t left = 100;
  85   int32_t right = 100;
  86   const uint32_t kNumLevels;
  87   IntComparator ucmp;
  88   FileIndexer* indexer;
  89
  90   std::vector<FileMetaData*>* files;
  91 };
  92
  93 // Case 0: Empty
  94 TEST_F(FileIndexerTest, Empty) {
  95   Arena arena;
  96   indexer = new FileIndexer(&ucmp);
  97   indexer->UpdateIndex(&arena, 0, files);
  98   delete indexer;
  99 }
 100
 101 // Case 1: no overlap, files are on the left of next level files
 102 TEST_F(FileIndexerTest, no_overlap_left) {
 103   Arena arena;
 104   indexer = new FileIndexer(&ucmp);
 105   // level 1
 106   AddFile(1, 100, 200);
 107   AddFile(1, 300, 400);
 108   AddFile(1, 500, 600);
 109   // level 2
 110   AddFile(2, 1500, 1600);
 111   AddFile(2, 1601, 1699);
 112   AddFile(2, 1700, 1800);
 113   // level 3
 114   AddFile(3, 2500, 2600);
 115   AddFile(3, 2601, 2699);
 116   AddFile(3, 2700, 2800);
 117   indexer->UpdateIndex(&arena, kNumLevels, files);
 118   for (uint32_t level = 1; level < 3; ++level) {
 119     for (uint32_t f = 0; f < 3; ++f) {
 120       GetNextLevelIndex(level, f, -1, -1, &left, &right);
 121       ASSERT_EQ(0, left);
 122       ASSERT_EQ(-1, right);
 123       GetNextLevelIndex(level, f, 0, -1, &left, &right);
 124       ASSERT_EQ(0, left);
 125       ASSERT_EQ(-1, right);
 126       GetNextLevelIndex(level, f, 1, -1, &left, &right);
 127       ASSERT_EQ(0, left);
 128       ASSERT_EQ(-1, right);
 129       GetNextLevelIndex(level, f, 1, 0, &left, &right);
 130       ASSERT_EQ(0, left);
 131       ASSERT_EQ(-1, right);
 132       GetNextLevelIndex(level, f, 1, 1, &left, &right);
 133       ASSERT_EQ(0, left);
 134       ASSERT_EQ(2, right);
 135     }
 136   }
 137   delete indexer;
 138   ClearFiles();
 139 }
 140
 141 // Case 2: no overlap, files are on the right of next level files
 142 TEST_F(FileIndexerTest, no_overlap_right) {
 143   Arena arena;
 144   indexer = new FileIndexer(&ucmp);
 145   // level 1
 146   AddFile(1, 2100, 2200);
 147   AddFile(1, 2300, 2400);
 148   AddFile(1, 2500, 2600);
 149   // level 2
 150   AddFile(2, 1500, 1600);
 151   AddFile(2, 1501, 1699);
 152   AddFile(2, 1700, 1800);
 153   // level 3
 154   AddFile(3, 500, 600);
 155   AddFile(3, 501, 699);
 156   AddFile(3, 700, 800);
 157   indexer->UpdateIndex(&arena, kNumLevels, files);
 158   for (uint32_t level = 1; level < 3; ++level) {
 159     for (uint32_t f = 0; f < 3; ++f) {
 160       GetNextLevelIndex(level, f, -1, -1, &left, &right);
 161       ASSERT_EQ(f == 0 ? 0 : 3, left);
 162       ASSERT_EQ(2, right);
 163       GetNextLevelIndex(level, f, 0, -1, &left, &right);
 164       ASSERT_EQ(3, left);
 165       ASSERT_EQ(2, right);
 166       GetNextLevelIndex(level, f, 1, -1, &left, &right);
 167       ASSERT_EQ(3, left);
 168       ASSERT_EQ(2, right);
 169       GetNextLevelIndex(level, f, 1, -1, &left, &right);
 170       ASSERT_EQ(3, left);
 171       ASSERT_EQ(2, right);
 172       GetNextLevelIndex(level, f, 1, 0, &left, &right);
 173       ASSERT_EQ(3, left);
 174       ASSERT_EQ(2, right);
 175       GetNextLevelIndex(level, f, 1, 1, &left, &right);
 176       ASSERT_EQ(3, left);
 177       ASSERT_EQ(2, right);
 178     }
 179   }
 180   delete indexer;
 181 }
 182
 183 // Case 3: empty L2
 184 TEST_F(FileIndexerTest, empty_L2) {
 185   Arena arena;
 186   indexer = new FileIndexer(&ucmp);
 187   for (uint32_t i = 1; i < kNumLevels; ++i) {
 188     ASSERT_EQ(0U, indexer->LevelIndexSize(i));
 189   }
 190   // level 1
 191   AddFile(1, 2100, 2200);
 192   AddFile(1, 2300, 2400);
 193   AddFile(1, 2500, 2600);
 194   // level 3
 195   AddFile(3, 500, 600);
 196   AddFile(3, 501, 699);
 197   AddFile(3, 700, 800);
 198   indexer->UpdateIndex(&arena, kNumLevels, files);
 199   for (uint32_t f = 0; f < 3; ++f) {
 200     GetNextLevelIndex(1, f, -1, -1, &left, &right);
 201     ASSERT_EQ(0, left);
 202     ASSERT_EQ(-1, right);
 203     GetNextLevelIndex(1, f, 0, -1, &left, &right);
 204     ASSERT_EQ(0, left);
 205     ASSERT_EQ(-1, right);
 206     GetNextLevelIndex(1, f, 1, -1, &left, &right);
 207     ASSERT_EQ(0, left);
 208     ASSERT_EQ(-1, right);
 209     GetNextLevelIndex(1, f, 1, -1, &left, &right);
 210     ASSERT_EQ(0, left);
 211     ASSERT_EQ(-1, right);
 212     GetNextLevelIndex(1, f, 1, 0, &left, &right);
 213     ASSERT_EQ(0, left);
 214     ASSERT_EQ(-1, right);
 215     GetNextLevelIndex(1, f, 1, 1, &left, &right);
 216     ASSERT_EQ(0, left);
 217     ASSERT_EQ(-1, right);
 218   }
 219   delete indexer;
 220   ClearFiles();
 221 }
 222
 223 // Case 4: mixed
 224 TEST_F(FileIndexerTest, mixed) {
 225   Arena arena;
 226   indexer = new FileIndexer(&ucmp);
 227   // level 1
 228   AddFile(1, 100, 200);
 229   AddFile(1, 250, 400);
 230   AddFile(1, 450, 500);
 231   // level 2
 232   AddFile(2, 100, 150);  // 0
 233   AddFile(2, 200, 250);  // 1
 234   AddFile(2, 251, 300);  // 2
 235   AddFile(2, 301, 350);  // 3
 236   AddFile(2, 500, 600);  // 4
 237   // level 3
 238   AddFile(3, 0, 50);
 239   AddFile(3, 100, 200);
 240   AddFile(3, 201, 250);
 241   indexer->UpdateIndex(&arena, kNumLevels, files);
 242   // level 1, 0
 243   GetNextLevelIndex(1, 0, -1, -1, &left, &right);
 244   ASSERT_EQ(0, left);
 245   ASSERT_EQ(0, right);
 246   GetNextLevelIndex(1, 0, 0, -1, &left, &right);
 247   ASSERT_EQ(0, left);
 248   ASSERT_EQ(0, right);
 249   GetNextLevelIndex(1, 0, 1, -1, &left, &right);
 250   ASSERT_EQ(0, left);
 251   ASSERT_EQ(1, right);
 252   GetNextLevelIndex(1, 0, 1, 0, &left, &right);
 253   ASSERT_EQ(1, left);
 254   ASSERT_EQ(1, right);
 255   GetNextLevelIndex(1, 0, 1, 1, &left, &right);
 256   ASSERT_EQ(1, left);
 257   ASSERT_EQ(4, right);
 258   // level 1, 1
 259   GetNextLevelIndex(1, 1, -1, -1, &left, &right);
 260   ASSERT_EQ(1, left);
 261   ASSERT_EQ(1, right);
 262   GetNextLevelIndex(1, 1, 0, -1, &left, &right);
 263   ASSERT_EQ(1, left);
 264   ASSERT_EQ(1, right);
 265   GetNextLevelIndex(1, 1, 1, -1, &left, &right);
 266   ASSERT_EQ(1, left);
 267   ASSERT_EQ(3, right);
 268   GetNextLevelIndex(1, 1, 1, 0, &left, &right);
 269   ASSERT_EQ(4, left);
 270   ASSERT_EQ(3, right);
 271   GetNextLevelIndex(1, 1, 1, 1, &left, &right);
 272   ASSERT_EQ(4, left);
 273   ASSERT_EQ(4, right);
 274   // level 1, 2
 275   GetNextLevelIndex(1, 2, -1, -1, &left, &right);
 276   ASSERT_EQ(4, left);
 277   ASSERT_EQ(3, right);
 278   GetNextLevelIndex(1, 2, 0, -1, &left, &right);
 279   ASSERT_EQ(4, left);
 280   ASSERT_EQ(3, right);
 281   GetNextLevelIndex(1, 2, 1, -1, &left, &right);
 282   ASSERT_EQ(4, left);
 283   ASSERT_EQ(4, right);
 284   GetNextLevelIndex(1, 2, 1, 0, &left, &right);
 285   ASSERT_EQ(4, left);
 286   ASSERT_EQ(4, right);
 287   GetNextLevelIndex(1, 2, 1, 1, &left, &right);
 288   ASSERT_EQ(4, left);
 289   ASSERT_EQ(4, right);
 290   // level 2, 0
 291   GetNextLevelIndex(2, 0, -1, -1, &left, &right);
 292   ASSERT_EQ(0, left);
 293   ASSERT_EQ(1, right);
 294   GetNextLevelIndex(2, 0, 0, -1, &left, &right);
 295   ASSERT_EQ(1, left);
 296   ASSERT_EQ(1, right);
 297   GetNextLevelIndex(2, 0, 1, -1, &left, &right);
 298   ASSERT_EQ(1, left);
 299   ASSERT_EQ(1, right);
 300   GetNextLevelIndex(2, 0, 1, 0, &left, &right);
 301   ASSERT_EQ(1, left);
 302   ASSERT_EQ(1, right);
 303   GetNextLevelIndex(2, 0, 1, 1, &left, &right);
 304   ASSERT_EQ(1, left);
 305   ASSERT_EQ(2, right);
 306   // level 2, 1
 307   GetNextLevelIndex(2, 1, -1, -1, &left, &right);
 308   ASSERT_EQ(1, left);
 309   ASSERT_EQ(1, right);
 310   GetNextLevelIndex(2, 1, 0, -1, &left, &right);
 311   ASSERT_EQ(1, left);
 312   ASSERT_EQ(1, right);
 313   GetNextLevelIndex(2, 1, 1, -1, &left, &right);
 314   ASSERT_EQ(1, left);
 315   ASSERT_EQ(2, right);
 316   GetNextLevelIndex(2, 1, 1, 0, &left, &right);
 317   ASSERT_EQ(2, left);
 318   ASSERT_EQ(2, right);
 319   GetNextLevelIndex(2, 1, 1, 1, &left, &right);
 320   ASSERT_EQ(2, left);
 321   ASSERT_EQ(2, right);
 322   // level 2, [2 - 4], no overlap
 323   for (uint32_t f = 2; f <= 4; ++f) {
 324     GetNextLevelIndex(2, f, -1, -1, &left, &right);
 325     ASSERT_EQ(f == 2 ? 2 : 3, left);
 326     ASSERT_EQ(2, right);
 327     GetNextLevelIndex(2, f, 0, -1, &left, &right);
 328     ASSERT_EQ(3, left);
 329     ASSERT_EQ(2, right);
 330     GetNextLevelIndex(2, f, 1, -1, &left, &right);
 331     ASSERT_EQ(3, left);
 332     ASSERT_EQ(2, right);
 333     GetNextLevelIndex(2, f, 1, 0, &left, &right);
 334     ASSERT_EQ(3, left);
 335     ASSERT_EQ(2, right);
 336     GetNextLevelIndex(2, f, 1, 1, &left, &right);
 337     ASSERT_EQ(3, left);
 338     ASSERT_EQ(2, right);
 339   }
 340   delete indexer;
 341   ClearFiles();
 342 }
 343
 344 }  // namespace rocksdb
 345
 346 int main(int argc, char** argv) {
 347   rocksdb::port::InstallStackTraceHandler();
 348   ::testing::InitGoogleTest(&argc, argv);
 349   return RUN_ALL_TESTS();
 350 }