Auf der Suche nach einem verteilten Verriegelungsmuster

10

Ich muss einen benutzerdefinierten rekursiven Objektsperrmechanismus \ Muster für ein verteiltes System in C # entwickeln. Im Wesentlichen habe ich ein System mit mehreren Knoten. Jeder Knoten verfügt über exklusive Schreibberechtigungen für n- Status-Teile. Der gleiche Status ist auch in schreibgeschützter Form auf mindestens einem anderen Knoten verfügbar . Einige Schreibvorgänge / Aktualisierungen müssen über alle Knoten hinweg atomar sein, während andere Aktualisierungen durch Hintergrundreplikationsprozesse, Warteschlangen usw. konsistent werden.

Für die atomaren Aktualisierungen suche ich nach einem Muster oder Beispielen, mit denen ich ein Objekt effizient als für Schreibvorgänge gesperrt markieren kann , die ich dann verteilen, festschreiben, zurücksetzen usw. kann. Da das System ein hohes Maß an Parallelität aufweist, habe ich Ich gehe davon aus, dass ich in der Lage sein muss, Sperren zu stapeln, die entweder eine Zeitüberschreitung aufweisen oder abgewickelt werden, sobald die Sperren freigegeben werden.

Die Transaktions- oder Messaging-Teile stehen nicht im Mittelpunkt dieser Frage, aber ich habe sie für einen zusätzlichen Kontext bereitgestellt. Wenn dies gesagt ist, können Sie gerne artikulieren, welche Nachrichten Ihrer Meinung nach benötigt werden, wenn Sie möchten.

Hier ist ein vages Beispiel von dem, was ich mir vorgestellt habe, obwohl ich offen für neue Ideen bin, abgesehen von der Implementierung ganz neuer Produkte

thing.AquireLock(LockLevel.Write);

//Do work

thing.ReleaseLock();

Ich dachte darüber nach, Erweiterungsmethoden zu verwenden, die ungefähr so ​​aussehen könnten

public static void AquireLock(this IThing instance, TupleLockLevel lockLevel)
{ 
    //TODO: Add aquisition wait, retry, recursion count, timeout support, etc...  
    //TODO: Disallow read lock requests if the 'thing' is already write locked
    //TODO: Throw exception when aquisition fails
    instance.Lock = lockLevel;
}

public static void ReleaseLock(this IThing instance)
{
    instance.Lock = TupleLockLevel.None;
}

Um ein paar Details zu klären ...

  • Alle Kommunikationen sind TCP / IP unter Verwendung eines binären Anforderungs- / Antwortprotokolls
  • Es gibt keine Zwischentechnologien wie Warteschlangen oder Datenbanken
  • Es gibt keinen zentralen Masterknoten. In diesem Fall wird die Sperranordnung vom Initiator der Sperre und vom Partner definiert, der die Anforderung mit einer Zeitüberschreitung zur Steuerung ihres Verhaltens berücksichtigt

Hat jemand irgendwelche Vorschläge?

JoeGeeky
quelle
Schlösser sind in den meisten Systemen Standard. Ich denke, es ist auch für C # da. (Ein Google-Suchergebnis: albahari.com/threading/part2.aspx ) Versuchen Sie, etwas zu erreichen, das über grundlegende Mutex- oder Semaphoren hinausgeht?
Dipan Mehta
2
@ DipanMehta Sorry, ich hätte das klarer ansprechen sollen. Die Knoten, die ich erwähnt habe, sind Maschinen in einem Netzwerk. Nach meinem Verständnis von Mutex und Semaphoren handelt es sich um maschinenweite Sperren ( z. B. prozessübergreifende Sperren) und nicht um Sperren, die sich zwischen Computern in einem Netzwerk erstrecken können.
JoeGeeky
@JoeGeeky Ihre Frage ist hier themenbezogen und für Stack Overflow möglicherweise zu theoretisch . Wenn Sie es dort erneut fragen möchten, können Sie dies, aber Sie möchten eine stärker auf den Code ausgerichtete Formulierung.
Adam Lear

Antworten:

4

Danke für die Klarstellungen.

In diesem Fall würde ich die Verwendung eines Publish / Subscribe-Modells empfehlen. Googles Chubby Distributed Locking-Protokoll (eine Implementierung von Paxos )

Ich habe noch nie Paxos (oder Chubby) verwendet, aber es scheint eine Open - Source - Implementierung zu sein hier .

