系统、服务的限流的总结和实现

<<本文待完善>>

为什么需要限流

  • 保护系统不被高并发的请求高挂
  • 针对免费提供给用户的服务进行限制,使得他们产生付费购买的欲望
  • 为了优先保护一些重要性比较高的服务,而对优先级比较低的服务进行降级处理,而限流就是其中的一种方式
  • 其他原因

限流时的一些考虑点

在设计限流功能的时候,往往都需要考虑下面的几点问题。没有标准答案,都得根据具体的业务需求场景来评估

节点限流 vs 集群限流

一般情况下来说,在线系统很少会出现单机的情况,基本都是集群系统。关于节点限流集群限流的最大区别其实就是限流操作发生的时间节点:

  • 节点限流 在请求被路由到某个确定的机器服务节点后产生的
  • 集群限流 在请求被路由之前产生的

可以看出节点限流其实就是把集群限流总数分摊到各个节点上,但是如果采用节点限流,会面临

  • 如何分摊限流这个问题,比如第一台机器10%, 第二台20%……
  • 有时候流量并不是100%的均匀到分摊到各个节点上,那么会出现限流不够精准
  • 如果后台节点扩容或者缩减容量的时候,如何去动态的更新这个分摊规则。

如果采用集群限流,那么可以很精准的对请求进行限制。常见的做法是采用redis、Memcached等工具做一个计数器。

客户端限流 vs 服务端限流

绝大多数情况下限流都是发生在服务端的,因为很多情况下客户端的数量是不确定的。但是有一些特殊的情况,为了防止单个客户端过度使用服务,那么此处可以在客户端来完成,当然在服务端也可以完成。因此一般都推荐在服务端做限流

限流的触发条件

触发条件无法就分为固定阈值和动态调整。

  • 固定阈值
    比如当服务延时大于500ms的时候,设定限流阈值为1000QPS,当然也有很多情况下使用阶梯规则:服务延时在100ms~200ms之间,设定限流阈值为10000qps,服务时延200ms~300ms之间,设定为5000qps等。
    当然这个固定阈值也可以动态更新他。

  • 动态自动增减调控
    要想达到动态自动调控限流,就需要配合监控系统以及服务治理中心来完成,但有些指标如服务延时也可以由服务节点自行计算,如服务延时。这种的实现成本相对来说比较高

被限流时的常见处理方式

  • 客户端
    • 立即返回拒绝错误码,由客户端决定如何进行后续处理
    • 短暂等待,期待有容量空余,直到超时,依然是客户端降级。
  • 服务器端
    • 服务端根据预设值的逻辑,进行低优先级的服务降级,尽可能的把资源让给高优先级的服务

限流的常用算法

令牌桶算法(Token Bucket )

令牌桶算法是网络流量整形(Traffic Shaping)和速率限制(Rate Limiting)中最常使用的一种算法。典型情况下,令牌桶算法用来控制发送到网络上的数据的数目,并允许突发数据的发送。
工作过程包括3个阶段:产生令牌消耗令牌判断数据包是否通过.
其中涉及到2个参数:令牌产生的速率r和令牌桶的大小b。下面用图形简要概括一下这3个阶段与2个参数的关系

  • 产生令牌:周期性的以r/s向令牌桶中增加令牌,桶中的令牌不断增多。如果桶中令牌数已到达b,则丢弃多余令牌。
  • 消耗令牌:输入数据包会消耗桶中的令牌。在网络传输中,数据包的大小通常不一致。大的数据包相较于小的数据包消耗的令牌要多,通常情况下每个另外对应每个数据包的最小单位。
  • 判断是否通过:输入数据包经过令牌桶后的结果包括输出的数据包和丢弃的数据包。当桶中的令牌数量可以满足数据包对令牌的需求,则将数据包输出,否则将其丢弃

从上面可以看出:令牌桶算法允许最长b个单位的突发,但从长期运行结果看,数据包的速率被限制成常量r。对于在流量限制外的数据包可以以不同的方式处理:

  • 它们可以被丢弃;
  • 它们可以排放在队列中以便当令牌桶中累积了足够多的令牌时再传输;
  • 它们可以继续发送,但需要做特殊标记,网络过载的时候将这些特殊标记的包丢弃。

