Method and system for tracking modification times of data in a storage system

Patent metadata

Field	Value
Publication number	US-9378149-B1
Application number	US-201414473243-A
Country	US
Kind code	B1
Filing date	Aug 29, 2014
Priority date	Aug 29, 2014
Publication date	Jun 28, 2016
Grant date	Jun 28, 2016

Abstract

A method for rebuilding an in-memory data structure. The method includes selecting a table of contents (TOC) entry of a TOC page in persistent storage, where the TOC entry includes an object identifier (ID) of an object, an offset ID, and a birth time. The method further includes determining, based on the object ID, that the in-memory data structure includes object metadata for the object including a mod time and an object map pointer to an object map tree. The method further includes that the birth time in the TOC entry is greater than the mod time, updating a stored physical address in the object map tree based on the offset ID to a physical address derived from the TOC entry; and updating the mod time stored in the object metadata to the birth time.

First claim

What is claimed is:

1. A method for rebuilding an in-memory data structure, comprising:
selecting a first table of contents (TOC) entry of a TOC page of a block in persistent storage, wherein the first TOC entry comprises a first object identifier (ID) of a first object, a first offset ID, and a first birth time;
determining, based on the first object ID, that the in-memory data structure comprises a first object metadata for the first object comprising a first mod time and a first object map pointer to a first object map tree;
determining, based on the first birth time, that the first birth time in the first TOC entry is greater than the first mod time of the first object;
updating, after determining the first object metadata exists and after determining that the first birth time is greater than the first mod time, a first stored physical address in the first object map tree based on the first offset ID to a first physical address derived from the first TOC entry; and
updating, after determining that the first birth time is greater than the first mod time, the first mod time stored in the first object metadata to the first birth time.

2. The method of claim 1 , further comprising:
selecting a second TOC entry of the TOC page of the block in the persistent storage, wherein the second TOC entry comprises the first object ID of the first object, the first offset ID, and a second birth time; and
determining, based on the second birth time, that the second birth time in the second TOC entry is not greater than the first mod time of the first object.

3. The method of claim 1 , further comprising:
selecting a second TOC entry of the TOC page of the block in the persistent storage, wherein the second TOC entry comprises a second object ID of a second object, a second offset ID, and a second birth time;
determining, based on the second object ID, that the in-memory data structure does not comprise a second object metadata for the second object;
creating, based on the second object ID, the second object metadata in the in-memory data structure;
populating the second object metadata with the second object ID, a size, a second mod time, a fragment size, and a second object map pointer;
creating a second object map tree referenced by the second object map pointer;
updating, after creating the second object map tree, a second stored physical address in the second object map tree based on the second offset ID to a second physical address derived from the second TOC entry; and
updating, after populating the second object, the second mod time to the second birth time.

4. The method of claim 1 , wherein the first object metadata comprises the first object map pointer to the first object map tree, a size, the first mod time, the first object ID, a fragment size, and a type field.

5. The method of claim 4 , wherein the type field comprises a modification type, wherein the modification type is at least one selected from a group consisting of updating, cropping, and trimming.

6. The method of claim 1 , wherein the first TOC entry further comprises at least one selected from a group consisting of a fragment size, a page ID, a byte, and a type field.

7. The method of claim 1 , wherein the first object map tree comprises a pointer level comprising a plurality of pointers, and wherein the plurality of pointers reference a plurality of physical addresses comprising the first stored physical address.

8. The method of claim 7 , wherein the first stored physical address is located within the first object map tree by determining a pointer of the plurality of pointers that references the first stored physical address based on a function of the first offset ID and a fragment size.

9. The method of claim 1 , wherein the in-memory data structure is an array of a plurality of object metadata comprising the first object metadata.

10. The method of claim 1 , wherein the block is located in a solid state memory module, and wherein the in-memory data structure is located in memory external to the solid state memory module.

11. The method of claim 1 , wherein the persistent storage comprises solid state memory.

12. A non-transitory computer readable medium comprising instructions, which when executed by a processor perform a method, the method comprising:
selecting a first table of contents (TOC) entry of a TOC page of a block in persistent storage, wherein the first TOC entry comprises a first object identifier (ID) of a first object, a first offset ID, and a first birth time;
determining, based on the first object ID, that the in-memory data structure comprises a first object metadata for the first object comprising a first mod time and a first object map pointer to a first object map tree;
determining, based on the first birth time, that the first birth time in the first TOC entry is greater than the first mod time of the first object;
updating, after determining the first object metadata exists and after determining that the first birth time is greater than the first mod time, a first stored physical address in the first object map tree based on the first offset ID to a first physical address derived from the first TOC entry; and
updating, after determining that the first birth time is greater than the first mod time, the first mod time stored in the first object metadata to the first birth time.

13. The non-transitory computer readable medium of claim 12 , the method further comprising:
selecting a second TOC entry of the TOC page of the block in the persistent storage, wherein the second TOC entry comprises a second object ID of a second object, a second offset ID, and a second birth time;
determining, based on the second object ID, that the in-memory data structure does not comprise a second object metadata for the second object;
creating, based on the second object ID, the second object metadata in the in-memory data structure;
populating the second object metadata with the second object ID, a size, a second mod time, a fragment size, and a second object map pointer;
creating a second object map tree referenced by the second object map pointer;
updating, after creating the second object map tree, a second stored physical address in the second object map tree based on the second offset ID to a second physical address derived from the second TOC entry; and
updating, after populating the second object, the second mod time to the second birth time.

14. The non-transitory computer readable medium of claim 12 , the method further comprising:
selecting a second TOC entry of the TOC page of the block in the persistent storage, wherein the second TOC entry comprises the first object ID of the first object, the first offset ID, and a second birth time; and
determining, based on the second birth time, that the second birth time in the second TOC entry is not greater than the first mod time of the first object.

15. The non-transitory computer readable medium of claim 12 , wherein the first object metadata comprises the first object map pointer to the first object map tree, a size, the first mod time, the first object ID, a fragment size, and a type field.

16. The non-transitory computer readable medium of claim 12 , wherein the first TOC entry further comprises at least one selected from a group consisting of a fragment size, a page ID, a byte, and a type field.

17. The non-transitory computer readable medium of claim 12 , wherein the first object map tree comprises a pointer level comprising a plurality of pointers, and wherein the plurality of pointers reference a plurality of physical

Assignees

• Bonwick Jeffrey S
• Emc Corp

Inventors

• Bonwick Jeffrey S

Classifications

• G06F2212/7201

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

• G06F2212/65

  Details of virtual memory and virtual address translation · CPC title

• G06F12/0246 Primary

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

• G06F12/1009 Primary

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

• G06F2212/7207

  management of metadata or control data · CPC title