分布式限流

经典限流算法

在介绍分布式限流之前,先介绍经典限流算法。经过笔者自己的整理,核心的算法主要可以总结为以下两类四种: A类:计数器法,滑动窗口法 B类:令牌桶法,漏桶法

这里的四种算法通常都是在应用级别讨论的,这里不重复介绍这四种算法的实现思路了,只不过我人为的将他们分成了A,B两类。

  • A类算法,否决式限流。即如果系统设定限流方案是1分钟允许100次调用,那么真实请求1分钟调用200次的话,意味着超出的100次调用,得到的是空结果或者调用频繁异常。
  • B类算法,阻塞式限流。即如果系统设定限流方案是1分钟允许100次调用,那么真实请求1分钟调用200次的话,意味着超出的100次调用,会均匀安排到下一分钟返回。(当然B类算法,也可以立即返回失败,也可以达到否决式限流的效果)

B类算法,如Guava包提供的RateLimiter,内部其实就是一个阻塞队列,达到阻塞限流的效果。然后分布式场景下,有一些思路悄悄的发生了变化。多个模块之间不能保证相互阻塞,共享的变量也不在一片内存空间。为了使用阻塞限流的算法,我们不得不将统计流量放到redis一类的共享内存中,如果操作是一系列复合的操作,我们还不能使用redis自带的CAS操作(CAS操作只能保证单个操作的原子性)或者使用中间件级别的队列来阻塞操作,显示加分布式锁的开销又是非常的巨大。最终选择放弃阻塞式限流,而在分布式场景下,仅仅使用redis+lua脚本的方式来达到分布式-否决式限流的效果。redis执行lua脚本是一个单线程的行为,所以不需要显示加锁,这可以说避免了加锁导致的线程切换开销。

锁的演变

下面记录一下这个设计的演变过程。

  • 单体式应用中显示加锁 首先还是回到单体应用中对共享变量进行+1的例子。
Integer count = 0;

    //sychronized锁
    public synchronized void synchronizedIncrement(){
        count++;
    }

    //juc中的lock
    Lock lock = new ReentrantLock();

    public void incrementByLock(){
        lock.lock();
        try{
            count++;
        }finally {
            lock.unlock();
        }

    }

用synchronized或者lock同步的方式进行统计,当单位时间内到达限定次数后否决执行。限制:单体应用下有效,分布式场景失效,显示加锁,开销大。

  • 单体式应用中CAS操作
public AtomicInteger atomicInteger = new AtomicInteger(0);

public increamt(){
    atomicInteger.incrementAndGet();
}

虽然没有显示加锁,但是CAS操作有一定的局限性,限流中不仅要对计数器进行+1,而且还要记录时间段,所以复合操作,还是无法避免加锁。

  • 分布式应用中显示加锁
RedisDistributeLock lock = new RedisDistributeLock();

public void incrementByLock(){
  lock.lock();
  try{
      count++;
  }finally {
      lock.unlock();
  }

}

分布式阻塞锁的实现,我的博客里曾经实现过,但生产中更多人自然是使用开源的分布式锁实现。虽然能达到多个模块之间的同步,但还是开销过大。不得已时才会考虑使用。

  • redis+lua脚本限流(最终方案)
local key = KEYS[1] --限流KEY(一秒一个)
local limit = tonumber(ARGV[1])        --限流大小
local current = tonumber(redis.call('get', key) or "0")
if current + 1 > limit then --如果超出限流大小
    redis.call("INCRBY", key,"1") -- 如果不需要统计真是访问量可以不加这行
    return 0
else  --请求数+1,并设置2秒过期
    redis.call("INCRBY", key,"1")
    if tonumber(ARGV[2]) > -1 then
        redis.call("expire", key,tonumber(ARGV[2])) --时间窗口最大时间后销毁键
    end
    return 1
end

lua脚本返回值比较奇怪,用java客户端接受返回值,只能使用Long,没有去深究,(学习openResty的过程中了解到lua这门动态语言的数字只有double类型)。这个脚本只需要传入key(url+时间戳/预设时间窗口大小),便可以实现限流。 这里也贴下java中配套的工具类

package sinosoftgz.apiGateway.utils;

import org.springframework.data.redis.core.RedisTemplate;
import org.springframework.data.redis.core.script.RedisScript;
import org.springframework.util.Assert;

import java.util.Arrays;

/**
 * Created by xujingfeng on 2017/3/13.
 * <p>
 * 基于redis lua脚本的线程安全的计数器限流方案
 * </p>
 */
public class RedisRateLimiter {

    /**
     * 限流访问的url
     */
    private String url;

    /**
     * 单位时间的大小,最大值为 Long.MAX_VALUE - 1,以秒为单位
     */
    final Long timeUnit;

    /**
     * 单位时间窗口内允许的访问次数
     */
    final Integer limit;

    /**
     * 需要传入一个lua script,莫名其妙redisTemplate返回值永远是个Long
     */
    private RedisScript<Long> redisScript;

    private RedisTemplate redisTemplate;

