数据存储管理技术的更新换代_第1页
数据存储管理技术的更新换代_第2页
数据存储管理技术的更新换代_第3页
全文预览已结束

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

1、数据存储管理技术的更新换代关键词:数据存储1 .引言在有数据存储能力的电子设备中,从微型的手机到大型的计算机和数据库系统,数据管理的一个 关键技术是由替换算法(Replacement Algorithm)来实现的。此类算法概念简单,但其优化和系统 实现有各种挑战和困难。1966年,IBM学者比雷迪(L.Belady)1发表了 LRU(Least Recent Used) 替换算法。1968年美国麻省理工学院教授考巴脱(F.J. Corbato, 1990年图灵奖获得者)2用Clock 近似操作在分时操作系统中的内存管理中实现了 LRU算法。在1966年到2009年的四十几年里,计算 机学者和系

2、统工程师从理论和实践上对替换算法的更新和改进做了不懈的努力。在过去很长的一段时 期里,LRU是存储管理的经典算法。尽管LRU算法有几个致命的缺陷,但由于它具有简单且可操作性 强的特点,这个算法及其Clock的近似实现在数据存储系统中广泛使用。这个局面在我们的LIRS替 换算法3及其近似实现算法Clock-pro4发表后,发生了改变。近年来在主要的操作系统和数据库 系统中,LIRS和Clock-pro逐步取代了 LRU和Clock,更新了这个存储管理的关键技术。随着CPU计算速度的不断加快和网络技术的更新,数据存储层也在不断加深。在CPU芯片上有 L1、L2和L3三层硬件快速缓存(Cache);

3、操作系统将程序的虚拟地址转换为内存的物理地址,这些 转换数据也缓存在芯片内的TLB里(Translation Lookaside Buffer);在DRAM内存中有行缓存区(Row Buffer)0除了放置主存数据以外,DRAM还设有I/O数据缓存区(Buffer Cache),磁盘内也有缓存 区(DiskCache)。数据中心和互联网上都有各种大大小小的缓存区。如果数据在某一层缓存区找不到,系统就要到下层去找,这样大大增加了访问的延迟。例如,通 过互联网,从美国到欧洲获取一个数据块的延迟,是从自己计算机的L1快速存储器取同样数据块延 迟的3亿倍!增加访问数据的延迟也增加了不必要的能源消耗和系

4、统的不稳定因素,所以替换算法的 质量在数据密集型计算中起着非常关键的作用。LRU算法及其优缺点LRU算法是通过一个LRU栈(Stack)将访问的数据自上而下地压进栈里,这样,在栈顶的数据 总是最新访问的(Most Recently Used或MRU),而在栈底的数据是最少访问的(LRU)。当访问命中 (Hit)时,LRU算法将此数据块移到栈顶;当访问不命中(Miss)时,如果存储区已满,LRU算法将 栈底的数据块替换出去,将在另一层存储空间获取的数据块压入栈顶。LRU栈里的每一块数据与栈顶 的距离给出了它多久没有被访问的信息(又称为Recency)。LRU算法的一个基本假设是:一个数据块一旦被

5、访问了,它还会再被访问。这个假设对局部性强 的数据是适用的,而且基于这个假设的算法的数据结构简单,实现容易。但是LRU算法的简单假设导致了它在结构上的三个缺陷。第一,一次性访问的数据和弱局部性的 数据,可以长期滞留在LRU栈中,大量的此类数据块的频繁访问还可以“污染”缓存区,将局部性强 的数据块替换出去;第二,如果LRU栈的长度是k,一个k+1的数据循环访问是没有任何命中的;第 三,几组访问频率不同的数据块在一起会相互冲突,访问频率高的数据可以被访问频率低的数据替换 掉。为了解决LRU算法的这三个问题,计算机学者和系统工程师从算法和系统实现上入手,做了大量 的工作,但是成效不是很大,在很长的时

