Atomic moves with lamport clocks in a content management system

Patent metadata

Field	Value
Publication number	US-10726044-B2
Application number	US-201815873693-A
Country	US
Kind code	B2
Filing date	Jan 17, 2018
Priority date	Dec 28, 2017
Publication date	Jul 28, 2020
Grant date	Jul 28, 2020

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.

First claim

What is claimed is:

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

Assignees

• Dropbox Inc

Inventors

• Koorapati Nipunn
• Wetterau David
• Walker Braden
• Cowling James
• Jayakar Sujay

Classifications

• G06F16/27 Primary

  Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor · CPC title

• G06F16/11 Primary

  File system administration, e.g. details of archiving or snapshots (error detection or correction of the data by redundancy in operations G06F11/14) · CPC title

• H04L67/01

  Protocols · CPC title

• G06F16/178 Primary

  Techniques for file synchronisation in file systems · CPC title

• G06F16/1767

  Concurrency control, e.g. optimistic or pessimistic approaches · CPC title