A technique for performing deduplication calculates a first fingerprint of a candidate block using a first function and a second fingerprint of the candidate block using a second function. The technique uses the first fingerprint to identify a target block, which is a potential match to the candidate block in the storage system. The technique then attempts to verify the potential match by accessing a fingerprint of the target block, which was previously calculated using the second function. The technique compares the fingerprint of the target block to the second fingerprint of the candidate block. A match between the two fingerprints confirms that the data of the candidate block matches the data of the target block. Storage of the candidate block can then be effectuated by reference to the target block.

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, also referred to herein as “nodes,” service storage requests arriving from host machines (“hosts”), which specify blocks, files, and/or other data elements to be written, read, created, deleted, and so forth. Software running on the nodes manages incoming storage requests and performs various data processing tasks to organize and secure the data elements on the non-volatile storage devices.

Many storage systems promote data reduction using deduplication. Deduplication is a technology that reduces the number of duplicate copies of data. A common deduplication scheme includes a digest database that associates hash values of data blocks with locations where those data blocks can be found. The hash values have sufficient uniqueness that a match between hash values computed from two blocks indicates a match between the two blocks themselves. When a storage system receives a new block for storage, the storage system may compute a hash value of the new block and perform a lookup for that hash value in the digest database. If a match is found, the storage system may conclude that the new block is already present. The storage system can then effectuate storage of the new block merely by setting a pointer from a logical address of the new block to a target block pointed to by the matching entry in the database. Storage of a duplicate copy of the data of the new block is therefore avoided.

SUMMARY

Some storage systems use fully cryptographic hash functions for deduplication. Such hash functions produce hash values with very high entropy, such that false matches between data blocks based on hash-value comparisons become a statistical impossibility. Such fully cryptographic hash functions are computationally intensive to execute, however. They also produce large hash values as results, such as values having sizes greater than 128 bits. Storing such large hash values on a per-block basis can consume considerable storage space.

To address these deficiencies, some storage systems use weaker hash functions that are easier to compute than fully cryptographic hash functions and produce smaller hash values (e.g., 64 bits or less). As it is not impossible for false-positives to occur with smaller hash values, a storage system may perform an additional step of verifying hash-based matches by comparing the data of blocks directly. For example, if a deduplication attempt on a candidate block produces a hash-based match to a target block, the storage system may confirm the match by performing a bit comparison between the candidate block and the target block. Unfortunately, bit comparisons require access to both the candidate block and the target block, however, and it is not always efficient or convenient to provide access to both. What is needed, therefore, is a deduplication solution that allows weaker hash functions to be used without requiring access to the data of blocks for bit comparisons.

To address the above need at least in part, an improved technique for performing deduplication uses at least two fingerprints instead of one. To perform deduplication on a candidate block, the improved technique calculates a first fingerprint of the candidate block using a first function and a second fingerprint of the candidate block using a second function. The technique uses the first fingerprint to identify a target block, which is a potential match to the candidate block in the storage system. The technique then attempts to verify the potential match by accessing a fingerprint of the target block, which was previously calculated using the second function. The technique compares the fingerprint of the target block to the second fingerprint of the candidate block. A match between the two fingerprints confirms that the data of the candidate block matches the data of the target block. Storage of the candidate block can then be effectuated by reference to the target block.

Advantageously, a match between the candidate block and the target block can be confirmed without having to access both blocks at the same time. Rather, matches can be confirmed based on fingerprints only. Also, use of the first fingerprint for identifying the potential target block enables the storage system to operate more efficiently than would be possible if larger fingerprints were used.

The improved technique is especially attractive when performing deduplication-enabled replication. In such arrangements, a source storage system identifies blocks to be replicated and sends fingerprints of those blocks to a destination storage system, which attempts to match the fingerprints with those of target blocks already stored at the destination. Providing both first and second fingerprints of blocks to be replicated enables the destination to find matches without requiring access to the blocks at the source. Replication can therefore proceed without the need to transmit blocks that are already present at the destination, increasing speed and reducing network traffic and congestion.

