Managing backup of logical-to-physical translation information to control boot-time and write amplification

Patent metadata

Field	Value
Publication number	US-10162561-B2
Application number	US-201615190216-A
Country	US
Kind code	B2
Filing date	Jun 23, 2016
Priority date	Mar 21, 2016
Publication date	Dec 25, 2018
Grant date	Dec 25, 2018

Abstract

An apparatus includes an interface and a processor. The interface is configured to communicate with a non-volatile memory. The processor is configured to hold a translation table that maps between logical addresses and respective physical addresses in the non-volatile memory, to back-up to the non-volatile memory a baseline version of the translation table in one or more bulks, to additionally back-up to the non-volatile memory one or more incremental updates, which specify changes relative to the baseline version of the translation table caused by subsequent storage operations, to determine a maximal number of the incremental updates that, when recovered together with the baseline version from the non-volatile memory and replayed in the processor, meets a target recovery time of the translation table, and to set a number of the backed-up incremental updates to not exceed the maximal number.

First claim

The invention claimed is:

1. An apparatus, comprising:
at least one non-volatile memory;
at least one processor; and
at least one memory storing instructions that, when executed by the at least one processor, cause the apparatus to:
manage a translation table that maps logical addresses to respective physical addresses of the at least one non-volatile memory;
divide the translation table into a plurality of baseline portions;
periodically and successively store the plurality of baseline portions to the at least one non-volatile memory;

determine a maximal number of incremental updates that, when recovered together with the translation table from the at least one non-volatile memory and replayed by the apparatus, satisfies a target recovery time of the translation table; and
periodically store the maximal number of incremental updates to the at least one non-volatile memory, wherein each incremental update specifies changes to a respective baseline portion of the translation table caused by storage operations that take place between periodically and successively storing the plurality of baseline portions.

2. The apparatus of claim 1 , wherein an incremental update is associated with an estimated replay time, and the maximal number of incremental updates is based on the estimated replay time.

3. The apparatus of claim 1 , wherein the at least one processor further causes the apparatus to:
determine the maximal number of incremental updates by evaluating a remaining time of the target recovery time for loading and replaying the incremental updates, with an assumption that the translation table is loaded.

4. The apparatus of claim 1 , wherein the at least one processor further causes the apparatus to:
select a differential number of the incremental updates allowed between periodically and successively storing the baseline portions based on a baseline portion size so as to meet the target recovery time and to sustain a workload performance of the apparatus.

5. The apparatus of claim 4 , wherein the at least one processor further causes the apparatus to:
select the differential number based on a fragmentation level of the translation table.

6. The apparatus of claim 1 , wherein periodically and successively storing the plurality of baseline portions to the at least one non-volatile memory comprises:
in response to successively storing at least two baseline portions of the translation table into the at least one non-volatile memory:
updating information stored in the at least one non-volatile memory that indicates a last-stored baseline portion of the translation table.

7. The apparatus of claim 1 , wherein the at least one processor further causes the apparatus to:
identify a write activity profile associated with the apparatus, wherein the write activity profile comprises a mixture of random activity and sequential activity, and the maximal number of incremental updates is based on the write activity profile.

8. A method implemented by a computing device, the method comprising:
managing a translation table that maps logical addresses to respective physical addresses of at least one non-volatile memory that communicably coupled to the computing device;
dividing the translation table into a plurality of baseline portions;
periodically and successively storing the plurality of baseline portions to the at least one non-volatile memory;
determining a maximal number of incremental updates that, when recovered together with the translation table from the at least one non-volatile memory and replayed by the computing device, satisfies a target recovery time of the translation table; and
periodically storing the maximal number of incremental updates to the at least one non-volatile memory, wherein each incremental update specifies changes to a respective baseline portion of the translation table caused by storage operations that take place between periodically and successively storing the plurality of baseline portions.

9. The method of claim 8 , wherein an incremental update is associated with an estimated replay time, and the maximal number of incremental updates is based on the estimated replay time.

10. The method of claim 8 , further comprising:
determining the maximal number of incremental updates by evaluating a remaining time of the target recovery time for loading and replaying the incremental updates, with an assumption that the translation table is loaded.

11. The method of claim 8 , further comprising: select a differential number of the incremental updates avowed between periodically and successively storing the baseline portions based on a baseline portion size so as to meet the target recovery time and to sustain a workload performance of the computing device.

12. The method of claim 11 , further comprising:
selecting the differential number based on a fragmentation level of the translation table.

13. The method of claim 8 , wherein periodically and successively storing the plurality of baseline portions to the at least one non-volatile memory comprises:
in response to successively storing at least two baseline portions of the translation table into the at least one non-volatile memory;
updating information stored in the at least one non-volatile memory that indicates a last-stored baseline portion of the translation table.

14. The method of claim 8 , further comprising:
identifying a write activity profile associated with the computing device, wherein the write activity profile comprises a mixture of random activity and sequential activity, and the maximal number of incremental updates is based on the write activity profile.

15. At least one non-transitory computer readable storage medium configured to store instructions that, when executed by at least one processor included in a computing device, cause the computing device to carry out steps that include:
managing a translation table that maps logical addresses to respective physical addresses of at least one non-volatile memory that is communicably coupled to the computing device;
dividing the translation table into a plurality of baseline portions;
periodically and successively storing the plurality of baseline portions to the at least one non-volatile memory;
determining a maximal number of incremental updates that, when recovered together with the translation table from the at least one non-volatile memory and replayed by the computing device, satisfies a target recovery time of the translation table; and
periodically storing the maximal number of incremental updates to the at least one non-volatile memory, wherein each incremental update specifies changes to a respective baseline portion of the translation table caused by storage operations that take place between periodically and successively storing the plurality of baseline portions.

16. The at least one non-transitory computer readable storage medium of claim 15 , wherein an incremental update is associated with an estimated replay time, and the maximal number of incremental updates is based on the estimated replay time.

17. The at least one non-transitory computer readable storage medium of claim 15 , wherein the steps further include:
determining the maximal number of incremental updates by evaluating a remaining time of the target recovery time for loading and replaying the incremental updates, with an assumption that the translation table is loaded.

18. The at least one non-transitory computer readable storage medium of claim 15 , wherein the steps further include:
select a differential num

Assignees

• Apple Inc

Inventors

• Paley Alexander
• Liu Yuhua

Classifications

• G06F11/1441 Primary

  Resetting or repowering · CPC title

• G06F12/1009

  using page tables, e.g. page table structures · CPC title

• G06F2212/7201

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

• G06F12/0246 Primary

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

• G06F2212/202

  Non-volatile memory · CPC title