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 <list>
   9 #include <string>
  10 #include <unordered_map>
  11 #include "db/dbformat.h"
  12 #include "index_builder.h"
  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 "util/autovector.h"
  20
  21 namespace ROCKSDB_NAMESPACE {
  22
  23 class PartitionedFilterBlockBuilder : public FullFilterBlockBuilder {
  24  public:
  25   explicit PartitionedFilterBlockBuilder(
  26       const SliceTransform* prefix_extractor, bool whole_key_filtering,
  27       FilterBitsBuilder* filter_bits_builder, int index_block_restart_interval,
  28       const bool use_value_delta_encoding,
  29       PartitionedIndexBuilder* const p_index_builder,
  30       const uint32_t partition_size);
  31
  32   virtual ~PartitionedFilterBlockBuilder();
  33
  34   void AddKey(const Slice& key) override;
  35   void Add(const Slice& key) override;
  36
  37   virtual Slice Finish(const BlockHandle& last_partition_block_handle,
  38                        Status* status) override;
  39
  40  private:
  41   // Filter data
  42   BlockBuilder index_on_filter_block_builder_;  // top-level index builder
  43   BlockBuilder
  44       index_on_filter_block_builder_without_seq_;  // same for user keys
  45   struct FilterEntry {
  46     std::string key;
  47     Slice filter;
  48   };
  49   std::list<FilterEntry> filters;  // list of partitioned indexes and their keys
  50   std::unique_ptr<IndexBuilder> value;
  51   std::vector<std::unique_ptr<const char[]>> filter_gc;
  52   bool finishing_filters =
  53       false;  // true if Finish is called once but not complete yet.
  54   // The policy of when cut a filter block and Finish it
  55   void MaybeCutAFilterBlock(const Slice* next_key);
  56   // Currently we keep the same number of partitions for filters and indexes.
  57   // This would allow for some potentioal optimizations in future. If such
  58   // optimizations did not realize we can use different number of partitions and
  59   // eliminate p_index_builder_
  60   PartitionedIndexBuilder* const p_index_builder_;
  61   // The desired number of keys per partition
  62   uint32_t keys_per_partition_;
  63   // The number of keys added to the last partition so far
  64   uint32_t keys_added_to_partition_;
  65   BlockHandle last_encoded_handle_;
  66 };
  67
  68 class PartitionedFilterBlockReader : public FilterBlockReaderCommon<Block> {
  69  public:
  70   PartitionedFilterBlockReader(const BlockBasedTable* t,
  71                                CachableEntry<Block>&& filter_block);
  72
  73   static std::unique_ptr<FilterBlockReader> Create(
  74       const BlockBasedTable* table, const ReadOptions& ro,
  75       FilePrefetchBuffer* prefetch_buffer, bool use_cache, bool prefetch,
  76       bool pin, BlockCacheLookupContext* lookup_context);
  77
  78   bool IsBlockBased() override { return false; }
  79   bool KeyMayMatch(const Slice& key, const SliceTransform* prefix_extractor,
  80                    uint64_t block_offset, const bool no_io,
  81                    const Slice* const const_ikey_ptr, GetContext* get_context,
  82                    BlockCacheLookupContext* lookup_context) override;
  83   void KeysMayMatch(MultiGetRange* range,
  84                     const SliceTransform* prefix_extractor,
  85                     uint64_t block_offset, const bool no_io,
  86                     BlockCacheLookupContext* lookup_context) override;
  87
  88   bool PrefixMayMatch(const Slice& prefix,
  89                       const SliceTransform* prefix_extractor,
  90                       uint64_t block_offset, const bool no_io,
  91                       const Slice* const const_ikey_ptr,
  92                       GetContext* get_context,
  93                       BlockCacheLookupContext* lookup_context) override;
  94   void PrefixesMayMatch(MultiGetRange* range,
  95                         const SliceTransform* prefix_extractor,
  96                         uint64_t block_offset, const bool no_io,
  97                         BlockCacheLookupContext* lookup_context) override;
  98
  99   size_t ApproximateMemoryUsage() const override;
 100
 101  private:
 102   BlockHandle GetFilterPartitionHandle(const CachableEntry<Block>& filter_block,
 103                                        const Slice& entry) const;
 104   Status GetFilterPartitionBlock(
 105       FilePrefetchBuffer* prefetch_buffer, const BlockHandle& handle,
 106       bool no_io, GetContext* get_context,
 107       BlockCacheLookupContext* lookup_context,
 108       CachableEntry<ParsedFullFilterBlock>* filter_block) const;
 109
 110   using FilterFunction = bool (FullFilterBlockReader::*)(
 111       const Slice& slice, const SliceTransform* prefix_extractor,
 112       uint64_t block_offset, const bool no_io,
 113       const Slice* const const_ikey_ptr, GetContext* get_context,
 114       BlockCacheLookupContext* lookup_context);
 115   bool MayMatch(const Slice& slice, const SliceTransform* prefix_extractor,
 116                 uint64_t block_offset, bool no_io, const Slice* const_ikey_ptr,
 117                 GetContext* get_context,
 118                 BlockCacheLookupContext* lookup_context,
 119                 FilterFunction filter_function) const;
 120   using FilterManyFunction = void (FullFilterBlockReader::*)(
 121       MultiGetRange* range, const SliceTransform* prefix_extractor,
 122       uint64_t block_offset, const bool no_io,
 123       BlockCacheLookupContext* lookup_context);
 124   void MayMatch(MultiGetRange* range, const SliceTransform* prefix_extractor,
 125                 uint64_t block_offset, bool no_io,
 126                 BlockCacheLookupContext* lookup_context,
 127                 FilterManyFunction filter_function) const;
 128   void MayMatchPartition(MultiGetRange* range,
 129                          const SliceTransform* prefix_extractor,
 130                          uint64_t block_offset, BlockHandle filter_handle,
 131                          bool no_io, BlockCacheLookupContext* lookup_context,
 132                          FilterManyFunction filter_function) const;
 133   Status CacheDependencies(const ReadOptions& ro, bool pin) override;
 134
 135   const InternalKeyComparator* internal_comparator() const;
 136   bool index_key_includes_seq() const;
 137   bool index_value_is_full() const;
 138
 139  protected:
 140   std::unordered_map<uint64_t, CachableEntry<ParsedFullFilterBlock>>
 141       filter_map_;
 142 };
 143
 144 }  // namespace ROCKSDB_NAMESPACE