Chord-Sytems

[m1au]

Hallo

Ich hoffe, euch sind so Begriffe wie Chord-System oder distributed Hashtable ein Begriff.

Hier für alle anderen Infos dazu, was ein Chord-System ist: https://de.wikipedia.org/wiki/Chord

Kurzfassung: Das ist ein System, das aus mehreren Rechnern besteht. Jeder Rechner stellt einen Knoten dar. Jeder Knoten verwaltet eine gewisse Anzahl an Datensätzen. Alle Datensätze aller Knoten zusammen ergeben die gesamten Datenbestand. D. h. die Daten werden auf mehrere Rechner aufgeteilt.

Zu Chord habe ich folgendes Java-Programm gefunden: https://github.com/netharis/Chord-Implementation

Das Hauptprogramm je Rechner (Knoten) ist https://github.com/netharis/Chord-Implementation/blob/master/Application/NodeClient.java

In dieser Implementierung kommunizieren die Server via RMI.

Das Problem ist, dass ich nicht verstehe, wie dieses Programm auch dann noch funktioniert, wenn man die Daten wirklich auf mehrere Rechner verteilt. Woher kennt dann ein bestimmter Knoten die IPAdresse/ProzessID aller anderen Knoten?

Ich hoffe, ihr könnte mir hier weiterhelfen.

 

[m1au]

Außerdem würde mich interessieren, ob die Suche, die ich hier programmiert habe, ok ist:

public class Mist {
   public static int[][] fingers;
   public static int[] successors;

   public static boolean isKeyBetween(int id, int from, int to) {
     // Sonderfall: nur 1 Knoten im Ring
     if(to == from)
       return true;

     // Fall: to links von 0, from ab 0
     if(to < from)
       return id > from || id <= to;

     // für alle anderen Fälle:
     return id > from && id <= to;
   }

   public static boolean isFingerBetween(int id, int from, int to) {
     // Sonderfall: nur 1 Knoten im Ring
     if(to == from)
       return true;

     // Fall: to links von 0, from ab 0
     if(to < from)
       return id > from || id <= to;

     // für alle anderen Fälle:
     return id > from && id < to;
   }

   // Ausgehend von n den successor von id suchen
   public static int findSuccessor(int n, int id) {
     // successor vom Knoten ist der nächste Knoten im Ring, also der successor vom nächsten Datensatz:
     int successor = successors[(n + 1) % 32];

     if(isKeyBetween(id, n, successor))
       return successor;

     n = closestPrecedingNode(n, id);
     return findSuccessor(n, id);
   }

   public static int closestPrecedingNode(int n, int id) {
     for(int i = 4; i >= 0; --i)
     if(isFingerBetween(fingers[n][i], n, id))
       return fingers[n][i];

     return n;
   }

   public static void main(String [] args) {
     // Fingertabellen:
     fingers = new int[32][5];
     fingers[1] = new int[]{4, 4, 9, 9, 18};
     fingers[4] = new int[]{9, 9, 9, 14, 20};
     fingers[9] = new int[]{11, 11, 14, 18, 28};
     fingers[11] = new int[]{14, 14, 18, 20, 28};
     fingers[14] = new int[]{18, 18, 18, 28, 1};
     fingers[18] = new int[]{20, 20, 28, 28, 4};
     fingers[20] = new int[]{21, 28, 28, 28, 4};
     fingers[21] = new int[]{28, 28, 28, 1, 9};
     fingers[28] = new int[]{1, 1, 1, 4, 14};

     // successors zu Datensätzen:
     successors = new int[]
     {
       1, 1,
       4, 4, 4,
       9, 9, 9, 9, 9,
       11, 11,
       14, 14, 14,
       18, 18, 18, 18,
       20, 20,
       21,
       28, 28, 28, 28, 28, 28, 28,
       1, 1, 1
     };

     // ausgehend von Knoten 1 den verantwortlichen Knoten für Datensatz 24 suchen:
     //System.out.println(findSuccessor(1, 24));

     // ausgehend von Knoten 28 den verantwortlichen Knoten für Datensatz 12 suchen:
     //System.out.println(findSuccessor(28, 12));

     // ausgehend von Knoten 4 den verantwortlichen Knoten für Datensatz 3 suchen:
     System.out.println(findSuccessor(4, 3));
   }
}

