基于布隆过滤器的新型混合内存架构磨损均衡策略

张 震，付印金，胡谷雨

(1.陆军工程大学 指挥控制工程学院，南京 210007； 2.73610部队，南京 210007)(*通信作者电子邮箱yinjinfu@gmail.com)

0 引言

随着信息技术的高速发展，大数据所催生的内存计算和处理器核数的不断增加对内存的速度、容量、功耗和可靠性的需求都达到前所未有的新高度。在过去数十年期间，动态随机存取存储器(Dynamic Random Access Memory, DRAM)作为主要主存储器被广泛应用在移动终端和大规模计算系统中。然而，现代计算机系统对大容量、低功耗、扩展性强的高性能内存的需求不断增加，高静态功耗、容量提升达到上限、扩展性有限的DRAM面临着众多新型存储技术的挑战。

新型非易失性存储器(NonVolatile Memory, NVM)的出现为打破这些限制提供契机，相变存储器(Phase Change Memory, PCM)被视为最有希望替代DRAM成为下一代的主存储器。PCM具有非易失性、低静态功耗、扩展性强等特性，但同时PCM单个存储单元的写寿命有限，访问性能也逊色于DRAM[1]，因此，PCM还无法完全取代DRAM单独作为主存使用。

为了解决PCM访问时延以及耐受性两方面的问题，研究者从存储层次结构方面提出两种基于PCM和DRAM的混合存储架构。第一种使用DRAM和PCM共同作为主存，通过数据分配以及数据迁移技术发挥DRAM的读写优势，同时减少PCM的写操作次数[2-4]；第二种架构使用DRAM作为PCM的缓存来掩盖PCM I/O性能以及写耐受性的不足[5-7]。两种架构各有优势，相比之下第二种架构更适合解决PCM写寿命受限的问题。

如何减少PCM写次数以及更好地均匀化写操作分布是设计高效磨损均衡算法必须考虑的两个因素。已有研究者提出使用DRAM缓存技术来减少PCM的写操作次数[4]，同时通过数据交换[2]和移位技术[5,8]来实现数据块内部和不同数据块之间的磨损均衡。前者将修改频繁的数据块缓存在DRAM，把修改较少或者访问不频繁的数据块淘汰至PCM，能够一定程度上减少写访问密集型应用对某些存储单元的磨损次数。数据移位和交换技术通过改变逻辑地址到物理地址映射关系的方式，将磨损严重的存储单元的写操作均匀到磨损较轻的存储单元，实现不同粒度下的写操作均匀分布。

现有的基于PCM的磨损均衡算法能够一定程度上延长PCM的写寿命，但是依然存在以下几点问题。1)已有的以DRAM作为缓存减少PCM写次数的设计方法只关注如何优化脏数据页的淘汰策略，并不能利用数据块的读写倾向性避免PCM上不必要的写操作；2)采用确定性映射机制的静态磨损均衡策略不能有效处理恶意访问攻击情况下的写操作均匀分布，替换页的选择缺乏随机性的保护；3)以单个页面为粒度的磨损均衡操作在空间局部性较强的应用场景中效率低下。

针对上述问题，本文提出一种在新型DRAM缓存+DRAM/PCM混合主存架构下基于布隆过滤器(Bloom Filter, BF)的两层动态磨损均衡策略:第一层在新型混合存储架构下通过最近最少使用(Least Recently Used, LRU)和带有时间变化的最不经常使用(Least Frequenctly Used with Aging, LFU-Aging)相结合的缓存算法减少PCM写操作;第二层则是在PCM内部实现写操作均匀分布的组间磨损均衡算法。本文工作主要包括：

1)设计一种全新的混合存储架构，使用DRAM作为cache，PCM和DRAM统一编址共同作为主存。DRAM cache在LRU和LFU-Aging的两级缓存策略的基础上对每个数据块的读写信息进行统计，当缓存写满时根据数据块的读写倾向性写回到相应的主存介质。其中，DRAM存储被淘汰的修改较为频繁的数据块，PCM存储修改较少的干净数据块，减少PCM写操作的同时通过读写热度区分避免脏数据块被写回到PCM。

