用于存储子系统的关联和原子回写高速缓冲存储系统和方法

摘要

本申请涉及用于存储子系统的关联和原子回写高速缓冲存储系统和方法。响应于来自主机的可高速缓冲存储写入请求，从自由列表中分配物理高速缓冲存储位置，并且在不考虑到对应逻辑地址的任何读取请求是否待决的情况下将数据块写入所述高速缓冲存储位置。在所述数据已经写入之后，同样在不考虑任何读取请求是否针对所述对应逻辑地址待决的情况下，更新元数据以使所述高速缓冲存储位置与所述逻辑地址相关联。维持针对具有有效数据的每个高速缓冲存储位置待决的数据存取请求的计数，并且仅当所述计数指示没有数据存取请求针对所述高速缓冲存储位置待决时将高速缓冲存储位置返回到所述自由列表。

权利要求

1.一种用于在数据存储子系统中高速缓冲存储的方法，其包括：接收写入请求，所述写入请求指示一或多个逻辑地址和待对应地写入所述一或多个逻辑地址的一或多个数据块；

响应于所述写入请求，从自由列表分配高速缓冲存储器中的一或多个物理位置；

将所述一或多个数据块存储在所述一或多个物理位置中；

响应于逻辑地址确定哈希表槽位；

确定在所述哈希表槽位中的多个表项中的任何一个是否识别所述逻辑地址；

将识别所述一或多个物理位置的识别信息存储在一或多个数据结构中；

更新哈希表中的表项以包括到所述一或多个数据结构的指针；

维持针对所述高速缓冲存储器中具有有效数据的每个物理位置待决的包括读取请求的数据存取请求的计数；以及当所述计数指示没有数据存取请求针对所述物理位置待决时将所述物理位置返回到所述自由列表。

2.根据权利要求1所述的方法，其中分配所述一或多个物理位置包括在不考虑所述一或多个物理位置在所述高速缓冲存储器中的顺序的情况下从所述自由列表中选择所述一或多个物理位置。

3.根据权利要求1所述的方法，其中分配所述一或多个物理位置包括在不考虑与所述写入请求相关联的所述一或多个逻辑地址的情况下从所述自由列表中选择所述一或多个物理位置。

4.根据权利要求1所述的方法，其中：

分配所述一或多个物理位置包括产生包含识别所述一或多个物理位置的信息的分散-聚集列表SGL；以及在所述一或多个物理位置中存储所述一或多个数据块包括：将所述SGL提供到直接存储器存取DMA引擎；以及所述DMA引擎响应于所述SGL将所述一或多个数据块从主机接口传送到所述高速缓冲存储器。

5.根据权利要求1所述的方法，其中所述一或多个数据结构限定链表。

6.根据权利要求5所述的方法，其中所述方法进一步包括响应于确定在所述哈希表槽位中所述表项中没有一个识别所述逻辑地址而将新数据结构添加到所述链表。

7.根据权利要求6所述的方法，其进一步包括将识别在所述链表中的所述新数据结构的信息添加到最近最少使用的脏列表。

8.根据权利要求1所述的方法，其中所述一或多个数据结构中的每一个包括多个子结构，每个子结构经配置以存储识别在所述高速缓冲存储器中的所述物理位置之一的所述识别信息，每个子结构进一步经配置以存储针对所述识别信息所识别的所述物理位置待决的所述数据存取请求的计数。

9.根据权利要求8所述的方法，其中每个子结构进一步经配置以存储脏指示符，所述脏指示符指示所述识别信息所识别的所述物理位置是否包含脏数据。

10.一种用于在数据存储子系统中高速缓冲存储的系统，其包括：高速缓冲存储器；以及

处理系统，其经配置以：

接收写入请求，所述写入请求指示一或多个逻辑地址和待对应地写入所述一或多个逻辑地址的一或多个数据块；

响应于所述写入请求，从自由列表分配高速缓冲存储器中的一或多个物理位置；

将所述一或多个数据块存储在所述一或多个物理位置中；

响应于逻辑地址确定哈希表槽位；

确定在所述哈希表槽位中的多个表项中的任何一个是否识别所述逻辑地址；

将识别所述一或多个物理位置的识别信息存储在一或多个数据结构中；

更新哈希表中的表项以包括到所述一或多个数据结构的指针；

维持针对所述高速缓冲存储器中具有有效数据的每个物理位置待决的包括读取请求的数据存取请求的计数；以及当所述计数指示没有数据存取请求针对所述物理位置待决时将物理位置返回到所述自由列表。

11.根据权利要求10所述的系统，其中所述处理系统经配置以分配所述一或多个物理位置，方法是经配置以在不考虑所述一或多个物理位置在所述高速缓冲存储器中的顺序的情况下从所述自由列表中选择所述一或多个物理位置。

12.根据权利要求10所述的系统，其中所述处理系统经配置以分配所述一或多个物理位置，方法是经配置以在不考虑与所述写入请求相关联的所述逻辑地址的情况下从所述自由列表中选择所述一或多个物理位置。

13.根据权利要求10所述的系统，其中：

