[BALANCER] Proposing ResourceBalancer & ResourceUsageHint

[garyparrot]

目前既有的 Balancer 如 GreedyBalancer 或 SingleStepBalancer 沒辦法在給定的 constraint 下找出好的解。主要原因為現在的優化框架對於限制這件事情沒有太大的支援，這導致現行的 Balancer 實作會在不可行的優化方向打轉無法前進。這個 Issue 嘗試提出新的機制 ResourceUsageHint 和 ResourceBalancer 來解決這個問題，目前初步的 POC 測試結果顯示這兩個機制合體可以在 NetworkIngressCost 和 NetworkEgressCost 和修正過的 ReplicaLeaderCost Constranit 下找到比 GreedyBalancer 好更多的解，另外在不套用 constraint 的情況下 POC 版本的 ResourceBalancer 的表現稍微輸 GreedyBalancer，在第二版本的 ResourceBalancer POC 中，無 constraint 的找解結果和 GreedyBalancer 一樣好。

ResourceUsageHint: 提供資源開銷資訊

Constraint 的優化問題中，解空間內的解不一定能夠拿來使用，有時候我們找到一個解，他可能可以把叢集的效能調整得很好，但是要做到那樣的調整會帶來非常大幅度的影響，這可能是使用者不能夠接受的。這個過程可以類比成踩地雷，我們可以有很多格子可以踩(每個格子是一個 Solution)，但踩下去（實際計算這個解的好壞）之後才發現這個格子的代價太高（地雷），並非使用者可以接受。

目前的框架和 Balancer 缺乏能夠感知 Constraint 的機制，我們只有一個 Predicate 單純用來告知這個解有沒有違反規則，Balancer 知道規則違反後其實沒有太大的方向去做改進，最後只能繼續在解空間撞牆瞎矇，這可能導致整個找解的效率和收斂速度降低，對此我們需要一個機制能夠得知這些限制的資訊，以利 Balancer 可以往正確的方向找解（提升找解效率）。

這個框架的設計包含幾個關於目前問題的直覺

• 在目前的 Kafka 叢集端優化問題中，我們的負載是每個 Broker 身上的 Replica。
• 直覺上每個 Broker 每多一個 Replica 就多一個負載。
• Broker 為了維護 Replica，需要付出 x,y,z ... Broker 資源。
• 當 Replica 從 Broker A 轉移到 Broker B 時，原本 Broker A 付出的資源 x,y,z 要轉移到 Broker B 身上。
• 每個 Broker 身上擁有的資源量有限，如網路卡最快 10 Gbps。
• 每個 Broker 身上的資源量通常有一個建議的用量，比如總輸入流量 3 GB/s，六個節點下去平分大家約一個人 500 MB/s
• 我們多半是在乎有沒有 over-utilize (如 10 Gbps 網卡但預期他輸入 30 Gbps 的流量)，而非 under-utilize

對此我們可以說每個 replica 會和一系列的資源開銷關聯，而每個 broker 會有一系列的建議資源使用量，然後我們需要嘗試去找到一個 replica 分配方法能夠去趨近那個資源使用量。當我們如此建模問題的時候，這個問題會變成一種 Number Partition Problem，我們需要有一群集合和一群數字，我們要把數字塞到任一個集合，目標是要讓集合之間滿足某個特性（如大家的流量差不多 500 MB/s，即負載平衡），只是我們的問題比較特殊，並非使用單純的數字，每個 Replica 的資源開銷比較像是一個向量，向量內的元素代表各項不同的資源開銷。

這個負載和限制的關聯方法存在一個問題，他沒辦法提及 RackAwareness 的情境，在 RackAwareness 中我們是要讓 Partition 的 Replica 不要重複出現在某個集合的節點之間，比如 Broker A,B,C 在同一個機架，上述的限制框架沒辦法描述這種限制，因為限制是套用在節點上，而非一群節點上。為了處理這種情境，這邊的資源是定義在整個叢集的 level，而非個別節點2，一個具體的範例如下圖：

上圖有兩個不同的 Partition，其中一個有兩個 Replica，他們要分配給下面的五個節點，其中三個節點是一個機架，另外兩個是另外一個機架。目前還沒有任何負載配放上去，因此 Cluster Resource Usage 沒有條目。

上圖中把第一個 Partition 分配給 broker k0，這個過程中衍生了三個 Cluster Resource Usage，分別是 網路輸入_k0 和 網路輸出_k0 還有 機架感知_topicA_partition0_rackA 這三個項目，這三個分別代表不同的叢集資源使用。旁邊的 Cluster Resource Usage 可以追蹤目前的分配方法的資源開銷。

接下來把有兩個 Replica 的 Partition 的 Leader 放到 k1 節點，這個過程中也衍生另外三個叢集的資源使用，這些資訊也會追蹤在旁邊的 Cluster Resource Usage

接下來把該 Replica 的 Follower 放到 k2 節點，這個時候我們可以提前偵測到一些問題，我們可以看到 機架感知_topicX_parttion0_rackA 的值變成了 2，這個 2 代表著該 topic/partition 在這個 rackA 中放置了兩個 replica，根據機架感知的規則這個是不被允許的，透過這種追蹤方法，我們可以提前得知某些 "資源" 的使用有沒有被違反，這邊的資源並非指物理上看得見的資源，他可以是虛擬的資源(rack awareness check)，這個手法能做到一定的靈活度來同時描述我們的限制和優化目標。

下面條列一些關於這個資源追蹤手法的細部需求：

