负载均衡 on 子恒的博客

[后台]负载均衡（三）限流篇

Mon, 27 Jul 2020 17:28:37 +0800

限流

限流能力是高并发系统中，对于服务提供方的一种保护手段。通过限流功能，我们可以通过控制QPS的方式，以避免被瞬时的流量高峰冲垮，从而保障系统的高可用性。

考虑的问题

完成一个限流系统，我们可以结合场景的需要做下面的考虑

多规则匹配：是否会存在有多重规则的限流？比如有的规则限制每天1000次，有的规则限制每分钟1次？是同时生效还是优先生效某个？
资源类型：能限流什么？QPS，连接数，并发数
全局限流/单机限流：多个服务的实例共享一个全局的流量限额，比如所有机器共享1000QPS。或者单个实例的限流，比如被调限定每台机器不超过1000QPS
限流阈值：单位时间内的最大配额数。是按照每秒种一次，还是按照每分钟60次？
限流处理：客户端如何处理超出限额的请求？超额后直接拒绝，还是超额后进行排队？

抽象出一个方案
接口级别限流：每个接口分配一个appid和key，各自计算各自的配额
多维度限流：支持每秒N次、每分钟N次、每天N次等维度
匀速防刷：假设配置了每分钟60次，依然可能出现第一秒访问了60次用光了配额。匀速防刷可以匀速消耗配额，解决这个问题
多级限流：支持不同的限流规则，并有采用的优先级，采用优先级最高的方案进行限流

限流算法

固定窗口

固定窗口是在一段时间内可以限制访问次数的方法。

将时间划分为多个窗口
在每个窗口内每有一次请求就将计数器加一
如果计数器超过了限制数量,则本窗口内所有的请求都被丢弃。当时间到达下一个窗口时,计数器重置

这样有一定的限流效果，但是限制住的流量可能是有毛刺的。比如1000次/分钟，可能00:59的时候有1000流量，01:00的时候也有1000流量，这样这两秒内就有2000流量！
具体实现：用一个变量C标记访问次数，一个事件定时过期，并在过期时把变量C清零：

type FixedWindowCounter struct {
	TimeSlice  time.Duration
	NowCount   int32
	AllowCount int32
}

func (p *FixedWindowCounter) Take() bool {
	once.Do(func() {
		go func() {
			for {
				select {
				case <-time.After(p.TimeSlice):
					atomic.StoreInt32(&p.NowCount, 0)
				}
			}
		}()
	})

	nowCount := atomic.LoadInt32(&p.NowCount)
	if nowCount >= p.AllowCount {
		return false
	}
	if !atomic.CompareAndSwapInt32(&p.NowCount, nowCount, nowCount+1) {
		return false
	}
	return true
}

滑动窗口

滑动窗口把一个固定窗口划分为多个小区间，以固定的窗口大小在区间上滑动，在一定程度上缓解了固定窗口的毛刺问题（我们假设某一区间qps非常高）。当然性能损耗也比较大。

[后台]负载均衡（二）能力篇

Thu, 21 May 2020 17:18:55 +0800

名字服务

基础设计

名字服务考虑的基本设计

客户端发现：
服务提供者的实例在启动时或者位置信息发生变化时会向服务注册表注册自身，在停止时会向服务注册表注销自身，如果服务提供者的实例发生故障，在一段时间内不发送心跳之后，也会被服务注册表注销。
服务消费者的实例会向服务注册表查询服务提供者的位置信息，然后通过这些位置信息直接向服务提供者发起请求。

服务端发现：
第一步与客户端发现相同。
服务消费者不直接向服务注册表查询，也不直接向服务提供者发起请求，而是将对服务提供者的请求发往一个中央路由器或者负载均衡器，中央路由器或者负载均衡器查询服务注册表获取服务提供者的位置信息，并将请求转发给服务提供者。

