選擇什么分片算法

范圍分片

選擇分片算法和選擇 Sharding Key 也有一定的關系，比如前一篇提到的 B 端系統使用創建時間去做分片，那算法就很簡單了，就是按照一定的時間范圍去做拆分。

這種實現最大的特點就是簡單并且查詢友好，因為所有相關的數據都按照時間范圍落在一個分片里。并且因為 B端系統低并發的特性，這樣查詢不會帶來什么效率問題。

但是如果是C端系統就不行了，按照時間范圍拆分會帶來熱點數據傾斜，可能即使分了很片，數據庫依然頻頻告警。

所以 C 端系統一般不會選擇時間范圍去拆分，而是選擇一個合適的算法，不僅是讓數據均勻去分布，而且需要讓熱點數據去均勻分布。這樣用戶的請求才能均勻去分布到每個機器上，發揮出分庫分表的優勢。

數據映射表

均勻分配數據的關鍵就在于知道有多少數據分配在了哪些庫里，那我們專門用一個表記錄這些 Sharding Key 對應的分片不就可以了嗎？數據映射表方案是這樣的，查詢的時候先使用 Sharding Key 去映射表查詢對應的分片信息，然后再根據分片信息去指定分片查詢。

這樣的好處是：數據分配靈活，可以人為掌控，想怎么分就怎么分，并且后期擴容方便，我想把哪些數據遷移到新數據庫直接調整映射表就好了。

缺點也顯而易見：這樣的查詢需要多一次數據庫連接的過程，當然這個問題可以通過把熱點映射 Key 加入到緩存中來進行優化。但是如果映射表數據過多，而我們又需要對映射表頻繁寫入和查詢，映射表本身就容易成為性能瓶頸。

圖片

ID取模算法

ID取模算法大家應該都能想到。我需要分N個庫，把用戶 id 對N直接取模就可以了，結果就等于分庫號。比如用戶id是2023007，限制有10個分庫，那么2023007%10=7，7就是分庫號。雖然簡單，但是對于大多數場景它完全可以勝任，因為大多數系統并沒有非常夸張的數據量。

相比第一種范圍分片，它的數據均勻程度通常要好很多。但是這是有前提條件的，他非常依賴ID的自增連續性，要求尾號相對連續。比如尾號不能和性別、地域等因素有關系，否則會影響數據再分片中的分布情況。

ID取模：
public class ShardingUtil {
    // 計算數據表編號
    public static int shard(int id, int tableCount) {
        return id % tableCount;
    }
}

Hash分片算法

Hash 分片算法也叫 Hash 取模算法，他跟ID 取模算法類似，最終都是對分片數量 N 取模，但是不同的是它會在取模之前先對 Sharding Key 做一次Hash計算。示例如下：

public class ShardingUtil {
    // 計算哈希值
    public static int hash(String key) {
        int hash = 0;
        for (int i = 0; i < key.length(); i++) {
            hash = hash * 31 + key.charAt(i);
        }
        return hash;
    }

    // 計算數據表編號
    public static int shard(int hash, int tableCount) {
        return (hash & Integer.MAX_VALUE) % tableCount;
    }
}

它的好處是，相比簡單的直接ID取模，多了一步Hash，讓數據分布更為均勻，且實現依舊簡單。但是缺點依舊存在，擴容不方便的問題并沒有得到解決，需要以2的倍數擴容，擴容時候最少需要遷移50%的數據到新分片上。

一致性Hash算法

一致性哈希算法是用于解決分布式系統中的數據分片和負載均衡問題的一種算法。一致性哈希算法的基本思想是將所有的數據和服務器都映射到一個固定大小的哈希環上，通過對數據的哈希值進行計算，將其映射到環上的某個位置，然后選擇離這個位置最近的服務器作為數據的存儲位置。

環的大小是2^32-1，這樣就可以保證每一個ip地址都可以在環上獲得一個映射位置，并且這個足夠大的數字可以提供更高的數據均勻度。查找數據時key落在某個點后，繼續向前遇到的第一個Node就是要查找的分片。在添加或刪除服務器時，只會影響哈希環上與該服務器相鄰的一小段數據的存儲位置，而不會影響整個系統的數據分布。

圖片

在分庫分表中，假設我們有N個數據庫或數據表，我們可以將它們映射到一個固定大小的哈希環上，然后通過數據庫的IP地址計算數據的哈希值，將其映射到環上的某個位置，并選擇離該位置最近的數據庫或數據表作為數據的存儲位置。

但是標準的一致性Hash通過 hash(數據庫IP地址) % 2^32 計算數據庫在Hash環中的位置，如果分片數量較少，會造成數據庫節點在Hash環節點分布不均勻，最終導致數據分布不均勻。并且現在大都使用云環境，節點的IP地址很可能會發生變化，從而導在hash環位置的變化。解決這個問題有下面幾種辦法：

1. 對于IP位置變更的問題，我們可以不采用IP去Hash，而使用分片的邏輯號，比如Node1、Node2。
2. 對于Hash偏斜問題，我們可以通過增加虛擬節點來解，認為去將數據調配。

但是通過上述優化，我覺得這樣的一致性Hash算法還是不夠簡單。首先是DB數量不夠多的情況下，增加虛擬節點的問題，還得多去維護虛擬節點。

這里有兩種解決思路：

1. 對DB計算Hash值的算法進行改寫，直接根據邏輯編號指定在Hash環位置的映射位置，比如指定Node1、Node2分別在Hash環的起點和中點。
2. 其實可以參考Redis cluster 采用的Hash槽算法的思路。我們直接將Hash環簡化為4096或者2048個槽位，將固定范圍的槽位分配到對應節點上。

這樣，數據的均勻分布情況得到進一步的優化。

示例如下：

public static final int SHARDING_COUNT = 4;
// 計算數據表編號
public static int shard(Long id) {
    return (Math.abs(id.hashCode()) % 2048) / (2048 / SHARDING_COUNT);
}

一致性hash分片算法的主要優點如下：

• 數據分布均勻，且可以人為調控。
• 擴容方便，沒有2倍限制，只需要遷移1/N的數據。

主要缺點：

• 相比于其他算法，他的實現更為復雜。
• 有分布不均勻的問題，但是可以通過虛擬節點解決，或者指定槽位。

它能夠幫助分布式系統實現數據的分片和負載均衡，提高系統的可伸縮性和可用性。

Redis Cluster采用的是一種基于哈希槽的分片機制，該機制是一致性哈希算法的一種變體，它將整個哈希環分成固定數量的槽，每個節點負責一定數量的槽。

具體來說，Redis Cluster將整個哈希環分成16384個槽，每個節點負責其中的一部分槽，每個key通過哈希函數計算出一個哈希值，并映射到某個槽中，然后根據槽和節點之間的映射關系，將該key存儲到對應的節點中。在Redis Cluster中，每個節點都維護了一個槽的分配表，記錄了每個槽被分配給了哪個節點。

相對于傳統的一致性哈希算法，Redis Cluster采用哈希槽算法的優勢在于：

1. 算法簡單：將哈希環分成固定數量的槽，每個節點負責一定數量的槽，可以簡化分片算法的實現。
2. 可擴展性好：增加或刪除節點時，只需要重新分配一部分槽即可，不需要像一致性哈希算法那樣重新映射所有的key，可以有效地減少數據遷移量。
3. 靈活性高：可以根據實際需要調整槽的數量和節點的分配情況，以滿足不同的應用場景。

總結

最后用一張表總結一下

最后，歡迎大家提問和交流。