11/23/25 刷題日記 — 説説那些常見的routing algorithm

好久不見，刷題日記👋

想當然我不是這段時間不刷題了，那當然是面試太多沒時間筆記下來這些我想記住的事情，當然也是沒有什麼觀眾，今天我想要説説那些常見的routing algorithm，不管是coding round 還是system design理解了實作都是很有幫助

常見的Routing algorithm有:

1. Round Robin 輪詢
2. least connection 最小連接數
3. IP hash 根據IP hash value分配server

還有最後系統設計的最愛: Consistent Hash (一致性哈希)

今天就說說Round Robin 和 Consistent Hash，其他幾個算法我覺得都比較直接了

Round Robin 輪詢

輪詢顧名思義就是在所有可用的服務器(Server)中，按照順序(通常就是連續整數)分配Server去服務Client

基本概念

假設有 5 台servers — [S0, S1, S3, S4, S5]，load balancer啟動時假設從index = 0開始遍歷這些server, 那按找client request的順序，如果當前Server available，我們就直接照順序安排給client

available server = [s0, s1, s4]
req1: s0,
req2: s1,
req3: 本來是s2, 但是s2, s3不可用 -> s4

假設過一陣子之後s2又回到available fleet，這時候下個request

available server = [s2]
req4: s2

從這件事情我們知道，round robin分配load balancer的指針是要不停的繞圈的，也就是說一個server list遍歷到尾的時候，要在從 index == 0繼續開始找是不是有available server了，這個概念類似數學裡頭的模運算 (modulus)

舉例: index剛剛的例子裡頭到尾巴了，index + 1 = 5

此時對index + 1做mod(size) -> 5 % 5 = 0，回到server list的頭部

index = (index + 1) % servers.size(); 

實現

class RoundRobin {
  private List<Server> servers; 
  private int index;
  public class RoundRobin(List<Server> servers){
   this.servers = servers;
   this.index = 0;
  }
  // client對load balancer發出request，load balancer call next()
  public Server next(){
    if (servers.size() == 0) return null;
    int n = servers.size();
    int count = 0; // 問尋過的server數目
    while (count < n) {
       // 1.檢查當前輪詢server可不可用
       Server cur = servers.get(index);
       if (cur.status.equals("AVAILABLE")) return cur;
       // 2. 如果不可用，往下個server問尋
       index = (index + 1) % n;
       count++;
    } 
    // 3. 輪詢所有server都不可用，只好回傳空
    return null;
  }
}

優點

1. 實現簡單，邏輯直接公平
2. 對一般Stateless的服務來說，不需要記錄client的狀態時皆可用

缺點

1. 對於需要紀錄Sticky session的服務來說，這種設計一但有Server掛掉或是有Scale up 需求，所有的Sticky session都要重新遷移 (migration)
2. 輪詢的時候必不考慮當前服務器的負載狀況，某些server負載能力差會有可靠性問題

Consistent Hash 一致性哈希

Consistent Hash的基本概念是為了解決scale up 或是 remove server (instance) 對整個系統遷移的問題，所有sharding相關的概念都會遇到類似的問題，舉個例子:

假設今天UserId = 123, 本來在一個capacity = 5 的系統中, 如果是一個固定的hash算法可能會被安排到 hash(123) % 5 == 3

今天系統traffic需要做水平擴展，capacity 增加到7，這時候同一個userId = hash(123) % 7肯定不是3了，這對於大型系統是個很大的問題，任何添加資源的行為都會讓本來的cache崩潰重新遷移，還有資料庫的存儲本來在A shard就要全部遷移到B shard

這個問題的最佳解法就是一致性哈希

Consistent hash示意圖

從上面這個圖可以看到Consistent Hash有兩個概念

1. 把所有server or shard分配到 hash ring上，假設今天你有4個server，那最接近且大於等於hashValue的key就是你要分配到的server

舉例: 一個ring劃分成100份，其中 0–25是serverA, 26–50是serverB, 51–75是server C, 76–99是server D

某個hash(userId) = 35，我們會分配給最接近且≥這個key的server，也就是serverB

2. 上面大概就可以理解如果這時候在45加上一個server E，traffic會變成下面這個樣子

A: 0-25
B: 26-44
E: 45-50
C: 51-75
D: 76-99

到目前爲止還是可以看得出來Consistent Hash不能完全解決migration的問題，但至少現在需要遷移的資料只有 hash value = [45–50]這個區域，比起本來100%的資料都要重新cache已經好多了

3. 這時候我們可以看到加入或是移除server到系統中有個問題，就是traffic分配不會是均勻的，明顯新加入的節點負載是比較小的，所以我們該怎麼解決這個問題呢? 下面要引入虛擬節點的蓋念

Virtual Nodes:

簡單來說就是在一開始的時候我們就對新加入系統的所有實體server，在所有環上面均勻加上也代表該server的vitual node，可以想像成是開分店的概念，這樣一來某個節點被刪掉的時候，剩下來的load就不會全部落在某一個鄰近的節點身上

server 1: [0, 20, 40, 60, 80]
server 2: [5, 25, 45, 65, 85]
server 3: [10, 30, 50, 70, 90]
server 4: [15, 35, 55, 75, 95]

實現

class ConsistentHash {
 private TreeMap<Integer, String> ring; 
 private static int n = 100; // virtual nodes counts per server
 public ConsistentHash(List<String> servers){
   for (String sid : servers) {
    addServer(sid);
   } 
 } 

 private void addServer(String server) {
   // 遍歷n virtual nodes
   for (int i = 0; i < n; i++){
     int hash = hash(server + "#vn" + i); // s1#vn0
     ring.put(hash, server); // assign vitual node
   }
 }

 private void removeServer(String server) {
   // 遍歷所有server以及其virtual nodes, 依序刪除
   for (int i = 0; i < n; i++){
     int hash = hash(server + "vn" + i);
     ring.remove(hash);
   } 
 } 

 private String getServer(String key){
   // 1. 找出離client key hash value最接近的hash value (順時針) 
   int hash = hash(key);
   Integer ck = ring.ceilingKey(hash);
   // 2. 如果沒有這個值，就直接ring上assign第一個entry
   if (ck == null) {
      return ring.firstEntry().getValue();
   } 
   return ring.get(ck);
 } 

 private int hash(String key){
   return key.hashCode();
 }
}

那今天就到這裡，希望一切順利