用于采用热度和重新定位度量的数据存储存储器的选择性空间收回的方法和系统

摘要

通过以下步骤收回数据存储存储器系统的数据存储存储器的空间：确定数据存储存储器中存储的数据的热度度量；确定与数据存储存储器中的数据的重新定位有关的重新定位度量；确定对于数据使热度度量与重新定位度量相关的数据的效用度量；以及使得其效用度量未达到效用度量阈值的数据可用于空间收回。因此，可以另外地驱逐或降低但是符合或超过效用度量阈值的数据被免除空间收回，并且替代地维持在数据存储存储器中。

说明书

技术领域

本发明涉及计算机实现的数据存储存储器，更具体地涉及存储器空间收 回。

背景技术

计算机实现的数据存储系统典型地包括其中代表主机计算机系统存储数 据的各种类型的数据存储。存储控制响应于读和写请求控制对数据存储介质 和存储器的存取。存储控制可以根据安排为各种冗余、存取速度和安全等级 的数据存储存储器和设备指引数据，数据存储设备诸如高速缓冲存储器、非 易失性存储、RAID(独立盘的冗余阵列)，JBOD(磁盘簇)等。

作为示例，国际商业机器公司ESS(企业存储服务器)，诸如 DS8000^TM，具有称为“中央电子复合体”或“CECs”的计算机实体、高速缓 冲存储器、非易失性存储等的冗余群集。

在数据存储系统中，可以采用快速存储器作为用于存储最近存取过、频 繁存取的、或有可能在不久的将来存取的数据或指令的高速缓冲存储器。代 替被提取或重新计算，高速缓冲存储器中存储的数据可以被迅速存取，从而 节省时间和资源二者。

高速缓冲存储器可以提供在多个等级中。例如，高速缓冲存储器数据存 储系统可以包括“第一”或“主要”高速缓冲存储器和“次级”高速缓冲存 储器二者。典型地，第一高速缓冲存储器比次级高速缓冲存储器具有更快的 存取并且比次级高速缓冲存储器每数据单元更昂贵，并且次级高速缓冲存储 器比第一高速缓冲存储器具有更大的存储容量。例如，第一高速缓冲存储器 包括DRAM(“动态随机存取存储器”)，然而次级高速缓冲存储器包括快 闪存储器固态驱动器(SSD)，诸如“Flash_Cache”(国际商业机器公司注 册商标)。当存取数据时，计算系统或设备可以首先在第一高速缓冲存储器 中查找数据，并且如果数据不存在于此，则在次级高速缓冲存储器中查找数 据。当在任一存储器中数据不可用时，典型地从包括较慢存取速度的数据存 储的主要数据存储(诸如，RAID、JBOD等)对数据进行存取。当读取数据 时，典型地数据保留在主要数据存储中并且复制到第一高速缓冲存储器和/或 次级高速缓冲存储器。如果第一高速缓冲存储器中的读取数据没有被迅速或 频繁地存取，则其可以被降级到次级高速缓冲存储器或被驱逐。如果次级高 速缓冲存储器中的读取数据没有被迅速或频繁地存取，则其可以被驱逐。当 写入数据时，计算系统或设备可以将数据写入到第一高速缓冲存储器。如果 没有迅速地或频繁地存取第一高速缓冲存储器中的写入数据，则该数据可以 被降级到次级高速缓冲存储器。如果没有迅速地或频繁地从次级高速缓冲存 储器存取数据，则可以将其降级到更慢存取速度的数据存储，诸如RAID、 JBOD等。可替代地，写入数据在被数据存储系统接收之后可以尽快写入到 主要数据存储。

典型地，采用LRU(最近最少使用)算法来将数据降级到下一较低等级 或从第一高速缓冲存储器或次级高速缓冲存储器驱逐数据。

