Randomized peer-to-peer synchronization of shared content items

• US 10,021,184 B2
• Filed: 10/14/2016
• Issued: 07/10/2018
• 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:
  US15/294,641
• Publication Number:
  US 20170195416A1
• Time in Patent Office: 634 Days
• Field of Search: 709201
• CPC Class Codes: G06F 16/176 Support for shared access to files; File sharing support
• CPC Class Codes: G06F 16/178 Techniques for file synchronisation in file systems
• CPC Class Codes: H04L 67/104 Peer-to-peer [P2P] networks
• CPC Class Codes: H04L 67/1095 Replication or mirroring of data, e.g. scheduling or transport for data synchronisation between network nodes

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 non-transitory computer-readable storage medium storing instructions that, when executed by a first client device of a plurality of client devices communicating with a local area network (LAN) and communicating with a content management system that is on a network other than the LAN, cause the first client device to perform operations comprising:

receiving, from the content management system, a synchronization notification indicating that the first client device is to synchronize a content item, wherein the content item comprises a plurality of blocks, the synchronizing comprising;

requesting from the plurality of client devices communicating on the LAN a first block in a randomized blocklist, the randomized blocklist specifying a random order of the plurality of blocks;

in response to determining from the request that a second device of the plurality of client devices has a copy of the requested first block identified in the randomized blocklist, downloading the first block from the second client device; and

in response to receiving from a third device of the plurality of client devices a request for the first block, sending the first block to the third device, the third device including a second randomized blocklist specifying a second random order of the plurality of blocks and configured to request the first block in response to downloading blocks preceding the first block within the second randomized blocklist.

2. The non-transitory computer-readable storage medium of claim 1, further comprising, in response to determining from the request that none of the plurality of client devices has a copy of the requested first block, downloading the requested first block from the content management system.

3. The non-transitory computer-readable storage medium of claim 1, wherein the content item and the first client device are associated with the namespace.

4. The non-transitory computer-readable storage medium of claim 1, wherein requesting from the plurality of client devices communicating on the LAN a first block in the blocklist comprises:

receiving broadcasts the one or more client devices communicating on the LAN, each broadcast identifying one or more namespaces associated with the broadcasting client device; and

identifying from the received broadcasts, a group of one or more broadcasting client devices broadcasting a namespace associated with the first client device.

5. The non-transitory computer-readable storage medium of claim 1, wherein synchronizing further comprises:

in response to determining that none of the one or more client devices also communicating on the LAN has a copy of the first block;

downloading the first block from the content management system; and

in response to determining that a fourth client device from the one or more client devices also communicating on the LAN has a copy of a second block identified in the blocklist, downloading the second block from the fourth client device.

6. The non-transitory computer-readable storage medium of claim 1, wherein determining that the second client device from one or more client devices also communicating on the LAN has a copy of the first block identified in the blocklist and downloading the first block from the second client device, further comprises:

sending a request to the second client device, the request including the randomized blocklist; and

downloading blocks from the randomized blocklist that are stored on the second client device in the order of the randomized blocklist.

7. The non-transitory computer-readable storage medium of claim 1, wherein the first client device performs operations further comprising:

selecting the second client device from the one or more client devices communicating on the LAN based on network characteristics of the LAN; and

sending a request to the second client device, the request requesting the first block.

8. The non-transitory computer-readable storage medium of claim 1, wherein the randomized blocklist and the second randomized blocklist are generated by the content management system.

9. The non-transitory computer-readable storage medium of claim 1, wherein the request for the first block includes the randomized blocklist.

10. A non-transitory computer-readable storage medium storing instructions that, when executed by a first client device of a plurality of client devices communicating with a local area network (LAN) and communicating with a content management system that is on a network other than the LAN, cause the first client device to perform operations comprising:

receiving, from the content management system, a synchronization notification indicating that the first client device is to synchronize a content item, wherein the content item comprises a plurality of blocks, the synchronizing comprising;

requesting from the plurality of client devices communicating on the LAN a first block in a randomized blocklist, the randomized blocklist specifying a random order of the plurality of blocks;

downloading the requested first block; and

in response to receiving, from a second client device on the LAN authorized to access the content item, a request for the first block, sending the first block to the second client device, the second client device including a second randomized blocklist specifying a second randomized ordering of the plurality of blocks and configured to request the first block in response to downloading blocks preceding the first block within the second randomized blocklist.

11. The non-transitory computer-readable storage medium of claim 10, wherein the content item and the first client device are associated with a same namespace.

12. The non-transitory computer-readable storage medium of claim 10, wherein downloading the first block further comprises, downloading the block from the content management system.

13. The non-transitory computer-readable storage medium of claim 10, wherein downloading the first block specified in the blocklist further comprises, downloading the block from a third client device, different from the second client device, communicating on the LAN.

14. A non-transitory computer-readable storage medium storing instructions that, when executed by a content management system, cause the content management system to perform operations comprising:

sending, to a first client device and a second client device, a synchronization notification associated with a content item in a namespace, wherein the content item includes a plurality of blocks, and wherein the first client device and the second client device are associated with a same namespace and a same local area network (LAN); and

in response to receiving a first synchronization request from the first client device, the first synchronization request specifying a first block from a first randomized order of the plurality of blocks, sending the first block to the first client device;

wherein the first client device is configured to send the first block to the second client device in response to receiving a request for the first block from the second client device, the second client device including a second randomized order of the plurality of blocks and configured to request the first block in response to downloading blocks preceding the first block within the second randomized order.

15. The non-transitory computer-readable storage medium of claim 14, wherein the first randomized order is different from the second randomized order.

16. The non-transitory computer-readable storage medium of claim 15, wherein the first block is different from the second block.

17. The non-transitory computer-readable storage medium of claim 14, wherein sending the synchronization notification is in response to a third client device adding the content item to the same namespace.

18. The non-transitory computer-readable storage medium of claim 14, wherein sending the synchronization notification is in response to a third client device modifying the content item.