Massive Technical Interviews Tips: Eviction policy

关于cache的 eviction policy设计
TODO: https://github.com/apache/ignite/tree/master/modules/core/src/main/java/org/apache/ignite/cache/eviction
https://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=316982

我觉得可能strategy看起来更好些，考虑到是个behavioral pattern，不同algorithm 重写同一个方法, 但是需要考虑的重点应该变成了如何使得这个重写的方法尽可能够都使用公共的数据存储结构。最坏不做抽象的情况，就是数据结构保存在当前类中，就变成了类似于factory模式的模式了

我刚搜了圈，发现 apache ignite 有类似的抽象的例子
https://ignite.apache.org/releas ... EvictionPolicy.html，不过好像就是把evictionPloicy抽象成abstract class了，然后数据结构也是在子类中定义的。就如同你说的，不一样的policy的数据结构是不一样的，强行去abstract common 数据结构会有点得不偿失，所以用个工厂模式可能会比较好懂，代码也比较直观

就是设计一个cache的eviction policy，你可以选择是LRU, 还是LFU，还是其他eviction policy. 选择哪个，就按照哪个eviction policy执行。
大家认为这种情况，用哪个pattern比较好？

首先回顾一下LeetCode的LRUCache这道题目所设计的接口：

class LRUCache {
public:
// Get the value (will always be positive) of the key if the key exists in the
// cache, otherwise return -1.
int get(int key);
// Set or insert the value if the key is not already present. When the cache
// reached its capacity, it should invalidate the least recently used item
// before inserting a new item.
void put(int key, int value);
};

复制代码

当然这个接口非常简陋，至少有两个问题：

(1) Cache和eviction policy（LRU）的逻辑是合并在一起的

这也正是我们这里OOD设计所要解决的问题：将eviction policy解耦（decouple）出来，使得其可以作为一个参数（或者模板参数）被传入Cache类，那么得到的Cache对象就会使用对应的policy。

(2) 没有触及cache设计的一个重要部分：value的生存期的管理

如果value是占用较多内存空间的大对象（而不是LeetCode题中仅占用4个字节的栈区int），或者是C/C++写的代码，一般是由cache管理生存期。
也就是说当evict一个value时，其占用内存应该立刻被回收，而这时所有对该value对象的引用应当立刻失效 —— 在这种情况下要避免代码出bug（非法内存访问），必须由cache对value进行引用计数，且返回值使用"counted reference"（类似于C++ shared pointer）。
不过如果返回的是栈区对象/对象的拷贝/带GC语言下（例如Java）的对象引用，那么不需要考虑引用计数问题，但是这时cache就无法保证内存的使用量被控制在规定范围内。

第(2)点其实是为了说一下eviction policy设计时关于引用计数的接口 —— 下面简化的代码中没有实现这一接口，但是需要了解一下，因为很多实际系统中是有相关内容的，例如PostgreSQL：https://github.com/postgres/postgres/blob/master/src/backend/storage/buffer/bufmgr.c#L139

现在回到(1)，下面贴的代码主要包含了：
(a) EvictionPolicy的抽象类
(b) 继承了EvictionPolicy的LRU/LFU实现
(c) 一个EvictionPolicy工厂，使得可以比较容易地添加新的Policy实现
(c) 使用EvictionPolicy实现的Cache类