这两种模式各有利弊，客户端发现模式的优势是，服务消费者向服务提供者发起请求时比服务端发现模式少了一次网络跳转，劣势是服务消费者需要内置特定的服务发现客户端和服务发现逻辑；
服务端发现模式的优势是服务消费者无需内置特定的服务发现客户端和服务发现逻辑，劣势是多了一次网络跳转，并且需要基础设施环境提供中央路由机制或者负载均衡机制。目前客户端发现模式应用的多一些，因为这种模式的对基础设施环境没有特殊的要求，和基础设施环境也没有过多的耦合性。
主调调用被调时，根据被调的名字从服务注册中心获取服务实例列表，包括节点ip、端口、权重、地理位置等；一般采取分钟级别的定时任务去拉取，本地做缓存，异步更新。

实现方式

DNS，传播速度太慢，没法发现端口。SkyDNS解决了这个问题，在k8s里大量使用
zookeeper或者etcd，如SmartStack，能保证强一致，但是要做很多开发
Eureka。Netflix的java生态里的优秀方案
Consul，提供服务配置、服务的内存和磁盘监测等

服务注册信息

IP和端口

一个服务端要接入名字服务，必须要先提供自己的IP和端口信息。
IP的获取方法：

通过遍历网卡的方式去获取，找到第一个不为本地环回地址的 IP 地址。dubbo就是这种方法
指定网卡名interfaceName，来获取IP
直接与服务注册中心建立 socket 连接，然后通过socket.getLocalAddress() 这种方式来获取本机的 IP
端口的获取方法：
一般的RPC服务或者Web服务监听的端口都在配置中写好，可以直接获取上报。

扩展设计

除了IP和端口，可能还有一些常用的服务信息需要注册上来，提供更高级的功能：
1.支持TLS：想知道某个 HTTP 服务是否开启了 TLS。
2.权重：对相同服务下的不同节点设置不同的权重，进行流量调度。
3.环境分配：将服务分成预发环境和生产环境，方便进行AB Test功能。
4.机房：不同机房的服务注册时加上机房的标签，以实现同机房优先的路由规则。

无损注册/下线

虽然服务注册一般发生在服务的启动阶段，但是细分的话，服务注册应该在服务已经完全启动成功，并准备对外提供服务之后才能进行注册。
1.有些 RPC 框架自身提供了方法来判断服务是否已经启动完成，如 Thrift ，我们可以通过 Server.isServing() 来判断。
2.有一些 RPC 框架本身没有提供服务是否启动完成的方式，这时我们可以通过检测端口是否已经处于监听状态来判断。
3.而对于 HTTP 服务，服务是否启动完毕也可以通过端口是否处于监听状态来判断。
下线也是一样的，可以注册服务下线的回调，或者监听服务下线的信号，或者做健康检查

健康检查

客户端主动心跳上报健康：

客户端每隔一定时间主动发送“心跳”的方式来向服务端表明自己的服务状态正常，心跳可以是 TCP 的形式，也可以是 HTTP 的形式。
也可以通过维持客户端和服务端的一个 socket 长连接自己实现一个客户端心跳的方式。
客户端的健康检查只能表明网络可达，不能代表服务可用。服务端的健康检查可以准确获得服务的健康状态：
服务端调用服务发布者某个 HTTP 接口来完成健康检查。
对于没有提供 HTTP 服务的 RPC 应用，服务端调用服务发布者的接口来完成健康检查。
可以通过执行某个脚本的形式来进行综合检查，覆盖多个场景。
服务端检查也有问题，一个是调用服务的方式不通用，需要额外实现，还有就是服务注册中心可能和服务的网络不互通。

节点变化通知

当服务有节点退出或新的节点加入时，订阅者如何及时收到通知？经典的push和pull的问题

[后台]负载均衡（一）算法篇

Wed, 06 May 2020 20:24:30 +0800

当单机的访问压力很大时，就需要引入集群。集群一个很重要的事情就是把请求均匀地分配在各个机器上，这就是负载均衡的雏形。
有基于MAC地址的二层负载均衡和基于IP地址的三层负载均衡。二层负载均衡会通过一个虚拟MAC地址接收请求，然后再分配到真实的MAC地址；三层负载均衡会通过一个虚拟IP地址接收请求，然后再分配到真实的IP地址；
四层通过虚拟IP+端口接收请求，然后再分配到真实的服务器（比如LVS，F5）；七层通过虚拟的URL或主机名接收请求，然后再分配到真实的服务器（Haproxy和Nginx）。
四层和七层是最常见的负载均衡模型。

