Granted Patent B2

US 9,311,016 · App. 14/092,243 · Granted Apr 12, 2016

Inventors: Josef Ezra (Even Yehuda, IL); Yechiel Yochai (Moshav Aviel, IL); Ido Ben-Tsion (Ramat Gan, IL); Efraim Zeidner (Haifa, IL); Nir Schenkler (Haifa, IL)

Assignee: INFINIDAT LTD.

G06F3/065G06F3/0604G06F3/0605G06F3/0614G06F3/0683G06F3/0689G06F11/1446G06F11/1458G06F12/0864G06F17/30088G06F2201/84

Abstract

Claims (59)

1. For use in a storage system comprising a control layer with a cache memory and operable to manage a snapshot family (SF) constituted by hierarchically related SF members and mapped by a SF mapping data structure configured to provide logical-to-physical mapping for SF members, a method of identifying delta-data between two points-in-time, the method comprising:

generating successive snapshots S i and S i+1 corresponding to the two points-in-time;

upon generating the snapshot S i+1 ,

searching the cache memory for data blocks associated with snap_version identifier indicative of snap_version=i, thereby yielding cached delta-metadata, wherein snap_version identifier associated with a given data block is indicative of the latest SF member existing at the time of writing the given data block to the cache memory;

searching the SF mapping data structure for destaged data blocks associated with snap_version identifier indicative of snap_version=i, thereby yielding destaged delta-metadata, wherein the SF mapping data structure is configured to associate a given physical address with snap_version identifier indicative of the latest snapshot existing at the time of writing to the cache memory data corresponding, when destaged, to the given physical address; and

joining the cached delta-metadata and the destaged delta-metadata, thereby yielding delta-metadata indicative of the delta-data between points-in-time corresponding to the successive snapshots with Snap_ID=i and Snap_ID=i+1.

2. The method of claim 1 , wherein joining the cached delta-metadata and the destaged delta-metadata comprises selecting only cached delta-metadata if both delta-metadata and destaged delta-metadata are indicative of the same data block kept in the cache memory after destage.

3. The method of claim 1 further comprising:

assigning to each cache mapping entry in the cache memory a constantly updated first value indicative of the highest snap_version identifier out of snap_version identifiers associated with data blocks mapped by the respective entry; and

searching the cache memory for data blocks associated with snap_version identifier indicative of snap_version=i solely in cache mapping entries with assigned first value indicative of snap_version≧i.

4. The method of claim 1 , further comprising:

assigning to each SF mapping entry in the SF mapping data structure a constantly updated second value indicative of the highest snap_version identifier out of snap_version identifiers associated with data blocks mapped by the respective entry; and

searching the SF mapping data structure for data blocks associated with snap_version identifier indicative of snap_version=i solely in SF mapping entries with assigned second value indicative of snap_version≧i.

5. The method of claim 1 , wherein the SF mapping data structure is configured as an ordered mapping tree comprising a plurality of nodes, the method further comprising:

assigning to each given node in the mapping tree a third value indicative of the highest snap_version identifier out of all snap_version identifiers associated with all data blocks mapped by all leaves represented by nodes below the given node;

responsive to destaging a data block associated with a snap_version identifier indicative of snap_version=k, k greater than the third value, updating third value assigned to a representing node that represents a leaf mapping the data block to become equal to k; and

traversing up the mapping tree and successively updating third values assigned to each node above the representing node to become equal to k, and stopping updating at a first with assigned third value not less than k.

6. The method of claim 5 , wherein searching the SF mapping data structure for data blocks associated with snap_version identifier indicative of snap_version=i comprises:

traversing down the mapping tree starting from a root node and successively comparing for each node the associated third value with snap_version=i value;

for representing nodes with associated third value not less than snap_version=i value, identifying in the represented leaves data blocks associated with snap_version=i, thereby yielding delta-metadata for respective leaves;

stopping traversing at a first node with assigned third value lower than i; and

joining delta-metadata for respective leaves thereby yielding the destaged delta-metadata.

7. The method of claim 6 , further comprising:

assigning to each leaf in the mapping tree a constantly updated second value indicative of the highest snap_version identifier out of snap_version identifiers associated with data blocks mapped by the respective leaf; and

for representing nodes with associated third value not less than snap_version=i value, searching data blocks associated with snap_version=i solely in represented leaves with assigned second value indicative of snap_version≧i.

8. The method of claim 1 , wherein searching the SF mapping data structure for destaged data blocks is provided over data blocks accessible for access requests received from one or more hosts.

9. A storage system comprising a control layer and a cache memory therein, the control layer configured to manage a snapshot family (SF) constituted by hierarchically related SF members and mapped by a SF mapping data structure configured to provide logical-to-physical mapping for SF members,

wherein the control layer is further configured to identify delta-data between two points-in-time by providing at least the following:

generating successive snapshots S i and S i+1 corresponding to the two points-in-time;

upon generating the snapshot S i+1 ,

