内存内存

软件学报ISSN1000-9825,CODENRUXUEWE-mail:jos@iscas.
ac.
cnJournalofSoftware,2016,27(8):21472167[doi:10.
13328/j.
cnki.
jos.
005103]http://www.
jos.
org.
cn中国科学院软件研究所版权所有.
Tel:+86-10-62562563内存计算技术研究综述罗乐,刘轶,钱德沛(北京航空航天大学计算机学院,北京100191)通讯作者:罗乐,E-mail:luole@buaa.
edu.
cn摘要:在大数据时代,如何高效地处理海量数据以满足性能需求,是一个需要解决的重要问题.
内存计算充分利用大容量内存进行数据处理,减少甚至避免I/O操作,因而极大地提高了海量数据处理的性能,同时也面临一系列有待解决的问题.
首先,在分析内存计算技术特点的基础上对其进行了分类,并分别介绍了各类技术及系统的原理、研究现状及热点问题;其次,对内存计算的典型应用进行了分析;最后,从总体层面和应用层面对内存计算面临的挑战予以分析,并且对其发展前景做了展望.
关键词:内存计算;新型混合内存;分布式集群;图计算;大数据处理中图法分类号:TP316中文引用格式:罗乐,刘轶,钱德沛.
内存计算技术研究综述.
软件学报,2016,27(8):21472167.
http://www.
jos.
org.
cn/1000-9825/5103.
htm英文引用格式:LuoL,LiuY,QianDP.
Surveyonin-memorycomputingtechnology.
RuanJianXueBao/JournalofSoftware,2016,27(8):21472167(inChinese).
http://www.
jos.
org.
cn/1000-9825/5103.
htmSurveyonIn-MemoryComputingTechnologyLUOLe,LIUYi,QIANDe-Pei(SchoolofComputerScienceandEngineering,BeiHangUniversity,Beijing100191,China)Abstract:Intheeraofbigdata,systemsneedtoprocessmassivedataefficientlytomeetperformancerequirementsofapplications.
In-memorycomputingtechnologycanimproveperformanceofmassivedataprocessingsignificantlybyutilizingmemoryandavoidI/Ooperations.
However,thetechnologyfacesaseriesofchallengesthatneedtobesolved.
Thispaperanalyzescharacteristicsofin-memorycomputingtechnology,laysoutitsclassification,andintroducesprinciples,relatedworksandhottopicsofeverycategory.
Inaddition,severaltypicalapplicationsofin-memorytechnologyareintroduced.
Finally,challengesandopportunitiesforin-memorycomputingareelaborated.
Keywords:in-memorycomputing;hybridmemory;distributedsystem;graphprocessing;bigdataprocessing随着大数据时代的来临,数据规模越来越大,从万亿字节(TB)到千万亿字节(PB)级;数据种类繁多,包括传统的结构化数据,又包括文字、图片、音频和视频等非结构化数据,且非结构化数据比重在快速增长;而数据快速增长,引发的数据处理时效性难以保障.
大数据所带来的大规模及需要实时处理等特点与传统的以计算为中心的模式产生巨大矛盾,使得传统计算模型难以适应当今大数据环境下的数据处理.
总的来说,数据处理从以计算为中心转变成了以数据为中心,这样,通过使用传统的内存—磁盘访问模式来处理大数据总会存在I/O瓶颈,处理的速度问题愈发突出,且时效性难以保证.
现有的方案都只能一定程度上缓解这个瓶颈,而不能彻底解决这个基金项目:国家自然科学基金(91530324);国家高科技研究发展计划(863)(2015AA01A301)Foundationitem:NationalNaturalScienceFoundationofChina(91530324);NationalHigh-TechR&DProgramofChina(863)(2015AA01A301)收稿时间:2015-07-22;修改时间:2016-03-18;采用时间:2016-05-23;jos在线出版时间:2016-07-30CNKI网络优先出版:2016-08-0109:38:56,http://www.
cnki.
net/kcms/detail/11.
2560.
TP.
20160801.
0938.
005.
html2148JournalofSoftware软件学报Vol.
27,No.
8,August2016问题.
而大数据所表现出的增量速度快、时间局部性低等特点,客观上使得以计算为中心的传统模式面临着内存容量有限、输入/输出(I/O)压力大、缓存命中率低、数据处理的总体性能低等诸多挑战.

