用隨機圖蓋資料中心網路——Amazon 的 RNG 怎麼把 fat-tree 換下來

RNG（Resilient Network Graphs）是 Amazon 揭露的資料中心網路架構，把階層式的 fat-tree／Clos 換成隨機圖（random graph／expander graph）。它要解的問題很具體——當你的網路要塞進幾萬顆 router、每年都得擴一批機櫃、隨時有 1% 的元件壞著，fat-tree 那種「層數固定、路徑可枚舉」的優雅就變成負債：要嘛 spine 變成瓶頸，要嘛擴容得整層重畫，要嘛一顆 spine switch 死掉就削掉一整片 bisection。RNG 由 Bernardi、Mahajan、Comandur 帶的團隊做出來，核心不是發明新理論，而是把一個 1970 年代就存在、2012 年 Jellyfish 點破卻卡死的點子——「隨機接線的圖在數學上逼近最佳 expander」——真的變成可路由、可佈線、可運維的生產系統。三個老問題各有一個對應的子系統：路由是 Spraypoint，佈線是 ShuffleBox，運維是「先用數學模型驗證再實體部署」。

底下四個小節對應這套架構的四個結構性問題。前三節各拆一個子系統——為什麼 expander 比 fat-tree 好（理論）、Spraypoint 怎麼在不爆 router memory 的前提下灑流量（路由）、ShuffleBox 怎麼把隨機性做成可佈線的被動硬體（佈線）。第四節回到 RNG 最反直覺的主張：把保證寫成機率，比把保證寫成絕對值更誠實。先從一個動態畫面開始——同一批封包，灑在隨機 expander 上跟集中在 fat-tree spine 上，掉 node 時兩者的退化方式完全不同。下方 canvas 可以邊跑邊敲掉節點，看「等比例退化」跟「斷崖式退化」的差別到底長什麼樣。

random expander fat-tree ⏸ pause ↺ reset delivered 0 · dropped 0 · capacity 100%

expander graph：為什麼一張隨機接線的圖能贏過 fat-tree

先把 fat-tree 的優點講清楚，才知道 RNG 在賭什麼。Clos／fat-tree 的迷人之處是 非阻塞（non-blocking）與 可預測：只要每一層的上行頻寬等於下行頻寬，理論上任意 src-sink 配對都能找到不衝突的路徑，而且因為層數固定，路徑長度是常數、轉發表是可枚舉的。代價藏在三個地方。第一，要做到非阻塞，spine 層必須堆足夠多的 router，router 數量隨規模呈超線性成長——每加一排 leaf，spine 就得跟著膨脹。第二，bisection bandwidth（把網路從中間切一刀、跨切面的總頻寬）全壓在 spine 上，spine 任何一顆 switch 掛掉，跨切面容量就掉一整塊。第三，擴容是離散的：fat-tree 的 radix（每顆 switch 的 port 數）決定了它能長到多大，要突破就得加一層、整個重畫。

expander graph 從另一個方向解這三件事。一張圖是好的 expander，意思是「任何一個節點子集都跟外界有很多條邊相連」——形式化講，任意大小不超過一半的頂點集合 S，從 S 連出去的邊數至少正比於 |S|，沒有任何子集能被少數幾條邊孤立起來。這個性質直接翻譯成網路的三個好處：path diversity（任兩點間有大量近乎等長的不相交路徑，流量天然分散）、高 bisection bandwidth（要把圖切兩半就得切斷大量邊，所以跨切面頻寬高且不集中在某一層）、漸進可擴張（隨機圖沒有「層」的概念，加機櫃就是再接一批隨機邊，不必重畫拓樸）。理論根源很老：1970 年代 expander graph 作為「連通性極強的稀疏圖」被提出，Valiant 在 1976 年就用它討論過 routing。真正讓它對工程有意義的是 Friedman 在 1991 年的證明——一張隨機接線的網路，以極高機率，幾乎跟最佳的顯式 expander 構造一樣好。也就是說，你不需要費力去設計一個數學上最優的拓樸，你只要「亂接」，接出來的圖就近乎最優。

