大数据环境下数据存储与管理的研究

1、大数据环境下存储技术发展对数据管理研究的影响提 纲引言新型存储及存储层级的演化面向不同存储层级的数据管理架构架构变化对技术发展的影响总结纸带穿孔卡磁存储介质电容存储新型非易失性存储介质NVM/SCM数据处理是推动计算机技术发展的核心技术之一作为数据处理的底层支撑，存储介质的更新和相关存储技术的发展是推动数据管理技术变革和发展的主要驱动力存储介质的发展推动数据管理技术提 纲引言新型存储及存储层级的演化总结面向不同存储层级的数据管理架构架构变化对技术发展的影响传统存储设备的演化（go away or on the stage）纸带-1857穿孔卡-1884HDD-1956/1973ROM-1970

2、s软盘-1971Flash-1984光盘-1978RAM-1970s传统存储器件的演化新型存储器件的发展计算机系统性能依赖于处理器的数据计算能力存储层次向处理器传输数据的能力随着多众核、多线程技术的发展，传统存储器件构成的存储层次面临的存储墙问题愈发严重处理单元（核）数的增长与存储数据供应能力（容量）不匹配SRAMDRAM的静态功耗过高纠错电路限制了存储容量的增加并引发更多的功耗新型存储器件包括：闪存、相变存储器、磁阻式存储、电阻式存储器、忆阻器等等。具备一个共同特点：非易失性优点：高存储密度、低静态功耗、对粒子及射线撞击产生的软错误具有抵抗能力等缺点：读写性能不对称、读写次数有限、可靠性不高

3、等Graph from “基于新型非易失存储的存储结构”, CCF学会通讯 2014闪存的工业化程度最高SSD（solid state drive）闪存芯片+控制器+FTL（WL, LBA-PBA, GC）（NAND）闪存的特点读写不对称：写操作需通过加压方式对cell进行电子填充写前擦除：异位更新、块擦除操作寿命有限：块擦除次数有限SLC （约10万次擦写）MLC（小于1万次）TLC（小于1000次）新型存储器件-闪存Spin-torque MRAMPhase change memoryMemristor PCM (Phase-change memory)：相变，工业化，最具潜力FeRAM

4、(Ferroelectric RAM)：铁电式，工业化，可扩展性差MRAM (Magnetic RAM)：磁阻式，工业化，可扩展性差STT-RAM (Spin-torque transfer Random Access Memory)RRAM (Resistive RAM)：电阻式，实验室原型Memristor/Solid Electrolyte：忆阻器，智能，具有学习能力新型存储器件-其他FeRAMComparison of TechnologiesDRAMPCMNAND FlashPage sizePage read latency Page write latencyWrite band

5、widthErase latency64B20-50ns20-50nsGB/s per dieN/A64B 50ns 1 s50-100 MB/s per dieN/A4KB 25 s 500 s5-40 MB/s per die 2 msEndurance106 108104 105Read energyWrite energyIdle power0.8 J/GB1.2 J/GB100 mW/GB1 J/GB6 J/GB1 mW/GB1.5 J/GB 2817.5 J/GB 28110 mW/GBDensity12 44Compared to NAND Flash, PCM is byte-

6、addressable, has orders of magnitude lower latency and higher endurance.Sources: Doller09 Lee et al. 09 Qureshi et al.09部分性能指标对比-IComparison of TechnologiesDRAMPCMNAND FlashPage sizePage read latency Page write latencyWrite bandwidthErase latency64B20-50ns20-50nsGB/s per dieN/A64B 50ns 1 s50-100 MB/

7、s per dieN/A4KB 25 s 500 s5-40 MB/s per die 2 msEndurance106 108104 105Read energyWrite energyIdle power0.8 J/GB1.2 J/GB100 mW/GB1 J/GB6 J/GB1 mW/GB1.5 J/GB 2817.5 J/GB 28110 mW/GBDensity12 44Compared to DRAM, PCM has better density and scalability; PCM has similar read latency but longer write late

