基于Redis和Lua的分布式限流

Java单机限流可以使用AtomicInteger,RateLimiter或Semaphore来实现,但是上述方案都不支持集群限流。集群限流的应用场景有两个,一个是网关,常用的方案有Nginx限流和Spring Cloud Gateway,另一个场景是与外部或者下游服务接口的交互,因为接口限制必须进行限流。
 本文的主要内容为:
  • Redis和Lua的使用场景和注意事项,比如说KEY映射的问题。
  • Spring Cloud Gateway中限流的实现。

集群限流的难点

 在上篇Guava RateLimiter的分析文章中,我们学习了令牌桶限流算法的原理,下面我们就探讨一下,如果将 RateLimiter扩展,让它支持集群限流,会遇到哪些问题。
RateLimiter会维护两个关键的参数 nextFreeTicketMicrosstoredPermits,它们分别是下一次填充时间和当前存储的令牌数。当 RateLimiteracquire函数被调用时,也就是有线程希望获取令牌时, RateLimiter会对比当前时间和 nextFreeTicketMicros,根据二者差距,刷新 storedPermits,然后再判断更新后的 storedPermits是否足够,足够则直接返回,否则需要等待直到令牌足够(Guava RateLimiter的实现比较特殊,并不是当前获取令牌的线程等待,而是下一个获取令牌的线程等待)。
 由于要支持集群限流,所以 nextFreeTicketMicrosstoredPermits这两个参数不能只存在JVM的内存中,必须有一个集中式存储的地方。而且,由于算法要先获取两个参数的值,计算后在更新两个数值,这里涉及到竞态限制,必须要处理并发问题。
 集群限流由于会面对相比单机更大的流量冲击,所以一般不会进行线程等待,而是直接进行丢弃,因为如果让拿不到令牌的线程进行睡眠,会导致大量的线程堆积,线程持有的资源也不会释放,反而容易拖垮服务器。

Redis和Lua

 分布式限流本质上是一个集群并发问题,Redis单进程单线程的特性,天然可以解决分布式集群的并发问题。所以很多分布式限流都基于Redis,比如说Spring Cloud的网关组件Gateway。
 Redis执行Lua脚本会以原子性方式进行,单线程的方式执行脚本,在执行脚本时不会再执行其他脚本或命令。并且,Redis只要开始执行Lua脚本,就会一直执行完该脚本再进行其他操作,所以Lua脚本中不能进行耗时操作。使用Lua脚本,还可以减少与Redis的交互,减少网络请求的次数。
 Redis中使用Lua脚本的场景有很多,比如说分布式锁,限流,秒杀等,总结起来,下面两种情况下可以使用Lua脚本:
  • 使用 Lua 脚本实现原子性操作的CAS,避免不同客户端先读Redis数据,经过计算后再写数据造成的并发问题。
  • 前后多次请求的结果有依赖时,使用 Lua 脚本将多个请求整合为一个请求。
 但是使用Lua脚本也有一些注意事项
  • 要保证安全性,在 Lua 脚本中不要定义自己的全局变量,以免污染 Redis内嵌的Lua环境。因为Lua脚本中你会使用一些预制的全局变量,比如说 redis.call()
  • 要注意 Lua 脚本的时间复杂度,Redis 的单线程同样会阻塞在 Lua 脚本的执行中。
  • 使用 Lua 脚本实现原子操作时,要注意如果 Lua 脚本报错,之前的命令无法回滚,这和Redis所谓的事务机制是相同的。
  • 一次发出多个 Redis 请求,但请求前后无依赖时,使用 pipeline,比 Lua 脚本方便。
  • Redis要求单个Lua脚本操作的key必须在同一个Redis节点上。解决方案可以看下文对Gateway原理的解析。

