SUBSCRIPTION GROUPS IN PUBLISH-SUBSCRIBE SYSTEM

• US 20140067940A1
• Filed: 08/31/2012
• Published: 03/06/2014
• Est. Priority Date: 08/31/2012
• Status: Active Grant

• Current Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Original Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Inventors: Demailly, Laurent, Kumar, Sanjeev, Li, Harry, Ajoux, Philippe, Atsmon Guz, Liat, Song, Yee Jiun, Roy, Sabyasachi
• Granted Patent: US 8,990,375 B2
• Time in Patent Office: Days
• US Class Current: 709/204
• CPC Class Codes: G06F 16/00 Information retrieval; Database structures therefor; File system structures therefor
• CPC Class Codes: H04L 51/00 User-to-user messaging in packet-switching networks, transmitted according to store-and-forward or real-time protocols, e.g. e-mail
• CPC Class Codes: H04L 51/226 Delivery according to priorities
• CPC Class Codes: H04L 51/52 for supporting social networking services
• CPC Class Codes: H04L 67/00 Network arrangements or protocols for supporting network services or applications user-to-user messaging H04L51/00; network arrangements, protocols or services for supporting real-time applications in data packet communications networks H04L65/00
• CPC Class Codes: H04L 67/306 User profiles
• CPC Class Codes: H04L 67/535 Tracking the activity of the user network monitoring arrangements H04L43/00; recording of computer activity G06F11/34
• CPC Class Codes: H04L 67/55 Push-based network services
• CPC Class Codes: H04L 69/16 Implementation or adaptation of Internet protocol [IP], of transmission control protocol [TCP] or of user datagram protocol [UDP]
• CPC Class Codes: H04W 4/08 User group management

Abstract

Disclosed is a method and system for publishing subscriptions in a publish-subscribe system in accordance with subscription groups. Embodiments may include (i) determining a consumption characteristic by which each of a plurality of subscribers in a publish-subscribe system consumes a subscription published by a publisher; (ii) identifying the subscribers whose consumption characteristics satisfy a specified similarity criterion; (iii) defining a plurality of subscription groups, each of which includes subscriptions of those of the subscribers whose consumption characteristics satisfy the specified similarity criterion; and (iv) transmitting the subscriptions to the subscribers in accordance with the subscription groups. Embodiments may also include moving a subscription of the subscriber, from a first subscription group having subscriptions of those of the subscribers whose consumption characteristics correspond to a first specified similarity criterion, to a second subscription group having subscriptions of those of the subscribers whose consumption characteristics correspond to a second specified similarity criterion.

Claims

1. A method comprising:

determining, by a publish-subscribe system that runs on a computer system in a network, a consumption characteristic by which each of a plurality of subscribers consumes a subscription published by a publisher;

identifying, by the publish-subscribe system, the subscribers whose consumption characteristics satisfy a specified similarity criterion;

defining, by the publish-subscribe system, a plurality of subscription groups, each of which includes subscriptions of those of the subscribers whose consumption characteristics satisfy the specified similarity criterion; and

transmitting, by the publish-subscribe system, the subscriptions to the subscribers in accordance with the subscription groups.

2. The method of claim 1, wherein the consumption characteristic includes a consumption rate of a subscriber and wherein the specified similarity criterion includes consumption rates that fall within predetermined ranges.

3. The method of claim 2, wherein one of the subscription groups is a lead subscription group which includes subscriptions of those subscribers whose consumption rates fall within a highest predetermined range among the predetermined ranges.

4. The method of claim 3, wherein the lead subscription group includes latest subscriptions published from the publisher and all others of the subscription groups include subscriptions older than the subscriptions in the lead subscription group.

5. The method of claim 3, wherein transmitting the subscriptions includes transmitting the subscription groups as a stream, the stream having the subscription groups arranged in a decreasing order of the predetermined ranges of the consumption rates of the subscribers to which the subscriptions in each of the subscription groups correspond.

6. The method of claim 5, wherein the lead subscription group is located at a first position in the stream and all others of the subscription groups trail the lead subscription group in the stream.

7. The method of claim 2 further comprising:

determining if a consumption rate of a subscriber whose consumption rate is in a first predetermined range of the predetermined ranges has changed; and

responsive to a determination that the consumption rate of the subscriber has changed,

identifying a second predetermined range of the predetermined ranges with which the changed consumption rate of the subscriber corresponds, and

moving a subscription of the subscriber, from a first subscription group having subscriptions of those of the subscribers whose consumption rates correspond to the first predetermined range, to a second subscription group having subscriptions of those of the subscribers whose consumption rates correspond to the second predetermined range, in a stream of subscription groups.

