[BALANCER] 增進負載優化框架對 Constrainted Optimization 的支持

[garyparrot]

Context: https://github.com/skiptests/astraea/pull/1499#issuecomment-1434031859

目前的 Balancer 優化框架對優化問題所附加的 Constraints 沒有感覺，這可能會造成 Balancer 演算法找解上的困難。

[chia7712]

@g1geordie 有機會的話可以了解一下這個題目，目前我們的balancer 能應用的情境不夠多元，還是需要大量的人工介入，這個題目會是一個不錯的開端

[g1geordie]

各位大大好 想跟大家確認一下目前方向對不對

會開一個functional class

ClusterConstraint{
  boolean accept(ClusterInfo newClusterInfo)
  static ClusterConstraint of(ClusterInfo originClusterInfo ,Map<String,String> config){
     return info ->{
       排除node 
       unaccept offline 等等
    }
  }
}

並在AlgorithmConfig 把 clusterConstraint return 改成 ClusterConstraint

ClusterConstraint clusterConstraint();

在BalancerHandler 加入判斷條件

[chia7712]

會開一個functional class

我們先用這個介面想像一下，如果現在的 topicFilter要用這個介面來重新實作的話，可以怎麼完成？

[g1geordie]

了解。 這樣的話就會需要判斷 物件String 和 物件 ClusterInfo 的constraint 大概會變成這樣.

Constraint<T>{
  boolean accept(T t)
  static Constraint<ClusterInfo> ofClusterConfig(ClusterInfo originClusterInfo ,Map<String,String> config){
     return info ->{
       排除node 
       unaccept offline 等等
    }
  }
}

Constraint<String> topicFilter();

[chia7712]

@g1geordie constraint這個機制希望之後可以延伸到各種用途，也就是能提供足夠的資訊讓 balancer 知道說哪些“資源”或“目標”不可用，別傻傻的花費一堆時間產生用不到的 plan。目前已知會用來當作constraint的條件有兩個：

1. topics，這是來自於搬移成本太高，使用者會希望排除用不到或冷門的topic
2. broker，這可以用在當某些節點已經不穩或是準備下線時，balancer就不要再把partitions往該節點身上放。另一種則是希望balancer可以將該節點身上的partitions通通移到別的地方放

所以我前面想討論的事情: constraint這個介面該怎麼訂，才可以滿足上面說的應用？以 topic 為例，假如使用者給了一堆字串 (topic names)，constraint該回傳什麼才能讓balancer方便知道有哪些目標或資源不可用？一個最簡單的做法當然是回傳boolean，讓balancer拿著plan來問，撞到限制就回傳false。但這種做法會有明顯的效能/優化議題，因為balancer始終不知道為何該plan被拒絕，可能接下來連續1000000次都用到被禁止的資源或目標，這樣就會很沒效率

[garyparrot]

關於 Constrained Optimization 的部分我可以分享一些 input，我看到的概念大多來自 Jing Liang 等人 2022 年發表的文章 "A Survey on Evolutionary Constrained Multi-Objective Optimization"，雖然文章是在講 Evolutionary Algorithm，和我們目前採用的演算法不一樣，不過就 Constrained 的部分大概跟我們遇到的部分一樣，應該是可以借用類似的解法。

文內提到這種 Constrained 和 Unconstrained 的優化問題差異在解空間的長相， Unconstrained 的版本整個空間的合法解都可以使用，可以任意採用，類似踩地雷但是沒有一個格子是地雷。但 Constrained 的版本中，非整個解空間的 solution 都可用，用文字形容的話他的解空間是坑坑巴巴的。整個優化的過程一般的踩地雷（但地雷不是平均地灑在空間，地雷比較常以一坨一坨的形式出現，擠在解空間的某個地方），有時候要我們自己踏過去才會發現這個解不可用（或是算法夠聰明的話可能會知道那個地方有點危險儘量避免）。

文中還有提到一些過去的論文如何解這個有限制版本的，這些部分應該都是 Balancer 的實作細節，可能和這隻 Issue 提到的演算法框架的修改無關，不過因為現在專案沒有一個 Balancer 有做 Constraint 的支持，所以可能現在做起來會有點模糊，這些手法是其他人 "用 constraint 的方法"，或許可以當做實作框架時的參考：

