工作原因要對一個(gè) newreno 實(shí)現(xiàn)增加 sack 支持。嘗試寫了 3 天 C++，同時(shí)一遍又一遍梳理 sack 標(biāo)準(zhǔn)演進(jìn)。這些東西我早就了解，但涉及落地寫實(shí)現(xiàn)，就得不斷摳細(xì)節(jié)，試圖寫一個(gè)完備的實(shí)現(xiàn)。

這事有更簡單的方法。根本沒必要完全實(shí)現(xiàn) RFC，目標(biāo)是高吞吐，而不是實(shí)現(xiàn)標(biāo)準(zhǔn) TCP，因此只要保證最寬容的可用性，剩下的交給現(xiàn)實(shí)。我們做 cc 時(shí)，為提高性能，何嘗不是這里 cwnd += 10，那邊 cwnd += whatever(sk)，異曲同工。

前面兩周寫了一些關(guān)于 TCP 演進(jìn)的文字，無論怎樣，這是個(gè)好機(jī)會(huì)以一個(gè)實(shí)例來展示演進(jìn)過程中的方法論。捕捉其中關(guān)于 sack 的兩個(gè)細(xì)節(jié)，降窗和重傳，再寫一些文字。

TCP 丟包后進(jìn)入 fast retransmit/recovery 后涉及如何降窗和如何重傳兩件事，TCP 經(jīng)過 40 多年的演化，關(guān)于這兩件事鑄建了 4 個(gè)里程碑。

最初的 TCP 只有 rto，沒有 fast retransmit，此即 TCP tahoe，只要有丟包，即將 cwnd = 1，重新開始慢啟動(dòng)。第 1 個(gè)里程碑是 TCP reno 和 TCP newreno，二者一脈相承。

reno 引入了 fast retransmit，但有很多問題，newreno 解決了這些問題。這部分參見 Wiki。seastar 只實(shí)現(xiàn)了 RFC6582 定義的 newreno，非常原始，但基本上這就是一個(gè)最小能用的 TCP 實(shí)現(xiàn)。

從第 2 個(gè)里程碑開始，TCP 開始起飛。我的工作也就是盡量追著這個(gè)尾跡跟著飛，在必要時(shí)加入一些自己的 trick，或覺得標(biāo)準(zhǔn)實(shí)現(xiàn)太麻煩時(shí)偷一下懶裁剪掉些東西。

引入 fast retransmit 時(shí) TCP 還不支持 sack，收到 3 個(gè) dupack 即進(jìn)入 fast retransmit/fast recovery，但只留下一個(gè)未被 ack 的 hole，hole 后面的情況什么也看不到，沒有任何啟發(fā)式手段讓 sender 猜測哪些 seg 丟了。

降窗如 范雅各布森 所述，直接將 cwnd = ssthresh = cwnd / 2。RFC5681 不允許超過一半的 seg 在途(這似乎是在迎合或確認(rèn) ssthresh = cwnd/2 這件事，詳見：雅各布森管道)：

until all lost segments in the window of data in question are repaired, the number of segments transmitted in each RTT MUST be no more than half the number of outstanding segments when the loss was detected.

這顯然降低了帶寬利用率，但這時(shí)沒有任何信息指示如何做得更好(每發(fā)送一個(gè) seg 只能至多帶回 1 個(gè) ack)，解決這個(gè)問題的條件尚未具備。

關(guān)于重傳，除了一個(gè) hole 沒有任何輔助信息，只能從 una 開始每次重傳 1 個(gè)往前挪 nua，沒有任何別的辦法。如下圖所示，整個(gè)圖景相當(dāng)于一個(gè) seq space 構(gòu)成的一維世界，一 hole 以障目：

隨著 sack 被引入，降窗和重傳邏輯均起了大變化。我們關(guān)注的是這個(gè)變化是如何如絲般順滑而一氣呵成的，以便這個(gè)方法論能指示 TCP(or any others) 未來的演化方向。

