Method and system for synchronizing a virtual file system at a computing device with a storage device

• US 8,572,136 B2
• Filed: 11/24/2010
• Issued: 10/29/2013
• Est. Priority Date: 08/28/2009
• Status: Active Grant

• Current Assignee: Beijing Innovation Works Technology Company Limited
• Original Assignee: Beijing Innovation Works Technology Company Limited
• Inventors: Guarraci, Brian J.
• Primary Examiner(s): TRUONG, CAM Y T
• Application Number:
  US12/954,386
• Publication Number:
  US 20110072059A1
• Time in Patent Office: 1,070 Days
• Field of Search: 707/638, 707/825, 707/778
• US Class Current: 707/825
• CPC Class Codes: G06F 16/188 Virtual file systems
• CPC Class Codes: G06F 16/27 Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor

Abstract

A method of synchronizing a virtual file system is implemented at a computing device. The virtual file system has a hierarchical tree structure including a plurality of tree nodes, each tree node having associated metadata and corresponding to a respective component of the virtual file system. Upon receipt of a request to generate a revision of a virtual file system in at least one storage device, the computing device serializes each tree node'"'"'s associated metadata into an object, generates an object ID from the serialized object, and stores the object in the storage device if the object ID is not found in an object-storage mapping table associated with the virtual file system. Finally, the computing device inserts the object ID into the object-storage mapping table and stores the object-storage mapping table in the storage device after processing the last tree node.

Claims

1. A computer-implemented method, comprising:

at a computing device;

receiving a request to convert a revision of a virtual file system at the computing device into a plurality of blocks within at least one storage device;

identifying a hierarchical tree structure associated with the revision of the virtual file system, wherein the hierarchical tree structure includes a plurality of tree nodes, each tree node having associated metadata and corresponding to a respective component of the revision of the virtual file system;

converting the hierarchical tree structure and associated metadata into the plurality of blocks within the one storage device in a top-down manner, further including;

for each tree node;

serializing the tree node'"'"'s associated metadata into an object;

generating an object ID from the serialized object by applying a hash algorithm to data in the serialized object, wherein the object ID is uniquely defined by the tree node'"'"'s associated metadata such that two different serialized objects do not share the same object ID, and the object is comprised of an object header and an object body, the object header including the object ID and the object body including the serialized metadata, and the object header further includes a tag for determining how the object was serialized and choosing a corresponding application program interface module for deserializing the object in connection with rebuilding the virtual file system;

storing the object in a respective one of the plurality of blocks within the storage device if the object ID is not found in an object-storage mapping table associated with the virtual file system and discarding the object if the object ID is found in the object-storage mapping table associated with the virtual file system; and

inserting the object ID into the object-storage mapping table; and

storing the object-storage mapping table in a respective one of the plurality of blocks within the storage device.

2. The computer-implemented method of claim 1, wherein at least one of the tree nodes includes a directory node that corresponds to a directory of the virtual file system.

3. The computer-implemented method of claim 2, wherein the metadata associated with the directory node includes a directory node identifier, a reference to another directory node, and one or more directory attributes.

4. The computer-implemented method of claim 3, wherein the directory node identifier is generated by hashing the reference to another directory node and the one or more directory attributes.

5. The computer-implemented method of claim 3, wherein serializing the directory node'"'"'s associated metadata includes combining the directory node identifier, the reference to another directory node, and the one or more directory attributes into the object in a predefined order.

6. The computer-implemented method of claim 1, wherein the object is comprised of an object header and an object body, the object header including the object ID and the object body including the serialized metadata.

7. The computer-implemented method of claim 6, wherein the object header further includes a key for determining whether the object is correctly deserialized in connection with rebuilding the virtual file system.

8. The computer-implemented method of claim 7, wherein the key is a hash of the serialized metadata.

9. The computer-implemented method of claim 7, wherein the key is used for encrypting the object before storing the object at a storage device.

10. The computer-implemented method of claim 1, wherein at least one of the tree nodes includes a file node that corresponds to a file of the virtual file system.

11. The computer-implemented method of claim 10, wherein the file includes a plurality of content blocks, the method further comprising:

for each content block;

generating a block ID from the content block;