对此,在体系结构方面,工业界和学术界通过使用众核处理器及分布式集群,增加协处理器和GPU,使用大内存,增加I/O通道等方式来应对.
然而,大内存、众核处理器等能耗超高.
文献[1,2]指出,如今大部分的DRAM内存能耗多达40%,这对于如今的大数据处理是一个非常重要的考虑因素.
在编程模型方面,研究者提出了以MapReduce[3],Hadoop[4]为代表的编程框架来解决大数据问题.
MapReduce在分布式系统上具有很好的可扩展性和容错性,但是它需要从磁盘获取数据,再将中间结果数据写回磁盘,导致系统的I/O开销极大,不适用于具有实时性需求的应用.
为了解决I/O开销大的问题,近些年又衍生出许多In-MemoryMapReduce系统[514],即把Map结果不再写入磁盘,而是将其写入内存,这些就避免了过多的I/O操作,减少了开销.
然而,虽然分布式的编程框架在一定程度上解决了大数据处理的问题,但是分布式系统带来的一致性问题、节点间通信及容错数据复制等,在一定程度上限制了大数据处理的并行性.
近年来,随着多核CPU的快速发展,内存价格的不断下降,以及系统架构的不断演进下,为大数据处理在硬件方面提供了有利的条件.
SAP公司在2012年推出的HANA内存计算[15]及加州大学伯克利分校开发的ApacheSpark[16]使得内存计算再次得到学术界和工业界的广泛关注.
同时,IBM的solidDB[17]、Oracle的ExadataX3、微软的SQLServer2012也引入了内存计算.
内存计算不是最新提出的概念,但是近年来它却成为业界和研究领域的一个热点,解决了前面提到的大数据时代数据处理速度以及时效性的问题,其原因在于,在内存计算模式下,所有的数据在初始化阶段全部加载到内存中,数据及查询的操作都在高速内存中执行,CPU直接从内存读取数据,进行实时地计算和分析,减少了磁盘数据访问,降低了网络与磁盘I/O的影响,大幅提升了计算处理的数据吞吐量与处理的速度,减少了原本占大量计算资源的I/O开销.
通过内存计算的应用,避免了I/O瓶颈,以前在数小时、数天时间内计算的结果,在内存计算环境中,可以在数秒内完成.
因此,在高性能的计算背景下,内存计算能再次成为工业界和学界研究关注的热点,成为海量数据分析的利器则不足为奇.
另外,关于大内存引起的能耗问题,近些年出现了大量新型非易失性随机存储介质,比如电阻存器、铁电存储器、相变存储器等,其容量大、价格低、读写速度与DRAM相当,最重要的是,其能耗远远低于DRAM,因此,在一定程度可以替换DRAM成为新型内存.
为此,出现了大量DRAM与非易失性的混合内存的研究.
本文主要对内存计算的技术特点、分类、研究现状、热点问题和典型应用进行介绍分析,展望内容计算的发展前景.
首先,介绍和分析内存计算的概念和技术特点;其次,给出内存计算技术及系统的分类,介绍3种类别的原理、现状和问题;再次,介绍内存计算的几种典型应用;最后,从总体层面和应用层面对内存计算面临的挑战予以分析,并且对其发展前景进行展望.
1内存计算概念内存计算不是一个新的概念,早在20世纪90年代就有关于内存计算雏形的论述[18,19],只是当时硬件发展有限,没有得到进一步地研究.
关于内存计算的概念,至今没有统一的定义.
Gartner对其定义为:一种应用平台中间件,实现分布式、可靠及可扩展性、强一致或最终一致性的内存NoSQL数据存储,可供多个应用共享[20].
IBM给出的解释是:内存计算主要是将数据存放在服务器的内存中,以此作为数据处理加速的一个手段,其主要适用于数据访问密集型的应用[21].
GridGrain关于内存计算给出这样的解释:通过使用一种中间件的软件将数据存储于分布式集群中的内存当中,并且进行并行处理[22].
TIBCO认为,内存计算是对处理大数据所遇到瓶颈的一种突破[23].
Techopedia认为,随着内存价格大幅下迭,内存容量增长,这样就更好地将信息存入专用服务器内存,而不是存储速度更慢的磁盘.
它能帮助商务用户快速地进行模式识别,及时分析大数据,即,所谓的内存计算[24].
内存计算不仅仅是把数据驻留内存,还需要对软件体系、计算模型等进行专门的设计[25].
因此可以看出,内存计算主要有以下特性:(1)硬件方面拥有大容量内存,可将待处理数据尽量全部存放于内存当中,内存可以是单机内存或者分布式内存,且单机内存要足够大;罗乐等:内存计算技术研究综述2149(2)具有良好的编程模型和编程接口;(3)主要面向数据密集型应用,数据规模大,处理实时性要求高;(4)大多支持并行处理数据.
综上所述,内存计算是以大数据为中心、依托计算机硬件的发展、依靠新型的软件体系结构,即,通过对体系结构及编程模型等进行重大革新,将数据装入内存中处理,而尽量避免I/O操作的一种新型的以数据为中心的并行计算模式.
在应用层面,内存计算主要用于数据密集型计算的处理,尤其是数据量极大且需要实时分析处理的计算.
这类应用以数据为中心,需要极高的数据传输及处理速率.
因此在内存计算模式中,数据的存储与传输取代了计算任务成为新的核心.
内存计算与传统的内存缓存有着较大的区别,主要体现在数据在内存中的存储和访问方式上.
在内存计算中,数据长久地存储于内存中,由应用程序直接访问.
即使当数据量过大导致其不能完全存放于内存中时,从应用程序视角看,待处理数据仍是存储于内存当中的,用户程序同样只是直接操作内存,而由操作系统、运行时环境完成数据在内存和磁盘间的交换.
而内存缓存,利用部分内存缓存磁盘/文件数据,应用程序通过文件系统接口访问缓存中的数据,而不是像内存计算那样直接访问.
因此,内存计算和传统的内存缓存都可以通过减少I/O操作提升系统性能,内存计算支持数据直接访问,效率更高,也更适合大数据应用,缺点是不像传统内存缓存那样对应用程序透明,通常需要专门的编程模型和接口支持.
2内存计算分类内存计算系统结构和实现方法在很大程度上取决于底层硬件架构,更准确地说,取决于底层内存架构.
根据内存计算所依托硬件架构的不同,可将内存计算分为3类:(1)基于单节点的内存计算;(2)基于分布集群的内存计算;(3)基于新型混合结构内存的内存计算.
2.
1基于单节点的内存计算单节点内存计算系统运行于单个物理节点上,节点拥有一个或多个处理器以及共享内存,内存结构可以是集中式共享内存,或者非一致性共享内存(non-uniformmemoryaccess,简称NUMA).
单节点上的内存计算利用多核CPU,采用大内存和多线程并行,以充分发挥单机的计算效能,并且采取充分利用内存和CPU的cache、优化磁盘读取等措施.
在软件层面,单节点内存计算主要分为内存数据处理系统和内存存储系统两类:在内存数据处理系统方面,主要利用如今发展起来的众核CPU和大内存,使得单节点系统有一定的大数据处理能力;且其易于编程,CPU和内存资源能被充分利用,因此具有良好的使用价值.
文献[27]中指出,拥有100G到1TB内存的高端服务器足够处理现实中的图数据.
近几年出现了众多基于众核内存计算的数据处理框架,比如Grace[26],Ligra[27],GRACE[28]和GraphLab[29].
其中,Grace,Ligra和GRACE都利用多核CPU和大内存,并采用了多线程并行技术,充分利用内存和CPU,只是三者处理机制及侧重点不同.
Grace提出一种图更新聚集策略,针对图划分间(线程之间)进行了通信及负载均衡优化,提高图处理的效率;Ligra以图为中心的计算方式,提出一种轻量级图处理框架,其重点在于使图遍历算法更容易实现;GRACE则重点针对同步模式,提出一种可以根据应用处理需求,由用户决定切换同步执行还是异步执行的并行图处理框架.
而GraphLab是一种基于图模型的处理机器学习算法的异步并行框架.
在内存存储系统方面,单节点内存计算在数据库方面应用较多.
比如早在上世纪80年代,全内存数据库MMDB[30,31],其思路是,将整个数据库存入内存,即可加快数据处理.
然而在当时,由于内存价值高,这种思路只是理论论述,直到近些年内存数据库对于企业级用户来说才可实现.
比如:Hyper[32]是一种混合式OLTP和OLAP高性能内存数据库;Hekaton[33]是一个针对事务处理(TP)的基于行的内存数据管理系统,其为遗留应用程序提升10倍的TP速度、为新优化的应用提升50倍的速度,且完全集成进SQLServer.
又如,图数据库WhiteDB[34]是建立在共享内存上的一个轻量级的NoSQL内存数据库,它没有服务器进程,可直接对其共享内存进行读写.
Neo4j[35]同样是建立在单节点众核上的一种广泛使用的内存2150JournalofSoftware软件学报Vol.
27,No.
8,August2016图数据库.
相对分布式内存计算而言,单节点内存计算资源利用率高、处理效率高,不需要管理集群及考虑容错,也不存在节点间通信的巨大开销,系统性能也具有较强的可预估性;从编程者的角度来看,调试及优化算法比分布式更容易.
缺点是单节点CPU、内存等资源有限,在单节点计算机上处理现实世界的大数据,则很可能面临内存不足的情况(out-of-core).
在此情况下,内存数据处理的解决方案有3种趋势.
(1)内存压缩技术.
Ligra+[36]系统就是在Ligra系统之上添加内存压缩技术,达到和Ligra相当的性能.
(2)提高I/O访问效率.
Graphchi[37]正是针对内存不足的情况,采用内存并行滑动窗口机制的一种单节点众核并行图处理框架.
PrefEdge[38]通过预取减少了固态硬盘I/O随机访问次数.
X-Stream[39]利用了流数据的顺序访问特性,对其与随机访问进行折中.
实验表明:X-Stream在拥有3TB磁盘的单节点系统上,可处理含640万条边的图数据.
(3)使用高速I/O设备,比如固态硬盘阵列.
FlashGraph[40]即为基于固态硬盘阵列的异步图处理框架,它采用消息传递机制,以顶点为中心,在处理数据过程中,图顶点和算法状态存于内存,边存于外存当中,其处理性超出X-Stream和Graphchi几个数量级.
2.
2基于分布式系统的内存计算单节点内存计算受硬件资源限制,在处理更大规模数据时面临硬件可扩展方面的问题.
在以MapReduce为代表的大规模分布式数据处理技术快速发展的背景下,人们也开始在分布式系统上实现内存计算.
这种内存计算利用多台计算机构成的集群构建分布式大内存,通过统一的资源调度,使待处理数据存储于分布式内存中,实现大规模数据的快速访问和处理.
根据内存计算的主要功用,可将基于分布式系统的内存计算进一步分为3种类型.
2.
2.
1内存存储系统近年来,磁盘容量快速增长,在过去的25年中增长10000多倍,且还有继续增长的态势,但磁盘访问性能增速远低于容量增速,同时期数据传输率仅提高了50倍,寻道时间及转动延迟仅降低为以前的1/2.
因此,磁盘I/O成了主要的数据访问瓶颈,难以满足在线海量数据处理需求.
为此,就有了这样的技术思路:将内存作为存储设备,数据全部存入内存,而将磁盘仅作为一种备份或存档工具.
RAMCloud[41]是一种典型的分布式内存数据存储模型,这种分布内存计算是通过上百台甚至上千台服务器互联,形成分布式内存存储系统,且易于扩展.
其思路是,所有数据一直缓存于内存中.
与基于磁盘的数据处理相比,该系统的延迟小100~1000倍,吞吐量大100~1000倍.
考虑到内存易失性问题,RAMCloud采用复制和备份技术,以保证它具有像磁盘存储系统一样的持续性和有效性,这也保证了内存数据和磁盘数据的同步性、一致性以及容错.
但是,这样内存系统存在一定的缺点,即:其能耗很高,是磁盘系统的50~100倍.
因此它适合有大吞吐量需求的应用,而对一些不需频繁访问且占大量存储空间的数据的应用不太适合.
另一种典型内存存储系统是分布式内存数据库,包括分布式内存关系数据库,如H-store[42],VoltDB[43],ScyPer[44]等,分布式NoSQL数据库,如MemepiC[45],Rediscluster[46]等以及分布式内存图数据库ArangoDB[47],GraphEngine[48],SqrrlEnterprise[49],Titan[50]等.
大规模数据处理应用常常要处理PB级的数据[51],将这些数据全部存储于内存中一方面会占用大量内存资源,增加成本和功耗;另一方面,过大的内存空间也使得数据检索和访问效率降低.
鉴于此,在提供分布式大内存的同时,也出现了另外一项重要的技术——内存压缩[5254].
内存压缩技术根据压缩率的不同分为轻量级压缩[5557]和重量级压缩[58],根据基于软硬件不同分为软件压缩[42,59]、硬件压缩[60,61]和软硬协作压缩[62,63],但其最终目的有3个:(1)提高访问效率,有利于查询性能的提高;(2)减少内存数据量,从而降低内存消耗;(3)提高内存使用效率,减少CPU等待时间,增加片间互连网络带宽利用率.
2.
2.
2内存缓存系统利用内存作为缓存这种计算方式[6467]已经提出20多年,但直到近些年,随着硬件技术的发展,内存缓存系统才出现大量新的研究,比如Memcached[68],BigTable[69],PACMan[70]和GridGrain[71]等等.
内存缓存产生的技术罗乐等:内存计算技术研究综述2151背景是:磁盘容量往往比内存大两个数量级,这就说明,想通过内存缓存加速数据批处理,将内存作为数据永久存放处不太现实,在很多情况下,只能将内存当作缓存.
因此,这类内存计算把数据分为访问频率高和低两类,将访问频率高的部分数据长久存放于内存当中,或者将一些重要数据长期缓存于内存当中.
比如,谷歌和雅虎将其检索索引全部存于内存当中,Memcached都是将其所有通用"键-值"对存于内存中,BigTable存储系统把它所有列族缓存于内存.
这样可以高效利用内存计算.
然而,内存局部性在很大程度上影响着作业的完成时间.
只有当作业的所有任务都从内存中读取数据时,作业的完成才会被加速.
相反,即使只有小部分任务不是从内存读取,那么这小部分任务(outliers)会拖慢整个作业的完成时间[72].
研究表明,大数据应用具有不同于传统应用的数据局部性特征.
一个突出表现是,大量的数据仅被访问一次.
文献[73]根据Facebook的hadoop日志指出:保守地看,64%的作业具有任务局部性,有75%的数据块只被访问一次,这将大大降低内存缓存的效率.
因此,对于内存缓存,仍然有很大的提升空间和面临的挑战.
体现在如下两个方面.

