קדמליה

קדמליה (מלועזית: Kademlia, ובקיצור: Kad) היא טבלת גיבוב מבוזרת (Distributed hash table, DHT) מדור שלישי, המשמשת ברשתות P2P שהומצאה על ידי פטר מיימאונקוב (Petar Maymounkov) ודייוויד מזיארס (David Mazières).

פונקציית הגיבוב ופונקציית המרחק

בקדמליה ממופים כל הערכים המאוחסנים בעזרת פונקציית הגיבוב SHA-1, הנותנת לכל ערך מפתח בן 160 בתים. פונקציית המרחק בין שני מפתחות היא פונקציית XOR, כך נוצר מרחב חיפוש בו ניתן למקם את כל הערכים ולתאר את המרחקים ביניהם לפי מרחקי המפתחות.
בנוסף, ממופים כל הצמתים ברשת לפי אותן פונקציות גיבוב ומרחק ואותו מרחב בן 160 הבתים מכיל הן את הערכים והן את המשתתפים ברשת.

משך החיפוש בקדמליה יחסי ל-$log(n)$, כאשר n הוא מספר החברים ברשת.

שימוש טיפוסי

השימוש הנפוץ ביותר ברשת הוא לצורך שיתוף קבצים, בדוגמה הבאה מודגם חיפוש אחר קובץ ברשת:

1. מחשב המחובר לרשת מעוניין למצוא קובץ בשם XXX.
2. המחשב המחפש מפעיל את פונקציית הגיבוב על השם XXX ומקבל YYY, ערך בן 128 ביט.
3. המחפש מאתר בעזרת טבלת הניתוב (ראו בהמשך) את הדרך לעמית (Peer) האחראי על הערך YYY, בתהליך זה יש לכל היותר $log(n)$ שלבים ברשת בת n עמיתים.
4. המחשב האחראי על הערך YYY (זה שיש לו מזהה הקרוב ביותר ל-YYY) מדווח למחפש על רשימת המחשבים שדיווחו לו על כך שהם מכילים את הקובץ XXX.
5. המחפש פונה אל כל איברי הרשימה ונרשם אצלם בתור להורדת הקובץ.

טבלת ניתוב

הניתוב בקדמליה הוא הדרגתי, כל צומת (node) ברשת מעביר למחפש את הכתובת אל הצומת הבא. מפני שכל צומת מחזיק מידע מאוד מפורט על המתחם הקרוב אליו במרחב החיפוש ומידע דליל יותר על החלקים המרוחקים יותר, ה"קפיצות" אותן מבצע המחפש הן בצעדים שהולכים ומתקצרים (מבחינת המרחק בין ערכי פונקציית הגיבוב) וכך מובטח החיפוש בן $log(n)$ שלבים לכל היותר.

מימושים עיקריים

את הפרוטוקול מממשת התוכנה הפופולרית eMule, שהיא המחליפה של eDonkey ותוכנות P2P נוספות משתמשות בו.