Eksponentiel backoff

Hvad det er

Eksponentiel backoff er en regel for, hvor længe man venter, før man
prøver igen. Efter hvert mislykket forsøg ganges ventetiden med en
fast faktor, oftest to, indtil den når et loft: ét sekund, så to,
fire, otte og så videre. Reglen bor i klienten, men den findes for
den tjenestes skyld, som klienten kalder. En server, en netværksvej
eller en database, der fejler under for høj belastning, kommer sig
ikke hurtigere af at blive spurgt igen med det samme. Den kommer
sig, når de, der kalder den, letter trykket, og en ventetid, der
vokser med hver fejl, får dem til at lette det mere, jo længere
problemerne varer.

Det ældste og mest udbredte eksempel findes i TCP. RFC 6298,
Standards Track-dokumentet fra juni 2011, der fastlægger, hvordan
TCP beregner sin timeout for genudsendelse, sætter timeouten til ét
sekund, før den første rundturstid er målt, og siger, at en beregnet
værdi under ét sekund bør rundes op. Hver gang timeren udløber, og
et segment skal sendes igen, skal værten fordoble timeouten. En øvre
grænse er tilladt, så længe den er mindst 60 sekunder. Når en ny
måling af rundturstiden kommer ind, beregnes timeouten igen ud fra
målingerne, og det kan bringe den helt ned igen efter en række
fordoblinger. Algoritmen går tilbage til Van Jacobsons artikel
Congestion Avoidance and Control fra 1988, og RFC'ens afsnit om
sikkerhed siger, hvad der står på spil: internettet er afhængigt af
en korrekt timer for genudsendelse for at holde netværket stabilt og
undgå congestion collapse, et sammenbrud under overbelastning.

I applikationskode kommer den samme idé med en håndfuld
indstillinger: en første ventetid, en multiplikator, en maksimal
ventetid, hvor væksten stopper, og en grænse for antallet af forsøg
eller for den samlede tid, der bruges på nye forsøg. Skrevet ud er
ventetiden efter den n'te fejl den mindste af loftet og basis ×
multiplikator i n'te potens, talt fra nul. Den analyse fra AWS, der
omtales nedenfor, kalder det capped exponential backoff, altså
eksponentiel backoff med loft. Loftet betyder mere, end man skulle
tro. Fordobler man en ventetid på ét sekund ti gange, får man 1.024
sekunder, mere end 17 minutter, og det er længere, end de fleste vil
vente på noget som helst.

Den sidste indstilling er jitter, et tilfældigt element i hver
ventetid. Protokollen for connection backoff i gRPC, der beskriver,
hvordan gRPC-klienter forbinder igen efter en mislykket forbindelse,
starter ved ét sekund, ganger med

1,6, holder op med at vokse ved 120 sekunder og bruger en jitter på
0,2, så hver ventetid flyttes tilfældigt op eller ned med op til 20
i%. Den giver også hvert forbindelsesforsøg mindst 20 sekunder til at		engineer.company	70
blive gennemført, og den nulstiller backoff til startværdien, når
serveren har accepteret en forbindelse, hvilket den regner for at
ske, når SETTINGS-rammen ankommer. Protokollen tillader andre
implementeringer, for eksempel på en mobiltelefon, der skal vågne så
sjældent som muligt, men kræver, at backoffs, der er startet på
samme tidspunkt, spredes, og at ingen implementering forsøger at
forbinde væsentligt oftere.

Hvorfor det betyder noget

Et nyt forsøg er ekstra belastning, og det kommer på det værst
tænkelige tidspunkt: netop når det, der bliver kaldt, er ved at
fejle. Bliver en tjeneste langsommere, fordi den er overbelastet, og
prøver alle, der kalder den, igen med det samme, stiger
belastningen, mens kapaciteten falder. Dokumentationen til Google
Cloud Storage regner derfor nye forsøg uden backoff for et
antimønster, fordi øjeblikkelige eller meget korte genforsøg kan
føre til kaskadefejl, hvor én fejl udløser andre. Backoff gør det
nye forsøg fra en forstærker til en bremse: jo længere problemerne
varer, jo mindre bidrager hver klient til dem.

Backoff alene er ikke nok, for klienter, der fejler samtidig, venter
også samtidig. I Exponential Backoff And Jitter, udgivet af AWS i
marts 2015, simulerede Marc Brooker mange klienter, der brugte
optimistisk samtidighedskontrol til at opdatere den samme række i en
fjern database. Når alle klienter konkurrerede i hver runde, voksede
det samlede arbejde med kvadratet på antallet af klienter.
Eksponentiel backoff med loft hjalp kun lidt. Kaldene kom stadig i
klynger med stille huller imellem, så konkurrencen faldt næsten
ikke. Da han tilføjede jitter ved at trække hver ventetid tilfældigt
mellem nul og den eksponentielle værdi med loft, forsvandt hullerne,
kaldene kom i en nogenlunde jævn strøm, og med 100 konkurrerende
klienter faldt antallet af kald til under det halve. Blandt de
varianter, han sammenlignede, var backoff uden jitter med Brookers
ord »den klare taber«. Han var også tydelig om grænsen: ingen af
metoderne ændrer ved, at arbejdet vokser med kvadratet på
konkurrencen. Jitter mindsker spildet, men fjerner ikke konflikten.
I en opdatering fra maj

