限制每个时间段的事件数

Question

我需要封顶事件的数量ñ在一段时间内允许的DeltaT.我能想到的任何方法,空间都是O(m),其中m是每个deltaT发送的最大事件请求数,或者是O(deltaT/r),其中r是可接受的分辨率.

编辑:deltaT是相对于时间戳的滑动时间窗口.

例如:保留事件时间戳的循环缓冲区.事件裁剪所有早于t-deltaT的时间戳.如果时间戳数超过n,则拒绝事件.将时间戳添加到缓冲区.

或者,初始化一个大小为deltaT/r的整数的循环桶缓冲区,该时间段相对于具有分辨率r的电流的时间索引.保持指针i.在事件中,自上次事件除以r后的时间增加i.将原始i和新原始i之间的缓冲区归零.增加我.拒绝,如果bugger的总和超过n.

什么是更好的方式？

---

我刚刚在c#中实现了我的第二个建议,固定deltaT为1 s,固定分辨率为10 ms.

public class EventCap
{
    private const int RES = 10; //resolution in ms

    private int _max;
    private readonly int[] _tsBuffer;
    private int p = 0;
    private DateTime? _lastEventTime;
    private int _length = 1000 / RES;

    public EventCap(int max)
    {
        _max = max;

        _tsBuffer = new int[_length];
    }

    public EventCap()
    {
    }

    public bool Request(DateTime timeStamp)
    {
        if (_max <= 0)
            return true;

        if (!_lastEventTime.HasValue)
        {
            _lastEventTime = timeStamp;
            _tsBuffer[0] = 1;
            return true;
        }

        //A
        //Mutually redundant with B
        if (timeStamp - _lastEventTime >= TimeSpan.FromSeconds(1))
        {
            _lastEventTime = timeStamp;
            Array.Clear(_tsBuffer, 0, _length);
            _tsBuffer[0] = 1;
            p = 0;
            return true;
        }

        var newP = (timeStamp - _lastEventTime.Value).Milliseconds / RES + p;

        if (newP < _length)
            Array.Clear(_tsBuffer, p + 1, newP - p);

        else if (newP > p + _length)
        {
            //B
            //Mutually redundant with A
            Array.Clear(_tsBuffer, 0, _length);
        }
        else
        {
            Array.Clear(_tsBuffer, p + 1, _length - p - 1);
            Array.Clear(_tsBuffer, 0, newP % _length);
        }

        p = newP % _length;
        _tsBuffer[p]++;
        _lastEventTime = timeStamp;

        var sum = _tsBuffer.Sum();

        return sum <= 10;
    }
}

Answer 1

那么有这些变量:num_events_allowed,time_before,time_now,time_passed

在初始时你会做: time_before = system.timer(), num_events_allowed = n

收到活动后,您可以执行以下操作:

  time_now = system.timer()
  time_passed = time_now - time_before
  time_before = time_now

  num_events_allowed += time_passed * (n / deltaT);

  if num_events_allowed > n 
      num_events_allowed = n

  if num_events_allowed >= 1
      let event through, num_events_allowed -= 1
  else
      ignore event

关于这个算法的好处是num_events_allowed实际上增加了自上次事件以来已经过去的时间以及可以接收事件的速率,这样你就可以按顺序增加每个时间可以发送的事件数量.留在n的极限.因此,如果您过早地获得某个事件,则会将其增加小于1,如果经过太多时间后您将其增加一个以上.当然,如果事件发生了,你刚刚得到一个事件就会减少1.如果允许通过最大事件n,则将其返回到n,因为在任何时间阶段都不允许超过n.如果津贴小于1,你就不能发送一个完整的事件,不要让它通过!

这是漏桶算法:https://en.wikipedia.org/wiki/Leaky_bucket