分布式环境中的负载均衡策略

蔚落 2022-08-10 06:20 160阅读 0赞

**分布式环境中的负载均衡策略**

**转载于：http://codemacro.com/2014/08/25/lb-policy/**

在分布式系统中相同的服务常常会部署很多台，每一台被称为一个服务节点（实例）。通过一些负载均衡策略将服务请求均匀地分布到各个节点，以实现整个系统支撑海量请求的需求。本文描述一些简单的负载均衡策略。

1.   Round-robin

简单地轮询。记录一个选择位置，每次请求来时调整该位置到下一个节点  ：

curId = ++curId % nodeCnt

2.  随机选择

随机地在所有节点中选择：

id = random(nodeCnt);

`3.本机选择`

访问后台服务的访问者可能本身是一个整合服务，或者是一个proxy，如果后台服务节点恰好有节点部署在本机的，则可以优先使用。在未找到本机节点时则可以继续走Round-robin策略：

if (node->ip() == local_ip) {
        return node;
    } else {
        return roundRobin();
    }

一旦遍历到本机节点，则后面的请求会一直落到本机节点。所以这里可以加上一些权重机制，仅是保证本机节点会被优先选择，但不会被一直选择。例如：

// initial
    cur_weight = 100;
    ...
    // select node
    cur_weight -= 5;
    if (cur_weight <= 0)
        cur_weight = 100;
    if (cur_weight > 50 && node->ip() == local_ip) {
        return node;
    } else {
        return roundRobin();
    }

`4. 本机房优先`

服务节点可能会被部署到多个机房，有时候确实是需要考虑跨机房服务。同`本机优先`策略类似，本机房优先则是优先考虑位于相同机房内的服务节点。该请求是从哪个机房中的前端服务发送过来的，则需要前端在请求参数中携带上机房ID。

在服务节点对应的数据结构中，也最好按照机房来组织。

本机房优先策略实际上会作为节点选择的第一道工序，它可以把非本机房的节点先过滤掉，然后再传入后面的各种节点选择策略。这里还可以考虑节点数参数，如果本机房的节点过少，则可以不使用该策略，避免流量严重不均。

`5. weighted Round-Robin`

`加权轮询。相对于普通轮询而言，该策略中每一个节点都有自己的权重，优先选择权重更大的节点。权重可以根据机器性能预先配置。摘抄一下网上的算法：`

假设有一组服务器S = {S0, S1, …, Sn-1}，W(Si)表示服务器Si的权值，一个
    指示变量i表示上一次选择的服务器，指示变量cw表示当前调度的权值，max(S)
    表示集合S中所有服务器的最大权值，gcd(S)表示集合S中所有服务器权值的最大
    公约数。变量i初始化为-1，cw初始化为零。
    
    while (true) {
      i = (i + 1) mod n;
      if (i == 0) {
         cw = cw - gcd(S); 
         if (cw <= 0) {
           cw = max(S);
           if (cw == 0)
             return NULL;
         }
      } 
      if (W(Si) >= cw) 
        return Si;
    }

遍历完所有节点后权重衰减，衰减到0后重新开始。这样可以让权重更大的节点被选择得更多。

`6. Consistent Hash`

一致性哈希。一致性哈希用于在分布式环境中，分布在各个节点上的请求，不会因为新增节点（扩容）或减少节点（节点宕机）而变化。如果每个服务节点上都有自己的缓存，其保存了该节点响应请求时的回应。正常情况下，这些缓存都可以很好地被运用，也即cache命中率较高。

如果某个节点不可用了，我们的选择策略又是基于所有节点的公平选择，那么原来一直分配在节点A上请求就很可能被分配到节点B上，从而导致节点A上的缓存较难被命中。这个时候就可以运用一致性哈希来解决。

其基本思想是，在节点选择区间内，在找节点时以顺时针方向找到不小于该请求对应的哈希值的节点。在这个区间里增加很多虚拟节点，每一个虚拟节点相当于一个物理节点的引用，这样相当于把物理节点变成了一个哈希值区间。这个哈希值区间不会因为增加节点和减少节点而变化，那么对某个请求而言，它就会始终落到这个区间里，也就会始终被分配到原来的节点。

至于这个不可用的节点，其上的请求也会被均匀地分配到其他节点中。

摘抄网上的一段代码：

// 添加一个物理节点时，会随之增加很多虚拟节点
    template <class Node, class Data, class Hash>
    size_t HashRing<Node, Data, Hash>::AddNode(const Node& node)
    {
        size_t hash;
        std::string nodestr = Stringify(node);
        for (unsigned int r = 0; r < replicas_; r++) {
            hash = hash_((nodestr + Stringify(r)).c_str());
            ring_[hash] = node;  // 物理节点和虚拟节点都保存在一个std::map中
        }
        return hash;
    }
    
    // 选择data对应的节点，data可以是请求
    template <class Node, class Data, class Hash>
    const Node& HashRing<Node, Data, Hash>::GetNode(const Data& data) const
    {
        if (ring_.empty()) {
            throw EmptyRingException();
        }
        size_t hash = hash_(Stringify(data).c_str()); // 对请求进行哈希
        typename NodeMap::const_iterator it;
        // Look for the first node >= hash
        it = ring_.lower_bound(hash); // 找到第一个不小于请求哈希的节点
        if (it == ring_.end()) {
            // Wrapped around; get the first node
            it = ring_.begin();
        }
        return it->second;