8、ncySources: Doller09 Lee et al. 09 Qureshi et al.09部分性能指标对比-II新型存储器件-读写延迟 &性价比需要思考和解决的问题如何利用新型存储的特性来优化或者重新架构当前的存储层次？能否结合存储器件的特性以及存储层次，设计上层应用（特别是数据管理系统）实现扬长避短提 纲引言新型存储及存储层级总结面向不同存储层级的数据管理架构架构变化对技术发展的影响数据库系统总会涉及不同层次的存储器，特别是为支持事务的ACID属性，数据持久化是必须的，因此对于非易失的存储存在需求。IO始终是制约数据库性能的主要瓶颈，对于支持可高速随机读写的存储存在需求。数据库就

9、是为了解决“大数据”问题，因此不断增长的数据规模对大容量的存储存在需求。用廉价磁盘阵列（集群）取代更大的磁盘，导致数据库系统对高可靠的存储存在需求。不同的读写访问模式，数据价值不同，使数据库对多级（混合）存储存在需求。数据管理系统对存储的内在要求数据库都是架构在目标存储层级（ storage hierarchy ）上的数据库架构与存储层级计算机对存储系统的基本要求：低延迟、高容量、价格成本低数据库都是架构在目标存储层级（ storage hierarchy ）上的依据主存储介质的不同，将数据库架构分为Disk-oriented Memory-orientedNVM-oriented数据库架构与

10、存储层级传统的关系数据库都是架构two-tier存储层级上的低速、非易失、高容量的HDD作为主存储介质高速、易失、低容量的DRAM作为Cache由于disk存储特性而引入的IO延时是影响数据库性能的主要瓶颈之一disk-oriented数据管理系统普遍采用如：Buffer pool或者复杂的并发控制，来缓解disk导致的IO延迟disk-oriented架构主存储介质cacheSIGMOD 08 ：OLTP through the looking glass, and what we found there测试结果显示，传统disk-oriented数据库只有约12%的CPU时间用于实际处理事

11、务，其它时间都“浪费”在缓存池管理、并发控制和基于日志的事务恢复等辅助性模块上disk-oriented架构-缺陷Ref “OLTP through the looking glass, and what we found there” SIGMOD 2008从传统关系数据库诞生以来，由存储层级导致的架构性性能缺陷一直都存在。在小数据量的应用环境下尚能应对。但是大数据环境下，缺陷被放大，越来越难以应对大数据应用的需求内存计算中内存的地位与概念正在发生改变地位：二级存储的cache 数据存储的主要载体内存计算中的“内存”Memory FirstArchitecture数据访问：API call

12、Pointeroriented延迟：纳秒级Disk FirstArchitecture数据访问：API callOS I/OI/O ControllerHDD延迟：微秒级随着内存成本的不断下降，通过内存来存储整个数据库成为现实。为消减数据驻留磁盘导致的高昂代价，引发了一类以内存作为主存储介质的研究并非新的研究话题90年代初就有研究：“Implementation techniques for main memory database systems”，1984，SIGOD Rec.早期也有很多知名的in-memory DB系统，如TimesTen、SolidDB、DataBlitz传统的内存数

13、据库沿袭了System R中的很多影响性能的特征，如disk-based日志、动态锁等（对性能产生一定的影响）memory-oriented架构memory-oriented架构-Anti-Caching内存数据库的难题：DB size Memory Size解决策略1：增加硬件内存容量；代价高昂解决策略2：回退到传统Disk-Oriented DB放弃对性能的要求解决策略3：启用虚拟内存（page virtual memory）引发大量page faults （产生大量HDD IO和事务的终止）解决策略4：分布式缓存两层式DB框架导致重复存储以及应用端的同步控制换个角度思考：从存储层次中数据

14、使用的需求（冷热程度）出发memory-oriented架构-Anti-Caching“anti”是针对传统存储层次保存数据的策略而言的。在传统DB系统中，disk是主存储介质，DRAM是作为caching存在。因此，一份数据可能会有多份拷贝而anti-caching架构中，把DRAM作为主存储介质，而Disk仅用来存放cold数据。因此同一份数据在任何时候，仅有一份副本。Anti-Caching:ANewApproachtoDatabase Management System Architecture, VLDB 2013memory-oriented架构-Anti-Caching图(a)(

15、b)所示的架构中，数据均存在冗余。特别是（b）存在两份冗余。从某种程度上是一种浪费，给维护一致性管理带来不可避免的开销特别对于图(b)而言，是一种解决磁盘访问缓慢的架构优化方法，即使用分布式缓存（如Memcached）。除了图(a)架构面临的问题，其还要求开发者在应用程序中嵌入逻辑来实现DBMS和分布式缓存的独立同步（应用耦合，增加了应用的开发难度）. Anti-Caching是一种可扩展的不局限于内存容量的内存数据库架构。其优于Disk-Oriented DB以及使用分布式缓存两层架构DB。NVM-oriented架构目前DRAM和Flash是半导体存储器技术的主流，但二者均面临计算速度以及

