Randomized peer-to-peer synchronization of shared content items

• US 9,479,578 B1
• Filed: 12/31/2015
• Issued: 10/25/2016
• Est. Priority Date: 12/31/2015
• Status: Active Grant

• Current Assignee: Dropbox, Inc.
• Original Assignee: Dropbox, Inc.
• Inventors: Swanson, Eric
• Primary Examiner(s): Vostal, O. C.
• Application Number:
  US14/985,974
• Time in Patent Office: 299 Days
• Field of Search: 709/201
• US Class Current: 1/1
• CPC Class Codes: H04L 65/611 for multicast or broadcast systems for broadcast or conference H04L12/18; arrangements for broadcast or distribution combined with broadcast H04H20/00; arrangements for broadcast applications with a direct linkage to broadcast information or to broadcast space-time H04H60/00; selective distribution of broadcast services, e.g. multimedia broadcast multicast service [MBMS], H04W4/06
• CPC Class Codes: H04L 65/80 Responding to QoS
• CPC Class Codes: H04L 67/1042 using topology management mechanisms
• CPC Class Codes: H04W 4/06 Selective distribution of broadcast services, e.g. multimedia broadcast multicast service [MBMS]; Services to user groups; One-way selective calling services

Abstract

A content management system synchronizes content items across client computing systems connected by a network. Client devices connected to peer devices on a LAN utilize peer-to-peer synchronization to synchronize content items. Client devices on the LAN broadcast namespaces synchronized on the client devices with other devices on the LAN. Client devices on the LAN connect to a subset of client devices that share a namespace with the connecting client device based on the broadcasts. Upon receiving a notification from the content management system that a new content item has been synchronized with the namespace a client device sends requests for a block comprising a content item to a subset of the connected devices. Additional block requests are sent in the order of randomized blocklist.

Claims

1. A method comprising:

on a first client device associated with a first namespace and communicating on a local area network (LAN) and with a content management system on a network other than the LAN, storing one or more content items associated with the namespace, each content item including one or more blocks;

receiving, by the first client device, broadcasts from a plurality of other client devices, each broadcast identifying one or more namespaces associated with the broadcasting client device;

identifying, by the first client device, from the received broadcasts, a group of one or more of the broadcasting client devices broadcasting the first namespace;

connecting, by the first client device, to a subset of the identified group of broadcasting client devices, the subset of client devices being associated with the first namespace and communicating with the content management system and on the LAN;

receiving, by the first client device, a notification from the content management system that a new content item is associated with the first namespace, wherein the new content item includes a plurality of blocks, the plurality of blocks arranged in a randomized block list;

selecting, by the first client device, a set of the connected client devices storing the first namespace;

sending, by the first client device, a first request to each of the selected set of the connected client devices requesting a first block of the plurality of blocks in the randomized block list;

responsive to determining, by the first client device, that none of the selected set of the connected client devices are storing the first block, downloading the first block from the content management system;

sending, by the first client device, a second request to each of the selected set of the connected client devices requesting a second block of the plurality of blocks in the randomized block list; and

responsive to determining, by the first client device, that a client device of the selected set of the connected client devices is storing the second block, downloading the second block from the client device that is storing the second block.

2. The method of claim 1, wherein connecting, by the first client device, to a subset of the identified broadcasting client devices further comprises connecting to a randomly selected subset of the identified broadcasting client devices, the subset of the client devices being associated with the first namespace and communicating with the content management system and on the LAN.

3. The method of claim 1, wherein selecting, by the first client device, a set of the connected client devices storing the first namespace further comprises:

determining, for each of the connected client devices, a weight based on current network characteristics of that client device;

generating randomly a modification value for each of the connected client devices;

modifying for each of the connected client devices the weight by the modification value; and

selecting, by the first client device, a set of the connected client devices storing the first namespace based on the modified weights of the group of the connected client devices.

4. The method of claim 1 further comprising measuring a least one of the current network characteristics for each client device in the group of client devices.

5. The method of claim 1, wherein historical network characteristics are at least one of:

a broadcast frequency for each client device,

an average latency for each client device,

a connection success rate for each client device, and

an average connection speed of the client device.

6. The method of claim 1, wherein current network characteristics are at least one of:

a current bandwidth of each client device,

a number of requests received within a predetermined time interval of each client device,

a number of namespaces synchronized with each client device,

a communication status with the content management system of each client device, and

a current latency of each client device.

7. The method of claim 1, further comprising:

determining, by the first client device, for each of the other client devices, a weight based on historical network characteristics of that client device; and

modifying, by the first client device, each weight by a randomly generated value; and

connecting, by the first client device, to a subset of the other client devices based on the modified weight.

8. A system comprising:

a processor; and

a memory storing instructions that, when executed by the processor, cause the processor to;

on a first client device associated with a first namespace and communicating on a local area network (LAN) and with a content management system on a network other than the LAN, storing one or more content items associated with the namespace, each content item including one or more blocks;

receive, by the first client device, broadcasts from a plurality of other client devices, each broadcast identifying one or more namespaces associated with the broadcasting client device;

identify, by the first client device, from the received broadcasts, a group of one or more of the broadcasting client devices broadcasting the first namespace;

connect, by the first client device, to a subset of the identified group of broadcasting client devices, the subset of client devices being associated with the first namespace and communicating with the content management system and on the LAN;

