Balancer 負載優化 查核點討論

[garyparrot]

情境

Kafka 叢集中存在一個吞吐量顯著地高，且其 Topic 的 Record Key 有著非常明顯的不平衡分佈。這個情境下叢集的網路流量會存在顯著地不平衡趨勢，Astraea Balancer 要能夠產生一個負載平衡的計劃，在套用至叢集後，能夠使下列提到的三個查核項目能夠一次滿足。

叢集規模

• 6 Broker, 9 Producer/Consumer
• Kafka Broker/Producer/Consumer 硬體規格參考 Issue 130 的 Balancer 設備敘述
• 1 Prometheus 在另外一個 Rack

叢集負載種類

由於 Kafka 本身的設計不一定會觸發負載不平衡的情況，這個查驗的情境設計成負載不平衡的情況一定會發生，此驗收叢集被設計成無 Replication 的情境。

普通 Topic

• 1000 個
• 平均 Topic 流量 1.5 MB/s (依 Pareto Distribution 分佈)
• Partition 10 個 ± 5 個 (有 Skewed Load)
• Replica Factor = 1
• Consumer Fanout = 1 ~ 6
• 依照 Kafka 預設邏輯擺放負載

骨幹 Topic

• 1 個
• Topic 流量 950 MB/s ± 20%
• Partition 24 個
• Replica Factor = 1
• Consumer Fanout = 1
• 依照 Kafka 預設邏輯擺放負載
• Record Key 存在分佈不平衡的趨勢

查核點

比較對象：負載優化前的叢集

• 節點讀取效能平衡程度改善至少 30%
• 節點寫入效能平衡程度改善至少 40%
• 每個節點負責的 Partition 數量介於平均量 ± 30%

附註

• 節點讀取/寫入平衡程度: 1- (節點網路流量最低值) / (節點網路流量最高值)
• 節點的網路負載僅考慮來自 Producer/Consumer 的流量
• 節點服務的 Partition 數量越多，他單位時間要處理的 Request 會越多，造成發送上的延遲。我這邊測試，兩個節點都各輸入 500 MB/s 的資料，但一個節點 2000 Partition，一個節點 1 Partition，前者的 Publish Latency 大約 10ms，而後者 Publish Latency 約 0.64ms。因此第三個查核點：平衡每個節點維護的 Partition 數量，對 Latency 有好處。

[chia7712]

感謝更新，幾個建議：

1. 監控用的元件可否用不同rack的節點來執行？我猜不會有太大的效能議題，這樣可以弄出一台來做客戶端
2. Topic的數量可否改成 > 1000？這樣的量級會比較真實一點
3. Replica =1 應該是代表此次查核我們要先忽略內部同步的流量？如果是的話可否在查核點上說明一下網路輸出輸入的部分只考慮伺服器跟客戶端之間的流量
4. Consumer fanout 的數量加總似乎跟客戶端節點數量不太一樣，客戶端至少有8台，假如是測試查核點的的時候，consumer fanout只有 3+1=4？還是說我誤會 consumer fanout 的意思？
5. 查核點的三個改善應該是分開的吧？也就是我們並沒有預期可以跑一次負載平衡同時達到三種不同面向的改善？如果是分開的話，麻煩文字要說明一下

[garyparrot]

已更正，感謝

Replica =1 應該是代表此次查核我們要先忽略內部同步的流量？如果是的話可否在查核點上說明一下網路輸出輸入的部分只考慮伺服器跟客戶端之間的流量

主要是 Kafka 本身的設計不一定會發生負載不平衡的情況，不使用 Replica 是因為有機會會不小心產生一個剛好負載很平衡的叢集，怕驗收太複雜所以我把情境弄成一定會不平衡的樣子。如果要考量 Replica 也不是不行，不過這樣叢集就不能隨機生成，或許要在叢集假設那邊添加一個但書，說叢集有負載不平衡的情形，然後叢集的 Topic 流量分佈會刻意被調整成不平衡的打法。我是怕這樣做會有人為介入的因素在而有一些疑慮。

Consumer fanout 的數量加總似乎跟客戶端節點數量不太一樣，客戶端至少有8台，假如是測試查核點的的時候，consumer fanout只有 3+1=4？還是說我誤會 consumer fanout 的意思？

應該說是 Topic 的 Consumer Fanout，就這個 topic 有多少個 Consumer Group 在消費。

查核點的三個改善應該是分開的吧？也就是我們並沒有預期可以跑一次負載平衡同時達到三種不同面向的改善？如果是分開的話，麻煩文字要說明一下

我本來是設計成一次做到三個面向，因為如果只一個做到非常好但其他做的很爛的話，那這樣的優化好像也沒有太大的意義。

[chia7712]

主要是 Kafka 本身的設計不一定會發生負載不平衡的情況，不使用 Replica 是因為有機會會不小心產生一個剛好負載很平衡的叢集，怕驗收太複雜所以我把情境弄成一定會不平衡的樣子。如果要考量 Replica 也不是不行，不過這樣叢集就不能隨機生成，或許要在叢集假設那邊添加一個但書，說叢集有負載不平衡的情形，然後叢集的 Topic 流量分佈會刻意被調整成不平衡的打法。我是怕這樣做會有人為介入的因素在而有一些疑慮。

這個擔憂合理，就麻煩文字上說明一下，調整是為了方便呈現查核時的數據呈現

應該說是 Topic 的 Consumer Fanout，就這個 topic 有多少個 Consumer Group 在消費。

瞭解，不過這個數字跟查核的內容哪一點比較有關係？

我本來是設計成一次做到三個面向，因為如果只一個做到非常好但其他做的很爛的話，那這樣的優化好像也沒有太大的意義。

這個目標很棒，就朝這個前進。

[chia7712]

我本來是設計成一次做到三個面向，因為如果只一個做到非常好但其他做的很爛的話，那這樣的優化好像也沒有太大的意義。

另外如果是要做三個面向的話，第一和第二個查核點都是偏向頻寬，第三項的話則是偏向連線數（我假設leader 也會平衡）、可以思考一下有沒有第三種分類是在上述平衡時會一併處理好的東西

[garyparrot]

這個擔憂合理，就麻煩文字上說明一下，調整是為了方便呈現查核時的數據呈現

已更新

應該說是 Topic 的 Consumer Fanout，就這個 topic 有多少個 Consumer Group 在消費。

瞭解，不過這個數字跟查核的內容哪一點比較有關係？

和節點的網路輸出負載有關

另外如果是要做三個面向的話，第一和第二個查核點都是偏向頻寬，第三項的話則是偏向連線數（我假設leader 也會平衡）、可以思考一下有沒有第三種分類是在上述平衡時會一併處理好的東西

第一個和第二個雖然都是頻寬，但是他們應該被視為不同的優化對象， 因為有 Consumer Fanout 這個不確定因素存在，因此輸入負載平衡不一定會輸出負載平衡，我覺得他們可以分成兩個驗收項目。

[chia7712]

因此輸入負載平衡不一定會輸出負載平衡，我覺得他們可以分成兩個驗收項目。

ok，那文字上可否調整成「讀取效能改善」和「寫入效能改善」？這樣從文字上比較能表達出你說的「不同對象」（讀和寫很明確是不同的對象，然後查核時再用你說的頻寬進出來呈現

[garyparrot]

ok，那文字上可否調整成「讀取效能改善」和「寫入效能改善」？這樣從文字上比較能表達出你說的「不同對象」（讀和寫很明確是不同的對象，然後查核時再用你說的頻寬進出來呈現

感謝，已修正

[chia7712]

硬體規格參考 Github

可否將連結到對應議題？

[garyparrot]

節點服務的 Partition 數量越多，他單位時間要處理的 Request 會越多，造成發送上的延遲。我這邊測試，兩個節點都各輸入 500 MB/s 的資料，但一個節點 2000 Partition，一個節點 1 Partition，前者的 Publish Latency 大約 10ms，而後者 Publish Latency 約 0.64ms。因此第三個查核點：平衡每個節點維護的 Partition 數量，對 Latency 有好處。

更新關於第三個查核點的優化目標

[chia7712]

@garyparrot 感謝更新，balancer的部分看起來沒問題了，感謝

[garyparrot]

1000 個

我剛剛在嘗試建立環境的時候發現，Kafka 的建立 topic 操作不太能併發，我測試出來的速度約 1 秒鐘建立 1 個 Topic。這樣下來如果實驗要準備 1000 個 topic，這個過程會需要大約 16 分鐘，這可能是以後實驗要注意的事情。