性能测试

 Redis虽然以单进程单线程模型进行操作,但是它的性能却十分优秀。总结来说,主要是因为:
  • 绝大部分请求是纯粹的内存操作
  • 采用单线程,避免了不必要的上下文切换和竞争条件
  • 内部实现采用非阻塞IO和epoll,基于epoll自己实现的简单的事件框架。epoll中的读、写、关闭、连接都转化成了事件,然后利用epoll的多路复用特性,绝不在io上浪费一点时间。
 所以,在集群限流时使用Redis和Lua的组合并不会引入过多的性能损耗。我们下面就简单的测试一下,顺便熟悉一下涉及的Redis命令。
  1. # test.lua脚本的内容
  2. local test = redis.call("get","test")
  3. local time = redis.call("get","time")
  4. redis.call("setex","test",10,"xx")
  5. redis.call("setex","time",10,"xx")
  6. return{test, time}
  7. # 将脚本导入redis,之后调用不需再传递脚本内容
  8. redis-cli -a 082203 script load "$(cat test.lua)"
  9. "b978c97518ae7c1e30f246d920f8e3c321c76907"
  10. # 使用redis-benchmark和evalsha来执行lua脚本
  11. redis-benchmark -a 082203-n 1000000 evalsha b978c97518ae7c1e30f246d920f8e3c321c76907 0
  12. ======
  13. 1000000 requests completed in20.00 seconds
  14. 50 parallel clients
  15. 3 bytes payload
  16. keep alive:1
  17. 93.54%<=1 milliseconds
  18. 99.90%<=2 milliseconds
  19. 99.97%<=3 milliseconds
  20. 99.98%<=4 milliseconds
  21. 99.99%<=5 milliseconds
  22. 100.00%<=6 milliseconds
  23. 100.00%<=7 milliseconds
  24. 100.00%<=7 milliseconds
  25. 49997.50 requests per second
 通过上述简单的测试,我们可以发现本机情况下,使用Redis执行Lua脚本的性能极其优秀,一百万次执行,99.99%在5毫秒以下。
 本来想找一下官方的性能数据,但是针对Redis + Lua的性能数据较少,只找到了几篇个人博客,感兴趣的同学可以去探索。这篇文章有Lua和zadd的性能比较(具体数据请看原文,链接缺失的话,请看文末)。
以上lua脚本的性能大概是zadd的70%-80%,但是在可接受的范围内,在生产环境可以使用。负载大概是zadd的1.5-2倍,网络流量相差不大,IO是zadd的3倍,可能是开启了AOF,执行了三次操作。

Spring Cloud Gateway的限流实现

