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 <iomanip>
  15 #include <iostream>
  16 #include <memory>
  17 #include <random>
  18 #include <set>
  19 #include <string>
  20 #include <vector>
  21
  22 #include "db/dbformat.h"
  23 #include "db/range_del_aggregator.h"
  24 #include "db/range_tombstone_fragmenter.h"
  25 #include "rocksdb/comparator.h"
  26 #include "rocksdb/system_clock.h"
  27 #include "util/coding.h"
  28 #include "util/gflags_compat.h"
  29 #include "util/random.h"
  30 #include "util/stop_watch.h"
  31 #include "util/vector_iterator.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 DEFINE_bool(use_compaction_range_del_aggregator, false,
  58             "Whether to use CompactionRangeDelAggregator. Default is to use "
  59             "ReadRangeDelAggregator.");
  60
  61 namespace {
  62
  63 struct Stats {
  64   uint64_t time_add_tombstones = 0;
  65   uint64_t time_first_should_delete = 0;
  66   uint64_t time_rest_should_delete = 0;
  67   uint64_t time_fragment_tombstones = 0;
  68 };
  69
  70 std::ostream& operator<<(std::ostream& os, const Stats& s) {
  71   std::ios fmt_holder(nullptr);
  72   fmt_holder.copyfmt(os);
  73
  74   os << std::left;
  75   os << std::setw(25) << "Fragment Tombstones: "
  76      << s.time_fragment_tombstones /
  77             (FLAGS_add_tombstones_per_run * FLAGS_num_runs * 1.0e3)
  78      << " us\n";
  79   os << std::setw(25) << "AddTombstones: "
  80      << s.time_add_tombstones /
  81             (FLAGS_add_tombstones_per_run * FLAGS_num_runs * 1.0e3)
  82      << " us\n";
  83   os << std::setw(25) << "ShouldDelete (first): "
  84      << s.time_first_should_delete / (FLAGS_num_runs * 1.0e3) << " us\n";
  85   if (FLAGS_should_deletes_per_run > 1) {
  86     os << std::setw(25) << "ShouldDelete (rest): "
  87        << s.time_rest_should_delete /
  88               ((FLAGS_should_deletes_per_run - 1) * FLAGS_num_runs * 1.0e3)
  89        << " us\n";
  90   }
  91
  92   os.copyfmt(fmt_holder);
  93   return os;
  94 }
  95
  96 auto icmp = ROCKSDB_NAMESPACE::InternalKeyComparator(
  97     ROCKSDB_NAMESPACE::BytewiseComparator());
  98
  99 }  // anonymous namespace
 100
 101 namespace ROCKSDB_NAMESPACE {
 102
 103 namespace {
 104
 105 // A wrapper around RangeTombstones and the underlying data of its start and end
 106 // keys.
 107 struct PersistentRangeTombstone {
 108   std::string start_key;
 109   std::string end_key;
 110   RangeTombstone tombstone;
 111
 112   PersistentRangeTombstone(std::string start, std::string end,
 113                            SequenceNumber seq)
 114       : start_key(std::move(start)), end_key(std::move(end)) {
 115     tombstone = RangeTombstone(start_key, end_key, seq);
 116   }
 117
 118   PersistentRangeTombstone() = default;
 119
 120   PersistentRangeTombstone(const PersistentRangeTombstone& t) { *this = t; }
 121
 122   PersistentRangeTombstone& operator=(const PersistentRangeTombstone& t) {
 123     start_key = t.start_key;
 124     end_key = t.end_key;
 125     tombstone = RangeTombstone(start_key, end_key, t.tombstone.seq_);
 126
 127     return *this;
 128   }
 129
 130   PersistentRangeTombstone(PersistentRangeTombstone&& t) noexcept { *this = t; }
 131
 132   PersistentRangeTombstone& operator=(PersistentRangeTombstone&& t) {
 133     start_key = std::move(t.start_key);
 134     end_key = std::move(t.end_key);
 135     tombstone = RangeTombstone(start_key, end_key, t.tombstone.seq_);
 136
 137     return *this;
 138   }
 139 };
 140
 141 struct TombstoneStartKeyComparator {
 142   explicit TombstoneStartKeyComparator(const Comparator* c) : cmp(c) {}
 143
 144   bool operator()(const RangeTombstone& a, const RangeTombstone& b) const {
 145     return cmp->Compare(a.start_key_, b.start_key_) < 0;
 146   }
 147
 148   const Comparator* cmp;
 149 };
 150
 151 std::unique_ptr<InternalIterator> MakeRangeDelIterator(
 152     const std::vector<PersistentRangeTombstone>& range_dels) {
 153   std::vector<std::string> keys, values;
 154   for (const auto& range_del : range_dels) {
 155     auto key_and_value = range_del.tombstone.Serialize();
 156     keys.push_back(key_and_value.first.Encode().ToString());
 157     values.push_back(key_and_value.second.ToString());
 158   }
 159   return std::unique_ptr<VectorIterator>(
 160       new VectorIterator(keys, values, &icmp));
 161 }
 162
 163 // convert long to a big-endian slice key
 164 static std::string Key(int64_t val) {
 165   std::string little_endian_key;
 166   std::string big_endian_key;
 167   PutFixed64(&little_endian_key, val);
 168   assert(little_endian_key.size() == sizeof(val));
 169   big_endian_key.resize(sizeof(val));
 170   for (size_t i = 0; i < sizeof(val); ++i) {
 171     big_endian_key[i] = little_endian_key[sizeof(val) - 1 - i];
 172   }
 173   return big_endian_key;
 174 }
 175
 176 }  // anonymous namespace
 177
 178 }  // namespace ROCKSDB_NAMESPACE
 179
 180 int main(int argc, char** argv) {
 181   ParseCommandLineFlags(&argc, &argv, true);
 182
 183   Stats stats;
 184   ROCKSDB_NAMESPACE::SystemClock* clock =
 185       ROCKSDB_NAMESPACE::SystemClock::Default().get();
 186   ROCKSDB_NAMESPACE::Random64 rnd(FLAGS_seed);
 187   std::default_random_engine random_gen(FLAGS_seed);
 188   std::normal_distribution<double> normal_dist(FLAGS_tombstone_width_mean,
 189                                                FLAGS_tombstone_width_stddev);
 190   std::vector<std::vector<ROCKSDB_NAMESPACE::PersistentRangeTombstone> >
 191       all_persistent_range_tombstones(FLAGS_add_tombstones_per_run);
 192   for (int i = 0; i < FLAGS_add_tombstones_per_run; i++) {
 193     all_persistent_range_tombstones[i] =
 194         std::vector<ROCKSDB_NAMESPACE::PersistentRangeTombstone>(
 195             FLAGS_num_range_tombstones);
 196   }
 197   auto mode = ROCKSDB_NAMESPACE::RangeDelPositioningMode::kForwardTraversal;
 198   std::vector<ROCKSDB_NAMESPACE::SequenceNumber> snapshots{0};
 199   for (int i = 0; i < FLAGS_num_runs; i++) {
 200     std::unique_ptr<ROCKSDB_NAMESPACE::RangeDelAggregator> range_del_agg =
 201         nullptr;
 202     if (FLAGS_use_compaction_range_del_aggregator) {
 203       range_del_agg.reset(new ROCKSDB_NAMESPACE::CompactionRangeDelAggregator(
 204           &icmp, snapshots));
 205     } else {
 206       range_del_agg.reset(new ROCKSDB_NAMESPACE::ReadRangeDelAggregator(
 207           &icmp, ROCKSDB_NAMESPACE::kMaxSequenceNumber /* upper_bound */));
 208     }
 209
 210     std::vector<
 211         std::unique_ptr<ROCKSDB_NAMESPACE::FragmentedRangeTombstoneList> >
 212         fragmented_range_tombstone_lists(FLAGS_add_tombstones_per_run);
 213
 214     for (auto& persistent_range_tombstones : all_persistent_range_tombstones) {
 215       // TODO(abhimadan): consider whether creating the range tombstones right
 216       // before AddTombstones is artificially warming the cache compared to
 217       // real workloads.
 218       for (int j = 0; j < FLAGS_num_range_tombstones; j++) {
 219         uint64_t start = rnd.Uniform(FLAGS_tombstone_start_upper_bound);
 220         uint64_t end = static_cast<uint64_t>(
 221             std::round(start + std::max(1.0, normal_dist(random_gen))));
 222         persistent_range_tombstones[j] =
 223             ROCKSDB_NAMESPACE::PersistentRangeTombstone(
 224                 ROCKSDB_NAMESPACE::Key(start), ROCKSDB_NAMESPACE::Key(end), j);
 225       }
 226       auto iter =
 227           ROCKSDB_NAMESPACE::MakeRangeDelIterator(persistent_range_tombstones);
 228       ROCKSDB_NAMESPACE::StopWatchNano stop_watch_fragment_tombstones(
 229           clock, true /* auto_start */);
 230       fragmented_range_tombstone_lists.emplace_back(
 231           new ROCKSDB_NAMESPACE::FragmentedRangeTombstoneList(
 232               std::move(iter), icmp, FLAGS_use_compaction_range_del_aggregator,
 233               snapshots));
 234       stats.time_fragment_tombstones +=
 235           stop_watch_fragment_tombstones.ElapsedNanos();
 236       std::unique_ptr<ROCKSDB_NAMESPACE::FragmentedRangeTombstoneIterator>
 237           fragmented_range_del_iter(
 238               new ROCKSDB_NAMESPACE::FragmentedRangeTombstoneIterator(
 239                   fragmented_range_tombstone_lists.back().get(), icmp,
 240                   ROCKSDB_NAMESPACE::kMaxSequenceNumber));
 241
 242       ROCKSDB_NAMESPACE::StopWatchNano stop_watch_add_tombstones(
 243           clock, true /* auto_start */);
 244       range_del_agg->AddTombstones(std::move(fragmented_range_del_iter));
 245       stats.time_add_tombstones += stop_watch_add_tombstones.ElapsedNanos();
 246     }
 247
 248     ROCKSDB_NAMESPACE::ParsedInternalKey parsed_key;
 249     parsed_key.sequence = FLAGS_num_range_tombstones / 2;
 250     parsed_key.type = ROCKSDB_NAMESPACE::kTypeValue;
 251
 252     uint64_t first_key = rnd.Uniform(FLAGS_should_delete_upper_bound -
 253                                      FLAGS_should_deletes_per_run + 1);
 254
 255     for (int j = 0; j < FLAGS_should_deletes_per_run; j++) {
 256       std::string key_string = ROCKSDB_NAMESPACE::Key(first_key + j);
 257       parsed_key.user_key = key_string;
 258
 259       ROCKSDB_NAMESPACE::StopWatchNano stop_watch_should_delete(
 260           clock, true /* auto_start */);
 261       range_del_agg->ShouldDelete(parsed_key, mode);
 262       uint64_t call_time = stop_watch_should_delete.ElapsedNanos();
 263
 264       if (j == 0) {
 265         stats.time_first_should_delete += call_time;
 266       } else {
 267         stats.time_rest_should_delete += call_time;
 268       }
 269     }
 270   }
 271
 272   std::cout << "=========================\n"
 273             << "Results:\n"
 274             << "=========================\n"
 275             << stats;
 276
 277   return 0;
 278 }
 279
 280 #endif  // GFLAGS