Continuous data protection

• US 7,653,800 B2
• Filed: 08/03/2005
• Issued: 01/26/2010
• Est. Priority Date: 08/03/2005
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Helman, Haim, Zohar, Ofir, Schwartz, Shemer, Revah, Yaron, Cohen, Dror
• Primary Examiner(s): Shah; Sanjiv
• Assistant Examiner(s): Eland; Shawn
• Application Number:
  US11/196,721
• Publication Number:
  US 20070033370A1
• Time in Patent Office: 1,637 Days
• Field of Search: 711/173
• US Class Current: 711/173
• CPC Class Codes: G06F 11/1435 using file system or storage system metadata
• CPC Class Codes: G06F 21/80 in storage media based on magnetic or optical technology, e.g. disks with sectors preventing unauthorised reproduction or copying of disc-type recordable media G11B20/00

Abstract

A method for continuous data protection in a storage system, including receiving a first write command to write first data to a partition of a logical volume and then generating a first partition descriptor record (PDR) having a first timestamp. The method further includes storing the first data at a first location, associating the first PDR with the first location, and receiving a second write command, subsequent to the first command, to update the first data with second data. Responsively to the second command, a second PDR having a second timestamp is generated. The second data is stored at a second location, and the second PDR is associated with the second location. The method includes generating a pointer between the first PDR and the second PDR, and accessing the first PDR using the pointer in response to a read command indicating a time prior to the second timestamp.

Claims

1. A method for data protection, comprising:

dividing a logical volume in a data storage system into partitions having equal sizes;

providing a first data structure, a second data structure, and a third data structure which are logically connected in accordance with a hierarchy and which are sequentially accessed in accordance with the hierarchy to locate data stored in the data storage system;

storing in each of a multiplicity of network interfaces of the data storage system the first data structure comprising a table of routing records mapping logical addresses for the partitions to caches of the data storage system;

storing in each cache the second data structure, comprising, within a given cache, a hash table mapping a logical address to a most-recent partition descriptor record (PDR) associated with a most-recent-version of a given partition in the logical volume, the most-recent PDR being comprised in partition descriptor records (PDRs), located in the given cache, having respective PDR-timestamps;

storing in each cache, for each most-recent PDR, an instance of the third data structure, comprising;

a doubly-linked list forward-linking and backward-linking the PDRs in response to the PDR-timestamps, and, for respective data associated with the PDRs, respective physical addresses in a non-volatile storage device of the data storage system of the respective data;

receiving a write command to write updated data to the given partition;

in response to the write command, traversing the first data structure to determine an appropriate cache, traversing therein the second data structure to determine if a prior PDR exists, and creating the most-recent PDR having a most-recent timestamp therein;

if the prior PDR for the given partition exists, updating the list to forward-link the prior PDR to the most-recent PDR and to backward-link the most-recent PDR to the prior PDR, and to incorporate a new physical address for the updated data;

writing the updated data to the new physical address;

updating the hash table of the second data structure in response to the most-recent PDR;

receiving a read command to read specific data at a specific logical address of the given partition current at a requested time; and

in response to the read request performing the following steps in sequence;

using the first data structure to locate the appropriate cache,

using the hash table of the second data structure comprised in the appropriate cache to access the most-recent PDR, and

accessing the third data structure to read the most-recent timestamp of the most-recent PDR, and if the requested time is greater than the most-recent timestamp, reading the updated data from the new physical address, and if the requested time is less than the most-recent timestamp, iteratively traversing the list to determine a particular prior PDR having a timestamp closest to, and less than, the requested time, and reading the data associated with the particular prior PDR.

2. The method according to claim 1, and comprising linking the PDRs to each other by a binary tree responsively to writing the data stored in the data storage system.

3. The method according to claim 2, wherein the binary tree is generated by an Adelson-Velskii and Landis (AVL) method.

4. The method according to claim 1, wherein the PDRs comprise respective bitmap fields and wherein writing the updated data comprises using the bitmap fields to determine that the write command does not comprise a split write command.

5. The method according to claim 1, wherein the hash table comprises pointers associating the given partition with respective PDRs.

6. The method according to claim 1, wherein the equal sizes of the partitions are set in response to sizes of the data of the write command.

7. The method according to claim 1, wherein none of the data stored in the data storage system is overwritten.