大数据已成为目前学术界和工业界共同关注的热点问题，同时，闪存、相变存储器等新型存储技术也正在极大地影响着计算机系统的软硬件设计与应用。大数据管理面临着诸多的挑战，例如能耗、性能等，而新型存储介质则在I/O延迟、能耗等方面优于传统磁盘存储介质。面向新型存储技术的大数据管理旨在通过利用新型存储技术来解决大数据管理中的关键问题，但目前尚有许多问题还有待于进一步探讨。试图对面向新型存储技术的大数据管理的研究现状做一个梳理，理清几个问题，例如新型存储技术的快速发展对于大数据管理而言带来了哪些新的机遇和问题？引入新型存储后是否能够部分解决大数据管理中的挑战性问题?论文首先讨论了目前新型存储器的器件特点，总结了面向新型存储技术的大数据存储架构研究现状，对已经提出的主要核心算法进行了概述。最后，给出了基于新型存储技术的大数据管理的若干未来发展方向，以期能够对新型存储技术和大数据管理的未来研究提供新的线索。
   1.引言
    近年来，大数据已经成为学术界和工业界普遍关注的一个热点问题。维基百科中将“大数据”定义为无法在一定时间内用常规软件工具对其内容进行抓取、管理和处理的数据集合。目前一般认为大数据具有4V特征，即Volume，Variety，Value，Velocity。Volume特征是指大数据的规模巨大，通常是PB甚至ZB级别。在2011年，就产生了1.8ZB(也就是1.8万亿GB)的大数据，著名咨询公司IDC发布的报告中称全球产生的数据将在2020年达到40 ZB。Variety特征是指数据类型繁多。大数据超越了以事务为代表的结构性数据的概念，涉及了以网页为代表的半结构化数据以及形式多样的非结构化数据，如文本、音频、视频等，也涉及了物流、交通、医疗、农业、金融、工业等多样化的信息源。Value特征是指大数据的高价值信息密度低。以视频为例，连续不间断监控过程中，可能有用的数据仅有一两秒。Velocity特征是指大数据要求很高的处理速度。大数据的处理通常具有时效性，必须把握好对数据流的掌控应用，从而才能最大化地挖掘利用大数据所潜藏的价值。
    大数据的4V特征对现有的数据管理技术提出了许多新的挑战。从存储的角度看，大数据管理面临的主要问题可归纳为如下几个方面：
    (1)大数据存储架构的挑战:磁盘读写性能差，与主存的速度差距正在逐渐增大，使得传统的主存-磁盘存储架构越来越无法适应大数据管理的要求。
    (2)大数据管理算法的挑战:随着新型存储介质越来越多地被运用于大规模分布式存储中，大规模分布式数据库中传统的持久化策略、索引结构、查询执行、查询优化、恢复策略等均是基于磁盘存储设计的，新型存储介质具有完全不同于磁盘的物理特性，因此无法发挥新型存储的优势。
    (3)大数据管理的能耗挑战:能耗在现有大型数据管理系统(通常是数据中心)中的费用比例逐年升高(目前大约占总能耗的16%左右)，给企业带来了沉重的经济负担。
    与大数据技术同步发展的是新型存储技术。新型存储是相对于传统的磁存储介质而言的。鉴于磁盘在面临上述挑战时已显得力不从心，市场上对于新型存储器件的需求越来越强烈，国际上从2000年以来在闪存、相变存储器等新型存储器件的制造和产业化方面取得了重要突破，并已开始逐步在各类应用领域(如嵌人式系统、企业计算等)中使用。
    但是，新型存储技术的快速发展对于大数据管理而言带来了哪些新的机遇和问题?引人新型存储技术后是否能够部分解决大数据管理中的挑战性问题？这些问题目前在研究面向新型存储的大数据管理中还没有满意的答案。基于这一背景，本文试图对面向新型存储的大数据管理的研究现状做一个梳理，分析该领域中的已有进展，理清存在的新问题和新方向，从而为未来新型存储和大数据管理的研究提供有价值的参考。
    本文的后续内容安排如下：第2节介绍了新型存储，第3节总结了面向新型存储的大数据存储架构现状，第4节讨论了面向新型存储的大数据管理算法进展，第5节给出了面向新型存储的大数据管理未来发展方向，最后是论文总结。
   2.新型存储技术
    目前，主流的新型存储设计观点是IBM提出的存储级主存技术SCM ( Storage Class Memo-ry)SCM同时具有内存级存取和持久存储的特点，其主要特征为:非易失(寿命在10年左右)，DRAM的高速访问时间、价格低廉、固态无机械运动等。SCM的性能特点使其可以存在于存储系统的不同层次上：既可以作为主存，也可以作为内存与二级存储之间的缓存，也可以作为二级存储器。SCM技术的候选材料有很多，如闪存(Flash Memory)、磁性存储器MRAM(Magnetic RAM)，电阻式存储器RRAM ( Resistive RAM)和相变存储器PCM ( Phase-Change Memory，也称PRAM或PCRAM)等。其中闪存和PCM发展最为迅速，目前已经达到了实用化的水平，也是大数据存储中最可能引人的新型存储技术。
    2.1 闪存
    闪存是一种可以被电子化擦除和重写的非易失性存储设备，闪存将二进制数据存储在双层MOS管组成的记忆单元阵列中，MOS管中包含“浮动栅”和“控制栅”，数据位是1或者0取决于浮动栅上是否有电子，写入0时，向栅电极和漏极施加高电压，增加在源极和漏极之间传导的电子能量，这样一来，电子就会突破氧化膜绝缘体，进人浮动栅，即成功写人。读取数据时，向栅电极施加一定的电压，电流大为1，电流小则为0。
    固态盘SSD ( Solid State Drives)是目前闪存存储的最主要形式，主要由闪存芯片闪存转换层、址映射表寄存器、控制器等部件构成，其中闪存芯片用于存储数据，闪存转换层向操作系统提供逻辑页的访问接口，实现了逻辑页和物理页的映射，隐藏了闪存芯片上的写前擦除、异地更新，实现擦除块之间的磨损平衡等功能。并且使闪存设备可以处理USB， SAS， SATA命令，实质上将闪存存储抽象为与磁盘一样的块设备。
    目前闪存发展迅速，已在便携式存储设备上广泛应用，随着半导体技术的进步，容量也在不断增加，价格不断降低，闪存也越多越多地应用到大型存储中，例如，百度已经在2009年开始就在其搜索服务器上全部使用了固态硬盘。
    与磁盘介质相比，闪存具有一些特殊的物理性质：
    (1)无机械延迟：闪存作为一种纯电子设备，没有机械寻道操作，随机读的延迟很低。
    (2)读写不对称：通常闪存上的随机读速度较快，但随机写速度较慢。这是因为写人数据时，需要通过加压的方式对存储单元进行电子填充。
    (3)异地更新：传统磁盘采用的是原位更新机制(In-Place Update)，即可以直接用新的二进制位覆盖磁盘上旧的二进制位。但是，对闪存的写操作不是简单地改变某个二进制位，而是需要将所在的整个擦除块的所有二进制位全部重置为1，即需要先执行块擦除操作。块擦除操作会使得系统性能显著降低。
    (4)寿命限制：闪存芯片的块擦除次数是有限制的，超过一定擦除次数的闪存单元将不再可用。
    (5)低能耗：与磁盘相比，闪存的能耗更低，每GB读数据的能耗只有磁盘的200，写操作能耗不足磁盘的3000。闪存的出现为建设绿色数据中心以及低能耗数据管理系统提供了有力支持。
    2.2 相变存储器PCM
    相变存储器PCM是一种非易失类型的存储器，由硫系玻璃材质构成。由于这种材质的特质，通过施以电脉冲热，它可以在无定形和结晶这两种状态之间进行切换。PCM兼具速度快、耐用、非挥发性和高密度性等多种优势于一身，其读写数据和恢复数据的速度是当前应用最广一泛的非挥发性存储技术闪存的100倍。
    自20世纪60年代开始人们就已经在研究相变存储器，但直到2000年Intel和Ovonyx发布合作和许可协议才标志着大容量PCM研发时代的到来。2009年12月工业界推出了1Gb的PCM产品，2012年推出了8GB的PCM存储芯片。国内的中国科学院上海微系统所近年来也研制了8MB的PCM芯片。
    与磁盘以及闪存相比，PCM具有以下特性：
    (1)非易失性：与闪存一样，PCM是非易失的存储介质。
    (2)读取速度高：和DRAM一样，相变存储技术以随机访问性能高而见长，它可直接从存储器执行代码。PCM的读取延迟比闪存缩短1到2个数量级，而读取带宽可与DRAM媲美。
    (3)写人速度高：与DRAM一样，PCM具有位可变性(Bit Alterability)，将信息存储在位可变性存储器中，只需在1和0之间进行转换，不需要独立的擦除步骤。
    (4)字节可寻址：类似于DRAM， PCM也具有字节可寻址的特性。
    (5)写寿命长：PCM写寿命已经达到了10的8次方次，远超过了闪存的105次。随着技术进步，PCM的写寿命正在接近磁盘的写寿命(10的15次方次)，一定程度上解决了闪存取代磁盘过程中因耐写能力严重不足带来的缺陷，可以保证存储器更高的可靠性。
    (6)低能耗：PCM基于微型存储单元的相变存储数据，没有机械转动装置并具有低电压的特性(0.2V-0.4V)，同时由于相变存储器的非易失性，保存代码或数据也不需要刷新电流，使其成为理想的下一代绿色存储器。
    3. 基于新型存储的大数据存储架构
    闪存、PCM等新型存储介质的引人使得大数据存储架构有了多种选择。但是，由于新型存储介质在价格、寿命等方面与传统的磁盘相比不具优势，因此目前主流的观点是在大数据存储系统中同时使用新型存储介质以及传统存储介质，由此产生了多种基于新型存储的大数据存储架构，例如基于PCM的主存架构、基于闪存的主存扩展架构、基于多存储介质的分层存储架构等。
    3.1 基于PCM的主存架构
    由于PCM存储密度高、容量大、耗电低，而且访问速度接近内存，因此工业界和学术界都开展了将PCM作为主存系统的研究。PCM替代DRAM，首先必须考虑克服PCM写次数限制，即延长PCM的寿命问题。为了解决PCM寿命的问题，目前的研究重点主要集中在减少对PCM的写操作以及负载均衡等方面。
    在文献中，研究者提出了一种利用DRAM来减少对PCM写操作的方法。它将PCM作为主存，同时使用一块较小的DRAM作为PCM的缓存，并借助DRAM缓存来延迟对PCM的写操作，从而达到减少PCM写次数的目的。研究的实验结果表明，这种混合存储结构可以在使用13%左右的额外DRAM存储代价的基础上，有效地延长PCM的寿命。
    负载均衡思想是通过增加一层地址映射，将PCM的写均匀地分配给所有的存储单元，以尽可能达到PCM的最大使用寿命。在文献中，研究者提出了一种代数映射方法Start-Gap。它利用少量的寄存器来保存地址映射关系和执行地址映射关系的改变，通过定期将每一个存储单元迁移到他相邻的位置来实现负载均衡。文献提出了随机化Start-Gap算法，改进了原始算法中具有集中写特征的存储单元在迁移时可能带来的不均衡写问题。
    在针对大数据存储的集群架构中，负载均衡主要通过适合PCM的数据划分算法来实现。文献提出了一种针对服务器集群的PCM与DRAM混合主存架构，并基于该架构设计了一种新的数据划分算法。该算法实现了集群的全局负载均衡以及DRAM和PCM之间的数据合理分配，使混合存储系统表现出比纯DRAM系统和纯PCM系统更好的性能。
    PCM作为主存系统的思想对大数据管理的性能和能耗等问题的解决都有着重要的意义。虽然大数据应用中涉及的原始数据量非常大，但真正有价值的数据量以及应用每次需要存取的数据量仍是有限的，因此我们可以利用PCM的高性能、低能耗特性，将应用需要实时存取的高价值数据存储在PCM中，同时利用磁盘等传统存储介质维护大规模的原始数据。因此，将PCM引人到目前的存储架构中构建混合存储系统，将有望解决大数据管理中的性能与能耗问题。
  3.2 基于闪存的主存扩展架构
    与PCM相比，目前闪存的应用更为广泛。高速大容量固态硬盘SSD设备的不断出现，使得SSD在存储架构中的地位也得以提升。在大数据管理方面，目前SSD的存储容量还达不到大数据的PB级别存储需求，因此近年来的主要工作集中在利用高端SSD进行主存扩展的研究上。
    在文献中，普林斯顿大学的研究人员提出了一种利用SSD进行内存扩展的主存管理系统一SSDAIIoc。SSDAIIoc在存储体系中将SSD升到一个更高的层次，它把SSD当做一个更大、更慢的RAM而不是将它当做磁盘的缓存。通过使用SSDAIIoc，应用程序可以几乎透明地将他们的主存扩展到几百GB而不需要对软件重新设计，远远超出了服务器上RAM容量的限制。此外，SS-DAlloc能够提升90%的SSD的原始性能，同时将SSD的寿命提高32倍。
    在文献中，研究者以NoSQL数据库系统Redis为基础平台，用SSD代替磁盘作为虚拟内存中的交换设备，扩大虚拟内存的同时帮助NoSQL数据库减少数据读延迟，并针对SSD随机写性能差的特点，设计了针对SSD的写缓冲区优化算法和垃圾回收机制，从而提高了数据库系统的整体性能。
    考虑到当将SSD作为虚拟交换设备时，页面交换的代价依然较大，文献设计了一种基于DRAM与SSD的混合主存架构，将SSD作为主存，将 DRAM作为SSD的高速缓冲，以对象为单位管理资源。为了减少写放大，将SSD组织成log结构的顺序块，并将这种混合主存结构融人Mem-cached，大幅提升了Memcached性能。
    基于闪存的混合主存系统与基于PCM的主存系统在设计动机上类似—都是以性能为主要的目标。对于大数据管理而言，引人闪存(或者PCM)来部分地替代传统内存，可以有效地扩展内存容量，减少对底层大数据的频繁访问，从而提高大数据系统的数据访问性能。此外，在能耗方面，由于闪存和PCM的能耗都低于磁盘，因此也有助于降低大数据管理的能耗。
    3.3 基于多存储介质的分层存储架构
    基于不同存储介质的分层存储架构目前主要集中在DRAM、闪存、磁盘的混合存储研究上。一种观点是将闪存做为内存与磁盘之间的缓存。例如，F1ash Cache是Facebook为innoDB设计的块缓存应用，它将闪存划分为一个逻辑集合，基于组相联映射的思想将磁盘上的块数据映射到闪存中。当I/O请求到达时，Flash Cache会先在闪存中查找该数据是否已被缓存，如果有，则直接进行读写操作，否则访问磁盘。将闪存作为DRAM与磁盘之间的缓存进行数据预取或者预写，还可以充分发挥闪存读性能好的优点，减少对磁盘的写操作，同时减少系统能耗。另一种观点是将闪存与磁盘一样作为二级存储介质，手动或者自动地将不同类别的数据分配到闪存或磁盘。由于不同的存储分配策略以及存储介质组合方式对于此类系统的性能有着决定性影响，因此目前主要集中在存储分配、存储介质用量组合等方面。
    (1)在存储分配方面，已有研究倾向于根据I/O特性和数据的冷热程度来进行存储分配，将读倾向负载的数据或者热点数据存放在SSD上，而写倾向负载或冷数据等则存放在磁盘上。IBM在其企业级存储设备DS8700上增加了EasyTier自动封存存储功能，将较大的逻辑卷进行划分，并对划分后的子卷进行热度检测，如果是热点卷，就将其迁移到SSD上，同时把SSD上的非热点卷再迁回到磁盘。文献中提出的HRO方法将随机性强、热度高的数据分配在SSD上，顺序性强、热度低的数据分配在磁盘上，并设计了数据随机性检测算法。文献结合数据页的访问次数以及访问热度实现对页面的准确分类和分配，即将读倾向负载的热页面存储到SSD上，将写倾向负载的页面或者冷页面存储到磁盘上。文献为了增加闪存的寿命，使用数据I/O特性进行存储分配，以减少对闪存的写操作，以页为单位检测数据的I/O特性，将写操作较多的数据放置在磁盘中，而读操作较多的数据放置在SSD中。文献将随机数据和读操作倾向较多的数据倾向于放置在SSD中，顺序数据和写操作较多的数据倾向于分配到磁盘。
    分层存储的存储分配思想也被运用于针对大数据存储的集群中。例如，淘宝网采用了基于SSD，SAS和SATA的分层存储系统，并采用了两种不同的存储分配方法:一种是根据文件大小来定义迁移到哪种存储介质上；另一种迁移策略按访问的热度来进行分配。文献讨论了在Lustre集群文件系统上的对象存储服务器OSS(Object-based Storage Server)。该服务器是由SSD和磁盘阵列构成的混合存储系统，其中SSD主要用来存储较小的、访问频率高的对象，磁盘阵列用于存储较大的、访问频率低的对象。文献针对面向对象存储的Lustre集群文件系统，在对象存储结构上增加一层基于PCM新型存储设备的高速存储层，自动分析I/O访问特征，预测其后续操作，主动把可能需要的对象预取到PCM高速存储层，并且设计了预取和对象迁移算法。
    此外，面向分层存储的存储分配方法还应用在大数据文件系统的元数据管理上。在面向大数据管理的分布式文件系统中，利用分层系统存储分配用频率、规模等都不允许将所有数据统一存储于集中式的存储设备上，因此基于分层存储的多介质混合存储技术将越来越受到研究者们的重视。但是，由于多种存储介质的分层存储存在着多种组合方式，什么样的混合存储策略适合大数据应用、在多介质混合存储系统中如何有效地实现数据分配与迁移等仍有待进一步探索。
    4.基于新型存储的大数据管理算法
    由于传统的数据库技术取得了巨大的成功，因此许多研究者从数据库管理系统的角度研究基于新型存储的大数据管理方法。传统的数据库研究集中在存储管理、索引、查询处理等方面，因此本节也从这些角度来总结现有的基于新型存储的大数据管理算法。
    4.1 基于新型存储的大数据存储管理
    大数据存储通常采用分布式存储策略，但传统的分布式存储策略通常采用基于副本的方式。例如，MongoDB设计了复制集指定每个文档的副本保存位置，Hbase基于HDFS进行副本管理并采用机架感知的方式进行副本分布。但是，已有的这些分布式存储策略没有考虑不同存储介质的性能、成本以及物理特性上的差异。引人了多样化的新型存储介质后，需要设计新的数据分配算法，使数据分布在合适的新型存储介质上，从而加快数据的访问性能。
    Ramcloud是针对异构多存储系统设计的高性能分布式数据库系统。它针对异构存储系统的不同特性，采用了所谓的日志缓存(Buffered Log-grog)技术，将主数据放置在性能最好的存储系统上，而将副本以及数据更新日志放置在成本较低的存储上，既降低了成本，又保证了性能。
    此外，由于Web作为大数据的主要来源之一，开展基于Web的大数据研究是当前的一个主要研究方向。Web领域中广泛使用了NoSQL数据库技术，但在NoSQL数据库中引人闪存等新型存储介质后产生了许多新的问题，例如持久化策略。
    持久化策略是指将数据写人持久存储介质的策略。不同的持久化策略对于系统性能有着很大的影响。在现有的NoSQL数据库系统中，Redis以AOF日志的形式把更新操作顺序写人日志结构文件，累计多次写操作，进行集中地追加写操作。BigTable，Cassandra和Hbase都采用了类似LSM树结构来进行写优化，数据首先被入数据内存缓冲区的Memstore，当Memstore达到一定阑值时，缓存数据会被刷新到磁盘，生成一个新的存储文件持久化数据SSTable。逐步增多的SSTable文件会以滚动合并(Rolling Merge)的模式合并成更大的SSTable。LSM树结构的好处是优化了写操作，但在一定程度上降低了查询性能，而且SSTable的合并也会引入较大的内存开销。在NoSQL数据库系统中引人闪存之后，由于闪存具有异地更新特性，往往需要设计新的持久化策略。RethinkDB是一个SSD优化的分布式No-SQL数据库系统。它为了有效减少闪存异地更新和垃圾回收对持久化性能带来的影响，设计了“隐形Trim”机制，优化了持久化策略，通过将闪存存储层作为黑盒，使用基于性能、块大小等参数的演化推理机制找到最理想的工作负载模式，最终实现系统在闪存上的读写性能优化。
    基于新型存储的大数据存储管理与传统的数据库系统有着较大的差别。主要的一点在于大数据环境下的数据存储通常是分布式、分层的，而传统数据库系统中的数据以集中存储为主。因此，面向新型存储的大数据存储管理面临着存储介质异构性、数据分片、存储分配等问题。虽然NoSQL在Web领域得到了广泛应用，但能否作为大数据管理的统一平台还有待进一步研究。
    4.2 基于新型存储的大数据索引设计
    数据库索引管理是有效组织数据、提高数据库查询性能的关键技术之一。大数据管理中的索引设计主要考虑高扩展性、高性能，能够有效支持非主键查询和多维查询等不同类型查询，主要索引结构有二级索引、双层索引、按照空间目标排序的索引等。
    二级索引由局部索引和全局索引构成，局部索引只负责该节点上的数据索引，全局索引则依据局部索引构建，如Efficient B-tree ，RT-CAN，QT-Chord，EMINC等；双层索引主要适用于非键值列的快速查询，索引表由原数据表中的键值和索引列的组合构成，如ITHBase，IHBase ，CCIndex等；按照空间目标排序的索引有MD-HBase， UQE-Index等。
    目前二级索引中的局部索引均基于磁盘特性进行设计，如Efficient B-tree局部索引结构采用了B+-tree，RT-CAN局部索引结构为R-tree，EM-INC局部索引结构为KD-tree。闪存等新型存储的特性和磁盘具有明显差异，将基于磁盘的索引实现方法直接移植到新型存储上会严重响索引性能。以闪存为例，传统的索引更新维护往往导致频繁的小数据量更新，这些更新操作会带来大量的闪存擦除操作，极大地降低了索引的性能和闪存寿命。
    在基于新型存储的索引方面，目前主要的研究集中在面向闪存的索引上。闪存数据库索引设计的目标是不仅要在闪存介质上实现索引的高查询性能，而且还要根据闪存的物理特性减少索引更新维护带来的性能代价(如频繁擦除等)。目前提出的闪存索引结构大都采用了传统的树型结构，并以减少对闪存的随机写为主要目的，采用的方法往往是延迟更新或者合并更新等。这方面的研究目前比较多，例如Hash-Tree ，u-Tree ，Lazy-up-date B+-Tree，LA-Tree等。u-Tree将从根到目标节点路径上的所有节点都放置在同一闪存块中，通过新分配闪存块来解决索引更新过程中产生的新路径，从而减少了随机写操作。Lazy-up-date B+-Tree。首先将更新在内存中进行缓冲，对属于相同节点的更新进行合并，然后进行组提交。Lazy-update-Tree方法存在以下两个优点：首先是缓冲的更新可以进行批量提交，这样可以减少在更新节点时因为寻址而带来的读代价；其次，更新可以进行分组，通过分组可以大大减少数据的更新次数。LA-Tree将索引树分为一组等高度的子树，每棵子树组织为B+-Tree，并且对于每棵子树采取延迟更新操作。Hash-Tree采用树形一散列的混合设计思路，它首先使用一个散列函数将数据划分到若干个桶中，然后对于每个桶中的数据提出了一种新的树形索引结构一FTree进行组织。由于Hash-Tree将数据组织成了许多棵小的树，因此发生更新时不需要更新整个索引，因此可以提高更新性能。
    虽然目前在基于闪存的索引设计方面已经做了不少的工作，但仍鲜有工作针对PB级别的超大规模数据开展研究。索引的性能通常与数据量的大小成反比，因此已有的索引技术能否在大规模数据下依然保持较好的性能还有待进一步研究。此外，由于大数据应用中，数据的价值、访问频度有高有低，在索引设计方面也需要进行有针对性的分层设计。
    4.3 基于新型存储的大数据查询处理
    查询处理与优化是数据库系统的一项主要功能。I/O问题是基于磁盘的传统数据库查询处理和优化的基础和核心问题。由于新型存储和磁盘物理特性的不同，两者具有不同的I/O机，所以基于磁盘I/O机制设计的查询处理和优化机制不能直接应用于基于新型存储的大数据管理上，需要设计全新的查询处理和优化机制。
    在数据库查询处理中，连接操作的方法对于查询执行的效率影响很大，特别是连接操作会产生大量的中间结果，需要写到外部存储，这对于闪存这样的新型存储介质来说代价非常昂贵，并且传统的连接算法主要是针对磁盘特性设计的，没有考虑新存储介质的读写特性。目前提出的面向新型存储的连接算法主要集中在闪存方面，其出发点是避免在闪存上执行大量随机写操作，同时尽量发挥闪存的随机读性能。相关的算法主要有DigestJoin算法，Sub一Join算法等。
    DigestJoin算法提出了两阶段连接的方法。在第一阶段仅将记录的关键字和连接列读人内存进行排序或者哈希，从而很大程度上减小连接表的大小，以此来减少连接操作的代价；在第二阶段，从闪存中按照连接的结果从表中读取投影的列输出，这个过程就是重新载人的过程。重新载人过程的代价对整个算法性能来说很关键，通过使用naive的载人方法、基于页的载人方法以及传统的载人方法证明重新载人过程的代价计算是个NP问题。DigestJoin算法提出了一种基于图的载人策略，用连接图来选择载人的页。通过实验发现该方法可以有效地减小连接的代价。
    子连接算法Sub-Join也是一种针对闪存关系数据库上的连接操作，通过减少对数据的读取和连接中的随机写操作来提高查询执行效率。首先将进行连接查询的相关数据表在主键和连接列上进行投影，形成子表；然后在子表上进行连接操作。最终的查询结果是根据子表连接查询的结果再从原始表中回取获得。Sub-Join仅从子表中读取数据进行匹配，从而大量减少了需要读取的数据量。同时，Sub-Join在生成子表时采取连续读，而且在写子表连接结果时采取顺序写的方式，有效地减少了连接过程中的随机写操作。
    此外，在大数据环境下，查询往往被分解成多个任务并发执行，根据资源的占用情况和节点的运行情况对任务进行有效的调度，对查询优化有着至关重要的作用。目前针对调度的优化已经有不少工作，根据调度对象的粒度，可以把已有工作分成三个类型：查询调度、MapReduce作业调度和MapReduce任务调度。
    查询调度的基本思想是，根据不同查询任务的优先级、服务等级协议(SLO)等调整资源分配，保障用户体验。文献设计了一种SLO感知的存储系统，讨论了SSD作为磁盘读缓存存储环境下的查询动态调度方案，通过将闪存缓存层进行分区，然后根据要求的服务等级对应用进行缓存大小分配，并且根据当前缓存命中率、利用率、系统延迟等要素对缓存大小进行调整，以提高查询调度性能。
    MapReduce任务调度的基本思想在于进行MapReduce任务运行时间预测，继而将更多的任务分配给性能高的节点，以提升查询性能。文献将任务负载特征和硬件异构性作为任务调度的指标，其中硬件异构性包含了CPU性能、网络带宽、内存、存储系统性能等特征。随着SSD在大数据存储系统中的普遍应用，存储系统异构性将日益凸显，同时副本也可能存储在不同的存储介质上，这些都给MapReduce任务调度带来了新的挑战。
    基于新型存储的大数据查询处理很难孤立地进行研究，因此查询处理机制、查询优化算法等与大数据存储架构、索引设计、存储管理机制等都是密切相关的。相对而言，基于新型存储的大数据查询处理研究的迫切程度要低于大数据存储管理与索引设计。
