PastryStrings: A Comprehensive Content-Based Publish/Subscribe DHT Network

Aekaterinidis and Triantafillou

dht distributed hashtable publish/subscribe pub/sub

@inproceedings{aekaterinidis:icdcs-2006,
  title={{PastryStrings}: A Comprehensive Content-Based
         Publish/Subscribe {DHT} Network},
  author={Aekaterinidis, I. and Triantafillou, P.},
  booktitle={{IEEE} International Conference on
             Distributed Computing Systems ({ICDCS})},
  year={2006}
}

Attach:Aekaterinidis-ICDCS2006.pdf

Prefix based routing over DHT

• Including numerical range and comparison predicates
• Including string prefix, suffix, containment, equality predicates
  • Note that containment does not seem to mean what it sounds like it means
    • It refers to a query like a*c, not *b*

Subscribing users are interested in particular events, a subset of all events

Order preserving hashes to support range comparisons

Distributed trie structure for Prefix Hash Trees

Constructs string trees as an overlay over the DHT network

• DHT Nodes control several string nodes

Walks a path along that tree, hashing each character of the string and storing a referent to the subscription at the nodes as it goes

Zipf distribution over message popularity

The PastryStrings publish/subscribe system~\cite{aekaterinidis:icdcs-2006} supports an expressive set of subscription operators over DHT based subscription management. Query operators available include numerical comparisons as well as string prefix, suffix, and equality\footnote{PastryString's 'containment' operator is a simple conjunction of prefix and suffix operators, not the more typical and difficult-to-support 'contains' operator.}. It does this by constructing several tree structures on top of its underlying Pastry DHT support. String operations proceed in a similar fashion to each other: Each successive character in the string is iteratively hashed and mapped to a node in the DHT, producing a string tree structure overlain the DHT. At the final node, a referent to the subscription is stored. Matching publications to subscriptions proceeds similarly, traversing the string tree and triggering any associated subscriptions stored at the nodes along the path. Numeric comparisons are managed via a virtual tree decomposing the domain into its exponential sub-ranges. To register a subscription range, it is first mapped to its decomposition by the fixed ranges in the virtual tree. Those ranges are then hashed and mapped to nodes within the DHT, at which a referent to the subscription is stored. A numeric publication is first mapped to its associated leaf node in the virtual tree. Each node from there to the virtual root is then tested for matching subscriptions, any such of which are then triggered.