(1)内存替换策略很多替换策略只是为了单纯的提高命中率,但是提高命中率并不能一定加快任务完成时间.
所以对于内存缓存来说,缩短任务完成时间才是最主要的目标[73].
在众多内存替换策略中,比如LFU,LRU等,虽然达到了一定的效果,但仍然有提升空间.
其原因在于:替换策略主要目标在于使整个作业的所有任务缓存于内存当中,以便于并行处理,消除outliers,提升整个作业执行效率.
如,文献[70]针对这种状况提出两种替换策略,其原理是:或将作业的所有并行任务缓存于内存中,或者所有任务都不缓存于内存中,即,所谓的all-or-nothing原则.
(2)预取对于一些只被任务访问一次的数据块,不具有内存局部性.
如前所述,某些应用中这种数据占到75%左右.
对于这种数据,只能通过预取的方式提高内存命中率,加快处理效率.
例如,一种选择就是将最新产生的数据预取进内存.
另外,如果作业有多个任务,我们可以根据第一个任务作为线索装载进其他任务的数据块.
文献[74]提出一种内存管理框架,通过前几次从磁盘上读取数据的行为预测以后要读取的数据,进而来设计出一个预取策略.

将数据缓存到内存中可以大幅提高数据处理效率,但在可靠性及其带来的问题方面存在不足.
如果集群中一个节点出现故障,那么将会产生集群内节点间的大量数据移动和复制,这将带来较大的存储和通信开销.
所以,如何避免或减少容错带来的节点间数据移动和复制开销,是这类内存计算面临的一个挑战.

