Using merkle trees in any point in time replication

Abstract

One example method includes performing various operations while a stream of IOs is being applied to a source dataset and replicated to a target dataset, and the operations include receiving a replicated IO that was previously applied to a source dataset Merkle tree, applying the replicated IO to a target dataset Merkle tree by entering an updated hash value in the target dataset Merkle tree, and applying a timestamp to the target dataset Merkle tree.

What is claimed is: 
     
         1 . A method, comprising:
 comparing a root hash value of a source dataset tree with a root hash value of a target dataset tree, and both the root hash value of the source dataset tree and the root hash value of the target dataset tree have the same timestamp;   determining, based on the comparing, that the target dataset tree and the source dataset tree are inconsistent with each other;   traversing a portion of the target dataset tree;   identifying, during the traversing, an inconsistency; and   synchronizing the target dataset tree with the source dataset tree.   
     
     
         2 . The method as recited in  claim 1 , wherein determining that the target dataset tree and the source dataset tree are inconsistent with each other comprises determining that the root hash of the source dataset tree and the root hash of the target dataset tree have different respective values. 
     
     
         3 . The method as recited in  claim 1 , wherein traversing the target dataset tree comprises comparing a hash value of the target dataset tree with a corresponding hash value of the source dataset tree and determining that the hash value of the target dataset tree is different from the corresponding hash value of the source dataset tree. 
     
     
         4 . The method as recited in  claim 1 , wherein the operations further comprising applying replicated IOs to the target dataset tree at the same time as any one or more of the comparing, determining, traversing, and synchronizing are being performed. 
     
     
         5 . The method as recited in  claim 1 , wherein traversing the target dataset tree comprising comparing a hash associated with a leaf of the target dataset tree with a hash associated with a leaf of the source dataset tree. 
     
     
         6 . The method as recited in  claim 1 , wherein synchronizing the source dataset tree and the target dataset tree with each other comprises resolving the inconsistency. 
     
     
         7 . The method as recited in  claim 16 , wherein resolving the inconsistency comprises updating a hash value of a leaf in the target dataset tree to match a hash value of a corresponding leaf in the source dataset tree. 
     
     
         8 . The method as recited in  claim 1 , wherein the operations are performed as part of a continuous replication process in which data is replicated from a source dataset to a target dataset. 
     
     
         9 . A non-transitory storage medium having stored therein instructions that are executable by one or more hardware processors to perform operations comprising:
 comparing a root hash value of a source dataset tree with a root hash value of a target dataset tree, and both the root hash value of the source dataset tree and the root hash value of the target dataset tree have the same timestamp;   determining, based on the comparing, that the target dataset tree and the source dataset tree are inconsistent with each other;   traversing a portion of the target dataset tree;   identifying, during the traversing, an inconsistency; and   synchronizing the target dataset tree with the source dataset tree.   
     
     
         10 . The non-transitory storage medium as recited in  claim 9 , wherein determining that the target dataset tree and the source dataset tree are inconsistent with each other comprises determining that the root hash of the source dataset tree and the root hash of the target dataset tree have different respective values. 
     
     
         11 . The non-transitory storage medium as recited in  claim 9 , wherein traversing the target dataset tree comprises comparing a hash value of the target dataset tree with a corresponding hash value of the source dataset tree and determining that the hash value of the target dataset tree is different from the corresponding hash value of the source dataset tree. 
     
     
         12 . The non-transitory storage medium as recited in  claim 9 , wherein the operations further comprising applying replicated IOs to the target dataset tree at the same time as any one or more of the comparing, determining, traversing, and synchronizing are being performed. 
     
     
         13 . The non-transitory storage medium as recited in  claim 9 , wherein traversing the target dataset tree comprising comparing a hash associated with a leaf of the target dataset tree with a hash associated with a leaf of the source dataset tree. 
     
     
         14 . The non-transitory storage medium as recited in  claim 9 , wherein synchronizing the source dataset tree and the target dataset tree with each other comprises resolving the inconsistency. 
     
     
         15 . The non-transitory storage medium as recited in  claim 14 , wherein resolving the inconsistency comprises updating a hash value of a leaf in the target dataset tree to match a hash value of a corresponding leaf in the source dataset tree. 
     
     
         16 . The non-transitory storage medium as recited in  claim 9 , wherein the operations are performed as part of a continuous replication process in which data is replicated from a source dataset to a target dataset.