קחו את המצב הבא:
יש שתי טבלאות עם כחצי מילארד רשומות בכל אחת.
באופן חד פעמי – אתם צריכים לעבד את טבלא א' בבלוקים של כמה אלפים בכל פעם.
עבור כל בלוק, אתם צריכים לגשת לטבלא ב' ולהשלים משם נתונים.
אתם צריכים לגשת רק לחלק מהעמודות בטבלא ב', אבל הביצועים חרבנה.
שליפה של כמה אלפי רשומות מטבלא ב' במכה עובד בקצב של כמה מאות בשניה:
[code lang="sql"]
SELECT a,b,c FROM table WHERE id IN (….)
[/code]
אז מה עושים כדי לשפר את המצב?
ניסיתי להוסיף שכבה של זכרון מטמון, בכל גישה לבסיס הנתונים לטעון קצת יותר שורות מתוך הבנה (נכונה) שבמקרה הספציפי שלי זה שנגעתי ברשומה אחת אומר בסבירות גבוהה שאני אצטרך לגעת בשכנות שלה.
למרבה הצער זה לא שיפר ביצועים, ואחוזי הפגיעה במטמון היו נמוכים מאוד.
הרעיון הבא שלי היה לשמור את הנתונים המעניינים על הדיסק בצורה בינרית, ממויינים לפי שדה הid, כאשר הפורמט הוא פשוט רשומה אחרי רשומה.
ברגע שכל הנתונים בקובץ, אפשר לטעון אותו לזכרון פעם אחת, ולבצע עליו חיפוש בינארי זריז כדי למצוא כל רשומה.
רעיון פשוט, אבל המימוש נתקל בכמה קשיים:
נפח הנתונים המעניינים במקרה שלי הוא כ14.4 ג'יגה בייטים, כל רשומה שוקלת 24 בתים, ויש 600 מליון רשומות כאלו.
אין הרבה מחשבים שמסוגלים להעלות כזו כמות של מידע לזכרון, בהתחלה חשבתי שנתונים ישקלו "רק" 12 ג'יגה, ולכן היה ישים לטעון את כולם לזכרון של שרת עם 16GB זכרון, אבל 14.4 ג'יגה זה כבר גבולי מדי.
בעיה נוספת היא שג'אווה, השפה בה אני מממש את העניין – לא תומכת במערכים גדולים מכ2 מילארד איברים (גם לא בJVM של 64 ביט), ולכן מערך הבייטים הגדול ביותר שאני יכול ליצור לא מספיק גדול בשביל להחזיק את הקובץ בזכרון.
כדי לפתור את הבעיה של המערך הקטן מדי, חילקתי את המערך לכמה מערכים של 2GB, וכשלב מקדים לחיפוש הבינארי בתוך המערך – אני עובר על המערכים בזריזות כדי להבין באיזה מהם נמצא הערך שאני מחפש (רק מביט באיבר הראשון והאחרון כדי לראות אם הID שאני מחפש נמצא ביניהם).
כדי לפתור את הבעיה השניה, כתבתי שכבה פשוטה של שרת לקוח, כאשר אני יכול להריץ כמה שרתים שאני רוצה על כמה מכונות שצריך, כשכל אחד מהם מעלה חלק אחר מהקובץ לזכרון.
לקוח פשוט פונה לכל השרתים ושואל ומבקש מהם על גבי חיבור TCP לחפש עבורו את הנתונים שמתאימים לרשימת מזהים.
בבדיקה ביצועים ראשונית יצרתי קובץ מ26 מיליון רשומות, וחיפשתי בתוכו 2 מיליון רשומות. הקצב היה קרוב למיליון רשומות בשניה, מה שאומר שהבעיה נפתרה.
ניצחון.
חשבת אולי ליצור Clustered Index על הרשומה בטבלה B שאתה מחפש עליה? נשמע כאילו זאת הדרך שבה הDATABASE יעשה בעצמו את מה שאתה עשית פחות או יותר. מינוס הביזוריות.
אולי באורקל קוראים לזה אחרת, יצא לי לעבוד רק עם SQL SERVER ברמה כזאת.
אני לא חושב שMySQL תומך בClustered index.
בכל מקרה, הוא יצטרך להיות הרבה יותר גנרי ממה שאני מימשתי, ולכן הרבה פחות יעיל.
אין שום סיכוי שבעולם שהביצועים של בסיס נתונים בגודל כזה יתקרבו בכלל למליון רשומות בשניה.
נשמע בדיוק כמו מה שmemcached עושה
http://www.danga.com/memcached/
זה לא מה שmemcache עושה.
יש דמיון, אבל ההבדל הוא שבמקרה הזה אני שומר את הנתונים בזכרון כמערך אחד גדול (או מספר קטן של מערכים גדולים) כדי לחסוך זכרון.
מערך של רשומות הוא הרבה יותר קומפקטי בצריכת זכרון מטבלאת גיבוב של אותם נתונים.
בנוסף, אין לי שום צורך באלגוריתם ניקוי מטמון (LRU) כמו של memcache, ואין לי אפשרות לעדכן את הנתונים בזמן ריצה.
עצם זה שהנתונים לא משתנים מאפשר לי להכין את המערך ככה שהגישה תהיה מהירה במיוחד (לא צריך לדאוג שאיבר חדש ישמור על המיון של המערך – כי אין איברים חדשים).
אם הקשר בין טבלא א' לב' הוא בערך 1:1, עוד אפשרות היא לבנות טבלא חדשה שמאחדת את השורות המתאימות משתי הטבלאות לשורה אחת. בכל אופן, אם כמויות המידע באמת גדולות, הדבר הנכון הוא לפצל את המידע.
נדב, ליצור את הטבלא המדוברת יקח ימים אם לא שבועות.
לגבי לפצל: מסכים לחלוטין – זו הסיבה שאני עושה את כל העניין. זה חלק מתהליך פיצול של הנתונים.
אם אתה טוען כל כך הרבה רושמות לאפיקציה (ולכן לזכרון ) אתה בטח עושה משהו לא בסדר. בדיוק לשם כך נועדו מסדי נתונים.
כמו שכבר אמרו פה באורקל ניתן ליצור cluster שמאפשר שליטה במיקום הפיסי של הנתונים על הדיסק. גישה לנתון במקרה הזה תהיה ב O(1).
גישה לדיסק זה באמת זמן קבוע O(1), אבל הקבוע יכול להיות גדול מדי עבור הבעייה שמנסים לפתור (ה- seek time בסדרי גודל של עשרות מילישניות), וגישה לזכרון נמדדת בננו-שניות. להעלות את כל הנתונים ל- RAM של כמה מכונות זה לא בהכרח לא בסדר – זה רק עסקת חליפין.
אני מסכים לגבי ה- memcached. זה לא בדיוק אותו דבר, אבל יכול מאוד להיות שהוא היה מספיק לך.
אישית, אם memcached לא היה מספיק לי, הייתי עושה מנסה הטמעה של Sphinx – http://www.sphinxsearch.com לפני שהייתי מממש בעצמי את מה שמימשת.
אבל, אם כבר מימשת – שחרר לקהילה, נראה לי שימושי :).
שם, סיסמאות ואמרות כנף לא משכנעות. מספרים קשים כן.
אם אני מסוגל לקחת צוואר בקבוק ולהעלים אותו תוך שימוש בהרבה זכרון (וכתוצאה מכך לחסוך שבועות של זמן – I shit you not), אז ברור שאני עושה את הדבר הנכון.
TGB,
פונקציונלית MEMCACHE היה מספיק, אבל צריכת הזכרון שלו תהיה בהכרח יותר גבוהה משמעותית משל הפתרון שלי, וכשמדובר בג'יגות של מידע שצריכים להכנס לזכרון, זה משחק תפקיד משמעותי מאוד.
על פניו לא נשמע שספינקס מתאים, ולו בגלל שאין שום דבר שקשור לחיפוש טקסט מלא במה שעשיתי.
לגבי שחרור לקהילה:
בשמחה, אבל מה שיש לי לא מספיק גנרי כדי להיות שימושי כמו שהוא כרגע, וקשה לי לראות אותי מוצא את הזמן להפוך אותו לגנרי כזה, יש לי מספיק פרוייקטים.
אם תרצה לקחת את זה על עצמך, רק תגיד ותקבל את הקוד. (ג'אווה).
ספינקס היה עושה עבודה מעולה, בהנחה שהיית מקנפג אתו נכון. אם היית מקנפג אותו להתאמות של אחד לאחד, ומוריד את כל אופציות החיפוש המתקדמות יותר זה היה יכול להיות מרשים מאוד. אני מניח שהפתרון שלך בכ"ז קצת יותר יעיל (בהכרח בזיכרון, ואולי גם בזמן, אבל לא בטוח), השאלה היא מה ההפרשים. Guess we'll never know.
הייתי שמח לקבל את הקוד, אבל גם לי יש כמה פרוייקטים משלי.
אולי מישהו אחר מהקוראים מרים את הכפפה?
תשקול לשחחרר פה את הקוד כמו שהוא, להגיד שהוא לא גנרי, ולבקש ממי שהופך אותו לקוד כמו שצריך שישחרר אותו, ויעשה טראקבאק לפוסט שלך.
TGB:
http://svn.firestats.cc/stuff/trunk/dindex/
הקוד מתקמפל ועובד, אבל מתאים למבנה נתונים מסויים.
אם מישהו רוצה לשפר ולהפוך את זה ליותר כללי, בשמחה.
אני גם מוכן לתת גישת כתיבה לריפוזיטורי למי שיקח עליו את העניין.
הקוד ברשיון BSD.
סחטיין עליך!
שליפה סדרתית מהדטהבייס, של כמה מאות רשומות, כ"א בגודל של סה"כ 24 בתים, לפי ID, התבצעה בקצב של רק כמה מאות בשניה?
נשמע די איטי, בטח מיותר לשאול אם ה- ID היה מאונדקס – אם הוא לא היה מאונדקס הקצב היה רשומה אחת בכמה מאות שניות.
גודל רשומה כאן הוא נורא קטן (24 בתים), וכמות הרשומות היא עצומה, לכן האינדקס גם הוא יהיה מליוני רשומות, ובגודל של מאות-אלפי מגה. מה שהופך אותו ללא יעיל באותה מידה כמו הטבלה שאותה הוא מאנדקס, אלא אם כן הוא מורכב מכמה רמות של אינדקס לאינדקס
אני מרשה לעצמי לנחש שאו הנתונים בטבלה, או אפילו האינדקס עצמו, לא אוחסנו בדיסק בבלוקים עוקבים, ולכן רובו ככולו של זמן השליפה בוזבז על תזוזות של ראש הדיסק (כלומר העדר של מפתח צבר ( http://en.wikipedia.org/wiki/Index_(database)#Clustered ) כמו שאוריאל שיער).
תכלס יכול להיות שהיית יכול להמנע מהפיתוח שעשית בעזרת DBA טוב, או DB טוב יותר, אבל זה עדיין נשמע מגניב! אז אתה הולך לפתח ענן משלך ולהתחרות ב- EC2? 🙂
טוב, בתכנון שלי כבר כמה שבועות לקרוא את הפוסטים שלך מ- 2005 ועד להיום, צפה לטוקבקים מתהום הנשייה.
גילי, השליפה לא היתה סדרתית.
תקרא שוב, יש שתי טבלאות, מאחת אני שולף סדרתית והמהשניה אני שולף כדי להשלים את הנתונים מהשליפה הראשונה.
הרשומות עצמן בגודל של בערך 200 בתים, אבל שלפתי רק 24 בתים.
אגב:
לא מדוייק לומר שאינדקס על טבלא עם עמודה בודדת הוא לא יעיל כמו הטבלא אותה הוא מאנדקס.
אינדקס מאפשר גישה בזמן לוגריתמי לפי המפתח, לעומת גישה בזמן לינארי בטבלא בלי אינדקס.
מה שכן, אינדקס בגודל של הנתונים עצמם יכול להיות בעיה, במקרה הזה הגודל של האינדקס מנע ממנו להכנס כולו למטמון הרלוונטי ופגע בביצועים.
כהערה:
רק להוריד את כל הנתונים לדיסק עם SELECT a,b,c FROM table INTO OUTFILE file.txt לקח שלושה ימים, וזה כן היה סדרתי. הסיבה היא שINNODB שולף בצורה ממויינת לפי האינדקס הראשי, והנתונים לא אוכסנו בבלוקים עוקבים ולכן אפילו שליפה כזו היתה איטית מאוד.
בכל מקרה, הטכניקה הוכיחה את עצמה וחסכתי ימים רבים של עבודה, אם לא שבועות.
מצפה בקוצר רוח לטוקבקים מתהום הנשיה 🙂