blocks|key|1385570|text|一种解决方案是将时间戳附加到每个队列项，并在经过8秒后丢弃该项。每次将队列添加到时，都可以执行此检查。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1385571|只有当您将队列大小限制为5，并在队列已满时丢弃任何添加的内容时，这才有效。|1385572|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|F|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|G|8|@]|9|@]|A|$]]|$1|D|3|-4|5|6|7|H|8|@]|9|@]|A|$]]]|E|$]]

One solution is to attach a timestamp to each queue item and to discard the item after 8 seconds have passed. You can perform this check each time the queue is added to.

This only works if you limit the queue size to 5 and discard any additions whilst the queue is full.

blocks|key|1385584|text|保持发送最后五行的时间。保留排队的消息，直到最近的第五条消息(如果存在)在过去至少8秒内(+last_five为时间数组)：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1385585|now+=+time.time()
if+len(last_five)+==+0+or+(now+-+last_five[-1])+>=+8.0:
++++last_five.insert(0,+now)
++++send_message(msg)
if+len(last_five)+>+5:
++++last_five.pop()|code-block|syntax|javascript|1385586|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

Keep the time that the last five lines were sent. Hold the queued messages until the time the fifth-most-recent message (if it exists) is a least 8 seconds in the past (with last_five as an array of times):

<pre><code>now = time.time()
if len(last_five) == 0 or (now - last_five[-1]) &gt;= 8.0:
 last_five.insert(0, now)
 send_message(msg)
if len(last_five) &gt; 5:
 last_five.pop()
</code></pre>

blocks|key|1600430|text|在你的入队函数之前使用这个装饰符@RateLimited(ratepersec)。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1600431|基本上，这会检查自上次以来是否经过了1/rate秒，如果没有，则等待剩余时间，否则不等待。这实际上将您限制为速率/秒。装饰器可以应用于任何你想要的速率限制的函数。|1600432|在您的示例中，如果您希望每8秒最多发送5条消息，请在sendToQueue函数之前使用@RateLimited(0.625)。|1600433|import+time

def+RateLimited(maxPerSecond):
++++minInterval+=+1.0+/+float(maxPerSecond)
++++def+decorate(func):
++++++++lastTimeCalled+=+[0.0]
++++++++def+rateLimitedFunction(*args,**kargs):
++++++++++++elapsed+=+time.clock()+-+lastTimeCalled[0]
++++++++++++leftToWait+=+minInterval+-+elapsed
++++++++++++if+leftToWait>0:
++++++++++++++++time.sleep(leftToWait)
++++++++++++ret+=+func(*args,**kargs)
++++++++++++lastTimeCalled[0]+=+time.clock()
++++++++++++return+ret
++++++++return+rateLimitedFunction
++++return+decorate

@RateLimited(2)++#+2+per+second+at+most
def+PrintNumber(num):
++++print+num

if+__name__+==+"__main__":
++++print+"This+should+print+1,2,3...+at+about+2+per+second."
++++for+i+in+range(1,100):
++++++++PrintNumber(i)|code-block|syntax|javascript|1600434|entityMap^0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|M|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|N|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|O|8|@]|9|@]|A|$]]|$1|F|3|G|5|H|7|P|8|@]|9|@]|A|$I|J]]|$1|K|3|-4|5|6|7|Q|8|@]|9|@]|A|$]]]|L|$]]

Use this decorator @RateLimited(ratepersec) before your function that enqueues.

Basically, this checks if 1/rate secs have passed since the last time and if not, waits the remainder of the time, otherwise it doesn't wait. This effectively limits you to rate/sec. The decorator can be applied to any function you want rate-limited.

In your case, if you want a maximum of 5 messages per 8 seconds, use @RateLimited(0.625) before your sendToQueue function.

<pre><code>import time

def RateLimited(maxPerSecond):
 minInterval = 1.0 / float(maxPerSecond)
 def decorate(func):
 lastTimeCalled = [0.0]
 def rateLimitedFunction(*args,**kargs):
 elapsed = time.clock() - lastTimeCalled[0]
 leftToWait = minInterval - elapsed
 if leftToWait&gt;0:
 time.sleep(leftToWait)
 ret = func(*args,**kargs)
 lastTimeCalled[0] = time.clock()
 return ret
 return rateLimitedFunction
 return decorate

@RateLimited(2) # 2 per second at most
def PrintNumber(num):
 print num

if __name__ == "__main__":
 print "This should print 1,2,3... at about 2 per second."
 for i in range(1,100):
 PrintNumber(i)
</code></pre>

