1 /**
2 * An persistent map : key -> (list of strings), using rocksdb merge.
3 * This file is a test-harness / use-case for the StringAppendOperator.
4 *
5 * @author Deon Nicholas (dnicholas@fb.com)
6 * Copyright 2013 Facebook, Inc.
7 */
8
9 #include <iostream>
10 #include <map>
11
12 #include "rocksdb/db.h"
13 #include "rocksdb/merge_operator.h"
14 #include "rocksdb/utilities/db_ttl.h"
15 #include "test_util/testharness.h"
16 #include "util/random.h"
17 #include "utilities/merge_operators.h"
18 #include "utilities/merge_operators/string_append/stringappend.h"
19 #include "utilities/merge_operators/string_append/stringappend2.h"
20
21 using namespace rocksdb;
22
23 namespace rocksdb {
24
25 // Path to the database on file system
26 const std::string kDbName = test::PerThreadDBPath("stringappend_test");
27
28 namespace {
29 // OpenDb opens a (possibly new) rocksdb database with a StringAppendOperator
OpenNormalDb(char delim_char)30 std::shared_ptr<DB> OpenNormalDb(char delim_char) {
31 DB* db;
32 Options options;
33 options.create_if_missing = true;
34 options.merge_operator.reset(new StringAppendOperator(delim_char));
35 EXPECT_OK(DB::Open(options, kDbName, &db));
36 return std::shared_ptr<DB>(db);
37 }
38
39 #ifndef ROCKSDB_LITE // TtlDb is not supported in Lite
40 // Open a TtlDB with a non-associative StringAppendTESTOperator
OpenTtlDb(char delim_char)41 std::shared_ptr<DB> OpenTtlDb(char delim_char) {
42 DBWithTTL* db;
43 Options options;
44 options.create_if_missing = true;
45 options.merge_operator.reset(new StringAppendTESTOperator(delim_char));
46 EXPECT_OK(DBWithTTL::Open(options, kDbName, &db, 123456));
47 return std::shared_ptr<DB>(db);
48 }
49 #endif // !ROCKSDB_LITE
50 } // namespace
51
52 /// StringLists represents a set of string-lists, each with a key-index.
53 /// Supports Append(list, string) and Get(list)
54 class StringLists {
55 public:
56
57 //Constructor: specifies the rocksdb db
58 /* implicit */
StringLists(std::shared_ptr<DB> db)59 StringLists(std::shared_ptr<DB> db)
60 : db_(db),
61 merge_option_(),
62 get_option_() {
63 assert(db);
64 }
65
66 // Append string val onto the list defined by key; return true on success
Append(const std::string & key,const std::string & val)67 bool Append(const std::string& key, const std::string& val){
68 Slice valSlice(val.data(), val.size());
69 auto s = db_->Merge(merge_option_, key, valSlice);
70
71 if (s.ok()) {
72 return true;
73 } else {
74 std::cerr << "ERROR " << s.ToString() << std::endl;
75 return false;
76 }
77 }
78
79 // Returns the list of strings associated with key (or "" if does not exist)
Get(const std::string & key,std::string * const result)80 bool Get(const std::string& key, std::string* const result){
81 assert(result != nullptr); // we should have a place to store the result
82 auto s = db_->Get(get_option_, key, result);
83
84 if (s.ok()) {
85 return true;
86 }
87
88 // Either key does not exist, or there is some error.
89 *result = ""; // Always return empty string (just for convention)
90
91 //NotFound is okay; just return empty (similar to std::map)
92 //But network or db errors, etc, should fail the test (or at least yell)
93 if (!s.IsNotFound()) {
94 std::cerr << "ERROR " << s.ToString() << std::endl;
95 }
96
97 // Always return false if s.ok() was not true
98 return false;
99 }
100
101
102 private:
103 std::shared_ptr<DB> db_;
104 WriteOptions merge_option_;
105 ReadOptions get_option_;
106
107 };
108
109
110 // The class for unit-testing
111 class StringAppendOperatorTest : public testing::Test {
112 public:
StringAppendOperatorTest()113 StringAppendOperatorTest() {
114 DestroyDB(kDbName, Options()); // Start each test with a fresh DB
115 }
116
117 typedef std::shared_ptr<DB> (* OpenFuncPtr)(char);
118
119 // Allows user to open databases with different configurations.
120 // e.g.: Can open a DB or a TtlDB, etc.
SetOpenDbFunction(OpenFuncPtr func)121 static void SetOpenDbFunction(OpenFuncPtr func) {
122 OpenDb = func;
123 }
124
125 protected:
126 static OpenFuncPtr OpenDb;
127 };
128 StringAppendOperatorTest::OpenFuncPtr StringAppendOperatorTest::OpenDb = nullptr;
129
130 // THE TEST CASES BEGIN HERE
131
TEST_F(StringAppendOperatorTest,IteratorTest)132 TEST_F(StringAppendOperatorTest, IteratorTest) {
133 auto db_ = OpenDb(',');
134 StringLists slists(db_);
135
136 slists.Append("k1", "v1");
137 slists.Append("k1", "v2");
138 slists.Append("k1", "v3");
139
140 slists.Append("k2", "a1");
141 slists.Append("k2", "a2");
142 slists.Append("k2", "a3");
143
144 std::string res;
145 std::unique_ptr<rocksdb::Iterator> it(db_->NewIterator(ReadOptions()));
146 std::string k1("k1");
147 std::string k2("k2");
148 bool first = true;
149 for (it->Seek(k1); it->Valid(); it->Next()) {
150 res = it->value().ToString();
151 if (first) {
152 ASSERT_EQ(res, "v1,v2,v3");
153 first = false;
154 } else {
155 ASSERT_EQ(res, "a1,a2,a3");
156 }
157 }
158 slists.Append("k2", "a4");
159 slists.Append("k1", "v4");
160
161 // Snapshot should still be the same. Should ignore a4 and v4.
162 first = true;
163 for (it->Seek(k1); it->Valid(); it->Next()) {
164 res = it->value().ToString();
165 if (first) {
166 ASSERT_EQ(res, "v1,v2,v3");
167 first = false;
168 } else {
169 ASSERT_EQ(res, "a1,a2,a3");
170 }
171 }
172
173
174 // Should release the snapshot and be aware of the new stuff now
175 it.reset(db_->NewIterator(ReadOptions()));
176 first = true;
177 for (it->Seek(k1); it->Valid(); it->Next()) {
178 res = it->value().ToString();
179 if (first) {
180 ASSERT_EQ(res, "v1,v2,v3,v4");
181 first = false;
182 } else {
183 ASSERT_EQ(res, "a1,a2,a3,a4");
184 }
185 }
186
187 // start from k2 this time.
188 for (it->Seek(k2); it->Valid(); it->Next()) {
189 res = it->value().ToString();
190 if (first) {
191 ASSERT_EQ(res, "v1,v2,v3,v4");
192 first = false;
193 } else {
194 ASSERT_EQ(res, "a1,a2,a3,a4");
195 }
196 }
197
198 slists.Append("k3", "g1");
199
200 it.reset(db_->NewIterator(ReadOptions()));
201 first = true;
202 std::string k3("k3");
203 for(it->Seek(k2); it->Valid(); it->Next()) {
204 res = it->value().ToString();
205 if (first) {
206 ASSERT_EQ(res, "a1,a2,a3,a4");
207 first = false;
208 } else {
209 ASSERT_EQ(res, "g1");
210 }
211 }
212 for(it->Seek(k3); it->Valid(); it->Next()) {
213 res = it->value().ToString();
214 if (first) {
215 // should not be hit
216 ASSERT_EQ(res, "a1,a2,a3,a4");
217 first = false;
218 } else {
219 ASSERT_EQ(res, "g1");
220 }
221 }
222
223 }
224
TEST_F(StringAppendOperatorTest,SimpleTest)225 TEST_F(StringAppendOperatorTest, SimpleTest) {
226 auto db = OpenDb(',');
227 StringLists slists(db);
228
229 slists.Append("k1", "v1");
230 slists.Append("k1", "v2");
231 slists.Append("k1", "v3");
232
233 std::string res;
234 bool status = slists.Get("k1", &res);
235
236 ASSERT_TRUE(status);
237 ASSERT_EQ(res, "v1,v2,v3");
238 }
239
TEST_F(StringAppendOperatorTest,SimpleDelimiterTest)240 TEST_F(StringAppendOperatorTest, SimpleDelimiterTest) {
241 auto db = OpenDb('|');
242 StringLists slists(db);
243
244 slists.Append("k1", "v1");
245 slists.Append("k1", "v2");
246 slists.Append("k1", "v3");
247
248 std::string res;
249 slists.Get("k1", &res);
250 ASSERT_EQ(res, "v1|v2|v3");
251 }
252
TEST_F(StringAppendOperatorTest,OneValueNoDelimiterTest)253 TEST_F(StringAppendOperatorTest, OneValueNoDelimiterTest) {
254 auto db = OpenDb('!');
255 StringLists slists(db);
256
257 slists.Append("random_key", "single_val");
258
259 std::string res;
260 slists.Get("random_key", &res);
261 ASSERT_EQ(res, "single_val");
262 }
263
TEST_F(StringAppendOperatorTest,VariousKeys)264 TEST_F(StringAppendOperatorTest, VariousKeys) {
265 auto db = OpenDb('\n');
266 StringLists slists(db);
267
268 slists.Append("c", "asdasd");
269 slists.Append("a", "x");
270 slists.Append("b", "y");
271 slists.Append("a", "t");
272 slists.Append("a", "r");
273 slists.Append("b", "2");
274 slists.Append("c", "asdasd");
275
276 std::string a, b, c;
277 bool sa, sb, sc;
278 sa = slists.Get("a", &a);
279 sb = slists.Get("b", &b);
280 sc = slists.Get("c", &c);
281
282 ASSERT_TRUE(sa && sb && sc); // All three keys should have been found
283
284 ASSERT_EQ(a, "x\nt\nr");
285 ASSERT_EQ(b, "y\n2");
286 ASSERT_EQ(c, "asdasd\nasdasd");
287 }
288
289 // Generate semi random keys/words from a small distribution.
TEST_F(StringAppendOperatorTest,RandomMixGetAppend)290 TEST_F(StringAppendOperatorTest, RandomMixGetAppend) {
291 auto db = OpenDb(' ');
292 StringLists slists(db);
293
294 // Generate a list of random keys and values
295 const int kWordCount = 15;
296 std::string words[] = {"sdasd", "triejf", "fnjsdfn", "dfjisdfsf", "342839",
297 "dsuha", "mabuais", "sadajsid", "jf9834hf", "2d9j89",
298 "dj9823jd", "a", "dk02ed2dh", "$(jd4h984$(*", "mabz"};
299 const int kKeyCount = 6;
300 std::string keys[] = {"dhaiusdhu", "denidw", "daisda", "keykey", "muki",
301 "shzassdianmd"};
302
303 // Will store a local copy of all data in order to verify correctness
304 std::map<std::string, std::string> parallel_copy;
305
306 // Generate a bunch of random queries (Append and Get)!
307 enum query_t { APPEND_OP, GET_OP, NUM_OPS };
308 Random randomGen(1337); //deterministic seed; always get same results!
309
310 const int kNumQueries = 30;
311 for (int q=0; q<kNumQueries; ++q) {
312 // Generate a random query (Append or Get) and random parameters
313 query_t query = (query_t)randomGen.Uniform((int)NUM_OPS);
314 std::string key = keys[randomGen.Uniform((int)kKeyCount)];
315 std::string word = words[randomGen.Uniform((int)kWordCount)];
316
317 // Apply the query and any checks.
318 if (query == APPEND_OP) {
319
320 // Apply the rocksdb test-harness Append defined above
321 slists.Append(key, word); //apply the rocksdb append
322
323 // Apply the similar "Append" to the parallel copy
324 if (parallel_copy[key].size() > 0) {
325 parallel_copy[key] += " " + word;
326 } else {
327 parallel_copy[key] = word;
328 }
329
330 } else if (query == GET_OP) {
331 // Assumes that a non-existent key just returns <empty>
332 std::string res;
333 slists.Get(key, &res);
334 ASSERT_EQ(res, parallel_copy[key]);
335 }
336
337 }
338
339 }
340
TEST_F(StringAppendOperatorTest,BIGRandomMixGetAppend)341 TEST_F(StringAppendOperatorTest, BIGRandomMixGetAppend) {
342 auto db = OpenDb(' ');
343 StringLists slists(db);
344
345 // Generate a list of random keys and values
346 const int kWordCount = 15;
347 std::string words[] = {"sdasd", "triejf", "fnjsdfn", "dfjisdfsf", "342839",
348 "dsuha", "mabuais", "sadajsid", "jf9834hf", "2d9j89",
349 "dj9823jd", "a", "dk02ed2dh", "$(jd4h984$(*", "mabz"};
350 const int kKeyCount = 6;
351 std::string keys[] = {"dhaiusdhu", "denidw", "daisda", "keykey", "muki",
352 "shzassdianmd"};
353
354 // Will store a local copy of all data in order to verify correctness
355 std::map<std::string, std::string> parallel_copy;
356
357 // Generate a bunch of random queries (Append and Get)!
358 enum query_t { APPEND_OP, GET_OP, NUM_OPS };
359 Random randomGen(9138204); // deterministic seed
360
361 const int kNumQueries = 1000;
362 for (int q=0; q<kNumQueries; ++q) {
363 // Generate a random query (Append or Get) and random parameters
364 query_t query = (query_t)randomGen.Uniform((int)NUM_OPS);
365 std::string key = keys[randomGen.Uniform((int)kKeyCount)];
366 std::string word = words[randomGen.Uniform((int)kWordCount)];
367
368 //Apply the query and any checks.
369 if (query == APPEND_OP) {
370
371 // Apply the rocksdb test-harness Append defined above
372 slists.Append(key, word); //apply the rocksdb append
373
374 // Apply the similar "Append" to the parallel copy
375 if (parallel_copy[key].size() > 0) {
376 parallel_copy[key] += " " + word;
377 } else {
378 parallel_copy[key] = word;
379 }
380
381 } else if (query == GET_OP) {
382 // Assumes that a non-existent key just returns <empty>
383 std::string res;
384 slists.Get(key, &res);
385 ASSERT_EQ(res, parallel_copy[key]);
386 }
387
388 }
389
390 }
391
TEST_F(StringAppendOperatorTest,PersistentVariousKeys)392 TEST_F(StringAppendOperatorTest, PersistentVariousKeys) {
393 // Perform the following operations in limited scope
394 {
395 auto db = OpenDb('\n');
396 StringLists slists(db);
397
398 slists.Append("c", "asdasd");
399 slists.Append("a", "x");
400 slists.Append("b", "y");
401 slists.Append("a", "t");
402 slists.Append("a", "r");
403 slists.Append("b", "2");
404 slists.Append("c", "asdasd");
405
406 std::string a, b, c;
407 slists.Get("a", &a);
408 slists.Get("b", &b);
409 slists.Get("c", &c);
410
411 ASSERT_EQ(a, "x\nt\nr");
412 ASSERT_EQ(b, "y\n2");
413 ASSERT_EQ(c, "asdasd\nasdasd");
414 }
415
416 // Reopen the database (the previous changes should persist / be remembered)
417 {
418 auto db = OpenDb('\n');
419 StringLists slists(db);
420
421 slists.Append("c", "bbnagnagsx");
422 slists.Append("a", "sa");
423 slists.Append("b", "df");
424 slists.Append("a", "gh");
425 slists.Append("a", "jk");
426 slists.Append("b", "l;");
427 slists.Append("c", "rogosh");
428
429 // The previous changes should be on disk (L0)
430 // The most recent changes should be in memory (MemTable)
431 // Hence, this will test both Get() paths.
432 std::string a, b, c;
433 slists.Get("a", &a);
434 slists.Get("b", &b);
435 slists.Get("c", &c);
436
437 ASSERT_EQ(a, "x\nt\nr\nsa\ngh\njk");
438 ASSERT_EQ(b, "y\n2\ndf\nl;");
439 ASSERT_EQ(c, "asdasd\nasdasd\nbbnagnagsx\nrogosh");
440 }
441
442 // Reopen the database (the previous changes should persist / be remembered)
443 {
444 auto db = OpenDb('\n');
445 StringLists slists(db);
446
447 // All changes should be on disk. This will test VersionSet Get()
448 std::string a, b, c;
449 slists.Get("a", &a);
450 slists.Get("b", &b);
451 slists.Get("c", &c);
452
453 ASSERT_EQ(a, "x\nt\nr\nsa\ngh\njk");
454 ASSERT_EQ(b, "y\n2\ndf\nl;");
455 ASSERT_EQ(c, "asdasd\nasdasd\nbbnagnagsx\nrogosh");
456 }
457 }
458
TEST_F(StringAppendOperatorTest,PersistentFlushAndCompaction)459 TEST_F(StringAppendOperatorTest, PersistentFlushAndCompaction) {
460 // Perform the following operations in limited scope
461 {
462 auto db = OpenDb('\n');
463 StringLists slists(db);
464 std::string a, b, c;
465 bool success;
466
467 // Append, Flush, Get
468 slists.Append("c", "asdasd");
469 db->Flush(rocksdb::FlushOptions());
470 success = slists.Get("c", &c);
471 ASSERT_TRUE(success);
472 ASSERT_EQ(c, "asdasd");
473
474 // Append, Flush, Append, Get
475 slists.Append("a", "x");
476 slists.Append("b", "y");
477 db->Flush(rocksdb::FlushOptions());
478 slists.Append("a", "t");
479 slists.Append("a", "r");
480 slists.Append("b", "2");
481
482 success = slists.Get("a", &a);
483 assert(success == true);
484 ASSERT_EQ(a, "x\nt\nr");
485
486 success = slists.Get("b", &b);
487 assert(success == true);
488 ASSERT_EQ(b, "y\n2");
489
490 // Append, Get
491 success = slists.Append("c", "asdasd");
492 assert(success);
493 success = slists.Append("b", "monkey");
494 assert(success);
495
496 // I omit the "assert(success)" checks here.
497 slists.Get("a", &a);
498 slists.Get("b", &b);
499 slists.Get("c", &c);
500
501 ASSERT_EQ(a, "x\nt\nr");
502 ASSERT_EQ(b, "y\n2\nmonkey");
503 ASSERT_EQ(c, "asdasd\nasdasd");
504 }
505
506 // Reopen the database (the previous changes should persist / be remembered)
507 {
508 auto db = OpenDb('\n');
509 StringLists slists(db);
510 std::string a, b, c;
511
512 // Get (Quick check for persistence of previous database)
513 slists.Get("a", &a);
514 ASSERT_EQ(a, "x\nt\nr");
515
516 //Append, Compact, Get
517 slists.Append("c", "bbnagnagsx");
518 slists.Append("a", "sa");
519 slists.Append("b", "df");
520 db->CompactRange(CompactRangeOptions(), nullptr, nullptr);
521 slists.Get("a", &a);
522 slists.Get("b", &b);
523 slists.Get("c", &c);
524 ASSERT_EQ(a, "x\nt\nr\nsa");
525 ASSERT_EQ(b, "y\n2\nmonkey\ndf");
526 ASSERT_EQ(c, "asdasd\nasdasd\nbbnagnagsx");
527
528 // Append, Get
529 slists.Append("a", "gh");
530 slists.Append("a", "jk");
531 slists.Append("b", "l;");
532 slists.Append("c", "rogosh");
533 slists.Get("a", &a);
534 slists.Get("b", &b);
535 slists.Get("c", &c);
536 ASSERT_EQ(a, "x\nt\nr\nsa\ngh\njk");
537 ASSERT_EQ(b, "y\n2\nmonkey\ndf\nl;");
538 ASSERT_EQ(c, "asdasd\nasdasd\nbbnagnagsx\nrogosh");
539
540 // Compact, Get
541 db->CompactRange(CompactRangeOptions(), nullptr, nullptr);
542 ASSERT_EQ(a, "x\nt\nr\nsa\ngh\njk");
543 ASSERT_EQ(b, "y\n2\nmonkey\ndf\nl;");
544 ASSERT_EQ(c, "asdasd\nasdasd\nbbnagnagsx\nrogosh");
545
546 // Append, Flush, Compact, Get
547 slists.Append("b", "afcg");
548 db->Flush(rocksdb::FlushOptions());
549 db->CompactRange(CompactRangeOptions(), nullptr, nullptr);
550 slists.Get("b", &b);
551 ASSERT_EQ(b, "y\n2\nmonkey\ndf\nl;\nafcg");
552 }
553 }
554
TEST_F(StringAppendOperatorTest,SimpleTestNullDelimiter)555 TEST_F(StringAppendOperatorTest, SimpleTestNullDelimiter) {
556 auto db = OpenDb('\0');
557 StringLists slists(db);
558
559 slists.Append("k1", "v1");
560 slists.Append("k1", "v2");
561 slists.Append("k1", "v3");
562
563 std::string res;
564 bool status = slists.Get("k1", &res);
565 ASSERT_TRUE(status);
566
567 // Construct the desired string. Default constructor doesn't like '\0' chars.
568 std::string checker("v1,v2,v3"); // Verify that the string is right size.
569 checker[2] = '\0'; // Use null delimiter instead of comma.
570 checker[5] = '\0';
571 assert(checker.size() == 8); // Verify it is still the correct size
572
573 // Check that the rocksdb result string matches the desired string
574 assert(res.size() == checker.size());
575 ASSERT_EQ(res, checker);
576 }
577
578 } // namespace rocksdb
579
main(int argc,char ** argv)580 int main(int argc, char** argv) {
581 ::testing::InitGoogleTest(&argc, argv);
582 // Run with regular database
583 int result;
584 {
585 fprintf(stderr, "Running tests with regular db and operator.\n");
586 StringAppendOperatorTest::SetOpenDbFunction(&OpenNormalDb);
587 result = RUN_ALL_TESTS();
588 }
589
590 #ifndef ROCKSDB_LITE // TtlDb is not supported in Lite
591 // Run with TTL
592 {
593 fprintf(stderr, "Running tests with ttl db and generic operator.\n");
594 StringAppendOperatorTest::SetOpenDbFunction(&OpenTtlDb);
595 result |= RUN_ALL_TESTS();
596 }
597 #endif // !ROCKSDB_LITE
598
599 return result;
600 }
601