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). 5 // 6 // Copyright (c) 2012 The LevelDB Authors. All rights reserved. 7 // Use of this source code is governed by a BSD-style license that can be 8 // found in the LICENSE file. See the AUTHORS file for names of contributors. 9 // 10 // A filter block is stored near the end of a Table file. It contains 11 // filters (e.g., bloom filters) for all data blocks in the table combined 12 // into a single filter block. 13 // 14 // It is a base class for BlockBasedFilter and FullFilter. 15 // These two are both used in BlockBasedTable. The first one contain filter 16 // For a part of keys in sst file, the second contain filter for all keys 17 // in sst file. 18 19 #pragma once 20 21 #include <stddef.h> 22 #include <stdint.h> 23 #include <memory> 24 #include <string> 25 #include <vector> 26 #include "db/dbformat.h" 27 #include "rocksdb/options.h" 28 #include "rocksdb/slice.h" 29 #include "rocksdb/slice_transform.h" 30 #include "rocksdb/table.h" 31 #include "table/format.h" 32 #include "table/multiget_context.h" 33 #include "trace_replay/block_cache_tracer.h" 34 #include "util/hash.h" 35 36 namespace ROCKSDB_NAMESPACE { 37 38 const uint64_t kNotValid = ULLONG_MAX; 39 class FilterPolicy; 40 41 class GetContext; 42 using MultiGetRange = MultiGetContext::Range; 43 44 // A FilterBlockBuilder is used to construct all of the filters for a 45 // particular Table. It generates a single string which is stored as 46 // a special block in the Table. 47 // 48 // The sequence of calls to FilterBlockBuilder must match the regexp: 49 // (StartBlock Add*)* Finish 50 // 51 // BlockBased/Full FilterBlock would be called in the same way. 52 class FilterBlockBuilder { 53 public: FilterBlockBuilder()54 explicit FilterBlockBuilder() {} 55 // No copying allowed 56 FilterBlockBuilder(const FilterBlockBuilder&) = delete; 57 void operator=(const FilterBlockBuilder&) = delete; 58 ~FilterBlockBuilder()59 virtual ~FilterBlockBuilder() {} 60 61 virtual bool IsBlockBased() = 0; // If is blockbased filter 62 virtual void StartBlock(uint64_t block_offset) = 0; // Start new block filter 63 virtual void Add(const Slice& key) = 0; // Add a key to current filter 64 virtual size_t NumAdded() const = 0; // Number of keys added Finish()65 Slice Finish() { // Generate Filter 66 const BlockHandle empty_handle; 67 Status dont_care_status; 68 auto ret = Finish(empty_handle, &dont_care_status); 69 assert(dont_care_status.ok()); 70 return ret; 71 } 72 virtual Slice Finish(const BlockHandle& tmp, Status* status) = 0; 73 }; 74 75 // A FilterBlockReader is used to parse filter from SST table. 76 // KeyMayMatch and PrefixMayMatch would trigger filter checking 77 // 78 // BlockBased/Full FilterBlock would be called in the same way. 79 class FilterBlockReader { 80 public: 81 FilterBlockReader() = default; 82 virtual ~FilterBlockReader() = default; 83 84 FilterBlockReader(const FilterBlockReader&) = delete; 85 FilterBlockReader& operator=(const FilterBlockReader&) = delete; 86 87 virtual bool IsBlockBased() = 0; // If is blockbased filter 88 89 /** 90 * If no_io is set, then it returns true if it cannot answer the query without 91 * reading data from disk. This is used in PartitionedFilterBlockReader to 92 * avoid reading partitions that are not in block cache already 93 * 94 * Normally filters are built on only the user keys and the InternalKey is not 95 * needed for a query. The index in PartitionedFilterBlockReader however is 96 * built upon InternalKey and must be provided via const_ikey_ptr when running 97 * queries. 98 */ 99 virtual bool KeyMayMatch(const Slice& key, 100 const SliceTransform* prefix_extractor, 101 uint64_t block_offset, const bool no_io, 102 const Slice* const const_ikey_ptr, 103 GetContext* get_context, 104 BlockCacheLookupContext* lookup_context) = 0; 105 KeysMayMatch(MultiGetRange * range,const SliceTransform * prefix_extractor,uint64_t block_offset,const bool no_io,BlockCacheLookupContext * lookup_context)106 virtual void KeysMayMatch(MultiGetRange* range, 107 const SliceTransform* prefix_extractor, 108 uint64_t block_offset, const bool no_io, 109 BlockCacheLookupContext* lookup_context) { 110 for (auto iter = range->begin(); iter != range->end(); ++iter) { 111 const Slice ukey = iter->ukey; 112 const Slice ikey = iter->ikey; 113 GetContext* const get_context = iter->get_context; 114 if (!KeyMayMatch(ukey, prefix_extractor, block_offset, no_io, &ikey, 115 get_context, lookup_context)) { 116 range->SkipKey(iter); 117 } 118 } 119 } 120 121 /** 122 * no_io and const_ikey_ptr here means the same as in KeyMayMatch 123 */ 124 virtual bool PrefixMayMatch(const Slice& prefix, 125 const SliceTransform* prefix_extractor, 126 uint64_t block_offset, const bool no_io, 127 const Slice* const const_ikey_ptr, 128 GetContext* get_context, 129 BlockCacheLookupContext* lookup_context) = 0; 130 PrefixesMayMatch(MultiGetRange * range,const SliceTransform * prefix_extractor,uint64_t block_offset,const bool no_io,BlockCacheLookupContext * lookup_context)131 virtual void PrefixesMayMatch(MultiGetRange* range, 132 const SliceTransform* prefix_extractor, 133 uint64_t block_offset, const bool no_io, 134 BlockCacheLookupContext* lookup_context) { 135 for (auto iter = range->begin(); iter != range->end(); ++iter) { 136 const Slice ukey = iter->ukey; 137 const Slice ikey = iter->ikey; 138 GetContext* const get_context = iter->get_context; 139 if (prefix_extractor->InDomain(ukey) && 140 !PrefixMayMatch(prefix_extractor->Transform(ukey), prefix_extractor, 141 block_offset, no_io, &ikey, get_context, 142 lookup_context)) { 143 range->SkipKey(iter); 144 } 145 } 146 } 147 148 virtual size_t ApproximateMemoryUsage() const = 0; 149 150 // convert this object to a human readable form ToString()151 virtual std::string ToString() const { 152 std::string error_msg("Unsupported filter \n"); 153 return error_msg; 154 } 155 CacheDependencies(bool)156 virtual void CacheDependencies(bool /*pin*/) {} 157 RangeMayExist(const Slice *,const Slice & user_key,const SliceTransform * prefix_extractor,const Comparator *,const Slice * const const_ikey_ptr,bool * filter_checked,bool need_upper_bound_check,BlockCacheLookupContext * lookup_context)158 virtual bool RangeMayExist(const Slice* /*iterate_upper_bound*/, 159 const Slice& user_key, 160 const SliceTransform* prefix_extractor, 161 const Comparator* /*comparator*/, 162 const Slice* const const_ikey_ptr, 163 bool* filter_checked, bool need_upper_bound_check, 164 BlockCacheLookupContext* lookup_context) { 165 if (need_upper_bound_check) { 166 return true; 167 } 168 *filter_checked = true; 169 Slice prefix = prefix_extractor->Transform(user_key); 170 return PrefixMayMatch(prefix, prefix_extractor, kNotValid, false, 171 const_ikey_ptr, /* get_context */ nullptr, 172 lookup_context); 173 } 174 }; 175 176 } // namespace ROCKSDB_NAMESPACE 177