操作系统对高性能 SSD 支持不力，TerarkDB 怎么办

*手机浏览时建议横屏

我们在测试中发现，即使对 mmap 的内存标记了 MADV_RANDOM，当随机访问量很高时（PCIe SSD 的随机 IO 性能很高），仍会导致操作系统失去响应。

经过分析，我们认为，mmap 时，操作系统无法时间得知 page 的实际访问情况，只能通过启发性的算法，将一些 page 从 mmap 中暂时移除，如果接下来该 page 被访问到，它就可以通过一个 minor page fault 重新变成 active，如果长时间未被访问到，当系统缺乏内存时，它就可以被回收。这样的方式在绝大多数情况下工作良好，但是在这种频繁随机访问的极端情况下，就会对系统造成很大的压力：kswap 进程满载，所有进程的内存申请都被阻塞，表现出整个系统都失去响应的状态。

根据一个直观的推测，如果我们使用 pread 去进行随机读，那么操作系统就有足够的信息去维护 LRU 链表，从而可以避免 mmap 导致的问题……

代码很快改完并进入测试，然而情况依旧，pread 并没有达到我们预期的效果……

什么也不能阻止 TerarkDB 的性能，我们决定自己做一个 user space page cache……

为了性能，我们实现了一个 

LruReadonlyPageCache

顾名思义：LRU，Readonly，PageCache，并且，为了大化性能，我们只针对高性能 SSD 做优化：以单个 page 为 cache 的单位，这样就可以使用 hash table 去进行搜索，当然，多线程的支持是必须的。

对于 LruCache，有一点很关键：每次访问时都需要对 lru list 进行修改，将访问到的那个节点移动到 lru head，这个操作需要修改 5 个结点(使用数组下标做链接):

1. 从 lru list 中删除命中结点 x：需要修改命中结点的前后两个结点

void lru_remove(Node* base, size_t x) {
    auto next = base[x].lru_next;
    auto prev = base[x].lru_prev;
    base[next].lru_prev = prev;
    base[prev].lru_next = next;
}

2. 将命中结点 x 插到 lru head 之后（0 是 head 伪结点）：

void lru_insert_after_head(Node* base, size_t x) {             
    auto n = base[].lru_next;
    base[x].lru_next = n;
    base[x].lru_prev = ;
    base[n].lru_prev = x;
    base[].lru_next = x;
}

其中 head 伪结点总在 CPU cache 中，其它 4 个结点都是随机访问，当然，还有至少一次对 hash bucket 的随机访问（每多一个 hash 冲突，就多一个随机访问），所以，在 cache 命中的情况下，至少需要对内存进行 5 次随机访问，在 cache 很大时，全随机访问几乎总会导致 CPU 的 tlb miss，这样，就变成了 10 次对物理内存的随机访问，并且这些访问都要加锁。这还不包括对 buffer 的 memcpy，好在对 buffer 的 memcpy 不需要加锁，并且我们尽大可能省略 memcpy。

经过我们的仔细实现，终达到这样的效果：

• 假定每次 read 操作读入 O(1) 个 page: O(1) 的意思是说，不会一次性读入很多个 page

• 那么每个 read 操作的时间复杂度都是 O(1)，特别是在 mutex 的临界区内，是严格的 O(1)

• 即使是关闭一个文件，一次产生大量可回收 page 时，时间复杂度依然是 O(1)

一切看上去都很美好，然而测试发现，当线程数量较多时，性能离预期相差太远！

接下来的解决办法，只有做 sharding：创建多个 Lru cache，然后根据 key(file, page_id) 做 hash 进行 sharding, sharding 的目的只有一个，就是减少修改 lru list 时的 mutex 锁冲突。

sharding 的效果非常好：在 benchmark 中，32线程，31 shards，500 字节的随机读达到 2300万 op/sec。的“缺点”就是，和单 Lru Cache 相比，sharding lru 并不是严格的 Lru，好在 page 数量会非常大，会有几百万，甚至几千万，几亿个 page，在统计意义上，也算是“”的 Lru 了。

接下来，在接近全命中的场景下，和操作系统的 pread 对比了一下，竟然比操作系统的 pread 还要慢，操作系统的 pread 达到了 2600万 op/sec！我们知道，操作系统的 pread 是个系统调用，系统调用本身就比函数调用慢不少呢……但是，再仔细想想，操作系统自身的一些内存可以不用分页，减少了 tlb miss 的开销，并且，正因为操作系统的 pread 要达到这么快，它才不能去维护的 lru 链表，导致极端情况下的性能崩溃。

要比操作系统 pread 快，只有增大 shards，进一步减小锁冲突，仍然是 32 线程，shards 增到 61 时，随机读达到 2800万 op/sec