• ResourceUsage 發生於 Replica 分派到 Broker 的這個過程，Replica 可以因為偏好 BrokerA 所以在分配到 Broker A 時開比較低的資源開銷，而 Broker B 的時候開比較高的資源開銷，或是開不同的資源（比如分派到不同 Rack 會影響不同的資源字串），這個是允許的。
• ResourceUsage 只和 Replica,Broker 兩個屬性有關，不能因為其他因素而開出不同的資源使用量，比如 Replica 不能因為該節點上有一個他喜歡的 Replica 所以開比較低的資源需求
  • 結合律：ru(replica0, broker0) -> ru(replica1, broker1) == ru(replica1, broker1) -> ru(replica0, broker0)
    • 進行分配的順序，不會影響最終得到的 ResourceUsage
• 當從 ResourceUsage 中移除一個 Replica,Broker 的分配關係，則 ResourceUsage 會的等同於扣除當初 Replica,Broker 分配關係帶來的資源開銷，或說會變成跟一開始沒有做這個操作一樣的 ResourceUsage
  • ru(replica0, broker0) -> ru(replica1, broker1) -> undo(ru(replica0, broker0)) == ru(replica1, broker1)
• 可以用 ResourceUsage 來描述 constraint，但是該 constraint 只能是 resource_usage <= constraint_value，比如 RackAwareness 就是 topic_partition_rackA <= 1.0，該比較關係不能是別的方向，我們不能有一個 Constraint 是比如 500 < resource_usage

這個做法和既有的 CostFunction 計算 CostValue 有非常顯著的差異，CostFunction 目前會把整個叢集的狀態壓成一個數字，這個數字只單純反映好壞，我們很難去從輸入的 ClusterInfo/ClusterBean 去得知出來的數字的前因後果，比如 NetworkIngressCost 中，會影響 cost value 的值就 max 和 min 的節點流量，如果我們的調整影響 max/min 之外的數字，我們沒辦法在 cost value 上看到任何數字上的變化。這導致我們很難從 cost value 去推論剛剛的變化對長遠的影響是好是壞。ResourceUsage 則把所有東西都攤開，所以能以比較細的粒度看到資源的使用情況，這個在後面我們 ResourceBalancer 做決策或提早截斷切斷不可能成立的解是有很大的幫助。

程式碼設計上，我們會需要 ClusterCostFunction 和 MoveCostFunction 實作 ResourceUsageHint 界面來描述他能夠支援他提供這些資訊，具體要實作的函數包含：

• 輸出他們針對眼前的 Replica 的資源開銷有何看法，他最終會回傳一個 Map<String, Double> 之類的資訊，描述該 Replica 的擺放會帶來什麼樣的資源開銷。
• 輸出他們覺得叢集內可能會有哪些資源，不管是實體的或虛擬的，比如
  • NetworkIngressCost 可能會輸出
    • 存在 Resource NetworkIngress_Broker0
    • 存在 Resource NetworkIngress_Broker1
    • 存在 Resource NetworkIngress_Broker2
  • RackAwarenessCost 可能會輸出
    • 存在 Resource topicA_partition0_rackA
    • 存在 Resource topicA_partition0_rackB
    • ...
• 輸出眼前的 Replica 在具體資源上的開銷，後面 ResourceBalancer 會用上
• 提供 Comparator 比較 ResourceUsage 的理想程度，後面 ResourceBalancer 會用上
• 提供 Predicate 衡量 ResourceUsage 的分配方法是不是踩到限制的底線，後面 ResourceBalancer 會用上。

ResourceBalancer

ResourceBalancer 本身有融合很多關於 Kafka 節點端優化問題的 heuristic，包含

1. 每個 replica 只需要變更一次，GreedyBalancer 沒有做到這一點，這導致他後面很多優化的嘗試可能都在推翻他前面的搬移，這導致他需要一點時間撞牆撞到更好的解。
2. 重要的 replica 變更先做，重要的 replica 的擺放決策通常大幅度左右搬移的好壞 (80/20法則?)，另外重要的 replica 數量相對於不重要的 replica 會比較少，因此偏好讓數量多的不重要 replica 去配合重要的 replica 的搬移決策，直覺上這樣比較不會卡到 move cost 的 constraint
3. 每個 replica 能夠做的變更其實很有限，比如有個 cluster 有 6 個節點每個 3 folder，則 partition 能移動到的地方大約就18個。
4. 針對上面 18 個移動，我們優先選擇 "有潛力" 的搬移做嘗試
5. 把 18 個搬移全部都嘗試過一次會需要非常大量的嘗試，如果有 10000 個 replica，全部嘗試要跑 18^10000 可能的分佈。針對比較 “重要的" replica 我們會嘗試比較多種可能，而不重要的 replica 則可能只挑唯一一種可能做測試。
6. 這 18 個搬移中可能有一些會踩到 constraint 的底線，這類的搬移會直接從選項中移除，比如前面 rack awareness 的例子，所有關於 rack A 的節點的搬移會從 18 個選項中拋棄，完全不考慮往那裡走。

從圖片來看這個過程大概類似這樣

當我們到達這個搜尋樹的結尾時，我們就得到了一個可行的解，會再跑 ClusterCost 和 MoveCost 檢查，更新目前找到的最佳解等。

比較

下面比較 GreedyBalancer 和 POC 版本的 ResourceBalancer 的搬移效果差異

測試有 Constraint 的情況

