Tuesday, July 31, 2012

Publish/Subscribe Systems

The many faces of publish/subscribe is one great paper if you're interested in distributed systems. This is one of those papers that I should have read several years ago when I started working on messaging brokers and even before doing my recent work creating a new publish/subscribe system.

This paper offers a lot of insight into the several options you have to "glue" systems and the characteristics of publish/subscribe, so you can make more informed decisions when picking an implementation for your problem or before you think of coming up with your own.

Please find below some of my highlights from the paper.

Introduction

The publish/subscribe interaction scheme is receiving increasing attention and is claimed to provide the loosely coupled form of interaction required in such large scale settings. Subscribers have the ability to express their interest in an event, or a pattern of events, and are subsequently notified of any event, generated by a publisher, which matches their registered interest. An event is asynchronously propagated to all subscribers that registered interest in that given event. The strength of this event-based interaction style lies in the full decoupling in time, space, and synchronization between publishers and subscribers.

The Basic Interaction Scheme

The publish/subscribe interaction paradigm provides subscribers with the ability to express their interest in an event or a pattern of events, in order to be notified subsequently of any event, generated by a publisher, that matches their registered interest. In other terms, producers publish information on a software bus (an event manager) and consumers subscribe to the information they want to receive from that bus. This information is typically denoted by the term event and the act of delivering it by the term notification.

The decoupling that the event service provides between publishers and subscribers can be decomposed along the following three dimensions […]:
  • Space decoupling: The interacting parties do not need to know each other.
  • Time decoupling: The interacting parties do not need to be actively participating in the interaction at the same time.
  • Synchronization decoupling: The production and consumption of events do not happen in the main flow of control of the publishers and subscribers, and do not therefore happen in a synchronous manner.
Decoupling the production and consumption of information increases scalability by removing all explicit dependencies between the interacting participants.

The Cousins: Alternative Communication Paradigms

  • Message Passing: Message passing represents a low-level form of distributed communication, in which participants communicate by simply sending and receiving messages. […] The producer and the consumer are coupled both in time and space (cf. Figure 3): they must both be active at the same time and the recipient of a message is known to the sender.
  • RPC: One of the most widely used forms of distributed interaction is the remote invocation, an extension of the notion of “operation invocation” to a distributed context. […] RPC differs from publish/subscribe in terms of coupling: the synchronous nature of RPC introduces a strong time, synchronization (on the consumer side1), and also space coupling (since an invoking object holds a remote reference to each of its invokees).
  • Notifications: In order to achieve synchronization decoupling, a synchronous remote invocation is sometimes split into two asynchronous invocations: the first one sent by the client to the server—accompanied by the invocation arguments and a callback reference to the client—and the second one sent by the server to the client to return the reply. This type of interaction—where subscribers register their interest directly with publishers, which manage subscriptions and send events—corresponds to the so-called observer design pattern. […] It is generally implemented using asynchronous invocations in order to enforce synchronization decoupling. Although publishers notify subscribers asynchronously, they both remain coupled in time and in space.
  • Shared Spaces: The distributed shared memory (DSM) paradigm [Li and Hudak 1989; Tam et al. 1990] provides hosts in a distributed system with the view of a common shared space across disjoint address spaces, in which synchronization and communication between participants take place through operations on shared data. […] A tuple space is composed of a collection of ordered tuples, equally accessible to all hosts of a distributed system. Communication between hosts takes place through the insertion/removal of tuples into/from the tuple space. […] The interaction model provides time and space decoupling, in that tuple producers and consumers remain anonymous with respect to each other. The creator of a tuple needs no knowledge about the future use of that tuple or its destination. Unlike the publish/subscribe paradigm, the DSM model does not provide synchronization decoupling because consumers pull new tuples from the space in a synchronous style (Figure 8). This limits the scalability of the model due to the required synchronization between the participants.
    • A similar communication abstraction, called rendezvous, has been introduced in the Internet Indirection Infrastructure (I3) [Stoica et al. 2002]. Instead of explicitly sending a packet to a destination, each packet is associated with an identifier; this identifier is then used by the receiver to obtain delivery of the packet. This level of indirection decouples the act of sending from the act of receiving.
  • Message Queuing: Message queuing and publish/subscribe are tightly intertwined: message queuing systems usually integrate some form of publish/subscribe-like interaction. […] At the interaction level, message queues recall much of tuple spaces: queues can be seen as global spaces, which are fed with messages from producers. From a functional point of view, message queuing systems additionally provide transactional, timing, and ordering guarantees not necessarily considered by tuple spaces. […] In message queuing systems, messages are concurrently pulled by consumers with one-of-n semantics similar to those offered by tuple spaces through the in() operation (Figure 9). These interaction model is often also referred to as point-to-point (PTP) queuing. Which element is retrieved by a consumer is not defined by the element’s structure, but by the order in which the elements are stored in the queue (generally first-in first-out (FIFO) or priority-based order). […] Similarly to tuple spaces, producers and consumers are decoupled in both time and space. As consumers synchronously pull messages, message queues do not provide synchronization decoupling. Some message queuing systems offer limited support for asynchronous message delivery, but these asynchronous mechanisms do not scale well to large populations of consumers because of the additional interactions needed to maintain transactional, timing, and ordering guarantees.