這就是 RNG 的理論賭注：放棄可枚舉的 deterministic 拓樸，換取隨機圖的 path diversity 與 bisection。但「亂接近乎最優」是個漸進命題——它說的是 with high probability、是 N 夠大時。實務上的問題從來不是「隨機圖好不好」，2012 年的 Jellyfish 論文已經把這點論證得很清楚：同樣的 port 預算，隨機圖能塞進比 fat-tree 多約 25% 的 server，而且擴容無痛。Jellyfish 卡死的是另外三件事——路由在隨機圖上很難（沒有層次就沒有現成的最短路轉發）、佈線更難（真正隨機的接線在機房裡無法施工）、運維變得不可預測（沒有規則拓樸就難以推理故障）。RNG 的貢獻不在理論，在於把這三道工程牆一道一道拆掉。下面這張對照表把 fat-tree、Jellyfish、RNG 三者在每個維度上並排，點欄位標題可以重排。

click column header to sort · 4 columns × 5 rows

從 expander 理論到 RNG 的譜系——年份、貢獻者、解掉了什麼、留下什麼沒解。點欄位標題排序。

年代	里程碑	帶來的	留下的缺口
1970s	expander graph 理論（Valiant 1976 用於 routing）	「稀疏卻連通性極強」的圖類，定義出 bisection／expansion 指標	純理論，沒人把它接成實體網路
1991	Friedman 證明	隨機接線的圖以極高機率逼近最佳 expander——「亂接」就近乎最優	是漸進命題，對「怎麼路由／佈線／運維」無話可說
2012	Jellyfish（隨機圖資料中心拓樸）	同 port 預算多塞 ~25% server、擴容無痛、bisection 高	路由難、佈線無法施工、運維不可預測——三牆未破
2026	RNG · Spraypoint（Bernardi, Mahajan, Comandur）	沿圖 expansion 灑流量，不爆 router forwarding state	保證是 stochastic 而非 deterministic（被論證為更誠實）
2026	RNG · ShuffleBox	被動光學裝置 + 隨機 box 間佈線 → quasi-random 拓樸，可施工	quasi-random 而非真隨機（行為上等價）

有一個容易混淆的點值得釐清：RNG 不是「無腦亂接」。Friedman 的定理保證的是「隨機接線在分布意義上近乎最優」，但任何一次具體的抽樣都可能抽到比較差的圖——可能某個區域恰好連得稀。RNG 的運維子系統正是處理這件事：在實體部署之前，先用數學模型對「這一次抽出來的具體拓樸」算出 expansion、bisection、最差情況路徑長度等指標，不合格就重抽或局部修補。也就是說隨機性被框在一個「先驗證、後佈線」的閘門後面——你享受隨機圖的統計優勢，但不接受任何一張碰巧很爛的圖。這跟 fat-tree「拓樸寫死在規格裡、不必驗證」是完全不同的工作流，卻換來了 fat-tree 給不起的彈性。

Spraypoint：在不爆 router memory 的前提下沿著圖灑流量

隨機圖最直接的路由難題是：fat-tree 因為有層次，每顆 switch 只要知道「往上送還是往下送」就夠了，forwarding state 小且規則；隨機圖沒有層，最短路徑路由意味著每顆 router 都得記住「到每個目的地的下一跳」，forwarding table 隨網路規模爆炸——這正是 Jellyfish 卡住的第一道牆。一個能裝幾萬顆 router 的網路，如果每顆都要存全域最短路表，router 的 TCAM／SRAM 根本放不下。

Spraypoint 的解法不是「算出最短路再塞進表裡」，而是利用圖的 expansion 性質直接灑。原文的說法是：Spraypoint 是「a forwarding scheme that exploits the expansion properties of the graph to distribute traffic without overwhelming router memory with forwarding state」。直覺是這樣——在一個好的 expander 上，你不需要知道最短路，因為「往隨機方向多跳幾步」就能以極高機率快速逼近任何目的地（這是 expander 的混合性質：random walk 在 expander 上收斂得非常快）。把流量沿著圖的多條路徑灑開（spray），不但天然做了 load balancing，還把每顆 router 需要維護的 state 從「全域目的地表」壓成「局部規則」。封包不再沿單一最短路前進，而是被分散到大量近乎等長的路徑上——這正是 path diversity 從理論性質變成可用頻寬的地方。

// fat-tree：每顆 switch 需要全域可達的 forwarding state
forward(pkt):
    nexthop = forwarding_table[pkt.dst]   // 表大小 ∝ 目的地數量
    send(pkt, nexthop)

