Ich hatte eben noch einen anderen Gedanken: das ganze muss ja ggf. skalieren; sprich du kannst ggf in die Situation kommen, dass mehrere Server Daten in die Queue schreiben; ob auch mehrere daraus lesen kann ich nicht beurteilen; aber die Möglichkeit würde ich auch in Betracht ziehen.
----
Also wenn du das Problem beheben sollst, dass keine Aufträge mehr verloren gehen, musst du die Daten auf jeden Fall dann persistieren, wenn du sie per REST entgegennimmst damit du per REST einen Fehler zurücksenden kannst, falls die Persistierung nicht geklappt hat (ist gleichbedeutend mit "der Server kann nicht garantieren, dass die Aufgabe abgearbeitet wird.").
Redis ist zwar eine Datenhaltung - wie man da eine saubere Queue hinbekommen kann, weiss ich allerdings nicht. Du könntest tatsächlich eine doppelt verkettete Liste im Redis aufbauen; ob das gut funktioniert musst du dann testen.
Apache Kafka ist eine Leichtgewichtige Message-Queue. Es hat einige Einschränkungen, was aber auch viel Performance und Flexibilität in manchen Anwendungsfällen mit sich bringt. Der Punkt bei Kafka ist, dass du Einträge aus der Queue nicht gezielt entfernen kannst. Sie werden entfernt wenn eine Gültigkeitsdauer überschritten ist oder wenn der Platz ausgeht; je nachdem, was du konfiguriert hast. Daher kannst du mit Kafka nicht richtig garantieren, dass ein Job aus der Queue auch ausgeführt wird, wenn er mal reingekommen ist (entweder weil zu viele Jobs reinkommen oder aber weil die Abarbeitung der vorhergehenden Jobs zu lange braucht).
Deshalb mein Tipp auf eine richtige Message Queue. Du kannst ggf. mit Redis eine nachbauen; aber warum sich den Aufwand geben, wenns das schon fertig gibt?