System and method for copy on write on an SSD

Patent metadata

Field	Value
Publication number	US-11226747-B2
Application number	US-202016746663-A
Country	US
Kind code	B2
Filing date	Jan 17, 2020
Priority date	Feb 25, 2015
Publication date	Jan 18, 2022
Grant date	Jan 18, 2022

Abstract

Techniques for improved copy on write functionality within an SSD are disclosed. In some embodiments, the techniques may be realized as a method for providing improved copy on write functionality within an SSD including providing, in memory of a device, an indirection data structure. The data structure may include a master entry for cloned data, the master entry having a reference to one or more indexes and a clone entry for the cloned data, the cloned entry having at least one of: a reference to a master index, a reference to a next index, and a value indicating an end of a data structure. The techniques may include traversing, using a computer processor, one or more copies of the cloned data using one or more of the references.

First claim

What is claimed is:

1. A method for improved copy on write functionality within an SSD, comprising:
creating a master c-entry, wherein the master c-entry contains LBAs mapped to a plurality of physical addresses and wherein the master c-entry contains actual mappings to less than all of the plurality of physical addresses;
creating a clone c-entry, wherein the clone c-entry contains LBAs mapped to less than all of the plurality of physical addresses, wherein the clone c-entry maps to at least one physical address of the plurality of physical addresses that matches a physical address actually mapped in the master c-entry, and wherein the clone c-entry maps to at least one physical address of the plurality of physical addresses that is not actually mapped in the master c-entry;
assigning a block within the master c-entry to indicate a first master index, wherein the first master index is configured to point to the master c-entry;
assigning a block within the master c-entry to indicate a first next index, wherein the first next index is configured to point to a first clone c-entry in a chain;
assigning a block within the clone c-entry to indicate a second master index, wherein the second master index is configured to point to the master c-entry;
assigning a block within the clone c-entry to indicate a second next index, wherein the second next index is configured to point to one or more of a next clone c-entry, the master c-entry, and a value indicating an end of the chain;
reading the master c-entry and the clone c-entry; and
uncloning the clone c-entry.

2. The method of claim 1 , wherein the creating the master c-entry and creating the clone c-entry is implemented on a flat indirection system.

3. The method of claim 2 , wherein the flat indirection system has an indirection data structure with entries.

4. The method of claim 3 , wherein the indirection data structure entry has a clone tracking bit.

5. The method of claim 4 , wherein the clone tracking bit is set to 1 to indicate that a particular packed logical block is a master copy.

6. A method for improved copy on write functionality within an SSD comprising:
creating a master c-entry, wherein the master c-entry contains LBAs mapped to a plurality of physical addresses and wherein the master c-entry contains actual mappings to less than all of the plurality of physical addresses;
creating a clone c-entry, wherein the clone c-entry contains LBAs mapped to less than all of the plurality of physical addresses, wherein the clone c-entry maps to at least one physical address of the plurality of physical addresses that matches a physical address actually mapped in the master c-entry, and wherein the clone c-entry maps to at least one physical address of the plurality of physical addresses that is not actually mapped in the master c-entry;
determining that a reference to a next index of the master c-entry points to the clone c-entry;
uncloning the clone c-entry by replacing the reference to the next index located in a first sub-entry with a packed logical block, and replacing a reference to a master index located in a second sub-entry with a packed logical block; and
uncloning the master c-entry by replacing the reference to the next index located in a third sub-entry with a packed logical block, and replacing the reference to the master index located in a fourth sub-entry with a packed logical block, wherein each packed logical block comprises a map of logical block addresses (LBAs) to a physical address.

7. The method of claim 6 , wherein the references comprise entries in a flat indirection table for logical block addressing.

8. The method of claim 6 , wherein the references comprise entries in a tree data structure for logical block addressing.

9. The method of claim 6 , further comprising setting an indicator for one or more of the packed logical blocks located in the master c-entry and the cloned entry to indicate that the one or more packed logical blocks are cloned.

10. The method of claim 6 , wherein the reference to the master index of the master c-entry points to the master entry.

11. The method of claim 6 , wherein the reference to the master index of the cloned entry points to the master c-entry.

12. The method of claim 6 , wherein a reference to the next index of a last cloned entry in a data structure points to the master entry.

13. The method of claim 6 , further comprising:
determining that the clone entry for cloned data is one of a plurality of clone entries, wherein the determination comprises determining at least one of:
that the reference to the next index of the cloned entry does not match the reference to the master index of the cloned entry; and
that the reference to the next index of the master entry does not point to the clone entry for the cloned data; and

uncloning the clone entry for the cloned data by setting a reference to a next index of a prior clone entry of the plurality of clone entries equal to the reference to the next index of the cloned entry for the cloned data.

14. The method of claim 6 , further comprising:
reviewing a fifth sub-entry of an indirection data structure during a garbage collection process;
determining that the fifth sub-entry contains a cloned indicator; and
determining that the fifth sub-entry in the garbage collection process is a valid sub-entry not to be deleted based upon the determination that the fifth sub-entry contains the cloned indicator.

15. A method for improved copy on write functionality within an SSD, comprising:
determining that a reference to a next index of a master entry points to a clone entry of cloned data;
uncloning the clone entry of cloned data by replacing the reference to the next index located in a first sub-entry with a packed logical block, and replacing the reference to the master index located in a second sub-entry with a packed logical block; and
uncloning the master entry of the cloned data by replacing the reference to the next index located in a third sub-entry with a packed logical block, and replacing the reference to the master index located in a fourth sub-entry with a packed logical block, wherein each packed logical block comprises a map of logical block addresses (LBAs) to a physical address.

16. A system for providing improved copy on write functionality within a solid state drive, the system comprising:
a first device;
wherein the first device includes stored instructions stored in memory, the instructions comprising:
determining that a reference to a next index of a master entry points to a clone entry of cloned data;
uncloning the clone entry of cloned data by replacing the reference to the next index located in a first sub-entry with a packed logical block, and replacing the reference to the master index located in a second sub-entry with a packed logical block; and
uncloning the master entry of the cloned data by replacing the reference to the next index located in a third sub-entry with a packed logical block, and replacing the reference to the master index located in a fourth sub-entry with a packed logical block, wherein each packed logical block comprises a map of logical block addresses (LBAs) to a physical address.

17. The system of claim 16 , wherein the references comprise entries in a flat indirection table for logical block addressing.

18. The system of claim 16 , further comprising an instruction to set an indicator for one or more of the packed logical blocks located in the master entry and the cloned entry to indicate that the one or more packed logical blocks

Assignees

• Dewitt Dylan Mark
• Espeseth Adam Michael
• Mccambridge Colin Christopher
• Dreyer David George
• Western Digital Tech Inc

Inventors

• Dewitt Dylan Mark
• Espeseth Adam Michael
• Mccambridge Colin Christopher
• Dreyer David George

Classifications

• G06F12/0246 Primary

  in block erasable memory, e.g. flash memory · CPC title

• G11C29/765 Primary

  in solid state disks · CPC title

• G06F2212/1008

  Correctness of operation, e.g. memory ordering · CPC title

• G06F13/4022

  using switching circuits, e.g. switching matrix, connection or expansion network (G06F13/4009 takes precedence) · CPC title

• G06F12/10

  Address translation · CPC title