所述处理系统经配置以分配所述一或多个物理位置，方法是经配置以产生包含识别所述一或多个物理位置的信息的分散-聚集列表SGL；以及所述处理系统经配置以在所述一或多个物理位置中存储所述一或多个数据块，方法是经配置以进行以下操作：将所述SGL提供到直接存储器存取DMA引擎；以及响应于所述SGL通过所述DMA引擎将所述一或多个数据块从主机接口传送到所述高速缓冲存储器。

14.根据权利要求10所述的系统，其中所述一或多个数据结构限定链表。

15.根据权利要求14所述的系统，其中所述处理系统经配置以响应于确定在所述哈希表槽位中所述表项中没有一个识别所述逻辑地址而将新数据结构添加到所述链表。

16.根据权利要求15所述的系统，其中所述处理系统进一步经配置以将识别在所述链表中的所述新数据结构的信息添加到最近最少使用的脏列表。

17.根据权利要求10所述的系统，其中所述一或多个数据结构中的每一个包括多个子结构，每个子结构经配置以存储识别在所述高速缓冲存储器中的所述物理位置之一的所述识别信息，每个子结构进一步经配置以存储针对所述识别信息所识别的所述物理位置待决的所述数据存取请求的计数。

18.根据权利要求17所述的系统，其中每个子结构进一步经配置以存储脏指示符，所述脏指示符指示所述识别信息所识别的所述物理位置是否包含脏数据。

说明书

用于存储子系统的关联和原子回写高速缓冲存储系统和方法

技术领域

[0001] 本发明大体上涉及数据存储系统，并且更确切地说涉及具有高速缓冲存储器的数据存储系统。

背景技术

[0002] 具有高速缓冲存储器的数据存储子系统可以充当缓冲器以用于主控计算机系统与后端数据存储装置(例如，磁盘驱动器阵列或非易失性(例如，快闪)存储器阵列)之间的频繁存取的数据。具有高速缓冲存储器的数据存储子系统可为(例如)采用促进主机与后端数据存储装置之间的低数据存取时延的加速器卡的形式。高速缓冲存储系统可以确定存储在高速缓冲存储器中的数据被存取的频率，并且仅维持高速缓冲存储器中的最频繁存取的数据同时逐出最不频繁存取的数据。

[0003] 在高速缓冲存储系统中，希望的是最小化时延，时延是在从接收来自主机的请求到写入或读取数据并且完成写入或读取操作之间的时间量。影响时延的特性是高速缓冲存储系统将主机所识别的逻辑地址转移到高速缓冲存储器中的物理存储位置中所需要的查找时间以及高速缓冲存储系统随后将数据传送到那些存储位置或从那些存储位置传送数据所需要的时间。

[0004] 常见类型的高速缓冲存储被称为“回写”，其中在写入请求中从主机接收的数据是首先存储在高速缓冲存储器中的并且使其可用于主机来进行读取，且随后当促进复制操作的条件对时延不太有影响时稍后复制到后端存储装置。存储在高速缓冲存储器中但是尚未被复制到后端存储装置的数据通常被称为“脏”数据。回写高速缓冲存储的缺点在于脏数据可能易受由于系统故障(例如，电源中断)的损失的影响。类似地，数据损失可以由中断高速缓冲存储器中的存储数据的过程的此类故障引起，这可以不合需要地引起一系列存储位置，包含与第一写入请求相关联的数据的一部分以及与随后写入请求相关联的数据的一部分。

[0005] 高速缓冲存储系统可以是直接映射的、完全关联的或此类类型的混合。在直接映射高速缓冲存储系统中，数据块的逻辑地址仅映射到高速缓冲存储器中的一个地址或物理位置，在所述位置处可以存储数据块。举例来说，物理地址可以通过模块化算术计算：高速缓冲存储地址＝逻辑地址模数(高速缓冲存储器中的地址的数目)。相比之下，在完全关联高速缓冲存储系统中，高速缓冲存储块可以存储在高速缓冲存储器中的任何物理存储器位置中。完全关联的高速缓冲存储系统总体上有益于存储器使用效率和命中率。然而，完全关联高速缓冲存储系统的缺点在于用于将所识别的逻辑地址转移到高速缓冲存储器中的物理存储位置中的查找过程可能是缓慢的并且因此影响时延。

发明内容

[0006] 本发明的实施例涉及操作的高速缓冲存储系统和方法。在示例性实施例中，高速缓冲存储系统包括高速缓冲存储器和经编程或经配置以实行所述方法的处理系统。

[0007] 在示例性实施例中，所述方法包括：接收指示一或多个逻辑地址和待对应地写入一或多个逻辑地址的一或多个数据块的写入请求；响应于写入请求，从自由列表分配高速缓冲存储器中的一或多个物理位置；在不考虑到一或多个逻辑地址的任何读取请求是否是待决的情况下将一或多个数据块存储在一或多个物理位置中；在一或多个数据块已经存储在一或多个物理位置中之后，并且在不考虑任何读取请求是否是针对一或多个逻辑地址待决的情况下，更新元数据以使一或多个物理位置与一或多个逻辑地址相关联；维持针对高速缓冲存储器中具有有效数据的每个物理位置待决的包括读取请求的数据存取请求的使用计数；以及当使用计数指示没有数据存取请求是针对物理位置待决时将物理位置返回到自由列表。

附图说明

[0008] 图1是说明根据本发明的示例性实施例的高速缓冲存储系统的方块图。

