THEORY: Little's Law and Applying Back Pressure When Overloaded

littles-law-and-back-pressure.md

Applying Back Pressure When Overloaded

[...]

Let’s assume we have asynchronous transaction services fronted by an input and output queues, or similar FIFO structures. If we want the system to meet a response time quality-of-service (QOS) guarantee, then we need to consider the three following variables:

1. The time taken for individual transactions on a thread
2. The number of threads in a pool that can execute transactions in parallel
3. The length of the input queue to set the maximum acceptable latency

max latency  = (transaction time / number of threads) * queue length
queue length = max latency / (transaction time / number of threads)

By allowing the queue to be unbounded the latency will continue to increase. So if we want to set a maximum response time then we need to limit the queue length.

By bounding the input queue we block the thread receiving network packets which will apply back pressure up stream. If the network protocol is TCP, similar back pressure is applied via the filling of network buffers, on the sender. This process can repeat all the way back via the gateway to the customer. For each service we need to configure the queues so that they do their part in achieving the required quality-of-service for the end-to-end customer experience.

One of the biggest wins I often find is to improve the time taken to process individual transaction latency. This helps in the best and worst case scenarios.

[...]

⭐️ Retry strategies and their impact on overloaded systems

⭐️⭐️ Good Retry, Bad Retry: An Incident Story

This article is gold! It shows how some retry techniques might overload a system through a DIDACTIC and well-written story. It covers techniques such as:

1. Simple retry;
2. Retry with backoff;
3. Retry with backoff and jitter;
4. Retry circuit breaker: The service client completely disables retries if the percentage of service errors exceeds a certain threshold (for example, 10%). As soon as the percentage of errors within an arbitrary minute drops below the threshold, retries are resumed. If the service experiences problems, it won’t receive any additional load from retries;
5. Retry budget (or adaptive retry): Retries are always allowed, but within a budget, for example, no more than 10% of the number of successful requests. In case of service problems, it can receive no more than 10% of additional traffic;
6. Retry + Circuit breaker(threshold=10%);
7. Retry + Circuit breaker(threshold=50%);
8. Retry + Deadline propagation;

Both (Retry circuit breaker and Retry budget) options guarantee that in case of service problems, clients will add no more than n% of additional load to it

[...] it’s necessary to differentiate between scenarios when the service is healthy and when it’s experiencing problems. If the service is healthy, it can be retried because errors might be transient. If the service is having issues, retries should be stopped or minimized.

The percentage of retries can be calculated locally without complicating the system with global statistics synchronization.

Ben conducted a simulation: for long-lived clients, local statistics behave identically to global ones, and exponential backoff doesn’t significantly impact amplification.

Based on these findings, Ben decided to propose a new postmortem action item: implementing a retry budget with a 10% limit, in addition to the existing exponential backoff. There’s no need for global statistics synchronization — a local token bucket should be enough.

References that are worth reading

• ⭐️ Google SRE Book: Handling Overload
• ⭐️ Marc's blog: Open and Closed, Omission and Collapse
  • Wiki - Control loop: Open-loop and closed-loop
  • Wiki - Negative feedback
  • Wiki - Control engineering
• ⭐️ Marc's blog: Fixing retries with token buckets and circuit breakers
• ⭐️ Marc's blog: What is Backoff For?
• ⭐️ Marc's blog: Will circuit breakers solve my problems?
• ⭐️ Marc's blog: Metastability and Distributed Systems
  • Metastable Failures in Distributed Systems
• Marc's blog: Simple Simulations for System Builders
  • Marc's blog: Serial, Parallel, and Quorum Latencies

Annotations (pt_BR)

Esse artigo eh PERFEITO, gesuis! 🤩🤩🤩
https://medium.com/yandex/good-retry-bad-retry-an-incident-story-648072d3cee6

O artigo eh sobre como retries podem sobrecarregar seu sistema e como lidar com isso.

Resumo do resumo:

Retries são perigosos, isso já sabemos. Mas como estratégias de retry impactam negativamente na sobrecarga do sistema eh onde fica interessante.

O artigo testa algumas estrategias de retry em alguns cenarios através de simulações. Mas como eh pra resumir o artigo que eh longo, vamos lá...

