Wie entwerfe ich eine Jobwarteschlange mit Einschränkungen am besten?

Betrachten Sie die folgende Situation:

• Sie haben ein Programm, das zahlreiche 'Jobs' erstellt, die verarbeitet werden müssen, und diese in eine Warteschlange stellt.
• Sie haben andere Worker-Programme, die den nächsten Job in der Reihe abrufen, damit sie diesen Job verarbeiten können.
• Jeder Job hat eine Kategorie.
• Es kann eine beliebige Anzahl von Kategorien geben.
• Zwei Jobs mit derselben Kategorie können nicht gleichzeitig von separaten Mitarbeitern bearbeitet werden.
• Ein Mitarbeiter kann jeweils einen Auftrag bearbeiten.

Eine herkömmliche Warteschlange würde in dieser Situation nicht funktionieren, da die Möglichkeit besteht, dass mehrere Jobs derselben Kategorie gleichzeitig verarbeitet werden, was nicht zulässig ist.

Sie können den Worker veranlassen, den Job zu überprüfen, der erfasst wird, um festzustellen, ob in dieser Jobkategorie ein anderer Worker gerade verarbeitet wird, und den Job in diesem Fall erneut in die Warteschlange zu senden, um ihn zu einem späteren Zeitpunkt zu verarbeiten. Dies scheint ein ineffizienter Weg zu sein, um dieses Problem zu lösen. Gibt es Datenstrukturen oder Entwurfsmuster, die dieses Problem lösen können?

Wenn Sie weitere Erläuterungen benötigen, lassen Sie es mich bitte wissen.

Dieses Problem besteht aus zwei Teilen.

Erstens: die unbekannte Liste möglicher Kategorien.

Zweitens: Interprozesskommunikation zwischen den Arbeitnehmern, um zu verhindern, dass zwei Jobs derselben Kategorie gleichzeitig verarbeitet werden.

Wenn Sie eine bekannte Liste von Kategorien hatten, können Sie eine Warteschlange und einen Arbeiter pro Kategorie haben.

Bei unbekannten Kategorien können Sie immer noch eine Warteschlange pro Kategorie haben. Wenn Sie jedoch einen Warteschlangenarbeiter pro Kategorie haben, müssen Sie alle Warteschlangen überwachen und neue Mitarbeiter starten, wenn eine neue Kategorie angezeigt wird.

Dies kann mit einem „Meister“ erreicht werden, der Jobs verteilt

Alle Jobs werden in die 'Master'-Warteschlange gestellt.

Kategorie Worker erstellt eine private Warteschlange und registriert sich beim Master als für die Arbeit verfügbar.

Der Hauptarbeiter nimmt Jobs auf, prüft die Kategorie, sucht nach verfügbaren Arbeitern und weist den Job einem von ihnen zu, indem er ihn in seine private Warteschlange stellt.

Der Master kann die dem Arbeiter zugewiesene Kategorie verfolgen.

Der Master nimmt den nächsten Job auf, es ist dieselbe Kategorie, und der Mitarbeiter ist immer noch beschäftigt, sodass er die Jobs in eine kategoriespezifische Warteschlange stellt

Der Master erhält den nächsten Job, es handelt sich um eine neue Kategorie, sodass er sie einem anderen Arbeiter der Kategorie zuweist.

Der Mitarbeiter der Kategorie schließt den Job ab und registriert sich erneut für die Arbeit

Master-Checks mit Warteschlangen und Master-Warteschlange für den nächsten Job und Zuweisung an verfügbare Mitarbeiter der Kategorie.

Wenn ein Kategoriearbeiter während eines Jobs abstürzt, wird er nicht erneut registriert. Der Master kann also eine Timeout-Logik haben, in der er aufgibt und die Kategorien einem anderen Mitarbeiter zuweist.

Sie müssen auch vorsichtig sein, um immer nur einen einzigen Meister zu haben. Dies führt zu einer exklusiven Sperre für die Hauptwarteschlange

Der Nachteil Ihres ineffizienten Vorschlags liegt darin, dass für eine Kategorie zwei Stellen vorhanden sind. Jetzt arbeitet einer ... und alle anderen warten viel.

Sie können dies gut genug machen, indem Mitarbeiter die Warteschlange nach einer nächsten ausführbaren Aufgabe durchsuchen und dann alles andere in die Warteschlange zurückgeben, wenn sie eine finden. Alternativ alles zurückgeben, dann schlafen. Wenn der Schlaf etwas Zufälligkeit und exponentielles Backoff hat, wird das "Besetzt-Warten" nicht zu voll sein.

Für einen effizienteren Ansatz ist ein Mitarbeiter, der sich einen Job schnappt, für die Ausführung dieser Kategorie verantwortlich, bis nichts anderes aus dieser Kategorie mehr zu tun ist. Dann kehren Sie zu einem normalen Arbeiter zurück. Aber es gibt einige Feinheiten.

Denen zu sehen, nehmen wir an , wir können tryund releaseSchlösser (beide non-blocking) und unsere Warteschlange Operationen sind add, getund is_emptymit geteinem Block und Warteoperation zu sein.

Wir nehmen eine allgemeine Warteschlange an und dann für jede Kategorie eine Warteschlange und eine Sperre.

Hier ist der grundlegende Arbeitsablauf.

while obj = get from main queue:
    if try category lock:
        do obj job
        do_whole_category_queue()
    else:
        add obj to category queue
        if try category lock:
            do_whole_category_queue()

wo

procedure do_whole_category_queue
    while not category queue is_empty:
        obj = get from category queue
        do obj job
    release category lock
    if not is_empty category queue:
        if try category lock:
            do_whole_category_queue()

Beachten Sie hier den sorgfältigen Handshake beim Verriegeln. Der Worker testet die Sperre und fügt den Job der Warteschlange hinzu, wenn er gesperrt ist. Aber dann müssen Sie das Schloss erneut testen, um sicherzustellen, dass es immer noch in der Verantwortung eines anderen liegt, die Arbeit tatsächlich zu erledigen. Nur für den Fall, dass der Kategoriearbeiter fertig ist, während Sie die Warteschlangenmanipulation durchgeführt haben.

(Dies ist die Art von Verriegelungsdetail, die Menschen oft vermasseln. Der Fehler ist unmöglich zuverlässig zu reproduzieren, aber er vermasselt sich zufällig und unbeholfen in der Produktion ...)