searching the cache memory for data blocks associated with snap_version identifier indicative of snap_version=i, thereby yielding cached delta-metadata, wherein snap_version identifier associated with a given data block is indicative of the latest SF member existing at the time of writing the given data block to the cache memory;

searching the SF mapping data structure for destaged data blocks associated with snap_version identifier indicative of snap_version=i, thereby yielding destaged delta-metadata, wherein the SF mapping data structure is configured to associate a given physical address with snap_version identifier indicative of the latest snapshot existing at the time of writing to the cache memory data corresponding, when destaged, to the given physical address; and

joining the cached delta-metadata and the destaged delta-metadata, thereby yielding delta-metadata indicative of the delta-data between points-in-time corresponding to the successive snapshots with Snap_ID=i and Snap_ID=i+1.

10. The system of claim 9 , wherein the control layer is configured, when joining the cached delta-metadata and the destaged delta-metadata comprises, to select only cached delta-metadata if both delta-metadata and destaged delta-metadata are indicative of the same data block kept in the cache memory after destage.

11. The system of claim 9 , wherein the control layer is further configured:

to assign to each cache mapping entry in the cache memory a constantly updated first value indicative of the highest snap_version identifier out of snap_version identifiers associated with data blocks mapped by the respective entry; and

to search the cache memory for data blocks associated with snap_version identifier indicative of snap_version=i solely in cache mapping entries with assigned first value indicative of snap_version≧i.

12. The system of claim 9 , wherein the control layer is further configured:

to assign to each SF mapping entry in the SF mapping data structure a constantly updated second value indicative of the highest snap_version identifier out of snap_version identifiers associated with data blocks mapped by the respective entry; and

to search the SF mapping data structure for data blocks associated with snap_version identifier indicative of snap_version=i solely in SF mapping entries with assigned second value indicative of snap_version≧i.

13. The system of claim 9 , wherein the SF mapping data structure is configured as an ordered mapping tree comprising a plurality of nodes, the control layer is further configured:

to assign to each given node in the mapping tree a third value indicative of the highest snap_version identifier out of all snap_version identifiers associated with all data blocks mapped by all leaves represented by nodes below the given node;

responsive to destaging a data block associated with a snap_version identifier indicative of snap_version=k, k greater than the third value, to update third value assigned to a representing node that represents a leaf mapping the data block to become equal to k; and

to traverse up the mapping tree and successively updating third values assigned to each node above the representing node to become equal to k, and stopping updating at a first with assigned third value not less than k.

14. The system of claim 13 , wherein the control layer is further configured to search the SF mapping data structure for data blocks associated with snap_version identifier indicative of snap_version=i by providing at least the following:

traversing down the mapping tree starting from a root node and successively comparing for each node the associated third value with snap_version=i value;

for representing nodes with associated third value not less than snap_version=i value, identifying in the represented leaves data blocks associated with snap_version=i, thereby yielding delta-metadata for respective leaves;

stopping traversing at a first node with assigned third value lower than i; and

joining delta-metadata for respective leaves thereby yielding the destaged delta-metadata.

15. The system of claim 14 , wherein the control layer is further configured:

to assign to each leaf in the mapping tree a constantly updated second value indicative of the highest snap_version identifier out of snap_version identifiers associated with data blocks mapped by the respective leaf; and

for representing nodes with associated third value not less than snap_version=i value, to search data blocks associated with snap_version=i solely in represented leaves with assigned second value indicative of snap_version≧i.

16. The system of claim 9 , wherein the control layer is further configured to search the SF mapping data structure for destaged data blocks over data blocks accessible for access requests received from one or more hosts.

17. A non-transitory computer readable storage medium comprising computer readable program code embodied therein for operating storage system comprising a control layer with a cache memory and operable to manage a snapshot family (SF) constituted by hierarchically related SF members and mapped by a SF mapping data structure configured to provide logical-to-physical mapping for SF members, the computer readable program code causing the control layer to identify delta-data between two points-in-time by providing, at least, the following:

generating successive snapshots S i and S i+1 corresponding to the two points-in-time;

upon generating the snapshot S i+1 ,

searching the cache memory for data blocks associated with snap_version identifier indicative of snap_version=i, thereby yielding cached delta-metadata, wherein snap_version identifier associated with a given data block is indicative of the latest SF member existing at the time of writing the given data block to the cache memory;

searching the SF mapping data structure for destaged data blocks associated with snap_version identifier indicative of snap_version=i, thereby yielding destaged delta-metadata, wherein the SF mapping data structure is configured to associate a given physical address with snap_version identifier indicative of the latest snapshot existing at the time of writing to the cache memory data corresponding, when destaged, to the given physical address; and

joining the cached delta-metadata and the destaged delta-metadata, thereby yielding delta-metadata indicative of the delta-data between points-in-time corresponding to the successive snapshots with Snap_ID=i and Snap_ID=i+1.

Assignments (10)

Continuity (2)