IP2C תכנון, מימוש ושיקולי יעילות

IP2C היא ספריה קטנה למציאת קוד המדינה אליה שייכת כתובת IP.
הספרייה מכילה נכון לכרגע מימוש בPHP ובג'אווה, וכוללת ומבוססת על המרת הנתונים לקובץ בינארי קומפקטי שמתוכנן לחיפוש מהיר.
בסיס נתונים של נתוני IP למדינה זה דבר די גדול, בסיס הנתונים החינמי של WHI שמגיע כקובץ CSV מכיל כ77000 טוחי כתובות (הטווח מכתובת X לכתובת Y שייך למדינה C) ובסיסי נתונים אחרים הם הרבה יותר גדולים.
כשרוצים לחפש בדבר כזה יש כמה אפשרויות:
1. העלאת הנתונים לטבלא לבסיס הנתונים ושימוש בבסיס הנתונים לחיפוש.
2. המרה של קובץ הCSV לקובץ בינארי חסכוני ואז חיפוש בקובץ. על הדרך הזו המשך הפוסט מדבר.

הגישה הראשונה בעייתית כי היא דורשת גישת מנהל לבסיס הנתונים כדי לבצע יבוא מהיר, או דורשת עדכון בלולאה – מה שלוקח דקות ארוכות.
הגישה השניה עדיפה כי הנתונים תופסים פחות מקום וקל יותר לעדכן אותם, בנוסף אין תלות בבסיס נתונים.

שורה בקובץ הCSV המקורי מכילה תחילת טווח, סוף טווח, ומידע לגבי הטווח – כמו קוד ISO של המדינה והשם שלה. שורה לדוגמא:
"201620312","201674095","US","USA","UNITED STATES"

נניח שאנחנו שומרים את הנתונים האלו לקובץ בצורה הזו:
לכל מדינה:
4 בתים: תחילת טווח.
4 בתים: סוף טווח.
2 בתים קודISO
X בתים שם מדינה.

יש פה בעיה, כי שם המדינה הוא לא באורך ידוע, מה שלא מאפשר גישה ישירה לנתונים (כדי להגיע לשורה X צריך לסרוק את כל השורות שלפניה).
פתרון חלופי הוא לחלק את הקובץ לשני תחומים כדלקמן:
חלק ראשון בקובץ, לכל מדינה:
4 בתים: תחילת טווח.
4 בתים: סוף טווח.
2 בתים קודISO
4 בתים ההיסט של שם המדינה בתוך הקובץ
חלק שני בקובץ, לכל מדינה:
X בתים: שם המדינה.

זה כבר יותר טוב, עכשיו אפשר לחפש חיפוש בינארי בחלק הראשון, ולמצוא את שם המדינה לפי ההיסט שמצאנו ברשומה בחלק הראשון.

נניח שאלו הנתונים שלנו:
1. 1 עד 10 : ישראל
2. 10 עד 20: הודו
3. 20 עד 22: סין
4. 25 עד 30: ארצות הברית

אפשר לשים לב שלמעט המעבר מסין לארצות הברית טווח n תמיד מתחיל איפה שטווח n-1 נגמר.
ככה זה גם במציאות, כמעט תמיד אין חורים בין הטווחים.
זה מאפשר לנו ליעל את צורת השמירה: פשוט נשמור רק את תחילת הטווח של כל שורה, ונשתמש בתחילת הטווח של השורה הבאה בתור סמן לסוף הטווח.
אבל אני שומע את הצעקות: אבל מה עם סין? היא תקבל עוד שלוש כתובות!
הפתרון הפשוט למדי הוא להוסיף שורת סרק אחרי סין, שסוגרת את הטווח שלה:
1. 1 : ישראל
2. 10: הודו
3. 20 : סין
4. 22: אף אחד
4. 25 : ארצות הברית
…
חסכנו בממוצע 4 בתים מתוך 14, שזה כשלושים אחוז מנפח הנתונים, בלי לאבד שום דבר.
כמובן שהאלגוריתם של החיפוש יצטרך להתחשב בשורות ששייכות ל"אף אחד", מה שיסבך אותו, אבל זה שווה את המחיר.