16、容量的挑战日立(Hitachi)、英特尔、IBM、美光(Mircon)、海力士(Hynix)等公司都在竞相研发新一代半导体存储器技术，即新型非易失存储器（NVM/SCM）技术新型介质可以实现高速存取与非易失性，在未来可以作为内存替代DRAM，也可以作为存储器替代传统硬盘、闪存。为内外存统一管理提供了可能性。思考：当新型存储（NVM/SCM）出现后，对disk-oriented架构的DB和memory-oriented架构的DB有什么影响?NVM-oriented架构新存储层级随着NVM的逐渐成熟，计算机系统面临一个重大课题：如何将NVM融入当今的存储子系统（存储层级）传统的存储系统中，不同存储

17、层次的数据交换占据整个IO的大部分开销新型存储器件的非易失特性、良好的扩展性，低能耗以及较低的访问延迟对于存储层级（体系结构）造成了巨大冲击新型存储的特性也在改变传统的CPU、系统总线、主存、辅存间的架构平衡，需要系统设计者重新思考存储架构以最大化应用性能可以分别从寄存器、缓存、主存和外存不同层次研究如何引入新型存储器件 新的存储金字塔形成单纯替换的问题相比于SRAM、DRAM甚至是HDD，各种新型存储介质都未形成绝对优势各种不同的存储介质还存在不同的特有的性质（特别是各自物理特性导致的难以改变的缺点，如闪存的擦除写）单纯的替换某一层无法实现最佳的性能混合式融入策略与构成技术每种SCM存储介质

18、在读写性能、成本、功耗等方面有各自的优势和不足混合存储是扬长避短，充分发挥不同存储介质的长处的一种可行的解决方案NVM-oriented架构新存储层级混合存储体系SRAM层面的混合技术互补优势SRAM的写延迟低、写能耗低SCM（STT-RAM）的容量大、静态功耗低混合技术思路按比例配比存储介质。常见比例：16:132:1（SST-RAM：SRAM）按数据的访问特性分配数据的存放。写密集型数据放入SRAM，读密集型数据放入STT-RAM。有基于硬件（控制器）和软件（编译器）两种分配方式DRAM层面的混合技术互补优势DRAM的写延迟低、写能耗低、耐写性高SCM（PCM）的存储密度高、静态功耗低、非

19、易失混合技术思路PCM和DRAM线性混合：无主次，线性编址。PCM为主存+DRAM为缓存：借助DRAM缓存写操作减少PCM的写次数效果：1G-DRAM+32G-PCM访问延迟、容量相当32GDRAM 70%功耗使用寿命增长300%混合存储体系HDD层面的混合技术互补优势HDD的廉价、高容量SCM（NAND FLASH）的随机读写能力、并发读写能力混合技术思路HDD作为SDD的写缓存：合并随机写为批量顺序写到SSD（不适合写密集应用）PCM+NAND Flash：读密集置入Flash，写密集置入PCM混合存储体系NVM-oriented架构-NVM模拟器A Prolegomenon on OLT

20、P Database Systems for Non-Volatile Memory, ADMSVLDB 2014数据库采用新存储层级的用例NVM-onlyNVM+DRAMNVM模拟器：如何系统级的评估面向NVM的软件是一个难题因为目前尚缺乏正式发布的硬件产品。需要使用合适的NVM硬件模拟器模拟器利用DRAM模拟NVM，并提供两种主要访问接口NUMA interface （内存方式）PMFS interface（文件方式）System Software for Persistent Memory， EuroSys 2014轻量级的兼容POSIX的文件读写的访问方式，可具名，且支持面向字节的访问