在一些存储器中，诸如次级高速缓冲存储器，数据以日志结构方式存储 为(顺序地写入，要求在逻辑的基础上确定数据存储在哪的日志)大数据范 围的页面。在LRU算法下查看数据页面，并且无效最近最少使用的页面。为 了收回空间，系统将选择具有最多无效的页面的日志结构范围(log-structured  extent，LSE)，并且压缩有效页面，将其重新定位在新LSE中，留下一个或 多个空闲LSE。重新定位招致大量的I/O(输入/输出)重新定位操作，因为 许多LSE需要被读取并且一个或多个LSE在收回过程的每个迭代处被写入。

发明内容

提供方法、计算机实现的数据存储存储器系统和计算机程序产品用于收 回数据存储存储器系统的数据存储存储器的空间。在本上下文中的“存储器” 是必须无效、驱逐或降级数据以为新进入的数据腾出可用空间的任何类型的 存储器，其示例是高速缓冲存储器。

在计算机实现的数据存储存储器系统的一个实施例中，执行以下步骤：

确定数据存储存储器中存储的数据的热度度量；

确定与数据存储存储器中的数据的重新定位有关的重新定位度量；

确定对于数据使热度度量与重新定位度量相关的数据的效用度量；

使得其效用度量未达到效用度量阈值的数据可用于空间收回；以及

其效用度量符合或超过效用度量阈值的数据免除空间收回。

因此，可以另外地保存但是未达到效用度量阈值的数据被替代地无效， 并且不必在数据存储存储器中重新定位。

在进一步的实施例中，最近添加到数据存储存储器的数据被免除空间收 回合格。

在又进一步的实施例中，通过空间管理策略指定为不合格的数据被免除 空间收回合格。

在另一实施例中，从对于数据存储存储器的数据的效用度量的平均值确 定效用度量阈值。

在进一步的实施例中，跨一时间段或预定数量的已处理的请求确定对于 数据存储存储器的数据的效用度量的平均值。

在又一实施例中，从用于数据存储存储器的LRU列表中识别的对于数据 存储的数据的效用度量的平均值动态地确定效用度量阈值。

在另一实施例中，数据存储存储器中存储的数据是页面的形式，并且从 对于具有与该试探空间收回牺牲品相似的热度度量的数据的页面的效用度量 平均值，动态地确定对于数据的试探空间收回牺牲品页面的效用度量阈值。

在另一实施例中，数据存储存储器中存储的数据在日志结构范围是页面 的形式；以及该方法还包括：

无效收回合格的数据页面选择具有最大数量的无效页面的至少一个日志 结构范围，用于将其中有效的页面重新定位到另一日志结构范围中，以便收 回选择的日志结构范围。

在进一步的实施例中，热度度量基于对其热度度量正在被确定的数据的 命中的数量；并且重新定位度量基于其重新定位度量正在被确定的数据重新 定位到另一日志结构范围的次数。

附图说明

现在将参考附图仅通过示例的方式描述本发明的优选实施例，其中：

图1是其中实现本发明的示例性网络和计算机实现的存储服务器系统的 框图；

图2是图1的计算机实现的数据存储存储器系统的图解示意；

图3是通过图2的数据存储存储器系统存储的数据的范围的图解示意； 以及

图4是描绘操作图1和2的系统的示例性方法的流程图。

具体实施方式

在以下参考附图的描述中以优选实施例描述本发明，其中同样的数字代 表相同或相似的元件。虽然按照实现本发明目的的最佳方式描述本发明，但 是本领域的技术人员将认识到鉴于这些教导不脱离本发明的范围可以完成多 种变化。

参考图1，用计算机实现的数据存储系统110图示基于计算机的网络架 构100的示例，计算机实现的数据存储系统110可以实现本文讨论的计算机 实现的高速缓冲存储器数据存储系统和方法。仅以示例的方式呈现架构100， 不意图对其限制。本文公开的计算机实现的高速缓冲存储器数据存储系统和 方法可以应用于广泛的多种不同计算机、服务器、数据存储系统和网络架构。