In some examples, a storage system uses the first fingerprint of a block (or a portion of the first fingerprint) as a checksum for that block, i.e., as a value for validating the data of the block. As checksums are useful regardless of deduplication, storing the first fingerprint or a portion thereof in a checksum means that less space is needed for storing fingerprints. Thus, the size of the checksum effectively subtracts from the space required for storing the first and second fingerprints. Also, calculating a checksum is a common task in a storage system. Basing the checksum on the first fingerprint, which itself is easy to calculate, thus ensures that the checksum is also easy to calculate. The storage advantages gained by basing the checksum on the first fingerprint do not impose a severe computational burden when it comes to calculating the checksum. It is noted that the computational burden would be more severe, however, if the checksum were instead based on a fully cryptographic hash function.

Certain embodiments are directed to a method of performing deduplication in a storage system. The method includes obtaining (i) a first fingerprint calculated from a candidate block using a first function and (ii) a second fingerprint calculated from the candidate block using a second function. The method further includes identifying a target block that the storage system associates with the first fingerprint and confirming that the target block matches the candidate block by (i) reading a fingerprint of the target block previously calculated using the second function and (ii) determining that the fingerprint of the target block matches the second fingerprint, the storage system then effectuating storage of the candidate block by reference to the target block.

Other embodiments are directed to a method of performing deduplication-enabled replication. The method includes calculating, by a source storage system (i) a first fingerprint of a candidate block using a first function and (ii) a second fingerprint of the candidate block using a second function. The method further includes sending, by the source storage system, the first fingerprint and the second fingerprint to a destination storage system, identifying, by the destination storage system, a target block that the destination storage system associates with the first fingerprint, and confirming, by the destination storage system, that the target block matches the candidate block by (i) reading a fingerprint of the target block previously calculated using the second function and (ii) determining that the fingerprint of the target block matches the second fingerprint, the destination storage system then effectuating storage of the candidate block by reference to the target block.

Other embodiments are directed to a computerized apparatus constructed and arranged to perform any of the methods described above. Still other embodiments are directed to a computer program product. The computer program product stores instructions which, when executed on control circuitry of a computerized apparatus, cause the computerized apparatus to perform any of the methods described above.

The foregoing summary is presented for illustrative purposes to assist the reader in readily grasping example features presented herein; however, this summary is not intended to set forth required elements or to limit embodiments hereof in any way. One should appreciate that the above-described features can be combined in any manner that makes technological sense, and that all such combinations are intended to be disclosed herein, regardless of whether such combinations are identified explicitly or not.

DETAILED DESCRIPTION

Embodiments of the improved technique will now be described. One should appreciate that such embodiments are provided by way of example to illustrate certain features and principles but are not intended to be limiting.

An improved technique for performing deduplication calculates a first fingerprint of a candidate block using a first function and a second fingerprint of the candidate block using a second function. The technique uses the first fingerprint to identify a target block, which is a potential match to the candidate block in the storage system. The technique then attempts to verify the potential match by accessing a fingerprint of the target block, which was previously calculated using the second function. The technique compares the fingerprint of the target block to the second fingerprint of the candidate block. A match between the two fingerprints confirms that the data of the candidate block matches the data of the target block. Storage of the candidate block can then be effectuated by reference to the target block.

FIG.1shows an example environment100in which embodiments of the improved technique can be practiced. Here, multiple hosts110are configured to access a data storage system116over a network114. The data storage system116includes one or more nodes120(e.g., node120aand node120b), and storage180, such as magnetic disk drives, electronic flash drives, and/or the like. Nodes120may be provided as circuit board assemblies or blades, which plug into a chassis (not shown) that encloses and cools the nodes. The chassis has a backplane or midplane for interconnecting the nodes120, and additional connections may be made among nodes120using cables. In some examples, the nodes120are part of a storage cluster, such as one which contains any number of storage appliances, where each appliance includes a pair of nodes120connected to shared storage. In some arrangements, a host application runs directly on the nodes120, such that separate host machines110need not be present. No particular hardware configuration is required, however, as any number of nodes120may be provided, including a single node, in any arrangement, and the node or nodes120can be any type or types of computing device capable of running software and processing host110's.

The network114may be any type of network or combination of networks, such as a storage area network (SAN), a local area network (LAN), a wide area network (WAN), the Internet, and/or some other type of network or combination of networks, for example. In cases where hosts110are provided, such hosts110may connect to the node120using various technologies, such as Fibre Channel, iSCSI (Internet small computer system interface), NVMeOF (Nonvolatile Memory Express (NVMe) over Fabrics), NFS (network file system), and CIFS (common Internet file system), for example. As is known, Fibre Channel, iSCSI, and NVMeOF are block-based protocols, whereas NFS and CIFS are file-based protocols. The node120is configured to receive I/O requests112according to block-based and/or file-based protocols and to respond to such I/O requests112by reading or writing the storage180.