[chia7712]

Kafka 的建立 topic 操作不太能併發

請問可否分享遇到的問題的細節？例如錯誤資訊或是觀察到什麼怪異的現象

[garyparrot]

請問可否分享遇到的問題的細節？例如錯誤資訊或是觀察到什麼怪異的現象

抱歉沒事了，我剛剛是對開在自己實驗室電腦開的測試叢集建立 topic，因為不知名的原因實驗室電腦上的叢集開起來特別慢，在其他地方建起來會比較快。

• 實驗室電腦的叢集： 建 10 個 topic 要約 10 秒
• 筆電的 test 環境的叢集：建 10 個 topic 要約 0.6 秒
• 筆電的 docker 叢集： 建 10 個 topic 要約 1.2 秒
• 實驗室後面的叢集：建 10 個 topic 約 1 秒

我沒看到實驗室電腦的叢集有出現錯誤

測試的程式碼

  @Test
  void testCreateTopics() {
    var host = SERVICE.bootstrapServers(); // 改成其他叢集
    try (var admin = Admin.of(host)) {
      long start = System.currentTimeMillis();
      IntStream.range(0, 10)
          .mapToObj(i -> Utils.randomString())
          .map(name -> admin.creator()
              .topic(name)
              .numberOfPartitions(10)
              .numberOfReplicas((short) 1)
              .run())
          .map(CompletionStage::toCompletableFuture)
          .collect(Collectors.toUnmodifiableSet())
          .forEach(CompletableFuture::join);
      long end = System.currentTimeMillis();
      System.out.println("Time: " + (end - start) / 1000.0);
    }
  }

[chia7712]

節點讀取/寫入平衡程度: 1- (節點網路流量最低值) / (節點網路流量最高值)

這句話的意思是值越高越好嗎？另外可否說明一下改善前和改善後兩者會如何比較

另外我們那天討論，負載平衡的目標是看某個 topic 下的平衡？還是看整個叢集？

[garyparrot]

節點讀取/寫入平衡程度: 1- (節點網路流量最低值) / (節點網路流量最高值)

這句話的意思是值越高越好嗎？另外可否說明一下改善前和改善後兩者會如何比較

是越低越好，其實他中文應該稱作不平衡程度，一些實際的例子是：

• 叢集內節點的最高流量是 500 MB/s，最低是 0 MB/s，則那個數字算出來會是 1 - 0 / 500 = 100%
• 叢集內節點的最高流量是 500 MB/s，最低是 250 MB/s，則那個數字算出來會是 1 - 250 / 500 = 50%
• 叢集內節點的最高流量是 500 MB/s，最低是 500 MB/s，則那個數字算出來會是 1 - 500 / 500 = 0%

另外可否說明一下改善前和改善後兩者會如何比較

具體的數學公式是 x1 = (1 - a) * x0，其中

• x1 是改善後的負載不平衡程度
• x0 是改善前的負載不平衡程度
• a 是改善的比例

一些具體的例子是

• 原本叢集內的最高流量是 500 MB/s，最低是 250 MB/s，這樣 x0 是 50%
  • 如果改善後變成最高 450 MB/s 最低 400 MB/s，這樣 x1 是 11.11%，則改善程度 a 是 78%
  • 如果改善後變成最高 499 MB/s 最低 251 MB/s，這樣 x1 是 49.70%，則改善程度 a 是 0.6%
  • 如果改善後變成最高 750 MB/s 最低 0 MB/s，這樣 x1 是 100%，則改善程度 a 是 -100%
  • 如果改善後變成最高 425 MB/s 最低 425 MB/s，這樣 x1 是 0%，則改善程度 a 是 100%

[chia7712]

具體的數學公式是 x1 = (1 - a) * x0，其中

這個算法可能會出現平衡後整體效能下降，但最大最小差距變小，但得到平衡程度變好的結論，你覺得呢？

[garyparrot]

這個算法可能會出現平衡後整體效能下降，但最大最小差距變小，但得到平衡程度變好的結論，你覺得呢？

那可能加上一個但書，負載優化後，整體叢集的吞吐量要大於等於負載優化前。

要再更嚴格的話就是每個 Topic 的吞吐量都要大於等於負載優化前

[chia7712]

那可能加上一個但書，負載優化後，整體叢集的吞吐量要大於等於負載優化前。
要再更嚴格的話就是每個 Topic 的吞吐量都要大於等於負載優化前

前一個比較有機會達成，後一個的話，如果我們驗收是只做一兩個topic的話，後面這個優化感覺意義不大，不過我看描述中還是以大量topic為目標，這是另一個疑問，那天會議我們討論可以改成少量topic和大量partition，這件事情後來有定案嗎

[garyparrot]

那天會議我們討論可以改成少量topic和大量partition，這件事情後來有定案嗎

要用少量 topic 和大量 partition 也行，不過我找不到這樣做的理由，通常 Partition 數量也不會開到太多，反而 topic 多的 Kafka 叢集感覺似乎還比較有這個叢集支持很多業務邏輯的感覺

[chia7712]

要用少量 topic 和大量 partition 也行，不過我找不到這樣做的理由，通常 Partition 數量也不會開到太多，反而 topic 多的 Kafka 叢集感覺似乎還比較有這個叢集支持很多業務邏輯的感覺

我記得那天會說到少量topic 和大量partitions的原因是：這樣方便用 key 來打出不平衡的狀態

所以後來上面這個原因有做實驗了嗎？在大量 topic下可以用key distribution打出不平衡的狀態嗎？

[garyparrot]

我記得那天會說到少量topic 和大量partitions的原因是：這樣方便用 key 來打出不平衡的狀態
所以後來上面這個原因有做實驗了嗎？在大量 topic下可以用key distribution打出不平衡的狀態嗎？

大量 topic 下可以打出來，只要 zipfian 的 topic 的流量特高就可以做出來，Produce 方面的不平衡大約 max - min = 150 MB/s，而 Consume 方面大約 max - min = 50 MB/s。

[chia7712]

而 Consume 方面大約 max - min = 50 MB/s。

這個差距還蠻有趣的

@harryteng9527 麻煩看一下我們的討論，key 分布不均的實驗你也可以考慮參考，這會比起手動控制流量更自然和常見

[garyparrot]

上圖是目前實驗的結果

• Ingress 的部分進步有限，看起來 Balancer 那邊有一個很大的空間跨不過去
• Egress 的部分還行，但還稱不太上完全平衡
• 平衡前和平衡後的流量一致，沒有整體吞吐量下降的問題

感覺演算法的部分需要進步一下。

[chia7712]

@garyparrot 感謝分享，幾個問題請教一下：

Ingress 的部分進步有限

就左上角的圖來看，似乎最大最小的範圍有“稍微”縮小一點，而這就是你說的進步有限嗎？

Egress 的部分還行，但還稱不太上完全平衡

同上，縮小的幅度看起來比較大？

平衡前和平衡後的流量一致，沒有整體吞吐量下降的問題

請問一下 balancing 的期限流量幾乎消失是為什麼？Ingress/Egress只有統計來自客戶端的流量嗎？

[garyparrot]

就左上角的圖來看，似乎最大最小的範圍有“稍微”縮小一點，而這就是你說的進步有限嗎？

是的

同上，縮小的幅度看起來比較大？

是的

請問一下 balancing 的期限流量幾乎消失是為什麼？Ingress/Egress只有統計來自客戶端的流量嗎？

目前故事是假設在叢集 Online 的時候收集效能數據，而 Offline 的時候做負載優化，所以 Balancing 的時候 Client 的流量會停掉，等搬移完後再重開。

[chia7712]

目前故事是假設在叢集 Online 的時候收集效能數據，而 Offline 的時候做負載優化，所以 Balancing 的時候 Client 的流量會停掉，等搬移完後再重開。

ok，所以這個實驗中大概花了五分鐘完成負載平衡嗎

[garyparrot]

ok，所以這個實驗中大概花了五分鐘完成負載平衡嗎

實際上搬移負載是 1 分鐘（看下面的 Ongoing Reassignment），Client 下線到觸發搬移，和搬移結束 Client 上限這段現在是手動觸發，所以並非每個時間點都在做搬移，有時候我按鈕比較慢按。

[garyparrot]

上面 1分鐘這個沒有算入計算計劃的時間，計算計劃我是設定 5 分鐘。

[chia7712]

