Using logical block addresses with generation numbers as data fingerprints to provide cache coherency

• US 8,473,690 B1
• Filed: 10/30/2009
• Issued: 06/25/2013
• Est. Priority Date: 10/30/2009
• Status: Active Grant

• Current Assignee: NetApp, Inc.
• Original Assignee: NetApp, Inc.
• Inventors: Condict, Michael N.
• Primary Examiner(s): Shah, Sanjiv
• Assistant Examiner(s): GOLDSCHMIDT, CRAIG S
• Application Number:
  US12/610,234
• Time in Patent Office: 1,334 Days
• Field of Search: 711/144
• US Class Current: 711/141
• CPC Class Codes: G06F 12/0815 Cache consistency protocols
• CPC Class Codes: G06F 12/0866 for peripheral storage systems, e.g. disk cache
• CPC Class Codes: G06F 2212/263 Network storage, e.g. SAN or NAS
• CPC Class Codes: G06F 2212/314 In storage network, e.g. network attached cache

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 maintain cache coherency among multiple storage nodes. It can also be employed to avoid sending the data to a network node over a network if it already has the data.

Claims

1. A method comprising:

assigning a logical block address to each of a plurality of data blocks stored in a storage system;

assigning a generation number to each said logical block address, each generation number indicative of a number of times that data at the corresponding logical block address has been modified;

receiving at a server a write signal from a caching device, the write signal indicating a write performed to a first data block at the caching device, the write signal including write data, a first logical block address and a first generation number corresponding to the first logical block address;

in response to the write signal, determining at the server whether the first generation number is the latest generation number for the first logical block address; and

if the generation number is the latest generation number for the first logical block address, then updating the first data block at the server according to the write data, the first logical block address and the first generation number, but if the generation number is not the latest generation number for the first logical block address, then sending an error message to the caching device in response to the write signal, to cause the caching device to

increment the first generation number at the caching device, and

send to the server a second write signal from the caching device, the second write signal including second write data for the first data block and further including the first logical block address and the incremented first generation number.

2. A method as recited in claim 1, wherein the write to the first data block is implemented as a read-modify-write operation at the caching device.

3. A method comprising:

assigning a block address to each of a plurality of data blocks in a shared, distributed set of data in the distributed storage system, each of the storage nodes caching portions of the shared, distributed set of data, each of the storage nodes having write privileges for the shared, distributed set of data;

assigning a generation number to each said block address, each generation number indicative of a number of times that data at the corresponding block address has been modified;

sending to a server a first write signal from the caching device, the write signal indicating a write performed to a first data block at the caching device, the write signal including first write data, a first logical block address and a first generation number corresponding to the logical block address;

receiving at the caching device from the server an error message responsive to the first write signal and responsive to the server determining that the first generation number is not the latest generation number for the first logical block address; and

in response to the error message, incrementing the first generation number at the caching device and sending to the server a second write signal from the caching device, the second write signal including second write data for the first data block and further including the first logical block address and the incremented first generation number.

4. A method as recited in claim 3, wherein the write to the first data block is implemented as a read-modify-write operation at the caching device.

5. A server for use in a network storage system, the server comprising:

a processor;

a communication device, coupled to the processor, through which the server can communicate with a caching device in the network storage system over an interconnect; and

a memory coupled to the processor and storing code which, when executed by the processor, causes the server to perform operations including

assigning a logical block address to each of a plurality of data blocks stored in the network storage system;

assigning a generation number to each said logical block address, each generation number indicative of a number of times that data at the corresponding logical block address has been modified;

receiving at the server a write signal from the caching device, the write signal indicating a write performed to a first data block at the caching device, the write signal including write data, a first logical block address and a first generation number corresponding to the first logical block address;

in response to the write signal, determining at the server whether the first generation number is the latest generation number for the first logical block address; and

if the generation number is the latest generation number for the first logical block address, then updating the first data block at the server according to the write data, the first logical block address and the first generation number, but if the generation number is not the latest generation number for the first logical block address, then sending an error message to the caching device in response to the write signal, to cause the caching device to

increment the first generation number at the caching device, and

send to the server a second write signal from the caching device, the second write signal including second write data for the first data block and further including the first logical block address and the incremented first generation number.

6. A server as recited in claim 5, wherein the write to the first data block is implemented as a read-modify-write operation at the caching device.

7. A caching device for use in a distributed storage system, the caching device comprising:

a processor;

a communication device, coupled to the processor, through which the caching device can communicate with a server in the distributed storage system over an interconnect; and

a memory coupled to the processor and storing code which, when executed by the processor, causes the caching device to perform operations including

assigning a block address to each of a plurality of data blocks in a shared, distributed set of data in the distributed storage system, each of the storage nodes caching portions of the shared, distributed set of data, each of the storage nodes having write privileges for the shared, distributed set of data;

assigning a generation number to each said block address, each generation number indicative of a number of times that data at the corresponding block address has been modified;

sending to the server a first write signal from the caching device, the write signal indicating a write performed to a first data block at the caching device, the write signal including first write data, a first logical block address and a first generation number corresponding to the logical block address;

receiving at the caching device from the server an error message responsive to the first write signal and responsive to the server determining that the first generation number is not the latest generation number for the first logical block address; and

in response to the error message, incrementing the first generation number at the caching device and sending to the server a second write signal from the caching device, the second write signal including second write data for the first data block and further including the first logical block address and the incremented first generation number.

8. A caching device as recited in claim 7, wherein the write to the first data block is implemented as a read-modify-write operation at the caching device.