Granted Patent B1

US 12,326,834 · App. 18/428,615 · Granted Jun 10, 2025

Inventors: Anirudh Kumar (San Jose, CA); Namit Sharma (San Jose, CA); Avinash Nath Aita (San Jose, CA); Samanvitha Reddy Panyam (Sunnyvale, CA)

Assignee: Cohesity, Inc.

G06F16/128G06F16/185

Abstract

Claims (65)

1. A method comprising:

identifying, by a data platform implemented by a computing system, a plurality of leaf nodes and a plurality of intermediate nodes in tree data corresponding to a snapshot of a storage system, wherein:

the plurality of intermediate nodes each comprise one or more pointers identifying one or more of the plurality of leaf nodes; and

the plurality of leaf nodes each include an indication of file system data of the storage system;

determining, by the data platform, a checksum for each of the plurality of leaf nodes;

determining, by the data platform, a checksum for each intermediate node of the plurality of intermediate nodes based on the respective checksums of the one or more of the plurality of leaf nodes identified by the one or more pointers of the intermediate node; and

storing, by the data platform, the checksum for each of the plurality of leaf nodes and the checksum for each of the plurality of intermediate nodes.

2. The method of claim 1 , further comprising:

determining, by the data platform, a validation checksum for a first intermediate node of the plurality of intermediate nodes based on the checksum of the one or more of the plurality of leaf nodes identified by the one or more pointers of the first intermediate node;

comparing the validation checksum for the first intermediate node to the checksum for the first intermediate node stored by the data platform; and

outputting, by a user interface of the computing system, an indication an integrity of the snapshot based on the comparison.

3. The method of claim 2 , wherein the intermediate node comprises a plurality of pointers identifying at least two of the plurality of leaf nodes.

4. The method of claim 1 , further comprising:

identifying, by the data platform, a root node in the tree data, wherein the root node comprises a plurality of pointers identifying the plurality of intermediate nodes; and

determining, by the data platform, a checksum for the root node based on the checksum of the plurality of intermediate nodes identified by the plurality of pointers of the root node.

5. The method of claim 1 , wherein determining the checksum for each of the plurality of leaf nodes and determining the checksum for each of the plurality of intermediate nodes comprises traversing the tree data in a post-order sequence and the checksum for each of the plurality of leaf nodes and the checksum for each of the plurality of intermediate nodes are determined according to the post-order sequence.

6. The method of claim 1 , wherein:

identifying the plurality of leaf nodes comprises identifying a subset of leaf nodes in the tree data associated with a change to the file system data of the storage system; and

identifying the plurality of intermediate nodes comprises identifying a subset of intermediate nodes in the tree data comprising the one or more pointers to the subset of leaf nodes in the tree data associated with a change to the file system data of the storage system.

7. The method of claim 1 , wherein:

identifying the plurality of leaf nodes comprises identifying a plurality of cloned leaf nodes in the tree data associated with a change to the file system data of the storage system; and

identifying the plurality of intermediate nodes comprises identifying a subset of intermediate nodes in the tree data comprising the one or more pointers to the plurality of cloned leaf nodes in the tree data associated with a change to the file system data of the storage system.

8. The method of claim 1 , wherein the tree data is first tree data and the indication of the file system data of the storage system in the plurality of leaf nodes includes an indication of second tree data comprising one or more leaf nodes including the file system data.

9. The method of claim 8 , further comprising determining, for each of the plurality of leaf nodes, a checksum for the second tree data based on the file system data in the one or more leaf nodes of the second tree data, wherein determining the checksum for each leaf node of the plurality of leaf nodes in the first tree data includes determining the checksum for the second tree data indicated in the leaf node.

10. A computing system comprising:

a memory storing instructions; and

processing circuitry that executes the instructions to:

identify a plurality of leaf nodes and a plurality of intermediate nodes in tree data corresponding to a snapshot of a storage system, wherein:

the plurality of intermediate nodes each comprise one or more pointers identifying one or more of the plurality of leaf nodes; and

the plurality of leaf nodes each include an indication of file system data of the storage system;

determine a checksum for each of the plurality of leaf nodes;

determine a checksum for each intermediate node of the plurality of intermediate nodes based on the respective checksums of the one or more of the plurality of leaf nodes identified by the one or more pointers of the intermediate node; and

