PSMatcher

A pub/sub matcher algorithm implementation that efficiently matches events against subscriptions.

Overview

PSMatcher is a Rust library that provides an efficient algorithm for matching events against subscriptions in a publish/subscribe system. The algorithm pre-processes subscriptions into a matching tree for optimized event matching.

Key features:

• Efficient matching using a tree-based algorithm
• Support for complex subscription predicates
• Flexible event attribute system
• Optimized for high-throughput event processing
• Support for regex pattern matching with compiled regex objects

Concepts

Events

Events are messages that contain a set of attributes. Each event must have at least one string attribute called "topic". Events can be matched against subscriptions to determine which subscribers should receive the event.

Subscriptions

Subscriptions are expressions that define which events a subscriber is interested in. In PSMatcher, subscriptions are represented as conjunctions of elementary predicates (combined with AND logic).

Elementary Predicates

Elementary predicates are the building blocks of subscriptions. Each predicate represents the result of an elementary test on an event attribute. For example, a predicate might test if the "topic" attribute equals "weather".

Matching Tree

The matching tree is a data structure that efficiently organizes subscriptions for fast event matching. The tree is built during pre-processing and optimized for quick traversal during event matching.

Implementation

The matching algorithm is based on the tree-based approach described in:

Marcos K. Aguilera, Robert E. Strom, Daniel C. Sturman, Mark Astley, and Tushar D. Chandra. 1999. Matching events in a content-based subscription system. In Proceedings of the eighteenth annual ACM symposium on Principles of distributed computing (PODC '99). Association for Computing Machinery, New York, NY, USA, 53–61. https://doi.org/10.1145/301308.301326

Usage

Note: All code examples in this README are tested as part of the crate's documentation tests.

use psmatcher::{Matcher, Subscription, ElementaryPredicate, ElementaryTest};
use psmatcher::event_types::{DefaultEvent, AttributeValue};

// Create a matcher
let mut matcher = Matcher::new();

// Create a subscription for weather updates in San Francisco
let subscription = Subscription::new("weather-sf".to_string())
    .with_predicate(ElementaryPredicate::new(
        ElementaryTest::Equals {
            attribute: "topic".to_string(),
            value: AttributeValue::String("weather".to_string()),
        },
        false,
    ))
    .with_predicate(ElementaryPredicate::new(
        ElementaryTest::Equals {
            attribute: "city".to_string(),
            value: AttributeValue::String("San Francisco".to_string()),
        },
        false,
    ));

// Add the subscription to the matcher
matcher.add_subscription(subscription);

// Create a subscription using regex pattern matching
let regex_subscription = Subscription::new("california-cities".to_string())
    .with_predicate(ElementaryPredicate::new(
        ElementaryTest::regex("topic".to_string(), "weather|forecast").unwrap(),
        false,
    ))
    .with_predicate(ElementaryPredicate::new(
        ElementaryTest::regex("city".to_string(), "San (Francisco|Jose|Diego)").unwrap(),
        false,
    ));

// Add the regex subscription to the matcher
matcher.add_subscription(regex_subscription);

// Create an event
let event = DefaultEvent::new("weather".to_string())
    .with_attribute("city".to_string(), AttributeValue::String("San Francisco".to_string()))
    .with_attribute("temperature".to_string(), AttributeValue::Float(72.5));

// Match the event against subscriptions
let matches = matcher.match_event(&event).unwrap();

// Check if our subscriptions matched
assert!(matches.contains("weather-sf"));
assert!(matches.contains("california-cities"));

License

This project is licensed under the Apache License, Version 2.0.