SSD内部去重模型和量化分析_ssdfans_传送门
SSD内部去重模型和量化分析
作者：阿呆 能在SSD内部实现去重吗？阿呆从理论到实现为你详细介绍。想要和阿呆还有全世界的大牛讨论SSD及存储相关技术？加nanoarch为微信好友，拉你进ssdfans微信群 。 提要上次ssdfans群里有人说三星有一款SSD，貌似是850主控使用了技术，阿呆难以置信，因为不仅有复杂的计算，还要维护一个LBA到哈希值的映射表，占用内存，增加延迟。不过，最近看到一篇韩国学者写的论文，讲的是SSD去重，所以简单介绍给大家看看。我们先来看看传统的去重是怎么实现的，就以我们曾经介绍过的EMC XtremIO全闪存阵列为例。XIO专门为去重维护了两张表，A2H（数据块逻辑地址——Hash值）和H2P（Hash值——SSD存放地址）。每个4KB数据块都会计算出一个SHA-1值作为指纹，以此来判断数据是不是重复，而不是直接比对数据。加上SSD内部的映射表，需要占用很大的内存，SHA-1计算也消耗CPU资源。显然，SSD内部不可能做到这么强大，所以我们来看看聪明的韩国工程师想出了什么办法。背景介绍以前阿呆读研究生的时候，学术大牛告诉我看论文最重要的就是introduction，这个东东看完，基本就知道了研究的来龙去脉和背景，如果introduction写得好，论文质量基本没问题。所以我们来看看这篇论文《Deduplication in SSDs: Model and Quantitative Analysis》的摘要和简介。SSD去重有三大好处：延长寿命，因为数据量少了；提升写性能，也是写的数据量少了；快：搬的数据少了。也有一些天然的便利条件：SSD内部有个映射表，所以去重可以直接用这个映射表，而不会增加新的映射表成本省下来的空间就是Over Provisioning了，空余空间越大，要搬移的数据就越少，速度越快写的数据少了，垃圾回收的写也少了，SSD的擦除次数就少了，寿命延长了。和生物一个道理啊，鳄鱼，乌龟，蟾蜍这些不怎么动的动物就是活得久。好处说了这么多，再来说说不利的形势：嵌入式环境太寒酸：一般是ARM嵌入式CPU，配一点点内存运气背，写下来的全是不可去重数据就惨了，或者重复率很低也得不偿失这篇论文使用了两种技术：采样过滤（软件实现，挺神秘的，往下看看就知道内容了）和指纹管理（其实就是硬件算Hash），实验结果是去重率在4%-51%，平均17%，写速度平均提升了15%，SSD寿命平均延长了2.4倍！（这是真的吗？）听起来牛逼烘烘的，让我们来一探究竟。去重架构经过对SSD数据的初步分析，作者得出一个惊人的结论：SSD内的重复数据往往写入时间也是相近的，所以维护一个小的Hash查找表就可以。同时把传统1：1的映射表改成了N：1，其中N就是重复的那些数据咯。最后在ARM7的OpenSSD开发板上实现了框架，同时Xilinx Virtex6 FPGA实现硬件去重计算，ARM9 EZ-X开发板实现软件去重。如上图的b为去重模块，分为三部分：指纹生成器：计算Hash值首先是指纹计算的数据块是多大？考虑到SSD写入的数据大部分都是4KB为单位，所以采用4KB作为数据块大小。其次是HASH算法用什么？SHA-1和MD5都比较常用，能保持非常好的唯一性，最终选择了SHA-1，每个4KB数据产生160位HASH值。指纹管理器：读写指纹需要考虑的主要问题是指纹查找表得多大？一般去重设计会维护一个完整的查找表，但SSD内部资源有限，OpenSSD只有64MB内存，还放了映射表和其他元数据。那怎么办？经过分析数据，发现重复数据在时间上很接近，所以只在内存中维护最近数据的指纹查找表。指纹映射表：指纹到物理地址的映射SSD攻城狮在《戏说FTL》中讲过，FTL中的映射表分为page映射,block映射和混合映射。因为去重使用了4KB数据块，所以这里采用page级映射。流程图下图，进来的数据[10, A]表示LBA 10的内容为A，计算出HASH值，A’，保存到物理地址100.看起来这里有两张表了：指纹映射表：A’— 物理地址100FTL映射表内容就是LBA 10 — 物理地址100最后一笔写[12, A]发现指纹有重复，就不写了，只更新了一下FTL映射表。不过在垃圾回收的时候这样做会有大麻烦，后面详述。去重理论模型如果你对理论没什么兴趣，可以直接跳到下一段。不过，还是建议你看看，因为所谓的理论其实就是四则运算而已。对于一般的SSD，写延迟包括映射表查询时间+Flash Program时间，计算如下但是对于加了去重的SSD，写延迟就变成了有重复和没重复两种情况的平均值：为了让去重能起到效果，就得要求公式2比公式1大，这样化简一下，得到公式3：这就是数据重复率的要求。这里面没有考虑垃圾回收，为什么？因为去重后要搬移的数据更少，垃圾回收带来的延迟肯定比以前更短，所以不予考虑。从公式3可以得出指纹生成和查询的时间与数据重复率的关系曲线，如下图。分别是四种Flash Program时间的曲线，明显，数据重复率和去重计算时间呈指数关系，这就要求我们要尽可能缩短去重带来的延迟。去重计算硬件方案为什么要用硬件来算SHA？可以看看下面这张图，在不同CPU上计算SHA需要的时间，可以看出最行的Microblaze需要6ms，最短的ARM9需要813us，都不可能商用。而硬件只需要80us。如下是FPGA里的硬件计算架构。4KB放数据，SHA-1 Core做计算，下面的Hash Comparator是做HASH值比较的。硬件计算时间80us，假如Flash Program时间1300us，那么数据重复率至少要有5%。如果能流水线处理HASH计算和Flash Program，映射表管理等，还可以更高效。软件方案 出方案之前，我们先来看一个统计。这个图是对各种典型应用写重复时间间隔的一个统计，横轴表示写了多少次才出现重复，纵轴表示在这个次数出现的重复案例在所有重复事件中的比例。可以看出来，绝大部分应用中，当你写了一个数据，如果还会再写一篇，那么它的重复写在4000次写内就出现了，之后就极少出现。基于这个现象就可以开发软件去重算法。这个软件算法设计得非常精妙，占用资源很少，但是效果却不错。如下是它的架构，首先数据从SATA写入后，就放入一个写buffer，这个buffer大小32MB，可以放8000个4KB数据块。每笔4KB数据块，从偏移512处读20个字节来快速计算出一个Hash索引值（512和20是实验证明比较好的参数），这个值是干什么的？就是对数据块做一个粗分类，按照Hash索引值，把数据块放到最下面不同的桶里面。Hash后放桶里分类是一种常见的软件分类方法。这样重复的数据肯定在一个桶里，不同桶里的数据必然不会重复。这些桶里放的其实不是数据本身，而是数据的指针而已，数据还在buffer里面呢。那为什么要分成不同的桶？什么时候去重啊？去重的时间很好猜到，那就是buffer满了，数据块要写到Flash了，就算算指纹，这时候桶就发挥作用了。如果数据块所在的桶里只有它一个，那就不用去重了，直接写下去。如果桶里有好几个小伙伴，那需要计算一下指纹，当然，是用软件计算，得花几百个微秒。不过说实话，这种采样之后数据Hash值还相同的话，重复的概率很高了。指纹管理指纹计算是结束了，但是怎么保存呢？搞一个大的指纹映射表明显不够现实，因为SSD主控的嵌入式环境伤不起啊！在给出方案之前，我们再来分析一下常见应用的写统计数据，思路自然就有了。LRU（Least Recently Used）是一种Cache常见的算法，就是把最近最少使用的数据从缓存移走。作者建了一个LRU模型，把最近写的4KB页都放在栈里面，顶部的被访问的时间近，底下的时间远。根据这个模型，在不同的栈深度下，新写的数据就有可能和栈里维护的数据重复，做实验得出重复率结果如下图。可以看出，栈其实不用太深，就能达到比较高的重复率。所以把栈深度设为2048，至于数据结构比较复杂，包括一个LRU双向链表和两个Hash表（Hash键值分别为指纹和物理地址）。在DRAM中占了2048×40字节=80KB空间:指纹20B（160bit），物理地址4B，LRU双向链表8B（估计两个4B指针），两个Hash表8B（内容估计是两个4B的指针）。这些都一直放在内存，不会保存或者恢复。阿呆的疑问和思考：为什么是栈？看起来是个队列，新数据写进来，入队列，旧数据到期，出队列。双向链表的作用：得到节点后，删除比较方便。为什么要删除呢？其实就是如果新写的数据和中间某个指纹重复，那就把这个节点删除，并添加到队列头上。Hash表的作用：指纹为Key的Hash表就是新数据写进来，来查是不是有重复的。物理地址为Key的Hash表是起什么作用？垃圾回收的时候用吗?怎么用？ FTL算法 选择FTL算法之前，我们先来做一个实验。看看常用的使用例子重复写的次数有多少，如下图，横轴是重复写次数，纵轴是重复写次数的累积百分比，可以看出，大部分应用重复写次数在3次以内。 基于这个事实，在正常的LBA->PBA (Logical Block Address -> Physical Block Address)映射表之外，还加了一个反向映射表，就是如果一个PBA对应多个LBA，就有映射PBA->LBA列表。这个方案的优点是读写查询快，没有特殊的查找。缺点是垃圾回收的时候搬一个物理页，需要更新好几个LBA的映射。但是前面的实验告诉我们，主要应用重复率不超过3，所以最多更新3条映射表记录，还可以接受。 映射表太大了，DRAM不够放，所以采用了Cache机制。为了防止异常掉电，加超级电容或者电池保护。 垃圾回收也比较简单，就是可用空间到80%以下（真的吗？太早了吧，20%差不多），就选择一个最合适的block开始数据搬移，把有效数据搬到新的block，更新映射表。最后擦除老的block，释放空间。一般选择最合适Block的方法就是找到无效数据最多的，这样搬的数据量最少。在这里，去重发挥了优势:重复数据只需要搬一次，提高了垃圾回收效率（阿呆认为单次搬的数据量没变，只不过频率降低了） 磨损平衡（Wear Leveling）：一般的算法是把擦出最多的Block和擦除最少的Block数据互换，为什么？因为擦除最少的Block数据访问最少，擦最多的Block访问最多，其实就是车多的马路坏的快，所以让车转移到量少的马路上。去重在此大显神威，重复数据大多在访问多的Block上，这样搬的数据量就少了（跟前面一样，单次数据量不变，频率降低了）。 维护两个映射表其实还是挺复杂的，就是要保证数据的一致性，所以更新一个映射表，另一个必须上锁，并同样更新。而且异常掉电后也会有很多特殊情况需要处理。 后面是性能测试，阿呆就不说了，无非是吹自己牛逼。不过这篇论文确实是一篇内容很扎实的文章，作者的算法并不是拍脑袋想出来的，而是都通过做实验来选择最佳方案，值得我们借鉴。 看完后，请完成课后作业：总结采用本去重方案后的SSD读，写流程，包括能去重和不能去重的写。 引用Jonghwa Kim, Dankook University, KoreaChoonghyun Lee, Massachusetts Institute of Technology, USA等作者Deduplication in SSDs: Model and Quantitative Analysis不想错过阿呆的后续精彩文章？长按或扫描下面二维码关注ssdfans就可以了！公司招聘：，SSD芯片设计，固件开发，机器学习相关人才！，RAID、USB、SATA、AHCI、NVME、FTL、文件系统的开发及调试，UFS FW开发
觉得不错，分享给更多人看到
ssdfans 微信二维码
分享这篇文章
ssdfans 最新文章他的最新文章
他的热门文章
您举报文章：
举报原因：
原文地址：
原因补充：
(最多只允许输入30个字)温馨提示！由于新浪微博认证机制调整，您的新浪微博帐号绑定已过期，请重新绑定！&&|&&
渔童使棒钓收纶,芦中鼓枻,樵青使苏兰薪桂,竹里煎茶
LOFTER精选
网易考拉推荐
用微信&&“扫一扫”
将文章分享到朋友圈。
用易信&&“扫一扫”
将文章分享到朋友圈。
从图表一可以看出，15块盘的重复率从7.9%到85.9%不等。我们同时可以看出，在唯一一个NTFS的磁盘中，重复块主要是“零”块。在其它块中的重复块主要是非零块，这表示重复块通常包含有意义的数据。考虑到典型的SSD能够额外配置闪存1-20%的空间，删除占到7.9%到85.9%重复数据能够实质上扩大可用的垃圾回收和负载均衡空间。如果这个努力能够成功，我们能将性能提高到可以与没有额外空间的高端SSD相比的程度。
除了对存储中的数据冗余作了静态分析，我们还收集了I/Otrace来分析三种类别的11个负载的数据读写情况。对每个负载，我们修改linux内核，拦截每个I/O请求，计算每个请求块的哈希值。我们分析了离线的I/Otrace。
&图2显示了每个负载中重复写的比率。可以看出5.8%到28.1%的写是重复的。这一发现证明如果我们能去掉这部分重复写，我们能够有效的减少对flash介质的写操作，进而直接提高耐久性，更不用说减少垃圾回收的次数等间接效果了。
1.3&让FTL内容感知
在上述观察和分析的基础上，我们提出了内容感知的Flash转换层（CAFTL）来整合在SSD消除重复写和数据冗余的功能，从而从设备层提高SSD的寿命。
CAFTL会拦截在SSD设备层过来的写请求，用无碰撞的哈希函数来产生指纹来统计更新数据的内容。通过查询指纹库，CAFTL可以精确而安全的消除对flash介质的重复写。CAFTL同时使用了两层映射机制来结合重复数据，有效的扩大了flash空间，提高了GC效率。为了使计算hash值造成的影响最小，我们还设计了一些加速方法来加速指纹计算。通过这些技术，CAFTL能够有效的减少对flash的写操作，扩大可用flash空间，同时维持高的数据访问表现。
CAFTL是一种增长型机制，而不是对现有FTL设计的完全替代。CAFTL跟其它FTL设计是正交的，例如很好的垃圾回收和负载均衡机制。事实上，现有SSD中的机制为CAFTL提供了很好的基础，让CAFTL对现有SSD架构有着很好的适应。比如间接映射机制很自然的让多个逻辑页与一个物理页相关联非常容易实施；定期扫描机制让垃圾回收和负载均衡也能够实现超行的异步去重；日志似的写机制让恢复删除数据成为可能；最后，闪存的半导体特性让读随机映射的数据不会有高的延迟。
CAFTL也是向下兼容的和便携的。CAFTL是作为SSD的固件在设备层工作，不需要改变主机或者设备的接口。所有的CAFTL设计都是与设备层独立的，对用户不可见。这保证CAFTL成为一种实用的方法，在实际中非常需要。
1.4&我们的贡献
在这篇论文中我们做了如下一些贡献：（1）我们研究了在不同负载下文件系统的重复数据，然后探索了通过重删来提高SSD忍耐力的可能性。（2）我们设计了一种内容感知的FTL，通过减少重复写来提高SSD的寿命。（3）我们设计了一些技术来加速SSD内嵌的重删。（4）我们在DiskSim模拟器中实施的CAFTL，评估了它的表现，证明了CAFTL在提高SSD寿命的功效。
这片论文剩下的部分是这样组织的。在第二部分，我们讨论CAFTL设计中独特的挑战。在第三章，我们介绍了CAFTL和我们的加速方法。我们在第四章展示了我们的绩效评估。第五章讲述了相关工作。最后讨论且总结了这篇论文。
2&技术挑战
CAFTL与通过CAS消除数据冗余有着同样的原则，CAS是用在备份和档案系统中的。可是，我们不能单纯的借用CAS的策略，由于以下4个独特的未处理的挑战。（1）有限的资源。CAFTL是为有着有限存储空间和计算能力的SSD设备设计的，而不是专用的强大的企业服务器。（2）相对低得冗余度。CAFTL主要处理常规文件系统负载，比备份流中的冗余度要笑得多。（3）缺少语义提示。CAFTL工作在设备层，只能看见一系列的逻辑块而没有主机文件系统的语义提示。（4）低开销要求。CAFTL必须为常规的负载获得很好的数据访问表现。
所有这些独特的需求让在SSD中的重删非常特殊，需要CAFTL中独特的方法来解决这些问题。
3.&CAFTL的设计
CAFTL的设计主要为了达到以下三个主要目标。
（1）减少不必要的写操作。通过检查到来的写请求，我们能够发现并减少重复写，从而能够有效的过滤对闪存的不必要写，直接提高SSD的寿命。
（2）扩大可用的闪存空间。通过在SSD中利用间接映射架构我们能够将两个有着同样内容的逻辑块映射到同一个物理块上。节省下来的空间能够用在垃圾回收和负载均衡上，这样间接的提高了SSD的寿命。
（3）保持高的读写绩效。让CAFTL真正有效的一个主要要求就是避免显著的不利表现影响。我们必须让运行时开销最小，维持高的数据访问绩效。
3.1&CAFTL综述
CAFTL通过线内和线外的重删比较来消除重复写和重复数据。线内的重删指的是CAFTL主动的检查到来的数据，在对flash执行写操作之前取消重复写操作。作为一个“尽最大努力”的方案，CAFTL不能保证所有的重复写能够被检测到和立即去掉。因此CAFTL也会定期扫描闪存来合并重复数据。
图三阐释了CAFTL中处理写请求的过程。当SSD收到一个写请求时，
（1）到来的数据首先在设备中的缓冲区暂存；
（2）每个在缓冲区中的更新数据会被哈希引擎计算出一个hash值，也称作指纹；
（3）每个指纹会在指纹库中查询，指纹库维持了已存在于闪存中的数据的指纹；
（4）如果找到了匹配的指纹，这意味着一个现有的数据单元有着相同的内容。这时只需要更新映射表，对flash的写操作会取消；
（5）如果没有发现匹配的指纹，数据会作为常规写写入闪存。
3.2&哈希和指纹库
CAFTL尝试识别和移除重复写和冗余数据，逐字节的比较会非常的慢。通常的做法是使用一个加密的哈希函数，计算出无碰撞的哈希值作为指纹。重复数据通过比较指纹能够检测到。这里我们解释了如何产生和管理指纹。
3.2.1&选择哈希单元
CAFTL使用了一个基于块的重删方法。不同于大多数的CAS系统，CAFTL使用了固定大小的分块方法，这主要有两个原因。首先，可变大小的分块是为分割一个厂的I/O流设计的。在CAFTL中，我们处理一系列的独立请求，它们的大小可能非常小，而且变化很大。因此可变大小的分块对CAFTL而言不适合。其次，在flash中的主要操作单元是页，而SSD内部的管理也主要以页为单位设计。因此，使用固定大小的块来哈希是很自然的选择。
3.2.2&哈希函数和指纹
为了识别重复数据，我们使用了一个无碰撞的哈希函数来汇总页的内容。我们使用的是SHA-1算法。对每个页，我们计算了一个160位的哈希值作为指纹，作为页的元数据存储在flash中。SHA-1算法已经被证明不可能发生碰撞。我们可以通过指纹安全的检测到两个页是否不同。
3.2.3&指纹库
为了通过特殊的指纹来快速的找到物理页，CAFTL维持了一个记忆结构，叫做指纹库。把所有的指纹和相关信息（每个25字节）保存在指纹库中开销显然十分大，而且也没有必要。我们研究了15个磁盘中的指纹的分布，绘制了累积分布函数图图4。
我们可以看出重复指纹的的分布是偏斜的，只有10-20%的指纹是高度重复的。这个发现有两个含义。首先，大多数指纹都是唯一的，没有机会去匹配一个到来的请求。其次，对指纹库的完全搜索会到之后很高的查询延迟，而大多数的查询最后会事无用的。因此，我们只需要存储和查询那些最有可能重复的指纹在记录中。
我们首先讲哈希值空间逻辑的划分为N个段。对一个指纹，f，我们可以将它映射的到段（f&mod&N），哈希函数的随机性保证了指纹的平均分配。每个段包含了一系列桶。每个桶在存储中是一个4KB的页且包含了多个条目，每个条目是一个key-value对，{指纹，（位置，引用）}。160位的指纹索引这些条目，32位的位置信息告诉我们怎么样找到这些数据，8位的引用表示这个指纹的热度信息。每个桶中的条目按他们指纹值的升序排列，这样能够在桶中快速的查找。总的桶数和端数由SSD生产商设计。
指纹库中维持的事最多被引用的指纹。在SSD启动的过程中，当映射表被建立后，指纹库通过查询映射表和元数据信息被重新构造。最初指纹库中没有分配桶，当插入一个指纹时，一个空的桶被分配并与一个相应段的桶表连接。这个桶会维持相应段的指纹直到桶被填满，再分配一个新的桶。我们持续用这种方式分配桶，直到没有可用的空桶。如果发生这种情况，新插入的指纹会替代桶中引用次数最少的指纹。我们使用了循环策略来保证每个段中桶的冷热均匀分配。值得提到的一点是，8位的引用计数对已辨别热的指纹已经够用了，因为大多数指纹的引用计数都小于255（见图4）。我们把引用计数器高于255的指纹视为高度引用而不进一步比较他们热度的差异。就这样，我们可以在内存中包含所有引用次数很多的指纹。虽然我们可能错过鉴别某些没有保存在内存中的重复数据，这种情况通常是很少的。而且我们没有追求完美的线内重删。我们的线外重删能够在之后鉴别出这些重复数据。
选择一个指纹是很简单的。我们计算映射段数并且一个一个扫描相应的桶链表。在每一个桶中，我们使用二分查询来急速桶内查询。但是，对于一个哟该有许多桶的段而言，这种方法还是有待改进的。我们已经设计了三种优化技术来进一步加速指纹查找。
（1）范围查找。在对桶进行二分查找之前，我们首先把指纹和桶内最小的和最大的指纹进行比较。如果指纹超出了范围，我们就马上跳过这个桶。
（2）基于热度的重组。在相关联桶中的指纹可以按照他们的引用数降序重组。把热得指纹移到链表头并且潜在的减少了扫描桶的数量。
（3）桶层次的二分查找。跨桶的指纹可以通过归并排序按照指纹值升序重组。对每一个段，我们都保持了一组指针，指向链表中的桶。我们通过递归选择中间的桶来做范围检查，在桶层次进行二分查找。通过这种方式，我们可以尽快地定位目标桶并且跳过大多数的桶。虽然重组指纹需要执行额外的归并排序，我们的实验显示这些优化可以显著的减少指纹值的比较。在4.3.3节，我们会显示和比较这三种方法的效率。
3.3&间接映射
间接映射是SSD系统结构中的核心机制。SSD使用一组逻辑块地址映射到主机，使用一个内部映射表来追踪逻辑块地址映射到的物理块地址。对CAFTL而言，已存的间接映射机制为重复数据删除提供了基本的架构，避免了设备的擦除。
在另一方面，SSD现存的1对1映射机制不能够直接用到CAFTL中，CAFTL需要N对1的映射，因为2个新的挑战。
（1）当一个物理页移动到另一个位置时（例如，垃圾收集），我们需要能够迅速地识别所有映射到物理页的逻辑页，并且更新指向最新位置的映射入口。
（2）因为一个物理页可以被多个逻辑页共享，这个不能通过垃圾收集器回收，除非所有的引用逻辑页都不再映射到这个物理页，这意味着我们必须能够跟踪逻辑页的引用值。
3.3.1&双层间接映射
图5：间接映射结构图
我们已经设计出了一种新型的间接映射机制来解决前面提出的问题。如图5所示，常用的FTL使用一个单层间接映射，从LBA到PBA。在CAFTL中，我们创建了另一个间接映射层，叫做虚拟块地址（VBA）。VBA是一个虚拟地址名，代表一系列的LBA映射到相同的PBA。在这个双层间接映射结构，我们可以把逻辑页定位到物理页，要么通过LBA-&PBA或者LBA-&VBA-&PBA.
我们在主存中保持了一个主映射表和一个次映射表。在逻辑页唯一时，主映射表把LBA映射到PBA，如果是重复页时，把LBA映射到VBA。我们通过32位比特页地址中非常重要的比特，来区分PBA和VBA。对一个4KB的页，使用剩余的31比特可以映射8192GB存储地址，这对于SSD而言，已经足够大了。次映射表把VBA映射到PBA。每一个入口都通过VBA来索引，并且有两个方面（PBA，引用值）。32位PBA表示物理闪存页，32位引用追踪额外的映射到物理页的逻辑页。只有没有被引用的物理页才能被垃圾回收循环利用。
这个双层间接映射机制有几个优点。
(1)&它显著的简化了重复逻辑页的反向映射的更新。当我们在垃圾回收，重新定位物理页时，我们可以使用它的相关的VBA来快速定位和更新新的位置（PBA），这样显著的避免了在主映射表中搜索所有的引用LBA。
(2)&次映射表可以很小。因为CAFTL处理日常的文件系统负载i，大部分的逻辑页都是唯一的，直接通过主映射表映射。我们也可以运用一个类似于DFTL的方法，通过保持最常用的映射表在贮存中，进一步减少内存需求。
(3)&这样可以吧额外查找开销降到最低。对于唯一的页，直接映射到通常的FTL；对于重复的页，查找操作只需访问一次内存。
3.3.2&闪存中的映射表
&&&&映射关系也保留在闪存中。我们把主次映射表的副本附带日志存放在SSD中。他们在闪存内的结构，被组织成链接物理闪存页的链表。当更新内存中的表（重新把LBA映射到一个新的位置），这个更新记录被日志记录到一个很小的内存缓存中。当这个缓存满了，这个日志记录就会追加到flash日志中。如果断电了，电容（比如SuperCap【46】）可以提供足够的电流把没有写的log刷到日志中，并且保证关键的映射结构在永久存储中。在内存中的表同步到闪存中的时候，日志也被重新初始化。在启动时间，闪存中的表被最先载入到内存中，在日志中log更新被运用到映射表的重组。
3.3.3闪存中的元数据页
&&&&和前面的工作不同，把元数据（比如LBA和指纹）写到额外的物理闪存页中，我们专门保留了一定数量的闪存页，也叫做元数据页，存储元数据并且保留一个元数据页队列来追踪元数据的PBA。剩余的物理页用来存放校验码（ECC）的校验和。如果每一个物理页都和24字节的元数据相关（160位的指纹，32位LBA/VBA），对于一个容量为32GB，以4KB单元作为一个闪存页的SSD，我们需要0.6%的闪存容量来存放元数据，并且需要192KB元数据页队列。这样我们可以把元数据页和数据页分离，这样我们可以轻松的管理物理闪存页的元数据。
3.4&加速方法
&&&&指纹在CAFTL重删中是关键的瓶颈，尤其是当设备缓存大小有限的时候。我们使用了三种有效地技术来减少它对性能的负面影响。
3.4.1&采样hash
&&&&在文件系统负载中，重复写不是常见的。这意味着，我们在指纹上花费的大部分时间是没用的。因此，我们为指纹选择一个样本页，我们使用这个样本指纹来查询指纹库，检查我们是否能够找到一个匹配。如果找到，整个写请求都很可能是重复数据，进一步计算其他页的指纹来确认。否则，我们认为整个请求都不是重复的，在最早时间放弃指纹。通过这种方法，我们可以显著的减少hash开销。
&&&&关键的技术是如何选取一个样本页。这对于CAFTL尤其是个难点，因为CAFTL只能看到连续的块，不能改变任何文件层次的语义提示。我们提倡使用基于内容的样本，我们从每个请求的每个页中选择头四个字节，叫做样本字节。把4个样本字节变成32位数字。我们比较这些值，值最大的页确定为样本页。这个的原理是，如果两个请求带有相似的内容，拥有最大样本字节的页也很可能是相同的。我们故意避免通过hash值来选择样本页，因为在CAFTL中，hash本身会引起高延迟。基于hash值得样本选取方法是不可取的，所以我们直接通过它们原始内容数据，来选取样本页。选择其他字节（图6）来作为样本字节，发现使用头四个字节对于不同的负载而言都表现得最好。
图6：样本字节的四个选取方法
&&&&在样本安装启用的过程中，我们把一个写请求中连续的页分成多个样本单元（比如32页），然后我们从单元中选取一个样本页。样本可以影响重删——样本单元越大，性能会越好但是重删率会越低。我们在4.4.1也研究了单元大小的影响。
3.4.2&轻量级预hash
图7：密集度VS.hash比特
&&&&计算一个轻量级的hash函数带来比较低的计算开销。比如，产生一个32位CRC32hash值比计算160位SHA-1hash值要快10倍。更为重要的是，我们的研究表明，减少hash的长度不会引起冲突率的显著增加。图7表明，使用32位几乎可以达到使用160位一样的密集度。另外，许多SSD集成了专门的ECC引擎来计算校验和，检测错误，这可以加速hash。
我们提出一种技术，叫做轻量级预hash。我们为每一个指纹保留一个额外的32位CRC32hash值。对于每一页，我们首先计算CRC32hash值，然后查询指纹库。如果找到了，这意味着这个页是重复的，使用SHA-1来进一步确认。否则，我们放弃高开销的指纹，把写直接写到闪存。虽然保留CRC32hash值，需要额外的指纹库空间。但是这个显著性能提升是值得的，正如4.4.2节所述。我们也考虑过使用一个Bloom&fileter[12]来做筛选，就像DataDomain文件系统一样[47]，但是发现这个不适用预CAFTL。因为它需要多个hash，当指纹移除的时候，简单的映射不能马上更新。
3.4.3&动态调整
在一些极端的例子中，到来的请求可能会等待前一个请求释放缓存空间。CAFTL提供动态调整来应对这种情况，以提高性能。
&&&&我们设置了最高水位和最低水位来打开或者关闭重删。如果缓存空间使用率达到了最高水位（95%），关闭内嵌的重删，把写尽快地刷到闪存，释放缓存空间。一旦达到最低水位（50%），重启内嵌重删。虽然这个挽救方法会降低重删率，我们可以执行脱机的重删，所以对于保持高性能而言，这是一个可以接受的折中。
3.5&脱机重删
&&&&如前面所示，CAFTL不追求一个完美的内嵌重删，一个内部路由执行脱机指纹识别和脱机重删当设备空闲的说时候。
脱机指纹很简单。扫描元数据页租（3.3.3.节）来查找物理页而不是指纹。如果页找到了，我们把页读出来，计算指纹，然后更新元数据。避免不必要的扫描已经计算指纹的页的元数据。我们在元数据页队列入口使用一个bit位来表示相应元数据页的指纹已经计算过了，然后跳过这些页。
因为内存空间的限制，脱机重删更加复杂。我们采用一个类似于数据库系统中的外部归并排序[39]的方法。假定我们有M个指纹，有用的空间只能支持N个指纹，M&N。我们从头扫描元数据页队列，每次载入N个指纹，在内存中排序，随后存放到闪存中，然后我们载入排序后面的N个指纹。这个过程重复K次（K=M/N）直到所有的指纹都计算完毕。最后我们归并排序这K个指纹块，定位重复的指纹。
脱机的指纹识别和重删可以和垃圾回收一起执行或者独立执行。因为离开重删或者没有计算指纹的页没有坏的影响，这些操作可以在闪存空闲的时候进行，放弃到来的请求，并且这个对前台可察觉的性能影响是很低的。
4&性能评估
4.1&实验系统
&&&&设计的CAFTL的安装和评估基于一个综合的trace驱动的模拟器上。在这一章，我们将要介绍我们的模拟器，trace收集，系统配置。
4.1.1&SSD模拟器
CAFTL是一个运行在SSD控制器上的设备层的设计。我们把它安装在一个精致的SSD模拟器，基于Microsoft&研究SSD扩展[5]，模拟磁盘环境。这个扩展页用于前面的工作[6].
Microsoft的扩展较好的模块化，安装了&FTL大部分部件，比如间接映射，垃圾回收，热点平衡策略和其他。因为现存的版本缺少设备缓存，这个缓存即将成为最近一代SSD的一个标准的部件。我们扩充了现存的部署，加入一个共享的缓存来处理到来的读写请求。当一个写操作到达SSD，它先缓存在缓存中，SSD马上报告主机完成任务。数据计算和闪存操作异步的在后台运行[16]。一旦数据从闪存进入缓存，读请求返回到主机。模拟器采用通用的FTL设计[6]，市场上实际SSD可以邮其他特性。
4.1.2.SSD配置
&&&&在我们的实验中，我们使用默认的配置，除非表示了其他。表1给出了一个主要配置参数的清单。
&&&&表2给出了我们实验中的参数延迟。对于闪存，使用默认的延迟。对于hash延迟，首先把hash函数代码交叉编译在ARM平台，运行在SimpleScalar-ARM模拟器[4]中，计算出运行一个hash函数总共的循环数。我们在设备上运行一个类似于ARM&CortexR4[8]的处理器，尤其针对高性能的嵌入式设备，包括存储。基于它的数据表，ARM处理器主频从304MHz到934MHz[8]，通过把处理器主频除以周期数，我们可以估算hash4KB页的延迟。根据我们与SSD厂家[3]进行沟通的结果可知，高频的处理器（高于600MHz），比如Cortex处理器，在高速存储器中将变得越来越普遍。改变冗余的计算能耗是一个值得进一步研究的课题。
4.1.3负载和trace收集
&&&&我们选择了11中负载，分别从三个方面来收集他们的数据访问踪迹（trace）。
（1）桌面电脑（d1，d2）——典型的办公室负载。比如上网，发邮件，编辑文字等等。负载分别运行12和19个小时。特性是不规则的空闲和小文件读写。
（2）Hadoop（h1-h7）——我们在Hadoop分布式系统平台运行7个TCP-H数据仓库请求（请求1，6,11,14,15,16,20），规模因子为1[2]。这些负载运行了2-40分钟，产生了密集的大文件写。
（3）事件（t1，t2）——我们在PostgreSQL8.4.3数据库系统上运行TPC-C负载（1-3个仓库，10个终端）。这两个负载分别运行30分钟和4小时，特性是密集的鞋操作。
&&&Trace在DELL&Dimension3100工作站上收集。该工作站配备有Intel&Pentium&4.3.0GHz处理器，3GB主存，160GB&7200RPM&Seagate&硬盘驱动。我们使用Ubuntu9.10，挂载Ext3文件系统。我们修改了2.6.32内核代码来中断每一个I/O请求，为请求中每4KB页计算hash值作为指纹。这些指纹和其他请求信息（比如偏移，类型），通过网络控制器[35]一起转移到另外的机器。这避免了追踪过程中可能引起的中断。收集的trace文件脱机分析，用来驱动模拟器，进行实验评估。
4.2&重删的效率
&&&&CAFTL为了减少重复写，扩展闪存空间。在这一章，我们使用两租实验来展示CAFTL的重删的效率。在两组实验中，我们使用一个带有934MHz处理器和16MB缓存的SSD。
4.2.1减少重复写
CAFTL&通过内嵌的重删识别和减少重复写。把所有的写页请求表示为n，所有的实际写到闪存的页表示为m，重删率表示为(n-m)/n。
&&&&图8表示运行在CAFTL上的11种负载的重删率。在这个图中，脱机表示最优案例，当所有的trace都检查，脱机重删。我们也展示没有样本和有128KB（32页）样本CAFTL，分别表示为no-sampling和128KB。
如图8所示，重删依靠与工作负载。在11个负载种，重删写的概率从5.8%（t1）到28.1%（h6）。没有样本CAFTL的重删率为4.6%（t1）到24.2%（h6）。和最优案例（脱机）相比，CAFTL识别了86.2%的重复写。当采用128KB的样本时，CAFTL取得了一个稍微低点但是合理的重删率。在4.4.1节中，我们会给出更多有关样本单元大小影响的细节分析。
4.2.2&扩充闪存空间
&&&&除了直接删除重复写，CAFTL还减少了闪存被占用的空间，增加了用于垃圾回收和热度平衡的可用空间。
&&&&图9表示了在每一个擦除块单元扩充闪存空间的比例，相比于基准线（没有CAFTL），没有样本（no-sampling）和有样本（128KB）。
如图所示，CAFTL可以为11种负载最高节省31.2%（h1）的闪存块。最差的案例是h2和h5，几乎没有空间节省。这是因为这两种负载相对较小，所有的占用的擦除块只有176，虽然写的页总数减少了16.6（h2）和15%（h5），但是节省的空间很小。
4.3性能影响
为了使CAFTL在实际工作中更为高效，必须保持高性能，减少负面影响。我研究了三种主要影响性能的因素。缓存大小，hash速度，和指纹搜索。加速方法没有应用到实验中。
4.3.1缓存大小
在图10中，我们不同缓存大小（2MB到16MB）读写延迟的增加。我们对比了CAFTL和基准线（没有CAFTL）。在实验中，我们给SSD配置了934MHz的处理器。我们可以看到，有小缓存空间（2MB）的SSD，读写延迟增加了34%（t1）。中等大小缓存（8MB），延迟减少为4.5%。对于一些负载（d2,h3,h5,h7,t1,t2），轻微的性能提升（0.2%-0.5%），因为CAFTL移动了不必要的写，减少了被闪存写操作阻塞的可能性。这种情况，小缓存对性能有负面影响，我们将会通过4,4节的加速方法来解决这个问题。
4.3.2&hash速度
计算指纹是一项耗时影响访问性能的工作。Hash速度取决于处理器的能力。使用一个更为强大的处理器可以有效地减少处理页和产生指纹的延迟。为了研究hash速度对性能的影响，把处理器的频率设置为304MHz到934MHz，基于Cortex数据表[8]。我们把SSD的缓存设置wie16MB，图11显示了相对于基准线（没有CAFTL）的读延迟的增加。我们没有观察到写延迟的增加，因为绝大多数的写都要放在缓存中。
在图11中，大部分的负载对hash速度都是不敏感的。在304MHz处理器下，性能的损耗少于8.5%（t2），有更多的密集型的更大的写。在934MHz中，性能损耗基本观察不到（最高为0.5%）。这有两个原因。
（1）设备上的16MB缓存吸收的大部分的写操作并且提供了足够的空间来处理读操作
（2）读请求具有比写更高的优先级，减少了关键路径的明显的延迟。
这些优化措施使得读操作对hash速度不敏感，减少了明显的延迟。同时，如果使用专门的hash引擎，hash延迟可以进一步降低。
4.3.3指纹查找
&&&&我们提出了3中技术来加速指纹查找。图12显示了相对于基准线，指纹减少的比例。指纹库被设置为256段，为每一个负载保存指纹。使用范围检查可以有效地减少23.7%（t2）指纹比较。但是，基于热度重组只能提供很少的性能提升（少于1%），因为它必须加速重复指纹的查找，这个相对而言不是一个经常性事件。桶级别的二分查找可以显著的减少每次查找的比较次数。在d2中，桶级二分查找可以有效地减少85.5%的平均比较次数。因此，我们建议运用桶级别的二分查找和范围检查来加速指纹查找。
4.4&加速方法
&&&&对于设备缓存很小的情况下，hash带来用户能够感知的高计算延迟。我们提出了3种加速指纹的技术。这一章，我们将展示每种单一技术的效率和结合在一起的效率。配置SSD一个934MHz的处理器和一个2MB的小缓存。
&&&&如图13和14所示，样本可以显著的提高性能。随着样本单元的增大，更少的指纹需要计算，多种形式的读写延迟的减少。比如，h7读的速度加速了94.1倍，写的速度加速了3.5倍，因为等待缓存的时间太长了。同时重删率只减少了18%到15.4%。考虑到这么重要的加速，损失一点重删率是可以接受的。在t1中观察到最大的加速比，110.6倍（读），重删率从4.6%降低到1.3%。这主要是因为负载具有很低的重复率，选取正确样本页的可能性页相对低。
4.4.2轻量级的预hash
&&&&在进行高开销的指纹识别之前，轻量级的预hash使用一个快速地CRC32hash函数来筛选大部分不可能重复的页。
&&&&图15表示了，和没有预hash的CAFTL相比，使用CRC32预hash带来的读写加速比。只有预hash在这里工作。在最好的例子（t1）中，预hash可以减少延迟，最大因子达到148.3倍读和3.9倍写。这是因为，如前面所述，这个负载是写密集的，有很长的等待队列，是的队列影响尤其明显。和取样类似，写的提升效果相对不明显，因为缓存吸收了低延迟的写，减少了加速写的效果。同时，我们也发现没有明显区别的重删率。这个和我们图7的分析也是一致的。
4.4.3动态调整
&&&&CAFTL提供了动态调整功能来自动的关闭和打开内嵌的重删，依据设备缓存的使用情况。设置最高水位95%（关闭），最低水位50%（打开）。图16显示了读写加速比。t1达到了200.6的加速比。一些负载（h1-h5）没有效果，因为他们I/O密集度较小。对于其他的负载，我们观察到了2.1到94.6的加速比。
4.4.4&整合效果
&&&&图17显示，把三个加速技术都开启，相对于基准线（没有CAFTL）的读写延迟的加速比和相应的重删率。通过结合这三种技术，我们在只有2MB设备缓存的情况下，几乎完全解决了性能损害的问题。在平均时间，我们的重删率达到了199.%。
5 其他相关工作
&&&&基于SSD的闪存吸引了学术和工业的兴趣。在闪存和SSD方面，有大量的研究工作[6,9,13,15–18,20,23,26–29,31,34,37,38,42,44]。关注耐久度，早期的工作主要是在设计垃圾回收和热点平衡策略上。一个调查[21]总结了这些技术。我们只展示与我们论文相关的一些工作。
最近Grupp等[22]展示了以实验为依据，有关闪存性能，功耗和可靠度的研究。他们的结果显示闪存尤其是MLC设备，当设备达到最高耐久度之后，甚至之前，将会显现出很高的错误率，这使得高密度SSD在商用系统中是一个很艰难的决定。另一份报告[13]研究了USB闪存驱动耐久度，得出了更为乐观的结论，闪存芯片的耐久度比预期的要好，但是整个设备的耐久度和FTL的设计密切相关。一个基于耐久度的模型已经展现出来[33]。这些研究提供了有关闪存和小容量闪存设备寿命所需要的信息。但是，目前为止，现在SSD耐久度的技术没有在相关领域得到证明[10]。
有关SSD早期的研究主要关注性能，一些最近的研究已经开始关注可靠性。不同的RAID[9]尝试提高基于SSD&的RAID存储可靠性，把奇偶校验码不均匀的分布在SSD中来减少相关多设备的错误可能性。Griffin[42]通过保持一个日志结构的HDD缓存，定期转移缓存数据，延长了SSD的寿命。最近的一个工作[36]，在可耗减的存储系统中，把写次数和存储空间视为有限的资源，并且建议属于耗减给系统中的用户，比如云计算。ChunkStash[19]使用闪存来加速内嵌存储重删的索引查找。另外一个工作[43]提出，整合相变改变内存到SSD中提升性能，功耗和寿命。我们的研究已经通过在设备层减少重复写，减少重复数据
来延长SSD的使用寿命，这是一个更为通用的方法。
6&总结和讨论
对于商业系统中广泛安装的SSD而言，延长SSD使用寿命是非常重要的。在这篇论文中，通过减少重复写操作和冗余数据，我们可以在宝石高速数据访问性能的同时，有效地扩展SSd的使用寿命。
一个潜在的CAFTL考虑是设备中的RAM缓存的易失性——缓存数据在断电的时候会丢失。但是，这个考虑对于SSD不是新的。一个硬盘驱动也可以由设备缓存，但是它提供给用户的是一个选择（比如使用sdparm&工具），根据用户需要来简单的启用/禁止缓存。类似的，如果需要，用户可以选择禁用内嵌的重删和SSD里面的缓存，脱机的重删可以照常有效。
虽然我们尝试减少内存使用，但是，相对于传统的FTL而言，CAFTL需要更多的空间来存放指纹和二级映射表。根据我们和SSD生产厂家交流[3]得结果，内存价格只占所有产品中很小的一部分，最贵的部件是闪存。这样我们考虑这样的交易是值得的，扩充闪存空间和SSD的使用寿命。如果预算允许的话，我们建议吧所有的指纹库都放在主存中，这不仅能够提高重删率，也能够简化设计。
进一步提高是有可能的。一个是放松“一次运行”的需求限制。根据规范说明，在干净的擦除块中，每一个闪存页都只能运行（写）一次。在实际工作中，闪存芯片可以允许多个程序写到一个页，“程序干扰”的概率相当低[7]。我们改变这种特性来简化许多的设计。例如，我们可以写多个版本的LBA/VBA和指纹到额外的物理页空间，这样可以极大地除去元数据页的必要。另外一个考虑是整合字节定位的持续内存（比如PCM）到SSD中来保持元数据，这样可以除去很多设计复杂度。我们也考虑增加内嵌的压缩到SSD中来优化设备中的高速处理器。这个可以进一步扩充有用的闪存空间，但是可能会需要更多的改变FTL设计，这个是我们未来的工作。
SSD技术变得越来越成熟，表现出满意的性能。我们相信，SSD的耐久度问题，尤其是高密度的MLC&SSD&有许多新的研究机会，应该取得研究者更多的重视。
我们感谢我们的来自VMware的导师Dr.&Christos&Karamanolis和提供指导性评论的匿名评论者。我们也谢谢我们的同时Bill&Bynum，读这篇论文还有他的建议。这个研究收NSF资助，编号CCF-0620152,&CCF-072380和&CCF-0913150。
[1]&FIPS&180-1,&Secure&Hash&Standard,&April&1995.
[2]&Hadoop.&http://hadoop.apache.org/,&2010.
[3]&Personal&communications&with&an&SSD&architect,&2010.
[4]&SimpleScalar&4.0.&http://www.simplescalar.com/v4test.html,2010.
[5]&SSD&extension&for&DiskSim&simulation&environment.
[6]&AGRAWAL,&N.,&PRABHAKARAN,&V.,&WOBBER,&T.,&DAVIS,J.&D.,&MANASSE,&M.,&AND&PANIGRAHY,&R.&Design&tradeoffs for&SSD&performance.&In&Proceedings&of&USENIX’08&(Boston,MA,&June&2008).
[7]&ANDERSEN,&D.&G.,&AND&SWANSON,&S.&Rethinking&flash&in&the data&center.&In&IEEE&Micro&(July/Aug&2010).
[8]&ARM.&Cortex&R4.&,&2010.
[9]&BALAKRISHNAN,&M.,&KADAV,&A.,&PRABHAKARAN,&V.,&AND MALKHI,&D.&Differential&RAID:&Rethinking&RAID&for&SSD&Reliability.
In&Proceedings&of&EuroSys’10&(Paris,&France,&April&2010).
[10]&BARROSO,&L.&A.&Warehouse-scale&computing.&In&Keynote&in&the SIGMOD’10&conference&(Indianapolis,&IN,&June&2010).
[11]&BHAGWAT,&D.,&ESHGHI,&K.,&LONG,&D.&D.&E.,&AND&LILLIBRIDGE,M.&Extreme&binning:&Scalable,&parallel&deduplication&for
chunk-based&file&backup.&In&Proceedings&of&MASCOTS’09&(London,UK,&September&2009).
[12]&BLOOM,&B.&H.&Space/time&trade-offs&in&hash&coding&with&allowable errors.&In&Communications&of&the&ACM&(1970),&vol.&13(7),pp.&422–426.
[13]&BOBOILA,&S.,&AND&DESNOYERS,&P.&Write&endurance&in&flashdrives:&Measurements&and&analysis.&In&Proceedings&of&FAST’10
(San&Jose,&CA,&February&2010).
[14]&BUCY,&J.,&SCHINDLER,&J.,&SCHLOSSER,&S.,&AND&GANGER,&G.DiskSim&4.0.&http://www.pdl.cmu.edu/DiskSim,&2010.
[15]&CHEN,&F.,&JIANG,&S.,&AND&ZHANG,&X.&SmartSaver:&Turning flash&drive&into&a&disk&energy&saver&for&mobile&computers.&In
Proceedings&of&ISLPED’06&(Tegernsee,&Germany,&October&2006).
[16]&CHEN,&F.,&KOUFATY,&D.&A.,&AND&ZHANG,&X.&Understanding intrinsic&characteristics&and&system&implications&of&flash
memory&based&solid&state&drives.&In&Proceedings&of&SIGMET-RICS/Performance’09&(Seattle,&WA,&June&2009).
[17]&CHEN,&F.,&LEE,&R.,&AND&ZHANG,&X.&Essential&roles&of&exploiting internal&parallelism&of&flash&memory&based&solid&state&drives in&high-speed&data&processing.&In&Proceedings&of&HPCA’11&(San Antonio,&TX,&Feb&2011).
[18]&CHEN,&S.&FlashLogging:&Exploiting&flash&devices&for&synchronous logging&performance.&In&Proceedings&of&SIGMOD’09
(Providence,&RI,&June&2009).
[19]&DEBNATH,&B.,&SENGUPTA,&S.,&AND&LI,&J.&ChunkStash:&Speeding up&inline&storage&deduplication&using&flash&memory.&In&Pro-
ceedings&of&USENIX’10&(Boston,&MA,&June&2010).
[20]&DIRIK,&C.,&AND&JACOB,&B.&The&performance&of&PC&solid-state disks&(SSDs)&as&a&function&of&bandwidth,&concurrency,&device,architecture,&and&system&organization.&In&Proceedings&of&ISCA’09(Austin,&TX,&June&2009).
[21]&GAL,&E.,&AND&TOLEDO,&S.&Algorithms&and&data&structures&for flash&memories.&In&ACMComputing&Survey’05&(2005),&vol.&37(2),
pp.&138–163.
[22]&GRUPP,&L.&M.,&CAULFIELD,&A.&M.,&COBURN,&J.,&SWANSON,S.,&YAAKOBI,&E.,&SIEGEL,&P.&H.,&AND&WOLF,&J.&K.&Characterizing
flash&memory:&Anomalies,&observations,&and&applications.In&Proceedings&of&MICRO’09&(New&York,&NY,&December&2009).
[23]&GUPTA,&A.,&KIM,&Y.,&AND&URGAONKAR,&B.&DFTL:&a&flash translation&layer&employing&demand-based&selective&caching&of page-level&address&mappings.&In&Proceedings&of&ASPLOS’09(Washington,&D.C.,&March&2009).
[24]&GUPTA,&D.,&LEE,&S.,&VRABLE,&M.,&SAVAGE,&S.,&SNOEREN,A.&C.,&VARGHESE,&G.,&VOELKER,&G.&M.,&AND&VAHDAT,&A.Difference&Engine:&Harnessing&memory&redundancy&in&virtual machines.&In&Proceedings&of&OSDI’08&(San&Diego,&CA,&2008).
[25]&INTEL.&Intel&X25-E&extreme&SATA&solid-state&drive.http://www.intel.com/design/flash/nand/extreme,&2008.
[26]&JOSEPHSON,&W.&K.,&BONGO,&L.&A.,&FLYNN,&D.,&AND&LI,&K. DFS:&A&file&system&for&virtualized&flash&storage.&In&Proceedings of&FAST’10&(San&Jose,&CA,&February&2010).
[27]&KAWAGUCHI,&A.,&NISHIOKA,&S.,&AND&MOTODA,&H.&A&flashmemory
based&file&system.&In&Proceedings&of&USENIX&Winter(New&Orleans,&LA,&Jan&1995),&pp.&155–164.
[28]&KIM,&H.,&AND&AHN,&S.&BPLRU:&A&buffer&management&scheme for&improving&random&writes&in&flash&storage.&In&Proceedings&of
FAST’08&(San&Jose,&CA,&February&2008).
[29]&LEE,&S.,&AND&MOON,&B.&Design&of&flash-based&DBMS:&An&inpage logging&approach.&In&Proceedings&of&SIGMOD’07&(Beijing,China,&June&2007).
[30]&LILLIBRIDGE,M.,&ESHGHI,&K.,&BHAGWAT,&D.,&DEOLALIKAR,V.,&TREZISE,&G.,&AND&CAMBLE,&P.&Sparse&indexing:&Large scale,&inline&deduplication&using&sampling&and&locality.&In&Pro-ceedings&of&FAST’09&(San&Jose,&CA,&2009).
[31]&MAKATOS,&T.,&KLONATOS,&Y.,&MARAZAKIS,&M.,&FLOURIS,M.&D.,&AND&BILAS,&A.&Using&transparent&compression&to&improveSSD-based&I/O&caches.&In&Proceedings&of&EuroSys’10(Paris,&France,&April&2010).
[32]&MENEZES,&A.&J.,&V.&OORSCHOT,&P.&C.,&AND&VANSTONE,&S.&A.Handbook&of&applied&cryptography.&In&CRC&Press&(1996).
[33]&MOHAN,&V.,&SIDDIQUA,&T.,&GURUMURTHI,&S.,&AND&STAN,M.&R.&How&I&learned&to&stop&worrying&and&love&flash&endurance.In&Proceedings&of&HotStorage’10&(Boston,&MA,&June&2010).
[34]&NARAYANAN,&D.,&THERESKA,&E.,&DONNELLY,&A.,&ELNIKETY,S.,&AND&ROWSTRON,&A.&Migrating&enterprise&storage&to&SSDs:analysis&of&tradeoffs.&In&Proceedings&of&EuroSys’09&(Nuremberg,Germany,&March&2009).
[35]&NETCONSOLE.&http://www.kernel.org/doc/Documentation/&networking/netconsole.txt,&2010.
[36]&PRABHAKARAN,&V.,&BALAKRISHNAN,&M.,&DAVIS,&J.&D.,&AND WOBBER,&T.&Depletable&storage&systems.&In&Proceedings&of HotStorage’10&(Boston,&MA,&June&2010).
[37]&PRABHAKARAN,&V.,&RODEHEFFEER,&T.&L.,&AND&ZHOU,&L.Transactional&flash.&In&Proceedings&of&OSDI’08&(San&Diego,&CA,December&2008).
[38]&PRITCHETT,&T.,&AND&THOTTETHODI,M.&SieveStore:&A&highlyselective,ensemble-level&disk&cache&for&cost-performance.&In Proceedings&of&ISCA’10&(Saint-Malo,&France,&June&2010).
[39]&RAMAKRISHNAN,&R.,&AND&GEHRKE,&J.&Database&managment
systems.&McGraw-Hill,&2030.
[40]&RIVEST,&R.&The&MD5&message-digest&algorithm.
http://www.ietf.org/rfc/rfc1321.txt,&April&1992.
[41]&ROSENBLUM,&M.,&AND&OUSTERHOUT,&J.&K.&The&design&and implementation&of&a&log-structured&file&system.&In&ACM&Transac-tions&on&Computer&Systems&(1992),&vol.&10(1):26-52.
[42]&SOUNDARARAJAN,&G.,&PRABHAKARAN,&V.,&BALAKRISHNAN,M.,&AND&WOBBER,&T.&Extending&SSD&lifetimes&with&disk-basedwrite&caches.&In&Proceedings&of&FAST’10&(San&Jose,&CA,&February2010).
[43]&SUN,&G.,&JOO,&Y.,&CHEN,&Y.,&NIU,&D.,&XIE,&Y.,&CHEN,&Y.,AND&LI,&H.&A&hybrid&solidstate&storage&architecture&for&the&performance,energy&consumption,&and&lifetime&improvement.&InProceedings&of&HPCA’10&(Bangalore,&India,&Jan&2010).
[44]&TSIROGIANNIS,&D.,&HARIZOPOULOS,&S.,&AND&SHAH,&M.&A.Query&processing&techniques&for&solid&state&drives.&In&Proceed-ings&of&SIGMOD’09&(Providence,&RI,&June&2009).
[45]&UNGUREANU,&C.,&ATKIN,&B.,&ARANYA,&A.,&GOKHALE,&S.,RAGO,&S.,&CALKOWSKI,&G.,&DUBNICKI,&C.,&AND&BOHRA,A.&HydraFS:&A&high-throughput&file&system&for&the&HYDRAstor content-addressable&storage&system.&In&Proceedings&of&FAST’10(San&Jose,&CA,&2010).
[46]&WIKIPEDIA.&Battery&or&supercap.&&or&SuperCap,&2010.
[47]&ZHU,&B.,&LI,&K.,&AND&PATTERSON,&H.&Avoiding&the&disk&bottleneck in&the&data&domain&deduplication&file&system.&In&Proceedings of&FAST’08&(San&Jose,&CA,&2008).
阅读(1633)|
用微信&&“扫一扫”
将文章分享到朋友圈。
用易信&&“扫一扫”
将文章分享到朋友圈。
历史上的今天
loftPermalink:'',
id:'fks_',
blogTitle:'【译】CAFTL:一种延长SSD闪存耐久度的识别内容的FTL',
blogAbstract:'
《CAFTL:一种延长SSD闪存耐久度的识别内容的FTL》
《CAFTL: A Content-Aware Flash Translation Layer Enhancing the Lifespan of Flash Memory based Solid State Drives》
Feng&Chen\x03&Tian&Luo&Xiaodong&Zhang
Dept.&of&Computer&Science&&&Engineering
The&Ohio&State&University',
blogTag:'',
blogUrl:'blog/static/0',
isPublished:1,
istop:false,
modifyTime:9,
publishTime:0,
permalink:'blog/static/0',
commentCount:0,
mainCommentCount:0,
recommendCount:0,
bsrk:-100,
publisherId:0,
recomBlogHome:false,
currentRecomBlog:false,
attachmentsFileIds:[],
groupInfo:{},
friendstatus:'none',
followstatus:'unFollow',
pubSucc:'',
visitorProvince:'',
visitorCity:'',
visitorNewUser:false,
postAddInfo:{},
mset:'000',
remindgoodnightblog:false,
isBlackVisitor:false,
isShowYodaoAd:false,
hostIntro:'渔童使棒钓收纶,芦中鼓枻,樵青使苏兰薪桂,竹里煎茶',
hmcon:'1',
selfRecomBlogCount:'0',
lofter_single:''
{list a as x}
{if x.moveFrom=='wap'}
{elseif x.moveFrom=='iphone'}
{elseif x.moveFrom=='android'}
{elseif x.moveFrom=='mobile'}
${a.selfIntro|escape}{if great260}${suplement}{/if}
{list a as x}
推荐过这篇日志的人：
{list a as x}
{if !!b&&b.length>0}
他们还推荐了：
{list b as y}
转载记录：
{list d as x}
{list a as x}
{list a as x}
{list a as x}
{list a as x}
{if x_index>4}{break}{/if}
${fn2(x.publishTime,'yyyy-MM-dd HH:mm:ss')}
{list a as x}
{if !!(blogDetail.preBlogPermalink)}
{if !!(blogDetail.nextBlogPermalink)}
{list a as x}
{if defined('newslist')&&newslist.length>0}
{list newslist as x}
{if x_index>7}{break}{/if}
{list a as x}
{var first_option =}
{list x.voteDetailList as voteToOption}
{if voteToOption==1}
{if first_option==false},{/if}&&“${b[voteToOption_index]}”&&
{if (x.role!="-1") },“我是${c[x.role]}”&&{/if}
&&&&&&&&${fn1(x.voteTime)}
{if x.userName==''}{/if}
网易公司版权所有&&
{list x.l as y}
{if defined('wl')}
{list wl as x}{/list}