2.
2.
3内存数据处理系统与前两类系统不同,此类系统从支持大数据应用角度出发,主要面向迭代式数据处理、实时数据查询等应用,通过提供编程模型/接口以及运行环境,支持这些应用在内存中进行大规模数据的分析处理和检索查询.
其处理机制是:首先将待处理数据从磁盘读入内存,此后,在这些数据上进行反复的迭代运算,即,除了第一次需要涉及I/O操作,此后便一直从内存读写数据.
此类内存计算不涉及预取数据,而且在内存管理方面使用内存替换策略也非常高效,因此在很大程度上提高了处理效率.
近些年出现了众多此类内存计算的框架/系统,最具影响力的是加州大学伯克利分校开发的Spark,它适用于迭代式及交互式的数据批处理应用,其原理即:将数据第一次从磁盘读入内存,生成一种抽象的内存对象,即,弹性分布式数据集(resilientdistributeddatasets,简称RDD)[75],此后,用户程序只操作在内存当中的RDD,计算过程只涉及内存读写,因此大幅提升了数据处理效率.
Piccolo[76]同样面向需要迭代处理的应用,比如机器学习、图算法、科学计算等问题,它主要将分布式的共享中间状态以key-value表格存于内存当中,以便高效解决分布式多线程之间共享变量的问题.
Pregel[77]和HaLoop[78]都是基于分布式内存计算的图数据处理框架,前者将中间结果存于内存用于迭代计算,后者提供一种迭代式的MapReduce接口.
Twister同样提供了一种迭代式的MapReduce模型,用户可创建MapReduce作业让其迭代计算,其中,数据在迭代时被保存在内存当中.
另一种典型的内存批处理应用为M3R[79],它是MapReduce的内存实现框架,适用于反复分析大量数据的应用,并且提供了向下兼容MapReduce的接口,相对MapReduce大幅提升处理效率.
另外,研究发现[8083]:在数据密集型环境下,存在大量程序以相同或者略微不同的输入反复运行多次.
文献[84]在基于M3R系统之上提出了MapReuse系统,2152JournalofSoftware软件学报Vol.
27,No.
8,August2016使得计算重使用发生在内存数据结构中,而不是文件系统,这样极大地加快了In-MemoryMapReduce的处理速度.
另外,内存实时数据处理近年来也发展迅猛,包括Sparkstreaming[85],Storm[86],Yahoo!
S4[87],MapReduceOnline[88]等等.
此类内存计算研究包括以下几个关键点.
(1)容错机制内存数据的易失性,使得内存计算环境下数据恢复和容错至关重要.
MapReduce的容错机制主要通过定期检查节点,对于出现故障的work节点,其上的任务要重新执行;对于出现故障的master节点,通过从集群其他master上复制数据并传输到本地的方法来解决.
因此,对于MapReduce来说,容错涉及到从磁盘到内存,从集群中的其他节点到本地的数据移动.
这对于对实时性要求很高的内存计算来说是非常耗时的,因为网络数据移动的延迟远远大于本地的数据移动,吞吐量也远远小于本地数据移动.
目前的一些集群内存存储系统,比如分布式共享内存[89]、键/值存储[41]、内存数据库等,都提供了基于细粒度更新可变状态的接口,这些接口的容错方式就是通过集群中节点间的数据移动和复制,或日志更新集群间各个节点.
而这两种方法对于数据密集型负载来说开销太大,原因在于:这些方法需要在集群网点节点间复制大量数据,而网络带宽又远远小于内存带宽,这将导致大量存储开销.
Spark采用了基于粗粒度的转化的接口,这种转化操作在计算过程中形成一种有向无环图(DAG),称为"血统(lineage)","血统"实质上是建立一种数据间转换的关系,而不是数据本身,因此当出现系统故障时,便可通过这个"血统"提供的信息,计算丢失的数据,即以计算换取数据移动和复制,这样即可大量节省容错所带来的开销.
同样,在Nectar[82]系统中,同样采用了"血统"容错,只是在特定编程框架下才采用"血统"容错,在传统的情形下,还是通过复制数据来解决容错问题.
Tachyon[90]也采用了"血统",使得在运用内存缓存容错时,数据恢复得到Memory访问速度级别的加速.
另外,虽然"血统"通过计算解决了不用复制和移动数据的问题,但是当"血统"的有向无环图很大时,则需要较长的时间来计算恢复数据.
在这种情况下,Spark和Tachyon都采用了检查点机制来解决"血统"链很长所带的计算开销问题.
目前,容错处理主要有数据移动和复制、日志机制、分布式锁、快照、检查点机制等等.
但是正如文献[80]所述,由于带宽限制,数据复制等数据恢复机制带来巨大开销,而基于"血统"容错的方法能很好地和内存计算在处理速度上相协调,因此,这可能将成为内存计算未来主要的容错方法.
(2)同步分布式内存处理系统主要处理机器学习、图算法、科学计算等问题,此类问题在并行计算的同时,往往涉及到结构或逻辑上的依赖关系,而并行处理的各个步骤在到达稳定点的时间不同,因此需要在并行进行的计算步之间进行同步控制,以保证结果的正确性.
常见的同步方式有同步计算、异步计算和混合方式.
目前,大多数内存计算系统采用BSP[91]同步,部分系统采用异步机制.
Spark和Pregel都采用BSP同步机制,而基于内存计算的分布式内存共享图处理系统PowerGraph[92]则采用BSP同步和异步两种方式.
Trinity[93]同样采用BSP同步和异步两种方式.
同步方式可确保计算的确定性,易于设计、编程和测试.
但是由于每个计算步的处理时间不同,最慢的计算将严重影响整体收敛速度.
异步处理模式的优势在于可加速计算的收敛速度,但其编程复杂,不便于调试和测试,不能保证更新一致性,且结果不确定.
两者各有优缺点,如何根据不同应用系统类型,取两者优点设计出高效且易于编程的同步机制越来越重要.
(3)内存分配与管理内存计算的核心资源为内存,因而内存分配与管理显得尤为重要.
如何在内存中安排数据存储方式,使数据访问更为高效且内存资源充分利用,这是首要解决的问题.
在实际的应用实例中,应用类型不同,内存数据安排也不尽相同,如Spark系统采用"键-值"存储方式,Piccolo采用内存表格方式及"键-值"两种方式,Pregel采用了BigTable的内存组织方式.
另外,内存容量总是有限的,如何高效利用有限的内存资源处理海量文件又是一个挑战.
Spark将内存数据罗乐等:内存计算技术研究综述2153抽象成RDD,然后在内存不足时,利用"最近最少使用"(LRU)内存替换策略协调内存资源.
同时,为了更灵活地分配内存资源,Spark可以通过所谓的RDD"持续存储优先权"给用户一定的管理权限.
总之,在此类内存计算当中,同样存在内存替换策略的选择.
因此,如何根据具体的编程框架的优缺点选择高效的内存替换策略,有待进一步研究.
(4)网络瓶颈谷歌的一份报告[94]显示:从内存读取数据比从本地磁盘或集群网络中其他主机读取数据快两个数量级,而磁盘和集群网络读取速度又处于同一数量级.
因此,在本地处理数据时,数据存在于内存当中,CPU很少停下来等待磁盘I/O,这样,内存计算解决了磁盘I/O瓶颈;但是,如果涉及到节点间通信或数据传输,则要比直接在内存读写慢两个数量级,内存计算必然面临一定的效率损失.
因此,在分布式集群内存计算当中,网络瓶颈成为主要瓶颈.
如何减少节点间的通信和数据传输开销,提高内存计算效率,这又是一个挑战.

