ceph/src/rocksdb/table/full_filter_block.cc

   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 #include "table/full_filter_block.h"
   7
   8 #ifdef ROCKSDB_MALLOC_USABLE_SIZE
   9 #ifdef OS_FREEBSD
  10 #include <malloc_np.h>
  11 #else
  12 #include <malloc.h>
  13 #endif
  14 #endif
  15
  16 #include "monitoring/perf_context_imp.h"
  17 #include "port/port.h"
  18 #include "rocksdb/filter_policy.h"
  19 #include "util/coding.h"
  20
  21 namespace rocksdb {
  22
  23 FullFilterBlockBuilder::FullFilterBlockBuilder(
  24     const SliceTransform* prefix_extractor, bool whole_key_filtering,
  25     FilterBitsBuilder* filter_bits_builder)
  26     : prefix_extractor_(prefix_extractor),
  27       whole_key_filtering_(whole_key_filtering),
  28       last_whole_key_recorded_(false),
  29       last_prefix_recorded_(false),
  30       num_added_(0) {
  31   assert(filter_bits_builder != nullptr);
  32   filter_bits_builder_.reset(filter_bits_builder);
  33 }
  34
  35 void FullFilterBlockBuilder::Add(const Slice& key) {
  36   const bool add_prefix = prefix_extractor_ && prefix_extractor_->InDomain(key);
  37   if (whole_key_filtering_) {
  38     if (!add_prefix) {
  39       AddKey(key);
  40     } else {
  41       // if both whole_key and prefix are added to bloom then we will have whole
  42       // key and prefix addition being interleaved and thus cannot rely on the
  43       // bits builder to properly detect the duplicates by comparing with the
  44       // last item.
  45       Slice last_whole_key = Slice(last_whole_key_str_);
  46       if (!last_whole_key_recorded_ || last_whole_key.compare(key) != 0) {
  47         AddKey(key);
  48         last_whole_key_recorded_ = true;
  49         last_whole_key_str_.assign(key.data(), key.size());
  50       }
  51     }
  52   }
  53   if (add_prefix) {
  54     AddPrefix(key);
  55   }
  56 }
  57
  58 // Add key to filter if needed
  59 inline void FullFilterBlockBuilder::AddKey(const Slice& key) {
  60   filter_bits_builder_->AddKey(key);
  61   num_added_++;
  62 }
  63
  64 // Add prefix to filter if needed
  65 inline void FullFilterBlockBuilder::AddPrefix(const Slice& key) {
  66   Slice prefix = prefix_extractor_->Transform(key);
  67   if (whole_key_filtering_) {
  68     // if both whole_key and prefix are added to bloom then we will have whole
  69     // key and prefix addition being interleaved and thus cannot rely on the
  70     // bits builder to properly detect the duplicates by comparing with the last
  71     // item.
  72     Slice last_prefix = Slice(last_prefix_str_);
  73     if (!last_prefix_recorded_ || last_prefix.compare(prefix) != 0) {
  74       AddKey(prefix);
  75       last_prefix_recorded_ = true;
  76       last_prefix_str_.assign(prefix.data(), prefix.size());
  77     }
  78   } else {
  79     AddKey(prefix);
  80   }
  81 }
  82
  83 void FullFilterBlockBuilder::Reset() {
  84   last_whole_key_recorded_ = false;
  85   last_prefix_recorded_ = false;
  86 }
  87
  88 Slice FullFilterBlockBuilder::Finish(const BlockHandle& /*tmp*/,
  89                                      Status* status) {
  90   Reset();
  91   // In this impl we ignore BlockHandle
  92   *status = Status::OK();
  93   if (num_added_ != 0) {
  94     num_added_ = 0;
  95     return filter_bits_builder_->Finish(&filter_data_);
  96   }
  97   return Slice();
  98 }
  99
 100 FullFilterBlockReader::FullFilterBlockReader(
 101     const SliceTransform* prefix_extractor, bool _whole_key_filtering,
 102     const Slice& contents, FilterBitsReader* filter_bits_reader,
 103     Statistics* stats)
 104     : FilterBlockReader(contents.size(), stats, _whole_key_filtering),
 105       prefix_extractor_(prefix_extractor),
 106       contents_(contents) {
 107   assert(filter_bits_reader != nullptr);
 108   filter_bits_reader_.reset(filter_bits_reader);
 109   if (prefix_extractor_ != nullptr) {
 110     full_length_enabled_ =
 111         prefix_extractor_->FullLengthEnabled(&prefix_extractor_full_length_);
 112   }
 113 }
 114
 115 FullFilterBlockReader::FullFilterBlockReader(
 116     const SliceTransform* prefix_extractor, bool _whole_key_filtering,
 117     BlockContents&& contents, FilterBitsReader* filter_bits_reader,
 118     Statistics* stats)
 119     : FullFilterBlockReader(prefix_extractor, _whole_key_filtering,
 120                             contents.data, filter_bits_reader, stats) {
 121   block_contents_ = std::move(contents);
 122 }
 123
 124 bool FullFilterBlockReader::KeyMayMatch(
 125     const Slice& key, const SliceTransform* /*prefix_extractor*/,
 126     uint64_t block_offset, const bool /*no_io*/,
 127     const Slice* const /*const_ikey_ptr*/) {
 128 #ifdef NDEBUG
 129   (void)block_offset;
 130 #endif
 131   assert(block_offset == kNotValid);
 132   if (!whole_key_filtering_) {
 133     return true;
 134   }
 135   return MayMatch(key);
 136 }
 137
 138 bool FullFilterBlockReader::PrefixMayMatch(
 139     const Slice& prefix, const SliceTransform* /* prefix_extractor */,
 140     uint64_t block_offset, const bool /*no_io*/,
 141     const Slice* const /*const_ikey_ptr*/) {
 142 #ifdef NDEBUG
 143   (void)block_offset;
 144 #endif
 145   assert(block_offset == kNotValid);
 146   return MayMatch(prefix);
 147 }
 148
 149 bool FullFilterBlockReader::MayMatch(const Slice& entry) {
 150   if (contents_.size() != 0)  {
 151     if (filter_bits_reader_->MayMatch(entry)) {
 152       PERF_COUNTER_ADD(bloom_sst_hit_count, 1);
 153       return true;
 154     } else {
 155       PERF_COUNTER_ADD(bloom_sst_miss_count, 1);
 156       return false;
 157     }
 158   }
 159   return true;  // remain the same with block_based filter
 160 }
 161
 162 size_t FullFilterBlockReader::ApproximateMemoryUsage() const {
 163   size_t usage = block_contents_.usable_size();
 164 #ifdef ROCKSDB_MALLOC_USABLE_SIZE
 165   usage += malloc_usable_size((void*)this);
 166   usage += malloc_usable_size(filter_bits_reader_.get());
 167 #else
 168   usage += sizeof(*this);
 169   usage += sizeof(*filter_bits_reader_.get());
 170 #endif  // ROCKSDB_MALLOC_USABLE_SIZE
 171   return usage;
 172 }
 173
 174 bool FullFilterBlockReader::RangeMayExist(const Slice* iterate_upper_bound,
 175     const Slice& user_key, const SliceTransform* prefix_extractor,
 176     const Comparator* comparator, const Slice* const const_ikey_ptr,
 177     bool* filter_checked, bool need_upper_bound_check) {
 178   if (!prefix_extractor || !prefix_extractor->InDomain(user_key)) {
 179     *filter_checked = false;
 180     return true;
 181   }
 182   Slice prefix = prefix_extractor->Transform(user_key);
 183   if (need_upper_bound_check &&
 184       !IsFilterCompatible(iterate_upper_bound, prefix, comparator)) {
 185     *filter_checked = false;
 186     return true;
 187   } else {
 188     *filter_checked = true;
 189     return PrefixMayMatch(prefix, prefix_extractor, kNotValid, false,
 190                           const_ikey_ptr);
 191   }
 192 }
 193
 194 bool FullFilterBlockReader::IsFilterCompatible(
 195     const Slice* iterate_upper_bound, const Slice& prefix,
 196     const Comparator* comparator) {
 197   // Try to reuse the bloom filter in the SST table if prefix_extractor in
 198   // mutable_cf_options has changed. If range [user_key, upper_bound) all
 199   // share the same prefix then we may still be able to use the bloom filter.
 200   if (iterate_upper_bound != nullptr && prefix_extractor_) {
 201     if (!prefix_extractor_->InDomain(*iterate_upper_bound)) {
 202       return false;
 203     }
 204     Slice upper_bound_xform =
 205         prefix_extractor_->Transform(*iterate_upper_bound);
 206     // first check if user_key and upper_bound all share the same prefix
 207     if (!comparator->Equal(prefix, upper_bound_xform)) {
 208       // second check if user_key's prefix is the immediate predecessor of
 209       // upper_bound and have the same length. If so, we know for sure all
 210       // keys in the range [user_key, upper_bound) share the same prefix.
 211       // Also need to make sure upper_bound are full length to ensure
 212       // correctness
 213       if (!full_length_enabled_ ||
 214           iterate_upper_bound->size() != prefix_extractor_full_length_ ||
 215           !comparator->IsSameLengthImmediateSuccessor(prefix,
 216                                                       *iterate_upper_bound)) {
 217         return false;
 218       }
 219     }
 220     return true;
 221   } else {
 222     return false;
 223   }
 224 }
 225
 226 }  // namespace rocksdb