(A document I wrote for my team at $DAYJOB, that might be of interest to the lobste.rs audience. Not super advanced stuff, but I’m convinced many programmers don’t know the concept, because over the years I’ve run into several networking libraries whose APIs don’t allow for backpressure.)
Synchronous APIs are indeed the simplest and most reliable way to implement backpressure. Retrofitting backpressure onto an async system typically means implementing all kinds of dodgy heuristics and trying to estimate various noisy quantities. Here’s one application I made of this principle to a DB system: a typical MVCC DB will have a dedicated GC thread (or possibly several) churning away in the background. If the amount of work this thread is responsible for isn’t carefully monitored, it’s easy for clients to submit work at a higher rate than the GC thread can keep up with. By the time you notice you’re in a hole, it may be too late to dig yourself out, at least without noticeably affecting client latency or availability by throttling new requests. But if you dispense with the background thread and instead schedule all GC work synchronously on the client threads, forcing each client to perform some quantum of work after each transaction commits, before they’re allowed to submit a new transaction, you’ll never get into this state. The only tricky bit is that now you have a whole bunch of different threads concurrently performing GC, and handling this in a lock-free design is a bit complex (but doable: I’ve done it).
In the Verona runtime, we have a backpressure mechanism that mutes a cown[1] if it schedules a behaviour on a cown that is either loaded or muted. A cown becomes loaded if the scheduler does not clear the cown‘s entire message queue when it reaches the front of the scheduling queue. This works well for pipelines and systems with fan-in, but it doesn’t help at all in cases of fan-out (where you’re not loading any cowns in the system, you’re loading the system with cowns). It also doesn’t help you until the next behaviour runs - if a single behaviour is generating a lot of work then it will mute the cown(s) that it runs on but won’t stop (because we don’t want to do stack capture).
We don’t have the GC problems that you allude to because we don’t have global GC. Any region[2] may perform local GC (or ref-counting, or bump-allocation with bulk free, or other policies that we may add later), but the non-interference guarantees from the language eliminate any need to synchronise memory management between regions.
Backpressure is a fascinating research area.
[1] A cown (Concurrent OWNer) is a generalisation of an actor that allows a single behaviour to have exclusive access to N cown, whereas in an actor-model system each behaviour (message + handler) has exclusive access to exactly one actor.
[2] A region can contain an arbitrary object graph but has a single pointer coming in from outside, so each region is owned by either the currently executing behaviour or by a cown (transitively, you can have trees of regions, but the root must be either the stack or a cown).
Synchronous back pressure sounds easy but I’ve seen two common failure modes at work.
First is making the mistake the back pressure is always an active signal or response. If your service has to respond “hey I’m in a bad spot please stop”, if the upstream service slams you so hard that you no longer have capacity to respond then the punishment keeps coming and coming. Teams solve this by saying “oh I’ll dedicate a thread just for back pressure”, but a better answer is thinking about back pressure being an absence rather than a presence. Maybe the host sends periodic health signals somewhere, and if they don’t appear the host is suspect.
The second is the legendary “infinite” queue. Work is precious and I get called out in ops meetings when I return errors so let’s just never return errors. But then you have this massive pile of work clients have probably given up on due to client timeouts that you’re uselessly churning through. The answer here is that throttles are a client error, and in such meetings thinking more holistically about errors and customer experience.
Yes, clients need to interpret timeouts as a form of backpressure and back off appropriately (the mechanisms are well-known). I think that some of the issues with processing work that has already timed out on the client can be addressed by the “deadline not timeout” approach (which solves other issues like coordinating timeout config across a deep decoupled service stack): clients initially calculate a deadline based on their own timeout requirements and submit that deadline with their request. Services transparently propagate that deadline to every other service they call to service the request, all the way down the stack. Then you can just look at a queued request and check if its deadline has expired before processing it.
Blocking bounded queues are indeed a simple way to implement backpressure (if you can actually block producers), but they introduce deadlock risks. “Fail-fast” load shedding tends to be more robust than blocking for this reason. Networking-inspired approaches like CoDel can work well for this.
Now that I think about it, I guess one could say that backpressure is inherent in a pull-based (synchronous, producer-blocking) system, but must be created artificially in a push-based (asynchronous, consumer-blocking) system.
the trouble with synchronous interfaces is that since they have to stay in lock-step, the system can only run at the speed of the slowest link. It produces an effectively single-threaded implementation that can only do one thing at a time
This is true, but typically that single-threaded execution path is isolated to a single unit of work: a request, a job, etc. which are typically numerous in a given system. Is that not the case for the replicator?
No; it’s not good for performance to treat every unit (a revision of a document) separately.
At the database level you get big economies of scale by querying for and updating many documents at once.
At the network level you need to multiplex the stream or else you introduce round-trip delays during every request-response cycle.
By processing a document synchronously, each one ties up a CPU thread (this is C++ not Go). That adds a bunch of overhead, esp. memory, to running them in parallel, which is a big deal on mobile devices.
We ran into a hilarious problem with backpressure a while back: we had a mushed up duplex JSON-RPC connection where the server was sending subscription notifications to the client (not allowed in normal JSON-RPC), and we logically couldn’t backpressure it because the client was also sending requests and expecting responses, and the responses would appear in line with the notifications. So if we tried to backpressure notifications, we might never receive a blocking response, and lock up forever. (And that’s why a service sat at 11GB RAM a few minutes after restart…)
We solved it by moving the subscriptions to a dedicated connection. No request/responses, so backpressure worked fine.
(A document I wrote for my team at $DAYJOB, that might be of interest to the lobste.rs audience. Not super advanced stuff, but I’m convinced many programmers don’t know the concept, because over the years I’ve run into several networking libraries whose APIs don’t allow for backpressure.)
Synchronous APIs are indeed the simplest and most reliable way to implement backpressure. Retrofitting backpressure onto an async system typically means implementing all kinds of dodgy heuristics and trying to estimate various noisy quantities. Here’s one application I made of this principle to a DB system: a typical MVCC DB will have a dedicated GC thread (or possibly several) churning away in the background. If the amount of work this thread is responsible for isn’t carefully monitored, it’s easy for clients to submit work at a higher rate than the GC thread can keep up with. By the time you notice you’re in a hole, it may be too late to dig yourself out, at least without noticeably affecting client latency or availability by throttling new requests. But if you dispense with the background thread and instead schedule all GC work synchronously on the client threads, forcing each client to perform some quantum of work after each transaction commits, before they’re allowed to submit a new transaction, you’ll never get into this state. The only tricky bit is that now you have a whole bunch of different threads concurrently performing GC, and handling this in a lock-free design is a bit complex (but doable: I’ve done it).
In the Verona runtime, we have a backpressure mechanism that mutes a
cown[1] if it schedules a behaviour on acownthat is either loaded or muted. Acownbecomes loaded if the scheduler does not clear thecown‘s entire message queue when it reaches the front of the scheduling queue. This works well for pipelines and systems with fan-in, but it doesn’t help at all in cases of fan-out (where you’re not loading anycowns in the system, you’re loading the system withcowns). It also doesn’t help you until the next behaviour runs - if a single behaviour is generating a lot of work then it will mute thecown(s) that it runs on but won’t stop (because we don’t want to do stack capture).We don’t have the GC problems that you allude to because we don’t have global GC. Any region[2] may perform local GC (or ref-counting, or bump-allocation with bulk free, or other policies that we may add later), but the non-interference guarantees from the language eliminate any need to synchronise memory management between regions.
Backpressure is a fascinating research area.
[1] A
cown(Concurrent OWNer) is a generalisation of an actor that allows a single behaviour to have exclusive access to Ncown, whereas in an actor-model system each behaviour (message + handler) has exclusive access to exactly one actor.[2] A region can contain an arbitrary object graph but has a single pointer coming in from outside, so each region is owned by either the currently executing behaviour or by a
cown(transitively, you can have trees of regions, but the root must be either the stack or acown).Synchronous back pressure sounds easy but I’ve seen two common failure modes at work.
First is making the mistake the back pressure is always an active signal or response. If your service has to respond “hey I’m in a bad spot please stop”, if the upstream service slams you so hard that you no longer have capacity to respond then the punishment keeps coming and coming. Teams solve this by saying “oh I’ll dedicate a thread just for back pressure”, but a better answer is thinking about back pressure being an absence rather than a presence. Maybe the host sends periodic health signals somewhere, and if they don’t appear the host is suspect.
The second is the legendary “infinite” queue. Work is precious and I get called out in ops meetings when I return errors so let’s just never return errors. But then you have this massive pile of work clients have probably given up on due to client timeouts that you’re uselessly churning through. The answer here is that throttles are a client error, and in such meetings thinking more holistically about errors and customer experience.
Yes, clients need to interpret timeouts as a form of backpressure and back off appropriately (the mechanisms are well-known). I think that some of the issues with processing work that has already timed out on the client can be addressed by the “deadline not timeout” approach (which solves other issues like coordinating timeout config across a deep decoupled service stack): clients initially calculate a deadline based on their own timeout requirements and submit that deadline with their request. Services transparently propagate that deadline to every other service they call to service the request, all the way down the stack. Then you can just look at a queued request and check if its deadline has expired before processing it.
I like this recipe for very high utilization, scalable systems:
Go was supposed to encourage designs like this, but I have heard that there is very limited use of channels (fixed size queues) in a lot of Go code
Blocking bounded queues are indeed a simple way to implement backpressure (if you can actually block producers), but they introduce deadlock risks. “Fail-fast” load shedding tends to be more robust than blocking for this reason. Networking-inspired approaches like CoDel can work well for this.
Now that I think about it, I guess one could say that backpressure is inherent in a pull-based (synchronous, producer-blocking) system, but must be created artificially in a push-based (asynchronous, consumer-blocking) system.
This is true, but typically that single-threaded execution path is isolated to a single unit of work: a request, a job, etc. which are typically numerous in a given system. Is that not the case for the replicator?
No; it’s not good for performance to treat every unit (a revision of a document) separately.
We ran into a hilarious problem with backpressure a while back: we had a mushed up duplex JSON-RPC connection where the server was sending subscription notifications to the client (not allowed in normal JSON-RPC), and we logically couldn’t backpressure it because the client was also sending requests and expecting responses, and the responses would appear in line with the notifications. So if we tried to backpressure notifications, we might never receive a blocking response, and lock up forever. (And that’s why a service sat at 11GB RAM a few minutes after restart…)
We solved it by moving the subscriptions to a dedicated connection. No request/responses, so backpressure worked fine.