// Eviction policy的抽象
template <typename Entry>
class EvictionPolicy {
public:
virtual Entry chooseEntryToEvict() = 0;
virtual void entryCreated(const Entry &entry) = 0;
virtual void entryReferenced(const Entry &entry) = 0;
// 如果维护引用计数的话需要这个接口
// virtual void entryUnreferenced(const Entry &entry) = 0;
virtual void entryEvicted(const Entry &entry) = 0;
};
// Eviction policy的类型
enum class EvictionPolicyType : int {
kLRU = 0,
kLFU,
kClock,
// ...
};
// 一个简单的LRU实现，不支持并发访问
template <typename Entry>
class LRUPolicy : public EvictionPolicy<Entry> {
public:
Entry chooseEntryToEvict() override {
return list_.back();
}
void entryCreated(const Entry &entry) override {
list_.push_front(entry);
index_.emplace(entry, list_.begin());
}
void entryReferenced(const Entry &entry) override {
const auto &it = index_.at(entry);
if (it != list_.begin()) {
list_.splice(list_.begin(), list_, it, std::next(it));
}
}
void entryEvicted(const Entry &entry) override {
const auto it = index_.find(entry);
list_.erase(it->second);
index_.erase(it);
}
private:
using EntryList = std::list<Entry>;
using EntryListIterator = typename EntryList::iterator;
std::list<Entry> list_;
std::unordered_map<Entry, const EntryListIterator> index_;
};
// 一个简单的LFU实现，不支持并发访问
template <typename Entry>
class LFUPolicy : public EvictionPolicy<Entry> {
public:
Entry chooseEntryToEvict() override {
return std::get<0>(*list_.begin());
}
void entryCreated(const Entry &entry) override {
const auto ret = list_.emplace(entry, Clock::now(), 1);
index_.emplace(entry, ret.first);
}
void entryReferenced(const Entry &entry) override {
auto &it = index_.at(entry);
const std::size_t count = std::get<2>(*it);
list_.erase(it);
const auto ret = list_.emplace(entry, Clock::now(), count + 1);
it = ret.first;
}
void entryEvicted(const Entry &entry) override {
const auto it = index_.find(entry);
list_.erase(it->second);
index_.erase(it);
}
private:
using Clock = std::chrono::high_resolution_clock;
using TimePoint = std::chrono::time_point<Clock>;
using Record = std::tuple<Entry, TimePoint, std::size_t>;
struct RecordComparator {
inline bool operator()(const Record &lhs, const Record &rhs) const {
if (std::get<2>(lhs) != std::get<2>(rhs)) {
return std::get<2>(lhs) < std::get<2>(rhs);
}
if (std::get<1>(lhs) != std::get<1>(rhs)) {
return std::get<1>(lhs) < std::get<1>(rhs);
}
return std::get<0>(lhs) < std::get<0>(rhs);
}
};
using SortedList = std::set<Record, RecordComparator>;
using SortedListIterator = typename SortedList::iterator;
SortedList list_;
std::unordered_map<Entry, SortedListIterator> index_;
};
// Eviction policy的单例工厂
template <typename Entry>
class EvictionPolicyFactory {
public:
static const EvictionPolicyFactory& Instance() {
static EvictionPolicyFactory<Entry> instance;
return instance;
}
EvictionPolicy<Entry>* createEvictionPolicy(const EvictionPolicyType type) const {
switch (type) {
case EvictionPolicyType::kLRU:
return new LRUPolicy<Entry>();
case EvictionPolicyType::kLFU:
return new LFUPolicy<Entry>();
default:
break;
}
throw std::runtime_error("Unsupported eviction policy type");
};
};
// 一个简单的泛型Cache实现
template <typename Key, typename Value>
class Cache {
private:
using Storage = std::unordered_map<Key, Value>;
using Entry = const typename Storage::value_type*;
using Factory = EvictionPolicyFactory<Entry>;
public:
Cache(const std::size_t capacity, const EvictionPolicyType type)
: capacity_(capacity),
eviction_policy_(Factory::Instance().createEvictionPolicy(type)) {
}
const Value* get(const Key &key) {
const auto it = storage_.find(key);
if (it == storage_.end()) {
return nullptr;
}
eviction_policy_->entryReferenced(&(*it));
return &it->second;
}
void put(const Key &key, const Value &value) {
const auto it = storage_.find(key);
if (it == storage_.end()) {
if (storage_.size() >= capacity_) {
const auto ev = eviction_policy_->chooseEntryToEvict();
eviction_policy_->entryEvicted(ev);
storage_.erase(ev->first);
}
const auto ret = storage_.emplace(key, value);
eviction_policy_->entryCreated(&(*ret.first));
} else {
it->second = value;
eviction_policy_->entryReferenced(&(*it));
}
}
private:
const std::size_t capacity_;
Storage storage_;
std::unique_ptr<EvictionPolicy<Entry>> eviction_policy_;
};
/*******************************************************************************
* 可以用于提交LeetCode 146的代码
class LRUCache {
public:
LRUCache(int capacity)
: cache_(capacity, EvictionPolicyType::kLRU) {
}
int get(int key) {
const int *value = cache_.get(key);
return value == nullptr ? -1 : *value;
}
void put(int key, int value) {
cache_.put(key, value);
}
private:
Cache<int, int> cache_;
};
*******************************************************************************/
template <typename C, typename T>
void Print(C &cache, const T &key) {
const auto *value = cache.get(key);
if (value == nullptr) {
std::cout << "[" << key << "] NULL\n";
} else {
std::cout << "[" << key << "] " << *value << "\n";
}
}

Tuesday, April 16, 2019

Eviction policy - Design Pattern

Labels

Popular Posts