5.未来发展展望
    5.1 面向新型存储的大数据层次化存储体系
    随着闪存、PCM ， SCM等新型存储介质的出现，未来数据存储体系中将以多介质混合存储为主流，这与目前RAM、磁盘、磁带共存的现象类似。在大数据应用中，将数据集中存储是不可行的，因为巨大的数据量将导致性能低下。因此，必须建立一种新的层次化的多介质存储体系，根据数据的不同特性(例如访问的冷热属性、操作的特性等)以及不同存储介质的特性合理地分配数据存储位置，从而实现海量存储、高性能以及低能耗的设计目标。这一问题涉及多个方面的内容，未来可能的研究内容包括多介质混合存储系统与一体化管理、存储器结构感知的数据管理技术以及大数据分布式协同存储技术等。
    (1)多介质棍合存储系统与一体化管理：市场上的闪存、磁盘等规格形式众多。以闪存为例，不同厂商生产的SSD产品性能差异比较大，SSD的接口协议主要有PCIe， SAS， SATA三种，磁盘分为FC HDD， SAS HDD， SATA HDD。此外，SCM技术的候选材料形式众多，除了闪存外，还包括了忆阻器(Memristor)、磁性存储器(MRAM) ，电阻式存储器(ReRAM， RRAM )、相变存储器(PCM，PRAM，PCRAM)等，在存储密度、寿命、读写速率方面都有较大的差异。因此，基于不同类型和性能的存储介质来构建多介质混合存储系统带来了更加复杂的问题，需要我们从理论模型和实验验证两方面研究不同的混合存储策略，并建立不同混合存储策略下的存储分配模型和代价模型。以RAM、闪存和磁盘混合存储为例，可能的混合存储策略包括：
    ①传统模式，即磁盘作为二级存储，RAM作为磁盘的缓存；
    ②闪存作为二级存储，RAM作为闪存的缓存；
    ③闪存和磁盘都作为二级存储，RAM作为两者共同的缓存；
    ④磁盘作为二级存储，闪存作为RAM的扩充并且与RAM共同作为磁盘的单一缓存；
    ⑤磁盘作为二级存储，闪存作为介于RAM和磁盘之间的另一层独立缓存。
    (2)存储器结构感知的数据管理技术：针对RAM，PCM、闪存、RRAM、磁盘等多类型存储介质共存的现状，研究适应新型存储器结构的数据库系统软件基础理论和关键技术。目前，Janus系统在闪存用量分配推荐上已经取得了非常好的性能，但对于更加复杂的异构存储环境，如何实现存储介质用量的自适应动态分配将是一个极具挑战性的问题。另一方面，充分利用新型存储低能耗的特点，将能耗作为存储用量分配的指标，可以有效减少大数据管理系统的整体能耗。因此，基于能耗的异构存储系统中存储介质用量分配也将是未来的一个研究方向。
    (3)大数据分布式协同存储技术：大数据在整个系统中的存储位置通常包括感知器件端、中间层、应用层等不同的位置。我们一般把感知器件端称为“海”端，而把应用端称为“云”端。大数据如何在海、云以及平台层实现分布式协同存储是大数据存储研究中的一个重要问题。在现有研究中，无论是通过数据的I/O特性、冷热程度进行存储分配，还是将所有新建文件放置在闪存或PCM上，都无法满足大多数大数据应用的需求。大数据应用数据负载具有多样性、复杂性，如相册、商品图片类存储应用，读远多于写；而社区游戏类应用的特点在于好友间互动性强，用户数据会被频交叉访问，也不存在明显热点数据。传统的分布式数据存储并没有考虑不同的大数据应用数据负载特点。此外，分布式大数据协同存储环境的数据迁移也是一个值得研究的问题。现有的基于页、块或文件的数据热点识别和数据迁移算法往往不能发挥有效作用，原因主要在于现有的数据管理系统(如NoSQL数据库系统)采用了特殊的持久化策略，如Big-Table，Hbase，Cassandra等采用的类似于LSM-Tree写优化结构，数据以SSTable的形式存储在存储介质上。因此，未来的研究重点可以集中在基于新的粒度模型的热点数据识别和数据迁移方面。
    (4)高性能、可扩展的大数据存储优化技术：传统的数据库系统以磁盘为基础进行设计，其核心算法包括体系结构都是针对磁盘而优化设计的。随着闪存、PCM等新型存储介质的快速发展和产品化，在未来的计算机系统中，一种更为可行的方法是在系统中同时使用磁盘、闪存、SCM，RAM等存储介质，构建一个多介质的混合存储环境，从而发挥各种介质的特性，在性能和价格上取得较好的折衷。数据库系统的存储优化机理不仅要建立可以充分发挥新型存储器件优点的数据库系统体系结构，还要解决多介质混合存储时的系统优化设计问题。此外，传统的关系数据库技术在可扩展性方面存在不足，因此在大数据混合存储系统的实现上，还需要综合考虑NoSQL、列存储等技术，同时从性能角度还应考虑内存数据库等技术。
    5.2 面向新型存储的大数据管理算法
    新型存储器件的发展要求数据库技术充分结合存储器件的特性，而现在的研究大都还停留在磁盘数据库上，造成存储与CPU之间的性能鸿沟，无法彻底解决计算机系统的性能瓶颈问题。同时，由于传统关系数据库在可扩展性方面存在的不足难以满足社会网络、生物计算等领域的应用需求，而大数据的海量、动态、多样化等特征也对数据库技术提出了新的挑战，因此面向新型存储的大数据研究迫切需要设计有效的系统层核心算法。结合传统DBMS的发展历史，可以预计，面向新型存储的大数据管理算法也将集中在索引、查询处理等方面。
    (1)基于新型存储的大数据持久化算法：No-SQL数据库系统普遍采用的日志追加写、类LSM-Tree写优化虽然可以较好地适应闪存的异地更新特性，但是往往采用为SSTable建立索引的方式弥补损失的查询性能，系统运行时索引全部都需要在内存中维护，占用了大量内存；同，如果SSTable较大，通过索引查找到SSTable之后的表顺序查找，同样会带来延迟，因此需要内存使用效率更高且查找效率高的存储策略。基于闪存的Key-Value存储SILT设计了三种不同的键值存储结构，降低了内存占用率、减少了闪存I/O，对基于新型存储的大数据持久化算法有启发性作用。未来可研究的方向包括:针对不同应用场景下高效的闪存持久化策略；提高内存使用效率和查找效率的闪存存储策略。
    (2)基于新型存储的大数据可靠性保障方法：Ramcloud中的副本管理策略对异构性存储副本管理有着启发作用，结合不同存储介质之间的不同读写性能、成本、能耗等，将读写操作集中在性能较好的新型存储上，而副本则保存在具有很高可靠性、低成本的磁盘等存储介质上。但是，随之带来了数据恢复问题，即如何从性能较差的磁盘存储中快速恢复数据?这方面值得研究的工作包括基于多介质分层存储的副本管理策略、基于多介质分层存储的恢复策略等。
    (3)基于新型存储的大数据索引算法：分布式