2.
3新型混合内存结构的内存计算近几年,新兴的非易失性随机存储介质(non-volatilememory,简称NVM)快速发展,如铁电存储器(ferroelectricrandomaccessmemory,简称FeRAM)[95]、相变存储器(phasechangememory,简称PCM)[9698]、电阻存储器(resistiverandomaccessmemory,简称RRAM)[99]等,其性能接近DRAM,但容量远远大于DRAM,同时,能耗和价格远远低于DRAM.
这为新型的内存体系结构提供了良好的硬件保障.
因此,基于新型存储器件和传统DRAM的新型混合内存体系在大幅提升内存容量,降低成本的同时,其访问速度与DRAM相当.
在众多的非易失性随机存储介质中,PCM凭借其非易失性、非破坏性读、读完无须回写、写操作无须先擦除、存储密度高等特性,逐渐成为大规模内存系统中颇具潜力的DRAM替代品[98].
在硬件体系结构方面,研究者围绕PCM和DRAM的混合方案开展了很多研究,国内外学术界出现的混合内存结构大概分为3类.
2.
3.
1线性统一编址混合内存这种混合内存结构由PCM和DRAM构成[100,101].
通过软件和硬件技术,避免了PCM较短的写寿命和较高的写能耗的缺点,充分发挥了PCM在读数据和存储数据方面低功耗、非易失性和DRAM在写数据时低功耗及超长的写寿命的特性.
实验表明:相比DRAM,PDRAM的能耗节省达到37%.
在PDRAM中,PCM和DRAM处于同等地位,无主次之分,对两者进行统一的线性编址,如图1所示.
Fig.
1Hybridmemorystructuresharingasinglephysicaladdressspace图1线性统一编址混合内存结构2.
3.
2以DRAM作为PCM缓存的混合内存这种混合型内存体系结构是由DRAM和PCM共同组成,其中,PCM作为主存,DRAM作为PCM的缓存,2154JournalofSoftware软件学报Vol.
27,No.
8,August2016其主要目的是利用PCM高容量以及DRAM快速访问的特点,同时,避免了PCM访问速度慢及DRAM容量小能耗高所带来的问题[102104].
另外,文献[104]中通过3种技术来减少PCM上的写操作,以达到延长PCM寿命的目的.
实验结果表明,这种内存系统较传统的内存容量提高了4倍,页错误平均降低5倍,PCM写操作次数降低了3倍,可延长PCM寿命3~9.
7年;且当DRAM容量为PCM的3%时,PCM较DRAM的访问延迟得到了很多的弥补.
图2描述了这种内存系统与传统内存系统的区别.
L1cacheL2cacheCPUMainmemoryDRAMcachePCMmemoryFig.
2HybridmemorystructureusingDRAMascache图2DRAM缓存混合内存结构2.
3.
3分层混合内存(hierarchicalhybridmemory)文献[105]中提出一种名叫MN-MATE的混合内存.
这种内存是由PCM和DRAM构成,具有层次结构.
这种层次内存分为片上和片下两部分:片上内存由单独的DRAM构成,因其内置于处理器因此具有较小的延迟;片下部分则由PCM和DRAM混合构成,两者共用同一个内存控制器且采用统一的线性编址.
如图3所示,M1为上片,M2为下片,分别由PCM和DRAM通过线性编址组成.
同样,这种内存结构通过3种技术发挥了PCM的大容量低能耗以及DRAM访问速度快的优点,提高内存性能和减少能耗.
CacheM1memoryCPULineraaddressspaceM2memoryPCMmemoryDRAMcacheFig.
3Hierarchicalhybridmemorystructure图3分层混合内存结构另外,虽然诸如PCM等新型存储介质和DRAM构成的混合内存在硬件技术方向的研究已经进展不小,但罗乐等:内存计算技术研究综述2155是其相应的软件平台研究仍相对滞后.
现阶段想要利用新型混合内存处理实时大数据,仍然有很多工作做要.

