Swarm-Based Synchronization Over a Network of Object Stores
First Claim
1. A method of synchronizing objects of an object set stored by a computer having a processor with corresponding objects of object sets stored by at least one node accessible over at least one network, the method comprising:
- executing on the processor instructions configured to;
select from the nodes a neighbor set comprising at least one neighbor that is accessible over the at least one network to the computer and other neighbors of the neighbor set; and
upon identifying an updated object in the object set;
determine the neighbors in the neighbor set that are not storing the updated object;
form a swarm network of swarm nodes comprising the neighbors not storing the updated object;
notify the swarm nodes of the swarm network formed for the updated object; and
send the updated object to the swarm nodes using the swarm network.
2 Assignments
0 Petitions
Accused Products
Abstract
An object set may be redundantly stored by a set of computers, each configured to store a local representation of corresponding objects. When a computer changes the object set (e.g., by adding or altering an object), the updated object may be synchronized across the computers by iteratively forming and using an ad hoc swarm network from the neighbors of a node storing the updated object. This swarm network may operate cooperatively, where each node distributes object chunks to other nodes as quickly as possible, and may disregard concepts of competitive swarm networks such as fairness and cheating avoidance, which may not apply to cooperative swarming and might otherwise slow the propagation of the object. An alternative “ask” technique may be included to identify and recover missed object updates, and a computing environment host may be included as an authoritative object source and/or as an object store of last resort.
50 Citations
20 Claims
-
1. A method of synchronizing objects of an object set stored by a computer having a processor with corresponding objects of object sets stored by at least one node accessible over at least one network, the method comprising:
executing on the processor instructions configured to; select from the nodes a neighbor set comprising at least one neighbor that is accessible over the at least one network to the computer and other neighbors of the neighbor set; and upon identifying an updated object in the object set; determine the neighbors in the neighbor set that are not storing the updated object; form a swarm network of swarm nodes comprising the neighbors not storing the updated object; notify the swarm nodes of the swarm network formed for the updated object; and send the updated object to the swarm nodes using the swarm network. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18)
-
19. A system configured to synchronize an updated object of an object set stored by a computer with corresponding objects of object sets stored by at least one node accessible over at least one network, the system comprising:
-
a neighbor selecting component configured to select from the nodes a neighbor set comprising at least one neighbor that is accessible over the at least one network to the computer and other neighbors of the neighbor set; a swarm network forming component configured to; determine the neighbors in the neighbor set that are not storing the updated object, form a swarm network of swarm nodes comprising the neighbors not storing the updated object, and notify the swarm nodes of the swarm network formed for the updated object; and a swarm network sending component configured to send the updated object to the swarm nodes using the swarm network.
-
-
20. A computer-readable storage medium, the medium comprising instructions that, when executed by at least one processor of a computer storing an object set comprising objects corresponding to objects of object sets stored by at least one node accessible over at least one network and stored as corresponding objects in an object store of a computing environment host, cause the at least one processor to perform:
-
upon detecting at least one network change event, selecting from the nodes a neighbor set comprising at least one neighbor by; enumerating the nodes of the network, and for respective nodes, selecting a neighbor set comprising the nodes of the network enumerated according to the formula;
Si=n×
or 2i|0≦
i<
ceiling(log2(N)), n×
or 2i<
N,wherein; Si represents neighbor i of the node; n represents the enumeration of the node; and N represents the number of nodes in the network; upon identifying a small updated object set comprising a small number of small updated objects to be delivered to a small neighbor set, send the small updated object set to the neighbors of the small neighbor set; upon identifying an updated object in the object set exceeding a small updated object set; determining the neighbors that are not storing the updated object by, for respective neighbors; sending to the neighbor an identifier of the updated object and a content indicator of the updated object, and receiving from the neighbor a notification whether the neighbor is storing the updated object forming a swarm network of swarm nodes comprising the neighbors not storing the updated object; notifying the swarm nodes of the swarm network formed for the updated object; and sending the updated object to the swarm nodes using the swarm network by; chunking the updated object into at least one chunk; initializing a swarm chunk map indicating whether respective swarm nodes are storing respective chunks of the updated object; and until the swarm chunk map indicates that the swarm nodes have received the chunks; sending a chunk to a swarm node not storing the chunk according to the swarm chunk map, and upon receiving from a swarm node a notification of storing a chunk, updating the swarm chunk map to indicate that the swarm node is storing the chunk; and upon determining from the swarm chunk map that the swarm nodes have received the chunks, terminating the swarm network; determine whether the computing environment host is storing the updated object; and upon determining that the computing environment host is not storing the updated object, send the updated object to the computing environment host; upon being notified by a neighbor of an updated object comprising an identifier and a content indicator; compare the identifier and the content indicator of the updated object to a corresponding object in the object store, and send to the neighbor a notification whether the computer is storing the updated object; upon being notified of a formation by a source of a swarm network comprising the computer for an updated object; create a corresponding updated object in the object store; generate a send queue for respective swarm nodes; create a swarm chunk map indicating whether respective swarm nodes are storing respective chunks of the updated object; until the swarm nodes have received the chunks of the object; upon receiving a chunk of the object; store the chunk in the object store, update the swarm chunk map to indicate that the computer is storing the chunk, and notify the swarm nodes and the source that the computer is storing the chunk; upon being notified that a swarm node is storing a chunk, update the swarm chunk map to indicate that the swarm node is storing the chunk; send the chunk to a swarm node not storing the chunk according to the swarm chunk map by; selecting a chunk comprising a rare chunk that is stored in the object store and that is infrequently stored among the swarm nodes according to the swarm chunk map; enqueuing the chunk in the send queue of the swarm node; upon enqueuing the chunk in an empty send queue of the swarm node, initiating sending the chunk to the swarm node; and upon completing sending a chunk to the swarm node; dequeuing the chunk from the send queue, and upon identifying a next enqueued chunk in the send queue of the swarm node, initiating sending the next enqueued chunk in the send queue to the swarm node; and updating the swarm chunk map to indicate that the swarm node is storing the chunk; and upon determining according to the swarm chunk map that the swarm nodes have received the chunks, terminate the swarm network; upon detecting a synchronization event; identify updated objects stored by at least one neighbor and not stored in the object store of the computer by requesting from the computing environment host a list of updated objects stored in the object store of the computing environment host and not stored in the object store of the computer; upon identifying an updated object stored by at least one neighbor and not stored in the object store of the computer; create the updated object in the object store; chunk the updated object into at least one chunk; and upon failing to receive at least one chunk of an updated object from the neighbors; request the at least one chunk from the computing environment host, and upon receiving the at least one chunk from the computing environment host, store the at least one chunk in the object store; until the chunks of the updated object are stored in the object store; request at least one chunk not stored in the object store from a neighbor storing the chunk, and upon receiving the chunk from the neighbor, store the chunk in the object store; and for objects stored in the object set of the computer that are not stored in the object set of at least one neighbor, identify the object as an updated object; and upon receiving from a neighbor a request for a chunk of an object stored in the object store of the computer, send the chunk of the object to the neighbor.
-
Specification