נתון Load Balancer שמחביא N שרתים זהים.
הוא מטפל במיליוני לקוחות (כתובות IP ללא חוקיות, סדר או מידע נוסף )
וצריך לעמוד בתנאים הבאים:
1. כתובות ה IP יופנו לשרתים כך שלא יווצר עומס על שרת מסוים אלא חלוקה מאוזנת
2. אם כתובת IP כבר הגיעה פעם אחת לשרת, כל פנייה שלה מכאן ואילך תופנה תמיד לאותו שרת
3. מלאכת ההפניה לשרת תיקח (O(1 זמן, ולמרות שיש הרבה מקום שניתן לבזבז - מספר כתובות ה IP רק הולך וגדל אז לא כדאי לסמוך על שמירת כתובות IP כמו שהן...
4. אמינות מלאה
אני חשבתי על HASH TABLE בגודל N כאשר ה-KEY (ה- INDEX) הוא תוצאת פונקציית HASH על כתובת ה-IP וה-VALUE הוא ה -ID של השרת שמטפל באותה כתובת:
index=HASHmodN
Server ID=
יש למישהו רעיון אחר\הצעות לשיפור?
ע"י: יאירזס
לדעתי הפתרון שהצעת הוא בהחלט לא רע.
בדרך כלל, כששואלים על סיבוכיות של O(1) מבחינת גישה רוצים פתרון של hash table. מכיון שכמות כתובות הip היא עצומה (בגרסא 4 של פרוטקול ip - קרוב ל2 בחזקת 32) הרי שאי אפשר להשתמש במערך, ויש להשתמש במבנה הנתונים שגדל דינאמית, ולכן hash table הוא פתרון.
צריך כמובן להשתמש ב modulo על כמות הסרברים כמו שאמרת , ואם תוצאת ההאש מתפלגת יוניפורמית , גם המודולו יתפלג בצורה יוניפורמית.
בעקרון, אני הייתי מחזיק מערך של רשימות מקושרות לכתובות ה ip
וכל כתובת היתה נכנסת לרשימה בתא שהאינדקס שלו הוא
האש על האיי פי מודולו N.