The depiction of node120ais intended to be representative of all nodes120. As shown, node120aincludes one or more communication interfaces122, a set of processors124, and memory130. The communication interfaces122include, for example, SCSI target adapters and/or network interface adapters for converting electronic and/or optical signals received over the network114to electronic form for use by the node120a. The set of processors124includes one or more processing chips and/or assemblies, such as numerous multi-core CPUs (central processing units). The memory130includes both volatile memory, e.g., RAM (Random Access Memory), and non-volatile memory, such as one or more ROMs (Read-Only Memories), disk drives, solid state drives, and the like. The set of processors124and the memory130together form control circuitry, which is constructed and arranged to carry out various methods and functions as described herein. Also, the memory130includes a variety of software constructs realized in the form of executable instructions. When the executable instructions are run by the set of processors124, the set of processors124is made to carry out the operations of the software constructs. Although certain software constructs are specifically shown and described, it is understood that the memory130typically includes many other software components, which are not shown, such as an operating system, various applications, processes, and daemons.

As further shown inFIG.1, the memory130“includes,” i.e., realizes by execution of software instructions, a deduplication facility140, a replication facility150, a data path160, and any number of data objects170. The data objects170may be any type or types of objects, such as LUNs (Logical UNits), file systems, virtual machine disks, and/or the like. The data objects170may be composed of blocks, where a “block” is a unit of allocatable storage space. Blocks are typically uniform in size, with typical block sizes being 4 kB (kilo Bytes), 8 kB, or 16 kB, for example. No particular block size is required, however, and embodiments may support non-uniform block sizes. The data storage system116is configured to access the data objects170by specifying blocks of the data objects to be created, read, updated, or deleted.

Deduplication facility140is configured to perform data deduplication based on both first fingerprints and second fingerprints. Deduplication may be performed in an inline or near-inline manner, using fingerprint-based matching in which duplicate copies are avoided prior to being written to persistent data-object structures. In some examples, deduplication may also be performed in the background, i.e., out of band with the initial processing of incoming writes. Deduplication is sometimes abbreviated as “dedupe.” In some examples, the deduplication facility140includes or otherwise has access to a digest database142, which associates first fingerprints260of data blocks with respective locations of those data blocks in the storage system116.

Replication facility150is configured to perform replication on data objects170. Typically, replication is performed between two data storage systems, with one storage system designated as a “source” and the other storage system designated as a “destination.” The source is the data storage system that “hosts” a data object, i.e., makes the data object available to hosts110for reading and/or writing, whereas the destination is the data storage system that maintains a “replica” of the data object, i.e., a copy of the data object that is current or nearly current. In an example, replication facility150is configured to perform asynchronous replication, also known as “snapshot shipping.” Asynchronous replication works by taking regular snapshots of a data object on a specified schedule, such as once every five minutes, once every hour, or at some other rate, which is typically defined by an administrator. Each time a new snapshot of the data object is taken, the replication facility150computes a deltaset, i.e., a set of changes or differences between blocks of the new snapshot and blocks of the immediately previous snapshot. The replication facility150then transmits (“ships”) the deltaset to the destination, which applies the deltaset in updating the replica. Once the update is complete, the contents of the replica are identical to those of the data object as of the most recent snapshot taken at the source.

Data path160is configured to provide metadata for accessing data objects, such as data objects170. As described in more detail below, data path160may include various logical blocks, mapping pointers, and block virtualization structures, some of which may track various attributes of blocks.

As further shown inFIG.1, the data storage system116may include a persistent storage region, such as a hash tier190, which is configured to store certain fingerprint data used for deduplication and/or replication. In an example, the hash tier190is formed using one or more high-speed, non-volatile storage devices (e.g., flash drives), such that the nodes120are able to access fingerprint data from storage180at high speed. As described more fully below, the hash tier190is configured to store second fingerprints290of data blocks, which are available as target blocks for deduplication. In some examples, the hash tier190is further configured to store portions of first fingerprints260of data blocks, with other portions of first fingerprints260stored in checksums associated with the data blocks.

