[Twisted-Python] Scalability of timers

[dw+twisted-python at hmmz.org]

Hey Tobias,

Individual OS have their own mechanisms for avoiding the kind of waste
you're describing. For example, Linux quite aggressively rounds up the
expiry of certain classes of timer at progressively less granular
intervals the further in the future they're scheduled ("timer
coalescing").

When Twisted wakes, there is no guarantee that that only one timer has
expired by then. In fact under load you would expect the select loop to
always be running (and thus timing out) late, and so each iteration may
process several timers simultaneously.

Twisted will set the select() timeout to the timer due to expire the
earliest. Finding this timer is a constant time operation. There is only
ever one active select() (or select-equivalent) call active at a time.

The Twisted timer implementation internally uses a heap, so scheduling
and expiry are quite efficint O(logN). With 4 billion timers active,
scheduling a new timer in the worst case would require 32 array elements
to be swapped.


On Sun, Aug 10, 2014 at 05:16:51AM -0700, Tobias Oberstein wrote:
> Hi,
> 
> I have a question regarding scalability of timers in Twisted.
> 
> Say I have a massive number of periodic timers (lets say each with period 1s, but all slightly time shifted to each other).
> 
> As far as I understand, timers are implemented ultimately by setting the timeout parameter when calling into OS select/poll/epoll/kqueue.
> 
> If this  is true, then the number of timers scales linearly with the number of syscalls. This can get limiting (the total number of syscalls a Linux box can sustain is a couple of 100k's per second). As more and more timers are setup, the timeout essentially will approach 0. On the upside, timers will fire precisely.
> 
> However, say I am fine with a precision of 1ms.
> 
> Is there a way that limits the syscall rate to 1000/s (given no FD activity happens) _independently_ of the number of timers setup?
> 
> Timers that fall into a certain ms slice would all fire roughly at the same time (still ordered).
> 
> Is that possible?
> 
> Thanks,
> Tobias
> 
> _______________________________________________
> Twisted-Python mailing list
> Twisted-Python at twistedmatrix.com
> http://twistedmatrix.com/cgi-bin/mailman/listinfo/twisted-python