8 月 8 日，GitHub 發(fā)布了開(kāi)源負(fù)載均衡組件 GitHub Load Balancer Director(GLB) Director，GLB 是 GitHub 針對(duì)裸機(jī)數(shù)據(jù)中心的可擴(kuò)展負(fù)載均衡解決方案，它支持大多數(shù) GitHub 的對(duì)外服務(wù)，并且還為諸如高可用 MySQL 集群這樣最為關(guān)鍵的內(nèi)部系統(tǒng)提供負(fù)載均衡服務(wù)。

項(xiàng)目地址：https://github.com/github/glb-director

GLB Director 有如下諸多優(yōu)勢(shì)：

使用ECMP擴(kuò)展IP

4層負(fù)載均衡器的基本屬性是能夠使用單個(gè)IP地址在多個(gè)服務(wù)器之間實(shí)現(xiàn)均衡連接。 為了擴(kuò)展單個(gè)IP以處理更多的流量，我們不僅需要在后端服務(wù)器之間進(jìn)行流量拆分，還需要能夠擴(kuò)展負(fù)載均衡器本身。 這實(shí)際上是另一層負(fù)載均衡。

通常，我們將IP地址視為單個(gè)物理機(jī)器，將路由器視為將數(shù)據(jù)包移動(dòng)到下一個(gè)最近路由器的機(jī)器。 在最簡(jiǎn)單的情況下，總是有一個(gè)最佳的下一跳，路由器選擇該跳并轉(zhuǎn)發(fā)所有數(shù)據(jù)包直到達(dá)到目的地。

實(shí)際上，大多數(shù)網(wǎng)絡(luò)都要復(fù)雜得多。 兩臺(tái)計(jì)算機(jī)之間通常有多條路徑可用，例如，使用多個(gè)ISP或者兩臺(tái)路由器通過(guò)多條物理電纜連接在一起以增加容量并提供冗余。 這是等價(jià)多路徑（ECMP）路由發(fā)揮作用的地方 - 而不是由路由器選擇單個(gè)最佳下一跳，ECMP中很多路徑具有相同成本（通常定義為到目的地的AS的數(shù)量）， 路由器分散流量以便在所有可用的相同成本路徑之間均衡連接。

ECMP通過(guò)對(duì)每個(gè)數(shù)據(jù)包進(jìn)行hash以確定其中一個(gè)可用路徑。此處使用的hash函數(shù)因設(shè)備而異，但通常是基于源和目標(biāo)IP地址以及TCP流量的源和目標(biāo)端口的一致性hash。這意味著同一個(gè)TCP連接的多個(gè)數(shù)據(jù)包通常會(huì)遍歷相同的路徑，這意味著即使路徑具有不同的延遲，數(shù)據(jù)包也會(huì)以相同的順序到達(dá)。值得注意的是，在這種情況下，路徑可以在不中斷連接的情況下進(jìn)行更改，因?yàn)樗鼈兛偸亲罱K位于同一個(gè)目標(biāo)服務(wù)器上，此時(shí)它所采用的路徑大多無(wú)關(guān)緊要。

ECMP的另一種用法是當(dāng)我們想要跨多個(gè)服務(wù)器而不是跨多個(gè)路徑上的同一服務(wù)器時(shí)。每個(gè)服務(wù)器都可以使用BGP或其他類似的網(wǎng)絡(luò)協(xié)議使用相同的IP地址，從而使連接在這些服務(wù)器之間進(jìn)行分片，路由器不知道連接是在不同的地方處理的，而非傳統(tǒng)做法那樣所有的連接都同一臺(tái)機(jī)器上處理。

雖然ECMP會(huì)像對(duì)流量進(jìn)行分片，但它有一個(gè)巨大的缺點(diǎn)：當(dāng)相同IP的服務(wù)器更改（或沿途的任何路徑或路由器發(fā)生變化）時(shí)，連接必須重新均衡，才能保證每個(gè)服務(wù)器上的連接比較均衡。 路由器通常是無(wú)狀態(tài)設(shè)備，只是為每個(gè)數(shù)據(jù)包做出最佳決策而不考慮它所屬的連接，這意味著在這種情況下某些連接會(huì)中斷。

在上面的例子中，我們可以想象每種顏色代表一個(gè)活動(dòng)的連接。 添加新的代理服務(wù)器使用相同的IP。 路由器保證一致性哈希，將1/3連接移動(dòng)到新服務(wù)器，同時(shí)保持2/3連接在老服務(wù)器上。 不幸的是，對(duì)于進(jìn)行中的1/3連接，數(shù)據(jù)包現(xiàn)在到達(dá)了無(wú)連接狀態(tài)的服務(wù)器，因此連接會(huì)失敗。

將director/proxy分離

以前僅使用ECMP的解決方案的問(wèn)題在于它不知道給定數(shù)據(jù)包的完整上下文，也不能為每個(gè)數(shù)據(jù)包/連接存儲(chǔ)數(shù)據(jù)。事實(shí)證明，通常使用Linux Virtual Server（LVS）等工具。我們創(chuàng)建了一個(gè)新的“director”服務(wù)器層，它通過(guò)ECMP從路由器獲取數(shù)據(jù)包，但不是依靠路由器的ECMP hash來(lái)選擇后端代理服務(wù)器，而是對(duì)所有鏈接控制hash和存儲(chǔ)狀態(tài)（選擇后端）。當(dāng)我們更改代理層服務(wù)器時(shí)，director層有望不變，我們的連接也不會(huì)斷掉。

雖然這在許多情況下效果很好，但它確實(shí)有一些缺點(diǎn)。在上面的示例中，我們同時(shí)添加了LVS director和后端代理服務(wù)器。新的director接收到一些數(shù)據(jù)包，但是還沒(méi)有任何狀態(tài)（或者具有延遲狀態(tài)），因此將其作為新連接進(jìn)行hash處理并可能使其出錯(cuò)（并導(dǎo)致連接失?。?。 LVS的典型解決方法是使用多播連接同步來(lái)保持所有LVS director服務(wù)器之間共享的連接狀態(tài)。這仍然需要傳播連接狀態(tài)，并且仍然需要重復(fù)狀態(tài) - 不僅每個(gè)代理都需要Linux內(nèi)核網(wǎng)絡(luò)堆棧中每個(gè)連接的狀態(tài)，而且每個(gè)LVS director還需要存儲(chǔ)連接到后端代理服務(wù)器的映射。

將所有狀態(tài)從director層移除

當(dāng)我們?cè)O(shè)計(jì)GLB時(shí)，我們決定要改善這種情況而不是重復(fù)狀態(tài)。 通過(guò)使用已存儲(chǔ)在代理服務(wù)器中的流狀態(tài)作為維護(hù)來(lái)自客戶端的已建立Linux TCP連接的一部分，GLB采用與上述方法不同的方法。

對(duì)于每個(gè)進(jìn)入的連接，我們選擇可以處理該連接的主服務(wù)器和輔助服務(wù)器。 當(dāng)數(shù)據(jù)包到達(dá)主服務(wù)器且無(wú)效時(shí)，會(huì)將數(shù)據(jù)包轉(zhuǎn)發(fā)到輔助服務(wù)器。 選擇主/輔助服務(wù)器的散列是預(yù)先完成一次，并存儲(chǔ)在查找表中，因此不需要在每個(gè)流或每個(gè)數(shù)據(jù)包的基礎(chǔ)上重新計(jì)算。 添加新的代理服務(wù)器時(shí)，對(duì)于1/N連接，它將成為新的主服務(wù)器，舊的主服務(wù)器將成為輔助服務(wù)器。 這允許現(xiàn)有流程完成，因?yàn)榇矸?wù)器可以使用其本地狀態(tài)（單一事實(shí)來(lái)源）做出決策。 從本質(zhì)上講，這使得數(shù)據(jù)包在到達(dá)保持其狀態(tài)的預(yù)期服務(wù)器時(shí)具有“第二次機(jī)會(huì)”。

即使director仍然會(huì)將連接發(fā)送到錯(cuò)誤的服務(wù)器，該服務(wù)器也會(huì)知道如何將數(shù)據(jù)包轉(zhuǎn)發(fā)到正確的服務(wù)器。 就TCP流而言，GLB director層是完全無(wú)狀態(tài)的：director服務(wù)器可以隨時(shí)進(jìn)出，并且總是選擇相同的主/輔服務(wù)器，只要它們的轉(zhuǎn)發(fā)表匹配（但它們很少改變）。 在變更代理時(shí)有些細(xì)節(jié)需要注意，我們將在下面介紹。

維護(hù)Hash集合不變

GLB Director設(shè)計(jì)的核心歸結(jié)為始終如一地選擇主服務(wù)器和輔助服務(wù)器，并允許代理層服務(wù)器根據(jù)需要排空和填充。 我們認(rèn)為每個(gè)代理服務(wù)器都有一個(gè)狀態(tài)，當(dāng)有服務(wù)器加入或者退出時(shí)調(diào)整狀態(tài)。

我們創(chuàng)建一個(gè)靜態(tài)二進(jìn)制轉(zhuǎn)發(fā)表，它以相同方式在每個(gè)控制器服務(wù)器上生成，以將進(jìn)入的連接映射到給定的主服務(wù)器和輔助服務(wù)器。 我們并沒(méi)有采用在數(shù)據(jù)包處理時(shí)從所有可用服務(wù)器中選擇服務(wù)器的這種復(fù)雜邏輯，而是通過(guò)創(chuàng)建表（65k行）這種間接的方式，每行包含主服務(wù)器和輔助服務(wù)器IP地址。 該表以二維數(shù)組的方式將數(shù)據(jù)存儲(chǔ)在內(nèi)存中，每個(gè)表大約512kb。 當(dāng)數(shù)據(jù)包到達(dá)時(shí)，我們始終將其（僅基于數(shù)據(jù)包數(shù)據(jù)）hash到該表中的同一行（使用hash作為數(shù)組的索引），這提供了一致的主服務(wù)器和輔助服務(wù)器對(duì)。

我們希望每個(gè)服務(wù)器在主要和輔助字段中大致相同，并且永遠(yuǎn)不會(huì)出現(xiàn)在同一行中。 當(dāng)我們添加新服務(wù)器時(shí)，我們希望某些行使其主服務(wù)器成為輔助服務(wù)器，并且新服務(wù)器將成為主服務(wù)器。 同樣，我們希望新服務(wù)器在某些行中成為輔助服務(wù)器。 當(dāng)我們刪除服務(wù)器時(shí)，在它是主服務(wù)器的任何行中，我們希望輔助服務(wù)器成為主服務(wù)器，而另一個(gè)服務(wù)器則成為輔助服務(wù)器。

這聽(tīng)起來(lái)很復(fù)雜，但可以用幾個(gè)不變量簡(jiǎn)潔地概括：

• 當(dāng)我們更改服務(wù)器集時(shí)，應(yīng)保持現(xiàn)有服務(wù)器的相對(duì)順序。

• 服務(wù)器的順序應(yīng)該是可計(jì)算的，除了服務(wù)器列表之外沒(méi)有任何其他狀態(tài)（可能還有一些預(yù)定義的種子）。

• 每個(gè)服務(wù)器在每行中最多應(yīng)出現(xiàn)一次。

• 每個(gè)服務(wù)器在每列中的出現(xiàn)次數(shù)應(yīng)大致相同。

針對(duì)上述的一些問(wèn)題，集合hash是一個(gè)理想的選擇，因?yàn)樗梢院芎玫貪M足這些不變量。 每個(gè)服務(wù)器（在我們的例子中，IP）都與行號(hào)一起進(jìn)行hash，服務(wù)器按該hash（只是一個(gè)數(shù)字）進(jìn)行排序，并且我們獲得該給定行的服務(wù)器的唯一順序。 我們分別將前兩個(gè)作為主要和次要。

將保持相對(duì)順序，因?yàn)闊o(wú)論包含哪些其他服務(wù)器，每個(gè)服務(wù)器的hash都是相同的。 生成表所需的唯一信息是服務(wù)器的IP。由于我們只是對(duì)一組服務(wù)器進(jìn)行排序，因此服務(wù)器只出現(xiàn)一次。 最后，如果我們使用偽隨機(jī)的良好hash函數(shù)，那么排序?qū)⑹莻坞S機(jī)的，因此分布將如我們所期望的那樣均勻。