2)基于BF实现低空间开销、高查询速度的磨损均衡算法。不同于传统的动态磨损均衡算法中每个数据块对应一个计数器来跟踪写次数，本文利用BF技术将所有数据块的写操作情况映射到一个开销更小的计数器数组当中，并且通过判断数据块所映射的计数器数值大小判断磨损情况。同时，BF有助于更快地查找需要进行磨损均衡的数据块以及选择替换对象。

3)针对现有算法在处理强空间局部性的数据集时出现的性能瓶颈，设计一种组间磨损均衡策略。算法以每128 MB的连续地址空间为一个分组，当记录分组写次数的BF计数器的数值超过阈值时进行组间磨损均衡，实现不同分组之间的写操作均匀分布。

1 相关工作

PCM的每个单元只能承受107～109次[9]的写操作，特别是在连续写的情况下，存储单元的耐受性将受到严重制约。研究者从存储系统的体系结构、缓存优化策略、数据迁移等方面对如何提高PCM耐受性作出了广泛且深入的研究。提升PCM写寿命最直接的方式就是减少对存储单元的写操作次数，而磨损均衡处理策略是延长存储器使用寿命的另一个重要方法。现有的磨损均衡策略可以分为两个方向：减少写操作以及均匀化写操作分布。

1.1 DRAM缓存技术

DRAM作为PCM缓存的二级主存系统模型是混合主存研究的一个重要方向，这种架构一方面为系统提供大容量的存储空间，另一方面可以解决由PCM本身读写延迟以及写寿命缺陷带来的系统性能下降问题。使用DRAM作为PCM缓存的方式能够将修改频繁的数据尽可能保存在DRAM中，减少这部分数据对主存造成的频繁写伤害，同时可以掩盖PCM写性能的不足。

Park等[4]提出脏数据保持策略，将修改频繁的脏数据在DRAM中保留更长的时间；Qureshi等[5]提出Lazy-Write的写操作策略，当页面被逐出DRAM且该页被修改过时才写入PCM；Ferreira等[7]针对PCM读写不均衡的特性，通过对页面设定优先级的方式把低功耗和低时延读操作集中的页面写回到PCM来减少主存的写数量；Mladenov等[10]根据空间局部性原理以及改进的Lazy-Write算法将DRAM中最早处理过的请求数据写回PCM，再将新数据写入DRAM中。

现有的DRAM缓存技术通过优化缓存策略能够有效减少修改频繁的数据对PCM造成的写伤害，但被写回的脏数据仍然会增加PCM写操作数量，同时这部分数据所表现出来的写倾向性会在将来增加PCM磨损均衡操作的负担。此外，不同算法在缓存大小的设置、何时将数据写回到PCM、替换页的选择等方面不尽相同，这些问题也将影响PCM耐久性提升的效果。

1.2 均匀化写操作分布技术

根据是否记录数据的访问热度，已有的均匀写操作分布的磨损均衡算法可以分为动态和静态两类。动态磨损均衡策略跟踪数据的写频率，当数据块的写次数超过设定的阈值时选择磨损情况良好的数据块作为替换对象，以此来均衡不同数据块之间的写次数；静态磨损均衡策略通过周期性地变换逻辑地址到物理地址的映射关系来实现局部或者全局的写操作均匀分布。

Dhiman等[2]设计了一种软硬件结合的混合内存系统—PDRAM，通过记账(book keeping)硬件技术来存储PCM页面粒度的写操作频率，同时利用软件手段维护PCM的写访问次数表；Park等[11]提出一种基于segment的数据交换策略PFFS，一旦写操作次数最大的分块与最少的分块之间的写次数差距超过一定的阈值就进行数据交换操作；Zhou等[12]通过限制数据段被频繁选中进行数据交换来避免某一个段被过多写访问；Park等[13]提出多级数据交换技术动态地平衡不同页面之间的写次数；Dong等[14]通过监测写数据流量以及存储单元承受写操作的情况来控制损耗均衡的力度，当数据更新分布较为均匀时提高数据交换的门槛，当写请求访问集中在少数存储块时降低数据交换的条件来触发更多的损耗均衡操作；Yun等[15]提出基于BF的磨损均衡算法，利用BF的特性判断数据块的冷热情况进行数据交换。