[0009] 图2是说明根据示例性实施例的高速缓冲存储器的广义映射的概念图。

[0010] 图3是根据示例性实施例说明数据结构之中的示例性关系的数据关系图。

[0011] 图4是说明根据示例性实施例的示例性高速缓冲存储区段链表和相关联的示例性缓冲块的另一数据关系图。

[0012] 图5说明根据示例性实施例的示例性分散-聚集列表。

[0013] 图6A是说明根据示例性实施例的写入操作的流程图。

[0014] 图6B是图6A的流程图的延续。

[0015] 图7A是说明根据示例性实施例的读取操作的流程图。

[0016] 图7B是图7A的流程图的延续。

[0017] 图8是说明根据示例性实施例的系统的操作方法的流程图。

[0018] 图9是说明根据示例性实施例的清空操作的流程图。

具体实施方式

[0019] 如图1中所说明，在本发明的说明性或示例性实施例中，存储子系统10提供主机系统12与后端存储装置14之间的高速缓冲存储。主机系统12可以是任何类型的常规的计算机系统或计算机系统的网络。后端存储装置14可以是任何类型的常规数据量存储系统。举例来说，后端存储装置14可以包括多个物理数据存储装置16、18、20等的阵列。此类物理数据存储装置16、18、20等的实例包括磁盘驱动器、快闪存储器模块和其它类型的非易失性数据存储装置。

[0020] 在本文中描述的示例性实施例中，在后端存储装置14中的多个物理数据存储装置16、18、20等的阵列可符合通常参考“磁盘阵列”或“独立(或便宜的)磁盘的冗余阵列”)的顶罩下的原理中的一或多个。举例来说，根据被称为分割法的常见磁盘阵列原理，后端存储装置14可在条带22的单元中存储数据。物理数据存储装置16、18、20等中的每一个存储每个条带22的一部分。后端存储装置14可以包括任何数目的物理存储装置16、18、20等。(图1中的省略号(“…”)指示包含于阵列中的额外的物理数据存储装置，但是为了清楚起见未单独地示出它们。)由于例如分割法的磁盘阵列原理是所属领域的技术人员很好的理解的，所以未在本文中进一步详细描述此类原理。并且，包括多个物理数据存储装置16、18、20等(例如，磁盘)或符合磁盘阵列原理等的后端存储装置14的上述描述是仅出于描述可以与本发明相关联的示例性数据存储环境或背景的目的提供的，且并非意图进行限制。举例来说，如本文所使用，术语“逻辑地址”应当不被解释为将本发明限制于任何特定的物理数据存储环境、组织、方案等。

[0021] 在示例性实施例中，存储子系统10包括高速缓冲存储器24。高速缓冲存储器24可以是任何类型的，举例来说，例如，双数据速率动态随机存取存储器(DDR-DRAM)。存储子系统10还包括中央处理单元(CPU)26和工作存储器28。工作存储器28可以是任何类型的，举例来说，例如，静态RAM。虽然CPU 26可执行一般化的处理任务，但是存储子系统10进一步包括以下特殊化处理元件：消息处理器30、命令处理器32、高速缓冲存储处理器34、缓冲处理器36、后端处理器38和直接存储器存取(DMA)引擎40。虽然在示例性实施例中存储子系统10包括这些特殊化处理元件，但是其它实施例可以包括更少或更多的处理元件，所述处理元件在此类其它实施例中可执行本文中描述的处理操作中的一些或全部。存储子系统10还包括系统互连件42，例如，总线的系统或矩阵，通过所述系统互连件上文参考的处理元件可以彼此通信。还可以包括上述参考元件中的其它通信或信号路径。还可以包括主机接口44和存储装置接口46，存储子系统10通过所述主机接口与主机系统12通信，存储子系统10通过所述存储装置接口与后端存储装置14通信。主机接口44可符合通信总线标准，举例来说，例如，周边组件高速互连(PCIe)并且包括相关联的PCIe控制器。另外，还可以包括例如存储器接口和相关联的存储器控制器等其它接口，但是为清楚起见未示出。虽然未示出，但是存储子系统10可限定插入到主机系统12的背板或主板中的加速器卡的一部分。上述参考处理元件中的一些或全部可以包含于集成电路装置(未示出)中，例如，现场可编程门阵列(FPGA)、专用集成电路(ASIC)或其它装置。

[0022] 如图2中所说明，高速缓冲存储器24可用于存储下文描述的若干类型的高速缓冲存储相关信息。然而，在其它实施例中，不同类型的数据可以存储在不同存储器或以任何其它方式组织。在示例性实施例中高速缓冲存储器24包括数据区域48、高速缓冲存储区段(CS)区域50、哈希表区域52、分散-聚集列表(SGL)区域54和杂项区域56。如所属领域的技术人员所理解，在图2中为清楚起见以概念性方式描绘了高速缓冲存储器24的这些区域的空间布置，并且信息可以任何方式映射或者布置在高速缓冲存储器24中或其它存储器中。

[0023] 高速缓冲存储的数据以被称作缓冲块的单元存储在数据区域48中。所述单元限定数据的量，举例来说，例如，4千字节(KB)。术语“块”意味着数据是连续的。在其中上文所提及的条带22由例如64KB组成的示例性实施例中，每个条带22因此对应于16个缓冲块。如在下文中进一步详细描述的，任何缓冲块可以高速缓冲存储或存储在数据区域48中的任何可供使用的物理位置(即，地址)中而无需考虑缓冲块的任何排序且无需考虑缓冲块的物理地址与逻辑地址之间的任何关系。因此，对应于条带22的缓冲块未必彼此连续地存储。此特征被称作关联性。

[0024] 出于说明的目的，某些示例性缓冲块58、60、62、64、66、68、70、72等被描绘为存储在数据区域48中的各种物理位置中。(数据区域48中的省略号指示额外的物理位置中的额外的缓冲块，为清楚起见未示出所述额外的缓冲块。)数据区域48的存储容量可以大体上小于后端存储装置14的存储容量。举例来说，后端存储装置14的存储容量可以为太字节的数量级，而数据区域48的存储容量可以为千兆字节或兆字节的数量级。为了促进处理，数据区域48中的物理位置可以通过充当相对于物理存储器地址的索引或偏移的缓冲块标识符(BBID)来识别。如下文参考实例所述，示例性缓冲块68、66、70、62和64是按照由虚线箭头所指示的方式排序的，其中示例性缓冲块68是序列中的第一者，并且示例性缓冲块64是序列中的最后一者(其中额外的缓冲块由省略号指示，但是为清楚起见未示出)。示例性缓冲块58、60、62、64、66、68、70和72在图2中描绘为分散在数据区域48中各处而不是集群在一起是意图举例说明关联性。

[0025] 出于说明的目的，某些示例性高速缓冲存储区段74、76、78等被描绘为存储在高速缓冲存储区段区域50中的物理位置中。额外的高速缓冲存储区段由省略号指示但为清楚起见未示出。如在下文中进一步详细描述的，高速缓冲存储区段是包含描述高速缓冲存储的缓冲块的元数据的数据结构。

[0026] 在图3中说明哈希表80与高速缓冲存储区段102相关的方式。哈希表80可以存储在哈希表区域52中(图2)。哈希函数84被应用到数据的逻辑地址，所述逻辑地址是通过主机系统12起始的写入操作或读取操作(其还可以被相应地称作写入输入/输出(I/O)操作和读取I/O操作)的目标。写入或读取操作通常是响应于存储子系统10从主机12接收到以下项而起始：写入请求或读取请求、将被写入或读取的数据的量的指示以及数据的一或多个逻辑地址。如所属领域的一般技术人员很好理解的，与其中存储子系统10和后端存储装置14对数据进行操作的物理地址空间相比，术语“逻辑地址”是指其中主机系统12对数据进行操作的地址空间。

[0027] 哈希表80包括多个(n个)槽位，其中示出了第一示例性槽位82、第二示例性槽位84等直到另一个示例性槽位86，并且最多达到最后或“第N个”示例性槽位88，其中额外的槽位是通过省略号指示的，但为清楚起见未示出。虽然哈希表80可以具有任何数目的槽位，但是所述数目通常大体上小于主机地址空间中的逻辑地址的数目。哈希函数84的实例是：槽位＝(LBA)MOD(n)，其中“槽位”表示到哈希表80中的槽位的指数，“LBA”表示逻辑地址，并且MOD或模除是模块化算术函数。由于哈希函数到指数的使用是在本领域中很好理解的，所以在本文中未描述进一步的细节。

[0028] 每个槽位具有多个表项90。举例来说，哈希表80的每个槽位可以具有四个表项90。每个哈希表槽位采用多个(即，两个或大于两个)表项90而不是每个哈希表槽位单个表项可以帮助最小化“冲突”，这是因为通常在本领域中参考哈希表地址冲突。如下文所述，(在未中的情况下)槽位内的任何空的表项90可用于满足写入请求。在占据槽位的全部表项的实例中，可以采用链表的形式添加随后的额外的表项92、94等。

[0029] 每个表项90包括逻辑地址字段96、高速缓冲存储区段标识符(CSID)字段98和有效表项字段或位(V)100。如下文关于写入和读取操作的实例所述，高速缓冲存储区段标识符字段98经配置以存储高速缓冲存储区段标识符(例如，指针)，所述标识符识别或索引存储在高速缓冲存储区段区域50中的高速缓冲存储区段(图2)。

[0030] 通过高速缓冲存储区段标识符所识别的每个高速缓冲存储区段可以具有图3中所示的示例性高速缓冲存储区段102的结构。每个此类高速缓冲存储区段包括多个高速缓冲存储区段列表元素，其中示出了第一示例性高速缓冲存储区段列表元素104、第二示例性高速缓冲存储区段列表元素106等一直到最后示例性高速缓冲存储区段列表元素108，其中额外的高速缓冲存储区段列表元素通过省略号指示，但是为清楚起见未单独地示出。在其中上文参考的条带22对应于16个缓冲块的示例性实施例中，每个高速缓冲存储区段可对应地具有16个高速缓冲存储区段列表元素以使得每个高速缓冲存储区段列表元素可以对应于那些缓冲块中的一个。仍然，在其它实施例中每个高速缓冲存储区段可以具有任何数目的高速缓冲存储区段列表元素。

