Naiad：融合批处理与流处理的高效数据流系统

需积分: 9 82 浏览量更新于2024-07-19 收藏 293KB PDF 举报

Naiad是一个专为图处理和流处理系统设计的分布式数据流系统，由微软研究硅谷团队开发。它的主要目标是提供高性能、低延迟以及支持迭代和增量计算的能力，这些都是现有系统中可能单独提供的特性，但将这些特性结合在一个框架中往往会导致效率下降、维护复杂性和代码简洁性的牺牲。Naiad通过引入"及时数据流"（Timely Dataflow）这一新的计算模型来解决这些问题。及时数据流模型的核心理念是为数据流程序注入时间戳，这些时间戳代表了计算中的逻辑点。这不仅提供了并行处理的机会，还为实现高效且轻量级的协调机制奠定了基础。通过时间戳，Naiad能够有效地管理和同步各个处理节点的操作，使得并发执行更加精准，避免了不必要的锁竞争和其他复杂同步问题。 Naiad的设计允许程序员利用高级编程模型，如图处理API，构建复杂的数据处理任务，同时保持代码的清晰和可扩展性。它支持实时数据的处理，包括事件驱动的计算，这对于现代应用中的实时分析、机器学习流水线和物联网场景尤其重要。由于其灵活性和性能优化，Naiad旨在成为一种通用的平台，让用户能够在同一个系统中享受到批处理的效率、流处理的实时性和迭代计算的便利。与传统的批量处理系统相比，Naiad在处理实时变化的数据时表现出色，而与专门的流处理系统相比，它又具备更强大的处理复杂图结构的能力。Naiad通过减少跨平台操作的必要性，简化了开发者的工作流程，促进了应用程序的开发效率和整体系统的稳定性。 Naiad作为一款综合性的数据流系统，其创新的及时数据流模型和设计理念使得在高效、低延迟和迭代计算之间取得了平衡，对于那些需要这些特性的现代应用开发者来说，是一个理想的工具选择。

delivery of notiﬁcations, and develop tools for a single-

threaded implementation. Section 3 discusses the issues

that arise in a distributed implementation.

At any point in an execution, the set of timestamps at

which future messages can occur is constrained by the

current set of unprocessed events (messages and notiﬁ-

cation requests), and by the graph structure. Messages

in a timely dataﬂow system ﬂow only along edges, and

their timestamps are modiﬁed by ingress, egress, and

feedback vertices. Since events cannot send messages

backwards in time, we can use this structure to compute

lower bounds on the timestamps of messages an event

can cause. By applying this computation to the set of

unprocessed events, we can identify the vertex notiﬁca-

tions that may be correctly delivered.

Each event has a timestamp and a location (either a

vertex or edge), and we refer to these as a pointstamp:

Pointstamp : (t ∈ Timestamp,

location

! "# $

l ∈ Edge ∪ Vertex).

The SENDBY and NOT IFYAT methods generate new

events: for v.SENDBY(e,m,t) the pointstamp of m is

(t, e) and for v.NOT IFYAT(t) the pointstamp of the no-

tiﬁcation is (t,v).

The structural constraints on timely dataﬂow graphs

induce an order on pointstamps. We say a pointstamp

) could-result-in (t

) if and only if there exists

a path ψ = ⟨l

,...,l

⟩ in the dataﬂow graph such that

the timestamp ψ(t

) that results from adjusting t

ac-

cording to each ingress, egress, or feedback vertex oc-

curring on that path satisﬁes ψ(t

) ≤ t

. Each path can

be summarized by the loop coordinates that its vertices

remove, add, and increment; the resulting path summary

between l

and l

is a function that transforms a time-

stamp at l

to a timestamp at l

. The structure of timely

dataﬂow graphs ensures that, for any locations l

and l

connected by two paths with different summaries, one of

the path summaries always yields adjusted timestamps

earlier than the other. For each pair l

and l

, we ﬁnd the

minimal path summary over all paths from l

to l

us-

ing a straightforward graph propagation algorithm, and

record it as Ψ[l

]. To efﬁciently evaluate the could-