8. The method of claim 7, wherein moving the subscription of the subscriber from the first subscription group to the second subscription group includes

determining if the consumption rate of the subscriber has decreased or increased;

responsive to a determination that the consumption rate of the subscriber has decreased, moving the subscription from the first subscription group to the second subscription group, where the second subscription group trails the first subscription group in the stream; and

responsive to a determination that the consumption rate of the subscriber has increased, moving the subscription from the first subscription group to the second subscription group, where the second subscription group is ahead of the first subscription group in the stream.

9. The method of claim 1, wherein transmitting the subscriptions in accordance with subscription groups further includes:

merging a first subscription group of the subscription groups with a second subscription group of the subscription groups to create a merged subscription group.

10. The method of claim 1, wherein transmitting the subscriptions in accordance with subscription groups further includes:

splitting a first subscription group of the subscription groups into a plurality of new subscription groups.

11. The method of claim 1 further comprising:

storing the subscriptions in a plurality of logical partitions of a storage system in the computer system, each of the logical partitions containing a separate non-overlapping subset of the subscriptions, wherein transmitting the subscriptions to the subscribers includes fetching the subscriptions from the storage system by making a number of connections to the storage system, the number of connections based, at least in part, on a number of the subscription groups created.

12. The method of claim 1, wherein transmitting the subscriptions includes adding, by the publisher, a token to each of the subscriptions published, the token indicating at least one of (i) a position of the subscription in the stream, or (ii) a time when the subscription was published by the publisher.

13. The method of claim 12, wherein each of the subscribers transmits an acknowledgement to the publisher indicating that each of the subscriptions to which the token was added has been consumed successfully, the each of the subscribers transmitting an acknowledgement to the publisher after at least one of (i) consuming a plurality of subscriptions, or (ii) consuming subscriptions for a predetermined period of time, corresponding to tokens of the subscriptions that have been consumed successfully.

14. The method of claim 13, wherein transmitting the subscriptions to the subscribers and receiving the acknowledgements for the transmitted subscriptions are performed asynchronously.

15. The method of claim 1, wherein transmitting the subscriptions from the publisher to the subscribers includes

determining an intermediary node through which the publisher can transmit subscriptions to a destination subscriber of the subscribers, wherein the intermediary node acts as at least one of a producer, a publisher or a subscriber, and wherein the intermediary node consumes the subscription transmitted by a previous node, produces the consumed subscription as a new subscription and publishes the new subscription to a next node,

generating a route including the publisher, the destination subscriber and the determined intermediary node, and

transmitting the subscriptions to the destination subscriber using the generated route.

16. The method of claim 15, wherein determining the intermediary node includes selecting the intermediary node based on at least one of (i) a type of data transmitted, (ii) a geographical location of the source publisher, the destination subscriber, or the intermediary node, (iii) a load on the intermediary node, (iv) a cost of transmitting the subscription to the intermediary node, (v) a cost of transmitting the subscription to the destination subscriber, (vi) a random function, or (vii) a probability function.

17. The method of claim 15, wherein the destination subscriber receives the subscriptions in an order transmitted by the source publisher.

18. The method of claim 11 further comprising:

determining, by the publisher, whether each of the logical partitions of the storage system is subscribed to by at least one of the subscribers; and

responsive to a determination that a logical partition is not subscribed to by the at least one of the subscribers,

identifying a subscriber from the subscribers as a potential consumer of a set of subscriptions contained in the logical partition, and

sending an invitation to the subscriber to subscribe to the set of subscriptions contained in the logical partition.

19. The method of claim 18, wherein identifying a subscriber from the subscribers as a potential consumer of a set of subscriptions includes determining the subscriber from the subscribers based, at least in part, on a random function.

20. The method of claim 11, wherein transmitting the subscriptions from the publisher to the subscribers includes transmitting the subscriptions using a transfer control protocol (TCP)/Internet protocol (IP) connection between the publisher and the subscribers, the transmitting using the TCP/IP connection including

identifying a plurality of sets of subscriptions published by the publisher to a first subscriber of the subscribers, each of the sets of subscriptions contained in a different logical partition of the storage system,

creating a single TCP/IP connection between the publisher and the first subscriber, the single TCP/IP connection capable of transmitting set of subscriptions from a single logical partition, and

transmitting the sets of subscriptions contained in the different logical partitions, from the publisher to the first subscriber by multiplexing the sets of subscriptions over the single TCP/IP connection.

21. The method of claim 11, wherein storing the subscriptions in the storage system includes

configuring the publish-subscribe system to extract events from a portable log file of the producer,

extracting the events from the portable log file of the producer, the extracting the events including identifying the events that the publisher is interested in publishing according to the subscriptions, and

storing the events as the subscriptions in the storage system.