[0031] 每个高速缓冲存储区段列表元素包括以下旗标字段：缓冲块标识符(BBID)字段110、有效缓冲块字段或位(V)112；脏缓冲块字段或位(D)114；清空缓冲块字段或位(F)116；
以及使用计数(CNT)字段118。虽然下文关于写入和读取操作论述了旗标存储在这些旗标字段中的方式，但是可以注意到以下内容。高速缓冲存储区段列表元素的有效(缓冲块)位112指示通过所述高速缓冲存储区段列表元素的缓冲块标识符字段110所识别的缓冲块是否是有效的。如所属领域的技术人员所理解，术语“有效的”常在高速缓冲存储到高速缓冲存储器中的指示位置中的情形下使用，数据已经被写入所述指示位置中。高速缓冲存储区段列表元素的脏(缓冲块)位114指示通过所述高速缓冲存储区段列表元素的缓冲块标识符字段
110所识别的缓冲块是否是脏的。如所属领域的技术人员所理解，术语“脏”常在高速缓冲存储指代尚未被复制到后端存储装置14的高速缓冲存储的数据的情形下使用。高速缓冲存储区段列表元素的清空(缓冲块)位116指示通过所述高速缓冲存储区段列表元素的缓冲块标识符字段110所识别的缓冲块是否在被逐出或“清空”到后端存储装置14的过程中。高速缓冲存储区段列表元素的使用计数字段118指示数据存取请求的数目，包括读取请求和清空操作，这是针对通过高速缓冲存储区段列表元素的缓冲块标识符字段110所识别的缓冲块待决的。高速缓冲存储区段的这些字段因此充当描述通过所述高速缓冲存储区段的缓冲块标识符字段110所识别的缓冲块的方面的元数据。

[0032] 每个高速缓冲存储区段还包括先前高速缓冲存储区段标识符字段120和下一高速缓冲存储区段标识符字段122。如图4中所说明，这些字段可用于在双链表中链接多个高速缓冲存储区段。举例来说，另一个示例性高速缓冲存储区段124可以链接到示例性高速缓冲存储区段102，并且又另一个示例性高速缓冲存储区段126可以链接到示例性高速缓冲存储区段124等。高速缓冲存储区段的此类双链表的其它实例(未示出)可以包括任何数目的高速缓冲存储区段。此类链表中的每个高速缓冲存储区段识别存储在数据区域48中的一或多个缓冲块或与其相关联(通过其缓冲块标识符字段110)(图1)。举例来说，参考图4并且再次参考图2：示例性高速缓冲存储区段102可识别示例性缓冲块68、66和70以及额外的缓冲块(未单独示出但是通过省略号表示)直到另一个示例性缓冲块128或与所述示例性缓冲块相关联；示例性高速缓冲存储区段124可识别又一示例性缓冲块130以及额外的缓冲块(未单独示出但是通过省略号表示)直到缓冲块62或与所述缓冲块相关联；并且示例性高速缓冲存储区段126可识别缓冲块64或与所述缓冲块相关联。

[0033] 应注意根据示例性实施例上述参考条带22对应于16个缓冲块：高速缓冲存储区段102的16个高速缓冲存储区段列表元素(未示出)对应于16个示例性缓冲块68、66、70等直到
128；并且高速缓冲存储区段124的16个高速缓冲存储区段列表元素(未示出)对应于16个示例性缓冲块130等直到62。注意在图2和4中所示的实例中，链表中的最终高速缓冲存储区段
126对应于仅一个示例性缓冲块64，因为在此实例中所涉及的缓冲块的总数并不是16的倍数。在此实例中，高速缓冲存储区段126的一个高速缓冲存储区段列表元素将包含有效的缓冲块标识符，而剩余的15个将不包含有效的缓冲块标识符(并且因此其有效位将是“0”或解除断言的)。如下文所述，写入请求可指示写入的任何数目的缓冲块。指示与高速缓冲存储区段中的高速缓冲存储区段列表元素的数目(例如，16)相比较少的缓冲块的写入请求可能仅需要一个高速缓冲存储区段来完成，而指示大于缓冲块数目的写入操作可能需要多个高速缓冲存储区段(如上文所述链接在一起)。

[0034] 作为数据结构的分散-聚集列表(SGL)可用于传送识别数据区域48中的物理位置的信息，在所述物理位置中存储缓冲块。任何数目的SGL可以被链接在一起。举例来说，如图5中所说明，第一SGL 132可以具有包含识别示例性缓冲块68、66和70的物理位置的信息的分散-聚集表项(SGE)，而第二SGL 134可以具有包含识别示例性缓冲块62和64的物理位置的信息的分散-聚集表项(SGE)。第一SGL 132包括指向第二SGL 134的链接(SGL ID)。至少第一SGL 132还可以包含与缓冲块相关联的高速缓冲存储区段的高速缓冲存储区段标识符(CSID)。

[0035] 如图6A到6B的流程图所说明，可以如下处理写入请求。如块136所指示，存储子系统10接收来自主机系统12的写入请求通知。写入请求指示一或多个逻辑地址和待对应地写入一或多个逻辑地址的数据的一或多个块。数据是从主机12中在与缓冲块相同大小(举例来说，例如，4KB)的块中接收的。写入请求可以指示待写入的任何数目的数据块。另外参考图1，消息处理器30可以接收写入请求并且将信息提供到命令处理器32，所述信息使得命令处理器32起始写入操作。