虽然各种新型NVM在容量、能耗方面比当前的DRAM更具有优势,但是在访问速度、写寿命等方面仍然不及DRAM[96].
比如:对于PCM存在的缺点,文献[106]通过使用消除冗余位写入、行替换和段交换等方法降低损耗,可延长PCM的使用寿命13到22年;为了解决混合内存中PCM写数据速度慢且写寿命较短的问题,文献[107,108]分别提出不同的内存管理技术,通过不同的预测写操作算法,让大多数写操作发生在DRAM而非PCM,从而延长了PCM的写寿命,并且可以隐藏PCM写数据慢的缺点;文献[109]不仅采用减少PCM写次数的方法延长PCM寿命,还采用了提高DRAM缓存命中率的方法,从两个方面来优化混合内存结构的能耗和性能.
此外,针对PCM等新型随机存储介质的缺点,还有众多研究从软硬件层面提出了很多的改进措施,也取得了不错的效果[98,110,111].
在硬件体系结构方面,这种内存计算的主要革新表现在:在原来的DRAM基础上,通过加入新型SCM扩展成了不同类型的混合结构大内存,访问速度接近于DRAM,而容量远远大于DRAM.
在这种内存计算模式中,SCM不仅可作为内存,而且相当于传统磁盘,计算可以直接发生在SCM上,避免了传统的内存—磁盘数据访问,CPU直接从内存读取数据,进行计算分析.
同时,这种新型内存架构也带来了一系列问题:(1)各种新型内存与DRAM存在访存速度、能耗、读写寿命等方面差异,如何协调这些差异,使整个内存处理效率较高,能耗较少(2)随着众核处理器性能越来越高,异构内存容量增大,如何处理大内存与众核处理器间不断加大的带宽鸿沟(3)内存较原来更大,如何应对大内存带来的高能耗问题相对于硬件体系结构,在软件方面,这种内存计算的相关研究滞后很多.
因为作为一种新兴的混合内存结构,它涉及到体系结构、操作系统、编程模型方面的诸多问题.
(1)体系结构由于新型内存替代了磁盘可以长期存储数据,那么传统的磁盘数据访问局部性将被内存访问局部性取代而成为性能优化的主要目标;并且,传统的磁盘数据预取、缓存以及替换策略无法直接迁移到非一致缓存访问以及非一致内存访问环境中.
(2)操作系统由于新型混合结构的出现,操作系统需要统一管理多种异构资源,实现高效的、透明的、可靠的内存访问与管理策略.
另外,由于新型内存容量增大,可用地址空间随之增大,致使操作系统内存管理开销增大.
所以,为了提高操作系统对内存管理效率,需要研究新的编址策略和访问方式.
(3)编程模型新型混合内存解决了磁盘I/O瓶颈问题,因此在内存计算当中,传统的编程模型对数据传输不再占大量处理时间,而数据处理将占据大量处理时间.
此外,由于新型非易失性内存的I/O延迟远小于磁盘,传统模型中磁盘与内存的数据一致性等问题不复存在,编程模型也因此有相应改变.
3典型内存计算应用当前,内存计算的应用类型众多,本文以4类典型的内存计算应用为例,深入剖析当今内存计算的发展和其存在的诸多挑战.
3.
1内存数据库内存计算技术的再次兴起,始于其在内存数据库方面的广泛应用.
早在1994年,内存墙[112]问题提出之后,为了减少内存墙的影响,针对缓存层次结构[113],出现了大量以缓存为中心的内存数据库系统研究,如MonetDB[114],EaseDB[115],FastDB[116],TimesTen[117]等.
而随着内存的容量大幅增长,特别是分布式集群环境下内存容量已经能够满足对海量数据处理的要求时,2006年之后,出现了面向事务处理和数据分析的两大类内存数据管理系统,这类系统包括H-store,VoltDB,HANA,DryadINQ[118],Pig[119],FlumeJava[120],Ciel[121],Twister[122]等等.
2156JournalofSoftware软件学报Vol.
27,No.
8,August2016表1列出近几年较为典型的一些内存数据库系统.
Table1Comparisonofsomein-memorydatabases表1部分内存数据库系统对比系统系统结构索引内存数据结构并发控制容错内存不足类型SAPHANA分布式时间线索引/CSB+-树/倒排索引关系/图/文本多版本并发控制协议日志/检测点/备份服务器Partition-levelswapping/内存压缩关系数据库H-Store分布式哈希/B+-树/二叉树关系Partition/顺序执行Commandlogging/检测点/数据复制Anti-caching关系数据库Hyper单节点哈希/平衡树关系虚拟快照/严格时间戳日志/检测点/数据复制内存压缩关系数据库MemepiC分布式哈希/跳表键-值原语日志/数据复制用户空间虚拟内存管理NoSQL数据库Trinity分布式N/A图细粒度自旋锁数据复制N/A图数据库Bitsy单节点嵌入式N/A图乐观并发控制日志/备份N/A图数据库MongoDB单节点B-树文档数据库级锁内存映射文件N/ANoSQL数据库不难看出,内存数据库研究热点以及面临的挑战主要存在以下几方面:(1)索引.
内存数据库中索引的建立与传统数据库不同,其主要目的是为了减少内存密集的扫描.
怎样建立一个合理的索引,以达到优化内存数据库时间和空间效率的目的(2)内存数据组织.
在内存数据库里,内存中的数据组织对内存和缓存的使用有很大的影响.
比如,基于列的关系表可以提高cache命中率,同样可以获得良好的内存压缩率,节省可观内存空间;但是这种数据组织对于OLTP查询来说不是一个好的选择,因为基于行的安排更能提高OLTP查询的效率.
所以,如何根据情况设计合理的内存数据组织,这对进一步优化内存及缓存的使用显得非常重要.

