中文字幕理论片,69视频免费在线观看,亚洲成人app,国产1级毛片,刘涛最大尺度戏视频,欧美亚洲美女视频,2021韩国美女仙女屋vip视频

前言
在我們的日常web應(yīng)用開(kāi)發(fā)當(dāng)中memcached可以算作是當(dāng)今的標(biāo)準(zhǔn)開(kāi)發(fā)配置了。相信memcache的基本原理大家也都了解過(guò)了，memcache雖然是分布式的應(yīng)用服務(wù)，但分布的原則是由client端的api來(lái)決定的，api根據(jù)存儲(chǔ)用的key以及已知的服務(wù)器列表，根據(jù)key的hash計(jì)算將指定的key存儲(chǔ)到對(duì)應(yīng)的服務(wù)器列表上。

基本的原理以及分布
在這里我們通常使用的方法是根據(jù) key的hash值%服務(wù)器數(shù)取余數(shù) 的方法來(lái)決定當(dāng)前這個(gè)key的內(nèi)容發(fā)往哪一個(gè)服務(wù)器的。這里會(huì)涉及到一個(gè)hash算法的分布問(wèn)題，哈希的原理用一句話解釋就是兩個(gè)集合間的映射關(guān)系函數(shù)，在我們通常的應(yīng)用中基本上可以理解為 在集合A（任意字母數(shù)字等組合，此處為存儲(chǔ)用的key）里的一條記錄去查找集合B（如0-2^32）中的對(duì)應(yīng)記錄。（題外話：md5的碰撞或者說(shuō)沖突其實(shí)就是發(fā)生在這里，也就是說(shuō)多個(gè)A的記錄映射到了同一個(gè)B的記錄）

實(shí)際應(yīng)用
顯然在我們的應(yīng)用中集合A的記錄應(yīng)該更均勻的分布在集合B的各個(gè)位置，這樣才能盡量避免我們的數(shù)據(jù)被分布發(fā)送到單一的服務(wù)器上，在danga的memcached的原始版本（perl）中使用的是crc32的算法用java的實(shí)現(xiàn)寫出來(lái)：
    private static int origCompatHashingAlg( String key ) {
        int hash    = 0;
        char[] cArr = key.toCharArray();

        for ( int i = 0; i < cArr.length; ++i ) {
            hash = (hash * 33) + cArr[i];
        }

        return hash;
    }
這里還有另一個(gè)改進(jìn)版本的算法：
    private static int newCompatHashingAlg( String key ) {
        CRC32 checksum = new CRC32();
        checksum.update( key.getBytes() );
        int crc = (int) checksum.getValue();

        return (crc >> 16) & 0x7fff;
    }

分布率測(cè)試
有人做過(guò)測(cè)試，隨機(jī)選擇的key在服務(wù)器數(shù)量為5的時(shí)候所有key在服務(wù)器群組上的分布概率是：
origCompatHashingAlg:
0 10%
1 9%
2 60%
3 9%
4 9%

newCompatHashingAlg:
0 19%
1 19%
2 20%
3 20%
4 20%

顯然使用舊的crc32算法會(huì)導(dǎo)致第三個(gè)memcached服務(wù)的負(fù)載更高，但使用新算法會(huì)讓服務(wù)之間的負(fù)載更加均衡。
其他常用的hash算法還有FNV-1a Hash,RS Hash,JS Hash,PJW Hash,ELF Hash,AP Hash等等。有興趣的童鞋可以查看這里：

http://www.partow.net/programming/hashfunctions/

http://hi.baidu.com/algorithms/blog/item/79caabee879ece2a2cf53440.html

小結(jié)
至此我們了解到了在我們的應(yīng)用當(dāng)中要做到盡量讓我們的映射更加均勻分布，可以使服務(wù)的負(fù)載更加合理均衡。

新問(wèn)題
但到目前為止我們依然面對(duì)了這樣一個(gè)問(wèn)題：就是服務(wù)實(shí)例本身發(fā)生變動(dòng)的時(shí)候，導(dǎo)致服務(wù)列表變動(dòng)從而會(huì)照成大量的cache數(shù)據(jù)請(qǐng)求會(huì)miss，幾乎大部分?jǐn)?shù)據(jù)會(huì)需要遷移到另外的服務(wù)實(shí)例上。這樣在大型服務(wù)在線時(shí)，瞬時(shí)對(duì)后端數(shù)據(jù)庫(kù)/硬盤照成的壓力很可能導(dǎo)致整個(gè)服務(wù)的crash。

一致性哈希（Consistent Hashing）
在此我們采用了一種新的方式來(lái)解決問(wèn)題，處理服務(wù)器的選擇不再僅僅依賴key的hash本身而是將服務(wù)實(shí)例（節(jié)點(diǎn)）的配置也進(jìn)行hash運(yùn)算。