Wenn dies nicht funktioniert, können Sie Ihre eigene Version von Paxos implementieren, indem Sie beispielsweise einen der üblichen Verdächtigen in Bezug auf Messaging-Bibliotheken verwenden: die Zero Message Queue Library , RabbitMQ oder ActiveMQ .


Vorherige Antwort:

Die meisten Vorschläge zu SO ( [A] , [B] ) verwenden eine Nachrichtenwarteschlange, um eine maschinenübergreifende Sperrung zu erreichen.

Ihre AcquireLockMethode würde etwas, das das Sperrobjekt identifiziert, in die Warteschlange verschieben und vor dem Erfolg nach früheren Instanzen von Sperren suchen. Ihre ReleaseLockMethode würde das Sperrobjekt aus der Warteschlange entfernen.

SO Benutzer atlantis schlägt vor, in diesem Beitrag , Jeff Key Post für einige Details.

Peter K.
quelle
Vielen Dank, aber diese Lösungen wären nicht geeignet, da ich keinen zentralen Master, keine Datenbank oder Warteschlange habe. Ich habe die Frage mit einigen zusätzlichen Details aktualisiert, um einige dieser Details zu klären.
JoeGeeky
Ich kann diese Produkte nicht direkt verwenden, da es bereits ein genau definiertes Protokoll gibt, das ich für die gesamte Kommunikation zwischen Knoten verwenden muss, aber Chubby und Paxos haben möglicherweise genau definierte Muster, aus denen ich lernen kann. Ich werde einen Blick darauf werfen.
JoeGeeky
@JoeGeeky Ja, der Paxos-Link verfügt über Sequenzdiagramme, mit denen Sie ihn möglicherweise über Ihren bevorzugten Kommunikationslink implementieren können.
Peter K.
Obwohl dies keine direkte Antwort war, half mir das Lesen aller Dinge von Chubby und Paxos, meine eigene Lösung zu definieren. Ich habe diese Tools nicht verwendet, konnte aber anhand einiger ihrer Konzepte ein vernünftiges Muster definieren. Vielen Dank.
JoeGeeky
@ JoeGeeky: Gut zu hören, dass es zumindest eine Hilfe war. Danke für die Zecke.
Peter K.
4

Mir scheint, Sie haben hier ein paar gemischte Technologien:

  • Kommunikation (auf die Sie sich im Wesentlichen als 100% zuverlässig verlassen ... was tödlich sein kann)

  • Sperren / gegenseitiger Ausschluss

  • Timeouts (zu welchem ​​Zweck)?

Ein Wort der Warnung: Zeitüberschreitungen in verteilten Systemen können mit Gefahren und Schwierigkeiten verbunden sein. Wenn sie verwendet werden, müssen sie sehr sorgfältig eingestellt und verwendet werden, da die wahllose Verwendung von Zeitüberschreitungen kein Problem behebt, sondern nur die Katastrophe aufschiebt. (Wenn Sie sehen möchten, wie Zeitüberschreitungen verwendet werden sollen, lesen und verstehen Sie die Dokumentation zum HDLC-Kommunikationsprotokoll. Dies ist ein gutes Beispiel für eine geeignete und clevere Verwendung in Kombination mit einem cleveren Bitcodierungssystem, mit dem beispielsweise IDLE-Leitungen erkannt werden können.) .

Eine Zeit lang arbeitete ich in verteilten Systemen mit mehreren Prozessoren, die über Kommunikationsverbindungen (nicht TCP, etwas anderes) verbunden waren. Eines der Dinge, die ich gelernt habe, war, dass es als grobe Verallgemeinerung einige gefährliche Orte mit mehreren Programmen gibt:

  • Das Vertrauen in Warteschlangen endet normalerweise in Tränen (wenn sich die Warteschlange füllt, sind Sie in Schwierigkeiten. AUSSER Sie können eine Warteschlangengröße berechnen, die niemals gefüllt wird. In diesem Fall könnten Sie wahrscheinlich eine Lösung ohne Warteschlange verwenden.)

  • Das Vertrauen in das Sperren ist schmerzhaft. Versuchen Sie zu überlegen, ob es einen anderen Weg gibt (wenn Sie das Sperren verwenden müssen, lesen Sie in der Literatur nach, dass das verteilte Sperren mit mehreren Prozessoren in den letzten zwei bis drei Jahrzehnten Gegenstand vieler acedemischer Veröffentlichungen war).