[0036] 如块138(图6A)所指示，缓冲处理器36(图1)响应于通过在来自自由列表(未示出)的数据区域48中分配一或多个物理位置的写入操作的起始。自由列表指示数据区域48中的物理位置，其中未存储有效的缓冲块并且因此有效的缓冲块对于缓冲块存储装置是可供使用的或“自由的”。物理位置是在不考虑缓冲块的任何顺序的情况下选择或分配的。举例来说，注意在图2中其中存储有示例性缓冲块62、64、66、68和70的物理位置彼此之间不相关，其例外之处在于那些物理位置中的每一个是在执行引起它们存储在那些位置中的写入操作时在自由列表中列出的。示例性缓冲块62、64、66、68和70的逻辑地址可以遵循由它们之间的虚线箭头所指示的顺序，但是所述顺序与它们存储在数据区域48中的物理位置无关。

[0037] 如块140所指示，可以产生包含识别所分配的物理位置的信息的一或多个SGL(未示出)。SGL被传送到DMA引擎40(图1)。如块142进一步指示，DMA引擎40使用SGL信息以将通过来自主机12的写入请求所识别的数据块传送到数据区域48中的所分配的物理位置。存储在高速缓冲存储器24的数据区域48中，数据块现在限定缓冲块，如上文所述。

[0038] 如下文所述，在响应于写入请求将数据从主机12传送到数据区域48之后，高速缓冲存储处理器34(图1)更新元数据以完成写入操作。在数据的传送无法被读取操作打断的情况下，应注意响应于写入请求的写入操作的完成是原子的。换句话说，在缓冲块已经存储在数据区域48中的物理位置中之后，更新元数据以使物理位置与逻辑地址相关联，而不考虑任何读取请求是否是针对逻辑地址待决的。在事务处理的词典中，高速缓冲存储处理器34通过更新元数据“提交”写入事务，由此确保原子性。以下操作涉及更新此类元数据。

[0039] 如块144所指示，高速缓冲存储处理器34在上文描述的哈希表80(图3)中查找在写入请求中所识别的一或多个逻辑地址。如上文所述，哈希函数84将到指数中的逻辑地址解析到哈希表80中的槽位。如块146所指示，高速缓冲存储处理器34比较逻辑地址与所述槽位中的表项中的每一个以确定是否存在指示数据已经高速缓冲存储在所述逻辑地址中的匹配或“命中”。如果四个表项中没有一个是匹配的，那么高速缓冲存储处理器34可遵循上文描述的链表到额外的表项。如果没有表项匹配逻辑地址，那么哈希表查询的结果是“未中”。

[0040] 如果高速缓冲存储处理器34确定(块146)哈希表查询的结果是未中，那么高速缓冲存储处理器34分配新的高速缓冲存储区段，如块148所指示。新高速缓冲存储区段是通过CSID识别的，如上文所述。高速缓冲存储处理器34在槽位表项的可供使用的一个中存储CSID，或者如果槽位本身的全部(例如，四个)表项被占据，那么槽位的“链接”表项的CSID被更新以将下一哈希链接设置到新近添加的CSID。新CSID的先前哈希链接被设置成哈希表的所提及槽位中的“链接”表项的CSID。随后，如块150所指示，对于新近分配的高速缓冲存储区段中的每个高速缓冲存储区段列表元素，高速缓冲存储处理器34将来自SGL的缓冲块标识符复制到缓冲块标识符字段110(图3)中，并且设置它们的有效位和脏位，以及清除清空位和使用计数。并且，如块152所指示，高速缓冲存储处理器34将新近分配的高速缓冲存储区段的高速缓冲存储区段标识符添加到最近最少使用的(LRU)脏链表(未示出)的尾部。LRU脏链表可以用于清空高速缓冲存储的数据到后端存储装置14，如下文所述。通过块146、148、150和152指示的操作涉及写入请求中的数据的一个条带22。如块154所指示，如果写入请求跨越一个以上条带22，那么这些操作是针对每个条带22重复的，对于所述每个条带哈希表查询的结果是未中。

[0041] 如果高速缓冲存储处理器34确定(块146)哈希表查询的结果是命中，那么高速缓冲存储处理器34读取由槽位表项所识别的高速缓冲存储区段，如块156所指示。随后，如块158所指示，对于“空的”每个高速缓冲存储区段列表元素，即，并不已经在其缓冲块标识符字段110中包含有效缓冲块标识符，高速缓冲存储处理器34将来自SGL的缓冲块标识符复制到缓冲块标识符字段110中。在所述高速缓冲存储区段列表元素中，高速缓冲存储处理器34还设置以下旗标(图3)：有效位112被设置成“1”的值(“真实”)；脏位114被设置成“1”的值(“真实”)；以及使用计数118被设置成零的值。对于并不为空的任何高速缓冲存储区段列表元素，即，包含有效的缓冲块标识符，处理在块162处继续(图6B)。

