# US 2024/0004877 A1 · Managing lookup operations of a metadata structure for a storage system

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2024/0004877 A1
- Document ID: US20240004877A1
- Status: Published application
- Kind: A1
- Application number: 17/853,364
- Filed: 2022-06-29
- Published: 2024-01-04
- Earliest claimed: 2022-06-29
- Assignees: Dell Products L.P.
- Applicants: Dell Products L.P.
- Inventors: Yosef Shatsky; Doron Tal
- Web page: https://patentgrep.com/patent/US20240004877A1

## CPC

- G06F 16/245: Query processing
- G06F 16/2246: {Trees, e.g. B+trees}
- G06F 16/285: {Clustering or classification}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## 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.

## Claims

### Claim 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, and individual filters associated with respective segments of 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, using the group filter.

### Claim 2 (depends on 1)

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

### Claim 3 (depends on 2)

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.

### Claim 4 (depends on 2)

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

### Claim 5 (depends on 1)

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.

### Claim 6 (depends on 5)

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.

### Claim 7 (depends on 1)

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.

### Claim 8 (depends on 1)

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

### Claim 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, and individual filters associated with respective segments of 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, using the group filter.

### Claim 10 (depends on 9)

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 merged out from a last level of the log-structured merge tree, and to enable random-access to the metadata entries using index keys.

### Claim 11 (depends on 10)

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.

### Claim 12 (depends on 10)

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

### Claim 13 (depends on 9)

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.

### Claim 14 (depends on 13)

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.

### Claim 15 (depends on 9)

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.

### Claim 16 (depends on 9)

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

### Claim 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 instantiate a storage control system, wherein the storage control system is configured to:
receive an input/output (I/O) read request to access target data; and
search 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, and individual filters associated with respective segments of the at least one group of segments, wherein in searching the primary metadata structure, the storage control system is configured to:
perform 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
perform 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, using the group filter.

### Claim 18 (depends on 17)

The apparatus of claim 17, wherein:
the primary metadata structure further comprises a B+ tree data structure which is configured to receive metadata entries merged out from a last level of the log-structured merge tree, and to enable random-access to the metadata entries using index keys; and
in searching the primary metadata structure, the storage control system is further configured to perform 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.

### Claim 19 (depends on 17)

The apparatus of claim 17, wherein the storage control system is further configured to:
merge the at least one group of segments into a new segment on a second level of the log-structured merge tree; and
designate the group filter associated with the at least one group of segments, as an individual filter for the new segment.

### Claim 20 (depends on 19)

The apparatus of claim 19, wherein the storage control system is further configured to generate a new group filter associated with a new group of segments which comprises at least the new segment.