The Siblings: Publish/Subscribe Variations

Subscribers are usually interested in particular events or event patterns, and not in all events.
  • Topic-based Publish/Subscribe: The earliest publish/subscribe scheme was based on the notion of topics or subjects […] It extends the notion of channels, used to bundle communicating peers, with methods to characterize and classify event content. […] subscribing to a topic T can be viewed as becoming a member of a group T, and publishing an event on topic T translates accordingly into broadcasting that event among the members of T. […] Every topic is viewed as an event service of its own, identified by a unique name, with an interface offering publish() and subscribe() operations.
  • Content-Based Publish/Subscribe: […] the topic-based publish/subscribe variant represents a static scheme which offers only limited expressiveness. The content-based (or property-based [Rosenblum and Wolf 1997]) publish/subscribe variant improves on topics by introducing a subscription scheme based on the actual content of the considered events. In other terms, events are not classified according to some predefined external criterion (e.g., topic name), but according to the properties of the events themselves.
  • Type-Based Publish/Subscribe: Topics usually regroup events that present commonalities not only in content, but also in structure. This observation has led to the idea of replacing the name-based topic classification model by a scheme that filters events according to their type […].


The Incarnations: Implementation Issues

  • Events
    • Messages
    • Invocations
  • The Media
    • Architectures
      • Centralized Architecture: the role of publish/subscribe systems is to permit the exchange of events between producers and consumers in an asynchronous manner. Asynchrony can be implemented by having producers send messages to a specific entity that stores them, and forwards them to consumers on demand. We call this approach a centralized architecture because of the central entity that stores and forwards messages. […] Applications based on such systems have strong requirements in terms of reliability, data consistency, or transactional support, but do not need a high data throughput. Examples of such applications are electronic commerce or banking applications.
      • Distributed Architecture: Asynchrony can also be implemented by using smart communication primitives that implement store and forward mechanisms both in the producer’s and consumer’s processes, so that communication appears asynchronous and anonymous to the application without the need for an intermediary entity. We call this approach a distributed architecture because there is no central entity in the system. TIBCO Rendezvous [TIBCO 1999] uses a decentralized approach in which no process acts as a bottleneck or a single point of failure. Such architectures are well suited for fast and efficient delivery of transient data, which is required for applications like stock exchange or multimedia broadcasting.
      • Dissemination
        • The actual transmission of data can happen in various ways. In particular, data can be sent using point-to-point communication primitives, or using hardware multicast facilities like IP multicast […]. Centralized approaches like certain message queuing systems are likely to use point-to-point communication primitives between producers/consumers and the centralized broker. […] To ensure high throughput, Internet protocol (IP) multicast or a wide range of reliable multicast protocols


Qualities of Service

  • Persistence: The communicating parties do not control how messages are transmitted and when they are processed. Thus, the messaging system must provide guarantees not only in terms of reliability, but also in terms of durability of the information. It is not sufficient to know that a message has reached the messaging system that sits between the producers and consumers; we must get the guarantee that the message will not be lost upon failure of that messaging system. Persistence is generally present in publish/subscribe systems that have a centralized architecture and store messages until consumers are able to process them. Distributed publish/ subscribe systems do not generally offer persistence since messages are directly sent by the producer to all subscribers. Unless the producer keeps a copy of each message, a faulty subscriber may not be able to get missed messages when recovering. TIBCO Rendezvous [TIBCO 1999] offers a mixed approach, in which a process may listen to specific subjects, store messages on persistent storage, and resend missed messages to recovering subscribers.
  • Priorities: message prioritization is a quality of service offered by some messaging systems. Indeed, it may be desirable to sort the messages waiting to be processed by a consumer in order of priority. […] Priorities should be considered as a best-effort quality of service (unlike persistence).
  • Transactions: Transactions are generally used to group multiple operations in atomic blocks that are either completely executed or not executed at all. In messaging systems, transactions are used to group messages into atomic units: either a complete sequence of messages is sent (received), or none of them is.
  • Reliability: Reliability is an important feature of distributed information systems. It is often necessary to have strong guarantees about the reliable delivery of information to one or several distributed entities. Because of the loose synchronization between producers and consumers of information, implementing reliable event propagation (“guaranteed delivery”) is challenging. […] Centralized publish/subscribe systems generally use reliable point-to-point channels to communicate with publishers and subscribers, and keep copies of events on stable storage. Systems based on an overlay network of distributed event brokers often use reliable protocols to propagate events to all or a subset of the brokers. Protocols based on group communication […] are good candidates as they are resilient to the failure of some of the brokers. […] systems that let publishers and subscriber communicate directly with each other, such as TIBCO Rendezvous [TIBCO 1999], also use lightweight reliable multicast protocols. As events are generally not kept in the system for failed or disconnected (time-decoupled) subscribers, guaranteed delivery must be implemented by deploying dedicated processes that store events and replay them to requesting subscribers.
Post a Comment