示例性的网络架构100可以包括耦接到网络(诸如，存储域网(SAN) 108)的一个或多个主机计算机系统102。网络108可以包括使用任何适当的 协议的任何合当的专用或公用互连。存储系统110包括存储控制200，其配 置为向和从开关202和数据存储203与204传输数据并且控制开关202和数 据存储203与204的操作。例如，数据存储可以包括经由开关202可存取的 固态驱动器阵列和硬盘驱动器。可替代或附加地，数据存储203和204可以 包括单独的设备或者可以包括具有许多设备的数据存储库。主机系统102的 全部或任何可以指引和利用存储系统110，并且利用本文的存储控制200和 数据高速缓存系统。

高速缓存系统可以实现在存储控制200中，并且还可以可应用于其他存 储系统。如所示，存储控制200包括一个或多个服务器206。控制200还可 以包括主机适配器208和设备适配器210以提供将控制200分别连接到主机 系统102和数据存储203与204的接口。多个服务器206a、206b可以提供冗 余以确保数据总是可用于连接的主机102。因此，如果一个服务器206a故障， 其他服务器206b可以保持运作以确保数据传输能够在主机系统102和数据存 储203与204之间继续。该过程可以称为“故障转移(failover)”。

具有类似于图1中图示的架构的架构的存储系统110的一个示例是国际 商业机器公司的DS8000^TM企业存储服务器。DS8000^TM是提供数据 存储的高性能、高容量存储控制，其设计为支持数据存储的连续操作和实现 数据存储的虚拟化，并且本文仅通过实施例示例的方式呈现，不意图对其限 制。因此，本文讨论的存储器数据存储系统不限于DS8000^TM，但是可以在任 何相当的具有存储器数据无效的存储控制200中实现，而不管制造商、产品 名称或者与系统110相关联的组件或组件名称。

在图1的示例中，每个服务器206可以包括一个或多个计算机处理器212 和存储器214。计算机处理器212可以包括内部处理和存储能力以存储运行 在处理器上并且和其他的事物用于存取数据存储203和204中的数据的软件 模块。

在一个实施例中，存储器214可以包括高速缓冲存储器218。例如每当 主机102在读取操作中从存储系统110存取数据时，执行该操作(例如，从 存储204读取数据)的服务器206可以在可能再次需要该数据的情况下，将 数据保存在其高速缓冲存储器218中。如果主机102再次存取该数据，则服 务器206可以代替从存储203和204提取该数据而从高速缓冲存储器218提 供该数据，节省了时间和资源二者。类似地，当主机系统102执行写入时， 服务器206可以在高速缓冲存储器218中进行存储，或者主机系统102可以 指引在高速缓冲存储器218中存储数据，以在稍后降级到存储203和204。 当在高速缓冲存储器218中存储写入时，该写入也可以存储在相对的服务器 206的非易失性存储器(NVS)220中，以便在第一服务器206故障的情况下 可以通过相对的服务器206恢复该写入。

参考图1和2，存储系统110可以包括诸如硬盘驱动器的数据存储204 和诸如基于快闪存储器的固态驱动器(SSD)的数据存储203二者。SSD驱 动器或其他类型的固态存储器的输入/输出(I/O)性能通常远快于硬盘驱动器 的I/O性能。因为较高的I/O性能，在某些实施例中SSD203可以用于在用 作第一高速缓冲存储器的高速缓冲存储器218和硬盘驱动器204之间提供大 次级高速缓冲存储器300。大次级高速缓冲存储器300的使用可以显著地提 高存储系统110的I/O性能。

如果读取请求通过服务器206接收，使用次级高速缓冲存储器300，该 服务器最初可以在第一高速缓冲存储器218中查找数据，如果数据不存在， 在驻留在SSD203中的次级高速缓冲存储器300中查找数据。如果在任一高 速缓冲存储器中数据均不可用，服务器206可以从硬盘驱动器204检索数据。 类似地，当写入或修改数据时，服务器206最初可以将数据或修改的数据写 入第一高速缓冲存储器218。数据最后可以降级到次级高速缓冲存储器300 以在第一高速缓冲存储器218中腾出空间。数据最终可以降级到盘驱动器204 以在次级高速缓冲存储器300中腾出可用空间。

