理修棟生活

Title:Borealis: Distributed Stream Processing Engines
Speaker: Magdalena Balazinska (Univ Washington)

research channelでborealisに関する講義が聴講できる。
この講演は信頼性のある分散ストリーム処理についての話だった。
以下メモ。

○Fault-Tolerance Goals
・Failure assumptions
Fail-stop failures of processing nodes
Network failures and network partitions
No data source failures or Byzantine failures
・Availability: Low per-tuple processing latency
・Consistency: Output identical to failure-free execution

○Fault-Tolerance Problem
・When possible,completely mask failures
・Goal1: Favor availability
Some increase in latency is tolerable
・Goal2: Eventual consistency
Correct results after failure heals
・Goal3: Minimize inconsistency
Minimize number of possibly incorrect tuples
Minimize impact of failures
Minimize degree of divergence

○New Data Model
{time,type,id, a1,...,an}
・id: unique identifier
・type: tuple type
Data tuples: STABLE,TENTATIVE
Control tuples: BOUNDARY,UNDO,REC_DONE
・TENTATIVE tuples
Result from processing a subset of inputs
Corrected with a single UNDO tuple

○Fault-Tolerance Challenges
・Replicas proces tuples as they arrive
Affects operators with multiple inputs
・Upstream/downstream dependencies
・Large,rapidly changing transient state
Reconciling state is expensive and disruptive
・Independently of failure scenario
STABLE tuples are immutable
Correct TENTATIVE with STABLE
Meet availability and consistency requirements

○Borealis Fault-Tolerance Protocol
・Under normal operation
New operator maintains replica consistency
・When a failure occurs
Process available data within per-node bound D
Attempt to minimize inconsistency
・When failure heals
Reconcile state and correct output
Continue to process new tuples
Attempt to minimize inconsistency

○Protocol State Machine
there are three state,STABLE, UPSTREAM FAILURE, and STABILIZATION.
STABLE state keeps to maintain consistency and to detect failures.

○Consistency Without Failures
・Replicas must process tuples in same order
・Approach: each replica computes the order
・New serializing union, SUnion operator
Deterministic sort function on buckets of data

○State Reconciliation. Option1: Checkpoint/Redo
・At runtime, periodically checkpoint state
・After failure heals, restart from checkpoint
・Correcting output tuples
UNDO tuple followed by stream of corrections

○Checkpoint/Redo Properties
・Multiple failures
All inputs must be corrected before reconciling
Checkpoint before new failure
・Performance
CPU and memory overhead of checkpoints
Checkpoint as entering UPSTREAM_FAILURE
Reconciliation time increases linearly with failure duration and state size

○Load Management Problem
・Continuous tasks impose load on resources
・Want to move tasks between participants
improve system-wide performance
At least all participants operate within capacity
・Well-studied problem
Assume collaborative environment
Don't work for federated systems

○Conclusion
・Borealis: distributed SPE
・Fault-tolerance scheme
Availability and eventual consistency
Flexible availability/consistency trade-off
Replica autonomy
・Load management scheme
Acceptable allocation
Simple,lightweight,enbales discrimination

○Future Work
・Stream Processing
Accuracy and integrity constraints on streams
Integration with various data types
Stream minig, storing, and indexing
Querying current and historical data
Variable data sources with duplicate information
・P2P and federated systems
Incentives and collaboration
Schemes that favor simplicity and practicality
Various types of collaborations and sharing