1 // Copyright (c) 2011-present, Facebook, Inc. All rights reserved.
2 // This source code is licensed under the BSD-style license found in the
3 // LICENSE file in the root directory of this source tree. An additional grant
4 // of patent rights can be found in the PATENTS file in the same directory.
8 #include "memtable/hash_cuckoo_rep.h"
18 #include "db/memtable.h"
19 #include "memtable/skiplist.h"
20 #include "memtable/stl_wrappers.h"
21 #include "port/port.h"
22 #include "rocksdb/memtablerep.h"
23 #include "util/murmurhash.h"
28 // the default maximum size of the cuckoo path searching queue
29 static const int kCuckooPathMaxSearchSteps
= 100;
32 static const int kNullStep
= -1;
33 // the bucket id in the cuckoo array.
35 // index of cuckoo-step array that points to its previous step,
36 // -1 if it the beginning step.
38 // the depth of the current step.
41 CuckooStep() : bucket_id_(-1), prev_step_id_(kNullStep
), depth_(1) {}
43 CuckooStep(CuckooStep
&& o
) = default;
45 CuckooStep
& operator=(CuckooStep
&& rhs
) {
46 bucket_id_
= std::move(rhs
.bucket_id_
);
47 prev_step_id_
= std::move(rhs
.prev_step_id_
);
48 depth_
= std::move(rhs
.depth_
);
52 CuckooStep(const CuckooStep
&) = delete;
53 CuckooStep
& operator=(const CuckooStep
&) = delete;
55 CuckooStep(int bucket_id
, int prev_step_id
, int depth
)
56 : bucket_id_(bucket_id
), prev_step_id_(prev_step_id
), depth_(depth
) {}
59 class HashCuckooRep
: public MemTableRep
{
61 explicit HashCuckooRep(const MemTableRep::KeyComparator
& compare
,
62 MemTableAllocator
* allocator
,
63 const size_t bucket_count
,
64 const unsigned int hash_func_count
,
65 const size_t approximate_entry_size
)
66 : MemTableRep(allocator
),
68 allocator_(allocator
),
69 bucket_count_(bucket_count
),
70 approximate_entry_size_(approximate_entry_size
),
71 cuckoo_path_max_depth_(kDefaultCuckooPathMaxDepth
),
73 hash_function_count_(hash_func_count
),
74 backup_table_(nullptr) {
75 char* mem
= reinterpret_cast<char*>(
76 allocator_
->Allocate(sizeof(std::atomic
<const char*>) * bucket_count_
));
77 cuckoo_array_
= new (mem
) std::atomic
<char*>[bucket_count_
];
78 for (unsigned int bid
= 0; bid
< bucket_count_
; ++bid
) {
79 cuckoo_array_
[bid
].store(nullptr, std::memory_order_relaxed
);
82 cuckoo_path_
= reinterpret_cast<int*>(
83 allocator_
->Allocate(sizeof(int) * (cuckoo_path_max_depth_
+ 1)));
84 is_nearly_full_
= false;
87 // return false, indicating HashCuckooRep does not support merge operator.
88 virtual bool IsMergeOperatorSupported() const override
{ return false; }
90 // return false, indicating HashCuckooRep does not support snapshot.
91 virtual bool IsSnapshotSupported() const override
{ return false; }
93 // Returns true iff an entry that compares equal to key is in the collection.
94 virtual bool Contains(const char* internal_key
) const override
;
96 virtual ~HashCuckooRep() override
{}
98 // Insert the specified key (internal_key) into the mem-table. Assertion
100 // the current mem-table already contains the specified key.
101 virtual void Insert(KeyHandle handle
) override
;
103 // This function returns bucket_count_ * approximate_entry_size_ when any
104 // of the followings happen to disallow further write operations:
105 // 1. when the fullness reaches kMaxFullnes.
106 // 2. when the backup_table_ is used.
108 // otherwise, this function will always return 0.
109 virtual size_t ApproximateMemoryUsage() override
{
110 if (is_nearly_full_
) {
111 return bucket_count_
* approximate_entry_size_
;
116 virtual void Get(const LookupKey
& k
, void* callback_args
,
117 bool (*callback_func
)(void* arg
,
118 const char* entry
)) override
;
120 class Iterator
: public MemTableRep::Iterator
{
121 std::shared_ptr
<std::vector
<const char*>> bucket_
;
122 std::vector
<const char*>::const_iterator
mutable cit_
;
123 const KeyComparator
& compare_
;
124 std::string tmp_
; // For passing to EncodeKey
125 bool mutable sorted_
;
129 explicit Iterator(std::shared_ptr
<std::vector
<const char*>> bucket
,
130 const KeyComparator
& compare
);
132 // Initialize an iterator over the specified collection.
133 // The returned iterator is not valid.
134 // explicit Iterator(const MemTableRep* collection);
135 virtual ~Iterator() override
{};
137 // Returns true iff the iterator is positioned at a valid node.
138 virtual bool Valid() const override
;
140 // Returns the key at the current position.
142 virtual const char* key() const override
;
144 // Advances to the next position.
146 virtual void Next() override
;
148 // Advances to the previous position.
150 virtual void Prev() override
;
152 // Advance to the first entry with a key >= target
153 virtual void Seek(const Slice
& user_key
, const char* memtable_key
) override
;
155 // Retreat to the last entry with a key <= target
156 virtual void SeekForPrev(const Slice
& user_key
,
157 const char* memtable_key
) override
;
159 // Position at the first entry in collection.
160 // Final state of iterator is Valid() iff collection is not empty.
161 virtual void SeekToFirst() override
;
163 // Position at the last entry in collection.
164 // Final state of iterator is Valid() iff collection is not empty.
165 virtual void SeekToLast() override
;
168 struct CuckooStepBuffer
{
169 CuckooStepBuffer() : write_index_(0), read_index_(0) {}
170 ~CuckooStepBuffer() {}
174 CuckooStep steps_
[kCuckooPathMaxSearchSteps
];
176 CuckooStep
& NextWriteBuffer() { return steps_
[write_index_
++]; }
178 inline const CuckooStep
& ReadNext() { return steps_
[read_index_
++]; }
180 inline bool HasNewWrite() { return write_index_
> read_index_
; }
182 inline void reset() {
187 inline bool IsFull() { return write_index_
>= kCuckooPathMaxSearchSteps
; }
189 // returns the number of steps that has been read
190 inline int ReadCount() { return read_index_
; }
192 // returns the number of steps that has been written to the buffer.
193 inline int WriteCount() { return write_index_
; }
197 const MemTableRep::KeyComparator
& compare_
;
198 // the pointer to Allocator to allocate memory, immutable after construction.
199 MemTableAllocator
* const allocator_
;
200 // the number of hash bucket in the hash table.
201 const size_t bucket_count_
;
202 // approximate size of each entry
203 const size_t approximate_entry_size_
;
204 // the maxinum depth of the cuckoo path.
205 const unsigned int cuckoo_path_max_depth_
;
206 // the current number of entries in cuckoo_array_ which has been occupied.
207 size_t occupied_count_
;
208 // the current number of hash functions used in the cuckoo hash.
209 unsigned int hash_function_count_
;
210 // the backup MemTableRep to handle the case where cuckoo hash cannot find
211 // a vacant bucket for inserting the key of a put request.
212 std::shared_ptr
<MemTableRep
> backup_table_
;
213 // the array to store pointers, pointing to the actual data.
214 std::atomic
<char*>* cuckoo_array_
;
215 // a buffer to store cuckoo path
217 // a boolean flag indicating whether the fullness of bucket array
218 // reaches the point to make the current memtable immutable.
219 bool is_nearly_full_
;
221 // the default maximum depth of the cuckoo path.
222 static const unsigned int kDefaultCuckooPathMaxDepth
= 10;
224 CuckooStepBuffer step_buffer_
;
226 // returns the bucket id assogied to the input slice based on the
227 unsigned int GetHash(const Slice
& slice
, const int hash_func_id
) const {
228 // the seeds used in the Murmur hash to produce different hash functions.
229 static const int kMurmurHashSeeds
[HashCuckooRepFactory::kMaxHashCount
] = {
230 545609244, 1769731426, 763324157, 13099088, 592422103,
231 1899789565, 248369300, 1984183468, 1613664382, 1491157517};
232 return static_cast<unsigned int>(
233 MurmurHash(slice
.data(), static_cast<int>(slice
.size()),
234 kMurmurHashSeeds
[hash_func_id
]) %
238 // A cuckoo path is a sequence of bucket ids, where each id points to a
239 // location of cuckoo_array_. This path describes the displacement sequence
240 // of entries in order to store the desired data specified by the input user
241 // key. The path starts from one of the locations associated with the
242 // specified user key and ends at a vacant space in the cuckoo array. This
243 // function will update the cuckoo_path.
245 // @return true if it found a cuckoo path.
246 bool FindCuckooPath(const char* internal_key
, const Slice
& user_key
,
247 int* cuckoo_path
, size_t* cuckoo_path_length
,
248 int initial_hash_id
= 0);
250 // Perform quick insert by checking whether there is a vacant bucket in one
251 // of the possible locations of the input key. If so, then the function will
252 // return true and the key will be stored in that vacant bucket.
254 // This function is a helper function of FindCuckooPath that discovers the
255 // first possible steps of a cuckoo path. It begins by first computing
256 // the possible locations of the input keys (and stores them in bucket_ids.)
257 // Then, if one of its possible locations is vacant, then the input key will
258 // be stored in that vacant space and the function will return true.
259 // Otherwise, the function will return false indicating a complete search
260 // of cuckoo-path is needed.
261 bool QuickInsert(const char* internal_key
, const Slice
& user_key
,
262 int bucket_ids
[], const int initial_hash_id
);
264 // Returns the pointer to the internal iterator to the buckets where buckets
265 // are sorted according to the user specified KeyComparator. Note that
266 // any insert after this function call may affect the sorted nature of
267 // the returned iterator.
268 virtual MemTableRep::Iterator
* GetIterator(Arena
* arena
) override
{
269 std::vector
<const char*> compact_buckets
;
270 for (unsigned int bid
= 0; bid
< bucket_count_
; ++bid
) {
271 const char* bucket
= cuckoo_array_
[bid
].load(std::memory_order_relaxed
);
272 if (bucket
!= nullptr) {
273 compact_buckets
.push_back(bucket
);
276 MemTableRep
* backup_table
= backup_table_
.get();
277 if (backup_table
!= nullptr) {
278 std::unique_ptr
<MemTableRep::Iterator
> iter(backup_table
->GetIterator());
279 for (iter
->SeekToFirst(); iter
->Valid(); iter
->Next()) {
280 compact_buckets
.push_back(iter
->key());
283 if (arena
== nullptr) {
285 std::shared_ptr
<std::vector
<const char*>>(
286 new std::vector
<const char*>(std::move(compact_buckets
))),
289 auto mem
= arena
->AllocateAligned(sizeof(Iterator
));
290 return new (mem
) Iterator(
291 std::shared_ptr
<std::vector
<const char*>>(
292 new std::vector
<const char*>(std::move(compact_buckets
))),
298 void HashCuckooRep::Get(const LookupKey
& key
, void* callback_args
,
299 bool (*callback_func
)(void* arg
, const char* entry
)) {
300 Slice user_key
= key
.user_key();
301 for (unsigned int hid
= 0; hid
< hash_function_count_
; ++hid
) {
303 cuckoo_array_
[GetHash(user_key
, hid
)].load(std::memory_order_acquire
);
304 if (bucket
!= nullptr) {
305 Slice bucket_user_key
= UserKey(bucket
);
306 if (user_key
== bucket_user_key
) {
307 callback_func(callback_args
, bucket
);
311 // as Put() always stores at the vacant bucket located by the
312 // hash function with the smallest possible id, when we first
313 // find a vacant bucket in Get(), that means a miss.
317 MemTableRep
* backup_table
= backup_table_
.get();
318 if (backup_table
!= nullptr) {
319 backup_table
->Get(key
, callback_args
, callback_func
);
323 void HashCuckooRep::Insert(KeyHandle handle
) {
324 static const float kMaxFullness
= 0.90f
;
326 auto* key
= static_cast<char*>(handle
);
327 int initial_hash_id
= 0;
328 size_t cuckoo_path_length
= 0;
329 auto user_key
= UserKey(key
);
331 if (FindCuckooPath(key
, user_key
, cuckoo_path_
, &cuckoo_path_length
,
332 initial_hash_id
) == false) {
333 // if true, then we can't find a vacant bucket for this key even we
334 // have used up all the hash functions. Then use a backup memtable to
335 // store such key, which will further make this mem-table become
337 if (backup_table_
.get() == nullptr) {
338 VectorRepFactory
factory(10);
340 factory
.CreateMemTableRep(compare_
, allocator_
, nullptr, nullptr));
341 is_nearly_full_
= true;
343 backup_table_
->Insert(key
);
346 // when reaching this point, means the insert can be done successfully.
348 if (occupied_count_
>= bucket_count_
* kMaxFullness
) {
349 is_nearly_full_
= true;
352 // perform kickout process if the length of cuckoo path > 1.
353 if (cuckoo_path_length
== 0) return;
355 // the cuckoo path stores the kickout path in reverse order.
356 // so the kickout or displacement is actually performed
357 // in reverse order, which avoids false-negatives on read
358 // by moving each key involved in the cuckoo path to the new
359 // location before replacing it.
360 for (size_t i
= 1; i
< cuckoo_path_length
; ++i
) {
361 int kicked_out_bid
= cuckoo_path_
[i
- 1];
362 int current_bid
= cuckoo_path_
[i
];
363 // since we only allow one writer at a time, it is safe to do relaxed read.
364 cuckoo_array_
[kicked_out_bid
]
365 .store(cuckoo_array_
[current_bid
].load(std::memory_order_relaxed
),
366 std::memory_order_release
);
368 int insert_key_bid
= cuckoo_path_
[cuckoo_path_length
- 1];
369 cuckoo_array_
[insert_key_bid
].store(key
, std::memory_order_release
);
372 bool HashCuckooRep::Contains(const char* internal_key
) const {
373 auto user_key
= UserKey(internal_key
);
374 for (unsigned int hid
= 0; hid
< hash_function_count_
; ++hid
) {
375 const char* stored_key
=
376 cuckoo_array_
[GetHash(user_key
, hid
)].load(std::memory_order_acquire
);
377 if (stored_key
!= nullptr) {
378 if (compare_(internal_key
, stored_key
) == 0) {
386 bool HashCuckooRep::QuickInsert(const char* internal_key
, const Slice
& user_key
,
387 int bucket_ids
[], const int initial_hash_id
) {
388 int cuckoo_bucket_id
= -1;
390 // Below does the followings:
391 // 0. Calculate all possible locations of the input key.
392 // 1. Check if there is a bucket having same user_key as the input does.
393 // 2. If there exists such bucket, then replace this bucket by the newly
394 // insert data and return. This step also performs duplication check.
395 // 3. If no such bucket exists but exists a vacant bucket, then insert the
396 // input data into it.
397 // 4. If step 1 to 3 all fail, then return false.
398 for (unsigned int hid
= initial_hash_id
; hid
< hash_function_count_
; ++hid
) {
399 bucket_ids
[hid
] = GetHash(user_key
, hid
);
400 // since only one PUT is allowed at a time, and this is part of the PUT
401 // operation, so we can safely perform relaxed load.
402 const char* stored_key
=
403 cuckoo_array_
[bucket_ids
[hid
]].load(std::memory_order_relaxed
);
404 if (stored_key
== nullptr) {
405 if (cuckoo_bucket_id
== -1) {
406 cuckoo_bucket_id
= bucket_ids
[hid
];
409 const auto bucket_user_key
= UserKey(stored_key
);
410 if (bucket_user_key
.compare(user_key
) == 0) {
411 cuckoo_bucket_id
= bucket_ids
[hid
];
417 if (cuckoo_bucket_id
!= -1) {
418 cuckoo_array_
[cuckoo_bucket_id
].store(const_cast<char*>(internal_key
),
419 std::memory_order_release
);
426 // Perform pre-check and find the shortest cuckoo path. A cuckoo path
427 // is a displacement sequence for inserting the specified input key.
429 // @return true if it successfully found a vacant space or cuckoo-path.
430 // If the return value is true but the length of cuckoo_path is zero,
431 // then it indicates that a vacant bucket or an bucket with matched user
432 // key with the input is found, and a quick insertion is done.
433 bool HashCuckooRep::FindCuckooPath(const char* internal_key
,
434 const Slice
& user_key
, int* cuckoo_path
,
435 size_t* cuckoo_path_length
,
436 const int initial_hash_id
) {
437 int bucket_ids
[HashCuckooRepFactory::kMaxHashCount
];
438 *cuckoo_path_length
= 0;
440 if (QuickInsert(internal_key
, user_key
, bucket_ids
, initial_hash_id
)) {
443 // If this step is reached, then it means:
444 // 1. no vacant bucket in any of the possible locations of the input key.
445 // 2. none of the possible locations of the input key has the same user
446 // key as the input `internal_key`.
448 // the front and back indices for the step_queue_
449 step_buffer_
.reset();
451 for (unsigned int hid
= initial_hash_id
; hid
< hash_function_count_
; ++hid
) {
452 /// CuckooStep& current_step = step_queue_[front_pos++];
453 CuckooStep
& current_step
= step_buffer_
.NextWriteBuffer();
454 current_step
.bucket_id_
= bucket_ids
[hid
];
455 current_step
.prev_step_id_
= CuckooStep::kNullStep
;
456 current_step
.depth_
= 1;
459 while (step_buffer_
.HasNewWrite()) {
460 int step_id
= step_buffer_
.read_index_
;
461 const CuckooStep
& step
= step_buffer_
.ReadNext();
462 // Since it's a BFS process, then the first step with its depth deeper
463 // than the maximum allowed depth indicates all the remaining steps
464 // in the step buffer queue will all exceed the maximum depth.
465 // Return false immediately indicating we can't find a vacant bucket
466 // for the input key before the maximum allowed depth.
467 if (step
.depth_
>= cuckoo_path_max_depth_
) {
470 // again, we can perform no barrier load safely here as the current
471 // thread is the only writer.
472 Slice bucket_user_key
=
473 UserKey(cuckoo_array_
[step
.bucket_id_
].load(std::memory_order_relaxed
));
474 if (step
.prev_step_id_
!= CuckooStep::kNullStep
) {
475 if (bucket_user_key
== user_key
) {
476 // then there is a loop in the current path, stop discovering this path.
480 // if the current bucket stores at its nth location, then we only consider
481 // its mth location where m > n. This property makes sure that all reads
482 // will not miss if we do have data associated to the query key.
484 // The n and m in the above statement is the start_hid and hid in the code.
485 unsigned int start_hid
= hash_function_count_
;
486 for (unsigned int hid
= 0; hid
< hash_function_count_
; ++hid
) {
487 bucket_ids
[hid
] = GetHash(bucket_user_key
, hid
);
488 if (step
.bucket_id_
== bucket_ids
[hid
]) {
492 // must found a bucket which is its current "home".
493 assert(start_hid
!= hash_function_count_
);
495 // explore all possible next steps from the current step.
496 for (unsigned int hid
= start_hid
+ 1; hid
< hash_function_count_
; ++hid
) {
497 CuckooStep
& next_step
= step_buffer_
.NextWriteBuffer();
498 next_step
.bucket_id_
= bucket_ids
[hid
];
499 next_step
.prev_step_id_
= step_id
;
500 next_step
.depth_
= step
.depth_
+ 1;
501 // once a vacant bucket is found, trace back all its previous steps
502 // to generate a cuckoo path.
503 if (cuckoo_array_
[next_step
.bucket_id_
].load(std::memory_order_relaxed
) ==
505 // store the last step in the cuckoo path. Note that cuckoo_path
506 // stores steps in reverse order. This allows us to move keys along
507 // the cuckoo path by storing each key to the new place first before
508 // removing it from the old place. This property ensures reads will
509 // not missed due to moving keys along the cuckoo path.
510 cuckoo_path
[(*cuckoo_path_length
)++] = next_step
.bucket_id_
;
512 for (depth
= step
.depth_
; depth
> 0 && step_id
!= CuckooStep::kNullStep
;
514 const CuckooStep
& prev_step
= step_buffer_
.steps_
[step_id
];
515 cuckoo_path
[(*cuckoo_path_length
)++] = prev_step
.bucket_id_
;
516 step_id
= prev_step
.prev_step_id_
;
518 assert(depth
== 0 && step_id
== CuckooStep::kNullStep
);
521 if (step_buffer_
.IsFull()) {
522 // if true, then it reaches maxinum number of cuckoo search steps.
528 // tried all possible paths but still not unable to find a cuckoo path
529 // which path leads to a vacant bucket.
533 HashCuckooRep::Iterator::Iterator(
534 std::shared_ptr
<std::vector
<const char*>> bucket
,
535 const KeyComparator
& compare
)
537 cit_(bucket_
->end()),
541 void HashCuckooRep::Iterator::DoSort() const {
543 std::sort(bucket_
->begin(), bucket_
->end(),
544 stl_wrappers::Compare(compare_
));
545 cit_
= bucket_
->begin();
550 // Returns true iff the iterator is positioned at a valid node.
551 bool HashCuckooRep::Iterator::Valid() const {
553 return cit_
!= bucket_
->end();
556 // Returns the key at the current position.
558 const char* HashCuckooRep::Iterator::key() const {
563 // Advances to the next position.
565 void HashCuckooRep::Iterator::Next() {
567 if (cit_
== bucket_
->end()) {
573 // Advances to the previous position.
575 void HashCuckooRep::Iterator::Prev() {
577 if (cit_
== bucket_
->begin()) {
578 // If you try to go back from the first element, the iterator should be
579 // invalidated. So we set it to past-the-end. This means that you can
580 // treat the container circularly.
581 cit_
= bucket_
->end();
587 // Advance to the first entry with a key >= target
588 void HashCuckooRep::Iterator::Seek(const Slice
& user_key
,
589 const char* memtable_key
) {
591 // Do binary search to find first value not less than the target
592 const char* encoded_key
=
593 (memtable_key
!= nullptr) ? memtable_key
: EncodeKey(&tmp_
, user_key
);
594 cit_
= std::equal_range(bucket_
->begin(), bucket_
->end(), encoded_key
,
595 [this](const char* a
, const char* b
) {
596 return compare_(a
, b
) < 0;
600 // Retreat to the last entry with a key <= target
601 void HashCuckooRep::Iterator::SeekForPrev(const Slice
& user_key
,
602 const char* memtable_key
) {
606 // Position at the first entry in collection.
607 // Final state of iterator is Valid() iff collection is not empty.
608 void HashCuckooRep::Iterator::SeekToFirst() {
610 cit_
= bucket_
->begin();
613 // Position at the last entry in collection.
614 // Final state of iterator is Valid() iff collection is not empty.
615 void HashCuckooRep::Iterator::SeekToLast() {
617 cit_
= bucket_
->end();
618 if (bucket_
->size() != 0) {
625 MemTableRep
* HashCuckooRepFactory::CreateMemTableRep(
626 const MemTableRep::KeyComparator
& compare
, MemTableAllocator
* allocator
,
627 const SliceTransform
* transform
, Logger
* logger
) {
628 // The estimated average fullness. The write performance of any close hash
629 // degrades as the fullness of the mem-table increases. Setting kFullness
630 // to a value around 0.7 can better avoid write performance degradation while
631 // keeping efficient memory usage.
632 static const float kFullness
= 0.7f
;
633 size_t pointer_size
= sizeof(std::atomic
<const char*>);
634 assert(write_buffer_size_
>= (average_data_size_
+ pointer_size
));
635 size_t bucket_count
=
637 (write_buffer_size_
/ (average_data_size_
+ pointer_size
)) / kFullness
+
639 unsigned int hash_function_count
= hash_function_count_
;
640 if (hash_function_count
< 2) {
641 hash_function_count
= 2;
643 if (hash_function_count
> kMaxHashCount
) {
644 hash_function_count
= kMaxHashCount
;
646 return new HashCuckooRep(compare
, allocator
, bucket_count
,
649 (average_data_size_
+ pointer_size
) / kFullness
)
653 MemTableRepFactory
* NewHashCuckooRepFactory(size_t write_buffer_size
,
654 size_t average_data_size
,
655 unsigned int hash_function_count
) {
656 return new HashCuckooRepFactory(write_buffer_size
, average_data_size
,
657 hash_function_count
);
660 } // namespace rocksdb
661 #endif // ROCKSDB_LITE