静态磨损均衡策略的优势在于使用有限的空间记录写访问信息，但是周期性的数据移位(data shifting)操作在写请求本身分布较为均匀的应用场景下会增加不必要的写操作，同时确定的地址映射机制不能应对特殊数据流的恶意攻击。动态磨损均衡策略主要针对页间的数据交换(data swapping)操作，该类方法需要通过一定的空间开销记录数据块的磨损情况，能够更加准确地定位到需要执行磨损均衡的数据块，同时使得PCM达到更长的使用寿命。如何降低记录写次数的空间开销、有效避免恶意攻击、以怎样的粒度进行数据交换和移位都是在设计磨损均衡算法时必须考虑的因素。

2 新型混合存储架构

图1(a)、(b)是两种常见的混合存储架构，为了解决PCM写耐受性的问题，前者利用DRAM作为缓存，将修改频繁的数据缓存在DRAM中以减少对主存的写操作数量，而后者使用DRAM和PCM共同作为主存，通过预测数据的读写倾向性进行页面迁移操作，将写频繁的页面保存在DRAM来提高PCM的使用寿命。DRAM缓存策略的主要目标是减少PCM上的写操作，为此，许多已有的研究工作都是利用局部性原理将频繁更新的数据缓存在DRAM，淘汰最近一段时间没有被频繁修改的数据至PCM。但是，基于传统的LRU、LFU等缓存算法，淘汰至PCM的脏数据页仍然会带来冗余的写操作。同时，PCM和DRAM混合主存架构下的页面迁移策略能够实现读写热度不同的数据存储在不同存储介质当中，但是迁移操作本身所带来的额外写操作也会在一定程度上磨损PCM的存储单元。

图1 基于DRAM和PCM的混合主存存储架构

针对现有的两种主要混合存储架构在改进PCM耐受性方面的不足，本文提出一种DRAM缓存+DRAM/PCM混合主存的新型存储架构，并在此基础上设计了一种基于LRU和LFU-Aging改进的两级缓存算法。本文将从两个方面说明这种策略的优势：

1)新型存储架构。使用DRAM作为缓存能够有效延长PCM的使用寿命，但是相比DRAM，PCM相对较低的读写性能和更新数据时的高能耗成为限制其独立作为主存的重要障碍。结合现有的两种主流的存储架构(如图1(c)所示)，本文设计了一种一小块DRAM作为缓存、PCM和DRAM共同作为主存的新型混合存储架构。该架构一方面利用缓存技术解决了PCM写寿命受限的问题，另一方面PCM和DRAM的混合主存能够充分发挥DRAM的写访问性能(存储写倾向性数据)以及PCM的低静态功耗(响应读倾向性数据)，在保证系统性能的同时降低了能耗开销。

2)新型缓存策略。时间局部性和访问频率是设计缓存策略时需要考虑的两个重要方面，新型存储架构下的DRAM缓存策略在同时参考时间局部性和访问频率的基础上，充分考虑数据的读写倾向性，将没有修改过的读倾向性数据淘汰至PCM，而更新频繁的热写数据被写回到DRAM。本文设计了一种基于LRU和LFU-Aging的双层缓存策略(如图2所示)：第一层通过LRU管理所有的脏数据块以及未经修改的干净数据块，根据时间局部性原理淘汰第一层中最近最少使用的冷数据块至相应的第二层LFU-Aging队列；第二层结合时间局部性和访问频率分别管理一个脏块LFU-Aging队列和一个干净块LFU-Aging队列，如果从第一层淘汰下来的冷数据块是修改过的，该数据页进入脏数据块队列，否则进入干净数据块队列。当需要淘汰数据时，将队列中处于LFU位置的数据块删除，即脏块写回到DRAM，干净数据块写回到PCM。传统的缓存策略通过长时间缓存更新频繁的数据来保护PCM，但是被写回的脏数据仍然更有可能在未来表现出写频繁趋势，该策略能够将不同读写热度的数据分别写回到DRAM和PCM，使PCM尽可能存储发生修改可能性更小的读倾向性数据，进一步减少PCM冗余写操作。此外，基于LRU和LFU-Aging改进的缓存算法在考虑访问频率的基础上，利用时间局部性避免了缓存污染，且易于实现、拥有高命中率。