代理(Proxy)相關(guān)操作

添加或刪除代理服務(wù)器，我們需要一些特別的處理方式。這是因?yàn)檗D(zhuǎn)發(fā)表?xiàng)l目?jī)H定義主要/輔助代理，因此排空/故障轉(zhuǎn)移僅適用單個(gè)代理主機(jī)。 我們?yōu)榇矸?wù)器定義以下有效狀態(tài)和狀態(tài)轉(zhuǎn)換：

當(dāng)代理服務(wù)器處于活動(dòng)狀態(tài)，耗盡或填充時(shí)，它將包含在轉(zhuǎn)發(fā)表?xiàng)l目中。 在穩(wěn)定狀態(tài)下，所有代理服務(wù)器都是活動(dòng)的，并且上面描述的集合點(diǎn)散列將在主列和輔助列中具有大致均勻且隨機(jī)的每個(gè)代理服務(wù)器分布。

當(dāng)代理服務(wù)器轉(zhuǎn)換為耗盡時(shí)，我們通過(guò)交換我們?cè)景闹饕痛我獥l目來(lái)調(diào)整轉(zhuǎn)發(fā)表中的條目：

這具有將數(shù)據(jù)包發(fā)送到先前次要的服務(wù)器的效果。 由于它首先接收數(shù)據(jù)包，它將接受SYN數(shù)據(jù)包，因此接受任何新連接。 對(duì)于任何不理解為與本地流有關(guān)的數(shù)據(jù)包，它將其轉(zhuǎn)發(fā)到其他服務(wù)器（先前的主服務(wù)器），這允許完成現(xiàn)有連接。

這樣可以優(yōu)雅地耗盡所需的連接服務(wù)器，之后可以完全刪除它，并且代理可以隨機(jī)填充到第二個(gè)空槽：

填充中的節(jié)點(diǎn)看起來(lái)就像活動(dòng)一樣，因?yàn)樵摫肀旧碓试S第二次機(jī)會(huì)：

此實(shí)現(xiàn)要求一次只有一個(gè)代理服務(wù)器處于活動(dòng)狀態(tài)以外的任何狀態(tài)，這實(shí)際上在GitHub上運(yùn)行良好。對(duì)代理服務(wù)器的狀態(tài)更改可以與需要維護(hù)的最長(zhǎng)連接持續(xù)時(shí)間一樣快。我們正致力于設(shè)計(jì)的擴(kuò)展，不僅支持主要和次要，而且一些組件（如下面列出的標(biāo)題）已經(jīng)包含對(duì)任意服務(wù)器列表的初始支持。

數(shù)據(jù)中心內(nèi)封裝

現(xiàn)在有了一個(gè)算法來(lái)一致地選擇后端代理服務(wù)器，但是如何在數(shù)據(jù)包內(nèi)把輔助服務(wù)器（secondary server ）的信息也封裝進(jìn)去呢？這樣主服務(wù)器可以在不理解數(shù)據(jù)包的情況下轉(zhuǎn)發(fā)數(shù)據(jù)包。

LVS 的傳統(tǒng)方式是使用IP over IP（IPIP）隧道?？蛻舳?IP 數(shù)據(jù)包封裝在內(nèi)部IP數(shù)據(jù)包內(nèi)，并轉(zhuǎn)發(fā)到代理服務(wù)器，代理服務(wù)器對(duì)其進(jìn)行解封裝。但很難在 IPIP 數(shù)據(jù)包中編碼其他服務(wù)器的元數(shù)據(jù)，因?yàn)槲ㄒ豢捎玫目臻g是 IP 選項(xiàng)，數(shù)據(jù)中心路由器傳遞未知 IP 的數(shù)據(jù)包到處理軟件（稱之為“第2層慢速路徑”），速度從每秒數(shù)百萬(wàn)到數(shù)千個(gè)數(shù)據(jù)包。