receive, by the first client device, a notification from the content management system that a new content item is associated with the first namespace, wherein the new content item includes a plurality of blocks, the plurality of blocks arranged in a randomized block list;

select, by the first client device, a set of the connected client devices storing the first namespace;

send, by the first client device, a first request to each of the selected set of the connected client devices requesting a first block of the plurality of blocks in the randomized block list;

responsive to determining, by the first client device, that none of the selected set of the connected client devices are storing the first block;

download the first block from the content management system;

send, by the first client device, a second request to each of the selected set of the connected client devices requesting a second block of the plurality of blocks in the randomized block list; and

responsive to determining, by the first client device, that a client device of the selected set of the connected client devices is storing the second block, download the second block from the client device that is storing the second block.

9. The system of claim 8, wherein the memory stores further instructions that cause the processor to connect, by the first client device, to a subset of the identified broadcasting client devices further comprises connecting to a randomly selected subset of the identified broadcasting client devices, the subset of the client devices being associated with the first namespace and communicating with the content management system and on the LAN.

10. The system of claim 8, wherein the memory stores further instructions causing the processor to select, by the first client device, a set of the connected client devices storing the first namespace further comprises:

determine, for each of the connected client devices, a weight based on current network characteristics of that client device;

generate randomly a modification value for each of the connected client devices;

modify for each of the connected client devices the weight by the modification value; and

select, by the first client device, a set of the connected client devices storing the first namespace based on the modified weights of the group of the connected client devices.

11. The system of claim 8 wherein the memory stores further instructions causing the processor to measure a least one of the current network characteristics for each client device in the group of client devices.

12. The system of claim 8, wherein historical network characteristics are at least one of:

a broadcast frequency for each client device,

an average latency for each client device,

a connection success rate for each client device, and

an average connection speed of the client device.

13. The system of claim 8, wherein current network characteristics are at least one of:

a current bandwidth of each client device,

a number of requests received within a predetermined time interval of each client device,

a number of namespaces synchronized with each client device,

a communication status with the content management system of each client device, and

a current latency of each client device.

14. The system of claim 8, wherein the memory stores further instructions causing the processor to:

determine, by the first client device, for each of the other client devices, a weight based on historical network characteristics of that client device; and

modify, by the first client device, each weight by a randomly generated value; and

connect, by the first client device, to a subset of the other client devices based on the modified weight.

15. A non-transitory computer readable storage medium storing instructions that, when executed by a processor causes the process to perform steps of:

on a first client device associated with a first namespace and communicating on a local area network (LAN) and with a content management system on a network other than the LAN, storing one or more content items associated with the namespace, each content item including one or more blocks;

receiving, by the first client device, broadcasts from a plurality of other client devices, each broadcast identifying one or more namespaces associated with the broadcasting client device;

identifying, by the first client device, from the received broadcasts, a group of one or more of the broadcasting client devices broadcasting the first namespace;

connecting, by the first client device, to a subset of the identified group of broadcasting client devices, the subset of client devices being associated with the first namespace and communicating with the content management system and on the LAN;

receiving, by the first client device, a notification from the content management system that a new content item is associated with the first namespace, wherein the new content item includes a plurality of blocks, the plurality of blocks arranged in a randomized block list;

selecting, by the first client device, a set of the connected client devices storing the first namespace;

sending, by the first client device, a first request to each of the selected set of the connected client devices requesting a first block of the plurality of blocks in the randomized block list;

responsive to determining, by the first client device, that none of the selected set of the connected client devices are storing the first block, downloading the first block from the content management system;

sending, by the first client device, a second request to each of the selected set of the connected client devices requesting a second block of the plurality of blocks in the randomized block list; and

responsive to determining, by the first client device, that a client device of the selected set of the connected client devices is storing the second block, downloading the second block from the client device that is storing the second block.

16. The non-transitory computer readable storage medium of claim 15, wherein connecting, by the first client device, to a subset of the identified broadcasting client devices further comprises connecting to a randomly selected subset of the identified broadcasting client devices, the subset of the client devices being associated with the first namespace and communicating with the content management system and on the LAN.

17. The non-transitory computer readable storage medium of claim 15, wherein selecting, by the first client device, a set of the connected client devices storing the first namespace further comprises:

determining, for each of the connected client devices, a weight based on current network characteristics of that client device;

generating randomly a modification value for each of the connected client devices;

modifying for each of the connected client devices the weight by the modification value; and

selecting, by the first client device, a set of the connected client devices storing the first namespace based on the modified weights of the group of the connected client devices.

18. The non-transitory computer readable storage medium of claim 15 further comprising instructions to perform the step of measuring a least one of the current network characteristics for each client device in the group of client devices.

19. The non-transitory computer readable storage medium of claim 15, wherein historical network characteristics are at least one of:

a broadcast frequency for each client device,

an average latency for each client device,

a connection success rate for each client device, and

an average connection speed of the client device.

20. The non-transitory computer readable storage medium of claim 15, wherein current network characteristics are at least one of:

a current bandwidth of each client device,

a number of requests received within a predetermined time interval of each client device,

a number of namespaces synchronized with each client device,

a communication status with the content management system of each client device, and

a current latency of each client device.