Review APM & Ratio scheduler

[krizhanovsky]

Issue #565 implements load distribution using algorithm from b7ccb83 . However, the algorithm distributes requests with bursts in some cases. For example 100 requests are distributed among servers with weights { 38, 9, 5, 4, 3, 3, 1 } as:

    0 0 1 0 1 2 0 1 2 0 1 2 0 1 2 3 0 1 2 3 0 1 3 0 1 0 1 0 3 4 0 4 0 0 0 0 4 5 0 0 5 0 0 0 0 5
    0 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 0 0 0 1 0 1 2 0 1 2 0 1 2 0 1 2 3 0 1 2 3 0 1 3 0 1 0 1 0 3
    4 0 4 0 0 0 0 4 

However, the first server (0) should be chosen more frequently at the begin reducing the long 0-series at the end. The behaviour can be used with Weighted Fair Queue.

Secondly, the implementation now uses spin lock. We need to think more how to improve concurrency of the scheduler. Probably it has sense to use some data structures per-CPU.

Next, decisions made by the machine learning logic can be very surprising for a system administrator, so history for dynamic ratios and predictions must be shown by APM module. Anyway, this is very useful information to show to user. In future we can have a special caution logic in WebUI dashboard.

Need to test real life requests distribution by the predictive load balancer among servers with different characteristics. Also APM and ratio schedulers use relatively complex calculations and locking, so extensive performance testing and profiling are required as well. Probably we should use SIMD calculations for SLR - this could be very beneficial for large number of servers...

APM solves trade offs between measurements accuracy and performance, so APM accounting also should be revised. For example, we can collect average values for each tick instead of rewriting TFW_APM_UBUF_SZ samples in round robin manner.

Consider EMA algorithm or its derivatives for APM calculations. If a "good" APM should use more complex algorithms, then with #736 (timers issues) in mind the whole analytics must be moved to user space and probably get cleanded (e.g. sampled) data from the kernel. #1137 (speculative retries) require even more advanced ML.

[krizhanovsky]

Also address comment https://github.com/tempesta-tech/tempesta/blob/master/tempesta_fw/http.c#L2173 :

    TODO: When a response is received and a paired request is found,
    pending (unsent) requests in the connection are forwarded to the
    server right away. In current design, @fwd_queue is locked until
    after a request is submitted to SS for sending. It shouldn't be
    necessary to lock @fwd_queue for that. Please see a similar TODO
    comment to tfw_http_req_fwd(). Also, please see the issue #687.

[krizhanovsky]

Current algorithm (tfw_sched_ratio_next_srv() or sched() in the unit test) requires a spin lock. That's a bad. We have to use the lock as described in the comment for tfw_sched_ratio_next_srv(), but we still want to have RR (ratio) scheduler as the most quick one. However, probably that would be an issue now if we for example try it to run on 4 processors machine (e.g. 40 and more CPU cores). Thus, let's introduce 2 versions of the function: this one for dynamic ratios and a variation of the old one, from RR scheduler, for static, maybe not equal, ratios.

Need to test performance of the scheduler (see #680) and gather profiling information - probably some further optimizations are required.

[keshonok]

The APM module has been reworked to use a different concept.

The major ideas and deficiencies of the former concept were:

• Updates for a specific server were performed in parallel by different threads (that run on different CPU). That was supported by the use of atomic ops on most of statistics data.
• Some of the necessary manipulations on stats data, like range extending or shrinking, still required locks that provided consistency of stats data.
• The algorithm favoured speed. If a lock was already taken, then a range extending/shrinking/adjusting procedure was postponed until next time. That lead to inconsistencies between various stats data at a given moment of time, where some stats data were updated, and some other data were not.
• The calculation of percentiles was also performed in parallel with updates, albeit at a significantly slower rate. Still, it run on data that were changing on the fly, and possibly inconsistent on top of that. That lead to situations where the calculation of percentiles could not be completed.

The reworked implementation uses the following ideas:

• Updates for a specific server that come from HTTP module just store the stats source data (RTT + time stamp) in a storage and return. That way updates are fast. The stats source data is not acted upon (processed) yet. Per-CPU arrays are used for storage, so it works completely lock-less.
• A thread wakes up every so often and processes the accumulated updates. That way processing of updates is serialized. Atomic ops on stats data are not needed.
• Necessary manipulations on stats data is inherently serialized as well. Stats data stay consistent at all times.
• No locks are needed due to serialization.
• The calculation of percentiles is run by the same thread after it processes the accumulated updates, so it is serialized as well. It runs on consistent data that is not changed from under the calculation process, so it's always successful.

The reworked implementation uses an idea that it's not necessary to accumulate each and every update of stats data for the algorithm to run in a reasonable way. The above mentioned thread that processes the accumulated updates and runs the calculation of percentiles, currently runs every 50 milliseconds (HZ/20). The per-CPU array is purposely made of 50 entries that is indexed by (timestamp % 50). That way approximately one stats result is accumulated for each millisecond of time, which should be sufficient for the purposes of APM. Other algorithms can be used to select a meaningful subset of stats source data for processing.

The processing thread currently runs on timer every 50 milliseconds (HZ/20). That may not be necessary. Please see #736.

[krizhanovsky]

Append issue #684 "Predictive load balancing: account current send queue size":

Currently predictive requests scheduler makes decision based on previous response times only. However, current queue size, and especially how significantly it differs from previous, of send (forward) queue for an upstream server means how busy the server is and how big delays we should expect.