ZFS文件系统中的ARC缓存算法
source link: https://allenwind.github.io/blog/6220/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
NLP、深度学习、机器学习、Python、Go
ZFS文件系统中的ARC缓存算法
毕业设计遇到一种缓存算法叫ARC，来自ZFS文件系统，今天简单介绍下。先前写过一篇文章LRU算法的优化，该文讲传统的LRU算法遇到的问题问题及其优化方案。LRU算法的问题是对于扫描读的情况丢失有效缓存，具体场景如下：业务一次过读取大量数据（可以是扫描整个table的读）并缓存，这些数据占满了缓存空间（把原先在缓存中的数据置换出去），可是它们只使用一次。这种场景下导致两个问题：
- 把原先缓存的有效的数据置换出去
- 当前缓存的数据并没有用，却把缓存空间填满
为了解决这个问题，LRU算法的优化一文提供了解决方案，本文讲述采用ARC Cache来解决这个问题。
ARC Cache 的特性
ARC Cache 提供了两种对数据缓存的策略：
- 根据数据的最近使用情况来缓存（LRU）
- 根据数据的使用频率情况来缓存（LFU）
但arc cache并不只是两者的结合，它们即便结合实现，也无法解决上述的问题。为此，arc cache还提供了两种机制：
- 存储从LRU链表中淘汰的page的信息
- 存储从LFU链表中淘汰的page的信息
好了，接下来看看arc cache的结构和算法过程
ARC Cache 的结构和算法过程
arc cache内部有四条双链表：
- 实现LRU算法的双链表
- 实现LFU算法的双链表
- 存储LRU链表中淘汰的page信息的链表
- 存储LFU链表中淘汰的page信息的链表
LRU链表和普通的LRU链表一样使用；LFU链表只存储使用次数大于一次的page，原先在LRU链表中的page如果被再次使用就被移动到LFU链表中，原先在LFU链表中的page如果被再次使用就被移动到链表的头部，这样，就LFU链表而言，最不频繁使用的page在缓存满的时候会被置换出去。这样的缓存方法对于那些被频繁使用的page不会因为局部性原理而被淘汰出去（LRU算法中，就算一块page被频繁使用，也有可能因为局部性原理，最终被淘汰出去）
你可能会发现，上面的策略并没有解决一个问题：当缓存填满后，新来的page置入前需要淘汰一个page，但这样会可能把刚刚才被缓存的page淘汰出去（就算那么最不近使用的page）？
在ARC的基础上可以添加常用的特性，比如：
- expire
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK