EFFICIENT PUBLISH/SUBSCRIBE SYSTEMS

• US 20140280317A1
• Filed: 03/14/2014
• Published: 09/18/2014
• Est. Priority Date: 03/15/2013
• Status: Active Grant

• Current Assignee: University of Florida Research Foundation, Incorporated (State University System of Florida)
• Original Assignee: University of Florida Research Foundation, Incorporated (State University System of Florida)
• Inventors: Sahni, Sartaj K., Mishra, Tania Banerjee
• Granted Patent: US 10,642,918 B2
• Time in Patent Office: Days
• US Class Current: 707/769
• CPC Class Codes: G06F 16/958 Organisation or management of web site content, e.g. publishing, maintaining pages or automatic linking

Abstract

A publish/subscribe system is described that can adjust to provide high performance for diverse application environments through an attribute structure based on predicates of a subscription, each attribute structure with one or more buckets to which attribute values of a subscription may be stored. Various data structures can be used in the attribute structure to locate the buckets containing the subscriptions. The data structures selected for each subscription are based on the attribute type and predicate operators of the subscription.

Claims

1. A publish/subscribe system comprising:

a database storing subscriptions; and

a database manager that when executed by one or more processors directs the one or more processors to;

perform an update action with respect to a subscription to the database by;

using attributes of the subscription to follow a path in a hierarchical subscription data structure stored in the database until a lowest level is reached where there are still non-empty attributes; and

performing the update action at an appropriate bucket of the database determined by the following of the path in the hierarchical subscription data structure; and

search for one or more matching subscriptions for an event by;

using the hierarchical subscription data structure to determine which buckets of the subscription structure are to be searched; and

searching the buckets of the subscription structure which are to be searched for the one or more subscriptions that match the event.

2. The system according to claim 1, wherein performing the update action at the appropriate bucket comprises inserting or deleting the subscription into/from the appropriate bucket.

3. The system according to claim 1, for an attribute of the subscription not used in the path in the hierarchical subscription data structure, the database manager, when executed by the one or more processors, directs the one or more processors to select an attribute data structure based on the subscription predicates that use this attribute.

4. The system according to claim 1, for an attribute of the subscription not used in the path in the hierarchical subscription data structure, the database manager, when executed by the one or more processors, directs the one or more processors to:

select a data structure for the attribute of the subscription not used in the path by;

determining whether subscription predicates that use this attribute specify a range of values;

a substring and/or suffix operators;

an exact match;

or string matching; and

in response to a determination that the attribute predicates specify the range of values, selecting a priority search tree or an interval tree;

in response to a determination that the attribute predicates specify the substring and/or suffix operators, selecting a suffix tree;

in response to a determination that the attribute predicates specify the exact match, selecting a red-black tree;

in response to a determination that the attribute predicates specify the string matching, selecting a suffix tree or an Aho-Corasick tree.

5. The system according to claim 4, wherein the database manager, when executed by the one or more processors, directs the one or more processors to select the data structure for the attribute of the subscription not used in the path further by:

determining whether subscription predicates that use this attribute specify an inequality;

a membership in a set;

or a non-membership in a set; and

in response to a determination that the attribute types of the subscription include the predicate specifying an inequality, the membership in a set, or the non-membership in a set, selecting a priority search tree.

6. The system according to claim 4, wherein when a domain cardinality of the predicate specifying the range of values is not known at a time of initialization, the database manager, when executed by the one or more processors, directs the one or more processors to

select a red-black priority search tree data structure for the subscription.

7. The system according to claim 4, wherein the interval tree comprises end-point lists that are stored as sorted arrays.

8. The system according to claim 1, wherein the attributes of the subscription are ordered from least occurring to most frequently occurring based on a frequency of occurrence of the attributes in the subscriptions in the database.

9. The system according to claim 1, further comprising a single hash table stored on a computer-readable storage medium that tracks a plurality of subscription attribute structures stored in the database.

10. A computer-readable storage medium having instructions stored thereon that, when executed by a processor, perform a method comprising:

in response to receiving a request to perform an update action with respect to a subscription, performing the update action with respect to the subscription to the database by;

