一些基本的负载平衡算法

以下算法，一般都只考虑节点负载的平衡，不考虑cache命中以及session维护

Round Robin / Random （weighted allowed）

  • 特点
    • 每个接受请求的概率相同（与权值正比）
    • simple
    • state
      • fixed weight = stateless
      • dynamic weight = 依赖权值计算的具体方法（可以根据连接数、响应时间、吞吐、内存、CPU等决定权值）
  • 场景
    • 每个处理节点性能差不多
    • 期望低延迟路由，计算量小

Chained Failover

  • 节点成链条，每次只有当前节点无法接受更多时，选择链条的下一个节点。
  • 可以和主从备份相结合

基于某个资源最小的节点

  • 共性： 有状态，需要节点个数
    • 无中心化
      • sender 去pull receiver的节点负载
      • receivwe 去 push 负载到 sender
    • 中心化
      • 由中心监控节点负责路由和连接记录
    • 可以弱加权： 连接数差不多时，选权值高的

Least Connection 最小连接（active task）数

  • 特点
    • 优先发送给当前连接数最少的节点
    • 往往需要对每个节点设置最大连接数
  • 场景
    • 每个连接（任务）开销差不多

The Least Response Time Method

  • 特点
    • 优先发送给最近响应时间内少的节点
  • 场景
    • 用于WAN下就近选择服务器，不适合LAN下极低响应的环境

The Least Bandwidth(Throughput) Method

  • 特点
    • 优先发送给最近一段时间内使用带宽最少的节点

The Least Packets method

  • 特点
    • 优先发送给最近一段时间内传输包最少的节点

一致性Hash - Memcached采用

本质：用DHT(distributed hash table）管理键值，原本的目的是在P2P网络中快速定位资源，但是也常用来做负载均衡

普通的Hash负载平衡

  • 根据key(比如IP)对节点个数取模
  • 优: 机器不变动时，缓存友好和便于维护session
  • 缺点：机器变动时，导致IP和节点的映射变化，缓存命中率下降，IO增加

优雅地处理节点动态增减

  • 目的: 为了使得原来的IP与节点映射关系变化尽量少
  • 方法：对 $2^{32}-1$ 取模，得到hash环。 每个请求直接路由到顺时针下的那个节点。 插入和删除节点就是在环上增减点
  • 减少： C节点宕机, 对象C从节点C变为D
  • 增加： 增加D节点，对象C从节点C变为D， 一般是随机分配

几种维护节点的方法

  • 链表：快改慢查， 每个节点记录前一个节点和后一个节点的位置信息
    • 根据key查找节点： O(N) , N为节点数量
    • 增删节点 ： O(1)

  • 幂次逼近，Chord系统采用： 每个节点都要维护一个大小为N（可以更小）的finger table。

    • 查找节点： O(logN)
    • 增删节点： O(logN)， 可以只更新一个节点的finger table
    • 容错：为防止某节点之后连续的节点失效，导致新加入的节点未加入，所以对于每个节点需要额外维护一个长度为r的后续节点表，比如r=1/2，只要不是连续有一半机器失效，就可以正常工作。

  • 虚拟节点：Dynamo系统

    • 去中心化，可以从任意一个节点请求，也可以从负载均衡器开始

    • 一个实际物理节点对应多个虚拟节点

      • 负载高的节点 减少虚拟节点
      • 负载低的节点 增加虚拟节点

    • 冗余容错：NWR策略

      只要满足W+R > N（即W和R读取的数据必有重叠），就可以保证当存在不超过一台机器故障的时候，至少能读到一份有效的数据。如果应用重视读效率，可以设置W=N，R=1; 如果应用需要在读/写之间权衡，一般可设置成N=3, W=2, R=2。Dynamo推荐使用322的组合。
      N：同一份数据备份的份数
      W：是更新一个数据对象的时候需要确保成功更新的份数
      R：读取一个数据需要读取的最少节点（备份）的份数

    • 数据版本管理： vector clock

      • 只保证eventual consistency，写请求可以写更新所有节点前返回，这个时候get就可能得到旧版数据。
      • 一旦数据之间发生了冲突不会丢失，但是可能会有已被删除的数据重新出现
      • 这就会导致版本会出现分支，因为修改一个keyvalue时候，并不会阻塞，分支无法自动解决，需要人为定义merge方法。

    • 传播节点增删协议： Gossip

      • 不断传播信息到接触到的最多的节点。

如何达到负载均衡

问题

  • 极端情况下的hash冲突
  • 多节点管理维护成本还是较高的。
  • DHT使得key变成散列，适合随机访问，如果存在顺序访问操作，还是B系列树结构比较合适

Hash槽 - redis采用

  • 目的：为了避免高额的管理成本

  • 取消了虚拟节点，每个物理节点管理一块连续的hash区域。

  • 删除节点和增加节点方法和一致性hash一样

  • 负载均衡方式改为调整槽的大小，而不是增加、减少虚拟节点个数

  • 图示：一个 Redis Cluster包含16384（0~16383）个哈希槽，存储在Redis Cluster中的所有键都会被映射到这些slot中，集群中的每个键都属于这16384个哈希槽中的一个，集群使用公式slot=CRC16（key）/16384来计算key属于哪个槽

Reference