3 基于BF的磨损均衡算法

通过新型混合存储架构下的基于LRU和LFU-Aging的缓存替换算法，本文能够在缓存被频繁访问数据的基础上，利用数据的读写倾向性将干净数据写回到PCM，进一步减少了PCM上的写操作。而在PCM主存中，本文在Partial Bloom Filter结构基础上针对强空间局部性的应用实现了低空间开销、高查询速度的组间磨损均衡算法。

3.1 基本思想

均匀化写操作分布是提高PCM耐受性的另一个重要研究方向，现有的磨损均衡操作根据数据交换或者数据移位的粒度可以分为组间和组内两大类：组间磨损均衡以一个分组(通常选取一个页面作为一个分组)为基本操作单位，能够实现写操作次数多的分组和写操作次数少的分组之间的磨损均衡；而组内磨损均衡则保证分组内部更细粒度的写操作单元(例如line)均匀化写操作分布。传统的以页面为粒度的数据交换磨损均衡操作在某些页面写操作次数突出的情况下效果良好，但是对于连续访问一段连续地址空间或者空间局部性较强的写访问模式，以单个页面为单位的磨损均衡将不再那么有效。

图2 基于LRU和LFU-Aging的新型缓存策略

Bloom Filter是一种拥有高空间和时间效率的随机数据结构，它利用位数组简洁地表示一个集合，并能判断一个元素是否属于这个集合。Counting Bloom Filter将标准Bloom Filter位数组的每一位扩展为一个计数器(Counter)，通过k个不同的hash函数将元素投影到k个不同的计数器，插入元素时对应的计数器加1，删除元素时减1。在Counting Bloom Filter基础之上演变而来的Partial Bloom Filter将位数组等分成k个区域，每个哈希函数只映射到其中一个区域，对应的哈希函数映射范围都是{0,1， …,m/k-1}。

基于Bloom Filter的思想，本文设计了一种针对强空间局部性数据流的组间磨损均衡策略。每个分组大小为128 MB，包含32 768个page，利用Partial Bloom Filter记录每个分组的写操作次数，当某个分组的写操作次数超过一定的阈值，则将该分组与写次数最少的分组进行数据交换。在分组之间进行数据交换时，将两个分组中一一对应的页面进行地址映射的变换(如图3 Segment swap)，实现分组之间的写操作均匀分布。

图3 基于Partial Bloom Filter的组间磨损均衡策略

3.2 组间磨损均衡

相比静态磨损均衡策略，动态磨损均衡对内存中每个分组的写操作次数进行跟踪，把磨损相对严重的分组中的写操作均匀到写操作次数较少的分组，这种依据全局写访问信息、没有确定性映射机制的重定位方式需要额外的映射表记录逻辑地址到物理地址的映射关系。传统的动态磨损均衡算法中每个分组对应一个计数器记录写次数，为了减少计数器带来的空间开销，同时提高查询效率，本文基于Partial Bloom Filter实现了低空间开销、高查询速度的组间磨损均衡算法。

由于很多应用程序会连续访问一段连续的地址空间，同时写操作表现出明显的空间局部性，一个页面被修改，相邻地址的数据页也会被修改，因此写操作的增加往往呈现一定的局部性，基于单个页面的磨损均衡操作不再那么高效。组间磨损均衡算法以每128 MB连续地址空间作为一个分组，利用Partial Bloom Filter的思想通过一个计数器记录分组所有页面的写操作情况，当分组中的页面响应写请求，计数器的数值加1，响应读请求时计数器数值不变化。当某个分组的写操作次数超过一定的阈值，找到写操作次数最少的分组并进行地址映射的变换。在进行组间数据交换时，定义写操作次数超过阈值的分组为A，写操作次数最少的分组为B，如果分组A中的页面i再次响应写请求，那么在分组B中找到对应的页面i，改变这两个页面之间的地址映射关系，即把页面Ai的逻辑地址映射到页面Bi的物理地址，将页面Bi的逻辑地址映射到页面Ai的物理地址，从而达到分组之间磨损均衡的目的。