In example operation, hosts110issue I/O requests112to the data storage system116. A node120receives the I/O requests112at the communication interfaces122and initiates further processing. Such processing may include performing deduplication and/or replication. Deduplication employs both first fingerprints260and second fingerprints290. For example, both a first fingerprint260and a second fingerprint290may be calculated from a candidate block received for storage. The first fingerprint260is used to match the candidate block to a potential target block, and the second fingerprint290is used to confirm that the match based on the first fingerprint260is proper.

Replication as described herein may leverage deduplication using both first and second fingerprints. For example, to replicate a data block of a data object170from the data storage system116acting as a source to another data storage system acting as a destination, the data storage system116may send the first and second fingerprints calculated from the data block along with an LBA (logical block address) of the data block in the data object170. The data block itself is not sent, however. Upon receiving the fingerprints and LBA, the destination may use the first and second fingerprints to perform inline deduplication, attempting to use the fingerprints to identify a matching target block already stored in the destination. If a match is found, the destination may update a replica of the data object to point to the target block at the indicated LBA. If a matching block cannot be found, then the destination may request and obtain the data block from the source.

The data storage system116may also act as a replication destination. For example, a node120may receive a transmission from another data storage system (a source). The transmission may include first and second fingerprints of a block and an LBA of the block being replicated. The block itself is not included, however. Upon receiving the transmission, the data storage system116attempts inline deduplication using the first and second fingerprints. Here, deduplication operates the same way as described above, except that the first and second fingerprints are received rather than calculated. Also, such fingerprints are based on a block that is not necessarily present. If a match to the block is found, the data storage system116may update a replica at the specified LBA, again, without ever receiving the block from the source.

FIG.2shows an example of the data path160in greater detail. The data path160provides an arrangement of metadata in the form of metadata elements, such as pointers, which may be traversed for locating data in the data storage system116and for supporting deduplication. As shown, the data path160includes a namespace210, a mapping structure (“mapper”)220, and a physical block layer230. The namespace210is configured to organize logical data, such as data of LUNs (volumes), file systems, virtual machine disks, snapshots, clones, and/or the like. In an example, the namespace210provides a large logical address space and is denominated in logical blocks212having associated logical addresses214.

The mapper220is configured to map logical blocks212in the namespace210to corresponding physical blocks232in the physical block layer230. The physical blocks232are normally compressed and may thus have non-uniform size. The mapper320may include multiple levels of mapping structures, such as pointers, which are arranged in a tree. The levels include tops222, mids224, and leaves226, which together are capable of mapping large amounts of data. The mapper220may also include a layer of virtuals228, i.e., block virtualization structures for providing indirection between the leaves226and physical blocks232, thus enabling physical blocks232to be moved without disturbing leaves226. Although the tops222, mids224, leaves226, and virtuals228depict individual pointer structures, such pointer structures may be grouped together in arrays (not shown), which themselves may be stored in blocks.

In general, logical blocks212in the namespace210point to respective physical blocks232in the physical block layer230via mapping structures in the mapper220. For example, a logical block212tin the namespace210may point, via a path216, to a particular top222t, which points to a particular mid224t, which points to a particular leaf226t. The leaf226tpoints to a particular virtual228t, which points to a particular physical block232t. In this manner, the data corresponding to logical block212tmay be found by following the pointers through the mapper to the data232t.

FIG.2further shows an example virtual228in greater detail. Here, the virtual228is a metadata element that includes a pointer240to the data (e.g., to block232a) as well as a checksum250and a virtual address270. In an example, the checksum250is based on a first fingerprint260of the data of logical block212t. For instance, the first fingerprint260may be calculated from the block212tusing a first function (e.g., a hash function), and the checksum250may be the entirety of the first fingerprint260or a portion thereof, e.g., some number of bits of the first fingerprint260.

The virtual address270is an address of the virtual228, such as an address in a virtual tier (not shown) or some other address associated with the block212t. The virtual address270may be stored explicitly (as a value in the virtual228), or it may be implied based on a location of the virtual228, e.g., a location in the virtual tier. In an example, the virtual address270directly implies a corresponding location in the hash tier190of a second fingerprint290calculated from the block212t. The second fingerprint290may be calculated, for example, using a second function (e.g., a different hash function). In an example, the location of the second fingerprint290may be calculated mathematically from the virtual address270. Thus, the second fingerprint290may be obtained from the hash tier190directly based on the virtual228, without the need for any additional data access.