blocks|key|1385630|text|这里是simplest+algorithm，如果您只想在消息到达太快时丢弃它们(而不是对它们进行排队，这是有意义的，因为队列可能会变得任意大)：|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|1385631|rate+=+5.0;+//+unit:+messages
per++=+8.0;+//+unit:+seconds
allowance+=+rate;+//+unit:+messages
last_check+=+now();+//+floating-point,+e.g.+usec+accuracy.+Unit:+seconds

when+(message_received):
++current+=+now();
++time_passed+=+current+-+last_check;
++last_check+=+current;
++allowance+%2B=+time_passed+*+(rate+/+per);
++if+(allowance+>+rate):
++++allowance+=+rate;+//+throttle
++if+(allowance+<+1.0):
++++discard_message();
++else:
++++forward_message();
++++allowance+-=+1.0;|code-block|syntax|javascript|1385632|在这个解决方案中没有数据结构、计时器等，它工作得很干净:)要看到这一点，“允许”以每秒最多5/8个单位的速度增长，即每8秒最多5个单位。每转发一条消息就会扣除一个单位，因此每8秒发送的消息不能超过5条。|1385633|请注意，rate应该是一个整数，即没有非零的小数部分，否则算法将无法正常工作(实际的速率不会是rate/per)。例如，因为allowance永远不会增长到1.0，所以rate=0.5;+per=1.0;无法工作。但是rate=1.0;+per=2.0;运行得很好。|style|CODE|1385634|entityMap|0|LINK|mutability|MUTABLE|url|http://en.wikipedia.org/wiki/Token_bucket^0|3|I|0|0|0|0|4|4|1B|8|1Q|9|2C|I|31|I|0^^$0|@$1|2|3|4|5|6|7|W|8|@]|9|@$A|X|B|Y|1|Z]]|C|$]]|$1|D|3|E|5|F|7|10|8|@]|9|@]|C|$G|H]]|$1|I|3|J|5|6|7|11|8|@]|9|@]|C|$]]|$1|K|3|L|5|6|7|12|8|@$A|13|B|14|M|N]|$A|15|B|16|M|N]|$A|17|B|18|M|N]|$A|19|B|1A|M|N]|$A|1B|B|1C|M|N]]|9|@]|C|$]]|$1|O|3|-4|5|6|7|1D|8|@]|9|@]|C|$]]]|P|$Q|$5|R|S|T|C|$U|V]]]]

Here the <a href="http://en.wikipedia.org/wiki/Token_bucket" rel="noreferrer">simplest algorithm</a>, if you want just to drop messages when they arrive too quickly (instead of queuing them, which makes sense because the queue might get arbitrarily large):

<pre><code>rate = 5.0; // unit: messages
per = 8.0; // unit: seconds
allowance = rate; // unit: messages
last_check = now(); // floating-point, e.g. usec accuracy. Unit: seconds

when (message_received):
 current = now();
 time_passed = current - last_check;
 last_check = current;
 allowance += time_passed * (rate / per);
 if (allowance &gt; rate):
 allowance = rate; // throttle
 if (allowance &lt; 1.0):
 discard_message();
 else:
 forward_message();
 allowance -= 1.0;
</code></pre>

There are no datastructures, timers etc. in this solution and it works cleanly :) To see this, 'allowance' grows at speed 5/8 units per seconds at most, i.e. at most five units per eight seconds. Every message that is forwarded deducts one unit, so you can't send more than five messages per every eight seconds.

Note that <code>rate</code> should be an integer, i.e. without non-zero decimal part, or the algorithm won't work correctly (actual rate will not be <code>rate/per</code>). E.g. <code>rate=0.5; per=1.0;</code> does not work because <code>allowance</code> will never grow to 1.0. But <code>rate=1.0; per=2.0;</code> works fine.

blocks|key|1385636|text|这样如何：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1385637|long+check_time+=+System.currentTimeMillis();
int+msgs_sent_count+=+0;

private+boolean+isRateLimited(int+msgs_per_sec)+{
++++if+(System.currentTimeMillis()+-+check_time+>+1000)+{
++++++++check_time+=+System.currentTimeMillis();
++++++++msgs_sent_count+=+0;
++++}

++++if+(msgs_sent_count+>+(msgs_per_sec+-+1))+{
++++++++return+true;
++++}+else+{
++++++++msgs_sent_count%2B%2B;
++++}

++++return+false;
}|code-block|syntax|javascript|1385638|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

How about this:

<pre><code>long check_time = System.currentTimeMillis();
int msgs_sent_count = 0;