作为示例，次级高速缓冲存储器300可以使其大小提供存储系统110的 总数据存储容量的约百分之一到百分之二十。因此，对于包括约4千万兆字 节的数据存储(来自硬盘驱动器204和SSD203二者)的存储系统110，该 存储空间的约2百万兆字节可以用作次级高速缓冲存储器300。第一高速缓 冲存储器218典型地是次级高速缓冲存储器300的大小的小百分比。作为示 例性实施例，用于第一高速缓冲存储器218和次级高速缓冲存储器300二者 的存储空间可以安排在各页面中以提供操作的方便。

参考图2、3和4，在一个实施例中，在第一高速缓冲存储器218和也在 次级高速缓冲存储器300中必须收回空间以适应新数据。类似地，一旦所有 的存储器满了，必须提供用于收回空间的部件以便适应新数据。如上所讨论 的，在一些存储器中，诸如次级高速缓冲存储器，数据以日志结构方式在大 数据范围280中存储为页面285。图1的控制200例如利用元数据以数据处 理信息320跟踪数据页面。日志结构范围(LSE)的性质是所有写入是顺序 写入，当存储器300包括SSD时的优点。另一优点是多个页面可以使用单个 I/O(输入/输出)操作写入到存储器。又一优点是用于LSE的内部簿记可以 在LSE280的开始使用小报头290完成。可替代的，小报头290也可以被放 置在范围中的其他地方，诸如范围的末尾。以上讨论缺点并且缺点是有效页 面可以被重新定位，并且可以被重新定位许多次，因为LSE被组合和重新安 排以便以空LSE的形式收回空间。

在一个实施例中，根据LRU算法查看数据页面以提供LRU列表330， 其可以被认为是提名要被无效的页面。如上，如果页面保留并且没有被无效， 但是在包括大量无效页面的LSE中，则页面被重新定位到另一LSE以便可以 收回当前LSE。在数据处理信息320中的页面或页面组的位置以及其中的映 射当页面被重新定位时可以被相应地更新。重新定位度量，诸如重新定位的 数量计数，通过重新定位度量340中的页面跟踪。

在一个实施例中，图1的控制200还跟踪诸如次级高速缓冲存储器300 的存储器中的数据的热度度量310。

热度度量的一个示例是自从数据页面最后存储在数据存储系统中已经存 取数据页面的次数的计数(“命中”)。例如，数据可以位于数据存储204中并 且由主机系统读取以及另外存储在次级高速缓冲存储器300中。此外，新写 入的数据可以存储在高速缓冲存储器300中，未决移动到数据存储204。例 如，命中的数量可以以对于每个页面320的元数据条目中的计数器的形式实 现。

热度度量的其他示例包括超过限定时间段或预定数量的已处理的请求的 页面的“命中”的数量。热度度量可以可替代地包括页面的“命中”与所有 页面的“命中”的平均值相比的比率。

此外，热度度量可以被老化，对不是最近的命中给予较小的权重。该老 化可以是线性的或指数的。

如上所讨论的，虽然诸如LSE280的页面295的一些页面被无效，但是 可以重新定位有效页面297，并且可以重新定位多次，因为LSE以空LSE的 形式被组合和重新安排以收回空间。在一个实施例中，图1的控制200还利 用数据处理信息320跟踪数据的位置，并且当数据重新定位在诸如次级高速 缓冲存储器300的数据存储存储器中时更新位置数据。控制200对于每个页 面跟踪重新定位度量340。

在一个实施例中，重新定位度量340包括在收回过程迭代期间页面已经 被重新定位的次数的计数。为了避免答案为无限的比率的可能性，重新定位 度量r(p)的分母可以被给予初始值“1”。

重新定位度量340和热度度量310二者可以通过用于与元数据320相关 联的每个页面的计数器来确定。

