Hello World
Spiga

讨论:一则并行聚合计算方案的设计

2012-09-05 23:31 by 老赵, 5436 visits

最近的工作让我想到了一个对集合的元素进行并行聚合的案例,尽管这个需求还不存在,但最近却一直在我的脑海里挥之不去,尚未得出令人满意的结果。今天下班前我将这个问题辛苦地缩减为140字内的描述发到了微博上,得到了许多同学的回复,但可能是由于描述过于简单,得到的建议似乎都不能满足我的需求。于是在此我通过博客详细描述下这个问题的需求,还有我之前做过的尝试,这样讨论起来也可以更加有针对性一些。

问题描述

现有一个集合,最多包含100K个元素。每个元素包含100个字段,为了简化问题假设这些字段都为整型,因此我们完全可以把所有数据都加载到内存中。同时,我们定义两种修改操作:

  1. 向集合中添加或删除一个元素。
  2. 修改元素中某个属性的值。

我们会有一个线程不断的将这两种修改操作运用到整个数据集中。修改是串行执行的,前一个操作完全执行结束才会开始下一个,但频率十分密集,例如每秒会产生数百甚至数千次修改,其中第2种修改的次数远多于第1种。

我们需要对集合中的元素进行聚合运算,聚合规则不超过50个,每条规则都会给定一个名称及其计算方式,例如:

  1. SumOfA:对集合中所有元素的A字段的值求和,即Sum(A)
  2. AvgOfB:对集合中所有元素的B字段的值求平均,即Avg(B),或Sum(A) / Count(A)
  3. WtdAvgOfCD:对集合中所有元素的C字段和D字段做加权平均,D为权,即Sum(C * D) / Sum(D)

除了对整个集合进行聚合之外,我们还会给出多个字段(不超过5个)用于分组,整个集合会被这些字段的不同值划分为不同的小集合,并需要将相同的聚合规则运用在每个小集合内,最终所有的聚合数据会完整展示在界面上,例如:

A B C SumOfA AvgOfB WtdAvgOfCD
- - -
1 - -
- 2 -
- - 3
- - 4
- 5 -
- - 6
- - 7
8 - -
- 9 -

上表中使用A,B,C三个字段进行分组。由于恰好每行一个数字,这里便以这个数字作为行号了(最上方没有数字的那行则当做第0行)。这个表格可以视作是一个展开的树状结构,每个树状结构的节点包含每个聚合规则的名称及其结果。

例如第0行,便是针对整个数据集的聚合结果,而第1行则是“字段A等于1”的所有元素的聚合结果。第2行从结构上看处于第1行的“内部”,因此它展示的其实是A == 1 && B == 2的所有元素的聚合结果。同理可得,第7行为A == 1 && B == 5 && C == 7,而第9行为A == 8 && B == 9的所有元素的聚合结果。

这张表格显然会无比巨大,在实际情况里我们只可能显示其中的一小部分数据,但是由于用户可以随意拖动滚动条,因此事实上所有的数据都希望可以立即显示出来,并且尽量实时地显示最新数据集的聚合结果。此外,也有一些(与本问题无关的)计算需要使用完整的聚合结果,因此我们希望在内存中存在完整的结果,而不是仅仅计算“显示出的那部分数据”。

另外,实际情况下内存中可能存在多个这样的集合,集合中的元素可以共享,但每个集合都需要聚合(规则各不相同)。如果还有什么额外的条件的话,那么再假设“分组的字段”更新频率较小吧。

我的串行解决方法及并行尝试

由于实际情况下的数据量相对较小,我通过一个简单的串行的实现便可以满足性能要求。为此我实现了两个基础功能:

  1. 一个在添加和删除元素时可以得到通知的集合。
  2. 在更新元素属性时,也可以得到元素本身,被更新的属性,以及更新前后的值。

我在集合上运用聚合器,同时监听集合中每个元素的属性改变。聚合器内部保留中间状态,这样当新元素添加到集合中时,便可以利用新增或删除的元素做差值计算,由于属性修改时可以获得更新前后的值,因此差值计算同样可行。