store the checksum for each of the plurality of leaf nodes and the checksum for each of the plurality of intermediate nodes.

11. The computing system of claim 10 , wherein the processing circuitry further executes the instructions to:

determine a validation checksum for a first intermediate node of the plurality of intermediate nodes based on the checksum of the one or more of the plurality of leaf nodes identified by the one or more pointers of the first intermediate node;

compare the validation checksum for the first intermediate node to the checksum for the first intermediate node stored by the processing circuitry; and

output, via a user interface of the computing system, an indication an integrity of the snapshot based on the comparison.

12. The computing system of claim 11 , wherein the intermediate node comprises a plurality of pointers identifying at least two of the plurality of leaf nodes.

13. The computing system of claim 10 , wherein the processing circuitry further executes the instructions to:

identify a root node in the tree data, wherein the root node comprises a plurality of pointers identifying the plurality of intermediate nodes; and

determine a checksum for the root node based on the checksum of the plurality of intermediate nodes identified by the plurality of pointers of the root node.

14. The computing system of claim 10 , wherein:

to determine the checksum for each of the plurality of leaf nodes and determine the checksum for each of the plurality of intermediate nodes the processing circuitry further executes the instructions to traverse the tree data in a post-order sequence; and

the checksum for each of the plurality of leaf nodes and the checksum for each of the plurality of intermediate nodes are determined according to the post-order sequence.

15. The computing system of claim 10 , wherein:

to identify the plurality of leaf nodes the processing circuitry further executes the instructions to identify a subset of leaf nodes in the tree data associated with a change to the file system data of the storage system; and

to identify the plurality of intermediate nodes the processing circuitry further executes the instructions to identify a subset of intermediate nodes in the tree data comprising the one or more pointers to the subset of leaf nodes in the tree data associated with a change to the file system data of the storage system.

16. The computing system of claim 10 , wherein:

to identify the plurality of leaf nodes the processing circuitry further executes the instructions to identify a plurality of cloned leaf nodes in the tree data associated with a change to the file system data of the storage system; and

to identify the plurality of intermediate nodes the processing circuitry further executes the instructions to identify a subset of intermediate nodes in the tree data comprising the one or more pointers to the plurality of cloned leaf nodes in the tree data associated with a change to the file system data of the storage system.

17. The computing system of claim 10 , wherein the tree data is first tree data and the indication of the file system data of the storage system in the plurality of leaf nodes includes an indication of second tree data comprising one or more leaf nodes including the file system data.

18. The computing system of claim 17 , wherein:

the processing circuitry further executes the instructions to determine for each of the plurality of leaf nodes a checksum for the second tree data based on the file system data in the one or more leaf nodes of the second tree data; and

determining the checksum for each leaf node of the plurality of leaf nodes in the first tree data includes determining the checksum for the second tree data indicated in the leaf node.

19. Non-transitory computer-readable storage media comprising instructions that, when executed, cause processing circuitry of a computing system to:

identify a plurality of leaf nodes and a plurality of intermediate nodes in tree data corresponding to a snapshot of a storage system, wherein:

the plurality of intermediate nodes each comprise one or more pointers identifying one or more of the plurality of leaf nodes; and

the plurality of leaf nodes each include an indication of file system data of the storage system;

determine a checksum for each of the plurality of leaf nodes;

determine a checksum for each intermediate node of the plurality of intermediate nodes based on the respective checksums of the one or more of the plurality of leaf nodes identified by the one or more pointers of the intermediate node; and

store the checksum for each of the plurality of leaf nodes and the checksum for each of the plurality of intermediate nodes.

20. The non-transitory computer-readable storage media of claim 19 , wherein, when further executed, the instructions cause the processing circuitry of the computing system to:

determine a validation checksum for a first intermediate node of the plurality of intermediate nodes based on the checksum of the one or more of the plurality of leaf nodes identified by the one or more pointers of the first intermediate node;

compare the validation checksum for the first intermediate node to the checksum for the first intermediate node stored by the processing circuitry; and

output, via a user interface of the computing system, an indication an integrity of the snapshot based on the comparison.

Assignments (2)

References Cited (9)