流控算法探讨——之计数器模型原理及实现

c/c++

浏览数:151

2019-3-28

AD:资源代下载服务

流控模型

概述

即流量控制,有的地方叫做”限流算法”。对于一个系统来说,受限于资源(CPU、内存、带宽、I/O等等因素)其处理能力是有限的,一旦客户的流量超过这个限制,往往会引来灾难性的后果。因此各种“限流算法”应运而生。比较简单的有以下几种模型

  • 计数器模型
  • 漏斗模型
  • 令牌桶模型

受限于本人的知识和眼界,目前只了解这三种模型,如果今后学习到更多的模型,会补上。

打算分三篇文章来分别探讨这几种模型的原理及其C++实现。本文是第一篇。

计数器算法

先介算法原理、接口,最后实现一个可用基于计数器的限流器。

原理

我认为这是最“简单粗暴的方法”,使用一个累加器来记录请求次数(即流量),然后按照规定的时间间隔来检查累加器的数值。这个模型可以采用“单线程”、“多线程”、“定时器”等多种多样的手段来实现。
该模型优点是实现起来简单,缺点也很明显:功能太弱、性能不高、不平滑。

接口设计

接口设计

计数器模型的实现

无锁的单线程实现

基于C++11标准

#ifndef RATE_LIMIT_H
#define RATE_LIMIT_H

#include <atomic>
#include <chrono>

class RateLimit
{
private:
    // uncopyable
    RateLimit(RateLimit&&) = delete;
    RateLimit(const RateLimit&) = delete;
    const RateLimit& operator=(const RateLimit&) = delete;

public:
    ///< rate: counter per second
    ///< timeWindow: second(s)
    RateLimit(uint64_t rate, uint64_t timeWindow)
        : m_rate(rate)
        , m_timeWindow(timeWindow * 1000 * 1000)
    {}

    bool Consume()
    {
        const uint64_t now = std::chrono::duration_cast<std::chrono::microseconds>(std::chrono::steady_clock::now().time_since_epoch()).count();
        if (m_time + m_timeWindow <= now)
        {
            m_time = now;
            m_count = 1;
            return true;
        }
        const auto count = m_count.fetch_add(1);
        return (count < m_rate);
    }

private:
    std::atomic<uint64_t> m_time = { 0 }; // the start timepoint of the window
    std::atomic<uint64_t> m_count = { 0 }; // count in one window
    const std::atomic<uint64_t> m_rate {0};
    const std::atomic<uint64_t> m_timeWindow {0}; // micro seconds
};
#endif