在一个实施例中，通过仅仅选择地重新定位符合热度效用阈值的页面增 加被无效的数据量。剩下的页面将被无效和从高速缓冲存储器移除。也就是 说，许多冷页面将在收回过程期间被处理为无效页面。因此，将避免大量的 重新定位写入，有效地导致更高的存储器性能。

仍然参考图2、3和4，图1的控制200确定对于数据存储存储器300中 存储的数据页面的热度度量h(p)；并且确定与数据存储存储器中的数据的重 新定位有关的重新定位度量r(p)。然后，确定对于数据使热度度量与重新定 位度量相关的数据的效用度量u(p)。其效用度量未达到效用度量阈值T的数 据被无效，使得它的空间可用于空间收回。在一个实施例中，效用度量包括 热度度量与重新定位度量的比率，以公式术语：u(p)＝h(p)/r(p)。

因此，可以另外地保存但是未达到效用度量阈值T的数据替代地被无效， 并且不必在数据存储存储器300中重新定位。

在步骤400，页面285“p”或许通过LRU算法330被提名用于驱逐。

在步骤410，例如通过提取对于页面的热度度量310和重新定位度量340 来测试页面。在步骤420确定对于页面的效用度量，例如热度度量与重新定 位度量的比率，u(p)＝h(p)/r(p)。

在页面最近已经被添加到数据存储存储器300并且发生要被重新定位的 实例中，热度度量可以是冷，因为已经几乎没有命中机会并且重新定位给出 不自然地低的效用度量。因此，在步骤430，检查添加到存储的定时，并且 如果页面最近已经添加到存储，则免除其空间收回合格，并且在步骤440， 使其可用于重新定位，将其保存在存储器330中。因此，该系统允许页面保 留在存储器中一些时间以对其给出获得命中的机会。

步骤430可以安排为将其他空间管理策略350应用于免除页面空间收回 合格。一些示例包括使得已经被命中仅仅一次的数据对于收回合格，但是已 经被命中多于两次的数据在最后命中之后的一时间段不合格；或者通过顺序 读取到达存储器的数据对于收回合格，但是由于随机读取到达的数据对于收 回不合格。

如果步骤430确定页面对于驱逐合格，则其变为试探空间收回牺牲品页 面。

步骤460提供效用阈值T。阈值T可以是固定值，或者可以动态设置。

在一个实施例中，根据对于数据存储存储器300的数据的效用度量的平 均值确定效用度量阈值T。

在另一实施例中，对于数据存储存储器的数据的效用度量的平均值跨一 时间段确定。

在又一实施例中，根据用于数据存储存储器300的LRU列表330中识别 的对于数据存储的数据的效用度量的平均值，动态地确定效用度量阈值T。

步骤470比较对于作为试探空间收回牺牲品的页面p的效用度u(p)量与 阈值T。该意图是仅保存和重新定位具有高效用的那些页面，并且无效未达 到效用度量阈值T的页面，以便他们不必在数据存储存储器中重新定位。

因此，如果步骤470确定对于页面p的效用度量未达到效用度量阈值T， 则步骤480使得该页面可用于空间收回。如果步骤470确定对于页面p的效 用度量符合或超过效用度量阈值T，则步骤440使得页面可用于重新定位， 免除页面空间收回并且将其保存在存储器300中。

步骤490或者移动到下一页面，或者前进以进行LSE的重新定位和重新 安排。页面的重新定位包括确定数据的无效页面对于收回合格；以及选择具 有最大数量的无效页面的至少一个日志结构范围，用于将其中有效的页面重 新定位到另一日志结构范围中，以便收回选择的日志结构范围。

如果不使用LSE以日志结构方式管理存储器300，则跨整个存储器收回 空间，并且重新定位算法、重新定位度量、效用度量和阈值安排为存储器安 排的特有事物。