Wenn Sie mit dem Sperren fortfahren müssen, dann:

Ich gehe davon aus, dass Sie Timeouts nur als Mittel zur Wiederherstellung des letzten Auswegs verwenden - dh zur Erkennung eines Fehlers des zugrunde liegenden Kommunikationssystems. Ich gehe weiter davon aus, dass Ihr TCP / IP-Kommunikationssystem eine hohe Bandbreite hat und als niedrige Latenz angesehen werden kann (idealerweise Null, aber dies passiert nie).

Was ich vorschlagen würde, ist, dass jeder Knoten eine Konnektivitätsliste anderer Knoten hat, mit denen er eine Verbindung herstellen kann. (Knoten würden sich nicht darum kümmern, woher eine Verbindung kommt.) Die Population der Tabellen, zu denen ein Knoten eine Verbindung herstellen kann, bleibt als separate Sache zum Aussortieren übrig. Sie haben nicht gesagt, ob dies statisch oder anderweitig festgelegt wäre. Praktisch ignoriert werden auch Dinge wie die Zuweisung der IP-Portnummern, bei denen Verbindungen zu einem Knoten kommen würden - es kann gute Gründe geben, Anforderungen nur an einem einzelnen Port oder an mehreren Ports anzunehmen. Dies muss sorgfältig abgewogen werden. Zu den Faktoren gehören implizite Warteschlangen, Reihenfolge, Ressourcennutzung, Betriebssystemtyp und Funktionen.

Sobald Knoten wissen, mit wem sie eine Verbindung herstellen, können sie eine Sperranforderung an diesen Knoten senden und müssen von einer Sperrantwort von diesem Remote-Knoten eine Rückmeldung erhalten. Sie können diese beiden Operationen in einen Wrapper packen, damit er atomar aussieht. Dies hat zur Folge, dass Knoten, die eine Sperre erwerben möchten, einen Anruf wie folgt tätigen:

if (get_lock(remote_node) == timeout) then
  {
    take some failure action - the comms network is down
  }

/* Lock is now acquired - do work here */

if (release_lock(remote_node) == timeout) then
  {
    take some failure action - the comms network is down
  }

Die Aufrufe get_lock und release_lock sollten ungefähr so ​​aussehen (im Prinzip):

send_to_remote_node(lock_request)
get_from_remote_node_or_timeout(lock_reply, time)
if (result was timeout) then
  return timeout
else
  return ok

Bei einem verteilten Schließsystem müssen Sie sehr darauf achten, dass die Arbeitseinheiten, die ausgeführt werden, während eine Sperre gehalten wird, klein und schnell sind, da möglicherweise viele entfernte Knoten auf eine Sperre warten. Dies ist effektiv ein Stop-and-Wait-Multiprozessor- / Kommunikationssystem, das robust ist, aber nicht die höchstmögliche Leistung aufweist.

Ein Vorschlag ist, einen völlig anderen Ansatz zu wählen. Können Sie einen Remoteprozeduraufruf verwenden, bei dem jeder RPC-Aufruf ein Informationspaket enthält, das vom Empfänger verarbeitet werden kann und das die Notwendigkeit von Sperren beseitigt?


Beim erneuten Lesen der Frage sieht es so aus, als ob Sie sich nicht wirklich mit der Kommunikationsseite der Dinge befassen möchten, sondern nur Ihr Sperrproblem lösen möchten.

Meine Antwort scheint daher etwas unangebracht zu sein, aber ich glaube, Sie können Ihr Verriegelungsproblem nicht lösen, ohne auch die Teile darunter richtig zu machen. Analogie: Wenn man ein Haus auf einem schlechten Fundament baut, fällt es herunter ... Irgendwann.

