公开(公告)号：US09720928B2

公开(公告)日：2017-08-01

申请号：US14518403

申请日：2014-10-20

Applicant: NetApp, Inc.

Inventor： Rohini Raghuwanshi ,  Ashish Shukla ,  Praveen Killamsetti

IPC: G06F17/30 ,  G06F11/10 ,  G06F11/14

CPC classification number: G06F17/30156 ,  G06F11/1004 ,  G06F11/1453 ,  G06F17/30088 ,  G06F17/30091 ,  G06F17/30159

Abstract: A system can efficiently removes ranges of entries from a flat sorted data structure that represent stale fingerprints As part of fingerprint verification during deduplication, the system performs an attributes intersect range calculation (AIRC) procedure on the stale fingerprint data structure to compute a set of non-overlapping and latest consistency point (CP) ranges. During the AIRC procedure, an inode associated with a data container is selected and the FBN tuple of each deleted data block in the file is sorted in a predefined FBN order. The AIRC procedure then identifies the most recent fingerprint associated with a deleted data block. The set of non-overlapping and latest CP ranges is then used to remove stale fingerprints associated with that deleted block from the fingerprint database. A single pass through the fingerprint database identifies the set of non-overlapping and latest CP ranges, thereby improving efficiency of the storage system.

公开(公告)号：US20150039572A1

公开(公告)日：2015-02-05

申请号：US14518403

申请日：2014-10-20

Applicant: NetApp, Inc.

Inventor： Rohini Raghuwanshi ,  Ashish Shukla ,  Praveen Killamsetti

IPC: G06F17/30 ,  G06F11/10 ,  G06F11/14

CPC classification number: G06F17/30156 ,  G06F11/1004 ,  G06F11/1453 ,  G06F17/30088 ,  G06F17/30091 ,  G06F17/30159

Abstract: A system and method efficiently removes ranges of entries from a flat sorted data structure, such as a fingerprint database, of a storage system. The ranges of entries represent fingerprints that have become stale, i.e., are not representative of current states of corresponding blocks in the file system, due to various file system operations such as, e.g., deletion of a data block without overwriting its contents. A deduplication module of a file system executing on the storage system performs a fingerprint verification procedure to remove the stale fingerprints from the fingerprint database. As part of the fingerprint verification procedure, the deduplication module performs an attributes intersect range calculation (AIRC) procedure on the stale fingerprint data structure to compute a set of non-overlapping and latest consistency point (CP) ranges. During the AIRC procedure, an inode associated with a data container, e.g., a file, is selected and the FBN tuple of each deleted data block in the file is sorted in a predefined, e.g., increasing, FBN order. The AIRC procedure then identifies the most recent fingerprint associated with a deleted data block. The output from the AIRC procedure, i.e., the set of non-overlapping and latest CP ranges, is then used to remove stale fingerprints associated with that deleted block (as well as each other deleted data block) from the fingerprint database. Notably, only a single pass through the fingerprint database is required to identify the set of non-overlapping and latest CP ranges, thereby improving efficiency of the storage system.

Abstract translation: 系统和方法有效地从存储系统的平坦排序的数据结构（诸如指纹数据库）中去除条目的范围。 条目的范围表示由于各种文件系统操作，例如删除数据块而不覆盖其内容，已经变得陈旧的指纹，即不代表文件系统中对应的块的当前状态。 在存储系统上执行的文件系统的重复数据删除模块执行指纹验证过程以从指纹数据库中移除陈旧的指纹。 作为指纹验证过程的一部分，重复数据消除模块在陈旧的指纹数据结构上执行属性相交范围计算（AIRC）过程，以计算一组非重叠和最新的一致性点（CP）范围。 在AIRC过程期间，选择与数据容器（例如文件）相关联的inode，并且以预定义的例如增加的FBN顺序对文件中每个被删除的数据块的FBN元组进行排序。 然后，AIRC过程识别与删除的数据块相关联的最新指纹。 然后使用来自AIRC过程的输出，即一组非重叠和最新的CP范围，以从指纹数据库中删除与该删除的块（以及每个其他已删除的数据块）相关联的陈旧的指纹。 值得注意的是，仅需要一次通过指纹数据库来识别一组不重叠和最新的CP范围，从而提高存储系统的效率。