Filtering algorithms and implementation for very fast publish/subscribe systems

Publish/Subscribe is the paradigm in which users express long-term interest s ("subscriptions") and some agent "publishes" events (e.g., offers). The j ob of Publish/Subscribe software is to send events to the owners of subscri ptions satisfied by those events. For example, a user subscription may cons ist of an interest in an airplane of a certain type, not to exceed a certai n price. A published event may consist of an offer of an airplane with cert ain properties including price. Each subscription consists of a conjunction of (attribute, comparison operator, value) predicates. A subscription clos ely resembles a trigger in that it is a long-lived conditional query associ ated with an action (usually, informing the subscriber). However, it is les s general than a trigger so novel data structures and implementations may e nable the creation of more scalable, high performance publish/subscribe sys tems. This paper describes an attempt at the construction of such algorithm s and its implementation. Using a combination of data structures, applicati on-specific caching policies, and application-specific query processing our system can handle 600 events per second for atypical workload containing 6 million subscriptions.