2023 skriver indlægget, at de fleste AWS SDK'er nu har eksponentiel
backoff og jitter indbygget i deres retry-tilstande standard og
adaptive.

Backoff afgør, hvornår man prøver igen, ikke om det er sikkert at
gøre det. Dokumentationen til Cloud Storage stiller to spørgsmål
først. Det ene er, om svaret tyder på et forbigående problem:
HTTP-statuskoderne 408, 429 og 5xx, timeouts på sockets og afbrudte
TCP-forbindelser. Det andet er, om forespørgslen er idempotent. En
list-operation kan gentages frit. Det kan oprettelsen af en
Pub/Sub-notifikation ikke, for hvert vellykket kald opretter en ny
notifikation. Imellem de to ligger betinget idempotente operationer,
der bliver sikre at gentage, når de har en forudsætning med, for
eksempel en upload, der kun lykkes, hvis objektets generationsnummer
stadig er det, klienten forventer.

Nogle gange ved serveren bedre end klientens formel. Headerfeltet
Retry-After, der er defineret i RFC 9110, fortæller klienten, hvor
længe den bør vente, før den sender en ny forespørgsel, enten som en
dato eller som et antal sekunder, og sammen med et 503 Service
Unavailable-svar siger det, hvor længe tjenesten regner med at være
utilgængelig. Statuskoden 429 Too Many Requests fra RFC 6585, der
signalerer ratebegrænsning, må have det samme felt med. En klient
med en backoff-løkke kan bruge den værdi i stedet for sin egen
beregnede ventetid, for den kommer fra den side, der kan se sin egen
belastning.

Sådan ser det ud i praksis

En løkke med nye forsøg, eksponentiel backoff med loft og fuld
jitter fylder kun nogle få linjer i Python:

```python
import random
import time

class TransientError(Exception):
    """En timeout, et 408-, 429- eller 5xx-svar eller en tabt forbindelse."""

def call_with_backoff(op, attempts=5, base=1.0, cap=30.0):
    for attempt in range(attempts):
        try:
            return op()
        except TransientError:
            if attempt == attempts - 1:
                raise
            ceiling = min(cap, base * 2**attempt)
            time.sleep(random.uniform(0, ceiling))
```

Med disse værdier er fem forsøg adskilt af fire ventetider, hvis
lofter er 1, 2,

4 og 8 sekunder. Løkken sover derfor højst 15 sekunder, før den
giver op, og i gennemsnit omkring 7,5 sekunder, fordi hver ventetid
trækkes jævnt mellem nul og dens loft. Kun `TransientError` får et
nyt forsøg; en afvist autorisation eller en forkert udformet
forespørgsel kaster en undtagelse med det samme. Og løkken gentager,
hvad `op` end gør, så `op` skal være sikker at gentage: en læsning
eller en skrivning, som serveren kan genkende som en gentagelse.

Klientbiblioteker leverer deres egne udgaver af denne løkke, og
deres standardværdier er forskellige, selv for den samme tjeneste.
Til Cloud Storage starter Python-klienten ved ét sekund, fordobler
hver ventetid op til 60 sekunder og giver op efter en standardfrist
på 120 sekunder. C++-klienten starter også ved ét sekund og
fordobler, men venter op til fem minutter mellem forsøgene og bliver
ved med at prøve i op til 15 minutter, mere end syv gange så længe.
Den prøver også igen med operationer, der aldrig er idempotente,
medmindre programmet vælger en streng idempotenspolitik.
Kommandolinjeværktøjet gcloud bruger det, Google kalder truncated
binary exponential backoff, med op til 32 nye forsøg som standard.
To programmer, der kalder det samme API med den samme fejl, kan
derfor melde den efter to minutter eller efter et kvarter, alt efter
hvilket sprog de er skrevet i.

Ventetiden behøver ikke at blokere en tråd. I baggrundsarbejde kan
et job, der fejler, sættes tilbage i en kø med et senere tidspunkt
for udførelse, og så bliver backoff en egenskab ved jobbet og ikke
ved en proces, der sover. Det er det naturlige sted for den, når
ingen sidder og venter på resultatet.

