讨论：一则并行聚合计算方案的设计
2012-09-05 23:31 by 老赵, 6912 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来对待。元素的改变会作为消息发送至聚合器，高一级聚合器又会发送消息给低一级的聚合器（这种消息传递并不一定是直接“转发”）。这种做法会让整个系统都是“热”的，且能够自然而然地进行并发，且单个聚合器可以保持串行。但是，随之而来的问题是，由于元素属性本身在不断更新，导致我们的“延迟计算”无法在处理消息时得到当时的值，这需要我们在发送消息时携带当前元素的“快照”，这样又会带来额外的开销。元素的添加删除操作倒也罢，但假如每次在字段更新时都要携带整个快照的话，这带来开销实在太高。不过似乎我们也只需要在“分组字段”改变时携带快照即可，因为只有那时才会引起聚合器的变动（这与之前元素在子集合之间移动的性质相同）。要知道分组字段改变次数相对会少很多，因此在大部分情况里我们只需要使用字段的更新前后的值即可。
总结
欢迎各位同学给出自己的设想，描述地越详细越好，如果能给出参考实现便再好不过了。假如您对需求或是限制还有什么不明白，也请立即提出，我可以作进一步解释或是更新文章。我也会继续尝试和探索，希望最后能给出一个完整的示例程序。
好复杂。。。