A estratégia de Retry+backoff+jitter funciona muito bem para sistemas que sejam considerados saudáveis (healthy), ou seja, que estão enfrentando uma sobrecarga temporaria, indisponibilidade parcial, mas principalmente curta, ou seja, que causa transient errors, mas ela não é de muita ajuda em sobrecargas longas (particionamento de rede, crash da aplicação ou alta taxa de erro), pois ela apenas posterga a sobrecarga da aplicação, aumentando o tempo de recovery da aplicação. De forma direta, podemos inferir que, se o tempo de sobrecarga for superior ao tempo que os clients (que fazem retry) estão dispostos a esperar, então os retries estão apenas piorando a situação!

Em contrapartida, Retry adaptativo (Retry Token Bucket) ou Retry Circuit-Breaker (o breaker é a nivel de retry, e não complemento a ele) funcionam para para sobrecargas ou indisponibilidades longas do sistema, e também para curtas - embora com menor taxa de sucesso para sobrecarga curta comparada ao backoff+jitter. Ambas as estratégias, em caso de sobrecarga longa, conseguem diminuir BASTANTE a carga da aplicação, para um percentual baixo da carga original, permitindo a aplicação se recupear mais rapido, que é justamente o que se quer em casos de indisponibilidade.

Outro ponto, é que Retry+backoff+jitter funciona muito bem para mitigação (diminuição ou eliminação) da sobrecarga do sistema em cenários mais estáveis (geralmente closed system), ou seja, cenários com long-lived clients ou número de clients limitados e/ou com execução serial/sequencial das requisições, como por exemplo, jobs em background fazendo polling no sistema ou numa fila. Enquanto as estratégias de Retry Token Bucket e Retry Circuit-Breaker, são ideais para cenários onde não há controle no número de clients (unbounded clients), por exemplo, bordas do sistema onde não se tem controle dos usuários ou dos clients - aqui, o importante é estar ciente que nesse tipo de cenário (geralmente open system), sempre haverá novos clients enviando novas requisições ("first try" - o primeiro request) independente se já existem outros usuários (ou threads) fazendo backoff nesse meio tempo.

O autor conseguiu combinar muito bem os vários artigos de resiliência do Marc Brooker e usar o simulador dele para validar as hipoteses! Ficou simplesmente ANIMAL!

(Eu acompanho o Marc, mas confesso que tive que reler os artigos do Marc para relembrar e conectar melhor os pontos - e gesuis, eh animal demais!)

• ⭐️ Google SRE Book: Handling Overload

  • In a majority of cases (although certainly not in all), we've found that simply using CPU consumption as the signal for provisioning works well, for the following reasons:

    • In platforms with garbage collection, memory pressure naturally translates into increased CPU consumption.
    • In other platforms, it's possible to provision the remaining resources in such a way that they're very unlikely to run out before CPU runs out.

  • Our larger services tend to be deep stacks of systems, which may in turn have dependencies on each other. In this architecture, requests should only be retried at the layer immediately above the layer that is rejecting them. When we decide that a given request can't be served and shouldn't be retried, we use an "overloaded; don't retry" error and thus avoid a combinatorial retry explosion.

• ⭐️ Google SRE Book: Addressing Cascading Failures

  • A cascading failure is a failure that grows over time as a result of positive feedback.

  • Limit retries per request. Don’t retry a given request indefinitely.

  • Consider having a server-wide retry budget. For example, only allow 60 retries per minute in a process, and if the retry budget is exceeded, don’t retry; just fail the request. [...]

  • Think about the service holistically and decide if you really need to perform retries at a given level. In particular, avoid amplifying retries by issuing retries at multiple levels: [...]

  • Use clear response codes and consider how different failure modes should be handled. For example, separate retriable and nonretriable error conditions. Don’t retry permanent errors or malformed requests in a client, because neither will ever succeed. Return a specific status when overloaded so that clients and other layers back off and do not retry.

  • If handling a request is performed over multiple stages (e.g., there are a few callbacks and RPC calls), the server should check the deadline left at each stage before attempting to perform any more work on the request. For example, if a request is split into parsing, backend request, and processing stages, it may make sense to check that there is enough time left to handle the request before each stage.

A tal da "Fila virtual"

• ⭐️ SeatGeek Case: Build a Virtual Waiting Room with Amazon DynamoDB and AWS Lambda at SeatGeek
• Youtube: A POLÊMICA "Fila Virtual" da Caixa na Mega-Sena da Virada! O que poderia melhorar? - By André Secco

