USING LOGICAL BLOCK ADDRESSES WITH GENERATION NUMBERS AS DATA FINGERPRINTS FOR NETWORK DEDUPLICATION

• US 20130332558A1
• Filed: 08/12/2013
• Published: 12/12/2013
• Est. Priority Date: 10/30/2009
• Status: Active Grant

• Current Assignee: NetApp, Inc.
• Original Assignee: NetApp, Inc.
• Inventors: Condict, Michael N., Kleiman, Steven R.
• Granted Patent: US 9,043,430 B2
• Time in Patent Office: Days
• US Class Current: 709/214
• CPC Class Codes: G06F 12/0813 with a network or matrix configuration
• CPC Class Codes: G06F 12/0815 Cache consistency protocols
• CPC Class Codes: G06F 2206/1014 One time programmable [OTP] memory, e.g. PROM, WORM
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/0641 De-duplication techniques
• CPC Class Codes: G06F 3/065 Replication mechanisms
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• CPC Class Codes: G06F 3/0679 Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]
• CPC Class Codes: H04L 49/9063 Intermediate storage in different physical parts of a node or terminal
• CPC Class Codes: H04L 67/1095 Replication or mirroring of data, e.g. scheduling or transport for data synchronisation between network nodes
• CPC Class Codes: H04L 67/1097 for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS]
• CPC Class Codes: H04L 67/568 Storing data temporarily at an intermediate stage, e.g. caching
• CPC Class Codes: H04L 69/04 Protocols for data compression, e.g. ROHC

Abstract

The technique introduced here involves using a block address and a corresponding generation number as a “fingerprint” to uniquely identify a sequence of data within a given storage domain. Each block address has an associated generation number which indicates the number of times that data at that block address has been modified. This technique can be employed, for example, to determine whether a given storage server already has the data, and to avoid sending the data to that storage server over a network if it already has the data. It can also be employed to maintain cache coherency among multiple storage nodes.

Claims

1. A method, comprising:

receiving, at a destination device, a write request identifying a source block address and a generation number, wherein a source device stores data associated with the write request at the source block address, the generation number indicating a number of times that data at the source block address has been modified;

determining whether the destination device already has a data block that matches the source block address and the generation number; and

processing, at the destination device, the write request by using the data block that matches the source block address and the generation number, without receiving the data associated with the write request from the source device, when it is determined that the destination device already has the data block that matches the source block address and the generation number.

2. The method of claim 1, further comprising:

processing, at the destination device, the write request by requesting the data associated with the write request from the source device, when it is determined that the destination device does not have a data block that matches the source block address and the generation number.

3. The method of claim 1, wherein the step of processing comprising:

copying from a data block at the destination device that matches the source block address and the generation number after determining that the destination device already has the data block that matches the source block address and the generation number.

4. The method of claim 1, wherein the destination device is configured to have permission to modify the data block.

5. The method of claim 1, wherein the source device and destination device communicate over a network.

6. The method of claim 1, wherein the source device is a caching device and the destination device is an origin server for content cached by the caching device.

7. The method of claim 1, wherein the destination device is a storage server and the source device is a client of the storage server.

8. The method of claim 1, wherein the source device is a first storage server and the destination device is a second storage server configured to mirror data stored by the first storage server.

9. A method, comprising:

determining, at a source device, that a data block stored by a source device should be stored by a destination device, wherein the source device and destination device communicate over a network;

Identifying, at the source device, a source block address of the data block and a generation number of the block address, the generation number indicating a number of times that data at the block address has been modified;

Sending, from the source device to the destination device, the source block address and the generation number of the data block; and

Receiving, from the destination device, an instruction not to send the data block because the destination device already has a data block that matches the source block address and the generation number.

10. The method of claim 9, wherein the destination device is configured to have permission to modify the data block.

11. The method of claim 9, wherein the source device is a caching device and the destination device is an origin server for content cached by the caching device.

12. The method of claim 9, wherein the destination device is a storage server and the source device is a client of the storage server.

13. The method of claim 9, wherein the source device is a first storage server and the destination device is a second storage server configured to mirror data stored by the first storage server.

14. A storage server, comprising:

a network interface through which to communicate over a network;

a storage interface through which to communicate with a non-volatile mass storage device;

a receiving component configured to receive, via the network interface, a write request including a source block address and a generation number, wherein a source device stores data associated with the write request at the source block address, and the generation number indicates a number of times that data at the source block address has been modified;

a determining component configured to determine whether storage server already has a data block that matches the source block address and the generation number; and

a processing component configured to process the write request by copying the data block that matches the source block address and the generation number to a data block in the non-volatile mass storage device via the storage interface, without receiving the data associated with the write request from the source device, if the storage server already has the data block that matches the source block address and the generation number.

15. The storage server of claim 14, wherein the storage server is configured to have permission to modify the data block.

16. The storage server of claim 14, wherein the source block address and the generation number uniquely identify the data at the source block address within the source device.

17. The storage server of claim 14, further comprising:

an incrementing component configured to increment a generation number of a block address each time the data at the block address is modified.

18. The storage server of claim 14, wherein the determining component is configured to determine whether storage server already has a data block that matches the source block address and the generation number by performing a lookup in a metadata index containing generations numbers associated with blocks addresses of the non-volatile mass storage device.

19. The storage server of claim 14, wherein the processing component is further configured to process the write request by requesting the data associated with the write request from the source device, if the storage server does not have a data block that matches the source block address and the generation number.

20. The storage server of claim 14, wherein the storage server is a network caching device and the destination device is an origin server for content cached by the storage server.