令牌桶算法理解学习（限流算法）

令牌桶算法是网络流量整形（Traffic Shaping）和速率限制（Rate Limiting）中最常使用的一种算法。典型情况下，令牌桶算法用来控制发送到网络上的数据的数目，并允许突发数据的发送。

用简单的话语来说就是限制流量，将其控制到某一平均值稳定输出，并可以在短时间内应对高额流量（短时高速率流量）的一种方法。

需要注意的是，限速只是让他尽可能速率一致，是存在速率不稳定的情况的，只有在长期来看速率才是恒定的，而当令牌桶应对突发流量时会进行令牌桶内令牌的小号，理论上的峰值速率=令牌桶的容量+恒定速率，举个例子，令牌桶的容量 为100MB，限制的速率为10MB/s，峰值速率则可以达到100+10=110MB/s。

?

?b为桶的容量，r为单位时间内放入的令牌数量，以下图为例：

在r=10，b=5时，即表明每1/r=0.1，每0.1秒投入一个令牌，而在到0.5秒时达到桶的极限容量5，在此刻继续投入令牌则无法维持，这些令牌将会被废弃，同时在此时若有5个指令同时想要去走令牌则可以同时取走令牌桶内的所有令牌，即为取走b=5个。

注意：

1. 当b>1时（桶的大小大于1个令牌时），任意1/r秒内最多可以取走b个令牌；
2. 而当b=1时（桶的大小就是1），每秒钟最多可以被取走r个令牌。

综上，令牌桶算法的总体流程大致分为如下三步：

1. 将令牌放入桶内：按照固定的速率放入令牌桶内，例如r=10，20，100等；
2. 获取令牌：任意请求只有在取得可用令牌才会被接收处理；
3. 令牌桶已满：当桶内令牌已满时，新加入的令牌会被丢弃或者拒绝接收。

与网络带宽分配相结合，可在一定程度上减少资源的浪费，同时可以根据不同优先级的业务来进行基于令牌桶的带宽分配改进方式，针对不同优先级的业务设定不同的业务权值，以此来自适应业务速率的变化，可通过业务权值的占用比例进行动态分配令牌资源，利用令牌桶嵌入漏桶机制实现对业务占用的带宽进行二次分配,根据业务优先级的高低对溢出的令牌实现依次填充,从而减少资源浪费。（源自论文：基于动态令牌桶的卫星网络带宽分配方法）

卫星网络模型：一个GEO卫星，若干地面终端和网络控制中心NCC（Network Control Center）组成，地面终端则是经由SG（Satallite Gateway）连接到Internet网络。通过网络控制中心NCC来进行处理各个SG发来的带宽申请和分配新的贷款，上行链路由各个SG提供，下行链路则是数据流共享的信道。

GEO卫星网络?

令牌桶方法实现：令牌桶的填充速率R，令牌桶容量S（令牌桶所能容纳的最大令牌数），令牌桶的当前状态为x，表示当前对应令牌桶的深度，工作流程如下图：

工作流程上，GEO卫星上的带宽资源被定义为n个令牌桶，当有业务传达到时，NCC处理由SG为每个业务发送的带宽请求并为其分配带宽，哥哥令牌桶为每个业务分配基本保证带宽，即为R1,R2,R3......Rn。调整R1,R2,R3......Rn的大小可以设定各个业务的保证带宽，需要注意，各个令牌桶的尺寸小于链路的信道容量，各个业务到达相应令牌桶后，根据数据包长度与令牌桶内数量来进行分配，若数据包长度小于令牌数，业务传送出去，令牌桶内令牌相应减少。而高优先级的业务将会优先进行放入。而由于令牌桶间仙姑独立，令牌桶无法动态借用空闲令牌，即空闲带宽无法进行有效利用，且令牌桶在填充过程中，令牌个数不会大于令牌桶容量，溢出令牌会丢失，也进一步造成了带宽资源的浪费。

改进方法：将漏桶嵌入到令牌桶中,即每一个令牌桶连接一个漏桶,有几个优先级就有几个令牌桶。这样可以保证优先级为n的最小带宽,溢出桶用来存储溢出的令牌,借用令牌桶的动态带宽分配算法（Dynamic Bandwidth Allocation Algorithm with Token Bucket,DBAATB），原理下图：

?代码实现：

acquire获取令牌的操作中，使用锁保护数据正确性，使用条件等待令牌足够才继续往下执行。

bool CountSemaphore::acquire(unsigned long long count)
{
    std::unique_lock<std::mutex> lck(m_mtx);
    if (count > m_maxCount)
    {
        return false;
    }
    m_cv.wait(lck, [&]() -> bool { return m_updateCount >= count; });
    m_updateCount -= count;
    return true;
}

release增加令牌数量，并通知其他等待条件的线程继续执行。

void CountSemaphore::release(unsigned long long count){
    std::unique_lock<std::mutex> lck(m_mtx);
    auto tobeCount = m_updateCount + count;
    if (tobeCount > m_maxCount){
        m_updateCount = m_maxCount;
    }
    else{
        m_updateCount = tobeCount;
    }
    m_cv.notify_all();
}

TokenSpeedLimiter是令牌桶的封装。包含令牌桶的限速速度，令牌的投递时间间隔和令牌桶的容量。提供开始和结束投递操作和获取令牌的操作。

void TokenSpeedLimiter::workingThread()
{
    auto lastTime = std::chrono::steady_clock::now();
    while (m_runing)
    {
        // 延时定时投递
        std::this_thread::sleep_for(std::chrono::milliseconds(m_deliveryIntervalMs));
        // 计算投递时间差
        auto curTime = std::chrono::steady_clock::now();
        auto elapsedMs = std::chrono::duration<double, std::milli>(curTime - lastTime).count();
        lastTime = curTime;
        // 根据时间差计算投递令牌的数量(除以1000换算成毫秒投递数量，然后再乘以毫秒时间差)
        auto tokens = m_limitSpeed * elapsedMs / 1000;
        // 投递令牌
        m_semaphore.release((unsigned long long)tokens);
    }
}