Resynchronizing metadata in a content management system

• US 10,691,720 B2
• Filed: 01/05/2018
• Issued: 06/23/2020
• Est. Priority Date: 12/28/2017
• Status: Active Grant

• Current Assignee: Dropbox, Inc.
• Original Assignee: Dropbox, Inc.
• Inventors: Lai, John
• Primary Examiner(s): Jacob, Ajith
• Application Number:
  US15/863,819
• Publication Number:
  US 20190208013A1
• Time in Patent Office: 900 Days
• CPC Class Codes: G06F 1/04 Generating or distributing clock signals or signals derived directly therefrom
• CPC Class Codes: G06F 11/1469 Backup restoration techniques
• CPC Class Codes: G06F 12/1466 Key-lock mechanism
• CPC Class Codes: G06F 16/11 File system administration, e.g. details of archiving or snapshots file system backup G06F11/14
• CPC Class Codes: G06F 16/113 Details of archiving lifecycle management in storage systems G06F3/0649; backup systems G06F11/1446
• CPC Class Codes: G06F 16/116 Details of conversion of file system types or formats
• CPC Class Codes: G06F 16/119 Details of migration of file systems migration mechanisms in storage systems G06F3/0647
• CPC Class Codes: G06F 16/122 using management policies backup systems G06F11/1446; file migration policies for HSM systems G06F16/185
• CPC Class Codes: G06F 16/125 characterised by the use of retention policies retention policies for HSM systems G06F16/185
• CPC Class Codes: G06F 16/128 Details of file system snapshots on the file-level, e.g. snapshot creation, administration, deletion use of snapshots for error detection or correction G06F11/14, G06F11/16
• CPC Class Codes: G06F 16/13 File access structures, e.g. distributed indices arrangements of input from, or output to, record carriers G06F3/06
• CPC Class Codes: G06F 16/137 Hash-based content-based indexing of textual data G06F16/31
• CPC Class Codes: G06F 16/148 File search processing
• CPC Class Codes: G06F 16/152 using file content signatures, e.g. hash values
• CPC Class Codes: G06F 16/156 Query results presentation
• CPC Class Codes: G06F 16/16 File or folder operations, e.g. details of user interfaces specifically adapted to file systems
• CPC Class Codes: G06F 16/162 Delete operations erasing in storage systems G06F3/0652
• CPC Class Codes: G06F 16/168 Details of user interfaces specifically adapted to file systems, e.g. browsing and visualisation, 2d or 3d GUIs query results presentation G06F16/156
• CPC Class Codes: G06F 16/172 Caching, prefetching or hoarding of files
• CPC Class Codes: G06F 16/1734 Details of monitoring file system events, e.g. by the use of hooks, filter drivers, logs
• CPC Class Codes: G06F 16/1744 : using compression, e.g. sparse files
• CPC Class Codes: G06F 16/176 : Support for shared access to files; File sharing support
• CPC Class Codes: G06F 16/1767 : Concurrency control, e.g. optimistic or pessimistic approaches
• CPC Class Codes: G06F 16/178 : Techniques for file synchronisation in file systems
• CPC Class Codes: G06F 16/1787 : Details of non-transparently synchronising file systems
• CPC Class Codes: G06F 16/18 : File system types
• CPC Class Codes: G06F 16/182 : Distributed file systems
• CPC Class Codes: G06F 16/1827 : Management specifically adapted to NAS management of storage area networks [SAN] G06F3/067
• CPC Class Codes: G06F 16/183 : Provision of network file services by network file servers, e.g. by using NFS, CIFS network file access protocols H04L67/1097
• CPC Class Codes: G06F 16/184 : implemented as replicated file system
• CPC Class Codes: G06F 16/1844 : Management specifically adapted to replicated file systems
• CPC Class Codes: G06F 16/185 : Hierarchical storage management [HSM] systems, e.g. file migration or policies thereof details of archiving G06F16/11
• CPC Class Codes: G06F 16/2246 : Trees, e.g. B+trees
• CPC Class Codes: G06F 16/2255 : Hash tables
• CPC Class Codes: G06F 16/2322 : using timestamps
• CPC Class Codes: G06F 16/2358 : Change logging, detection, and notification replication G06F16/27
• CPC Class Codes: G06F 16/2365 : Ensuring data consistency and integrity
• CPC Class Codes: G06F 16/2379 : Updates performed during online database operations; commit processing
• CPC Class Codes: G06F 16/24552 : Database cache management
• 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
• CPC Class Codes: G06F 16/275 : Synchronous replication
• CPC Class Codes: G06F 16/9027 : Trees
• CPC Class Codes: G06F 16/907 : Retrieval characterised by using metadata, e.g. metadata not derived from the content or metadata generated manually
• CPC Class Codes: G06F 16/951 : Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/955 : using information identifiers, e.g. uniform resource locators [URL]
• CPC Class Codes: G06F 16/958 : Organisation or management of web site content, e.g. publishing, maintaining pages or automatic linking
• CPC Class Codes: G06F 21/10 : Protecting distributed programs or content, e.g. vending or licensing of copyrighted material protection in video systems or pay television H04N7/16 ; Digital rights management [DRM]
• CPC Class Codes: G06F 21/604 : Tools and structures for managing or administering access control systems
• CPC Class Codes: G06F 21/6218 : to a system of files or objects, e.g. local or distributed file system or database
• CPC Class Codes: G06F 2201/84 : Using snapshots, i.e. a logical point-in-time copy of the data
• CPC Class Codes: G06F 2212/1052 : Security improvement
• CPC Class Codes: G06F 2221/2141 : Access rights, e.g. capability lists, access control lists, access tables, access matrices
• CPC Class Codes: G06F 3/0619 : in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/0623 : in relation to content
• CPC Class Codes: G06F 3/0629 : Configuration or reconfiguration of storage systems
• CPC Class Codes: G06F 3/065 : Replication mechanisms
• CPC Class Codes: G06F 3/0652 : Erasing, e.g. deleting, data cleaning, moving of data to a wastebasket
• CPC Class Codes: G06F 3/067 : Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• CPC Class Codes: G06F 9/547 : Remote procedure calls [RPC]; Web services
• CPC Class Codes: H04L 63/08 : for authentication of entities cryptographic mechanisms or cryptographic arrangements for entity authentication H04L9/32
• CPC Class Codes: H04L 63/0853 : using an additional device, e.g. smartcard, SIM or a different communication terminal cryptographic mechanisms or cryptographic arrangements for entity authentication involving additional secure or trusted devices H04L9/3234
• CPC Class Codes: H04L 63/10 : for controlling access to devices or network resources
• CPC Class Codes: H04L 63/101 : Access control lists [ACL]
• CPC Class Codes: H04L 63/102 : Entity profiles
• CPC Class Codes: H04L 67/01 : Protocols
• CPC Class Codes: H04L 67/06 : specially adapted for file transfer, e.g. file transfer protocol [FTP]
• CPC Class Codes: H04L 67/1095 : Replication or mirroring of data, e.g. scheduling or transport for data synchronisation between network nodes
• CPC Class Codes: H04L 67/1097 : for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS]
• CPC Class Codes: H04L 67/306 : User profiles
• CPC Class Codes: H04L 9/3213 : using tickets or tokens, e.g. Kerberos network architectures or network communication protocols for entities authentication using tickets in a packet data network H04L63/0807
• CPC Class Codes: H04L 9/3247 : involving digital signatures

