数据存储管理技术的更新换代

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可以在实际 系统中得以有效地实