An experiment in elastically scaling a thread pool using a PID controller
github.com
github.com
Some notes adding to the author's questions at end:
* In addition to putting a maximum number of threads, you'll probably want to put a maximum on your integral accumulator (oh, and probably a minimum number of threads too).
* If there's no cost in switching threads between different jobs, and all jobs are truly part of a single tree of steps, then you could probably get away with a global controller. However if you have certain steps that have especially unpredictable and/or time-varying requirements, you might consider giving it a separate controller
* Because queue length can't get less than 0, you can get pretty asymmetric behavior in your controller (it can only "unload" excess threads at a given rate). This might be useful behavior, but also might be worth tuning. You can implement gain scheduling (so picking different PID values for different states), or change your error measure to something that is more symmetric.
* Consider adding a dead zone/hysteresis around your zero point.
* The D term is probably not that useful here. As you saw, the addition of the I was the big game changer. Won't go into full control theory, but one way you can think about this is that 'effort' that you're putting in is scaling the number of threads. The time integral of number of threads gives you number of items processed, which is the same units as queue length. If you find a 'measure' and an 'effort' that have the same units, then you might even find that you can skip the I term completely.
* Always worth studying the cost you see (either total resources spend on threads, or cost of volatility scaling up and down) versus what the end user sees (wait time). It's possible you can get away with a much simpler system with an appropriate hard minimum + simpler (ie maybe just P + maximum rate of change) system.
Nevertheless I did my best explaining what I can, but if you think you can improve upon it then I'm happy to accept pull requests.
Teasing apart, it always amazes me how slow the diffusion of innovation is across different fields.
The main idea is that control problems can be posed as optimization problems where we try to achieve some goal (financial / stability etc) while satisfying some hard restrictions.
For example try to change lines gracefully and fast on the highway without crashing on another car.
For your particular case, if you want something dirt cheap (computationally) and reliable then the PID is a great first step.
I had been dabbling with electronics for a while, so I had heard of PID controllers (as black boxes). Never really thought of them outside of that.
The first time it clicked for me that this could have applications in other fields was when playing a game. Stationeers, to be precise. Sure, the PID controller that a user is created was controlling a device in the game, but the actual code was implemented in 'assembly' and very simple to understand. That led me to think that I could use that in place of our simpler autoscalers at work. I have not implemented a solution, but that's how the gears started to turn.
Reading this thread, apparently the field has advanced far past PID controllers. Now it's yet another rabbit hole to go through...
Blog by DoorDash team - https://doordash.engineering/2023/03/14/failure-mitigation-f...
Project - https://github.com/fluxninja/aperture
The processor has fixed resource capabilities, if you run it at the maximum the only tradeoff is power. If you don't account for power it's like driving a car with unlimited fuel, why should you use a pid controller to control how many pistons fire if my fuel is unlimited? Just have the engine run idle always.
I mean there's wear and tear on an engine but this aspect of the analogy doesn't translate to threads.
The only other place where I see this is useful is competing tasks. One task needs more resources from a thread pool shared by other tasks. A pid controller can allocate existing threads based off of pressure. Allocating more threads to a pool in this case though, still doesn't make sense.
Saving costs, if you're in a cloud environment.
Imagine you got 16 CPUs/cores and a 4 stage pipeline, lets say we want to run one thread per CPU/core for max performance (avoiding context switching). Without knowing anything about the workload: what is the best way to distributed the threads over the stages? You can't tell. Even if you tested all the possilble ways to spread out the threads over the different stages on some particular workload, then as the workload changes you wouldn't have optimal allocation anymore. A controller can adjust the threads per stage until it finds the optimal allocation for the current workload and change it as it changes.
This article is NOT exactly about that. It's about allocating more threads to a thread pool. I'm addressing the pointlessness of using PID controllers for allocating new threads.
So your point is mistaken and redundant to mine.
It is not about utilizing existing threads in threadpools.
Thats where YOU are mistaken. Your example has threads preallocated to core affinity. Which is what Im saying when I say run all pistons on the engine even when idle.
Maybe I should learn more about kernel internals.
They all need to be regulated, somehow, for best performance. Unfortunately, nobody really knows how to do that except in small isolated cases. What is even more unfortunate: very few of the people working in this area seem to know anything about control theory.
Feedback Control for Computer Systems
Philipp K. Janert
330 pages
O’Reilly (2013)
ISBN: 978-1449361693Typical things: scheduling algorithms for 1) processes, 2) disk reads/writes/seeks, TCP/IP stuff (slow start, throttling, window sizing).
For control theory viewed as part of engineering: "Control System Design" by Goodwin, Graebe, and Salgado.
There are many others but that was the one that worked best for me.
One interesting read: https://www.cs.unc.edu/~tracker/media/pdf/SIGGRAPH2001_Cours...
[1] https://mattwarren.org/2017/04/13/The-CLR-Thread-Pool-Thread...
It is very rare that you can successfully use this in practice. You either a) Have just one machine, and that machine has a fixed number of cores (or cannot readily swap number of cores on the fly). If your machine is dedicated to this task, it doesn't make much sense to resize your thread pool - Leave it at max. The only way a smaller threadpool would help is if you have noisy neighbors sharing a machine and cores. However, if you have noisy neighbors, your simple queue-length PID controller will start using more cores not just when you have more than one core worth of traffic, but also when you have a lot of noise and are at max threads. It's fine and dandy in the happy case, but it fails pretty spectacularly in the worst case - Each additional thread creates more exposure to your noisy neighbors and possibly even worse global throughput.
If you b) Have multiple machines, you don't want to do this at all. The number of replicas (processes, or "pods" as I will call them because anchoring this in real-world K8s experience is helpful) goes up and down, but you need feedback on the number of threads or cores involved at the top level. If the number of threads goes up per process but the number of processes goes down, or the number of threads goes down but the number of processes goes up, you can get really wonky feedback loops.
E.g. you have an application that could get spammed with 10,000 requests. The application server is fine, but the database can suffer performance issues.
So you have some sort of feedback loop monitoring the response time of the database and deciding how many requests you let through.
I thought about this because it's useful for something I was working on. But I have never used PID controllers and it looked like it's the sort of thing they could be used for. Never went further with it though.
In your scenario, since the rate of database requests is probably a very simple function of number (ie, well modelled by a simple constant multiple) of application requests, you probably don't need a "full controller" to implement the throttling.
For example, say I want to list all the keys in an s3 bucket that start with any of 1000 given prefixes. I can do a lot of calls per second, but of course have limited bandwidth and limited cpu to process the incoming responses, and sometimes s3 can say "too many requests" if other users are querying the same prefixes. How do I do this as fast as possible?
I’ve started writing extensive documentation for internal projects at work, with the intention that someone could pick them up, understand the context, use the code and improve it without needing to talk to me.
[0]: https://people.eecs.berkeley.edu/~brewer/papers/SEDA-sosp.pd...
It might be more suited to infinitely-scalable situations like cloud VMs, where you are trying to optimize money spent.
Right, it should base the feedback on throughput measures instead. If throughput starts dropping, then the threadpool is overcommitted, and should scale back.
I believe the SEDA papers mentioned in the README discusses this as backpressure.
If your threads don't block and you have one main application running on the node, you usually just want to run one thread per node and you're done. If you are running a very network heavy load where you can eliminate or highly reduce cross thread communication, you may want one core per NIC tx/rx queue and one thread per core to eliminate cross-core communication; any cores above the number of queues will just be idle, because cross-core communication is more expensive than the work they can do (but that's not a super common scenario).
A control system to add and remove nodes makes sense if you're cloudy, though, since there's a cost for running nodes.
That would be my intuition too, in particular that usually the cost of idle workers is pretty low, so it's better just to preallocate some fixed max number of workers than try to scale them.
I wouldn't necessarily intuit the cost of idle workers is low, more that the non-cpu cost of workers is roughly fixed, and if it's too expensive to run more than you need at idle, it's still going to be too expensive to run that many at full load. Sometimes it's hard to know what the max load capacity is, but Apache configs where the worker count scales in and out are really easy to get into load is high -> spawn more workers -> use too much memory -> pick your poison: evict too much disk cache / swap to death / oom killer
Is that intended? Or I'm misinterpreting the graphs?
You are right that it's not unloading. In general, you'd expect the response (green line) of a PID controller to a sinusoid load to be another sinusoid. In this case, because the maximum error is bounded on one side(the setpoint is 0, and queue length can never get below 0), it can only unload at a certain rate. It's typically the job of the Ki term to bring the long-term error towards zero. In this case, I think it's tuned small enough + the bounded asymmetric maximum error to result in it never unloading.
Perhaps my naive implementation of the PID controller isn't good enough, maybe:
> you'll probably want to put a maximum on your integral accumulator
is needed as icegreentea2 pointed out.
The PID controller is finding a reasonable number of workers that handle the peak bursts without allowing the queue to get too long, and without spamming and destroying threads unnecessarily.
The cost is that under peak load the queue does back up a little, but if the queue stayed long for too long, the PID should create new threads.
The other line, which flattens out at 26 (see right y axis) is the number of workers.
Some stuff I learned over the years somebody might find useful:
1) Tune your app for max load. This is the most important parameter, nobody really cares what happens when you have 10% of the load -- what is important is how it behaves when you are close to, at or above capacity. If your app can behave nicely as it reaches its limit it should also be able to behave nicely at less than it. Why scale down your thread pools? Threads do not use extra resources when they are not running -- if you had resources at max capacity you now have resources laying around to have an idle thread. Just find the number you need at your max load and leave it at that. Your framework should be able to allocate concurrency until it hits the limit at which point it will be in the state as tuned for max load.
2) A trick I found is to make sure the application becomes more efficient per-transaction as the load increases. This means things like increasing batch sizes, etc. Increasing concurrency can have opposite effect. When per-transaction efficiency increases the application tends to behave nicely as it approaches its max throughput and it is much easier to keep stable at or close to the limit.
3) One way of increasing per-transaction efficiency is increase batch sizes. Imagine a system where every user login requires an object to be fetched from the database. Rather than generate database request for each login, pipe them together and batch them every 100ms. Then take that 100ms batch and generate single request to the database engine, fetch the results, distribute to clients. Now as more and more users log in your application does not create more requests to the database -- it creates 10 requests every second regardless of the load. Larger requests should translate to higher efficiency per item. When the number of users logging in reaches limit you have option of buffering requests (preserving the database from getting overloaded) but this is more likely going to dramatically drop the efficiency. Instead, you can drop requests and require client to implement exponential backoff when retrying the requests.
4) I actually use control engineering techniques to change parameters of the system (just not the concurrency). For example, you can try to regulate processing latency or server load by modifying the limit of transactions in flight. You can even try to regulate database load (I have MongoDB report its state to app layer and app layer adjust its parameters to keep database in safe operating conditions). The reason to do this is because the system is incredibly complex and with all asynchronous stuff happening there is nobody that really understands what is happening. Feedback control helps stabilising system in much wider range of circumstances without people having to change any configuration which is one of big reliability improvements. Feedback control will regulate faster and kick in before anybody notices anything and has much less chance of messing stuff up. One warning, though, it is important to put some boundaries on safe operating space for the control. Whatever control you implement there are going to be limits to what it can and can't do. There are ways to implement stuff so that you can ensure your app stays within limits -- for example start dropping request when the app reaches throughput limit.