Abstract

A client can resynchronize tree data structures representing a server, local, and sync state of content items in an account. In some aspects, the client identifies a local set of content items on the account and generates a local tree representing a filesystem state and including a local node for each item in the local set. The client determines a server state for a remote set of content items on the account. Based on the server state, the client generates a remote tree representing the remote set and including a respective node for each item in the remote set. Based on the local and remote trees, the client generates a sync tree including matching nodes between the local and remote trees, the sync tree representing a synchronized state between the filesystem state and the server state. The client then stores the local, remote, and sync trees.

Claims

1. A method comprising:

identifying, via a client device, a local set of content items stored at the client device and associated with a user account at a content management system;

based on the local set of content items, generating, via the client device, a local tree data structure representing a filesystem state at the client device, the local tree data structure comprising a respective local node corresponding to each of the local set of content items;

receiving, from the content management system, a server state identifying a remote set of content items stored at the content management system and associated with the user account;

based on the server state, generating, via the client device, a remote tree data structure representing the remote set of content items, the remote tree data structure comprising a respective remote node corresponding to each of the remote set of content items;

based on the local tree data structure and the remote tree data structure, generating, via the client device, a sync tree data structure comprising a matching set of nodes in the local tree data structure and the remote tree data structure, the sync tree data structure representing a synchronized state between the filesystem state and the server state; and

