[Paper Review] Optimizing Paxos with batching and pipelining

05-12

使用batch, pipeline 一直是優化包含state machine 一致性協議的方法, 比如paxos, raft 等等, 這篇文章主要是提出了模型(cpu 利用率, 網路延遲, 網路帶寬), 然後結合實際測試和模擬為我們提供了實際環境中如何使用batch, pipeline 的方法.

首先看結論

結論

在同機房的場景中, 由於網路延遲較低, 即使在小包的情況下, 系統的瓶頸主要是是cpu, 因此只需要通過batch 就可以達到系統最大的吞吐, 而且batch 實現又較為簡單, 因此幾乎在任意的包含狀態機的系統中, batch 是第一步要做的優化.

pipeline 的效果決定於節點的性能和網路延遲, 節點花越多的時間等待從副本的返回, 那麼pipeline 帶來的效果是越好的. pipeline 在上面的實驗中可以看出, 如果允許選擇過多的pipeline 會導致系統性能反而下降

那麼在網路延遲比較高的跨機房場景中, 可以通過batch + pipeline 可以達到最大的吞吐. 那麼該如何進行選擇參數呢

在用戶能夠接受的延遲下, 選擇一個最大的batch size
使用上述的模型, 選擇一個合理的Pipeline 的值

為什麼這樣做呢?

首先batch 帶來的優化是非常明顯, 但是batch 過大會拉大返回的時間. 所在可以在給定帶寬和相應時間的情況下, 我們可以很快的算出這個batch 的大小, 然後可以根據上述的模型, 可以算出設置pipeline 多少個的時候,可以獲得最大的吞吐.

比如在下面跨機房的模型裡面, 如果平均請求的大小是1KB, 那麼根據上述做法 batch 大小應該設置成8kb, 然後pipeline 的個數應該設置成16

TLDR; 接下來是論文具體的內容

模型主要參數:

主要關注3個瓶頸點

網路延遲

其實就是網路帶寬的佔用

cpu time

也就是cpu 的利用

網路帶寬

在區域網中, 主要的瓶頸是cpu, 在廣域網中, 主要的瓶頸是網路延遲. 如果請求都是大包的場景中, 瓶頸主要是帶寬

出現瓶頸的過程基本是這樣, 如果cpu 是瓶頸, 那麼可以通過調整batch 的大小, 因為加大batch 的size 可以提高cpu 的利用率, 如果延遲是瓶頸, 那麼可以增加Pipeline 的個數, 來減少延遲帶來的影響. 如果帶寬是瓶頸, 那麼說明我們已經達到極限了.

最後如何設定這個pipeline 的個數呢?

w = ?min(wcpu,wnet)?.

這裡也就是看cpu 先達到瓶頸, 還是網路先打到瓶頸. 如果cpu 先打到瓶頸, 那麼 w = wcpu, 如果是網路, 那麼w = wnet.

接下來就是通過實際的實驗和模擬對模型的正確性進行了驗證.

這裡instance 值得是執行一整個batch 的時候, 所包含的所有請求, 也就是一個instance 包含多個client request

首先是同機房場景下的驗證

這裡的測試環境是同機房下netperf 940Mbit/s 的網路,

這裡主要三個參數 WND 就是最大的pipeline 的個數, BSZ 就是最大的batch size, 三角形B是最大的batch 時候的timeout

從上面這個圖可以看到

無論 request size 是多少, pipeline 個數對qps 幾乎沒有影響, 主要原因是因為這個時候的主要瓶頸是cpu, 因此提高pipeline 個數對結果沒有影響

上面這幾圖可以看出

4(a) 圖中, 隨著batch size 的增加, 平均每一個客戶端請求的延遲是立刻降低的, 比如這裡從最開始的500ms 降低到了100ms 左右
4(b) 圖中, 隨著batch size 的增加, 執行每一個instance 的延遲是增加的, 因為這個batch 的大小增加了, 也可以理解
4(c) 隨著這裡batch size 的提高, qps 雖然在降低, 但是因為每一個instance 中包含的請求數是增加的, 因此整體的吞吐是增加的, 比如這裡batch size 最小的時候只有2000, 那麼也就是只有200 的qps, 而3(a) 圖中可以看到, 在有一定的batch 大小以後, qps 是可以達到12000 的