實際上搬移負載是 1 分鐘（看下面的 Ongoing Reassignment），Client 下線到觸發搬移，和搬移結束 Client 上限這段現在是手動觸發，所以並非每個時間點都在做搬移，有時候我按鈕比較慢按。

喔喔，了解，感謝告知

[garyparrot]

用 CostProfiling 跑過幾次之後確定是 cost 值沒辦法被繼續優化的關係，後面會試看看如何讓算法的優化能力變好一點。

目前猜測問題是在 Backbone 的流量太大，進步的幅度太小，以現在的算法邏輯這些小進步會被嫌棄，然後就卡住優化不了。

60秒

120 秒

180 秒

[chia7712]

用 CostProfiling 跑過幾次之後確定是 cost 值沒辦法被繼續優化的關係，後面會試看看如何讓算法的優化能力變好一點。

請問一下用了哪些參數？就是哪些 cost function

[garyparrot]

請問一下用了哪些參數？就是哪些 cost function

• NetworkIngressCost 權重 3.0
• NetworkEgressCost 權重 3.0
• ReplicaNumberCost 權重 1.0

[garyparrot]

在開始優化之前我打算先確認我們的 Backbone Imbalance Scenario 有更好的解，免得自己在追尋不存在的理想解。

第一次測試

https://github.com/garyparrot/astraea/blob/3aba486eb3a55e500e9e4bd0d99a2a695e3c412d/common/src/main/java/org/astraea/common/balancer/algorithms/NetworkBalancer.java#L22-L94

我寫了一個完全針對 NetworkCost 和 Backbone Imbalance 情境（replica = 1）的 Balancer，他的特色是可以在 replica = 1 且 consumer 行為符合實驗預期 的叢集中，在多項式時間裡面把 NetworkIngress 和 NetworkEgress 弄得很平衡（依照 Greedy 的邏輯做，我沒有驗證這個算法的邏輯是不是最佳解）

該 Balancer 可以產生出把網路弄很平衡的解。但他的實作沒有顧慮到 Replica 數量的部分，以查核點來看，這個結果沒有把每個節點的 partition 數量控制在平均值的 ± 30% 裡面，他在我的測試中只做到 ± 38 %。

這個 Balancer 為了把網路弄到完全平衡，搬移了 10000 個 partition 中的 9600 個，算是做了非常大幅度的移動。對比 #1643 (comment) 這個 comment 的圖的搬移，雖然該圖在 ingress 的部分沒有做到 ingress 平衡，但他也只動到 2000 多個 partition，比上述的實驗少搬移了 7600 個 partition。

因為現在都還沒有上 constraint 我們的 GreedyBalancer 就沒辦法走遠(Partition 數字上和 Cost 值上)，合理懷疑他是卡在 local minimum，後面可能要想一下怎麽跳出那個 local minimum。

第二次實驗

突發奇想的方法，簡單來說是做了兩輪 balancing，像 linux pipe 一樣把結果傳遞到下個一個 balancer 做二次優化。

EDIT: 這個技巧叫 hierarchical optimization

我首先執行一次上面的 NetworkGreedyBalancer 產生出一個網路上平衡的 ClusterInfo，然後把這個產生的 ClusterInfo 拿去餵給會顧及 NetworkIngress,NetworkEgress,ReplicaNumber 的 GreedyBalancer，產生出下一個 ClusterInfo。由於第二次優化有顧及到 ReplicaNumber，所以理論上可以改善上面提到的 partition 數量沒有控制在 ± 30% 的問題。由於 replica number 的優化難度沒有說很高，因此我猜 GreedyBalancer 可以在不做太多 ingress/egress tradeoff 的情況下讓 replica number 進步。

最後產生出來的解，以給 Ingress 造成 9 MB/s 的不平衡的情況下，把 partition 數量從 ± 38 % 控制到 ± 28 %

NetworkGreedyBalancer 計劃下的 Partition 數量

NetworkGreedyBalancer + GreedyBalancer 計劃下的 Partition 數量

流量圖

NetworkGreedyBalancer + GreedyBalancer 的流量有稍微不平一點。

結論

存在一個可以過查核點的解，能做得比 #1643 (comment) 這個 comment 的圖更好，後面有機會可以看怎麽樣讓 Balancer 去發掘這種計劃。