至于分组,其实就是利用一个额外的组件,将一个集合划分为多个子集合。例如我们要对A,B,C进行分组,则先根据A进行分组得到一堆子集合,每个子集合内的元素都拥有相同的字段A的值,然后为每个子集合分别运用聚合器,这便是满足如A == 1的所有元素的聚合结果。分组器同样会监听集合以及集合中每个元素字段的改变,维护每个子集合内的元素。例如某个元素的字段A从1被修改为2时,分组器会将这个元素从子集合1移动到子集合2中,这会触发两个子集合的变化通知,从而触发这两个集合中的聚合器更新。至于更深一级的聚合结果,则会将相同的分组策略运用到每个子集合中,只不过这次针对下一级的分组字段(例如B)即可。不断深入,直到最后一层分组。

这样无论是什么样的修改操作,每次修改完成之后都会立即更新聚合结果,且只会改动受影响的部分。但是随着数据量和更新频率的提高,我希望可以利用多核CPU来增加计算效率。这种并行运算会产生延迟,这并没有关系,只要尽量实时即可。有些同学提出在每次变动后并行计算结果,这个最容易,但实际上并不可行。因为数据随时都在更新,每次针对整个数据集进行计算会导致CPU久高不下,且并行计算的同时数据也在变动,因此计算过程中也会出现并发问题,甚至得到错误的结果。

我目前的尝试是像Erlang那样,将每个聚合器作为一个Actor来对待。元素的改变会作为消息发送至聚合器,高一级聚合器又会发送消息给低一级的聚合器(这种消息传递并不一定是直接“转发”)。这种做法会让整个系统都是“热”的,且能够自然而然地进行并发,且单个聚合器可以保持串行。但是,随之而来的问题是,由于元素属性本身在不断更新,导致我们的“延迟计算”无法在处理消息时得到当时的值,这需要我们在发送消息时携带当前元素的“快照”,这样又会带来额外的开销。元素的添加删除操作倒也罢,但假如每次在字段更新时都要携带整个快照的话,这带来开销实在太高。不过似乎我们也只需要在“分组字段”改变时携带快照即可,因为只有那时才会引起聚合器的变动(这与之前元素在子集合之间移动的性质相同)。要知道分组字段改变次数相对会少很多,因此在大部分情况里我们只需要使用字段的更新前后的值即可。

总结

欢迎各位同学给出自己的设想,描述地越详细越好,如果能给出参考实现便再好不过了。假如您对需求或是限制还有什么不明白,也请立即提出,我可以作进一步解释或是更新文章。我也会继续尝试和探索,希望最后能给出一个完整的示例程序。

Creative Commons License

本文基于署名 2.5 中国大陆许可协议发布,欢迎转载,演绎或用于商业目的,但是必须保留本文的署名赵劼(包含链接),具体操作方式可参考此处。如您有任何疑问或者授权方面的协商,请给我留言

Add your comment

