用于改进重复数据删除的内存控制器和方法与流程

1.本发明大体上涉及数据模式识别，尤其涉及内存控制器和用于内存控制器的方法。


背景技术：

2.重复数据删除是一种用于减少通过网络传递或存储在数据存储系统中的数据量的方法，通过以粒度级别识别数据的重复并避免显式地传递或存储此类重复。重复数据删除通过以下方式完成：(i)将数据分成段，(ii)计算每个段的指纹(即强哈希)，(iii)使用指纹识别相同的数据(即重复数据)。重复数据删除方法中的主要问题是如何高效地定位与传入指纹大概率相同的现有指纹，因为指纹量对于与重复数据删除最相关的大量数据来说非常重要。
3.解决上述问题的一种已知方法是通过稀疏索引。稀疏索引包括具有索引字段的文档的条目，即使索引字段为空值。使用稀疏索引的方法包括：(i)将指纹划分为区域(即关联块)，(ii)通过确定性方法从每个区域选择代表(即弱哈希)。代表是从选定的指纹导出的。例如，选择该区域中具有最大值的两个指纹(即强哈希)，并从这些指纹中的每一个中选择要使用的比特子集作为代表。
4.这些代表带有指向它们所表示区域的指针，被放置到稀疏索引中。当新指纹到达(即传入指纹)时，将以与存储指纹相同的方式从新指纹中选择新代表。这些新代表用于在稀疏索引中搜索。在稀疏索引中定位相同的代表后，将上传相关的指纹区域，并对传入指纹与现有指纹进行逐一比较。当识别到相同的指纹时，可以定位重复的数据。
5.稀疏索引中的信息需要与现有指纹一致。否则，由于现有指纹在稀疏索引中可能不会被代表，因此重复数据删除率可能会降低。检测较大区块的相似性，一方面有利于使元数据占用空间较小，用于保持索引层较高，另一方面，一旦数据和元数据根据时间和/或位置参考分组，就能够高效地访问元数据和数据信息。但是，在处理小文件和/或执行小的随机覆盖时，存在两个问题：(1)如何将小文件分组成一个相对大的关联块(维护小的关联块效率不高)；(2)如何查找代表指纹(否则，需要为每个小的随机io访问稀疏索引)。
6.有几种基本方法可以维护元数据，并在查找数据重复的同时提高访问低性能介质的效率。一种这样的已知方法涉及使用预测过滤器来预测这种访问应实现成功相似性检测的概率。通过这样做，可以显著减少由于搜索元数据的尝试失败而导致的性能降低，并且可以显著提高性能。这种预测过滤器的一个很好的示例是布隆过滤器。然而，使用预测过滤器来提高对低性能介质的访问效率是具有挑战性的，因为此类过滤器没有高效删除引用内容的手段，这通常会导致需要在一段时间内将过滤器归零一次。此外，使用预测过滤器本身只能增加单一相似性查找成功的概率，但它确实提供了预测预期数据和元数据、对预期数据和元数据进行提前读取以及高效利用读取和写入缓存的能力。
7.另一种已知的方法涉及使用分层索引层，其中，为较大的数据区块收集元数据。通常，元数据被划分为块，从每个块中确定地选择几个代表，将其添加到索引中。代表选择的
一种可能的确定性方法是在块中选择x个最小哈希，并从中导出可以作为此块的代表添加到索引中的稀疏哈希。对大数据区块使用相似性检测以提高对低性能介质的访问效率是具有挑战性的，因为在某些系统和/或场景中，不可能收集或不可能高效地收集足够的数据来执行需要大数据区块的第一层的相似性检测。例如，存储系统接收小io速率慢，并需要在给定的时间限制内完成每个io，可能无法聚合足够大的数据来进行大数据区块相似性检测，因此无法访问分层索引来检测相似性。
8.在使用确定性方法选择每个块的x个代表的情况下，当接收到防止聚合的小io时，要管理上下文(即)使其能够确定何时有足够的强哈希表示块，并在索引中搜索其代表，或者将执行对小得多的块的代表的搜索——即更多的搜索。因此这可能会带来更多的搜索和更多的io，索引中可能会找到更多的匹配项，但它们指向的块可能与选择要搜索的代表的强哈希集不匹配(小得多)。
9.在某些情况下，引用的上下文可能太小以至于添加的元数据成本变得很大，并影响整体系统性能。例如，在使用单个文件作为相似性上下文来检测文件相似性时，元数据/数据的比率在小文件中会显著增长，并显著降低数据缩减率。
10.因此，需要解决在数据存储系统中检测用于重复数据删除的数据相似性时的上述技术缺陷和问题。