本领域的技术人员将认识到本文公开的本发明的实施例，包括用于收回 图1的存储系统110的数据存储存储器300的空间、以及在此提供的功能， 可以实施为系统、方法或计算机程序产品。因此，本方面的实施例可以采用 以下形式，即完全的硬件所述、完全的软件实施例(包括固件、驻留软件、 微代码等)、或者硬件和软件结合，诸如本文一般可以称为“电路”、“模块”或 “系统”的组合软件和硬件方面的实施例。此外，本发明的实施还可以采用在 一个或多个非瞬时计算机可读介质中实施的计算机程序产品的形式，该计算 机可读介质具有实现在其上计算机可读的程序代码。

可以采用一个或多个非瞬时计算机可读的介质的任意组合。计算机可读 介质可以是计算机可读存储介质。计算机可读存储介质例如可以是——但不 限于——电、磁、光、电磁、红外线、或半导体的系统、装置或器件，或者 任意以上的适当组合。计算机可读存储介质的更具体的例子(非穷举的列表) 包括以下：具有一个或多个导线的电连接、便携式计算机磁盘、硬盘、随机 存取存储器(RAM)、只读存储器(ROM)、可擦式可编程只读存储器(EPROM 或闪存)、光纤、便携式紧凑磁盘只读存储器(CD-ROM)、光存储器件、磁存 储器件、或者上述的任意合适的组合。在本文的上下文中，计算机可读存储 介质可以是任何包含或存储程序的有形介质，该程序可以被指令执行系统、 装置或者器件使用或者与其结合使用。

计算机可读介质上实现的程序代码可以用任何适当的介质传输，包括— —但不限于——无线、电线、光缆、RF等等，或者上述的任意合适的组合。

可以以一种或多种程序设计语言的组合来编写用于执行本发明的实施例 的操作的计算机程序代码，所述程序设计语言包括面向对象的程序设计语言 —诸如Java、Smalltalk、C++等，还包括常规的过程式程序设计语言—诸如”C” 程序设计语言或类似的程序设计语言。程序代码可以完全地在用户计算机上 执行、部分地在用户计算机上执行、作为一个独立的软件包执行、部分在用 户计算机上部分在远程计算机上执行、或者完全在远程计算机或服务器上执 行。在后者的情形中，远程计算机可以通过任意种类的网络——包括局域网 (LAN)或广域网(WAN)—连接到用户计算机，或者，可以连接到外部计算机(例 如利用因特网服务提供商来通过因特网连接)。

以上将参照根据本发明实施例的方法、装置(系统)和计算机程序产品 的流程图和/或框图描述本发明。将理解，流程图和/或框图的每个方框以及流 程图和/或框图中各方框的组合，都可以由计算机程序指令实现。这些计算机 程序指令可以提供给通用计算机、专用计算机或其它可编程数据处理装置的 处理器，从而生产出一种机器，这些指令通过计算机或其它可编程数据处理 装置的处理器执行，产生了实现流程图和/或框图中的方框中规定的功能/操作 的装置。

也可以把这些计算机程序指令存储在能指令计算机、其它可编程数据处 理装置或其他设备以特定方式工作的计算机可读介质中，这样存储在计算机 可读介质中的指令就产生出一个包括实现流程图和/或框图中的方框中规定 的功能/操作的指令的制造品(manufacture)。

也可以把计算机程序指令加载到计算机、其它可编程数据处理装置、或 其它设备上，使得在计算机、其它可编程数据处理装置或其它设备上执行一 系列操作步骤，以产生计算机实现的过程，从而使得在计算机或其它可编程 装置上执行的指令提供实现流程图和/或框图中的方框中规定的功能/操作的 过程。

本领域的技术人员将理解可以关于以上讨论方法做出改变，包括对步骤 的排序的改变。此外，本领域的技术人员将理解可以采用与本文图示的相比 不同的具体组件安排。

虽然已经详细图示了本发明的优选实施例，但是不脱离如权利要求阐述 的本发明的范围，对本领域的技术人员而言可以出现对这些实施例的修改和 改装应当是显然的。