Method for storing data in a geographically-diverse data-storing system providing cross-site redundancy

• US 6,970,987 B1
• Filed: 01/27/2003
• Issued: 11/29/2005
• Est. Priority Date: 01/27/2003
• Status: Expired due to Fees

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Leung, Shun-Tak, Ji, Minwen
• Primary Examiner(s): BATAILLE, PIERRE MICHE
• Application Number:
  US10/352,842
• Time in Patent Office: 1,037 Days
• Field of Search: 711/162, 711/165, 711/112, 711/170, 707/203, 707/204, 714/6, 714/1, 714/42, 709/217
• US Class Current: 711/162
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 11/1471 involving logging of persistent data for recovery
• CPC Class Codes: G06F 2211/1028 Distributed, i.e. distributed RAID systems with parity

Abstract

A method of redundantly storing data in a geographically-diverse data-storing system is presented. The data-storing system has one or more data sites and a set of data-protecting sites. A new version of a set of data is written to a first data site, and a representation of the new version is generated. The representation is transmitted from the first data site to a subset of the data-protecting sites. At each data-protecting site, the representation is stored and an acknowledgment of the storing is transmitted back. Also, upon receipt back of a commit command, a data-protecting operation is performed on the representation to generate a data-protecting value, which is also stored. Then, storage corresponding to the representation is released. Further, at a first data site, once acknowledgments from each data-protecting site are received, a commit command is transmitted to the subset of data-protecting sites. Additionally, storage is released corresponding to a previous version of the set of data.

Claims

1. A method of redundantly storing data in a geographically-diverse data-storing system, the data-storing system having one or more data sites and a plurality of data-protecting sites, the method comprising:

writing a new version of a set of data to a first data site of the one or more data sites;

generating a representation of the new version;

transmitting the representation from the first data site to a subset of the plurality of data-protecting sites;

at each data-protecting site of the subset of the data-protecting sites;

storing the representation;

transmitting an acknowledgment of the storing;

upon receipt of a commit command, performing a data-protecting operation on the representation to generate a data-protecting value;

storing the data-protecting value; and

releasing storage corresponding to the representation; and

at the first data site, after receipt of acknowledgments from each data-protecting site of the subset of data-protecting sites;

transmitting a commit command to the subset of the data-protecting sites; and

releasing storage corresponding to a previous version of the set of data.

2. The method of claim 1, wherein the subset of the data-protecting sites comprises two or more data-protecting sites.

3. The method of claim 1, wherein the generating of the representation is based at least in part on both the new version of the set of data and on the previous version of the set of data.

4. The method of claim 3, wherein the new version of the set of data is written to a first physical address at the first data site, and the previous version of the set of data is written to a second physical address at the first data site.

5. The method of claim 1, wherein the data-protecting operation is conducted at least in part on both the representation and on a previous version of the data-protecting value.

6. The method of claim 1, further comprising:

after receipt of the acknowledgment at the first data site, modifying a logical address corresponding to the set of data in a logical-to-physical map to point to a physical address of the new version of the set of data.

7. A method of redundantly storing data in a geographically-diverse data-storing system, the data-storing system having one or more data sites and a plurality of data-protecting sites, the method comprising:

writing first and second versions of a set of data to a first data site of the one or more data sites, wherein the first data site is local, and other data sites and the plurality of data-protecting sites are remote;

generating a representation of the second version, based at least in part on a change in the set of data between the second version and the first version;

transmitting the representation from the first data site to a subset of the plurality of data-protecting sites;

at each data-protecting site of the subset of the data-protecting sites;

storing the representation;

transmitting an acknowledgment of the storing;

upon receipt of a commit command, performing a data-protecting operation on the representation and on an existing data-protecting value to generate a new data-protecting value;

storing the new data-protecting value; and

releasing storage corresponding to the representation; and

locally, after receipt of acknowledgments from each data-protecting site of the subset of data-protecting sites;

transmitting a commit command to the subset of the data-protecting sites; and

releasing storage corresponding to the first version of the set of data.

8. The method of claim 7, wherein the subset of the data-protecting sites comprises two or more data-protecting sites.

9. The method of claim 7, further comprising;

after receipt of all acknowledgments at the first data site, modifying a logical address corresponding to the set of data in a logical-to-physical map to point to a physical address of the second version of the set of data.