使用 NetworkIngressCost 和 NetworkEgressCost 當做 ClusterCost，限制的部分是採用修正後的 ReplicaLeaderCost，限制只能更動 60 個 leader，二者執行時間皆是 180 秒。

GreedyBalancer

在 0.07 附近撞牆

ResourceBalancer (第一版 POC)

找到的最佳解在 0.04 附近

ResourceBalancer (第二版 POC)

找到的最佳解也是在 0.04 附近

測試沒有 Constraint 的情況

使用 NetworkIngressCost 和 NetworkEgressCost 當做 ClusterCost，沒有限制，二者執行時間皆是 180 秒。

GreedyBalancer

他跑出最好的 cost 是 0.012

ResourceBalancer (第一版 POC)

他跑出最好的 cost 是 0.018

ResourceBalancer (第二版 POC)

跑出最好的成績是 0.0118854，類似 GreedyBalancer 的分數

2023/04/25 EDIT: 修正一些 ResourceBalancer POC 的問題，重新測固定情境下的優化表現，現在沒有 Constraint 的分數和 GreedBalancer 一樣高。

[chia7712]

@garyparrot 感謝提供分析和建議，整體來說我覺得都蠻有道理，以下就幾個點展開一下討論：

1. 更細緻的資源描述這個想法很棒，不過我們要如何定義介面達到”物件“和”純數“之間的轉換？議題中有描述了網路和rack的配置對應的資源，如果要新增更多不同的資源描述、甚至是開放給使用者動態新增的話，這部分要如何處理？
2. Map<String, Double>中的字串感覺是一個通用的描述字符，這跟後續balancer可以採取的動作有關嗎？如果有關的話是怎樣互動？根據不同字符有不同的的動作？
3. 議題中有一句話針對上面 18 個移動，我們優先選擇 "有潛力" 的搬移做嘗試，這個優化蠻有道理的，甚至可以直接做在目前的 balancer 上面，因為很多 move 的限制其實是因為“單方面”的限制影響了全局，例如在避免下游大量掉線而限制 moved replicas數量時，就應該避免把這寶貴的限制留給沒啥影響力的replica。另外我覺得值得先嘗試看看的原因是改動幅度應該不大，我們可以讓ClusterCost可以回傳一個“潛力股”的陣列，用來提示可以嘗試看看更動哪些 replica 來獲得更好的分數

@qoo332001 也麻煩看一下喔

[garyparrot]

不過我們要如何定義介面達到”物件“和”純數“之間的轉換？議題中有描述了網路和rack的配置對應的資源，如果要新增更多不同的資源描述、甚至是開放給使用者動態新增的話，這部分要如何處理？

優化所使用的 CostFunction 要實作 ResourceUsageHint 來讓這些 CostFunction 能夠支援給定特定的 feedback，這些 feedback 能夠被 ResourceBalancer 看懂和使用，成為後續搜尋解的考量。btw ResourceUsageHint 的實作有很多要注意的事情（內文），如果沒寫好，會發生找解上的困難或往反方向找解。

Map<String, Double>中的字串感覺是一個通用的描述字符，這跟後續balancer可以採取的動作有關嗎？如果有關的話是怎樣互動？根據不同字符有不同的的動作？

ResourceUsageHint 是提供 Map<String,Double> 的源頭，介面設計上會有另外一個函數，Balancer 可以拎著目前的 Cluster Resource Usage (另外一個 Map<String,Double>) 給他，問他對目前的叢集資源使用的感想，該函數內部會假設每個資源都有一個 "理想的使用量"，比如 RackAwareness 可能是 0 或 1，流量的話可能是整體流量在節點之間的平均，ResourceUsageHint 會去讀那個 Map 裡面他負責管的 Resource String 對應的 Double 值，如果 Double 接近理想值則他會給出一個好的分數，反之就壞的分數，這個分數會作為 Balancer 搜尋上的參考，理論上一個解的所有 Resource 的分數都很好的時候，該解的 ClusterCost 或 MoveCost 的 score/overflow 也會是好的 (near 0/ no overflow)。

議題中有一句話針對上面 18 個移動，我們優先選擇 "有潛力" 的搬移做嘗試，這個優化蠻有道理的，甚至可以直接做在目前的 balancer 上面，因為很多 move 的限制其實是因為“單方面”的限制影響了全局，例如在避免下游大量掉線而限制 moved replicas數量時，就應該避免把這寶貴的限制留給沒啥影響力的replica。另外我覺得值得先嘗試看看的原因是改動幅度應該不大，我們可以讓ClusterCost可以回傳一個“潛力股”的陣列，用來提示可以嘗試看看更動哪些 replica 來獲得更好的分數

我後面會先把 ResourceUsageHint 整合到專案裡面，到時候再看效果如何。

[garyparrot]

這段時間有修正 ResourceBalancer 內部的實作，現在在在 BackboneImbalanceScenario 測試情境中， ResourceBalancer 在沒有套用 constraint 的情況也能找到和 GreedyBalancer 一樣好的解，詳細圖看更新後的內文。

[chia7712]

ResourceUsageHint 會去讀那個 Map 裡面他負責管的 Resource String 對應的 Double 值，如果 Double 接近理想值則他會給出一個好的分數，反之就壞的分數，這個分數會作為 Balancer 搜尋上的參考，理論上一個解的所有 Resource 的分數都很好的時候，該解的 ClusterCost 或 MoveCost 的 score/overflow 也會是好的 (near 0/ no overflow)。

請問這段能給個範例嗎？或是把PR分享一下

