loop_in_codes

低调做技术__欢迎移步我的独立博客 codemaro.com 微博 kevinlynx

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

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

Round-robin

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

curId = ++curId % nodeCnt

随机选择

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

id = random(nodeCnt);

本机优先

访问后台服务的访问者可能本身是一个整合服务,或者是一个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();
}

本机房优先

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

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

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

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后重新开始。这样可以让权重更大的节点被选择得更多。

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;
}

参考一致性 hash 算法(consistent hashing)Consistent Hash Ring

posted on 2014-08-26 00:11 Kevin Lynx 阅读(3945) 评论(0)  编辑 收藏 引用 所属分类: network


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理