Systems and methods for a snapshot of data
View Patent ↗In one embodiment, a user or client device is connected to a distributed file system comprised of one or more physical nodes. The data on each of the physical nodes store metadata about files and directories within the file system. Some of the embodiments permit a user to take a snapshot of data stored on the file system. The snapshot may include a single file, a single directory, a plurality of files within a directory, a plurality of directories, a path on the file system that includes nested files and subdirectories, or more than one path on the file system that each include nested files and directories. According to one embodiment, the system stores representations of the snapshots that govern a file or directory and its descendants within metadata associated with that file or directory. Before modifying a file or directory, the system updates the representations of the governing snapshots by traversing the metadata of ancestors of the file or directory.
1. A method of preserving a file or directory stored in a processor-accessible storage system as of a point in time, the method comprising:
accessing, by a computer processor, a target metadata node associated with the file or directory in a file system, the file system comprising multiple metadata nodes arranged in a logical hierarchy, one or more of the metadata nodes comprising a governance list, the governance list comprising one or more snapshot identifiers, each snapshot identifier uniquely identifying a snapshot governing the file or directory and indicating when the snapshot was taken, each snapshot identifier based on a global count of the file system at a time when its corresponding snapshot was taken, the global count indicating a time relative to when a snapshot is taken;
comparing, by the computer processor, the most recent snapshot identifier of the governance list of the target metadata node with the global count of the file system, the most recent snapshot identifier indicating when the most recent snapshot was taken relative to the global count;
based on the comparison of the most recent snapshot identifier to the global count, determining, by the computer processor, that one or more ancestors of the target metadata node must be accessed;
accessing, by the computer processor, at least one ancestor metadata node of the target metadata node;
determining, by the computer processor, that a snapshot identifier of the governance list of the at least one ancestor metadata node is more recent than the most recent snapshot identifier of the governance list of the target metadata node; and
adding, by the computer processor, the more recent snapshot identifier of the governance list of the at least one ancestor metadata node to the governance list of the target metadata node.
2. The method of claim 1 wherein the comparison is performed after receiving a request to modify at least a portion of the file or directory.
3. The method of claim 2 , wherein the adding is performed prior to any modification of the at least a portion of the file or directory.
4. The method of claim 1 wherein the determining that one or more ancestors of the target metadata node must be accessed comprises determining that the target metadata node does not correspond to a root of the file system and that the most recent snapshot identifier of the governance list of the target metadata node is different than the global count.
5. The method of claim 1 wherein the accessing at least one ancestor metadata node comprises traversing ancestor metadata nodes of the target metadata node from the target metadata node toward a root metadata node corresponding to the root of the file system until either an ancestor metadata node is accessed which is not out-of-date or the root metadata node is accessed.
6. The method of claim 5 , wherein each ancestor metadata node comprises an indication of the relative time that the governance list of the ancestor metadata node was last updated, the method further comprising determining that an ancestor metadata node is not out-of-date if the indication of the ancestor metadata node is greater than or equal to the global count.
7. The method of claim 1 , further comprising:
accessing at least one different version of the target metadata node;
determining that a snapshot identifier of the governance list of the at least one different version is more recent than the most recent snapshot identifier of the governance list of the target metadata node; and
adding the more recent snapshot identifier of the governance list of the at least one different version to the governance list of the target metadata node.
8. The method of claim 1 , wherein the at least one ancestor metadata node comprises at least two ancestor metadata nodes and the method further comprises:
determining that a snapshot identifier of the governance list of a first node of the at least two ancestor metadata nodes is more recent than a most recent snapshot identifier of the governance list of a second node of the at least two ancestor metadata nodes, the first node being an ancestor of the second node; and
adding the more recent snapshot identifier of the governance list of the first node to the governance list of the second node.
9. The method of claim 1 , further comprising updating an indication in the target metadata node based on the global count, the indication indicating the relative time that the governance list of the target metadata node was last updated.
10. A system for tracking snapshots of a file system, the system comprising:
at least one computer processor;
at least one memory;
a file structure comprising a plurality of files and directories that are logically stored in a tree on the at least one memory;
a plurality of metadata structures, each metadata structure corresponding to a file or directory of the file structure, each metadata structure comprising a governance list, the governance list comprising one or more snapshot identifiers, each snapshot identifier uniquely identifying a snapshot governing the file or directory and indicating when the snapshot was taken, each snapshot identifier based on a global count of the file system at a time when its corresponding snapshot was taken, the global count indicating a time relative to when a snapshot is taken;
at least one executable software module executed by the at least one computer processor and configured to:
access a target metadata structure corresponding to a target file or directory of the file structure;
compare the most recent snapshot identifier of the governance list of the target metadata structure with the global count of the file system, the most recent snapshot identifier indicating when the most recent snapshot was taken relative to the global count;
based on the comparison of the most recent snapshot identifier to the global count, determine that one or more ancestors of the target metadata structure must be accessed;
access at least one ancestor metadata structure of the target metadata structure;
determine that a snapshot identifier of the governance list of the at least one ancestor metadata structure is more recent than the most recent snapshot identifier of the governance list of the target metadata node; and
add the more recent snapshot identifier of the governance list of the at least one ancestor metadata structure to the governance list of the target metadata structure.
11. The system of claim 10 , wherein the at least one executable software module is further configured to:
receive a request to modify at least a portion of the target file or directory;
perform said comparison if a request to modify at least a portion of the target file or directory is received.
12. The system of claim 11 , wherein the at least one executable software module is further configured to perform said addition prior to any modification of the at least a portion of the target file or directory.
13. The system of claim 10 , wherein the at least one executable software module is configured to determine that one or more ancestors of the target metadata structure must be accessed if the target metadata structure does not correspond to a root of the file structure and the most recent snapshot identifier of the governance list of the target metadata structure is different than the global count.
14. The system of claim 10 , wherein the at least one executable software module is configured to access the at least one ancestor metadata structure by traversing the ancestor metadata structures of the target metadata structure from the target metadata structure toward a root metadata structure corresponding to the root of the file structure until either an ancestor metadata structure is accessed which is not out-of-date or the root metadata structure is accessed.
15. The system of claim 14 , wherein each ancestor metadata structure comprises an indication of the relative time that the governance list of the ancestor metadata structure was last updated, and the at least one executable software module is configured to determine that an ancestor metadata node is not out-of-date if the indication of the ancestor metadata node is greater than or equal to the global count.
16. The system of claim 10 , wherein the at least one executable software module is further configured to:
access at least one different version of the target metadata structure;
determine that a snapshot identifier of the governance list of the at Least one different version is more recent than the most recent snapshot identifier of the governance list of the target metadata structure; and
add the more recent snapshot identifier of the governance list of the at least one different version to the governance list of the target metadata structure.
17. The system of claim 10 , wherein the at least one ancestor metadata structure comprises at least two ancestor metadata structures and the at least one executable software module is further configured to:
determine that a snapshot identifier of the governance list of a first structure of the at least two ancestor metadata structures is more recent than a most recent snapshot identifier of the governance list of a second structure of the at least two ancestor metadata structures, the first structure being an ancestor of the second structure; and
add the more recent snapshot identifier of the governance list of the first structure to the governance list of the second structure.
18. The system of claim 10 , wherein the at least one executable software module is further configured to update an indication in the target metadata structure based on the global count, the indication indicating the relative time that the governance list of the target metadata structure was last updated.