网络信息安全理论.ppt
Log-Structured Memory for DRAM-Based Storage,Slide 1,Slide 2,全闪存储存速度存储系统的极限RAMCloud-内存云存储的内存分配机制,Slide 2,Slide 3,文章逻辑思路：,RAMCloud 概述Log MetadataLog-Structured Storage：日志结构的储存Two-level Cleaning-两种不同清除策略Parallel Cleaning：并行清除额外工作：Avoiding Cleaner DeadlockRAMCloud内存云存储的内存分配机制-意义RAMCloud的未来,Slide 3,Slide 4,RAMCloud 概述：,RAMCloud是一个完全使用DRAM的存储系统，它的所有数据都保存到内存中。当然为了恢复故障，RAMCloud会将日志和数据持久化备份到普通硬盘中。RAMCloud 适用场景：应用服务器（主要实现生成网页和执行业务规则等应用逻辑）存储服务器（为应用服务器提供长期共享存储）两种数据中心一般支持许多应用；有的很小，只使用一台服务器的一部分能力；有的很大，要用到数千台专用应用和存储服务器。,Slide 4,Slide 5,RAMCloud 概述：,RAMCloud内存云中保存的信息必须和硬盘一样持久，单个存储服务器的故障不能造成数据丢失和哪怕几秒钟的服务不可用。RAMCloud将所有数据存放在DRAM中，性能可以达到比目前最高性能的硬盘存储系统还要高1001000倍。在访问延迟方面，RAMCloud方案中运行在应用服务器中的一个进程从同一数据中心的存储服务器中通过网络读取数百字节数据只需510s，而目前实际系统一般要花费0.510ms（具体取决于数据是在服务器内存缓存中，还是硬盘中)一台多核存储服务器每秒可以服务至少100万次小读取请求。而硬盘系统中同样的机器每秒只能服务100010000次请求。,Slide 5,Slide 6,Slide 6,RAMCloud 概述:,DatacenterNetwork,Coordinator,1000 10,000 存储服务器,1000 100,000 应用服务器,Key-value store32-256 GB DRAM,5s RTT forsmall RPCs,系统易崩溃就采用多个备份,任何时段所有数据皆放于DRAM里,storage server,Slide 7,Log Metadata,在基于日志的文件系统中，为了快速的访问日志数据，日志中使用了各种索引。RAMCloud是使用了hash table来访问在memory中的数据。硬盘中的日志在正常工作的环境下是永远用不到的。它唯一被用到的机会就是故障恢复。,Slide 7,Slide 8,Log Metadata,日志分三种：1).元数据包含了存储基本单元object的table id，key，version，value。在数据恢复时，将根据最新version的条目来重建hash table。2).日志摘要(log digest)每一个新的日志段都会有一个日志摘要，这个摘要包含了所有属于这个段的日志。在数据恢复时，将根据段的最新的日志摘要来加载所有的元数据。3).tombstone这个日志是比较特殊的。它代表了被删除的object。日志一旦写入就不可修改，但若一个object被删除就在日志中添加一条tombstone的记录。记录包含table id，key和version。在平时的操作中，tombstone是不会用到。但是在数据恢复时，它能保证被删除的object不会被重建。,Slide 8,Slide 9,Slide 9,Log-Structured Storage：日志结构的储存,哈希表,table id,object key,不变的日志,8 MBSegments,Log head:在这增加下个目标,每一段复制到磁盘上的3个备份服务器上,主服务器,Slide 10,Two-level Cleaning：,对于基于日志的内存分配，主要的瓶颈就在于log cleaner。碎片管理，或者说内存回收是非常昂贵的，这就需要巧妙的设计。特别是随着内存利用率的上升，回收的成本也越来越大。例如，对于一个内存利用率80%的情况，为了获取2B的可用空间，平均情况下需要移动8B的数据。如果是90%，那么移动9B的数据只能带来1B的空间。见下图的上半部分。,U:fraction of live bytesin cleaned segments,0.5,0.99,0.9,Bytes copied by cleaner(U),Bytes copied/byte freed(U/(1-U),Bytes freed(1-U),Slide 10,Slide 11,Two-level Cleaning：,对于Memory来说，更关注的是空间的利用率，因为DRAM比较贵的。对于硬盘来说，带宽是昂贵的，可以说很多系统的瓶颈都是在硬盘的IO读写速度上。因此RAMCloud对于memory和disk采取了两种不同的回收策略。,Disk,Memory,Capacity,Bandwidth,cheap,expensive,expensive,cheap,Conflicting Needs:,Slide 11,Slide 12,Two-level Cleaning-两种不同清除策略,因为两个阶段的清除，使得memory的cleaning可以不影响Backup，这个结果就是一般来说memory的利用率要高于disk。memory的利用率可以达到90%，disk的要低得多。当然因为disk的cleaning的频率更低，这也就可以理解了。第一种：segment compaction 仅仅是处理了in-memory的segment，并没有消耗网络或者disk的IO。实际上占用了更少的空间。第二种：combined cleaning不仅清理disk，也清理 memory。因为已经有segment compaction了，所以该方法效率更高。且因为这一阶段被延后进行了，可以合并更多的删除操作了。,Slide 12,Slide 13,Two-level Cleaning-两种不同清除策略,“seglet”如果没有segment compaction，那么所有的segment都有相同的大小，默认情况下是8MB。因为有了压缩，因此segment可以有不同的大小。但是不能采用传统的heap allocator，因为会产生碎片。RAMCloud将segment分为64KB的seglet。每个segment分为不同的seglet，seglet的数量就决定了segment的大小。虽然认为seglet的引入=也会引入碎片。实际上，对于一个segment来说，只可能产生大约1/2个seglet大小的碎片，也就是32KB/8MB=1/64=1.5%。也是由于seglet的引入，log现在变得不连续了，因为log有可能跨越多个seglet，RAMCloud使用了额外的机制来处理这种情况。,Slide 13,Slide 14,Two-level Cleaning-两种不同清除策略,“clean的触发机制”two-level的cleaning的引入，引入了一个新的问题：什么时候触发segment compaction，什么时候触发combined cleaning？这个选择将会影响到系统的性能，因为combined cleaning占用了系统珍贵的disk IO和network IO。这个policy 模块，称为balancer。一般情况下，在memory和disk的利用率不是很高的情况下，cleaner是不会工作的。因为cleaner的提早工作并不会有多高的效率。相反，如果cleaner的工作延后，那么可以处理更多的删除的object，可以回收更多的空间资源，因此，延后的cleaner是非常有意义而且有好处的。,Slide 14,Slide 15,Two-level Cleaning-两种不同清除策略,那么选择segment compaction呢，还是选择combined cleaner呢？一般来说，会优先选compaction因为它更有效率。但是有两种情况下必须启动combined cleaner：第一种情况就是tombstone太多了。因为segment compaction是不能单独把tombstone标记的数据删除的，它必须将这些数据从backup中删除之后才可以删除在memory中的tombstone。由于tombstone的越来越多，使得memory的使用率越来越高，导致compaction越来越低效。最终，选择combined cleaner可以是系统删除那些tombstone，也会使得以后的segment compaction更有效率。第二个原因就是on-disk log太大时。为了防止disk run out-of-space，也为了避免系统恢复时重建时间太久，都会启动combined cleaner。,Slide 15,Slide 16,Slide 16,Backups,DRAM,Backups,DRAM,Backups,DRAM,Compaction:Clean single segment in memoryNo change to replicas on backups,Combined Cleaning:Clean multiple segmentsFree old segments(disk&memory),Slide 17,Parallel Cleaning：并行清除,最简单的cleaning方法就是把需要移动的数据添加到log的头部。但会和service的写请求冲突。为避免，RAMCloud是将这些需要移动的数据移动到一个新的segment。每个cleaner都会申请一组segment用于保存移动的数据，只有在申请segment的时候需要同步。申请完成后，每个cleaner就可以操作自己所属的segment了而无需额外的同步操作。移动完成后，cleaner会把这些segment放到下一个的log digest中，同时被回收的segment也会在下一个log digest中也会被删除。这些数据移动到不同的segment而不是head segment中的另外好处：这些segment可以备份到不同的disk中，可以提高Master的吞吐量。,Slide 17,Slide 18,Parallel Cleaning：并行清除,“Hash Table的争夺”Hash Table由于同时被cleaner和service threads使用，因此会有同步的问题。Hash table标明了哪些object是可用的并且保存了在memory中的地址。cleaner使用Hash table去确定某个object是否alive：通过判断指向的地址是否真的是该object，如果是alive的，它就将Hash table中更新该object中的新地址。同时，service线程通过Hash table来读 取或者删除某个object。RAMCloud现在使用在每个hash的bucket上使用一个fine-gained lock来同步。,Slide 18,Slide 19,Parallel Cleaning：并行清除,“释放内存空间的时机”当cleaner thread clean完成一个segment后，这个segment的空间可以被释放或者被重用。在这个时间点，所有service thread都不会看到这个segment的数据，因为没有hash table的条目指向这个segment。但是有可能老的service thread还在使用这个segment。所以free这个segment可能会导致非常严重的问题。RAMCloud采用了一个非常简单的机制来处理这个问题：系统直到所有当前的service thead数据请求处理完成才会释放该segment。当然的service thread处理完成之后，释放segment是安全的，因为所有后来的service thread都不可能使用到这个segment。这个设计很简单，避免了使用死锁来完成这个普通的读写操作。,Slide 19,Slide 20,由于clean的过程中需要额外的内存，因此在内存利用率高的时候，clean的过程中有可能会耗掉最后的内存，run out-of-memory。因此形成了deadlock。RAMCould为了避免这种deadlock采取了多种技术，首先，它会为cleaner申请一个seglet的pool。使得不会因为seglet的申请而导致死锁。而且，它在clean一个segment时，会计算是否这个clean会带来空间的利用率升高。还有一个措施是会申请专门的log digest以免申请额外的log digest时导致内存耗尽。综合以上技术，RAMCloud的空间利用率可以达到98%，而不会产生deadlock。,Slide 20,额外工作：Avoiding Cleaner Deadlock,Slide 21,Parallel Cleaning：并行清除,“释放disk空间的时机”当segment被clean后，在backup上的冗余备份也需要删除。然而，这个删除只能在被移动到的segment正确的写到on-disk中的日志之后。这需要两个步骤。合并后的segment需要在backup中完成冗余拷贝。因为所有的冗余拷贝都是异步进行传输的，因此只有cleaner在接收到所有的响应接到后。新的log digest必须包含新的合并的segment和删除被clean的segment。只有上述数据被持久化后，这个冗余备份就可以被安全的删除了。,Slide 21,Slide 22,传统的内存分配器不能达到以下几点要求：快速分配/释放处理不断变化的工作负载有效地使用内存RAMCloud:日志式分配器:双倍复制 数据收集两种不同的清除方式（磁盘和内存分开的策略）同时清除（无停顿）成果:甚至可以达到80-90的高性能内存利用率处理不断变化的工作负载使任何基于DRAM的存储系统有意义,Slide 22,RAMCloud内存云存储的内存分配机制-意义！,Slide 23,RAMCloud的未来,基于DRAM存储设备比基于闪存的存储设备速度更快，但成本也要高得多。比如，2TB大小基于闪存的存储设备成本大约为18万美元；相比之下，存储容量相同但基于DRAM的存储设备成本高达约100万美元。基于DRAM的驱动器读取或写入数据的时间只要0.015毫秒，工作状态下随机速度达到了每秒可以处理40万次I/O。这种驱动器最适合以写操作为主的软件以及使用高性能数据库应用系统的公司。,Slide 23,Slide 24,RAMCloud的未来,目前一个可行的RAMCloud配置，每台服务器配置24GB的DRAM，这是高性价比的配置。扩展内存会导致成本的急剧增加。2000服务器会配备48TB的存储空间，平均每GB成本65美元。据预测，到2020年，随着DRAM技术的不断完善，激励1PB-10PB配置的RAMCloud时每GB成本仅需6美元。RAMCloud已经在实际中有所应用。例如一个大型的网络零售商或航空公司使用RAMCloud的花费在几十万美元。截止2009年8月Facebook所有非图像数据大约有260TB。这可能接近了当今RAMCloud实用的上限。像电视频、照片、歌曲等数据还没有大规模应用RAMCloud，然而RAMCloud实际已经可以用在所有在线的数据。随着DRAM技术的不断改进，RAMCloud在未来会更具吸引力。,Slide 24,Slide 25,谢谢观看,Slide 25,