[garyparrot]

請問這段能給個範例嗎？或是把PR分享一下

#1674 有我目前的進度

[garyparrot]

議題中有一句話針對上面 18 個移動，我們優先選擇 "有潛力" 的搬移做嘗試，這個優化蠻有道理的，甚至可以直接做在目前的 balancer 上面

我剛剛思考了一下這個機制很難做到 GreedyBalancer 或說他的 ShuffleTweaker 裡面。因為 ShuffleTweaker 一次面對的是一整群 replicas 做移動，所以他一次面對的可能是 18 * 10000 個移動，而非 18 個移動，然後他要做 n 次連續的移動的話會是 n^(180000) 種可能，我們沒辦法衡量如此大量的移動。如果他真的套用了這個做法，最後 GreedyBalancer 得到的解會跟 ResourceBalancer 嘗試的第一個解一樣。

另外我覺得值得先嘗試看看的原因是改動幅度應該不大

除了這個限制之外，GreedyBalancer 設計上缺乏 ResourceBalancer 的後退機制，所以他在解空間的搜尋其實不廣，嘗試修正這個問題將會使他不再是 Greedy Balancer，最後恐怕會得到另外一種 Balancer 實作。如果不修正的直接套用的話，最後實作出來的 GreedyBalancer 基本上和前面的版本沒有太大的差異（可能修正後的版本在第一個 iteration 就到達他原本 50sec 能走到的那種 local minimum 解，然後就困在裡面）

我們可以讓ClusterCost可以回傳一個“潛力股”的陣列，用來提示可以嘗試看看更動哪些 replica 來獲得更好的分數

這個設計的時間複雜度會不能被接受，ResourceBalancer & ResourceUsageHint 的設計上有一個重點是要避免 evaluate 所有的 replica，在 replica 數目高的叢集中這個會很耗費時間。

所以我的主張是不要把這個設計貼到 GreedyBalancer 上面，最後可能改了一堆東西然後得到和 ResourceBalancer 一樣的能力，不然就是只改了少許的模組，最後計算上更花時間，但演算法設計上也找不到好的解。還是說學長你有看到什麼設計上的改進，能夠從 "算法邏輯" 上讓 GreedyBalancer 有機會觸擊更好的解，同時把這個過程控制在合理的執行時間內。

[chia7712]

還是說學長你有看到什麼設計上的改進，能夠從 "算法邏輯" 上讓 GreedyBalancer 有機會觸擊更好的解，同時把這個過程控制在合理的執行時間內。

這個題目現在是“根據 cost function 給的提示來選擇要優先調整哪幾個 partition/replica"，所以或許可以將提示交給ShuffleTweaker隨機處理優先權較高的 partition/replica，簡單來說，我們將“隨機過程中的選項抽出來成為某種提示，讓 cost function可以稍微協助一下隨機的過程，讓隨機的過程具備某種程度的感知能力“

[garyparrot]

我的改法： ShuffleTweaker 挑 Topic/Partition/Replica 的邏輯不動，一樣是 Random Select，但移動他的時候會挑 18 種移動中 ResourceUsageHint 覺得最理想的一個動作去執行。

GreedyBalancer (ResourceUsageHint ver), 有 Constraint

一樣優化 Network In/Out, 限制 60 leader 受影響, 180 秒執行

最終 cost 卡在 0.068 那邊，這個結果有符合我前面的想法，GreedyBalancer 不擅長後退。

GreedyBalancer (ResourceUsageHint ver), 無 Constraint

一樣優化 Network In/Out, 沒有限制, 180 秒執行

最終 Cost 在 0.011575024015158164，結果和 ResourceBalancer 的優化結果差不多。

[garyparrot]

我把 topic/partition 的選擇從原本的 random 改成依照重要程度(網路流量大小)來選擇，高流量的 partition 有較高機率被改變

GreedyBalancer (ResourceUsageHint ver 2), 有 Constraint

min cost = 0.057989435443133674

GreedyBalancer (ResourceUsageHint ver 2), 無 Constraint

min cost = 0.016111394633264428

[chia7712]

最終 cost 卡在 0.068 那邊，這個結果有符合我前面的想法，GreedyBalancer 不擅長後退。

“後退“這個字很有意思，整個議題描述有兩個很重要的概念：

1. 如何讓 balancer "退後"以跳出區域解（此議題提出的方式是給足夠的線索）
2. 如何讓 balancer 一開始就走向正確的路 (此議題提到的是選出有潛力的replica)

然後有幾個延伸的問題：

1. 哪一個能帶來“最明顯”的效果？究竟是一開始就走正確的路？還是說可以多走錯幾次但要能倒退？
2. 這兩個改善是否能有最小幅度的修改？例如"退後"的觸發能否用"走幾步都卡卡就退回起點重新走”這種方式來取代？

@garyparrot 如今天討論的結果，大幅度調整程式碼永遠是一個方法，但我會希望你能試著分析一下解法，然後看能否在最小的修改下達到最佳的效果，這會是一個很重要的技能，我們一起練習看看

[garyparrot]

如何讓 balancer "退後"以跳出區域解（此議題提出的方式是給足夠的線索）

這個議題不是透過足夠的線索來後退，他把整個優化問題建立成一顆樹的 traversal，而非現在的 state graph 之上的 hill climbing，這使他可以往不同的區域去做搜尋且保證每次走的都是不同的區域。

如何讓 balancer 一開始就走向正確的路 (此議題提到的是選出有潛力的replica)

