Kø

arbeid lagt i rekkefølge for at noe annet skal hente det

Hva det er

En kø er et oppbevaringssted mellom to programmer: den ene siden legger inn meldinger eller jobber, den andre tar dem ut når den er klar, som regel de eldste først. De fleste systemer har flere køer, én per type arbeid. Programmet som legger inn arbeid, er produsenten, programmet som tar det, er konsumenten, og det som lagrer meldingene imellom, er megleren (broker), som kan være en egen server eller en tabell i en database systemet allerede har.

Ordningen gjør at de to sidene slutter å vente på hverandre. En nettforespørsel som trenger å sende en e-post, legger inn en melding og svarer brukeren med en gang; en arbeider (worker) henter meldingen noen øyeblikk senere, og hvis hundre kommer samtidig, tømmer den dem i sitt eget tempo. En topp blir et etterslep, og en avhengighet blir en forsinkelse.

To begreper beskriver hva en kø lover om levering. Det første er kvittering (acknowledgement): en konsument sier fra til megleren når den er ferdig med en melding, og først da fjernes meldingen. I modellen AMQP 0-9-1, som RabbitMQ implementerer, går en melding videre til en annen konsument hvis konsumenten dør før den har kvittert. Det andre er varighet (durability): en varig kø med persistente meldinger overlever en omstart av megleren, og en kø som bare holdes i minnet, gjør det ikke.

Tre nabobegreper er verdt å holde fra hverandre. En meldingskø frakter data mellom tjenester. En jobbkø frakter arbeidsoppgaver til bakgrunnsarbeidere, hver med argumentene sine, en tilstand og et antall forsøk. En logg, modellen bak Apache Kafka, ser ut som en kø utenfra, men beholder hendelsene etter at de er lest, i en oppbevaringsperiode som velges per topic, slik at flere lesere kan spille av den samme historikken. Å lese fra en kø fjerner meldingen; å lese fra en logg flytter bare leserens posisjon.

En kø trenger ikke være et eget produkt i det hele tatt. PostgreSQL kan spille rollen med en tabell med jobber og en spørring som gjør krav på neste rad og hopper over rader en annen arbeider allerede har låst. Håndboken nevner kø-lignende tabeller som grunnen til at leddet SKIP LOCKED finnes:

WITH next AS (
  SELECT id
    FROM jobs
   WHERE state = 'available'
   ORDER BY id
   LIMIT 1
     FOR UPDATE SKIP LOCKED
)
UPDATE jobs
   SET state = 'running',
       attempt = attempt + 1
  FROM next
 WHERE jobs.id = next.id
RETURNING jobs.id, jobs.args;

Hvorfor det er viktig

En kø avgjør hva en bruker venter på. Arbeid som legges i en kø, skjer etter at svaret er sendt, så en side som utløser en e-post, en PDF, en ny indeksering for søk og en omberegning, kan svare på den tiden det tar å skrive fire rader, og de fire trege oppgavene blir ferdige bak den. For en kjøper er det forskjellen på en utsjekking som svarer på noen hundre millisekunder, og en som svarer når e-postserveren er klar.

Den avgjør også hva som overlever en feil. Arbeid som startes i en bakgrunnstråd, lever i minnet til den prosessen, og en produksjonssetting som starter prosessen på nytt, tar arbeidet med seg og etterlater ikke noe spor av at det noen gang skulle gjøres. Arbeid i en varig kø er i stedet en post: det kan prøves på nytt, inspiseres og telles.

Den skiller også to hastigheter. Produsenter beveger seg i takt med trafikken som kommer inn; konsumenter i takt med den tregeste tjenesten de kaller. En kø mellom dem tar opp forskjellen, og dybden i køen blir et av de mest ærlige tallene et system kan rapportere. En kø som har vokst i en time, sier at konsumentene taper terreng, uansett hva grafen for prosessoren antyder.

Kostnadene kommer sammen med fordelene. Arbeidet ligger nå ute av syne mellom det sendes og det er gjort. Levering skjer nesten alltid minst én gang, så en konsument må tåle å se en melding to ganger. Rekkefølgen er svakere enn den ser ut. Og en egen megler er én server til som skal driftes, sikres, overvåkes og oppgraderes.

Slik ser det ut i praksis

