ceph/src/rocksdb/table/block_based/filter_block.h

   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 #pragma once
  15
  16 #include <stddef.h>
  17 #include <stdint.h>
  18
  19 #include <memory>
  20 #include <string>
  21 #include <vector>
  22
  23 #include "rocksdb/options.h"
  24 #include "rocksdb/slice.h"
  25 #include "rocksdb/slice_transform.h"
  26 #include "rocksdb/table.h"
  27 #include "table/format.h"
  28 #include "table/multiget_context.h"
  29 #include "trace_replay/block_cache_tracer.h"
  30 #include "util/hash.h"
  31
  32 namespace ROCKSDB_NAMESPACE {
  33
  34 const uint64_t kNotValid = ULLONG_MAX;
  35 class FilterPolicy;
  36
  37 class GetContext;
  38 using MultiGetRange = MultiGetContext::Range;
  39
  40 // A FilterBlockBuilder is used to construct all of the filters for a
  41 // particular Table.  It generates a single string which is stored as
  42 // a special block in the Table, or partitioned into smaller filters.
  43 //
  44 // The sequence of calls to FilterBlockBuilder must match the regexp:
  45 //      Add* Finish
  46 class FilterBlockBuilder {
  47  public:
  48   explicit FilterBlockBuilder() {}
  49   // No copying allowed
  50   FilterBlockBuilder(const FilterBlockBuilder&) = delete;
  51   void operator=(const FilterBlockBuilder&) = delete;
  52
  53   virtual ~FilterBlockBuilder() {}
  54
  55   virtual void Add(
  56       const Slice& key_without_ts) = 0;  // Add a key to current filter
  57   virtual bool IsEmpty() const = 0;      // Empty == none added
  58   // For reporting stats on how many entries the builder considered unique
  59   virtual size_t EstimateEntriesAdded() = 0;
  60   Slice Finish() {  // Generate Filter
  61     const BlockHandle empty_handle;
  62     Status dont_care_status;
  63     auto ret = Finish(empty_handle, &dont_care_status);
  64     assert(dont_care_status.ok());
  65     return ret;
  66   }
  67   // If filter_data is not nullptr, Finish() may transfer ownership of
  68   // underlying filter data to the caller,  so that it can be freed as soon as
  69   // possible. BlockBasedFilterBlock will ignore this parameter.
  70   //
  71   virtual Slice Finish(
  72       const BlockHandle& tmp /* only used in PartitionedFilterBlock as
  73                                 last_partition_block_handle */
  74       ,
  75       Status* status, std::unique_ptr<const char[]>* filter_data = nullptr) = 0;
  76
  77   // This is called when finishes using the FilterBitsBuilder
  78   // in order to release memory usage and cache charge
  79   // associated with it timely
  80   virtual void ResetFilterBitsBuilder() {}
  81
  82   // To optionally post-verify the filter returned from
  83   // FilterBlockBuilder::Finish.
  84   // Return Status::OK() if skipped.
  85   virtual Status MaybePostVerifyFilter(const Slice& /* filter_content */) {
  86     return Status::OK();
  87   }
  88 };
  89
  90 // A FilterBlockReader is used to parse filter from SST table.
  91 // KeyMayMatch and PrefixMayMatch would trigger filter checking
  92 //
  93 // BlockBased/Full FilterBlock would be called in the same way.
  94 class FilterBlockReader {
  95  public:
  96   FilterBlockReader() = default;
  97   virtual ~FilterBlockReader() = default;
  98
  99   FilterBlockReader(const FilterBlockReader&) = delete;
 100   FilterBlockReader& operator=(const FilterBlockReader&) = delete;
 101
 102   /**
 103    * If no_io is set, then it returns true if it cannot answer the query without
 104    * reading data from disk. This is used in PartitionedFilterBlockReader to
 105    * avoid reading partitions that are not in block cache already
 106    *
 107    * Normally filters are built on only the user keys and the InternalKey is not
 108    * needed for a query. The index in PartitionedFilterBlockReader however is
 109    * built upon InternalKey and must be provided via const_ikey_ptr when running
 110    * queries.
 111    */
 112   virtual bool KeyMayMatch(const Slice& key, const bool no_io,
 113                            const Slice* const const_ikey_ptr,
 114                            GetContext* get_context,
 115                            BlockCacheLookupContext* lookup_context,
 116                            Env::IOPriority rate_limiter_priority) = 0;
 117
 118   virtual void KeysMayMatch(MultiGetRange* range, const bool no_io,
 119                             BlockCacheLookupContext* lookup_context,
 120                             Env::IOPriority rate_limiter_priority) {
 121     for (auto iter = range->begin(); iter != range->end(); ++iter) {
 122       const Slice ukey_without_ts = iter->ukey_without_ts;
 123       const Slice ikey = iter->ikey;
 124       GetContext* const get_context = iter->get_context;
 125       if (!KeyMayMatch(ukey_without_ts, no_io, &ikey, get_context,
 126                        lookup_context, rate_limiter_priority)) {
 127         range->SkipKey(iter);
 128       }
 129     }
 130   }
 131
 132   /**
 133    * no_io and const_ikey_ptr here means the same as in KeyMayMatch
 134    */
 135   virtual bool PrefixMayMatch(const Slice& prefix, const bool no_io,
 136                               const Slice* const const_ikey_ptr,
 137                               GetContext* get_context,
 138                               BlockCacheLookupContext* lookup_context,
 139                               Env::IOPriority rate_limiter_priority) = 0;
 140
 141   virtual void PrefixesMayMatch(MultiGetRange* range,
 142                                 const SliceTransform* prefix_extractor,
 143                                 const bool no_io,
 144                                 BlockCacheLookupContext* lookup_context,
 145                                 Env::IOPriority rate_limiter_priority) {
 146     for (auto iter = range->begin(); iter != range->end(); ++iter) {
 147       const Slice ukey_without_ts = iter->ukey_without_ts;
 148       const Slice ikey = iter->ikey;
 149       GetContext* const get_context = iter->get_context;
 150       if (prefix_extractor->InDomain(ukey_without_ts) &&
 151           !PrefixMayMatch(prefix_extractor->Transform(ukey_without_ts), no_io,
 152                           &ikey, get_context, lookup_context,
 153                           rate_limiter_priority)) {
 154         range->SkipKey(iter);
 155       }
 156     }
 157   }
 158
 159   virtual size_t ApproximateMemoryUsage() const = 0;
 160
 161   // convert this object to a human readable form
 162   virtual std::string ToString() const {
 163     std::string error_msg("Unsupported filter \n");
 164     return error_msg;
 165   }
 166
 167   virtual Status CacheDependencies(const ReadOptions& /*ro*/, bool /*pin*/) {
 168     return Status::OK();
 169   }
 170
 171   virtual bool RangeMayExist(const Slice* /*iterate_upper_bound*/,
 172                              const Slice& user_key_without_ts,
 173                              const SliceTransform* prefix_extractor,
 174                              const Comparator* /*comparator*/,
 175                              const Slice* const const_ikey_ptr,
 176                              bool* filter_checked, bool need_upper_bound_check,
 177                              bool no_io,
 178                              BlockCacheLookupContext* lookup_context,
 179                              Env::IOPriority rate_limiter_priority) = 0;
 180 };
 181
 182 }  // namespace ROCKSDB_NAMESPACE