2010年11月7日 星期日

Nagle's Algorithm 和 Delayed ACK 的問題

測 httplib2 POST 的時候發現 httplib2 實作造成的問題 (Issue 91), 就順著討論往下查原因, 還滿有趣的。

The trouble with the Nagle algorithm 簡單的解釋 Nagle's Algorithm 和 Delayed ACK 的目的和作法, 這篇文末兩段 "Delayed ACK" 和 "Nagle's Algorithm" 有更詳細的解釋。看懂後再回頭看 httplib2 Issue 91 的逐步說明, 終於明白為啥 Nagle's Algorithm 的作者說 write-write-read 會造成問題, 而 httplib2 剛好在 POST 的情況下就是 write-write-read (送 head, 送 body, 讀 response)。

在這裡整理一下讀到的重點:

TCP 的 ACK

用 TCP 傳資料時, 收到任何封包後都會回傳一個 ACK, 表示有收到該封包 (會有個流水號對應是收到那個封包)。

Delayed ACK

若收到資料的一端會馬上會回傳資料, 那就不用急著回傳 ACK, 可以等要回傳資料時, 再一起送回 ACK, 藉此少送一個封包。像 ssh 連線時, 每收到 client 端送來的按鍵, 都會將螢幕上的變化送回去。

但 TCP 不會知道 application layer 會不會立即回傳資料, 所以它只能先猜「會立即回傳」而先不回傳 ACK, 等個一陣子 (500ms?) 都沒有回傳資料的話, 再回傳 ACK。除此之外, 還有個例外規則, 一但收到第二個封包, 立即回傳這兩個封包的 ACK。

Nagle's Algorithm

收到送資料的請求時, 不會立即送出資料, 而是等下列兩個條件之一發生時, 才送出資料:
  • 送出的資料可以塞滿一個封包 (避免送出太多小封包, 浪費頻寬)。
  • 收到 ACK (表示之前的資料已成功送達, 此時不送也是讓頻寬空著)。

兩者的衝突

假設要送出的封包都不大。Nagle's Algorithm 會等到收到 ACK 後, 才會送出下一個封包。
  • 若操作是 write-read-write-read, 不會有問題, 因為對方的 Delayed ACK 猜中了, ACK 成功地搭回傳資料的便車送回來。
  • 但若是 write-write-read, 送完第一個封包後, 不會送出第二個封包, 因為沒有滿足 Nagle's Algorithm 的兩個條件。對方等個一段時間才會送出 ACK, 於是造成不必要的時間負擔。
如 Issue 91 第二則留言說的, 理想的解法是將 head 和 body 合在一個封包送出。關掉 client 端的 Nagle's Algorithm 可以避開這問題, 但卻不會避免送出一堆小封包。若 client 端不小心寫成送出一堆小封包, 會降低效率。

備註

如 Issue 91 作者所言, httplib2 只有在重用同一 connection 時才會有 write-write-read 卡住的問題。不知為何每次都用新的 connection 的話, 就沒有這個問題。得實際追踪送出封包和回 ACK 的時機, 才能明白為何用新的 connection 沒這問題。也許 Delayed ACK 或 Nagle's Algorithm 的運作方式不如上面所言那般單純。

沒有留言:

張貼留言

在 Fedora 下裝 id-utils

Fedora 似乎因為執行檔撞名,而沒有提供 id-utils 的套件 ,但這是使用 gj 的必要套件,只好自己編。從官網抓好 tarball ,解開來編譯 (./configure && make)就是了。 但編譯後會遇到錯誤: ./stdio.h:10...