免费视频淫片aa毛片_日韩高清在线亚洲专区vr_日韩大片免费观看视频播放_亚洲欧美国产精品完整版

打開APP
userphoto
未登錄

開通VIP，暢享免費電子書等14項超值服

開通VIP

首頁

好書

留言交流

下載APP

聯(lián)系客服
一致性Hash算法(分布式算法)

一致性哈希算法是分布式系統(tǒng)中常用的算法，為什么要用這個算法？

比如：一個分布式存儲系統(tǒng)，要將數(shù)據(jù)存儲到具體的節(jié)點（服務(wù)器）上， 在服務(wù)器數(shù)量不發(fā)生改變的情況下，如果采用普通的hash再對服務(wù)器總數(shù)量取模的方法（如key%服務(wù)器總數(shù)量），如果期間有服務(wù)器宕機(jī)了或者需要增加服務(wù)器，問題就出來了。 同一個key經(jīng)過hash之后，再與服務(wù)器總數(shù)量取模的結(jié)果跟之前的結(jié)果會不一樣，這就導(dǎo)致了之前保存數(shù)據(jù)的丟失。因此，引入了一致性Hash（Consistent Hashing）分布算法

把數(shù)據(jù)用hash函數(shù)（如md5，sha1)，映射到一個圓環(huán)上，如上圖所示，數(shù)據(jù)在存儲時，先根據(jù)hash算法算出key的hash值，對應(yīng)到這個環(huán)中的位置，如k1對應(yīng)圖中所示的位置同，然后沿著順時針方向找到服務(wù)器節(jié)點B，然后把k1在存到B這個節(jié)點中。
如果B節(jié)點宕機(jī)了，則B上的數(shù)據(jù)就會落到C節(jié)點上，如下圖所示

這樣，只會影響C節(jié)點，對于其他節(jié)點A、D的數(shù)據(jù)不會造成影響。但是問題來了，這樣會造成C節(jié)點負(fù)載過重的情況，因為C節(jié)點承擔(dān)了B節(jié)點的數(shù)據(jù)，所以C節(jié)點容易宕機(jī)，這樣造成了分布不均勻。
為了解決這個問題，引入了“虛擬節(jié)點“的概念：即想象空上環(huán)上有很多”虛擬節(jié)點“，一個真實的服務(wù)器節(jié)點對應(yīng)多個虛擬節(jié)點，數(shù)據(jù)存儲的時候沿著環(huán)的順時針方向找到虛擬節(jié)點，就找到了對應(yīng)的真實服務(wù)器節(jié)點。如下圖

圖中的A1、A2、B1、B2、C1、C2、D1、D2都是虛擬節(jié)點，機(jī)器A負(fù)載存儲A1、A2的數(shù)據(jù)，機(jī)器B負(fù)載存儲B1、B2的數(shù)據(jù)，機(jī)器C負(fù)載存儲C1、C2的數(shù)據(jù)。由于這些虛擬節(jié)點數(shù)量很多，均勻分布，因此不會造成“雪崩”現(xiàn)象。
 

一致性哈希算法的PHP實現(xiàn)

下面給出一個接口
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
 * 一致性哈希實現(xiàn)接口
 * Interface ConsistentHash
 */
interface ConsistentHash
{
    //將字符串轉(zhuǎn)為hash值
    public function cHash($str);
    //添加一臺服務(wù)器到服務(wù)器列表中
    public function addServer($server);
    //從服務(wù)器刪除一臺服務(wù)器
    public function removeServer($server);
    //在當(dāng)前的服務(wù)器列表中找到合適的服務(wù)器存放數(shù)據(jù)
    public function lookup($key);
}
這個接口分別定義了4個方法，cHash（將字符串處理為hash值）、addServer（增加一臺服務(wù)器）、removeServer（移除一臺服務(wù)器）、lookup（找到一臺服務(wù)器來存儲數(shù)據(jù)）
下面給出一個該接口的具體實現(xiàn)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
/**
 * 具體一致性哈希實現(xiàn)
 * author chenqionghe
 * Class MyConsistentHash
 */
