Medusa: Distributed Stream-Processing System

There is a large class of emerging applications in which data, generated in a distributed environment, is pushed asynchronously to servers for processing. Some example applications for which this ``push'' model for data processing is appropriate include financial services (e.g., price feeds), asset-tracking services (e.g., reporting the status of objects and equipment in real-time), fabrication line management (e.g., real-time monitoring and control of manufacturing systems), network management (e.g., intrusion detection), medical applications (e.g., monitoring devices and sensors attached to patients), environmental sensor/actuator systems (e.g., climate, traffic, building, bridge monitoring), and military applications (e.g., missile or target detection).

Several research projects currently focus on building novel stream-processing engines that are better suited to support this new class of applications than classic data-management systems. Some of these projects are Aurora, STREAM, TelegraphCQ. and Cougar, Early efforts in stream-oriented processing have focused on designing new operators and new languages, as well as building high-performance engines operating at a single site. More recently, the attention has shifted toward extending these engines to distributed environments. The latter is the focus of Medusa.

Medusa is a distributed stream-processing system built using Aurora as the single-site processing engine. Medusa takes Aurora queries and distributes them across multiple nodes. These nodes can all be under the control of one entity or can be organized as a loosely coupled federation under the control of different autonomous participants.

A distributed stream-processing system such as Medusa offers several benefits:

(*) It allows stream processing to be incrementally scaled over multiple nodes.
(*)It enables high-availability because the processing nodes can monitor and take over for each other when failures occur.
(*)It allows the composition of stream feeds from different participants to produce end-to-end services, and to take advantage from the distribution inherent in many stream processing applications (e.g., climate monitoring, financial analysis, etc.).
(*)It allows participants to cope with load spikes without individually having to maintain and administer the computing, network, and storage resources required for peak operation. When organized as a loosely coupled federated system, load movements between participants based on pre-defined contracts can significantly improve performance.

In Medusa we thus focus on distributed stream processing. We investigate in particular load management and high availability issues. We also take into consideration participant autonomy focusing on schemes that apply to loosely coupled federated environments. To promote positive interactions in such environments, Medusa relies on economic principles to regulate participant collaborations and solve the hard problems concerning load management and sharing.

Medusa employs an agoric system model to create incentives for autonomous participants to handle each others load. Clients outside the system pay Medusa participants for processing their queries and Medusa participants pay each other to handle load. Payments and load movements are based on pairwise contracts negotiated offline between participants. These contracts set tightly bounded prices for migrating each unit of load and specify the set of tasks that each participant is willing to execute on behalf of its partner. The mechanism, called the bounded-price mechanism, gives participants tight control over their choice of partners, the acceptable range of unit-prices for load, and the set of tasks that can be shed or accepted. It also achieves a low runtime overhead by bounding prices throu gh offline negotiations.
High Availability

In collaboration with members of the Aurora team, we are exploring the runtime overhead and recovery time tradeoffs between different approaches to achieve high-availability (HA) in distributed stream processing. These approaches range from classical Tandem-style process-pairs to using upstream nodes in the processing flow as backup for their downstream neighbors. Different approaches also provide different recovery semantics where either some tuples are lost, some tuples are re-processed, or operations take-over precisely where the failure happened. We discuss these algorithms in more detail in the technical report below. An important HA goal for the future is handling network partitions in addition to individual node failures.