這裡仍然可以看出, pipeline 的大小在同機房的場景下,是沒有影響的

這個圖中w = ?min(wcpu,wnet)?. w 表示的是在當前環境下, 最大化的利用資源時, pipeline 的個數, 可以看出, 在同機房的網路中, 幾乎不需要pipeline 都可以達到最大值吞吐, 最大的資源利用率, 因此這裡都可以看出wcpu 都會小於wnet, 因此cpu 一直都是瓶頸, 提高pipeline 是沒有效果的.

在跨機房的場景中的模擬

這裡測試場景中replicas 的帶寬是10Mbits, 延遲是50ms

從上圖可以看到, 在高延遲的跨機房場景中, 雖然通過batch 還是能夠有非常明顯的性能提升, 比如在WND=1 的情形下, 無論batch size 的大小都從只有個位數的 qps 到了 request size = 128 的時候有3000, request size = 1kb 的時候到達了 600 等等, 但是還是無法達到最大的吞吐, 在request size = 1kb, 8kb 的時候, 甚至只有最大吞吐的一半的性能, 因此可以看出在跨機房的場景中, 僅僅通過batch 是達不到最大的吞吐

從上面圖中可以看到,

上圖(a) 中, 在高延遲的跨機房場景中, 在request size 比較小的時候, 僅僅通過pipeline 也同樣達不到最大吞吐(這裡k 表示的是一個batch 請求裡面request 的個數), 但是在request size = 8kb 的時候, 是可以達到最大吞吐的. 為什麼這樣?

在request size 比較小的時候, 主要的瓶頸是cpu, 因此batching 能夠降低平均每一個request 的cpu 利用率. 所以請求數就上來了, 但是當request size 比較大的時候, 那麼這個時候主要瓶頸就是網路帶寬或者網路延遲, 這個時候batch 就沒用了. 當瓶頸是網路延遲的時候, pipeline 能夠有效的提高吞吐, 但是當瓶頸是帶寬的時候, 就沒辦法了

圖(b),(c)還有一個結果是隨著 pipeline window 大小的提高, 反而有性能的下降. 原因是pipeline 過多, 超過了網路的容量, 那麼會導致包的丟失和重傳, 進而影響了網路的效率.

上圖(a)可以看到在跨機房的網路中, 無論pipeline 的個數是多少, 使用batch 都能夠明顯降低客戶端的延遲, 從原來的10s 降低到0.5s 左右, pipeline 個數雖然也影響客戶端的延遲, 但是影響的沒有batch 那麼明顯.

同樣這裡的測試可以看到其實 WND=5的時候, Latency 就已經差不多是最小的了, 所以在polarstore 裡面Praft 裡面的LBA 的大小是2~5 其實就夠了, 之前我一直以為pipeline 的話, 一般都需要有上百個pipeline 並行才會達到最大的吞吐, 但是在praft 中LBA 從1=>2 就有了幾乎翻倍的性能提升, 所以pipeline 其實不需要特別大, 有幾個同時並行就夠了.

上圖(c) 可以看到通過batch 和 pipeline, 在跨機房的網路中, 同樣如果batch size 比較小, 那麼執行的instance 個數就比較多, 但是由於instance 中只包含1個request, 那麼其實獲得的qps 是不夠高的, 需要選擇合理batch size 才可以獲得最大的qps. 比如這裡合理的batch size 應該是20kb

從這裡圖裡面可以看出 w 在request size 比較小並且batch size 也比較小的時候, pipeline 個數需要 20~35 來實現最大的吞吐, 但是隨著batch size 的增加, 其實還是只需要1~2 個來達到最大的吞吐. batch size 唯一的缺點是在壓力不大的時候, request 也需要等待一段時間.

Reference:https://pdfs.semanticscholar.org/a0d0/cdd2e8af1945c03cfaf2cb451f71f208d0c9.pdf