class MyConsistentHash implements ConsistentHash
{
    public $serverList = array();    //服務(wù)器列列表
    public $virtualPos = array();    //虛擬節(jié)點的位置
    public $virtualPosNum = 5;        //每個節(jié)點對應(yīng)5個虛節(jié)點
    /**
     * 將字符串轉(zhuǎn)換成32位無符號整數(shù)hash值
     * @param $str
     * @return int
     */
    public function cHash($str)
    {
        $str = md5($str);
        return sprintf('%u', crc32($str));
    }
    /**
     * 在當(dāng)前的服務(wù)器列表中找到合適的服務(wù)器存放數(shù)據(jù)
     * @param $key 鍵名
     * @return mixed 返回服務(wù)器IP地址
     */
    public function lookup($key)
    {
        $point = $this->cHash($key);//落點的hash值
        $finalServer = current($this->virtualPos);//先取圓環(huán)上最小的一個節(jié)點當(dāng)成結(jié)果
        foreach($this->virtualPos as $pos=>$server)
        {
            if($point <= $pos)
            {
                $finalServer = $server;
                break;
            }
        }
        reset($this->virtualPos);//重置圓環(huán)的指針為第一個
        return $finalServer;
    }
    /**
     * 添加一臺服務(wù)器到服務(wù)器列表中
     * @param $server 服務(wù)器IP地址
     * @return bool
     */
    public function addServer($server)
    {
        if(!isset($this->serverList[$server]))
        {
            for($i=0; $i<$this->virtualPosNum; $i++)
            {
                $pos = $this->cHash($server . '-' . $i);
                $this->virtualPos[$pos] = $server;
                $this->serverList[$server][] = $pos;
            }
            ksort($this->virtualPos,SORT_NUMERIC);
        }
        return TRUE;
    }
    /**
     * 移除一臺服務(wù)器（循環(huán)所有的虛節(jié)點，刪除值為該服務(wù)器地址的虛節(jié)點）
     * @param $key
     * @return bool
     */
    public function removeServer($key)
    {
        if(isset($this->serverList[$key]))
        {
            //刪除對應(yīng)虛節(jié)點
            foreach($this->serverList[$key] as $pos)
            {
                unset($this->virtualPos[$pos]);
            }
            //刪除對應(yīng)服務(wù)器
            unset($this->serverList[$key]);
        }
        return TRUE;
    }
}
然后， 我們來測試一下該算法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
$hashServer = new MyConsistentHash();
$hashServer->addServer('192.168.1.1');
$hashServer->addServer('192.168.1.2');
$hashServer->addServer('192.168.1.3');
$hashServer->addServer('192.168.1.4');
$hashServer->addServer('192.168.1.5');
$hashServer->addServer('192.168.1.6');
$hashServer->addServer('192.168.1.7');
$hashServer->addServer('192.168.1.8');
$hashServer->addServer('192.168.1.9');
$hashServer->addServer('192.168.1.10');
echo "增加十臺服務(wù)器192.168.1.1~192.168.1.10<br />";
echo "保存 key1 到 server :".$hashServer->lookup('key1') . '<br />';
echo "保存 key2 到 server :".$hashServer->lookup('key2') . '<br />';
echo "保存 key3 到 server :".$hashServer->lookup('key3') . '<br />';
echo "保存 key4 到 server :".$hashServer->lookup('key4') . '<br />';
echo "保存 key5 到 server :".$hashServer->lookup('key5') . '<br />';
echo "保存 key6 到 server :".$hashServer->lookup('key6') . '<br />';
echo "保存 key7 到 server :".$hashServer->lookup('key7') . '<br />';
echo "保存 key8 到 server :".$hashServer->lookup('key8') . '<br />';
echo "保存 key9 到 server :".$hashServer->lookup('key9') . '<br />';
echo "保存 key10 到 server :".$hashServer->lookup('key10') . '<br />';
echo '<hr />';
echo "移除一臺服務(wù)器192.168.1.2<br />";
$hashServer->removeServer('192.168.1.2');
echo "保存 key1 到 server :".$hashServer->lookup('key1') . '<br />';
echo "保存 key2 到 server :".$hashServer->lookup('key2') . '<br />';
echo "保存 key3 到 server :".$hashServer->lookup('key3') . '<br />';
echo "保存 key4 到 server :".$hashServer->lookup('key4') . '<br />';
echo "保存 key5 到 server :".$hashServer->lookup('key5') . '<br />';
echo "保存 key6 到 server :".$hashServer->lookup('key6') . '<br />';
echo "保存 key7 到 server :".$hashServer->lookup('key7') . '<br />';
echo "保存 key8 到 server :".$hashServer->lookup('key8') . '<br />';
echo "保存 key9 到 server :".$hashServer->lookup('key9') . '<br />';
echo "保存 key10 到 server :".$hashServer->lookup('key10') . '<br />';
echo '<hr />';
echo "移除一臺服務(wù)器192.168.1.6<br />";
$hashServer->removeServer('192.168.1.6');
echo "保存 key1 到 server :".$hashServer->lookup('key1') . '<br />';
echo "保存 key2 到 server :".$hashServer->lookup('key2') . '<br />';
echo "保存 key3 到 server :".$hashServer->lookup('key3') . '<br />';
echo "保存 key4 到 server :".$hashServer->lookup('key4') . '<br />';
echo "保存 key5 到 server :".$hashServer->lookup('key5') . '<br />';
echo "保存 key6 到 server :".$hashServer->lookup('key6') . '<br />';
echo "保存 key7 到 server :".$hashServer->lookup('key7') . '<br />';
echo "保存 key8 到 server :".$hashServer->lookup('key8') . '<br />';
echo "保存 key9 到 server :".$hashServer->lookup('key9') . '<br />';
echo "保存 key10 到 server :".$hashServer->lookup('key10') . '<br />';
echo '<hr />';
echo "移除一臺服務(wù)器192.168.1.8<br />";
$hashServer->removeServer('192.168.1.8');
echo "保存 key1 到 server :".$hashServer->lookup('key1') . '<br />';
echo "保存 key2 到 server :".$hashServer->lookup('key2') . '<br />';
echo "保存 key3 到 server :".$hashServer->lookup('key3') . '<br />';
echo "保存 key4 到 server :".$hashServer->lookup('key4') . '<br />';
echo "保存 key5 到 server :".$hashServer->lookup('key5') . '<br />';
echo "保存 key6 到 server :".$hashServer->lookup('key6') . '<br />';
echo "保存 key7 到 server :".$hashServer->lookup('key7') . '<br />';
echo "保存 key8 到 server :".$hashServer->lookup('key8') . '<br />';
echo "保存 key9 到 server :".$hashServer->lookup('key9') . '<br />';
echo "保存 key10 到 server :".$hashServer->lookup('key10') . '<br />';
echo '<hr />';
echo "移除一臺服務(wù)器192.168.1.2<br />";
$hashServer->removeServer('192.168.1.2');
echo "保存 key1 到 server :".$hashServer->lookup('key1') . '<br />';
echo "保存 key2 到 server :".$hashServer->lookup('key2') . '<br />';
echo "保存 key3 到 server :".$hashServer->lookup('key3') . '<br />';
echo "保存 key4 到 server :".$hashServer->lookup('key4') . '<br />';
echo "保存 key5 到 server :".$hashServer->lookup('key5') . '<br />';
echo "保存 key6 到 server :".$hashServer->lookup('key6') . '<br />';
echo "保存 key7 到 server :".$hashServer->lookup('key7') . '<br />';
echo "保存 key8 到 server :".$hashServer->lookup('key8') . '<br />';
echo "保存 key9 到 server :".$hashServer->lookup('key9') . '<br />';
echo "保存 key10 到 server :".$hashServer->lookup('key10') . '<br />';
echo '<hr />';
echo "增加一臺服務(wù)器192.168.1.11<br />";
$hashServer->addServer('192.168.1.11');
echo "保存 key1 到 server :".$hashServer->lookup('key1') . '<br />';
echo "保存 key2 到 server :".$hashServer->lookup('key2') . '<br />';
echo "保存 key3 到 server :".$hashServer->lookup('key3') . '<br />';
echo "保存 key4 到 server :".$hashServer->lookup('key4') . '<br />';
echo "保存 key5 到 server :".$hashServer->lookup('key5') . '<br />';
echo "保存 key6 到 server :".$hashServer->lookup('key6') . '<br />';
echo "保存 key7 到 server :".$hashServer->lookup('key7') . '<br />';
echo "保存 key8 到 server :".$hashServer->lookup('key8') . '<br />';
echo "保存 key9 到 server :".$hashServer->lookup('key9') . '<br />';
echo "保存 key10 到 server :".$hashServer->lookup('key10') . '<br />';
echo '<hr />';

