Scribe: The Design of a Large-Scale Event Notification Infrastructure

Rowstron et al

multicast overlay distributed hash table topic publish/subscribe pub/sub

@inproceedings{rowstron:ngc-2001,
  author={Rowstron, Antony and Kermarrec, Anne-Marie and
          Castro, Miguel and Druschel, Peter},
  title={{Scribe}: The Design of a Large-Scale Event
         Notification Infrastructure},
  booktitle={International Workshop on Networked Group Communication},
  publisher={Springer-Verlag},
  pages={30-43},
  year={2001}
}

Built on top of Pastry

General model:

• Nodes can create a topic
• Other nodes can subscribe to that topic
• Appropriately credentialed nodes can publish to that topic

Topics are hashed a controlling node, and subscriptions and publications rendezvous there

• As subscriptions are rooted to the root, they are stashed at each node along the way
• Unsubscriptions managed by propagated up unsubscribe messages as forwarding tables empty out

Different applications may have different reliability requirements

• Scribe manages this by providing simple best effort, and assuming applications will build reliability on top

Heartbeats periodically to children; if children don't receive in some interval, they route to a new parent

Root lists are replicated to the k nodes with IDs numerically closest to the root

• One of them takes over if the root fails, just based on the DHT semantics

Of note:

• Overcast
• Narada
• Bayeux

Scribe~\cite{rowstron:ngc-2001} provides a typical topic-based publish/subscribe service over a Pastry DHT. Topics are identified by flat, exact string labels, and associated with a dissemination tree rooted at the hashed topic's controlling node as mapped by the DHT. Subscriptions to a topic are routed toward the root using the DHT. At each step, the previous node is added to the current node's children list for that topic. If the current node is not already a forwarder for the topic, it notifies the next hop node in the DHT overlay that it has joined the topic, and so on recursively to the root. Unsubscribe requests are handled in a similar fashion, tearing down the forwarding tree in a bottom-up fashion. In disseminating a message, publications are first routed directly to the associated topic root by the DHT. They are then recursively forwarded to children in the dissemination tree.

Scribe nodes maintain the dissemination trees by periodically transmitting heartbeats to their dissemination tree children if there has been no recent publication traffic. Any node in a tree that hasn't received a heartbeat or message from a parent in some interval reroutes that topic toward the root and establishes a new parent. Root nodes are also replicated among a small number of their numerically closest nodes, one of which naturally takes its place if it fails. Using this maintenance, Scribe provides a best effort delivery service upon which extensions can be made to provide other guarantees, e.g., buffering messages at each node and retransmitting when local tree updates occur.