代币桶算法的原理与实现

    令牌桶算法是经典的网络限流算法，它可以限制带宽，使流量以一个较为均匀的速度向外发送。我们可以把令牌桶算法想象成一个有固定容量的桶，每个数据包都要经过这个桶处理。如果当前数据包的大小 大于 桶内的令牌数，则放行该数据包，否则丢掉该数据包，或者延时发送。

 一、先来看几个名词解释：

1.令牌数：可以把令牌数理解为字节数或者比特数。

2.桶的容量：就是允许的最大突发信息传输速率，即允许的最大瞬时带宽。

3.带宽：单位时间内能够在线路上传送的数据量，常用的单位是bps(bit per second)。

二、性质：（假设：限制带宽为20kbps）

1.令牌桶的容量是固定的，令牌桶中可以保存的最大令牌数永远不会超过桶的大小。

2.令牌桶处理数据包会消耗令牌桶内的令牌，消耗的令牌数.等于数据包的大小。

3.令牌桶以恒定的速率产生令牌，速率大小就是限制的带宽，即，v = 20kbps。

三、代码实现

#include <iostream>
#include <atomic> 
#include <ctime>
#include <time.h>


class TokenBucket {
	typedef enum color{
		GREEN,
		RED
	}COLOR;
private :
	int m_cir; // 添加令牌的速率
	int m_cbs; // 桶的容量

	std::atomic<int64_t> m_clsLastUpdateTime; // 上次桶内令牌数更新时间
	std::atomic<int64_t> m_clsCurTokenNum; // 当前桶内令牌数

	// 毫秒级时间，不够用可以自己重写
	int64_t _get_cur_time() {
		return clock();
	}

public:
	TokenBucket(int cir, int cbs) {
		m_cir = cir;
		m_cbs = cbs;
		m_clsLastUpdateTime = _get_cur_time();
	}

	~TokenBucket() {}

	/************************ 
	  数据包处理函数
	  参数：token, 数据包大小
	  返回值：RED, 惩罚处理
		     GREED, 放行
	************************/
	COLOR packetProcess(int token) {
		int64_t nowTime;
		int64_t timeInterval;
		int64_t updateTokenNum;
		int64_t curTokenNum = m_clsCurTokenNum.load();
		if (token <= curTokenNum) {
			m_clsCurTokenNum.fetch_sub(token);
			return GREEN;
		}
		nowTime = _get_cur_time();
		timeInterval = nowTime - m_clsLastUpdateTime.load();
		updateTokenNum = timeInterval * m_cir + curTokenNum;
		if (updateTokenNum < token) {
			return RED;
		}
		else {
			updateTokenBucket(nowTime, updateTokenNum);
		}
		m_clsCurTokenNum.fetch_sub(token);
        return GREEN;
	}

	/************************ 
	  更新令牌桶内的时间以及数量
	  参数：time, 更新时间
		    num, 数量
	  返回值：void
	************************/
	void updateTokenBucket(int64_t time, int64_t num) {
		m_clsLastUpdateTime.store(time);
		m_clsCurTokenNum.store(num);
	}
};