Pegasus Balancer

[levy5307]

https://levy5307.github.io/blog/pegasus-balancer/

背景介绍

在当前pegasus balancer的实现中，meta server会定期对所有replica server节点的replica情况做评估，当其认为replica在节点分布不均衡时，会将相应replica进行迁移。

在balancer生成决策过程中需要考虑的因素有：

对于任意表，其partition在节点上的分布要均衡，这其中包括如下几个方面：

  某个partition的三个副本不能全部落在一个节点上
  primary的数量要均摊
  secondary的数量也要均摊

如果发现primary分配不均衡时，首先考虑的策略应该是对primary进行角色切换，而不是直接就进行数据拷贝
不仅要考虑节点间的负载均衡，也要尽量保证节点内各个磁盘的replica个数是均衡的

魔改Ford-Fulkerson

上面讲到，当primary分布不均衡时，首先考虑的策略是对进行角色切换，也就是说，需要寻找到一条从路径，将primary从“多方”迁移到“少方”。将迁移的primary数量作为流量，很自然的我们就想到了Ford-Fulkerson，即：

寻找一条从source到sink的增广路径
按照增广路径修改各边权重，形成残差网络
在残差网络中继续步骤1，直到找不到增广路径为止。

但是我们又不能直接套用Ford-Fulkerson。原因在于第2步中，按照Ford-Fulkerson，增广路上的一条权重为x的边意味着从A流向B的primary的个数为x，此时形成残差网络中，该边的权重需要减去x，然而其反向边也同时增加x（反向边的作用用于提供一个调整的机会，因为之前形成的增广路径很有可能不是最大流，该反向边用于调整此前形成的增广路径，具体参考Ford-Fulkerson算法）。但是在我们的模型中，反向边增加x是不合理的，例如，对于Partition[Primary: A, Secondary: (B, C)]，Primary从A向B流动，最终使得Partition成为[Primary: B, Secondary: (A, C)]，这时意味着：

A到B的流量减少
A到C的流量减少
B到A的流量增加
B到C的流量增加

这显然与Ford-Fulkerson的残差网络的反向边的权重变化是不同的。
所以我们将算法修改如下：

按照当前的partition分布生成图结构，并根据Ford-Fulkerson算法，找到一条增广路径
根据找到的增广路径，构造primary角色切换的决策动作。并在集群中执行该动作，生成新的partition分布
3.根据新的partition分布，迭代步骤1，一直到不能找到增广路径
从上面可以看出，该算法主要是对第2步进行了修改，并非像Ford-Fulkerson算法那样简单的进行边权重修改。

NOTE：我们在执行Ford-Fulkerson进行primary迁移的时候，是针对单个表的，也就是说构造网络、执行角色切换都是针对单个表的，当要对多个表进行迁移，则只要循环对所有表各执行上述流程就可以了。

当然，有可能我们执行完上述算法后，集群负载仍然不平衡，此时说明通过primary切换已经无法达到集群平衡了，那么接下来就必须要进行primary迁移了(即背景介绍中讲到的进行数据拷贝)。
同样，在执行完primary迁移后，也要对secondary进行迁移。但是secondary迁移就不用像primary这么复杂还要考虑角色切换了（因为在做primary迁移时能切换的已经切换过了），此时直接进行数据拷贝就可以了。
下面我们分别对这几个点进行详细讲解。

Primary负载均衡
Primary角色切换是Pegasus balancer整体逻辑的核心部分，先看一下这一块是如何实现的。

构造Ford-Fulkerson图

根据上文所述，primary角色切换采用的是改进Ford-Fulkerson来实现的，Ford-Fulkerson执行的第一步就是要构造partition分布图，其构造方式如下：

记N为某个表partition的数目，M为replica server节点数目
图中增加两个点source和sink，分别代表源点和汇点
如果某个节点A上primary的数目x >= N/M, 则从source到A添加一条有向边，边的权重为x - N/M，表示可以从该节点向外流出x - N/M个primary；反之，如果节点B上的primary数目y < N/M，则添加一条B到sink的有向边，其权重为N/M - y，表示可以向B流入N/M - y个primary
如果节点A上有一个primary，其对应的secondary在结点B上，则为A->B的有向边的权重+1

上图所示为在3 replica server集群上，一个7分片表的图情况：

