如何用PHP實現(xiàn)分布算法之一致性哈希算法

更新時間：2021年05月26日 10:27:07 作者：枕邊書

進行大型網(wǎng)站的web開發(fā)時，分布式這個詞經(jīng)常出現(xiàn)在我們面前。如： memcache、redis服務器等緩存服務器的負載均衡（分布式cache）、 MySQL的分布式集群，這些都會用到分布式的思想，都要理解分布式算法。接下來以緩存服務器的負載均衡來談一下一致性哈希算法。

傳統(tǒng)算法缺陷

對于服務器分布，我們要考慮的東西有如下三點：數(shù)據(jù)平均分布，查找定位準確，降低宕機影響。

傳統(tǒng)算法一般是將數(shù)據(jù)的鍵用算法映射出數(shù)字，對其用服務器數(shù)量取模，并根據(jù)結(jié)果選擇要存儲的服務器。其能達到數(shù)據(jù)平均分布和查找定位準確的要求，并且優(yōu)點是算法簡單，存取時的計算量都比較小（在數(shù)據(jù)非常大時才會明顯）。

但其有一個致命缺點，即一個服務器宕機后的影響很大，我們可以推算一下一臺服務器宕機后的影響：

原有數(shù)據(jù)大部分丟失：服務器數(shù)量減少一臺，取模數(shù)減1導致取模值錯亂，如果以前有N臺服務器，那么宕機后數(shù)據(jù)只有1/(n*(n-1))的數(shù)據(jù)能夠被準確查找到。
負載無法均衡導致集體宕機：如果沒有及時處理宕機的服務器，那么他的存儲任務將會被順序積累給它的下一個服務器，那么下一個服務器也會很快被壓致宕機，如此一來，服務器組很快會集體宕機。

算法思想

一致性哈希算法是使用一定的哈希算法，將大量的數(shù)據(jù)平均映射到不同的存儲目標上，在保證其查找準確性的同時，還要考慮其中一個存儲目標失效時，其他存儲目標對其責任存儲內(nèi)容的負載均衡。

一致性哈希算法的實現(xiàn)思想不難理解，如圖：

1.用一定的哈希算法（哈希函數(shù)等）將一組服務器的多個（數(shù)目自己設定）節(jié)點隨機映射分散到0-232之間，由于其隨機分布，保證了其數(shù)據(jù)平均分布的特點；

2.用同一算法計算要存儲數(shù)據(jù)的鍵，根據(jù)服務器節(jié)點確定其存儲的服務器結(jié)點，由于每次用同一算法計算，所以得出的結(jié)果是相同的，使其查找定位準確；

3.查找數(shù)據(jù)時，再次用同一算法計算鍵，并查找服務器的數(shù)據(jù)結(jié)點；

4.如果有一個服務器宕機，消除其服務器結(jié)點，并將數(shù)據(jù)放在下一個結(jié)點上，由于隨機節(jié)點位置的隨機性，所以數(shù)據(jù)被其他服務器平均負載，也就降低了宕機影響。

需要注意的是，這個環(huán)形空間只是一個虛擬空間，只是表示了服務器存儲的范圍和數(shù)據(jù)的落點，在進行存儲時，我們還要通過查找到的落點，將數(shù)據(jù)放入對應的服務器進行查改。

算法實現(xiàn)

編程語言我們使用PHP來實現(xiàn)一致性哈希算法：

我們主要用到以下函數(shù)：

int crc32 ( string $str )
生成 str 的 32 位循環(huán)冗余校驗碼多項式。這通常用于檢查傳輸?shù)臄?shù)據(jù)是否完整。

string sprintf ( string $format [, mixed $args [, mixed $... ]] )
通過傳入的格式產(chǎn)生字符串的特定格式形態(tài)。

實現(xiàn)如下：

class Consistance
{
    protected $num=24;          //設定每一個服務器的節(jié)點數(shù)，數(shù)量越多，宕機時服務器負載就會分布得越平均，但也增大數(shù)據(jù)查找消耗。
    protected $nodes=array();   //當前服務器組的結(jié)點列表。

    //計算一個數(shù)據(jù)的哈希值，用以確定位置
    public function make_hash($data)
    {
        return sprintf('%u',crc32($data));
    }

    //遍歷當前服務器組的節(jié)點列表，確定需要存儲/查找的服務器
    public function set_loc($data)
    {
        $loc=self::make_hash($data);
        foreach ($this->nodes as $key => $val)
        {
            if($loc<=$key)
            {
                return $val;
            }
        }
    }

    //添加一個服務器，將其結(jié)點添加到服務器組的節(jié)點列表內(nèi)。
    public function add_host($host)
    {
        for($i=0;$i<$this->num;$i++)
        {
            $key=sprintf('%u',crc32($host.'_'.$i));
            $this->nodes[$key]=$host;   
        }
        ksort($this->nodes);        //對結(jié)點排序，這樣便于查找。
    }

    //刪除一個服務器，并將其對應節(jié)點從服務器組的節(jié)點列表內(nèi)移除。
    public function remove_host($host)
    {
        for($i=0;$i<$this->num;$i++)
        {
            $key=sprintf('%u',crc32($host.'_'.$i));
            unset($this->nodes[$key]);
        }
    }
}

我們用以下代碼進行測試：