Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Hauptstudiumsprüfungen » Lehrstuhl 4 » vs-2022-08-01 (Übersicht)
Prüfung war sehr ähnlich zu den bisherigen Protokollen des letzten Jahres, weshalb ich nur neues hier erwähne. Fragen werden außerdem in der Prüfung ausführlicher gestellt und auch besser in einen Kontext eingebunden. Teilweise liste ich die Fragen hier nicht im üblichen Frage - Antwort Schema auf, um noch ein bisschen mehr Kontext zu geben…
Es kam die übliche Frage, was genau gemacht werden muss, um einen Fernaufruf im Stub als Nachricht zu verpacken. Hier liegt der Fokus ziemlich darauf, wie mit den Parametern umgegangen wird. In Java kann man so gut wie immer beide Varianten zum Umgang mit Parametern verwenden: Call-by-value-result sowie Call-by-reference. In welchem Fall gibt es Probleme? → Call-by-value-result klappt nicht immer. Bei unserem Auktionsservice aus der Übung gab es beispielsweise beim platzieren eines Gebots den Eventhandler Parameter, der vom Server dann aufgerufen wurde, wenn ein Client die jeweilige Auktion gewonnen hat. In unserer Implementation wurde dort lediglich ein System.out.println aufgerufen, welches by „Call-by-value-result“ natürlich dann beim Server ausgeführt und geprintet wird und eben nicht beim Client, wo es eigentlich gebraucht wird. Hier müsste man als definitiv Call-by-reference verwenden. (Aus meiner Sicht liegt das auch explizit am Print, in vielen anderen Fällen würde Call-by-value-result wahrscheinlich trotzdem funktionieren)
Außerdem kam hier die übliche Frage, ob es denn in anderen Programmiersprachen Probleme geben könnte. → In den anderen Protokollen wird als Antwort nur kurz der Vergleich char* vs char[] in C / C++ erwähnt. Bei dieser kurzen Antwort kommen definitiv nachfragen, deswegen ein bisschen mehr Hintergrund: In C++ ist ein char* „under the hood“ exakt das gleiche wie char[] also einfach eine Referenz zu einer Speicheradresse an der ein Char liegt. Hat man wirklich einen Char Array, dann kommen halt hinter dieser Speicheradresse noch weiter Chars. Normalerweise wird in einem weiteren Parameter oft deswegen noch die Länge des Char Arrays mitgegeben. Und das macht es dann eben nicht so leicht wie in Java, einen generischen Stub zu bauen, weil man ja anhand char* nicht einfach herausfinden kann, wie viele chars man für „call-by-value-result“ kopieren müsste. Und Reflection gibts ja sowieso nicht in C / C++. Deswegen benötigt man IDL, um solche Dinge explizit zu definieren. Aus der IDL Spezifikation lassen sich dann die korrekten Stubs / Skeletons in der jeweiligen Programmiersprache generieren.
Gibt es noch weitere Möglichkeiten, um den Garbage Collection Mechanismus bei At Most Once umzusetzen (statt Timeout und „Antwort wegwerfen, wenn eine frische Anfrage vom Client kommt“)? → Nach dem Request-Reply-Acknowledge Prinzip. Client sendet Bestätigung, dass die Antwort erhalten wurde und dementsprechend kann der Server die Antwort aus dem Cache entfernen.
Jetzt gehts darum den Auktionsservice aktiv zu replizieren. Problem: Auktionsservice ist aktuell nicht deterministisch. An welcher Stelle haben wir denn genau aufgrund des Nichtdeterminismus Probleme? → Ganz explizit das Beispiel: Client sendet Anfrage eine Auktion zu erstellen. Anfrage wird an Replikate verteilt und jeder nimmt seinen eigenen Zeitstempel als Erzeugungszeit dieser Auktion. Jetzt sendet ein Client ein Gebot und die Anfrage wird wieder verteilt. Aufgrund der leicht unterschiedlichen Timestamps kann es nun sein, dass der Client auf manchen Replikaten die Auktion gewinnt, weil sie noch nicht ausgelaufen ist und auf manchen verliert, weil sie schon ausgelaufen war.
Nun war die Frage, wie wir das deterministisch machen könnten und zwar ganz explizit, ohne einfach eine passive Replikation zu verwenden. → Antwort wie in anderen Protokollen: Timestamp bei der Erzeugung der Auktion mitsenden. Was aber in den anderen Protokollen nicht vorkommt, ist dass man eben trotzdem auch noch zusätzlich eine Möglichkeit braucht, um das Auslaufen von Auktionen zum richtigen Zeitpunkt geschehen zu lassen, da zwar der Auslaufzeitpunkt jetzt überall gleich ist, aber die Uhren der Replikate ja nicht 100% synchron sein können. Also wird noch ein Request vom Leader gebraucht, dass das Auslaufen einer Auktion signalisiert.
Jetzt fließend der Übergang zu Raft. Folgendes Szenario wurde präsentiert: Wir haben 100% synchrone Uhren und wir wissen, dass die Latenzen zwischen den Replikaten alle exakt gleich sind. Können wir den Auktionsservice jetzt auch ohne zusätzliche Requests / Timestamps deterministisch machen? → Nein, wir haben ja einen uniformen Multicast und spezielle bei Raft werden Requests zuerst beim Leader applied und dann bei den Followern. Hier kamen dann auch nachfragen, wie es genau bei Raft funktioniert. Leader kriegt als Ergebnis der appendEntries Aufrufe die Antwort der Replikate, ob diese die Log Entries bei sich abgespeichert haben. Wenn F + 1 Bestätigungen da sind, kann der Leader seinen Commit Index entsprechend anpassen und selbst die Log Entries auf die State Machine anwenden. In darauf folgenden appendEntries Aufrufen kriegen die Follower den neuen Commit Index mit und können dann auch die Log Entries applyen. Man sieht also hier direkt, dass der Leader zeitlich definitiv früher dran wäre.
Nun theoretische Fragen, warum denn bei einen Rechnerausfall und 3 Replikaten die Committeten Log Entries trotzdem sicher sind. → Committet wird erst bei Mehrheit, also bei mindestens 2 Replikaten. Leaderausfall bedeutet, dass noch mindestens ein Replikate den Committeten Log hat. Man hat noch 2 Replikate übrig und braucht genau die Stimmen dieser beiden Replikate, um eine Mehrheit für die Leaderwahl zu haben. Dementsprechend ist in dieser Mehrheit mindestens ein Replikat, dass alle Committeten Logs hat! Und Leader wird ja sowieso nur das Replikat, dass den neusten Log Entry Stand hat.
Jetzt wurde das vorherige noch weiter ausgeführt und ein bisschen mit den Quorengrößen bei Committen und Leaderwahl gespielt. Tatsächlich könnte man ja sagen, man will bei 5 Replikaten nur zwei Bestätigungen, um etwas zu committen. Also hat man nach einem Leadercrash mindestens noch ein Replikat, auf dem die Logs sicher sind. Aber wenn man für die Leaderwahl nur 3 Stimmen braucht, dann könnten genau die 3 von 4 Replikate ein Quorum bilden, die nicht die neusten Logs haben. → Man braucht 2 Bestätigungen beim Committen und 4 Votes für die Leaderwahl, dann kann man immerhin bei 5 Replikaten noch einen Ausfall tolerieren. Besser wären natürlich trotzdem 3 Commit Bestätigungen und 3 Votes für Leaderwahl, denn dann können zwei Ausfälle toleriert werden.
Was passiert bei einem Ausfall, wenn wir 1 Commit Bestätigung wollen und 5 Votes für Leaderwahl bei 5 Replikaten? Es wird keine Mehrheit mehr für die Leaderwahl gefunden, da ja nur 4 Replikate verfügbar sind.
Und zuletzt kam dann die Frage, wie die Anführerwahl bei Paxos anders ist, als bei Raft. Ist auch schon so in anderen Protokollen vorgekommen, aber die Antworten dort waren scheinbar nicht ausreichend.