技术实现要素：

11.该目的通过独立权利要求的特征来实现。此外，实现方式在从属权利要求、说明书和附图中是显而易见的。
12.本发明提供了一种内存控制器和用于内存控制器接收传入数据和利用重复数据删除存储和/或发送所述传入数据的方法。
13.根据第一方面，提供了一种内存控制器，其设置为接收传入数据，并利用重复数据删除存储和/或发送所述传入数据。所述内存控制器用于确定与一个或多个第一哈希对应的第二哈希。所述第二哈希是稀疏哈希，对应一个或多个第一哈希。所述第一哈希是强哈希。所述内存控制器用于，使用所述第二哈希填充稀疏索引。所述稀疏索引将所述第二哈希与对应的第一哈希相关联。所述内存控制器还用于使用概率方法，基于所述第二哈希对应于多个第一哈希的概率来确定所述第二哈希。
14.所述内存控制器通过在概率方法中填充稀疏索引，并使用相同的概率方法从传入的第一哈希中选择要在稀疏索引中搜索哪些代表，优化对小文件和/或小随机io的支持。所述内存控制器基于概率方法从少量传入的第一哈希中选择代表，该概率方法有很大概率为类似的第一哈希集选择与存储在索引中的代表相同的代表。这种方法减少了对稀疏索引的访问次数，因为该稀疏索引仅用于代表性的第一哈希。内存控制器使用小的第二哈希集将多个小文件作为单个虚拟大文件处理。在定位匹配后，所述内存控制器将上传由第一哈希代表的所有块到内存中。对于大文件中的小io，或确定分组在一起的小文件中的小io，上传的块将很有可能包括可能与未来将要接收的第一哈希匹配的第一哈希。因此，内存控制器利用“预读的”第一哈希数据来设置缓存的种子。
15.概率方法可以是数学概率方法。可选地，所述内存控制器还用于选择第一哈希的代表，并根据代表确定第二哈希。所述内存控制器可以基于具有特定位模式的代表选择代
表。所述特定位模式包括特定数量的前导零。可选地，所述内存控制器还用于，基于单个第一哈希选择多个代表。
16.可选地，所述内存控制器还用于：(i)接收传入数据并将传入数据划分为多个数据区块，(ii)为每个数据区块确定第一哈希，提供一个或多个传入的第一哈希，(iii)基于概率方法为一个或多个传入的第一哈希选择至少一个代表。数据区块的数量可以低于区块数阈值。接收到的传入数据可以代表许多系统请求。系统请求的数量可以低于第一数量阈值。
17.可选地，所述内存控制器还用于读取第一哈希的元数据。概率指示元数据对应于传入数据中的多个第一哈希的概率。所述内存控制器可以是数据存储装置。
18.根据第二方面，提供了一种用于内存控制器的方法，其设置为用于接收传入数据和利用重复数据删除存储和/或发送所述传入数据。该方法包括确定对应于一个或多个第一哈希的第二哈希。所述第二哈希是稀疏哈希，所述第一哈希是强哈希。该方法包括使用所述第二哈希填充稀疏索引。所述稀疏索引将所述第二哈希与对应的第一哈希相关联。该方法包括使用概率方法，基于所述第二哈希对应于多个第一哈希的概率来确定所述第二哈希。
19.该方法通过在概率方法中填充稀疏索引，并使用相同的概率方法从传入的第一哈希中选择要在稀疏索引中搜索哪些代表，优化对小文件和/或小随机io的支持。基于概率方法从少量传入的第一哈希中选择代表，该概率方法有很大概率为类似的第一哈希集选择与存储在索引中的代表相同的代表。这种方法减少了对稀疏索引的访问次数，因为该稀疏索引仅用于代表性的第一哈希。该方法能够使用小的第二哈希集，将多个小文件作为单个虚拟大文件处理。在定位匹配后，将上传由所述第一哈希代表的所有块到内存中。对于大文件中的小io，或确定分组在一起的小文件中的小io，上传的块将很有可能包括可能与未来将要接收的第一哈希匹配的第一哈希。因此，提供一种高效的方法，利用“预读的”第一哈希数据来设置缓存的种子。
20.根据第三方面，提供了一种携带计算机指令的计算机可读介质，所述计算机指令当加载到内存控制器中并由所述内存控制器执行时，使所述内存控制器能够实现上述方法。
21.现有技术中的技术问题得以解决，其中，所述技术问题是通过上下文聚合动态检测小文件和随机io的数据相似性进行重复数据删除。
22.因此，与现有技术不同的是，根据内存控制器和接收传入数据和利用重复数据删除存储和/或发送所述传入数据的方法，提高了检测小文件和随机io的数据相似性的效率，并且内存控制器避免传递或存储由于通过执行更多的搜索在索引中定位更多的匹配而可能发生的重复。例如，所定位的匹配指向的块可能不匹配从其中选择代表进行搜索的小得多的第二哈希集。内存控制器通过在概率方法中填充稀疏索引，并使用相同的概率方法从传入的第一哈希中选择要在索引中搜索的代表，优化对小文件和/或小随机io的支持。
23.本发明的这些和其它方面在下文描述的一种或多种实现方式中是显而易见的。
附图说明
24.现仅通过示例的方式，结合附图对本发明的各实现方式进行说明，其中：
25.图1是本发明的实现方式提供的包括内存控制器的系统的框图；
26.图2是本发明的实现方式提供的内存控制器进行数据分段和第一哈希计算的示例图；
27.图3是本发明的实现方式提供的内存控制器填充稀疏索引的示例图；
28.图4是本发明的实现方式提供的内存控制器从一个大文件中选择代表性的第二哈希的示例图；
29.图5是本发明的实现方式提供的内存控制器从多个小文件中选择代表性的第二哈希的示例图；
30.图6是本发明的实现方式提供的用于内存控制器的方法的流程图，所述内存控制器设置为用于接收传入数据和利用重复数据删除存储和/或发送所述传入数据；
31.图7是计算机系统(例如，内存控制器、数据存储装置)的图示，其可以实现各种先前实现的各种体系结构和功能。
具体实施方式
32.本发明的实现方式提供了一种内存控制器和用于内存控制器的方法。
33.为了使本领域技术人员更容易理解本发明的方案，结合附图描述本发明的以下实现方式。
34.本发明的说明书、权利要求书及上述附图中的“第一”、“第二”、“第三”和“第四”(如果有)等术语用于区分相似的对象，而不一定用于描述特定的序列或顺序。应当理解，如此使用的术语在适当的情况下是可互换的，例如使得本文描述的本发明的实现方式能够以本文所示或所描述的序列以外的序列来实现。此外，术语“包括”和“具有”及其任何变体旨在涵盖非排他性包括。例如，包括一系列步骤或单元的过程、方法、系统、产品或设备不一定限于明确列出的步骤或单元，而是可以包括未明确列出的或此类过程、方法、产品或设备固有的其它步骤或单元。
35.图1是本发明的实现方式提供的包括内存控制器102的系统100的框图。系统100包括内存控制器102。内存控制器102设置为接收传入数据，并利用重复数据删除存储和/或发送所述传入数据。内存控制器102用于确定与一个或多个第一哈希对应的第二哈希。所述第二哈希是稀疏哈希，所述第一哈希是强哈希。内存控制器102用于，使用所述第二哈希填充稀疏索引。所述稀疏索引将所述第二哈希与对应的第一哈希相关联。内存控制器102用于使用概率方法，基于所述第二哈希对应于一个或多个第一哈希的概率来确定所述第二哈希。
36.内存控制器102通过以概率方法填充稀疏索引，并使用相同的概率方法从传入的第一哈希中选择要在稀疏索引中搜索哪些代表，优化对小文件和/或小随机io的支持。内存控制器102基于概率方法从少量传入的第一哈希中选择代表，该概率方法有很大概率为类似的第一哈希集选择与存储在索引中的代表相同的代表。这种方法减少了对稀疏索引的访问次数，因为该稀疏索引仅用于代表性的第一哈希。内存控制器102使用小的第二哈希集将多个小文件作为单个虚拟大文件处理。在定位匹配之后，内存控制器102将上传由所述第一哈希代表的所有块到内存中。对于大文件中的小io，或确定分组在一起的小文件中的小io，上传的块将很有可能包括可能与未来将要接收的第一哈希匹配的第一哈希。因此，内存控制器102通过“预读的”第一哈希数据来设置缓存的种子。
37.概率方法可以是数学概率方法。可选地，内存控制器102还用于选择第一哈希的代
表，并根据该代表确定第二哈希。内存控制器102可以基于具有特定位模式的代表选择代表。所述特定位模式包括特定数量的前导零。
38.为了填充稀疏索引，基于可能有大概率提供与在确定性方法中相同数量的代表的条件，从第一哈希中选择代表。与现有的方法相反，该方法不需要将多个第一哈希聚集在一起以查找最小哈希或最大哈希，而是一次仅使用单个第一哈希来选择代表。内存控制器102从每个第一哈希计算第二哈希，并且仅选择6个最低有效位均为0的那些哈希。这提供了从64个第一哈希中选择一个第一哈希作为代表的概率，按此平均，从每128个第一哈希中选择两个代表。内存控制器102为每个传入的第一哈希计算第二哈希，检查第二哈希是否可能是代表性的，即内存控制器102检查6个最低有效位是否都为0，并且内存控制器102相应地在稀疏索引中搜索第二哈希。因此，内存控制器102不需要存储传入的第一哈希的上下文，来确保来自表示块的每128个第一哈希的两个代表，和查询每个传入的第一哈希的稀疏索引。平均而言，对稀疏索引的查询量可能与维护上下文的查询量相同。
39.可选地，内存控制器102还用于基于单个第一哈希选择多个代表。可选地，内存控制器102还用于(i)接收传入数据并将传入数据划分为多个数据区块，(ii)为每个数据区块确定第一哈希，提供一个或多个传入的第一哈希，和(iii)基于概率方法为一个或多个传入的第一哈希选择至少一个代表。数据区块的数量可以低于区块数阈值。接收到的传入数据可以代表许多系统请求。系统请求的数量可以低于第一数量阈值。
40.可选地，内存控制器102还用于读取第一哈希的元数据。该概率指示元数据对应于传入数据中的一个或多个第一哈希的概率。内存控制器102可以是数据存储装置。
41.图2是本发明的实现方式提供的内存控制器进行数据分段和第一哈希计算的示例图。内存控制器将可变大小的数据段202划分为数据区块204a、204b、204c、204d、204e和204f。内存控制器可以计算对应于数据区块204a、204b、204c、204d、204e和204f的第一哈希206a、206b、206c、206d、206e和206f。
42.内存控制器接收传入数据。传入数据可以是可变大小的数据。内存控制器为每个数据区块确定第一哈希，提供一个或多个传入的第一哈希。数据区块的数量可以低于区块数阈值。接收到的传入数据可以代表许多系统请求。系统请求的数量可以低于第一数量阈值。
43.图3是本发明的实现方式提供的内存控制器填充稀疏索引的示例图。该示例图描绘了第一哈希302a、302b、302c、302d、302e和302f。内存控制器确定对应于一个或多个第一哈希302a、302b、302c、302d、302e和302f的第二哈希304a、304b。第二哈希304a、304b是稀疏哈希，一个或多个第一哈希302a、302b、302c、302d、302e和302f是强哈希。内存控制器用第二哈希304a、304b填充稀疏索引306。稀疏索引306将第二哈希304a、304b与对应的第一哈希302a、302b、302c、302d、302e和302f相关联。内存控制器使用概率方法，基于第二哈希对应于一个或多个第一哈希302a、302b、302c、302d、302e和302f的概率来确定第二哈希304a、304b。内存控制器读取一个或多个第一哈希302a、302b、302c、302d、302e和302f的关联块元数据308a、308b、308c和310a、310b，并且概率指示元数据对应于传入数据中的一个或多个第一哈希302a、302b、302c、302d、302e和302f的概率。
44.概率方法可以是数学概率方法。可选地，内存控制器还用于选择一个或多个第一哈希302a、302b、302c、302d、302e和302f的代表，并基于该代表确定第二哈希304a、304b。内
存控制器基于具有特定位模式的代表选择代表。特定位模式包括特定数量的前导零。
45.内存控制器从每个第一哈希302a、302b、302c、302d、302e和302f计算第二哈希304a、304b，并仅选择6个最低有效位全为0的哈希。这提供了从64个第一哈希中选择一个第一哈希作为代表的概率，按此平均，从每128个第一哈希中选择两个代表。内存控制器为每个传入的第一哈希计算第二哈希。内存控制器检查每个用于传入的第一哈希的第二哈希是否是代表性的，即内存控制器检查6个最低有效位是否都为0，并相应地在稀疏索引中搜索第二哈希。因此，内存控制器不需要存储传入的第一哈希的上下文，来确保代表块的每128个第一哈希中的两个代表和查询每个传入的第一哈希的稀疏索引。平均而言，对稀疏索引的查询量可能与维护上下文的查询量相同。可选地，内存控制器还用于基于单个第一哈希选择一个或多个代表。
46.图4是本发明的实现方式提供的内存控制器从大文件402中选择代表性第二哈希的示例图。示例图描绘了包括块0到块n
–
1的文件402。每个块的文件大小为8kb。一个或多个第一哈希404包括每个块160位，一个或多个第二哈希406包括每个块64位。内存控制器从每个第一哈希404计算第二哈希，并仅选择6个最低有效位全为0的那些哈希。这提供了从64个第一哈希中选择第一哈希作为代表的概率，按此平均，从每128个第一哈希中平均选择两个代表408a、408b。当接收到传入的第一哈希时，内存控制器为每个传入的第一哈希计算第二哈希。检查第二哈希是否是(即)6个最低有效位都为0的代表。如果第二哈希是代表，则内存控制器可以在稀疏索引中执行对第二哈希的搜索。内存控制器还用于读取第一哈希的元数据，概率指示元数据对应于传入数据中的第一哈希的概率。因此，如果在读取块的元数据时确定相似性，则后续的块可能是相似的，因此不需要读取更多的块。为整个块维护一个上下文可以避免不必要地读取块，因为每次读取都需要时间。
47.图5是本发明的实现方式提供的内存控制器从多个小文件502中选择代表性第二哈希的示例图。示例图描绘了包括块0到块n
–
1的多个小文件502。每个块的文件大小为8kb。至少有两个块构成文件。一个或多个第一哈希504包括每个块160位，一个或多个第二哈希506包括每个块64位。内存控制器从每个第一哈希504计算第二哈希，并仅选择6个最低有效位全为0的那些哈希。这提供了从64个第一哈希中选择一个第一哈希作为代表的概率，按此平均，从每128个第一哈希504中选择两个代表508a、508b。当接收到传入的第一哈希504时，内存控制器为每个传入的第一哈希504计算第二哈希。内存控制器检查第二哈希是否为(即)6个最低有效位都为0的代表。如果第二哈希是代表，则内存控制器可以在稀疏索引中执行对第二哈希的搜索。可以使用小的第二哈希集506将多个小文件作为单个虚拟大文件处理。
48.图6是本发明的实现方式提供的用于内存控制器的方法的流程图，该内存控制器设置为用于接收传入数据和利用重复数据删除存储和/或发送所述传入数据。在步骤602中，确定第二哈希。第二哈希是对应于一个或多个第一哈希的稀疏哈希，第一哈希是强哈希。在步骤604中，用第二哈希填充稀疏索引。所述稀疏索引将所述第二哈希与对应的第一哈希相关联。在步骤606中使用概率方法，基于第二哈希对应于一个或多个第一哈希的概率来确定第二哈希。
49.该方法通过在概率方法中填充稀疏索引，并使用相同的概率方法从传入的第一哈希中选择要在稀疏索引中搜索哪些代表，优化对小文件和/或小随机io的支持。基于概率方
法从少量传入的第一哈希中选择代表，该概率方法有很大概率为类似的第一哈希集选择与存储在索引中的代表相同的代表。这种方法减少了对稀疏索引的访问次数，因为该稀疏索引仅用于代表性的第一哈希。该方法能够使用小的第二哈希集，将多个小文件作为单个虚拟大文件处理。在定位匹配后，将上传由第一哈希代表的所有块到内存中。对于大文件中的小io，或确定分组在一起的小文件中的小io，上传的块将很有可能包括可能与未来将要接收的第一哈希匹配的第一哈希，从而提供了一种高效的方法，即利用“预读的”第一哈希数据来设置缓存的种子。当重复数据删除机制集成到存储系统的数据路径中时，该方法是有益的，并且存储系统确保小文件的强哈希能确定分组在一起。
50.图7是计算机系统(例如，内存控制器、数据存储装置)的图示，其中包括可以实现各种先前实现的各种体系结构和功能。如图所示，计算机系统700包括连接到总线702的至少一个处理器704，其中计算机系统700可以使用任何合适的协议来实现，例如外围组件互连(peripheral component interconnect，pci)、pci-express、加速图形端口(accelerated graphics port，agp)、超传输或任何其它总线或一个或多个点对点通信协议。计算机系统700还包括内存706。
51.控制逻辑(软件)和数据存储在内存706中，内存706可以采取随机存取存储器(random-access memory，ram)的形式。在本发明中，单个半导体平台可以指唯一的基于单一半导体的集成电路或芯片。应当注意，术语单半导体平台也可以指具有增加的连通性的多芯片模块，其模拟芯片上操作，并且对使用传统的中央处理单元(central processing unit，cpu)和总线实现进行实质性的改进。当然，根据用户的愿望，各种模块也可以单独地放置或以半导体平台的各种组合放置。
52.计算机系统700还可以包括辅助存储器710。辅助存储器710包括例如硬盘驱动器和可移动存储驱动器，代表软盘驱动器、磁带驱动器、压缩磁盘驱动器、数字多功能磁盘(digital versatiledisk，dvd)驱动器、记录设备、通用串行总线(universal serial bus，usb)闪存。可移动存储驱动器以众所周知的方式读取和写入至少一个可移动存储单元。
53.计算机程序或计算机控制逻辑算法可以存储在至少一个内存706和辅助存储器710中。当执行这样的计算机程序时，计算机系统700能够实现如上所述的各种功能。内存706、辅助存储器710和任何其它存储器是计算机可读介质的可能示例。
54.在一种实现方式中，在各种先前附图中描述的体系结构和功能可以在处理器704、耦合到通信接口712的图形处理器、具有处理器704和图形处理器两者的至少一部分能力的集成电路(未示出)、芯片组(即，一组集成电路，设计用于作为执行相关功能的单元工作和销售等)的上下文中实现。
55.此外，在各种先前描述的附图中描述的体系结构和功能可以在一般计算机系统、电路板系统、专用于娱乐目的的游戏控制台系统、特定于应用的系统的上下文中实现。例如，计算机系统700可以采取台式计算机、笔记本电脑、服务器、工作站、游戏机、嵌入式系统的形式。
56.此外，计算机系统700可以采取各种其它设备的形式，包括但不限于个人数字助理(personal digital assistant，pda)设备、移动电话设备、智能手机、电视等。此外，尽管未示出，但计算机系统700可以通过i/o接口708耦合到网络(例如，电信网络、局域网(local area network，lan)、无线网络、互联网等广域网(wide area network，wan)、对等网络、电
缆网络等)来通信。
57.应当理解，在所描述的附图中示出的组件的布置是示例性的，并且其它布置也是可能的。还应理解，由权利要求定义的、下文描述的并在各种框图中示出的各种系统组件(和装置)代表根据本文公开的主题配置的一些系统中的组件。例如，这些系统组件(和装置)中的一个或多个可以全部或部分地在所描述的附图的所示的布置中所示的至少一些组件中实现。
58.此外，虽然至少一个这些组件中的至少部分实现为电子硬件组件并因此构成机器，但其它组件可以在软件中实现。当该软件包括在执行环境中时，构成机器、硬件或软件和硬件的组合。
59.虽然本发明及其优点已详细描述，但是应当理解，在不脱离所附权利要求书界定的本发明的精神和范围的情况下，可以作出各种改变、替代和更改。

