Granted Patent B1

US 12,645,550 · App. 18/428,551 · Granted Jun 2, 2026

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.

G06F11/1471G06F11/1469G06F16/2246G06F2201/80G06F2201/84

Abstract

Claims (68)

1 . A method comprising:

identifying, by a data platform implemented by a computing system, a first tree data structure corresponding to a first snapshot of at least a first portion of a storage system at a first time;

identifying, by the data platform, a second tree data structure corresponding to a second snapshot of at least a second portion of the storage system at a second later time;

synchronously traversing, by the data platform, the first tree data structure and the second tree data structure to identify one or more deleted keys indicative of deleted data that has been previously stored by the storage system at the first time and has been deleted from the storage system; and

performing, by the data platform and based on the one or more deleted keys, a data protection operation.

2 . The method of claim 1 ,

wherein the first tree data structure includes a first root node, one or more first child nodes, and one or more first edges interconnecting the first root node to one or more first child nodes, and

wherein the second tree data structure includes a second root node, at least one second child node, and a plurality of second edges interconnecting the second root node to the at least one second child node and to at least one of the one or more first child nodes of the first tree data structure.

3 . The method of claim 1 , wherein synchronously traversing the first tree data structure and the second tree data structure comprises:

initializing a first iterator to traverse the first tree data structure and a second iterator to traverse the second tree data structure, wherein the first iterator identifies a first root node of the first tree data structure and the second iterator identifies a second root node of the second tree data structure; and

synchronously traversing, using the first iterator and the second iterator, the first tree data structure and the second tree data structure to identify the one or more deleted keys indicative of the deleted data previously stored by the storage system at the first time.

4 . The method of claim 1 , wherein synchronously traversing the first tree data structure and the second tree data structure comprises:

initializing a first iterator to traverse the first tree data structure and a second iterator to traverse the second tree data structure;

advancing the first iterator along a first edge of the first tree data structure from a first parent node of the first tree data structure to identify a first child node of the first parent node;

advancing the second iterator along a second edge of the second tree data structure from a second parent node in the second tree data structure to identify a second child node of the second parent node; and

determining whether the second child node has changed relative to the first child node.

5 . The method of claim 4 , wherein determining whether the first child node has changed relative to the second child node comprises:

determining one or more first keys associated with the first child node, wherein the one or more first keys indicate data stored by at least the first portion of the storage system at the first time;

determining one or more second keys associated with the second child node, wherein the one or more second keys indicate changed data stored by at least the second portion of the storage system that has changed between the first time and the second later time;

advancing each of the first iterator and the second iterator to traverse each of the one or more first keys and the one or more second keys to compare each of the one the one or more first keys to a corresponding one of the one or more second keys;

determining, based on the comparison of each of the one the one or more first keys to the corresponding one of the one or more second keys, one or more of whether at least one of the one or more first keys has been deleted relative to the corresponding one of the one or more second keys, whether at least one of the one or more of first keys has been updated relative to the corresponding one of the one or more second keys, and whether at least one of the one or more second keys has been created between the first time and the second later time.

6 . The method of claim 5 , wherein determining one or more of whether the at least one of the one or more first keys has been deleted relative to the corresponding one of the one or more second keys, whether the at least one of the one or more of first keys has been updated relative to the corresponding one of the one or more second keys, and whether the at least one of the one or more second keys has been created between the first time and the second later time comprises determining, when the one of the one or more first keys is less than the corresponding one of the one or more second keys, that the one of the one or more first keys is included in the one or more deleted keys.

7 . The method of claim 5 , wherein determining one or more of whether the at least one of the one or more first keys has been deleted relative to the corresponding one of the one or more second keys, whether the at least one of the one or more of first keys has been updated relative to the corresponding one of the one or more second keys, and whether the at least one of the one or more second keys has been created between the first time and the second later time comprises:

determining, when the one of one of the one or more first keys is the same as the corresponding one of the one or more second keys, whether a first tree identifier included in the one of the one or more first keys is different from a second tree identifier included in the corresponding one of the one or more second keys;

determining, when the first tree identifier is different from the second tree identifier, that the corresponding one of the one or more second keys indicates updated data that has been updated relative to data associated with the one of the one or more first keys; and

determining, when the first tree identifier is not different from the second tree identifier, that the corresponding one of the one or more second keys indicates unchanged data that has not been changed relative to the data associated with the one of the one or more first keys.

8 . The method of claim 5 , wherein determining one or more of whether the at least one of the one or more first keys has been deleted relative to the corresponding one of the one or more second keys, whether the at least one of the one or more of first keys has been updated relative to the corresponding one of the one or more second keys, and whether the at least one of the one or more second keys has been created between the first time and the second later time comprises determining, when one of the one or more first keys is greater than the one or more second keys, that the corresponding one of the one or more second keys has been created.

9 . The method of claim 4 , wherein determining that the first child node has changed relative to the second child node comprises:

determining a range of one or more first keys identified by the first child node that were skipped, where the range identifies the one or more first keys that indicate one or more skipped first keys;

determining that the one or more skipped first keys are the one or more deleted keys; and

advancing, based on the range, the first iterator past the one or more skipped first keys.

10 . The method of claim 1 , wherein traversing the first tree data structure and the second tree data structure comprises executing respective instances of a depth first search algorithm to synchronously traverse each of the first tree data structure and the second tree data structure.

