Techniques for managing context information for a storage device while maintaining responsiveness

Patent metadata

Field	Value
Publication number	US-11544159-B2
Application number	US-202017033420-A
Country	US
Kind code	B2
Filing date	Sep 25, 2020
Priority date	Sep 19, 2018
Publication date	Jan 3, 2023
Grant date	Jan 3, 2023

Abstract

Disclosed are techniques for managing context information for data stored within a computing device. According to some embodiments, the method can include the steps of (1) loading, into a volatile memory of the computing device, the context information from a non-volatile memory of the computing device, where the context information is separated into a plurality of portions, and each portion of the plurality of portions is separated into a plurality of sub-portions, (2) writing transactions into a log stored within the non-volatile memory, and (3) each time a condition is satisfied: identifying a next sub-portion to be processed, where the next sub-portion is included in the plurality of sub-portions of a current portion being processed, identifying a portion of the context information that corresponds to the next sub-portion, converting the portion from a first format to a second format, and writing the portion into the non-volatile memory.

First claim

What is claimed is:

1. A method for restoring context information when an inadvertent shutdown of a computing device occurs, the computing device comprising a volatile memory and a non-volatile memory, the method comprising, at the computing device:
accessing context information stored in the non-volatile memory; and
for each portion of a plurality of portions of which the context information is comprised:
loading the portion into the volatile memory,
in response to identifying, within a log, that at least one transaction (i) corresponds to the portion, and (ii) occurred after a last write of the portion into the non-volatile memory:
updating the portion in the volatile memory to reflect the at least one transaction and to produce an updated portion, and

writing the updated portion into the non-volatile memory.

2. The method of claim 1 , wherein the log is stored in the non-volatile memory.

3. The method of claim 1 , wherein:
each portion of the plurality of portions stored in the non-volatile memory is encoded in a first format, and
each portion of the plurality of portions loaded into the volatile memory is encoded in a second format.

4. The method of claim 1 , wherein each sub-portion of a plurality of sub-portions of a given portion of the plurality of portions corresponds to a different, non-successive range of logical base addresses (LBAs) that are referenced by the context information.

5. The method of claim 1 , wherein each portion of the plurality of portions is separated into a plurality of sub-portions in accordance with a quality of service (QoS) metric to be satisfied by the computing device.

6. The method of claim 3 , further comprising, for each portion of the plurality of portions:
converting the portion from the first format to the second format prior to loading the portion into the volatile memory.

7. The method of claim 3 , wherein:
the first format utilizes (1) a plurality of first-tier entries, and (2) a plurality of second-tier entries, and
for a given portion of the plurality of portions:
each first-tier entry of the plurality of first-tier entries references (1) an area of memory within the non-volatile memory, or (2) at least one second-tier entry of the plurality of second-tier entries, and
each second-tier entry of the plurality of second-tier entries references an area of memory within the non-volatile memory.

8. A non-transitory computer readable storage medium configured to store instructions that, when executed by a processor included in a computing device, cause the computing device to restore context information when an inadvertent shutdown of the computing device occurs, by carrying out steps that include:
accessing context information stored in a non-volatile memory of the computing device; and
for each portion of a plurality of portions of which the context information is comprised:
loading the portion into a volatile memory of the computing device,
in response to identifying, within a log, that at least one transaction (i) corresponds to the portion, and (ii) occurred after a last write of the portion into the non-volatile memory:
updating the portion in the volatile memory to reflect the at least one transaction and to produce an updated portion, and

writing the updated portion into the non-volatile memory.

9. The non-transitory computer readable storage medium of claim 8 , wherein the log is stored in the non-volatile memory.

10. The non-transitory computer readable storage medium of claim 8 , wherein:
each portion of the plurality of portions stored in the non-volatile memory is encoded in a first format, and
each portion of the plurality of portions loaded into the volatile memory is encoded in a second format.

11. The non-transitory computer readable storage medium of claim 8 , wherein each sub-portion of a plurality of sub-portions of a given portion of the plurality of portions corresponds to a different, non-successive range of logical base addresses (LBAs) that are referenced by the context information.

12. The non-transitory computer readable storage medium of claim 8 , wherein each portion of the plurality of portions is separated into a plurality of sub-portions in accordance with a quality of service (QoS) metric to be satisfied by the computing device.

13. The non-transitory computer readable storage medium of claim 10 , wherein the steps further include, for each portion of the plurality of portions:
converting the portion from the first format to the second format prior to loading the portion into the volatile memory.

14. The non-transitory computer readable storage medium of claim 10 , wherein:
the first format utilizes (1) a plurality of first-tier entries, and (2) a plurality of second-tier entries, and
for a given portion of the plurality of portions:
each first-tier entry of the plurality of first-tier entries references (1) an area of memory within the non-volatile memory, or (2) at least one second-tier entry of the plurality of second-tier entries, and
each second-tier entry of the plurality of second-tier entries references an area of memory within the non-volatile memory.

15. A computing device configured to restore context information when an inadvertent shutdown of the computing device occurs, the computing device comprising:
a volatile memory;
a non-volatile memory; and
a processor configured to cause the computing device to carry out steps that include:
accessing context information stored in the non-volatile memory; and
for each portion of a plurality of portions of which the context information is comprised:
loading the portion into the volatile memory,
in response to identifying, within a log, that at least one transaction (i) corresponds to the portion, and (ii) occurred after a last write of the portion into the non-volatile memory:
updating the portion in the volatile memory to reflect the at least one transaction and to produce an updated portion, and

writing the updated portion into the non-volatile memory.

16. The computing device of claim 15 , wherein the log is stored in the non-volatile memory.

17. The computing device of claim 15 , wherein:
each portion of the plurality of portions stored in the non-volatile memory is encoded in a first format, and
each portion of the plurality of portions loaded into the volatile memory is encoded in a second format.

18. The computing device of claim 15 , wherein each sub-portion of a plurality of sub-portions of a given portion of the plurality of portions corresponds to a different, non-successive range of logical base addresses (LBAs) that are referenced by the context information.

19. The computing device of claim 17 , wherein the steps further include, for each portion of the plurality of portions:
converting the portion from the first format to the second format prior to loading the portion into the volatile memory.

20. The computing device of claim 17 , wherein:
the first format utilizes (1) a plurality of first-tier entries, and (2) a plurality of second-tier entries, and
for a given portion of the plurality of portions:
each first-tier entry of the plurality of first-tier entries references (1) an area of memory within the non-volatile memory, or (2) at least one second-tier entry of the plurality of second-tier entries, and
each second-tier entry of the plurality of second-tier entries references an area of memory within the non-volatile memory.

Assignees

• Apple Inc

Inventors

• Paley Alexander
• Vogan Andrew W
• Antoniu Tudor

Classifications

• G06F11/1471 Primary

  involving logging of persistent data for recovery · CPC title

• G06F2212/1044

  Space efficiency improvement · CPC title

• G06F2212/7207

  management of metadata or control data · CPC title

• G06F2212/7201

  Logical to physical mapping or translation of blocks or pages · CPC title

• G06F11/1469

  Backup restoration techniques · CPC title