讨论:一则并行聚合计算方案的设计
2012-09-05 23:31 by 老赵, 6914 visits最近的工作让我想到了一个对集合的元素进行并行聚合的案例,尽管这个需求还不存在,但最近却一直在我的脑海里挥之不去,尚未得出令人满意的结果。今天下班前我将这个问题辛苦地缩减为140字内的描述发到了微博上,得到了许多同学的回复,但可能是由于描述过于简单,得到的建议似乎都不能满足我的需求。于是在此我通过博客详细描述下这个问题的需求,还有我之前做过的尝试,这样讨论起来也可以更加有针对性一些。
问题描述
现有一个集合,最多包含100K个元素。每个元素包含100个字段,为了简化问题假设这些字段都为整型,因此我们完全可以把所有数据都加载到内存中。同时,我们定义两种修改操作:
- 向集合中添加或删除一个元素。
- 修改元素中某个属性的值。
我们会有一个线程不断的将这两种修改操作运用到整个数据集中。修改是串行执行的,前一个操作完全执行结束才会开始下一个,但频率十分密集,例如每秒会产生数百甚至数千次修改,其中第2种修改的次数远多于第1种。
我们需要对集合中的元素进行聚合运算,聚合规则不超过50个,每条规则都会给定一个名称及其计算方式,例如:
- SumOfA:对集合中所有元素的A字段的值求和,即
Sum(A)
。 - AvgOfB:对集合中所有元素的B字段的值求平均,即
Avg(B)
,或Sum(A) / Count(A)
。 - 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
的所有元素的聚合结果。
这张表格显然会无比巨大,在实际情况里我们只可能显示其中的一小部分数据,但是由于用户可以随意拖动滚动条,因此事实上所有的数据都希望可以立即显示出来,并且尽量实时地显示最新数据集的聚合结果。此外,也有一些(与本问题无关的)计算需要使用完整的聚合结果,因此我们希望在内存中存在完整的结果,而不是仅仅计算“显示出的那部分数据”。
另外,实际情况下内存中可能存在多个这样的集合,集合中的元素可以共享,但每个集合都需要聚合(规则各不相同)。如果还有什么额外的条件的话,那么再假设“分组的字段”更新频率较小吧。
我的串行解决方法及并行尝试
由于实际情况下的数据量相对较小,我通过一个简单的串行的实现便可以满足性能要求。为此我实现了两个基础功能:
- 一个在添加和删除元素时可以得到通知的集合。
- 在更新元素属性时,也可以得到元素本身,被更新的属性,以及更新前后的值。
我在集合上运用聚合器,同时监听集合中每个元素的属性改变。聚合器内部保留中间状态,这样当新元素添加到集合中时,便可以利用新增或删除的元素做差值计算,由于属性修改时可以获得更新前后的值,因此差值计算同样可行。
至于分组,其实就是利用一个额外的组件,将一个集合划分为多个子集合。例如我们要对A,B,C进行分组,则先根据A进行分组得到一堆子集合,每个子集合内的元素都拥有相同的字段A的值,然后为每个子集合分别运用聚合器,这便是满足如A == 1
的所有元素的聚合结果。分组器同样会监听集合以及集合中每个元素字段的改变,维护每个子集合内的元素。例如某个元素的字段A从1被修改为2时,分组器会将这个元素从子集合1移动到子集合2中,这会触发两个子集合的变化通知,从而触发这两个集合中的聚合器更新。至于更深一级的聚合结果,则会将相同的分组策略运用到每个子集合中,只不过这次针对下一级的分组字段(例如B)即可。不断深入,直到最后一层分组。
这样无论是什么样的修改操作,每次修改完成之后都会立即更新聚合结果,且只会改动受影响的部分。但是随着数据量和更新频率的提高,我希望可以利用多核CPU来增加计算效率。这种并行运算会产生延迟,这并没有关系,只要尽量实时即可。有些同学提出在每次变动后并行计算结果,这个最容易,但实际上并不可行。因为数据随时都在更新,每次针对整个数据集进行计算会导致CPU久高不下,且并行计算的同时数据也在变动,因此计算过程中也会出现并发问题,甚至得到错误的结果。
我目前的尝试是像Erlang那样,将每个聚合器作为一个Actor来对待。元素的改变会作为消息发送至聚合器,高一级聚合器又会发送消息给低一级的聚合器(这种消息传递并不一定是直接“转发”)。这种做法会让整个系统都是“热”的,且能够自然而然地进行并发,且单个聚合器可以保持串行。但是,随之而来的问题是,由于元素属性本身在不断更新,导致我们的“延迟计算”无法在处理消息时得到当时的值,这需要我们在发送消息时携带当前元素的“快照”,这样又会带来额外的开销。元素的添加删除操作倒也罢,但假如每次在字段更新时都要携带整个快照的话,这带来开销实在太高。不过似乎我们也只需要在“分组字段”改变时携带快照即可,因为只有那时才会引起聚合器的变动(这与之前元素在子集合之间移动的性质相同)。要知道分组字段改变次数相对会少很多,因此在大部分情况里我们只需要使用字段的更新前后的值即可。
总结
欢迎各位同学给出自己的设想,描述地越详细越好,如果能给出参考实现便再好不过了。假如您对需求或是限制还有什么不明白,也请立即提出,我可以作进一步解释或是更新文章。我也会继续尝试和探索,希望最后能给出一个完整的示例程序。
好复杂。。。