I e-mail med failover og leveringslog, fra 2025, hører backoff til
på systemets asynkrone side. Mailen går ud gennem tre udbydere, med
SendGrid som den primære og SMTP2GO og Azure Communication Services
bag den, og der skiftes automatisk mellem dem. Selve afsendelsen går
gennem en klient med en timeout på 30 sekunder, mens den asynkrone
levering prøver igen med backoff, så en kort forstyrrelse ikke får
en besked til at gå tabt. Siden opsummerer resultatet: når en
udbyder har en dårlig eftermiddag, bliver leveringen forringet i
stedet for at gå ned. Den nævner også prisen, nemlig tre
integrationer at holde i gang i stedet for én.

Hvor det går galt

Alle klienter venter lige længe. Uden jitter prøver klienter, der
fejlede sammen, igen sammen, og serveren ser den samme top igen
efter ét, to, fire og otte sekunder. Brookers simulering viste, at
almindelig eksponentiel backoff af den grund næsten ikke mindskede
konkurrencen. Tilføj jitter: i hans sammenligning skar både Full
Jitter og Decorrelated Jitter markant ned på klienternes arbejde og
serverens belastning, og begge er et fornuftigt standardvalg.

Ventetiden har intet loft, eller forsøgene har ingen ende. En
fordobling uden loft passerer 17 minutter efter ti fejl, og en løkke
uden grænse holder en forespørgsel i live længe efter, at den, der
ventede på svaret, er gået videre. Google regner det at ignorere
grænser for nye forsøg for et antimønster: at prøve igen i det
uendelige kan opbruge programmets ressourcer eller blive ved med at
sende forespørgsler til en tjeneste, der ikke kommer sig uden
indgriben. Sæt en maksimal ventetid og en samlet frist, der er
afstemt efter den, der kalder: kort, hvor latenstiden betyder noget,
og længere for batchjob.

Permanente fejl får nye forsøg. En afvist autorisation eller en
ugyldig forespørgsel fejler på samme måde ved hvert forsøg. Et nyt
forsøg udskyder kun fejlen, og uden en grænse kan klienten ende i en
uendelig løkke, som dokumentationen til Cloud Storage advarer om.
Sortér fejlene i forbigående og permanente før løkken, prøv kun de
forbigående igen, for eksempel 408, 429, 5xx og afbrudte
forbindelser, og log resten med deres årsag.

En ikke-idempotent operation gentages i blinde. Fik en forespørgsel
timeout, efter at serveren allerede havde udført den, gentager et
nyt forsøg handlingen, hvad Googles liste over antimønstre beskriver
som utilsigtede overskrivninger eller sletninger af data. Prøv kun
idempotente operationer igen, gør skrivninger betingede, hvor API'et
tillader det, og sørg ellers for, at den modtagende side kan
genkende en dublet.

Nye forsøg stables i flere lag. Foretager programmet tre forsøg, og
foretager klientbiblioteket under det tre forsøg for hvert af de
forsøg, bliver én fejl til ni forsøg, hvilket er Googles eget
eksempel, og hvert yderligere lag, der prøver igen på egen hånd,
ganger antallet op igen. Dokumentationen tilføjer, at så mange nye
forsøg kan få forespørgslerne droslet og give højere latenstid uden
at forbedre andelen af vellykkede kald. Prøv igen i ét lag, som
regel biblioteket, og slå nye forsøg fra eller ned i de andre.

Backoff nulstilles aldrig, eller ingen ser det. En klient, der
beholder sin sidste, lange ventetid efter en genopretning, sidder
maksimummet ud ved den næste lille fejl; gRPC nulstiller til den
første backoff, så snart en forbindelse er accepteret, og TCP
beregner sin timer igen ud fra nye målinger. Nulstil efter en
succes. Og fordi nye forsøg skjuler problemerne for brugerne,
skjuler de dem også for teamet. Tæl dem i overvågningen, og udløs en
alarm, når andelen af nye forsøg stiger, for en afhængighed, der
skal bruge tre forsøg pr. kald, fejler allerede.

Læs mere

  * RFC 6298: Computing TCP's Retransmission Timer — reglerne fra
Standards Track for TCP's timeout for genudsendelse, herunder
fordoblingen, hver gang timeren udløber.

  * gRPC Connection Backoff Protocol — algoritmen for
genforbindelse, dens fem parametre med deres værdier, og hvornår
backoff nulstilles.

  * Exponential Backoff And Jitter — Marc Brookers simulering fra
2015 af konkurrerende klienter, der sammenligner backoff uden jitter
med Full, Equal og Decorrelated Jitter.

  * Retry strategy — hvad Cloud Storage anser for sikkert at prøve
igen, standardværdierne i hvert klientbibliotek og fem antimønstre
for nye forsøg.

  * RFC 9110: HTTP Semantics — headerfeltet Retry-After, som en
server bruger til at fortælle en klient, hvor længe den skal vente
før sin næste forespørgsel.

hDenne side på nettet	URL:https://engineer.company/da/glossary/exponential-backoff/	engineer.company	70