第 3 個(gè)里程碑來自 sack 被引入后。詳見 RFC6675。 sack 反饋了更加豐富的信息，sender 有了繞到 hole 后面查看究竟的途徑，這相當(dāng)于引入了額外的維度，將 seq space 直立了起來，仰起頭就能看到 seq space 的細(xì)節(jié)：

TCP 將 seq space 抽象成一個(gè) scoreboard，該 scoreboard 上對 seq space 的每一個(gè) seg 區(qū)分對待，可 mark sacked，mark lost，mark reordering，針對 lost seg 進(jìn)行重傳并 mark retrans，inflight 從而可精確獲取：

inflight = snd_nxt - snd_una + snd_retrans - snd_lost - snd_sacked

基于守恒律，于是 cwnd = inflight 更加精確。

二維世界豐富的多的信息指示 sender 做出更好的決策，不再每次 retransmit 一個(gè) seg，TCP 重傳算法第一次統(tǒng)一處理重傳 seg 以及新 seg，它們統(tǒng)一受 cwnd 限制：cwnd - inflight > 0。

重傳邏輯將 seg 分三個(gè)優(yōu)先級，mark lost 的 seg 被優(yōu)先傳輸，因?yàn)樗鼈冏钊菀籽a(bǔ) hole 而推進(jìn) una，新 seg 第二優(yōu)先，它們可能帶回新的 sack，推進(jìn) mark lost，背后的考慮是盡量延后 mark lost，而剩余的最后重傳：

下面再看降窗邏輯。

重傳 seg 和新 seg 在 fast retransmit/recovery 狀態(tài)被統(tǒng)一安排，一個(gè) seg 帶回的 sack 可導(dǎo)致大量 mark lost，參考前面 inflight 公式，大量 seg 由于 mark lost 被清出 pipe，inflight 急劇減少而騰出大量 pipe 空間。cwnd 一定時(shí)，后果便是 burst(可 burst 一個(gè) cwnd = ssthresh 的數(shù)據(jù))。而 burst 會(huì)加劇網(wǎng)絡(luò)擁塞而丟包，形成正反饋。

TCP 第一次以 ack 攜帶信息(sack)而非 ack 本身來計(jì)數(shù)，引入了 scoreboard 細(xì)化了 seq space，但處理降窗的方式卻沒有同步跟進(jìn)處理這個(gè) burst 問題。

有兩個(gè)更平滑降窗的方案，第一個(gè)是 Linux TCP 的 rate-halving 算法。rate-halving 思路很簡單，不再一下子將 cwnd 折半，而是每收到 2 個(gè) ack 將 cwnd 減 1，這樣收到一個(gè) cwnd 的 ack 后，cwnd 即原來的一半了。

但彼時(shí) cc 已模塊化，丟包降窗的目標(biāo)可自定義，比如 cubic 將 cwnd 降為 0.7*cwnd，而 rate-halving 寫死了比例 0.5，且未考慮 sack 計(jì)數(shù)而精度不夠(sack 大大提高了判斷精度，rate-halving 卻沒有利用任何 inflight 信息)。 后來 Google 提出了 prr 算法，將 cwnd 精確平滑收斂到 ssthresh = (1 - beta)*cwnd。

思路和 rate-halving 類似，只是 prr 基于 scoreboard 精確計(jì)算 fast retransmit/recovery 期間被 ack/sack 的數(shù)據(jù) prr_delivered 和實(shí)際發(fā)送的數(shù)據(jù) prr_out 以獲得收益。按照正常的 seg 守恒律：

cnt = prr_delivered - prr_out

結(jié)果應(yīng)為 0，意思是 prr_delivered 被確認(rèn)之后才能兌換等量的 prr_out 而發(fā)出，按比例縮放這個(gè)守恒律即可：

cnt = (1 - beta)*prr_delivered - prr_out

以 beta = 0.3 為例，意思是 0.7 個(gè)單位的 prr_delivered 被確認(rèn)后兌換 一個(gè)單位的 prr_out，為了滿足守恒律使結(jié)果為 0，prr_out 也要進(jìn)行 0.7 縮放，因此必須從 cwnd 中扣除這個(gè)差異：

cwnd = inflight - |cnt|

由此在一個(gè) rtt 內(nèi)，sender 緩慢地，平滑地，等比例地將 cwnd 降到 (1-beta)*cwnd。

…

降窗邏輯看起來很 perfect。

讓我們回看引入 sack 后的第 3 個(gè)里程碑的重傳邏輯，看它有什么問題不能解決，并且該問題還必須被解決。

隨著帶寬資源的增加，傳輸協(xié)議對帶寬利用率有所期待，而不再僅僅滿足于保證可用性的 AIMD 算法。需實(shí)時(shí)測量的 rate-based cc 在這個(gè)背景下被設(shè)計(jì)。

與 cwnd-based cc(cwnd 配額用盡即不可再發(fā)送) 不同，實(shí)時(shí)測量考慮 delivery rate 反饋而非僅僅 ack 時(shí)鐘，需要 sender 有持續(xù)數(shù)據(jù)流可發(fā)送，即使 rwnd 憋死(矢量滑動(dòng) rwnd 導(dǎo)致，我對此有單邊解法)，在收不到重傳 seg 的 sack 后，要再次重傳該 seg(這在某種意義上確實(shí)可以取消 rto 了，但這是后話)。

RFC6675 標(biāo)準(zhǔn) sack 重傳機(jī)制涉及兩個(gè)細(xì)節(jié)，一個(gè)是 reordering 更新，一個(gè)是依賴前者的 mark lost，先看 reordering 更新：

reordering 根據(jù) sack 的布局和批次不斷被更新，關(guān)于 reordering 的細(xì)節(jié)，詳見早期的一篇分析：TCP 的亂序&丟包判斷。

基于此，再看 mark lost：

這兩個(gè)機(jī)制揉在一起非常復(fù)雜。

RFC6675 的算法顯然無法滿足多次重傳相同 seg，因?yàn)?sender 的 scoreboard 沒有信息區(qū)分多次 mark lost 被重傳的 seg，這就無法在 mark lost 和 mark reordering 之間做判斷：

每個(gè) seg 只能 mark lost 一次，如果重傳丟了，只能 rto。

第 4 個(gè)里程碑就來了。

在 sack 引入的額外維度后，一維 seq space 展成了二維，sender 可以從額外的維度繞過 hole 看到信息量更大的 scoreboard。尋著同樣的思路，再加一個(gè)維度，為傳輸加上時(shí)間軸，這就是 rack：

兩根坐標(biāo)軸就搞定了所有事情，不再需要額外的兩個(gè)過程，雖然也依然會(huì)有由于 reordering 對 rack window 所做的調(diào)整，但相比更新 reordering 值本身的邏輯就太簡單和直觀了。

看一下清爽的 rack 全景：

sender 維護(hù)一個(gè)統(tǒng)一安排 mark lost 重傳 seg 和新 seg 的按發(fā)送時(shí)間 fifo 隊(duì)列。每一個(gè) hole 只要在一定時(shí)間(比它后發(fā)送的都被 ack/sack，而它在此一定時(shí)間后仍是 hole)內(nèi)沒被 ack/sack 可以重新被 mark lost，與其是否被重傳過以及重傳過幾次無關(guān)。每次傳輸都會(huì)將時(shí)間戳打入，以區(qū)別傳輸輪次。

就這樣，rack 引入一個(gè)時(shí)間序解決了 reordering 和 mark lost 歧義的問題。

rack 靠時(shí)間驅(qū)動(dòng)，即時(shí)間序，而此前的方法則是在 seq space 上根據(jù)字節(jié)序關(guān)系靠啟發(fā)(且看 Linux TCP 的 update scoreboard)驅(qū)動(dòng)，再往前，則連啟發(fā)都沒得啟發(fā)了，因?yàn)楦緵]信息。過程的發(fā)展非常柔滑，值得再次總結(jié)。