One should appreciate that the virtual228may include other metadata besides that shown, such as a reference count, a compressed size of the pointed-to physical block, and the like. In addition, some embodiments may exclude the checksum250and/or the virtual address270. The virtual228as shown is thus intended to be illustrative rather than limiting.

FIG.2further shows an example arrangement for supporting deduplication. For instance, a candidate block212cmay be deduplicated by reference to the above-mentioned block212t, which is designated here as a target block. As shown, logical block212chas its own path218through the mapper220, but the leaf226cin the path218points to the virtual228t, the same virtual that was in path216. Thus, deduplication can be achieved at the leaf level by pointing different blocks to the same virtual228. For example, storage of the candidate block212ccan be effectuated by reference to the target block212t, e.g., by establishing a pointer in the leaf226cso that it points to the virtual228t.

FIG.3shows an example arrangement for generating fingerprints260and290from a candidate block212c. Here, a first function310receives the candidate block212cas input and generates the first fingerprint260as output. The first function may include a hash function312and an optional function316(which may be omitted in some embodiments). In an example, the hash function312is an efficient hash function, which is less burdensome to execute than a fully cryptographic hash function and which produces smaller results. As a non-limiting example, the hash function312may be configured to produce 64-bit hash values314. Such hash values314may be used for deduplication, but they are not immune to hash collisions. Optional function316modifies the hash values314, e.g., by truncating such values (e.g., to 56 bits) to support more efficient computations.

As described above, first fingerprints260are used to identify potential target blocks during deduplication. For example, the deduplication facility140performs hash-based lookups into the digest database142using first fingerprints260.

The first fingerprints260may each include two portions260aand260b. The first portion260amay provide a checksum of the candidate block212c. For example, the checksum may be formed from a defined set of bits of the first fingerprint260, or from the entire first fingerprint260. The checksum for a block may be stored as the checksum250in the virtual228associated with that block (FIG.2), for example. At any point during system operations, the storage system may perform data validation on the block by executing the first function310on the block and by forming a checksum based on the defined set of bits. The storage system116may then compare the calculated checksum with the checksum250already stored for the same block in the virtual228. A match indicates valid data; a mismatch indicates corruption.

The second portion260bof the first fingerprint260may include additional bits. These additional bits are simply those bits of the first fingerprint260that are not required for the checksum. For example, the checksum may have an optimal size, and anything larger than that size may be excluded from the checksum for best performance. In an example, the additional bits are stored along with corresponding second fingerprints290in the hash tier190.

As further shown inFIG.3, the candidate block212cmay be processed by a second function320for generating the second fingerprint290as output. The second function320includes a hash function322, which produces a second hash value324, and an optional function326. In an example, the hash function322is a strong hash function, stronger than the hash function312used to create the first fingerprint260. Nonlimiting examples of the hash function322include the well-known SHA-1 and SHA-2 functions. The hash function322may be more burdensome to compute than the hash function312, but it is computed less often and is not needed for generating a checksum.

In an example, the storage system116does not require the full size of the second hash value324to guarantee collision-free deduplication. Rather, the needed number of bits of the second hash value324is only that number which, when combined with the number of bits in the first fingerprint260, provides sufficient entropy to guarantee no collisions across the maximum expected number of blocks in the storage system116. If we assume that this maximum number is 1012, then the probability of a hash collision statistically approaches zero with a total of 171 bits. If we assume that the size of the first fingerprint260is 56 bits, that leaves 115 bits as the optimal size of the second fingerprint290. Thus, function326may truncate the second hash value324to 115 bits without risking hash collisions. As indicated above, the second fingerprint290may be stored in the hash tier190, e.g., at a location that can be calculated based on the virtual address270(FIG.2).

In an example, the storage system116calculates both the first fingerprint260and the second fingerprint290upon data ingest, e.g., when first receiving a candidate block for storage. For example, the storage system116calculates the first and second fingerprints while performing a memory copy of the candidate block from kernel buffers to cache. In this manner, fingerprints may be calculated when calculations are unlikely to cause substantial additional delays.

FIG.4shows an example method400of performing deduplication in the environment ofFIG.1. The acts of method400are typically performed by the deduplication facility140and may be carried out in any suitable order, including performing some acts simultaneously.

At410, the deduplication facility140obtains first and second fingerprints260and290of a candidate block212c. The deduplication facility140may calculate the fingerprints in the case of local deduplication, or it may receive the fingerprints from a replication source in the case of replication. The deduplication facility140searches the digest database142using the first fingerprint260as a key, i.e., in an attempt to find a target block212twith a matching first fingerprint.