(3)并发控制.
随着众核系统的不断发展,在内存数据库中,并发控制显得更加重要.
基于锁的重量级机制控制效果好,但是其开销大,影响系统总体性能.
如何在内存系统下,根据内存计算自身特点设计合理的并发控制策略,既可以达到并发控制的效果,又不太影响系统性能,这同样是一个挑战.

(4)容错.
与传统数据库相比,由于内存的易失性,导致内存数据库对于ACID中的持久性不能很好支持.
因此,当突发性故障,比如断电、软硬故障发生时,如何设计出合理的策略使内存数据不丢失(5)内存不足.
尽管如今内存容量越大越大,但是其增长速率无法赶上数据量的增长,这势必导致总内存不足的情况出现.
在硬件方面,如何利用新型大内存设计出有效的内存系统以应对快速增长的数据,以及在软件方面,如何设计出有效率的策略来解决内存不足的现象,这些都是科研工作者将要面临的挑战.
3.
2内存图计算过去10年内,基于图的应用快速增多.
在网络中寻找最短路径、计算网页的PageRank以及更新社交网络等等,都需要进行大量的计算存储资源.
为此,图计算变得越来越重要,而由于图数据规模的快速增长,内存计算快速成为当今图计算的热点问题.
由于图的计算中涉及到边与边的依赖关系,以及图计算缺少数据并行性,所以大规模图处理使得MapReduce显得力不从心.
为此,近几年出现了大量内存图计算的模型,比如Pregel、GraphLab、Piccolo、基于Spark的GraphX[123]等,其中,Pregel和GraphLab是以顶点为中心的计算模型.
表2为近些年的部分图模式对比.
内存图计算为内存计算的一个应用,同样,它涉及到内存分配管理、同步和容错机制.
但是图计算有其自身的关键研究点,主要包括以下两方面:(1)图划分.
图划分是图处理的首要步骤.
一个好的划分,可以使负担均衡,减小节点间通信开销以及提高计算效率.
换言之,如何合理划分大规模图数据,对图处理效率至关重要.

罗乐等:内存计算技术研究综述2157(2)计算模式.
图的计算模式分为以顶点为中心、以边为中心及以图为中心这3种计算模式.
不同计算模式对不同应用的图的处理效率有极大的影响,比如,以顶点为中心的计算模式适用于PageRank、图挖掘等应用,以图为中心的计算模式适用于聚集计算.
3种计算模式各有优缺点:以顶为中心的模式编程简单,但是收敛慢;以边为中心的模式避免了边数据随机访问,但涉及到随机访问顶点,计算模型复杂;以图为中心的连通计算性能较好,但划分图负担过重.
所以,没有完美的计算模式,我们需要根据不同应用设计合理的计算模式.
另外,对于通用性的应用,计算模式的设计就更为困难.