[0042] 如块162和164所指示，如果高速缓冲存储处理器34确定高速缓冲存储区段列表元素的清空位116并不是“0”(“错误”)或者高速缓冲存储区段列表元素的使用计数118包含除零之外的值，那么如块166所指示，高速缓冲存储处理器34将旗标(即，有效位112、脏位114、清空位116和使用计数字段118的值)复制或保存到例如高速缓冲存储器24(图1)的杂项区域56中(如以初始列表元素BBID值作为索引)。一旦保存旗标，则高速缓冲存储处理器34可以用从SGL获得的缓冲块标识符覆写高速缓冲存储区段列表元素的缓冲块标识符字段110，如块168所指示。对于新近写入的缓冲块，旗标被设置成相同级：清空＝0，脏＝1，有效＝1，使用计数＝0。

[0043] 然而，如果高速缓冲存储处理器34确定(块162和164)高速缓冲存储区段列表元素的清空位116是“0”(“错误”)并且高速缓冲存储区段列表元素的使用计数118包含零的值，如块170所指示，那么高速缓冲存储处理器34将在所述高速缓冲存储区段列表元素的缓冲块标识符字段110中的缓冲块标识符解除分配。也就是说，缓冲块标识符返回到上文提及的自由列表。随后，高速缓冲存储处理器34用从SGL获得的缓冲块标识符覆写所述高速缓冲存储区段的缓冲块标识符字段110，如块168所指示。

[0044] 并且响应于哈希表命中，高速缓冲存储处理器34更新LRU脏链表，如块172所指示。更确切地说，如果确定高速缓冲存储区段标识符已经存在于LRU脏链表的位置中，那么从所述位置中移除高速缓冲存储区段标识符，并且用于所述高速缓冲存储区段标识符的新位置被添加到(即，链接到)LRU脏链表的尾部。因此，最近写入的高速缓冲存储区段标识符被移动到LRU脏链表的尾部。如下文所述，以此方式维持LRU脏链表有助于逐出或清空不太近期写入(即，最旧的)数据到后端存储装置14。所述过程随后继续，如上文关于块158所述。

[0045] 如果写入请求跨越一个以上条带22，那么上文描述的操作对于哈希表查询的结果是命中的每个条带22是重复的，如块154所指示。当已经以上文描述的方式处理写入操作的全部条带22时，通知主机12已经完成写入操作，如块174所指示。

[0046] 如图7的流程图所说明，可以如下处理读取请求。如块180所指示，存储子系统10接收来自主机系统12的读取请求。读取请求指示待从中读取数据的一或多个逻辑地址。读取请求可以指示待读取的数据的量。主机系统12读取与缓冲块相同大小的数据的块，举例来说，例如，4KB。另外参考图1，消息处理器30可以接收读取请求并且将信息提供到命令处理器32，所述信息使得命令处理器32起始读取操作。

[0047] 如块182所指示，高速缓冲存储处理器34通过在哈希表80(图3)中执行查询响应于读取操作的起始。也就是说，以上文关于写入操作所述相同的方式，哈希函数84被应用到每个逻辑地址以产生一或多个索引到哈希表80中。每个索引指示待读取的一个槽位。从哈希表80读取的槽位的数目取决于通过读取请求所指示的数据的量。如上文所述，每个槽位表示一个条带22，其可能对应于例如64KB。读取请求可跨越多个条带22。读取所指示的槽位中的每一个以确定结果是否是命中或未中。更确切地说，对于读取操作存在三种可能结果：全部的所请求数据可存在于数据区域48中(所述结果被称作完全命中)；所请求的数据中的一些可存在于数据区域48中(所述结果被称作部分命中)；或者所请求的数据中没有一个可存在于数据区域48中(所述结果被称作未中或完全未中)。

[0048] 如块184所指示，如果高速缓冲存储处理器34确定哈希表查询的结果是命中(可以是完全命中或部分命中)，那么高速缓冲存储处理器34读取通过引起命中的表项所指示的高速缓冲存储区段，如块186所指示。如上文关于图3所述，所述高速缓冲存储区段的每个高速缓冲存储区段列表元素具有有效(缓冲块)位112，所述位指示在所述高速缓冲存储区段列表元素的缓冲块标识符字段110中所识别的缓冲块是否是有效的。在读取请求中所指示的逻辑地址的最低有效位可用于识别包含所请求的缓冲块的缓冲块标识符的高速缓冲存储区段列表元素的开始。随后，如块188所指示，对于相应地通过在其中识别缓冲块的高速缓冲存储区段列表元素的有效的位112和脏位114确定为有效和脏的所请求的缓冲块中的每一个，高速缓冲存储处理器34在所述高速缓冲存储区段列表元素的使用计数字段118中递增所述值或计数。如块190所指示，高速缓冲存储处理器34随后产生和填充一或多个SGL(未示出)以用于从数据区域48中读取数据。高速缓冲存储处理器34随后确定读取请求是否跨越另一个条带22，如块192所指示。如果另一个条带22将被读取，那么处理返回到块184。如果确定(块184)哈希表查询的结果是未中，那么高速缓冲存储处理器34递增未中计数，如块194所指示，并且处理继续，如上文关于块192所述。