At420, if a match to a target block212tis found, then operation proceeds to430, whereupon the deduplication facility140retrieves a second fingerprint290of the matching target block212t, e.g., from the hash tier190. For example, the matching entry in the digest database142includes a pointer to the virtual228tof the target block212t(FIG.2). The virtual228stores or otherwise indicates a virtual address270, which implies the location of the second fingerprint290in the hash tier190, e.g., based on a predetermined mathematical relationship.

At440, the deduplication facility140compares the second fingerprint290(retrieved at430) of the target block212twith the second fingerprint290of the candidate block212c.

At450, if the two second fingerprints match, then the target block212tis confirmed to be a match to the candidate block212cand deduplication can proceed.

At460, the storage system effectuates storage of the candidate block212cby reference to the target block212t, e.g., by configuring a pointer in leaf226c(FIG.2) to point to the virtual of the target block212t, i.e., virtual228t. Effective storage of the candidate block212cis thus achieved without having to separately store the data of the candidate block212c. Redundant storage is therefore avoided.

If the attempt at deduplication fails, either at420or at450, then operation proceeds to470, whereupon the data of the candidate block212cis stored, e.g., in a newly allocated physical block232. At480, the storage system identifies or otherwise determines a checksum of the candidate block212cfrom the first fingerprint260(as shown inFIG.3). The storage system also updates a virtual228of the candidate block212cto store the determined checksum as checksum250. At490, the storage system stores the second fingerprint290of the candidate block212cin the hash tier190, e.g., at a location implied by the virtual address270of the virtual228associated with the candidate block212c. Any additional bits of the first fingerprint260(portion260b) of the candidate block212cmay be stored at the same location. Also, at or around this time, the deduplication facility140may update the digest database142to include a new entry for the candidate block212c. For example, the new entry associates the first fingerprint260of the candidate block212cwith a pointer to the virtual228of the candidate block212c.

FIG.5shows an example arrangement for performing replication facilitated by fingerprints260and290. As shown, a source storage system116aand a destination storage system116bare configured to perform replication of a data object510s(e.g., a volume) on the source116aby maintaining a replica510dof that data object at the destination116b. Replication proceeds based on snapshots (point-in-time versions) of the volume510s. For example, a first snapshot (Snap 1) of volume510sis taken at a first point in time and a second snapshot (Snap 2) of the same volume510sis taken at a second point in time, which is later than the first point in time. As the volume510smay be a live, production data object, it is expected that Snap 2 differs from Snap 1, with the difference reflecting changes in the volume510sbetween the first point in time and the second point in time. To capture this difference, the source116agenerates a deltaset520, which identifies blocks found in Snap 2 but not in Snap 1. Here, such blocks are identified by listing, for each block, a first fingerprint260of the block, a second fingerprint290of the block, and an LBA of the block, e.g., a logical address of the block within the volume510c. The deltaset520may list many blocks, but it does not include the data of such blocks.

As shown by arrow530, the source116asends the deltaset to the destination116b. At540, the destination116breceives the deltaset520and treats the blocks identified therein as candidate blocks for deduplication.

At550, the destination116battempts to deduplicate the candidate blocks, e.g., in the same manner as shown inFIG.4, by using the first and second fingerprints provided in the deltaset520. If a candidate block is successfully deduplicated, storage of the candidate block in the replica510dmay be effectuated by associating the LBA received for that block (as represented in the replica510d) with a target block identified during deduplication. Thus, the candidate block may be stored without having to transfer the data of the candidate block from source116ato destination116b.

Some candidate blocks listed in the deltaset520may be missing at the destination116b. At560, the destination116bidentifies the missing blocks, i.e., the candidate blocks for which no target blocks are found, and sends a request for the missing blocks to the source116a.

At570, the source116aresponds to the request by sending compressed versions of the missing blocks and their associated LBAs to the destination116b. At580, the destination116breceives the missing blocks and stores them at the specified LBAs in the replica510d.

Replication may proceed over time in this manner, by taking additional snapshots of volume510s, identifying deltasets520between new snapshots and their immediate predecessors, and sending the deltasets520to the destination116b, where the above-described activities are repeated. In this manner, the replica510dis kept current with the volume510sover time.