21、方式类似内存申请的方式，无需测试系统做任何更改即可测试运行NVM-oriented架构-NVM-onlyA Prolegomenon on OLTP Database Systems for Non-Volatile Memory, ADMSVLDB 2014问题： memory-oriented和disk-oriented数据库架构能否直接应用新的存储层级获得收益？m-o system（H-store） 利用NUMA接口访问的NVM模拟内存作为主存储介质；而利用PMFS接口访问的NVM则模拟磁盘保存日志问题：disk-oriented逻辑日志没有考虑NVM的非易失特性。已经在NVM上完成持久

22、化的事务需要被重新执行。d-o system（mysql+innoDB）利用NUMA接口访问的NVM模拟内存用于缓冲池；而利用PMFS接口访问的NVM则模拟磁盘作为主存储介质问题：用于防止partial page write 错误的doublewrite机制，在NVM执行环境下是不必要的NVM-oriented架构-NVM+DRAMA Prolegomenon on OLTP Database Systems for Non-Volatile Memory, ADMSVLDB 2014问题： memory-oriented和disk-oriented数据库架构能否直接应用新的存储层级获得收益？

23、这种架构与传统的two-tier相似，只是利用NVM替换了HDD。 其最主要的瓶颈依然是为了支持恢复机制，将DRAM中的数据写入持久化存储介质的开销，及时是使用（相比于HDD）非常快速的NVM“we conclude that neither system is ideally suited for NVM. Instead, a new system is needed with principles of both disk-oriented and memory-oriented systems and a lightweight recovery scheme designed to

24、utilize the non-volatile property of NVM”“we envision that this new DBMS, dubbed N-Store” - A Prolegomenon on OLTP Database Systems for Non-Volatile Memory 提 纲引言新型存储及存储层级架构变化对技术发展的影响总结面向不同存储层级的数据管理架构 对恢复技术的影响存储介质的特性对于WAL的设计影响深刻Append only：基于顺序写速度高于随机写特性In-place update：基于原位更新能力Batch write：基于块（block）处

25、理粒度NVM新型存储在特性上和传统设备具有很大不同Byte-addressable、非易失、读写性能差异小需要充分考虑新特征，并扬长避短设计面向NVM的新日志策略 对恢复技术的影响-ICDE 2011问题：传统的日志设计中，为了协调基于块的磁盘I/O，采用两层日志设计策略，首先缓存到DRAM上，再溢写到持久存储设备上，所以需要缓冲管理和磁盘I/O。因此，当一个事务触发日志记录持久化，它须等待这个日志记录之前的日志记录填满。这种设计成为日志并发读写的主要瓶颈。方案：新的基于SCM的日志方法。数据库事务从SCM日志空间直接分配块用于写日志记录，不用缓存到DRAM再溢写到持久存储设备上，避免了复杂的

26、缓冲管理和低速磁盘I/O，同时简化了日志框架，支持更好的并发度和延迟。同时开发了有效的基于SCM的日志管理和系统恢复算法。Ref：High Performance Database Logging using Storage Class Memory, ICDE,2011 对恢复技术的影响-VLDB 2014问题：大规模并行硬件（multicore、multi-socket）越来越多的背景下，集中式日志导致的竞争开销已经成为DB的主要性能瓶颈。NVM的非易失性不但使传统日志的flush-before-commit的设计需求不再必要，同时也使得分布式日志成为消除传统基于HDD的日志读写瓶颈的具有

27、前景的策略方案：利用NVM的字节存取、非易失性建立基于多核的分布式可扩展的日志系统。每一个日志分配一个基于NVM的缓冲，一旦写日志立即持久化。同时利用基于逻辑时钟的全局顺序号，追踪同一事务在分布式日志中分散的记录之间的依赖关系，最后利用被动式群组提交确保在发生系统故障时事务处理的正确性。Ref：Scalable Logging through Emerging NonVolatile Memory, VLDB 2014 对恢复技术的影响-SOSP 2013问题：为了适应HDD的读写特征，传统的WAL被设计为append-only和write-only。同时为了最小化同步写代价，需要采取很多面向

28、磁盘的如批量写等优化技术，也增加了设计的复杂度。但是NVM的新读写特征使得一些优化技术不再必要，同时也为设计基于NVM的面向WAL的回复算法提供了新的机遇方案：结合硬件技术，利用可编辑的原子写操作（editable atomic writes, EAW），以一种可扩展的方式支持事务隔离，并设计了一种面向NVM优化的基于WAL的恢复策略：MARS（ Modified ARIES Redesigned for SSDs ）。不但具有和ARIES一样的特性，同时消除了面向HDD的一些设计权衡。 From ARIES to MARS transaction support for next-gener