private boolean isRateLimited(int msgs_per_sec) {
 if (System.currentTimeMillis() - check_time &gt; 1000) {
 check_time = System.currentTimeMillis();
 msgs_sent_count = 0;
 }

 if (msgs_sent_count &gt; (msgs_per_sec - 1)) {
 return true;
 } else {
 msgs_sent_count++;
 }

 return false;
}
</code></pre>

blocks|key|1600519|text|为了阻塞处理，直到可以发送消息，从而使更多的消息排队，antti的漂亮解决方案也可以像这样修改：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1600520|rate+=+5.0;+//+unit:+messages
per++=+8.0;+//+unit:+seconds
allowance+=+rate;+//+unit:+messages
last_check+=+now();+//+floating-point,+e.g.+usec+accuracy.+Unit:+seconds

when+(message_received):
++current+=+now();
++time_passed+=+current+-+last_check;
++last_check+=+current;
++allowance+%2B=+time_passed+*+(rate+/+per);
++if+(allowance+>+rate):
++++allowance+=+rate;+//+throttle
++if+(allowance+<+1.0):
++++time.sleep(+(1-allowance)+*+(per/rate))
++++forward_message();
++++allowance+=+0.0;
++else:
++++forward_message();
++++allowance+-=+1.0;|code-block|syntax|javascript|1600521|它只是等待，直到有足够的余量来发送消息。为了不以两倍的速率开始，容差也可以初始化为0。|1600522|entityMap^0|0|0|0^^$0|@$1|2|3|4|5|6|7|K|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|L|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|M|8|@]|9|@]|A|$]]|$1|I|3|-4|5|6|7|N|8|@]|9|@]|A|$]]]|J|$]]

to block processing until the message can be sent, thus queuing up further messages, antti's beautiful solution may also be modified like this:

<pre><code>rate = 5.0; // unit: messages
per = 8.0; // unit: seconds
allowance = rate; // unit: messages
last_check = now(); // floating-point, e.g. usec accuracy. Unit: seconds

when (message_received):
 current = now();
 time_passed = current - last_check;
 last_check = current;
 allowance += time_passed * (rate / per);
 if (allowance &gt; rate):
 allowance = rate; // throttle
 if (allowance &lt; 1.0):
 time.sleep( (1-allowance) * (per/rate))
 forward_message();
 allowance = 0.0;
 else:
 forward_message();
 allowance -= 1.0;
</code></pre>

it just waits until enough allowance is there to send the message. to not start with two times the rate, allowance may also initialized with 0.

blocks|key|1385742|text|如果有人仍然感兴趣，我将这个简单的可调用类与定时LRU键值存储结合使用，以限制每个IP的请求率。使用双队列，但可以重写为与列表一起使用。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1385743|from+collections+import+deque
import+time


class+RateLimiter:
++++def+__init__(self,+maxRate=5,+timeUnit=1):
++++++++self.timeUnit+=+timeUnit
++++++++self.deque+=+deque(maxlen=maxRate)

++++def+__call__(self):
++++++++if+self.deque.maxlen+==+len(self.deque):
++++++++++++cTime+=+time.time()
++++++++++++if+cTime+-+self.deque[0]+>+self.timeUnit:
++++++++++++++++self.deque.append(cTime)
++++++++++++++++return+False
++++++++++++else:
++++++++++++++++return+True
++++++++self.deque.append(time.time())
++++++++return+False

r+=+RateLimiter()
for+i+in+range(0,100):
++++time.sleep(0.1)
++++print(i,+"block"+if+r()+else+"pass")|code-block|syntax|javascript|1385744|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

If someone still interested, I use this simple callable class in conjunction with a timed LRU key value storage to limit request rate per IP. Uses a deque, but can rewritten to be used with a list instead.

<pre><code>from collections import deque
import time


class RateLimiter:
 def __init__(self, maxRate=5, timeUnit=1):
 self.timeUnit = timeUnit
 self.deque = deque(maxlen=maxRate)

 def __call__(self):
 if self.deque.maxlen == len(self.deque):
 cTime = time.time()
 if cTime - self.deque[0] &gt; self.timeUnit:
 self.deque.append(cTime)
 return False
 else:
 return True
 self.deque.append(time.time())
 return False

r = RateLimiter()
for i in range(0,100):
 time.sleep(0.1)
 print(i, "block" if r() else "pass")
</code></pre>