一維世界，一個(gè) hole 就堵住了，sack 相當(dāng)于二維平面，sender 可繞到 hole 后看情況，順著往后，用時(shí)間編碼發(fā)送順序，就是 rack，sender 在一個(gè)三維看板看到的信息更詳細(xì)，從而可做出更精確合理的判斷。

接下來的事情尚未發(fā)生(或者發(fā)生了一點(diǎn)點(diǎn))，但按照上面的推理邏輯，它應(yīng)該會(huì)發(fā)送。

rack 就像一架引擎，只要 ack 時(shí)鐘不斷，在丟包時(shí)亦始終有 seg 被發(fā)送，這些 seg 將帶回驅(qū)動(dòng)引擎的進(jìn)一步的 ack 流，該策略非常適合高速網(wǎng)絡(luò)，發(fā)送引擎不再區(qū)分 seg 類型，與 scoreboard 解耦，rack 將代替任何基于重復(fù) ack/sack 的啟發(fā)算法 mark lost，發(fā)送引擎維持高速運(yùn)轉(zhuǎn)，源源不斷提供數(shù)據(jù)用于實(shí)時(shí)測量。

BBR 即使用 rack 作為自己的丟包探測驅(qū)動(dòng)。

隨著帶寬資源進(jìn)一步豐富，類似 BBR 的算法未競?cè)?。由?TCP 沒有打包直接傳輸 seq space 字節(jié)流，導(dǎo)致無邊界確認(rèn)處理非常復(fù)雜，由此帶來了 undo 歧義和 ack 歧義問題，不必要重傳，不準(zhǔn)確的 rtt 測量和 delivery rate/cwnd 計(jì)算都是其影響。這些復(fù)雜且不精確的處理是高帶寬利用率的絆腳石。

問題根源在于，正向傳輸?shù)?seg 是 seq space 的矢量字節(jié)流，而 ack/sack 指導(dǎo) cwnd 更新的只有標(biāo)量 account，丟失了 seg 傳輸順序。換句話說，sender 發(fā)送的 seg 是按序的，而 sender 接收到的 ack/sack 卻沒有信息可還原對應(yīng) seg 的順序。

按以往慣例，既然 rack 已將時(shí)間序編碼到了 sender 本地，只需將該時(shí)間序同時(shí)編碼到 seg 本身，這樣 seg 將引導(dǎo) ack 反饋更豐富的 receiver 端信息，該信息與 sender 的本地傳輸時(shí)間序進(jìn)行比對，就什么都有了。過年期間，我曾想了一個(gè)方法，詳見：重新設(shè)計(jì) TCP。下面是對該文字的一點(diǎn)前置分析。

如果 seg 攜帶 1 bit 額外信息，就能區(qū)分一次重傳和原始 seg，攜帶 2 bit 能區(qū)分 3 次重傳和原始 seg，以此類推，攜帶 32 bit 能區(qū)分 4G 次傳輸(1 次原始 seg 和 4G-1 次重傳)，為將每次傳輸識別為一個(gè)不允許切割的整體，需將 seq space 的字節(jié)流按序打包進(jìn)固定長度的 packet，以 packet 為單位傳輸并針對 packet 確認(rèn)，為每一個(gè) packet 打標(biāo)遞增的 packet id 作為序列號。

這想法是個(gè)自然而然的過程。邏輯反而更簡單明，加入一個(gè) packet id 便清除了啟發(fā)式判斷。

可 TCP 沒地方編碼 packet id 了，況且 TCP 的標(biāo)準(zhǔn)處理流程無法要求不切割，打包過程很難合并入 TCP。但 QUIC 接力了。雖然 QUIC 未必是 TCP 后繼，但它在 sack，rack，重傳等方面的處理方式，正是針對 TCP 的 bugfix，整個(gè)過程一脈相承，可理解。

后面的路怎么走我不知道，也不預(yù)測，但俯拾皆是的肯定依然一地雞毛，而且如果它確實(shí)發(fā)生了，將它與前面的事情連起來，必將在同一條線上。

浙江溫州皮鞋濕，下雨進(jìn)水不會(huì)胖。