Chord σε ~400 γραμμές C: Ένας μίνι κατανεμημένος hash table σε ένα μηχάνημα

Ένα μικρό project για να καταλάβει κανείς, μέσα σε ένα απόγευμα, γιατί το Chord έγινε διάσημο. Αν δεν το έχεις ακουστά, μην ανησυχείς — ξεκινάμε από το μηδέν.

Το πρόβλημα: «Ποιος έχει το αρχείο kittens.png;»

Ας πούμε ότι έχεις 10.000 μηχανήματα και ένα μάτσο αρχεία. Θέλεις, δοθέντος ενός κλειδιού (πες, του ονόματος του αρχείου), να βρίσκεις γρήγορα ποιο μηχάνημα έχει την τιμή. Οι «προφανείς» λύσεις σπάνε:

  • Κεντρικός index server: εύκολο, αλλά αν πέσει αυτός, πέφτει το πάντα. Κλασικό single point of failure (το πρόβλημα του παλιού Napster).
  • Broadcast σε όλους: «Έχει κανείς το αρχείο X;». Κλιμακώνει σαν αλεξίπτωτο φτιαγμένο από κουβέρτες (το πρόβλημα του Gnutella).
  • Hash table στο τοπικό μηχάνημα: τέλειο για ένα μηχάνημα, αλλά πώς το «μοιράζεις» σε 10.000;

Το Chord, που πρότειναν οι Stoica et al. το 2001, λύνει αυτό το τελευταίο: είναι ένας κατανεμημένος hash table (DHT). Δίνεις κλειδί, σε γυρνάει στον κόμβο που είναι υπεύθυνος για αυτό. Καμία κεντρική αρχή. Καμία πλημμύρα μηνυμάτων. Κάθε κόμβος θυμάται μόνο O(log N) άλλους και κάθε αναζήτηση κοστίζει O(log N) hops.

Αυτό το repo είναι μια παιχνιδιάρικη υλοποίηση σε C: όλο το «δίκτυο» τρέχει σε ένα μηχάνημα, σε ένα process, χωρίς sockets — αλλά ο πυρήνας του αλγορίθμου είναι αυτούσιος από το paper.

Η μεγάλη ιδέα: ένας κύκλος, και κάθε κλειδί στον επόμενο γείτονα

Φαντάσου ότι παίρνεις όλους τους πιθανούς αριθμούς από 0 μέχρι 2^m − 1 και τους τυλίγεις σε έναν κύκλο. Στον κώδικά μας m = 6, οπότε ο κύκλος έχει 64 θέσεις.

Δύο πράγματα ζουν πάνω σε αυτόν τον κύκλο:

  1. Κόμβοι (μηχανήματα). Κάθε κόμβος παίρνει μια ID παίρνοντας το hash της IP του. Έτσι σκορπίζονται «τυχαία» στον κύκλο.
  2. Κλειδιά. Κάθε κλειδί επίσης hash-άρεται και πέφτει σε μια θέση του κύκλου.

Ο κανόνας ανάθεσης είναι, με μία γραμμή, εξής:

Το κλειδί k το έχει ο πρώτος κόμβος που συναντάς αν περπατήσεις δεξιόστροφα από το k. Αυτόν τον κόμβο τον λέμε successor(k).

Αυτό λέγεται consistent hashing και έχει μια θαυμάσια ιδιότητα: όταν μπαίνει/βγαίνει κόμβος, μόνο τα κλειδιά της γειτονιάς του μετακινούνται. Όχι όλα. Σε σύστημα με 1.000.000 κλειδιά και 1.000 κόμβους, η εισαγωγή ενός νέου κόμβου μετακινεί κατά μέσο όρο 1.000 κλειδιά, όχι 500.000. Αυτό είναι καθαρή χρυσή ιδιότητα.

Η αφελής αναζήτηση: «πέρνα τον τόπο σου στον γείτονα»

Πόσα χρειάζεται να ξέρει ένας κόμβος για να δουλέψει αυτό; Τυπικά, έναν: τον αμέσως επόμενο κόμβο στον κύκλο, τον λεγόμενο successor.

Με αυτό μόνο, μπορείς ήδη να ψάξεις:

n.find_successor(id):
  if (id ∈ (n, successor]) return successor;
  else return successor.find_successor(id);

Δηλαδή: «αν το κλειδί μένει μεταξύ εμού και του γείτονά μου, αυτός είναι ο υπεύθυνος. Αλλιώς, ρώτα τον γείτονά μου». Δουλεύει. Αλλά είναι O(N) — στη χειρότερη περίπτωση η ερώτηση κάνει ολόκληρο τον γύρο. Σε δίκτυο 10.000 κόμβων, αυτό είναι αργό.

Αυτό υλοποιεί η συνάρτηση lookup() στον κώδικα.

Η έξυπνη αναζήτηση: το finger table

Εδώ έρχεται η μαγική ιδέα. Αντί κάθε κόμβος να ξέρει μόνο τον αμέσως επόμενο, ας ξέρει και κάποιους «μακρινούς», αλλά με στρατηγική:

Ο κόμβος n κρατάει m δείκτες (ένα ανά bit). Ο i-ος δείκτης δείχνει στον επόμενο κόμβο σε απόσταση τουλάχιστον 2^(i−1) δεξιόστροφα από τον n.

Αυτό λέγεται finger table. Σκέψου το σαν διπολικά γυαλιά: ο κόμβος βλέπει τους κοντινούς του με ακρίβεια, και τους μακρινούς με όλο και πιο αραιό δείγμα. Σε ένα δίκτυο 64 θέσεων, ο N8 ξέρει «κάποιον κοντά στο 9», «κάποιον κοντά στο 10», «κάποιον κοντά στο 12», «κάποιον κοντά στο 16», «κάποιον κοντά στο 24», «κάποιον κοντά στο 40». Έξι δείκτες, εκθετική κάλυψη.

Με αυτό, ο αλγόριθμος αναζήτησης μετατρέπεται σε binary-search-style:

n.find_successor(id):
  if (id ∈ (n, successor]) return successor;
  n' = ο μακρινότερος finger που είναι ακόμη πριν το id
  return n'.find_successor(id);

Η ένταση: σε κάθε βήμα κόβουμε στη μέση την υπολειπόμενη απόσταση μέχρι τον στόχο. Αυτό είναι O(log N) — ίδιο με binary search σε ταξινομημένο πίνακα, μόνο που εδώ ο πίνακας είναι κατανεμημένος σε χιλιάδες μηχανήματα.

Αυτό υλοποιεί η smartLookup(). Στην έξοδο που ακολουθεί παρακάτω, βλέπεις τα ίδια queries να τρέχουν με τους δύο αλγορίθμους και τη διαφορά να είναι σαφής:

lookup(N2, 42)      successor-only, 10 hops
smartLookup(N2, 42) finger-table,    4 hops

Σε δίκτυο 10 κόμβων η διαφορά είναι μερικά hops. Σε δίκτυο εκατομμυρίων, είναι η διαφορά μεταξύ «δουλεύει» και «δεν δουλεύει».

Τι ΔΕΝ υλοποιήσαμε (και γιατί)

Το paper περιγράφει αρκετά παραπάνω από αυτά που υλοποιήσαμε:

  • Δυναμικά joins/leaves με τον stabilize() αλγόριθμο.
  • Αντοχή σε αποτυχίες μέσω successor list μεγέθους r.
  • Replication των ίδιων δεδομένων σε πολλούς κόμβους.

Όλα αυτά είναι σπουδαία, αλλά η εκφώνηση ζητούσε τον πυρήνα: το consistent hashing και τα δύο είδη αναζήτησης. Επιπλέον, αφού όλο τρέχει σε ένα μηχάνημα και ένα process, η έννοια του «αποτυχημένου κόμβου» δεν είναι πραγματικά ελκυστική. Στήνουμε όμως τα finger tables απευθείας με την τελική τους τιμή κατά την initialize(), οπότε η συμπεριφορά είναι ισοδύναμη με ένα Chord δίκτυο που έχει ήδη συγκλίνει.

Δομή του κώδικα

chord/
├── chord.h     # Αφαιρετικός τύπος DHT — types και public interface
├── chord.c     # Υλοποίηση: ring state, hashing, lookups
├── main.c      # Demo που δείχνει τη χρήση και συγκρίνει lookup vs smartLookup
└── Makefile

Διεπαφή (όπως ζητούσε η εκφώνηση):

typedef int    nodeType;     // αναγνωριστικό κόμβου στον κύκλο
typedef int    keyType;      // αρχικό κλειδί (κατακερματίζεται)
typedef char * valueType;    // τιμή ως string

void       initialize(void);
void       insert     (nodeType n, keyType key, valueType value);
valueType  lookup     (nodeType n, keyType key);
valueType  smartLookup(nodeType n, keyType key);

Βοηθητικά: getNodeID(int i) για να πάρεις τον i-οστό ενεργό κόμβο, printRing() και printNode(n) για debugging.

Σχεδιαστικές επιλογές

m = 6, RING_SIZE = 64, MAXNODENUMBER = 10. Αυθαίρετα μικρά νούμερα ώστε να βλέπεις τον κύκλο τυπωμένο. Με m = 6 και 10 κόμβους, ο κύκλος είναι αραιά γεμάτος (10 από 64 θέσεις πιασμένες), όπως και στα σχήματα του paper. Σε πραγματικό σύστημα θα έβαζες m = 160 (όσο και το SHA-1).

Σκόρπιος πίνακας ring[RING_SIZE]. Κάθε θέση του κύκλου είτε φιλοξενεί έναν κόμβο, είτε είναι NULL. Έτσι το lookup-by-ID γίνεται σε O(1). Σπατάλη χώρου, αλλά με RING_SIZE = 64 αυτό είναι 512 bytes — οριακά. Σε m = 160 δεν θα δούλευε καν, εκεί θες hash-set ή ταξινομημένο πίνακα.