storing the local tree data structure, the remote tree data structure, and the sync tree data structure at the client device.

2. The method of claim 1, wherein identifying the local set of content items stored at the client device comprises:

crawling a storage at the client device to identify the local set of content items at the client device;

indexing the local set of content items; and

calculating a respective hash value for each of the local set of content items.

3. The method of claim 2, wherein each respective local node in the local tree data structure comprises the respective hash value calculated for a corresponding local content item in the local set of content items and respective metadata associated with the corresponding local content item.

4. The method of claim 3, wherein the respective metadata comprises at least one of a respective file identifier, a respective directory identifier, or a respective content item name.

5. The method of claim 4, wherein each respective remote node in the remote tree data structure comprises a second respective hash value calculated for a corresponding remote content item in the remote set of content items and respective metadata associated with the corresponding remote content item.

6. The method of claim 1, wherein generating the sync tree data structure comprises:

for each respective local node in the local tree data structure;

determining whether the respective local node matches one of a plurality of remote nodes in the remote tree data structure; and

adding the respective local node to the sync tree data structure when the respective local node matches one of the plurality of remote nodes in the remote tree data structure.

7. The method of claim 6, further comprising excluding the respective local node from the sync tree data structure when the respective local node does not match one of the plurality of remote nodes in the remote tree data structure.

8. The method of claim 7, wherein determining whether the respective local node matches one of the plurality of remote nodes in the remote tree data structure comprises searching the remote tree data structure for at least one of a respective file identifier associated with the respective local node, a respective directory identifier associated with the respective local node, or a respective content item name associated with the respective local node.

9. The method of claim 8, further comprising:

prior to excluding the respective local node from the sync tree data structure when the respective local node does not match one of the plurality of remote nodes in the remote tree data structure, querying a journal of revisions at the content management system for a record comprising at least one of the respective file identifier associated with the respective local node, the respective directory identifier associated with the respective local node, or the respective content item name associated with the respective local node; and

excluding the respective local node from the sync tree data structure only when the content management system indicates that the journal of revisions does not contain the record comprising at least one of the respective file identifier, the respective directory identifier, or the respective content item name.

10. The method of claim 1, further comprising:

identifying a difference between the sync tree data structure and the remote tree data structure, the difference representing one or more conflicts between the server state and the filesystem state;

converging the server state and the filesystem state to yield a resynchronized state; and

synchronizing the local tree data structure, the sync data structure, and the remote tree data structure based on the resynchronized state.

11. A non-transitory computer readable medium comprising instructions, the instructions, when executed by a computing device, cause the computing device to:

identify a local set of content items associated with a user account registered at a content management system;

based on the local set of content items, generate a local tree data structure representing a filesystem state at the computing device, the local tree data structure comprising a respective local node corresponding to each of the local set of content items;

receive, from the content management system, a server state identifying a remote set of content items stored at the content management system and associated with the user account;

based on the server state, generate a remote tree data structure representing the remote set of content items, the remote tree data structure comprising a respective remote node corresponding to each of the remote set of content items;

based on the local tree data structure and the remote tree data structure, generate a sync tree data structure comprising a matching set of nodes in the local tree data structure and the remote tree data structure, the sync tree data structure representing a synchronized state between the filesystem state and the server state; and

store the local tree data structure, the remote tree data structure, and the sync tree data structure at the computing device.

12. The non-transitory computer readable medium of claim 11, wherein identifying the local set of content items comprises:

crawling a storage at the computing device to identify the local set of content items;

indexing the local set of content items; and

calculating a respective hash value for each corresponding local content item in the local set of content items.

13. The non-transitory computer readable medium of claim 12, wherein each respective local node in the local tree data structure comprises the respective hash value calculated for the corresponding local content item and respective metadata associated with the corresponding local content item, wherein the respective metadata comprises at least one of a respective file identifier, a respective directory identifier, or a respective content item name.

14. The non-transitory computer readable medium of claim 11, wherein generating the sync tree data structure comprises:

for each respective local node in the local tree data structure;

determining whether the respective local node matches one of a plurality of remote nodes in the remote tree data structure; and

adding the respective local node to the sync tree data structure when the respective local node matches one of the plurality of remote nodes in the remote tree data structure.

15. The non-transitory computer readable medium of claim 14, storing instructions which, when executed by the computing device, cause the computing device to:

when the respective local node does not match one of the plurality of remote nodes in the remote tree data structure, query a journal of revisions at the content management system for a record comprising at least one of a respective file identifier associated with the respective local node, a respective directory identifier associated with the respective local node, or a respective content item name associated with the respective local node; and

exclude the respective local node from the sync tree data structure when the content management system indicates that the journal of revisions does not contain the record comprising at least one of the respective file identifier, the respective directory identifier, or the respective content item name.

16. The non-transitory computer readable medium of claim 11, storing instructions which, when executed by the computing device, cause the computing device to:

identify a difference between the sync tree data structure and the remote tree data structure, the difference representing one or more differences between the server state and the filesystem state;

converge the server state and the filesystem state to yield a resynchronized state; and

based on the resynchronized state, synchronize the local tree data structure, the sync tree data structure, and the remote tree data structure by modifying at least one of the local tree data structure, the sync tree data structure, or the remote tree data structure.

17. A computing device comprising:

one or more processors; and

at least one non-transitory computer readable medium having stored therein instructions which, when executed by the one or more processors, cause the computing device to;

identify a local set of content items associated with a user account registered at a content management system;

based on the local set of content items, generate a local tree data structure representing a filesystem state at the computing device, the local tree data structure comprising a respective local node corresponding to each of the local set of content items;

receive, from the content management system, a remote state corresponding to a remote set of content items on the content management system, the remote set of content items being associated with the user account;

based on the remote state, generate a remote tree data structure representing the remote set of content items, the remote tree data structure comprising a respective remote node corresponding to each of the remote set of content items;

based on the local tree data structure and the remote tree data structure, generate a sync tree data structure comprising a matching set of nodes in the local tree data structure and the remote tree data structure, the sync tree data structure representing a synchronized state between the filesystem state and the remote state; and

store the local tree data structure, the remote tree data structure, and the sync tree data structure at the computing device.

18. The computing device of claim 17, storing instructions which, when executed by the one or more processors, cause the computing device to:

identify a difference between the sync tree data structure and the remote tree data structure, the difference representing one or more differences between the remote state and the filesystem state;

converge the remote state and the filesystem state to yield a resynchronized state; and

based on the resynchronized state, synchronize the local tree data structure, the sync data structure, and the remote tree data structure by modifying at least one of the local tree data structure, the sync data structure, or the remote tree data structure.

19. The computing device of claim 17, wherein identifying the local set of content items comprises:

crawling the at least one non-transitory computer readable medium to identify the local set of content items;

indexing the local set of content items; and

calculating a respective hash value for each corresponding local content item in the local set of content items.

20. The computing device of claim 19, wherein each respective local node in the local tree data structure comprises the respective hash value calculated for the corresponding local content item and respective metadata comprising at least one of a respective file identifier, a respective directory identifier, or a respective content item name, wherein generating the sync tree data structure comprises:

for each respective local node in the local tree data structure;

determining whether the respective local node matches one of a plurality of remote nodes in the remote tree data structure;

adding the respective local node to the sync tree data structure when the respective local node matches one of the plurality of remote nodes in the remote tree data structure; and

excluding the respective local node from the sync tree data structure when the respective local node does not match one of the plurality of remote nodes in the remote tree data structure and a journal of revisions at the content management system does not contain a journal entry comprising at least one of the respective file identifier, the respective directory identifier, or the respective content item name.