是依照重要程度排序 & 挑有潛力的 movement 移動。

哪一個能帶來“最明顯”的效果？究竟是一開始就走正確的路？還是說可以多走錯幾次但要能倒退？

這兩個在解不同的問題。

• 走正確的路是避免浪費時間搜尋沒有意義的地方
• 倒退是要有辦法跳出 local minimum 和提升搜尋上的廣度

我覺得這兩個問題，一個沒有解，結果都不會好，不會有任何 "明顯“ 的效果顯現

這兩個改善是否能有最小幅度的修改？例如"退後"的觸發能否用"走幾步都卡卡就退回起點重新走”這種方式來取代？

退回起點重新走有很高的機率最後會走到一樣的地方，因為每個 state 都偏好走一樣的路徑，然後到達跟剛剛一樣的 local minimum，透過一些手法可能可以稍微減緩這個問題，但那個要付出複雜度和成效未知。主要還是解的多樣性的問題，如果重新走的話，要如何確保能走到不一樣的地方。ResourceBalancer 透過給訪問的狀態強加一個方向性來保證這件事情，但 GreedyBalancer 沒有這種機制。

@garyparrot 如今天討論的結果，大幅度調整程式碼永遠是一個方法，但我會希望你能試著分析一下解法，然後看能否在最小的修改下達到最佳的效果，這會是一個很重要的技能，我們一起練習看看

在 State Graph 上解 "走正確的路" 和 "後退" 這兩個機制在既有的解決方法中都很多(Simulated Annleaning & others)，如果你想要我嘗試這些方法的話，我可以試試看，但我先前的直覺是能帶來的效果是一個非常大的問號。

[chia7712]

這個議題不是透過足夠的線索來後退，他把整個優化問題建立成一顆樹的 traversal，而非現在的 state graph 之上的 hill climbing，這使他可以往不同的區域去做搜尋且保證每次走的都是不同的區域。

這部分應該是我沒看懂，不過這樣是暗示說這個手法可以不用 resource hint嗎？

[chia7712]

走正確的路是避免浪費時間搜尋沒有意義的地方
倒退是要有辦法跳出 local minimum 和提升搜尋上的廣度

欸細節是這樣沒錯，但我想表達的是新方法（或是你心裡的打算）哪一個最能幫到最後的結果？也就是在一定限制下找到最好的結果

[chia7712]

在 State Graph 上解 "走正確的路" 和 "後退" 這兩個機制在既有的解決方法中都很多(Simulated Annleaning & others)，如果你想要我嘗試這些方法的話，我可以試試看，但我先前的直覺是能帶來的效果是一個非常大的問號。

我很喜歡你的直覺。但在工程面上，遇到一個新的需求就打掉重練是一個「最後手段」，所以我才會有前面試著去分析說你帶來的新方法中「有哪些進步」、「這些進步哪個重要」、「重要的進步能否在最小範圍下整合進現在的方法」。如果透過分析討論後確認各種進步的手法都難以改善現有的程式碼，那我們自然可以開始發展一個新的作法。另外我是希望是由你來分析給我看，這樣對你個人才好（一種訓練）

如果我們總是朝打掉重練的方向前進，那很有可能你現在這個新方法在一兩個月後又要打掉了，因為使用者需求來得很快。

最後要記得 greedy 當時也是這樣的思維，基於你當時的手法在最小的改動範圍下帶來一個程度的進步。

[garyparrot]

• 廣度: GreedyBalancer 的移動方向很狹隘
• 方向性: GreedyBalancer 可以隨意移動，每個移動前往的解差異性很大。Resource Balancer 的解空間有整理過，理論上越先進行的移動越理想，理想的狀況也能比較保留下去
• 後退: GreedyBalancer 不支援後退

我研究看看怎麽改能夠保留 Greedy 的靈魂同時兼容兼容這些優勢，然後修改很少，又不會和 ResourceBalancer 長得一樣，你有什麼想法也可以提出來。

[chia7712]

我研究看看怎麽改能夠保留 Greedy 的靈魂同時兼容兼容這些優勢，然後修改很少，又不會和 ResourceBalancer 長得一樣，你有什麼想法也可以提出來。

我想再確認一下，你那隻PR中有多少部分是只屬於新的演算法？

我現在的認知是 RB 需要 resource hint 等機制的幫助才能成行，如果 RB 可以類似 SB or GB 一樣，在一樣的基礎架構下可以完成的話，那就屬於我說在少量改動下完成的改善

所以重點不是要保留 greedy的靈魂！

[garyparrot]

我想再確認一下，你那隻PR中有多少部分是只屬於新的演算法？

• ResourceUsageHint 框架的定義 150 行左右
• 讓一個 CostFunction 支持 ResourceUsageHint 大約 60 行左右，大部分的邏輯可以透過 ClusterCost 原本的實作重複利用
• ResourceBalancer 本身 450 行。

PR 裡面剩下 2300 行是我測試用的程式碼。

我現在的認知是 RB 需要 resource hint 等機制的幫助才能成行，如果 RB 可以類似 SB or GB 一樣，在一樣的基礎架構下可以完成的話，那就屬於我說在少量改動下完成的改善

目前 RB 需要 ResourceUsageHint 才能動作。

目前的基礎架構: ClusterCost#value 的數字只能夠反映 "整個叢集" 的負載分數， RB 提出的方法沒辦法單靠這個分數運作：