FIG.6shows an example method600that may be carried out in connection with the environment100and provides a review of some of the features described above. The method600is typically performed, for example, by the software constructs described in connection withFIG.1, which reside in the memory130of a node120and are run by the set of processors124. The various acts of method600may be ordered in any suitable way.

At610, a storage system116obtains both (i) a first fingerprint260calculated from a candidate block212cusing a first function310and (ii) a second fingerprint290calculated from the candidate block212cusing a second function320. Fingerprints260and290may be calculated locally, e.g., in the case of local deduplication, or they may be received from another storage system, e.g., in the case of replication.

At620, the storage system116identifies a target block212tthat the storage system associates with the first fingerprint260. For example, the storage system116performs a lookup into the digest database142using the first fingerprint260as a key. The lookup may yield a match to an entry in the digest database142that indicates a target block212t, e.g., by specifying a pointer to a virtual228associated with the target block212t.

At630, the storage system116confirms that the target block212tmatches the candidate block212cby (i) reading a fingerprint of the target block212tpreviously calculated using the second function320and (ii) determining that the fingerprint of the target block212tmatches the second fingerprint290of the candidate block212c. The storage system116then effectuates storage of the candidate block212cby reference to the target block212t, e.g., by pointing the candidate block212cto a virtual228tof the target block212t.

An improved technique has been described for performing deduplication on a candidate block212c. The technique calculates a first fingerprint260of the candidate block212cusing a first function310and a second fingerprint290of the candidate block212cusing a second function320. The technique uses the first fingerprint260to identify a target block212t, which is a potential match to the candidate block212cin the storage system116. The technique then attempts to verify the potential match by accessing a fingerprint of the target block212t, which was previously calculated using the second function320. The technique compares the fingerprint of the target block212tto the second fingerprint290of the candidate block212t. A match between the two fingerprints confirms that the data of the candidate block212cmatches the data of the target block212t. Storage of the candidate block212ccan then be effectuated by reference to the target block.

Having described certain embodiments, numerous alternative embodiments or variations can be made. For example, although embodiments have been described that involve one or more data storage systems, other embodiments may involve computers, including those not normally regarded as data storage systems. Such computers may include servers, such as those used in data centers and enterprises, as well as general purpose computers, personal computers, and numerous devices, such as smart phones, tablet computers, personal data assistants, and the like.

Further, although features have been shown and described with reference to particular embodiments hereof, such features may be included and hereby are included in any of the disclosed embodiments and their variants. Thus, it is understood that features disclosed in connection with any embodiment are included in any other embodiment.

Further still, the improvement or portions thereof may be embodied as a computer program product including one or more non-transient, computer-readable storage media, such as a magnetic disk, magnetic tape, compact disk, DVD, optical disk, flash drive, solid state drive, SD (Secure Digital) chip or device, Application Specific Integrated Circuit (ASIC), Field Programmable Gate Array (FPGA), and/or the like (shown by way of example as medium650inFIG.6). Any number of computer-readable media may be used. The media may be encoded with instructions which, when executed on one or more computers or other processors, perform the process or processes described herein. Such media may be considered articles of manufacture or machines and may be transportable from one machine to another.

As used throughout this document, the words “comprising,” “including,” “containing,” and “having” are intended to set forth certain items, steps, elements, or aspects of something in an open-ended fashion. Also, as used herein and unless a specific statement is made to the contrary, the word “set” means one or more of something. This is the case regardless of whether the phrase “set of” is followed by a singular or plural object and regardless of whether it is conjugated with a singular or plural verb. Also, a “set of” elements can describe fewer than all elements present. Thus, there may be additional elements of the same kind that are not part of the set. Further, ordinal expressions, such as “first,” “second,” “third,” and so on, may be used as adjectives herein for identification purposes. Unless specifically indicated, these ordinal expressions are not intended to imply any ordering or sequence. Thus, for example, a “second” event may take place before or after a “first event,” or even if no first event ever occurs. In addition, an identification herein of a particular element, feature, or act as being a “first” such element, feature, or act should not be construed as requiring that there must also be a “second” or other such element, feature or act. Rather, the “first” item may be the only one. Also, and unless specifically stated to the contrary, “based on” is intended to be nonexclusive. Thus, “based on” should be interpreted as meaning “based at least in part on” unless specifically indicated otherwise. Although certain embodiments are disclosed herein, it is understood that these are provided by way of example only and should not be construed as limiting.