Friday, August 01, 2008

3: Thoughts on a new NDB API: Adaptive send algorithm

I thought a bit more on the adaptive send algorithm and kind of like
the following approach:

Keep track of how many sends we are at maximum allowed to wait
until we send in any ways. This is the state of the adaptive send
algorithm which is adapted through the following use of statistics
(we call this state variable max_waits):

For each send we calculate how long time has passed since the
send that was sent max_waits sends ago. We also do the same for
max_waits + 1. At certain intervals (e.g. every 10 milliseconds) we
calculate the mean wait that a send would have to do, if this lies
within half the desired maximum wait then we accept the current
state, if also the mean value using max_waits + 1 is acceptable
then we increase the state by one. If the state isn't acceptable
we decrease it by one.

In the actual decision making we will always send as soon as we
notify that more than the maximum wait time has occurred so this
means that the above algorithm is conservative. However the user
should have the ability to control how long he accepts a wait
through a configuration variable, thus increasing or decreasing
send buffering at the expense of extra delays.

This algorithm is applied on each socket and the actual decision
making is done within the critical section and also the statistics
calculation and from coding this it seems like the overhead should
be manageable.

No comments: