Wie erklärt man Idempotenz ?

"Man bezeichnet ein Element einer Menge (also auch eine Funktion), das mit sich selbst verknüpft wieder sich selbst ergibt, als idempotent." (wikipedia). Dass es sich hierbei um eine der zentralen Anforderungen bei der Programmierung verteilter Systeme handelt, und dass das ganz erhebliche Auswirkungen auf Architektur und Entwurf solcher Systeme hat, ist (nach meiner Erfahrung) für Studenten nicht grade leicht verständlich.

Um das anschaulicher zu machen, habe ich eine "Lampe" gebaut:

Dazu gibt es einen Schalter, genauer gesagt einen Taster

Bei jedem Druck auf den Taster (ganz klein, rechts an der Platine) ändert sich der Zustand der Lampe: Ist sie aus, dann geht sie an, ist sie an, dann geht sie aus.

Soweit ganz einfach. Der Taster sendet eine Nachricht ("wurde gedrückt") an den Empfänger, der schaltet entsprechend hin und her. Kompliziert wird das dadurch, dass die Übertragung über Funk erfolgt. Die Übertragung ist deshalb nicht verläßlich. Insbesondere haben die Module nur eine beschränkte Reichweite. Vergrössert man den Abstand weit genug, gehen Nachrichten verloren.

Steht die Lampe in einem Raum und der Schalter in einem anderen, weiss man nach dem Drücken der Taste nicht mehr sicher, ob die Nachricht angekommen, die Lampe also an oder aus ist. Dies wäre nur der Fall, wenn jede Nachricht genau einmal zugestellt würde ("exactly once").

Das ist aber nicht realisierbar: Ein Ansatz wäre, dass der Empfänger eine Bestätigung schickt, wenn er die Nachricht erhält. Kommt diese beim ursprünglichen Absender an, weiss er, dass die Nachricht erfolgreich zugestellt wurde und damit, ob das Licht jetzt an oder aus ist. Er kennt also den Zustand der Lampe ("shared state", beide sind sich einig darüber, ob die Lampe brennt oder nicht).

Aber was passiert, wenn die Bestätigung nicht ankommt ? Wenn die Nachricht tatsächlich nicht angekommen ist, könnte sie ein weiteres Mal gesendet werden. Aber eben das läßt sich nicht feststellen, denn das Ausbleiben der Bestätigung könnte mehrere Ursachen haben: Entweder ist die ursprüngliche Nachricht verloren gegangen, oder die Nachricht ist zwar angekommen, aber der Empfänger ist abgestürzt, bevor er die Bestätigung schicken konnte oder die Bestätigung ist verloren gegangen. Je nachdem, welche Ursache vorliegt, ist die Lampe an oder aus, der Taster (Absender) weiss es nicht.

Wie ließe sich dieses Problem lösen ? Man könnte die Bestätigung bestätigen. Kommt diese an, ist alles OK, aber wenn nicht, gibt es verschiedene Ursachen usw.

So wird das Problem also nicht zufriedenstellend gelöst, da zumindest die letzte Nachricht in einer Kommunikation nicht verlässlich übertragen werden kann. Deshalb kann man nicht vermeiden, dass eine Nachricht gelegentlich entweder verloren geht, oder mehrfach übertragen wird. Es gibt nur "at most once" oder "at least once".

Bestätigungen sind also für diesen Fall nicht geeignet. So wird die Grundannahme, dass mit einem solchen Protokoll (wie es etwa TCP realisiert) eine verläßliche Übertragung von Nachrichten, die den Zustand ändern, möglich ist, erschüttert. Doch wie löst man das jetzt ?

Man betrachtet den Eingang einer Bestätigung nicht als verläßliche Bestätigung, sondern schickt eine Nachricht, falls nicht innerhalb einer bestimmten Zeitspanne eine Bestätigung eintrifft, einfach nochmal ("at least once"). Oder man überträgt gleich die Nachricht immer wieder. Dazu braucht man natürlich andere Nachrichten, mit unserem Beispiel würde die Lampe ständig an und aus geschaltet werden.

Man muss die Anwendung so konstruieren, dass kein Schaden entsteht, wenn eine Nachricht mehrfach empfangen wird. Das ist Idempotenz.

Im Bild sieht man einen Schalter, der zwei Zustände hat (an und aus) und den aktiven Zustand immer wieder (im Beispiel alle 200 Millisekunden) überträgt. Diese Nachricht (entweder "An" oder "Aus") kann beliebig oft übertragen werden, der Empfänger ist, sobald er mindestens eine (aktuelle) Nachricht erhält, im richtigen Zustand. Ist die Lampe an, und es wird nochmal "An" empfangen, passiert nichts (unerwünschtes).


Nächste Woche werde ich das in der Vorlesung ausprobieren, mal schauen, ob dieses Konzept so besser verständlich ist.

Realisiert wurde das System mit ZigBee zur Übertragung, hierfür wurden XBee-Module der Firma Digi verwendet. Das würde natürlich auch mit anderen Übertragungstechniken funktionieren, aber diese Module sind sehr bequem zu verwenden, die Funktionen, die man hier braucht, sind schon eingebaut: Im einen Fall wird der Zustand eines digitalen Eingangs bei jeder Änderung übertragen, im anderen Fall werden die Eingänge in einem festen Zeitintervall abgetastet und übertragen.

Für den Empfänger bräuchte man an sich nur ein bisschen Logik (im Taster-Betrieb ein Flip-Flop, das den aktuellen Zustand speichert und eine Erkennung mit entsprechender Logik, die erkennt, welche Betriebsart grade vorliegt, das wird durch einen weiteren Eingang mit entsprechend fixem Wert festgelegt). Das liesse sich leicht diskret ohne Controller realisieren, wenn nicht ... die XBee-Module mit 3.3 Volt arbeiten würden ... Man bräuchte also auch noch Level-Shifter. Und da ich den Arduino grade rumliegen hatte ....