BACKGROUND

Data storage systems are arrangements of hardware and software in which storage processors are coupled to arrays of non-volatile storage devices, such as magnetic disk drives, electronic flash drives, and/or optical drives. The storage processors service storage requests arriving from host machines (“hosts”), which specify blocks, files, and/or other data elements to be written, read, created, deleted, etc. Software running on the storage processors manages incoming storage requests and performs various data processing tasks to organize and secure the data elements on the non-volatile storage devices.

Some storage systems support data “deduplication.” A common deduplication scheme involves replacing redundant copies of a data block with pointers to a single retained copy. Such schemes may involve computing digests of data blocks and storing the digests in a database. Each digest is computed as a hash of a data block's contents and identifies the data block with a high level of uniqueness, even though the digest is typically much smaller than the data block itself. Digests thus enable block matching to proceed quickly and efficiently, without having to compare blocks byte-by-byte. For each digest, the database stores a pointer that leads to a stored version of the respective data block. To perform deduplication on a particular candidate block, a storage system computes a digest of the candidate block and searches the database for an entry that matches the computed digest. If a match is found, the storage system arranges metadata of the candidate block to point to the data block that the database has associated with the matching digest. In this manner, a duplicate copy of the data block is avoided.

SUMMARY

Unfortunately, conventional deduplication schemes fail to detect redundant data when blocks are similar but not identical or when redundant data is not aligned to block boundaries. For example, a data storage system might store multiple copies of a given block, which are identical except for a timestamp or label. Owing to the randomizing nature of the hash function, digests computed from the nearly identical copies of the data block differ widely from one another, such that deduplication is unable to detect the redundant content. Many opportunities to improve storage efficiency are therefore missed.

In contrast with prior approaches, improved techniques for performing data deduplication operate at sub-block granularity by selecting a representative sub-block from a candidate block and hashing that representative sub-block to form a digest. The techniques then involve searching a deduplication database for a match between the digest computed from the representative sub-block and a target digest stored in the database. The target digest was previously computed by hashing a target sub-block of a previously-stored target block. When a match is found, the techniques may identify a duplicate range shared between the candidate block and the target block and logically effect persistent storage of the duplicate range. In some embodiments, this is accomplished by configuring mapping metadata of the candidate block so that it points to the duplicate range in the target block.

Advantageously, the improved techniques avoid redundant storage of identical portions of data within blocks, even when the data blocks as a whole are different. Storage efficiency is thereby improved.

In one embodiment, a method of performing deduplication is provided. The method includes (a) selecting, by applying a deterministic selection criterion, a sub-block of a block of data that contains multiple sub-blocks; (b) performing a lookup, into a deduplication table, of a digest generated by hashing the selected sub-block, the lookup matching an entry indexed by the digest in the deduplication table, the entry identifying a previously processed block; and (c) effecting storage of the block, including pointing to the previously processed block. An apparatus, system, and computer program product for performing a similar method are also provided.

The foregoing summary is presented for illustrative purposes to assist the reader in readily grasping example features presented herein. However, the foregoing summary is not intended to set forth required elements or to limit embodiments hereof in any way.

