使用.Net Core實現FNV分散式hash一致性演算法

  • 2019 年 10 月 4 日
  • 筆記

# 使用.Net Core實現FNV分散式hash一致性演算法

說到FNV哈希演算法不得不提Memcached，我們先簡單介紹一下Memcached。

# Memcached

Memcached分為客戶端與服務端，Memcached是服務端，服務端本身不提供分散式實現，只是一個單獨的k-v快取；Memcached的分散式是在客戶端類庫中實現的，也就是說你可以根據自己的需要實現不同的分散式方案，不一定非得使用FNV哈希演算法。

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

# FNV分散式hash演算法實現

如果你還不了解FNV哈希演算法，可以先看一下我之前的文章。

# FNV1演算法實現

程式碼實現上我將參考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的實現和FNV哈希演算法來實現FNV1a演算法。我有一個幫助類MicroFx.Cryptography 分別實現了FNV1和FNV1a的32bit、64bit演算法版本。

# 為什麼使用FNV演算法實現hash一致性

無論是分散式演算法還是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）

VirMach 便宜 VPS

QNews

QNews