6、期里,LRU以及Clock都在计算机系统中占有主导的位置。 我们在设计替换算法和开发相关系统软件的启始,就设立了两个明确的目标:(1)从根本上解决LRU 的三个问题;(2)保存LRU的所有优点,即合理的假设和简单的数据结构。LIRS算法简介当一个数据块被两次访问后,在这两个数据块中间的其它非重复访问的数据块的数量,被定义为 重新访问距离(Reuse-distance)。一个数据块的重新访问距离的长度可以精确地测量其局部性的强 度,即距离越短,局部性越强,反之则局部性就弱。LIRS算法是用重新访问距离来做替换决定的, 这样可以从根本上解决LRU的三个问题。但是最大的挑战是如何在有限的空间里快速地

7、测量重新访问 距离。我们利用一个大栈和一个小栈来构造LIRS的数据结构,在大栈中,记录有三种数据块:(1) 经常被访问的块(重新访问距离短的);(2)刚刚被访问的块(重新访问距离很长的);(3)刚刚被替 换出去的。在小栈中只记录刚刚被访问的块。每次访问都对数据块的重新访问距离做测量,使得数据 块可以动态地在两个栈中交换位置。从而LIRS算法有效地解决了 LRU的三个问题。重新访问距离长 的或一次性访问的数据块会很快被替换出去,而局部性强的数据块会保持在大栈中。在循环中,大栈 中保存的数据不会被替换掉。在LIRS的算法中,访问频率低的数据被及时替换掉。LIRS算法尽管比 LRU算法动态变化得多,

8、但是它的复杂度与LRU 一致都是O(1)。详情可参阅文献3。Clock-pro 和 BP-wrapper好的算法不等于在实际系统上一定有好的效果。为此,我们为LIRS做了一个可以在系统中有效 实现2的近似算法Clock-pro。该算法大大改进了 Clock算法的单指针简单结构,用三根指针将LIRS 所有关键功能给出有效的近似实现(详见文献4)。LIRS算法在系统实现中遇到的另一个挑战是锁竞争(Lock Contention)。替换算法的数据结构 是互斥的(Mutual Exclusive),即在数据结构被改动时,它需要一个锁保护。这个锁保护使并发数 据访问增加了延迟,这样,整个系统的可伸展性(

9、Scalability)受到了限制。针对这个问题,我们 开发了一个系统工具BP-Wrapper,利用批处理(Batch)和预取锁(Profetch),使任何一个替换算 法,包括LIRS都可以在系统运行中使竞争带来的延迟降到最小(详见文献5)。多核处理器中的共享存储器管理LIRS算法中的一个重要原则就是利用大栈保护局部性强的数据,利用小栈去控制和替换局部性 弱的数据。在多核处理器中有一个共享的L3存储器。多线程在访问L3的时候会发生硬件无法控制的 冲突。我们在操作系统中,利用页面管理和L3块之间的关系,开发了一个系统软件控制的L3划分系 统。这样,操作系统就可以通过划分L3来保护局部性强的线程,

10、控制和限制局部性弱的线程(详见 文献6)。这个在Linux开发的系统上已被英特尔公司正式采用,并广泛在工业应用中推广,几家大 的工业生产线(比如,西门子公司的自控装置)用了此系统后,多核处理器的性能得到大大提高。LIRS在计算机系统中发挥的作用和影响LIRS和它的近似算法Clock-pro以及消除锁竞争的系统工具BP-Wrapper逐渐在主要操作系统和 数据库系统中取代LRU和Clock。以下是几个典型的实例:LIRS已被世界最大的数据库系统MySQL所采用。MySQL在世界范围有一千多万用户;LIRS以及BP-Wrapper已被Infinispan (一个大型内存数据管理系统)采用;LIRS

11、和BP-Wrapper在谷歌管理的Java库中优化了 Concurrentlinkedhashmap标准调用程 序,这一程序功能在各类应用中,起到软件缓存的作用;Clock-pro 已被 FreeBSD/NetBSD 操作系统(开源 Unix)采用;Clock-pro是Linux操作系统的一个选项;Clock-pro 是 Aparche Derby 数据库的一个选项;Clock-pro是Open LDAP目录查寻系统的一个选项。结语LIRS算法将最值得保留的数据块放入缓存,并替换出局部性弱的数据块。两个栈的数据结构使 LIRS做出高质量的替换决定,其复杂度又与LRU 一样。Clock-pro和BP-Wrapper让LIRS可以在实际 系统中得以有效地实

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论