双层索引RT-CAN， EMINC中分别使用R-Tree，Tree提高其多维查询效率，R-Tree，Tree等高维索引的频繁更新在闪存上会造成写放大和擦除，代价较大。而目前闪存数据库中的索引研究主要集中在为数不多的树结构，缺乏类似于R-Tree和KB-Tree的高效多维查询索引。未来的一些发展方向包括:分布式多维索引设计、复杂数据索引(如物联网数据、社会网络数据等)、针对大数据复杂查询的索引等。
    (4)基于新型存储的大数据查询执行算法：目前，大数据查询处理通常采用MapReduce策略。闪存数据库领域的一些连接算法对于基于Ma-pReduce的连接算法有很大的启发作用。MapRe-duce连接操作主要考虑中间结果产生量、网络传输量，中间结果需要写到外部存储，这对于闪存、PCM等来说代价非常昂贵。如果能够尽量发挥闪存的快速读性能，消除MapReduce连接产生的大量中间结果，则有望得到高效的大数据连接算法。但是，同样也面临着一些问题。首先，大数据查询执行中对内存容量要求较高，但目前内存单机容量已经较难提升，易形成性能瓶颈；此外，仍然缺乏面向闪存的高效等值连接算法，如星型连接、链式连接等。因此，基于新型存储的高效多表等值连接算法、基于新型存储的高效MapReduce连接算法等可能是未来在大数据连接算法方面的发展方向。
    (5)基于新型存储的大数据查询优化算法：大数据环境中，随着基于SSD的分层存储系统的应用越来越广泛，存储系统的异构性越来越成为查询优化中的关键要素，这要求大数据管理系统能够根据集群中不同节点的不同存储性能，将更多的Ma-pReduce任务放置在存储性能更强的节点上，从而提升查询性能。因此，基于新型存储的大数据查询优化算法可以集中研究考虑不同节点存储设备的不同耐用性、I/O特性、访存速度等因素的MapRe-duce任务调度算法。
    5.3 能耗感知的大数据管理技术
    能耗代价是大数据管理中的一个核心问题。传统的数据管理技术通常以高性能为主要目标，忽略了能耗代价。随着数据规模的快速增长，存储和管理数据的能耗代价在数据中心的比例越来越高，因此研究能耗感知的大数据管理技术是未来大数据库系统中必须考虑的一个重要方面。
    传统的磁盘存储介质能耗较大，而闪存、PCM等新型存储介质则具有相对更低的能耗代价，因此也为我们设计能耗感知的大数据存储系统提供了新的支持。能耗感知的大数据管理技术涉及两个层面的研究：一是DBMS的能耗有效性算法和技术，主要研究DBMS能耗测试技术、能耗有效的查询处理机制；二是以多个数据库节点集群为背景的能耗均衡性实现方法，主要研究如何使数据库节点集群以及存储设备能够根据负载动态地切换电源状态，以实现能耗与负载之间的匹配。这两个方面的问题都涉及到数据库系统架构以及存储架构的重新设计，同时需要解决其中出现的一些新问题，具有很大的挑战性。未来主要的研究方向包括：
    (1)能耗有效的查询优化技术：不同的查询计划已被证明具有不同的能耗，但目前已有研究没有在查询处理器中提供灵活的能耗和性能折衷的方案。因此，在查询处理器中引人能耗代价，开展能耗有效的查询优化技术研究将是未来的一个主要研究方向。
    (2)能耗均衡的数据库节点集群体系结构:数据库节点集群中一般包括计算节点、存储节点以及控制节点。计算节点用于任务处理(例如Join操作)，存储节点提供数据存储和管理，控制节点提供协调、控制等功能。计算架构研究主要探讨节点的分组、任务划分、节点间的协同方式、状态控制等问题。能耗均衡的主要思想是根据负载来动态切换节点的电源状态，因此，需要研究有效的算法来决定何时切换节点电源状态。此外，对于存储设备的能耗均衡性控制，也需要研究根据数据访问的频率、本地性等特征来动态切换存储设备电源状态的算法。
    (3)能耗均衡的集群存储分配方法：在数据库节点集群中，存储设备的能耗均衡性依赖于优化的冷热数据划分算法以及存储分配算法，同时还要考虑集群中存储节点之间的数据复制策略，以保证在不同的访问模式下存储系统能够使用尽可能少的设备就可以响应数据访问请求。存储分配和复制策略还要避免频繁地切换设备的电源状态。
    (4)面向集群的高能效缓冲区置换算法：在闪存数据库方面的已有研究表明，不同的缓冲区管理策略对性能和能耗有着很大的影响。但是，以往工作主要是针对单节点数据库服务器的缓冲区管理开展的，其主要目标是提高缓冲区命中率和减少对存储设备的。而面向集群的高能效缓冲区管理方法的目的是更好地实现存储设备的能耗均衡性，即通过设计高能效的缓冲区管理机制，使得底层的存储设备能够在保证响应性能的前提下减少带电工作的存储设备比例，从而实现降低能耗的目标。这一问题是研究能耗均衡的数据库节点集群中出现的新问题。
    6.结束语
    随着新型存储的快速发展和大数据时代的来临，面向新型存储的大数据管理将成为未来新的研究热点。利用新型存储的独特优势来解决大数据管理中的关键问题是这一研究方向中的核心和要点。本文简要论述了目前大数据管理面临的问题，重点讨论了新型存储的特点；在此基础上对结合新型存储的大数据管理现状进行了梳理，总结了目前在大数据存储架构和管理算法方面的进展；最后给出了面向新型存储的大数据管理未来发展方向，以期对此领域未来的研究提供有价值的参考。