Methods and Apparatus for Efficiently Placing Stream Transforms Among Broker Machines Comprising an Overlay Network in a Publish-Subscribe Messaging System

• US 20080177880A1
• Filed: 03/21/2008
• Published: 07/24/2008
• Est. Priority Date: 03/10/2005
• Status: Active Grant

• Current Assignee: X Corp. (f/k/a Twitter, Inc.) (X Holdings Corp.)
• Original Assignee: International Business Machines Corporation
• Inventors: Ginis, Roman
• Granted Patent: US 7,756,925 B2
• Time in Patent Office: Days
• US Class Current: 709/226
• CPC Class Codes: H04L 67/1001 for accessing one among a plurality of replicated servers

Abstract

The methods and apparatus of the present invention operate in publish-subscribe messaging systems including at least publishing clients, subscribing clients and a plurality of broker machines. The broker machines form an overlay network responsible for receiving input messages from publishing clients, transforming information contained in the input messages according to pre-determined transformation specifications, and transmitting output messages containing the transformed information to the subscribing clients. The pre-determined transformation specifications are reduced to information transforms implemented as software modules that are distributed among the broker machines. The present invention provides methods and apparatus for placing transforms among the broker machines comprising the overlay network in such a way that the latency and throughput of messaging activities executed by the broker machines of the overlay network is improved.

Claims

1. A signal-bearing medium tangibly embodying a program of machine-readable instructions executable by a digital processing apparatus of a computer system to perform operations controlling a publish-subscribe messaging system, where the publish-subscribe messaging system comprises publishing clients, subscribing clients, and a plurality of broker machines, the plurality of broker machines comprising an overlay network that accepts input message streams from publishing clients, transforms input message streams into output message streams according to pre-determined message transformation criteria, where the criteria are contained in message transforms implemented as software modules, the software modules being distributed among the broker machines, and then delivers the output message streams to the subscribing clients, the operations comprising:

selecting at least one performance parameter corresponding to a performance measure of the publish-subscribe messaging system;

monitoring a level of resource utilization of the overlay network;

making a provisional assignment of message transforms among the broker machines;

performing calculations to determine a value of the at least one performance parameter of the publish-subscribe messaging system in accordance with the provisional assignment of message transforms and the level of resource utilization of the overlay network; and

deciding if the provisional assignment of the message transforms among the broker machines results in an acceptable value of the at least one performance parameter and, if it does,

assigning the message transforms among the broker machines in accordance with the provisional assignment.

2. The signal-bearing medium of claim 1 where the operations further comprise:

if an acceptable value for the performance parameter is not reached, continuing to make additional provisional message transform assignments among the broker machines and to calculate a value of the performance parameter corresponding to each of the additional provisional message transform assignments until an acceptable value of the performance parameter is reached; and

assigning the message transforms among the broker machines in accordance with the provisional message transform assignment resulting in the acceptable value of the performance parameter.

3. The signal-bearing medium of claim 1 where the performance parameter is message throughput.

4. The signal-bearing medium of claim 1 where the performance parameter is message latency.

5. The signal-bearing medium of claim 1 where the message transforms operate on one input message at a time to create an output message for delivery to the subscribing client.

6. The signal-bearing medium of claim 1 where the message transforms operate on at least two input messages at a time to create an output message for delivery to the subscribing client.

7. The signal-bearing medium of claim 1 where the predetermined message transformation criteria are established by at least one message service provider.

8. The signal-bearing medium of claim 1:

where selecting at least one performance parameter further comprises selecting at least two performance parameters, a first performance parameter being message latency and a second performance parameter being message throughput;

where performing calculations further comprises

determining values for message latency and message throughput based, at least in part, on the level or resource utilization of the overlay network;

calculating a value of an objective function based on values calculated for message latency and message throughput; and

where deciding if the provisional assignment of the message transforms among the broker machines results in an acceptable value of the performance parameter further comprises deciding if the provisional assignment results in an acceptable value of the objective function.

9. The signal-bearing medium of claim 8 where the operations further comprise:

if an acceptable value for the objective value is not reached, continuing to make additional provisional assignments among the broker machines and to calculate a value of the objective function corresponding to each of the additional provisional message transform assignments until an acceptable value of the objective function is reached, where the value of the objective function for each of additional provisional message transform assignments is based on calculations of message latency and message throughput for that provisional message transform assignment; and

assigning the message transforms among the broker machines in accordance with the provisional message transform assignment resulting in the acceptable value of the performance parameter.

10. The signal-bearing medium of claim 8 where the message transforms operate in a stateful manner.

11. A system for managing operations of an overlay network comprising a plurality of broker machines in a publish-subscribe messaging system, where the publish-subscribe messaging system comprises publishing clients, subscribing clients, and the plurality of broker machines, the plurality of broker machines comprising the overlay network that accepts input message streams from publishing clients, transforms input message streams into output message streams according to pre-determined message transformation criteria, where the criteria are contained in message transforms implemented as software modules, the software modules being distributed among the broker machines, and then delivers the output message streams to the subscribing clients, the system comprising:

at least one memory to store at least one program of machine-readable instructions, where the at least one program performs operations to distribute the message transforms among the broker machines;

a plurality of sensors to measure a level of resource utilization of the overlay network; and

at least one processor coupled to the at least one memory, plurality of sensors and overlay network, where the at least one processor performs at least the following operations when executed;

selecting at least one performance parameter corresponding to a performance measure of the publish-subscribe messaging system;

