Lab3: Giffords Scheme Prinzip

  • Hallo,
    ich habe zuerst die FileServers durch Usage aufsteigend sortiert danach auf NR und NW aufgeteilt. Ich habe in der Angabe verstanden, dass NR geringste Usage und den Rest für Nw speichert, stimmt das so? Folgende algorithmus habe ich implementiert.
    Könnte jemand vielleicht kurz schauen ob es richtig ist bzw. ob ich richtig verstanden habe :)


    Danke im Voraus.


    Edit : Noch eine Frage, falls eine Datei uploaded werden soll, sollte das auf jede NW-Server geschickt werden oder nur geringste Usage server?

  • ich habe zuerst die FileServers durch Usage aufsteigend sortiert danach auf NR und NW aufgeteilt. Ich habe in der Angabe verstanden, dass NR geringste Usage und den Rest für Nw speichert, stimmt das so?

    Nein. Das wurde doch schon in den Postings #16 und #17 behandelt.


    Edit : Noch eine Frage, falls eine Datei uploaded werden soll, sollte das auf jede NW-Server geschickt werden oder nur geringste Usage server?

    Natürlich an das ganze Schreibquorum.


    Setz dich nochmal hin und überlege, wie Gifford's Scheme funktioniert. Ich unterstelle dir einfach, dass du es nicht verstanden hast.

  • Hi Leute!


    Bis jetzt hab ich alles hier geschriebene verstanden (glaube ich). Aber eine Frage wurde mir noch nicht beantwortet.


    Das Gifford's Scheme ist, soweit ich dem Internet glauben kann, eine Art "Wahl". Genauer habe ich diese Beschreibung des Gifford's Scheme gefunden.


    http://www.ifi.uzh.ch/groups/r…Classes/VS_WS99/V-7-2.pdf


    Nehmen wir jetzt beispielsweise die Quorum-Auswahl aus der Angabe (wir sagen einfach, die Usage behauptet das), und alle haben von File1 die Version 0. Das sagen die Nr-Server zumindest. Jetzt wird die neue Version geschrieben: Server 3 und 4 erhalten den neuen File mit der Version 1.


    Ok, sagen wir, es kommt jetzt ein Lesezugriff. Aufgrund der niedrigen Usage von Server 3 bekommen wir wieder das EXAKT gleiche Nr-Quorum. Nach dem oben angegebenen PDF müsste jetzt das "Voting" der Nr-Server so aussehen: (Version 0: 2 Stimmen; Version 1: 1 Stimme) und dementsprechend müsste Version 0 ausgegeben werden.


    Stimmt das oder hab ich da was falsch verstanden?


    BTW.: Wenn die Nw-Server ausgewählt werden und das ebenfalls über die Usage geht, müssten dann nicht genau die gleichen wie bei Nr ausgewählt werden? oder wird die Versionsabfrage bereits als Usage gewertet?

  • Ok, sagen wir, es kommt jetzt ein Lesezugriff. Aufgrund der niedrigen Usage von Server 3 bekommen wir wieder das EXAKT gleiche Nr-Quorum. Nach dem oben angegebenen PDF müsste jetzt das "Voting" der Nr-Server so aussehen: (Version 0: 2 Stimmen; Version 1: 1 Stimme) und dementsprechend müsste Version 0 ausgegeben werden.

    So steht's im PDF, aber das ist Käse. Wenn du dann eine Schreiboperation durchführst, verlierst du ja die Änderungen von Version 0 auf Version 1.


    Die Idee von Gifford's Scheme ist ja jene, dass es bei beliebig ausgewählten Lese- und Schreibquoren, deren Größe den genannten Bedingungen genügen, immer mindestens einen Server gibt, der in beiden Quoren enthalten ist. Das führt dazu, dass du beim Lesen immer zumindest einen Server kontaktierst, auf dem die aktuellste Version liegt. Und die verwendest du dann auch.


    Gifford's Scheme findet man übrigens auch unter dem Begriff "Quorum Consensus" (soviel ich weiß auch in Kempers Datenbanksysteme-Buch), das Originalpaper gibt's übrigens auch online.


    BTW.: Wenn die Nw-Server ausgewählt werden und das ebenfalls über die Usage geht, müssten dann nicht genau die gleichen wie bei Nr ausgewählt werden? oder wird die Versionsabfrage bereits als Usage gewertet?

    Dann werden halt die gleichen Server ausgewählt, macht ja nichts. Über die Zeit ändert sich dann die Usage der Server, dann kommen andere Server zum Zug. :)

  • Die größe des Quorums bleibt ja nur dann gleich, wenn ich davon ausgehe, dass beim Start alle Fileserver online sind.


    Davon darfst du laut Angabe ausgehen:

    Quote

    Concerning the implementation of Gifford's scheme, you may assume that no additional fileservers will join the network or old ones disappear after the first client has made an upload


    Außerdem haben beim Starten alle Fileserver dieselben Dateien, daher kannst du bei einem Download vor dem ersten Upload nicht viel falsch machen.

  • ich kenne mich mit regular expressions zwar aus aber bin mir trotzdem nicht sicher, wie die Nachricht aussehen soll.


    z.B.: assert firstMessage.matches("!login \\w+ ['+B64+']{43}=") : "1st message";



    -> das heißt ja, dass meine Nachricht die Form z.B haben kann: !login bla1


    für was steht eigentlich das 1st message. müssen wir das mit assertions irgendwie im code einbauen?

  • Quote

    Ja. Erlaubt sind alle Werte für NR und NW, welche die beiden in der Angabe genannten Bedingungen erfüllen. NR = NW = 4 ist für 4-7 Fileserver erlaubt.


    Hallo, ich wollte nur anmerken, dass ich Stage 1 so implementiert habe und für den Fall N=4 -> NR = NW = 4 Punkte verloren hab, da in diesem Fall volle Replikation stattfindet und kein Unterschied zum Lab 1 auszumachen ist.

  • Hallo, ich wollte nur anmerken, dass ich Stage 1 so implementiert habe und für den Fall N=4 -> NR = NW = 4 Punkte verloren hab, da in diesem Fall volle Replikation stattfindet und kein Unterschied zum Lab 1 auszumachen ist.



    Ja, weiß ich mittlerweile auch. Relevant ist folgender Satz, der in der Angabe unter "Overview" zu finden ist:

    Quote

    To make things more interesting, a file is not uploaded to every single fileserver -- our fileservers won't be fully replicated any longer.


    Es tut mir leid, falls sich jemand diesbezüglich an meine Aussagen gehalten hat und dadurch Punkte verloren hat.

  • eigentlich ist das aber dann schon unfair - es steht drinnen in der angabe das die constraints nicht verletzt werden sollen - mehr nicht! fully replicated heißt für mich in jedem fall (also egal wieviele server da sind) wird das file an alle geschrieben. bei nr=nw=4 für 4-7 servern trifft ja das fully replicated nicht zu mMn..

  • Es steht ja da, dass die Dateien nicht mehr "fully replicated" sind.


    Ich find's auch nicht toll, dass irgendwo in der Angabe eine zusätzliche Bedingung steht, und bei der Beschreibung von Gifford's Scheme steht mehr oder weniger "NR und NW müssen diese beiden Bedingungen erfüllen, dann passt's".

  • ich brauch mich nicht beschweren weil ich nicht betroffen bin ;) ich hab round(N/2)+1 genommen


    aber was mir grad eingefallen ist - lt. der beschreibung:

    Quote

    To make things more interesting, a file is not uploaded to every single fileserver -- our fileservers won't be fully replicated any longer.

    müsste dann jeder abzüge bekommen weil bei nur einem fileserver jeder die daten fully replicated speichert - also rein vom prinzip her...

  • ... wenn nur ein FileServer vorhanden ist ist mir das auch schon aufgefallen bei der Implementierung dass sich da die Angabe widerspricht, auf der andern Seite, wenn mans einfach so implementiert nach den beiden Constraints, die auch im Buch bzw im Netz zu finden sind - dürfts in jedem Fall korrekt sein ... das Beispiel macht ja keinen Sinn wenn man nur einen FileServer verwendet.

    Mac Book Pro - what else