determining whether the block ID is in a content block-storage mapping table that includes identifiers of content blocks associated with the virtual file system;

if the block ID is not found in the content block-storage mapping table;

storing the content block in a respective one of the plurality of blocks within the storage device; and

inserting the block ID into the content block-storage mapping table;

if the block ID is found in the content block-storage mapping table;

having the file reference a content block that has the same block ID found in the content block-storage mapping table; and

storing the content block-storage mapping table in a respective one of the plurality of blocks within the storage device.

12. The computer-implemented method of claim 11, wherein the referenced content block is associated with an earlier revision of same file.

13. The computer-implemented method of claim 11, wherein the referenced content block is associated with a different file of the virtual file system.

14. The computer-implemented method of claim 1, wherein the at least one storage device include a storage device local to the computing device and a storage device remote from the computing device.

15. The computer-implemented method of claim 14, wherein the remote one storage device is associated with a cloud storage service provided by a third party.

16. The computer-implemented method of claim 1, wherein the computing device is one selected from the group consisting of a desktop computer, a laptop computer, a tablet computer, and a mobile telephone.

17. The computer-implemented method of claim 1, wherein the computing device has a local file system and the local file system includes directories and files associated with the virtual file system.

18. A computing device in association with a distributed storage system that includes a plurality of storage devices, comprising:

one or more processors;

memory; and

one or more programs stored in the memory for execution by the one or more processors, the one or more programs comprising instructions for;

receiving a request to convert a revision of a virtual file system at the computing device into a plurality of blocks within at least one storage device;

identifying a hierarchical tree structure associated with the revision of the virtual file system, wherein the hierarchical tree structure includes a plurality of tree nodes, each tree node having associated metadata and corresponding to a respective component of the revision of the virtual file system;

converting the hierarchical tree structure and associated metadata into the plurality of blocks within the one storage device in a top-down manner, further including;

for each tree node;

serializing the tree node'"'"'s associated metadata into an object;

generating an object ID from the serialized object by applying a hash algorithm to data in the serialized object, wherein the object ID is uniquely defined by the tree node'"'"'s associated metadata such that two different serialized objects do not share the same object ID, and the object is comprised of an object header and an object body, the object header including the object ID and the object body including the serialized metadata, and the object header further includes a tag for determining how the object was serialized and choosing a corresponding application program interface module for deserializing the object in connection with rebuilding the virtual file system;

storing the object in a respective one of the plurality of blocks within the storage device if the object ID is not found in an object-storage mapping table associated with the virtual file system and discarding the object if the object ID is found in the object-storage mapping table associated with the virtual file system; and

inserting the object ID into the object-storage mapping table; and

storing the object-storage mapping table in a respective one of the plurality of blocks within the storage device.

19. A non-transitory computer readable storage medium storing one or more programs configured for execution by a computing device having one or more processors and memory storing one or more programs for execution by the one or more processors in association with a distributed storage system that includes a plurality of storage devices, the one or more programs comprising instructions to:

receive a request to convert a revision of a virtual file system at the computing device into a plurality of blocks within at least one storage device;

identify a hierarchical tree structure associated with the revision of the virtual file system, wherein the hierarchical tree structure includes a plurality of tree nodes, each tree node having associated metadata and corresponding to a respective component of the revision of the virtual file system;

convert the hierarchical tree structure and associated metadata into the plurality of blocks within the one storage device in a top-down manner, further including;

for each tree node;

serialize the tree node'"'"'s associated metadata into an object;

generate an object ID from the serialized object by applying a hash algorithm to data in the serialized object, wherein the object ID is uniquely defined by the tree node'"'"'s associated metadata such that two different serialized objects do not share the same object ID, and the object is comprised of an object header and an object body, the object header including the object ID and the object body including the serialized metadata, and the object header further includes a tag for determining how the object was serialized and choosing a corresponding application program interface module for deserializing the object in connection with rebuilding the virtual file system;

store the object in a respective one of the plurality of blocks within the storage device if the object ID is not found in an object-storage mapping table associated with the virtual file system and discarding the object if the object ID is found in the object-storage mapping table associated with the virtual file system; and

insert the object ID into the object-storage mapping table; and

store the object-storage mapping table in a respective one of the plurality of blocks within the storage device.