運行結(jié)果如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
增加十臺服務(wù)器192.168.1.1~192.168.1.10
保存 key1 到 server :192.168.1.2
保存 key2 到 server :192.168.1.1
保存 key3 到 server :192.168.1.6
保存 key4 到 server :192.168.1.8
保存 key5 到 server :192.168.1.9
保存 key6 到 server :192.168.1.10
保存 key7 到 server :192.168.1.7
保存 key8 到 server :192.168.1.4
保存 key9 到 server :192.168.1.7
保存 key10 到 server :192.168.1.4
移除一臺服務(wù)器192.168.1.2
保存 key1 到 server :192.168.1.7
保存 key2 到 server :192.168.1.1
保存 key3 到 server :192.168.1.6
保存 key4 到 server :192.168.1.8
保存 key5 到 server :192.168.1.9
保存 key6 到 server :192.168.1.10
保存 key7 到 server :192.168.1.7
保存 key8 到 server :192.168.1.4
保存 key9 到 server :192.168.1.7
保存 key10 到 server :192.168.1.4
移除一臺服務(wù)器192.168.1.6
保存 key1 到 server :192.168.1.7
保存 key2 到 server :192.168.1.1
保存 key3 到 server :192.168.1.3
保存 key4 到 server :192.168.1.8
保存 key5 到 server :192.168.1.9
保存 key6 到 server :192.168.1.10
保存 key7 到 server :192.168.1.7
保存 key8 到 server :192.168.1.4
保存 key9 到 server :192.168.1.7
保存 key10 到 server :192.168.1.4
移除一臺服務(wù)器192.168.1.8
保存 key1 到 server :192.168.1.7
保存 key2 到 server :192.168.1.1
保存 key3 到 server :192.168.1.3
保存 key4 到 server :192.168.1.10
保存 key5 到 server :192.168.1.9
保存 key6 到 server :192.168.1.10
保存 key7 到 server :192.168.1.7
保存 key8 到 server :192.168.1.4
保存 key9 到 server :192.168.1.7
保存 key10 到 server :192.168.1.4
移除一臺服務(wù)器192.168.1.2
保存 key1 到 server :192.168.1.7
保存 key2 到 server :192.168.1.1
保存 key3 到 server :192.168.1.3
保存 key4 到 server :192.168.1.10
保存 key5 到 server :192.168.1.9
保存 key6 到 server :192.168.1.10
保存 key7 到 server :192.168.1.7
保存 key8 到 server :192.168.1.4
保存 key9 到 server :192.168.1.7
保存 key10 到 server :192.168.1.4
增加一臺服務(wù)器192.168.1.11
保存 key1 到 server :192.168.1.7
保存 key2 到 server :192.168.1.1
保存 key3 到 server :192.168.1.11
保存 key4 到 server :192.168.1.10
保存 key5 到 server :192.168.1.9
保存 key6 到 server :192.168.1.10
保存 key7 到 server :192.168.1.7
保存 key8 到 server :192.168.1.4
保存 key9 到 server :192.168.1.7
保存 key10 到 server :192.168.1.4
可以，看到，使用一致性哈希后，無認(rèn)是增加服務(wù)器還是減少服務(wù)器都最大程度的保證了數(shù)據(jù)的完整性、均勻性.
本站僅提供存儲服務(wù)，所有內(nèi)容均由用戶發(fā)布，如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容，請點擊舉報。
打開APP，閱讀全文并永久保存 查看更多類似文章
猜你喜歡
類似文章
JBoss教程
php幾個預(yù)定義變量$
Memcache基礎(chǔ)教程 - Memcache
PHP: 深入了解一致性哈希
使用Mosh來優(yōu)化SSH連接 – 運維生存時間
對于C#中的FileUpload解決文件上傳大小限制的問題設(shè)置
更多類似文章 >>
生活服務(wù)
分享 收藏 導(dǎo)長圖 關(guān)注 下載文章
綁定賬號成功
后續(xù)可登錄賬號暢享VIP特權(quán)！
如果VIP功能使用有故障，
可點擊這里聯(lián)系客服！

聯(lián)系客服