Habe ich ohne LOOKUP programmiert, zum Testen der Suche läuft also alles nur auf einem einzigen Rechner. Daten in Bezug auf https://vowi.fsinf.at/images/b/bc/TU_Wien-Verteilte_Systeme_VO_(Göschka)_-_Tannenbaum-distributed_systems_principles_and_paradigms_2nd_edition.pdf Seite 189.

P. S. ich weiß leider nicht, wie ich hier java-code formattieren kann

 

[m1au]

Also, falls es wen interessiert, ich habe 2 Unschönheiten entdeckt:
- der erste Kommentar in der Methode isFingerBetween war falsch
- den successor eines Knotens (also den im Ring direkt folgenden Knoten) kann man einfacher ermitteln

// Pfad zu Java: set PATH=%PATH%;C:\Program Files\Java\jdk1.8.0_45\bin
// Literatur: https://vowi.fsinf.at/images/b/bc/TU_Wien-Verteilte_Systeme_VO_%28G%C3%B6schka%29_-_Tannenbaum-distributed_systems_principles_and_paradigms_2nd_edition.pdf
public class Mist
{
  // Grundsätzlich muss man unterscheiden:
  //  - Datensatz-successor:
  //  Der successor eines Datensatzes ist immer der für diesen Datensatz zuständige Knoten.
  //  Hat man die Knoten 1, 4, 9, 11, 14, 18, 20, 21 und 28, dann gelten folgende Aussagen:
  //  - Knoten 4 ist zuständig für Datensatz 3.
  //  D. h. Knoten 4 ist der Datensatz-successor von Datensatz 3
  //  - Knoten 4 ist zuständig für Datensatz 4.
  //  D. h. Knoten 4 ist der Datensatz-successor von Datensatz 4
  //  - Knoten-successor:
  //  Der successor eines Knotens ist immer der jeweils folgende Knoten im Ring.
  //  Hat man wieder die gleichen Knoten, gilt folgende Aussage:
  //  Knoten 9 ist der Knoten-successor von Knoten 4.
  
  public static int[][] fingers;

  /**
  * Kontrolle, ob sich ein Datensatz zwischen einem bestimmten Knoten und dessen Knoten-successor befindet.
  * @param int id Datensatz (key)
  * @param int from Knoten
  * @param int to Knoten-successor von from
  * @return boolean Ob id zwischen (from, to] exklusive from, inklusive to
  */
  public static boolean isKeyBetween(int id, int from, int to)
  {
  // Sonderfall: nur 1 Knoten im Ring
  if(to == from)
  return true;

  // Fall: to links von 0, from ab 0
  if(to < from)
  return id > from || id <= to;
  
  // für alle anderen Fälle:
  return id > from && id <= to;
  }

  /**
  * Kontrolle, ob sich ein Finger (Knoten) der Fingertabelle zwischen einem Knoten und einem Datensatz befindet.
  * @param int id Finger
  * @param int from Knoten
  * @param int to Datensatz
  * @return boolean Ob id zwischen (from, to) exklusive from, exklusive to
  */
  public static boolean isFingerBetween(int id, int from, int to)
  {
  // Fall: ausgehend von Knoten n soll Datensatz n gesucht werden (der Knoten sucht sich sozusagen selbst)
  if(to == from)
  return true;
  
  // Fall: to links von 0, from ab 0
  if(to < from)
  return id > from || id <= to;
  
  // für alle anderen Fälle:
  return id > from && id < to;
  }

