论文阅读 Prefetch-aware fingerprint cache management for data deduplication systems
论文链接 https://link.springer.com/article/10.1007/s11704-017-7119-0
这篇论文试图解决的问题是在cache 环节之前,prefetch-cache 进来的可能无关的 fingerprint 造成的cache pollution问题,即可能把没有用的 fingerprint 换入 cache,造成 cache 污染的问题。
这篇论文的贡献:提出了一种新的针对 prefetch 进来的 fingerprint 替换策略,并且提出了一种 adaptive 的方法,针对不同的 fingerprint 有与其对应的替换策略,提高了 deduplication throughput 和 deduplication ratio. 本文并不是试图提出一种新的对 fingerprint 如何进行 prefetch 的方法,而是针对不同种类的,已经做过了 prefetch 操作的 fingerprint,针对他们不同的种类,做不同的replacement。同时,这种 replacement policy 并不和 LRU 等 policy 相冲突,反而可以和之前的 LRU policy 相结合。
具体方法框架如图所示:
细节:针对一个被 prefetch 的 fingerprint 分为了两大类,一类是 accurate 的fingerprint,一类是 inaccurate 的fingerprint。accurate 的 fingerprint 是说那些prefetch 进 cache 之后,hit 了超过不止一次的 fingerprint,反之则是 inaccurate。对于 inaccurate fingerprint 又可以划分为不同的种类,有 Unused prefetched fingerprint,used only once fingerprint,mixed pattern fingerprint,针对这三种不同的 fingerprint,提出了不同的替换策略,分别是 PreCache-UNU, PreCache-UOO,PreCache-MIX。不同的替换策略都有不同的假设,自然也有不同的操作。
PreCache-UNU 预测所有新被 prefetch 的 fingerprint 都不会被用到(distant future)所以应该直接要被 LRU 算法替换出去(evicted quickly)针对这些 fingerprint,采用的方法是把他们直接移动到 LRU queue 的尾端,这样当 LRU 进行替换的时候,他们就是第一批被替换出去的 fingerprint。如果这些被认为是 UNU 的fingerprint 被使用了(即这个时候我们错误的划分了 fingerprint)那么根据 LRU 的规则他们也会被放到 head 端,这就是没有直接把这些 fingerprint 剔除的原因。
PreCache-UOO 预测所有的新的被 prefetch 的 fingerprint 只会被使用一次,然后就不会被使用。所以,他把这些 fingerprint 放在 LRU 队列的 head 端,并且当这些 fingerprint 被 hit 的时候,并不会重新调整他们的位置。(因为预测他们只会被使用一次,如果调整了他们的位置,就和传统的并无差别)。针对一些被 prefetch 进 cache,并且较长时间没有被使用,到快被替换出去的时候才被hit了一次,然后又不会被 hit 的fingerprint 而言,这种策略能够很快的将他们替换出去(因为并没有调整他们的位置)。
PreCache-MIX 给所有的 fingerprint 一个统一的策略,放在 LRU 队列的 tail 端,并且即使命中也不会调整位置。
同时,还存在一个问题,针对一个 fingerprint,如何把它进行分类,如何去选择一个适合他的替换策略。提出了一种动态适应的选择器,可以根据预测的历史结果,动态选择合适的策略去替换不同的 fingerprint。
选择器的功能:针对一个 fingerprint,去预测这个 fingerprint 是属于 accurate 还是 inaccurate 的,如果是 inaccurate 的,那么是 UNU 的,还是 UOO 的,还是 MIX 的。
选择器维护了几个计数器:
- total 记录了所有被 prefetch 的 fingerprint 个数。
- use_over_once,记录了cache中所有被 hit 超过一次的 fingerprint 的个数
- unused,记录了被 prefetch 的,但是没有被使用的 fingerprint 的个数。
- Use_only_once 记录了只被使用过一次的 fingerprint 的个数。
- hit_evice_buf 记录了一个main cache miss 在 evicted 中被 hit 的个数。
选择器主要的 idea:根据历史信息来预测。
每个种类都有一个对应的判别阈值和公式去决定这个 prefetch 的 fingerprint 是否是对应的种类。
效果评估:
在 BLC 和 SiLO 这两个系统的基础上加入了 PreCache 算法,使用的数据是 Kernel,MacOS 和 Homes 三种。BLC 系统代表的是 exact deduplication 系统,SiLO 系统代表的是 near exact deduplication 系统,针对两个不同的系统,采取的评价指标也不一样。BLC 中,因为 fingerprint 无法完全被存入cache,所以使用 look up index 的次数去评价系统,而 SiLO 因为 采用的是 sample feature 的方式,所以使用 deduplication ratio 去评价系统。
最新文章
- Atitit java集成内嵌浏览器与外嵌浏览器attilax总结
- MySQL 数据库的备份与恢复
- CSS display:inline-block
- Fail to start neutron-server
- easyUI笔记09.03
- linux设备驱动归纳总结(三):3.设备驱动面向对象思想和lseek的实现【转】
- VS2003 下GridControl的列显示成图片+文字的形式实现
- sql 判断表是否存在
- jQuery表格操作
- iOS7适配问题
- jsoup_解析任意网站,做任意网站客户端
- poj2777--Count Color(线段树,二进制转化)
- tar、scp、sftp、rsync简单使用
- 【从零开始搭建自己的.NET Core Api框架】(四)实战!带你半个小时实现接口的JWT授权验证
- redis的特点
- Python_基于Python同Linux进行交互式操作实现通过堡垒机访问目标机
- java匹配竖线的错误警示
- win7系统Oracle数据库本地备份
- excel设定备选值
- windows8.1中组件服务DCOM配置里属性灰色不可修改的解决办法
热门文章
- golang学习之路
- ELK 学习笔记之 Logstash之output配置
- iOS渠道分包2种模式之包内注入文件分包
- JSON parse error: No suitable constructor found for type
- SpringBootSecurity学习(23)前后端分离版之OAuth2.0 其它模式
- 02-22 决策树C4.5算法
- BZOJ 2535: [Noi2010]Plane 航空管制2
- Numpy数组操作
- 基于vue组件,发布npm包
- Qt5教程: (6) 菜单栏、工具栏、状态栏及核心控件