Cloud Computing - Lagrangian Relaxation & Load Balance & Dynamic Scheduling Algorithms
針對雲端群集伺服器的負載平衡優化實驗中應用到的 Lagrangian Relaxation 拉格朗日鬆弛演算法、Load Balance 負載平衡和 Dynamic Scheduling Algorithms 動態排程演算法的學習筆記
Lagrangian Relaxation Intro
拉格朗日鬆弛 (Lagrangian Relaxation) 是一種優化問題的方法，通常用於處理具有約束條件的問題
基本概念是透過將原始問題的約束條件放入目標函數中，並引入拉格朗日鬆弛乘子來進行鬆弛
讓原問題轉化為無約束的優化問題
作法為透過在原目標函數中引入的拉格朗日項讓原目標函數的最小值問題更小、讓原目標函數的最大值問題更大
例如對於最小值問題，在由拉格朗日乘子構造的拉格朗日函數中去最大值，將下界 (lower bound) 提高，以此獲得最佳下界
Lagrangian Relaxation 的基本運算式
Lagrangian Relaxation 的基本運算式為：
- λi 為非負的拉格朗日乘子
- μj 為拉格朗日乘子
- L (x,λ,μ) 便是我們想要的 Lagrangian 函數
- minxL (x,λ,μ) 即為我們要的 Lagrangian Relaxation，將原始問題轉化為 Lagrangian 函數的最小化問題
Load Balance Intro
負載平衡 (Load balancing) 是在電腦中，合理的分配工作到不同的資源上，以確保資源能夠最有效的被利用
其目標是確保每個資源都能盡可能地平均處理工作
針對伺服器的負載失衡問題：
在分散式伺服器中，不同的伺服器可能處於不同負載狀態
當某些伺服器過度忙碌，其他伺服器處於閒置狀態，就是負載失衡
當有人忙得要死但同事啥事都不用幹，會讓員工不爽
且使公司效率降低，損失整體效益，所以好的主管要學會負載平衡分配好工作！
伺服器負載平衡方法
Load Balancer
負載平衡器 (Load Balancer) 是在伺服器群集前一步的裝置，用來將請求分配到不同的伺服器，根據不同的負載平衡演算法
Dynamic Scheduling Algorithms
Load Balancer 分配請求使用的負載平衡演算法，我以下述 動態排程演算法 (Dynamic Scheduling Algorithms) 中的五種演算法做主要分析
- 輪詢法 (Round Robin)
- 加權輪詢演算法 (Weighted Round Robin)
- 平滑加權輪詢演算法 (Smoothing Weighted Round Robin)
- 最少連接法 (Least Connections)
- 隨機法 (Random)
Dynamic Scheduling Algorithms
1. 輪詢法 (Round Robin)
將請求按照輪詢方式分配給伺服器，每個伺服器一次接收一個請求
2. 加權輪詢演算法 (Weighted Round Robin)
為不同的伺服器分配不同的權重，用以反映它們的性能，性能較好的伺服器分配更多請求
加權輪詢演算法利用權重分配機制，權重越大，伺服器處理請求的優先級越高，每個請求將會以各自權重比例被送到伺服器上進行處理
3. 平滑加權輪詢演算法 (Smoothing Weighted Round Robin)
在分配任務給不同的伺服器時，每個伺服器有一個權重的平滑計分值，每完成一項任務，計分會增加，每次分配會考慮伺服器的當前權重指標計分多少
平滑加權輪詢演算之步驟如下：
1. 為每個伺服器節點分配一個決策權重(Descision Weight)，初始值與權重相同
2. 選擇決策權重最大的伺服器節點
3. 將步驟2中所選的伺服器節點的決策權重減去所有伺服器節點的權重總和
4. 將每個伺服器節點的決策權重加上權重，更新為新的決策權重
5. 重複步驟2到步驟4，直到得出平滑加權循環數列
4. 最少連接法 (Least Connections)
將請求分配給目前連接數最少的伺服器，讓較閒的伺服器來處理請求
5. 隨機法 (Random)
透過隨機選擇來分配伺服器處理請求，但可能導致資源分配不均勻
Checkpoint
檢查點 (Checkpoint) 用於在執行過程中定期保存系統的當前狀態,
以確保在系統遇到錯誤、中斷或意外狀況的時候，可以回復到之前有被保存到的狀態，而不會損失太多數據或進度
Starvation
飢餓問題 (Starvation) 是指 process、threads 或任務由於無法獲得所需的資源而無法繼續運行或完成的情況
通常發生在多任務環境中，因為多個 process 競爭有限的系統資源而導致，因此需要通過合理的資源分配策略來避免飢餓問題產生
NP-hard Problem
NP-hard 問題是指，在多項式時間內不可能找到精確解的決策問題，所以目前沒有已知的演算法可以在多項式時間內解決 NP-hard 問題的所有實例
如果有一個 NP-hard 問題可以被多項式時間解決，則所有 NP 問題都可以被多項式時間解決，所以 NP-hard 問題是所有 NP 問題中最難解決的問題
但 NP-hard 問題沒有已知的可解決的演算法，目前只能使用一些演算法來獲得近似解