精确掌控并发：滑动时间窗口算法在分布式环境下并发流量控制的设计与实现

这是《百图解码支付系统设计与实现》专栏系列文章中的第（15）篇，也是流量控制系列的第（2）篇。点击上方关注，深入了解支付系统的方方面面。

上一篇介绍了固定时间窗口算法在支付渠道限流的应用以及使用redis实现的核心代码。

本篇重点讲清楚滑动时间窗口算法原理和应用场景，以及使用reids实现的核心代码。

1. 滑动时间窗口原理

滑动窗口算法是一种更为灵活的流量控制方案，它比固定窗口算法能更平滑地处理突发流量。在滑动窗口中，时间窗口是重叠的，这意味着流量的计算是基于过去的一段连续时间内发生的事件。

精确掌控并发：滑动时间窗口算法在分布式环境下并发流量控制的设计与实现-LMLPHP

工作流程：

窗口定义：确定窗口的大小，例如1秒钟，并设置窗口的滑动间隔，比如100毫秒。
计数与滑动：每个窗口都有自己的计数器。当一个新请求到达时，增加当前时间窗口及其前面相邻的窗口的计数。
限制检查：如果任何连续时间段内的请求总数超过阈值，则拒绝新的请求。
窗口更新：随着时间的推移，不断向前滑动窗口，并更新相应的计数器。

2. 滑动时间窗口在支付系统中的应用场景

滑动时间窗口在支付系统中的应用场景主要也是各种精确限流，比如把前一篇讲的固定时间窗口算法中，我们对外部渠道请求会做限流，那么就可以升级到滑动时间窗口，以提高精度。

只要是API限流，都可以使用。

3. 使用redis实现的核心代码

滑动窗口可以通过队列或循环数组来实现。每个窗口对应队列中的一个元素，记录该窗口期间的请求数。当时间滑动时，更新队列头部的元素，并可能将旧的元素出队。

在Redis中，可以使用列表或有序集合来模拟这种滑动窗口。下面是一个Rdis实现的示例，使用有序集合（sorted set）来实现了滑动时间窗口算法：

/**
 * redis限流操作类
 */
@Component
public class RedisLimitUtil {
    @Autowired
    private RedisTemplate<String, Object> redisTemplate;
    // 滑动时间窗口大小
    private static final long WINDOW_SIZE_IN_SECONDS = 1000;

    /**
     * 判断是否限流
     * 这里不考虑超过long最大值的情况，系统在达到long最大值前就奔溃了。
     */
    public boolean isLimited(String key, String reuqestId, long countLimit) {
		// 使用Redis的多个命令来实现滑动窗口
        redisTemplate.zremrangeByScore(key, 0, currentTimeMillis - WINDOW_SIZE_IN_SECONDS);
        long count = redisTemplate.zcard(key);

        if (countLimit >= count) {
            redisTemplate.zadd(key, currentTimeMillis, reuqestId);
            return true;
        } else {
            return false;
        }
    }
}

每个请求都以其发生的时间戳作为分数(SCORE)存储在集合中。通过移除旧于当前时间窗口的请求来维护滑动窗口。通过检查集合中的元素数量，以确定是否超过了设定的最大请求数。

zremrangeByScore 用于移除窗口之外的旧请求。
zcard 获取当前窗口内的请求数量。
zadd 将新请求添加到集合中。

使用：PayServiceImpl

/**
 * 支付服务示例
 */
public class PayServiceImpl implements PayService {
    @Autowired
    private RedisLimitUtil redisLimitUtil;

    @Override
    public PayOrder pay(PayRequest request) {
        if (isLimited(request)) {
            throw new RequestLimitedException(buildExceptionMessage(request));
        }

        // 其它业务处理
        ... ...
    }

    /*
     * 限流判断
     */
    private boolean isLimited(PayRequest request) {
        // 限流KEY，这里以[业务类型 + 渠道]举例
        String key = request.getBizType() + request.getChannel();
        // 限流值
        Long countLimit = countLimitMap.get(key);

        // 如果key对应的限流值没有配置，或配置为-1，说明不限流
        if (null == countLimit || -1 == countLimit) {
            return false;
        }

        return redisLimitUtil.isLimited(key, request.getRequestId(), countLimit);
    }
}

需要注意一点的是，这次需要传入requestId进去，用于保存这个requestId在redis有序队列里的分数，用于计数和清理。

其它的注释写得比较清楚，没什么补充的。

4. 注意事项

一些分布式服务框架，为了更高的可靠性，他们使用的是本地计算。比如接口限流1000TPS，一共有20台应用服务器，框架就会把计算出每台机器是50个TPS，下发给所有的应用服务器，在服务器上线、下线过程中，可能会有一段时间是不准确的。

但在渠道限流应该中，因为每个渠道的流量都不太高，所以可以使用这种redis方案。且精度更高，不受应用服务器的上、下线影响。

另外，在分布式系统中，需要确保不同节点之间的时间同步，以保证流量计算的准确性。如果应用服务器之间的时间不同步，那么流量就会计算错误。

5. 结束语

分布式流控有很多实现方案，通过把固定时间窗口算法升级为滑动时间窗口算法，我们对流量控制的精度会大幅提升。

下一篇会介绍漏桶原理及实现。漏桶和令牌桶的特点是请求进来先保存起来，然后按一定的速度发送出，而不是超过阀值就拒绝。

6. 传送门

支付系统设计与实现是一个专业性非常强的领域，里面涉及到的很多设计思路和理论也可以应用到其它行业的软件设计中，比如幂等性，加解密，领域设计思想，状态机设计等。

在《百图解码支付系统设计与实现》的知识宇宙，每一篇深入浅出的文章都是一颗既独立但又彼此强关联的星球，有必要提供一个传送门以便让大家即刻到达想要了解的文章。

专栏地址：百图解码支付系统设计与实现
领域相关：
支付行业黑话：支付系统必知术语一网打尽
 跟着图走，学支付：在线支付系统设计的图解教程
 支付交易的三重奏：收单、结算与拒付在支付系统中的协奏曲
 在线支付系统的精英搭档：深入剖析收银核心与支付引擎的协同作战（一）
在线支付系统的精英搭档：深入剖析收银核心与支付引擎的协同作战（二）

技术专题：
交易流水号的艺术：掌握支付系统的业务ID生成指南
 揭密支付安全：为什么你的交易无法被篡改
 金融密语：揭秘支付系统的加解密艺术
 支付系统日志设计完全指南：构建高效监控和问题排查体系的关键基石
 避免重复扣款：分布式支付系统的幂等性原理与实践
 支付系统的心脏：简洁而精妙的状态机设计与核心代码实现
 精确掌控并发：分布式环境下并发流量控制的设计与实现（一）
精确掌控并发：分布式环境下并发流量控制的设计与实现（二）
金融疆界：在线支付系统渠道网关的创新设计（一）

隐墨_SC