Adaptive and dynamic replication management in cloud computing

• US 9,002,939 B2
• Filed: 06/03/2012
• Issued: 04/07/2015
• Est. Priority Date: 06/03/2012
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Laden, Guy, Melamed, Roie
• Primary Examiner(s): Etienne, Ario
• Assistant Examiner(s): MENDAYE, KIDEST H
• Application Number:
  US13/487,203
• Publication Number:
  US 20130325950A1
• Time in Patent Office: 1,038 Days
• Field of Search: None
• US Class Current: 709/204
• CPC Class Codes: H04L 67/1095 Replication or mirroring of data, e.g. scheduling or transport for data synchronisation between network nodes

Abstract

A system for communicating information among a plurality of nodes of a network. The system comprises a plurality of disseminating modules installed in a plurality of nodes of a network which hosts a plurality of replicas of data having a plurality of objects, each the disseminating module has access to a dataset defining a plurality of write request dissemination topologies. Each disseminating module is defined to receive a write request from a client, to select dynamically one of the write request dissemination topologies according to at least one parameter of the client, and to disseminate the write request according to the selected write request dissemination topology.

Claims

1. A system for communicating information among a plurality of nodes of a network, comprising:

a plurality of disseminating modules installed in a plurality of nodes of a network which hosts a plurality of replicas of data having a plurality of objects, each said disseminating module has access to a dataset defining a plurality of write request dissemination topologies;

wherein each said disseminating module is defined to receive a write request from a client, to select dynamically one of said plurality of write request dissemination topologies according to at least one parameter of said client, and to disseminate said write request according to said selected write request dissemination topology;

wherein each of said plurality of nodes is set to receive a read request to read a selected object of a plurality of objects of said data and to retrieve a copy of said object from a respective of said plurality of replicas;

wherein each of said plurality of nodes manages a dataset indicative of which of said plurality of objects has been updated by said write request and not acknowledged by a common tail node;

wherein each of said plurality of nodes forwards said read request to said common tail node if according to said dataset said selected object has been updated said write request and not acknowledged by said common tail node.

2. The system of claim 1, wherein said disseminating module is defined to disseminate said write request in association with an indicator of said selected write request dissemination topology so as to allow any of other of said plurality of disseminating modules to further disseminate said write request in said network according to said selected write request dissemination topology.

3. The system of claim 2, wherein each said disseminating module forwards an acknowledge message to indicate a compliance with said write request to a common tail node in a reverse version of said selected write request dissemination topology.

4. The system of claim 1, wherein each said disseminating module includes a counter that increments when any write request is received and said disseminating module adds to each said write request a clock dataset so as to allow any of other of said plurality of disseminating modules to add a time tag set according to said counter before further disseminating said write request in said network.

5. The system of claim 4, wherein said clock dataset is used for ordering a disseminating of a plurality of write request including said write request.

6. The system of claim 1, wherein each said disseminating module is defined to receive a read request to read an object of said data from said client and to provide said client with said object from a respective said replica.

7. The system of claim 1, further comprising at least one probe to detect a change in a performance of at least one of said plurality of replicas and a service module sends update messages to update said plurality of write request dissemination topologies according to said change.

8. The system of claim 1, further comprising at least one probe to detect a change in said at least one parameter and a service module which disseminates an update message among at least some of said plurality of nodes to update said plurality of write request dissemination topologies according to said change.

9. The system of claim 8, wherein each of said at least some of said plurality of nodes forward said update message to another of said at least some nodes, waits for an acknowledge message for a predefined period, and forwards said update message to further another of said at least some nodes if said acknowledge message is not received.

10. A system for communicating information among a plurality of nodes of a network, comprising:

a plurality of disseminating modules installed in a plurality of nodes of a network which hosts a plurality of replicas of data having a plurality of objects, each said disseminating module has access to a dataset defining a plurality of write request dissemination topologies;

wherein each said disseminating module is defined to receive a write request from a client, to select dynamically one of said plurality of write request dissemination topologies according to at least one parameter of said client, and to disseminate said write request according to said selected write request dissemination topology;

wherein said disseminating module is defined to disseminate said write request in association with an indicator of said selected write request dissemination topology so as to allow any of other of said plurality of disseminating modules to further disseminate said write request in said network according to said selected write request dissemination topology;

wherein each said disseminating module forwards an acknowledge message to indicate a compliance with said write request to a common tail node in a reverse version of said selected write request dissemination topology;

wherein said common tail node sends a write request acknowledgment message to said client after receiving said acknowledgment message from at least some of said plurality of disseminating modules.

11. A method for communicating information among a plurality of nodes of a network, comprising:

managing a plurality of replicas of data, said plurality of replicas being stored in a plurality of nodes of a network with one of a plurality of disseminating modules; and

at any of said plurality of nodes a respective disseminating module is defined for;

receiving a write request from a client;

dynamically selecting one of a plurality of write request dissemination topologies according to at least one parameter of at least one of said client, said network and said write request; and

disseminating said write request according to said selected write request dissemination topology;

wherein each of said plurality of write request dissemination topologies defines one of said plurality of nodes as a tail node to which each other node which receives said write request sends a respective acknowledge message.

12. The method of claim 11, wherein a consistent estimator measure of said data remains strongly consistent when at least one of said plurality of replicas fails to follow said write request.

13. The method of claim 11, wherein said write request is disseminated in association with an indicator of said selected write request dissemination topology so as to allow respective said disseminating modules of other of said plurality of nodes to further disseminate said write request in said network.

14. The method of claim 11, wherein each of said plurality of write request dissemination topologies provides a different a tradeoff between latency and throughput.

15. The method of claim 11, wherein said at least one parameter is of said client and selected from a group consisting of a service level agreement (SLA) of said client, a payment plan of said client and a ranking of said client.

16. The method of claim 11, wherein said at least one parameter is of said network and selected from a group consisting of a throughput probing outcomes and latency probing outcomes.

17. The method of claim 11, wherein said at least one parameter is of said write request and selected from a group consisting of a size of said write request, an origin of said write request, a latency indicator of said write request.

18. The method of claim 11, wherein according to at least one of said plurality of write request dissemination topologies a first node forwards said write request to a group of nodes each disseminates said write request in a different chain of nodes.

19. The method of claim 11, wherein according to at least one of said plurality of write request dissemination topologies is a star topology.

20. A computer program product for communicating information among a plurality of nodes of a network, comprising:

a non-transitory computer readable storage medium;

first program instructions to manage a plurality of replicas of data, said plurality of replicas being stored in a plurality of nodes of a network with one of a plurality of disseminating modules; and

second program instructions to be used by any of said plurality of disseminating modules for;

receiving a write request from a client;

dynamically selecting one of a plurality of write request dissemination topologies according to at least one parameter of at least one of said client, said network and said write request; and

disseminating said write request according to said selected write request dissemination topology;

wherein said first and second program instructions are stored on said non transitory computer readable storage medium;

wherein each of said plurality of nodes is set to receive a read request to read a selected object of a plurality of objects of said data and to retrieve a copy of said object from a respective of said plurality of replicas;

wherein each of said plurality of nodes manages a dataset indicative of which of said plurality of objects has been updated by said write request and not acknowledged by a common tail node;

wherein each of said plurality of nodes forwards said read request to said common tail node if according to said dataset said selected object has been updated said write request and not acknowledged by said common tail node.

21. A method for communicating information among a plurality of nodes of a network, comprising:

storing a replica of data in a node of a network having a plurality of nodes storing a plurality of replicas;

receiving a write request to update said data at said node from a client;

dynamically selecting a write request dissemination topology from a plurality of write request dissemination topologies according to at least one parameter of at least one of said client, said network, and said write request; and

disseminating said write request among said plurality of nodes according to said selected write request dissemination topology in association with an indicator of said selected write request dissemination topology;

wherein each of said plurality of write request dissemination topologies defines one of said plurality of nodes as a tail node to which each other node which receives said write request sends a respective acknowledge message.

22. The method of claim 21, wherein said receiving comprises adding a time tag to said write request so as to allow another of said plurality of nodes to order the processing of said write request accordingly.

23. The method of claim 22, wherein said time tag is one of a plurality of time tags added by said plurality of nodes to said write request during said disseminating.

24. The method of claim 21, wherein a consistent estimator measure of said data remains strongly consistent when at least one of said plurality of replicas fails to follow said write request.

25. A computer program product for communicating information among a plurality of nodes of a network, comprising:

a non transitory computer readable storage medium;

first program instructions to store a replica of data in a node of a network having a plurality of nodes;

second program instructions to receive a write request to update said data at said node from a client;

third program instructions to dynamically select a write request dissemination topology from a plurality of write request dissemination topologies according to at least one parameter of at least one of said client, said network, and said write request; and

fourth program instructions to disseminate said write request among said plurality of nodes according to said selected write request dissemination topology in association with an indicator of said selected write request dissemination topology;

wherein said first, second, third, and fourth program instructions are stored on said non transitory computer readable storage medium;

wherein each of said plurality of write request dissemination topologies defines one of said plurality of nodes as a tail node to which each other node which receives said write request sends a respective acknowledge message.