Atomic moves with lamport clocks in a content management system

• US 10,726,044 B2
• Filed: 01/17/2018
• Issued: 07/28/2020
• Est. Priority Date: 12/28/2017
• Status: Active Grant

• Current Assignee: Dropbox, Inc.
• Original Assignee: Dropbox, Inc.
• Inventors: Koorapati, Nipunn, Wetterau, David, Walker, Braden, Cowling, James, Jayakar, Sujay
• Primary Examiner(s): Dwivedi, Mahesh H
• Application Number:
  US15/873,693
• Publication Number:
  US 20190205457A1
• Time in Patent Office: 923 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 system can serialize moves and mounts across namespaces based on lamport clocks. In some examples, the system obtains a request to move a content item from a source namespace to a destination namespace. The system processes an incoming move at the destination and an outgoing move at the source. The system processes for the content item a delete at the source and an add at the destination. The system assigns a first clock to the incoming move and a second clock to the outgoing move, the first clock being lower than the second clock. The system assigns a third clock to the delete and a fourth clock to the add, the third clock being higher than the second clock and lower than the fourth clock. The system serializes the incoming and outgoing moves, the delete and the add based on the first, second, third and fourth clocks.

Claims

1. A method comprising:

obtaining, via a content management system, a set of operations associated with a user account on the content management system, the set of operations comprising a request to move a content item from a source namespace to a destination namespace;

processing, via the content management system, an incoming move operation at the destination namespace and an outgoing move operation at the source namespace;

processing a delete operation and an add operation for the content item, the delete operation being processed at the source namespace and the add operation being processed at the destination namespace;

assigning a first lamport clock value to the incoming move operation and a second lamport clock value to the outgoing move operation, wherein the first lamport clock value is lower than the second lamport clock value;

assigning a third lamport clock value to the delete operation and a fourth lamport clock value to the add operation, wherein the third lamport clock value is higher than the second lamport clock value and lower than the fourth lamport clock value; and

serializing the incoming move operation, the outgoing move operation, the delete operation, and the add operation based on the first lamport clock value, the second lamport clock value, the third lamport clock value, and the fourth lamport clock value.

2. The method of claim 1, further comprising providing, to a client device, a listing of serialized operations and a cursor indicating a state of at least one of the source namespace and the destination namespace, the listing of serialized operations comprising at least one of the incoming move operation, the outgoing move operation, the delete operation, and the add operation serialized according to the first lamport clock value, the second lamport clock value, the third lamport clock value, and the fourth lamport clock value.

3. The method of claim 2, wherein the listing of serialized operations excludes the outgoing move operation and the add operation when the destination namespace is not mounted at the client device.

4. The method of claim 1, wherein processing the incoming move operation and the outgoing move operation comprises:

recording, via the content management system, at a server file journal, the incoming move operation at a first journal record associated with the destination namespace; and

recording, via the content management system, at the server file journal, the outgoing move operation at a second journal record associated with the source namespace.

5. The method of claim 4, wherein assigning the first lamport clock value to the incoming move operation and the second lamport clock value to the outgoing move operation comprises:

calculating the first lamport clock value for the incoming move operation based on a current lamport clock value;

incrementing the first lamport clock value based on the outgoing move operation to yield the second lamport clock value; and

recording the first lamport clock value for the incoming move operation and the second lamport clock value for the outgoing move operation.

6. The method of claim 5, wherein processing the delete operation and the add operation comprises:

recording, via the content management system, at the server file journal, the delete operation at a third journal record associated with the source namespace; and

recording, via the content management system, at the server file journal, the add operation at a fourth journal record associated with the destination namespace.

7. The method of claim 6, wherein assigning the third lamport clock value to the delete operation and the fourth lamport clock value to the add operation comprises:

calculating the third lamport clock value for the delete operation based on the second lamport clock value;

incrementing the third lamport clock value based on the add operation to yield the fourth lamport clock value; and

recording the third lamport clock value for the delete operation and the fourth lamport clock value for the add operation.

8. The method of claim 1, further comprising:

emitting, via the content management system, to a client device, a move of the content item from the source namespace to the destination namespace;

after emitting the move, detecting, via the content management system, a namespace unmount operation;

when the namespace unmount operation unmounts the source namespace, processing a finish operation at the destination namespace; and

when the namespace unmount operation unmounts the destination namespace, processing a finish operation at the source namespace.

9. The method of claim 8, further comprising:

prior to processing the finish operation, detecting a remount namespace operation;

when the namespace unmount operation and the remount namespace operation are associated with the source namespace;

ignoring add operations for adding the content item to the source namespace until at least processing the finish operation at the destination namespace; and

when the namespace unmount operation and the remount namespace operation are associated with the destination namespace;

ignoring one or more delete operations for removing the content item from the destination namespace until at least processing the finish operation at the source namespace.

