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 #include <string>
  19 #include <memory>
  20 #include <vector>
  21 #include "rocksdb/options.h"
  22 #include "rocksdb/slice.h"
  23 #include "rocksdb/slice_transform.h"
  24 #include "table/filter_block.h"
  25 #include "util/hash.h"
  26
  27 namespace rocksdb {
  28
  29
  30 // A BlockBasedFilterBlockBuilder is used to construct all of the filters for a
  31 // particular Table.  It generates a single string which is stored as
  32 // a special block in the Table.
  33 //
  34 // The sequence of calls to BlockBasedFilterBlockBuilder must match the regexp:
  35 //      (StartBlock Add*)* Finish
  36 class BlockBasedFilterBlockBuilder : public FilterBlockBuilder {
  37  public:
  38   BlockBasedFilterBlockBuilder(const SliceTransform* prefix_extractor,
  39       const BlockBasedTableOptions& table_opt);
  40
  41   virtual bool IsBlockBased() override { return true; }
  42   virtual void StartBlock(uint64_t block_offset) override;
  43   virtual void Add(const Slice& key) override;
  44   virtual size_t NumAdded() const override { return num_added_; }
  45   virtual Slice Finish(const BlockHandle& tmp, Status* status) override;
  46   using FilterBlockBuilder::Finish;
  47
  48  private:
  49   void AddKey(const Slice& key);
  50   void AddPrefix(const Slice& key);
  51   void GenerateFilter();
  52
  53   // important: all of these might point to invalid addresses
  54   // at the time of destruction of this filter block. destructor
  55   // should NOT dereference them.
  56   const FilterPolicy* policy_;
  57   const SliceTransform* prefix_extractor_;
  58   bool whole_key_filtering_;
  59
  60   size_t prev_prefix_start_;        // the position of the last appended prefix
  61                                     // to "entries_".
  62   size_t prev_prefix_size_;         // the length of the last appended prefix to
  63                                     // "entries_".
  64   std::string entries_;             // Flattened entry contents
  65   std::vector<size_t> start_;       // Starting index in entries_ of each entry
  66   std::string result_;              // Filter data computed so far
  67   std::vector<Slice> tmp_entries_;  // policy_->CreateFilter() argument
  68   std::vector<uint32_t> filter_offsets_;
  69   size_t num_added_;                // Number of keys added
  70
  71   // No copying allowed
  72   BlockBasedFilterBlockBuilder(const BlockBasedFilterBlockBuilder&);
  73   void operator=(const BlockBasedFilterBlockBuilder&);
  74 };
  75
  76 // A FilterBlockReader is used to parse filter from SST table.
  77 // KeyMayMatch and PrefixMayMatch would trigger filter checking
  78 class BlockBasedFilterBlockReader : public FilterBlockReader {
  79  public:
  80   // REQUIRES: "contents" and *policy must stay live while *this is live.
  81   BlockBasedFilterBlockReader(const SliceTransform* prefix_extractor,
  82                               const BlockBasedTableOptions& table_opt,
  83                               bool whole_key_filtering,
  84                               BlockContents&& contents, Statistics* statistics);
  85   virtual bool IsBlockBased() override { return true; }
  86
  87   virtual bool KeyMayMatch(
  88       const Slice& key, const SliceTransform* prefix_extractor,
  89       uint64_t block_offset = kNotValid, const bool no_io = false,
  90       const Slice* const const_ikey_ptr = nullptr) override;
  91   virtual bool PrefixMayMatch(
  92       const Slice& prefix, const SliceTransform* prefix_extractor,
  93       uint64_t block_offset = kNotValid, const bool no_io = false,
  94       const Slice* const const_ikey_ptr = nullptr) override;
  95   virtual size_t ApproximateMemoryUsage() const override;
  96
  97   // convert this object to a human readable form
  98   std::string ToString() const override;
  99
 100  private:
 101   const FilterPolicy* policy_;
 102   const SliceTransform* prefix_extractor_;
 103   const char* data_;    // Pointer to filter data (at block-start)
 104   const char* offset_;  // Pointer to beginning of offset array (at block-end)
 105   size_t num_;          // Number of entries in offset array
 106   size_t base_lg_;      // Encoding parameter (see kFilterBaseLg in .cc file)
 107   BlockContents contents_;
 108
 109   bool MayMatch(const Slice& entry, uint64_t block_offset);
 110
 111   // No copying allowed
 112   BlockBasedFilterBlockReader(const BlockBasedFilterBlockReader&);
 113   void operator=(const BlockBasedFilterBlockReader&);
 114 };
 115 }  // namespace rocksdb