4 ms·
> High throughput and low latency stream processing with exactly-once guarantees. Precisely how is this possible in a real-world distributed system? At-least-o
by falcolas 11y ago
> High throughput and low latency stream processing with exactly-once guarantees.
Precisely how is this possible in a real-world distributed system? At-least-once and at-most-once are possible with different distribution methods, but "exactly-once" is, well, I have yet to see it actually implemented (even theoretically, see the Two Generals thought experiment). Even their checkpointing algorithm has an assumption that the underlying transport is "exactly once" and "FIFO ordered".
If I had to guess, I'd say that what they're really guaranteeing is "at most once" message delivery. Unfortunately, that has a very different meaning from "exactly once".
http://bravenewgeek.com/you-cannot-have-exactly-once-delivery/ http://bravenewgeek.com/you-cannot-have-exactly-once-deliver...
- faizshah 11y agoI'm pretty sure that this is the algorithm flink uses: http://arxiv.org/pdf/1506.08603.pdf http://arxiv.org/pdf/1506.08603.pdf EDIT: fyi sewen is one of the authors of the paper and a founder of flink
- sewen 11y agoYou do not need physical exactly once. If you can "roll back" changes, than physical "at least once" is enough to realize logical "exactly once".
- falcolas 11y agoRolling back changes means that at some point in time, you have "more than once". It also means you can only ever implement logic which can be rolled back. In a pipeline scenario, that is challenging to do without some sort of external locking system.
- sewen 11y agoTrue. In most streaming systems, exactly-once refers to the state that is maintained and controlled by the streaming system. For that, Flink can guarantee such semantics. That state can also be exposed externally, see for example here: http://data-artisans.com/extending-the-yahoo-streaming-benchmark/ http://data-artisans.com/extending-the-yahoo-streaming-bench... For interactions (writes) with external systems, you need transactional integration. There is WIP to do this for transactional databases, for non transactional systems, there are cases where it cannot be strictly solved.
- pkolaczk 11y agoPhysical at-least-once is easy to transform into a logical exactly-once. Just assign a unique id to every message at the source and discard duplicates at the target.
- falcolas 11y agoYou're describing "at most once". The key is that a message could be lost between components, and there's nothing here which accounts for that. EDIT: To clarify a bit more, I'm looking at the "at most once" as once throughout the entire system. Not once per node. Combining a physical at-least-once with a logical "at-most-once" only works at the per-logical node level, not at the system level. Some processing will occur more than once in a system, which could have negative consequences if the processing is not strictly idempotent.
- TheHydroImpulse 11y agoUsing an acking system (like that in Storm or Heron) would move it to be physically at-least-once with a logical exactly-once by de-duping at the target. This means if you observe the inner system, you won't be seeing exactly-once semantics but looking at the system from the outside, the semantics would indeed be exactly-once at the target.
- jahitr 11y agoThis is something it bothers me a lot. What they don't tell you is that in order to achieve "exactly once" delivery you need to have idempotent writes. For example inserting in a database using PKs.
- senorcarbone 11y agoExactly-once delivery really depends where and how you actually "deliver". Even if your writes are idempontent you need to know if they have been properly committed on the other side, not that simple. If the system you are committing your output offers version control and/or proper transactional support then delivery can be eventually re-conciliated. Apache Flink's snapshotting algorithm solely guarantees exactly-once application state access, plain and simple.
- ptgoetz 11y agoExactly-once in a distributed system doesn't exist, and we need to get past that. It can be approximated with replay (at-least-once) and de-dupe/idempotency. Trying to ensure true exactly-once is a fools errand. In a distributed system it required guarantees (down to the magnetic material level) that are very hard to get right. If any of those guarantees fail, you don't have it. What you have is a close approximation. Real world applications usually involve a lot more than counting words in memory. At-least-once is relatively easy. Combine it with idempotent operations and your work is done. Storm is fairly explicit in documenting what it takes to achieve this, but it's not trivial, and every system involved has to support certain guarantees. Spark (streaming) made some pretty big claims about exactly-once guarantees, but it turned out that claim was riddled with holes. In my opinion, "exactly-once" doesn't imply that there are exceptions to that rule. Guard against dupes and you'll be fine (easier said than done, obviously), but also know the limitations of the systems and frameworks you are working with. EDIT: Disclaimer: I am an Apache Storm PMC Member
- sewen 11y agoI disagree on some points. First, it is crucial to distinguish between "exactly-once" semantics with respect to state inside the stream processor (for example an aggregate computed in a window) an exactly-once delivery to external systems. The former is built into Flink, the later is only possible in some cases (transactional systems) and requires extra effort. Exactly-once for state inside the stream processor is incredibly useful, because it allows you to implement many non-idempotent operations such that the writes to external systems are idempotent: For example, you compute the complex aggregate in the stream processor and only periodically write the result to the external system (overwriting previous values). Now the external system always reflects an aggregate without duplicates. That is very valuable and only possible if inside the stream processor, you have exactly-once semantics for state. That does imply that the stream processor has a notion of managed state (in Flink for example the Windows, key/value state, and generic checkpointed state). Disclaimer: I am a Flink committer.
- pcx 11y agoIt is possible to provide exactly-once guarantee. Trident does this over Storm. http://storm.apache.org/documentation/Trident-tutorial.html http://storm.apache.org/documentation/Trident-tutorial.html
- cbsmith 11y agoThis has been demonstrated for a long time with Storm's Trident.
- azylman 11y ago"exactly once" is actually pretty common. You can read about how Google does it in their MillWheel paper: http://static.googleusercontent.com/media/research.google.com/en//pubs/archive/41378.pdf http://static.googleusercontent.com/media/research.google.co... They also compare their guarantees to other streaming systems, and they're not the only one to offer exactly once.
- senorcarbone 11y agoFlink guarantees exactly-once application state access/updates. There is no mention of exactly-once delivery anywhere and it is pretty much impossible to offer this for just any general sink. That does not exclude the possibility of offering a special-purpose transactional sink implementation in the future though (e.g. via external distributed locking/state reconciliation), just saying...
- senorcarbone 11y agoEven that solution would approximate exactly-once delivery (eventually) but not strongly guarantee it.