ceph/src/rocksdb/table/block_based/partitioned_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 <deque>
   9 #include <list>
  10 #include <string>
  11 #include <unordered_map>
  12
  13 #include "rocksdb/options.h"
  14 #include "rocksdb/slice.h"
  15 #include "rocksdb/slice_transform.h"
  16 #include "table/block_based/block.h"
  17 #include "table/block_based/filter_block_reader_common.h"
  18 #include "table/block_based/full_filter_block.h"
  19 #include "table/block_based/index_builder.h"
  20 #include "util/autovector.h"
  21 #include "util/hash_containers.h"
  22
  23 namespace ROCKSDB_NAMESPACE {
  24 class InternalKeyComparator;
  25
  26 class PartitionedFilterBlockBuilder : public FullFilterBlockBuilder {
  27  public:
  28   explicit PartitionedFilterBlockBuilder(
  29       const SliceTransform* prefix_extractor, bool whole_key_filtering,
  30       FilterBitsBuilder* filter_bits_builder, int index_block_restart_interval,
  31       const bool use_value_delta_encoding,
  32       PartitionedIndexBuilder* const p_index_builder,
  33       const uint32_t partition_size);
  34
  35   virtual ~PartitionedFilterBlockBuilder();
  36
  37   void AddKey(const Slice& key) override;
  38   void Add(const Slice& key) override;
  39   size_t EstimateEntriesAdded() override;
  40
  41   virtual Slice Finish(
  42       const BlockHandle& last_partition_block_handle, Status* status,
  43       std::unique_ptr<const char[]>* filter_data = nullptr) override;
  44
  45   virtual void ResetFilterBitsBuilder() override {
  46     // Previously constructed partitioned filters by
  47     // this to-be-reset FiterBitsBuilder can also be
  48     // cleared
  49     filters.clear();
  50     FullFilterBlockBuilder::ResetFilterBitsBuilder();
  51   }
  52
  53   // For PartitionFilter, optional post-verifing the filter is done
  54   // as part of PartitionFilterBlockBuilder::Finish
  55   // to avoid implementation complexity of doing it elsewhere.
  56   // Therefore we are skipping it in here.
  57   virtual Status MaybePostVerifyFilter(
  58       const Slice& /* filter_content */) override {
  59     return Status::OK();
  60   }
  61
  62  private:
  63   // Filter data
  64   BlockBuilder index_on_filter_block_builder_;  // top-level index builder
  65   BlockBuilder
  66       index_on_filter_block_builder_without_seq_;  // same for user keys
  67   struct FilterEntry {
  68     std::string key;
  69     std::unique_ptr<const char[]> filter_data;
  70     Slice filter;
  71   };
  72   std::deque<FilterEntry> filters;  // list of partitioned filters and keys used
  73                                     // in building the index
  74
  75   // Set to the first non-okay status if any of the filter
  76   // partitions experiences construction error.
  77   // If partitioned_filters_construction_status_ is non-okay,
  78   // then the whole partitioned filters should not be used.
  79   Status partitioned_filters_construction_status_;
  80   std::string last_filter_entry_key;
  81   std::unique_ptr<const char[]> last_filter_data;
  82   std::unique_ptr<IndexBuilder> value;
  83   bool finishing_filters =
  84       false;  // true if Finish is called once but not complete yet.
  85   // The policy of when cut a filter block and Finish it
  86   void MaybeCutAFilterBlock(const Slice* next_key);
  87   // Currently we keep the same number of partitions for filters and indexes.
  88   // This would allow for some potentioal optimizations in future. If such
  89   // optimizations did not realize we can use different number of partitions and
  90   // eliminate p_index_builder_
  91   PartitionedIndexBuilder* const p_index_builder_;
  92   // The desired number of keys per partition
  93   uint32_t keys_per_partition_;
  94   // The number of keys added to the last partition so far
  95   uint32_t keys_added_to_partition_;
  96   // According to the bits builders, how many keys/prefixes added
  97   // in all the filters we have fully built
  98   uint64_t total_added_in_built_;
  99   BlockHandle last_encoded_handle_;
 100 };
 101
 102 class PartitionedFilterBlockReader : public FilterBlockReaderCommon<Block> {
 103  public:
 104   PartitionedFilterBlockReader(const BlockBasedTable* t,
 105                                CachableEntry<Block>&& filter_block);
 106
 107   static std::unique_ptr<FilterBlockReader> Create(
 108       const BlockBasedTable* table, const ReadOptions& ro,
 109       FilePrefetchBuffer* prefetch_buffer, bool use_cache, bool prefetch,
 110       bool pin, BlockCacheLookupContext* lookup_context);
 111
 112   bool KeyMayMatch(const Slice& key, const bool no_io,
 113                    const Slice* const const_ikey_ptr, GetContext* get_context,
 114                    BlockCacheLookupContext* lookup_context,
 115                    Env::IOPriority rate_limiter_priority) override;
 116   void KeysMayMatch(MultiGetRange* range, const bool no_io,
 117                     BlockCacheLookupContext* lookup_context,
 118                     Env::IOPriority rate_limiter_priority) override;
 119
 120   bool PrefixMayMatch(const Slice& prefix, const bool no_io,
 121                       const Slice* const const_ikey_ptr,
 122                       GetContext* get_context,
 123                       BlockCacheLookupContext* lookup_context,
 124                       Env::IOPriority rate_limiter_priority) override;
 125   void PrefixesMayMatch(MultiGetRange* range,
 126                         const SliceTransform* prefix_extractor,
 127                         const bool no_io,
 128                         BlockCacheLookupContext* lookup_context,
 129                         Env::IOPriority rate_limiter_priority) override;
 130
 131   size_t ApproximateMemoryUsage() const override;
 132
 133  private:
 134   BlockHandle GetFilterPartitionHandle(const CachableEntry<Block>& filter_block,
 135                                        const Slice& entry) const;
 136   Status GetFilterPartitionBlock(
 137       FilePrefetchBuffer* prefetch_buffer, const BlockHandle& handle,
 138       bool no_io, GetContext* get_context,
 139       BlockCacheLookupContext* lookup_context,
 140       Env::IOPriority rate_limiter_priority,
 141       CachableEntry<ParsedFullFilterBlock>* filter_block) const;
 142
 143   using FilterFunction = bool (FullFilterBlockReader::*)(
 144       const Slice& slice, const bool no_io, const Slice* const const_ikey_ptr,
 145       GetContext* get_context, BlockCacheLookupContext* lookup_context,
 146       Env::IOPriority rate_limiter_priority);
 147   bool MayMatch(const Slice& slice, bool no_io, const Slice* const_ikey_ptr,
 148                 GetContext* get_context,
 149                 BlockCacheLookupContext* lookup_context,
 150                 Env::IOPriority rate_limiter_priority,
 151                 FilterFunction filter_function) const;
 152   using FilterManyFunction = void (FullFilterBlockReader::*)(
 153       MultiGetRange* range, const SliceTransform* prefix_extractor,
 154       const bool no_io, BlockCacheLookupContext* lookup_context,
 155       Env::IOPriority rate_limiter_priority);
 156   void MayMatch(MultiGetRange* range, const SliceTransform* prefix_extractor,
 157                 bool no_io, BlockCacheLookupContext* lookup_context,
 158                 Env::IOPriority rate_limiter_priority,
 159                 FilterManyFunction filter_function) const;
 160   void MayMatchPartition(MultiGetRange* range,
 161                          const SliceTransform* prefix_extractor,
 162                          BlockHandle filter_handle, bool no_io,
 163                          BlockCacheLookupContext* lookup_context,
 164                          Env::IOPriority rate_limiter_priority,
 165                          FilterManyFunction filter_function) const;
 166   Status CacheDependencies(const ReadOptions& ro, bool pin) override;
 167
 168   const InternalKeyComparator* internal_comparator() const;
 169   bool index_key_includes_seq() const;
 170   bool index_value_is_full() const;
 171
 172  protected:
 173   // For partition blocks pinned in cache. Can be a subset of blocks
 174   // in case some fail insertion on attempt to pin.
 175   UnorderedMap<uint64_t, CachableEntry<ParsedFullFilterBlock>> filter_map_;
 176 };
 177
 178 }  // namespace ROCKSDB_NAMESPACE