// Spraypoint：利用 expansion，沿多路徑灑、不存全域最短路
forward(pkt):
    if at_destination(pkt): deliver(pkt); return
    // 在一個好的 expander 上，往「擴張方向」的隨機鄰居推進，
    // 期望跳數 ~ O(log N)，state 只需局部資訊
    cand = expansion_neighbors(local_topology)   // 局部、規則
    nexthop = spray_pick(cand, pkt.flow_hash)    // 分散到多路徑
    send(pkt, nexthop)

// 關鍵差異：forwarding state 不再 ∝ N，
// 而是 ∝ 本地 degree——這是 Jellyfish 卡死、RNG 解開的那道牆

這裡有個工程上的張力要說清楚：灑流量會打亂封包順序，也可能讓某些封包繞遠路。Spraypoint 之所以可行，前提是底層拓樸真的是個好 expander——expansion 夠好，random walk 的混合時間（mixing time）就短，平均跳數壓在 O(log N) 而不是發散，繞遠的尾巴才不會太長。這把「拓樸品質」跟「路由可行性」綁在一起：拓樸不夠 expander，Spraypoint 的灑就會退化成漫無目的的亂走。所以前一節講的「先驗證拓樸的 expansion 再佈線」不只是運維潔癖，它是 Spraypoint 能不能成立的前置條件。把這三件事連起來看——ShuffleBox 保證接出來的是 quasi-random 的好 expander、運維模型保證這次抽樣確實夠好、Spraypoint 才能放心地沿 expansion 灑而不必背全域路表。

結果是 fat-tree 給不起的數字。原文列的對照是：相較 fat-tree，RNG 用少 69% 的 router、達到高 33% 的吞吐量、低 40% 的網路功耗、低 27% 的營運成本。少 69% router 而吞吐量還高 33%，這個組合不是調參調出來的，是拓樸層面的：fat-tree 的 router 預算大量花在「為了非阻塞而堆的 spine」，expander 把那筆預算省下來，同樣的 port 拿去拉 path diversity。下面這張圖把四個指標並排——注意 router 數量與吞吐量是反向的（少而快），這才是重點。

ShuffleBox：把隨機性做成可佈線的被動光學硬體

Jellyfish 卡死的第二道牆是佈線。一張真正隨機的圖，意味著機房裡有成千上萬條光纖以「沒有規則」的方式從任一機櫃連到任一機櫃——這在施工上是惡夢：無法畫線材表、無法批量採購固定長度的線、無法讓技師照圖施工、壞了無法定位。「隨機」在數學上是優點，在物理佈線上是不可施工。

ShuffleBox 是 RNG 化解這道牆的關鍵：它是一個被動光學裝置，原文描述為「a passive optical device whose internal wiring combined with randomized ShuffleBox-to-ShuffleBox cabling yields 'quasi-random' graphs that behave like truly random graphs」。拆開看是兩層隨機的疊加。第一層是 ShuffleBox 內部的固定接線——盒子裡的光纖按某個固定但「打散」的 permutation 接好，這是出廠就定死的、可大量複製的硬體，不需要現場施工。第二層是 ShuffleBox 之間的接線本身帶一點隨機。兩層疊起來，產生的不是真隨機圖，而是 quasi-random（準隨機）圖——但它在 expansion、bisection、path diversity 這些對網路真正重要的指標上，行為跟真隨機圖一樣好。這正好踩在 Friedman 定理的精神上：你不需要真隨機，你只需要一個在統計性質上跟隨機圖無法區分的圖。

「被動」這個詞是 ShuffleBox 的工程核心，值得多說一句。被動光學裝置沒有電子元件、不耗電、不發熱、幾乎不會壞——隨機性被固化進一塊無源的玻璃與光纖裡，而不是靠一台會故障的交換機去動態產生。這把「隨機拓樸」的成本從「每次都要現場亂接」降到「採購一批標準化的盒子、照規則插上」。技師看到的是規則的、可重複的佈線（盒子 A 的 port 連盒子 B 的 port），而 expander 的隨機性藏在盒子內部與盒間 permutation 裡——施工複雜度跟 fat-tree 同級，拓樸性質卻是隨機圖等級。下面這張 SVG 把這兩層隨機畫出來：左邊是技師眼中規則的 box-to-box 佈線，右邊是它在邏輯上等價的 quasi-random 圖。