10. The method of claim 1, further comprising:

generating a move identifier associated with the request to move the content item from the source namespace to the destination namespace; and

assigning the move identifier to each of the outgoing move operation, the incoming move operation, the delete operation, and the add operation.

11. A non-transitory computer readable medium comprising instructions, the instructions, when executed by one or more processors, cause a content management system to:

detect a mount operation associated with a user account on the content management system, the mount operation mounting a namespace for the user account at a first path;

identify a prior mount operation that mounts the namespace for the user account at a second path;

determine that the mount operation and the prior mount operation create two paths to the namespace for the user account;

identify an unmount operation for unmounting the namespace from the second path;

assign a first lamport clock to the unmount operation, the first lamport clock being higher than a respective lamport clock associated with the prior mount operation;

increment the first lamport clock to yield a second lamport clock; and

assign the second lamport clock to the mount operation.

12. The non-transitory computer readable medium of claim 11, storing instructions which, when executed by the one or more processors, cause the content management system to:

linearize the prior mount operation, the unmount operation, and the mount operation based on the respective lamport clock associated with the prior mount operation, the first lamport clock and the second lamport clock.

13. The non-transitory computer readable medium of claim 11, storing instructions which, when executed by the one or more processors, cause the content management system to:

identify a set of causally related mount operations associated with the user account;

identify a highest lamport clock from respective lamport clocks associated with the set of causally related mount operations; and

propagating a new lamport clock to the set of causally related mount operations, the new lamport clock being based on the highest lamport clock.

14. The non-transitory computer readable medium of claim 11, storing instructions which, when executed by the one or more processors, cause the content management system to:

identify a set of causally related unmount operations associated with the user account;

identify a highest lamport clock from respective lamport clocks associated with the set of causally related unmount operations; and

propagating a new lamport clock to the set of causally related unmount operations, the new lamport clock being based on the highest lamport clock.

15. A content management system 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 content management system to;

obtain a set of operations associated with a user account on the content management system, the set of operations comprising a request to move a content item from a source namespace to a destination namespace;

process an incoming move operation at the destination namespace and an outgoing move operation at the source namespace;

process a delete operation and an add operation for the content item, the delete operation being processed at the source namespace and the add operation being processed at the destination namespace;

assign a first lamport clock value to the incoming move operation and a second lamport clock value to the outgoing move operation, wherein the first lamport clock value is lower than the second lamport clock value;

assign a third lamport clock value to the delete operation and a fourth lamport clock value to the add operation, wherein the third lamport clock value is higher than the second lamport clock value and lower than the fourth lamport clock value; and

serialize the incoming move operation, the outgoing move operation, the delete operation, and the add operation based on the first lamport clock value, the second lamport clock value, the third lamport clock value, and the fourth lamport clock value.

16. The content management system of claim 15, storing instructions which, when executed by the one or more processors, cause the content management system to:

provide, to a client device, a listing of serialized operations and a cursor indicating a state of at least one of the source namespace and the destination namespace, the listing of serialized operations comprising at least one of the incoming move operation, the outgoing move operation, the delete operation, and the add operation serialized according to the first lamport clock value, the second lamport clock value, the third lamport clock value, and the fourth lamport clock value.

17. The content management system of claim 16, wherein the listing of serialized operations excludes the outgoing move operation and the add operation when the destination namespace is not mounted at the client device.

18. The content management system of claim 15, wherein processing the incoming move operation and the outgoing move operation comprises recording, at a server file journal, the incoming move operation at a first journal record associated with the destination namespace and the outgoing move operation at a second journal record associated with the source namespace, wherein assigning the third lamport clock value to the delete operation and the fourth lamport clock value to the add operation comprises:

calculating the third lamport clock value for the delete operation based on the second lamport clock value;

incrementing the third lamport clock value based on the add operation to yield the fourth lamport clock value; and

recording the third lamport clock value for the delete operation and the fourth lamport clock value for the add operation.

19. The content management system of claim 15, storing instructions which, when executed by the one or more processors, cause the content management system to:

emit, to a client device, a move of the content item from the source namespace to the destination namespace;

after emitting the move, detect a namespace unmount operation;

when the namespace unmount operation unmounts the source namespace, processing a finish operation at the destination namespace; and

when the namespace unmount operation unmounts the destination namespace, processing a finish operation at the source namespace.

20. The content management system of claim 19, storing instructions which, when executed by the one or more processors, cause the content management system to:

prior to processing the finish operation, detect a remount namespace operation;

when the namespace unmount operation and the remount namespace operation are associated with the source namespace;

ignore add operations for adding the content item to the source namespace until at least processing the finish operation at the destination namespace; and

when the namespace unmount operation and the remount namespace operation are associated with the destination namespace;

ignore one or more delete operations for removing the content item from the destination namespace until at least processing the finish operation at the source namespace.