Token bucket算法是流量控制里的经典算法,根据wiki(https://en.wikipedia.org/wiki/Token_bucket) 上的记载,其算法主要分为以下四个步骤:
- 每1/r秒,一个token加入到bucket中
- 一个bucket最多拥有b个token,如果当一个token在加入bucket时,bucket是满的,抛弃这个token
- 当n个字节到达时,从bucket里取出n个token并继续传递这n个字节
- 当bucket里不够n个token时,这n个字节是超出了流量限制的
根据上面的描述,把n个字节换成1个query,就可以看作是qps的控制算法,代码地址:https://github.com/boully/boully/blob/master/boully/TokenBucket.h
为了保证算法的效率,这里使用了原子变量来表示bucket中的token的个数,并使用无锁的原子操作来实现上述算法中判断流量是否需要控制的过程,为了达到更高的效率,牺牲了精确的并发控制,但能达到相同控制qps的效果。
网友评论