FlowControl

From RAD Lab

Applying control theory in flow control of software system

Students

• Wei Xu

Summary

Many large software systems today are built out of black-box components. Workload is pushed through these components at different stage of processing (in many cases, pushing is more intuitive than pulling in Internet applications). One practical problem is that throughput of these components can be different. Also, some of these components are not designed to handle overload situation well. For example, in a J2EE system, when the database tier is slower than the front end, deadlock occurs once overloaded. Programmers need to do tedious hand-tuning to avoid these situations. This is even worse if components run on different machines, each of which can get performance disturbances independently. Automatic and adaptive flow control mechanism is thus important. Flow control in software system is different from networking since we do not have the freedom of dropping requests. However, we have more global information.

We found feedback control theory a suitable method to deal with these situations. With control theory, we can treat components as black boxes, and use standard system identification techniques to construct (linear) models of the system. Disturbances and inaccuracy of model are dynamically fixed by the feedback loop. The controller implementation is simple and the performance can be mathematically proved.

We applied control theory to a parallel data stream processing system, using TelegraphCQ, a data stream query engine, as building blocks. We applied control theory to prevent overloading any TelegraphCQ node, while dynamically adjust the node to the optimal throughput. The resulting system adapts to workload changes and disturbances within seconds, preventing undesired data loss due to buffer overflow. We also built a load balancer to dynamically re-distribute workload among nodes to deal with slow down in part of the system.

Our current project is flow control in a J2EE application server mentioned above. The goal is to regulate workload at the front tier to prevent overloading the shared database, while keeping fairness over all requests. This project is more challenging than data stream since workload in an enterprise application has a much larger variance in terms of resource demand. Our current approach is that using simple statistical method to categorize workload at the web server tier and predict its resource usage. The inaccuracy of this prediction is fixed by the feedback loop. We also employed queuing theory algorithms and probabilistic scheduling, typically seen in networking, to dynamically control resources sharing among categories. The initial results show that it effectively prevented database overloading and thus preventing deadlock, and clients see a smaller response time.

References Can be found at Publication page of this Wiki