• RB 要知道 Replica 的重要程度：這個重要程度是 Replica 等級的資訊，但 ClusterCost#value 是叢集等級的資訊，沒辦法從這個整體叢集的分數去逆推單獨 Replica 的資源使用量。
• RB 要知道資源的理想程度：這個是 Resource 等級的資訊，目前既有的 Cost (PartitionCost, BrokerCost, ClusterCost) 都沒辦法表達這種靈活的資訊。比如 RackAwareness 中的資訊是以 Rack (一集合的節點) 為單位做規劃，沒辦法用 Partitoin/Broker/Cluster 描述。另外這些 Cost 的函數簽名也不合，他們是透過 XXXCost HasXXXCost#xxxCost(ClusterInfo, ClusterBean) 取得結果，這邊偏好的簽名是 double ResourceCapacity#idealness(Resource)。

我感覺現在的 XxxCost 的運作模型隱藏太多細節，所有暴露出來的資訊都是 summary (比如把整個叢集的狀況壓成一個數字，然後再把多個不同面向的指標以 weight 壓成另外一個數字?)，summary 很適合用來當做指標幫助理解大量資訊的趨勢，但這個數字太大略 Balancer 很難做細部的決策，這好比眼前有 10000 可以轉向 18 個方向的桿子，要怎麽知道轉哪個桿子哪個方向可以讓那個 f(a0,a1,a .... 那 10000 個輸入) 的值往下降，btw f 是使用者可以調整的，所以 f 對我們未知。

[chia7712]

summary 很適合用來當做指標幫助理解大量資訊的趨勢，但這個數字太大略 Balancer 很難做細部的決策，這好比眼前有 10000 可以轉向 18 個方向的桿子，要怎麽知道轉哪個桿子哪個方向可以讓那個 f(a0,a1,a .... 那 10000 個輸入) 的值往下降，btw f 是使用者可以調整的，所以 f 對我們未知。

這段我很同意，也如同我們會議上討論過的內容，我們需要一個新的介面來適當的暴露細節幫助Balancer做決定。我們先聚焦在這一塊，可否試著把你說的ResourceUsageHint 框架的定義 150 行左右這塊拉出來成一個PR，並且選擇一個 cost 來實作 例如 NetworkIngressCost.java

這樣可行嗎？

[garyparrot]

這段我很同意，也如同我們會議上討論過的內容，我們需要一個新的介面來適當的暴露細節幫助Balancer做決定。我們先聚焦在這一塊，可否試著把你說的ResourceUsageHint 框架的定義 150 行左右這塊拉出來成一個PR，並且選擇一個 cost 來實作 例如
這樣可行嗎？

ok，我接下來會往這個方向執行

[garyparrot]

#1685 有對 POC 版本的框架做一些變動，現在非 Constraint 的情況下可以找到非常接近 cost 0 的解。

ResourceBalancer (POC3) Network Cost, No Constraint, 180s

min cost 7.859093057492593E-5

Resource Balancer (POC3) Network Cost, Leader 60, 180s

有套用限制的情況下的表現和先前差不多，但圖的波型有比之前的實驗更寛一點，這是因為 ResourceUsage 的設計從 mutable 變成 immutable 帶來的額外效能開銷所致。現在的 ResourceUsage 結合速度有稍微慢一點（大約 10 ~ 20%）

min cost = 0.0411147

[chia7712]

cost 0 的解。

請問一下這個概念是什麼意思？以流量當作成本的話是指每個節點的量都幾乎一樣嗎？

[garyparrot]

以流量當作成本的話是指每個節點的量都幾乎一樣嗎？

對，接近 0 基本上代表所有的優化目標都做得很好才會拿到這個分數，比如下面是 2.3423441224366525E-4 的例子

Initial Cost: WeightCompositeClusterCost[
{"NetworkIngressCost" cost 0.07420329522755623 weight 3.0 description {335.40 MB/SECOND, 282.84 MB/SECOND, 267.50 MB/SECOND, 273.01 MB/SECOND, 288.47 MB/SECOND, 482.49 MB/SECOND} }, 
{"NetworkEgressCost" cost 0.07873122891973776 weight 3.0 description {506.93 MB/SECOND, 439.45 MB/SECOND, 418.90 MB/SECOND, 430.92 MB/SECOND, 454.00 MB/SECOND, 647.00 MB/SECOND} }] 
= 0.07646726207364699

Final Cost: WeightCompositeClusterCost[
{"NetworkIngressCost" cost 8.213331078911895E-5 weight 3.0 description {321.66 MB/SECOND, 321.66 MB/SECOND, 321.66 MB/SECOND, 321.66 MB/SECOND, 321.42 MB/SECOND, 321.66 MB/SECOND} }, 
{"NetworkEgressCost" cost 3.8633551369821154E-4 weight 3.0 description {482.83 MB/SECOND, 482.82 MB/SECOND, 482.35 MB/SECOND, 482.92 MB/SECOND, 483.46 MB/SECOND, 482.82 MB/SECOND} }] 
= 2.3423441224366525E-4

[garyparrot]

我嘗試了其他 Balancer 的設計，以 Network Ingress/Egress 為優化目標、限制只能更動 60 Leader、180秒的情境，以下是結果：

GreedyRestartBalancer

這個是 GreedyBalancer 但是有 Restart 的能力，在他覺得找不到更好的進步的時候從起點重開。

每次重開基本上也沒辦法到達更好的解，因為隨機的前進的特性，如果有高機率會卡在一個很糟糕的 local minimum，不論怎麽 restart 結局大致上也差不多。

