Snapshot efficiency

Patent metadata

Field	Value
Publication number	US-9740632-B1
Application number	US-201414496359-A
Country	US
Kind code	B1
Filing date	Sep 25, 2014
Priority date	Sep 25, 2014
Publication date	Aug 22, 2017
Grant date	Aug 22, 2017

Abstract

In one aspect, a method includes receiving a request to write to an offset in a first logical device, determining a second logical device that wrote to the offset, the second logical device being an ancestor of the first logical device in a hierarchical tree of snapshots, determining from decedents of the second logical device in the hierarchical tree whether data in the offset of the second logical device is shadowed data or partially shadowed data, removing address-to-hash mapping for the offset of the second logical device if the data for the offset is shadowed and moving address-to-hash mapping to a single descendent of the second logical device if the data for the offset is partially shadowed.

First claim

What is claimed is:

1. A method comprising:
receiving a plurality of write request requests to write to an offset in a first logical device;
determining, for each write request received, a second logical device that wrote to the offset, the second logical device being an ancestor of the first logical device in a hierarchical tree of snapshots;
determining, for each write request received, from descendants of the second logical device in the hierarchical tree whether data in the offset of the second logical device is shadowed data or partially shadowed data;
and for each write request received, removing an address-to-hash mapping for the offset of the second logical device if the data for the offset is shadowed; and moving the address-to-hash mapping to a single descendant that has sole access to the offset of the second logical device if the data for the offset is partially shadowed.

2. The method of claim 1 , wherein determining a second logical device that wrote to the offset comprises ascending the hierarchical tree from the first logical device to determine a second logical device that is the first to write to the offset.

3. The method of claim 1 , wherein determining a second logical device that wrote to the offset comprises determining a second logical device that wrote to the offset using a bitmap of the offset.

4. The method of claim 1 , wherein determining from decedents of the second logical device in the hierarchical tree whether data in the offset of the second logical device is shadowed data or partially shadowed data comprises determining from decedents of the second logical device in the hierarchical tree whether data in the offset of the second logical device is shadowed data or partially shadowed data using a bitmap of the offset.

5. The method of claim 1 , wherein data in the offset of the second logical device is shadowed data if no external device may access the data in the offset of the second logical unit.

6. The method of claim 1 , wherein data in the offset of the second logical device is partially shadowed data if only one external device may access the data in the offset of the second logical unit.

7. An apparatus, comprising:
electronic hardware circuitry configured to:
receive a plurality of write requests to write to an offset in a first logical device;
determine, for each write request, a second logical device that wrote to the offset, the second logical device being an ancestor of the first logical device in a hierarchical tree of snapshots;
determine, for each write request, from descendants of the second logical device in the hierarchical tree whether data in the offset of the second logical device is shadowed data or partially shadowed data;
and for each write request received, remove an address-to-hash mapping for the offset of the second logical device if the data for the offset is shadowed; and move the address-to-hash mapping to a single descendent that has sole access to the offset of the second logical device if the data for the offset is partially shadowed.

8. The apparatus of claim 7 , wherein the circuitry comprises at least one of a processor, a memory, a programmable logic device or a logic gate.

9. The apparatus of claim 7 , wherein the circuitry configured to determine a second logical device that wrote to the offset comprises circuitry configured to ascend the hierarchical tree from the first logical device to determine a second logical device that is the first to write to the offset.

10. The apparatus of claim 7 , wherein the circuitry configured to determine a second logical device that wrote to the offset comprises circuitry configured to determine a second logical device that wrote to the offset using a bitmap of the offset.

11. The apparatus of claim 7 , wherein the circuitry configured to determine from decedents of the second logical device in the hierarchical tree whether data in the offset of the second logical device is shadowed data or partially shadowed data comprises circuitry configured to determine from decedents of the second logical device in the hierarchical tree whether data in the offset of the second logical device is shadowed data or partially shadowed data using a bitmap of the offset.

12. The apparatus of claim 7 , wherein data in the offset of the second logical device is shadowed data if no external device may access the data in the offset of the second logical unit.

13. The apparatus of claim 7 , wherein data in the offset of the second logical device is partially shadowed data if only one external device may access the data in the offset of the second logical unit.

14. An article comprising:
a non-transitory computer-readable medium that stores computer-executable instructions the instructions causing a machine to:
receive a plurality of write requests to write to an offset in a first logical device;
determine, for each write request, a second logical device that wrote to the offset, the second logical device being an ancestor of the first logical device in a hierarchical tree of snapshots;
determine, for each write request, from descendants of the second logical device in the hierarchical tree whether data in the offset of the second logical device is shadowed data or partially shadowed data;
and for each write request received, remove an address-to-hash mapping for the offset of the second logical device if the data for the offset is shadowed; and move the address-to-hash mapping to a single descendent that has sole access to the offset of the second logical device if the data for the offset is partially shadowed.

15. The article of claim 14 , wherein the instructions causing the machine to determine a second logical device that wrote to the offset comprises instructions causing the machine to ascend the hierarchical tree from the first logical device to determine a second logical device that is the first to write to the offset.

16. The article of claim 14 , wherein the instructions causing the machine to determine a second logical device that wrote to the offset comprises instructions causing the machine to determine a second logical device that wrote to the offset using a bitmap of the offset.

17. The article of claim 14 , wherein the instructions causing the machine to determine from decedents of the second logical device in the hierarchical tree whether data in the offset of the second logical device is shadowed data or partially shadowed data comprises instructions causing the machine to determine from decedents of the second logical device in the hierarchical tree whether data in the offset of the second logical device is shadowed data or partially shadowed data using a bitmap of the offset.

18. The article of claim 14 , wherein data in the offset of the second logical device is shadowed data if no external device may access the data in the offset of the second logical unit.

19. The article of claim 14 , wherein data in the offset of the second logical device is partially shadowed data if only one external device may access the data in the offset of the second logical unit.

Assignees

• Emc Corp
• Emc Ip Holding Co Llc

Inventors

• Love Phil
• Shoikhet Kirill
• Hallak Renen
• Halevi Ido
• Lempel Irit

Classifications

• G06F3/0619 Primary

  in relation to data integrity, e.g. data losses, bit errors · CPC title

• G06F17/30324

  Physics · mapped topic

• G06F12/1018 Primary

  involving hashing techniques, e.g. inverted page tables · CPC title

• G06F11/1446

  Point-in-time backing up or restoration of persistent data · CPC title

• G06F12/0292

  using tables or multilevel address translation means (G06F12/023 takes precedence; address translation in virtual memory systems G06F12/10) · CPC title