ceph/src/rocksdb/utilities/table_properties_collectors/compact_on_deletion_collector_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 // 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 <stdio.h>
  11
  12 #ifndef ROCKSDB_LITE
  13 #include <algorithm>
  14 #include <cmath>
  15 #include <vector>
  16
  17 #include "rocksdb/table.h"
  18 #include "rocksdb/table_properties.h"
  19 #include "rocksdb/utilities/table_properties_collectors.h"
  20 #include "util/random.h"
  21 #include "utilities/table_properties_collectors/compact_on_deletion_collector.h"
  22
  23 int main(int /*argc*/, char** /*argv*/) {
  24   const int kWindowSizes[] =
  25       {1000, 10000, 10000, 127, 128, 129, 255, 256, 257, 2, 10000};
  26   const int kDeletionTriggers[] =
  27       {500, 9500, 4323, 47, 61, 128, 250, 250, 250, 2, 2};
  28   rocksdb::TablePropertiesCollectorFactory::Context context;
  29   context.column_family_id =
  30       rocksdb::TablePropertiesCollectorFactory::Context::kUnknownColumnFamily;
  31
  32   std::vector<int> window_sizes;
  33   std::vector<int> deletion_triggers;
  34   // deterministic tests
  35   for (int test = 0; test < 9; ++test) {
  36     window_sizes.emplace_back(kWindowSizes[test]);
  37     deletion_triggers.emplace_back(kDeletionTriggers[test]);
  38   }
  39
  40   // randomize tests
  41   rocksdb::Random rnd(301);
  42   const int kMaxTestSize = 100000l;
  43   for (int random_test = 0; random_test < 30; random_test++) {
  44     int window_size = rnd.Uniform(kMaxTestSize) + 1;
  45     int deletion_trigger = rnd.Uniform(window_size);
  46     window_sizes.emplace_back(window_size);
  47     deletion_triggers.emplace_back(deletion_trigger);
  48   }
  49
  50   assert(window_sizes.size() == deletion_triggers.size());
  51
  52   for (size_t test = 0; test < window_sizes.size(); ++test) {
  53     const int kBucketSize = 128;
  54     const int kWindowSize = window_sizes[test];
  55     const int kPaddedWindowSize =
  56         kBucketSize * ((window_sizes[test] + kBucketSize - 1) / kBucketSize);
  57     const int kNumDeletionTrigger = deletion_triggers[test];
  58     const int kBias = (kNumDeletionTrigger + kBucketSize - 1) / kBucketSize;
  59     // Simple test
  60     {
  61       auto factory = rocksdb::NewCompactOnDeletionCollectorFactory(
  62           kWindowSize, kNumDeletionTrigger);
  63       const int kSample = 10;
  64       for (int delete_rate = 0; delete_rate <= kSample; ++delete_rate) {
  65         std::unique_ptr<rocksdb::TablePropertiesCollector> collector(
  66             factory->CreateTablePropertiesCollector(context));
  67         int deletions = 0;
  68         for (int i = 0; i < kPaddedWindowSize; ++i) {
  69           if (i % kSample < delete_rate) {
  70             collector->AddUserKey("hello", "rocksdb",
  71                                   rocksdb::kEntryDelete, 0, 0);
  72             deletions++;
  73           } else {
  74             collector->AddUserKey("hello", "rocksdb",
  75                                   rocksdb::kEntryPut, 0, 0);
  76           }
  77         }
  78         if (collector->NeedCompact() !=
  79             (deletions >= kNumDeletionTrigger) &&
  80             std::abs(deletions - kNumDeletionTrigger) > kBias) {
  81           fprintf(stderr, "[Error] collector->NeedCompact() != (%d >= %d)"
  82                   " with kWindowSize = %d and kNumDeletionTrigger = %d\n",
  83                   deletions, kNumDeletionTrigger,
  84                   kWindowSize, kNumDeletionTrigger);
  85           assert(false);
  86         }
  87         collector->Finish(nullptr);
  88       }
  89     }
  90
  91     // Only one section of a file satisfies the compaction trigger
  92     {
  93       auto factory = rocksdb::NewCompactOnDeletionCollectorFactory(
  94           kWindowSize, kNumDeletionTrigger);
  95       const int kSample = 10;
  96       for (int delete_rate = 0; delete_rate <= kSample; ++delete_rate) {
  97         std::unique_ptr<rocksdb::TablePropertiesCollector> collector(
  98             factory->CreateTablePropertiesCollector(context));
  99         int deletions = 0;
 100         for (int section = 0; section < 5; ++section) {
 101           int initial_entries = rnd.Uniform(kWindowSize) + kWindowSize;
 102           for (int i = 0; i < initial_entries; ++i) {
 103             collector->AddUserKey("hello", "rocksdb",
 104                                   rocksdb::kEntryPut, 0, 0);
 105           }
 106         }
 107         for (int i = 0; i < kPaddedWindowSize; ++i) {
 108           if (i % kSample < delete_rate) {
 109             collector->AddUserKey("hello", "rocksdb",
 110                                   rocksdb::kEntryDelete, 0, 0);
 111             deletions++;
 112           } else {
 113             collector->AddUserKey("hello", "rocksdb",
 114                                   rocksdb::kEntryPut, 0, 0);
 115           }
 116         }
 117         for (int section = 0; section < 5; ++section) {
 118           int ending_entries = rnd.Uniform(kWindowSize) + kWindowSize;
 119           for (int i = 0; i < ending_entries; ++i) {
 120             collector->AddUserKey("hello", "rocksdb",
 121                                   rocksdb::kEntryPut, 0, 0);
 122           }
 123         }
 124         if (collector->NeedCompact() != (deletions >= kNumDeletionTrigger) &&
 125             std::abs(deletions - kNumDeletionTrigger) > kBias) {
 126           fprintf(stderr, "[Error] collector->NeedCompact() %d != (%d >= %d)"
 127                   " with kWindowSize = %d, kNumDeletionTrigger = %d\n",
 128                   collector->NeedCompact(),
 129                   deletions, kNumDeletionTrigger, kWindowSize,
 130                   kNumDeletionTrigger);
 131           assert(false);
 132         }
 133         collector->Finish(nullptr);
 134       }
 135     }
 136
 137     // TEST 3:  Issues a lots of deletes, but their density is not
 138     // high enough to trigger compaction.
 139     {
 140       std::unique_ptr<rocksdb::TablePropertiesCollector> collector;
 141       auto factory = rocksdb::NewCompactOnDeletionCollectorFactory(
 142           kWindowSize, kNumDeletionTrigger);
 143       collector.reset(factory->CreateTablePropertiesCollector(context));
 144       assert(collector->NeedCompact() == false);
 145       // Insert "kNumDeletionTrigger * 0.95" deletions for every
 146       // "kWindowSize" and verify compaction is not needed.
 147       const int kDeletionsPerSection = kNumDeletionTrigger * 95 / 100;
 148       if (kDeletionsPerSection >= 0) {
 149         for (int section = 0; section < 200; ++section) {
 150           for (int i = 0; i < kPaddedWindowSize; ++i) {
 151             if (i < kDeletionsPerSection) {
 152               collector->AddUserKey("hello", "rocksdb",
 153                                     rocksdb::kEntryDelete, 0, 0);
 154             } else {
 155               collector->AddUserKey("hello", "rocksdb",
 156                                     rocksdb::kEntryPut, 0, 0);
 157             }
 158           }
 159         }
 160         if (collector->NeedCompact() &&
 161             std::abs(kDeletionsPerSection - kNumDeletionTrigger) > kBias) {
 162           fprintf(stderr, "[Error] collector->NeedCompact() != false"
 163                   " with kWindowSize = %d and kNumDeletionTrigger = %d\n",
 164                   kWindowSize, kNumDeletionTrigger);
 165           assert(false);
 166         }
 167         collector->Finish(nullptr);
 168       }
 169     }
 170   }
 171   fprintf(stderr, "PASSED\n");
 172 }
 173 #else
 174 int main(int /*argc*/, char** /*argv*/) {
 175   fprintf(stderr, "SKIPPED as RocksDBLite does not include utilities.\n");
 176   return 0;
 177 }
 178 #endif  // !ROCKSDB_LITE