ceph/src/rocksdb/table/full_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 #pragma once
   7
   8 #include <stddef.h>
   9 #include <stdint.h>
  10 #include <memory>
  11 #include <string>
  12 #include <vector>
  13 #include "rocksdb/options.h"
  14 #include "rocksdb/slice.h"
  15 #include "rocksdb/slice_transform.h"
  16 #include "db/dbformat.h"
  17 #include "util/hash.h"
  18 #include "table/filter_block.h"
  19
  20 namespace rocksdb {
  21
  22 class FilterPolicy;
  23 class FilterBitsBuilder;
  24 class FilterBitsReader;
  25
  26 // A FullFilterBlockBuilder is used to construct a full filter for a
  27 // particular Table.  It generates a single string which is stored as
  28 // a special block in the Table.
  29 // The format of full filter block is:
  30 // +----------------------------------------------------------------+
  31 // |              full filter for all keys in sst file              |
  32 // +----------------------------------------------------------------+
  33 // The full filter can be very large. At the end of it, we put
  34 // num_probes: how many hash functions are used in bloom filter
  35 //
  36 class FullFilterBlockBuilder : public FilterBlockBuilder {
  37  public:
  38   explicit FullFilterBlockBuilder(const SliceTransform* prefix_extractor,
  39                                   bool whole_key_filtering,
  40                                   FilterBitsBuilder* filter_bits_builder);
  41   // bits_builder is created in filter_policy, it should be passed in here
  42   // directly. and be deleted here
  43   ~FullFilterBlockBuilder() {}
  44
  45   virtual bool IsBlockBased() override { return false; }
  46   virtual void StartBlock(uint64_t /*block_offset*/) override {}
  47   virtual void Add(const Slice& key) override;
  48   virtual size_t NumAdded() const override { return num_added_; }
  49   virtual Slice Finish(const BlockHandle& tmp, Status* status) override;
  50   using FilterBlockBuilder::Finish;
  51
  52  protected:
  53   virtual void AddKey(const Slice& key);
  54   std::unique_ptr<FilterBitsBuilder> filter_bits_builder_;
  55   virtual void Reset();
  56
  57  private:
  58   // important: all of these might point to invalid addresses
  59   // at the time of destruction of this filter block. destructor
  60   // should NOT dereference them.
  61   const SliceTransform* prefix_extractor_;
  62   bool whole_key_filtering_;
  63   bool last_whole_key_recorded_;
  64   std::string last_whole_key_str_;
  65   bool last_prefix_recorded_;
  66   std::string last_prefix_str_;
  67
  68   uint32_t num_added_;
  69   std::unique_ptr<const char[]> filter_data_;
  70
  71   void AddPrefix(const Slice& key);
  72
  73   // No copying allowed
  74   FullFilterBlockBuilder(const FullFilterBlockBuilder&);
  75   void operator=(const FullFilterBlockBuilder&);
  76 };
  77
  78 // A FilterBlockReader is used to parse filter from SST table.
  79 // KeyMayMatch and PrefixMayMatch would trigger filter checking
  80 class FullFilterBlockReader : public FilterBlockReader {
  81  public:
  82   // REQUIRES: "contents" and filter_bits_reader must stay live
  83   // while *this is live.
  84   explicit FullFilterBlockReader(const SliceTransform* prefix_extractor,
  85                                  bool whole_key_filtering,
  86                                  const Slice& contents,
  87                                  FilterBitsReader* filter_bits_reader,
  88                                  Statistics* statistics);
  89   explicit FullFilterBlockReader(const SliceTransform* prefix_extractor,
  90                                  bool whole_key_filtering,
  91                                  BlockContents&& contents,
  92                                  FilterBitsReader* filter_bits_reader,
  93                                  Statistics* statistics);
  94
  95   // bits_reader is created in filter_policy, it should be passed in here
  96   // directly. and be deleted here
  97   ~FullFilterBlockReader() {}
  98
  99   virtual bool IsBlockBased() override { return false; }
 100
 101   virtual bool KeyMayMatch(
 102       const Slice& key, const SliceTransform* prefix_extractor,
 103       uint64_t block_offset = kNotValid, const bool no_io = false,
 104       const Slice* const const_ikey_ptr = nullptr) override;
 105
 106   virtual bool PrefixMayMatch(
 107       const Slice& prefix, const SliceTransform* prefix_extractor,
 108       uint64_t block_offset = kNotValid, const bool no_io = false,
 109       const Slice* const const_ikey_ptr = nullptr) override;
 110   virtual size_t ApproximateMemoryUsage() const override;
 111   virtual bool RangeMayExist(const Slice* iterate_upper_bound, const Slice& user_key,
 112                              const SliceTransform* prefix_extractor,
 113                              const Comparator* comparator,
 114                              const Slice* const const_ikey_ptr, bool* filter_checked,
 115                              bool need_upper_bound_check) override;
 116  private:
 117   const SliceTransform* prefix_extractor_;
 118   Slice contents_;
 119   std::unique_ptr<FilterBitsReader> filter_bits_reader_;
 120   BlockContents block_contents_;
 121   bool full_length_enabled_;
 122   size_t prefix_extractor_full_length_;
 123
 124   // No copying allowed
 125   FullFilterBlockReader(const FullFilterBlockReader&);
 126   bool MayMatch(const Slice& entry);
 127   void operator=(const FullFilterBlockReader&);
 128   bool IsFilterCompatible(const Slice* iterate_upper_bound,
 129                           const Slice& prefix, const Comparator* comparator);
 130
 131 };
 132
 133 }  // namespace rocksdb