Ceph Client 中的 LRU 设计

在 Ceph 中 Client 和 MDS 部分的 lru 实现和淘汰策略稍有不同，但作用都是用来管理 dentry 等结构，方便及时将不使用的文件和目录清出内存，这里主要关注 lru 的实现而不关注 dentry 的淘汰时机。

首先看下 LRU 的结构：

1
2
3
4
5
6
7

// lru.h
class LRU {
// ...
private:
  using LRUList = xlist<LRUObject*>;
  LRUList top, bottom, pintail;
}

这里和大部分 LRU 的实现类似， ceph 也使用一个双向链表作为 lru 的基础结构（也就是这里的 xlist，基本可以当作一个双向链表看待）。只不过 ceph 同时使用了三个链表 top、bottom 和 pintail 来细化 lru 的不同位置。

其中 top 和 bottom 比较好理解就是一般 lru 实现中的首尾两端，越靠近 top.front() 则说明最近越多使用，越靠近 bottom.back() 则说明最近越少使用，可以被淘汰。

pintail 稍微特殊一点，在此链中的 dentry 表示正在有人使用（可能是外部应用持有文件的 filehandle，因此随时有可能访问），因此不会被 从 lru 链中淘汰，即使最近没有人使用。

1
2
3

void lru_insert_top(LRUObject *o);
void lru_insert_mid(LRUObject *o);
void lru_insert_bot(LRUObject *o);

这里就对应将一个 lru object 插入 lru 链的三个位置（从外部看 lru 是一个链，内部才分为 top 或者 bottom），实际对应就是

1
2
3

top.push_front(&o->lru_link); // 将 object 插入 top 头部
bottom.push_front(&o->lru_link); // 将 object 插入 bottom 头部
bottom.push_back(&o->lru_link); // 将 object 插入 bottom 尾部，也是最接近淘汰的位置

另外之前已经说了 xlist 的实现属于是一个双向链表的变种，这里也简单看一下，以 top.push_front 为例：

1
2
3
4

void push_front(item *i) {
    if (i->_list) 
      i->_list->remove(i);
// ...

首先就是如果这个 item（也就是一个 lru object） 已经在某一个链上了，那么先通过 remove 把这个 item 从先前的链上摘下来，这个实现可以避免一个 item 挂在多个链上

1
2
3

// ...
    i->_list = this;
// ...

接着将自己的 _list 指向 this，表示 item 的所属链表（也就是 top）

1
2
3
4

// ...
		i->_next = _front;
		i->_prev = 0;
// ...

这里就是首先把 item 挂到链表上，因为是 push_front 所以 _prev 为空， _front 是整个链表的头部。

1
2
3
4
5
6
7
8

// ...
		if (_front) 
			_front->_prev = i;
		else
			_back = i;
		_front = i;
		_size++;
	}

同时要更新一下链表的头尾指针，以及整个链表的长度。

接着，必要时 client 通过 lru_get_next_expire 获取最近最少使用的 object 进行 trim，这个过程实际上就是从 lru 中拿出 bottom.back()

1
2
3
4
5
6
7
8
9
10

LRUObject *lru_get_next_expire() {
	adjust();
	// look through tail of bot
	while (bottom.size()) {
		LRUObject *p = bottom.back();
	if (!p->lru_pinned) return p;

	// move to pintail
	pintail.push_front(&p->lru_link);
}

这里 adjust 就是把整个 lru 链中 object 数量的 60%（实际要减去 pinned object）放入 top，剩余部分放入 bottom

接着直接从 bottom 拿出末端 object，如果这个 object 没有 pinned 则直接将其返回，表示此 object 可以被 trim

pin 和 unpin 则是一个特殊的过程， pin 一个指定的 dentry 时我们只需要将对应的 object 从 top 或者 bottom 上移出到 pintail 链上（无关乎首尾，因为 pintail 上的 dentry 都不能 trim），而 unpin 则只需要将其 pintail 中移出到 bottom 的尾部即可

整个 lru 设计相对来说比较容易理解，也非常易于使用。

对于一个特定的 dentry，我们会在初次获取到其 object 时可以将其放至 lru mid，初次使用时将其放至 lru top，接着如果没有使用会随着 lru 的 adjust 逐渐移动到 bottom 然后被 client 取出作为 expired object 淘汰掉，而如果这时通过 pin 加入 pintail 的话就会一直等到 unpin 之后再放到 bottom.back 等待 trim