Queuing, Backpressure, Single Writer and other useful patterns for managing concurrency

Youtube | ScyllaDB: Resilient Design Using Queue Theory: This talk discusses backpressure, load shedding, and how to optimize latency and throughput.

⭐️ SREcon24 Americas - System Performance and Queuing Theory - Concepts and Application

The #1 rule of scalable systems is to avoid congestion collapse - by @jamesacowling
https://x.com/jamesacowling/status/1934991944234770461

A good metaphor for congestion collapse is to imagine you're a barista at a coffee shop that just got popular. The cashier keeps taking orders and stacking them up higher and higher but you can't make coffees any faster. [...] - by @jamesacowling
https://x.com/jamesacowling/status/1935812480254787819

Linkedin post: When your system is overloaded, you have 2 options...

RabbitMQ: Stack Overflow Behavior

RabbitMQ's "stack overflow behavior" refers to how the system handles situations where a queue's capacity is exceeded, leading to an "overflow" of messages. This is particularly relevant when the rate of messages being published to a queue is significantly higher than the rate at which consumers can process them.

---

Key Aspects of RabbitMQ Queue Overflow Behavior

📏 Maximum Queue Length

RabbitMQ allows configuring a max-length for queues. This limit dictates the maximum number of messages a queue can hold. Setting this limit is crucial for preventing queues from consuming excessive memory and resources.

---

⚙️ Overflow Strategies

When a queue reaches its max-length, RabbitMQ employs a defined overflow strategy to determine how new messages are handled:

• drop-head (Default)
  This strategy, the default for classic queues, discards the oldest message in the queue when a new message arrives and the queue is full. This ensures new messages are accepted while maintaining the queue's length limit.

• reject-publish
  With this strategy, newly published messages are rejected (nacked) by the broker when the queue is full. This signals to the publisher that the message could not be enqueued.

• reject-publish-dlx
  Similar to reject-publish, but rejected messages are routed to a Dead Letter Exchange (DLX) if configured. This allows for specific handling of rejected messages, such as logging or retrying.

---

🚦 Flow Control

Beyond explicit overflow strategies, RabbitMQ implements a credit flow control mechanism. This system monitors the rate of message consumption and can temporarily block publishers if consumers are falling significantly behind, preventing the broker from becoming overwhelmed and potentially crashing due to memory exhaustion.

Note: This is distinct from queue overflow but contributes to overall system stability.

---

⏱️ Message TTL (Time-To-Live)

While not an overflow strategy in itself, setting a message-ttl can help manage queue size by automatically expiring messages after a specified time, regardless of whether they have been consumed. This can prevent queues from growing indefinitely due to slow consumers or unconsumed messages.

---

⚠️ Consequences of Overflow

• Message Loss: If drop-head is used, older messages are discarded.
• Publisher Blocking/Errors: If reject-publish or flow control is active, publishers may experience delays or receive errors when attempting to send messages.
• Resource Consumption: Without proper limits and strategies, an overflowing queue can consume excessive memory on the RabbitMQ server, potentially impacting performance or leading to crashes.

---

✅ Addressing Queue Overflow

• Increase Consumer Capacity
  Scale up the number of consumers or optimize consumer processing logic to handle messages more efficiently.

• Optimize Queue Length
  Adjust the max-length based on system requirements and expected message volume.

• Implement Overflow Strategies
  Choose the appropriate x-overflow strategy (for classic queues) based on desired message handling behavior.

• Utilize Message TTL
  Set TTLs for messages or queues to prevent indefinite message accumulation.

• Monitor and Alert
  Implement monitoring to detect queue overflow conditions and trigger alerts for proactive intervention.

Twitter thread about Cascading Failure and Backpressure Fundamentals

I liked this thread because it talks about 2 (two) useful patterns on the consumer side to handle backpressuring.

However, it didn't discuss system overloading in general. But, on another tweet, he gives an excellent perspective on the (main) trade-off that drives the choice between back-pressure (blocking on input) and load shedding (dropping data on the floor):

When a service is overwhelmed, we have exactly two choices: preserve data or preserve latency.

We either build backpressure to queue and risk collapse, or we shed load and risk data loss.

Which side of this trade-off does your system live on, and can you defend why?

Your Circuit Breaker is Misconfigured - by Shopify blog