schnell_now
quelle
1
Die Timeout-Semantik dient hauptsächlich dazu, Knoten zu behandeln, die aus dem Netzwerk verschwinden, oder große Rückstände in Sperrstapeln zu behandeln. Dies begrenzt die Zeit, die blockiert wird, während auf das Erhalten einer Sperre gewartet wird, und bietet denjenigen, die die Sperre anfordern, eine Gelegenheit um andere Prozesse inmitten unerwarteter Verzögerungen, Ausfälle usw. zu starten. Außerdem würde dies verhindern, dass etwas für immer gesperrt wird, falls etwas ausfällt. Ich schätze Ihre Bedenken, obwohl ich derzeit keine Alternativen sehe, da irgendwann etwas scheitern wird
JoeGeeky
Um mit einigen Ihrer anderen Kommentare zu sprechen, verwende ich keine Warteschlangen an sich (im Sinne der asynchronen Kommunikation), obwohl ich erwarten würde, dass Sperren basierend auf einem FIFO-Muster gestapelt und freigegeben werden. Ich habe nicht ganz in Einklang gebracht, wie dies in Bezug auf das erforderliche Anforderungs- / Antwortmuster funktionieren wird, außer dass dies in irgendeiner Weise blockiert werden muss und Teil eines größeren Handshakes sein muss. Im Moment arbeite ich den gestapelten Sperrmechanismus innerhalb eines einzelnen Knotens durch und dann, wie er durch das verteilte Szenario funktioniert. Ich werde ein bisschen mehr lesen, als Sie vorgeschlagen haben. Vielen Dank
JoeGeeky
@ JoeGeeky - Ein FIFO ist eine Warteschlange. Vorsicht vor Warteschlangen. Denken Sie diese Seite sehr sorgfältig durch. Es hört sich sehr danach an, als würden Sie nicht einfach etwas "von der Stange" bekommen, sondern müssen Ihr Problem und Ihre Lösung sorgfältig durchdenken.
schnell_now
Ich verstehe ... Ich habe versucht, den Unterschied zwischen einer FIFO-Warteschlange zu klären, die in asynchronen Prozessen verwendet wird ( z. B. eine Prozess-Warteschlange und dann eine andere Warteschlange ). In diesem Fall müssen die Dinge in der richtigen Reihenfolge verwaltet werden, aber der Prozess, der in die Warteschlange eingeht, wird erst beendet, wenn (a) sie die Sperre erhalten, (b) eine Sperre verweigert wird oder (c) sie eine Zeitüberschreitung haben und die Leitung verlassen. Eher wie am Geldautomaten Schlange stehen. Dies verhält sich im Erfolgsfall wie ein FIFO-Muster, aber Prozesse können vor Erreichen der Frontlinie nicht in Ordnung sein. Wie von der Stange? Nein, aber das ist kein neues Problem
JoeGeeky
0

Ihre Frage kann einfach mit einem verteilten Cache wie NCache implementiert werden. Was Sie benötigen, ist ein pessimistischer Sperrmechanismus, mit dem Sie eine Sperre mithilfe eines Objekts erwerben können. Führen Sie dann Ihre Aufgaben und Vorgänge aus und geben Sie die Sperre frei, damit andere Anwendungen sie später verwenden können.

Schauen Sie sich den folgenden Code an.

Hier würden Sie eine Sperre für einen bestimmten Schlüssel erwerben und dann Aufgaben (von einer oder mehreren Operationen) ausführen und die Sperre schließlich aufheben, wenn Sie fertig sind.

// Instance of the object used to lock and unlock cache items in NCache
LockHandle lockHandle = new LockHandle();

// Specify time span of 10 sec for which the item remains locked
// NCache will auto release the lock after 10 seconds.
TimeSpan lockSpan = new TimeSpan(0, 0, 10); 

try
{
    // If item fetch is successful, lockHandle object will be populated
    // The lockHandle object will be used to unlock the cache item
    // acquireLock should be true if you want to acquire to the lock.
    // If item does not exists, account will be null
    BankAccount account = cache.Get(key, lockSpan, 
    ref lockHandle, acquireLock) as BankAccount;
    // Lock acquired otherwise it will throw LockingException exception

    if(account != null && account.IsActive)
    {
        // Withdraw money or Deposit
        account.Balance += withdrawAmount;
        // account.Balance -= depositAmount;

        // Insert the data in the cache and release the lock simultaneously 
        // LockHandle initially used to lock the item must be provided
        // releaseLock should be true to release the lock, otherwise false
        cache.Insert("Key", account, lockHandle, releaseLock); 
        //For your case you should use cache.Unlock("Key", lockHandle);
    }
    else
    {
        // Either does not exist or unable to cast
        // Explicitly release the lock in case of errors
        cache.Unlock("Key", lockHandle);
    } 
}
catch(LockingException lockException)
{
    // Lock couldn't be acquired
    // Wait and try again
}

Entnommen aus dem Link: http://blogs.alachisoft.com/ncache/distributed-locking/

Basit Anwer
quelle