Filesystem embedded Merkle trees
One example method includes creating a source FS Merkle tree having a structure that matches a topology of a source FS, and a target FS Merkle tree having a structure that matches a topology of a target FS, receiving a change to the source FS, implementing the change in the source FS, updating the source FS Merkle tree to reflect the change, replicating the change to the target FS so that, with respect to the change, the target FS is synchronized with the source FS, updating the target FS Merkle tree to reflect the change to the target FS, and comparing the source FS Merkle tree to the target FS Merkle tree.
1. A method, comprising:
creating a source FS Merkle tree having a structure that corresponds to a topology of a source FS, and a target FS Merkle tree having a structure that corresponds to a topology of a target FS, wherein:
the structure of the source FS Merkle tree is configured so that a root node of the source FS Merkle tree is a root directory and includes a root hash that is a hash of all contents of the FS Merkle tree, and each child node of the FS Merkle tree below the root node is either a directory or a file; and
the structure of the target FS Merkle tree is configured so that a root node of the target FS Merkle tree is a root directory and includes a root hash that is a hash of all contents of the FS Merkle tree, and each child node of the FS Merkle tree below the root node is either a directory or a file;
implementing a change in the source FS;
updating the source FS Merkle tree to reflect the change;
replicating the change to the target FS so that, with respect to the change, the target FS is synchronized with the source FS;
updating the target FS Merkle tree to reflect the change to the target FS; and
comparing the source FS Merkle tree to the target FS Merkle tree.
2. The method as recited in claim 1 , wherein the change comprises one or both of: a modification to a file of the source FS; and, a modification to a directory of the source FS.
3. The method as recited in claim 1 , wherein updating the source FS Merkle tree to reflect the change comprises hashing a file of the source FS to create a file hash and/or hashing a directory of the source FS to create a directory hash, and entering the file hash and/or the directory hash into the source FS Merkle tree.
4. The method as recited in claim 1 , wherein the source FS Merkle tree comprises a directory node with which the change is associated, and the method further comprises creating a source FS directory Merkle tree that holds only entries of the directory node, and updating the target FS Merkle tree comprises synchronizing the source FS directory Merkle tree with a corresponding target FS directory Merkle tree.
5. The method as recited in claim 1 , wherein implementing the change in the source FS and implementing the change in the target FS comprise directory level operations and/or file level operations.
6. The method as recited in claim 1 , wherein updating the source FS Merkle tree and updating the target FS Merkle tree are performed without the use of any block level operations.
7. The method as recited in claim 1 , wherein updating the source FS Merkle tree and updating the target FS Merkle tree are performed while replication from the source FS to the target FS is ongoing.
8. The method as recited in claim 1 , wherein when the comparing indicates that the source FS Merkle tree and the target FS Merkle tree are the same, then the source FS and the target FS are the same as each other.
9. The method as recited in claim 1 , wherein an operation involving a file or directory of the source FS is reflected at the target FS Merkle tree using a pickup table at the target.
10. The method as recited in claim 1 , wherein the change to the source FS involves a change to metadata respectively associated with a file and/or directory of the source FS.
11. A non-transitory storage medium having stored therein instructions that are executable by one or more hardware processors to perform operations comprising:
creating a source FS Merkle tree having a structure that corresponds to a topology of a source FS, and a target FS Merkle tree having a structure that corresponds to a topology of a target FS, wherein:
the structure of the source FS Merkle tree is configured so that a root node of the source FS Merkle tree is a root directory and includes a root hash that is a hash of all contents of the FS Merkle tree, and each child node of the FS Merkle tree below the root node is either a directory or a file; and
the structure of the target FS Merkle tree is configured so that a root node of the target FS Merkle tree is a root directory and includes a root hash that is a hash of all contents of the FS Merkle tree, and each child node of the FS Merkle tree below the root node is either a directory or a file;
implementing a change in the source FS;
updating the source FS Merkle tree to reflect the change;
replicating the change to the target FS so that, with respect to the change, the target FS is synchronized with the source FS;
updating the target FS Merkle tree to reflect the change to the target FS; and
comparing the source FS Merkle tree to the target FS Merkle tree.
12. The non-transitory storage medium as recited in claim 11 , wherein the change comprises one or both of: a modification to a file of the source FS; and, a modification to a directory of the source FS.
13. The non-transitory storage medium as recited in claim 11 , wherein updating the source FS Merkle tree to reflect the change comprises hashing a file of the source FS to create a file hash and/or hashing a directory of the source FS to create a directory hash, and entering the file hash and/or the directory hash into the source FS Merkle tree.
14. The non-transitory storage medium as recited in claim 11 , wherein the source FS Merkle tree comprises a directory node with which the change is associated, and the method further comprises creating a source FS directory Merkle tree that holds only entries of the directory node, and updating the target FS Merkle tree comprises synchronizing the source FS directory Merkle tree with a corresponding target FS directory Merkle tree.
15. The non-transitory storage medium as recited in claim 11 , wherein implementing the change in the source FS and implementing the change in the target FS comprise directory level operations and/or file level operations.
16. The non-transitory storage medium as recited in claim 11 , wherein updating the source FS Merkle tree and updating the target FS Merkle tree are performed without the use of any block level operations.
17. The non-transitory storage medium as recited in claim 11 , wherein updating the source FS Merkle tree and updating the target FS Merkle tree are performed while replication from the source FS to the target FS is ongoing.
18. The non-transitory storage medium as recited in claim 11 , wherein when the comparing indicates that the source FS Merkle tree and the target FS Merkle tree are the same, then the source FS and the target FS are the same as each other.
19. The non-transitory storage medium as recited in claim 11 , wherein an operation involving a file or directory of the source FS is reflected at the target FS Merkle tree using a pickup table at the target.
20. The non-transitory storage medium as recited in claim 11 , wherein the change to the source FS involves a change to metadata respectively associated with a file and/or directory of the source FS.