monitoring the level of resource utilization of the overlay network;

making a provisional assignment of message transforms among the broker machines;

performing calculations to determine a value of the at least one performance parameter of the publish-subscribe messaging system in accordance with the provisional assignment of message transforms and the level of resource utilization of the overlay network; and

deciding if the provisional assignment of the message transforms among the broker machines results in an acceptable value of the at least one performance parameter and, if it does,

assigning the message transforms among the broker machines in accordance with the provisional assignment.

12. The system of claim 11 where the operations further comprise:

if an acceptable value for the performance parameter is not reached, continuing to make additional provisional message transform assignments among the broker machines and to calculate a value of the performance parameter corresponding to each of the additional provisional message transform assignments until an acceptable value of the performance parameter is reached; and

assigning the message transforms among the broker machines in accordance with the provisional message transform assignment resulting in the acceptable value of the performance parameter.

13. The system of claim 11 where the performance parameter is message throughput.

14. The system of claim 11 where the performance parameter is message latency.

15. The system of claim 11 where the message transforms operate on one input message at a time to create an output message for delivery to the subscribing clients.

16. The system of claim 11 where the message transforms operate on at least two input messages at a time to create an output message for delivery to the subscribing clients.

17. The system of claim 11 where the predetermined message transformation criteria are established by at least one message service provider.

18. The system of claim 11:

where selecting at least one performance parameter further comprises selecting at least two performance parameters, a first performance parameter being message latency and a second performance parameter being message throughput;

where performing calculations further comprises

determining values for message latency and message throughput based, at least in part, on the level or resource utilization of the overlay network;

calculating a value of an objective function based on values calculated for message latency and message throughput; and

where deciding if the provisional assignment of the message transforms among the broker machines results in an acceptable value of the performance parameter further comprises deciding if the provisional assignment results in an acceptable value of the objective function.

19. The system of claim 18 where the operations further comprise:

if an acceptable value for the objective value is not reached, continuing to make additional provisional assignments among the broker machines and to calculate a value of the objective function corresponding to each of the additional provisional message transform assignments until an acceptable value of the objective function is reached, where the value of the objective function for each of additional provisional message transform assignments is based on calculations of message latency and message throughput for that provisional message transform assignment; and

assigning the message transforms among the broker machines in accordance with the provisional message transform assignment resulting in the acceptable value of the performance parameter.

20. The system of claim 18 where the message transforms operate in a stateful manner.

21. A processor-implemented method for use in a publish-subscribe messaging system, where the publish-subscribe messaging system comprises publishing clients, subscribing clients, and a plurality of broker machines, the plurality of broker machines comprising an overlay network that accepts input message streams from publishing clients, transforms input message streams into output message streams according to pre-determined message transformation criteria, where the criteria are contained in message transforms implemented as software modules, the software modules being distributed among the broker machines, and then delivers the output message streams to the subscribing clients, the method comprising:

selecting at least one performance parameter corresponding to a performance measure of the publish-subscribe messaging system;

monitoring a level of resource utilization of the overlay network;

making a provisional assignment of message transforms among the broker machines;

performing calculations to determine a value of the at least one performance parameter of the publish-subscribe messaging system in accordance with the provisional assignment of message transforms and the level of resource utilization of the overlay network; and

deciding if the provisional assignment of the message transforms among the broker machines results in an acceptable value of the at least one performance parameter and, if it does,

assigning the message transforms among the broker machines in accordance with the provisional assignment.

22. The processor-implemented method of claim 21 further comprising:

if an acceptable value for the performance parameter is not reached, continuing to make additional provisional message transform assignments among the broker machines and to calculate a value of the performance parameter corresponding to each of the additional provisional message transform assignments until an acceptable value of the performance parameter is reached; and

assigning the message transforms among the broker machines in accordance with the provisional message transform assignment resulting in the acceptable value of the performance parameter.

23. The processor-implemented method of claim 21 where the performance parameter is message throughput.

24. The processor-implemented method of claim 21 where the performance parameter is message latency.

25. The processor-implemented method of claim 21 where the message transforms operate on one input message at a time to create an output message for delivery to the subscribing clients.

26. The processor-implemented method of claim 21 where the message transforms operate on at least two input messages at a time to create an output message for delivery to the subscribing clients.

27. The processor-implemented method of claim 21 where the predetermined message transformation criteria are established by at least one message service provider.

28. The processor-implemented method of claim 21:

where selecting at least one performance parameter further comprises selecting at least two performance parameters, a first performance parameter being message latency and a second performance parameter being message throughput;

where performing calculations further comprises

determining values for message latency and message throughput based, at least in part, on the level or resource utilization of the overlay network;

calculating a value of an objective function based on values calculated for message latency and message throughput; and

where deciding if the provisional assignment of the message transforms among the broker machines results in an acceptable value of the performance parameter further comprises deciding if the provisional assignment results in an acceptable value of the objective function.

29. The processor-implemented method of claim 28 where the operations further comprise:

if an acceptable value for the objective value is not reached, continuing to make additional provisional assignments among the broker machines and to calculate a value of the objective function corresponding to each of the additional provisional message transform assignments until an acceptable value of the objective function is reached, where the value of the objective function for each of additional provisional message transform assignments is based on calculations of message latency and message throughput for that provisional message transform assignment; and

assigning the message transforms among the broker machines in accordance with the provisional message transform assignment resulting in the acceptable value of the performance parameter.

30. The processor-implemented method of claim 28 where the message transforms operate in a stateful manner.