  /**
  * Ausgehend von Knoten n jenen Knoten suchen, der für den Datensatz id zuständig ist.
    * @param int n Knoten von hier aus wird die Suche gestartet
    * @param int id Datensatz, dessen zuständiger Knoten gesucht werden soll
    * @return int jener Knoten, der für den Datensatz id zuständig ist
    */
  public static int findSuccessor(int n, int id)
  {
  // Es gibt 2 Möglichkeiten, wie man einen Knoten-successor finden kann:
  //  - Man nimmt den nächsten Datensatz vom Knoten n und ermittelt dessen Datensatz-successor:
  //  int successor = successors[(n + 1) % 32];
  //  - Man nimmt den ersten Eintrag in der Fingertabelle von Knoten n:
  //  int successor = fingers[n][0];
  //  Um nicht zusätzlich eine successors-Tabelle für Datensatz-successoren anlegen zu müssen,
  //  wird im Folgenden diese Variante verwendet.

  int successor = fingers[n][0]; // Knoten-successor
  if(isKeyBetween(id, n, successor))
  return successor;

  n = closestPrecedingNode(n, id);
  
  // In einem verteilten System muss nun auf den Knoten n gewechselt werden. Dort muss dann wieder findSuccessor
  // aufgerufen und dessen Ergebnis hier zurückgegeben werden.
  // Doch in diesem Testsystem laufen alle Knoten auf einem einzigen Rechner. Darum wird hier findSuccessor
  // direkt rekursiv aufgerufen.
  
  return findSuccessor(n, id);
  }

  /**
  * In der Fingertabelle eines Knotens jenen Knoten suchen, der sich im Ring möglichst nahe vor dem Datensatz id befindet.
  * @param int n Knoten, dessen Fingertabelle durchsucht wird
  * @param int id Datensatz
  * @return Knoten Ein Knoten aus der Fingertabelle oder der übergebene Knoten n.
  */
  public static int closestPrecedingNode(int n, int id)
  {
  // Die Fingertabelle wird von unten nach oben durchlaufen.
  // Man versucht also, immer möglichst schnell möglichst weit zu springen.
  for(int i = 4; i >= 0; --i)
  if(isFingerBetween(fingers[n][i], n, id))
  return fingers[n][i];

  return n;
  }

  public static void main(String [] args)
  {
  // Test-Ring 1 ===================================================================
  // Fingertabellen für Ring mit 9 Knoten:
  fingers = new int[32][5];
  fingers[1] = new int[]{4, 4, 9, 9, 18};
  fingers[4] = new int[]{9, 9, 9, 14, 20};
  fingers[9] = new int[]{11, 11, 14, 18, 28};
  fingers[11] = new int[]{14, 14, 18, 20, 28};
  fingers[14] = new int[]{18, 18, 18, 28, 1};
  fingers[18] = new int[]{20, 20, 28, 28, 4};
  fingers[20] = new int[]{21, 28, 28, 28, 4};
  fingers[21] = new int[]{28, 28, 28, 1, 9};
  fingers[28] = new int[]{1, 1, 1, 4, 14};

  // ausgehend von Knoten 1 den verantwortlichen Knoten für Datensatz 24 suchen:
  System.out.println(findSuccessor(1, 24)); // 28
  // Knoten: 1 -> 18 -> 20 -> 21 => 28
  
  // ausgehend von Knoten 28 den verantwortlichen Knoten für Datensatz 12 suchen:
  //System.out.println(findSuccessor(28, 12)); // 14
  // Knoten: 28 -> 4 -> 9 -> 11 => 14
  
  // ausgehend von Knoten 4 den verantwortlichen Knoten für Datensatz 3 suchen:
  //System.out.println(findSuccessor(4, 3)); // 4
  // läuft im Ring rundherum: 4 -> 20 -> 28 -> 1 => 4
  
  /*
  // Test-Ring 2 ===================================================================
  // Fingertabelle für Ring mit nur 1 Knoten:
  fingers = new int[32][5];
  fingers[1] = new int[]{1, 1, 1, 1, 1};
  // ausgehend von Knoten 1 den verantwortlichen Knoten für Datensatz 24 suchen:
  System.out.println(findSuccessor(1, 24)); // 1
  */
  }
}

P. S. Tja, das mit dem Einrückungen klappt hier irgendwie nicht so richtig

 

[Java20134]

Ich kenne mich mit dem Programm nicht großartig aus. Aber ich würde dir einen kleinen Tipp geben: Ich finde es sehr schön, dass du Kommentare schreibst, aber entscheide dich für eine Sprache, entweder Englisch oder Deutsch. Eine Mischung, in welcher du mal deutsch und englisch schreibst macht einen Leser irre.