Filtering algorithms and implementation for very fast publish/subscribe systems

ABSTRACT

Publish/Subscribe is the paradigm in which users express long-term interests (“subscriptions”) and some agent “publishes” events (e.g., offers). The job of Publish/Subscribe software is to send events to the owners of subscriptions satisfied by those events. For example, a user subscription may consist of an interest in an airplane of a certain type, not to exceed a certain price. A published event may consist of an offer of an airplane with certain properties including price. Each subscription consists of a conjunction of (attribute, comparison operator, value) predicates. A subscription closely resembles a trigger in that it is a long-lived conditional query associated with an action (usually, informing the subscriber). However, it is less general than a trigger so novel data structures and implementations may enable the creation of more scalable, high performance publish/subscribe systems. This paper describes an attempt at the construction of such algorithms and its implementation. Using a combination of data structures, application-specific caching policies, and application-specific query processing our system can handle 600 events per second for a typical workload containing 6 million subscriptions.

REFERENCES

• 1: Marcos K. Aguilera , Robert E. Strom , Daniel C. Sturman , Mark Astley , Tushar D. Chandra, Matching events in a content-based subscription system, Proceedings of the eighteenth annual ACM symposium on Principles of distributed computing, p.53-61, May 04-06, 1999, Atlanta, Georgia, United States [doi>10.1145/301308.301326]
• 2: Mehmet Altinel , Michael J. Franklin, Efficient Filtering of XML Documents for Selective Dissemination of Information, Proceedings of the 26th International Conference on Very Large Data Bases, p.53-64, September 10-14, 2000
• 3: Antonio Carzaniga , David S. Rosenblum , Alexander L. Wolf, Achieving scalability and expressiveness in an Internet-scale event notification service, Proceedings of the nineteenth annual ACM symposium on Principles of distributed computing, p.219-227, July 16-19, 2000, Portland, Oregon, United States [doi>10.1145/343477.343622]
• 4: Jianjun Chen , David J. DeWitt , Feng Tian , Yuan Wang, NiagaraCQ: a scalable continuous query system for Internet databases, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.379-390, May 15-18, 2000, Dallas, Texas, United States
• 5: Phil Bernstein , Michael Brodie , Stefano Ceri , David DeWitt , Mike Franklin , Hector Garcia-Molina , Jim Gray , Jerry Held , Joe Hellerstein , H. V. Jagadish , Michael Lesk , Dave Maier , Jeff Naughton , Hamid Pirahesh , Mike Stonebraker , Jeff Ullman, The Asilomar report on database research, ACM SIGMOD Record, v.27 n.4, p.74-80, Dec. 1998 [doi>10.1145/306101.306137]
• 6: K. J. Gough and G. Smith. Efficient recognition of events in distributed systems. In Proceedings of ACSC-18, 1995.
• 7: Eric N. Hanson, Rule condition testing and action execution in Ariel, Proceedings of the 1992 ACM SIGMOD international conference on Management of data, p.49-58, June 02-05, 1992, San Diego, California, United States
• 8: Chris Carnes , J. B. Park , Albert Vernon, Scalable Trigger Processing, Proceedings of the 15th International Conference on Data Engineering, p.266, March 23-26, 1999
• 9: Eric N. Hanson , Moez Chaabouni , Chang-Ho Kim , Yu-Wang Wang, A predicate matching algorithm for database rule systems, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.271-280, May 23-26, 1990, Atlantic City, New Jersey, United States
• 10: New Era of networks Inc. http://www.neonsoft.com/products/NEONet.html.
• 11: João Pereira , Françoise Fabret , François Llirbat , Radu Preotiuc-Pietro , Kenneth A. Ross , Dennis Shasha, Publish/Subscribe on the Web at Extreme Speed, Proceedings of the 26th International Conference on Very Large Data Bases, p.627-630, September 10-14, 2000
• 12: João Pereira , Françoise Fabret , François Llirbat , Dennis Shasha, Efficient Matching for Web-Based Publish/Subscribe Systems, Proceedings of the 7th International Conference on Cooperative Information Systems, p.162-173, September 06-08, 2000
• 13: Jun Rao , Kenneth A. Ross, Cache Conscious Indexing for Decision-Support in Main Memory, Proceedings of the 25th International Conference on Very Large Data Bases, p.78-89, September 07-10, 1999
• 14: Bill Segal and David Arnold. Elvin has left the building: A publish/ subscribe notification service with quenching. In Proceedings of AUUG97, 1997.
• 15: Steven P. Vanderwiel , David J. Lilja, Data prefetch mechanisms, ACM Computing Surveys (CSUR), v.32 n.2, p.174-199, June 2000 [doi>10.1145/358923.358939]
• 16: Tak W. Yan , Hector Garcia-Molina, The SIFT information dissemination system, ACM Transactions on Database Systems (TODS), v.24 n.4, p.529-565, Dec. 1999 [doi>10.1145/331983.331992]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Information filtering; Clustering
      H.3.5 On-line Information Services
          Subjects: Web-based services
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)

  I. Computing Methodologies
  I.5 PATTERN RECOGNITION

General Terms:
Algorithms, Design, Experimentation, Management, Measurement, Performance, Theory