IP Library › Granted Patent US 8,185,649

Granted Patent B2

US 8,185,649 · App. 12/166,250 · Granted May 22, 2012

Subscription propagation in a high performance highly available content-based publish/subscribe system

Assignee: International Business Machines Corporation

View Patent ↗

Loading inventors, assignments & file history…

Monitor This Case

Get email alerts when status or documents change.

Order Certified Copies

Most orders are placed with the USPTO same day — all within 24 business hours.

Order via The Patent Place →

Pre-filled with this patent's details

Quick Facts

Patent No.: US 8,185,649
App. No.: 12/166,250
Granted: May 22, 2012
Kind: B2

External Links

USPTO Patent Center↗ Full Patent PDF↗

Abstract

The present invention is directed to a publish/subscribe system containing a plurality of brokers, a plurality of subscribers and plurality of brokers including publisher connecting brokers, intermediate brokers and subscriber connecting brokers. Subscriptions are introduced into the system by the subscribers through associated subscription brokers. New subscriptions are aggregated, assigned a virtual start time and propagated through the system toward the publishers. Each broker maintains subscription information in the form of a directed acyclic graph and a broker vector. Messages are published through the system by the publishers through their associated publisher connecting brokers. Each message is assigned a message vector associating subscriptions to that message. The published messages are routed through the brokers toward the subscribers in accordance with comparisons of message brokers and vector brokers conducted at each broker.

Claims (67)

1. A method for propagating subscriptions to published messages across a network, the method comprising:

associating a message vector with a published message, the message vector comprising a plurality of elements, each element comprising a set of message subscriptions to the published message and an associated message vector virtual start time for that set of message subscriptions, each given set of message subscriptions comprising all active subscriptions associated with a given subscriber broker in the network that have associated virtual start times earlier than or equal to the message vector virtual start time associated with that set of message subscriptions;

associating a broker vector with a broker in the network, the broker vector comprising a plurality of elements, each element comprising a set of broker subscriptions to the published message and an associated broker vector virtual start time for that set of broker subscriptions, each given set of broker subscriptions comprising all active subscriptions associated with a given subscriber broker in the network that have associated virtual start times earlier than or equal to the broker vector virtual start time associated that set of broker subscriptions;

comparing the message subscriptions in the message vector to the broker subscriptions in the broker vector; and

routing the published message through the network in accordance with the comparison.

2. The method of claim 1 , wherein the step of routing the published message comprises routing the published message in accordance with one or more of the broker subscriptions when each message subscription matches one of the broker subscriptions in the set of broker subscriptions.

3. The method of claim 1 , wherein the step of routing the published message comprises routing the published to all downstream brokers and subscribers when the comparison of the message subscriptions indicates that at least one message subscription contained in the set of message subscriptions is not contained in the set of broker subscriptions.

4. The method of claim 1 , wherein the step of comparing message and broker subscriptions comprises confirming that the broker vector virtual start time associated each one of the broker vectors is later than or equal to the message vector virtual start time associated with the message subscription matching that broker subscription.

5. The method of claim 1 , further comprising confirming that the broker vector virtual start times are earlier than a current value of a clock contained in the broker associated with the set of broker subscriptions.

6. The method of claim 1 , further comprising:

defining each message subscription and each broker subscription as a plurality of logical conjunctions, each logical conjunction defining a set of published messages; and

aggregating the logical conjunctions.

7. The method of claim 6 , wherein the step of aggregating the logical conjunctions comprises aggregating the logical conjunctions associated with the set of broker subscriptions at the broker associated with the set of broker subscriptions.

8. The method of claim 6 , wherein the step of aggregating the logical conjunctions comprises aggregating the logical conjunctions at all brokers in the network.

9. The method of claim 6 , wherein the step of aggregating the logical conjunctions comprises maintaining a directed acyclic graph representing the logical conjunctions associated with the set of broker subscriptions at the broker associated with the set of broker subscriptions.

10. The method of claim 9 , wherein the step of maintaining the directed acyclic graph comprises:

identifying uncovered conjunctions in the logical conjunctions, wherein the set of published messages associated with each uncovered conjunction is not a subset of any other set of published messages defined by the logical conjunctions; and

identifying covered conjunctions in the logical conjunction, wherein the set of published messages associated with each covered conjunction is a subset of one of the published messages defined by one of the uncovered conjunctions.

11. The method of claim 10 , further comprising:

assigning an uncovered conjunction virtual start time to each uncovered conjunction, the uncovered conjunction virtual start time equivalent to a current value of a clock associated with the broker when the uncovered conjunction is added to the directed acyclic graph; and

