哈希演算法是程式開發程序中最廣泛接觸到的的演算法之一，典型的應用有安全加密、資料校驗、唯一標識、散列函式、負載均衡、資料分片、分布式存盤，前些天遇到用一致性哈希（哈希環）的場景，不過我細想一下，對這個知識點好像了解過，但是又沒太深印象，說不出具體是什么原理，怎么用，有哪些注意的地方，本文簡單記錄，希望也能給其他人作為初步了解所用，
1.誕生背景解決了怎么樣的問題
一個常見的結論是在需要均勻的解決資料分布場景時通過引入一致性哈希演算法可以很好解決此類問題，一致性哈希誕生，是麻省理工學院在1997年提出的一種分布式哈希（DHT）實作演算法，其設計目標是為了解決因特網中的熱點（Hot Spot）問題，將來自網路上的流量動態的均勻分發到不同的服務器處理，處理大量資料時很可能是遇到類似這樣的難點：
- 1.處理檔案很大單臺機器記憶體受限無法計算；
- 2.如果單臺機器處理這樣大量資料處理耗時很大；
為了突破單機記憶體，cup資源限制，借助分片思路，先切分資料，再利用多臺機器提高處理速度，最后在合并起來得到最終結果，這個處理程序也是MapReduce的基本思想，不過再思考一下，僅僅是解決上面問題話，一個普通的哈希演算法就能解決；為什么會要引入一致性哈希演算法呢？
當資料增多，需要擴容機器時，直接加上新機器，那么所有資料會遇到一個問題，就是之前哈希值不對了，通常哈希值計算和機器數量有關，最簡單就是對機器數量取模，當數量變化是需要重新計算哈希值，然后搬移資料到正確的機器上，用在快取場景就相當于所有快取失效，請求資料穿透快取，直接請求資料庫，這樣就很容易發生雪崩效應，所以就需要一種新方法，讓加入機器后，不需要做大量資料遷移，
2.原理介紹
一致性哈希原理介紹
一致性哈希是一種用于分布式系統中資料分片和負載均衡的演算法，它的核心思想是將資料根據哈希值映射到一個環形空間中，然后將節點也映射到環上，當需要查找某個資料時，先計算該資料的哈希值，然后沿著環的順時針方向找到第一個大于等于該哈希值的節點，即為該資料所在的節點，這樣可以將資料均勻地分布在各個節點上，并且在節點動態添加或洗掉時，只需要重新映射該節點的哈希值，而不需要重新映射所有資料的哈希值，從而避免了資料遷移的開銷，
一致性哈希演算法的優點是具有高度的可擴展性和容錯性，能夠自動適應節點的動態變化，同時保證資料的一致性和負載均衡，它被廣泛應用于分布式快取、分布式資料庫、負載均衡等領域，
Powered by ChatGPT
再借用大牛們對一致性哈希原理介紹的，通過hash函式映射到一個哈希環上，哈希環可以理解為一個連續變好的回圈鏈表，一般會用32位的哈希值，可以映射2^32個值，
假設key1和key2經過計算都命中哈希環上一個機器節點0，此時新加入一個節點n，節點n接管了部分原來歸屬于節點0的區域（只有key2在其中），此時再次訪問key1和key2，只會有key2因為變更節點，需要重新遷移資料，
3.一致性哈希優點
從上面原理介紹，我們可以很容易看到一致性哈希演算法在可伸縮性的優點，我們簡單模擬下看看是否解決之前的雪崩問題，另外這里我們再討論下它均衡性優點，
我們模擬一下當機器B故障，需要在服務串列里摘除機器B，我們直接將故障機器B從哈希環上移除，原來歸屬于機器B的資料按照一致性哈希規則，應該被快取到哈希環上下一個機器節點例如機器C，其他資料并不會因此產生變化，只有一部分快取失敗需要重新構建，從而不至于所有全部快取失效導致的雪崩效應問題，
不過就像買家秀和買家秀的巨大差距一樣，通常理想很豐滿，現實很骨感，只是按照上述定義，哈希環上機器映射大概率是沒法均分的，快取物件很大可能被集中在某一臺機器上，分布極度不均，產生hash環的偏斜，極端情況下，仍然可能引起系統崩潰，所以一致性哈希演算法中使用‘虛擬節點’解決這個問題，
所謂‘虛擬節點’就是有實際節點虛擬復制而來的節點，填充在哈希環上，讓機器盡量多，均勻的出現在哈希環上，所以通常是一個實際節點對應多個虛擬節點，有虛擬節點加入后再看哈希環，我們就可以達到良好的均衡性，減少哈希環偏斜帶來的影響，快取也就被均勻分布概率越大，
4.總結和思考
一致性哈希主要解決資料分布場景，它存在這樣的優點：
- 1.可伸縮性
- 2.負載平衡 （將節點與Hash演算法解耦，而且通過交錯分配虛擬節點的方式解決了負載不均衡導致的快取熱點問題）
缺點（有個觀點是用錯了場景才是缺陷，用對了，那是特性）： - 1.key值通過hash演算法算出，映射固定，不靈活，而且節點數量變化時虛擬節點數量也會變化，這種耦合限制哈希演算法進一步優化
- 2.資料分布均勻，不代表流量和負載的均勻，熱點key導致節點實際表現不均勻
5.參考資料
https://time.geekbang.org/column/article/67388
https://www.wikiwand.com/zh-cn/一致哈希
https://juejin.cn/post/7134656152452726792
https://www.geeksforgeeks.org/consistent-hashing-in-distributed-systems/
https://www.zsythink.net/archives/1182
https://blog.csdn.net/randompeople/article/details/103723839
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/552328.html
標籤：其他
上一篇：NES 系統架構
下一篇：返回列表