Continuous data protection
View Patent ↗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.
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.