    /**
     * 配置键是否会过期,
     * true:可以用来做接口流量统计,用定时器去删除
     * false:过期自动删除
     */
    private boolean isDurable = false;

    public void setRedisScript(RedisScript<Long> redisScript) {
        this.redisScript = redisScript;
    }

    public void setRedisTemplate(RedisTemplate redisTemplate) {
        this.redisTemplate = redisTemplate;
    }

    public String getUrl() {
        return url;
    }

    public void setUrl(String url) {
        this.url = url;
    }

    public boolean isDurable() {
        return isDurable;
    }

    public void setDurable(boolean durable) {
        isDurable = durable;
    }

    public RedisRateLimiter(Integer limit, Long timeUnit) {
        this.timeUnit = timeUnit;
        Assert.isTrue(timeUnit < Long.MAX_VALUE - 1);
        this.limit = limit;
    }

    public RedisRateLimiter(Integer limit, Long timeUnit, boolean isDurable) {
        this(limit, timeUnit);
        this.isDurable = isDurable;
    }

    public boolean acquire() {
        return this.acquire(this.url);
    }

    public boolean acquire(String url) {
        StringBuffer key = new StringBuffer();
        key.append("rateLimiter").append(":")
                .append(url).append(":")
                .append(System.currentTimeMillis() / 1000 / timeUnit);
        Integer expire = limit + 1;
        String convertExpire = isDurable ? "-1" : expire.toString();
        return redisTemplate.execute(redisScript, Arrays.asList(key.toString()), limit.toString(), convertExpire).equals(1l);
    }

}

总结

一个小小的统计次数的需求,如果真想在分布式下做到最完善,还真需要花不小的精力。这篇文章原写于今年的三月份,当时我正在我老大(@钱钱)的带领下开发我们公司的网关,涉及到限流功能时做的一个调研,记录成了博客,到了如今的9月有了更深的理解,限流功能不仅可以放到应用层实现,如nginx+lua或者说是openResty都提供了限流算法,从性能和架构设计的角度来看都更加合适。但实际上掌握一门新的语言(nginx二次开发+lua),又要考虑到公司人力投入和项目规模是否需要等因素,这也是从事技术开发之外个人的一点思考,更大的一点收获便是,对于以前的想法,过一段时间再来看,会有更加深刻的认识。这或许也是我想要维护公众号和博客的初衷。

本文分享自微信公众号 - Kirito的技术分享(cnkirito),作者:徐靖峰

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2017-09-08

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 浅析项目中的并发(一)

    前言 开头扯两句,最近项目略忙,一堆零散的东西要做,没那么多时间维护文章了。又迷上了吃鸡,大雾spring security系列投入了我不少时间,但总体收获也颇...

    kirito-moe
  • JAVA拾遗--关于SPI机制

    JDK提供的SPI(Service Provider Interface)机制,可能很多人不太熟悉,因为这个机制是针对厂商或者插件的,也可以在一些框架的扩展中看...

    kirito-moe
  • JAVA 拾遗--JPA 二三事

    记得前几个月,spring4all 社区刚搞过一次技术话题讨论:如何对 JPA 或者 MyBatis 进行技术选型?传送门:http://www.spring4...

    kirito-moe
  • Sentinel的基本应用

    目标:Sentinel的基本应用 工具:IDEA--2020.1、Sentinel Maven 学习目标:学习Sentinel的限流设置 本次学习的工程下载链接...

    背雷管的小青年
  • 宜信开源|(功能上新)UAVStack服务治理之流量控制

    应用微服务化场景下,随着服务个数的增加,服务之间的相互调用变得更加复杂,服务治理需求愈加突出,其中服务流量控制是服务治理中的重要一环。

    宜信技术学院
  • Sentinel 集群限流设计原理

    为了充分利用硬件的资源,诸如 Dubbo 都提供了基于权重的负载均衡机制,例如可以将8C16G的机器设置的权重是4C8G的两倍,这样充分利用硬件资源,假如现在需...

    丁威
  • Sentinel 系统自适应限流原理剖析与实战指导

    看到标题中的几个关键字系统自适应限流是不是觉得高大上,这个自适应又是如何实现的呢?

    丁威
  • Spring Cloud 入门教程9、服务限流/API限流(Zuul+RateLimiter)

    RateLimiter是Google开源的实现了令牌桶算法的限流工具(速率限制器)。http://ifeve.com/guava-ratelimiter/

    KenTalk
  • 限流的6大狠招,附详细代码和评测结果

    为了上班方便,去年我把自己在北郊的房子租出去了,搬到了南郊,这样离我上班的地方就近了,它为我节约了很多的时间成本,我可以用它来做很多有意义的事,最起码不会因为堵...

    Java中文社群_老王
  • Spring Cloud Gateway 结合配置中心限流

    上篇文章《Spring Cloud Gateway 限流操作》我讲过复杂的限流场景可以通过扩展RedisRateLimiter来实现自己的限流策略。

    猿天地

扫码关注云+社区

领取腾讯云代金券