钱 璐 李 弋 吴毅坚 赵文耘
(复旦大学软件学院 上海 201203) (上海市数据科学重点实验室(复旦大学) 上海 200433)
非易失性内存设备NVM(Non-volatile memory)是指在系统掉电时仍能保持数据不丢失的存储设备。从发展历程看,主要分为块寻址和字节寻址两种。块寻址设备性能比动态随机存储器DRAM(Dynamic Random Access Memory)低得多,而字节寻址设备性能接近DRAM。针对NVM建立访问模式的研究主要集中在两个方面。一方面将NVM当作存储设备,在NVM上建立文件系统进行持久内存管理[1]。另一方面,对于按字节寻址的NVM,将其替代传统DRAM,提供应用程序load/store访问方式[2]。前者并没充分挖掘NVM优秀特性,没有最大限度降低软件系统开销。后者直接访问NVM,绕过很多软件层包括系统调用、文件系统等,大大降低了访问延迟。本文设计的非易失性内存卷模式通过将多块不同种类NVM组织成地址连续的持久内存卷,简称PM卷(Persistent Memory Volume),并将卷映射到用户空间。既提供处理器load/store访问方式,也对异构NVM设备实现有效管理。
主要从为NVM设备建立文件系统、以load/store方式直接访问NVM设备、内存通道划分、热数据划分四方面阐述相关工作。
BPFS[3]文件系统以字节寻址方式管理NVM,通过在文件系统构建树状数据结构,省去文件系统缓存与映像间的数据拷贝,从而减少对NVM的写入。SCMFS文件系统[4]与BPFS一样在持久性内存中不需要数据拷贝,并且尽可能为每一个文件分配连续空间从而提供优越的性能。PMFS文件系统[5]绕开了文件系统缓存直接访问NVM,避免了系统中数据的拷贝。NOVA[6]文件系统通过为每个文件inode维持一个日志来提高系统并发性,并在日志之外存储文件数据来减少垃圾回收的开销,最终在混合NVM内存结构中最大化性能。
在NVM单层存储模型中,内存中可以存储持久化数据结构,所以Haris Volos等[7]提出Mnemosyne,Joel Coburn等[8]提出NV-Heaps,提供了新的NVM编程接口。Mnemosyne和NV-Heaps通过提供用户态的编程接口,使应用程序能够在用户态访问非易失内存设备,避免了通过文件系统访问NVM的系统开销,包括系统调用、文件系统接口、设备驱动程序等。
Muralidhara等[9]提出一种应用感知的内存通道隔离方法来减少多核环境下的访存干扰,该方法映射相互之间可能产生严重访存冲突的应用的数据到不同的内存通道并优先调度非访存密集型应用的访存请求。Jeong等[10]提出一种通过在多核之间隔离内存Bank以隔离访存请求从而减少局部性冲突的方法。为了弥补因此而损失的bank级并行性,该方法采用Memory Subranking技术来增加独立的Bank数。
Kyu Ho Park等[11]提出了一种简单的基于页面访问频度的冷热页面划分策略。通过设置一个访问位来统计页面的访问频繁程度来划分冷页面和热页面。Dong-Jae Shin等[12]提出了一种更为准确反映页面热度的页面划分策略。通过扩展页表的条目,增加了4个记录位,越是靠左的位权重更小:8、4、2、1,每当页面被访问的时候标记就会左移一位,最后划分的时候计算页面的总权重,根据设定的冷热页面的阈值来划分冷热页面。Luiz Ramos等[13]提出了一种考虑页面访问频度和时间的RaPP策略。策略利用一个M级的LRU队列来记录页面的访问信息,页面在生存时间内随着被访问的程度不断地提高队列等级。当超过生存时间后降低队列等级,全面地考虑页面在很长时间和最近时间段的访问情况。
随着大数据技术的发展传统以计算为中心的系统架构逐渐转向以数据为中心。然而磁盘访问性能的提升远落后于CPU计算能力的提升,无法满足大数据处理应用的需求。字节寻址NVM具有访问性能高、容量大等特性,对数据密集型应用性能的提升带来了希望。传统存储架构不利于发挥NVM的性能优势。本文研究如何针对NVM设计更加高效的访存方式,从而替代DRAM。针对字节寻址NVM特性,设计相应的文件系统在很大程度上提升了系统性能,如SCMFS、BPFS文件系统等。但始终将NVM当作存储使用,并没充分挖掘NVM的优秀特性,没有最大限度的降低软件系统的开销。Mnemosyne在内核中创建并虚拟化一个持久区域,通过内存映射方式将持久区域映射到用户空间,提供应用程序load/store方式访问,从而直接替代DRAM。直接访问NVM绕过了很多软件层包括系统调用、文件系统以及设备驱动等,大大降低了访问延迟。但Mnemosyne对于NVM设备的不同种类,在内核中如何管理并没有研究。本文设计并实现的非易失性内存卷模式将NVM设备直接替代DRAM,通过将多块不同种类NVM组织成地址连续的持久内存卷,并将卷映射到用户空间。既提供了处理器load/store访问方式,也很好地对异构NVM设备实现管理。
Linux通过虚拟内存实现内存管理,应用程序中进程使用虚拟地址访问内存。虚拟地址也即逻辑地址,是系统中分段机制产生的段内偏移地址部分。实际数据需要物理地址直接访问。物理地址是前端总线上寻址物理内存的地址信号。虚拟地址加上相应的段基地址就生成了线性地址,最后通过分页机制将线性地址翻译成物理地址。Linux操作系统中虚拟地址等于线性地址,所以在Linux中只需要分页机制便能将虚拟地址转换成物理地址。
如图1所示,PM卷是在NVM硬件层之上建立地址连续的软件层。在内核中表现为一段地址连续的内存空间,并和传统内存物理地址空间统一寻址。在系统中拥有一段物理地址空间,并提供内核组件调用的接口。PM卷和异构NVM之间通过映射算法实现地址翻译,对PM卷的访问实际被映射到NVM设备上。最后通过内存映射方式将PM卷映射到用户空间,使得应用程序能够以load/store方式访问PM卷。
图1 非易失性内存卷模式结构图
非易失性内存卷模式设计提供程序员一个持久内存卷模式的抽象。应用程序以load/store方式访问PM卷,内核负责将多个NVM设备组织成一个地址连续的PM卷。PM卷主要实现了三个方面的目标。
1) 用户态直接访问持久内存,绕过了包括系统调用,文件系统以及设备驱动等软件层降低访问延迟。
2) 设计卷到非易失性内存设备的映射关系,降低卷到非易失性内存的地址翻译开销。
3) 一个灵活方便的卷模式管理机制,实现用户态创建、初始化、删除卷等。
现在的内存系统都是多通道架构,不同通道的内存可以被并行访问。一个典型的DRAM内存模块,通常有16个banks,而不同的bank之间也可以并行访问。假设系统中有四个内核,且每个内核只有一个访存请求。最好的情况下,四个访问请求的数据分别位于四个不同的内存bank中,那么四个访问请求可以并行执行。最坏的情况下,来自于四个内核的访存请求都指向同一个内存bank,此时只能执行其中一个请求,其他请求需要等待并按顺序执行,无法并行执行。因而访存延迟会成倍增加。大数据时代背景下,数据规模越来越大,而对数据的访问更多集中在对数据的读取上。由于缓存容量有限,大量的数据访问是以内存为主。在多核环境中热数据的频繁访问会导致同一时刻不在同一cache line但位于同一内存bank中的数据被多个访存用户同时请求访问,这些访存请求无法并行访问,因此导致严重访存冲突,极大地增加了系统访问延迟。
针对热数据频繁访问导致的严重访存冲突,考虑将频繁访问的热数据备份多次放置在不同内存通道或不同内存bank上。多核环境中,对于同一块数据的多个访问请求分配到不同的数据备份上,实现并行访问,降低系统访问延迟。由于数据有多个备份,对内存容量要求很高,鉴于NVM容量很大,因而使用NVM替代DRAM,将同一块数据备份多次,每个数据备份放置在不同的非易失性内存设备上,并且使不同的NVM位于不同的内存通道上。当同一时刻对同一块数据有多个访问请求时,将访问映射到存有不同数据备份的NVM上。在多核环境中,不同的处理器处理其中一个访存请求,可以实现对同一块数据的并行访问。借助非易失性内存卷模式,在位于不同内存通道的NVM设备之上建立一个地址连续的PM卷层,对于PM卷中的每一页映射到不同内存通道NVM设备的多个页面。
假设PM卷中页面是热数据页面,在大量数据访问时会产生严重访存冲突,所以将PM卷中的页面映射到多个不同NVM设备上。并在设计一对多映射时将每一个NVM设备的大小看作与PM卷相同。类似于传统内存访问的请求分页方式,通过建立页表机制实现一对多地址映射。页表中页表项按照PM卷地址由小到大依次存储。但由于PM卷上的每一页,可以映射到多个NVM设备,每个PM卷页面可以对应多个页表项,对应于同一个PM卷页的多个页表项按照页表项对应NVM设备的设备号由小到大依次存储。
以PM卷和非易失性内存的地址都用32 bit表示,并且建立的页表中的每一个页表项都是32 bit,而系统是以4 KB为一页大小,给出页表项的格式如图2所示。地址中12-31位表示物理页号,指向NVM中某一页的基地址,要求物理页4 KB对齐。由于页表项前20位是页帧号,后12位并没有实际意义,取其中一位标记此页是否已经被映射,就是V字段,当为1的时候表示已经映射。创建PM卷的时候初始化页表项,将所有的页表项初始化为0。建立的页表映射都是固定的,一旦某个进程访问了PM卷的某一页,通过一对多映射将地址映射到某个NVM设备某页之后,在此进程结束之前,该映射的页表项保持不变。
图2 一级页表结构的页表项含义图
建立了页表机制,并初始化页表项为0。当有进程首次对PM卷某页写入数据时,将数据写入构成卷的第一个NVM设备上(由于构成卷的NVM设备是用链表链接,链表是按照NVM设备号的大小链接,第一个设备指的是链表中第一个结点),之后将数据拷贝到其他k个设备上。通过写入的PM卷地址计算得到对应的页表项的位置,然后将每个数据备份的物理页帧号根据设备号写入正确的页表项中。有了映射页表,在大规模数据读取时,需要设计地址翻译策略,来实现并行的访问。一对多地址映射算法见表1。
表1 一对多地址映射算法伪代码
因为不同平台的页面大小不尽相同,伪代码中的PAGE_SHIFT是地址中页面偏移量的位数。Nums指的是PM卷的一页究竟映射到多少个NVM设备上。1~4行代码通过页表基址加上PFN*Nums的方式找到页表项。函数isValidEntry通过检查V标记位是否为1来判断页表项是否有效,如果是1则表示该页表项无效。searchValidEntry函数寻找下一个有效的页表项,函数setEntryNotValid将V标记位设置为1。pfn_to_page函数将NVM设备的pfn转化成对应页的page。算法的整体思路是:通过PM卷中待映射的页帧号相对于PM卷初始地址页帧号的偏移量乘以构成PM卷的NVM设备总数,再加上页表基地址得到待映射页对应页表项集的初始地址,然后判断该页表项是否已经被分配给某进程,最后找到没有被分配的页表项,将该页表项设置为已分配,同时通过页表项前20位页面物理地址得到页帧号。
由于页表的大小会随着PM卷地址空间大小的增加成倍增加,因而增加缺页开销,所以考虑将页表设计成多级结构。若设计成二级页表,对应PM卷地址结构如图3所示。以一对四映射为例,页表项中是4个页表项指向同一个PM卷地址页框,那么在一页中(4 KB)可放入256个(一个页表项占4 B,4 KB/(4 B×4))映射到不同PM卷地址的页表项,所以需要8位来标记,也即是图3中的PPN2(physical page number),一级页表用12位,也即是图3中的PPN1来标记,需要存储在4页中。
图3 二级页表结构的PM卷地址含义图
一对多地址映射由于在多块NVM上建立了PM卷层,并且PM卷层到NVM设备之间通过页表形式进行地址翻译,相比于传统内存架构,多了一层地址翻译过程。传统内存架构中应用程序虚拟地址在MMU作用下最多只需要一次访存操作便可以得到物理地址,而非易失性内存卷模式下的一对多地址映射中。应用程序虚拟地址首先需要类似于传统内存架构中地址翻译过程得到PM卷对应的地址,然后仍需要进行PM卷到NVM地址映射得到最终存储数据的NVM设备上地址,至少需要两次访存操作。这会导致缺页处理开销加大。
多路并行访存是将数据备份放置在不同内存通道的NVM上,在多核环境中通过一对多映射算法,将同一块数据不同访存请求分配到不同数据备份上,实现并行访问。首先实现非易失性内存卷模式,然后实现PM卷到NVM之间一对多地址映射。
为了对PM卷进行管理,在内核中创建结构体struct pm_volume保存PM卷的卷大小、卷号、卷的开始地址以及组成卷的NVM设备等信息。同时PM卷是取自不同NVM设备的中的一部分内存空间组成,因此创建结构体struct pm_device保存组成PM卷的NVM设备开始页号、大小、设备号等信息。实现非易失性内存卷模式分两步进行,首先将PM卷加入内存系统中,提供内核中组件访问接口。然后通过内存映射方式将PM卷映射到用户地址空间,提供应用程序load/stroe访问方式。
(1) 将PM卷加入内存系统分两步实现,首先将PM卷加入伙伴系统,然后修改内核中alloc_pages函数使内核组件能够访问PM卷。
传统内存系统中,内核将内存空间划分成结点,每个结点划分成管理区(zone),每个管理区由各自的伙伴系统负责所有页面的申请和释放。管理区中的每个页帧对应一个struct page结构。我们自定义了PM_ZONE管理区,让PM卷和PM_ZONE管理区的页面一一对应,然后将PM_ZONE管理区中的页面加入伙伴系统。通过修改管理区和伙伴系统初始化方法,加入对自定义PM_ZONE的管理。为了方便区分PM_ZONE和系统其他管理区,在struct zone结构体中增加了char*name字段表示管理区的名字。完成管理区和伙伴系统初始化之后,PM_ZONE管理区上并没有实际页面,所以内核中申请PM_ZONE大小的连续内存页,将其每页初始化为属于PM_ZONE管理区。由于申请和释放页面时系统通过page_zone(page)函数获取页所在的管理区,但该函数用到很多系统预定义标记符,而PM_ZONE并没有添加到系统中维护,因此无法通过此方法获取页所在的管理区,故在struct page中添加了一个struct zone*zone字段来表示该页所在的管理区。在内核申请PM_ZONE大小页面并设置成所属管理区时,通过page->zone->name=″PM_ZONE″实现。
PM卷以PM_ZONE管理区的形式加入内存伙伴系统之后,需修改内核的alloc_pages函数才能使内核申请PM卷的页面。实现中增加自定义GFP_PM标志,也就是将GFP_PM标志加入alloc_pages函数第一个参数gfp_t gfp_mask中。通过判断gfp_mask标志是否等于GFP_PM,进而选择是否从PM卷对应的PM_ZONE管理区中申请页面。
(2) PM卷以PM_ZONE管理区形式加入内存系统之后,内核可以申请释放PM卷中页面。但应用程序对PM卷的访问还需要提供正确的访问接口,本文基于mmap的内存映射接口模式,将PM卷层中的页面通过mmap函数映射到用户空间。基于mmap的内存映射方式是指通过mmap函数将PM卷地址空间映射到用户进程地址空间,提供用户进程load/store方式访问。函数接口形式是int pm_mmap(struct file*filp, struct vm_area_struct*vma),参数filp是待映射目标文件的结构体指针,vma是虚拟内存区域。
一对多地址映射通过页表机制实现,本文实现了单级页表结构。首先在PM卷结构体struct pm_volume中加入属性unsigned long*pageTableBase表示当前PM卷对应页表基地址。由于struct pm_volume结构体中有属性volume_size表示PM卷大小以及num表示构成卷的NVM设备个数。volume_size和num乘积就是页表大小。另外还需在struct page结构体中增加属性unsigned int firstaccess,表示PM卷中每页是否第一次被进程访问并写入数据。0表示首次被访问,1表示否。
创建PM卷时根据页表大小将所有页表项初始化为0。当有进程首次访问PM卷的某页时,修改mmap函数,通过判断PM卷的当前被写入页面的struct page的firstaccess属性是否为0,决定是将数据直接写入第一个NVM设备的对应页还是访问页表得到页表项。如果是0,表示访问的PM卷页面是首次写入,因此将数据写入第一个NVM设备对应页。然后通过memcpy函数将该页数据拷贝到其他NVM设备对应页面上。Memcpy函数使用内存虚拟地址,可通过函数kmap将NVM设备物理地址转换成内存虚拟地址。最后修改PM卷中当前页面的页表项集。
建立页表后,对PM卷该页面的大量读取操作可以通过地址翻译算法在多核环境中实现并行访问。以PM卷映射到四个NVM设备为例子阐述地址翻译的实现过程,考虑到非易失性内存总的空间大小是PM卷的4倍,在制作页表时PM卷的每一个页号对应四个不同NVM的页号,PM卷每一页对应的四个不同的NVM页号的页表条目连续(每个页表条目的大小为4 B)。若PM卷的大小为4 GB,每个NVM的大小同样也是4 GB。以PM卷地址为:0x000645b0为例,一对四地址翻译如图4所示。对应PM卷地址的页表项有4个(图中只画出3个),地址0x000645b0前20位的物理页号是100,根据算法乘以4得到400。查看页表400位置处对应的V标记位是1,表示此页表项已经被映射,由searchValidEntry函数找到401处V标记位是0有效,则将该标记位设置为1,并且根据该页表项的前二十位页面物理基地址找到对应的NVM设备的那一页,再由offset为1 456计算得到最终目标字节位置并找到。
图4 一对四单级页表结构图,左边是页表结构,右边是找到的NVM设备的具体物理页
一旦将某个非易失性内存的页帧号映射给对应进程的时候,当该进程此后访问PM卷同一页时,一律访问之前绑定的非易失性内存的页,而不再进行缺页处理,也就是缺页处理只会在进程首次访问PM卷地址空间某一页的时候进行。即便缺页访问时,需要进行两次的地址翻译,当有大量的数据访问时候,这个缺页的开销会被不断稀释掉。
实验中,硬件是ThinkPad x230 Intel i5双核4 GB DDR3双通道内存笔记本电脑,安装了Ubuntu15.10操作系统,内核版本是4.2.8。
在验证了非易失性内存卷模式实现的合理性后,验证一对多地址映射。从内存DRAM中申请两个连续内存块模拟两个NVM设备。由于一对多设计比传统内存访问方式多了一层地址翻译过程,因而首先考虑缺页中断处理中开销的增加对系统的影响。实验组中测量的是实现了一对多映射的缺页处理时间,对照组测量传统内存请求分页方式缺页处理时间。实验结果见图5。
图5 性能优化后PM卷页面访问缺页处理时间和正常内存访问缺页处理时间对比图
缺页处理的开销会增加,但由于页表项一旦写进页表,在当前进程结束前页表项不会改变,所以缺页只在首次访问PM卷页面时发生。在大规模数据读取时开销会被不断稀释,因此进一步测试对PM卷大规模数据访问时的性能提升情况。实验主要验证一对二地址映射时,双通道并行访问是否能够提升系统性能,因而,对于映射到不同内存通道的同一块数据的两个备份不要求数据相同,主要保证两个数据备份位于不同内存通道即可。
内存控制器地址映射,是将一个内存请求的物理地址翻译并映射成DRAM模块的物理结构:channel、rank、bank、column等。对于双通道的内存结构中,物理地址有1 bit表示该内存请求的数据所在内存通道。实验中使用的ThinkPad x230设备是物理地址右边起第12 bit。
一对二地址映射实验中访问不同内存通道便可以通过访问物理地址channel标记位分别为0和1的两个内存通道。也就是一对二设计中同一PM卷页面映射的两个实际页面的页帧号倒数第2 bit不相同。实验中设计两个并发的线程,分别读取PM卷空间的一段页框。由于实现了一对二的情况,当访问同一块数据时两个并发线程会实现并行执行。对照组中将与一对多中PM卷大小相同的一块连续内存通过mmap函数映射到进程虚拟地址空间,设计两个线程执行并发访问。实验是在禁用cache中进行。实验是将每一个线程对PM卷进行100万次读取操作,测量两个线程执行完需要的总时间,与对照组总时间进行对比。结果如表2所示。
表2 实验结果汇总表 us
如图5缺页处理实验共进行了15组,实验组数据的最大值、最小值和平均值分别是9 514 ns、5 255 ns和6 917.9 ns。对照组数据的最大值、最小值和平均值分别是1 693 ns、322 ns和550.4 ns。从平均值看来,实验组所用时间是对照组的12.6倍。可以看出在缺页处理上对性能产生了较大的影响。针对一对多地址映射进行了22组实验得到数据,见表2。
表2中实验组数据的平均值、最大值和最小值分别是:11 430.8 us、14 728 us、9 496 us。对照组数据平均值、最大值和最小值分别是:12 324.9 us、15 968 us、9 889 us。由平均值可计算得出实验组比对照组性能提升7.25%。从实验结果看来,基于一对多映射的PM卷模式增加了一层地址翻译过程虽然在缺页处理时间上是传统访存方式的12.6倍,但在大量数据读取中,整体性能提升了7.25%。但是仍然存在些不足之处,实验是在双通道环境下进行的,实现了一对二映射的情况,对于更多的一对三、一对四等映射情况可进一步进行实验。
本文针对新型NVM设备的优秀特性,设计实现了load/store方式访问NVM设备,并管理异构的NVM设备的非易失性内存卷。然后基于热数据访存冲突在非易失性内存卷模式的基础上提出了一对多的地址映射方案,实现了一对多地址映射策略。最后,通过在双通道内存中,进行一对二映射实验,得到的数据在一对二映射情况下,系统访存性能提升了7.25%。表明这种设计确实能够改变内存访问方式并提升访问性能,比较好地避免热数据的访存冲突。