由于N=8, M=3，则N/M = 2
由于只有节点B上的primary数量>2，则源点只指向B，其权重为B节点上的primary数量 - N/M = 6 - 2 = 4；其他节点则指向汇点t，其权重均为1
节点B上有6个primary其相应的secondary在C和D上，所以B->C和B->D上权重等于6。同理可以得出D->B, C->D, D->C的权重均为1

获取增广路径

另外，为了减少primary切换的数量，我们在寻找最大流时，需要寻找到最小费用最大流的增广路径，也就是说：

获取最大的流
在保证获取了最大流的前提下，选择费用最小的那条路径

为了达到这个目的，我们采用了dijstra算法来查找增广路经，以获取费用最小的路径。这里粘贴上代码，并加上必要的注释以帮助理解
void shortest_path(std::vector &visit,
std::vector &flow,
std::vector &prev,
std::vector<std::vector> &network)
{
int pos, max_value;
flow[0] = INT_MAX;

int graph_nodes = network.size();
while (!visit[graph_nodes - 1]) {
    pos = -1, max_value = 0;
    for (int i = 0; i != graph_nodes; ++i) {
	    // 在这里获取最大的流，用于满足1
        if (visit[i] == false && flow[i] > max_value) {
            pos = i;
            max_value = flow[i];
        }
    }

    if (pos == -1)
        break;

    visit[pos] = true;
    for (int i = 0; i != graph_nodes; ++i) {
	    // 这里的条件主要用于满足2，也就是说，已经获取了最大流了，保证当前选择的路径是最小费用的路径
        if (!visit[i] && std::min(flow[pos], network[pos][i]) > flow[i]) {
            flow[i] = std::min(flow[pos], network[pos][i]);
            prev[i] = pos;
        }
    }
}

}

primary角色切换

当获取到增广路径之后，接下来的工作则是按照获取到的路径进行primary角色切换了。在了解具体算法前，先看一下几个变量与结构的定义：

typedef std::map<std::string, int> disk_load: 表示磁盘负载，其key是disk tag，value则是该磁盘上的primary/partition count
std::vector prev: 表示该增广路径，prev[i]表示该路径上节点i的前置节点

算法具体执行步骤如下：

依次遍历增广路径中的每个节点(current)，并获取其在增广路径上的相邻节点(prev)
获取current和prev两个节点的磁盘负载(disk_load *current_load和disk_load *prev_load)
对prev中的每一个primary，查找其在current中是否有相应的secondary，如果有的话，则将该primary放入到potential_moving中，表示有可能move的primary
通过增广路径，可以获取到从prev应该move多少个primary到current上(plan_moving)
对于potential_moving中的所有的primary，选择plan_moving个磁盘负载差最大的primary(prev中primary所在的磁盘的负载 - current中相应的secondary所载磁盘的负载)，将选择出来的这些primary进行角色切换。这样选择的优点是不仅可以优化节点间的负载，同时还可以兼顾到磁盘的负载

copy primary

当没有成功获取增广路径时，则说明简单通过角色切换的方式已经无法达到负载均衡了，必须通过迁移primary来实现了。
迁移primary算法的实现相对简单，其具体执行步骤如下：

将节点按照primary数量按从小到大排序，得到pri_queue
对pri_queue上，id_min从左到右，id_max从右到左移动，如下图所示:
+------+------+------+------+------+------+------+------+
| |
V V
id_min --> <--id_max

对当前id_max上的所有primary，分别找到其对应的磁盘并获取其磁盘负载，选择负载最大的磁盘及其对应的primary，进行迁移
依次将id_min和id_max进行移动，重复上述步骤。直到id_min节点上的primary数量 >= N/M

NOTE： 上述构建图、查找增广路径、move primary和copy primary步骤都是针对一个表进行的操作，对于集群上的多个表，都要执行一次上述步骤。

secondary负载均衡
上述讲解了primary负载均衡，当然secondary也同样需要负载均衡，否则的话可能会出现不同节点上primary均衡，但是partition总数不均衡的情况。
因为在做primary迁移时已经做过角色切换了，secondary迁移就不用像primary这么复杂，不用考虑角色切换的问题了。此时直接进行copy就可以。因此secondary的负载均衡，直接采用copy primary一样的算法实现，这里不再赘述。
同理，secondary也要对所有表分别进行负载均衡。

Conlusion
当然对所有表执行完上述步骤也只是查找了一次增广路径而已，我们知道对于最大流问题，可能要查找多个增广路径。所以我们需要根据执行后集群是否处于load balance的状态来判断是否还要继续查找增广路径。

[Smityz]

点赞！