cachelib/allocator/NvmAdmissionPolicy.h (133 lines of code) (raw):
/*
* Copyright (c) Facebook, Inc. and its affiliates.
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
#pragma once
#include <folly/Range.h>
#include "cachelib/common/ApproxSplitSet.h"
#include "cachelib/common/AtomicCounter.h"
#include "cachelib/common/PercentileStats.h"
namespace facebook {
namespace cachelib {
// Base class for admission policy into nvm cache
// It provides:
// 1. Interface function for testing whether an item should be admitted.
// 2. Stats gathering functionalities.
// 3. minTTL functionality: when set, items with configured TTL smaller than
// minTTL will be rejected.
template <typename Cache>
class NvmAdmissionPolicy {
public:
using Item = typename Cache::Item;
using ChainedItemIter = typename Cache::ChainedItemIter;
virtual ~NvmAdmissionPolicy() = default;
// The method that the outside class calls to get the admission decision.
// It captures the common logics (e.g statistics) then
// delicates the detailed implementation to subclasses in acceptImpl.
virtual bool accept(const Item& item,
folly::Range<ChainedItemIter> chainItem) final {
util::LatencyTracker overallTracker(overallLatency_);
overallCount_.inc();
auto minTTL = minTTL_.load(std::memory_order_relaxed);
auto itemTTL = static_cast<uint64_t>(item.getConfiguredTTL().count());
if (minTTL > 0 && itemTTL < minTTL) {
ttlRejected_.inc();
return false;
}
const bool decision = acceptImpl(item, chainItem);
if (decision) {
accepted_.inc();
} else {
rejected_.inc();
}
return decision;
}
// same as the above, but makes admission decisions given just the key and
// not the entire item. This can be used when we can infer the information
// needed for admission decision from only the key.
// Note: minTTL will be ignored if a callsite uses this function to test
// a key.
virtual bool accept(typename Item::Key key) final {
util::LatencyTracker overallTracker(overallLatency_);
overallCount_.inc();
const bool decision = acceptImpl(key);
if (decision) {
accepted_.inc();
} else {
rejected_.inc();
}
return decision;
}
// The method that exposes stats.
virtual std::unordered_map<std::string, double> getCounters() final {
auto ctrs = getCountersImpl();
ctrs["ap.called"] = overallCount_.get();
ctrs["ap.accepted"] = accepted_.get();
ctrs["ap.rejected"] = rejected_.get();
auto visitorUs = [&ctrs](folly::StringPiece name, double count) {
ctrs[name.toString()] = count / 1000;
};
overallLatency_.visitQuantileEstimator(visitorUs, "ap.latency_us");
ctrs["ap.ttlRejected"] = ttlRejected_.get();
return ctrs;
}
// Track access for an item.
// This is useful when the admission policy requires access pattern to make
// admission decision.
// @param key key corresponding to the item
virtual void trackAccess(typename Item::Key) {}
// Set minTTL. This method should be called only once.
void initMinTTL(uint64_t minTTL) {
auto initValue = minTTL_.load(std::memory_order_relaxed);
if (initValue > 0) {
throw std::invalid_argument(
"minTTL should be initialized to non-zero only once.");
}
auto success = minTTL_.compare_exchange_strong(initValue, minTTL);
if (!success) {
throw std::invalid_argument("Setting minTTL failed.");
}
}
uint64_t getMinTTL() const { return minTTL_; }
protected:
// Implement this method for the detailed admission decision logic.
// By default this accepts all items.
virtual bool acceptImpl(const Item&, folly::Range<ChainedItemIter>) {
return true;
}
// Implement this method for the detailed admission decision logic.
// By default this accepts all items.
virtual bool acceptImpl(typename Item::Key) { return true; }
// Implementation specific statistics.
// Please include a prefix/postfix with the name of implementation to avoid
// collision with base level stats.
virtual std::unordered_map<std::string, double> getCountersImpl() {
return {};
}
private:
util::PercentileStats overallLatency_;
AtomicCounter overallCount_{0};
AtomicCounter accepted_{0};
AtomicCounter rejected_{0};
AtomicCounter ttlRejected_{0};
// The minimum TTL to an item need to have to be accepted.
std::atomic<uint64_t> minTTL_{0};
};
// an admission policy that keeps track of a number (numEntries) of unique keys
// recently observed and rejects an item if the key is not recently observed,
// backed by cachelib/common/ApproxSplitSet
template <typename Cache>
class RejectFirstAP final : public NvmAdmissionPolicy<Cache> {
public:
using Item = typename Cache::Item;
using ChainedItemIter = typename Cache::ChainedItemIter;
// @param numEntries number of items to be tracked
// @param numSplits number of splits in the ApporxSplitSet
// @param suffixIgnoreLength length of the suffix to be ignored in the key.
// Useful when an admission policy treates items with the same key prefix as
// the same item.
RejectFirstAP(uint64_t numEntries,
uint32_t numSplits,
size_t suffixIgnoreLength,
bool useDramHitSignal)
: tracker_{numEntries, numSplits},
suffixIgnoreLength_{suffixIgnoreLength},
useDramHitSignal_{useDramHitSignal} {}
protected:
bool acceptImpl(const Item& it,
folly::Range<ChainedItemIter>) final override {
const bool wasDramHit =
useDramHitSignal_ && it.getLastAccessTime() > it.getCreationTime();
const auto seenBefore = trackAndCheckIfSeenBefore(it.getKey());
if (!seenBefore && wasDramHit) {
admitsByDramHits_.inc();
}
return seenBefore || wasDramHit;
}
bool acceptImpl(typename Item::Key key) final override {
return trackAndCheckIfSeenBefore(key);
}
std::unordered_map<std::string, double> getCountersImpl() final override {
std::unordered_map<std::string, double> ctrs;
ctrs["ap.reject_first_keys_tracked"] = tracker_.numKeysTracked();
ctrs["ap.reject_first_tracking_window_secs"] =
tracker_.trackingWindowDurationSecs();
ctrs["ap.reject_first_admits_by_dram_hit"] = admitsByDramHits_.get();
return ctrs;
}
private:
// @param key the key to check and start tracking
// @return true if the key was seen before, false otherwise.
bool trackAndCheckIfSeenBefore(typename Item::Key key) {
const size_t len = key.size() > suffixIgnoreLength_
? key.size() - suffixIgnoreLength_
: key.size();
const auto keyHash = folly::hash::SpookyHashV2::Hash64(key.data(), len, 0);
// if key already existed, return true. If we are inserting it for
// the first time, we insert to track and return false
bool seenBefore = tracker_.insert(keyHash);
return seenBefore;
}
ApproxSplitSet tracker_;
const size_t suffixIgnoreLength_;
AtomicCounter admitsByDramHits_{0};
const bool useDramHitSignal_{true};
};
} // namespace cachelib
} // namespace facebook