一致性Hash算法在Memcached中的應(yīng)用

2019-11-14 13:32:11

字體：大中小

供稿：網(wǎng)友

前言

　　大家應(yīng)該都知道Memcached要想實(shí)現(xiàn)分布式只能在客戶端來完成,目前比較流行的是通過一致性hash算法來實(shí)現(xiàn).常規(guī)的方法是將server的hash值與server的總臺(tái)數(shù)進(jìn)行求余,即hash%N,這種方法的弊端是當(dāng)增減服務(wù)器時(shí),將會(huì)有較多的緩存需要被重新分配且會(huì)造成緩存分配不均勻的情況(有可能某一臺(tái)服務(wù)器分配的很多,其它的卻很少).

　　今天分享一種叫做”ketama”的一致性hash算法,它通過虛擬節(jié)點(diǎn)的概念和不同的緩存分配規(guī)則有效的抑制了緩存分布不均勻，并最大限度地減少服務(wù)器增減時(shí)緩存的重新分布。

實(shí)現(xiàn)思路

　　假設(shè)我們現(xiàn)在有N臺(tái)Memcached的Server,如果我們用統(tǒng)一的規(guī)則對(duì)memcached進(jìn)行Set,Get操作. 使具有不同key的object很均衡的分散存儲(chǔ)在這些Server上,Get操作時(shí)也是按同樣規(guī)則去對(duì)應(yīng)的Server上取出object,這樣各個(gè)Server之間不就是一個(gè)整體了嗎?

那到底是一個(gè)什么樣的規(guī)則?

　　如下圖所示,我們現(xiàn)在有5臺(tái)(A,B,C,D,E)Memcached的Server,我們將其串聯(lián)起來形成一個(gè)環(huán)形,每一臺(tái)Server都代表圓環(huán)上的一個(gè)點(diǎn),每一個(gè)點(diǎn)都具有唯一的Hash值,這個(gè)圓環(huán)上一共有2^32個(gè)點(diǎn).

那么該如何確定每臺(tái)Server具體分布在哪個(gè)點(diǎn)上? 這里我們通過”Ketama”的Hash算法來計(jì)算出每臺(tái)Server的Hash值,拿到Hash值后就可以對(duì)應(yīng)到圓環(huán)上點(diǎn)了.(可以用Server的ip地址作為Hash算法的Key.)

　　這樣做的好處是,如下圖當(dāng)我新增Server F時(shí),那么我只需要將hash值落在C和F之間的object從原本的D上重新分配到F上就可以了,其它的server上的緩存不需要重新分配,并且新增的Server也能及時(shí)幫忙緩沖其它Server的壓力.

　　到此我們已經(jīng)解決了增減服務(wù)器時(shí)大量緩存需要被重新分配的弊端.那該如何解決緩存分配不均勻的問題呢?因?yàn)楝F(xiàn)在我們的server只占據(jù)圓環(huán)上的6個(gè)點(diǎn),而圓環(huán)上總共有2^32個(gè)點(diǎn),這極其容易導(dǎo)致某一臺(tái)server上熱點(diǎn)非常多，某一臺(tái)上熱點(diǎn)很少的情況.

　　”虛擬節(jié)點(diǎn)”的概念很好的解決了這種負(fù)載不均衡的問題.通過將每臺(tái)物理存在的Server分割成N個(gè)虛擬的Server節(jié)點(diǎn)(N通常根據(jù)物理Server個(gè)數(shù)來定,這里有個(gè)比較好的閾值為250).這樣每個(gè)物理Server實(shí)際上對(duì)應(yīng)了N個(gè)虛擬的節(jié)點(diǎn). 存儲(chǔ)點(diǎn)多了,各個(gè)Server的負(fù)載自然要均衡一些.就像地鐵站出口一樣,出口越多,每個(gè)出口出現(xiàn)擁擠的情況就會(huì)越少.

　　代碼實(shí)現(xiàn):

//保存所有虛擬節(jié)點(diǎn)信息, key : 虛擬節(jié)點(diǎn)的hash key, value: 虛擬節(jié)點(diǎn)對(duì)應(yīng)的真實(shí)server        PRivate Dictionary<uint, string> hostDictionary = new Dictionary<uint, string>();        //保存所有虛擬節(jié)點(diǎn)的hash key, 已按升序排序        private uint[] ketamaHashKeys = new uint[] { };        //保存真實(shí)server主機(jī)地址        private string[] realHostArr = new string[] { };        //每臺(tái)真實(shí)server對(duì)應(yīng)虛擬節(jié)點(diǎn)個(gè)數(shù)        private int VirtualNodeNum = 250;        public KetamaVirtualNodeInit(string[] hostArr)        {            this.realHostArr = hostArr;            this.InitVirtualNodes();        }        /// <summary>        /// 初始化虛擬節(jié)點(diǎn)        /// </summary>        private void InitVirtualNodes()        {            hostDictionary = new Dictionary<uint, string>();            List<uint> hostKeys = new List<uint>();            if (realHostArr == null || realHostArr.Length == 0)            {                throw new Exception("不能傳入空的Server集合");            }            for (int i = 0; i < realHostArr.Length; i++)            {                for (int j = 0; j < VirtualNodeNum; j++)                {                    byte[] nameBytes = Encoding.UTF8.GetBytes(string.Format("{0}-node{1}", realHostArr[i], j));                    //調(diào)用Ketama hash算法獲取hash key                    uint hashKey = BitConverter.ToUInt32(new KetamaHash().ComputeHash(nameBytes), 0);                    hostKeys.Add(hashKey);                    if (hostDictionary.ContainsKey(hashKey))                    {                        throw new Exception("創(chuàng)建虛擬節(jié)點(diǎn)時(shí)發(fā)現(xiàn)相同hash key,請(qǐng)檢查是否傳入了相同Server");                    }                    hostDictionary.Add(hashKey, realHostArr[i]);                }            }            hostKeys.Sort();            ketamaHashKeys = hostKeys.ToArray();        }