29、ation, solid-state drives, SOSP 2013 对恢复技术的影响-比较 AlgorithmSCM-based LongingNVM-based by distributed loggingMARSsimilarities1.都是应对新型存储设备下的日志系统优化方案2.缓冲设备都是PCM/SCM/NVM+主内存3.降低了多次读写磁盘I/O的次数4.都提出了针对不同底层设计的系统崩溃恢复方案Differences实现方案底层通过SCM日志空间数据结构和SCM日志空间管理器进行块、锁管理和归档数据到其它持久设备通过GSN在分布式日志中定位唯一日志序列号、事务分发到本地节点日

30、志避免远程内存访问，管理检查点减少不必要的数据扫描。通过硬件和软件同时支持，提供的对原子化写操作的支持，以及相关的原语，简化了ARIES类日志的设计复杂度以及不必要的面向磁盘的开销整体框架软件、集中式软件、分布式软硬结合、集中式恢复机制恢复系统仅仅需要知道SCM日志空间的地址就可获取最新检查点位置，从而加载数据执行恢复直接使用页面级的分区做parallel redo,事务级的分区做parallel undo利用内核驱动(kernel driver)实现恢复。在恢复时，驱动会扫描所有logger的事务表构建一个完整的事务状态场景。利用WriteBack和Abort命令完成恢复操作几种设计方案的对

31、比： 对事务技术的影响传统的数据库系统架构主要基于上世纪70年代的计算机硬件特点而设计，主要包括以下几个模块：Buffer Pool Manager（解决内存不足问题）Concurrency Control Mechanism（解决磁盘延迟高问题）Recovery Mechanism（利用持久化介质解决故障问题）这些模块大多与事务处理密切相关。而且这些机制所面对的执行环境都是disk-oriented的。因此，在NVM时代（包括内存计算），上述技术都面临新的机遇与挑战 对事务技术的影响-分布式事务基于内存的H-store用存储过程模拟事务。把所有事务都转为存储过程的一系列操作。可减少应用与数据

32、库之间多次信息交互产生的延迟。并且为事务事前优化提供了可能性只提供基于分区的单线程，消除了与典型多线程环境中的锁定和闩锁有关的开销，保证事务请求按顺序执行采取在一个分区中单线程顺序执行事务的策略，对于单分区事务具有高可扩展性非和高吞吐量；对于跨分区的分布式事务亦可支持，但事务并发性较低，因此吞吐量较低。适用于上层应用容易分区的业务场景。ClientApplicationDatabase ClusterTransactionResultProcedure NameInput Parameters问题：在传统RDBMS中，MVCC机制下记录的更新操作会产生较高的索引维护代价。维护索引开销的主要来源

33、：低效的磁盘I/O以及索引与多版本记录物理存储位置的高度耦合关系。因此索引数量和检索性能、维护开销存在tradeoff方案：通过利用低延迟的SCM引入一个间接层，改变了在混合存储层次中的数据结构。利用该间接层解耦了多版本记录在物理表示与逻辑表示之间的关系。当记录更新时，除了建立在更新属性上的索引需要涉及磁盘IO外，其他属性上的索引都只会涉及低延迟的SCM I/ORef：Making updates disk-I/O friendly using SSDs, VLDB 2013 对事务技术的影响-并发控制对核心算法的影响传统关系数据库中的部分核心算法在新型存储环境下无法达到最优，如B+树、Has

34、h连接等，因为很多算法及相关优化技术主要针对HDD的读写特性而设计。在PCM为主存的存储架构下，PCM-friendly的主存算法的技术指标不仅有：低计算复杂度、好的cpu cahce性能、节能，还有最小化PCM写需求对核心算法的影响-CIDR 2011问题：基于DRAM的传统B+树的插入删除操作代价不高，仅在节点分裂和合并时，代价较高。但是在PCM为主存的环境下，B+树的任何插入删除的相对代价都较高，因为在有序节点中执行插入删除操作都会产生大量PCM写操作方案： unsorted化-叶子节点无序化，非叶子节点有序化Ref： Rethinking Database Algorithms for Phase Change Memory, CIDR图：PCM为主存的三种典型存储架构组织形式Unsorted nodeU