22. The method of claim 11 further comprising:

determining, by the publisher, if a set of subscriptions has moved from a first logical partition of the logical partitions to a second logical partition of the logical partitions; and

responsive to a determination that the set of subscriptions has moved from the first logical partition to the second logical partition,

notifying, by the publisher, the subscribers subscribed to the set of subscriptions in the first logical partition that the set of subscriptions has moved to the second logical partition, and

sending an invitation to the subscribers to subscribe to the set of subscriptions in the second logical partition.

23. The method of claim 11 further comprising:

determining, by the publisher, if a first logical partition of the logical partitions of the storage system has failed; and

responsive to a determination that the first logical partition has failed,

notifying, by the publisher, the subscribers subscribed to the set of subscriptions in the first logical partition that the first logical partition has failed,

determining, by the publisher, a second logical partition of the logical partitions to which the set of subscriptions has moved to from the first logical partition, and

sending an invitation to the subscribers to subscribe to the set of subscriptions in the second logical partition.

24. The method of claim 23, wherein determining if the first logical partition of the logical partitions of the storage system has failed includes determining if no subscriptions have been published from the first logical partition for a predetermined period.

25. The method of claim 23, wherein determining if the first logical partition of the logical partitions of the storage system has failed includes

determining if no subscriptions have been published from the first logical partition for a predetermined period,

responsive to a determination that no subscriptions have been published from the first logical partition for the predetermined period,

executing a process to terminate publishing subscriptions from the first logical partition, and

determining that the first logical partition has failed if a number of times that the process is executed exceeds a predefined threshold.

26. The method of claim 1, wherein the consumption characteristic includes a subscription to a highly engaged story.

27. The method of claim 26, wherein the highly engaged story includes a set of user-understandable information each having at least a specified minimum number of at least one of (i) comments on user-understandable information;

(ii) likes on the user-understandable information which is indicating of user approval of the user-understandable information, or (iii) sharing of the user-understandable information with other users.

28. A method comprising:

transmitting, by a publisher in publish-subscribe system that runs on a computer system in a network, subscriptions to subscribers in accordance with a plurality of subscription groups, each of the subscription groups including subscriptions of subscribers whose consumption characteristics satisfy a specified similarity criterion;

determining if a consumption characteristic of one of the subscribers has changed;

responsive to a determination that the consumption characteristic of one of the subscribers satisfies a predetermined change criteria,

identifying a subscription group among the subscription groups which includes subscriptions of the subscribers whose consumption characteristics are similar to the consumption characteristic of the one of the subscribers, and

moving a subscription of the one of the subscribers to the identified subscription group to create an updated subscription group; and

transmitting, by the publisher, the subscriptions to the subscribers in accordance with the subscription groups, the subscription groups including the updated subscription group.

29. The method of claim 28, wherein the consumption characteristic includes a consumption rate of a subscriber, the consumption rate including a rate at which the subscriptions are consumed by the subscriber, and wherein the specified similarity criterion includes consumption rates of subscribers falling within a particular predetermined range of a plurality of predetermined ranges.

30. The method of claim 29, wherein transmitting the subscriptions includes transmitting the subscription groups as a stream, the stream having the subscription groups arranged in a decreasing order of the predetermined ranges of the consumption rates of the subscribers to which the subscriptions in each of the subscription groups correspond.

31. The method of claim 29, wherein moving the subscription of one of the subscribers to the identified subscription group includes

determining if the consumption rate of the one of the subscribers has increased or decreased;

responsive to a determination that the consumption rate of one of the subscribers has decreased, moving the subscription to the identified subscription group trailing a subscription group the subscription belonged to, in the stream; and

responsive to a determination that the consumption rate of the one of the subscribers has increased, moving the subscription to the identified subscription group ahead of a subscription group the subscription belonged to, in the stream.

32. An apparatus comprising:

a) a processor;

b) an input device coupled with the processor and configured to receive processor executable instructions; and

c) a storage device storing the processor executable instructions which, when executed by the processor, cause the processor to execute a process including;

determining, by a publish-subscribe system, a consumption characteristic which each of a plurality of subscribers consumes a subscription published by a publisher;

identifying, by the publish-subscribe system, the subscribers whose consumption characteristics satisfy a specified similarity criterion;

defining, by the publish-subscribe system, a plurality of subscription groups, each of which includes subscriptions of those of the subscribers whose consumption characteristics satisfy a specified similarity criterion; and

transmitting, by the publish-subscribe system, the subscriptions to the subscribers in accordance with the subscription groups.

33. The apparatus of claim 32, wherein the consumption characteristic includes a consumption rate of a subscriber and wherein the specified similarity criterion includes consumption rates that fall within predetermined ranges.