**四层：**以常见的TCP为例，负载均衡设备在接收到第一个来自客户端的SYN请求时，通过负载均衡算法选择服务器，并对报文中目标IP地址进行修改（改为后端服务器IP），直接转发给该服务器。TCP的连接建立，即三次握手是客户端和服务器直接建立的，负载均衡设备只是起到一个类似路由器的转发动作。在某些部署情况下，为保证服务器回包可以正确返回给负载均衡设备，在转发报文的同时可能还会对报文原来的源地址进行修改。
**七层：**以常见的TCP为例，负载均衡设备如果要根据真正的应用层内容再选择服务器，只能先代理最终的服务器和客户端建立连接(三次握手)后，才可能接受到客户端发送的真正应用层内容的报文，然后再根据该报文中的特定字段，再加上设置的负载均衡算法，选择内部某台服务器。负载均衡设备在这种情况下，更类似于一个代理服务器。负载均衡和前端的客户端以及后端的服务器会分别建立TCP连接。所以从这个技术原理上来看，七层负载均衡明显的对负载均衡设备的要求更高，处理七层的能力也必然会低于四层模式的部署方式。
参考资料：四层和七层负载均衡的区别

nginx用的负载均衡算法

Nginx可以作为HTTP反向代理，把访问本机的HTTP请求，均分到后端集群的若干台服务器上。负载均衡的核心就是负载均衡所使用的平衡算法，适用于各种场景。
Nginx的负载均衡算法
Nginx目前提供的负载均衡模块：
ngx_http_upstream_round_robin，加权轮询，可均分请求，是默认的HTTP负载均衡算法，集成在框架中。
ngx_http_upstream_ip_hash_module，IP哈希，可保持会话。
ngx_http_upstream_least_conn_module，最少连接数，可均分连接。适用于链接数体现资源的服务，比如FTP。
ngx_http_upstream_hash_module，一致性哈希，可减少缓存数据的失效。

随机访问

在介绍nginx的模式前，先介绍下普通的负载均衡方法。假设有7个请求，我们给A、B、C三个节点分别4、2、1的权重。最朴素的负载均衡方式有下面几种：

完全轮询：访问完A去访问B，访问完B去访问C，再去访问A。缺点是没有权重，不能根据负载调节。
列表轮询：构造一个数组[A, A, A, A, B, B, C]，每次pop出去一个访问。缺点是pop出去的元素太随机，可能一次集中访问A ，而且占用内存太大，对于几万的权重范围不合适。
随机数：我们按照A、B、C的权重划分好区间，A（0、1、2、3），B（4、5），C（6），然后取一个随机数，模余7，看看最后的结果在哪个区间内，就取哪个节点。缺点是完全随机，无法避免集中访问。

加权轮询

假设有7个请求，我们给A、B、C三个节点分别4、2、1的权重。如果随机按照概率来选，那么很可能出现连续四个请求都在A上面的情况，这样只能保证结果看起来均衡，但是时间段内不均衡。Nginx采用了一种平滑的加权平均算法来选取节点（Weighted Round Robin）。
先引入三个概念，都用来描述服务器节点的权重：

$W$ : weight 我们指定的权重，就是上面例子中的4、2、1。
$W_{ew}$: effective_weight 有效权重，初始值为$W$。用来对故障节点降权。
如果通信中有错误产生，就减小effective_weight。（故障降权）
此后有新的请求过来时，再逐步增加effective_weight，最终又恢复到weight。（自动恢复）
$W_{cw}$ : current_weight 当前真实权重，每次都会选到最大的真实权重的节点去请求

真实权重$W_{cw}$计算方式：

初始化：$W_{cw}$ 起始值为0
获得实时权重：请求到来后，给每个节点的真实权重加上有效权重，即$每个节点 W_{cw} = W_{cw} + W_{ew}$
选出最大权重：选择真实权重最大的节点最为本次请求的目标
回避刚选的节点：最选择的节点的实时权重减去所有节点（包括自己）的有效权重和。即$选中节点 W_{cw} = W_{cw} - (W_{ew1} + W_{ew2} + … + W_{ewn})$

来看一个具体的例子：
假设A、B、C三个节点的权重分别为4、2、1。