把 ShuffleBox 跟運維子系統連起來看，就能理解 RNG 為什麼能「先驗證再佈線」。因為拓樸是由「ShuffleBox 內部 permutation」加「盒間佈線方案」這兩個可枚舉的參數決定的，工程團隊可以在還沒插任何一條線之前，先把這組參數餵進數學模型、算出整張圖的 expansion 與 bisection、確認它是個夠好的 expander，然後才生成「port-by-port 的安裝指令」交給技師。原文特別點出 RNG「designed to work with the exact same routers and optics already deployed in fat-tree data centers」——它不需要新硬體，省下的成本來自拓樸本身，而不是換一批昂貴的設備。這也是為什麼 27% 的 opex 降幅是可信的：少 69% router、低 40% 功耗，本來就是 opex 的兩個大頭，再加上「用既有設備、施工複雜度不變」，營運面沒有引入新的長期負擔。

stochastic 比假裝 deterministic 更誠實

RNG 最容易被攻擊的點，是它的效能保證是機率性的而非絕對的。fat-tree 可以拍胸脯說「只要拓樸照規格接好、沒有故障，任意配對都非阻塞」；RNG 只能說「以極高機率，這張圖的 expansion 不低於某個值」。直覺上前者聽起來更可靠。RNG 團隊的反駁很鋒利：原文指出，「Fat-tree guarantees are also effectively stochastic once you account for real-world failures, which are frequent at scale. RNG simply makes the stochastic nature explicit.」——fat-tree 的保證一旦把「現實中無時無刻都有元件在壞」算進去，本來就是機率性的；RNG 只是把這件事攤開來講。

這個論點的力道，在故障退化的形狀上看得最清楚。fat-tree 的「非阻塞」是一個建立在「沒有故障」假設上的保證——而在幾萬顆 router 的規模下，「沒有故障」從來不成立，always-on 的真相是「隨時有 1% 的元件壞著」。一旦 spine switch 壞了，fat-tree 的退化是斷崖式的：跨切面的 bisection 集中在 spine，掉一顆 spine 就削掉一整塊容量，掉幾顆就可能讓某些 src-sink 配對徹底斷線。RNG 的退化是等比例的——原文的數字是「losing 1% of routers results in a roughly 1% capacity loss」，掉 1% 的 router 大約只掉 1% 的容量。原因正是 expander 的定義：沒有任何子集能被少數邊孤立，也就沒有「打掉它就斷一片」的單點。容量像氣球漏氣一樣平滑地下降，而不是像玻璃一樣某一點裂開就碎。

所以「誠實」不是修辭。一個寫死 deterministic 保證的系統，把「故障」當成規格之外的例外處理——而例外恰恰是規模下的常態，於是真實行為（斷崖）跟承諾（非阻塞）之間出現一道你只能在事故時才發現的鴻溝。一個明說自己 stochastic 的系統，把故障放進模型的核心：它不承諾「永不阻塞」，它承諾「容量隨損壞等比例平滑退化」——而這個承諾在故障常態化的世界裡，是真的能兌現的。把這件事翻成維運語言：fat-tree 給你一條漂亮但會突然斷裂的繩子，RNG 給你一條稍微鬆一點、但你拉斷一股它只少一股力的纜繩。回到最上面那個 canvas——切到 fat-tree、敲掉中間那顆深藍色的 spine，看 capacity 怎麼掉；再切回 random expander、隨便敲掉幾顆，看它怎麼只少一點點。那個視覺差距，就是「誠實的機率保證」跟「會碎的絕對保證」之間的全部差別。

退一步看，RNG 給我們的不只是一個更省的網路，而是一個關於「保證」的方法論轉向：在故障是常態而非例外的尺度下，把不確定性顯式地寫進設計，比把它藏進「正常情況下」的小字裡更可靠。expander 理論從 1970 年代躺到現在，Friedman 在 1991 年就證明「亂接近乎最優」，Jellyfish 在 2012 年就指出該怎麼用——缺的從來不是理論，是把路由、佈線、運維三道工程牆一起拆掉的決心。Spraypoint、ShuffleBox、外加「先驗證後佈線」的運維模型，補上的正是這三塊。

What this enables：當網路不再假裝自己永不故障、而是把隨機性與退化曲線寫進設計核心，資料中心就能用既有的 router 與光學設備、少 69% 的 router、達到高 33% 的吞吐量，並換來「掉 1% router 只掉 1% 容量」的平滑退化——一張誠實承認自己是機率的網路，比一張假裝確定的網路更耐得住規模。