ceph/src/rocksdb/utilities/simulator_cache/cache_simulator.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 "utilities/simulator_cache/cache_simulator.h"
   7
   8 #include <algorithm>
   9
  10 #include "db/dbformat.h"
  11 #include "rocksdb/trace_record.h"
  12
  13 namespace ROCKSDB_NAMESPACE {
  14
  15 namespace {
  16 const std::string kGhostCachePrefix = "ghost_";
  17 }  // namespace
  18
  19 GhostCache::GhostCache(std::shared_ptr<Cache> sim_cache)
  20     : sim_cache_(sim_cache) {}
  21
  22 bool GhostCache::Admit(const Slice& lookup_key) {
  23   auto handle = sim_cache_->Lookup(lookup_key);
  24   if (handle != nullptr) {
  25     sim_cache_->Release(handle);
  26     return true;
  27   }
  28   // TODO: Should we check for errors here?
  29   auto s = sim_cache_->Insert(lookup_key, /*value=*/nullptr, lookup_key.size(),
  30                               /*deleter=*/nullptr);
  31   s.PermitUncheckedError();
  32   return false;
  33 }
  34
  35 CacheSimulator::CacheSimulator(std::unique_ptr<GhostCache>&& ghost_cache,
  36                                std::shared_ptr<Cache> sim_cache)
  37     : ghost_cache_(std::move(ghost_cache)), sim_cache_(sim_cache) {}
  38
  39 void CacheSimulator::Access(const BlockCacheTraceRecord& access) {
  40   bool admit = true;
  41   const bool is_user_access =
  42       BlockCacheTraceHelper::IsUserAccess(access.caller);
  43   bool is_cache_miss = true;
  44   if (ghost_cache_ && !access.no_insert) {
  45     admit = ghost_cache_->Admit(access.block_key);
  46   }
  47   auto handle = sim_cache_->Lookup(access.block_key);
  48   if (handle != nullptr) {
  49     sim_cache_->Release(handle);
  50     is_cache_miss = false;
  51   } else {
  52     if (!access.no_insert && admit && access.block_size > 0) {
  53       // Ignore errors on insert
  54       auto s = sim_cache_->Insert(access.block_key, /*value=*/nullptr,
  55                                   access.block_size,
  56                                   /*deleter=*/nullptr);
  57       s.PermitUncheckedError();
  58     }
  59   }
  60   miss_ratio_stats_.UpdateMetrics(access.access_timestamp, is_user_access,
  61                                   is_cache_miss);
  62 }
  63
  64 void MissRatioStats::UpdateMetrics(uint64_t timestamp_in_ms,
  65                                    bool is_user_access, bool is_cache_miss) {
  66   uint64_t timestamp_in_seconds = timestamp_in_ms / kMicrosInSecond;
  67   num_accesses_timeline_[timestamp_in_seconds] += 1;
  68   num_accesses_ += 1;
  69   if (num_misses_timeline_.find(timestamp_in_seconds) ==
  70       num_misses_timeline_.end()) {
  71     num_misses_timeline_[timestamp_in_seconds] = 0;
  72   }
  73   if (is_cache_miss) {
  74     num_misses_ += 1;
  75     num_misses_timeline_[timestamp_in_seconds] += 1;
  76   }
  77   if (is_user_access) {
  78     user_accesses_ += 1;
  79     if (is_cache_miss) {
  80       user_misses_ += 1;
  81     }
  82   }
  83 }
  84
  85 Cache::Priority PrioritizedCacheSimulator::ComputeBlockPriority(
  86     const BlockCacheTraceRecord& access) const {
  87   if (access.block_type == TraceType::kBlockTraceFilterBlock ||
  88       access.block_type == TraceType::kBlockTraceIndexBlock ||
  89       access.block_type == TraceType::kBlockTraceUncompressionDictBlock) {
  90     return Cache::Priority::HIGH;
  91   }
  92   return Cache::Priority::LOW;
  93 }
  94
  95 void PrioritizedCacheSimulator::AccessKVPair(
  96     const Slice& key, uint64_t value_size, Cache::Priority priority,
  97     const BlockCacheTraceRecord& access, bool no_insert, bool is_user_access,
  98     bool* is_cache_miss, bool* admitted, bool update_metrics) {
  99   assert(is_cache_miss);
 100   assert(admitted);
 101   *is_cache_miss = true;
 102   *admitted = true;
 103   if (ghost_cache_ && !no_insert) {
 104     *admitted = ghost_cache_->Admit(key);
 105   }
 106   auto handle = sim_cache_->Lookup(key);
 107   if (handle != nullptr) {
 108     sim_cache_->Release(handle);
 109     *is_cache_miss = false;
 110   } else if (!no_insert && *admitted && value_size > 0) {
 111     // TODO: Should we check for an error here?
 112     auto s = sim_cache_->Insert(key, /*value=*/nullptr, value_size,
 113                                 /*deleter=*/nullptr,
 114                                 /*handle=*/nullptr, priority);
 115     s.PermitUncheckedError();
 116   }
 117   if (update_metrics) {
 118     miss_ratio_stats_.UpdateMetrics(access.access_timestamp, is_user_access,
 119                                     *is_cache_miss);
 120   }
 121 }
 122
 123 void PrioritizedCacheSimulator::Access(const BlockCacheTraceRecord& access) {
 124   bool is_cache_miss = true;
 125   bool admitted = true;
 126   AccessKVPair(access.block_key, access.block_size,
 127                ComputeBlockPriority(access), access, access.no_insert,
 128                BlockCacheTraceHelper::IsUserAccess(access.caller),
 129                &is_cache_miss, &admitted, /*update_metrics=*/true);
 130 }
 131
 132 void HybridRowBlockCacheSimulator::Access(const BlockCacheTraceRecord& access) {
 133   // TODO (haoyu): We only support Get for now. We need to extend the tracing
 134   // for MultiGet, i.e., non-data block accesses must log all keys in a
 135   // MultiGet.
 136   bool is_cache_miss = true;
 137   bool admitted = false;
 138   if (access.caller == TableReaderCaller::kUserGet &&
 139       access.get_id != BlockCacheTraceHelper::kReservedGetId) {
 140     // This is a Get request.
 141     const std::string& row_key = BlockCacheTraceHelper::ComputeRowKey(access);
 142     GetRequestStatus& status = getid_status_map_[access.get_id];
 143     if (status.is_complete) {
 144       // This Get request completes.
 145       // Skip future accesses to its index/filter/data
 146       // blocks. These block lookups are unnecessary if we observe a hit for the
 147       // referenced key-value pair already. Thus, we treat these lookups as
 148       // hits. This is also to ensure the total number of accesses are the same
 149       // when comparing to other policies.
 150       miss_ratio_stats_.UpdateMetrics(access.access_timestamp,
 151                                       /*is_user_access=*/true,
 152                                       /*is_cache_miss=*/false);
 153       return;
 154     }
 155     if (status.row_key_status.find(row_key) == status.row_key_status.end()) {
 156       // This is the first time that this key is accessed. Look up the key-value
 157       // pair first. Do not update the miss/accesses metrics here since it will
 158       // be updated later.
 159       AccessKVPair(row_key, access.referenced_data_size, Cache::Priority::HIGH,
 160                    access,
 161                    /*no_insert=*/false,
 162                    /*is_user_access=*/true, &is_cache_miss, &admitted,
 163                    /*update_metrics=*/false);
 164       InsertResult result = InsertResult::NO_INSERT;
 165       if (admitted && access.referenced_data_size > 0) {
 166         result = InsertResult::INSERTED;
 167       } else if (admitted) {
 168         result = InsertResult::ADMITTED;
 169       }
 170       status.row_key_status[row_key] = result;
 171     }
 172     if (!is_cache_miss) {
 173       // A cache hit.
 174       status.is_complete = true;
 175       miss_ratio_stats_.UpdateMetrics(access.access_timestamp,
 176                                       /*is_user_access=*/true,
 177                                       /*is_cache_miss=*/false);
 178       return;
 179     }
 180     // The row key-value pair observes a cache miss. We need to access its
 181     // index/filter/data blocks.
 182     InsertResult inserted = status.row_key_status[row_key];
 183     AccessKVPair(
 184         access.block_key, access.block_size, ComputeBlockPriority(access),
 185         access,
 186         /*no_insert=*/!insert_blocks_upon_row_kvpair_miss_ || access.no_insert,
 187         /*is_user_access=*/true, &is_cache_miss, &admitted,
 188         /*update_metrics=*/true);
 189     if (access.referenced_data_size > 0 && inserted == InsertResult::ADMITTED) {
 190       // TODO: Should we check for an error here?
 191       auto s = sim_cache_->Insert(row_key, /*value=*/nullptr,
 192                                   access.referenced_data_size,
 193                                   /*deleter=*/nullptr,
 194                                   /*handle=*/nullptr, Cache::Priority::HIGH);
 195       s.PermitUncheckedError();
 196       status.row_key_status[row_key] = InsertResult::INSERTED;
 197     }
 198     return;
 199   }
 200   AccessKVPair(access.block_key, access.block_size,
 201                ComputeBlockPriority(access), access, access.no_insert,
 202                BlockCacheTraceHelper::IsUserAccess(access.caller),
 203                &is_cache_miss, &admitted, /*update_metrics=*/true);
 204 }
 205
 206 BlockCacheTraceSimulator::BlockCacheTraceSimulator(
 207     uint64_t warmup_seconds, uint32_t downsample_ratio,
 208     const std::vector<CacheConfiguration>& cache_configurations)
 209     : warmup_seconds_(warmup_seconds),
 210       downsample_ratio_(downsample_ratio),
 211       cache_configurations_(cache_configurations) {}
 212
 213 Status BlockCacheTraceSimulator::InitializeCaches() {
 214   for (auto const& config : cache_configurations_) {
 215     for (auto cache_capacity : config.cache_capacities) {
 216       // Scale down the cache capacity since the trace contains accesses on
 217       // 1/'downsample_ratio' blocks.
 218       uint64_t simulate_cache_capacity = cache_capacity / downsample_ratio_;
 219       std::shared_ptr<CacheSimulator> sim_cache;
 220       std::unique_ptr<GhostCache> ghost_cache;
 221       std::string cache_name = config.cache_name;
 222       if (cache_name.find(kGhostCachePrefix) != std::string::npos) {
 223         ghost_cache.reset(new GhostCache(
 224             NewLRUCache(config.ghost_cache_capacity, /*num_shard_bits=*/1,
 225                         /*strict_capacity_limit=*/false,
 226                         /*high_pri_pool_ratio=*/0)));
 227         cache_name = cache_name.substr(kGhostCachePrefix.size());
 228       }
 229       if (cache_name == "lru") {
 230         sim_cache = std::make_shared<CacheSimulator>(
 231             std::move(ghost_cache),
 232             NewLRUCache(simulate_cache_capacity, config.num_shard_bits,
 233                         /*strict_capacity_limit=*/false,
 234                         /*high_pri_pool_ratio=*/0));
 235       } else if (cache_name == "lru_priority") {
 236         sim_cache = std::make_shared<PrioritizedCacheSimulator>(
 237             std::move(ghost_cache),
 238             NewLRUCache(simulate_cache_capacity, config.num_shard_bits,
 239                         /*strict_capacity_limit=*/false,
 240                         /*high_pri_pool_ratio=*/0.5));
 241       } else if (cache_name == "lru_hybrid") {
 242         sim_cache = std::make_shared<HybridRowBlockCacheSimulator>(
 243             std::move(ghost_cache),
 244             NewLRUCache(simulate_cache_capacity, config.num_shard_bits,
 245                         /*strict_capacity_limit=*/false,
 246                         /*high_pri_pool_ratio=*/0.5),
 247             /*insert_blocks_upon_row_kvpair_miss=*/true);
 248       } else if (cache_name == "lru_hybrid_no_insert_on_row_miss") {
 249         sim_cache = std::make_shared<HybridRowBlockCacheSimulator>(
 250             std::move(ghost_cache),
 251             NewLRUCache(simulate_cache_capacity, config.num_shard_bits,
 252                         /*strict_capacity_limit=*/false,
 253                         /*high_pri_pool_ratio=*/0.5),
 254             /*insert_blocks_upon_row_kvpair_miss=*/false);
 255       } else {
 256         // Not supported.
 257         return Status::InvalidArgument("Unknown cache name " +
 258                                        config.cache_name);
 259       }
 260       sim_caches_[config].push_back(sim_cache);
 261     }
 262   }
 263   return Status::OK();
 264 }
 265
 266 void BlockCacheTraceSimulator::Access(const BlockCacheTraceRecord& access) {
 267   if (trace_start_time_ == 0) {
 268     trace_start_time_ = access.access_timestamp;
 269   }
 270   // access.access_timestamp is in microseconds.
 271   if (!warmup_complete_ &&
 272       trace_start_time_ + warmup_seconds_ * kMicrosInSecond <=
 273           access.access_timestamp) {
 274     for (auto& config_caches : sim_caches_) {
 275       for (auto& sim_cache : config_caches.second) {
 276         sim_cache->reset_counter();
 277       }
 278     }
 279     warmup_complete_ = true;
 280   }
 281   for (auto& config_caches : sim_caches_) {
 282     for (auto& sim_cache : config_caches.second) {
 283       sim_cache->Access(access);
 284     }
 285   }
 286 }
 287
 288 }  // namespace ROCKSDB_NAMESPACE