為了避免這種情況，需要將數(shù)據(jù)隱藏在路由器不同數(shù)據(jù)包格式中，避免它試圖去理解。我們最初采用原始 Foo-over-UDP（FOU）和自定義 GRE載荷（payload），基本上封裝了 UDP 數(shù)據(jù)包中的所有內(nèi)容。我們最近轉(zhuǎn)換到通用 UDP 封裝（GUE），它提供了封裝內(nèi)部 IP 協(xié)議的標(biāo)準(zhǔn) UDP 數(shù)據(jù)包。我們將輔助服務(wù)器的 IP 放在GUE標(biāo)頭的私有數(shù)據(jù)中。從路由器的角度來(lái)看，這些數(shù)據(jù)包都是兩個(gè)普通服務(wù)器之間的內(nèi)部數(shù)據(jù)中心 UDP 數(shù)據(jù)包。

使用 UDP 的另一個(gè)好處是源端口可以使用每個(gè)連接的哈希填充，以便它們通過(guò)不同的路徑（在數(shù)據(jù)中心內(nèi)使用ECMP）在數(shù)據(jù)中心內(nèi)流動(dòng)，并可在代理服務(wù)器的 NIC 的不同 RX 隊(duì)列上接收消息（類似使用 TCP/IP 頭字段的哈希）。這對(duì) IPIP 是不可能的，因?yàn)榇蠖鄶?shù)數(shù)據(jù)中心的 NIC 只能理解普通 IP，TCP/IP 和 UDP/IP。值得注意的是，NIC 無(wú)法查看 IP/IP 數(shù)據(jù)包。

當(dāng)代理服務(wù)器想要將數(shù)據(jù)包發(fā)送回客戶端時(shí)，它不需要封裝或通過(guò)我們的導(dǎo)向器層（director tier）返回，它可以直接發(fā)送數(shù)據(jù)到客戶端（通常稱為“Direct Server Return”）。這是典型的負(fù)載均衡器設(shè)計(jì)，對(duì)于內(nèi)容提供商尤其有用，因?yàn)榇蠖鄶?shù)情況都是出站流量遠(yuǎn)大于入站流量。

數(shù)據(jù)包流如下圖所示：

引入DPDK

自從首次公開(kāi)討論了我們的初始設(shè)計(jì)以來(lái)，我們已經(jīng)完全使用 DPDK重寫了 glb-director 。DPDK 是一個(gè)開(kāi)源的通過(guò)繞過(guò)Linux內(nèi)核，允許從用戶空間進(jìn)行非?？焖俚臄?shù)據(jù)包處理的項(xiàng)目。這樣就能夠在普通 NIC 上通過(guò) CPU 上實(shí)現(xiàn) NIC 線路速率處理，并可輕松擴(kuò)展導(dǎo)向器層，以處理與公共連接所需的入站流量一樣多的流量。這在防 DDoS 攻擊中尤為重要，我們不希望負(fù)載均衡器成為瓶頸。

GLB 最初的目標(biāo)之一是可以在通用數(shù)據(jù)中心的硬件上運(yùn)行，而無(wú)需任何特殊的硬件配置。 GLB 的 Director 和代理服務(wù)器都可像數(shù)據(jù)中心的普通服務(wù)器一樣供應(yīng)。每個(gè)服務(wù)器都有一對(duì)綁定的網(wǎng)絡(luò)接口，這些接口在 GLB Director 服務(wù)器上的 DPDK 和 Linux 系統(tǒng)之間共享。

現(xiàn)代 NIC 支持SR-IOV，這種技術(shù)可以使單個(gè) NIC 從操作系統(tǒng)的角度看起來(lái)像多個(gè) NIC。這通常由虛擬機(jī)管理程序使用，以要求真實(shí) NIC（“Physical Function”）為每個(gè) VM 創(chuàng)建多個(gè)虛擬 NIC（“Virtual Functions”）。為了使 DPDK 和 Linux 內(nèi)核能夠共享 NIC，我們使用 flow bifurcation，它將特定流量（目標(biāo)是 GLB IP 地址）發(fā)送給我們DPDK 在 Virtual Function 上處理，同時(shí)將剩余的數(shù)據(jù)包與 Linux 內(nèi)核的網(wǎng)絡(luò)堆棧保留在 Physical Function 上。

我們發(fā)現(xiàn) Virtual Function 上 DPDK 的數(shù)據(jù)包處理速率可以滿足要求。 GLB Director 使用 DPDK Packet Distributor模式來(lái)分發(fā)封裝數(shù)據(jù)包的任務(wù)到機(jī)器上的 CPU，支持任意數(shù)量的 CPU 核心，因?yàn)樗菬o(wú)狀態(tài)的，可以高度并行化。

GLB Director 支持匹配和轉(zhuǎn)發(fā)包含 TCP 有效負(fù)載的入站 IPv4 和 IPv6 數(shù)據(jù)包，以及作為 Path MTU Discovery的一部分的入站 ICMP Fragmentation Required 消息。

使用Scapy為DPDK加入測(cè)試用例

一個(gè)典型的問(wèn)題是，在創(chuàng)建（或使用）那些使用了低級(jí)原語(yǔ)（例如直接與NIC通信）但是高速運(yùn)行的技術(shù)時(shí)，它們變得非常難以測(cè)試。作為創(chuàng)建GLB Director的一部分，我們也創(chuàng)建了一個(gè)測(cè)試環(huán)境，支持對(duì)我們的DPDK應(yīng)用進(jìn)行簡(jiǎn)單的端對(duì)端包流測(cè)試，通過(guò)影響DPDK的方式支持一個(gè)環(huán)境抽象層（EAL），允許物理NIC和基于libpcap的本地接口，在應(yīng)用視圖中是相同的。

這允許我們?cè)赟capy中寫測(cè)試，使用簡(jiǎn)單的Python的lib包查看，操作和寫數(shù)據(jù)包。通過(guò)創(chuàng)建一個(gè)Linux的虛擬網(wǎng)卡驅(qū)動(dòng)，一邊用Scapy，另一邊用DPDK，我們能傳輸定制的包并且驗(yàn)證我們軟件在另一邊支持的功能，這是一個(gè)完整GUE封裝的后端代理服務(wù)期望的數(shù)據(jù)包。

該方法允許我們測(cè)試更多的復(fù)雜行為，例如為了正確路由，遍歷傳輸層的ICMPv4/ICMPv6頭獲取源IP和TCP端口，以便正確轉(zhuǎn)發(fā)來(lái)自外部路由器的ICMP消息。

健康檢查

GLB的設(shè)計(jì)包含了優(yōu)雅地處理服務(wù)器故障的部分。目前設(shè)計(jì)包含主/備，對(duì)于給定的轉(zhuǎn)發(fā)表/客戶端，意味著我們可以通過(guò)健康檢查通過(guò)觀察每個(gè)Director來(lái)解決單服務(wù)器故障。我們運(yùn)行一個(gè)名為glb-healthcheck的服務(wù)，它不斷驗(yàn)證每個(gè)后端服務(wù)器的GUE隧道和任意HTTP端口。

當(dāng)服務(wù)器出現(xiàn)故障時(shí)，我們將切換主/備，將備換成主。這是服務(wù)器的“軟切換”，支持故障轉(zhuǎn)移的好辦法。如果健康檢查失敗是誤報(bào)，則連接不會(huì)中斷，它們只會(huì)換一條不同的路徑遍歷。

proxy使用iptables提供第二次機(jī)會(huì)

構(gòu)成GLB的最后一個(gè)組件是Netfilter模塊和iptables的目標(biāo)，它在每個(gè)代理服務(wù)器上運(yùn)行，并提供“第二次機(jī)會(huì)”進(jìn)行設(shè)計(jì)。

此模塊提供了一個(gè)簡(jiǎn)單的任務(wù)，根據(jù)Linux內(nèi)核TCP堆棧，確定每個(gè)GUE數(shù)據(jù)包的內(nèi)部TCP / IP數(shù)據(jù)包是否在本地有效，如果不是，則將其轉(zhuǎn)發(fā)到下一個(gè)代理服務(wù)器（備服務(wù)器），而不是在當(dāng)前服務(wù)器解封裝。

在數(shù)據(jù)包是SYN（新連接）或在本地對(duì)已建立的連接有效的情況下，當(dāng)前服務(wù)器會(huì)接收它。然后，我們接收GUE包，使用包含fou模塊的Linux 內(nèi)核4.x GUE在本地處理它。