Continuous data protection

Claim 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.

Claim 2

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.