2011 年 CSDN 的“脫庫”事件刘莹，當(dāng)時(shí)暇藏，CSDN 網(wǎng)站被黑客攻擊，超過 600 萬用戶的注冊(cè)郵箱和密碼明文被泄露靴迫，很多網(wǎng)友對(duì) CSDN 明文保存用戶密碼行為產(chǎn)生了不滿惕味。如果你是 CSDN 的一名工程師，你會(huì)如何存儲(chǔ)用戶密碼這么重要的數(shù)據(jù)嗎玉锌？?jī)H僅 MD5 加密一下存儲(chǔ)就夠了嗎名挥？ 要想搞清楚這個(gè)問題，就要先弄明白哈希算法主守。
哈希算法歷史悠久禀倔，業(yè)界著名的哈希算法也有很多，比如 MD5参淫、SHA 等救湖。在我們平時(shí)的開發(fā)中，基本上都是拿現(xiàn)成的直接用涎才。在實(shí)際的開發(fā)中捎谨，我們?cè)撊绾斡霉Ｋ惴ń鉀Q問題。
什么是哈希算法憔维？
實(shí)際上涛救，不管是“散列”還是“哈希”业扒，這都是中文翻譯的差別检吆，英文其實(shí)就是“Hash”。所以程储，我們常聽到有人把“散列表”叫作“哈希表”“Hash 表”蹭沛，把“哈希算法”叫作“Hash 算法”或者“散列算法”臂寝。那到底什么是哈希算法呢？哈希算法的定義和原理非常簡(jiǎn)單摊灭，基本上一句話就可以概括了咆贬。將任意長(zhǎng)度的二進(jìn)制值串映射為固定長(zhǎng)度的二進(jìn)制值串，這個(gè)映射的規(guī)則就是哈希算法帚呼，而通過原始數(shù)據(jù)映射之后得到的二進(jìn)制值串就是哈希值掏缎。但是，要想設(shè)計(jì)一個(gè)優(yōu)秀的哈希算法并不容易煤杀，需要滿足的幾點(diǎn)要求：
- 從哈希值不能反向推導(dǎo)出原始數(shù)據(jù)（所以哈希算法也叫單向哈希算法）眷蜈；
- 對(duì)輸入數(shù)據(jù)非常敏感，哪怕原始數(shù)據(jù)只修改了一個(gè) Bit沈自，最后得到的哈希值也大不相同酌儒；
- 散列沖突的概率要很小，對(duì)于不同的原始數(shù)據(jù)枯途，哈希值相同的概率非常屑稍酢；
- 哈希算法的執(zhí)行效率要盡量高效酪夷，針對(duì)較長(zhǎng)的文本呆躲，也能快速地計(jì)算出哈希值。
這些定義和要求都比較理論捶索，拿 MD5 這種哈希算法來具體說明一下。我們分別對(duì)“今天我來講哈希算法”和“jiajia”這兩個(gè)文本灰瞻，計(jì)算 MD5 哈希值腥例，得到兩串看起來毫無規(guī)律的字符串（MD5 的哈希值是 128 位的 Bit 長(zhǎng)度，為了方便表示酝润，我把它們轉(zhuǎn)化成了 16 進(jìn)制編碼）燎竖。可以看出來要销，無論要哈希的文本有多長(zhǎng)构回、多短，通過 MD5 哈希之后疏咐，得到的哈希值的長(zhǎng)度都是相同的纤掸，而且得到的哈希值看起來像一堆隨機(jī)數(shù)，完全沒有規(guī)律浑塞。
MD5("今天我來講哈希算法") = bb4767201ad42c74e650c1b6c03d78fa
MD5("jiajia") = cd611a31ea969b908932d44d126d195b
我們?cè)賮砜磧蓚€(gè)非常相似的文本借跪，“我今天講哈希算法！”和“我今天講哈希算法”酌壕。這兩個(gè)文本只有一個(gè)感嘆號(hào)的區(qū)別掏愁。如果用 MD5 哈希算法分別計(jì)算它們的哈希值歇由，你會(huì)發(fā)現(xiàn)，盡管只有一字之差果港，得到的哈希值也是完全不同的沦泌。
MD5("我今天講哈希算法！") = 425f0d5a917188d2c3c3dc85b5e4f2cb
MD5("我今天講哈希算法") = a1fb91ac128e6aa37fe42c663971ac3d
通過哈希算法得到的哈希值辛掠，很難反向推導(dǎo)出原始數(shù)據(jù)谢谦。比如上面的例子中，我們就很難通過哈希值“a1fb91ac128e6aa37fe42c663971ac3d”反推出對(duì)應(yīng)的文本“我今天講哈希算法”公浪。哈希算法要處理的文本可能是各種各樣的他宛。比如，對(duì)于非常長(zhǎng)的文本欠气，如果哈希算法的計(jì)算時(shí)間很長(zhǎng)厅各，那就只能停留在理論研究的層面，很難應(yīng)用到實(shí)際的軟件開發(fā)中预柒。比如队塘，我們把今天這篇包含 4000 多個(gè)漢字的文章，用 MD5 計(jì)算哈希值宜鸯，用不了 1ms 的時(shí)間憔古。哈希算法的應(yīng)用非常非常多，最常見的七個(gè)淋袖，分別是安全加密鸿市、唯一標(biāo)識(shí)、數(shù)據(jù)校驗(yàn)即碗、散列函數(shù)焰情、負(fù)載均衡、數(shù)據(jù)分片剥懒、分布式存儲(chǔ)内舟。
應(yīng)用一：安全加密
說到哈希算法的應(yīng)用，最先想到的應(yīng)該就是安全加密初橘。最常用于加密的哈希算法是 MD5（MD5 Message-Digest Algorithm验游，MD5 消息摘要算法）和 SHA（Secure Hash Algorithm，安全散列算法）保檐。除了這兩個(gè)之外耕蝉，當(dāng)然還有很多其他加密算法，比如 DES（Data Encryption Standard夜只，數(shù)據(jù)加密標(biāo)準(zhǔn)）赔硫、AES（Advanced Encryption Standard，高級(jí)加密標(biāo)準(zhǔn)）盐肃。前面講到的哈希算法四點(diǎn)要求爪膊，對(duì)用于加密的哈希算法來說权悟，有兩點(diǎn)格外重要。第一點(diǎn)是很難根據(jù)哈希值反向推導(dǎo)出原始數(shù)據(jù)推盛，第二點(diǎn)是散列沖突的概率要很小峦阁。第一點(diǎn)很好理解，加密的目的就是防止原始數(shù)據(jù)泄露耘成，所以很難通過哈希值反向推導(dǎo)原始數(shù)據(jù)榔昔，這是一個(gè)最基本的要求。所以我著重講一下第二點(diǎn)瘪菌。實(shí)際上撒会，不管是什么哈希算法，我們只能盡量減少碰撞沖突的概率师妙，理論上是沒辦法做到完全不沖突的诵肛。為什么這么說呢？這里就基于組合數(shù)學(xué)中一個(gè)非衬ǎ基礎(chǔ)的理論怔檩，鴿巢原理（也叫抽屜原理）蓄诽。這個(gè)原理本身很簡(jiǎn)單仑氛，它是說锯岖，如果有 10 個(gè)鴿巢嚎莉，有 11 只鴿子趋箩，那肯定有 1 個(gè)鴿巢中的鴿子數(shù)量多于 1 個(gè)叫确，換句話說就是竹勉，肯定有 2 只鴿子在 1 個(gè)鴿巢內(nèi)吓歇。有了鴿巢原理的鋪墊之后城看，我們?cè)賮砜床饽瑸槭裁垂Ｋ惴o法做到零沖突缘滥？我們知道轰胁，哈希算法產(chǎn)生的哈希值的長(zhǎng)度是固定且有限的。比如前面舉的 MD5 的例子朝扼，哈希值是固定的 128 位二進(jìn)制串赃阀，能表示的數(shù)據(jù)是有限的，最多能表示 2^128 個(gè)數(shù)據(jù)吟税，而我們要哈希的數(shù)據(jù)是無窮的凹耙。基于鴿巢原理肠仪，如果我們對(duì) 2^128+1 個(gè)數(shù)據(jù)求哈希值，就必然會(huì)存在哈希值相同的情況异旧。這里你應(yīng)該能想到，一般情況下荤崇，哈希值越長(zhǎng)的哈希算法，散列沖突的概率越低术荤。
2^128=340282366920938463463374607431768211456
比如下面兩串字符串經(jīng)過MD5加密之后產(chǎn)生的HASH值就是一樣的
不過，即便哈希算法存在散列沖突的情況每篷，但是因?yàn)楣Ｖ档姆秶艽螅瑳_突的概率極低子库，所以相對(duì)來說還是很難破解的。像 MD5，有 2^128 個(gè)不同的哈希值，這個(gè)數(shù)據(jù)已經(jīng)是一個(gè)天文數(shù)字了颜价，所以散列沖突的概率要小于 1/2^128专挪。如果我們拿到一個(gè) MD5 哈希值率寡，希望通過毫無規(guī)律的窮舉的方法，找到跟這個(gè) MD5 值相同的另一個(gè)數(shù)據(jù)，那耗費(fèi)的時(shí)間應(yīng)該是個(gè)天文數(shù)字。所以，即便哈希算法存在沖突航揉，但是在有限的時(shí)間和資源下塞祈，哈希算法還是很難被破解的。除此之外帅涂，沒有絕對(duì)安全的加密议薪。越復(fù)雜尤蛮、越難破解的加密算法，需要的計(jì)算時(shí)間也越長(zhǎng)斯议。比如 SHA-256 比 SHA-1 要更復(fù)雜产捞、更安全，相應(yīng)的計(jì)算時(shí)間就會(huì)比較長(zhǎng)哼御。密碼學(xué)界也一直致力于找到一種快速并且很難被破解的哈希算法坯临。我們?cè)趯?shí)際的開發(fā)過程中，也需要權(quán)衡破解難度和計(jì)算時(shí)間恋昼，來決定究竟使用哪種加密算法看靠。
應(yīng)用二：唯一標(biāo)識(shí)
如果要在海量的圖庫中，搜索一張圖是否存在液肌，我們不能單純地用圖片的元信息（比如圖片名稱）來比對(duì)挟炬，因?yàn)橛锌赡艽嬖诿Q相同但圖片內(nèi)容不同，或者名稱不同圖片內(nèi)容相同的情況嗦哆。那我們?cè)撊绾嗡阉髂匕妫课覀冎溃魏挝募谟?jì)算中都可以表示成二進(jìn)制碼串老速，所以粥喜，比較笨的辦法就是，拿要查找的圖片的二進(jìn)制碼串與圖庫中所有圖片的二進(jìn)制碼串一一比對(duì)烁峭。如果相同容客，則說明圖片在圖庫中存在。但是约郁，每個(gè)圖片小則幾十 KB缩挑、大則幾 MB，轉(zhuǎn)化成二進(jìn)制是一個(gè)非常長(zhǎng)的串鬓梅，比對(duì)起來非常耗時(shí)供置。有沒有比較快的方法呢？我們可以給每一個(gè)圖片取一個(gè)唯一標(biāo)識(shí)绽快，或者說信息摘要芥丧。比如，我們可以從圖片的二進(jìn)制碼串開頭取 100 個(gè)字節(jié)坊罢，從中間取 100 個(gè)字節(jié)续担，從最后再取 100 個(gè)字節(jié)，然后將這 300 個(gè)字節(jié)放到一塊活孩，通過哈希算法（比如 MD5）物遇，得到一個(gè)哈希字符串，用它作為圖片的唯一標(biāo)識(shí)。通過這個(gè)唯一標(biāo)識(shí)來判定圖片是否在圖庫中询兴，這樣就可以減少很多工作量乃沙。如果還想繼續(xù)提高效率，我們可以把每個(gè)圖片的唯一標(biāo)識(shí)诗舰，和相應(yīng)的圖片文件在圖庫中的路徑信息警儒，都存儲(chǔ)在散列表中。當(dāng)要查看某個(gè)圖片是不是在圖庫中的時(shí)候眶根，我們先通過哈希算法對(duì)這個(gè)圖片取唯一標(biāo)識(shí)蜀铲，然后在散列表中查找是否存在這個(gè)唯一標(biāo)識(shí)。如果不存在属百，那就說明這個(gè)圖片不在圖庫中蝙茶；如果存在，我們?cè)偻ㄟ^散列表中存儲(chǔ)的文件路徑诸老，獲取到這個(gè)已經(jīng)存在的圖片隆夯，跟現(xiàn)在要插入的圖片做全量的比對(duì)，看是否完全一樣别伏。如果一樣蹄衷，就說明已經(jīng)存在；如果不一樣厘肮，說明兩張圖片盡管唯一標(biāo)識(shí)相同愧口，但是并不是相同的圖片。
應(yīng)用三：數(shù)據(jù)校驗(yàn)
電驢這樣的 BT 下載軟件你肯定用過的类茂。我們知道耍属，BT下載的原理是基于 P2P 協(xié)議的。我們從多個(gè)機(jī)器上并行下載一個(gè) 2GB 的電影巩检，這個(gè)電影文件可能會(huì)被分割成很多文件塊（比如可以分成 100 塊厚骗，每塊大約 20MB）。等所有的文件塊都下載完成之后兢哭，再組裝成一個(gè)完整的電影文件就行了领舰。我們知道，網(wǎng)絡(luò)傳輸是不安全的迟螺，下載的文件塊有可能是被宿主機(jī)器惡意修改過的冲秽，又或者下載過程中出現(xiàn)了錯(cuò)誤，所以下載的文件塊可能不是完整的矩父。如果我們沒有能力檢測(cè)這種惡意修改或者文件下載出錯(cuò)锉桑，就會(huì)導(dǎo)致最終合并后的電影無法觀看，甚至導(dǎo)致電腦中毒∏现辏現(xiàn)在的問題是民轴，如何來校驗(yàn)文件塊的安全郑诺、正確、完整呢杉武？具體的 BT 協(xié)議很復(fù)雜，校驗(yàn)方法也有很多辙售，我來說其中的一種思路轻抱。我們通過哈希算法，對(duì) 100 個(gè)文件塊分別取哈希值旦部，并且保存在種子文件中祈搜。我們?cè)谇懊嬷v過，哈希算法有一個(gè)特點(diǎn)士八，對(duì)數(shù)據(jù)很敏感容燕。只要文件塊的內(nèi)容有一丁點(diǎn)兒的改變，最后計(jì)算出的哈希值就會(huì)完全不同婚度。所以蘸秘，當(dāng)文件塊下載完成之后，我們可以通過相同的哈希算法蝗茁，對(duì)下載好的文件塊逐一求哈希值醋虏，然后跟種子文件中保存的哈希值比對(duì)。如果不同哮翘，說明這個(gè)文件塊不完整或者被篡改了颈嚼，需要再重新從其他宿主機(jī)器上下載這個(gè)文件塊。
應(yīng)用四：散列函數(shù)
實(shí)際上饭寺，散列函數(shù)也是哈希算法的一種應(yīng)用阻课。散列函數(shù)是設(shè)計(jì)一個(gè)散列表的關(guān)鍵。它直接決定了散列沖突的概率和散列表的性能艰匙。不過限煞，相對(duì)哈希算法的其他應(yīng)用，散列函數(shù)對(duì)于散列算法沖突的要求要低很多员凝。即便出現(xiàn)個(gè)別散列沖突晰骑，只要不是過于嚴(yán)重，我們都可以通過開放尋址法或者鏈表法解決绊序。不僅如此硕舆，散列函數(shù)對(duì)于散列算法計(jì)算得到的值，是否能反向解密也并不關(guān)心骤公。散列函數(shù)中用到的散列算法抚官，更加關(guān)注散列后的值是否能平均分布，也就是阶捆，一組數(shù)據(jù)是否能均勻地散列在各個(gè)槽中凌节。除此之外钦听，散列函數(shù)執(zhí)行的快慢，也會(huì)影響散列表的性能倍奢，所以朴上，散列函數(shù)用的散列算法一般都比較簡(jiǎn)單，比較追求效率卒煞。
應(yīng)用五：負(fù)載均衡
我們知道痪宰，負(fù)載均衡算法有很多，比如輪詢畔裕、隨機(jī)衣撬、加權(quán)輪詢等。那如何才能實(shí)現(xiàn)一個(gè)會(huì)話粘滯（session sticky）的負(fù)載均衡算法呢扮饶？也就是說具练，我們需要在同一個(gè)客戶端上，在一次會(huì)話中的所有請(qǐng)求都路由到同一個(gè)服務(wù)器上甜无。最直接的方法就是扛点，維護(hù)一張映射關(guān)系表，這張表的內(nèi)容是客戶端 IP 地址或者會(huì)話 ID 與服務(wù)器編號(hào)的映射關(guān)系岂丘≌技客戶端發(fā)出的每次請(qǐng)求，都要先在映射表中查找應(yīng)該路由到的服務(wù)器編號(hào)元潘，然后再請(qǐng)求編號(hào)對(duì)應(yīng)的服務(wù)器畔乙。這種方法簡(jiǎn)單直觀，但也有幾個(gè)弊端：
- 如果客戶端很多翩概，映射表可能會(huì)很大牲距，比較浪費(fèi)內(nèi)存空間；
- 客戶端下線钥庇、上線牍鞠，服務(wù)器擴(kuò)容、縮容都會(huì)導(dǎo)致映射失效评姨，這樣維護(hù)映射表的成本就會(huì)很大难述；
如果借助哈希算法，這些問題都可以非常完美地解決吐句。我們可以通過哈希算法胁后，對(duì)客戶端 IP 地址或者會(huì)話 ID 計(jì)算哈希值，將取得的哈希值與服務(wù)器列表的大小進(jìn)行取模運(yùn)算嗦枢，最終得到的值就是應(yīng)該被路由到的服務(wù)器編號(hào)攀芯。 這樣，我們就可以把同一個(gè) IP 過來的所有請(qǐng)求文虏，都路由到同一個(gè)后端服務(wù)器上侣诺。
應(yīng)用六：數(shù)據(jù)分片
哈希算法還可以用于數(shù)據(jù)的分片殖演。我這里有兩個(gè)例子。
- 如何統(tǒng)計(jì)“搜索關(guān)鍵詞”出現(xiàn)的次數(shù)年鸳？
假如我們有 1T 的日志文件趴久，這里面記錄了用戶的搜索關(guān)鍵詞，我們想要快速統(tǒng)計(jì)出每個(gè)關(guān)鍵詞被搜索的次數(shù)搔确，該怎么做呢彼棍？我們來分析一下。這個(gè)問題有兩個(gè)難點(diǎn)妥箕，第一個(gè)是搜索日志很大，沒辦法放到一臺(tái)機(jī)器的內(nèi)存中更舞。第二個(gè)難點(diǎn)是畦幢，如果只用一臺(tái)機(jī)器來處理這么巨大的數(shù)據(jù)，處理時(shí)間會(huì)很長(zhǎng)缆蝉。針對(duì)這兩個(gè)難點(diǎn)宇葱，我們可以先對(duì)數(shù)據(jù)進(jìn)行分片，然后采用多臺(tái)機(jī)器處理的方法刊头，來提高處理速度黍瞧。具體的思路是這樣的：為了提高處理的速度，我們用 n 臺(tái)機(jī)器并行處理原杂。我們從搜索記錄的日志文件中印颤，依次讀出每個(gè)搜索關(guān)鍵詞，并且通過哈希函數(shù)計(jì)算哈希值穿肄，然后再跟 n 取模年局，最終得到的值，就是應(yīng)該被分配到的機(jī)器編號(hào)咸产。這樣矢否，哈希值相同的搜索關(guān)鍵詞就被分配到了同一個(gè)機(jī)器上。也就是說脑溢，同一個(gè)搜索關(guān)鍵詞會(huì)被分配到同一個(gè)機(jī)器上僵朗。每個(gè)機(jī)器會(huì)分別計(jì)算關(guān)鍵詞出現(xiàn)的次數(shù)，最后合并起來就是最終的結(jié)果屑彻。實(shí)際上验庙，這里的處理過程也是 MapReduce 的基本設(shè)計(jì)思想。 - 如何快速判斷圖片是否在圖庫中社牲？
如何快速判斷圖片是否在圖庫中壶谒？假設(shè)現(xiàn)在我們的圖庫中有 1 億張圖片，很顯然膳沽，在單臺(tái)機(jī)器上構(gòu)建散列表是行不通的汗菜。因?yàn)閱闻_(tái)機(jī)器的內(nèi)存有限让禀，而 1 億張圖片構(gòu)建散列表顯然遠(yuǎn)遠(yuǎn)超過了單臺(tái)機(jī)器的內(nèi)存上限。
我們同樣可以對(duì)數(shù)據(jù)進(jìn)行分片陨界，然后采用多機(jī)處理巡揍。我們準(zhǔn)備 n 臺(tái)機(jī)器，讓每臺(tái)機(jī)器只維護(hù)某一部分圖片對(duì)應(yīng)的散列表菌瘪。我們每次從圖庫中讀取一個(gè)圖片腮敌，計(jì)算唯一標(biāo)識(shí)，然后與機(jī)器個(gè)數(shù) n 求余取模俏扩，得到的值就對(duì)應(yīng)要分配的機(jī)器編號(hào)糜工，然后將這個(gè)圖片的唯一標(biāo)識(shí)和圖片路徑發(fā)往對(duì)應(yīng)的機(jī)器構(gòu)建散列表。
當(dāng)我們要判斷一個(gè)圖片是否在圖庫中的時(shí)候录淡，我們通過同樣的哈希算法捌木，計(jì)算這個(gè)圖片的唯一標(biāo)識(shí)，然后與機(jī)器個(gè)數(shù) n 求余取模嫉戚。假設(shè)得到的值是 k刨裆，那就去編號(hào) k 的機(jī)器構(gòu)建的散列表中查找。
現(xiàn)在彬檀，我們來估算一下帆啃，給這 1 億張圖片構(gòu)建散列表大約需要多少臺(tái)機(jī)器。
散列表中每個(gè)數(shù)據(jù)單元包含兩個(gè)信息窍帝，哈希值和圖片文件的路徑努潘。假設(shè)我們通過 MD5 來計(jì)算哈希值，那長(zhǎng)度就是 128 比特坤学，也就是 16 字節(jié)慈俯。文件路徑長(zhǎng)度的上限是 256 字節(jié)，我們可以假設(shè)平均長(zhǎng)度是 128 字節(jié)拥峦。如果我們用鏈表法來解決沖突贴膘，那還需要存儲(chǔ)指針，指針只占用 8 字節(jié)略号。所以刑峡，散列表中每個(gè)數(shù)據(jù)單元就占用 152 字節(jié)（這里只是估算，并不準(zhǔn)確）玄柠。
假設(shè)一臺(tái)機(jī)器的內(nèi)存大小為 2GB突梦，散列表的裝載因子為 0.75，那一臺(tái)機(jī)器可以給大約 1000 萬（2GB*0.75/152）張圖片構(gòu)建散列表羽利。所以宫患，如果要對(duì) 1 億張圖片構(gòu)建索引，需要大約十幾臺(tái)機(jī)器这弧。在工程中娃闲，這種估算還是很重要的虚汛，能讓我們事先對(duì)需要投入的資源、資金有個(gè)大概的了解皇帮，能更好地評(píng)估解決方案的可行性卷哩。
實(shí)際上，針對(duì)這種海量數(shù)據(jù)的處理問題属拾，我們都可以采用多機(jī)分布式處理将谊。借助這種分片的思路，可以突破單機(jī)內(nèi)存渐白、CPU 等資源的限制尊浓。
應(yīng)用七：分布式存儲(chǔ)
現(xiàn)在互聯(lián)網(wǎng)面對(duì)的都是海量的數(shù)據(jù)、海量的用戶纯衍。我們?yōu)榱颂岣邤?shù)據(jù)的讀取栋齿、寫入能力，一般都采用分布式的方式來存儲(chǔ)數(shù)據(jù)托酸，比如分布式緩存褒颈。
我們有海量的數(shù)據(jù)需要緩存柒巫，所以一個(gè)緩存機(jī)器肯定是不夠的励堡。于是，我們就需要將數(shù)據(jù)分布在多臺(tái)機(jī)器上堡掏。
該如何決定將哪個(gè)數(shù)據(jù)放到哪個(gè)機(jī)器上呢应结？我們可以借用前面數(shù)據(jù)分片的思想，即通過哈希算法對(duì)數(shù)據(jù)取哈希值泉唁，然后對(duì)機(jī)器個(gè)數(shù)取模鹅龄，這個(gè)最終值就是應(yīng)該存儲(chǔ)的緩存機(jī)器編號(hào)。但是亭畜，如果數(shù)據(jù)增多扮休，原來的 10 個(gè)機(jī)器已經(jīng)無法承受了，我們就需要擴(kuò)容了拴鸵，比如擴(kuò)到 11 個(gè)機(jī)器玷坠，這時(shí)候麻煩就來了。因?yàn)榫⒚辏@里并不是簡(jiǎn)單地加個(gè)機(jī)器就可以了八堡。原來的數(shù)據(jù)是通過與 10 來取模的。比如 13 這個(gè)數(shù)據(jù)聘芜，存儲(chǔ)在編號(hào)為 3 這臺(tái)機(jī)器上兄渺。但是新加了一臺(tái)機(jī)器中，我們對(duì)數(shù)據(jù)按照 11 取模汰现，原來 13 這個(gè)數(shù)據(jù)就被分配到 2 號(hào)這臺(tái)機(jī)器上了挂谍。
因此叔壤，所有的數(shù)據(jù)都要重新計(jì)算哈希值，然后重新搬移到正確的機(jī)器上凳兵。這樣就相當(dāng)于百新，緩存中的數(shù)據(jù)一下子就都失效了。所有的數(shù)據(jù)請(qǐng)求都會(huì)穿透緩存庐扫，直接去請(qǐng)求數(shù)據(jù)庫饭望。這樣就可能發(fā)生雪崩效應(yīng)，壓垮數(shù)據(jù)庫形庭。
所以铅辞，我們需要一種方法，使得在新加入一個(gè)機(jī)器后萨醒，并不需要做大量的數(shù)據(jù)搬移斟珊。這時(shí)候，一致性哈希算法就要登場(chǎng)了富纸。假設(shè)我們有 k 個(gè)機(jī)器囤踩，數(shù)據(jù)的哈希值的范圍是[0, MAX]。我們將整個(gè)范圍劃分成 m 個(gè)小區(qū)間（m 遠(yuǎn)大于 k）晓褪，每個(gè)機(jī)器負(fù)責(zé) m/k 個(gè)小區(qū)間堵漱。當(dāng)有新機(jī)器加入的時(shí)候，我們就將某幾個(gè)小區(qū)間的數(shù)據(jù)涣仿，從原來的機(jī)器中搬移到新的機(jī)器中勤庐。這樣，既不用全部重新哈希好港、搬移數(shù)據(jù)愉镰，也保持了各個(gè)機(jī)器上數(shù)據(jù)數(shù)量的均衡。一致性哈希算法的基本思想就是這么簡(jiǎn)單钧汹。除此之外丈探，它還會(huì)借助一個(gè)虛擬的環(huán)和虛擬結(jié)點(diǎn)，更加優(yōu)美地實(shí)現(xiàn)出來拔莱。