leaky_bucket
tmp9787

漏桶算法(Leaky Bucket )

简单的想象有一个木桶,有新请求就是不断的倒水进来,然后桶底下有个洞,按照固定的速率把水漏走,如果水进来的速度比漏走的快,桶可能就会满了,然后就拒绝请求。
WX20170406-174010@2x

​令牌桶算法和漏桶算法的区别在哪里

两个算法起到的作用是一模一样的,两个算法的实现也可以一样,对于相同的参数得到的限流效果是一样的。从工程实现角度来说可以认为没有区别

开源的限流工具

Guava RateLimiter

Guava已实现了一个性能非常好的RateLimiter,基本不需要我们再费心实现。 RateLimiter 对简单的令牌桶算法做了一些工程上的优化,具体的实现是 SmoothBursty。需要注意的是,RateLimiter 的另一个实现 SmoothWarmingUp,就不是令牌桶了,而是漏桶算法。也许是出于简单起见,RateLimiter 中的时间窗口能且仅能为 1s,如果想搞其他时间单位的限流,只能另外造轮子。但其中有一些实现的细节,需要我们留意:

  • 支持桶外预借的突发. 突发,原本是指如果单位时间的前半段流量较少,桶里会积累一些令牌,然后支持来一波大的瞬时流量,将前面积累的令牌消耗掉。

但在RateLimiter的实现里,还多了个桶外预借(我自己给他的命名),就是即使桶里没有多少令牌,你也可以消耗一波大的,然后桶里面在时间段内都没有新令牌。比如桶的容量是5,桶里面现在只有1个令牌,如果你要拿5个令牌,也可以,清了桶里的一个令牌,再预借4个。然后再过800毫秒,桶里才会出现新令牌。
可见,Guava版的RateLimiter对突发的支持,比原版的两种算法都要大,你几乎随时都可以一次过消费burst个令牌,不管现在桶里有没有积累的令牌。
不过有个副作用,就是如果前面都没什么流量,桶里累积了5个令牌,则你其实可以一次过消费10个令牌。。。不过那么一下,超借完接下来还是固定速率的,直到还清了旧账,才可能再来那么一下。

  • 支持等待可用令牌与立刻返回两种接口
  • 单位时段是秒,这有点不太好用,不支持设定5分钟的单位。
  • 发令牌的计算粒度是MicroSeconds,也就是最多支持一百万的QPS。

小例子:

public class TrafficShaper {
    public static class RateLimitException extends Exception {
        private static final long serialVersionUID = 1L;
        private String resource;
        public String getResource() {
            return resource;
        }
        public RateLimitException(String resource) {
            super(resource + " should not be visited so frequently");
            this.resource = resource;
        }
        @Override
        public synchronized Throwable fillInStackTrace() {
            return this;
        }
    }
    private static final ConcurrentMap<String, RateLimiter>
            resourceLimiterMap = Maps.newConcurrentMap();
    public static void updateResourceQps(String resource, double qps) {
        RateLimiter limiter = resourceLimiterMap.get(resource);
        if (limiter == null) {
            limiter = RateLimiter.create(qps);
            RateLimiter putByOtherThread
                    = resourceLimiterMap.putIfAbsent(resource, limiter);
            if (putByOtherThread != null) {
                limiter = putByOtherThread;
            }
        }
        limiter.setRate(qps);
    }
    public static void removeResource(String resource) {
        resourceLimiterMap.remove(resource);
    }
    public static void enter(String resource) throws RateLimitException {
        RateLimiter limiter = resourceLimiterMap.get(resource);
        if (limiter == null) {
            return;
        }
        if (!limiter.tryAcquire()) {
            throw new RateLimitException(resource);
        }
    }
    public static void exit(String resource) {
        //do nothing when use RateLimiter
    }
}

nginx limit_conn 模块

nginx limit_req 模块

业界限流的例子

twitter API Rate Limits

页面地址:https://dev.twitter.com/rest/public/rate-limiting

github

页面地址:https://developer.github.com/v3/rate_limit/

参考资料

本文版权归作者所有,禁止一切形式的转载,复制等操作
赞赏

微信赞赏支付宝赞赏

发表评论

电子邮件地址不会被公开。 必填项已用*标注