blocks|key|1600577|text|我需要Scala的一个变种。这就是它：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1600578|case+class+Limiter[-A,+%2BB](callsPerSecond:+(Double,+Double),+f:+A+⇒+B)+extends+(A+⇒+B)+{

++import+Thread.sleep
++private+def+now+=+System.currentTimeMillis+/+1000.0
++private+val+(calls,+sec)+=+callsPerSecond
++private+var+allowance++=+1.0
++private+var+last+=+now

++def+apply(a:+A):+B+=+{
++++synchronized+{
++++++val+t+=+now
++++++val+delta_t+=+t+-+last
++++++last+=+t
++++++allowance+%2B=+delta_t+*+(calls+/+sec)
++++++if+(allowance+>+calls)
++++++++allowance+=+calls
++++++if+(allowance+<+1d)+{
++++++++sleep(((1+-+allowance)+*+(sec+/+calls)+*+1000d).toLong)
++++++}
++++++allowance+-=+1
++++}
++++f(a)
++}

}|code-block|syntax|javascript|1600579|下面是它的使用方法：|1600580|val+f+=+Limiter((5d,+8d),+{+
++_:+Unit+⇒+
++++println(System.currentTimeMillis)+
})
while(true){f(())}|1600581|entityMap^0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|M|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|N|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|O|8|@]|9|@]|A|$]]|$1|I|3|J|5|D|7|P|8|@]|9|@]|A|$E|F]]|$1|K|3|-4|5|6|7|Q|8|@]|9|@]|A|$]]]|L|$]]

I needed a variation in Scala. Here it is:

<pre><code>case class Limiter[-A, +B](callsPerSecond: (Double, Double), f: A ⇒ B) extends (A ⇒ B) {

 import Thread.sleep
 private def now = System.currentTimeMillis / 1000.0
 private val (calls, sec) = callsPerSecond
 private var allowance = 1.0
 private var last = now

 def apply(a: A): B = {
 synchronized {
 val t = now
 val delta_t = t - last
 last = t
 allowance += delta_t * (calls / sec)
 if (allowance &gt; calls)
 allowance = calls
 if (allowance &lt; 1d) {
 sleep(((1 - allowance) * (sec / calls) * 1000d).toLong)
 }
 allowance -= 1
 }
 f(a)
 }

}
</code></pre>

Here is how it can be used:

<pre><code>val f = Limiter((5d, 8d), { 
 _: Unit ⇒ 
 println(System.currentTimeMillis) 
})
while(true){f(())}
</code></pre>

blocks|key|1600622|text|只是一个python实现的代码，从接受的答案。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1600623|import+time

class+Object(object):
++++pass

def+get_throttler(rate,+per):
++++scope+=+Object()
++++scope.allowance+=+rate
++++scope.last_check+=+time.time()
++++def+throttler(fn):
++++++++current+=+time.time()
++++++++time_passed+=+current+-+scope.last_check;
++++++++scope.last_check+=+current;
++++++++scope.allowance+=+scope.allowance+%2B+time_passed+*+(rate+/+per)
++++++++if+(scope.allowance+>+rate):
++++++++++scope.allowance+=+rate
++++++++if+(scope.allowance+<+1):
++++++++++pass
++++++++else:
++++++++++fn()
++++++++++scope.allowance+=+scope.allowance+-+1
++++return+throttler|code-block|syntax|javascript|1600624|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

Just a python implementation of a code from accepted answer.

<pre><code>import time

class Object(object):
 pass

def get_throttler(rate, per):
 scope = Object()
 scope.allowance = rate
 scope.last_check = time.time()
 def throttler(fn):
 current = time.time()
 time_passed = current - scope.last_check;
 scope.last_check = current;
 scope.allowance = scope.allowance + time_passed * (rate / per)
 if (scope.allowance &gt; rate):
 scope.allowance = rate
 if (scope.allowance &lt; 1):
 pass
 else:
 fn()
 scope.allowance = scope.allowance - 1
 return throttler
</code></pre>

I could use some pseudo-code, or better, Python. I am trying to implement a rate-limiting queue for a Python IRC bot, and it partially works, but if someone triggers less messages than the limit (e.g., rate limit is 5 messages per 8 seconds, and the person triggers only 4), and the next trigger is over the 8 seconds (e.g., 16 seconds later), the bot sends the message, but the queue becomes full and the bot waits 8 seconds, even though it's not needed since the 8 second period has lapsed.

What's a good rate limiting algorithm?

数据结构

Python

我可以使用一些伪代码，或者更好的Python。我正在尝试为Python IRC机器人实现一个速率限制队列，它部分工作，但是如果有人触发的消息少于限制(例如，速率限制是每8秒5条消息，而人只触发4条)，并且下一个触发器超过8秒(例如，16秒后)，机器人发送消息，但是队列变满，机器人等待8秒，即使由于8秒周期已经过去而不需...

问什么是好的速率限制算法？
EN

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问什么是好的速率限制算法？EN

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问什么是好的速率限制算法？
EN