אופטימיציה נוספת שמתבקשת היא לשמור את שם המדינה ואת הנתונים הנילוים (קוד מדינה וכו') פעם אחת בלבד לכל מדינה.
מה שיוביל לחסכון רציני נוסף בנפח הנתונים.

למעשה הקובץ שIP2C מייצרת אפילו יותר חסכוני מזה, החלק הראשון של הקובץ מכיל שורות בצורת:
IP התחלה: 4 בתים.
קוד מדינה: 2 בתים.

החלק השני של הקובץ מכיל עוד טבלה מאפשרת לגשת לשאר הנתונים (שם מדינה וכו'), אבל מחיב הפעלת חיפוש בינארי שני (במילים אחרות, המרתי את הנפח הדרוש להיסט בזמן מעט גבוה יותר לחיפוש).
בממוצע, כל טווח מהקובץ המקורי תופס כ7 בתים בקובץ, מאד חסכוני לכל הדעות.

גישה לנתונים

עכשיו שסגרנו את מבנה הקובץ (פחות או יותר), הגיע הזמן לדבר על דרך הגישה אל הנתונים.
יש כמה דרכים, שלא כולן ישימות בכל שפה:
טעינת הקובץ לזכרון
הגישה הטבעית שכמעט כולם יבחרו תהיה להעלות את כל הקובץ לזכרון (סך הכל חצי מגה במקרה שלי) ולחפש בתוכו.
יש שתי חסרונות לגישה הזו: הראשונה היא צריכת הזכרון שפרופורציונית לגודל הקובץ, והשניה היא שהזמן לחיפוש הראשון הוא גדול כי משלמים גם על טעינת הקובץ.
מצד שני החיפוש עצמו מהיר מאוד, הכי מהיר למעשה מכל הגישות האחרות.
הגישה הזו לא אופטימלית לPHP בדרך כלל, כי בכל בקשה נצטרך לטעון את הקובץ מחדש.
הגישה הזו ממומשת כרגע במימוש בJava בלבד.

חיפוש ישירות על הקובץ
הטכניקה הזו היתה הרבה יותר נפוצה בעבר, כש640K היו צריכים להספיק לכולם.
במקום לטעון את הקובץ כולו לזכרון, מבצעים את החיפוש הבינארי ישירות על הקובץ.
החסרון הוא שזה איטי משמעותית יותר מחיפוש בזכרון, והיתרונות הם שצריכת הזכרון מינימלית ושהמחיר של החיפוש הראשון זול בדיוק כמו של אלו שאחריו.
הגישה הזו מתאימה מאוד לPHP, במיוחד אם צריך לבצע מספר קטן של חיפושים בכל בקשה.
מימוש: Java וPHP.

קובץ ממופה זכרון
קובץ ממופה זכרון (Memory mapped file) לוקח את הטוב משני העולמות. מצד אחד לא טוענים את כל הקובץ לזכרון, מצד שני המהירות קרובה למהירות חיפוש בזכרון.
PHP לא תומך בזה, אבל ג'אווה כן – וקיבלתי תוצאות יפות למדי עם זה.
היתרונות הם שכמו בחיפוש ישירות על הקובץ, לא טוענים את כל הקובץ לזכרון בהתחלה ולכן החיפוש הראשון יהיה מהיר בערך כמו החיפוש הראשון בחיפוש ישיר על הקובץ, אבל החיפושים הבאים יתקרבו למהירות חיפוש בזכרון. החיסרון העיקרי הוא שלא כל הפלטפורמות תומכות בזה.
מימוש: Java בלבד.

זכרון משותף
זכרון משותף (Shared memory) היא עוד גישה. הפעם הקובץ נטען פעם אחת ויחידה לזכרון, ונשאר שם. הגישה הזו מנטרלת את הבעיה המרכזית של PHP עם הגישה של טעינת הקובץ לזכרון (שצריך לטעון אותו כל פעם מחדש), אבל עדיין סובלת מהבעיה של צריכת זכרון גבוהה (למעשה הבעיה מחריפה גם הזכרון יהיה בשימוש גם אם אף אחד לא רוצה לבצע חיפוש במשך שבוע).
גם PHP וגם Java תומכים בזכרון משותף, אבל לא בדקתי את הביצועים של מימוש כזה.
מימוש: לא ממומש.

IP2C משוחררת ברשיון GPL2, והיא קלה מאוד לשימוש.