System and method for copy on write on an SSD
View Patent ↗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.
1. A method for providing improved copy on write functionality within an SSD comprising:
providing, in memory of a device, an indirection data structure as part of a circularly linked list, the indirection data structure comprising:
a master entry for cloned data, the master entry comprising a first plurality of sub-entries, wherein a first sub-entry of the first plurality sub-entries contains a reference to a next index, a second sub-entry of the first plurality of sub-entries contains a reference to a master index, and the remaining sub-entries of the first plurality of sub-entries each contain a packed logical block (PLB);
a clone entry for the cloned data, the cloned entry comprising a second plurality of sub-entries, wherein a third sub-entry of the second plurality of sub-entries contains a reference to a master index, a fourth sub-entry of the second plurality of sub-entries contains a reference to a next index, and the remaining sub-entries of the second plurality of sub-entries each contain a PLB; and
traversing, using a computer processor, one or more copies of the cloned data using one or more of the references included in the master entry and/or the clone entry;
determining that the clone entry for the cloned data is an only clone entry, wherein the determination comprises:
determining that the reference to the next index of the cloned entry matches the reference to the master index of the cloned entry;
determining that the reference to the next index of the master entry points to the clone entry;
uncloning the clone entry of the cloned data by replacing the reference to the next index located in the fourth sub-entry with a PLB, and replacing the reference to the master index located in the third sub-entry with a PLB; and
uncloning the master entry of the cloned data by replacing the reference to the next index located in the first sub-entry with a PLB, and replacing the reference to the master index located in the second sub-entry with a PLB;
wherein each PLB comprises a map of logical block addresses (LBAs) to a physical address.
2. The method of claim 1 , wherein the references comprise entries in a flat indirection table for logical block addressing.
3. The method of claim 1 , wherein the references comprise entries in a tree data structure for logical block addressing.
4. The method of claim 1 , further comprising setting 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 are cloned.
5. The method of claim 1 , wherein the reference to the master index of the master entry points to the master entry.
6. The method of claim 1 , wherein the reference to the master index of the cloned entry points to the master entry.
7. The method of claim 1 , wherein a reference to the next index of a last cloned entry in a data structure points to the master entry.
8. The method of claim 1 , further comprising:
reviewing a fifth sub-entry of the 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.
9. A computer program product embodied on a non-transitory computer readable medium, comprised of a series of instructions executable on a computer, the computer program product performing a process for providing improved copy on write functionality within an SSD; the computer program implementing the steps of:
providing, in memory of a device, an indirection data structure as part of a circularly linked list, the indirection data structure comprising:
a master entry for cloned data, the master entry comprising a first plurality of sub-entries, wherein a first sub-entry of the first plurality sub-entries contains a reference to a next index, a second sub-entry of the first plurality of sub-entries contains a reference to a master index, and the remaining sub-entries of the first plurality of sub-entries each contain a packed logical block (PLB);
a clone entry for the cloned data, the cloned entry comprising a second plurality of sub-entries, wherein a third sub-entry of the second plurality of sub-entries contains a reference to a master index, a fourth sub-entry of the second plurality of sub-entries contains a reference to a next index, and the remaining sub-entries of the second plurality of sub-entries each contain a PLB; and
traversing, using a computer processor, one or more copies of the cloned data using one or more of the references included in the master entry and/or the clone entry;
determining that the clone entry for the cloned data is an only clone entry, wherein the determination comprises:
determining that the reference to the next index of the cloned entry matches the reference to the master index of the cloned entry;
determining that the reference to the next index of the master entry points to the clone entry;
uncloning the clone entry of the cloned data by replacing the reference to the next index located in the fourth sub-entry with a PLB, and replacing the reference to the master index located in the third sub-entry with a PLB; and
uncloning the master entry of the cloned data by replacing the reference to the next index located in the first sub-entry with a PLB, and replacing the reference to the master index located in the second sub-entry with a PLB;
wherein each PLB comprises a map of logical block addresses (LBAs) to a physical address.
10. A system for providing improved copy on write functionality within an SSD, the system comprising:
a first device;
wherein the first device includes stored instructions stored in memory, the instructions comprising:
an instruction to provide, in memory of the first device, an indirection data structure as part of a circularly linked list, the indirection data structure comprising:
a master entry for cloned data, the master entry comprising a first plurality of sub-entries, wherein a first sub-entry of the first plurality sub-entries contains a reference to a next index, a second sub-entry of the first plurality of sub-entries contains a reference to a master index, and the remaining sub-entries of the first plurality of sub-entries each contain a packed logical block (PLB);
a clone entry for the cloned data, the cloned entry comprising a second plurality of sub-entries, wherein a third sub-entry of the second plurality of sub-entries contains a reference to a master index, a fourth sub-entry of the second plurality of sub-entries contains a reference to a next index, and the remaining sub-entries of the second plurality of sub-entries each contain a PLB; and
traversing, using a computer processor, one or more copies of the cloned data using one or more of the references included in the master entry and/or the clone entry;
determining that the clone entry for the cloned data is an only clone entry, wherein the determination comprises:
determining that the reference to the next index of the cloned entry matches the reference to the master index of the cloned entry;
determining that the reference to the next index of the master entry points to the clone entry;
uncloning the clone entry of the cloned data by replacing the reference to the next index located in the fourth sub-entry with a PLB, and replacing the reference to the master index located in the third sub-entry with a PLB; and
uncloning the master entry of the cloned data by replacing the reference to the next index located in the first sub-entry with a PLB, and replacing the reference to the master index located in the second sub-entry with a PLB;
wherein each PLB comprises a map of logical block addresses (LBAs) to a physical address.
11. The system of claim 10 , wherein the references comprise entries in a flat indirection table for logical block addressing.
12. The system of claim 10 , wherein the first device comprises a Peripheral Component Interconnect Express (PCIe) device.
13. The system of claim 10 , 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 are cloned.