Incremental snapshot based technique on paged translation systems

Patent metadata

Field	Value
Publication number	US-10175896-B2
Application number	US-201615197131-A
Country	US
Kind code	B2
Filing date	Jun 29, 2016
Priority date	Jun 29, 2016
Publication date	Jan 8, 2019
Grant date	Jan 8, 2019

Abstract

A system comprising a processor and a memory storing instructions that, when executed, cause the system to identify a plurality of dump units associated with a translation table in a storage device, determine a plurality of snapshot markers associated with the plurality of dump units, calculate a first value of a first snapshot marker from the plurality of snapshot markers in the storage device, identify a second snapshot marker from an additional source, the second snapshot marker having a second value satisfying the first value, retrieve a dump unit associated with the second snapshot marker from the additional source, and reconstruct the translation table using the dump unit.

First claim

What is claimed is:

1. A method comprising:
identifying a plurality of dump units associated with a translation table in a storage device;
determining a plurality of snapshot markers associated with the plurality of dump units;
calculating a first value of a first snapshot marker from the plurality of snapshot markers in the storage device;
identifying a second snapshot marker from an additional source, the second snapshot marker having a second value after the first value;
retrieving a dump unit associated with the second snapshot marker from the additional source; and
reconstructing the translation table using the dump unit.

2. The method of claim 1 , wherein the first snapshot marker includes a free running incrementing counter value denoting a timestamp of sufficient granularity.

3. The method of claim 1 , wherein the first snapshot marker includes a counter value associated with an update of a reverse translation table, the counter value being incremented each time the reverse translation table is persisted.

4. The method of claim 1 , wherein the additional source is a meta-log and the first snapshot marker includes a counter value associated with a meta-log entry, the counter value being incremented each time a new meta-log entry is created.

5. The method of claim 1 , wherein the additional source includes a reverse translation table and a meta-log.

6. The method of claim 1 , further comprising:
receiving a request to reconstruct translation table statistics;
identifying a third snapshot marker from the additional source, the third snapshot marker being associated with a subset of dump groups and the third snapshot marker having a third value after the first value;
reading the subset of dump groups associated with the translation table from the additional source; and
reconstructing the translation table statistics using the subset of dump groups associated with the translation table.

7. The method of claim 1 , wherein the reconstruction of the translation table using the dump unit further comprises adding the dump unit to the translation table in memory.

8. A method comprising:
receiving a request to create a translation table entry;
logging the translation table entry in a meta-log;
incrementing a first value of a first snapshot marker associated with the meta-log;
updating a reverse translation table with the translation table entry;
determining whether the updated reverse translation table is persisted in a storage device; and
in response to determining that the updated reverse translation table is persisted in the storage device, incrementing a second snapshot marker associated with the reverse translation table.

9. The method of claim 8 , further comprising:
storing the first snapshot marker and the second snapshot marker in memory.

10. The method of claim 8 , wherein the first snapshot marker includes a free running counter value denoting a timestamp of sufficient granularity.

11. The method of claim 8 , wherein the first snapshot marker includes a counter associated with an update of a translation table, the counter being incremented each time the translation table is persisted.

12. The method of claim 8 , wherein an additional source is a meta-log and the first snapshot marker includes a counter value associated with a meta-log entry, the counter value being incremented each time a new meta-log entry is created.

13. The method of claim 8 , further comprising:
receiving a request to reconstruct translation table statistics;
identifying a third snapshot marker from an additional source, the third snapshot marker being associated with a subset of dump groups and the third snapshot marker having a third value after the first value;
reading the subset of dump groups associated with a translation table from the additional source; and
reconstructing the translation table statistics using the subset of dump groups associated with the translation table.

14. A system comprising:
a processor; and
a memory storing instructions that, when executed, cause the system to:
identify a plurality of dump units associated with a translation table in a storage device;
determine a plurality of snapshot markers associated with the plurality of dump units;
calculate a first value of a first snapshot marker from the plurality of snapshot markers in the storage device;
identify a second snapshot marker from an additional source, the second snapshot marker having a second value satisfying the first value;
retrieve a dump unit associated with the second snapshot marker from the additional source; and
reconstruct the translation table using the dump unit.

15. The system of claim 14 , wherein the first snapshot marker includes a free running counter denoting a timestamp of sufficient granularity.

16. The system of claim 14 , wherein the first snapshot marker includes a counter associated with an update of a reverse translation table, the counter being incremented each time the reverse translation table is persisted.

17. The system of claim 14 , wherein the additional source is a meta-log and the first snapshot marker includes a counter associated with a meta-log entry, the counter being incremented each time a new meta-log entry is created.

18. The system of claim 14 , wherein the additional source includes a reverse translation table and a meta-log.

19. The system of claim 14 , further comprising:
receiving a request to reconstruct translation table statistics;
identifying a third snapshot marker from the additional source, the third snapshot marker being associated with a subset of dump groups and the third snapshot marker having a third value satisfying the first value;
reading the subset of dump groups associated with the translation table from the additional source; and
reconstructing the translation table statistics using the subset of dump groups associated with the translation table.

20. The system of claim 14 , wherein the reconstruction of the translation table using the dump unit, further comprises adding the dump unit to the translation table in memory.

Assignees

• HGST Netherlands BV
• Western Digital Tech Inc

Inventors

• Battaje Ajith Kumar
• Goel Tanay
• Mishra Rajendra Prasad

Classifications

• G06F2212/702

  Conservative garbage collection · CPC title

• G06F3/065

  Replication mechanisms · CPC title

• G06F2212/68

  Details of translation look-aside buffer [TLB] · CPC title

• G06F3/0619 Primary

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

• G06F3/067

  Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS] · CPC title