From b53307e3f4264f75307f08107279c67785fd6c28 Mon Sep 17 00:00:00 2001 From: Mark Nelson Date: Tue, 12 Jun 2018 13:32:13 -0500 Subject: [PATCH] cache: aged based bin counters. Signed-off-by: Mark Nelson --- cache/lru_cache.cc | 56 +++++++++++++++++++++++++- cache/lru_cache.h | 13 ++++++ cache/sharded_cache.cc | 33 +++++++++++++++ cache/sharded_cache.h | 11 +++++ include/rocksdb/cache.h | 12 ++++++ utilities/simulator_cache/sim_cache.cc | 16 ++++++++ 6 files changed, 140 insertions(+), 1 deletion(-) diff --git a/cache/lru_cache.cc b/cache/lru_cache.cc index 28b93800..061bd9d5 100644 --- a/cache/lru_cache.cc +++ b/cache/lru_cache.cc @@ -107,12 +107,15 @@ LRUCacheShard::LRUCacheShard(size_t capacity, bool strict_capacity_limit, high_pri_pool_ratio_(high_pri_pool_ratio), high_pri_pool_capacity_(0), usage_(0), - lru_usage_(0) { + lru_usage_(0), + bin_count_(1), + age_bins_() { // Make empty circular linked list lru_.next = &lru_; lru_.prev = &lru_; lru_low_pri_ = &lru_; SetCapacity(capacity); + RotateBins(); } LRUCacheShard::~LRUCacheShard() {} @@ -180,6 +183,48 @@ double LRUCacheShard::GetHighPriPoolRatio() const{ return high_pri_pool_ratio_; } +void LRUCacheShard::SetBinCount(uint64_t count) { + MutexLock l(&mutex_); + if (count > 0) { + bin_count_ = count; + } +} + +void LRUCacheShard::RotateBins() { + MutexLock l(&mutex_); + age_bins_.push_front(std::make_shared(0)); + age_bins_.resize(bin_count_); +} + +size_t LRUCacheShard::GetBinnedUsage(uint64_t bin) const { + MutexLock l(&mutex_); + // Bin out of range, ie no data. + if (bin > age_bins_.size() - 1) { + return 0; + } + return *(age_bins_[bin]); +} + +size_t LRUCacheShard::GetBinnedUsage(uint64_t first_bin, uint64_t last_bin) const { + MutexLock l(&mutex_); + + // first bin out of range, return 0 + if (first_bin > age_bins_.size() - 1) { + return 0; + } + + // last bin out of range, don't walk off the end. + if (last_bin > age_bins_.size() - 1) { + last_bin = age_bins_.size() - 1; + } + + size_t bytes = 0; + for (uint64_t i = first_bin; i < last_bin; i++) { + bytes += *(age_bins_[i]); + } + return bytes; +} + void LRUCacheShard::LRU_Remove(LRUHandle* e) { assert(e->next != nullptr); assert(e->prev != nullptr); @@ -193,6 +238,8 @@ void LRUCacheShard::LRU_Remove(LRUHandle* e) { if (e->InHighPriPool()) { assert(high_pri_pool_usage_ >= e->charge); high_pri_pool_usage_ -= e->charge; + } else { +// *(e->cache_age_bin) -= e->charge; } } @@ -369,6 +416,9 @@ Status LRUCacheShard::Insert(const Slice& key, uint32_t hash, void* value, { MutexLock l(&mutex_); + // Set the current age_bin + e->cache_age_bin = age_bins_[0]; + // Free the space following strict LRU policy until enough space // is freed or the lru list is empty EvictFromLRU(charge, &last_reference_list); @@ -390,6 +440,10 @@ Status LRUCacheShard::Insert(const Slice& key, uint32_t hash, void* value, // space was freed LRUHandle* old = table_.Insert(e); usage_ += e->charge; + // Count High Pri items separately + if (!e->IsHighPri()) { + *(e->cache_age_bin) += e->charge; + } if (old != nullptr) { old->SetInCache(false); if (Unref(old)) { diff --git a/cache/lru_cache.h b/cache/lru_cache.h index c80594a1..eb8a563d 100644 --- a/cache/lru_cache.h +++ b/cache/lru_cache.h @@ -9,6 +9,7 @@ #pragma once #include +#include #include "cache/sharded_cache.h" @@ -44,6 +45,7 @@ namespace rocksdb { // RUCache::Release (to move into state 2) or LRUCacheShard::Erase (for state 3) struct LRUHandle { + std::shared_ptr cache_age_bin; // cache age bin void* value; void (*deleter)(const Slice&, void* value); LRUHandle* next_hash; @@ -211,6 +213,12 @@ class ALIGN_AS(CACHE_LINE_SIZE) LRUCacheShard : public CacheShard { virtual size_t GetHighPriPoolUsage() const; virtual double GetHighPriPoolRatio() const; + // Age binned byte counter methods + virtual void SetBinCount(uint64_t count) override; + virtual void RotateBins() override; + virtual size_t GetBinnedUsage(uint64_t bin) const override; + virtual size_t GetBinnedUsage(uint64_t first_bin, uint64_t last_bin) const override; + private: void LRU_Remove(LRUHandle* e); void LRU_Insert(LRUHandle* e); @@ -279,6 +287,10 @@ class ALIGN_AS(CACHE_LINE_SIZE) LRUCacheShard : public CacheShard { // We don't count mutex_ as the cache's internal state so semantically we // don't mind mutex_ invoking the non-const actions. mutable port::Mutex mutex_; + + // Age binned cache byte counters + uint64_t bin_count_; + std::deque> age_bins_; }; class LRUCache : public ShardedCache { @@ -297,6 +309,7 @@ class LRUCache : public ShardedCache { virtual size_t GetHighPriPoolUsage() const override; virtual double GetHighPriPoolRatio() const override; virtual void SetHighPriPoolRatio(double high_pri_pool_ratio) override; + // Retrieves number of elements in LRU, for unit test purpose only size_t TEST_GetLRUSize(); diff --git a/cache/sharded_cache.cc b/cache/sharded_cache.cc index 6a0a2228..5a8fe230 100644 --- a/cache/sharded_cache.cc +++ b/cache/sharded_cache.cc @@ -111,6 +111,39 @@ size_t ShardedCache::GetPinnedUsage() const { return usage; } +// Aged based counter binning +void ShardedCache::SetBinCount(uint64_t count) { + int num_shards = 1 << num_shard_bits_; + for (int s = 0; s < num_shards; s++) { + GetShard(s)->SetBinCount(count); + } +} + +void ShardedCache::RotateBins() { + int num_shards = 1 << num_shard_bits_; + for (int s = 0; s < num_shards; s++) { + GetShard(s)->RotateBins(); + } +} + +size_t ShardedCache::GetBinnedUsage(uint64_t bin) const { + int num_shards = 1 << num_shard_bits_; + size_t usage = 0; + for (int s = 0; s < num_shards; s++) { + usage += GetShard(s)->GetBinnedUsage(bin); + } + return usage; +} + +size_t ShardedCache::GetBinnedUsage(uint64_t first_bin, uint64_t last_bin) const { + int num_shards = 1 << num_shard_bits_; + size_t usage = 0; + for (int s = 0; s < num_shards; s++) { + usage += GetShard(s)->GetBinnedUsage(first_bin, last_bin); + } + return usage; +} + void ShardedCache::ApplyToAllCacheEntries(void (*callback)(void*, size_t), bool thread_safe) { int num_shards = 1 << num_shard_bits_; diff --git a/cache/sharded_cache.h b/cache/sharded_cache.h index 54d0c377..4f58996d 100644 --- a/cache/sharded_cache.h +++ b/cache/sharded_cache.h @@ -40,6 +40,11 @@ class CacheShard { bool thread_safe) = 0; virtual void EraseUnRefEntries() = 0; virtual std::string GetPrintableOptions() const { return ""; } + + virtual void SetBinCount(uint64_t count) = 0; + virtual void RotateBins() = 0; + virtual size_t GetBinnedUsage(uint64_t bin) const = 0; + virtual size_t GetBinnedUsage(uint64_t first_bin, uint64_t last_bin) const = 0; }; // Generic cache interface which shards cache by hash of keys. 2^num_shard_bits @@ -77,6 +82,12 @@ class ShardedCache : public Cache { virtual size_t GetHighPriPoolUsage() const override = 0; virtual double GetHighPriPoolRatio() const override = 0; + // Aged based counter binning + virtual void SetBinCount(uint64_t count); + virtual void RotateBins(); + virtual size_t GetBinnedUsage(uint64_t bin) const; + virtual size_t GetBinnedUsage(uint64_t first_bin, uint64_t last_bin) const; + virtual void ApplyToAllCacheEntries(void (*callback)(void*, size_t), bool thread_safe) override; virtual void EraseUnRefEntries() override; diff --git a/include/rocksdb/cache.h b/include/rocksdb/cache.h index 46661c79..146e5d1f 100644 --- a/include/rocksdb/cache.h +++ b/include/rocksdb/cache.h @@ -226,6 +226,18 @@ class Cache { return 0; } + // Set the maximum number of age bins to track + virtual void SetBinCount(uint64_t count) = 0; + + // Add a new age bin and remove any bins over the bin count. + virtual void RotateBins() = 0; + + // Get the byte usage for a given age bin. + virtual size_t GetBinnedUsage(uint64_t bin) const = 0; + + // Get the byte usage for a given range of age bins. + virtual size_t GetBinnedUsage(uint64_t first_bin, uint64_t last_bin) const = 0; + // Call this on shutdown if you want to speed it up. Cache will disown // any underlying data and will not free it on delete. This call will leak // memory - call this only if you're shutting down the process. diff --git a/utilities/simulator_cache/sim_cache.cc b/utilities/simulator_cache/sim_cache.cc index e7750dd5..b4efa996 100644 --- a/utilities/simulator_cache/sim_cache.cc +++ b/utilities/simulator_cache/sim_cache.cc @@ -315,6 +315,22 @@ class SimCacheImpl : public SimCache { return cache_activity_logger_.bg_status(); } + virtual void SetBinCount(uint64_t count) override { + key_only_cache_->SetBinCount(count); + } + + virtual void RotateBins() override { + key_only_cache_->RotateBins(); + } + + virtual size_t GetBinnedUsage(uint64_t bin) const override { + return key_only_cache_->GetBinnedUsage(bin); + } + + virtual size_t GetBinnedUsage(uint64_t first_bin, uint64_t last_bin) const override { + return key_only_cache_->GetBinnedUsage(first_bin, last_bin); + } + private: std::shared_ptr cache_; std::shared_ptr key_only_cache_; -- 2.47.3