Table2Comparisonofsomein-memorygraphprocessingframeworks表2部分内存图处理框架对比图计算系统同步划分方式内存组织容错体系结构GraphXBSP同步哈希键-值血统/检测点分布式PowerGraphBSP同步/异步边切割/启发式顶点切割N/A快照分布式PregelBSP同步哈希BigTable检测点分布式GraphLab异步/同步哈希N/A检测点单节点众核/分布式Graphchi异步Interval滑动窗口N/A单节点众核GraceBSP同步哈希/启发式划分数组N/A单节点众核Piccolo同步用户控制表划分内存表/键-值检测点分布式3.
3其他内存计算应用由于众多机器学习算法涉及到大规模数据的反复迭代运算,比如分类算法需要通过大量数据多次迭代计算,进而产生训练模型中的参数,因而,将需反复运算的数据存放内存中将大幅加快此类计算速度.
因此,内存计算非常适合此类应用.
近几年出现多种基于内存计算的机器学习框架,如建立在Spark之上的MLlib[124]是最为知名的基于内存计算的机器学习算法库,它支持分类、聚类以及矩阵分解(如主成分分析(PCA))等算法.
另外,还有基于异构分布式系统的大规模机器学习系统TensorFlow[125]、训练深度学习网络的框架SparkNet[126]等.
内存计算的另一个典型应用为流数据处理,即实时计算.
这类应用常见于大型网站的访问数据处理、搜索引擎的响应处理等,一般涉及海量数据处理,响应时间为秒级.
而内存计算将海量数据存于内存,为实时数据处理提供了保障.
当今主流的基于内存的流处理系统有SparkStreaming[85],Yahoo!
S4[87],Storm[86]等.
4内存计算面临挑战及展望尽管内存计算为当前工业界和学术界高度关注的热点问题,然而内存计算涉及硬件体系结构、软件体系结构、操作系统、编程模型、大数据处理等诸多方面内容,使得内存计算从底层的硬件架构到高层的编程模型都存在许多问题,面临一系列挑战.
因此,本节对这些问题及挑战从总体层面到应用层面予以梳理.

4.
1总体层面的问题与挑战内存计算的兴起,主要源于硬件的快速发展以及大数据的处理需求.
大数据处理复杂,主要原因有3方面:数据量大、增长速度快、数据种类多[127,128].
因此,无论单节点内存计算还是分布式内存计算,都将面临诸多问题.
单节点内存计算面临的主要问题是系统性能容易受限于硬件资源的不足,比如内存不足时,如何高效地访问I/O,提高单节点内存计算的性能而分布式内存计算面临的主要问题是通信问题,网络通信在分布式内存计算中起着十分重要的作用:容错时的数据复制,节点间相互协调时的数据信息交换,数据共享或负载平衡所需的数据传输等等.
另外,相比与如今越来越大的数据量,单一节点内存大小有限,进一步增加了网络通信的需求.
然而,内存与网络间的数据访问延迟差距巨大,使得网络通信效率对整个内存计算中的性能有极大的影响.
因此,如何处理随着通信量大幅提升及通信多样化所带来的内存与网络间的访问延迟鸿沟,是当前分布式内存计算面临的主要问题.
不管是单节点还是分布式内存计算,都将面临着大规模并行带来的并发性控制问题.
一个高效的并发控制协议既要保证原子性和隔离性,又不能影响并行执行所带来效率提高.
随着集群规模的扩大和单节点CPU核数的增加,大量进程/线程平行执行,从而显着地增加了并发控制的复杂性,对高效的并发控制带来了巨大挑战.
研2158JournalofSoftware软件学报Vol.
27,No.
8,August2016究[129]显示,目前并发控制算法还无法扩展到1024个核以上.
因此,如何提高并发控制的可扩展性越来越重要.
集群调度是过去几年来最为广泛研究热点问题之一[130135],但如今,随着数据量激增,集群规模扩大,任务调度将成为分布式处理性能提高的瓶颈[136].
原因在于:当前流行的数据处理系统,比如Dryad[118,137],Spark,GraphX等采用中心控制器(master)调度任务,当集群中工作节点(workers)数和任务数过大时,这种调度方式必然成为整体性能提升的瓶颈.
由此,针对数据规模的激增以及集群规模的扩大,研究者们开始作类似图计算框架,如GraphLab[29],PowerGraph[92]和Galois[138]中的调度策略——控制器负责分配数据,工作节点负责在本地生成任务[139].
因此,随着大数据时代来临,集群调度又将成为分布式内存计算的热点问题.

随着新型非易失性存储器的快速发展,如何用其替换或补充原有的DRAM作为主存,成为工业界和学术界的研究热点[98,104,106,140147].
而内存计算同样为当今工业界和学术界关于大数据处理的热点,比如数据库系统方面,IBM的Blink项目[148]中,MicrosoftSQLServer[33]和SAPHANA[15]等都采用内存存储及处理数据.
此外,在更广泛的数据密集型计算领域,有很多学术界的研究和工业界的产品都是基于内存计算,如Memcached,Pregel,Ramcloud和Spark等等.
因此,大数据时代的一个必然趋势是主存容量的快速增长及其在内存计算中的作用愈发的重要.
那么,随之产生众多新的研究问题.
总体上讲,如何应对新型大内存在体系结构、操作系统、编程模型方面的诸多挑战:在细节的方面,如何将现有的内存数据库、内存数据处理框架迁移到新型非易失性内存上,并且充分利用新型非易失性内存的大容量和非易失性;如何应对大容量内存与处理器之间的带宽鸿沟.
这些都是内存计算将要面临的挑战.
4.
2应用层面的问题与挑战内存计算从硬件架构来看,不管是单节点、分布式,还是基于新型混合内存系统,最终表现为软件层次的应用,比如内存存储系统表现为内存数据库,内存数据处理系统表现为图计算系框架、机器学习算法处理框架、流处理框架等.
内存数据库将整个数据库装载进内存,避免了传统数据库I/O操作所带来的开销.
这样,内存数据库性能提升的瓶颈从传统的I/O访问便转为如何提高计算时间及减少访存延迟,具体表现在前文所述几方面的挑战,即索引建立、内存数据组织以及并发控制策略等,以达到优化内存数据库时间空间效率,优化内存及缓存的使用,保证系统性能的目的.
另外,硬件的快速发展正在迅速改变商用处理器的场景,如NUMA架构[149]、SIMD指令[150]、RDMA网络,硬件事务内存(HTM)[151]、非易失性存储器(NVM)以及片上GPU[152],FPGA和其他硬件加速器,可以以较低的开销提供更高的性能[151,153155].
综上,内存数据库性能的提升不仅面临软件方面的挑战与机遇,同样,硬件加速为内存数据库提出了新的挑战以及提供了新的发展前景.