Managing insert operations of a metadata structure for a storage system

Patent metadata

Field	Value
Publication number	US-11921714-B2
Application number	US-202217868045-A
Country	US
Kind code	B2
Filing date	Jul 19, 2022
Priority date	Jul 19, 2022
Publication date	Mar 5, 2024
Grant date	Mar 5, 2024

Abstract

A storage control system manages a storage metadata structure which comprises first and second tree structures. The first tree structure is configured to accumulate metadata entries associated with newly written data items, and sort the accumulated metadata entries by index keys. The second tree structure is configured to organize metadata entries using an index structure that enables random-access to the metadata entries using the index keys. The storage control system performs a merging process to merge metadata entries in leaf levels of the first and second tree structures, and performs a tree construction process to construct a third tree structure by populating a leaf level of the third tree structure with merged metadata entries from the leaf levels of the first and second tree structures. The storage metadata structure is updated to comprise the first tree structure, and the third tree structure in place of the second tree structure.

First claim

What is claimed is:

1. A method, comprising:
managing, by a storage control system, a storage metadata structure which comprises metadata entries associated with stored data items, wherein the storage metadata structure comprises a first tree data structure and a second tree data structure, wherein the first tree data structure is configured to accumulate metadata entries associated with newly written data items, and sort the accumulated metadata entries by index keys, and wherein the second tree data structure is configured to organize metadata entries using an index structure that enables random-access to the metadata entries using the index keys;
performing, by the storage control system, a merging process to merge metadata entries in a leaf level of the first tree data structure and a leaf level of the second tree data structure;
performing, by the storage control system, a tree construction process to construct a third tree data structure by populating a leaf level of the third tree data structure with merged metadata entries from the leaf levels of the first and second tree data structures; and
updating, by the storage control system, the storage metadata structure to comprise the first tree data structure, and the third tree data structure in place of the second tree data structure.

2. The method of claim 1 , wherein the second tree data structure and the third tree data structure each comprise a same type of tree data structure.

3. The method of claim 2 , wherein:
the first tree data structure comprises a log-structured merge tree data structure; and
the second tree data structure and the third tree data structure each comprise a B+ tree data structure.

4. The method of claim 1 , wherein performing the merging process comprises:
iterating over metadata entries in the leaf levels of the first and second tree data structures to logically sort the metadata entries in an order of key value; and
deleting older versions of metadata entries having key values that match key values of respective newer versions of metadata entries.

5. The method of claim 1 , wherein the merging process and the tree construction process are concurrently performed as part of a background process.

6. The method of claim 5 , wherein the storage metadata structure is updated to comprise the first tree data structure, and the third tree data structure in place of the second tree data structure, in response to completion of the background process.

7. The method of claim 5 , further comprising:
persisting, by the storage control system, a state of the background process at points in time during operation of the background process;
wherein persisting the state of the background process comprises utilizing, by the storage control system, a plurality of pointers that point to locations in the leaf levels of the first and second tree data structure, wherein the plurality of pointers are configured to provide an indication, at a given point in time, of which metadata entries in the leaf levels of the first and second tree data structures have not yet been added to the leaf level of the third tree data structure.

8. The method of claim 7 , wherein persisting the state of the background process comprises persisting, by the storage control system, an intermediate structure of the third tree data structure.

9. The method of claim 8 , further comprising utilizing, by the storage control system, the first tree data structure, the second tree data structure, and the intermediate structure of the third tree data structure to perform a lookup operation for a metadata entry at the given point in time during operation of the background process.

10. The method of claim 1 , wherein performing the tree construction process to construct the third tree data structure by populating a leaf level of the third tree data structure with merged metadata entries from the leaf levels of the first and second tree data structures comprises adding a pointer in the leaf level of the third tree data structure which points to an unmodified portion of the leaf level of the second tree data structure.

11. An article of manufacture comprising a non-transitory processor-readable storage medium having stored therein program code of one or more software programs, wherein the program code is executable by one or more processors to implement a method which comprises:
managing, by a storage control system, a storage metadata structure which comprises metadata entries associated with stored data items, wherein the storage metadata structure comprises a first tree data structure and a second tree data structure, wherein the first tree data structure is configured to accumulate metadata entries associated with newly written data items, and sort the accumulated metadata entries by index keys, and wherein the second tree data structure is configured to organize metadata entries using an index structure that enables random-access to the metadata entries using the index keys;
performing, by the storage control system, a merging process to merge metadata entries in a leaf level of the first tree data structure and a leaf level of the second tree data structure;
performing, by the storage control system, a tree construction process to construct a third tree data structure by populating a leaf level of the third tree data structure with merged metadata entries from the leaf levels of the first and second tree data structures; and
updating, by the storage control system, the storage metadata structure to comprise the first tree data structure, and the third tree data structure in place of the second tree data structure.

12. The article of manufacture of claim 11 , wherein:
the first tree data structure comprises a log-structured merge tree data structure; and
the second tree data structure and the third tree data structure each comprise a B+ tree data structure.

13. The article of manufacture of claim 11 , wherein the program code for performing the merging process comprises program code for:
iterating over metadata entries in the leaf levels of the first and second tree data structures to logically sort the metadata entries in an order of key value; and
deleting older versions of metadata entries having key values that match key values of respective newer versions of metadata entries.

14. The article of manufacture of claim 11 , wherein:
the merging process and the tree construction process are concurrently performed as part of a background process; and
the storage metadata structure is updated to comprise the first tree data structure, and the third tree data structure in place of the second tree data structure, in response to completion of the background process.

15. The article of manufacture of claim 14 , further comprising program code that is executable by the one or more processors to implement a method which comprises:
persisting, by the storage control system, a state of the background process at points in time during operation of the background process;
wherein persisting the state of the background process comprises utilizing, by the storage control system, a plurality of pointers that point to locations in the leaf levels of the first and second tree data structure, wherein the plurality of pointers are configured to provide an indication, at a given point in time, of which metadata entries in the leaf levels of the first and second tree data structures have not yet been added to the leaf level of the third tree data structure; and
wherein persisting the state of the background process comprises persisting, by the storage control system, an intermediate structure

Assignees

• Dell Products Lp

Inventors

• Shatsky Yosef
• Tal Doron

Classifications

• G06F16/244 Primary

  Grouping and aggregation · CPC title

• G06F16/2246

  Trees, e.g. B+trees · CPC title

• G06F16/24573

  using data annotations, e.g. user-defined metadata · CPC title

• G06F16/13 Primary

  File access structures, e.g. distributed indices (arrangements of input from, or output to, record carriers G06F3/06) · CPC title