Efficiently propagating diff values

Patent metadata

Field	Value
Publication number	US-11048720-B2
Application number	US-201715858207-A
Country	US
Kind code	B2
Filing date	Dec 29, 2017
Priority date	Dec 28, 2017
Publication date	Jun 29, 2021
Grant date	Jun 29, 2021

Abstract

The disclosed technology relates to a system configured to detect a modification to a node in a tree data structure. The node is associated with a content item managed by a content management service as well as a filename. The system may append the filename and a separator to a filename array, determine a location of the filename in the filename array, and store the location of the filename in the node.

First claim

What is claimed is:

1. A computer-implemented method to determine changes in a tree data structure upon adding a new leaf node that avoids recalculating a hash value for each ancestor node in the tree data structure, the computer-implemented method comprising:
receiving modification data for content items stored by a content management system;
adding the new leaf node in the tree data structure based on the modification data, the tree data structure representing content items at the content management system, wherein parent nodes in the tree data structure are assigned diff values calculated based on a hash of a sum of diff values of their respective child nodes;
calculating a diff value for the new leaf node;
calculating a new diff value for a parent of the new leaf node by performing an exclusive-or (XOR) operation using a current diff value of a parent node and the diff value of the added new leaf node;
storing the new diff value for the parent in the parent node without changing diff values of any other node in the tree data structure;
comparing the diff value of the added new leaf node in the tree data structure with a second diff value for a corresponding node in a different tree data structure;
identifying a difference between the tree data structure and the different tree data structure based on the comparing; and
generate a set of operations based on the difference.

2. The computer-implemented method of claim 1 , wherein the tree data structure is one of a local tree, a remote tree, or a sync tree.

3. The computer-implemented method of claim 1 , wherein the diff value for the new leaf node is calculated using a hash of the new leaf node.

4. The computer-implemented method of claim 1 , further comprising:
managing execution of the set of operations.

5. The computer-implemented method of claim 4 , further comprising transmitting the set of operations to the content management system.

6. The computer-implemented method of claim 1 , wherein the new leaf node represents a content item associated with a content management service.

7. The computer-implemented method of claim 1 , wherein the new diff value is zero if the current diff value of the parent node and the diff value of the added node are identical.

8. The computer-implemented method of claim 1 , wherein no other node is updated in order for the new diff value to be stored.

9. A non-transitory computer-readable medium to determine changes in a sync tree upon adding a new leaf node that avoids recalculating a hash value for each ancestor node in the sync tree, the non-transitory computer-readable medium comprising instructions, the instructions, when executed by a computing system, cause the computing system to:
receive modification data for content items stored by a content management system;
add a new leaf node in a sync tree based on the modification data, wherein parent nodes in the sync tree are assigned diff values calculated based on a hash of a sum of diff values of their respective child nodes;
calculate a diff value for the new leaf node in the sync tree, wherein the sync tree represents a known synced state between a server state and a file system state, wherein diff values for nodes in the sync tree are numerical values;
calculate a new diff value for a parent node of the new leaf node by performing an exclusive-or (XOR) operation on a current diff value of the parent node and the diff value of the new leaf node;
store the new diff value for the parent node without changing diff values of any other node in the sync tree;
compare the diff value of the added new leaf node in the sync tree with a second diff value for a corresponding node in a different tree data structure;
identify a difference between the sync tree and the different tree data structure based on the comparing; and
generate a set of operations based on the difference.

10. The non-transitory computer-readable medium of claim 9 , wherein the instructions further cause the computing system to add the node in the sync tree.

11. The non-transitory computer-readable medium of claim 9 , wherein the set of operations is configured to operate on content items stored on a client device to converge the server state and the file system state.

12. The non-transitory computer-readable medium of claim 9 , wherein the different tree data structure is a local tree.

13. A device comprising:
one or more processors; and
at least one memory having instructions stored thereon, that when executed the instructions are effective to cause the one or more processors to:
receive modification data for content items stored by a content management system;
add a new leaf node in a sync tree based on the modification data, wherein parent nodes in the sync tree are assigned diff values calculated based on a hash of a sum of diff values of their respective child nodes;
calculate a diff value for the new leaf node in the sync tree, wherein the sync tree represents a known synced state between a server state and a file system state, wherein diff values for nodes in the sync tree are numerical values;
calculate a new diff value for a parent node of the new leaf node by performing an exclusive-or (XOR) operation on a current diff value of the parent node and the diff value of the new leaf node;
store the new diff value for the parent node without changing diff values of any other node in the sync tree;
compare the diff value of the added new leaf node in the sync tree with a second diff value for a corresponding node in a different tree data structure;
identify a difference between the sync tree and the different tree data structure based on the comparing; and
generate a set of operations based on the difference.

14. The device of claim 13 , wherein the set of operations is configured to operate on content items stored on the device to converge the server state and the file system state.

15. The device of claim 13 , wherein the new diff value is zero if the current diff value of the parent node and the diff value of the added new leaf node are identical.

16. The device of claim 13 , further comprising transmitting the set of operations to the content management system.

Assignees

• Dropbox Inc

Inventors

• 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/1734

  Details of monitoring file system events, e.g. by the use of hooks, filter drivers, logs · CPC title

• G06F16/178 Primary

  Techniques for file synchronisation in file systems · CPC title