• 有一些人的做法是 Penalty Method：類似考試倒扣的概念，如果有限制被違反，則 cost score 分數會變差。具體如何變差，有些論文的做法是採用固定的權重去扣，但這個做法在 Evolutionary Algorithm 中不太適合，因為很難找到一個好的值能夠在每個優化的 iteration 中適用，所以有一些論文是採用比較 adaptive 的做法，隨著 iteration 去改動這個扣分的權重。這個做法基本上是把 Optimization Goal 和 Constraint 以分數的方式合體，下面一個做法是把他們抽離
• 另外一種做法是分離 Optimization Goal 和 Constraint 的做法：如果今天有兩個來自解空間的 Soltuion A & B，他的進化演算法在選解的時候會：
  • 如果 A 和 B 都是 feasible soltuion(沒有違反 constraint 的解)，則看 A B 誰分數高，選分數高的進入下一個時代
  • 如果 A 是 feasible solution 而 B 是 infeasible solution，選 A。
  • 如果 A 和 B 都是 infeasible solution，則 violation degree 低的那個 solution 會進入下一個世代。
    • 這邊 violation degree 是一種從 constraint 算出來的分數，這個分數越高代表他違反的限制越多。

論文裡面還有其他更複雜的手法，但最直覺的例子應該是這兩個

[g1geordie]

@garyparrot @chia7712 感謝大家的建議 我們所要做的是告訴balance 現在有什麼限制, balancer 再去實作對吧 這樣直接列舉出許多不同的constraint 是不是會比較容易懂

變成 balancer 需要去使用 TopicFilterConstraint, NodeFilterConstraint, NodePermitConstraint

  List<Constraint> constraint();

  ---
  interface Constraint{

  }

  /**
   * topic 是否參與變異
   */
  interface TopicFilterConstraint extends Constraint{
    boolean accept(String topic);
  }

  /**
   * broker 是否參與變異
   */
  interface NodeFilterConstraint extends Constraint{
    boolean accept(String bkId);
  }

  /**
   * 新的cluster 準不準許使用 broker 資源
   */
  interface NodePermitConstraint extends Constraint{
    boolean accept(String bkId);
  }

[chia7712]

@g1geordie 條列是一個方式，但這個條列的顆粒度要夠細，細到可以方便我們組合出更多規則，否則就會陷入每加一個動作然後所有演算法都要跟著動的窘境。例如你現在列的方法中就不容易描述”禁止將 topic_a 移動到 broker_a"。

整個 cost function 體系中目前只有 "move cost" 是用條列的方式，會允許該 cost 使用條列的原因是該物件主要是用於”生產報告“，而不是用於"計算"，所以可以接受條列，因為一來不會隨便新增（人類想看的就那幾樣數據）、二來就算新增也不會影響 balancer 的運算（只會影響特定的 cost function)

@qoo332001 上面的字敲一敲我突然想到你的部分，或許你也可以分享一下你要如何從“估計“走到”限制“。上方討論的限制是針對”具體對象”或“行為”（例如某個 topic 不能動、某個節點不能怎樣），你要做的限制是來自於估計（只能移動多少資料、只能動幾個 leaders），這兩者有沒有機會合併成同樣的介面 (我猜現階段可能有點難以想像)？另外一個可以討論的則是，就你估計後的“限制”，該如何讓balancer可以使用？如果回頭去看 web 端使用的方式，其實是自己拿 move cost 來計算，這樣其實不太好，這等同於 balancer 需要去知道 move cost 的細節才能計算，我們可否讓這段也通用一點，例如在MoveCost上新增一個方法來表示"overflow"? 然後透過建構式吃參數來得知限制值？以上只是個想法，都可以討論

[qoo332001]

如果回頭去看 web 端使用的方式，其實是自己拿 move cost 來計算，這樣其實不太好，這等同於 balancer 需要去知道 move cost 的細節才能計算，我們可否讓這段也通用一點，例如在MoveCost上新增一個方法來表示"overflow"?

@chia7712 我在 #1531 實做了這個功能，是否可以等這隻討論完成後再接著看看能否合併另一種限制，謝謝

[g1geordie]

@chia7712 稍微被這個ticket 卡住了 在constraint 的定義上面

１如果使用列舉 增加很多balancer的實作難度 也沒辦法描述複雜問題

 List<Constraint> constraint();
---
 interface Constraint{}
 interface TopicFilterConstraint extends Constraint
 interface NodeFilterConstraint extends Constraint

2. 如果使用一般的限制 表示他需要先計算出新的 cluster 才能去檢查限制 這會導致大大講的 可能接下來連續1000000次都用到被禁止的資源或目標，這樣就會很沒效率

   List<ClusterConstraint> clusterConstraint();
   ---
   ClusterConstraint{
   boolean accept(ClusterInfo newClusterInfo)
   }

有優化的空間 實作者可以自行決定 要在新的cluster 前就不准許這些資源參與 或產生後 就要選１

感覺要很動態的接受各式各樣的條件和 稍微慢一些的速度可能 就要選2

不知道是不是有一個３的完美集合

[chia7712]

不知道是不是有一個３的完美集合

這就是這個題目難的地方，在2的基礎上，我們還需要設計一個「方式」，讓 constrain function 可以「事先」提供一些提示給使用者，讓使用者可以事先知道哪些plan 是一定會被拒絕