| // Some portions Copyright (c) 2011 The LevelDB Authors. All rights reserved. |
| // Use of this source code is governed by a BSD-style license that can be |
| // found in the LICENSE file. |
| |
| #include "kudu/util/cache.h" |
| |
| #include <cstring> |
| #include <functional> |
| #include <memory> |
| #include <string> |
| #include <tuple> |
| #include <utility> |
| #include <vector> |
| |
| #include <gflags/gflags.h> |
| #include <glog/logging.h> |
| #include <gtest/gtest.h> |
| |
| #include "kudu/gutil/macros.h" |
| #include "kudu/gutil/ref_counted.h" |
| #include "kudu/gutil/strings/substitute.h" |
| #include "kudu/util/block_cache_metrics.h" |
| #include "kudu/util/cache_metrics.h" |
| #include "kudu/util/coding.h" |
| #include "kudu/util/env.h" |
| #include "kudu/util/faststring.h" |
| #include "kudu/util/mem_tracker.h" |
| #include "kudu/util/metrics.h" |
| #include "kudu/util/nvm_cache.h" |
| #include "kudu/util/slice.h" |
| #include "kudu/util/test_macros.h" |
| #include "kudu/util/test_util.h" |
| |
| DECLARE_bool(cache_force_single_shard); |
| DECLARE_string(nvm_cache_path); |
| |
| DECLARE_double(cache_memtracker_approximation_ratio); |
| |
| using std::make_tuple; |
| using std::tuple; |
| using std::shared_ptr; |
| using std::unique_ptr; |
| using std::vector; |
| using strings::Substitute; |
| |
| namespace kudu { |
| |
| // Conversions between numeric keys/values and the types expected by Cache. |
| static std::string EncodeInt(int k) { |
| faststring result; |
| PutFixed32(&result, k); |
| return result.ToString(); |
| } |
| static int DecodeInt(const Slice& k) { |
| CHECK_EQ(4, k.size()); |
| return DecodeFixed32(k.data()); |
| } |
| |
| // Cache sharding policy affects the composition of the cache. Some test |
| // scenarios assume cache is single-sharded to keep the logic simpler. |
| enum class ShardingPolicy { |
| MultiShard, |
| SingleShard, |
| }; |
| |
| class CacheBaseTest : public KuduTest, |
| public Cache::EvictionCallback { |
| public: |
| explicit CacheBaseTest(size_t cache_size) |
| : cache_size_(cache_size) { |
| } |
| |
| size_t cache_size() const { |
| return cache_size_; |
| } |
| |
| // Implementation of the EvictionCallback interface. |
| void EvictedEntry(Slice key, Slice val) override { |
| evicted_keys_.push_back(DecodeInt(key)); |
| evicted_values_.push_back(DecodeInt(val)); |
| } |
| |
| int Lookup(int key) { |
| auto handle(cache_->Lookup(EncodeInt(key), Cache::EXPECT_IN_CACHE)); |
| return handle ? DecodeInt(cache_->Value(handle)) : -1; |
| } |
| |
| void Insert(int key, int value, int charge = 1) { |
| std::string key_str = EncodeInt(key); |
| std::string val_str = EncodeInt(value); |
| auto handle(cache_->Allocate(key_str, val_str.size(), charge)); |
| CHECK(handle); |
| memcpy(cache_->MutableValue(&handle), val_str.data(), val_str.size()); |
| cache_->Insert(std::move(handle), this); |
| } |
| |
| void Erase(int key) { |
| cache_->Erase(EncodeInt(key)); |
| } |
| |
| protected: |
| void SetupWithParameters(Cache::MemoryType mem_type, |
| Cache::EvictionPolicy eviction_policy, |
| ShardingPolicy sharding_policy) { |
| // Disable approximate tracking of cache memory since we make specific |
| // assertions on the MemTracker in this test. |
| FLAGS_cache_memtracker_approximation_ratio = 0; |
| |
| // Using single shard makes the logic of scenarios simple for capacity- |
| // and eviction-related behavior. |
| FLAGS_cache_force_single_shard = |
| (sharding_policy == ShardingPolicy::SingleShard); |
| |
| if (google::GetCommandLineFlagInfoOrDie("nvm_cache_path").is_default) { |
| FLAGS_nvm_cache_path = GetTestPath("nvm-cache"); |
| ASSERT_OK(Env::Default()->CreateDir(FLAGS_nvm_cache_path)); |
| } |
| |
| switch (eviction_policy) { |
| case Cache::EvictionPolicy::FIFO: |
| if (mem_type != Cache::MemoryType::DRAM) { |
| FAIL() << "FIFO cache can only be of DRAM type"; |
| } |
| cache_.reset(NewCache<Cache::EvictionPolicy::FIFO, |
| Cache::MemoryType::DRAM>(cache_size(), |
| "cache_test")); |
| MemTracker::FindTracker("cache_test-sharded_fifo_cache", &mem_tracker_); |
| break; |
| case Cache::EvictionPolicy::LRU: |
| switch (mem_type) { |
| case Cache::MemoryType::DRAM: |
| cache_.reset(NewCache<Cache::EvictionPolicy::LRU, |
| Cache::MemoryType::DRAM>(cache_size(), |
| "cache_test")); |
| break; |
| case Cache::MemoryType::NVM: |
| if (CanUseNVMCacheForTests()) { |
| cache_.reset(NewCache<Cache::EvictionPolicy::LRU, |
| Cache::MemoryType::NVM>(cache_size(), |
| "cache_test")); |
| } |
| break; |
| default: |
| FAIL() << mem_type << ": unrecognized cache memory type"; |
| break; |
| } |
| MemTracker::FindTracker("cache_test-sharded_lru_cache", &mem_tracker_); |
| break; |
| default: |
| FAIL() << "unrecognized cache eviction policy"; |
| break; |
| } |
| |
| // Since nvm cache does not have memtracker due to the use of |
| // tcmalloc for this we only check for it in the DRAM case. |
| if (mem_type == Cache::MemoryType::DRAM) { |
| ASSERT_TRUE(mem_tracker_.get()); |
| } |
| |
| // cache_ will be null if we're trying to set up a test for the NVM cache |
| // and were unable to do so. |
| if (cache_) { |
| scoped_refptr<MetricEntity> entity = METRIC_ENTITY_server.Instantiate( |
| &metric_registry_, "test"); |
| unique_ptr<BlockCacheMetrics> metrics(new BlockCacheMetrics(entity)); |
| cache_->SetMetrics(std::move(metrics), Cache::ExistingMetricsPolicy::kKeep); |
| } |
| } |
| |
| const size_t cache_size_; |
| vector<int> evicted_keys_; |
| vector<int> evicted_values_; |
| shared_ptr<MemTracker> mem_tracker_; |
| unique_ptr<Cache> cache_; |
| MetricRegistry metric_registry_; |
| }; |
| |
| class CacheTest : |
| public CacheBaseTest, |
| public ::testing::WithParamInterface<tuple<Cache::MemoryType, |
| Cache::EvictionPolicy, |
| ShardingPolicy>> { |
| public: |
| CacheTest() |
| : CacheBaseTest(16 * 1024 * 1024) { |
| } |
| |
| void SetUp() override { |
| const auto& param = GetParam(); |
| SetupWithParameters(std::get<0>(param), |
| std::get<1>(param), |
| std::get<2>(param)); |
| } |
| }; |
| |
| INSTANTIATE_TEST_SUITE_P( |
| CacheTypes, CacheTest, |
| ::testing::Values( |
| make_tuple(Cache::MemoryType::DRAM, |
| Cache::EvictionPolicy::FIFO, |
| ShardingPolicy::MultiShard), |
| make_tuple(Cache::MemoryType::DRAM, |
| Cache::EvictionPolicy::FIFO, |
| ShardingPolicy::SingleShard), |
| make_tuple(Cache::MemoryType::DRAM, |
| Cache::EvictionPolicy::LRU, |
| ShardingPolicy::MultiShard), |
| make_tuple(Cache::MemoryType::DRAM, |
| Cache::EvictionPolicy::LRU, |
| ShardingPolicy::SingleShard), |
| make_tuple(Cache::MemoryType::NVM, |
| Cache::EvictionPolicy::LRU, |
| ShardingPolicy::MultiShard), |
| make_tuple(Cache::MemoryType::NVM, |
| Cache::EvictionPolicy::LRU, |
| ShardingPolicy::SingleShard))); |
| |
| TEST_P(CacheTest, TrackMemory) { |
| RETURN_IF_NO_NVM_CACHE(std::get<0>(GetParam())); |
| if (mem_tracker_) { |
| Insert(100, 100, 1); |
| ASSERT_EQ(1, mem_tracker_->consumption()); |
| Erase(100); |
| ASSERT_EQ(0, mem_tracker_->consumption()); |
| ASSERT_EQ(1, mem_tracker_->peak_consumption()); |
| } |
| } |
| |
| TEST_P(CacheTest, HitAndMiss) { |
| RETURN_IF_NO_NVM_CACHE(std::get<0>(GetParam())); |
| ASSERT_EQ(-1, Lookup(100)); |
| |
| Insert(100, 101); |
| ASSERT_EQ(101, Lookup(100)); |
| ASSERT_EQ(-1, Lookup(200)); |
| ASSERT_EQ(-1, Lookup(300)); |
| |
| Insert(200, 201); |
| ASSERT_EQ(101, Lookup(100)); |
| ASSERT_EQ(201, Lookup(200)); |
| ASSERT_EQ(-1, Lookup(300)); |
| |
| Insert(100, 102); |
| ASSERT_EQ(102, Lookup(100)); |
| ASSERT_EQ(201, Lookup(200)); |
| ASSERT_EQ(-1, Lookup(300)); |
| |
| ASSERT_EQ(1, evicted_keys_.size()); |
| ASSERT_EQ(100, evicted_keys_[0]); |
| ASSERT_EQ(101, evicted_values_[0]); |
| } |
| |
| TEST_P(CacheTest, Erase) { |
| RETURN_IF_NO_NVM_CACHE(std::get<0>(GetParam())); |
| Erase(200); |
| ASSERT_EQ(0, evicted_keys_.size()); |
| |
| Insert(100, 101); |
| Insert(200, 201); |
| Erase(100); |
| ASSERT_EQ(-1, Lookup(100)); |
| ASSERT_EQ(201, Lookup(200)); |
| ASSERT_EQ(1, evicted_keys_.size()); |
| ASSERT_EQ(100, evicted_keys_[0]); |
| ASSERT_EQ(101, evicted_values_[0]); |
| |
| Erase(100); |
| ASSERT_EQ(-1, Lookup(100)); |
| ASSERT_EQ(201, Lookup(200)); |
| ASSERT_EQ(1, evicted_keys_.size()); |
| } |
| |
| TEST_P(CacheTest, EntriesArePinned) { |
| RETURN_IF_NO_NVM_CACHE(std::get<0>(GetParam())); |
| Insert(100, 101); |
| auto h1 = cache_->Lookup(EncodeInt(100), Cache::EXPECT_IN_CACHE); |
| ASSERT_EQ(101, DecodeInt(cache_->Value(h1))); |
| |
| Insert(100, 102); |
| auto h2 = cache_->Lookup(EncodeInt(100), Cache::EXPECT_IN_CACHE); |
| ASSERT_EQ(102, DecodeInt(cache_->Value(h2))); |
| ASSERT_EQ(0, evicted_keys_.size()); |
| |
| h1.reset(); |
| ASSERT_EQ(1, evicted_keys_.size()); |
| ASSERT_EQ(100, evicted_keys_[0]); |
| ASSERT_EQ(101, evicted_values_[0]); |
| |
| Erase(100); |
| ASSERT_EQ(-1, Lookup(100)); |
| ASSERT_EQ(1, evicted_keys_.size()); |
| |
| h2.reset(); |
| ASSERT_EQ(2, evicted_keys_.size()); |
| ASSERT_EQ(100, evicted_keys_[1]); |
| ASSERT_EQ(102, evicted_values_[1]); |
| } |
| |
| // Add a bunch of light and heavy entries and then count the combined |
| // size of items still in the cache, which must be approximately the |
| // same as the total capacity. |
| TEST_P(CacheTest, HeavyEntries) { |
| RETURN_IF_NO_NVM_CACHE(std::get<0>(GetParam())); |
| const int kLight = cache_size() / 1000; |
| const int kHeavy = cache_size() / 100; |
| int added = 0; |
| int index = 0; |
| while (added < 2 * cache_size()) { |
| const int weight = (index & 1) ? kLight : kHeavy; |
| Insert(index, 1000+index, weight); |
| added += weight; |
| index++; |
| } |
| |
| int cached_weight = 0; |
| for (int i = 0; i < index; i++) { |
| const int weight = (i & 1 ? kLight : kHeavy); |
| int r = Lookup(i); |
| if (r >= 0) { |
| cached_weight += weight; |
| ASSERT_EQ(1000+i, r); |
| } |
| } |
| ASSERT_LE(cached_weight, cache_size() + cache_size() / 10); |
| } |
| |
| TEST_P(CacheTest, InvalidateAllEntries) { |
| RETURN_IF_NO_NVM_CACHE(std::get<0>(GetParam())); |
| constexpr const int kEntriesNum = 1024; |
| // This scenarios assumes no evictions are done at the cache capacity. |
| ASSERT_LE(kEntriesNum, cache_size()); |
| |
| // Running invalidation on empty cache should yield no invalidated entries. |
| ASSERT_EQ(0, cache_->Invalidate({})); |
| for (auto i = 0; i < kEntriesNum; ++i) { |
| Insert(i, i); |
| } |
| // Remove a few entries from the cache (sparse pattern of keys). |
| constexpr const int kSparseKeys[] = {1, 100, 101, 500, 501, 512, 999, 1001}; |
| for (const auto key : kSparseKeys) { |
| Erase(key); |
| } |
| ASSERT_EQ(ARRAYSIZE(kSparseKeys), evicted_keys_.size()); |
| |
| // All inserted entries, except for the removed one, should be invalidated. |
| ASSERT_EQ(kEntriesNum - ARRAYSIZE(kSparseKeys), cache_->Invalidate({})); |
| // In the end, no entries should be left in the cache. |
| ASSERT_EQ(kEntriesNum, evicted_keys_.size()); |
| } |
| |
| TEST_P(CacheTest, InvalidateNoEntries) { |
| RETURN_IF_NO_NVM_CACHE(std::get<0>(GetParam())); |
| constexpr const int kEntriesNum = 10; |
| // This scenarios assumes no evictions are done at the cache capacity. |
| ASSERT_LE(kEntriesNum, cache_size()); |
| |
| const Cache::ValidityFunc func = [](Slice /* key */, Slice /* value */) { |
| return true; |
| }; |
| // Running invalidation on empty cache should yield no invalidated entries. |
| ASSERT_EQ(0, cache_->Invalidate({ func })); |
| |
| for (auto i = 0; i < kEntriesNum; ++i) { |
| Insert(i, i); |
| } |
| |
| // No entries should be invalidated since the validity function considers |
| // all entries valid. |
| ASSERT_EQ(0, cache_->Invalidate({ func })); |
| ASSERT_TRUE(evicted_keys_.empty()); |
| } |
| |
| TEST_P(CacheTest, InvalidateNoEntriesNoAdvanceIterationFunctor) { |
| RETURN_IF_NO_NVM_CACHE(std::get<0>(GetParam())); |
| constexpr const int kEntriesNum = 256; |
| // This scenarios assumes no evictions are done at the cache capacity. |
| ASSERT_LE(kEntriesNum, cache_size()); |
| |
| const Cache::InvalidationControl ctl = { |
| Cache::kInvalidateAllEntriesFunc, |
| [](size_t /* valid_entries_count */, size_t /* invalid_entries_count */) { |
| // Never advance over the item list. |
| return false; |
| } |
| }; |
| |
| // Running invalidation on empty cache should yield no invalidated entries. |
| ASSERT_EQ(0, cache_->Invalidate(ctl)); |
| |
| for (auto i = 0; i < kEntriesNum; ++i) { |
| Insert(i, i); |
| } |
| |
| // No entries should be invalidated since the iteration functor doesn't |
| // advance over the list of entries, even if every entry is declared invalid. |
| ASSERT_EQ(0, cache_->Invalidate(ctl)); |
| // In the end, all entries should be in the cache. |
| ASSERT_EQ(0, evicted_keys_.size()); |
| } |
| |
| TEST_P(CacheTest, InvalidateOddKeyEntries) { |
| RETURN_IF_NO_NVM_CACHE(std::get<0>(GetParam())); |
| constexpr const int kEntriesNum = 64; |
| // This scenarios assumes no evictions are done at the cache capacity. |
| ASSERT_LE(kEntriesNum, cache_size()); |
| |
| const Cache::ValidityFunc func = [](Slice key, Slice /* value */) { |
| return DecodeInt(key) % 2 == 0; |
| }; |
| // Running invalidation on empty cache should yield no invalidated entries. |
| ASSERT_EQ(0, cache_->Invalidate({ func })); |
| |
| for (auto i = 0; i < kEntriesNum; ++i) { |
| Insert(i, i); |
| } |
| ASSERT_EQ(kEntriesNum / 2, cache_->Invalidate({ func })); |
| ASSERT_EQ(kEntriesNum / 2, evicted_keys_.size()); |
| for (auto i = 0; i < kEntriesNum; ++i) { |
| if (i % 2 == 0) { |
| ASSERT_EQ(i, Lookup(i)); |
| } else { |
| ASSERT_EQ(-1, Lookup(i)); |
| } |
| } |
| } |
| |
| // This class is dedicated for scenarios specific for FIFOCache. |
| // The scenarios use a single-shard cache for simpler logic. |
| class FIFOCacheTest : public CacheBaseTest { |
| public: |
| FIFOCacheTest() |
| : CacheBaseTest(10 * 1024) { |
| } |
| |
| void SetUp() override { |
| SetupWithParameters(Cache::MemoryType::DRAM, |
| Cache::EvictionPolicy::FIFO, |
| ShardingPolicy::SingleShard); |
| } |
| }; |
| |
| // Verify how the eviction behavior of a FIFO cache. |
| TEST_F(FIFOCacheTest, EvictionPolicy) { |
| static constexpr int kNumElems = 20; |
| const int size_per_elem = cache_size() / kNumElems; |
| // First data chunk: fill the cache up to the capacity. |
| int idx = 0; |
| do { |
| Insert(idx, idx, size_per_elem); |
| // Keep looking up the very first entry: this is to make sure lookups |
| // do not affect the recency criteria of the eviction policy for FIFO cache. |
| Lookup(0); |
| ++idx; |
| } while (evicted_keys_.empty()); |
| ASSERT_GT(idx, 1); |
| |
| // Make sure the earliest inserted entry was evicted. |
| ASSERT_EQ(-1, Lookup(0)); |
| |
| // Verify that the 'empirical' capacity matches the expected capacity |
| // (it's a single-shard cache). |
| const int capacity = idx - 1; |
| ASSERT_EQ(kNumElems, capacity); |
| |
| // Second data chunk: add (capacity / 2) more elements. |
| for (int i = 1; i < capacity / 2; ++i) { |
| // Earlier inserted elements should be gone one-by-one as new elements are |
| // inserted, and lookups should not affect the recency criteria of the FIFO |
| // eviction policy. |
| ASSERT_EQ(i, Lookup(i)); |
| Insert(capacity + i, capacity + i, size_per_elem); |
| ASSERT_EQ(capacity + i, Lookup(capacity + i)); |
| ASSERT_EQ(-1, Lookup(i)); |
| } |
| ASSERT_EQ(capacity / 2, evicted_keys_.size()); |
| |
| // Early inserted elements from the first chunk should be evicted |
| // to accommodate the elements from the second chunk. |
| for (int i = 0; i < capacity / 2; ++i) { |
| SCOPED_TRACE(Substitute("early inserted elements: index $0", i)); |
| ASSERT_EQ(-1, Lookup(i)); |
| } |
| // The later inserted elements from the first chunk should be still |
| // in the cache. |
| for (int i = capacity / 2; i < capacity; ++i) { |
| SCOPED_TRACE(Substitute("late inserted elements: index $0", i)); |
| ASSERT_EQ(i, Lookup(i)); |
| } |
| } |
| |
| class LRUCacheTest : |
| public CacheBaseTest, |
| public ::testing::WithParamInterface<tuple<Cache::MemoryType, |
| ShardingPolicy>> { |
| public: |
| LRUCacheTest() |
| : CacheBaseTest(16 * 1024 * 1024) { |
| } |
| |
| void SetUp() override { |
| const auto& param = GetParam(); |
| SetupWithParameters(std::get<0>(param), |
| Cache::EvictionPolicy::LRU, |
| std::get<1>(param)); |
| } |
| }; |
| |
| INSTANTIATE_TEST_SUITE_P( |
| CacheTypes, LRUCacheTest, |
| ::testing::Combine(::testing::Values(Cache::MemoryType::DRAM, |
| Cache::MemoryType::NVM), |
| ::testing::Values(ShardingPolicy::MultiShard, |
| ShardingPolicy::SingleShard))); |
| |
| TEST_P(LRUCacheTest, EvictionPolicy) { |
| RETURN_IF_NO_NVM_CACHE(std::get<0>(GetParam())); |
| static constexpr int kNumElems = 1000; |
| const int size_per_elem = cache_size() / kNumElems; |
| |
| Insert(100, 101); |
| Insert(200, 201); |
| |
| // Loop adding and looking up new entries, but repeatedly accessing key 101. |
| // This frequently-used entry should not be evicted. |
| for (int i = 0; i < kNumElems + 1000; i++) { |
| Insert(1000+i, 2000+i, size_per_elem); |
| ASSERT_EQ(2000+i, Lookup(1000+i)); |
| ASSERT_EQ(101, Lookup(100)); |
| } |
| ASSERT_EQ(101, Lookup(100)); |
| // Since '200' wasn't accessed in the loop above, it should have |
| // been evicted. |
| ASSERT_EQ(-1, Lookup(200)); |
| } |
| |
| } // namespace kudu |