这种组间磨损均衡算法具有如下几点优势：

1)降低记录写操作历史信息所带来的开销。每128 MB连续地址下的写操作被映射到1个计数器，相比传统的动态磨损均衡策略中每一个页面对应一个写操作计数器，算法利用Partial Bloom Filter极大地减少了计数器数量，从而降低了因统计写操作历史信息所带来的空间开销。

2)在写访问空间局部性较强的应用中，能够有效判断分组的磨损情况。当几个连续的页面响应写请求时，这些页面所在分组的写操作计数器会迅速增加，且写访问的局部性越强，分组之间的写操作次数差异越明显，将超过写操作阈值分组的逻辑地址重映射到写操作次数小的分组将会起到很好的均衡效果。

4 性能评估

对于PCM耐受性的缺陷，本文从减少写操作数量和均匀化写操作分布两个方向实现了PCM写寿命的提高。基于DRAM cache+PCM/DRAM混合主存的新型存储架构能够对数据流读写倾向性进行划分，减少对PCM存储介质不必要的写操作，基于Bloom Filter的组间磨损均衡策略能够实现分组之间的写操作均匀分布。本章从实验环境的设置以及新型存储架构下的磨损均衡算法对于减少PCM写操作、均匀化写操作分布的实验效果这两方面进行阐述和分析。

4.1 测试环境

由于目前还没有真实的混合内存物理器件，对于混合内存的研究工作都是基于模拟器平台进行仿真，本文使用基于GEM5和NVMain搭建的混合模拟器(如图4所示)来测试算法的有效性。GEM5是由M5和GEMS紧耦合而成的全系统模拟器，而NVMain是一个在内存结构层面模拟新型非易失性存储器件的局部硬件模拟器，两者结合不仅可以支持构建混合存储体系结构，而且能够更准确地模拟各种非易失性存储设备的性能。

图4 GEM5+NVMaim混合存储架构

实验中仿真实现了DRAM cache+PCM/DRAM混合主存的存储架构，在主存这一层级对两种存储介质进行统一编址，channel0为DRAM，其余地址空间被PCM占据。对于从DRAM cache淘汰至混合主存的数据块，根据其在缓存中表现出来的读写倾向性被写回到相应的主存设备，即修改频繁的数据被写回到DRAM，修改较少的静态数据写回到PCM。

GEM5模拟器中Alpha处理器架构提供四种可选择的CPU类型以及三级缓存的设置。本实验将CPU类型指定为Timing类型，即根据时序模型模拟相应的访问，设置两级缓存，包括64 KB的一级指令缓存、32 KB一级数据缓存以及2 MB二级缓存。对于主存，实验配置4个channel，其中channel0为传统的DDR3 SDRAM，channel1～3为PCM，主存大小设置为4 GB，而针对强空间局部性应用场景所设计的组间磨损均衡的实现以128 MB大小的Subarray作为基本操作单位。参数配置如表1所示。

表1 测试环境及参数配置

实验选取SPLASH-2测试集中的FFT、LU、RADIX作为基本测试程序，每个测试程序的大小、读写比例不尽相同，磨损均衡算法在不同测试程序下因数据流的空间局部性不同而产生实验效果上的差异。

4.2 性能分析

本文提出的两层磨损均衡算法分别从缓存数据写回时减少PCM上写操作数量以及PCM存储设备内部上的写操作均匀分布这两方面实现了PCM写寿命的延长，实验测试结果将对写操作数量的减少以及均匀分布情况进行分析与对比。

4.2.1 写操作次数减少情况

