Liran Chen's Blog

.Net Internals, Development, Multithreading - and More!

January 2010 - Posts

The Case of Delayed ACKs and Nagle's Algorithm
למרות שההשלכות של השילוב בין Nagle's Algorithm ו-Delayed ACKs בעבודה עם TCP מתועדות היטב בספרות, עדיין מדובר בפרט שלא פעם קל לשכוח ממנו ולא לקחת אותו בחשבון כשצריך. מאחר ולסימפטומים הבעייתים של השילוב ביניהם יש נטייה לצוף רק תחת אוסף של תנאים מקדימים, יכול לעבור קצת זמן עד שמשייכים את את ה"תופעות המעניינות" לשימוש בשני האלגוריתמים הנ"ל. במקרה הזה, ככל שהסימפטומים שנוצרים עקב השילוב חריפים יותר, כך גם יותר קל להבין את המקור שלהם.
אבל קודם כל, נבין מה הרעיון מאחורי כל אחד מהאלגוריתמים האלה, ולמה למעשה האינטרקציה ביניהם יכולה להביא לתוצאות לא רצויות.

Delayed ACKs
בגלל ש-TCP דואג להבטיח שכל פאקט (Packet) שנשלח ברשת אל לקוח מרוחק באמת יצליח להגיע אליו, הוא זקוק לאיזשהו אישור (Acknowledgment) מהצד המקבל שאותו פאקט באמת הגיע אליו. לכן, אותו לקוח שקיבל את ההודעה החדשה, חייב לדאוג לשלוח בחזרה הודעת ACK מתאימה שתאשר את קבלתה.
הבעיה עם שימוש בהודעות בלעדיות עבור ACKs היא שאנחנו מהר מאוד יכולים למצוא את עצמנו "מציפים" את הרשת בהודעות חסרות תוכן שכל משמעותן היא בסך הכל להגיד "כן, קיבלתי את ההודעה שלך" (אם מחברים את הגודל המינימלי עבור ה-Header'ים של TCP ו-IP בלבד [גם מבלי להחשיב את התוספת של Ethernet] כבר מגיעים ל-40 בתים [ועבור IPv6 המספר הזה כבר גדל ל-60 בתים]).
לכן, על מנת לחסוך את ה-Overhead, הוגדר השימוש ב-Delayed ACKs. הרעיון הוא שבמקום שנענה בהודעה חדשה על כל פאקט שאנחנו מקבלים, יוצאים מתוך הנחה שהאפליקציה שלנו כנראה הולכת לשלוח "איזשהיא" הודעה בזמן הקרוב עבור מי ששלח לנו אותה ההודעה המקורית (לא בהכרח מדובר בהודעת Reponse, אלא כל הודעה שהיא), ולכן למעשה נוכל "לרכב" על ההודעה שהאפליקציה רוצה לשלוח, ונוסיף לה את ה-ACK על הפאקט שקיבלנו מקודם. כך שבצורה הזאת אנחנו יכולים לחסוך לא מעט תעבורת רשת מיותרת.
בדרך כלל נהוג להשתמש בעיכוב של 200ms עבור שליחת ACK'ים (האופי המדוייק של הערך הוא גם תלוי במימוש של הפרוטוקול. למשל האם המפתח החליט להשתמש בטיימר שמתעורר תמיד כל 200ms מאז פתיחת הסוקט, או שהוא פותח טיימר חדש רק כשהוא צריך לשלוח ACK?). ב-Windows ברירת המחדל היא 200ms גם כן, אבל אם רוצים, ניתן לערוך את הערך של
TcpDelAckTicks ב-Registry ולקבוע אותו היכנשהו בין הגבולות של 0ms עד 600ms (בתור אנקדוטה, ה-Host Requirements RFC אוסר על שימוש ב-delay הגבוה יותר מ-500ms).
כדאי גם לציין שעל פי ה-RFC גם אין צורך לשלוח ACK על כל פאקט שאנו מקבלים. הרי ש-ACK אחד יכול להחשב בתור אישור קבלה עבור מספר פאקטים שונים. דוגמה למקרה כזה היא שעמדה א' שולחת 5 הודעות נפרדות בהפרשים של 10ms לעמדה ב'. ברגע שההודעה הראשונה מגיעה לעמדה ב', נפתח טיימר ל-200ms שמטרתו לשלוח ACK על ההודעה הזאת (נצא מתוך הנחה שמדובר בממשק חד-כיווני ושהאפליקציה לא מתכוונת לשלוח שום הודעה בעצמה). עד שאותו טיימר יספיק לפקוע, אנחנו מספיקים לקבל את שאר ארבעת ההודעות הנותרות. אבל בכלל שאנחנו כבר יודעים שיש לנו הודעת ACK שנמצאת כבר "בקנה", אנחנו רק צריכים לדאוג לעדכן אותה כך שהיא תאשר גם את קבלת ההודעות הנוספות. לאחר פקיעת הטיימר, תשלח הודעת ACK בודדת שתאשר את קבלת כל 5 ההודעות.
נוסף על כך, לא מדובר בטריגרים היחידים לשליחת ACK. למשל, טריגר אחר לשליחה הוא התמלאות ה-Receive Window (מירב הבתים שאנחנו יכולים לקבל ללא שליחת ACK), עוד אחד הוא שימוש בפוליסת ה-"ACK עבור כל הודעה שניה" שדואגת לשלוח ACK עבור כל פאקט שני שאנחנו מקבלים. ב-Windows אפשר גם לשנות את מספר ברירת המחדל הזה (2), על ידי עדכון הערך של TcpAckFrequency ב-Registry.
 
Nagle's Algorithm
למרות שאינו קשור לשימוש ב-Delayed ACKs, אלגוריתם זה בא לפתור בעייה דומה שמתרחשת בצד השני של שולח הנתונים.מאותה הסיבה שכדאי להמנע משליחת הודעות ACK בודדות וקטנות על הרשת, כך כדאי גם להמנע משליחת הודעות קטנות "רגילות" מצד האפליקציה, משום שגם במקרה כזה אנחנו נסבול מה-Overhead של שליחת ה-Header'ים, בעוד שגודל ההודעה שהאפליקציה רוצה לשלוח הוא מאוד קטן.
על פי האלגוריתם, הפרוטוקול רשאי לדחות פעולות שליחה קטנות על מנת לבצע "Buffering" להודעות כך שבסופו של דבר ישלח רק פאקט בודד שמכיל בתוכו מספר הודעות שונות. התשובה לשאלה "מתי להפסיק לצבור הודעות ולשלוח את הפאקט" אינה שרירותית והיא מסתמכת על קצב קבלת ה-ACK'ים מהלקוח המרוחק. הרעיון הוא שכל עוד לא קיבלנו ACK על הפאקט האחרון ששלחנו, אין טעם שנשלח פאקט נוסף. לכן, בזמן שבו אנחנו מחכים לקבלת ה-ACK על הפאקט הקודם, אנחנו מבצעים צוברים את כל ההודעות שהאפליקציה מעוניינת לשלוח (תחת גבולות ה-MSS). ברגע שנקבל את ה-ACK על הפאקט הקודם, כל ההודעות שהצטברו עד כה ישלחו בתוך פאקט בודד. מה שיפה באלגוריתם הזה הוא שהוא מתאים את עצמו ללקוח ששולח בחזרה ACK'ים. ככל שקצב קבלת ה-ACK'ים גודל, כך גם יגדל קצב שליחת ההודעות החדשות.

אז כפי שזה נראה, לשני האלגוריתמים שהזכרנו עכשיו יש "זכות קיום" לגיטימית מאחר והם באים לפתור בעיות אמיתיות ומהותיות בטבען. עם זאת, מה יקרה כשנשלב בין שניהם? מצד אחד כל אחד מהם ינסה לצמצם את שליחת ה-tinygrams בצד שלו (שליחת הודעות אפליקטיביות לעומת שליחת ACK'ים), אבל מצד שני, תחת תנאים מסויימים הם יכולים לגרום לעיכובים משמעותיים בתדרי שליחת ההודעות על גבי הרשת. הדוגמה הבולטת ביותר לכך היא אצל ממשקים חד-כיווניים, שם רק צד אחד שולח הודעות, בעוד שהצד השני אף פעם לא שולח הודעה בחזרה (למשל לקוח שהתחבר לשרת וכעת רק מזין אותו בנתונים, בלי לקבל שום Feedback בחזרה). במקרה כזה, גם אם האפליקציה שלנו שולחת הודעות ללא הפסקה בקצב מאוד גבוה, אנחנו עדיין צפויים לחוש בקפיצות של עד 200ms מהזמן שהאפליקציה רצתה לשלוח את ההודעה, עד שהפרוטוקול החליט לשלוח אותה בפועל. במקרים אחרים, גם אצל ממשקים דו-כיווניים, יתכנו מצבים בהם אחד מהצדדים מפסיק לשלוח הודעה לכמה רגעים, ובעקבות זאת הוא גם מפסיק לקבל הודעות חדשות במשך 200ms. במקרה כזה, אנחנו עשויים לראות הקפיצות בעיכוב שליחת ההודעות רק "לפעמים" בלי הסבר ברור (וגם אז, לא בהכרח נחכה 200ms שלמים). מידת ההשפעה והחומרה של עיכוב כזה על האפליקציה יכול להשתנות בהתאם לאופי האפליקציה.



כדי להמחיש את התופעה דרך הקוד, אפשר לקחת בתור דוגמה את התוכנית הבאה, שמודדת כמה זמן לוקח לנו לקבל 2 הודעות שכביכול נשלחות בצמוד אחת לשניה:


void Server()

{

    Socket server = new Socket(AddressFamily.InterNetwork, SocketType.Stream, ProtocolType.Tcp);

    server.Bind(ServerEndPoint);

    server.Listen(1);

    Socket s = server.Accept();

 

    while (true)

    {

        // measure how long it takes to receive both messages

        Stopwatch stopwatch = Stopwatch.StartNew();

 

        s.Receive(new byte[8]);

        s.Receive(new byte[8]);

 

        // Output: around 200ms

        Console.WriteLine(stopwatch.ElapsedMilliseconds);

    }

}

 

void Client()

{

    Socket client = new Socket(AddressFamily.InterNetwork, SocketType.Stream, ProtocolType.Tcp);

    client.Bind(ClientEndPoint);

    client.Connect(ServerEndPoint);

 

    while (true)

    {

        client.Send(new byte[8]); // will be sent immediately

        client.Send(new byte[8]); // delayed for 200ms

 

        // wait for an imaginery response

        client.Receive(new byte[0]);

    }

}


בעקבות ההשלכות הלא רצויות שיכולות להיווצר כתוצאה מהעיכוב הזה, ה-RFC מציין שמימושים של TCP שממשים את Nagle's Algorithm חייבים לתמוך גם בדרך לבטל את השימוש בו, כך שהודעות אפליקטיביות שנשלחות לא יעוכבו ללא סיבה על ידי הפרוטוקול, וישלחו מיידית ליעד שלהן. היכולת הזאת בדרך כל נחשפת דרך השימוש בדגל TCP_NODELAY, ובדוט-נט עטפו את השימוש בו דרך הפרופרטי Socket.NoDelay.
Behind .locals init
כפי שכולנו מכירים, #C דורשת שכל המשתנים הלוקאלים יאותחלו לפני השימוש בהם.
עם זאת, למי שיצא להעזר ב-ildasm בשביל להציץ לתוך קוד ה-IL שהקומפיילר מייצר, בוודאי שם לב שמייד לאחר ההכרזה על שם הפונקציה, מתווספת שורה בסגנון הבא:

.method private hidebysig static void  Main(string[] args) cil managed
{
  .entrypoint
  // Code size       10 (0xa)
  .maxstack  1
  .locals init ([0] int32 x) <--- localsinit flag
  IL_0000:  ldc.i4.4
  IL_0001:  stloc.0
  IL_0002:  ldloc.0
  IL_0003:  call       void [mscorlib]System.Console::WriteLine(int32)
}
השורה הזאת מייצגת את הימצאות הדגל CorILMethod_InitLocals ב-Header של הפונקציה שאנחנו נמצאים בה. הדגל הזה למעשה מבטיח שה-CLR יאתחל את כל המשתנים הלוקאלים הנמצאים בפונקציה לערכי ברירת המחדל שלהם. כלומר, לא משנה איזה ערך דאגתם לתת למשתנה הלוקאלי שלכם (במקרה הזה המשתנה x מקבל את הערך 4), הסביבה תוודא שלפני שהקוד יתבצע, המשתנה x בהכרח יהיה מאותחל לערך חוקי (במקרה הזה, 0).

במימוש המיקרוסופטי של הסטנדרט, הדגל הזה תמיד קיים ב-Header (בהנחה שבאמת נוצרים משתנים לוקאלים בגוף הפונקציה). מה שיכול לגרום לנו מעט לתהות למה אם כך הקומפיילר ה-#C'י מכריח אותנו לאתחל את כל המשתנים הלוקאלים שלנו, אם הקוד שהוא מייצר בעצמו גם ככה מבטיח שכל המשתנים יאותחלו. האילוץ הזה יוצר רושם כמיותר אבל בפועל קיימות מספר סיבות שגורמות להמצאות הדגל הזה להיות כמעט הכרחית.

לפני שנבדוק מהי המשמעות מאחורי השימוש בדגל localsinit, נחזור לרגע לשאלת האתחול הכפול.
כאמור, כפי שניתן להבין מקוד ה-IL שנוצר לנו, נראה שבכל פעם שאנחנו יוצרים משתנה לוקאלי חדש, נוספת לנו תקורה מיותרת הנובעת מהאתחול הכפול של המשתנה (פעם אחת על ידי הסביבה, ועוד פעם על ידינו). התקורה הזאת היא אומנם מינורית לגמרי בהיבט של פגיעה בביצועים, אבל היא בכל זאת יכולה להעביר בנו איזשהו vibe לא טוב בגלל שאם אפשר פשוט להודות: הקוד הזה נראה רע.
אך למעשה, האתחול הכפול הזה אף פעם לא מתקיים. הסיבה לכך טמונה בצורה בה הדגל localsinit מבטיח את ערכי ברירת המחדל. כל מה שהוא עושה, זה לדאוג שה-JIT יחולל קוד שיאתחל את המשתנה לפני השימוש בו. במקרה שלנו, ה-JIT יצטרך לחולל הוראת mov שתאתחל את x ב-0.
ואכן, קוד האסמבלי שאנחנו מקבלים בזמן ריצה (ללא שימוש באופטימיזציות) מאשר זאת:

Normal JIT generated code
ConsoleApplication4.Program.Main(System.String[])
Begin 00e20070, size 30
00E20070 push        ebp
00E20071 mov         ebp,esp
00E20073 sub         esp,8
00E20076 mov         dword ptr [ebp-4],ecx
00E20079 cmp         dword ptr ds:[00942E14h],0
00E20080 je          00E20087
00E20082 call        7A0CA6C1 (JitHelp: CORINFO_HELP_DBG_IS_JUST_MY_CODE)

-------------------- Generated code due to the LocalsInit flag  ----------------
00E20087 xor         edx,edx                    // zero out the EDX register
00E20089 mov         dword ptr [ebp-8],edx   // assign the value of EDX to the location of 'X'

--------------------- Our own application's code ---------------------------------
00E2008C mov         dword ptr [ebp-8],4     // assign the value 4 to the location of 'X'

00E20093 mov         ecx,dword ptr [ebp-8]
00E20096 call        79793E74 (System.Console.WriteLine(Int32), mdToken: 060007c3)
00E2009B nop
00E2009C mov         esp,ebp
00E2009E pop         ebp
00E2009F ret

אם כן, בדוגמאת הקוד הזאת ניתן לראות באופן מובהק את ההשפעה שלדגל localsinit יש על חילול הקוד JIT, ועל הדרך אנחנו נחשפים לאותו אתחול כפול של המשתנה x.
אולם, צריך לזכור שהקוד הזה חולל ללא אופטימיזציות של ה-JIT. ברגע שנאפשר את השימוש באופטמיזציות, נראה שה-JIT מזהה את האתחול הראשוני בתור dead code משום שאין לו שום השפעה על התוכנית (והמשתנה הלוקאלי הוא בהכרח לא volatile). כתוצאה מכך, ה-JIT יהיה מספיק חכם כדי להסיר לגמרי את האתחול הראשוני, וחולל קוד אך ורק לאתחול האמיתי של התוכנית שלנו.
כך שלאחר שנאפשר את השימוש באופטימיזציות, הקוד המחולל נראה כך:

Normal JIT generated code
ConsoleApplication4.Program.Main(System.String[])
Begin 00c80070, size 19
00c80070 push    ebp
00c80071 mov     ebp,esp
00c80073 call    mscorlib_ni+0x22d2f0 (792ed2f0) (System.Console.get_Out(), mdToken: 06000772)
00c80078 mov     ecx,eax
00c8007a mov   edx,4  // assign 4 to the "virtual representation" of X
00c8007f mov     eax,dword ptr [ecx]
00c80081 call    dword ptr [eax+0BCh]

הדבר הראשון שניתן להבחין בו הוא שעכשיו אין לנו למעשה "משתנה x" בזכרון, אלא יש לנו במקומו register שמחזיק את ערכו. אבל חשוב מכך, ניתן לראות שכעת אין בקוד שום זכר לאותו אתחול כפול שראינו מקודם. כך בפועל אנחנו לא סובלים מתקורה כלשהיא עקב השימוש ב-localsinit.

עכשיו, אפשר לבדוק מהי למעשה המשמעות מאחורי השימוש ב-localsinit והאילוץ של הקומפיילר שמכריח את המפתח לאתחל את המשתנים הלוקאלים שלו.
הטיעון של מיקרוסופט בנוגע לשימוש במנגנון ה-Definite Assignment הוא שרוב הפעמים בהן מתכנתים לא מאתחלים משתנים לוקאלים נובעים מבאגים לוגים, ולא בגלל שהוא בונה על זה שהסביבה תאתחל את הערך ל-0. באחת התגובות של Eric Lippert בבלוג שלו, הוא מציין בעצמו:

"The reason we require definite assignment is because failure to definitely assign a local is probably a bug. We do not want to detect and then silently ignore your bug! We tell you so that you can fix it."
 
את החשיבות של הדגל localsinit אפשר לסכם במילה אחת: Verfication.
ורפיקציה היא התהליך שבו ה-CLR מוודא שכל קוד ה-CIL שקיים בתוכנית הוא "בטוח". זה כולל וידוא שהפונקציות שאנחנו מפעילים מקבלות בדיוק את מספר הפרמטרים שהן צריכות לקבל, שהפרמטרים שהן מקבלות הם מהטיפוסים הנכונים, שכל המשתנים הלוקאלים מאותחלים לפני השימוש ועוד...
במידה וה-CLR מגלה קטע קוד שנכשל בתהליך הורפיקציה, תזרק שגיאת VerficationException.
צריך לשים לב שלא כל קוד CIL חייב בהכרח להיות Verifiable, כפי שמצויין ב-Partition III של הסטנדרט:

"It is perfectly acceptable to generate correct CIL code that is not verifiable, but which is known to be memory safe by the compiler writer. Thus, correct CIL  might not be verifiable, even though the producing compiler might know that it is memory safe."

עם זאת, ברגע שאנחנו כותבים קוד שהוא לא Verifiable, אנחנו מוכרחים לשנות את ההרשאות הניתנות לו בעזרת SecurityPermissionAttribute, ולומר ל-CLR במפורש לא לבצע בדיקות ורפיקציה על הקוד בעזרת הפרופרטי SkipVerfication (ה-CLR לא יבצע בדיקת Definite Assignment על הקוד). אחת הפעמים שבאמת משתמשים ביכולת הזאת, היא כאשר רוצים לכתוב קוד unsafe בתוכנית. במקרה כזה, אנחנו צריכים לסמן בהגדרות הפרוייקט באופן מפורש שאנחנו רוצים לתמוך ב-unsafe code, מלבד שכעת הקומפיילר באמת יאפשר לנו לקמפל את הקוד, הוא גם יוסיף לאסמבלי המחולל את UnverifiableCodeAttribute, שידאג לספר ל-CLR שכל המודול הזה הוא לא Verifiable.

תהליך הורפיקציה דורש שכל משתנה לוקאלי יהיה מאותחל. ליתר דיוק, הוא דורש שבמידה ולא היתה דרישה לדלג על הורפיקציה, אזי שהדגל localsinit חייב להמצא. לכן ניתן ברפרנס לפקודות ה-CIL השונות ניתן להתקל בהערות מהסוג הזה:

"Local variables are initialized to 0 before entering the method only if the localsinit on the method is true (see Partition I) ... System.VerificationException is thrown if the the localsinit bit for this method has not been set, and the assembly containing this method has not been granted
System.Security.Permissions.SecurityPermission.SkipVerification (and the CIL does not perform automatic definite-assignment analysis) "


בשלב מאוחר יותר המסמך גם כן מתייחס לאותה תקורה המתווספת כאשר מבצעים ניתוח של Definite Assignment על הקוד:

"Performance measurements on C++ implementations (which do not require definite-assignment analysis) indicate that adding this requirement has almost no impact, even in highly optimized code. Furthermore, customers incorrectly attribute bugs to the compiler when this zeroing is not performed, since such code often fails when small, unrelated changes are made to the program."