[0049] 在已经读取与读取请求相关联的所有条带之后，处理在块196处继续(图7B)。高速缓冲存储处理器34可以使用上文参考的未中计数来确定(块196)结果是否是完全未中，即，没有条带被命中，或者被完全命中(块197)，即，全部的条带被命中。如果高速缓冲存储处理器34确定(块196)结果是完全未中，那么后端处理器38(图1)从后端存储装置14(图1)读取所请求的数据，如块198所指示。DMA引擎40可以参与将数据从后端存储装置14传送到主机12。如果高速缓冲存储处理器34确定(块197)结果是完全命中，那么高速缓冲存储处理器34读取来自数据区域48(图2)的全部的所请求的数据，如块199所指示。如果高速缓冲存储处理器34确定结果是部分命中，即，既不完全未中(块196)也不完全命中(块197)，那么高速缓冲存储处理器34从后端存储装置14中读取无法在数据区域48中发现的所请求的数据的那些缓冲块，如块200所指示，并且从数据区域48中读取可以在数据区域48中发现的所请求的数据的那些缓冲块，如块201所指示。当完成数据传送时，通知主机12已经完成读取操作，如块202所指示。

[0050] 如上文所陈述，SGL可用于促进来自数据区域48的数据的传送。在部分命中而非完全命中的情况下，高速缓冲存储处理器34使用识别脏缓冲块和不脏缓冲块的信息以在SGL中包括信息，所述信息指示从数据区域48中读取哪些缓冲块以及在数据区域48中“跳过”那些缓冲块并且替代地从后端存储装置14中读取。有效且脏的缓冲块必须从数据区域48中读取，但是有效且不脏的缓冲块可以从后端存储装置14中读取。高速缓冲存储管理器34在部分命中的情况下发送SGL(或被链接在一起的多个SGL)到后端处理器38，或者在完全命中的情况下发送SGL到DMA引擎40。如块200所指示，随后从数据区域48、后端存储装置14或数据区域48和后端存储装置14两者的组合中读取所请求的缓冲块。

[0051] 如图8中所说明，高速缓冲存储方法可以包括：(块204)接收指示一或多个逻辑地址和待对应地写入一或多个逻辑地址的一或多个数据块的写入请求；(块206)响应于写入请求，从自由列表分配高速缓冲存储器中的一或多个物理位置；(块208)在不考虑到一或多个逻辑地址的任何读取请求是否待决的情况下将一或多个数据块存储在一或多个物理位置中；(块210)在一或多个数据块已经存储在一或多个物理位置中之后，并且在不考虑任何读取请求是否针对一或多个逻辑地址待决的情况下，更新元数据以使一或多个物理位置与一或多个逻辑地址相关联；(块212)维持数据存取请求或“使用”的计数针对高速缓冲存储器中具有有效数据的每个物理位置待决；以及(块214)当使用计数指示没有数据存取请求针对物理位置待决时将物理位置返回到自由列表。可注意到，当物理位置返回到自由列表时(块214)，对应的高速缓冲存储区段列表元素的有效位是解除断言的。

[0052] 并不详细地描述将数据从数据区域48传送到后端存储装置14(其在本领域中通常被称作从高速缓冲存储器中逐出数据或清空数据)，这是因为逐出或清空数据可以所属领域的一般技术人员所理解的常规方式来执行。简要地，参考图9的流程图，当确定自由列表中的缓冲块的数目已减小到阈值以下时可以将缓冲块从数据区域48清空到后端存储装置14，如块216所指示。如块218所指示，上文描述的LRU脏链表可以促进清空，因为识别最近最少写入的缓冲块的高速缓冲存储区段维持在LRU脏链表的顶部处。此类最近最少写入的缓冲块可以被清空到后端存储装置14并且LRU脏链表更新以去除对应的高速缓冲存储区段。
应注意此类清空操作可以独立于上文描述的写入和读取操作执行，即，在背景技术中。另外，虽然在图9中为清楚起见未示出，但是在一或多个缓冲块被清空之后，使用计数递减，如图8中的块212所指示。类似于图8中的块214，如果递减的使用计数是零，指示没有读取请求或清空操作(本文中统称为数据存取请求)是针对物理位置(通过BBID所识别)待决的，那么物理位置返回到自由列表，并且对应的高速缓冲存储区段列表元素的有效位是解除断言的。

[0053] 应理解图6A到6B和7A到7B、8和9的流程图仅意图是所描述的方法的基础的示例性或说明性逻辑。所属领域的技术人员可以理解在各种实施例中存储子系统可以各种方式中的任何一种配置以实行所描述的方法。在一些实施例中，上文关于图6A到6B、7A到7B、8和9所述的步骤或动作可以按照任何合适的顺序或序列发生，包括彼此并行或异步地发生。在一些实施例中，上文所述的步骤或动作可以与其它步骤或动作组合或省略。虽然为清楚起见在图1中采用单个处理元件的形式进行描绘并且在图6A到6B、7A到7B、8和9中采用单个流程图的形式进行描绘，但是基础逻辑可以任何合适方式模块化或分布在硬件或软件元件的任何组合之中。

[0054] 应注意已经出于展示本发明的原理和概念的目的参考一或多个示例性实施例描述了本发明。本发明不限于这些实施例。如将通过所属领域的技术人员所理解，鉴于本文中提供的描述，可以作出本文中描述的实施例的许多变化并且全部的此类变化都在本发明的范围内。