Source-linked AI summary
Muppet: MapReduce-Style Processing of Fast Data
Wang Lam, Lu Liu, STS Prasad, Anand Rajaraman, Zoheb Vacheri, AnHai Doan
TL;DR
Fast data streams have grown, while applications need low-latency and scalable processing beyond a static batch model. MapUpdate and its Muppet implementation use stream-oriented workflows and slate state; the authors conclude this approach is feasible and promising.
Problem
Method
Results
The authors conclude that a MapReduce-style fast-data framework such as Muppet is feasible and highly promising for applications requiring low latency and high scalability.
Source: §7 · p. 10Takeaways & Limitations
Based on their experience, the authors are deploying Muppet to more applications and extending it in several directions.
Source: §7 · p. 10Muppet does not currently recover lost queue events, accepting some event loss in order to prioritize low latency for most applications.
Source: §4.3 · p. 6
Abstract
from arXiv · showhide
MapReduce has emerged as a popular method to process big data. In the past few years, however, not just big data, but fast data has also exploded in volume and availability. Examples of such data include sensor data streams, the Twitter Firehose, and Facebook updates. Numerous applications must process fast data. Can we provide a MapReduce-style framework so that developers can quickly write such applications and execute them over a cluster of machines, to achieve low latency and high scalability? In this paper we report on our investigation of this question, as carried out at Kosmix and WalmartLabs. We describe MapUpdate, a framework like MapReduce, but specifically developed for fast data. We describe Muppet, our implementation of MapUpdate. Throughout the description we highlight the key challenges, argue why MapReduce is not well suited to address them, and briefly describe our current solutions. Finally, we describe our experience and lessons learned with Muppet, which has been used extensively at Kosmix and WalmartLabs to power a broad range of applications in social media and e-commerce.
1. INTRODUCTION
Fast data streams have grown in volume and availability, creating demand for low-latency, scalable processing. The paper introduces MapUpdate and Muppet, its implementation, and reports their use in social-media and e-commerce applications.
1. INTRODUCTION
- Fast data—high-speed real-time and near-real-time streams—has grown sharply in volume and availability.Examples include sensor streams, stock-market data, and social-media feeds.Source: §1 · p. 1
- Applications need minimal-latency, scalable processing, motivating a MapReduce-like framework for writing and running fast-data applications on clusters.The introduction gives earthquake monitoring of the Twitter Firehose as an example requiring information within seconds while handling volume spikes.Source: §1 · p. 1
- MapUpdate uses stream-based map and update functions, per-key slates that summarize prior events, and workflows combining multiple mappers and updaters.Slates act as updater memory and are distributed across machines and persisted in a key-value store.Source: §1 · p. 1
- Muppet implements MapUpdate and has been used extensively at Kosmix and WalmartLabs for social-media and e-commerce applications.The introduction names Twitter and Foursquare as example streams.Source: §1 · pp. 1–2
2. MOTIVATING APPLICATIONS
The section illustrates stream applications that maintain live outputs, then explains why MapReduce's batch model does not fit them. It outlines requirements for a framework that supports continuous, low-latency, scalable processing.
2. MOTIVATING APPLICATIONS
- Examples include live retailer check-in counts, minute-level hot-topic detection, per-user reputation scores, and live top-URL or web-request counters.The retailer counts are displayed on a web page; hot-topic outputs identify topics by minute.Source: §2 · p. 2
- MapReduce processes a static snapshot, whereas stream computations operate on data that keeps changing.A reducer cannot begin until all mappers finish, unlike computations over evolving streams.Source: §2 · p. 2
- Stream computations do not end and often update data structures or answer queries, while MapReduce reduction requires all values for a key.That complete list is unavailable in a streaming model.Source: §2 · p. 2
- Restarting a failed MapReduce job may be possible, but restarting stream computation may not be because streams continue flowing during processing failures.The section says systems must cope with failures quickly to avoid falling behind the stream.Source: §2 · p. 2
- The desired framework should be easy to program, manage dynamic data structures as first-class citizens, deliver low latency, and scale on commodity hardware.The section also calls for a familiar Map-and-Reduce feel and live querying of computed structures.Source: §2 · p. 2
3. THE MAPUPDATE FRAMEWORK
MapUpdate models applications as workflows that process ordered event streams with map and update functions. Updaters maintain per-key slates as live summaries, while workflows can combine streams, state, and multiple processing stages.
Hardware Assumption
- The framework targets commodity-machine clusters, but stream computations call for machines that are more memory-heavy and less disk-heavy than MapReduce clusters.The section attributes this difference to in-memory structures maintained as streams flow by.Source: §3 · p. 2
Events and Streams
- Events are tuples ⟨sid, ts, k, v⟩, and a stream groups events with the same sid in timestamp order using deterministic tie-breaking.The model assumes timestamps are global across streams and keys group events.Source: §3 · pp. 2–3
Map and Update Functions
- Maps consume subscribed events in timestamp order and emit zero or more later-timestamped events; update functions also consume their subscribed streams in order.Later output timestamps keep stream processing ordered even when events return to the input stream.Source: §3 · p. 3
Update Functions and Slates
- Because a stream does not finish and its full event history may be too large to retain, an updater uses a per-key slate summarizing events seen so far.A new event with the same key updates that slate.Source: §3 · p. 3
- Each update-key pair has its own slate, kept in memory and persisted in a key-value store; a time-to-live can allow deletion to free memory.Developers can reason about and query slates live.Source: §3 · pp. 3–4
MapUpdate Applications
- MapUpdate workflows connect map and update functions through streams; examples count retailer check-ins into slates and detect hot topics from topic-minute counts against historical averages.The hot-topic workflow emits a topic-minute event when the current count exceeds a threshold relative to the average for that topic and minute.Source: §3 · p. 4
Execution Semantics
- Well-defined execution assumes deterministic functions, ordered inputs, and output timestamps later than input timestamps; implementations may approximate, while per-slate state avoids global-variable concurrency conflicts.The model says implementations should approximate the specified streams and slate updates as closely as practical.Source: §3 · p. 4
4. THE MUPPET SYSTEM
Muppet implements MapUpdate by routing events among cluster workers and maintaining persistent, keyed slate state. Its design prioritizes low-latency processing while providing slate access, failure handling, and a more parallel worker model in version 2.0.
4.1 Distributed Execution
- Workers hash event keys and destination functions to route events directly through per-worker queues, avoiding a master intermediary in the latency-sensitive workflow.Events with the same key reach the same updater, which updates the associated slate.Source: §4.1 · p. 5
4.2 Managing Slates
- Muppet caches slates in updater memory and persists them in a key-value store for recovery, overflow beyond memory, and later queries.Configurable time-to-live settings allow unused slates to be garbage-collected; Cassandra-backed storage also supports configurable flushing and quorum choices.Source: §4.2 · pp. 5–6
4.3 Handling Failures
- On worker failure, Muppet redirects events to another worker, but unflushed slate changes and queued events can be lost; replay recovery remains future work.The system prioritizes quickly detecting failure and redirecting events to minimize latency and losses.Source: §4.3 · p. 6
4.4 Reading Slates
- A small HTTP server on each node serves slate fetches from the cache, forwarding requests internally as needed to return current state.The fetch path uses the cache rather than the durable key-value store to ensure an up-to-date reply.Source: §4.4 · p. 6
4.5 Developing Muppet 2.0
- Muppet 2.0 replaces tightly coupled worker processes with shared-code threads and a central slate cache, reducing duplicated memory and enabling parallel execution on multicore machines.Events may be assigned to a secondary queue to balance load, allowing at most two workers to contend for a slate.Source: §4.5 · p. 7
AND ONGOING EXTENSIONS
Muppet was used at production scale for social-media and e-commerce applications, while the authors describe techniques and open constraints around hotspots, throttling, slate access, and cluster operation.
Production experience
- By early 2011, Muppet processed over 100 million tweets and 1.5 million checkins daily at under 2 seconds latency, and by June 2012 its Cassandra store maintained over 2 billion slates.It ran on tens of machines and had been used by about 16 developers to build about 15 applications.Source: AND ONGOING EXTENSIONS · p. 8
Limiting Slate Sizes; Managing Side Effects
- Large slates can slow updaters, so the authors recommend keeping individual slates small, such as kilobytes rather than megabytes.Side effects such as shared logging remain application-managed and can cause lock contention that slows workers.Source: AND ONGOING EXTENSIONS · pp. 8–9
Changing the Number of Machines on the Fly
- The cluster size cannot currently change on the fly, and adding machines requires restarting the application.Redistributing a hot key across machines would require coordinating replicated slate copies; the authors also identify simplifying later Hadoop processing of slates as future work.Source: AND ONGOING EXTENSIONS · pp. 8–9
Handling hotspots
- For associative and commutative counts, Muppet can split a hot key across updaters and emit partial counts for a further updater to aggregate.The example partitions Best Buy events into two keys, then emits and sums their counts under the original key.Source: AND ONGOING EXTENSIONS · p. 8
- When near-real-time latency is unnecessary, source throttling slows input consumption so a hotspot updater can catch up.The authors describe this as suitable for applications without time-sensitive data or for legacy tweets.Source: AND ONGOING EXTENSIONS · p. 8
- Throttling later in a workflow can deadlock when an updater emits back into its own input, whereas input-stream throttling avoids that scenario under the stated assumption.The input streams are assumed not to receive events emitted by mappers or updaters.Source: AND ONGOING EXTENSIONS · pp. 8–9
Placing Mappers and Updaters
- Placing workers near their data to reduce network traffic is difficult because stream popularity and connected update functions can change the best assignment.Muppet may not know in advance which streams will carry the most data or whether popularity changes are transient spikes or trends.Source: AND ONGOING EXTENSIONS · p. 9
Bulk Reading of Slates
- For bulk slate reads, users can log selected data during updates for later streaming to HDFS, or query the durable store if they know Muppet’s storage layout.Logging selected data can reduce dump size and avoid sudden bulk I/O; repeated HTTP fetches may require many round trips or advance knowledge of slate keys.Source: AND ONGOING EXTENSIONS · p. 9
6. RELATED WORK
Related systems support incremental or streaming computation, but differ from MapUpdate in their programming models and state management. Muppet’s explicit, first-class management of application memory as slates distinguishes it from these approaches.
6. RELATED WORK
- Incremental MapReduce systems pipeline partial results, provide deltas, or reuse prior computations, while MapReduce Online retains periodic reducer execution and Nova warns of overhead for small increments.The authors compare Muppet’s main-memory slate cache with pre-combining map outputs by key in.Source: §6 · p. 9
- Streaming query systems often use declarative languages over structured data, whereas MapUpdate uses procedural workflows of custom code for relatively arbitrary Maps and Updates [10] [21] [1] [6] [3] [11].Muppet also differs from Spark Streaming’s small-batch model and does not dynamically change load partitioning except when a machine fails.Source: §6 · p. 10
- Unlike GPU or RDMA approaches, MapUpdate targets arbitrary per-event computation on general-purpose CPUs and uses sharded state on commodity machines linked by gigabit Ethernet.The authors say this design sidesteps an explicit need for fast shared memory between machines.Source: §6 · p. 10
- Muppet’s first-class management of application memory as slates contrasts with S4 and Storm, which leave application state management to developers.The authors say their experience suggests managing that state is highly nontrivial.Source: §6 · p. 10
7. CONCLUSION
The paper concludes that a MapReduce-style framework for fast data is feasible and promising, based on Muppet’s use at Kosmix and WalmartLabs. It highlights the stream-oriented functions, persistent slates, and low-latency design challenges involved.
7. CONCLUSION
- The paper describes MapUpdate as the fast-data framework and Muppet as its implementation developed at Kosmix and WalmartLabs.The authors report experience using Muppet at both organizations.Source: §7 · p. 10
- MapUpdate’s key design differences include stream-based functions, continuously updated slates, Map-and-Update workflows, latency-aware distribution and failure handling, and application-dependent slate persistence.These differences shape how events are distributed and passed through the system.Source: §7 · p. 10
- The authors conclude that a MapReduce-style framework such as Muppet is feasible and highly promising for quickly developing fast-data applications with low latency and high scalability.They report using Muppet at Kosmix and WalmartLabs and say they are deploying it to more applications and extending it.Source: §7 · p. 10
A. EXAMPLE MAP AND UPDATE
Muppet implements application map and update functions through Java interfaces. Figures 3 and 4 show example implementations of the Mapper and Updater interfaces.
A. EXAMPLE MAP AND UPDATE
- Muppet expresses application map and update functions as implementations of the Java interfaces Mapper and Updater.The functions are written in JVM languages.Source: A. EXAMPLE MAP AND UPDATE · p. 11
- Each Mapper or Updater instance is constructed with an application configuration object and a function name, allowing shared code to serve uniquely named functions..Source: A. EXAMPLE MAP AND UPDATE · p. 11
- Figure 3 shows an example Java Mapper, while Figure 4 shows an example Java Updater.The examples correspond to M1 and U1, respectively.Source: Figure 3 · p. 11, A. EXAMPLE MAP AND UPDATE · p. 11, Figure 4 · p. 12