ceph/src/rocksdb/db/range_del_aggregator_bench.cc

   1 //  Copyright (c) 2018-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 GFLAGS
   7 #include <cstdio>
   8 int main() {
   9   fprintf(stderr, "Please install gflags to run rocksdb tools\n");
  10   return 1;
  11 }
  12 #else
  13
  14 #include <iostream>
  15 #include <iomanip>
  16 #include <memory>
  17 #include <random>
  18 #include <set>
  19 #include <string>
  20 #include <vector>
  21
  22 #include "db/range_del_aggregator.h"
  23 #include "db/range_tombstone_fragmenter.h"
  24 #include "rocksdb/comparator.h"
  25 #include "rocksdb/env.h"
  26 #include "util/coding.h"
  27 #include "util/random.h"
  28 #include "util/stop_watch.h"
  29 #include "util/testutil.h"
  30
  31 #include "util/gflags_compat.h"
  32
  33 using GFLAGS_NAMESPACE::ParseCommandLineFlags;
  34
  35 DEFINE_int32(num_range_tombstones, 1000, "number of range tombstones created");
  36
  37 DEFINE_int32(num_runs, 1000, "number of test runs");
  38
  39 DEFINE_int32(tombstone_start_upper_bound, 1000,
  40              "exclusive upper bound on range tombstone start keys");
  41
  42 DEFINE_int32(should_delete_upper_bound, 1000,
  43              "exclusive upper bound on keys passed to ShouldDelete");
  44
  45 DEFINE_double(tombstone_width_mean, 100.0, "average range tombstone width");
  46
  47 DEFINE_double(tombstone_width_stddev, 0.0,
  48               "standard deviation of range tombstone width");
  49
  50 DEFINE_int32(seed, 0, "random number generator seed");
  51
  52 DEFINE_int32(should_deletes_per_run, 1, "number of ShouldDelete calls per run");
  53
  54 DEFINE_int32(add_tombstones_per_run, 1,
  55              "number of AddTombstones calls per run");
  56
  57 namespace {
  58
  59 struct Stats {
  60   uint64_t time_add_tombstones = 0;
  61   uint64_t time_first_should_delete = 0;
  62   uint64_t time_rest_should_delete = 0;
  63 };
  64
  65 std::ostream& operator<<(std::ostream& os, const Stats& s) {
  66   std::ios fmt_holder(nullptr);
  67   fmt_holder.copyfmt(os);
  68
  69   os << std::left;
  70   os << std::setw(25) << "AddTombstones: "
  71      << s.time_add_tombstones /
  72             (FLAGS_add_tombstones_per_run * FLAGS_num_runs * 1.0e3)
  73      << " us\n";
  74   os << std::setw(25) << "ShouldDelete (first): "
  75      << s.time_first_should_delete / (FLAGS_num_runs * 1.0e3) << " us\n";
  76   if (FLAGS_should_deletes_per_run > 1) {
  77     os << std::setw(25) << "ShouldDelete (rest): "
  78        << s.time_rest_should_delete /
  79               ((FLAGS_should_deletes_per_run - 1) * FLAGS_num_runs * 1.0e3)
  80        << " us\n";
  81   }
  82
  83   os.copyfmt(fmt_holder);
  84   return os;
  85 }
  86
  87 auto icmp = rocksdb::InternalKeyComparator(rocksdb::BytewiseComparator());
  88
  89 }  // anonymous namespace
  90
  91 namespace rocksdb {
  92
  93 namespace {
  94
  95 // A wrapper around RangeTombstones and the underlying data of its start and end
  96 // keys.
  97 struct PersistentRangeTombstone {
  98   std::string start_key;
  99   std::string end_key;
 100   RangeTombstone tombstone;
 101
 102   PersistentRangeTombstone(std::string start, std::string end,
 103                            SequenceNumber seq)
 104       : start_key(std::move(start)), end_key(std::move(end)) {
 105     tombstone = RangeTombstone(start_key, end_key, seq);
 106   }
 107
 108   PersistentRangeTombstone() = default;
 109
 110   PersistentRangeTombstone(const PersistentRangeTombstone& t) { *this = t; }
 111
 112   PersistentRangeTombstone& operator=(const PersistentRangeTombstone& t) {
 113     start_key = t.start_key;
 114     end_key = t.end_key;
 115     tombstone = RangeTombstone(start_key, end_key, t.tombstone.seq_);
 116
 117     return *this;
 118   }
 119
 120   PersistentRangeTombstone(PersistentRangeTombstone&& t) noexcept { *this = t; }
 121
 122   PersistentRangeTombstone& operator=(PersistentRangeTombstone&& t) {
 123     start_key = std::move(t.start_key);
 124     end_key = std::move(t.end_key);
 125     tombstone = RangeTombstone(start_key, end_key, t.tombstone.seq_);
 126
 127     return *this;
 128   }
 129 };
 130
 131 struct TombstoneStartKeyComparator {
 132   explicit TombstoneStartKeyComparator(const Comparator* c) : cmp(c) {}
 133
 134   bool operator()(const RangeTombstone& a, const RangeTombstone& b) const {
 135     return cmp->Compare(a.start_key_, b.start_key_) < 0;
 136   }
 137
 138   const Comparator* cmp;
 139 };
 140
 141 std::unique_ptr<InternalIterator> MakeRangeDelIterator(
 142     const std::vector<PersistentRangeTombstone>& range_dels) {
 143   std::vector<std::string> keys, values;
 144   for (const auto& range_del : range_dels) {
 145     auto key_and_value = range_del.tombstone.Serialize();
 146     keys.push_back(key_and_value.first.Encode().ToString());
 147     values.push_back(key_and_value.second.ToString());
 148   }
 149   return std::unique_ptr<test::VectorIterator>(
 150       new test::VectorIterator(keys, values));
 151 }
 152
 153 // convert long to a big-endian slice key
 154 static std::string Key(int64_t val) {
 155   std::string little_endian_key;
 156   std::string big_endian_key;
 157   PutFixed64(&little_endian_key, val);
 158   assert(little_endian_key.size() == sizeof(val));
 159   big_endian_key.resize(sizeof(val));
 160   for (size_t i = 0; i < sizeof(val); ++i) {
 161     big_endian_key[i] = little_endian_key[sizeof(val) - 1 - i];
 162   }
 163   return big_endian_key;
 164 }
 165
 166 }  // anonymous namespace
 167
 168 }  // namespace rocksdb
 169
 170 int main(int argc, char** argv) {
 171   ParseCommandLineFlags(&argc, &argv, true);
 172
 173   Stats stats;
 174   rocksdb::Random64 rnd(FLAGS_seed);
 175   std::default_random_engine random_gen(FLAGS_seed);
 176   std::normal_distribution<double> normal_dist(FLAGS_tombstone_width_mean,
 177                                                FLAGS_tombstone_width_stddev);
 178   std::vector<std::vector<rocksdb::PersistentRangeTombstone> >
 179       all_persistent_range_tombstones(FLAGS_add_tombstones_per_run);
 180   for (int i = 0; i < FLAGS_add_tombstones_per_run; i++) {
 181     all_persistent_range_tombstones[i] =
 182         std::vector<rocksdb::PersistentRangeTombstone>(
 183             FLAGS_num_range_tombstones);
 184   }
 185   auto mode = rocksdb::RangeDelPositioningMode::kForwardTraversal;
 186
 187   for (int i = 0; i < FLAGS_num_runs; i++) {
 188     rocksdb::ReadRangeDelAggregator range_del_agg(
 189         &icmp, rocksdb::kMaxSequenceNumber /* upper_bound */);
 190
 191     std::vector<std::unique_ptr<rocksdb::FragmentedRangeTombstoneList> >
 192         fragmented_range_tombstone_lists(FLAGS_add_tombstones_per_run);
 193
 194     for (auto& persistent_range_tombstones : all_persistent_range_tombstones) {
 195       // TODO(abhimadan): consider whether creating the range tombstones right
 196       // before AddTombstones is artificially warming the cache compared to
 197       // real workloads.
 198       for (int j = 0; j < FLAGS_num_range_tombstones; j++) {
 199         uint64_t start = rnd.Uniform(FLAGS_tombstone_start_upper_bound);
 200         uint64_t end = static_cast<uint64_t>(
 201             std::round(start + std::max(1.0, normal_dist(random_gen))));
 202         persistent_range_tombstones[j] = rocksdb::PersistentRangeTombstone(
 203             rocksdb::Key(start), rocksdb::Key(end), j);
 204       }
 205
 206       auto range_del_iter =
 207           rocksdb::MakeRangeDelIterator(persistent_range_tombstones);
 208       fragmented_range_tombstone_lists.emplace_back(
 209           new rocksdb::FragmentedRangeTombstoneList(
 210               rocksdb::MakeRangeDelIterator(persistent_range_tombstones),
 211               icmp));
 212       std::unique_ptr<rocksdb::FragmentedRangeTombstoneIterator>
 213           fragmented_range_del_iter(
 214               new rocksdb::FragmentedRangeTombstoneIterator(
 215                   fragmented_range_tombstone_lists.back().get(), icmp,
 216                   rocksdb::kMaxSequenceNumber));
 217
 218       rocksdb::StopWatchNano stop_watch_add_tombstones(rocksdb::Env::Default(),
 219                                                        true /* auto_start */);
 220       range_del_agg.AddTombstones(std::move(fragmented_range_del_iter));
 221       stats.time_add_tombstones += stop_watch_add_tombstones.ElapsedNanos();
 222     }
 223
 224     rocksdb::ParsedInternalKey parsed_key;
 225     parsed_key.sequence = FLAGS_num_range_tombstones / 2;
 226     parsed_key.type = rocksdb::kTypeValue;
 227
 228     uint64_t first_key = rnd.Uniform(FLAGS_should_delete_upper_bound -
 229                                      FLAGS_should_deletes_per_run + 1);
 230
 231     for (int j = 0; j < FLAGS_should_deletes_per_run; j++) {
 232       std::string key_string = rocksdb::Key(first_key + j);
 233       parsed_key.user_key = key_string;
 234
 235       rocksdb::StopWatchNano stop_watch_should_delete(rocksdb::Env::Default(),
 236                                                       true /* auto_start */);
 237       range_del_agg.ShouldDelete(parsed_key, mode);
 238       uint64_t call_time = stop_watch_should_delete.ElapsedNanos();
 239
 240       if (j == 0) {
 241         stats.time_first_should_delete += call_time;
 242       } else {
 243         stats.time_rest_should_delete += call_time;
 244       }
 245     }
 246   }
 247
 248   std::cout << "=========================\n"
 249             << "Results:\n"
 250             << "=========================\n"
 251             << stats;
 252
 253   return 0;
 254 }
 255
 256 #endif  // GFLAGS