# US 2021/0342298 A1 · Finding storage objects of a snapshot group pointing to a logical page in a logical address space of 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 2021/0342298 A1
- Document ID: US20210342298A1
- Status: Published application
- Kind: A1
- Application number: 16/862,733
- Filed: 2020-04-30
- Published: 2021-11-04
- Earliest claimed: 2020-04-30
- Assignees: EMC IP Holding Company LLC
- Applicants: EMC IP Holding Company LLC
- Inventors: Alexander S. Mathews; Dixitkumar Vishnubhai Patel
- Web page: https://patentgrep.com/patent/US20210342298A1

## CPC

- G06F 16/128: {Details of file system snapshots on the file-level, e.g. snapshot creation, administration, deletion (error detection or correction of the data by redundancy in operations or in hardware G06F11/14, G06F11/16)}
- G06F 16/188: Virtual file systems
- G06F 16/2246: {Trees, e.g. B+trees}
- G06F 16/2255: {Hash tables}
- G06F 16/24: Querying
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

An apparatus comprises a processing device configured to generate a tree structure characterizing relationships between storage objects in a storage system represented as logical page nodes specifying respective logical page addresses, arrays of pointers to other logical page addresses, snapshot group identifiers, and logical extent offsets. The processing device is also configured to traverse the generated tree structure to identify (i) a given logical page node specifying a given logical page address, snapshot group identifier and logical extent offset from a query and (ii) other ones of the logical page nodes that specify the given snapshot group identifier and logical extent offset and comprise a pointer to the given logical page address in its associated array of pointers. The processing device is further configured to provide a response to the query specifying the given logical page node and the identified other ones of the logical page nodes.

## Claims

### Claim 1

An apparatus comprising:
at least one processing device comprising a processor coupled to a memory;
the at least one processing device being configured to perform steps of:
generating a tree structure characterizing relationships between a plurality of storage objects in a storage system, the tree structure comprising a plurality of logical page nodes representing the plurality of storage objects, the plurality of logical page nodes specifying respective logical page addresses in a logical address space of the storage system, arrays of pointers to one or more other logical page addresses in the logical address space, snapshot group identifiers for snapshot groups in the storage system, and logical extent offsets in the logical address space;
receiving a query comprising a given logical page address, a given snapshot group identifier for a given one of the snapshot groups, and a given logical extent offset;
traversing the generated tree structure to identify: (i) whether the generated tree structure comprises a given logical page node specifying the given logical page address, the given snapshot group identifier, and the given logical extent offset; and (ii) one or more other ones of the plurality logical page nodes that specify the given snapshot group identifier and the given logical extent offset and comprise a pointer to the given logical page address in its associated array of pointers; and
providing a response to the query specifying the given logical page node and the identified other ones of the plurality of logical page nodes.

### Claim 2 (depends on 1)

The apparatus of claim 1 wherein the logical address space is organized as a B-tree comprising a leaf logical page level and one or more additional logical page levels above the leaf logical page level.

### Claim 3 (depends on 2)

The apparatus of claim 2 wherein the generated tree structure comprises a hash of binary trees arranging the plurality of logical page nodes into the leaf logical page level and the one or more additional logical page levels above the leaf logical page level.

### Claim 4 (depends on 3)

The apparatus of claim 3 wherein the one or more additional logical page levels comprise:
a middle page level comprising middle pages associated with respective subsets of leaf pages in the leaf page level; and
a top page level comprising top pages associated with respective subsets of the middle page in the middle page level.

### Claim 5 (depends on 4)

The apparatus of claim 4 wherein a given one of the top pages represents an n*m sized portion of the logical address space that references n middle pages in the middle page level each representing an m sized portion of the logical address space, a given one of the middle pages referencing n leaf pages in the leaf page level each representing an m/n sized portion of the logical address space.

### Claim 6 (depends on 5)

The apparatus of claim 5 wherein n is 512 and m is one gigabyte.

### Claim 7 (depends on 4)

The apparatus of claim 4 wherein traversing the generated tree structure comprises iterating over storage objects corresponding to a given logical storage volume starting with one of the plurality of logical page nodes corresponding to a top page in the top page level for the given logical storage volume.

### Claim 8 (depends on 4)

The apparatus of claim 4 wherein traversing the generated tree structure further comprises iterating over storage objects corresponding to one or more snapshots of the given logical storage volume starting with ones of the plurality of logical page nodes corresponding to top pages in the top page level for snapshot volumes of the given logical storage volume.

### Claim 9 (depends on 1)

The apparatus of claim 1 wherein the plurality of logical page nodes further specify namespace addresses associated with respective storage objects in the storage system.