min cost = 0.0729391

GreedyResourceBalancer

這個是 Greedy 版本的 ResourceBalancer，他會隨機挑選一個 Replica，把它移動到所有可能的目的地中最好的一個(透過 idealness 比較)。這個版本和原本的 ResourceBalancer 的差異在他不管 importance，然後已經被動過的 replica 可以再被動一次。由於沒有用到 importance 機制，這個版本的 ResourceUsageHint 只有三個函數。

另外由於隨機動有可能把叢集調整得更糟糕，當遇到沒有更好的動作時，會進行 Restart 從起點重新搜尋。

由於沒有 Importance 機制，每個 replica 被更動的機率相同且可以重複動，在 BackboneImbalanceScenario 中真正重要的 replicas 大約在整體的比率大約是 50/10000，要動到他們的機率不高，且即使動到了也要動得好，想要做到動得好這件事情需要其他 9999/10000 個 replicas 的合作，要在有 Restart 機制的情況下，要求 replicas 一起合作，這個情況發生的可能性很低。（合作機制，這點在 ResourceBalancer 的 Search Tree 中可以很情境的辦得到，Search Tree 強加的順序始得不重要的 replicas 要去配合重要的 replicas 的移動）。

min cost = 0.0683978

圖中掉下去的 cost 應該是隨機塞到的。

GreedyResourceBalancer2

這個是上者的改良版本，他嘗試在每次 Restart 之間共享一些訊息，這個改進是啟發自 PSO 和 ACO 的演算法。

這個方法的目標是在不使用 importance 機制的情況下，從 idealness 去逆推出每個 replica 的 importance。他逆推的方法是在每次的搬移之後，衡量這個搬移帶來的影響和搬移前差距多大，如果是好的差距，則該 partition 的 weight 會上升，越高的 weight 意味著被挑選到的機率更高。

上圖中可以看到這個改進帶來反效果。
這個改進的問題在於我們的情境中重要的 replica 的數量很少，目前看到的情況是多大多都是抽到不重要的 replica 來表現(畢竟他們數量多)，然後 weight 上升的都是這些不重要的 replica，最後優化多集中在不重要的地方。

min cost = 0.0733456

GreedyResourceBalancer3

上一個版本的問題是每次看的眼界太狹小導致 weight 的更新不準確，這個版本在每次移動的時候把眼界放寬，一次看到所有 180000 種可能的搬移，然後挑最好的那個搬移做，因為這個機制用不上隨機所以連帶 weight 的機制也拿掉了。結果意外的好

min cost = 0.041660666097902546

這個 cost 的值和 ResourceBalancer 找到的解差不多（其實小輸 0.0005）。

這個做法的一個問題是執行的效率，一次檢查 180000 種可能需要一段計算時間，肉眼估計提出一次解的速度要比 ResourceBalancer 慢 1 倍，另外 ResourceBalancer 是一次前往那個 local minimum 的邊界，而 GreedyResourceBalancer3 和 GreedyBalancer 一樣要慢慢撞到 local minimum 的邊界。另外一個他沒有做到但 ResourceBalancer 有做到的解的多樣性，ResourceBalancer 的設計是直接在多種 local minimum 的邊界上做掃描，這個版本的做法會卡在同一個 local minimum 內走不出來，在比較複雜的情境中 GreedyResourceBalancer3 可能會不到 ResourceBalancer 找得到的解，由於我手上沒有更複雜的情境，所以剛剛這些是我的直覺，非實際測試出來的結果。

因為限制找解的效果好像不錯，所以順手測試看看沒有限制的情況，結果比較遜色一點：

min cost = 0.013065321112508865

這個結果比 ResourceBalancer 差很多，然後比 GreedyBalancer 差一點。從圖上來看應該是還沒到達收斂，他的速度過慢導致 180 秒也不夠展現他的實力

[chia7712]

@garyparrot 我覺得這幾個嘗試都蠻有趣的，而且看得出來有收斂問題，期待再看到更多的嘗試

另外這些測試過程是否能方便讓第三方重現？或許跟你之前貢獻的測試工具有關？

[garyparrot]

@garyparrot 我覺得這幾個嘗試都蠻有趣的，而且看得出來有收斂問題，期待再看到更多的嘗試

你有嘗試的建議嗎，當初想 ResourceBalancer 花了 2 個禮拜的時間，我覺得我短時間內想不到更好的解法。而且 ResourceBalancer 也修好了我想得到 GreedyBalancer 存在的問題，我不太確定還有哪邊可以進步。更多的嘗試後我變得確定 ResourceUsageHint 的設計需要那 5 個函數，如果要簡化的話可能就讓 5 個函數都變成 default，實作者想提供再提供，如果他們希望找解更順利的話。

另外這些測試過程是否能方便讓第三方重現？或許跟你之前貢獻的測試工具有關？

看第三方想重現什麼，可能會需要不同的步驟：

• 如果只是想重現找解順利，那可以用 CostProfiling，給定 Balancer 參數和 ClusterInfo & ClusterBean 序列化檔案即可，這個應該會在 [BALANCER] Enable BalancerBenchmark to Astraea app #1693 完成。目前我的實驗的序列化是自己做的，因為有這個需求的時候專案沒有對應的工具，現在有了我可能測試看看能不能用。
• 如果是想重現負載優化的效果，那會需要一個真實的叢集，然後套用解到他身上。主要是因為 CostProfiling 只能告訴我們找解順不順，沒辦法驗證解在真實叢集的效果（有機會 Cost Function 的實作沒辦法順利描述實際的資源開銷，或輸入情境過多雜訊導致誤判）。為了重現負載優化效果，第三方要提供 ClusterBean，然後根據目前叢集的 ClusterInfo 和給定的 ClusterBean 去找出一個解，然後套用那個解到叢集，透過 Grafana 或其他監控工具驗證優化效果如何。這個過程其實不太 “方便"

