Finding storage objects of a snapshot group pointing to a logical page in a logical address space of a storage system
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.
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.
2. 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.
3. 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.
4. 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.
5. 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.
6. The apparatus of claim 5 wherein n is 512 and m is one gigabyte.
7. 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.
8. 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.
9. 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.
10. 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.
11. 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.
12. 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.
13. 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.
14. 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.
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.
16. 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.
17. 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.
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.
19. 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.
20. 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.