-->

יום רביעי, 19 באוקטובר 2011

שיקולים בתכנון מקביליות: Beyond Threads

מקביליות (concurrency) מתורגמת ע"י לא מעט אנשים ל Thread ו synchronized (בג'אווה) - דבר שהוא נכון, אבל מסתיר כמה אלטרנטיבות חשובות.

  • האם חשובה לי יותר פשטות הקוד או יעילות? (או בעצם - עד כמה)
  • באיזו פרדיגמה של סנכון הכי נכון לעבוד עבור הבעיה הנוכחית?


Thread נתפס כ"אמצעי להאצת התוכנה", אבל זה לא בדיוק נכון. אם יש לי משימה מקבילית שכוללת הרבה I/O (כגון client להורדת קבצים מהאינטרנט) הגדרת thread לכל קובץ או segment שמורד היא הדרך הקלה לפיתוח, אבל לא הדרך היעילה.

דרך יעילה יותר היא הגדרת thread יחיד שעובד עם ערוצים רבים של IO אסינכרוני (כגון channels בספרית java.nio. מקביל לפקודת select ב C של unix/linux, למי שמכיר). בגישה זו יש thread יחיד שמאזין לרשימת ערוצי ה IO הרלוונטים (sockets מאתר ההורדות + streams לכתיבה לקבצים) וכל פעם שערוץ IO זמין לקבל פקודה (התקבל packet ברשת או נסתיימה כתיבה של באפר לדיסק)ה thread שלנו יתעורר ע"י event. עליו לעשות איטרציה ולבדוק איזה ערוצ(י)  מוכנים, לבצע את הפעולה ולחזור לישון עד פעולת ה I/O הבאה שהסתיימה.


אז מה חסכנו בעבודה עם thread יחיד (בסדר עולה):
  • יצירה של thread היא פעולה יקרה (thread pool עוזר להתמודד)
  • תזמון ה threads השונים הוא overhead.
  • לcontext switch בין threads יש מחיר.
כתיבה ב Thread אחד היא בהחלט יותר יעילה! בכל זאת ברוב הפרוייקטים הייתי מעדיף לעבוד עם מספר threads. דוגמת אפליקציית ההורדות היא דוגמא פשוטה במיוחד שבה כל ה threads הם אחידים, אבל לרוב המצב יותר מורכב. כמות הרווח מ thread יחיד תתרום, נאמר, 5% לביצועי המערכת? לא שווה ברוב המקרים לייצר קוד מסובך בשביל שיפור שכזה.
סיכום: thread יחיד היא אופטימיזציה טובה למקרים כמו המתואר לעיל.

היבט חשוב נוסף הוא מערכת multi-core שאותה ניתן לנצל רק עם מספר threads שיתאים למספר ה cores.
אם הייתי מריץ את המערכת הנ"ל על מערכת עם ארבעה cores (וייתכן היה שיש לי מספיק ערוצי IO להעסיק את ה thread עד תום) - הייתי רוצה 4 threads שינצלו את ה CPU עד הסוף. דוגמא קלאסית היא WinZip שעובד עם thread בודד מול תוכנות דומות (winrar, 7zip) שעובדות עם מספר threads:


אפרופו multi-core: הנוסחא המקובלת לבחור כמה threads לייצר ליעילות מרבית היא:

# threads = # of cores / (1 - blocking coefficient)
כאשר המקדם (Blocking Coefficient) הוא ערך מ 0 עד 1 כמה אחוז מהזמן ה thread ישן בין פעולות IO. אם יש לי מערכת עם 4 cores שישנים 30% מהזמן, אני ארצה לעבוד עם 6 threads.

Runtime.getRuntime().availableProcessors();
ייתן לי בג'אווה את מספר הcores הלוגים (יתחשב ב hyperthreading).

אסטרטגיות מקביליות

אחד הדברים שכן כואבים במספר threads הוא עלות הסינכרון. אם לא נסנכרן - יכולים להיות שיבוש מידע, deadlocks ו livelocks. אם אנחנו מסנכרנים, אז המחיר הוא בביצועים: כל lock שמגיעים אליו n threads גורם לכך ש n-1 יאלצו "לישון" למרות שהם רוצים לעבוד. דמיינו בעבודה את קבצי ה excel שמישהו פותח ואף אחד לא יכול לעבוד עליהם (כי הם נעולים), אבל במקום לעבור למשימה אחרת - כל מי שניסה לפתוח את הקובץ חייב ללכת לישון! (ועד עובדי חברת החשמל - רעיון לעיונכם). יצירת המון threads במקום לרוב לא תשפר את המצב: תשלמו הרבה על context switch בלי לפתור את הבעיה המהותית.

