選擇什么分片算法

范圍分片

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

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

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

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

數(shù)據(jù)映射表

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

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

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

圖片

ID取模算法

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

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

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

Hash分片算法

Hash 分片算法也叫 Hash 取模算法，他跟ID 取模算法類似，最終都是對分片數(shù)量 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;
    }

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

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

一致性Hash算法

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

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

圖片

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

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

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

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

這里有兩種解決思路：

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

這樣，數(shù)據(jù)的均勻分布情況得到進(jìn)一步的優(yōu)化。

示例如下：

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

一致性hash分片算法的主要優(yōu)點如下：

• 數(shù)據(jù)分布均勻，且可以人為調(diào)控。
• 擴(kuò)容方便，沒有2倍限制，只需要遷移1/N的數(shù)據(jù)。

主要缺點：

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

它能夠幫助分布式系統(tǒng)實現(xiàn)數(shù)據(jù)的分片和負(fù)載均衡，提高系統(tǒng)的可伸縮性和可用性。

Redis Cluster采用的是一種基于哈希槽的分片機(jī)制，該機(jī)制是一致性哈希算法的一種變體，它將整個哈希環(huán)分成固定數(shù)量的槽，每個節(jié)點負(fù)責(zé)一定數(shù)量的槽。

具體來說，Redis Cluster將整個哈希環(huán)分成16384個槽，每個節(jié)點負(fù)責(zé)其中的一部分槽，每個key通過哈希函數(shù)計算出一個哈希值，并映射到某個槽中，然后根據(jù)槽和節(jié)點之間的映射關(guān)系，將該key存儲到對應(yīng)的節(jié)點中。在Redis Cluster中，每個節(jié)點都維護(hù)了一個槽的分配表，記錄了每個槽被分配給了哪個節(jié)點。

相對于傳統(tǒng)的一致性哈希算法，Redis Cluster采用哈希槽算法的優(yōu)勢在于：

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

總結(jié)

最后用一張表總結(jié)一下

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