46 条回复

  1. 宝玉
    114.84.2.*
    链接

    宝玉 2012-09-05 23:39:02

    好复杂。。。

  2. 老赵
    admin
    链接

    老赵 2012-09-05 23:52:34

    @宝玉

    我当时居然用140个字进行描述,哈哈。

  3. 宝玉
    114.84.2.*
    链接

    宝玉 2012-09-06 00:12:01

    我的思路是类似于数据库索引表:

    每一种聚合条件(或排序条件)维护一个独立的排序数组,数组包含聚合的结果和对应元素的Key。每次元素更新去更新元素在各个数组中的值并排序。需要用到哪个聚合去访问哪个数组获取到Key的集合,然后根据Key结合去访问元素集合。去更新这些排序数组的时候多线程执行。

    我觉得还比较简单可行。

  4. Ruoshi Li
    121.15.1.*
    链接

    Ruoshi Li 2012-09-06 00:19:22

    把每次的操作和操作目标封装起来放到一个队列里面由一个独立的线程进行计算行不?

    例如

    {"Action": "Add", "Delta": {...}} // Delta = 新元素
    {"Action": "Remove", "Delta": {...}} // Delta = -1 * 被删除元素
    {"Action": "Update", "Delta": {...}} // Delta = 保留分组属性
    

    其他元素所有属性都初始化为0,除了更新的元素为 “新值 - 旧值”,如果分组属性改变则更新被分解为一条新增和一条删除,由另外的变量保存计算结果,例如Sum、Count、分组的Sum、Count等等。计算的时候只计算差异即可,例如Sum可以只加或者减Delta中相应值。

  5. 老赵
    admin
    链接

    老赵 2012-09-06 00:25:40

    @Ruoshi Li

    你的思路和我差不多,但是我是Erlang形式的并行,你是独立线程并发不充分……

    此外光有Delta是不够的,假如A字段修改导致这条记录从一个分组转移到另一个分组,这会引起两个分组的Add和Remove操作。但是这个Add和Remove操作在计算时是需要其他字段的数据的,光有A字段的数据是不够的。这就是我文章里提到的“快照”。

    还有一个办法,就是在每个聚合器里保存那个元素到聚合器里当前值的映射关系,但是这个对空间要求就太高了,你想100K个元素就要一个100K大小的字典,而且是每个聚合器都一个字典……

  6. dcaoyuan
    222.240.149.*
    链接

    dcaoyuan 2012-09-06 00:33:07

    你文章后头提到的“像Erlang那样,将每个聚合器作为一个Actor来对待”,我觉得基本可行,也是我现在的金融计算平台的并行处理情境之一。我是用Scala实现的,实践证明可以应对2000 * 100K以上的数据,且相应聚合器的种类有100个以上。至于携带快照的开销,一个(变动)元素的数据应该不会太大吧,而且这个数据拷贝一次成immutable量后就可以给所有的聚合器Actor使用。

    如果真的发现监听+异步传递的方式需要传递的“快照”开销太大,干脆不采用每次变动都触发计算的方法,而是同时维护一个数据副本,每隔指定间隔,比如10ms(这个间隔必须大于做完一次计算需要的时间,或者每计算完一次触发下一次),立即锁住这个副本,同时把后续的变动记入一个log以在计算完成并释放锁后用来追上最新的变化,然后利用前次的log和这个完整的副本“快照”做计算。

    以上这些措施在我的平台中都有用到,以处理各种不同的并行计算场景。

    其实,现在我最不确定的,是你提到的“这需要我们在发送消息时携带当前元素的“快照”,这样又带来的额外的开销”,这个“开销”究竟是什么个情况。

  7. 左耳朵耗子
    123.121.25.*
    链接

    左耳朵耗子 2012-09-06 00:37:43

    我一开始在想怎么建数据结构,后面在想你要多线程,安全性怎么办?想着想着就发现就是数据库+索引,集合就是view,修改删除的操作可能用触发子解决。我猜想数据库做得已经很牛B了,没必在重要发明轮子了,100K的记录数对数库小菜一盘。呵呵,我这样说,不知道LZ满不满意。嘿嘿嘿……

  8. Ruoshi Li
    121.15.1.*
    链接

    Ruoshi Li 2012-09-06 00:38:51

    哦,其实我也写到了,如果分组改变则把一个Update操作变为一个Add和一个Remove操作,遵循Add/Remove的Delta规则。对多核的充分利用,可以考虑把不同的计算放到不同的线程里面?或者使用CCR/TPL Dataflow那种Post/Arbiter模型?

  9. deerchao
    121.11.193.*
    链接

    deerchao 2012-09-06 00:39:12

    既然数据时刻都在变, 那么就没有必要总是要显示最新的值.

    可以直接每隔一段时间(如1秒,或者其它对业务场景更有意义的时间段),重新计算一次即可. 计算时也可以暂停数据更新, 这样也有利于并行.

    这肯定不是科学上最优解法, 却可能是工程上一个比较合适的处理选项.

  10. Ruoshi Li
    121.15.1.*
    链接

    Ruoshi Li 2012-09-06 00:46:09

    @左耳朵耗子

    没错,使用数据库是个方法,尤其是支持列式存储的数据库

  11. 老赵
    admin
    链接

    老赵 2012-09-06 00:48:31

    @Ruoshi Li

    正是分组改变需要数据快照,否则光靠Delta是不行的,你试一下就会遇到障碍了……还有.NET里搞Erlang式的Actor自然就是TPL DataFlow了嘿嘿……

  12. zhangyijun
    58.41.22.*
    链接

    zhangyijun 2012-09-06 00:50:05

    简单的想了一个增量+并发的思路:

    1. 所有改变有一个递增ID,类似DB 的Redo Log记录全部更新事件。事件保存完整修改前后diff数据(新增、删除记录所有字段信息,修改记录字段名、修改前后值。如果数据量太大,也可以根据规则过滤不相关的字段信息)
    2. 每一个聚合规则,是一个独立的对象,内部记录最后更新事件ID,规则计算的结果(还有必要中间结果,例如Avg保留 Sum和 Count)
    3. 多个线程(或进程)可以定期(或结合其他出发机制,但一定要批量)获取最新事件ID,来触发聚合规则计算:增量方式(依据两个ID)计算新结果,并记录最后更新事件ID。
    4. 一个线程可以检索规则中,最早的更新ID,清理小于此ID的事件记录,释放内存

    聚合的增量计算,则要单个规则去实现。Sum非常容易,简单加减即可。Avr则需要内部记录Sum,Count,再分别加减后,重新计算。 至于分组聚合,也可以类似方式去做,但需要更多内存记录中间结果,如果这中间还要再并行,需要做排序、和等待协调,感觉上复杂,不一定带来效率。

    weibo: @张义军SH

  13. 老赵
    admin
    链接

    老赵 2012-09-06 00:51:16

    @deerchao

    每隔1秒或更新时重新计算一次CPU就永远停不下来了……还有计算时停止数据更新是不好的,因为数据本身不光是给聚合用的,还有别的用处啊。而且也不容易实现,本来聚合和数据集修改是无关的操作,现在变成紧密相关的了……

  14. 老赵
    admin
    链接

    老赵 2012-09-06 00:55:08

    @dcaoyuan

    “开销”就是把涉及到的字段都拷贝出来一份啦,例如所有的聚合条件涉及到100个字段中的20个,那么就复制这20个。我的担心是更新单个属性的时候,就需要创建一个快照,但现在看来,只要在涉及分组字段更新的时候创建一份快照即可,这个情况会少很多。

    我现在也觉得我的“设想”是可行的,得抽空实现一下,还是需要写不少代码的。

  15. deerchao
    121.11.193.*
    链接

    deerchao 2012-09-06 01:14:04

    每隔1秒或更新时重新计算一次CPU就永远停不下来了

    永远停不下来是因为数据永远在变, 我觉得这个是没有问题的. 如果有时数据会停止变动, 那也好办, 设一个标志, 数据变了就设为真, 计算完成后设为假, 下次计算时先检查该标志就可以了.

    还有计算时停止数据更新是不好的,因为数据本身不光是给聚合用的,还有别的用处啊

    保存两个版本的集合(100 K * 2 = 20 M, 这么多的元素引用存储起来没什么压力). A用于更新和其它用途, B用于计算, A/B可以用享元数据模式引用相同的元素来减少内存占用. A持续更新不被打断. 要计算时先复制A到B(应该可以无锁直接复制吧), 然后对 B 进行计算. 计算过程中要更新A里元素的属性时采用 Copy On Write 方式.

    而且也不容易实现,本来聚合和数据集修改是无关的操作,现在变成紧密相关的了……

    采用以上方式后,两者仅通过两个标志相关: 一个是数据是否变脏, 一个是计算是否正在进行.

  16. 老赵
    admin
    链接

    老赵 2012-09-06 01:37:04

    @deerchao

    一个简单的数据改变就重新计算整个数据集了,这太不环保了,而且要知道实际情况下还可能有5~10个数据集同时存在啊,未来可能更多。事实上我之所以改成现在这种串行的结构,就是因为之前用你说的这种做法让CPU久高不下(更新触发重新计算,并做Throttling,不超过500毫秒更新一次),而且数据量还比现在设计地要小不少。

    Copy on Write我也考虑过(就是上面说的创建“快照”的时候),但发现实现起来影响会很大。本来元素都是普通的POCO或POJO,现在设置的时候需要更多操作了。而且实际情况下一个元素会共享给多个数据集,每个数据集都是独立计算的,所以一个元素会关联多个Copy,还要维护元素和Copy之间的关系,例如计算前把Copy关联到对象,计算后再移除,关系甚至会是双向的。

    最后还是耦合的问题,本来修改和其他操作是独立的完全没有耦合,而现在负责“修改”的那个组件需要关注的东西就更多了。实际情况里还有更复杂的状况,例如可能某个聚合规则是计算Sum(A),而A会由B、C和D的改变来更新(例如B > 0 ? C : D)。本来例如B的更新会触发普通的A的更新,处理起来和另一个字段的普通更新没啥两样,现在如果要Copy on Write,还真不是一下子能想明白的,活活。

  17. deerchao
    121.11.193.*
    链接

    deerchao 2012-09-06 01:57:22

    一个简单的数据改变就重新计算整个数据集了,这太不环保了,而且要知道实际情况下还可能有5~10个数据集啊,未来可能更多。事实上我之所以改成现在这种串行的结构,就是因为之前你说的这种做法性能上不可行,而且数据量还比现在设计地要小不少。

    正是为了可伸缩性才用了定时计算的办法啊. 一定时间内,这种办法只会重新执行一次大的计算; 不定时的话每次有数据变动都要执行一次小的计算, 理论上还不好说哪种方式更节约计算资源. 当更新变得更频繁时, 不会影响到这种方式计算的效率. 当数据规模变大时, 只需要改一个参数(定时间隔)就可以轻松应对. 当然, 事实胜于雄辨 :((

    Copy on Write我也考虑过(就是上面说的创建“快照”的时候),但发现实现起来影响会很大。本来元素都是普通的POCO或POJO,现在设置的时候需要更多操作了。而且实际情况下一个元素会共享给多个数据集,每个数据集都是独立计算的,所以一个元素会关联多个Copy,还要维护元素和Copy之间的关系,例如计算前把Copy关联到对象,计算后再移除,关系甚至会是双向的。

    最后还是耦合的问题,本来修改和其他操作是独立的完全没有耦合,而现在负责“修改”的那个组件需要关注的东西就更多了。实际情况里还有更复杂的状况,例如可能某个聚合规则是计算Sum(A),而A会由B、C和D的改变来更新(例如B > 0 ? C : D)。本来例如B的更新会触发普通的A的更新,处理起来和另一个字段的普通更新没啥两样,现在如果要Copy on Write,还真不是一下子能想明白的,活活。

    是很麻烦. 元素改成 immutable 呢?

    耦合当然不好,但也是设计中可以取舍的一个方面.

  18. tokimeki
    114.34.164.*
    链接

    tokimeki 2012-09-06 02:52:31

    我最近做的一個 Waterfall 控件內部的資料處理很類似你這個問題,差別在於這個控件會在每隔一段時間(例如每0.1秒)確定整個集合的暫態。 然後根據一個固定的時間帶(例如1分鐘)去維持一段可使用的資料暫態的集合,超過這個時間帶的資料會被拋棄。

    我不清楚你使用聚合計算的場景為何,我的做法可以簡單的把資料看成一個隨時間流動的二維陣列,你要怎麼並行計算都隨你。

    或許不見得可以用在你的例子上,不過還是給你參考看看~

  19. Ruoshi Li
    121.15.1.*
    链接

    Ruoshi Li 2012-09-06 07:19:18

    @老赵

    嗯,下周找时间搞个简单的TPL Dataflow的实现看看,自从N年前翻译了CCR User Guide之后就再也没真正用过这个东东,可惜了

  20. 空明流转
    220.152.198.*
    链接

    空明流转 2012-09-06 08:58:17

    看来我一开始完全把老赵的意思弄错了。(哈哈,140字不够用啊)

    从工程上我同意左耳朵的观点,内存数据库是个挺理想的选择,线程安全性和效率都相对折中。

    @deerchao 的办法可以调整成标记清除的办法,只重新计算已经聚合的部分。

    如果列集是固定的话,我的想法比较原始:

    1. 一次性接受若干Changes,然后集中更新。
    2. 因为聚合索引表本身是树状结构,因此每个节点都是一个独立线程。那么需要把数据(差值或者源-目标值对)都分派到独立线程上。
    3. 在索引表固定的情况下,Avg和Sum的更新成本基本上是O(n*h) h是字段数量。
    4. 带权重的更新需要缓存下Sum(C*D)与Sum(D)。在D修改后,需要将同行的C和D均置脏,并且,Sum(C*D)和Sum(D)都能做累积计算而不是重新统计。这样它的更新成本也是O(n*h)
  21. 神仙
    114.80.133.*
    链接

    神仙 2012-09-06 09:01:19

    这样是否可行: 每个分组分配一个Actor或者goroutine之类的东西,不分级别。比如按 (A,B,C) 分组,就把这三个看成一整个元组。

    虽然每个分组还是需要保存数据,但是整个系统里就只有一份了。

  22. fantiny
    210.22.158.*
    链接

    fantiny 2012-09-06 09:48:18

    我认为老赵的思路可行,快照方式上参照 @dcaoyuan 大大的做法

  23. 老赵
    admin
    链接

    老赵 2012-09-06 10:03:08

    @deerchao 是很麻烦. 元素改成 immutable 呢?耦合当然不好,但也是设计中可以取舍的一个方面.

    假如从一开始设计起可能会搞成immutable的会让聚合容易一些,但是已有的系统是POCO/POJO的,要加上的聚合功能改动会很大……

    不过这让我想到另一个问题,用POCO/POJO的话应该是传统如.NET和Java里最常用的做法吧,这种情况下怎么再改为immutable呢?似乎问题都会比较麻烦,又涉及到创建快照了……

  24. 老赵
    admin
    链接

    老赵 2012-09-06 10:04:48

    @左耳朵耗子 我一开始在想怎么建数据结构,后面在想你要多线程,安全性怎么办?

    线程安全是要考虑的,所以我后来的设想是Erlang那样,这样对于单个聚合器来说所有的更新是串行的,可以保证线程安全,而聚合器之间就是各自独立的……

  25. 老赵
    admin
    链接

    老赵 2012-09-06 10:08:30

    @神仙: 每个分组分配一个Actor或者goroutine之类的东西,不分级别。比如按 (A,B,C) 分组,就把这三个看成一整个元组。虽然每个分组还是需要保存数据,但是整个系统里就只有一份了。

    没懂,主要是元素状态是会变动的,导致会进入不同分组,如果是在添加删除的时候决定分组之后再也不会变就好办多了,我之前也是写着写着发现元素会变动,于是计算聚合时元素状态获取不到了,只能携带元素快照。你说的分组保存数据,是指保存什么数据啊?大概是什么样的数据结构?

  26. 必填
    114.113.197.*
    链接

    必填 2012-09-06 13:56:35

    果断CouchDB啊

  27. 链接

    rex 2012-09-07 02:47:34

    根据已经写出来的需求,我的理解及设想如下:

    1,原始数据的结构

    1.1,大小是 100K rows X 100 fields X size-of-field,由独立的模块和线程管理。

    1.2,原始数据的更新是独立的,每次更新将发出更新及增减消息,消息内容有两种:1)row的新旧快照;2)field的新旧快照。两种消息都包含分组field的新旧快照。

    2,聚合器的结构

    2.1,每种聚合器有自己的class,一个(分组key + 聚合器type)有一个该聚合器的instance。

    2.2,分组key例子:A1,A1B2,A1B2C6等。

    2.3,所有聚合器的instance放在一个字典中(分组key -> instance)

    2.4,聚合器instance的state完全根据上述原始数据消息计算而得。聚合器instance之间互相独立。

    2.5,每一条原始数据消息将发送给每一个聚合器的instance,由该instance决定是否该消息与其有关,并更新state。

    3,聚合器的使用。

    3.1,在字典中,聚合器instance是独立的,但它可以被其他caller比如GUI使用。通过分组key,可以构建成tree view等不同的UI view。

    4,并发设想

    4.1,原始数据和聚合器之间肯定是并发的

    4.2,聚合器之间有多种并发可能性

    4.2.1,用Actor或Active Object(使用FastMessenger的话)来表达单个聚合器instance在productivity很合算,但性能可能不会太好,因为单个聚合器instance的计算太小了。也就是并发粒度问题。

    4.2.2,用thread / thread pool可能会是个比较折衷的方案。首先,消息全发到一个thread上,这个thread快速把字典中的聚合器instance都过一遍,得到一组有关的instance。然后根据每个instance在计算上的重量(由instance提供),以及core的数量,大概地分一分组,再把各组submit给thread pool。

  28. 链接

    rex 2012-09-07 06:31:43

    光折腾线程并不能得到更好的并发性,特别是当任务又多又小的时候。所以有几个问题要了解一下。

    1,要在机器上用单线程实际运行一下,看看一个更新所导致的所有聚合器计算到底要多少时间。我估计这么简单的计算,可能连毫秒级都达不到。

    2,有没有data integrity的要求?比如一个原始数据的更新导致了A1和A1B2的更新,如果你只显示了新的A1,A1B2还是旧的,客户有没有问题?

    3,还是和data integrity有关的并发时序问题,所有聚合器是否必须完成本次更新才能开始处理下一个原始数据的更新?

    4,聚合器的最终使用者是GUI的话,用户对更新频率有无要求?比如最多1秒2次。甚至要求提供一个按钮,可以暂停GUI的更新。

    5,如果因为某种原因聚合器和原始数据out of sync了(比如一个软件bug导致某次更新失败),有没有从原始数据重新refresh的能力?

    我在之前的post中考虑了这里的一些问题,比如message receiving thread可以控制更新频率,甚至暂停;又比如聚合器instance字典可以提供快照功能来实现data integrity;但总的来说,没有通盘考虑这里提出的问题,所以之前的设想对“到底要并发哪一部分”没有掌握得很好。

  29. 老赵
    admin
    链接

    老赵 2012-09-07 10:55:26

    @rex

    多谢,等我忙完周末的事情再仔细看啊,先回答几个问题。首先并发肯定不能折腾线程,大量小任务也没关系,反正是一个线程执行大量任务,不会切换来切换去。例如,Actor可以用TPL DataFlow来实现,线程或Task跟Block没有对应关系,不同Block之间的消息可以由同一个Task处理,只要系统是热的就行。

    此外:

    1、单次更新当然很快了,但是密集更新就占用很多CPU了。现在的实验结果是,同步方案会吃满CPU一个核,所以可以认为是CPU到达瓶颈了。

    2、客户是肉眼,延迟零点几秒看到结果问题不大,只要结果正确的就行。

    3、没有理解,现在需要实现的就是聚合器,只要结果正确,怎么处理都行。

    4、GUI不用担心,你可以认为是根据你的数据实时更新,这方面做过测试的,完全不成问题。

    5、暂时先不考虑这个吧,最多在出了问题的时候从头计算数据集咯,数据量又不大,主要是更新密集。

  30. felix
    113.111.197.*
    链接

    felix 2012-09-07 14:29:42

    测试一下头像 呵

  31. @WAYNEBABY
    114.247.10.*
    链接

    @WAYNEBABY 2012-09-07 15:53:52

    嗯 我看了下。在我理解中需求最主要的问题是 变更结果要保证自己的一次变更内不脏,至于是否几个变更在一批执行,以及输出数据是不是最新的 似乎并没有特别的要求,所以考虑做了下面这样一个设计。

    数据定义:

    *所有的元素所有的聚合值在一个瞬间的完整数据:数据镜像

    *一次操作对所有的元素和所有的聚合值产生的影响Delta:变更集合

    两种线程定义:

    *一种是变更请求线程 。

    多个线程

    除了输入变更外 还计算变更集。

    (可以考虑合并多个请求进行一次计算发起一次变更请求,只要计算成功 变更集本身不会脏。)

    *另一种是变更applier线程。该线程只有一条,计算

    两个镜像:

    *一个表示当前静态的数据镜像 只能被applier线程访问

    *一个上次完成数据镜像副本 可以被applier写入 被任何线程访问

    变更集队列:

    *线程安全队列

    运行过程大概是

    1变更请求线程

    1.1 根据一次或者多次输入计算变更集

    1.2 变更集压入变更队列

    1.3 取得已完成数据镜像副本

    1.4 复制该副本 将变更集应用于其上

    1.5 输出该复制副本

    2 Applier 线程

    2.1 从队列中取得一个变更集,

    2.2 应用在当前数据镜像上

    2.3 复制其副本

    2.4 将副本替换到已完成数据镜像副本引用上

    这个设计基本上只能利用多cpu来计算变更集。

    优点:变更集计算越复杂越有意义

    缺点:会造成每个变更集被apply 两次,及多次镜像复制 需要权衡。

    注意:

    考虑用数组储存镜像核心,用ReaderWriterClass方式操作

    可用buffer.copy来快速复制镜像

    因为镜像创建销毁可能有点频繁,可以做一个资源池。

  32. @WAYNEBABY
    114.247.10.*
    链接

    @WAYNEBABY 2012-09-07 16:27:22

    分组不一定要确定是一个集合,可能只是一个标记组名的字段的变化,所以我觉得分组变更仍可以用delta来表示啊

  33. @WAYNEBABY
    114.247.10.*
    链接

    @WAYNEBABY 2012-09-07 16:36:36

    给上面的方案打个补丁

    1变更请求线程

    1.1 取得已完成数据镜像副本并复制

    1.2 根据一次或者多次输入应用在此副本镜像

    1.3 计算变更集

    1.4 变更集压入变更队列

    1.5 输出该复制副本

  34. 祈祷幸福丶
    61.135.172.*
    链接

    祈祷幸福丶 2012-09-11 11:21:26

    其实我看不懂文章...我是来顶楼的...表示对偶像的支持...会不会删水贴呀....

  35. 老赵
    admin
    链接

    老赵 2012-09-11 20:04:56

    @祈祷幸福丶

    女神您太客气了……

  36. CodeMain
    221.3.133.*
    链接

    CodeMain 2012-09-11 22:06:57

    嗯,好复杂,没能很好的理解你的东东,看到前面的时候,我第一反应是模拟 “列式存储数据库”做聚合,SybaseIQ就是列式存储的佼佼者,看到后面的时候感觉看不懂了,呵呵,最后留个脚印,表示对你尊敬,支持一下!

  37. Ricepig
    123.116.149.*
    链接

    Ricepig 2012-09-12 02:26:23

    其实上面几位及@WAYNEBABY的总结已经很完整了

    但是是不是仅计算变更集值得商榷,需要更新数据更新的频率和统计结果所需要的刷新频率来权衡。

    若数据更新频率较快且均匀,则全部重新统计反而是比较快的选择,因为此时标记数据变更已经变成了额外的负担。

    若数据更新频率慢,或者更新的数据比较集中,则可以考虑只计算变更的数据与差额。

    如果有数据一致性的要求,则我认为需要建立数据快照,再在快照上进行统计。虽然数据或许有关联性,但是做更细粒度的处理,搞不好性能还更加烂,因为随机内存访问的性能一般是不如连续内存访问的。至于快照的建立方法,你可以考虑参照各种Cache和数据库多节点Replication的解决方法,例如redis。

  38. 链接

    martin zhang 2012-09-12 10:09:37

    技术神圣不可亵渎但是也要在老赵地盘上混个脸熟

  39. Paul Xu
    116.228.4.*
    链接

    Paul Xu 2012-09-18 17:11:54

    将数据集拆成树结构存储,每个节点上记录该节点所有下属节点的聚合后结果,当数据发生变动的时候,只需要重新计算该节点上层节点的计算结果即可,这样的话,运算量会小很多

  40. 链接

    少名谈 2012-09-21 16:41:46

    又没有想过,需求上是不是合理。真的要那么实时的计算结果吗?真的要滚动就可以看见任意的数据吗?

  41. 老赵
    admin
    链接

    老赵 2012-09-21 22:36:10

    @少名谈

    尽量实时,需要滚动就能见到任意数据。

  42. gsralex
    123.14.93.*
    链接

    gsralex 2012-09-26 20:52:28

    建立一个Action 用来表示类似编辑器软件的撤销,重复

    class Action()
    {
       //动作:Add,Update,Remove
       enum MethodType;
       //时间:操作时间
       Datetime ActionTime;
       //业务实体
       T t; // (如果t过大,可以考虑换成类似 Key,Value的形式,Key表示ChangedPropertyName,Value表示数据)
    }
    

    你说到“每秒会产生数百甚至数千次修改”,如果针对所有的操作都要显示到客户端界面上,那几乎界面变动过快,客户几乎也无法看清楚变化,需要对一些操作进行屏蔽。

    所以建立一个Stack,让所有的Action进入,每500ms进行一次处理操作,如果一个类在这次的stack加入多次修改的话,则取最后一次的修改。

    最后得到一个Stack actionStack的实例,对这个实例起多个线程来进行更新操作,这样在上一次更新操作结束之后,下一个Stack也会被处理完,保持cpu一直处于高负载,500ms可以根据具体情况进行调整。

    不知道是否可行。

  43. 老赵
    admin
    链接

    老赵 2012-09-26 21:21:24

    @gsralex: 如果t过大,可以考虑换成类似 Key,Value的形式,Key表示ChangedPropertyName,Value表示数据

    显然你这个会让T更大……

  44. jakefoley
    202.107.218.*
    链接

    jakefoley 2012-10-03 15:19:14

    最近微软新出了TypeScript呢,请问赵姐夫对这个语言有什么看法呢~3Q~

  45. jakefoley
    202.107.218.*
    链接

    jakefoley 2012-10-03 21:18:29

    PS:是C# 之父 Anders Hejlsberg带领的项目呢。。。不过这个问题跑题了呢,不好意思。。

  46. Libra
    61.153.67.*
    链接

    Libra 2012-10-22 10:13:50

    评论那么多,不知道老大能不能看到...

    其实我是来问问题的,有个问题困扰了我好几天...不知道能不能帮我解决,或者找人帮帮我..

    问题参照: Your text to link here...

    最近都没更新博客,不知道有没有在看评论/回复?

发表回复

登录 / 登录并记住我 ,登陆后便可删除或修改已发表的评论 (请注意保留评论内容)

昵称:(必填)

邮箱:(必填,仅用于Gavatar

主页:(可选)

评论内容(大于5个字符):

  1. Your Name yyyy-MM-dd HH:mm:ss

使用Live Messenger联系我