Απλή multiplicative hash αντί για SHA-1. Το paper χρησιμοποιεί SHA-1 γιατί χρειάζεται cryptographic uniformity (ώστε αντίπαλος να μην μπορεί να χτίσει κλειδιά που πέφτουν όλα στον ίδιο κόμβο). Εμείς θέλουμε απλώς «αρκετά ομοιόμορφη» κατανομή για επίδειξη — μια μίξη με τη σταθερά 0x45d9f3b κάνει τη δουλειά σε 6 γραμμές. Η αντικατάσταση από SHA-1 είναι αλλαγή μιας συνάρτησης.

Επαναληπτικά αντί για αναδρομικά. Το paper περιγράφει τις find_successor αναδρομικά. Επαναληπτική υλοποίηση είναι ισοδύναμη και απαλλάσσει από κίνδυνο stack overflow όταν αργότερα κάποιος βάλει m = 160.

Δύο range checks (in_range_oc, in_range_oo). Όλη η αριθμητική στο Chord είναι modulo 2^m, οπότε τα διαστήματα μπορεί να «τυλίγονται» γύρω από το 0. Δύο μικρές βοηθητικές με τη σημειογραφία του paper ((a, b] και (a, b) αντίστοιχα) κρατάνε τον κύριο κώδικα ευανάγνωστο.

Deterministic seed (srand(42)). Το ίδιο τρέξιμο, το ίδιο δίκτυο, την ίδια έξοδο — απαραίτητο για debugging και αναπαραγωγιμότητα.

Καμία δομή pre-computed «επόμενος ενεργός κόμβος». Κατά την initialize(), για κάθε finger entry διασχίζω την ταξινομημένη λίστα IDs. Αυτό είναι O(N · m) για όλο το στήσιμο, που είναι αμελητέο για N = 10. Σε μεγαλύτερη κλίμακα θα έβαζα binary search.

Linked list για τα κλειδιά κάθε κόμβου. Είναι το πιο βαρετό κομμάτι του κώδικα και επίτηδες — η εστίαση είναι στο ring routing, όχι στη local αποθήκευση. Σε πραγματικό σύστημα ο κόμβος θα είχε δικό του local hash table.

Πώς το τρέχεις

make           # μεταγλώττιση
make run       # τρέχει το demo
make clean     # καθαρίζει object files

Το demo:

  1. Κατασκευάζει το δίκτυο και τυπώνει τον κύκλο μαζί με τα finger tables όλων.
  2. Εισάγει 7 ζεύγη (key, value) ξεκινώντας από διαφορετικούς κόμβους.
  3. Ξανατυπώνει τον κύκλο για να δεις πού πήγε κάθε κλειδί.
  4. Τρέχει τα ίδια queries με lookup και smartLookup και τυπώνει τα hops.
  5. Κάνει μια συστηματική σύγκριση: από 3 διαφορετικούς αρχικούς κόμβους ψάχνει όλα τα κλειδιά και με τους δύο τρόπους.

Δείγμα εξόδου

=== Δαχτυλίδι μετά τις εισαγωγές ===
  N2   pred=N49  succ=N6
       finger: [k=1 s=3→N6] [k=2 s=4→N6] [k=3 s=6→N6]
               [k=4 s=10→N23] [k=5 s=18→N23] [k=6 s=34→N36]
       keys  : (k=999 id=50 "σχεδόν χίλια")
               (k=7   id=51 "τυχερό")
               (k=42  id=53 "η απάντηση")
  N6   pred=N2   succ=N7
       ...
  N36  pred=N31  succ=N41
       keys  : (k=10 id=36 "δέκα")
  N41  pred=N36  succ=N45
       keys  : (k=1 id=39 "ένα")
  ...

=== Σύγκριση hops από N2 ===
  lookup(N2, 42)      successor-only, 10 hops -> "η απάντηση"
  smartLookup(N2, 42) finger-table,    4 hops -> "η απάντηση"
  lookup(N2, 1)       successor-only,  7 hops -> "ένα"
  smartLookup(N2, 1)  finger-table,    2 hops -> "ένα"

Σταθερά παίρνεις 1–4 hops με fingers vs μέχρι N hops χωρίς. Αυτό είναι ολόκληρο το insight του paper σε δύο γραμμές.

Αν θες να σκάψεις παραπάνω

  • Το paper: Chord: A Scalable Peer-to-peer Lookup Protocol for Internet Applications (Stoica, Morris, Liben-Nowell, Karger, Kaashoek, Dabek, Balakrishnan, 2003). Διαβάζεται μια Κυριακή απόγευμα.
  • Δοκίμασε να επεκτείνεις τον κώδικα ώστε ένας κόμβος να γίνεται «νεκρός» και δες τι σπάει στο lookup πριν προσθέσεις successor list.
  • Άλλαξε το m σε 16 και βάλε 1.000 κόμβους. Η μέση smartLookup παραμένει στους ~5 hops — αυτό είναι το ½ log₂ N που μετράει το paper.

Καλό κυκλικό περπάτημα.