יתרה מכך, סינכרון חוסם את מידת ה scalability האפשרי בריבוי cores.
בהינתן מערכת ש 5% מזמן הביצוע שלה הוא קטע מסונכרן, אפילו אם יהיה לי את ה banana bridge i9-9990EX של אינטל שיצא ב 2024 עם 6400 cores, לא אוכל להשיג יותר מפי 5 ביצועים מאשר על מעבד ה i5 ארבעה cores הסטנדרטי שלי (בהנחה שלא היה חיזוק כוחו של כל core ושזו משימה יחידה שאני מריץ). נשמע דיי מאכזב למי שמתכוון לחכות לbanana bridge מעכשיו.

עקרון זה ידוע כ Amdahl's Law וניתן לקרוא עוד עליו כאן. הפיתרון הוא לצמצם את כמות הסינכרון למינימום.


אז איך מפחיתים את כמות הסינכרון למינימום? ישנן מספר אסטרטגיות להתמודדות עם סנכרון:
  • mutable synchronization
  • isolated mutability
  • pure immutability
  • actors
mutable synchronization
זו הגישה שרובנו בוחרים בד"כ באופן אוטומטי בלי לשים לב. העקרון הוא לשים synchronized על כל מתודה שיש בה שינוי state שיכול להשתנות בין threads. זו הגישה הקלה והפחות יעילה. דרך שיפור מהירה היא לכתוב את ה synchronized בבלוקים הכי קטנים שאפשר ולא בחתימת המתודה (למי שלא מכיר - תנסו - אפשר לכתוב אותם אפילו על שורה בודדת).


isolated mutability
גישה זו היא צעד אחד הלאה, לצמצם את כמות הסינכרון למינימום - שזה המשתנים עצמם. במקום לעבוד עם Long אני אעבוד עם AtomicLong של java.util.concurrent שמספק לי פעולות אטומיות כגון getAndIncrement או incrementAndGet
שימוש בהן יאפשר לי לצמצם את הסינכרון לנתונים עצמם ולא מעבר.

pure immutability
זו גישה הפוכה לגמרי שאומרת - אל תשנה משתנים. כל ערך שתיצור יהיה immutable (כמו String), כל פעם שתצטרך ערך אחר - צור אובייקט חדש. גישה זו דיי קשה ולא כ"כ נתמכת בג'אווה. אם פיספסתי - הקומפיילר לא יתריע וגם יש כמה מצבים בעייתים שאצטרך להתחכם בהם. Closure דוגמא לשפה שתומכת בגישה זו באופן מובנה.

actors
זו גישה שפופולארית היום ב scala (השפה שנוצרה ל multi-core ו scalability). הגישה מדברת על active objects או actors שהם אובייקטים "חיים" - כלומר ה threads. לכל actor יש תור נכנס ("דואר נכנס") והם מתקשרים אחד עם השני רק בהודעות אסינכרוניות (שמונעות מצב של deadlock). בזכות התקשורת - אין צורך בסנכרון בכלל. גישה זו ניראית מוצלחת וישימה, לא ניסיתי בעצמי - אך שמעתי כמה סיפורי הצלחה ממקור ראשון. נראה שהיא גם עובדת יפה כשהמערכת גדלה והופכת למסובכת.
אמנם בג'אווה אין תמיכה בשפה ל actors אך יש מספר ספריות (כגון akka או GPars) שלמרות שנכתבו בשפות שונות על ה JVM - עובדות יפה מתוך Java. הגישה מתאימה, אגב, גם לסנכרון בתוך אותו JVM וגם ב remoting בין JVMs שונים (כגון nodes שונים ב cluster).


-----

קישורים
מעבדי XEON מול Power8 של יבמ: http://anandtech.com/show/9193/the-xeon-e78800-v3-review



3 תגובות:

  1. תודה על פוסט יפה ותמציתי על שיטות מיקבול.

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

    השבמחק
  2. יפה מאד. :)

    עכשיו אני יכול להביא קישור לכאן במקום להתווכח עם אנשים במשך שעות ולנסות להסביר להם שליצור 5,000 threads עם פעולות סינכרוניות, שעושות block, לא יעזור להם יותר מאשר ליצור אחד כזה. במקרה הטוב, בתנאי ויש לך הרבה ליבות... פי 4? שזה כלום לאומת מה שאפשר לעשות עם פעולות אסינכרוניות.

    השבמחק