使用.Net Core實作FNV分布式hash一緻性算法使用.Net Core實作FNV分布式hash一緻性算法

目錄

• 使用.Net Core實作FNV分布式hash一緻性算法
  • Memcached
  • FNV分布式hash算法實作
    • FNV1算法實作
  • 為什麼使用FNV算法實作hash一緻性

說到

FNV雜湊演算法

不得不提Memcached，我們先簡單介紹一下Memcached。

Memcached

分為用戶端與服務端，

Memcached

是服務端，服務端本身不提供分布式實作，隻是一個單獨的k-v緩存；Memcached的分布式是在用戶端類庫中實作的，也就是說你可以根據自己的需要實作不同的分布式方案，不一定非得使用

。

Memcached通過FNV算法實作了服務的分布式，并通過引入虛拟節點的辦法盡量是伺服器分布的更均勻。已經有很多文章在介紹Memcached的分布式實作原理了，是以我就不那麼多廢話了。

如果你還不了解

，可以先看一下我之前的文章，在那裡我摘錄了wiki上的

實作公式。

代碼實作上我将參考MD5算法的實作來編寫FNV1算法：

1. 首先，我将建立一個FNV1類，該類需要實作HashAlgorithm，之是以實作HashAlgorithm，是因為該抽象類定義了hash算法通用的接口，這樣也可以使我們的實作與.net架構內建的更好，當然如果你不喜歡也可以不實作HashAlgorithm，就當是寫了一個獨立的幫助類。
2. 然後，我們重寫Create方法，這裡我們将建立一個FNV1類的執行個體
3. 最後，我們去實作這個FNV1類

   所有實作代碼如下：

//首先我将建立FNV1類 
public abstract class FNV1 : HashAlgorithm
{
    //重寫隐藏HashAlgorithm的Create方法
    public static new FNV1 Create()
    {
        return new Implementation();
    }
    //下面FNV1的實作我們完全是套用的公式沒有什麼好講的
    private sealed class Implementation : FNV1
    {
        private const uint OFFSETBASIS = 2166136261;
        private const uint PRIME = 16777619;
        private uint _hash;
        public override void Initialize()
        {
            _hash = OFFSETBASIS;
        }
        protected override void HashCore(byte[] array, int ibStart, int cbSize)
        {
            int end = ibStart + cbSize;
            for (var index = ibStart; index < end; index++)
            {
            _hash *= PRIME;
            _hash ^= array[index];
            }
        }
        protected override byte[] HashFinal()
        {
            return BitConverter.GetBytes(_hash);
        }
    }
}


## 使用方法

var bytes=Encoding.UTF8.GetBytes("Test");
var hashBytes=FNV1.Create().ComputerHash(bytes);
var hashValue=BitConverter.ToUInt32(hashBytes);           

FNV其實還有FNV1a算法，與FNV1有些許的差別，這裡我就不一一實作了，你可以參考FNV1的實作和

來實作FNV1a算法。我有一個幫助類

MicroFx.Cryptography

分别實作了FNV1和FNV1a的32bit、64bit算法版本。

無論是分布式算法還是hash一緻性算法都不隻有一種或幾種實作方案，但Memached為什麼會選擇FNV算法，而不是md5，不是sha呢？我有自己的認識。

1. 我們先看幾行代碼，分别使用MD5，sha，FNV算法計算一個

   Test

   字元串的哈希值，然後對比hash結果中數組的長度

   var bytes = Encoding.UTF8.GetBytes("Test");
   var shabytes = SHA1.Create().ComputeHash(bytes); //shabytes長度為20，及160bit
   var md5bytes=MD5.Create().ComputeHash(bytes);    //md5bytes長度為16，及128bit
   var fnvbytes = FNV1a.Create().ComputeHash(bytes); //fnvbytes長度為4，及32bit           

   算法	取值範圍
   sha1	[0,2^160-1]
   md5	[0,2^128-1]
   fnv	[0,2^32-1]

   從上表我們可以看出，FNV的取值範圍最小，如果将區間内的每一個整數看做一個Memcached服務端節點，那麼FNV容納的數量最少，但相對于實際的環境下已經足夠多了，這樣我們每次在計算一台伺服器屬于哪個節點的時候速度上會比md5、sha1快很多。
2. FNV的32bit計算結果值剛好是一個uint類型，.net core最大支援ulong也就是uint64，再大的話就需要我們自己實作，是以這也是選擇FNV的一個原因。（或許我這裡不應該拿.net舉例，但實際常用的進階語言最大也是64bit）