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>
main()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 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
operator <<(std::ostream & os,const Stats & s)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_NAMESPACE::InternalKeyComparator(
88 ROCKSDB_NAMESPACE::BytewiseComparator());
89
90 } // anonymous namespace
91
92 namespace ROCKSDB_NAMESPACE {
93
94 namespace {
95
96 // A wrapper around RangeTombstones and the underlying data of its start and end
97 // keys.
98 struct PersistentRangeTombstone {
99 std::string start_key;
100 std::string end_key;
101 RangeTombstone tombstone;
102
PersistentRangeTombstoneROCKSDB_NAMESPACE::__anon48870ef20211::PersistentRangeTombstone103 PersistentRangeTombstone(std::string start, std::string end,
104 SequenceNumber seq)
105 : start_key(std::move(start)), end_key(std::move(end)) {
106 tombstone = RangeTombstone(start_key, end_key, seq);
107 }
108
109 PersistentRangeTombstone() = default;
110
PersistentRangeTombstoneROCKSDB_NAMESPACE::__anon48870ef20211::PersistentRangeTombstone111 PersistentRangeTombstone(const PersistentRangeTombstone& t) { *this = t; }
112
operator =ROCKSDB_NAMESPACE::__anon48870ef20211::PersistentRangeTombstone113 PersistentRangeTombstone& operator=(const PersistentRangeTombstone& t) {
114 start_key = t.start_key;
115 end_key = t.end_key;
116 tombstone = RangeTombstone(start_key, end_key, t.tombstone.seq_);
117
118 return *this;
119 }
120
PersistentRangeTombstoneROCKSDB_NAMESPACE::__anon48870ef20211::PersistentRangeTombstone121 PersistentRangeTombstone(PersistentRangeTombstone&& t) noexcept { *this = t; }
122
operator =ROCKSDB_NAMESPACE::__anon48870ef20211::PersistentRangeTombstone123 PersistentRangeTombstone& operator=(PersistentRangeTombstone&& t) {
124 start_key = std::move(t.start_key);
125 end_key = std::move(t.end_key);
126 tombstone = RangeTombstone(start_key, end_key, t.tombstone.seq_);
127
128 return *this;
129 }
130 };
131
132 struct TombstoneStartKeyComparator {
TombstoneStartKeyComparatorROCKSDB_NAMESPACE::__anon48870ef20211::TombstoneStartKeyComparator133 explicit TombstoneStartKeyComparator(const Comparator* c) : cmp(c) {}
134
operator ()ROCKSDB_NAMESPACE::__anon48870ef20211::TombstoneStartKeyComparator135 bool operator()(const RangeTombstone& a, const RangeTombstone& b) const {
136 return cmp->Compare(a.start_key_, b.start_key_) < 0;
137 }
138
139 const Comparator* cmp;
140 };
141
MakeRangeDelIterator(const std::vector<PersistentRangeTombstone> & range_dels)142 std::unique_ptr<InternalIterator> MakeRangeDelIterator(
143 const std::vector<PersistentRangeTombstone>& range_dels) {
144 std::vector<std::string> keys, values;
145 for (const auto& range_del : range_dels) {
146 auto key_and_value = range_del.tombstone.Serialize();
147 keys.push_back(key_and_value.first.Encode().ToString());
148 values.push_back(key_and_value.second.ToString());
149 }
150 return std::unique_ptr<VectorIterator>(
151 new VectorIterator(keys, values, &icmp));
152 }
153
154 // convert long to a big-endian slice key
Key(int64_t val)155 static std::string Key(int64_t val) {
156 std::string little_endian_key;
157 std::string big_endian_key;
158 PutFixed64(&little_endian_key, val);
159 assert(little_endian_key.size() == sizeof(val));
160 big_endian_key.resize(sizeof(val));
161 for (size_t i = 0; i < sizeof(val); ++i) {
162 big_endian_key[i] = little_endian_key[sizeof(val) - 1 - i];
163 }
164 return big_endian_key;
165 }
166
167 } // anonymous namespace
168
169 } // namespace ROCKSDB_NAMESPACE
170
main(int argc,char ** argv)171 int main(int argc, char** argv) {
172 ParseCommandLineFlags(&argc, &argv, true);
173
174 Stats stats;
175 ROCKSDB_NAMESPACE::SystemClock* clock =
176 ROCKSDB_NAMESPACE::SystemClock::Default().get();
177 ROCKSDB_NAMESPACE::Random64 rnd(FLAGS_seed);
178 std::default_random_engine random_gen(FLAGS_seed);
179 std::normal_distribution<double> normal_dist(FLAGS_tombstone_width_mean,
180 FLAGS_tombstone_width_stddev);
181 std::vector<std::vector<ROCKSDB_NAMESPACE::PersistentRangeTombstone> >
182 all_persistent_range_tombstones(FLAGS_add_tombstones_per_run);
183 for (int i = 0; i < FLAGS_add_tombstones_per_run; i++) {
184 all_persistent_range_tombstones[i] =
185 std::vector<ROCKSDB_NAMESPACE::PersistentRangeTombstone>(
186 FLAGS_num_range_tombstones);
187 }
188 auto mode = ROCKSDB_NAMESPACE::RangeDelPositioningMode::kForwardTraversal;
189
190 for (int i = 0; i < FLAGS_num_runs; i++) {
191 ROCKSDB_NAMESPACE::ReadRangeDelAggregator range_del_agg(
192 &icmp, ROCKSDB_NAMESPACE::kMaxSequenceNumber /* upper_bound */);
193
194 std::vector<
195 std::unique_ptr<ROCKSDB_NAMESPACE::FragmentedRangeTombstoneList> >
196 fragmented_range_tombstone_lists(FLAGS_add_tombstones_per_run);
197
198 for (auto& persistent_range_tombstones : all_persistent_range_tombstones) {
199 // TODO(abhimadan): consider whether creating the range tombstones right
200 // before AddTombstones is artificially warming the cache compared to
201 // real workloads.
202 for (int j = 0; j < FLAGS_num_range_tombstones; j++) {
203 uint64_t start = rnd.Uniform(FLAGS_tombstone_start_upper_bound);
204 uint64_t end = static_cast<uint64_t>(
205 std::round(start + std::max(1.0, normal_dist(random_gen))));
206 persistent_range_tombstones[j] =
207 ROCKSDB_NAMESPACE::PersistentRangeTombstone(
208 ROCKSDB_NAMESPACE::Key(start), ROCKSDB_NAMESPACE::Key(end), j);
209 }
210
211 fragmented_range_tombstone_lists.emplace_back(
212 new ROCKSDB_NAMESPACE::FragmentedRangeTombstoneList(
213 ROCKSDB_NAMESPACE::MakeRangeDelIterator(
214 persistent_range_tombstones),
215 icmp));
216 std::unique_ptr<ROCKSDB_NAMESPACE::FragmentedRangeTombstoneIterator>
217 fragmented_range_del_iter(
218 new ROCKSDB_NAMESPACE::FragmentedRangeTombstoneIterator(
219 fragmented_range_tombstone_lists.back().get(), icmp,
220 ROCKSDB_NAMESPACE::kMaxSequenceNumber));
221
222 ROCKSDB_NAMESPACE::StopWatchNano stop_watch_add_tombstones(
223 clock, true /* auto_start */);
224 range_del_agg.AddTombstones(std::move(fragmented_range_del_iter));
225 stats.time_add_tombstones += stop_watch_add_tombstones.ElapsedNanos();
226 }
227
228 ROCKSDB_NAMESPACE::ParsedInternalKey parsed_key;
229 parsed_key.sequence = FLAGS_num_range_tombstones / 2;
230 parsed_key.type = ROCKSDB_NAMESPACE::kTypeValue;
231
232 uint64_t first_key = rnd.Uniform(FLAGS_should_delete_upper_bound -
233 FLAGS_should_deletes_per_run + 1);
234
235 for (int j = 0; j < FLAGS_should_deletes_per_run; j++) {
236 std::string key_string = ROCKSDB_NAMESPACE::Key(first_key + j);
237 parsed_key.user_key = key_string;
238
239 ROCKSDB_NAMESPACE::StopWatchNano stop_watch_should_delete(
240 clock, true /* auto_start */);
241 range_del_agg.ShouldDelete(parsed_key, mode);
242 uint64_t call_time = stop_watch_should_delete.ElapsedNanos();
243
244 if (j == 0) {
245 stats.time_first_should_delete += call_time;
246 } else {
247 stats.time_rest_should_delete += call_time;
248 }
249 }
250 }
251
252 std::cout << "=========================\n"
253 << "Results:\n"
254 << "=========================\n"
255 << stats;
256
257 return 0;
258 }
259
260 #endif // GFLAGS
261