1. 首先求出每個(gè)服務(wù)節(jié)點(diǎn)的hash，并將其配置到一個(gè)0~2^32的圓環(huán)（continuum）區(qū)間上。
2. 其次使用同樣的方法求出你所需要存儲(chǔ)的key的hash，也將其配置到這個(gè)圓環(huán)（continuum）上。
3. 然后從數(shù)據(jù)映射到的位置開(kāi)始順時(shí)針查找，將數(shù)據(jù)保存到找到的第一個(gè)服務(wù)節(jié)點(diǎn)上。如果超過(guò)2^32仍然找不到服務(wù)節(jié)點(diǎn)，就會(huì)保存到第一個(gè)memcached服務(wù)節(jié)點(diǎn)上。

整個(gè)數(shù)據(jù)的圖例：

當(dāng)增加服務(wù)節(jié)點(diǎn)時(shí)：

其他：只有在圓環(huán)上增加服務(wù)節(jié)點(diǎn)的位置為逆時(shí)針?lè)较虻牡谝粋€(gè)服務(wù)節(jié)點(diǎn)上的鍵會(huì)受到影響。

小結(jié)
一致性哈希算法最大程度的避免了key在服務(wù)節(jié)點(diǎn)列表上的重新分布，其他附帶的改進(jìn)就是有的一致性哈希算法還增加了虛擬服務(wù)節(jié)點(diǎn)的方法，也就是一個(gè)服務(wù)節(jié)點(diǎn)在環(huán)上有多個(gè)映射點(diǎn)，這樣就能抑制分布不均勻，
最大限度地減小服務(wù)節(jié)點(diǎn)增減時(shí)的緩存重新分布。

應(yīng)用
在memcached的實(shí)際應(yīng)用，雖然官方的版本并不支持Consistent Hashing，但是已經(jīng)有了現(xiàn)實(shí)的Consistent Hashing實(shí)現(xiàn)以及虛節(jié)點(diǎn)的實(shí)現(xiàn)，第一個(gè)實(shí)現(xiàn)的是last.fm（國(guó)外流行的音樂(lè)平臺(tái)）開(kāi)發(fā)的libketama，
其中調(diào)用的hash的部分的java版本的實(shí)現(xiàn)（基于md5）：
    /**
     * Calculates the ketama hash value for a string 
     * @param s
     * @return
     */
    public static Long md5HashingAlg(String key) {

        if(md5==null) {
            try {
                md5 = MessageDigest.getInstance("MD5");
            } catch (NoSuchAlgorithmException e) {
                log.error( "++++ no md5 algorythm found" );
                throw new IllegalStateException( "++++ no md5 algorythm found");            
            }
        }

        md5.reset();
        md5.update(key.getBytes());
        byte[] bKey = md5.digest();
        long res = ((long)(bKey[3]&0xFF) << 24) | ((long)(bKey[2]&0xFF) << 16) | ((long)(bKey[1]&0xFF) << 8) | (long)(bKey[0]&0xFF);
        return res;
    }
在一致性哈希的算法/策略環(huán)境中，按照測(cè)試來(lái)說(shuō)時(shí)間和分布性都是綜合來(lái)說(shuō)比較讓人滿意的，參見(jiàn)：
http://www.javaeye.com/topic/346682

總結(jié)
在我們的web開(kāi)發(fā)應(yīng)用中的分布式緩存系統(tǒng)里哈希算法承擔(dān)著系統(tǒng)架構(gòu)上的關(guān)鍵點(diǎn)。
使用分布更合理的算法可以使得多個(gè)服務(wù)節(jié)點(diǎn)間的負(fù)載相對(duì)均衡，可以最大程度的避免資源的浪費(fèi)以及服務(wù)器過(guò)載。
使用一致性哈希算法，可以最大程度的降低服務(wù)硬件環(huán)境變化帶來(lái)的數(shù)據(jù)遷移代價(jià)和風(fēng)險(xiǎn)。
使用更合理的配置策略和算法可以使分布式緩存系統(tǒng)更加高效穩(wěn)定的為我們整體的應(yīng)用服務(wù)。

展望
一致性哈希的算法/策略來(lái)源于p2p網(wǎng)絡(luò)，其實(shí)縱觀p2p網(wǎng)絡(luò)應(yīng)用的場(chǎng)景，在許多地方與我們的應(yīng)用有很多相似的地方，可以學(xué)習(xí)借鑒。
參考文章：
對(duì)等網(wǎng)絡(luò)(P2P)中主流分布式哈希算法比較分析
http://www.ppcn.net/n3443c38.aspx

其他參考文章：
http://www.taiwanren.com/blog/article.asp?id=840
http://www.iwms.net/n923c43.aspx
http://tech.idv2.com/2008/07/24/memcached-004/

相關(guān)代碼：
last.fm的ketama代碼
http://static.last.fm/rj/ketama.tar.bz2

php版的Consistent Hashing實(shí)現(xiàn)：Flexihash
主頁(yè)：
http://paul.annesley.cc/articles/2008/04/flexihash-consistent-hashing-php
google code上的代碼主頁(yè)：
http://code.google.com/p/flexihash/
現(xiàn)在已經(jīng)移居到github上了：
http://github.com/pda/flexihash/