using attributes of the subscription to follow a path in a hierarchical subscription data structure stored in the database until a lowest level is reached where there are still non-empty attributes; and

performing the update action at an appropriate bucket of the database determined by the following of the path in the hierarchical subscription data structure; and

in response to receiving a request to process an event, searching for one or more matching subscriptions for the event by;

using the hierarchical subscription data structure to determine which buckets of the subscription structure are to be searched; and

searching the buckets of the subscription structure which are to be searched for the one or more subscriptions that match the event.

11. The medium according to claim 10, wherein performing the update action at the appropriate bucket comprises inserting or deleting the subscription into/from the appropriate bucket.

12. The medium according to claim 10, wherein the method further comprises, for an attribute of the subscription not used in the path in the hierarchical subscription data structure, selecting an attribute data structure based on the subscription predicates that use this attribute.

13. The medium according to claim 10, wherein the method further comprises, for an attribute of the subscription not used in the path in the hierarchical subscription data structure, selecting the data structure for the attribute of the subscription not used in the path by:

determining whether the subscription predicates that use this attribute specify a range of values;

a substring and/or suffix operators;

an exact match;

or string matching; and

in response to a determination that the attribute predicates specify the range of values, selecting a priority search tree or an interval tree;

in response to a determination that the attribute predicates specify the substring and/or suffix operators, selecting a suffix tree;

in response to a determination that the attribute predicates specify the exact match, selecting a red-black tree;

in response to a determination that the attribute predicates specify the string matching, selecting a suffix tree or an Aho-Corasick trie.

14. The medium according to claim 13, wherein selecting the data structure for the attribute of the subscription not used in the path further comprises:

determining whether the subscription predicates that use this attribute specify an inequality;

a membership in a set;

or a non-membership in a set; and

in response to a determination that the attribute predicates specify an inequality, membership in a set, or non-membership in a set, selecting a priority search tree.

15. The medium according to claim 13, wherein when a domain cardinality of the predicate specifying the range of values is not known at a time of initialization, the selecting of the data structure for the attribute of the subscription not used in the path comprises:

selecting a red-black priority search tree data structure for the subscription.

16. The medium according to claim 13, wherein the interval tree comprises end-point lists that are stored as sorted arrays.

17. The medium according to claim 10, wherein the attributes of the subscription are ordered from least occurring to most frequently occurring based on a frequency of occurrence of the attributes in the subscriptions in the database.

18. The medium according to claim 10, further comprising a single hash table stored on a computer-readable storage medium that tracks a plurality of subscription attribute structures stored in the database.

19. A method of selecting a data structure for an attribute of a subscription in a publish/subscribe system, the attribute comprising attribute predicates, the method comprising:

selecting an attribute data structure based on subscription predicates that use the attribute.

20. The method according to claim 19, wherein selecting the attribute data structure based on the subscription predicates that use the attribute comprises:

determining whether the attribute predicates specify a range of values, an inequality, a membership in a set, a non-membership in a set, a substring and/or suffix operators, an exact match, or a string matching; and

in response to a determination that the attribute predicates specify the range of values, selecting a priority search tree or an interval tree;

in response to a determination that the attribute predicates specify the inequality, the membership in the set, the non-membership in the set, selecting a priority search tree;

in response to a determination that the attribute predicates specify the substring and/or suffix operators, selecting a suffix tree;

in response to a determination that the attribute predicates specify the exact match, selecting a red-black tree;

in response to a determination that the attribute predicates specify the string matching, selecting a suffix tree or an Aho-Corasick tree.

21. The method according to claim 20, wherein when a domain cardinality of the predicate specifying the range of values is not known at a time of initialization,

selecting a red-black priority search tree data structure for the subscription.

22. The method according to claim 20, wherein the interval tree comprises end-point lists that are stored as sorted arrays.

23. The method according to claim 20, wherein the attributes of the subscription are ordered from least occurring to most frequently occurring based on a frequency of occurrence of the attributes in the subscriptions in the database.

24. The method according to claim 20, further comprising a single hash table stored on a computer-readable storage medium that tracks a plurality of subscription attribute structures stored in the database.