如果第三方可以確定 CostFunction 的實作是正確的，不會有誤判的情況，那其實用 CostProfiling 就足以重現驗證負載優化結果這件事情，但驗證 CostFunction 實作正確很困難，之前 NetworkCost 就有出現預估不準的情況 #1641

[chia7712]

我的實驗的序列化

這部分可以嘗試用 protobuf 嗎？

如果是想重現負載優化的效果，那會需要一個真實的叢集，然後套用解到他身上

請問一下上面討論中貼出來的圖是在真實叢集上測試，抑或是用CostProfiling的結果？

你有嘗試的建議嗎，當初想 ResourceBalancer 花了 2 個禮拜的時間，我覺得我短時間內想不到更好的解法。而且 ResourceBalancer 也修好了我想得到 GreedyBalancer 存在的問題，我不太確定還有哪邊可以進步。更多的嘗試後我變得確定 ResourceUsageHint 的設計需要那 5 個函數，如果要簡化的話可能就讓 5 個函數都變成 default，實作者想提供再提供，如果他們希望找解更順利的話。

在討論更進一步想法之前，我想先確定“實驗”本身的可複製性，原因是隨著方法越來越複雜，除了程式碼和理論的審查外，我們也需要針對實驗做審查，以免我們在錯誤的結果上做討論

[garyparrot]

這部分可以嘗試用 protobuf 嗎？

這邊有一個 #1704 Bug，所以沒辦法從序列化後的 ClusterInfo 取得 Broker 資訊，Balancer 運行時會需要知道每個節點的 Data Folder 才能進行搬移決策。 ClusterBean 的部分，我剛剛看了一下專案好像沒有整個 ClusterBean 的序列化工具，但有 BeanObject 的序列化。

請問一下上面討論中貼出來的圖是在真實叢集上測試，抑或是用CostProfiling的結果？

都是 CostProfiling 的圖，不是從真實叢集測出來的。真實叢集的測試一次大約要 15 分鐘到 30 分鐘，我沒辦法以這個速度做測試，另外我很確定目前的情境中 NetworkCost 的運作是正確的，所以可以直接拿 CostProfiling 的結果對照到真實的情況。

[chia7712]

都是 CostProfiling 的圖，不是從真實叢集測出來的。真實叢集的測試一次大約要 15 分鐘到 30 分鐘，我沒辦法以這個速度做測試，另外我很確定目前的情境中 NetworkCost 的運作是正確的，所以可以直接拿 CostProfiling 的結果對照到真實的情況

ok，那我們先完成實驗的可複製性 #1693 後再回頭討論演算法的部分

[garyparrot]

那我們先完成實驗的可複製性

這邊可複製性也有兩種層面的複製：

• 透過 ClusterInfo 和 ClusterBean 的序列化檔案複製實驗結果，這個是第三方直接使用我們的檔案來跑出結果。這個情況是建立在第三方信任我們的 ClusterInfo 和 ClusterBean 的情況，如果對方比較謹慎的話可能會懷疑 ClusterInfo 和 ClusterBean 的檔案內容的叢集狀態，和我們對外聲稱的情境不一樣（對外聲稱 10000 replicas 但裡面其實只有 10 replicas, 對外聲稱 beans 裡面是高流量的情境，但其實裡面 metrics 的數字都是捏造的，非源自真的叢集）。
• 第三方透過 "真實叢集" 複製。這個版本是我們提供他們產生對情境的程式碼，程式碼內容包含把 Brokers/Topics 建立好，Producer/Consumer 啟動，然後對目標叢集做一次真的情境，然後在這個情況下去錄製 ClusterInfo 和 ClusterBean 的序列化檔案，因為這些檔案是第三方自己製造的，他可以看 Grafana Dashboard 就知道裡面錄製的情境和他心裡面所設想的情境一樣。

之前有討論過要不要把這些情境(Scenario) 的程式碼推入專案，但後來討論是沒有要推入(#1476 (comment) )，其實那些 Scenario 也只有做到建立 Topic 的部分，Producer/Consumer/Broker 的部分是用我自己獨自的腳本去完成。要在專案內做到這種等級的環境重現可能會需要更高級的工具來實踐。我覺得這個實驗的可複製性如果要做到非常有說服力的話可能會有點複雜。

[garyparrot]

ResourceUsageHint 的部分，在 Helix 的 WAGED Rebalancer https://github.com/apache/helix/wiki/Weight-aware-Globally-even-distribute-Rebalancer 有類似的設計。

先前實驗的時候有發現 ResourceBalancer 設計上的問題，Local Search 問題中有一個情況是優化函數本身很平，因此沒有進步的方向感，ResourceBalancer 將負載排序且依照順序下去挑選，可能會遭遇這種很平的現象，在優化目標少的時候這個問題可能還好，但當目標變多的時候會變成一個問題。

[chia7712]

ResourceUsageHint 的部分，在 Helix 的 Wage Balancer https://github.com/apache/helix/wiki/Weight-aware-Globally-even-distribute-Rebalancer 有類似的設計。

這個看起來不錯，很值得參考，感謝分享