1.LRU简介
最近最少使用（LRU，Least Recently Used）算法用于简单的缓存淘汰策略。如果最近访问了某个元素，且这个元素在缓存队列中，就将这个元素提升至队列头部；否则就将其加入到队列中，处于队列末尾的元素将被淘汰。
读写和更新的效率需要达到O(1)，可以使用HashMap+双向链表实现。Ceph里使用双向链表实现，并记录链表头和尾部。
2.LRU数据结构
LRU至少需要双向链表list和LRU算法的封装即LRUImpl。
- Ceph中使用xlist类做为双向链表，链表中的元素用item类表示。
- Ceph中使用LRU类实现LRU算法。
- Ceph中使用LRUObject类做为LRU算法处理的对象类型。
- Ceph中如果想让某个class具备LRU算法的功能，就继承LRUObject。
需要注意的是，通常设置midpoint，用于划分两个队列，前者为top，后者为bottom，midpoint指明了top和bottom长度的比例。Ceph中设置midpoint为0.6，即top占总长度的60%，bottom占40%。
3.LRU的实现
- 双向链表的实现
template<typename T>
class xlist {
public:
class item {
…
private:
friend xlist;
T _item;
item *_prev = nullptr, *_next = nullptr;
xlist *_list = nullptr;
};
...
private:
item *_front, *_back;
size_t _size;
};
- LRU算法的实现
class LRU {
public:
LRU() : num_pinned(0), midpoint(0.6) {}
uint64_t lru_get_size() const {
return lru_get_top()+lru_get_bot()+lru_get_pintail(); }
uint64_t lru_get_top() const { return top.size(); }
uint64_t lru_get_bot() const{ return bottom.size(); }
uint64_t lru_get_pintail() const { return pintail.size(); }
uint64_t lru_get_num_pinned() const { return num_pinned; }
void lru_insert_top(LRUObject *o);
void lru_insert_mid(LRUObject *o);
void lru_insert_bot(LRUObject *o);
...
private:
typedef xlist<LRUObject *> LRUList;
LRUList top, bottom, pintail;
}
- LRU中对象的实现
class LRUObject {
public:
LRUObject() : lru(), lru_link(this), lru_pinned(false) { }
~LRUObject();
// pin/unpin item in cache
void lru_pin();
void lru_unpin();
bool lru_is_expireable() const { return !lru_pinned; }
friend class LRU;
private:
class LRU *lru;
xlist<LRUObject *>::item lru_link;
bool lru_pinned;
};
- 通过继承具备LRU功能
class BufferHead : public LRUObject{...}
class Object : public LRUObject{...}
