]>
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 | #include <vector> | |
9 | #include <string> | |
10 | #include <map> | |
11 | #include <utility> | |
12 | ||
13 | #include "table/meta_blocks.h" | |
14 | #include "table/cuckoo_table_builder.h" | |
15 | #include "util/file_reader_writer.h" | |
16 | #include "util/testharness.h" | |
17 | #include "util/testutil.h" | |
18 | ||
19 | namespace rocksdb { | |
20 | extern const uint64_t kCuckooTableMagicNumber; | |
21 | ||
22 | namespace { | |
23 | std::unordered_map<std::string, std::vector<uint64_t>> hash_map; | |
24 | ||
25 | uint64_t GetSliceHash(const Slice& s, uint32_t index, | |
11fdf7f2 | 26 | uint64_t /*max_num_buckets*/) { |
7c673cae FG |
27 | return hash_map[s.ToString()][index]; |
28 | } | |
29 | } // namespace | |
30 | ||
31 | class CuckooBuilderTest : public testing::Test { | |
32 | public: | |
33 | CuckooBuilderTest() { | |
34 | env_ = Env::Default(); | |
35 | Options options; | |
36 | options.allow_mmap_reads = true; | |
37 | env_options_ = EnvOptions(options); | |
38 | } | |
39 | ||
40 | void CheckFileContents(const std::vector<std::string>& keys, | |
41 | const std::vector<std::string>& values, | |
42 | const std::vector<uint64_t>& expected_locations, | |
43 | std::string expected_unused_bucket, uint64_t expected_table_size, | |
44 | uint32_t expected_num_hash_func, bool expected_is_last_level, | |
45 | uint32_t expected_cuckoo_block_size = 1) { | |
494da23a TL |
46 | uint64_t num_deletions = 0; |
47 | for (const auto& key : keys) { | |
48 | ParsedInternalKey parsed; | |
49 | if (ParseInternalKey(key, &parsed) && parsed.type == kTypeDeletion) { | |
50 | num_deletions++; | |
51 | } | |
52 | } | |
7c673cae | 53 | // Read file |
494da23a | 54 | std::unique_ptr<RandomAccessFile> read_file; |
7c673cae FG |
55 | ASSERT_OK(env_->NewRandomAccessFile(fname, &read_file, env_options_)); |
56 | uint64_t read_file_size; | |
57 | ASSERT_OK(env_->GetFileSize(fname, &read_file_size)); | |
58 | ||
11fdf7f2 TL |
59 | // @lint-ignore TXT2 T25377293 Grandfathered in |
60 | Options options; | |
61 | options.allow_mmap_reads = true; | |
62 | ImmutableCFOptions ioptions(options); | |
7c673cae FG |
63 | |
64 | // Assert Table Properties. | |
65 | TableProperties* props = nullptr; | |
494da23a | 66 | std::unique_ptr<RandomAccessFileReader> file_reader( |
11fdf7f2 | 67 | new RandomAccessFileReader(std::move(read_file), fname)); |
7c673cae FG |
68 | ASSERT_OK(ReadTableProperties(file_reader.get(), read_file_size, |
69 | kCuckooTableMagicNumber, ioptions, | |
11fdf7f2 | 70 | &props, true /* compression_type_missing */)); |
7c673cae FG |
71 | // Check unused bucket. |
72 | std::string unused_key = props->user_collected_properties[ | |
73 | CuckooTablePropertyNames::kEmptyKey]; | |
74 | ASSERT_EQ(expected_unused_bucket.substr(0, | |
75 | props->fixed_key_len), unused_key); | |
76 | ||
77 | uint64_t value_len_found = | |
78 | *reinterpret_cast<const uint64_t*>(props->user_collected_properties[ | |
79 | CuckooTablePropertyNames::kValueLength].data()); | |
80 | ASSERT_EQ(values.empty() ? 0 : values[0].size(), value_len_found); | |
81 | ASSERT_EQ(props->raw_value_size, values.size()*value_len_found); | |
82 | const uint64_t table_size = | |
83 | *reinterpret_cast<const uint64_t*>(props->user_collected_properties[ | |
84 | CuckooTablePropertyNames::kHashTableSize].data()); | |
85 | ASSERT_EQ(expected_table_size, table_size); | |
86 | const uint32_t num_hash_func_found = | |
87 | *reinterpret_cast<const uint32_t*>(props->user_collected_properties[ | |
88 | CuckooTablePropertyNames::kNumHashFunc].data()); | |
89 | ASSERT_EQ(expected_num_hash_func, num_hash_func_found); | |
90 | const uint32_t cuckoo_block_size = | |
91 | *reinterpret_cast<const uint32_t*>(props->user_collected_properties[ | |
92 | CuckooTablePropertyNames::kCuckooBlockSize].data()); | |
93 | ASSERT_EQ(expected_cuckoo_block_size, cuckoo_block_size); | |
94 | const bool is_last_level_found = | |
95 | *reinterpret_cast<const bool*>(props->user_collected_properties[ | |
96 | CuckooTablePropertyNames::kIsLastLevel].data()); | |
97 | ASSERT_EQ(expected_is_last_level, is_last_level_found); | |
98 | ||
99 | ASSERT_EQ(props->num_entries, keys.size()); | |
494da23a | 100 | ASSERT_EQ(props->num_deletions, num_deletions); |
7c673cae FG |
101 | ASSERT_EQ(props->fixed_key_len, keys.empty() ? 0 : keys[0].size()); |
102 | ASSERT_EQ(props->data_size, expected_unused_bucket.size() * | |
103 | (expected_table_size + expected_cuckoo_block_size - 1)); | |
104 | ASSERT_EQ(props->raw_key_size, keys.size()*props->fixed_key_len); | |
105 | ASSERT_EQ(props->column_family_id, 0); | |
106 | ASSERT_EQ(props->column_family_name, kDefaultColumnFamilyName); | |
107 | delete props; | |
108 | ||
109 | // Check contents of the bucket. | |
110 | std::vector<bool> keys_found(keys.size(), false); | |
111 | size_t bucket_size = expected_unused_bucket.size(); | |
112 | for (uint32_t i = 0; i < table_size + cuckoo_block_size - 1; ++i) { | |
113 | Slice read_slice; | |
114 | ASSERT_OK(file_reader->Read(i * bucket_size, bucket_size, &read_slice, | |
115 | nullptr)); | |
116 | size_t key_idx = | |
117 | std::find(expected_locations.begin(), expected_locations.end(), i) - | |
118 | expected_locations.begin(); | |
119 | if (key_idx == keys.size()) { | |
11fdf7f2 TL |
120 | // i is not one of the expected locations. Empty bucket. |
121 | if (read_slice.data() == nullptr) { | |
122 | ASSERT_EQ(0, expected_unused_bucket.size()); | |
123 | } else { | |
124 | ASSERT_EQ(read_slice.compare(expected_unused_bucket), 0); | |
125 | } | |
7c673cae FG |
126 | } else { |
127 | keys_found[key_idx] = true; | |
128 | ASSERT_EQ(read_slice.compare(keys[key_idx] + values[key_idx]), 0); | |
129 | } | |
130 | } | |
131 | for (auto key_found : keys_found) { | |
132 | // Check that all keys wereReader found. | |
133 | ASSERT_TRUE(key_found); | |
134 | } | |
135 | } | |
136 | ||
494da23a TL |
137 | std::string GetInternalKey(Slice user_key, bool zero_seqno, |
138 | ValueType type = kTypeValue) { | |
7c673cae | 139 | IterKey ikey; |
494da23a | 140 | ikey.SetInternalKey(user_key, zero_seqno ? 0 : 1000, type); |
7c673cae FG |
141 | return ikey.GetInternalKey().ToString(); |
142 | } | |
143 | ||
144 | uint64_t NextPowOf2(uint64_t num) { | |
145 | uint64_t n = 2; | |
146 | while (n <= num) { | |
147 | n *= 2; | |
148 | } | |
149 | return n; | |
150 | } | |
151 | ||
152 | uint64_t GetExpectedTableSize(uint64_t num) { | |
153 | return NextPowOf2(static_cast<uint64_t>(num / kHashTableRatio)); | |
154 | } | |
155 | ||
156 | ||
157 | Env* env_; | |
158 | EnvOptions env_options_; | |
159 | std::string fname; | |
160 | const double kHashTableRatio = 0.9; | |
161 | }; | |
162 | ||
163 | TEST_F(CuckooBuilderTest, SuccessWithEmptyFile) { | |
494da23a | 164 | std::unique_ptr<WritableFile> writable_file; |
11fdf7f2 | 165 | fname = test::PerThreadDBPath("EmptyFile"); |
7c673cae | 166 | ASSERT_OK(env_->NewWritableFile(fname, &writable_file, env_options_)); |
494da23a | 167 | std::unique_ptr<WritableFileWriter> file_writer( |
11fdf7f2 | 168 | new WritableFileWriter(std::move(writable_file), fname, EnvOptions())); |
7c673cae FG |
169 | CuckooTableBuilder builder(file_writer.get(), kHashTableRatio, 4, 100, |
170 | BytewiseComparator(), 1, false, false, | |
171 | GetSliceHash, 0 /* column_family_id */, | |
172 | kDefaultColumnFamilyName); | |
173 | ASSERT_OK(builder.status()); | |
174 | ASSERT_EQ(0UL, builder.FileSize()); | |
175 | ASSERT_OK(builder.Finish()); | |
176 | ASSERT_OK(file_writer->Close()); | |
177 | CheckFileContents({}, {}, {}, "", 2, 2, false); | |
178 | } | |
179 | ||
180 | TEST_F(CuckooBuilderTest, WriteSuccessNoCollisionFullKey) { | |
494da23a TL |
181 | for (auto type : {kTypeValue, kTypeDeletion}) { |
182 | uint32_t num_hash_fun = 4; | |
183 | std::vector<std::string> user_keys = {"key01", "key02", "key03", "key04"}; | |
184 | std::vector<std::string> values; | |
185 | if (type == kTypeValue) { | |
186 | values = {"v01", "v02", "v03", "v04"}; | |
187 | } else { | |
188 | values = {"", "", "", ""}; | |
189 | } | |
190 | // Need to have a temporary variable here as VS compiler does not currently | |
191 | // support operator= with initializer_list as a parameter | |
192 | std::unordered_map<std::string, std::vector<uint64_t>> hm = { | |
193 | {user_keys[0], {0, 1, 2, 3}}, | |
194 | {user_keys[1], {1, 2, 3, 4}}, | |
195 | {user_keys[2], {2, 3, 4, 5}}, | |
196 | {user_keys[3], {3, 4, 5, 6}}}; | |
197 | hash_map = std::move(hm); | |
198 | ||
199 | std::vector<uint64_t> expected_locations = {0, 1, 2, 3}; | |
200 | std::vector<std::string> keys; | |
201 | for (auto& user_key : user_keys) { | |
202 | keys.push_back(GetInternalKey(user_key, false, type)); | |
203 | } | |
204 | uint64_t expected_table_size = GetExpectedTableSize(keys.size()); | |
205 | ||
206 | std::unique_ptr<WritableFile> writable_file; | |
207 | fname = test::PerThreadDBPath("NoCollisionFullKey"); | |
208 | ASSERT_OK(env_->NewWritableFile(fname, &writable_file, env_options_)); | |
209 | std::unique_ptr<WritableFileWriter> file_writer( | |
210 | new WritableFileWriter(std::move(writable_file), fname, EnvOptions())); | |
211 | CuckooTableBuilder builder(file_writer.get(), kHashTableRatio, num_hash_fun, | |
212 | 100, BytewiseComparator(), 1, false, false, | |
213 | GetSliceHash, 0 /* column_family_id */, | |
214 | kDefaultColumnFamilyName); | |
7c673cae | 215 | ASSERT_OK(builder.status()); |
494da23a TL |
216 | for (uint32_t i = 0; i < user_keys.size(); i++) { |
217 | builder.Add(Slice(keys[i]), Slice(values[i])); | |
218 | ASSERT_EQ(builder.NumEntries(), i + 1); | |
219 | ASSERT_OK(builder.status()); | |
220 | } | |
221 | size_t bucket_size = keys[0].size() + values[0].size(); | |
222 | ASSERT_EQ(expected_table_size * bucket_size - 1, builder.FileSize()); | |
223 | ASSERT_OK(builder.Finish()); | |
224 | ASSERT_OK(file_writer->Close()); | |
225 | ASSERT_LE(expected_table_size * bucket_size, builder.FileSize()); | |
226 | ||
227 | std::string expected_unused_bucket = GetInternalKey("key00", true); | |
228 | expected_unused_bucket += std::string(values[0].size(), 'a'); | |
229 | CheckFileContents(keys, values, expected_locations, expected_unused_bucket, | |
230 | expected_table_size, 2, false); | |
7c673cae | 231 | } |
7c673cae FG |
232 | } |
233 | ||
234 | TEST_F(CuckooBuilderTest, WriteSuccessWithCollisionFullKey) { | |
235 | uint32_t num_hash_fun = 4; | |
236 | std::vector<std::string> user_keys = {"key01", "key02", "key03", "key04"}; | |
237 | std::vector<std::string> values = {"v01", "v02", "v03", "v04"}; | |
238 | // Need to have a temporary variable here as VS compiler does not currently | |
239 | // support operator= with initializer_list as a parameter | |
240 | std::unordered_map<std::string, std::vector<uint64_t>> hm = { | |
241 | {user_keys[0], {0, 1, 2, 3}}, | |
242 | {user_keys[1], {0, 1, 2, 3}}, | |
243 | {user_keys[2], {0, 1, 2, 3}}, | |
244 | {user_keys[3], {0, 1, 2, 3}}, | |
245 | }; | |
246 | hash_map = std::move(hm); | |
247 | ||
248 | std::vector<uint64_t> expected_locations = {0, 1, 2, 3}; | |
249 | std::vector<std::string> keys; | |
250 | for (auto& user_key : user_keys) { | |
251 | keys.push_back(GetInternalKey(user_key, false)); | |
252 | } | |
253 | uint64_t expected_table_size = GetExpectedTableSize(keys.size()); | |
254 | ||
494da23a | 255 | std::unique_ptr<WritableFile> writable_file; |
11fdf7f2 | 256 | fname = test::PerThreadDBPath("WithCollisionFullKey"); |
7c673cae | 257 | ASSERT_OK(env_->NewWritableFile(fname, &writable_file, env_options_)); |
494da23a | 258 | std::unique_ptr<WritableFileWriter> file_writer( |
11fdf7f2 | 259 | new WritableFileWriter(std::move(writable_file), fname, EnvOptions())); |
7c673cae FG |
260 | CuckooTableBuilder builder(file_writer.get(), kHashTableRatio, num_hash_fun, |
261 | 100, BytewiseComparator(), 1, false, false, | |
262 | GetSliceHash, 0 /* column_family_id */, | |
263 | kDefaultColumnFamilyName); | |
264 | ASSERT_OK(builder.status()); | |
265 | for (uint32_t i = 0; i < user_keys.size(); i++) { | |
266 | builder.Add(Slice(keys[i]), Slice(values[i])); | |
267 | ASSERT_EQ(builder.NumEntries(), i + 1); | |
268 | ASSERT_OK(builder.status()); | |
269 | } | |
270 | size_t bucket_size = keys[0].size() + values[0].size(); | |
271 | ASSERT_EQ(expected_table_size * bucket_size - 1, builder.FileSize()); | |
272 | ASSERT_OK(builder.Finish()); | |
273 | ASSERT_OK(file_writer->Close()); | |
274 | ASSERT_LE(expected_table_size * bucket_size, builder.FileSize()); | |
275 | ||
276 | std::string expected_unused_bucket = GetInternalKey("key00", true); | |
277 | expected_unused_bucket += std::string(values[0].size(), 'a'); | |
278 | CheckFileContents(keys, values, expected_locations, | |
279 | expected_unused_bucket, expected_table_size, 4, false); | |
280 | } | |
281 | ||
282 | TEST_F(CuckooBuilderTest, WriteSuccessWithCollisionAndCuckooBlock) { | |
283 | uint32_t num_hash_fun = 4; | |
284 | std::vector<std::string> user_keys = {"key01", "key02", "key03", "key04"}; | |
285 | std::vector<std::string> values = {"v01", "v02", "v03", "v04"}; | |
286 | // Need to have a temporary variable here as VS compiler does not currently | |
287 | // support operator= with initializer_list as a parameter | |
288 | std::unordered_map<std::string, std::vector<uint64_t>> hm = { | |
289 | {user_keys[0], {0, 1, 2, 3}}, | |
290 | {user_keys[1], {0, 1, 2, 3}}, | |
291 | {user_keys[2], {0, 1, 2, 3}}, | |
292 | {user_keys[3], {0, 1, 2, 3}}, | |
293 | }; | |
294 | hash_map = std::move(hm); | |
295 | ||
296 | std::vector<uint64_t> expected_locations = {0, 1, 2, 3}; | |
297 | std::vector<std::string> keys; | |
298 | for (auto& user_key : user_keys) { | |
299 | keys.push_back(GetInternalKey(user_key, false)); | |
300 | } | |
301 | uint64_t expected_table_size = GetExpectedTableSize(keys.size()); | |
302 | ||
494da23a | 303 | std::unique_ptr<WritableFile> writable_file; |
7c673cae | 304 | uint32_t cuckoo_block_size = 2; |
11fdf7f2 | 305 | fname = test::PerThreadDBPath("WithCollisionFullKey2"); |
7c673cae | 306 | ASSERT_OK(env_->NewWritableFile(fname, &writable_file, env_options_)); |
494da23a | 307 | std::unique_ptr<WritableFileWriter> file_writer( |
11fdf7f2 | 308 | new WritableFileWriter(std::move(writable_file), fname, EnvOptions())); |
7c673cae FG |
309 | CuckooTableBuilder builder( |
310 | file_writer.get(), kHashTableRatio, num_hash_fun, 100, | |
311 | BytewiseComparator(), cuckoo_block_size, false, false, GetSliceHash, | |
312 | 0 /* column_family_id */, kDefaultColumnFamilyName); | |
313 | ASSERT_OK(builder.status()); | |
314 | for (uint32_t i = 0; i < user_keys.size(); i++) { | |
315 | builder.Add(Slice(keys[i]), Slice(values[i])); | |
316 | ASSERT_EQ(builder.NumEntries(), i + 1); | |
317 | ASSERT_OK(builder.status()); | |
318 | } | |
319 | size_t bucket_size = keys[0].size() + values[0].size(); | |
320 | ASSERT_EQ(expected_table_size * bucket_size - 1, builder.FileSize()); | |
321 | ASSERT_OK(builder.Finish()); | |
322 | ASSERT_OK(file_writer->Close()); | |
323 | ASSERT_LE(expected_table_size * bucket_size, builder.FileSize()); | |
324 | ||
325 | std::string expected_unused_bucket = GetInternalKey("key00", true); | |
326 | expected_unused_bucket += std::string(values[0].size(), 'a'); | |
327 | CheckFileContents(keys, values, expected_locations, | |
328 | expected_unused_bucket, expected_table_size, 3, false, cuckoo_block_size); | |
329 | } | |
330 | ||
331 | TEST_F(CuckooBuilderTest, WithCollisionPathFullKey) { | |
332 | // Have two hash functions. Insert elements with overlapping hashes. | |
333 | // Finally insert an element with hash value somewhere in the middle | |
334 | // so that it displaces all the elements after that. | |
335 | uint32_t num_hash_fun = 2; | |
336 | std::vector<std::string> user_keys = {"key01", "key02", "key03", | |
337 | "key04", "key05"}; | |
338 | std::vector<std::string> values = {"v01", "v02", "v03", "v04", "v05"}; | |
339 | // Need to have a temporary variable here as VS compiler does not currently | |
340 | // support operator= with initializer_list as a parameter | |
341 | std::unordered_map<std::string, std::vector<uint64_t>> hm = { | |
342 | {user_keys[0], {0, 1}}, | |
343 | {user_keys[1], {1, 2}}, | |
344 | {user_keys[2], {2, 3}}, | |
345 | {user_keys[3], {3, 4}}, | |
346 | {user_keys[4], {0, 2}}, | |
347 | }; | |
348 | hash_map = std::move(hm); | |
349 | ||
350 | std::vector<uint64_t> expected_locations = {0, 1, 3, 4, 2}; | |
351 | std::vector<std::string> keys; | |
352 | for (auto& user_key : user_keys) { | |
353 | keys.push_back(GetInternalKey(user_key, false)); | |
354 | } | |
355 | uint64_t expected_table_size = GetExpectedTableSize(keys.size()); | |
356 | ||
494da23a | 357 | std::unique_ptr<WritableFile> writable_file; |
11fdf7f2 | 358 | fname = test::PerThreadDBPath("WithCollisionPathFullKey"); |
7c673cae | 359 | ASSERT_OK(env_->NewWritableFile(fname, &writable_file, env_options_)); |
494da23a | 360 | std::unique_ptr<WritableFileWriter> file_writer( |
11fdf7f2 | 361 | new WritableFileWriter(std::move(writable_file), fname, EnvOptions())); |
7c673cae FG |
362 | CuckooTableBuilder builder(file_writer.get(), kHashTableRatio, num_hash_fun, |
363 | 100, BytewiseComparator(), 1, false, false, | |
364 | GetSliceHash, 0 /* column_family_id */, | |
365 | kDefaultColumnFamilyName); | |
366 | ASSERT_OK(builder.status()); | |
367 | for (uint32_t i = 0; i < user_keys.size(); i++) { | |
368 | builder.Add(Slice(keys[i]), Slice(values[i])); | |
369 | ASSERT_EQ(builder.NumEntries(), i + 1); | |
370 | ASSERT_OK(builder.status()); | |
371 | } | |
372 | size_t bucket_size = keys[0].size() + values[0].size(); | |
373 | ASSERT_EQ(expected_table_size * bucket_size - 1, builder.FileSize()); | |
374 | ASSERT_OK(builder.Finish()); | |
375 | ASSERT_OK(file_writer->Close()); | |
376 | ASSERT_LE(expected_table_size * bucket_size, builder.FileSize()); | |
377 | ||
378 | std::string expected_unused_bucket = GetInternalKey("key00", true); | |
379 | expected_unused_bucket += std::string(values[0].size(), 'a'); | |
380 | CheckFileContents(keys, values, expected_locations, | |
381 | expected_unused_bucket, expected_table_size, 2, false); | |
382 | } | |
383 | ||
384 | TEST_F(CuckooBuilderTest, WithCollisionPathFullKeyAndCuckooBlock) { | |
385 | uint32_t num_hash_fun = 2; | |
386 | std::vector<std::string> user_keys = {"key01", "key02", "key03", | |
387 | "key04", "key05"}; | |
388 | std::vector<std::string> values = {"v01", "v02", "v03", "v04", "v05"}; | |
389 | // Need to have a temporary variable here as VS compiler does not currently | |
390 | // support operator= with initializer_list as a parameter | |
391 | std::unordered_map<std::string, std::vector<uint64_t>> hm = { | |
392 | {user_keys[0], {0, 1}}, | |
393 | {user_keys[1], {1, 2}}, | |
394 | {user_keys[2], {3, 4}}, | |
395 | {user_keys[3], {4, 5}}, | |
396 | {user_keys[4], {0, 3}}, | |
397 | }; | |
398 | hash_map = std::move(hm); | |
399 | ||
400 | std::vector<uint64_t> expected_locations = {2, 1, 3, 4, 0}; | |
401 | std::vector<std::string> keys; | |
402 | for (auto& user_key : user_keys) { | |
403 | keys.push_back(GetInternalKey(user_key, false)); | |
404 | } | |
405 | uint64_t expected_table_size = GetExpectedTableSize(keys.size()); | |
406 | ||
494da23a | 407 | std::unique_ptr<WritableFile> writable_file; |
11fdf7f2 | 408 | fname = test::PerThreadDBPath("WithCollisionPathFullKeyAndCuckooBlock"); |
7c673cae | 409 | ASSERT_OK(env_->NewWritableFile(fname, &writable_file, env_options_)); |
494da23a | 410 | std::unique_ptr<WritableFileWriter> file_writer( |
11fdf7f2 | 411 | new WritableFileWriter(std::move(writable_file), fname, EnvOptions())); |
7c673cae FG |
412 | CuckooTableBuilder builder(file_writer.get(), kHashTableRatio, num_hash_fun, |
413 | 100, BytewiseComparator(), 2, false, false, | |
414 | GetSliceHash, 0 /* column_family_id */, | |
415 | kDefaultColumnFamilyName); | |
416 | ASSERT_OK(builder.status()); | |
417 | for (uint32_t i = 0; i < user_keys.size(); i++) { | |
418 | builder.Add(Slice(keys[i]), Slice(values[i])); | |
419 | ASSERT_EQ(builder.NumEntries(), i + 1); | |
420 | ASSERT_OK(builder.status()); | |
421 | } | |
422 | size_t bucket_size = keys[0].size() + values[0].size(); | |
423 | ASSERT_EQ(expected_table_size * bucket_size - 1, builder.FileSize()); | |
424 | ASSERT_OK(builder.Finish()); | |
425 | ASSERT_OK(file_writer->Close()); | |
426 | ASSERT_LE(expected_table_size * bucket_size, builder.FileSize()); | |
427 | ||
428 | std::string expected_unused_bucket = GetInternalKey("key00", true); | |
429 | expected_unused_bucket += std::string(values[0].size(), 'a'); | |
430 | CheckFileContents(keys, values, expected_locations, | |
431 | expected_unused_bucket, expected_table_size, 2, false, 2); | |
432 | } | |
433 | ||
434 | TEST_F(CuckooBuilderTest, WriteSuccessNoCollisionUserKey) { | |
435 | uint32_t num_hash_fun = 4; | |
436 | std::vector<std::string> user_keys = {"key01", "key02", "key03", "key04"}; | |
437 | std::vector<std::string> values = {"v01", "v02", "v03", "v04"}; | |
438 | // Need to have a temporary variable here as VS compiler does not currently | |
439 | // support operator= with initializer_list as a parameter | |
440 | std::unordered_map<std::string, std::vector<uint64_t>> hm = { | |
441 | {user_keys[0], {0, 1, 2, 3}}, | |
442 | {user_keys[1], {1, 2, 3, 4}}, | |
443 | {user_keys[2], {2, 3, 4, 5}}, | |
444 | {user_keys[3], {3, 4, 5, 6}}}; | |
445 | hash_map = std::move(hm); | |
446 | ||
447 | std::vector<uint64_t> expected_locations = {0, 1, 2, 3}; | |
448 | uint64_t expected_table_size = GetExpectedTableSize(user_keys.size()); | |
449 | ||
494da23a | 450 | std::unique_ptr<WritableFile> writable_file; |
11fdf7f2 | 451 | fname = test::PerThreadDBPath("NoCollisionUserKey"); |
7c673cae | 452 | ASSERT_OK(env_->NewWritableFile(fname, &writable_file, env_options_)); |
494da23a | 453 | std::unique_ptr<WritableFileWriter> file_writer( |
11fdf7f2 | 454 | new WritableFileWriter(std::move(writable_file), fname, EnvOptions())); |
7c673cae FG |
455 | CuckooTableBuilder builder(file_writer.get(), kHashTableRatio, num_hash_fun, |
456 | 100, BytewiseComparator(), 1, false, false, | |
457 | GetSliceHash, 0 /* column_family_id */, | |
458 | kDefaultColumnFamilyName); | |
459 | ASSERT_OK(builder.status()); | |
460 | for (uint32_t i = 0; i < user_keys.size(); i++) { | |
461 | builder.Add(Slice(GetInternalKey(user_keys[i], true)), Slice(values[i])); | |
462 | ASSERT_EQ(builder.NumEntries(), i + 1); | |
463 | ASSERT_OK(builder.status()); | |
464 | } | |
465 | size_t bucket_size = user_keys[0].size() + values[0].size(); | |
466 | ASSERT_EQ(expected_table_size * bucket_size - 1, builder.FileSize()); | |
467 | ASSERT_OK(builder.Finish()); | |
468 | ASSERT_OK(file_writer->Close()); | |
469 | ASSERT_LE(expected_table_size * bucket_size, builder.FileSize()); | |
470 | ||
471 | std::string expected_unused_bucket = "key00"; | |
472 | expected_unused_bucket += std::string(values[0].size(), 'a'); | |
473 | CheckFileContents(user_keys, values, expected_locations, | |
474 | expected_unused_bucket, expected_table_size, 2, true); | |
475 | } | |
476 | ||
477 | TEST_F(CuckooBuilderTest, WriteSuccessWithCollisionUserKey) { | |
478 | uint32_t num_hash_fun = 4; | |
479 | std::vector<std::string> user_keys = {"key01", "key02", "key03", "key04"}; | |
480 | std::vector<std::string> values = {"v01", "v02", "v03", "v04"}; | |
481 | // Need to have a temporary variable here as VS compiler does not currently | |
482 | // support operator= with initializer_list as a parameter | |
483 | std::unordered_map<std::string, std::vector<uint64_t>> hm = { | |
484 | {user_keys[0], {0, 1, 2, 3}}, | |
485 | {user_keys[1], {0, 1, 2, 3}}, | |
486 | {user_keys[2], {0, 1, 2, 3}}, | |
487 | {user_keys[3], {0, 1, 2, 3}}, | |
488 | }; | |
489 | hash_map = std::move(hm); | |
490 | ||
491 | std::vector<uint64_t> expected_locations = {0, 1, 2, 3}; | |
492 | uint64_t expected_table_size = GetExpectedTableSize(user_keys.size()); | |
493 | ||
494da23a | 494 | std::unique_ptr<WritableFile> writable_file; |
11fdf7f2 | 495 | fname = test::PerThreadDBPath("WithCollisionUserKey"); |
7c673cae | 496 | ASSERT_OK(env_->NewWritableFile(fname, &writable_file, env_options_)); |
494da23a | 497 | std::unique_ptr<WritableFileWriter> file_writer( |
11fdf7f2 | 498 | new WritableFileWriter(std::move(writable_file), fname, EnvOptions())); |
7c673cae FG |
499 | CuckooTableBuilder builder(file_writer.get(), kHashTableRatio, num_hash_fun, |
500 | 100, BytewiseComparator(), 1, false, false, | |
501 | GetSliceHash, 0 /* column_family_id */, | |
502 | kDefaultColumnFamilyName); | |
503 | ASSERT_OK(builder.status()); | |
504 | for (uint32_t i = 0; i < user_keys.size(); i++) { | |
505 | builder.Add(Slice(GetInternalKey(user_keys[i], true)), Slice(values[i])); | |
506 | ASSERT_EQ(builder.NumEntries(), i + 1); | |
507 | ASSERT_OK(builder.status()); | |
508 | } | |
509 | size_t bucket_size = user_keys[0].size() + values[0].size(); | |
510 | ASSERT_EQ(expected_table_size * bucket_size - 1, builder.FileSize()); | |
511 | ASSERT_OK(builder.Finish()); | |
512 | ASSERT_OK(file_writer->Close()); | |
513 | ASSERT_LE(expected_table_size * bucket_size, builder.FileSize()); | |
514 | ||
515 | std::string expected_unused_bucket = "key00"; | |
516 | expected_unused_bucket += std::string(values[0].size(), 'a'); | |
517 | CheckFileContents(user_keys, values, expected_locations, | |
518 | expected_unused_bucket, expected_table_size, 4, true); | |
519 | } | |
520 | ||
521 | TEST_F(CuckooBuilderTest, WithCollisionPathUserKey) { | |
522 | uint32_t num_hash_fun = 2; | |
523 | std::vector<std::string> user_keys = {"key01", "key02", "key03", | |
524 | "key04", "key05"}; | |
525 | std::vector<std::string> values = {"v01", "v02", "v03", "v04", "v05"}; | |
526 | // Need to have a temporary variable here as VS compiler does not currently | |
527 | // support operator= with initializer_list as a parameter | |
528 | std::unordered_map<std::string, std::vector<uint64_t>> hm = { | |
529 | {user_keys[0], {0, 1}}, | |
530 | {user_keys[1], {1, 2}}, | |
531 | {user_keys[2], {2, 3}}, | |
532 | {user_keys[3], {3, 4}}, | |
533 | {user_keys[4], {0, 2}}, | |
534 | }; | |
535 | hash_map = std::move(hm); | |
536 | ||
537 | std::vector<uint64_t> expected_locations = {0, 1, 3, 4, 2}; | |
538 | uint64_t expected_table_size = GetExpectedTableSize(user_keys.size()); | |
539 | ||
494da23a | 540 | std::unique_ptr<WritableFile> writable_file; |
11fdf7f2 | 541 | fname = test::PerThreadDBPath("WithCollisionPathUserKey"); |
7c673cae | 542 | ASSERT_OK(env_->NewWritableFile(fname, &writable_file, env_options_)); |
494da23a | 543 | std::unique_ptr<WritableFileWriter> file_writer( |
11fdf7f2 | 544 | new WritableFileWriter(std::move(writable_file), fname, EnvOptions())); |
7c673cae FG |
545 | CuckooTableBuilder builder(file_writer.get(), kHashTableRatio, num_hash_fun, |
546 | 2, BytewiseComparator(), 1, false, false, | |
547 | GetSliceHash, 0 /* column_family_id */, | |
548 | kDefaultColumnFamilyName); | |
549 | ASSERT_OK(builder.status()); | |
550 | for (uint32_t i = 0; i < user_keys.size(); i++) { | |
551 | builder.Add(Slice(GetInternalKey(user_keys[i], true)), Slice(values[i])); | |
552 | ASSERT_EQ(builder.NumEntries(), i + 1); | |
553 | ASSERT_OK(builder.status()); | |
554 | } | |
555 | size_t bucket_size = user_keys[0].size() + values[0].size(); | |
556 | ASSERT_EQ(expected_table_size * bucket_size - 1, builder.FileSize()); | |
557 | ASSERT_OK(builder.Finish()); | |
558 | ASSERT_OK(file_writer->Close()); | |
559 | ASSERT_LE(expected_table_size * bucket_size, builder.FileSize()); | |
560 | ||
561 | std::string expected_unused_bucket = "key00"; | |
562 | expected_unused_bucket += std::string(values[0].size(), 'a'); | |
563 | CheckFileContents(user_keys, values, expected_locations, | |
564 | expected_unused_bucket, expected_table_size, 2, true); | |
565 | } | |
566 | ||
567 | TEST_F(CuckooBuilderTest, FailWhenCollisionPathTooLong) { | |
568 | // Have two hash functions. Insert elements with overlapping hashes. | |
569 | // Finally try inserting an element with hash value somewhere in the middle | |
570 | // and it should fail because the no. of elements to displace is too high. | |
571 | uint32_t num_hash_fun = 2; | |
572 | std::vector<std::string> user_keys = {"key01", "key02", "key03", | |
573 | "key04", "key05"}; | |
574 | // Need to have a temporary variable here as VS compiler does not currently | |
575 | // support operator= with initializer_list as a parameter | |
576 | std::unordered_map<std::string, std::vector<uint64_t>> hm = { | |
577 | {user_keys[0], {0, 1}}, | |
578 | {user_keys[1], {1, 2}}, | |
579 | {user_keys[2], {2, 3}}, | |
580 | {user_keys[3], {3, 4}}, | |
581 | {user_keys[4], {0, 1}}, | |
582 | }; | |
583 | hash_map = std::move(hm); | |
584 | ||
494da23a | 585 | std::unique_ptr<WritableFile> writable_file; |
11fdf7f2 | 586 | fname = test::PerThreadDBPath("WithCollisionPathUserKey"); |
7c673cae | 587 | ASSERT_OK(env_->NewWritableFile(fname, &writable_file, env_options_)); |
494da23a | 588 | std::unique_ptr<WritableFileWriter> file_writer( |
11fdf7f2 | 589 | new WritableFileWriter(std::move(writable_file), fname, EnvOptions())); |
7c673cae FG |
590 | CuckooTableBuilder builder(file_writer.get(), kHashTableRatio, num_hash_fun, |
591 | 2, BytewiseComparator(), 1, false, false, | |
592 | GetSliceHash, 0 /* column_family_id */, | |
593 | kDefaultColumnFamilyName); | |
594 | ASSERT_OK(builder.status()); | |
595 | for (uint32_t i = 0; i < user_keys.size(); i++) { | |
596 | builder.Add(Slice(GetInternalKey(user_keys[i], false)), Slice("value")); | |
597 | ASSERT_EQ(builder.NumEntries(), i + 1); | |
598 | ASSERT_OK(builder.status()); | |
599 | } | |
600 | ASSERT_TRUE(builder.Finish().IsNotSupported()); | |
601 | ASSERT_OK(file_writer->Close()); | |
602 | } | |
603 | ||
604 | TEST_F(CuckooBuilderTest, FailWhenSameKeyInserted) { | |
605 | // Need to have a temporary variable here as VS compiler does not currently | |
606 | // support operator= with initializer_list as a parameter | |
607 | std::unordered_map<std::string, std::vector<uint64_t>> hm = { | |
608 | {"repeatedkey", {0, 1, 2, 3}}}; | |
609 | hash_map = std::move(hm); | |
610 | uint32_t num_hash_fun = 4; | |
611 | std::string user_key = "repeatedkey"; | |
612 | ||
494da23a | 613 | std::unique_ptr<WritableFile> writable_file; |
11fdf7f2 | 614 | fname = test::PerThreadDBPath("FailWhenSameKeyInserted"); |
7c673cae | 615 | ASSERT_OK(env_->NewWritableFile(fname, &writable_file, env_options_)); |
494da23a | 616 | std::unique_ptr<WritableFileWriter> file_writer( |
11fdf7f2 | 617 | new WritableFileWriter(std::move(writable_file), fname, EnvOptions())); |
7c673cae FG |
618 | CuckooTableBuilder builder(file_writer.get(), kHashTableRatio, num_hash_fun, |
619 | 100, BytewiseComparator(), 1, false, false, | |
620 | GetSliceHash, 0 /* column_family_id */, | |
621 | kDefaultColumnFamilyName); | |
622 | ASSERT_OK(builder.status()); | |
623 | ||
624 | builder.Add(Slice(GetInternalKey(user_key, false)), Slice("value1")); | |
625 | ASSERT_EQ(builder.NumEntries(), 1u); | |
626 | ASSERT_OK(builder.status()); | |
627 | builder.Add(Slice(GetInternalKey(user_key, true)), Slice("value2")); | |
628 | ASSERT_EQ(builder.NumEntries(), 2u); | |
629 | ASSERT_OK(builder.status()); | |
630 | ||
631 | ASSERT_TRUE(builder.Finish().IsNotSupported()); | |
632 | ASSERT_OK(file_writer->Close()); | |
633 | } | |
634 | } // namespace rocksdb | |
635 | ||
636 | int main(int argc, char** argv) { | |
637 | ::testing::InitGoogleTest(&argc, argv); | |
638 | return RUN_ALL_TESTS(); | |
639 | } | |
640 | ||
641 | #else | |
642 | #include <stdio.h> | |
643 | ||
11fdf7f2 | 644 | int main(int /*argc*/, char** /*argv*/) { |
7c673cae FG |
645 | fprintf(stderr, "SKIPPED as Cuckoo table is not supported in ROCKSDB_LITE\n"); |
646 | return 0; | |
647 | } | |
648 | ||
649 | #endif // ROCKSDB_LITE |