1 // Copyright (c) 2011-present, Facebook, Inc. All rights reserved.
2 // This source code is licensed under both the GPLv2 (found in the
3 // COPYING file in the root directory) and Apache 2.0 License
4 // (found in the LICENSE.Apache file in the root directory).
6 // This file contains the interface that must be implemented by any collection
7 // to be used as the backing store for a MemTable. Such a collection must
8 // satisfy the following properties:
9 // (1) It does not store duplicate items.
10 // (2) It uses MemTableRep::KeyComparator to compare items for iteration and
12 // (3) It can be accessed concurrently by multiple readers and can support
13 // during reads. However, it needn't support multiple concurrent writes.
14 // (4) Items are never deleted.
15 // The liberal use of assertions is encouraged to enforce (1).
17 // The factory will be passed an MemTableAllocator object when a new MemTableRep
20 // Users can implement their own memtable representations. We include three
22 // - SkipListRep: This is the default; it is backed by a skip list.
23 // - HashSkipListRep: The memtable rep that is best used for keys that are
24 // structured like "prefix:suffix" where iteration within a prefix is
25 // common and iteration across different prefixes is rare. It is backed by
26 // a hash map where each bucket is a skip list.
27 // - VectorRep: This is backed by an unordered std::vector. On iteration, the
28 // vector is sorted. It is intelligent about sorting; once the MarkReadOnly()
29 // has been called, the vector will only be sorted once. It is optimized for
30 // random-write-heavy workloads.
32 // The last four implementations are designed for situations in which
33 // iteration over the entire collection is rare since doing so requires all the
34 // keys to be copied into a sorted data structure.
43 #include <unordered_set>
45 #include "rocksdb/customizable.h"
46 #include "rocksdb/slice.h"
48 namespace ROCKSDB_NAMESPACE
{
57 using KeyHandle
= void*;
59 extern Slice
GetLengthPrefixedSlice(const char* data
);
63 // KeyComparator provides a means to compare keys, which are internal keys
64 // concatenated with values.
67 using DecodedType
= ROCKSDB_NAMESPACE::Slice
;
69 virtual DecodedType
decode_key(const char* key
) const {
70 // The format of key is frozen and can be treated as a part of the API
71 // contract. Refer to MemTable::Add for details.
72 return GetLengthPrefixedSlice(key
);
75 // Compare a and b. Return a negative value if a is less than b, 0 if they
76 // are equal, and a positive value if a is greater than b
77 virtual int operator()(const char* prefix_len_key1
,
78 const char* prefix_len_key2
) const = 0;
80 virtual int operator()(const char* prefix_len_key
,
81 const Slice
& key
) const = 0;
83 virtual ~KeyComparator() {}
86 explicit MemTableRep(Allocator
* allocator
) : allocator_(allocator
) {}
88 // Allocate a buf of len size for storing key. The idea is that a
89 // specific memtable representation knows its underlying data structure
90 // better. By allowing it to allocate memory, it can possibly put
91 // correlated stuff in consecutive memory area to make processor
92 // prefetching more efficient.
93 virtual KeyHandle
Allocate(const size_t len
, char** buf
);
95 // Insert key into the collection. (The caller will pack key and value into a
96 // single buffer and pass that in as the parameter to Insert).
97 // REQUIRES: nothing that compares equal to key is currently in the
98 // collection, and no concurrent modifications to the table in progress
99 virtual void Insert(KeyHandle handle
) = 0;
102 // Returns false if MemTableRepFactory::CanHandleDuplicatedKey() is true and
103 // the <key, seq> already exists.
104 virtual bool InsertKey(KeyHandle handle
) {
109 // Same as Insert(), but in additional pass a hint to insert location for
110 // the key. If hint points to nullptr, a new hint will be populated.
111 // otherwise the hint will be updated to reflect the last insert location.
113 // Currently only skip-list based memtable implement the interface. Other
114 // implementations will fallback to Insert() by default.
115 virtual void InsertWithHint(KeyHandle handle
, void** /*hint*/) {
116 // Ignore the hint by default.
120 // Same as ::InsertWithHint
121 // Returns false if MemTableRepFactory::CanHandleDuplicatedKey() is true and
122 // the <key, seq> already exists.
123 virtual bool InsertKeyWithHint(KeyHandle handle
, void** hint
) {
124 InsertWithHint(handle
, hint
);
128 // Same as ::InsertWithHint, but allow concurrent write
130 // If hint points to nullptr, a new hint will be allocated on heap, otherwise
131 // the hint will be updated to reflect the last insert location. The hint is
132 // owned by the caller and it is the caller's responsibility to delete the
135 // Currently only skip-list based memtable implement the interface. Other
136 // implementations will fallback to InsertConcurrently() by default.
137 virtual void InsertWithHintConcurrently(KeyHandle handle
, void** /*hint*/) {
138 // Ignore the hint by default.
139 InsertConcurrently(handle
);
142 // Same as ::InsertWithHintConcurrently
143 // Returns false if MemTableRepFactory::CanHandleDuplicatedKey() is true and
144 // the <key, seq> already exists.
145 virtual bool InsertKeyWithHintConcurrently(KeyHandle handle
, void** hint
) {
146 InsertWithHintConcurrently(handle
, hint
);
150 // Like Insert(handle), but may be called concurrent with other calls
151 // to InsertConcurrently for other handles.
153 // Returns false if MemTableRepFactory::CanHandleDuplicatedKey() is true and
154 // the <key, seq> already exists.
155 virtual void InsertConcurrently(KeyHandle handle
);
157 // Same as ::InsertConcurrently
158 // Returns false if MemTableRepFactory::CanHandleDuplicatedKey() is true and
159 // the <key, seq> already exists.
160 virtual bool InsertKeyConcurrently(KeyHandle handle
) {
161 InsertConcurrently(handle
);
165 // Returns true iff an entry that compares equal to key is in the collection.
166 virtual bool Contains(const char* key
) const = 0;
168 // Notify this table rep that it will no longer be added to. By default,
169 // does nothing. After MarkReadOnly() is called, this table rep will
170 // not be written to (ie No more calls to Allocate(), Insert(),
171 // or any writes done directly to entries accessed through the iterator.)
172 virtual void MarkReadOnly() {}
174 // Notify this table rep that it has been flushed to stable storage.
175 // By default, does nothing.
177 // Invariant: MarkReadOnly() is called, before MarkFlushed().
178 // Note that this method if overridden, should not run for an extended period
179 // of time. Otherwise, RocksDB may be blocked.
180 virtual void MarkFlushed() {}
182 // Look up key from the mem table, since the first key in the mem table whose
183 // user_key matches the one given k, call the function callback_func(), with
184 // callback_args directly forwarded as the first parameter, and the mem table
185 // key as the second parameter. If the return value is false, then terminates.
186 // Otherwise, go through the next key.
188 // It's safe for Get() to terminate after having finished all the potential
189 // key for the k.user_key(), or not.
192 // Get() function with a default value of dynamically construct an iterator,
193 // seek and call the call back function.
194 virtual void Get(const LookupKey
& k
, void* callback_args
,
195 bool (*callback_func
)(void* arg
, const char* entry
));
197 virtual uint64_t ApproximateNumEntries(const Slice
& /*start_ikey*/,
198 const Slice
& /*end_key*/) {
202 // Returns a vector of unique random memtable entries of approximate
203 // size 'target_sample_size' (this size is not strictly enforced).
204 virtual void UniqueRandomSample(const uint64_t num_entries
,
205 const uint64_t target_sample_size
,
206 std::unordered_set
<const char*>* entries
) {
208 (void)target_sample_size
;
213 // Report an approximation of how much memory has been used other than memory
214 // that was allocated through the allocator. Safe to call from any thread.
215 virtual size_t ApproximateMemoryUsage() = 0;
217 virtual ~MemTableRep() {}
219 // Iteration over the contents of a skip collection
222 // Initialize an iterator over the specified collection.
223 // The returned iterator is not valid.
224 // explicit Iterator(const MemTableRep* collection);
225 virtual ~Iterator() {}
227 // Returns true iff the iterator is positioned at a valid node.
228 virtual bool Valid() const = 0;
230 // Returns the key at the current position.
232 virtual const char* key() const = 0;
234 // Advances to the next position.
236 virtual void Next() = 0;
238 // Advances to the previous position.
240 virtual void Prev() = 0;
242 // Advance to the first entry with a key >= target
243 virtual void Seek(const Slice
& internal_key
, const char* memtable_key
) = 0;
245 // retreat to the first entry with a key <= target
246 virtual void SeekForPrev(const Slice
& internal_key
,
247 const char* memtable_key
) = 0;
249 virtual void RandomSeek() {}
251 // Position at the first entry in collection.
252 // Final state of iterator is Valid() iff collection is not empty.
253 virtual void SeekToFirst() = 0;
255 // Position at the last entry in collection.
256 // Final state of iterator is Valid() iff collection is not empty.
257 virtual void SeekToLast() = 0;
260 // Return an iterator over the keys in this representation.
261 // arena: If not null, the arena needs to be used to allocate the Iterator.
262 // When destroying the iterator, the caller will not call "delete"
263 // but Iterator::~Iterator() directly. The destructor needs to destroy
264 // all the states but those allocated in arena.
265 virtual Iterator
* GetIterator(Arena
* arena
= nullptr) = 0;
267 // Return an iterator that has a special Seek semantics. The result of
268 // a Seek might only include keys with the same prefix as the target key.
269 // arena: If not null, the arena is used to allocate the Iterator.
270 // When destroying the iterator, the caller will not call "delete"
271 // but Iterator::~Iterator() directly. The destructor needs to destroy
272 // all the states but those allocated in arena.
273 virtual Iterator
* GetDynamicPrefixIterator(Arena
* arena
= nullptr) {
274 return GetIterator(arena
);
277 // Return true if the current MemTableRep supports merge operator.
279 virtual bool IsMergeOperatorSupported() const { return true; }
281 // Return true if the current MemTableRep supports snapshot
283 virtual bool IsSnapshotSupported() const { return true; }
286 // When *key is an internal key concatenated with the value, returns the
288 virtual Slice
UserKey(const char* key
) const;
290 Allocator
* allocator_
;
293 // This is the base class for all factories that are used by RocksDB to create
294 // new MemTableRep objects
295 class MemTableRepFactory
: public Customizable
{
297 ~MemTableRepFactory() override
{}
299 static const char* Type() { return "MemTableRepFactory"; }
300 static Status
CreateFromString(const ConfigOptions
& config_options
,
301 const std::string
& id
,
302 std::unique_ptr
<MemTableRepFactory
>* factory
);
303 static Status
CreateFromString(const ConfigOptions
& config_options
,
304 const std::string
& id
,
305 std::shared_ptr
<MemTableRepFactory
>* factory
);
307 virtual MemTableRep
* CreateMemTableRep(const MemTableRep::KeyComparator
&,
308 Allocator
*, const SliceTransform
*,
310 virtual MemTableRep
* CreateMemTableRep(
311 const MemTableRep::KeyComparator
& key_cmp
, Allocator
* allocator
,
312 const SliceTransform
* slice_transform
, Logger
* logger
,
313 uint32_t /* column_family_id */) {
314 return CreateMemTableRep(key_cmp
, allocator
, slice_transform
, logger
);
317 const char* Name() const override
= 0;
319 // Return true if the current MemTableRep supports concurrent inserts
321 virtual bool IsInsertConcurrentlySupported() const { return false; }
323 // Return true if the current MemTableRep supports detecting duplicate
324 // <key,seq> at insertion time. If true, then MemTableRep::Insert* returns
325 // false when if the <key,seq> already exists.
327 virtual bool CanHandleDuplicatedKey() const { return false; }
330 // This uses a skip list to store keys. It is the default.
333 // lookahead: If non-zero, each iterator's seek operation will start the
334 // search from the previously visited record (doing at most 'lookahead'
335 // steps). This is an optimization for the access pattern including many
336 // seeks with consecutive keys.
337 class SkipListFactory
: public MemTableRepFactory
{
339 explicit SkipListFactory(size_t lookahead
= 0);
341 // Methods for Configurable/Customizable class overrides
342 static const char* kClassName() { return "SkipListFactory"; }
343 static const char* kNickName() { return "skip_list"; }
344 virtual const char* Name() const override
{ return kClassName(); }
345 virtual const char* NickName() const override
{ return kNickName(); }
346 std::string
GetId() const override
;
348 // Methods for MemTableRepFactory class overrides
349 using MemTableRepFactory::CreateMemTableRep
;
350 virtual MemTableRep
* CreateMemTableRep(const MemTableRep::KeyComparator
&,
351 Allocator
*, const SliceTransform
*,
352 Logger
* logger
) override
;
354 bool IsInsertConcurrentlySupported() const override
{ return true; }
356 bool CanHandleDuplicatedKey() const override
{ return true; }
363 // This creates MemTableReps that are backed by an std::vector. On iteration,
364 // the vector is sorted. This is useful for workloads where iteration is very
365 // rare and writes are generally not issued after reads begin.
368 // count: Passed to the constructor of the underlying std::vector of each
369 // VectorRep. On initialization, the underlying array will be at least count
370 // bytes reserved for usage.
371 class VectorRepFactory
: public MemTableRepFactory
{
375 explicit VectorRepFactory(size_t count
= 0);
377 // Methods for Configurable/Customizable class overrides
378 static const char* kClassName() { return "VectorRepFactory"; }
379 static const char* kNickName() { return "vector"; }
380 const char* Name() const override
{ return kClassName(); }
381 const char* NickName() const override
{ return kNickName(); }
383 // Methods for MemTableRepFactory class overrides
384 using MemTableRepFactory::CreateMemTableRep
;
385 virtual MemTableRep
* CreateMemTableRep(const MemTableRep::KeyComparator
&,
386 Allocator
*, const SliceTransform
*,
387 Logger
* logger
) override
;
390 // This class contains a fixed array of buckets, each
391 // pointing to a skiplist (null if the bucket is empty).
392 // bucket_count: number of fixed array buckets
393 // skiplist_height: the max height of the skiplist
394 // skiplist_branching_factor: probabilistic size ratio between adjacent
395 // link lists in the skiplist
396 extern MemTableRepFactory
* NewHashSkipListRepFactory(
397 size_t bucket_count
= 1000000, int32_t skiplist_height
= 4,
398 int32_t skiplist_branching_factor
= 4);
400 // The factory is to create memtables based on a hash table:
401 // it contains a fixed array of buckets, each pointing to either a linked list
402 // or a skip list if number of entries inside the bucket exceeds
403 // threshold_use_skiplist.
404 // @bucket_count: number of fixed array buckets
405 // @huge_page_tlb_size: if <=0, allocate the hash table bytes from malloc.
406 // Otherwise from huge page TLB. The user needs to reserve
407 // huge pages for it to be allocated, like:
408 // sysctl -w vm.nr_hugepages=20
409 // See linux doc Documentation/vm/hugetlbpage.txt
410 // @bucket_entries_logging_threshold: if number of entries in one bucket
411 // exceeds this number, log about it.
412 // @if_log_bucket_dist_when_flash: if true, log distribution of number of
413 // entries when flushing.
414 // @threshold_use_skiplist: a bucket switches to skip list if number of
415 // entries exceed this parameter.
416 extern MemTableRepFactory
* NewHashLinkListRepFactory(
417 size_t bucket_count
= 50000, size_t huge_page_tlb_size
= 0,
418 int bucket_entries_logging_threshold
= 4096,
419 bool if_log_bucket_dist_when_flash
= true,
420 uint32_t threshold_use_skiplist
= 256);
422 #endif // ROCKSDB_LITE
423 } // namespace ROCKSDB_NAMESPACE