技术特征：
1.一种内存控制器(102)，其特征在于，设置为接收传入数据并利用重复数据删除存储和/或发送所述传入数据，所述内存控制器(102)用于：确定第二哈希(304a和304b、408a和408b、508a和508b)，所述第二哈希(304a和304b、408a和408b、508a和508b)是稀疏哈希，并对应于一个或多个第一哈希(206a至206f、302a至302f、404、504)，所述第一哈希(206a至206f、302a至302f、404、504)是强哈希；用所述第二哈希(304a和304b、408a和408b、508a和508b)填充稀疏索引(306)，所述稀疏索引(306)将所述第二哈希(304a和304b、408a和408b、508a和508b)与对应的第一哈希(206a至206f、302a至302f、404、504)相关联，所述内存控制器(102)特征在于，所述内存控制器(102)还用于使用概率方法，基于所述第二哈希(304a和304b、408a和408b、508a和508b)对应于多个第一哈希(206a至206f、302a至302f、404、504)的概率来确定所述第二哈希(304a和304b、408a和408b、508a和508b)。2.根据权利要求1所述的内存控制器(102)，所述内存控制器(102)特征还在于，所述概率方法是数学概率方法。3.根据权利要求1或2任一项所述的内存控制器(102)，所述内存控制器(102)特征还在于，所述内存控制器(102)还用于选择所述第一哈希(206a至206f、302a至302f、404、504)的代表，并基于所述代表确定所述第二哈希(304a和304b、408a和408b、508a和508b)。4.根据权利要求3所述的内存控制器(102)，其特征在于，所述内存控制器(102)基于具有特定位模式的代表选择所述代表。5.根据权利要求4所述的内存控制器(102)，其特征在于，所述特定位模式包括特定数量的前导零。6.根据权利要求3至5任一项所述的内存控制器(102)，所述内存控制器(102)特征还在于，所述内存控制器(102)还用于基于单个第一哈希(206a至206f、302a至302f、404、504)选择多个代表。7.根据上述权利要求中任一项所述的内存控制器(102)，所述内存控制器(102)特征还在于，所述内存控制器(102)还用于：接收所述传入数据，并将所述传入数据划分为多个数据区块(204a至204f)；为每个数据区块(204a至204f)确定第一哈希(206a至206f、302a至302f、404、504)，以提供一个或多个传入的第一哈希(206a至206f、302a至302f、404、504)；基于所述概率方法为所述一个或多个传入的第一哈希(206a至206f、302a至302f、404、504)选择至少一个代表。8.根据权利要求7所述的内存控制器(102)，所述内存控制器(102)特征还在于，所述数据区块(204a至204f)的数量低于区块数阈值。9.根据权利要求8所述的内存控制器(102)，所述内存控制器(102)特征还在于，接收到的传入数据表示系统请求的数量，其中，所述系统请求的数量低于第一数量阈值。10.根据上述权利要求中任一项所述的内存控制器(102)，其特征在于，所述内存控制器(102)还用于读取第一哈希(206a至206f、302a至302f、404、504)的元数据，其中，所述概率指示所述元数据对应于所述传入数据中的多个第一哈希(206a至206f、302a至302f、404、504)的概率。
11.根据上述权利要求中任一项所述的内存控制器(102)，其特征在于，所述内存控制器(102)是数据存储装置。12.一种用于内存控制器(102)的方法，其特征在于，所述内存控制器(102)被设置为用于接收传入数据和利用重复数据删除存储和/或发送所述传入数据，所述方法包括：确定第二哈希(304a和304b、408a和408b、508a和508b)，所述第二哈希(304a和304b、408a和408b、508a和508b)是稀疏哈希，并对应于一个或多个第一哈希(206a至206f、302a至302f、404、504)，所述第一哈希(206a至206f、302a至302f、404、504)是强哈希；用所述第二哈希(304a和304b、408a和408b、508a和508b)填充稀疏索引(306)，所述稀疏索引(306)将所述第二哈希(304a和304b、408a和408b、508a和508b)与对应的第一哈希(206a至206f、302a至302f、404、504)相关联，所述方法特征在于，所述方法还包括使用概率方法，基于所述第二哈希(304a和304b、408a和408b、508a和508b)对应于多个第一哈希(206a至206f、302a至302f、404、504)的概率来确定所述第二哈希(304a和304b、408a和408b、508a和508b)。13.一种携带计算机指令的计算机可读介质，其特征在于，所述计算机指令当加载到内存控制器(102)中并由所述内存控制器(102)执行时使所述内存控制器(102)能够实现如权利要求12所述的方法。

技术总结
提供了一种内存控制器(102)，用于接收传入数据并利用重复数据删除存储和/或发送传入数据。内存控制器(102)确定对应于一个或多个第一哈希(206A至206F、302A至302F、404、504)的第二哈希(304A和304B、408A和408B、508A和508B)。第二哈希(304A和304B、408A和408B、508A和508B)是稀疏哈希，第一哈希(206A至206F、302A至302F、404、504)是强哈希。内存控制器(102)用第二哈希(304A和304B、408A和408B、508A和508B)填充稀疏索引(306)。稀疏索引(306)将第二哈希(304A和304B、408A和408B、508A和508B)与对应的第一哈希(206A至206F、302A至302F、404、504)相关联。内存控制器(102)使用概率方法，基于第二哈希(304A和304B、408A和408B、508A和508B)对应于多个第一哈希(206A至206F、302A至302F、404、504)的概率来确定第二哈希(304A和304B、408A和408B、508A和508B)。508A和508B)。508A和508B)。


技术研发人员：奥瓦德
受保护的技术使用者：华为技术有限公司
技术研发日：2021.03.09
技术公布日：2023/10/11