result-in relation for two pointstamps (t

) and (t

we test whether Ψ[l

](t

) ≤ t

We now consider how a single-threaded scheduler de-

livers events in a timely dataﬂow implementation. The

scheduler maintains a set of active pointstamps, which

are those that correspond to at least one unprocessed

event. For each active pointstamp the scheduler main-

tains two counts: an occurrence count of how many

outstanding events bear the pointstamp, and a precur-

sor count of how many active pointstamps precede it in

the could-result-in order. As vertices generate and retire

events, the occurrence counts are updated as follows:

Operation Update

v.SENDBY(e,m,t) OC[(t,e)] ← OC[(t, e)] + 1

v.ONRECV(e,m,t) OC[(t, e)] ← OC[(t,e)] −1

v.NOTIFYAT(t) OC[(t,v)] ← OC[(t, v)] + 1

v.ONNOT IFY (t) OC[(t,v)] ← OC[(t, v)] − 1

The scheduler applies updates at the start of calls to

SENDBY and NOT IFYAT, and as calls to ONRECV and

ONNOT IFY complete. When a pointstamp p becomes

active, the scheduler initializes its precursor count to the

number of existing active pointstamps that could-result-

in p. At the same time, the scheduler increments the

precursor count of any pointstamp that p could-result-

in. A pointstamp p leaves the active set when its occur-

rence count drops to zero, at which point the scheduler

decrements the precursor count for any pointstamp that

p could-result-in. When an active pointstamp p’s pre-

cursor count is zero, there is no other pointstamp in the

active set that could-result-in p, and we say that p is in

the frontier of active pointstamps. The scheduler may

deliver any notiﬁcation in the frontier.

When a computation begins the system initializes an

active pointstamp at the location of each input vertex,

timestamped with the ﬁrst epoch, with an occurrence

count of one and a precursor count of zero. When an

epoch e is marked complete the input vertex adds a new

active pointstamp for epoch e + 1, then removes the

pointstamp for e, permitting downstream notiﬁcations

to be delivered for epoch e. When the input vertex is

closed it removes any active pointstamps at its location,

allowing all events downstream of the input to eventu-

ally drain from the computation.

2.4 Discussion

Although the timestamps in timely dataﬂow are

more complicated than traditional integer-valued time-

stamps [22, 38], the vertex programming model supports

many advanced use cases that motivate other systems.

The requirement that a vertex explicitly request notiﬁ-

cations (rather than passively receive notiﬁcations for all

times) allows a programmer to make performance trade-

offs by choosing when to use coordination. For exam-

ple, the monotonic aggregation operators in Bloom

[13]

may continually revise their output without coordina-

tion; in Naiad a vertex can achieve this by sending out-

puts from ONRECV. Such an implementation can im-

prove performance inside a loop by allowing fast un-

coordinated iteration, at the possible expense of send-

ing multiple messages before the output reaches its ﬁnal

value. On the other hand an implementation that sends

only once, in ONNOTIF Y, may be more useful at the

boundary of a sub-computation that will be composed

with other processing, since the guarantee that only a

single value will be produced simpliﬁes the downstream

442

剩余16页未读，继续阅读

skyact

粉丝: 0
资源: 4

Naiad：融合批处理与流处理的高效数据流系统

dataflow:一个关于块、操作、模块和中间箭头的项目

Naiad: A Timely Dataflow System

UP-Naiad 1.4

Naiad: A Timely Dataflow System(presenation)

Naiad-Clients:此git repo包含所有Exotic Matter的官方Naiad客户端应用程序的完整源代码，例如Naiad Studio和Naiad Command-Line客户端-git source code

Naiad-Buddies:Naiad Buddy是促进Naiad与第三方应用程序之间通信的插件，Naiad用户操作和命令行工具的集合。 这个git repo包含了所有当前可用的Naiad好友的完整源代码-Source code collection

UP-Naiad Player1.3

CFE10A14-D883-4ACE-990A-0DDA86AA362B:预装了 Naiad 支持的 Pharo 3.0 内存

naiad buddy for maya2011-2014

Naiad3dsMaxBuddy_2011-2014_x64

最新资源

Naiad-Buddies:Naiad Buddy是促进Naiad与第三方应用程序之间通信的插件，Naiad用户操作和命令行工具的集合。这个git repo包含了所有当前可用的Naiad好友的完整源代码-Source code collection