assigning a covered conjunction virtual start time to each covered conjunction, the covered conjunction virtual start time equal to the uncovered conjunction virtual start time associated with its covering conjunction.

12. The method of claim 11 , further comprising setting the broker vector virtual start time equivalent to a maximum value of the covered and uncovered conjunction virtual start times for the logical conjunctions contained in the broker vector.

13. The method of claim 11 , further comprising:

propagating the directed acyclic graph through one or more other brokers in the network; and

advancing the clock associated with the broker after propagating the directed acyclic graph.

14. The method of claim 13 , further comprising:

assuring monotonicity of the clock; and

maintaining the clock as an integer counter.

15. The method of claim 9 , further comprising propagating the directed acyclic graph through one or more other brokers in the network.

16. The method of claim 15 , wherein the step of propagating the directed acyclic graph comprises propagating in accordance with a pre-determined time interval.

17. The method of claim 15 , wherein the step of propagating the directed acyclic graph comprises propagating in response to a change in the directed acyclic graph.

18. The method of claim 17 , wherein the step of propagating the directed acyclic graph further comprises:

identifying a highest vector broker virtual start time that can be associated with any of the broker subscriptions in order to process the propagated change in the directed acyclic graph; and

propagating the highest vector virtual start time in a constraint vector.

19. The method of claim 18 , further comprising:

confirming that each broker subscription in the broker vector associated with the broker receiving the propagated change in the directed acyclic graph satisfies the constraint vector;

updating the broker vector in accordance with the propagated change if the constraint vector is satisfied; and

updating the broker vector in accordance with the constraint vector if the constraint vector is not satisfied.

20. The method of claim 9 , wherein the step of maintaining the directed acyclic graph further comprises:

adding new subscriptions to the set of broker subscriptions; and

removing expired subscriptions to the set of broker subscriptions.

21. The method of claim 9 , further comprising omitting transitive arcs from the directed acyclic graph.

22. A non-transitory computer readable medium containing a computer executable code that when read by a computer causes the computer to perform a method for propagating subscriptions to published messages across a network, the method comprising:

comparing the message subscriptions in the message vector to the broker subscriptions in the broker vector; and

routing the published message through the network in accordance with the comparison.

23. The non-transitory computer readable medium of claim 22 , wherein the step of comparing message and broker subscriptions comprises confirming that the broker vector virtual start time associated each one of the broker vectors is later than or equal to the message vector virtual start time associated with the message subscription matching that broker subscription.

24. The non-transitory computer readable medium of claim 22 , further comprising:

defining each message subscription and each broker subscription as a plurality of logical conjunctions, each logical conjunction defining a set of published messages; and

aggregating the logical conjunctions.

25. The non-transitory computer readable medium of claim 24 , wherein the step of aggregating the logical conjunctions comprises maintaining a directed acyclic graph representing the logical conjunctions associated with the set of broker subscriptions at the broker associated with the set of broker subscriptions.

26. The non-transitory computer readable medium of claim 25 , wherein the step of maintaining the directed acyclic graph comprises:

27. The non-transitory computer readable medium of claim 26 , further comprising:

28. The non-transitory computer readable medium of claim 27 , further comprising setting the broker vector virtual start time equivalent to a maximum value of the covered and uncovered conjunction virtual start times for the logical conjunctions contained in the broker vector.

29. The non-transitory computer readable medium of claim 25 , further comprising propagating the directed acyclic graph through one or more other brokers in the network in response to a change in the directed acyclic graph.

30. The non-transitory computer readable medium of claim 29 , wherein the step of propagating the directed acyclic graph further comprises:

identifying a highest vector broker virtual start time that can be associated with any of the broker subscriptions in order to process the propagated change in the directed acyclic graph; and

propagating the highest vector virtual start time in a constraint vector.

31. The non-transitory computer readable medium of claim 30 , further comprising:

confirming that each broker subscription in the broker vector associated with the broker receiving the propagated change in the directed acyclic graph satisfies the constraint vector;

updating the broker vector in accordance with the propagated change if the constraint vector is satisfied; and

updating the broker vector in accordance with the constraint vector if the constraint vector is not satisfied.

Assignments (7)

RELEASE OF SECURITY INTEREST Recorded Dec 13, 2024

From: JPMORGAN CHASE BANK, N.A., AS COLLATERAL AGENT

To: DROPBOX, INC.

Reel/Frame 069635/0332 →

SECURITY INTEREST Recorded Dec 12, 2024

From: DROPBOX, INC.

To: WILMINGTON TRUST, NATIONAL ASSOCIATION, AS COLLATERAL AGENT

Reel/Frame 069604/0611 →

RELEASE OF SECURITY INTEREST Recorded Dec 12, 2024