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

数据存储管理技术的更新换代 数据存储管理技术的更新换代是计算机科学中的一个关键技术，从微型的手机到大型的计算机和数据库系统，数据管理的技术都是由替换算法来实现的。 Replacement Algorithm 是一种简单的概念，但是它的优化和系统实现有各种挑战和困难。 replacement Algorithm 的发展可以追溯到 1966 年，IBM 学者 L.Belady 发表了 LRU（Least Recent Used）替换算法。1968 年，美国麻省理工学院教授 F.J. Corbato 用 Clock 近似操作在分时操作系统中的内存管理中实现了 LRU 算法。在过去的四十几年里，计算机学者和系统工程师从理论和实践上对替换算法的更新和改进做了不懈的努力。 LRU 算法是一个经典的存储管理算法，但是它有几个致命的缺陷，例如一次性访问的数据和弱局部性的数据可以长期滞留在 LRU 栈中，且 LRU 栈的长度是 k 时，一个 k+1 的数据循环访问是没有任何命中的。为了解决 LRU 算法的这三个问题，计算机学者和系统工程师从算法和系统实现上入手，做了大量的工作，但是成效不是很大。 LIRS 算法是用重新访问距离来做替换决定的，这样可以从根本上解决 LRU 的三个问题。LIRS 算法的数据结构是由一个大栈和一个小栈构成的，在大栈中，记录有三种数据块：经常被访问的块、刚刚被访问的块和刚刚被替换出去的块。 LIRS 算法的优点是解决了 LRU 的三个问题，且保持了 LRU 的所有优点，即合理的假设和简单的数据结构。LIRS 算法的应用在主要的操作系统和数据库系统中，逐步取代了 LRU 和 Clock，更新了这个存储管理的关键技术。 数据存储管理技术的更新换代对数据密集型计算的影响非常关键，例如增加访问数据的延迟也增加了不必要的能源消耗和系统的不稳定因素。因此， replacement Algorithm 的质量在数据密集型计算中起着非常关键的作用。 计算机科学中的数据存储管理技术的更新换代对缓存区的影响也非常关键，例如 CPU 芯片上有 L1、L2 和 L3 三层硬件快速缓存（Cache）；操作系统将程序的虚拟地址转换为内存的物理地址，这些转换数据也缓存在芯片内的 TLB 里 ；在 DRAM 内存中有行缓存区（Row Buffer）；磁盘内也有缓存区（Disk Cache）。数据中心和互联网上都有各种大大小小的缓存区。如果数据在某一层缓存区找不到，系统就要到下层去找，这样大大增加了访问的延迟。 数据存储管理技术的更新换代对数据密集型计算和缓存区的影响非常关键，因此 replacement Algorithm 的质量和系统实现对数据存储管理技术的更新换代起着非常关键的作用。