11 . The method of claim 1 ,

wherein the first tree data structure comprises a first B+ tree data structure, and

wherein the second tree data structure comprises a second B+ tree data structure.

12 . The method of claim 1 , wherein one or more of the first snapshot and the second snapshot are stored remote from the data platform in a cloud storage system.

13 . A computing system that implements a data platform, the computing system comprising:

a memory configured to store metadata identifying, at least in part, one or more deleted keys representative of deleted data that has been deleted from a storage system; and

processing circuitry configured to:

identify a first tree data structure corresponding to a first snapshot of at least a first portion of the storage system at a first time;

identify a second tree data structure corresponding to a second snapshot of at least a second portion of the storage system at a second later time;

synchronously traverse the first tree data structure and second tree data structures to identify the one or more deleted keys indicative of deleted data that has been previously stored by the storage system at the first time and has been deleted from the storage system; and

perform, based on the one or more deleted keys, a data protection operation.

14 . The computing system of claim 13 , wherein to synchronously traverse the first tree data structure and the second tree data structure, the processing circuitry is configured to:

initialize a first iterator to traverse the first tree data structure and a second iterator to traverse the second tree data structure;

advance the first iterator along a first edge of the first tree data structure from a first parent node of the first tree data structure to identify a first child node of the first parent node;

advance the second iterator along a second edge of the second tree data structure from a second parent node in the second tree data structure to identify a second child node of the second parent node; and

determine whether the second child node has changed relative to the first child node.

15 . The computing system of claim 14 , wherein to determine whether the first child node has changed relative to the second child node, the processing circuitry is configured to:

determine one or more first keys associated with the first child node, wherein the one or more first keys indicate data stored by at least the first portion of the storage system at the first time;

determine one or more second keys associated with the second child node, wherein the one or more second keys indicate changed data stored by at least the second portion of the storage system that has changed between the first time and the second later time;

advance each of the first iterator and the second iterator to traverse each of the one or more first keys and the one or more second keys to compare each of the one the one or more first keys to a corresponding one of the one or more second keys;

determine, based on the comparison of each of the one the one or more first keys to the corresponding one of the one or more second keys, one or more of whether at least one of the one or more first keys has been deleted relative to the corresponding one of the one or more second keys, whether at least one of the one or more of first keys has been updated relative to the corresponding one of the one or more second keys, and whether at least one of the one or more second keys has been created between the first time and the second later time.

16 . The computing system of claim 15 , wherein to determine one or more of whether the at least one of the one or more first keys has been deleted relative to the corresponding one of the one or more second keys, whether the at least one of the one or more of first keys has been updated relative to the corresponding one of the one or more second keys, and whether the at least one of the one or more second keys has been created between the first time and the second later time, the processing circuitry is configured to determine, when the one of the one or more first keys is less than the corresponding one of the one or more second keys, that the one of the one or more first keys is included in the one or more deleted keys.

17 . The computing system of claim 15 , wherein to determine one or more of whether the at least one of the one or more first keys has been deleted relative to the corresponding one of the one or more second keys, whether the at least one of the one or more of first keys has been updated relative to the corresponding one of the one or more second keys, and whether the at least one of the one or more second keys has been created between the first time and the second later time, the processing circuitry is configured to:

determine, when the one of one of the one or more first keys is the same as the corresponding one of the one or more second keys, whether a first tree identifier included in the one of the one or more first keys is different from a second tree identifier included in the corresponding one of the one or more second keys;

determine, when the first tree identifier is different from the second tree identifier, that the corresponding one of the one or more second keys indicates updated data that has been updated relative to data associated with the one of the one or more first keys; and

determine, when the first tree identifier is not different from the second tree identifier, that the corresponding one of the one or more second keys indicates unchanged data that has not been changed relative to the data associated with the one of the one or more first keys.

18 . The computing system of claim 15 , wherein to determine one or more of whether the at least one of the one or more first keys has been deleted relative to the corresponding one of the one or more second keys, whether the at least one of the one or more of first keys has been updated relative to the corresponding one of the one or more second keys, and whether the at least one of the one or more second keys has been created between the first time and the second later time, the processing circuitry is configured to determine, when one of the one or more first keys is greater than the one or more second keys, that the corresponding one of the one or more second keys has been created.

19 . The computing system of claim 14 , wherein to determine that the first child node has changed relative to the second child node the processing circuitry is configured to:

determine a range of one or more first keys identified by the first child node that were skipped, where the range identifies the one or more first keys that represent one or more skipped first keys;

determine that the one or more skipped first keys are the one or more deleted keys; and

advance, based on the range, the first iterator past the one or more skipped first keys.

20 . Non-transitory computer-readable storage media having instructions stored thereon that, when executed, cause one or more processors to:

identify a first tree data structure corresponding to a first snapshot of at least a first portion of a storage system at a first time;

identify a second tree data structure corresponding to a second snapshot of at least a second portion of the storage system at a second later time;

synchronously traverse the first tree data structure and second tree data structures to identify one or more deleted keys indicative of deleted data that has been previously stored by the storage system at the first time and has been deleted from the storage system; and

perform, based on the one or more deleted keys, a data protection operation.

Assignments (2)

References Cited (9)