一致性hash算法的分配規(guī)則

　　到此我們已經(jīng)知道了所有虛擬節(jié)點(diǎn)的Hash值, 現(xiàn)在讓我們來看下當(dāng)我們拿到一個(gè)對(duì)象時(shí)如何存入Server, 或是拿到一個(gè)對(duì)象的Key時(shí)該如何取出對(duì)象.

Set一個(gè)對(duì)象時(shí),先將對(duì)象的Key作為”Ketama”算法的Key,計(jì)算出Hash值后我們需要做下面幾個(gè)步驟.

1:首先檢查虛擬節(jié)點(diǎn)當(dāng)中是否有與當(dāng)前對(duì)象Hash值相等的,如有則直接將對(duì)象存入那個(gè)Hash值相等的節(jié)點(diǎn),后面的步驟就不繼續(xù)了.

2:如沒有,則找出第一個(gè)比當(dāng)前對(duì)象Hash值要大的節(jié)點(diǎn),(節(jié)點(diǎn)的Hash值按升序進(jìn)行排序,圓環(huán)上對(duì)應(yīng)按照順時(shí)針來排列),即離對(duì)象最近的節(jié)點(diǎn),然后將對(duì)象存入該節(jié)點(diǎn).

3:如果沒有找到Hash值比對(duì)象要大的Server,證明對(duì)象的Hash值是介于最后一個(gè)節(jié)點(diǎn)和第一個(gè)節(jié)點(diǎn)之間的,也就是圓環(huán)上的E和A之間.這種情況就直接將對(duì)象存入第一個(gè)節(jié)點(diǎn),即A.

　　代碼實(shí)現(xiàn):　　

     /// <summary>        /// 根據(jù)hash key 獲取對(duì)應(yīng)的真實(shí)Server        /// </summary>        /// <param name="hash"></param>        /// <returns></returns>        public string GetHostByHashKey(string key)        {            byte[] bytes = Encoding.UTF8.GetBytes(key);            uint hash = BitConverter.ToUInt32(new KetamaHash().ComputeHash(bytes), 0);            //尋找與當(dāng)前hash值相等的Server.             int i = Array.BinarySearch(ketamaHashKeys, hash);            //如果i小于零則表示沒有hash值相等的虛擬節(jié)點(diǎn)            if (i < 0)            {                //將i繼續(xù)按位求補(bǔ),得到數(shù)組中第一個(gè)大于當(dāng)前hash值的虛擬節(jié)點(diǎn)                i = ~i;                //如果按位求補(bǔ)后的i大于等于數(shù)組的大小,則表示數(shù)組中沒有大于當(dāng)前hash值的虛擬節(jié)點(diǎn)                //此時(shí)直接取第一個(gè)server                if (i >= ketamaHashKeys.Length)                {                    i = 0;                }            }            //根據(jù)虛擬節(jié)點(diǎn)的hash key 返回對(duì)應(yīng)的真實(shí)server host地址            return hostDictionary[ketamaHashKeys[i]];        }

Get一個(gè)對(duì)象,同樣也是通過”Ketama”算法計(jì)算出Hash值,然后與Set過程一樣尋找節(jié)點(diǎn),找到之后直接取出對(duì)象即可.

那么這個(gè)”Ketama”到底長(zhǎng)什么樣呢,讓我們來看看代碼實(shí)現(xiàn).

    /// <summary>    ///  Ketama hash加密算法    ///  關(guān)于HashAlgorithm參見MSDN鏈接    ///  http://msdn.microsoft.com/zh-cn/library/system.security.cryptography.hashalgorithm%28v=vs.110%29.aspx    /// </summary>    public class KetamaHash : HashAlgorithm    {        private static readonly uint FNV_prime = 16777619;        private static readonly uint offset_basis = 2166136261;        protected uint hash;        public KetamaHash()        {            HashSizeValue = 32;        }        public override void Initialize()        {            hash = offset_basis;        }        protected override void HashCore(byte[] array, int ibStart, int cbSize)        {            int length = ibStart + cbSize;            for (int i = ibStart; i < length; i++)            {                hash = (hash * FNV_prime) ^ array[i];            }        }        protected override byte[] HashFinal()        {            hash += hash << 13;            hash ^= hash >> 7;            hash += hash << 3;            hash ^= hash >> 17;            hash += hash << 5;            return BitConverter.GetBytes(hash);        }    }