在传统的使用DRAM缓存减少PCM主存写操作次数方式的基础上，本文提出一种DRAM cache+DRAM/PCM混合内存的新型存储架构。该架构能够从两方面减少主存中PCM存储介质的写操作数量：一方面使修改频繁的数据尽可能保存在DRAM cache中，避免了主存频繁的存取访问；另一方面通过LRU和LFU-Aging相结合的缓存策略区分数据块的读写访问趋势，使得写访问频繁的数据写回到DRAM，读访问频繁的数据保存在PCM，进一步减少了PCM存储介质的写操作数量。

实验从混合存储架构中DRAM cache上减少的写回请求次数以及LRU+LFU-Aging缓存策略对于混合主存命中率的影响这两方面来衡量新型混合存储架构以及缓存策略的优劣性。从表2可以看出，相比传统的LRU缓存策略，本文所提出的缓存策略能够有效判断数据流的读写倾向性，使得从cache写回PCM上写请求的数量减少达到13.4%～38.6%。同时，针对DRAM cache设计的基于LRU+LFU-Aging的缓存策略在不同测试程序下的读写缓存命中率和传统的LRU相当(如表2所示)，增加读写倾向性的判断并未造成命中率的下降。

表2 新型混合存储架构下缓存策略的性能对比

4.2.2 写操作均匀分布情况

对于写访问局部性较强的数据流，往往会呈现出内存中某一个连续区域内的写次数明显多于其他区域，针对该问题本文设计了一种基于Bloom Filter的组间写操作均匀分布策略。如图5(a)所示，从左至右分别是测试集Barnes、Radix和Ocean，在没有磨损均衡策略的情况下测试集的写操作分布呈现出明显的空间局部性，某些分组的写次数远远高于其他分组，值得注意的是，这些写次数突出的分组往往集中在某一个channel中，这种情况往往会加速存储介质的损坏。本文利用Partial Bloom Filter结构记录每个分组的磨损情况并依据分组写次数计数情况执行组间磨损均衡，从统计数据可以发现，90%分组的写次数都能集中在平均写次数的20%浮动范围之内(如图5(b)所示)。值得注意的是，Ocean 测试集原先的写操作分布相对均匀，这种情况下的均匀化写操作分布的效果相比强空间局部性测试集下的实现效果稍有逊色。

图5 以128 MB为分组大小时磨损均衡前后写操作分布情况对比

本文设计的组间磨损均衡策略以128 MB为一个分组，当分组的写次数超过某一阈值，触发组间磨损均衡。这种粗粒度的触发条件对于分组内部页面的写次数缺乏一定的监控，会出现分组写次数尚未超过阈值，但是分组内某一页面已经被过多“磨损”的情况。以更细粒度的分组作为写访问历史信息统计的基本单位往往能够取得更好的磨损均衡效果，同时以更大的几率避免分组内部某一存储单元被提前损坏，例如以一个页面作为一个独立分组，统计每一个页面的写信息，但是这样也会带来空间开销增大和数据迁移造成的额外写操作问题。如图6所示，以测试集Barnes为例，如果以64 MB为一个分组，可以将90%以上的写操作均匀分布在平均值10%的浮动范围内，但是冗余写操作的比例也相应地从2.35%提高至4.1%。

图6 以64 MB为分组大小时磨损均衡前后写操作分布情况

5 结语

相变存储器的发展成熟打破了传统存储架构中以DRAM作为主存设备所面临的高能耗、易失性等瓶颈，为了解决PCM写寿命受限的问题，本文从减少写次数和均匀化写操作分布两个方向有效地延长PCM的使用寿命。本文提出DRAM cache+DRAM/PCM的混合存储结构，通过LRU和LFU-Aging相结合的缓存策略将读写热度不同的数据分别存储在DRAM或PCM中，避免频繁修改数据对PCM所造成的不必要的写操作负担。同时，针对访问局部性较强的应用，本文设计一种组间磨损均衡策略，通过Bloom Filter结构以较低空间代价实现PCM中所有分组的写次数记录，从而实现了写操作的均匀化分布。实验结果表明，在新型混合存储架构下减少PCM写操作达13.4%～38.6%，并且针对强空间局部性的访问模式，能够有效均匀分组之间的写操作分布，90%以上的分组的写次数能够浮动在平均写次数±20%之内。