Token-Bucket

上周解决的bug（其实并不能算是bug，是因为量太大导致的OOM）用到了令牌桶，简单在此记录一下。

关于令牌桶，最早接触的时候还是实习的时候用到的tc，这货限流就是用的令牌桶，简单地说，就是有一个桶，这个桶中有一些令牌，每进来一个包，就拿走一个令牌，当一定时间内（比如说，一秒）令牌被拿完了，那接下来的包就被丢弃了，因为他们没有拿到令牌；等到下一个时间周期，桶中再次被填满令牌，然后包来了再拿。

更详尽的参考：限流:漏桶算法和令牌桶算法 其中也有wikipedia的链接。

关于实现，github上搜到的golang的实现有这几个：

(P.S 还有我的hhh token bucket)

大体思路有这几个：

  1. 使用lock+对比时间
  2. 使用原子操作+对比时间
  3. 使用原子操作+后台填桶（tikcer）

令牌桶其实很简单，就看怎样实现性能最好。

使用lock去拿token（看桶里还有没有token），然后再对比一下上次填桶的时间和取token的时间，就可以判断这个token能不能取到，这种实现的弊处在于lock的引入在数据量很大的情况下带来了不必要的lock和unlock，引起性能的下降。

所以就引出了第二种方案，使用原子操作来取代lock，性能有很大的提升。对比测试在下文中有代码。

可能会有人问，为什么要用对比时间的方式呢，后台用一个ticker定时填满不就行了。这也是我一开始想到的，但实际操作中却出现了问题，不知道是我姿势不对还是什么，测出的效果很差，怀疑是ticker没有定时执行，CPU没能调度到它上，没有来得及重置bucket。

然后就到了最后一种方式，后台填桶。这是最直白的，开一个goroutine每隔一段时间更新bucket中的token数量。但是，理论上在高并发的情况下，CPU繁忙，go出去的ticker容易失效（goroutine没能得到CPU资源），但实际情况却。。。大大超出我的想想，这种方法竟然是效率最高的！！！

对比测试：token-bucket-test.go

2018/01/13 18:05:17 5s test
2018/01/13 18:05:22 bsm:  5.000064716
2018/01/13 18:05:22 take: 6000
2018/01/13 18:05:22 drop: 54533531
2018/01/13 18:05:22 
2018/01/13 18:05:28 wrfly:  5.000066249
2018/01/13 18:05:28 take: 4977
2018/01/13 18:05:28 drop: 57039560
2018/01/13 18:05:28 
2018/01/13 18:05:34 tb:  5.000073633
2018/01/13 18:05:34 take: 6000
2018/01/13 18:05:34 drop: 113551687
2018/01/13 18:05:34 
2018/01/13 18:05:35 range test:  100000000
2018/01/13 18:05:35 dry run:  0.176605558
2018/01/13 18:05:35 
2018/01/13 18:05:40 bsm:  5.501930454
2018/01/13 18:05:40 take: 6501
2018/01/13 18:05:40 drop: 99993499
2018/01/13 18:05:40 
2018/01/13 18:05:45 wrfly:  4.907704798
2018/01/13 18:05:45 take: 4896
2018/01/13 18:05:45 drop: 99995104
2018/01/13 18:05:45 
2018/01/13 18:05:46 tb:  0.299582854
2018/01/13 18:05:46 take: 1000
2018/01/13 18:05:46 drop: 99999000
2018/01/13 18:05:46

回头要看一下是什么原因导致ticker的方式竟然没毛病了，在繁忙的情况下，可能是我测试的方法不对，没能达到很多CPU占用的效果。

但是在CPU资源充足的时候，用这种方法是绝对没问题的。

comments powered by Disqus