Using logical block addresses with generation numbers as data fingerprints for network deduplication

• US 8,799,367 B1
• Filed: 10/30/2009
• Issued: 08/05/2014
• Est. Priority Date: 10/30/2009
• Status: Active Grant

• Current Assignee: NetApp, Inc.
• Original Assignee: NetApp, Inc.
• Inventors: Condict, Michael N., Kleiman, Steven R.
• Primary Examiner(s): DOAN, DUYEN MY
• Application Number:
  US12/610,231
• Time in Patent Office: 1,740 Days
• Field of Search: 709/205, 711/141, 711/217, 707/624, 707/626, 707635-637
• US Class Current: 709/205
• 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:

determining that a first data block stored by a source device has been modified, that the first data block has the same content as a second data block on the source device, and that the first data block should be updated by a destination device;

determining a block address of the second data block and a generation number of the block address, the generation number indicative of a number of times which data at the block address has been modified; and

using the block address and the generation number to determine whether the destination device already has a data block that matches the block address and the generation number and to avoid sending the first data block to the destination device after determining that the destination device already has a data block that matches the block address and the generation number.

2. A method as recited in claim 1, wherein determining that a first data block stored by a source device should be updated by a destination device is performed in the source device;

the method further comprising;

sending the block address and the generation number of the second data block from the source device to the destination device; and

wherein using the block address and the generation number to determine whether the destination device already has a data block that matches the block address and the generation number is performed in the destination device.

3. A method as recited in claim 2, further comprising:

when destination device does not have a data block that matches the block address and the generation number, then requesting the source device to send the data block that matches the block address and the generation number to the destination device.

4. A method as recited in claim 1, wherein the source device and destination device are coupled to communicate over a network.

5. A method as recited in 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.

6. A method as recited in claim 1, wherein the destination device is a storage server and the source device is a client of the storage server.

7. A method as recited in 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.

18. A method as recited in claim 1, further comprising:

updating the first data block on the destination device by copying from a data block on the destination device that matches the block address and the generation number after determining that the destination device already has the data block that matches the block address and the generation number.

8. A method comprising:

determining in a source device that a first data block stored by a source device has been modified, that the first data block has the same content as a second data block on the source device, and that the first data block should be updated by a destination device, wherein the source device and destination device are coupled to communicate over a network;

determining in the source device a block address of the second data block and a generation number of the block address, the generation number indicative of a number of times which data at the block address has been modified;

sending the block address and the generation number of the second data block from the source device to the destination device; and

using the block address and the generation number to determine in the destination device whether the destination device already has a data block that matches the block address and the generation number and to avoid sending the data block to the destination device when it is determined that the destination device already has a data block that matches the block address and the generation number.

9. A method as recited in claim 8, wherein the source device is a caching device and the destination device is are origin server for content cached by the caching device.

10. A method as recited in claim 8, wherein the destination device is a storage server and the source device is a client of the storage server.

11. A method as recited in claim 8, 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.

19. A method as recited in claim 8, further comprising:

updating the first data block on the destination device by copying from a data block on the destination device that matches the block address and the generation number after determining that the destination device already has the data block that matches the block address and the generation number.

12. 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;

a processor coupled to the network interface and the storage interface;

a memory storing code which configures the processor to cause the storage server to perform a communication process that includes

determining that a first data block stored by a source device has been modified, that the first data block has the same content as a second data block on the source device, and that the first data block should be updated by a destination device;

determining a block address of the second data block and a generation number of the block address, the generation number indicative of a number of times which data at the block address has been modified; and

using the block address and the generation number to uniquely identify a data block that matches the block address and the generation number, including using the block address and the generation number to avoid communication of the data block over the network in response to a determination that a destination device already has a data block that matches the block address and the generation number.

13. A storage server as recited in claim 12, wherein using the block address and the generation number to avoid communication of the data block over the network comprises:

sending the block address and the generation number of the second data block from the storage server to the destination device to allow the destination device to determine whether the destination device has a data block that matches the block address and the generation number.

14. A storage server as recited in claim 12, wherein the storage server is the destination device, and wherein using the block address and the generation number to avoid communication of the data block over the network comprises:

receiving the block address and the generation number of the second data block from a source device.

15. A storage server as recited in claim 14, wherein the communication process further comprises:

when storage server does not have a data block that matches the block address and the generation number, then requesting the source device to send the data block that matches the block address and the generation number to the storage server.

16. A storage server as recited in claim 12, wherein the storage server is a network caching device and the destination device is an origin server for content cached by the storage server.

20. A storage server as recited in claim 12, wherein the communication process further includes:

updating the first data block on the destination device by copying from a data block on the destination device that matches the block address and the generation number after determining that the destination device already has the data block that matches the block address and the generation number.

17. An apparatus comprising:

means for determining that a first data block stored by a source device has been modified, that the first data block has the same content as a second data block on the source device, and that the first data block should be updated by a destination device;

means for determining a block address of the second data block and a generation number of the block address, the generation number indicative of a number of times which data at the block address has been modified; and

means for using the block address and the generation number to determine whether the destination device already has a data block that matches the block address and the generation number and to avoid sending the data block to the destination device when it is determined that the destination device already has a data block that matches the block address and the generation number.