Managing lookup operations of a metadata structure for a storage system

Patent metadata

Field	Value
Publication number	US-11960481-B2
Application number	US-202217853364-A
Country	US
Kind code	B2
Filing date	Jun 29, 2022
Priority date	Jun 29, 2022
Publication date	Apr 16, 2024
Grant date	Apr 16, 2024

Abstract

A storage control system receives a request to access target data and searches a primary metadata structure to find an associated metadata entry. The primary metadata structure comprises a log-structured merge tree comprising a first level of segments which comprises a group of segments having an associated group filter, and individual filters associated with respective segments of the group of segments. The storage control system searches the primary metadata structure by performing a lookup operation using the group filter to determine whether the associated metadata entry is potentially present in a given segment of the group of segments, and performing a lookup operation using the individual filters to identify the given segment of the group of segments which potentially includes the metadata entry, when the metadata entry is determined to be potentially present in a given segment of group of segments, using the group filter.

First claim

What is claimed is:

1. A method, comprising:
receiving, by a storage control system, an input/output (I/O) read request to access target data; and
searching, by the storage control system, a primary metadata structure to find a metadata entry associated with the target data, wherein the primary metadata structure comprises a log-structured merge tree comprising at least a first level of segments, wherein the at least first level of segments comprises at least one group of segments having an associated group filter which is configured to enable a search of metadata entries of segments within the at least one group of segments, and individual filters associated with respective segments of the at least one group of segments, wherein each individual filter is configured to enable a search of metadata entries of a respective one of the segments within the at least one group of segments, wherein searching the primary metadata structure comprises:
performing a lookup operation using the group filter to determine whether the metadata entry, which is associated with the target data, is potentially present in a given segment of the at least one group of segments; and
performing a lookup operation using the individual filters to identify the given segment of the at least one group of segments which potentially includes the metadata entry, in response to determining that the metadata entry is potentially present in a given segment of the at least one group of segments, as a result of the lookup operation using the group filter.

2. The method of claim 1 , wherein the primary metadata structure further comprises a B+ tree data structure which is configured to receive metadata entries that are merged out from a last level of the log-structured merge tree, and to enable random-access to the metadata entries using index keys.

3. The method of claim 2 , wherein searching the primary metadata structure further comprises performing, by the storage control system, a lookup operation using the B+ tree data structure to find the metadata entry which is associated with the target data, when the storage control system determines that the log-structured merge tree data structure does not have the metadata entry associated with the target data.

4. The method of claim 2 , wherein a size of the log-structured merge tree is significantly smaller than a size of the B+ tree data structure.

5. The method of claim 1 , further comprising:
merging, by the storage control system, the at least one group of segments into a new segment on a second level of the log-structured merge tree; and
designating, by the storage control system, the group filter associated with the at least one group of segments, as an individual filter for the new segment.

6. The method of claim 5 , further comprising generating, by the storage control system, a new group filter associated with a new group of segments which comprises at least the new segment.

7. The method of claim 1 , wherein:
the log-structured merge tree is configured to receive and accumulate metadata, which is written to a write cache, and organize the accumulated metadata in segments of metadata entries that are sorted by index keys; and
the write cache is implemented in one of (i) a non-volatile memory device of primary memory of a storage node and (ii) primary storage in which data is stored.

8. The method of claim 1 , wherein one or more of the individual filters and the group filter each comprise a Bloom filter.

9. 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:
receiving, by a storage control system, an input/output (I/O) read request to access target data; and
searching, by the storage control system, a primary metadata structure to find a metadata entry associated with the target data, wherein the primary metadata structure comprises a log-structured merge tree comprising at least a first level of segments, wherein the at least first level of segments comprises at least one group of segments having an associated group filter which is configured to enable a search of metadata entries of segments within the at least one group of segments, and individual filters associated with respective segments of the at least one group of segments, wherein each individual filter is configured to enable a search of metadata entries of a respective one of the segments within the at least one group of segments, wherein searching the primary metadata structure comprises:
performing a lookup operation using the group filter to determine whether the metadata entry, which is associated with the target data, is potentially present in a given segment of the at least one group of segments; and
performing a lookup operation using the individual filters to identify the given segment of the at least one group of segments which potentially includes the metadata entry, in response to determining that the metadata entry is potentially present in a given segment of the at least one group of segments, as a result of the lookup operation using the group filter.

10. The article of manufacture of claim 9 , wherein the primary metadata structure further comprises a B+ tree data structure which is configured to receive metadata entries that are merged out from a last level of the log-structured merge tree, and to enable random-access to the metadata entries using index keys.

11. The article of manufacture of claim 10 , wherein the program code for searching the primary metadata structure further comprises program code for performing, by the storage control system, a lookup operation using the B+ tree data structure to find the metadata entry which is associated with the target data, when the storage control system determines that the log-structured merge tree data structure does not have the metadata entry associated with the target data.

12. The article of manufacture of claim 10 , wherein a size of the log-structured merge tree is significantly smaller than a size of the B+ tree data structure.

13. The article of manufacture of claim 9 , further comprising program code which is executable by the one or more processors to implement a method which comprises:
merging, by the storage control system, the at least one group of segments into a new segment on a second level of the log-structured merge tree; and
designating, by the storage control system, the group filter associated with the at least one group of segments, as an individual filter for the new segment.

14. The article of manufacture of claim 13 , further comprising program code for generating a new group filter associated with a new group of segments which comprises at least the new segment.

15. The article of manufacture of claim 9 , wherein:
the log-structured merge tree is configured to receive and accumulate metadata, which is written to a write cache, and organize the accumulated metadata in segments of metadata entries that are sorted by index keys; and
the write cache is implemented in one of (i) a non-volatile memory device of primary memory of a storage node and (ii) primary storage in which data is stored.

16. The article of manufacture of claim 9 , wherein one or more of the individual filters and the group filter each comprise a Bloom filter.

17. An apparatus comprising:
at least one processor; and
memory configured to store program code, wherein the program code is executable by the at least one processor to in

Assignees

• Dell Products Lp

Inventors

• Shatsky Yosef
• Tal Doron

Classifications

• G06F16/245 Primary

  Query processing · CPC title

• G06F16/2246 Primary

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

• G06F16/285

  Clustering or classification · CPC title