10. The method of claim 9, wherein the logical-to-physical map is stored in nonvolatile memory.

11. The method of claim 7, wherein the second version is entered into a redo log when it is written to the first data site, and is removed from the redo log after the acknowledgment is received at the first data site;

and

wherein the redo log identifies versions of sets of data being processed in the event of a system crash such that processing of the identified versions can be completed upon reboot.

12. The method of claim 7, wherein the data-performing operation is determined in accordance with an erasure code.

13. The method of claim 7, wherein the generating the representation of the second version includes XORing the second version and the first version of the set of data.

14. The method of claim 7, wherein the writing of the second version of the set of data to the first data site occurs in response to a write request from a client, and wherein the client write request is fully completed before the generating occurs.

15. The method of claim 7, wherein the one or more data sites comprise one or more hard disks.

16. The method of claim 7, wherein the storing, transmitting, and performing at each data-protecting site are repeated serially for later versions of the set of data, after being performed for the second version of the set of data.

17. The method of claim 7, wherein, at each data-protecting site, the stored second version of the data-protecting value is associated with its corresponding version number in memory.

18. A method of redundantly storing data in a geographically-diverse data-storing system, the data-storing system having one or more data sites and a plurality of data-protecting sites, the method comprising:

mapping physical addresses of the one or more data sites to a plurality of logical addresses in a logical-to-physical map, to logically associate a plurality of data blocks that include geographically-diverse data blocks;

at a local portion of the data-storing system;

writing a new version of a set of data to a first physical address of a first data site of the one or more data sites, wherein a previous version of the set of data was previously written to a second physical address of the first data site;

logging the new version of the set of data in a redo log;

transmitting a representation of the second version to a subset of the plurality of data-protecting sites; and

when the subset of the one or more data-protecting sites acknowledge receipt of the representation;

removing the new version from the redo log;

modifying the logical-to-physical map such that a logical data block corresponding to the set of data identifies the new version;

releasing storage corresponding to the new version; and

transmitting a command to the subset of the data-protecting sites to generate and store a data-protecting value based at least in part on the representation.

19. The method of claim 18, wherein the subset of the data-protecting sites comprises two or more data-protecting sites.

20. The method of claim 18, further comprising, at each data-protecting site of the subset of the data-protecting sites:

storing the representation;

logging the representation in a second redo log;

transmitting an acknowledgment of the storing;

upon receipt of the command to generate and store a data-protecting value,

performing a data-protecting operation on the representation to generate a data-protecting value;

storing the data-protecting value;

releasing storage corresponding to the representation; and

removing the representation from the second redo log.

21. A method of recovering data in a geographically-diverse data-storing system, the data-storing system having one or more data sites and a plurality of data-protecting sites, wherein a set of data blocks is lost from a first data site of the one or more data sites, the method comprising:

for each lost data block of the set of lost data blocks;

requesting, from a subset of the plurality of data-protecting sites, one or more available version numbers corresponding to the lost data block;

requesting, from a subset of the one or more data sites, a set of version numbers of stable data blocks that comprise, along with the lost data block and one or more data-protecting blocks, a redundancy group;

based at least in part on the one or more available version numbers, determining a latest recoverable version of the lost data block;

receiving, from the subset of the data-protecting sites, one or more data-protecting values corresponding to the latest recoverable version;

receiving, from the subset of the data sites, one or more stable data blocks,

associated with the same redundancy group as the lost data block; and

regenerating the lost data block from the one or more data-protecting values and the one or more stable data blocks by performing a data-regenerating operation.

22. The method of claim 21, wherein the first data site is geographically diverse from other data sites of the one or more data sites, and from the plurality of data-protecting sites.

23. The method of claim 21, wherein recovering all lost data is possible if a total number of the plurality of data-protecting sites is greater than a total number of sites lost, including both lost data sites and lost data-protecting sites.

24. The method of claim 21, further comprising:

instructing the subset of the data-protecting sites to synchronize their data-protecting values corresponding to the regenerated lost data block.

25. The method of claim 21, wherein at each data-protecting site of the subset of data-protecting site:

upon receiving a request for a data-protecting value corresponding to the latest recoverable version, stopping operations to store or release additional data-protecting values.