Det trege arbeidet på én plattform ble flyttet ut av forespørselsløpet: å sende e-post, bygge en søkeindeks på nytt, generere dokumenter, beregne rangeringer på nytt. Arbeid som overlates til en goroutine, forsvinner når prosessen starter på nytt midt i en produksjonssetting, så arbeidet ble flyttet over i en jobbkø i River som holdes i PostgreSQL. Databasen var allerede det autoritative kildesystemet, og det gjør det å legge en jobb i køen til en del av den samme transaksjonen som dataene jobben gjelder. Det plattformen fikk, er nye forsøk og en historikk noen kan åpne og lese; begrensningen siden selv oppgir, er at en kø inne i databasen ikke skalerer i det uendelige.

I en macOS-app bygd over et C-bibliotek var køen der for å holde rekkefølgen. Den blokkerende hendelsesløkken i biblioteket sender ut hendelser i en rekkefølge som betyr noe, fordi en redigering må komme etter meldingen den redigerer. Å starte én oppgave per hendelse lar kjøretiden planlegge dem i vilkårlig rekkefølge, så en redigering kan gå forbi meldingen den viser til. Designet som ble levert, har én produsenttråd, én konsument og én kø mellom dem, fulgt av ett enkelt hopp over til main actor. Rekkefølgen holder fordi det finnes nøyaktig én vei gjennom. Prisen er parallellitet: hver hendelse går gjennom den ene konsumenten.

En kø kan også gjøre skade. I en applikasjon ble en hendelsesstrøm konsumert uten noen grense: hendelsene kom raskere enn grensesnittet kunne behandle dem, og etterslepet ble beholdt. Den køen var én av årsakene til at minnet steg med rundt 41 MB i sekundet; maskinen hadde 36 GB, og hendelsen som ble registrert, nådde 111 GB komprimerte sider. Hver ubegrenset kodevei fikk en grense, med en eksplisitt regel for en full buffer, fordi, som siden sier det, én begrenset kø ved siden av tre ubegrensede ikke er en løsning. En regresjonstest sjekker nå at minnetaket holder.

Hvor det går galt

Trøbbel med køer viser seg sent og et annet sted, fordi arbeidet er ute av syne med vilje.

Etterslepet vokser til minnet eller disken tar slutt. En kø uten grense tar imot arbeid raskere enn det blir gjort, og beholder differansen. Gi hver kø en maksimal lengde, og bestem på forhånd hva som skjer ved den lengden: brems produsenten, avvis nytt arbeid eller kast det eldste. Følg så med på to tall, dybden og alderen på den eldste meldingen, fordi en kort kø med svært gamle meldinger er like ille som en lang.

Den samme meldingen behandles to ganger. En konsument blir ferdig med arbeidet og dør før den kvitterer; megleren leverer, helt korrekt, meldingen på nytt. Dokumentasjonen til RabbitMQ ber konsumenter regne med nye leveringer og være skrevet slik at de er idempotente. Gi hver melding en identifikator, og registrer identifikatorene som allerede er behandlet, i den samme transaksjonen som selve arbeidet. Skriveren i notatet om lynsalg uten oversalg er bygd rundt akkurat den antakelsen.

Meldinger kommer i en annen rekkefølge enn de ble sendt i. Parallelle konsumenter, forhåndshenting (prefetch) og nye forsøk som legger en feilet melding bak nyere meldinger, stokker alle om på arbeidet. Når rekkefølgen betyr noe, send alt som gjelder én konto eller én ordre, gjennom den samme partisjonen eller den samme konsumenten. Kafka gjør dette etter nøkkel, med den kostnaden at én travel nøkkel bare beveger seg så raskt som én konsument.

Én dårlig melding blokkerer eller går i løkke for alltid. En melding med et innhold som krasjer konsumenten hver gang, legges tilbake i køen, leveres på nytt og krasjer den igjen. Sett et tak på forsøkene, og flytt en melding som har brukt opp alle, til et eget sted der en person kan se på den. RabbitMQ kaller dette dead-lettering og bruker det på avviste meldinger, utløpte meldinger og meldinger som ville gått over en lengdegrense.

Arbeid forsvinner ved omstart. En kanal, en liste i minnet eller en bakgrunnstråd er en kø som mister alt ved en omstart. I AMQP holder heller ikke en varig kø alene: meldingene må også publiseres som persistente. Avgjør for hver type arbeid om det er akseptabelt å miste det.

Databasen og køen er uenige. En tjeneste skriver en rad, publiserer så en melding og krasjer mellom de to; nå finnes det ene uten det andre. Enten holder du køen i den samme databasen, så en jobb blir synlig for arbeiderne først når transaksjonen dens committes, slik River oppfører seg, eller du skriver meldingen inn i en outbox-tabell i den transaksjonen og publiserer den derfra.

Les mer

Ordliste