Gateway是微服务架构 SpringCloud的网关组件,它基于Redis和Lua实现了令牌桶算法的限流功能,下面我们就来看一下它的原理和细节吧。
Gateway基于Filter模式,提供了限流过滤器 RequestRateLimiterGatewayFilterFactory。只需在其配置文件中进行配置,就可以使用。具体的配置感兴趣的同学自行学习,我们直接来看它的实现。
RequestRateLimiterGatewayFilterFactory依赖 RedisRateLimiterisAllowed函数来判断一个请求是否要被限流抛弃。
  1. publicMono<Response> isAllowed(String routeId,String id){
  2. //routeId是ip地址,id是使用KeyResolver获取的限流维度id,比如说基于uri,IP或者用户等等。
  3. Config routeConfig = loadConfiguration(routeId);
  4. // 每秒能够通过的请求数
  5. int replenishRate = routeConfig.getReplenishRate();
  6. // 最大流量
  7. int burstCapacity = routeConfig.getBurstCapacity();
  8. try{
  9. // 组装Lua脚本的KEY
  10. List<String> keys = getKeys(id);
  11. // 组装Lua脚本需要的参数,1是指一次获取一个令牌
  12. List<String> scriptArgs =Arrays.asList(replenishRate +"",
  13. burstCapacity +"",Instant.now().getEpochSecond()+"","1");
  14. // 调用Redis,tokens_left = redis.eval(SCRIPT, keys, args)
  15. Flux<List<Long>> flux =this.redisTemplate.execute(this.script, keys,
  16. scriptArgs);
  17. .....// 省略
  18. }
  19. staticList<String> getKeys(String id){
  20. String prefix ="request_rate_limiter.{"+ id;
  21. String tokenKey = prefix +"}.tokens";
  22. String timestampKey = prefix +"}.timestamp";
  23. returnArrays.asList(tokenKey, timestampKey);
  24. }
 需要注意的是 getKeys函数的prefix包含了”{id}”,这是为了解决Redis集群键值映射问题。Redis的KeySlot算法中,如果key包含{},就会使用第一个{}内部的字符串作为hash key,这样就可以保证拥有同样{}内部字符串的key就会拥有相同slot。Redis要求单个Lua脚本操作的key必须在同一个节点上,但是Cluster会将数据自动分布到不同的节点,使用这种方法就解决了上述的问题。
 然后我们来看一下Lua脚本的实现,该脚本就在Gateway项目的resource文件夹下。它就是如同 GuavaRateLimiter一样,实现了令牌桶算法,只不过不在需要进行线程休眠,而是直接返回是否能够获取。
  1. local tokens_key = KEYS[1]
  2. -- request_rate_limiter.${id}.tokens 令牌桶剩余令牌数的KEY
  3. local timestamp_key = KEYS[2]
  4. --令牌桶最后填充令牌时间的KEY
  5. local rate = tonumber(ARGV[1])
  6. -- replenishRate 令令牌桶填充平均速率
  7. local capacity = tonumber(ARGV[2])
  8. -- burstCapacity 令牌桶上限
  9. local now = tonumber(ARGV[3])
  10. --得到从1970-01-0100:00:00开始的秒数
  11. local requested = tonumber(ARGV[4])
  12. --消耗令牌数量,默认1
  13. local fill_time = capacity/rate
  14. --计算令牌桶填充满令牌需要多久时间
  15. local ttl = math.floor(fill_time*2)
  16. --*2保证时间充足
  17. local last_tokens = tonumber(redis.call("get", tokens_key))
  18. --获得令牌桶剩余令牌数
  19. if last_tokens ==nilthen
  20. --第一次时,没有数值,所以桶时满的
  21. last_tokens = capacity
  22. end
  23. local last_refreshed = tonumber(redis.call("get", timestamp_key))
  24. --令牌桶最后填充令牌时间
  25. if last_refreshed ==nilthen
  26. last_refreshed =0
  27. end
  28. local delta = math.max(0, now-last_refreshed)
  29. --获取距离上一次刷新的时间间隔
  30. local filled_tokens = math.min(capacity, last_tokens+(delta*rate))
  31. --填充令牌,计算新的令牌桶剩余令牌数填充不超过令牌桶令牌上限。
  32. local allowed = filled_tokens >= requested
  33. local new_tokens = filled_tokens
  34. local allowed_num =0
  35. if allowed then
  36. --若成功,令牌桶剩余令牌数(new_tokens)减消耗令牌数( requested ),
  37. -- 并设置获取成功( allowed_num =1)
  38. new_tokens = filled_tokens - requested
  39. allowed_num =1
  40. end
  41. --设置令牌桶剩余令牌数( new_tokens ),令牌桶最后填充令牌时间(now)
  42. -- ttl是超时时间
  43. redis.call("setex", tokens_key, ttl, new_tokens)
  44. redis.call("setex", timestamp_key, ttl, now)
  45. --返回数组结果
  46. return{ allowed_num, new_tokens }

后记

 Redis的主从异步复制机制可能丢失数据,出现限流流量计算不准确的情况,当然限流毕竟不同于分布式锁这种场景,对于结果的精确性要求不是很高,即使多流入一些流量,也不会影响太大。 正如Martin在他质疑Redis分布式锁RedLock文章中说的,Redis的数据丢弃了也无所谓时再使用Redis存储数据。
I think it’s a good fit in situations where you want to share some transient, approximate, fast-changing data between servers, and where it’s not a big deal if you occasionally lose that data for whatever reason
 接下来我们回来学习阿里开源的分布式限流组件 sentinel,希望大家持续关注。

参考

  • https://www.cnblogs.com/itrena/p/5926878.html
  • 压测的文章:https://www.fuwuqizhijia.com/redis/201704/60935.html
  • https://blog.csdn.net/forezp/article/details/85081162
  • https://blog.csdn.net/xixingzhe2/article/details/86167859
  • Matin RedLock http://martin.kleppmann.com/2016/02/08/how-to-do-distributed-locking.html
本站所有文章均由网友分享,仅用于参考学习用,请勿直接转载,如有侵权,请联系网站客服删除相关文章。若由于商用引起版权纠纷,一切责任均由使用者承担
极客文库 » 基于Redis和Lua的分布式限流

Leave a Reply

欢迎加入「极客文库」,成为原创作者从这里开始!

立即加入 了解更多