Druid的Coordinator负载均衡原理

「爱情、让人受尽委屈。」 2022-07-13 06:26 184阅读 0赞

此方法在 [Druid 0.9.1.1 release][]版本中已上线。

segment是druid的工作单元。当执行一个query的时候，每个segment被分配给一个core，各个segment并行计算。query的查询范围从几小时到几周不等，对每个查询，我们想最大限度的使用CPU cores。因此，对每一个给定的时间段，我们要把data放在尽可能多的server上，即跨多个服务器分散数据。

Druid coordinator节点负责分发各个segment，考虑数据的复制策略，把realtime的数据移动到historical。

## Coordinator均衡原理 ##

### 1. 原始方法 ###

1）随机选取一个有足够空间的node，把segment放入即可。不适用于集群的动态扩展，最新数据区成为访问热点。

2）node按剩余空间排序，选择剩余空间最大的node放入segment。

### 2. 均衡算法 ###

#### 目标 ####

避免热点，把segment放在尽可能多的server上，最大化并行计算；查找segment大小对CPU占有率的影响。

#### 解决方案 ####

定义成本函数cost(x,y)，segment x在server Sk上的成本： TotalCost ( x , S k )= ∑ y ∈ S k ∖ \{  x \} cost ( x , y )

对每一个新的segment，coordinator计算它在每一个server上的cost，然后把segment放在成本最小的server上。为了平衡集群，druid用贪心再平衡策略，随机选取一个segment，将其放在成本最小的server上。

#### 核心问题 ####

cost函数的选取。现有的选取方案用了多种启发方案，如segment大小、segment间隔间的“距离”由segments覆盖的时间间隔决定。这种以来，较大的segment需要更多的CPU时间来扫描，在时间间隔上“近”的segments大多同时被查询。

#### 结果 ####

work fine，查询速度为常量；但问题是不同server间差别很小，算法改进的可能性很小。

### 3. 改进cost函数 ###

#### cost函数缺点 ####

太多参数，有“扭结”和“高原”，导致有时看到的是局部集群。

#### 目标 ####

（1）cost函数应该反映扫描segment的成本；

（2）同时扫描多个segments时的成本；

（3）cost函数应具有可加性  segments  A ,  B , and  C ,  cost ( A , B ∪ C )= cost ( A , B )+ cost ( A , C )（保证在数据分片时，cost函数具有独立性，不论是一个覆盖一天的segment，还是24个segments每个覆盖1h，cost一致）

#### 解决方案 ####

解决问题1 ：假定扫描一个时间单位的data时间一定，为常量；cost函数只依赖于segment间隔；

解决问题2：用指数衰减相互作用函数 ![image2016-8-29_2018_3A49_3A0.png_version_1_modificationDate_1472468028000_api_v2][]来表示查询两个时间片的成本，t表示两个时间片的相对时间差， λ表示相互作用衰减的速率。这个函数调控相互作用，减少了当时间差增大时二者的相互作用成本。

two segments  X  and  Y  covering intervals  X =\[ x 0 , x 1 )  and  Y =\[ y 0 , y 1 )，

![image2016-8-29_2018_3A49_3A58.png_version_1_modificationDate_1472468023000_api_v2][]

由于每一个segment都在一个data source上，接下来考虑X和Y是否在同一个data source上的情况。

![image2016-8-29_2018_3A51_3A36.png_version_1_modificationDate_1472468019000_api_v2][]

#### 结果 ####

query速度提升30-40%。

[Druid 0.9.1.1 release]: https://github.com/druid-io/druid/releases/tag/druid-0.9.1.1
[image2016-8-29_2018_3A49_3A0.png_version_1_modificationDate_1472468028000_api_v2]: http://wiki.intra.xiaojukeji.com/download/thumbnails/77570519/image2016-8-29%2018%3A49%3A0.png?version=1&modificationDate=1472468028000&api=v2
[image2016-8-29_2018_3A49_3A58.png_version_1_modificationDate_1472468023000_api_v2]: http://wiki.intra.xiaojukeji.com/download/attachments/77570519/image2016-8-29%2018%3A49%3A58.png?version=1&modificationDate=1472468023000&api=v2
[image2016-8-29_2018_3A51_3A36.png_version_1_modificationDate_1472468019000_api_v2]: http://wiki.intra.xiaojukeji.com/download/attachments/77570519/image2016-8-29%2018%3A51%3A36.png?version=1&modificationDate=1472468019000&api=v2