歡迎光臨
每天分享高質量文章

淺談一致性Hash原理及應用

在講一致性Hash之前我們先來討論一個問題。

問題:現在有億級用戶,每日產生千萬級訂單,如何將訂單進行分片分表?

  小A:我們可以按照手機號的尾數進行分片,同一個尾數的手機號寫入同一片/同一表中。

  大佬:我希望通過會員ID來查詢這個會員的所有訂單信息,按照手機號分片/分表的話,前提是需要該用戶的手機號保持不變,並且在查詢訂單串列時需要提前查詢該用戶的手機號,利用手機號尾數不太合理。

  小B:按照大佬的思路,我們需要找出一個唯一不變的屬性來進行分片/分表。

  大佬:迷之微笑~

  小B:(信心十足)會員在我們這邊保持不變的就是會員ID(int),我們可以通過會員ID的尾數進行分片/分表

  小C:盡然我們可以用會員ID尾數進行分片/分表,那就用取模的方式來進行分片/分表,通過取模的方式可以達到很好的平衡性。示意圖如下:

 

  大佬:嗯嗯嗯,在不考慮會員冷熱度的情況下小B和小C說的方案絕佳;但是往往我們的會員有冷熱度和僵屍會員,通過取模的方式往往會出現某個分片資料異常高,部分分片資料異常低,導致平衡傾斜。示意圖如下:

  

  大佬:當出現某個分片/分表達到極限時我們需要添加片/表,此時發現我們無法正常添加片/表。因為一旦添加片/或表的時候會導致絕大部分資料錯亂,按照原先的取模方式是無法正常獲取資料的。示意圖如下

  

添加分片/分表前4,5,6會員的訂單分別儲存在A,B,C上,當添加了片/表的時候在按照(會員ID%N)方式取模去取資料4,5,6會員的訂單資料時發現無法取到訂單資料,因為此時4,5,6這三位會員資料分佈存在了D,E,A上,具體示意圖如下:

  

  大佬:所以通過取模的方式也會存在缺陷;好了接下來我們來利用一致hash原理的方式來解決分片/分表的問題。

 首先什麼是一致性哈希演算法?一致性哈希演算法(Consistent Hashing Algorithm)是一種分佈式演算法,常用於負載均衡。Memcached client也選擇這種演算法,解決將key-value均勻分配到眾多Memcached server上的問題。它可以取代傳統的取模操作,解決了取模操作無法應對增刪Memcached Server的問題(增刪server會導致同一個key,在get操作時分配不到資料真正儲存的server,命中率會急劇下降)。

  還以上述問題為例,假如我們有10片,我們利用Hash演算法將每一片算出一個Hash值,而這些Hash點將被虛擬分佈在Hash圓環上,理論視圖如下:

  

按照順時針的方向,每個點與點之間的弧形屬於每個起點片的容量,然後按照同樣的Hash計算方法對每個會員ID進行Hash計算得出每個Hash值然後按照區間進行落片/表,以保證資料均勻分佈。

如果此時需要在B和C之間新增一片/表(B1)的話,就不會出現按照取模形式導致資料幾乎全部錯亂的情況,僅僅是影響了(B1,C)之間的資料,這樣我們清洗出來也就比較方便,也不會出現資料大批量

癱瘓。

但是如果我們僅僅是將片/表進行計算出Hash值之後,這些點分佈並不是那麼的均勻,比如就會下麵的這種情況,導致區間傾斜。如圖

這個時候虛擬節點就此誕生,下麵讓我們來看一下虛擬節點在一致性Hash中的作用。當我們在Hash環上新增若干個點,那麼每個點之間的距離就會接近相等。按照這個思路我們可以新增若干個

片/表,但是成本有限,我們通過複製多個A、B、C的副本({A1-An},{B1-Bn},{C1-Cn})一起參與計算,按照順時針的方向進行資料分佈,按照下圖示意:

  

此時A=[A,C1)&[A1,C2)&[A2,B4)&[A3,A4)&[A4,B1);B=[B,A1)&[B2,C)&[B3,C3)&[B4,C4)&[B1,A);C=[C1,B)&[C2,B2)&[C,B3)&[B3,C3)&[C4,A3);由圖可以看出分佈點越密集,平衡性約好。

using System;

using System.Collections.Generic;

using System.Data.HashFunction;

using System.Data.HashFunction.xxHash;

using System.Linq;

namespace HashTest

{

public class ConsistentHash

{

///

        /// 虛擬節點數

        ///

        private static readonly int VirturalNodeNum = 10;

        ///

        /// 服務器IP

        ///

        private static readonly string[] Nodes = { “192.168.1.1”, “192.168.1.2”, “192.168.1.3”};

        ///

        /// 按照一致性Hash進行分組

        ///

        private static readonly IDictionary ConsistentHashNodes = new Dictionary();

        private static uint[] _nodeKeys = null;

        public static void ComputeNode()

        {

            foreach (var node in Nodes)

            {

                AddNode(node);

            }

        }

        private static void AddNode(string node)

        {

            for (int i = 0; i < VirturalNodeNum; i++)

            {

                var key = node + “:” + i;

                var hashValue = ComputeHash(key);

                if (!ConsistentHashNodes.ContainsKey(hashValue))

                {

                    ConsistentHashNodes.Add(hashValue, node);

                }

            }

            _nodeKeys = ConsistentHashNodes.Keys.ToArray();

        }

        private static uint ComputeHash(string virturalNode)

        {

            var hashFunction = xxHashFactory.Instance.Create();

            var hashValue = hashFunction.ComputeHash(virturalNode);

            return BitConverter.ToUInt32(hashValue.Hash, 0);

        }

        public static string Get(string item)

        {

            var hashValue = ComputeHash(item);

            var index = GetClockwiseNearestNode(hashValue);

            return ConsistentHashNodes[_nodeKeys[index]];

        }

        private static int GetClockwiseNearestNode(uint hash)

        {

            int begin = 0;

            int end = _nodeKeys.Length – 1;

            if (_nodeKeys[end] < hash || _nodeKeys[0] > hash)

            {

                return 0;

            }

            while ((end – begin) > 1)

            {

                var mid = (end + begin) / 2;

                if (_nodeKeys[mid] >= hash) end = mid;

                else begin = mid;

            }

            return end;

        }

    }

}

原文地址:https://www.cnblogs.com/xialihua1023/p/10304932.html

赞(0)

分享創造快樂