关于cache的 eviction policy设计

flykite083

注册一亩三分地论坛，查看更多干货！

您需要登录才可以下载或查看附件。没有帐号？注册账号

x

有这样一道面试题，觉得很不错，拿过来给大家讨论讨论。
就是设计一个cache的eviction policy，你可以选择是LRU, 还是LFU，还是其他eviction policy. 选择哪个，就按照哪个eviction policy执行。
大家认为这种情况，用哪个pattern比较好？

magicsets

我来大概写一点想法..

首先回顾一下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类

#include <chrono>
#include <cstddef>
#include <iostream>
#include <list>
#include <memory>
#include <mutex>
#include <set>
#include <stdexcept>
#include <unordered_map>
#include <utility>
#include <vector>
// 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";
}
}
int main(int argc, char *argv[]) {
std::vector<std::pair<EvictionPolicyType, std::string>> types = {
{ EvictionPolicyType::kLRU, "LRU" },
{ EvictionPolicyType::kLFU, "LFU" }
};
// 测试 LRU/LFU
for (const auto type : types) {
Cache<std::string, std::string> cache(2, type.first);
std::cout << "Testing " << type.second << ":\n";
std::cout << "--------\n";
cache.put("1", "A");
cache.put("2", "B");
Print(cache, "1");
Print(cache, "2");
std::cout << "##\n";
cache.put("1", "C");
cache.put("3", "D");
cache.put("4", "E");
Print(cache, "1");
Print(cache, "2");
Print(cache, "3");
Print(cache, "4");
std::cout << "\n";
}
}

复制代码

PS 可以在线测试一下代码：http://cpp.sh/5ifbw

输出是这样的

Testing LRU:
--------
[1] A
[2] B
##
[1] NULL
[2] NULL
[3] D
[4] E
Testing LFU:
--------
[1] A
[2] B
##
[1] C
[2] NULL
[3] NULL
[4] E

复制代码

kuanghaochina

flykite083 发表于 2018-1-29 23:50
我也想过strategy, 但是问题是cache自带一些数据结构，比如说dictionary, linkedlist, capacity等。然后 ...

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

flykite083

kuanghaochina 发表于 2018-1-29 22:23
我觉得可能strategy看起来更好些，考虑到是个behavioral pattern，不同algorithm 重写同一个方法, 但是需要 ...

我也想过strategy, 但是问题是cache自带一些数据结构，比如说dictionary, linkedlist, capacity等。然后用strategy的话，就是LRUstrategy和LFUstrategy class各自都有他们的get和put. 这时get和put就得传一堆东西了，比如node, dictionary等。这样好么？

oneexy

这个问题，伟大的linux帮你准备了N多套方案，简单来说，就是在cache hit和latency之间找平衡，lru最好啦，要速度就lfu 或者clock, 都要就lru+lfu。

flykite083

oneexy 发表于 2018-1-28 07:18
这个问题，伟大的linux帮你准备了N多套方案，简单来说，就是在cache hit和latency之间找平衡，lru最好啦， ...

多谢解答！不过面试的那个问题是要你design这个，是个OOD的问题。

oneexy

flykite083 发表于 2018-1-28 09:36
多谢解答！不过面试的那个问题是要你design这个，是个OOD的问题。

那样的话就变成一个算法题了呗，就是落实到代码呗，最难得就是lru这个会了就没啥问题了吧。真遇到了这个问题，我肯定选一个我会写代码的发昂发去做。

flykite083

oneexy 发表于 2018-1-28 09:42
那样的话就变成一个算法题了呗，就是落实到代码呗，最难得就是lru这个会了就没啥问题了吧。真遇到了这个 ...

应该是这样的：你可以选择eviction的policy, LRU, LFU, 或者其他x策略，y策略，z策略。用什么design pattern?

oneexy

flykite083 发表于 2018-1-28 10:08
应该是这样的：你可以选择eviction的policy, LRU, LFU, 或者其他x策略，y策略，z策略。用什么design patt ...

工厂模式么

flykite083

oneexy 发表于 2018-1-28 10:15
工厂模式么

嗯，我也这么觉得。想到过strategy模式，后来写了写觉得不对劲。

AAS1

请问这是哪家面试问的，有点狠。

flykite083

AAS1 发表于 2018-1-28 10:28
请问这是哪家面试问的，有点狠。

听说是Houzz

[题目讨论] 关于cache的 eviction policy设计

注册一亩三分地论坛，查看更多干货！

相关帖子

浏览过的版块