确定性流处理总结

StreamScopeflamestream实现了确定性流处理。

1.实现思想

这两篇论文中都指出需要实现确定性的处理,需要保证

  • 确定的执行逻辑,即相同的输入会有相同的输出,在flamestream[1]中指出用户定义的逻辑必须是pure function。StreamScope[2]中提到用户定义的逻辑必须是确定的。
  • 确信的执行顺序
    在算子计算逻辑是确定的情况下,需要保证输入顺序是确定的。在保证source输入顺序和传输管道FIFO的情况下,造成算子输入不确定的原因主要是shuffle过程带来的多个上游输入交汇导致交汇后的顺序无法保障,针对这一情况,目前流行的做法是IOP和OOP.
    对于有多个流输入的情况,StreamScope和flamescope采用了不同的处理方式,StreamScope采用了IOP(in order process)的方式,,flamestream则采用了OOP(out of order)的方式.


    IOP处理

    OOP

Streamscope中在有多个上游输入的算子前加入merge算子插入CTI event(CTI event类似low watermark,event类似tuple)的方式,保证收到时间戳在CTI event之前的event,之后按照确定的方式进行排序和处理,从而保证流交汇后的顺序,从而保证处理的确定性。这里和OOP的处理方式类似,也是通过插入punctuation保证元组都收到了。但由于streamscope对buffer的元组进行了确定性排序,以保证数据能被通过确定性的计算恢复,所以我认为算是IOP的处理方式。

进行join的两个输入流在处理之前通过merge算子合并成确定性的顺序

flamestream则是将状态视为流的一部分,使得大部分算子从有状态算子转变成无状态算子,仅grouping算子需要维护状态,grouping算子的作用是将计算状态和item(item类型flink中的tuple)划分到一个窗口为2的item中,使得下游算子处理时能够按照状态和状态对应的算子进行计算。
将状态视为流的一部分

仅grouping算子需要维护状态,grouping算子对于乱序的输入,采用了乐观的修复方式,具体可以参考[3]
grouping修复乱序

2.延迟的引入:

Streams延迟主要存在于有多个流输入的算子,需要等待CTI event 到来,从而进行排序和输出,由于下游算子需要满足确定性的顺序,只有有流合并的产生对于有状态和无状态的算子都需要等待CTI event并进行排序。论文认为Because the processing logic of vertices tends to wait for the CTI events in the same way, this solution does not introduce additional noticeable delay 面对deep pipeline时,下游和上游算子等待处理CTI event的方式相同,因此多个级联的merge并不会引入过多的延迟。
flamestream面对流交汇产生的乱序tuple,采用的修复策略。只要在最终输出设置barrier根据接受的tomb过滤无效的算子,因此只会在barrier处引入延迟,。

3.性能

Streamscope尚未开源,没有与其他框架的性能对比实验
flamestream就建立倒排索引与flink进行了对比实验,证明在低吞吐量情况下,flamestream具有比flink更低的延迟,但在吞吐量较高的情况下,flink更为占优。

flink 和 flamstream对比

flink与flamestream的对比

图八来源[4]

4.疑问和思考

1.flamestream[1]中提到乱序tombstone仅占所有item的10%。但我觉得可能针对不同的情况有不同结果,可能有不同的性能,比如一个迟到很久的event会导致好重新计算很多的item,对性能造成很大影响,如果对group的输入元组进行一个排序,比如采用 Max determine 的方法[5],不严格保证顺序,应该能显著降低tombstone的产生。
2.flamestream中只提到基础的map reduce的实现,对于其他算子,如窗口、join等没有进一步说明。
3.flamestream没有提到是否支持event time,但我想如果系统外部输入元组的时间不是有序的,则flamestream不能保证处理所有乱序数据,barrier是按最小运行的元组的global time进行拦截的,若此时外部输出时间小于系统此时记录的最小运行时间,则barrier无法保障拦截所有无效元组。


  1. Kuralenok I E , Trofimov A , Marshalkin N , et al. Deterministic Model for Distributed Speculative Stream Processing[J]. 2018.jiangq

  2. Wei L, Fan H, Qian Z, et al. STREAMSCOPE: continuous reliable distributed processing of big data streams[C]// Usenix Conference on Networked Systems Design & Implementation. 2016.

  3. https://www.jianshu.com/p/d77048c8ae7d

  4. https://research.jetbrains.org/files/material/5b2459ef42bb9.pdf

  5. Zacheilas N , Kalogeraki V , Nikolakopoulos Y , et al.Maximizing Determinism in Stream Processing Under Latency Constraints[C]// Acm International Conference on Distributed & Event-based Systems. ACM, 2017

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 213,417评论 6 492
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 90,921评论 3 387
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 158,850评论 0 349
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 56,945评论 1 285
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 66,069评论 6 385
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 50,188评论 1 291
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 39,239评论 3 412
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 37,994评论 0 268
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 44,409评论 1 304
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,735评论 2 327
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,898评论 1 341
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 34,578评论 4 336
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 40,205评论 3 317
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,916评论 0 21
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,156评论 1 267
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 46,722评论 2 363
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 43,781评论 2 351

推荐阅读更多精彩内容