请求序号	请求后的current_weight	选择的节点	选择后的current_weight
未请求	{0,0,0}	/	/
1	{4,2,1}	A	{-3,2,1}
2	{1,4,2}	B	{1,-3,2}
3	{5,-1,3}	A	{-2,-1,3}
4	{2,1,4}	C	{2,1,-3}
5	{6,3,-2}	A	{-1,3,-2}
6	{3,5,-1}	B	{3,-2,-1}
7	{7,0,0}	A	{0,0,0}
三个结论：每个节点被选中的次数是符合权重的；A没有被连续选取；七次之后权重会归零，是一个循环。

static ngx_http_upstream_rr_peer_t *ngx_http_upstream_get_peer(ngx_http_upstream_rr_peer_data_t *rrp)
{
    time_t                        now;
    uintptr_t                     m;
    ngx_int_t                     total;
    ngx_uint_t                    i, n, p;
    ngx_http_upstream_rr_peer_t  *peer, *best;

    now = ngx_time();
    best = NULL;
    total = 0;
    ...

    /* 遍历集群中的所有后端 */
    for (peer = rrp->peers->peer, i = 0;
         peer;
         peer = peer->next, i++)
    {

        n = i / (8 * sizeof(uintptr_t));
        m = (uintptr_t) 1 << i % (8 * sizeof(uintptr_t));

        /* 检查该后端服务器在位图中对应的位，为1时表示不可用 */
        if (rrp->tried[n] & m)
            continue;
       
        /* 永久不可用的标志 */
        if (peer->down) 
            continue;
        
       /* 在一段时间内，如果此后端服务器的失败次数，超过了允许的最大值，那么不允许使用此后端了 */
       if (peer->max_fails
            && peer->fails >= peer->max_fails
            && now - peer->checked <= peer->fail_timeout)
            continue;
        
        peer->current_weight += peer->effective_weight; /* 对每个后端，增加其当前权重 */
        total += peer->effective_weight; /* 累加所有后端的有效权重 */

        /* 如果之前此后端发生了失败，会减小其effective_weight来降低它的权重。          
         * 此后在选取后端的过程中，又通过增加其effective_weight来恢复它的权重。          
         */        
        if (peer->effective_weight < peer->weight) 
            peer->effective_weight++;
        
        /* 选取当前权重最大者，作为本次选定的后端 */
        if (best == NULL || peer->current_weight > best->current_weight) {
            best = peer;
            p = i;
        }
    }

    if (best == NULL) /* 没有可用的后端 */
        return NULL;
    
    rrp->current = best; /* 保存本次选定的后端 */

    n = p / (8 * sizeof(uintptr_t));
    m = (uintptr_t) 1 << p % (8 * sizeof(uintptr_t));

    /* 对于本次请求，如果之后需要再次选取后端，不能再选取这个后端了 */    
    rrp->tried[n] |= m;

    best->current_weight -= total; /* 选定后端后，需要降低其当前权重 */  
    /* 更新checked时间 */
    if (now - best->checked > best->fail_timeout)
        best->checked = now;
    
    return best;
}

ip_hash

ip_hash是基于客户端IP的哈希值来选择服务器。同一个客户端的请求，都会发往同一台后端，除非该后端不可用了。ip_hash能够达到保持会话的效果。
和随机加权哈希一样，ip哈希借鉴了权重分段的思想，先算出哈希值, 然后模余total_weight，得到初始权重W [0, total_weight)，开始遍历节点。如果哈希值小于当前节点的权重，就选择当前节点；如果哈希值大于等于当前节点的权重，就减去当前节点的权重，再去尝试下个节点。我们还是讨论A，B，C三个节点的情况，假设权重分别为2、4、1 。
权重的和是7，那么哈希值应该是0~6 （因为模了哈希值）
6的情况：6 >= 2 , 所以不选A，减去2。 6-2 >= 4，所以不选B，减去4。2-4 < 1，所以选C
5的情况：5 >= 2 , 所以不选A，减去2。 5-2 < 4，所以选B
4的情况：4 >= 2 , 所以不选A，减去2。 4-2 < 4，所以选B 。哈希值为3、2的情况也一样。
1、0的情况：1 < 2，所以选A
可以看到最后四个选B，两个选A，一个选C，还是均衡的。