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, והיא קלה מאוד לשימוש.

Facebook Comments

8 תגובות בנושא “IP2C תכנון, מימוש ושיקולי יעילות”

  1. אני חושב שאתה פספסת נקודה. אני לא אעשה חיפוש לIP שאינו מקושר למדינה לעולם, כי לא יהיה קיים דבר כזה. לפיכך, אני יכול רק לציין שבמספר 20 התחילה סין, ואין צורך לציין ש22 עד 25 זה אף אחד. לא יצא לי לבדוק את 22 בשום סיטואציה. ככה אני גם מוריד את הסיבוכיות של הקוד.

  2. אם אתה חושב שכל IP בעולם משוייך למדינה אתה טועה.
    אם אתה חושב שכל IP שמשוייך למדינה גם מופיע בבסיס הנתונים שלך ככזה אתה טועה שוב.
    חוץ מזה, שים לב שאני לא מציין ש22-25 זה אף אחד, אלא רק שזה לא שייך לסין.

  3. קודם כל, כל הכבוד.

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

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

    אבל שלוש הערות:

    1. תודה שהוספת את שורת ה- CSV.
    2. בדוגמה "נניח שאלו הנתונים שלנו:", ציינת עבור כל טווח א' במסתיים בכתובת X את טווח ב' שבא אחריו המתחיל בכתובת X במקום בכתובת X+1. זה עניין מינורי כי רוב האנשים מבינים למה אתה מתכוון (אלא אם כן אני הוא זה שלא הבין נכון).
    3. אני קורא עכשיו ספר על מסדי נתונים ("בסיסי נתונים טבלאיים ושפת SQL – עקרונות ועיצוב"), וזה מביא אותי לשאלה הזו: אם למשל, במקום להגדיר פורמט בינארי מישלך היית מתמש ב- SQLite, האם לא ניתן היה גם להתגבר על מגבלות מסדי הנתונים שציינת וגם להשיג תוצאות מהירות? עד כמה שאני יודע, PHP תומך בו, ואני מניח שגם JAVA.

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

    עוד חיסרון של sqlite הוא שגם אם הוא נתמך, הוא מביא תלות נוספת בספריות ריצה של sqlite. אם אתה כותב משהו שמכוון לאנשים שלא בהכרח שולטים בתצורה של המכונה שהם מריצים עליה (כמו פיירסטטס) אתה לא רוצה תלויות חיצוניות.

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

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

סגור לתגובות.