### Claim 10 (depends on 9)

The apparatus of claim 9 wherein traversing the generated tree structure comprises iterating over the plurality of logical page nodes vertically starting with the identified ones of the plurality of logical page nodes specifying namespace addresses corresponding to storage objects in the given snapshot group.

### Claim 11 (depends on 10)

The apparatus of claim 10 wherein the identified ones of the plurality of logical page nodes specifying namespace addresses corresponding to storage objects in the given snapshot group comprises a first one of the plurality of logical page nodes corresponding to a logical storage volume in the given snapshot group and at least a second one of the plurality of logical page nodes corresponding to at least one snapshot of the logical storage volume in the given snapshot group.

### Claim 12 (depends on 1)

The apparatus of claim 1 wherein receiving the query comprises generating the query in response to identifying the given logical page address as being one of corrupted and orphaned during a file system check of the storage system.

### Claim 13 (depends on 1)

The apparatus of claim 1 wherein the given logical page address corresponds to a corrupted logical page in the logical address space, and wherein the response to the query provides a corrupted range bitmap in the logical address space.

### Claim 14 (depends on 1)

The apparatus of claim 1 wherein the given logical page address corresponds to a corrupted logical page in the logical address space, wherein the given logical page node is in a given level of the generated tree structure, and wherein the at least one processing device is further configured fix the corrupted logical page utilizing one or more logical page nodes in the given subset of the plurality of logical page nodes having horizontal relationships to the given logical page node in the given level of the generated tree structure.

### Claim 15

A computer program product comprising a non-transitory processor-readable storage medium having stored therein program code of one or more software programs, wherein the program code when executed by at least one processing device causes the at least one processing device to perform steps of:
generating a tree structure characterizing relationships between a plurality of storage objects in a storage system, the tree structure comprising a plurality of logical page nodes representing the plurality of storage objects, the plurality of logical page nodes specifying respective logical page addresses in a logical address space of the storage system, arrays of pointers to one or more other logical page addresses in the logical address space, snapshot group identifiers for snapshot groups in the storage system, and logical extent offsets in the logical address space;
receiving a query comprising a given logical page address, a given snapshot group identifier for a given one of the snapshot groups, and a given logical extent offset;
traversing the generated tree structure to identify: (i) whether the generated tree structure comprises a given logical page node specifying the given logical page address, the given snapshot group identifier, and the given logical extent offset; and (ii) one or more other ones of the plurality logical page nodes that specify the given snapshot group identifier and the given logical extent offset and comprise a pointer to the given logical page address in its associated array of pointers; and
providing a response to the query specifying the given logical page node and the identified other ones of the plurality of logical page nodes.

### Claim 16 (depends on 15)

The computer program product of claim 15 wherein receiving the query comprises generating the query in response to identifying the given logical page address as being one of corrupted and orphaned during a file system check of the storage system.

### Claim 17 (depends on 15)

The computer program product of claim 15 wherein the given logical page address corresponds to a corrupted logical page in the logical address space, and wherein the response to the query provides a corrupted range bitmap in the logical address space.

### Claim 18

A method comprising steps of:
generating a tree structure characterizing relationships between a plurality of storage objects in a storage system, the tree structure comprising a plurality of logical page nodes representing the plurality of storage objects, the plurality of logical page nodes specifying respective logical page addresses in a logical address space of the storage system, arrays of pointers to one or more other logical page addresses in the logical address space, snapshot group identifiers for snapshot groups in the storage system, and logical extent offsets in the logical address space;
receiving a query comprising a given logical page address, a given snapshot group identifier for a given one of the snapshot groups, and a given logical extent offset;
traversing the generated tree structure to identify: (i) whether the generated tree structure comprises a given logical page node specifying the given logical page address, the given snapshot group identifier, and the given logical extent offset; and (ii) one or more other ones of the plurality logical page nodes that specify the given snapshot group identifier and the given logical extent offset and comprise a pointer to the given logical page address in its associated array of pointers; and
providing a response to the query specifying the given logical page node and the identified other ones of the plurality of logical page nodes;
wherein the method is performed by at least one processing device comprising a processor coupled to a memory.

### Claim 19 (depends on 18)

The method of claim 18 wherein receiving the query comprises generating the query in response to identifying the given logical page address as being one of corrupted and orphaned during a file system check of the storage system.

### Claim 20 (depends on 18)

The method of claim 18 wherein the given logical page address corresponds to a corrupted logical page in the logical address space, and wherein the response to the query provides a corrupted range bitmap in the logical address space.
