]>
Commit | Line | Data |
---|---|---|
7c673cae | 1 | // Copyright (c) 2011-present, Facebook, Inc. All rights reserved. |
11fdf7f2 TL |
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). | |
7c673cae FG |
5 | |
6 | #ifndef ROCKSDB_LITE | |
7 | ||
8 | #ifndef GFLAGS | |
9 | #include <cstdio> | |
10 | int main() { | |
11 | fprintf(stderr, "Please install gflags to run this test... Skipping...\n"); | |
12 | return 0; | |
13 | } | |
14 | #else | |
15 | ||
16 | #include <algorithm> | |
17 | #include <iostream> | |
18 | #include <vector> | |
19 | ||
f67539c2 | 20 | #include "db/db_impl/db_impl.h" |
7c673cae FG |
21 | #include "monitoring/histogram.h" |
22 | #include "rocksdb/comparator.h" | |
23 | #include "rocksdb/db.h" | |
24 | #include "rocksdb/filter_policy.h" | |
25 | #include "rocksdb/memtablerep.h" | |
26 | #include "rocksdb/perf_context.h" | |
27 | #include "rocksdb/slice_transform.h" | |
1e59de90 | 28 | #include "rocksdb/system_clock.h" |
7c673cae | 29 | #include "rocksdb/table.h" |
f67539c2 | 30 | #include "test_util/testharness.h" |
20effc67 | 31 | #include "util/cast_util.h" |
11fdf7f2 TL |
32 | #include "util/coding.h" |
33 | #include "util/gflags_compat.h" | |
7c673cae FG |
34 | #include "util/random.h" |
35 | #include "util/stop_watch.h" | |
36 | #include "util/string_util.h" | |
7c673cae | 37 | #include "utilities/merge_operators.h" |
7c673cae | 38 | |
11fdf7f2 | 39 | using GFLAGS_NAMESPACE::ParseCommandLineFlags; |
7c673cae FG |
40 | |
41 | DEFINE_bool(trigger_deadlock, false, | |
42 | "issue delete in range scan to trigger PrefixHashMap deadlock"); | |
43 | DEFINE_int32(bucket_count, 100000, "number of buckets"); | |
44 | DEFINE_uint64(num_locks, 10001, "number of locks"); | |
45 | DEFINE_bool(random_prefix, false, "randomize prefix"); | |
46 | DEFINE_uint64(total_prefixes, 100000, "total number of prefixes"); | |
47 | DEFINE_uint64(items_per_prefix, 1, "total number of values per prefix"); | |
48 | DEFINE_int64(write_buffer_size, 33554432, ""); | |
49 | DEFINE_int32(max_write_buffer_number, 2, ""); | |
50 | DEFINE_int32(min_write_buffer_number_to_merge, 1, ""); | |
51 | DEFINE_int32(skiplist_height, 4, ""); | |
52 | DEFINE_double(memtable_prefix_bloom_size_ratio, 0.1, ""); | |
53 | DEFINE_int32(memtable_huge_page_size, 2 * 1024 * 1024, ""); | |
54 | DEFINE_int32(value_size, 40, ""); | |
55 | DEFINE_bool(enable_print, false, "Print options generated to console."); | |
56 | ||
57 | // Path to the database on file system | |
f67539c2 TL |
58 | const std::string kDbName = |
59 | ROCKSDB_NAMESPACE::test::PerThreadDBPath("prefix_test"); | |
7c673cae | 60 | |
f67539c2 | 61 | namespace ROCKSDB_NAMESPACE { |
7c673cae FG |
62 | |
63 | struct TestKey { | |
64 | uint64_t prefix; | |
65 | uint64_t sorted; | |
66 | ||
67 | TestKey(uint64_t _prefix, uint64_t _sorted) | |
68 | : prefix(_prefix), sorted(_sorted) {} | |
69 | }; | |
70 | ||
71 | // return a slice backed by test_key | |
1e59de90 | 72 | inline Slice TestKeyToSlice(std::string& s, const TestKey& test_key) { |
7c673cae FG |
73 | s.clear(); |
74 | PutFixed64(&s, test_key.prefix); | |
75 | PutFixed64(&s, test_key.sorted); | |
76 | return Slice(s.c_str(), s.size()); | |
77 | } | |
78 | ||
79 | inline const TestKey SliceToTestKey(const Slice& slice) { | |
1e59de90 | 80 | return TestKey(DecodeFixed64(slice.data()), DecodeFixed64(slice.data() + 8)); |
7c673cae FG |
81 | } |
82 | ||
83 | class TestKeyComparator : public Comparator { | |
84 | public: | |
7c673cae FG |
85 | // Compare needs to be aware of the possibility of a and/or b is |
86 | // prefix only | |
494da23a | 87 | int Compare(const Slice& a, const Slice& b) const override { |
7c673cae FG |
88 | const TestKey kkey_a = SliceToTestKey(a); |
89 | const TestKey kkey_b = SliceToTestKey(b); | |
1e59de90 TL |
90 | const TestKey* key_a = &kkey_a; |
91 | const TestKey* key_b = &kkey_b; | |
7c673cae FG |
92 | if (key_a->prefix != key_b->prefix) { |
93 | if (key_a->prefix < key_b->prefix) return -1; | |
94 | if (key_a->prefix > key_b->prefix) return 1; | |
95 | } else { | |
96 | EXPECT_TRUE(key_a->prefix == key_b->prefix); | |
97 | // note, both a and b could be prefix only | |
98 | if (a.size() != b.size()) { | |
99 | // one of them is prefix | |
100 | EXPECT_TRUE( | |
101 | (a.size() == sizeof(uint64_t) && b.size() == sizeof(TestKey)) || | |
102 | (b.size() == sizeof(uint64_t) && a.size() == sizeof(TestKey))); | |
103 | if (a.size() < b.size()) return -1; | |
104 | if (a.size() > b.size()) return 1; | |
105 | } else { | |
106 | // both a and b are prefix | |
107 | if (a.size() == sizeof(uint64_t)) { | |
108 | return 0; | |
109 | } | |
110 | ||
111 | // both a and b are whole key | |
112 | EXPECT_TRUE(a.size() == sizeof(TestKey) && b.size() == sizeof(TestKey)); | |
113 | if (key_a->sorted < key_b->sorted) return -1; | |
114 | if (key_a->sorted > key_b->sorted) return 1; | |
115 | if (key_a->sorted == key_b->sorted) return 0; | |
116 | } | |
117 | } | |
118 | return 0; | |
119 | } | |
120 | ||
121 | bool operator()(const TestKey& a, const TestKey& b) const { | |
122 | std::string sa, sb; | |
123 | return Compare(TestKeyToSlice(sa, a), TestKeyToSlice(sb, b)) < 0; | |
124 | } | |
125 | ||
494da23a | 126 | const char* Name() const override { return "TestKeyComparator"; } |
7c673cae | 127 | |
494da23a TL |
128 | void FindShortestSeparator(std::string* /*start*/, |
129 | const Slice& /*limit*/) const override {} | |
7c673cae | 130 | |
494da23a | 131 | void FindShortSuccessor(std::string* /*key*/) const override {} |
7c673cae FG |
132 | }; |
133 | ||
134 | namespace { | |
135 | void PutKey(DB* db, WriteOptions write_options, uint64_t prefix, | |
136 | uint64_t suffix, const Slice& value) { | |
137 | TestKey test_key(prefix, suffix); | |
138 | std::string s; | |
139 | Slice key = TestKeyToSlice(s, test_key); | |
140 | ASSERT_OK(db->Put(write_options, key, value)); | |
141 | } | |
142 | ||
143 | void PutKey(DB* db, WriteOptions write_options, const TestKey& test_key, | |
144 | const Slice& value) { | |
145 | std::string s; | |
146 | Slice key = TestKeyToSlice(s, test_key); | |
147 | ASSERT_OK(db->Put(write_options, key, value)); | |
148 | } | |
149 | ||
150 | void MergeKey(DB* db, WriteOptions write_options, const TestKey& test_key, | |
151 | const Slice& value) { | |
152 | std::string s; | |
153 | Slice key = TestKeyToSlice(s, test_key); | |
154 | ASSERT_OK(db->Merge(write_options, key, value)); | |
155 | } | |
156 | ||
157 | void DeleteKey(DB* db, WriteOptions write_options, const TestKey& test_key) { | |
158 | std::string s; | |
159 | Slice key = TestKeyToSlice(s, test_key); | |
160 | ASSERT_OK(db->Delete(write_options, key)); | |
161 | } | |
162 | ||
163 | void SeekIterator(Iterator* iter, uint64_t prefix, uint64_t suffix) { | |
164 | TestKey test_key(prefix, suffix); | |
165 | std::string s; | |
166 | Slice key = TestKeyToSlice(s, test_key); | |
167 | iter->Seek(key); | |
168 | } | |
169 | ||
170 | const std::string kNotFoundResult = "NOT_FOUND"; | |
171 | ||
172 | std::string Get(DB* db, const ReadOptions& read_options, uint64_t prefix, | |
173 | uint64_t suffix) { | |
174 | TestKey test_key(prefix, suffix); | |
175 | std::string s2; | |
176 | Slice key = TestKeyToSlice(s2, test_key); | |
177 | ||
178 | std::string result; | |
179 | Status s = db->Get(read_options, key, &result); | |
180 | if (s.IsNotFound()) { | |
181 | result = kNotFoundResult; | |
182 | } else if (!s.ok()) { | |
183 | result = s.ToString(); | |
184 | } | |
185 | return result; | |
186 | } | |
187 | ||
188 | class SamePrefixTransform : public SliceTransform { | |
189 | private: | |
190 | const Slice prefix_; | |
191 | std::string name_; | |
192 | ||
193 | public: | |
194 | explicit SamePrefixTransform(const Slice& prefix) | |
195 | : prefix_(prefix), name_("rocksdb.SamePrefix." + prefix.ToString()) {} | |
196 | ||
494da23a | 197 | const char* Name() const override { return name_.c_str(); } |
7c673cae | 198 | |
494da23a | 199 | Slice Transform(const Slice& src) const override { |
7c673cae FG |
200 | assert(InDomain(src)); |
201 | return prefix_; | |
202 | } | |
203 | ||
494da23a | 204 | bool InDomain(const Slice& src) const override { |
7c673cae FG |
205 | if (src.size() >= prefix_.size()) { |
206 | return Slice(src.data(), prefix_.size()) == prefix_; | |
207 | } | |
208 | return false; | |
209 | } | |
210 | ||
494da23a | 211 | bool InRange(const Slice& dst) const override { return dst == prefix_; } |
11fdf7f2 | 212 | |
494da23a | 213 | bool FullLengthEnabled(size_t* /*len*/) const override { return false; } |
7c673cae FG |
214 | }; |
215 | ||
1e59de90 | 216 | } // anonymous namespace |
7c673cae FG |
217 | |
218 | class PrefixTest : public testing::Test { | |
219 | public: | |
220 | std::shared_ptr<DB> OpenDb() { | |
221 | DB* db; | |
222 | ||
223 | options.create_if_missing = true; | |
224 | options.write_buffer_size = FLAGS_write_buffer_size; | |
225 | options.max_write_buffer_number = FLAGS_max_write_buffer_number; | |
226 | options.min_write_buffer_number_to_merge = | |
1e59de90 | 227 | FLAGS_min_write_buffer_number_to_merge; |
7c673cae FG |
228 | |
229 | options.memtable_prefix_bloom_size_ratio = | |
230 | FLAGS_memtable_prefix_bloom_size_ratio; | |
231 | options.memtable_huge_page_size = FLAGS_memtable_huge_page_size; | |
232 | ||
233 | options.prefix_extractor.reset(NewFixedPrefixTransform(8)); | |
234 | BlockBasedTableOptions bbto; | |
235 | bbto.filter_policy.reset(NewBloomFilterPolicy(10, false)); | |
236 | bbto.whole_key_filtering = false; | |
237 | options.table_factory.reset(NewBlockBasedTableFactory(bbto)); | |
238 | options.allow_concurrent_memtable_write = false; | |
239 | ||
1e59de90 | 240 | Status s = DB::Open(options, kDbName, &db); |
7c673cae FG |
241 | EXPECT_OK(s); |
242 | return std::shared_ptr<DB>(db); | |
243 | } | |
244 | ||
1e59de90 | 245 | void FirstOption() { option_config_ = kBegin; } |
7c673cae FG |
246 | |
247 | bool NextOptions(int bucket_count) { | |
248 | // skip some options | |
249 | option_config_++; | |
250 | if (option_config_ < kEnd) { | |
251 | options.prefix_extractor.reset(NewFixedPrefixTransform(8)); | |
1e59de90 | 252 | switch (option_config_) { |
7c673cae FG |
253 | case kHashSkipList: |
254 | options.memtable_factory.reset( | |
255 | NewHashSkipListRepFactory(bucket_count, FLAGS_skiplist_height)); | |
256 | return true; | |
257 | case kHashLinkList: | |
258 | options.memtable_factory.reset( | |
259 | NewHashLinkListRepFactory(bucket_count)); | |
260 | return true; | |
261 | case kHashLinkListHugePageTlb: | |
262 | options.memtable_factory.reset( | |
263 | NewHashLinkListRepFactory(bucket_count, 2 * 1024 * 1024)); | |
264 | return true; | |
265 | case kHashLinkListTriggerSkipList: | |
266 | options.memtable_factory.reset( | |
267 | NewHashLinkListRepFactory(bucket_count, 0, 3)); | |
268 | return true; | |
269 | default: | |
270 | return false; | |
271 | } | |
272 | } | |
273 | return false; | |
274 | } | |
275 | ||
276 | PrefixTest() : option_config_(kBegin) { | |
277 | options.comparator = new TestKeyComparator(); | |
278 | } | |
494da23a TL |
279 | ~PrefixTest() override { delete options.comparator; } |
280 | ||
7c673cae FG |
281 | protected: |
282 | enum OptionConfig { | |
283 | kBegin, | |
284 | kHashSkipList, | |
285 | kHashLinkList, | |
286 | kHashLinkListHugePageTlb, | |
287 | kHashLinkListTriggerSkipList, | |
288 | kEnd | |
289 | }; | |
290 | int option_config_; | |
291 | Options options; | |
292 | }; | |
293 | ||
294 | TEST(SamePrefixTest, InDomainTest) { | |
295 | DB* db; | |
296 | Options options; | |
297 | options.create_if_missing = true; | |
298 | options.prefix_extractor.reset(new SamePrefixTransform("HHKB")); | |
299 | BlockBasedTableOptions bbto; | |
300 | bbto.filter_policy.reset(NewBloomFilterPolicy(10, false)); | |
301 | bbto.whole_key_filtering = false; | |
302 | options.table_factory.reset(NewBlockBasedTableFactory(bbto)); | |
303 | WriteOptions write_options; | |
304 | ReadOptions read_options; | |
305 | { | |
306 | ASSERT_OK(DestroyDB(kDbName, Options())); | |
307 | ASSERT_OK(DB::Open(options, kDbName, &db)); | |
308 | ASSERT_OK(db->Put(write_options, "HHKB pro2", "Mar 24, 2006")); | |
309 | ASSERT_OK(db->Put(write_options, "HHKB pro2 Type-S", "June 29, 2011")); | |
310 | ASSERT_OK(db->Put(write_options, "Realforce 87u", "idk")); | |
1e59de90 | 311 | ASSERT_OK(db->Flush(FlushOptions())); |
7c673cae FG |
312 | std::string result; |
313 | auto db_iter = db->NewIterator(ReadOptions()); | |
314 | ||
315 | db_iter->Seek("Realforce 87u"); | |
316 | ASSERT_TRUE(db_iter->Valid()); | |
317 | ASSERT_OK(db_iter->status()); | |
318 | ASSERT_EQ(db_iter->key(), "Realforce 87u"); | |
319 | ASSERT_EQ(db_iter->value(), "idk"); | |
320 | ||
321 | delete db_iter; | |
322 | delete db; | |
323 | ASSERT_OK(DestroyDB(kDbName, Options())); | |
324 | } | |
325 | ||
326 | { | |
327 | ASSERT_OK(DB::Open(options, kDbName, &db)); | |
328 | ASSERT_OK(db->Put(write_options, "pikachu", "1")); | |
329 | ASSERT_OK(db->Put(write_options, "Meowth", "1")); | |
330 | ASSERT_OK(db->Put(write_options, "Mewtwo", "idk")); | |
1e59de90 | 331 | ASSERT_OK(db->Flush(FlushOptions())); |
7c673cae FG |
332 | std::string result; |
333 | auto db_iter = db->NewIterator(ReadOptions()); | |
334 | ||
335 | db_iter->Seek("Mewtwo"); | |
336 | ASSERT_TRUE(db_iter->Valid()); | |
337 | ASSERT_OK(db_iter->status()); | |
338 | delete db_iter; | |
339 | delete db; | |
340 | ASSERT_OK(DestroyDB(kDbName, Options())); | |
341 | } | |
342 | } | |
343 | ||
344 | TEST_F(PrefixTest, TestResult) { | |
345 | for (int num_buckets = 1; num_buckets <= 2; num_buckets++) { | |
346 | FirstOption(); | |
347 | while (NextOptions(num_buckets)) { | |
348 | std::cout << "*** Mem table: " << options.memtable_factory->Name() | |
1e59de90 TL |
349 | << " number of buckets: " << num_buckets << std::endl; |
350 | ASSERT_OK(DestroyDB(kDbName, Options())); | |
7c673cae FG |
351 | auto db = OpenDb(); |
352 | WriteOptions write_options; | |
353 | ReadOptions read_options; | |
354 | ||
355 | // 1. Insert one row. | |
356 | Slice v16("v16"); | |
357 | PutKey(db.get(), write_options, 1, 6, v16); | |
358 | std::unique_ptr<Iterator> iter(db->NewIterator(read_options)); | |
359 | SeekIterator(iter.get(), 1, 6); | |
360 | ASSERT_TRUE(iter->Valid()); | |
361 | ASSERT_TRUE(v16 == iter->value()); | |
362 | SeekIterator(iter.get(), 1, 5); | |
363 | ASSERT_TRUE(iter->Valid()); | |
364 | ASSERT_TRUE(v16 == iter->value()); | |
365 | SeekIterator(iter.get(), 1, 5); | |
366 | ASSERT_TRUE(iter->Valid()); | |
367 | ASSERT_TRUE(v16 == iter->value()); | |
368 | iter->Next(); | |
369 | ASSERT_TRUE(!iter->Valid()); | |
20effc67 | 370 | ASSERT_OK(iter->status()); |
7c673cae FG |
371 | |
372 | SeekIterator(iter.get(), 2, 0); | |
373 | ASSERT_TRUE(!iter->Valid()); | |
20effc67 | 374 | ASSERT_OK(iter->status()); |
7c673cae FG |
375 | |
376 | ASSERT_EQ(v16.ToString(), Get(db.get(), read_options, 1, 6)); | |
377 | ASSERT_EQ(kNotFoundResult, Get(db.get(), read_options, 1, 5)); | |
378 | ASSERT_EQ(kNotFoundResult, Get(db.get(), read_options, 1, 7)); | |
379 | ASSERT_EQ(kNotFoundResult, Get(db.get(), read_options, 0, 6)); | |
380 | ASSERT_EQ(kNotFoundResult, Get(db.get(), read_options, 2, 6)); | |
381 | ||
382 | // 2. Insert an entry for the same prefix as the last entry in the bucket. | |
383 | Slice v17("v17"); | |
384 | PutKey(db.get(), write_options, 1, 7, v17); | |
385 | iter.reset(db->NewIterator(read_options)); | |
386 | SeekIterator(iter.get(), 1, 7); | |
387 | ASSERT_TRUE(iter->Valid()); | |
388 | ASSERT_TRUE(v17 == iter->value()); | |
389 | ||
390 | SeekIterator(iter.get(), 1, 6); | |
391 | ASSERT_TRUE(iter->Valid()); | |
392 | ASSERT_TRUE(v16 == iter->value()); | |
393 | iter->Next(); | |
394 | ASSERT_TRUE(iter->Valid()); | |
395 | ASSERT_TRUE(v17 == iter->value()); | |
396 | iter->Next(); | |
397 | ASSERT_TRUE(!iter->Valid()); | |
20effc67 | 398 | ASSERT_OK(iter->status()); |
7c673cae FG |
399 | |
400 | SeekIterator(iter.get(), 2, 0); | |
401 | ASSERT_TRUE(!iter->Valid()); | |
20effc67 | 402 | ASSERT_OK(iter->status()); |
7c673cae FG |
403 | |
404 | // 3. Insert an entry for the same prefix as the head of the bucket. | |
405 | Slice v15("v15"); | |
406 | PutKey(db.get(), write_options, 1, 5, v15); | |
407 | iter.reset(db->NewIterator(read_options)); | |
408 | ||
409 | SeekIterator(iter.get(), 1, 7); | |
410 | ASSERT_TRUE(iter->Valid()); | |
411 | ASSERT_TRUE(v17 == iter->value()); | |
412 | ||
413 | SeekIterator(iter.get(), 1, 5); | |
414 | ASSERT_TRUE(iter->Valid()); | |
415 | ASSERT_TRUE(v15 == iter->value()); | |
416 | iter->Next(); | |
417 | ASSERT_TRUE(iter->Valid()); | |
418 | ASSERT_TRUE(v16 == iter->value()); | |
419 | iter->Next(); | |
420 | ASSERT_TRUE(iter->Valid()); | |
421 | ASSERT_TRUE(v17 == iter->value()); | |
422 | ||
423 | SeekIterator(iter.get(), 1, 5); | |
424 | ASSERT_TRUE(iter->Valid()); | |
425 | ASSERT_TRUE(v15 == iter->value()); | |
426 | ||
427 | ASSERT_EQ(v15.ToString(), Get(db.get(), read_options, 1, 5)); | |
428 | ASSERT_EQ(v16.ToString(), Get(db.get(), read_options, 1, 6)); | |
429 | ASSERT_EQ(v17.ToString(), Get(db.get(), read_options, 1, 7)); | |
430 | ||
431 | // 4. Insert an entry with a larger prefix | |
432 | Slice v22("v22"); | |
433 | PutKey(db.get(), write_options, 2, 2, v22); | |
434 | iter.reset(db->NewIterator(read_options)); | |
435 | ||
436 | SeekIterator(iter.get(), 2, 2); | |
437 | ASSERT_TRUE(iter->Valid()); | |
438 | ASSERT_TRUE(v22 == iter->value()); | |
439 | SeekIterator(iter.get(), 2, 0); | |
440 | ASSERT_TRUE(iter->Valid()); | |
441 | ASSERT_TRUE(v22 == iter->value()); | |
442 | ||
443 | SeekIterator(iter.get(), 1, 5); | |
444 | ASSERT_TRUE(iter->Valid()); | |
445 | ASSERT_TRUE(v15 == iter->value()); | |
446 | ||
447 | SeekIterator(iter.get(), 1, 7); | |
448 | ASSERT_TRUE(iter->Valid()); | |
449 | ASSERT_TRUE(v17 == iter->value()); | |
450 | ||
451 | // 5. Insert an entry with a smaller prefix | |
452 | Slice v02("v02"); | |
453 | PutKey(db.get(), write_options, 0, 2, v02); | |
454 | iter.reset(db->NewIterator(read_options)); | |
455 | ||
456 | SeekIterator(iter.get(), 0, 2); | |
457 | ASSERT_TRUE(iter->Valid()); | |
458 | ASSERT_TRUE(v02 == iter->value()); | |
459 | SeekIterator(iter.get(), 0, 0); | |
460 | ASSERT_TRUE(iter->Valid()); | |
461 | ASSERT_TRUE(v02 == iter->value()); | |
462 | ||
463 | SeekIterator(iter.get(), 2, 0); | |
464 | ASSERT_TRUE(iter->Valid()); | |
465 | ASSERT_TRUE(v22 == iter->value()); | |
466 | ||
467 | SeekIterator(iter.get(), 1, 5); | |
468 | ASSERT_TRUE(iter->Valid()); | |
469 | ASSERT_TRUE(v15 == iter->value()); | |
470 | ||
471 | SeekIterator(iter.get(), 1, 7); | |
472 | ASSERT_TRUE(iter->Valid()); | |
473 | ASSERT_TRUE(v17 == iter->value()); | |
474 | ||
475 | // 6. Insert to the beginning and the end of the first prefix | |
476 | Slice v13("v13"); | |
477 | Slice v18("v18"); | |
478 | PutKey(db.get(), write_options, 1, 3, v13); | |
479 | PutKey(db.get(), write_options, 1, 8, v18); | |
480 | iter.reset(db->NewIterator(read_options)); | |
481 | SeekIterator(iter.get(), 1, 7); | |
482 | ASSERT_TRUE(iter->Valid()); | |
483 | ASSERT_TRUE(v17 == iter->value()); | |
484 | ||
485 | SeekIterator(iter.get(), 1, 3); | |
486 | ASSERT_TRUE(iter->Valid()); | |
487 | ASSERT_TRUE(v13 == iter->value()); | |
488 | iter->Next(); | |
489 | ASSERT_TRUE(iter->Valid()); | |
490 | ASSERT_TRUE(v15 == iter->value()); | |
491 | iter->Next(); | |
492 | ASSERT_TRUE(iter->Valid()); | |
493 | ASSERT_TRUE(v16 == iter->value()); | |
494 | iter->Next(); | |
495 | ASSERT_TRUE(iter->Valid()); | |
496 | ASSERT_TRUE(v17 == iter->value()); | |
497 | iter->Next(); | |
498 | ASSERT_TRUE(iter->Valid()); | |
499 | ASSERT_TRUE(v18 == iter->value()); | |
500 | ||
501 | SeekIterator(iter.get(), 0, 0); | |
502 | ASSERT_TRUE(iter->Valid()); | |
503 | ASSERT_TRUE(v02 == iter->value()); | |
504 | ||
505 | SeekIterator(iter.get(), 2, 0); | |
506 | ASSERT_TRUE(iter->Valid()); | |
507 | ASSERT_TRUE(v22 == iter->value()); | |
508 | ||
509 | ASSERT_EQ(v22.ToString(), Get(db.get(), read_options, 2, 2)); | |
510 | ASSERT_EQ(v02.ToString(), Get(db.get(), read_options, 0, 2)); | |
511 | ASSERT_EQ(v13.ToString(), Get(db.get(), read_options, 1, 3)); | |
512 | ASSERT_EQ(v15.ToString(), Get(db.get(), read_options, 1, 5)); | |
513 | ASSERT_EQ(v16.ToString(), Get(db.get(), read_options, 1, 6)); | |
514 | ASSERT_EQ(v17.ToString(), Get(db.get(), read_options, 1, 7)); | |
515 | ASSERT_EQ(v18.ToString(), Get(db.get(), read_options, 1, 8)); | |
516 | } | |
517 | } | |
518 | } | |
519 | ||
520 | // Show results in prefix | |
521 | TEST_F(PrefixTest, PrefixValid) { | |
522 | for (int num_buckets = 1; num_buckets <= 2; num_buckets++) { | |
523 | FirstOption(); | |
524 | while (NextOptions(num_buckets)) { | |
525 | std::cout << "*** Mem table: " << options.memtable_factory->Name() | |
526 | << " number of buckets: " << num_buckets << std::endl; | |
1e59de90 | 527 | ASSERT_OK(DestroyDB(kDbName, Options())); |
7c673cae FG |
528 | auto db = OpenDb(); |
529 | WriteOptions write_options; | |
530 | ReadOptions read_options; | |
531 | ||
532 | // Insert keys with common prefix and one key with different | |
533 | Slice v16("v16"); | |
534 | Slice v17("v17"); | |
535 | Slice v18("v18"); | |
536 | Slice v19("v19"); | |
537 | PutKey(db.get(), write_options, 12345, 6, v16); | |
538 | PutKey(db.get(), write_options, 12345, 7, v17); | |
539 | PutKey(db.get(), write_options, 12345, 8, v18); | |
540 | PutKey(db.get(), write_options, 12345, 9, v19); | |
541 | PutKey(db.get(), write_options, 12346, 8, v16); | |
1e59de90 | 542 | ASSERT_OK(db->Flush(FlushOptions())); |
7c673cae FG |
543 | TestKey test_key(12346, 8); |
544 | std::string s; | |
20effc67 TL |
545 | ASSERT_OK(db->Delete(write_options, TestKeyToSlice(s, test_key))); |
546 | ASSERT_OK(db->Flush(FlushOptions())); | |
7c673cae FG |
547 | read_options.prefix_same_as_start = true; |
548 | std::unique_ptr<Iterator> iter(db->NewIterator(read_options)); | |
549 | SeekIterator(iter.get(), 12345, 6); | |
550 | ASSERT_TRUE(iter->Valid()); | |
551 | ASSERT_TRUE(v16 == iter->value()); | |
552 | ||
553 | iter->Next(); | |
554 | ASSERT_TRUE(iter->Valid()); | |
555 | ASSERT_TRUE(v17 == iter->value()); | |
556 | ||
557 | iter->Next(); | |
558 | ASSERT_TRUE(iter->Valid()); | |
559 | ASSERT_TRUE(v18 == iter->value()); | |
560 | ||
561 | iter->Next(); | |
562 | ASSERT_TRUE(iter->Valid()); | |
563 | ASSERT_TRUE(v19 == iter->value()); | |
564 | iter->Next(); | |
565 | ASSERT_FALSE(iter->Valid()); | |
566 | ASSERT_EQ(kNotFoundResult, Get(db.get(), read_options, 12346, 8)); | |
567 | ||
568 | // Verify seeking past the prefix won't return a result. | |
569 | SeekIterator(iter.get(), 12345, 10); | |
570 | ASSERT_TRUE(!iter->Valid()); | |
20effc67 | 571 | ASSERT_OK(iter->status()); |
7c673cae FG |
572 | } |
573 | } | |
574 | } | |
575 | ||
576 | TEST_F(PrefixTest, DynamicPrefixIterator) { | |
577 | while (NextOptions(FLAGS_bucket_count)) { | |
578 | std::cout << "*** Mem table: " << options.memtable_factory->Name() | |
1e59de90 TL |
579 | << std::endl; |
580 | ASSERT_OK(DestroyDB(kDbName, Options())); | |
7c673cae FG |
581 | auto db = OpenDb(); |
582 | WriteOptions write_options; | |
583 | ReadOptions read_options; | |
584 | ||
585 | std::vector<uint64_t> prefixes; | |
586 | for (uint64_t i = 0; i < FLAGS_total_prefixes; ++i) { | |
587 | prefixes.push_back(i); | |
588 | } | |
589 | ||
590 | if (FLAGS_random_prefix) { | |
20effc67 | 591 | RandomShuffle(prefixes.begin(), prefixes.end()); |
7c673cae FG |
592 | } |
593 | ||
594 | HistogramImpl hist_put_time; | |
595 | HistogramImpl hist_put_comparison; | |
7c673cae FG |
596 | // insert x random prefix, each with y continuous element. |
597 | for (auto prefix : prefixes) { | |
1e59de90 | 598 | for (uint64_t sorted = 0; sorted < FLAGS_items_per_prefix; sorted++) { |
7c673cae FG |
599 | TestKey test_key(prefix, sorted); |
600 | ||
601 | std::string s; | |
602 | Slice key = TestKeyToSlice(s, test_key); | |
603 | std::string value(FLAGS_value_size, 0); | |
604 | ||
11fdf7f2 | 605 | get_perf_context()->Reset(); |
1e59de90 | 606 | StopWatchNano timer(SystemClock::Default().get(), true); |
7c673cae FG |
607 | ASSERT_OK(db->Put(write_options, key, value)); |
608 | hist_put_time.Add(timer.ElapsedNanos()); | |
11fdf7f2 | 609 | hist_put_comparison.Add(get_perf_context()->user_key_comparison_count); |
7c673cae FG |
610 | } |
611 | } | |
612 | ||
1e59de90 TL |
613 | std::cout << "Put key comparison: \n" |
614 | << hist_put_comparison.ToString() << "Put time: \n" | |
615 | << hist_put_time.ToString(); | |
7c673cae FG |
616 | |
617 | // test seek existing keys | |
618 | HistogramImpl hist_seek_time; | |
619 | HistogramImpl hist_seek_comparison; | |
620 | ||
621 | std::unique_ptr<Iterator> iter(db->NewIterator(read_options)); | |
622 | ||
623 | for (auto prefix : prefixes) { | |
624 | TestKey test_key(prefix, FLAGS_items_per_prefix / 2); | |
625 | std::string s; | |
626 | Slice key = TestKeyToSlice(s, test_key); | |
1e59de90 | 627 | std::string value = "v" + std::to_string(0); |
7c673cae | 628 | |
11fdf7f2 | 629 | get_perf_context()->Reset(); |
1e59de90 | 630 | StopWatchNano timer(SystemClock::Default().get(), true); |
7c673cae FG |
631 | auto key_prefix = options.prefix_extractor->Transform(key); |
632 | uint64_t total_keys = 0; | |
633 | for (iter->Seek(key); | |
1e59de90 | 634 | iter->Valid() && iter->key().starts_with(key_prefix); iter->Next()) { |
7c673cae FG |
635 | if (FLAGS_trigger_deadlock) { |
636 | std::cout << "Behold the deadlock!\n"; | |
637 | db->Delete(write_options, iter->key()); | |
638 | } | |
639 | total_keys++; | |
640 | } | |
641 | hist_seek_time.Add(timer.ElapsedNanos()); | |
11fdf7f2 | 642 | hist_seek_comparison.Add(get_perf_context()->user_key_comparison_count); |
1e59de90 TL |
643 | ASSERT_EQ(total_keys, |
644 | FLAGS_items_per_prefix - FLAGS_items_per_prefix / 2); | |
7c673cae FG |
645 | } |
646 | ||
647 | std::cout << "Seek key comparison: \n" | |
1e59de90 | 648 | << hist_seek_comparison.ToString() << "Seek time: \n" |
7c673cae FG |
649 | << hist_seek_time.ToString(); |
650 | ||
651 | // test non-existing keys | |
652 | HistogramImpl hist_no_seek_time; | |
653 | HistogramImpl hist_no_seek_comparison; | |
654 | ||
655 | for (auto prefix = FLAGS_total_prefixes; | |
1e59de90 | 656 | prefix < FLAGS_total_prefixes + 10000; prefix++) { |
7c673cae FG |
657 | TestKey test_key(prefix, 0); |
658 | std::string s; | |
659 | Slice key = TestKeyToSlice(s, test_key); | |
660 | ||
11fdf7f2 | 661 | get_perf_context()->Reset(); |
1e59de90 | 662 | StopWatchNano timer(SystemClock::Default().get(), true); |
7c673cae FG |
663 | iter->Seek(key); |
664 | hist_no_seek_time.Add(timer.ElapsedNanos()); | |
1e59de90 TL |
665 | hist_no_seek_comparison.Add( |
666 | get_perf_context()->user_key_comparison_count); | |
7c673cae | 667 | ASSERT_TRUE(!iter->Valid()); |
20effc67 | 668 | ASSERT_OK(iter->status()); |
7c673cae FG |
669 | } |
670 | ||
671 | std::cout << "non-existing Seek key comparison: \n" | |
672 | << hist_no_seek_comparison.ToString() | |
673 | << "non-existing Seek time: \n" | |
674 | << hist_no_seek_time.ToString(); | |
675 | } | |
676 | } | |
677 | ||
678 | TEST_F(PrefixTest, PrefixSeekModePrev) { | |
679 | // Only for SkipListFactory | |
680 | options.memtable_factory.reset(new SkipListFactory); | |
681 | options.merge_operator = MergeOperators::CreatePutOperator(); | |
682 | options.write_buffer_size = 1024 * 1024; | |
683 | Random rnd(1); | |
684 | for (size_t m = 1; m < 100; m++) { | |
685 | std::cout << "[" + std::to_string(m) + "]" + "*** Mem table: " | |
686 | << options.memtable_factory->Name() << std::endl; | |
1e59de90 | 687 | ASSERT_OK(DestroyDB(kDbName, Options())); |
7c673cae FG |
688 | auto db = OpenDb(); |
689 | WriteOptions write_options; | |
690 | ReadOptions read_options; | |
691 | std::map<TestKey, std::string, TestKeyComparator> entry_maps[3], whole_map; | |
692 | for (uint64_t i = 0; i < 10; i++) { | |
693 | int div = i % 3 + 1; | |
694 | for (uint64_t j = 0; j < 10; j++) { | |
695 | whole_map[TestKey(i, j)] = entry_maps[rnd.Uniform(div)][TestKey(i, j)] = | |
696 | 'v' + std::to_string(i) + std::to_string(j); | |
697 | } | |
698 | } | |
699 | ||
700 | std::map<TestKey, std::string, TestKeyComparator> type_map; | |
701 | for (size_t i = 0; i < 3; i++) { | |
702 | for (auto& kv : entry_maps[i]) { | |
703 | if (rnd.OneIn(3)) { | |
704 | PutKey(db.get(), write_options, kv.first, kv.second); | |
705 | type_map[kv.first] = "value"; | |
706 | } else { | |
707 | MergeKey(db.get(), write_options, kv.first, kv.second); | |
708 | type_map[kv.first] = "merge"; | |
709 | } | |
710 | } | |
711 | if (i < 2) { | |
1e59de90 | 712 | ASSERT_OK(db->Flush(FlushOptions())); |
7c673cae FG |
713 | } |
714 | } | |
715 | ||
716 | for (size_t i = 0; i < 2; i++) { | |
717 | for (auto& kv : entry_maps[i]) { | |
718 | if (rnd.OneIn(10)) { | |
719 | whole_map.erase(kv.first); | |
720 | DeleteKey(db.get(), write_options, kv.first); | |
721 | entry_maps[2][kv.first] = "delete"; | |
722 | } | |
723 | } | |
724 | } | |
725 | ||
726 | if (FLAGS_enable_print) { | |
727 | for (size_t i = 0; i < 3; i++) { | |
728 | for (auto& kv : entry_maps[i]) { | |
729 | std::cout << "[" << i << "]" << kv.first.prefix << kv.first.sorted | |
730 | << " " << kv.second + " " + type_map[kv.first] << std::endl; | |
731 | } | |
732 | } | |
733 | } | |
734 | ||
735 | std::unique_ptr<Iterator> iter(db->NewIterator(read_options)); | |
736 | for (uint64_t prefix = 0; prefix < 10; prefix++) { | |
737 | uint64_t start_suffix = rnd.Uniform(9); | |
738 | SeekIterator(iter.get(), prefix, start_suffix); | |
739 | auto it = whole_map.find(TestKey(prefix, start_suffix)); | |
740 | if (it == whole_map.end()) { | |
741 | continue; | |
742 | } | |
743 | ASSERT_NE(it, whole_map.end()); | |
744 | ASSERT_TRUE(iter->Valid()); | |
745 | if (FLAGS_enable_print) { | |
746 | std::cout << "round " << prefix | |
747 | << " iter: " << SliceToTestKey(iter->key()).prefix | |
748 | << SliceToTestKey(iter->key()).sorted | |
749 | << " | map: " << it->first.prefix << it->first.sorted << " | " | |
750 | << iter->value().ToString() << " " << it->second << std::endl; | |
751 | } | |
752 | ASSERT_EQ(iter->value(), it->second); | |
753 | uint64_t stored_prefix = prefix; | |
754 | for (size_t k = 0; k < 9; k++) { | |
755 | if (rnd.OneIn(2) || it == whole_map.begin()) { | |
756 | iter->Next(); | |
f67539c2 | 757 | ++it; |
7c673cae FG |
758 | if (FLAGS_enable_print) { |
759 | std::cout << "Next >> "; | |
760 | } | |
761 | } else { | |
762 | iter->Prev(); | |
763 | it--; | |
764 | if (FLAGS_enable_print) { | |
765 | std::cout << "Prev >> "; | |
766 | } | |
767 | } | |
768 | if (!iter->Valid() || | |
769 | SliceToTestKey(iter->key()).prefix != stored_prefix) { | |
770 | break; | |
771 | } | |
20effc67 | 772 | ASSERT_OK(iter->status()); |
7c673cae FG |
773 | stored_prefix = SliceToTestKey(iter->key()).prefix; |
774 | ASSERT_TRUE(iter->Valid()); | |
775 | ASSERT_NE(it, whole_map.end()); | |
776 | ASSERT_EQ(iter->value(), it->second); | |
777 | if (FLAGS_enable_print) { | |
778 | std::cout << "iter: " << SliceToTestKey(iter->key()).prefix | |
779 | << SliceToTestKey(iter->key()).sorted | |
780 | << " | map: " << it->first.prefix << it->first.sorted | |
781 | << " | " << iter->value().ToString() << " " << it->second | |
782 | << std::endl; | |
783 | } | |
784 | } | |
785 | } | |
786 | } | |
787 | } | |
788 | ||
789 | TEST_F(PrefixTest, PrefixSeekModePrev2) { | |
790 | // Only for SkipListFactory | |
791 | // test the case | |
792 | // iter1 iter2 | |
793 | // | prefix | suffix | | prefix | suffix | | |
794 | // | 1 | 1 | | 1 | 2 | | |
795 | // | 1 | 3 | | 1 | 4 | | |
796 | // | 2 | 1 | | 3 | 3 | | |
797 | // | 2 | 2 | | 3 | 4 | | |
798 | // after seek(15), iter1 will be at 21 and iter2 will be 33. | |
799 | // Then if call Prev() in prefix mode where SeekForPrev(21) gets called, | |
800 | // iter2 should turn to invalid state because of bloom filter. | |
801 | options.memtable_factory.reset(new SkipListFactory); | |
802 | options.write_buffer_size = 1024 * 1024; | |
803 | std::string v13("v13"); | |
20effc67 | 804 | ASSERT_OK(DestroyDB(kDbName, Options())); |
7c673cae FG |
805 | auto db = OpenDb(); |
806 | WriteOptions write_options; | |
807 | ReadOptions read_options; | |
808 | PutKey(db.get(), write_options, TestKey(1, 2), "v12"); | |
809 | PutKey(db.get(), write_options, TestKey(1, 4), "v14"); | |
810 | PutKey(db.get(), write_options, TestKey(3, 3), "v33"); | |
811 | PutKey(db.get(), write_options, TestKey(3, 4), "v34"); | |
20effc67 TL |
812 | ASSERT_OK(db->Flush(FlushOptions())); |
813 | ASSERT_OK( | |
814 | static_cast_with_check<DBImpl>(db.get())->TEST_WaitForFlushMemTable()); | |
7c673cae FG |
815 | PutKey(db.get(), write_options, TestKey(1, 1), "v11"); |
816 | PutKey(db.get(), write_options, TestKey(1, 3), "v13"); | |
817 | PutKey(db.get(), write_options, TestKey(2, 1), "v21"); | |
818 | PutKey(db.get(), write_options, TestKey(2, 2), "v22"); | |
20effc67 TL |
819 | ASSERT_OK(db->Flush(FlushOptions())); |
820 | ASSERT_OK( | |
821 | static_cast_with_check<DBImpl>(db.get())->TEST_WaitForFlushMemTable()); | |
7c673cae FG |
822 | std::unique_ptr<Iterator> iter(db->NewIterator(read_options)); |
823 | SeekIterator(iter.get(), 1, 5); | |
824 | iter->Prev(); | |
20effc67 | 825 | ASSERT_TRUE(iter->Valid()); |
7c673cae FG |
826 | ASSERT_EQ(iter->value(), v13); |
827 | } | |
828 | ||
829 | TEST_F(PrefixTest, PrefixSeekModePrev3) { | |
830 | // Only for SkipListFactory | |
831 | // test SeekToLast() with iterate_upper_bound_ in prefix_seek_mode | |
832 | options.memtable_factory.reset(new SkipListFactory); | |
833 | options.write_buffer_size = 1024 * 1024; | |
834 | std::string v14("v14"); | |
835 | TestKey upper_bound_key = TestKey(1, 5); | |
836 | std::string s; | |
837 | Slice upper_bound = TestKeyToSlice(s, upper_bound_key); | |
838 | ||
839 | { | |
20effc67 | 840 | ASSERT_OK(DestroyDB(kDbName, Options())); |
7c673cae FG |
841 | auto db = OpenDb(); |
842 | WriteOptions write_options; | |
843 | ReadOptions read_options; | |
844 | read_options.iterate_upper_bound = &upper_bound; | |
845 | PutKey(db.get(), write_options, TestKey(1, 2), "v12"); | |
846 | PutKey(db.get(), write_options, TestKey(1, 4), "v14"); | |
20effc67 TL |
847 | ASSERT_OK(db->Flush(FlushOptions())); |
848 | ASSERT_OK( | |
849 | static_cast_with_check<DBImpl>(db.get())->TEST_WaitForFlushMemTable()); | |
7c673cae FG |
850 | PutKey(db.get(), write_options, TestKey(1, 1), "v11"); |
851 | PutKey(db.get(), write_options, TestKey(1, 3), "v13"); | |
852 | PutKey(db.get(), write_options, TestKey(2, 1), "v21"); | |
853 | PutKey(db.get(), write_options, TestKey(2, 2), "v22"); | |
20effc67 TL |
854 | ASSERT_OK(db->Flush(FlushOptions())); |
855 | ASSERT_OK( | |
856 | static_cast_with_check<DBImpl>(db.get())->TEST_WaitForFlushMemTable()); | |
7c673cae FG |
857 | std::unique_ptr<Iterator> iter(db->NewIterator(read_options)); |
858 | iter->SeekToLast(); | |
859 | ASSERT_EQ(iter->value(), v14); | |
860 | } | |
861 | { | |
20effc67 | 862 | ASSERT_OK(DestroyDB(kDbName, Options())); |
7c673cae FG |
863 | auto db = OpenDb(); |
864 | WriteOptions write_options; | |
865 | ReadOptions read_options; | |
866 | read_options.iterate_upper_bound = &upper_bound; | |
867 | PutKey(db.get(), write_options, TestKey(1, 2), "v12"); | |
868 | PutKey(db.get(), write_options, TestKey(1, 4), "v14"); | |
869 | PutKey(db.get(), write_options, TestKey(3, 3), "v33"); | |
870 | PutKey(db.get(), write_options, TestKey(3, 4), "v34"); | |
20effc67 TL |
871 | ASSERT_OK(db->Flush(FlushOptions())); |
872 | ASSERT_OK( | |
873 | static_cast_with_check<DBImpl>(db.get())->TEST_WaitForFlushMemTable()); | |
7c673cae FG |
874 | PutKey(db.get(), write_options, TestKey(1, 1), "v11"); |
875 | PutKey(db.get(), write_options, TestKey(1, 3), "v13"); | |
20effc67 TL |
876 | ASSERT_OK(db->Flush(FlushOptions())); |
877 | ASSERT_OK( | |
878 | static_cast_with_check<DBImpl>(db.get())->TEST_WaitForFlushMemTable()); | |
7c673cae FG |
879 | std::unique_ptr<Iterator> iter(db->NewIterator(read_options)); |
880 | iter->SeekToLast(); | |
881 | ASSERT_EQ(iter->value(), v14); | |
882 | } | |
883 | } | |
884 | ||
f67539c2 | 885 | } // namespace ROCKSDB_NAMESPACE |
7c673cae FG |
886 | |
887 | int main(int argc, char** argv) { | |
1e59de90 | 888 | ROCKSDB_NAMESPACE::port::InstallStackTraceHandler(); |
7c673cae FG |
889 | ::testing::InitGoogleTest(&argc, argv); |
890 | ParseCommandLineFlags(&argc, &argv, true); | |
7c673cae FG |
891 | return RUN_ALL_TESTS(); |
892 | } | |
893 | ||
894 | #endif // GFLAGS | |
895 | ||
896 | #else | |
897 | #include <stdio.h> | |
898 | ||
11fdf7f2 | 899 | int main(int /*argc*/, char** /*argv*/) { |
7c673cae FG |
900 | fprintf(stderr, |
901 | "SKIPPED as HashSkipList and HashLinkList are not supported in " | |
902 | "ROCKSDB_LITE\n"); | |
903 | return 0; | |
904 | } | |
905 | ||
906 | #endif // !ROCKSDB_LITE |