原文

Felix Chern: 設計高效能的Hash Table(一)

心得

還記得當初在寫 Consistent Hashing 的時候,一直不願意拿人家寫好的 Hash Function 來改,硬要自己寫一個.

結果發現寫出來的 Hashing 一直出問題.才知道原來 Hash Function 是實作 Consistent Hashing 的一個重點.

這一篇文章有了一些基本對於 Hash Function 的介紹,也把幾個好用的 Hash Function 一一的列出來.

其中包括了最近被移到了 Google 的 “highwayhash”

或是之前有介紹過在 Uber/ringpop 下作為 Consistent Hashing 的 farmhash

這篇文章相當推薦,原因如下:

  1. 作者 (Felix Chern) 目前似乎在 Google 工作,部落格文章都相當有深度.
  2. 有 Hash Function 列出的清單並且有簡單的介紹.

參考:

  • ringpop 是 Uber 的去中心化 App :
  • 這篇文章有下集,在這裡

關於實作與相關測試:

其實 Damian Gryski 實作了不少 Hash Function 的 Go 套件

HighWay Hash

其 Benchmark 如下:

 ~/s/g/s/g/d/go-highway   master  go test -bench=.             六  4/29 01:31:56 2017
BenchmarkHighway8-8    	50000000	        26.3 ns/op	 304.36 MB/s
BenchmarkHighway16-8   	50000000	        26.7 ns/op	 599.24 MB/s
BenchmarkHighway40-8   	50000000	        29.7 ns/op	1345.35 MB/s
BenchmarkHighway64-8   	50000000	        33.3 ns/op	1924.53 MB/s
BenchmarkHighway1K-8   	10000000	       137 ns/op	7452.07 MB/s
BenchmarkHighway8K-8   	 2000000	       873 ns/op	9378.40 MB/s

Farm Hash

其 Benchmark 如下:

 !  ~/s/g/s/g/d/go-farm   master  go test -bench=.    257ms  六  4/29 01:30:43 2017
BenchmarkHash32-8    	20000000	       100 ns/op
BenchmarkHash64-8    	20000000	        58.2 ns/op
BenchmarkHash128-8   	20000000	       123 ns/op

xxHash

這不是 Damian Gryski 實作的,是由 LiftOff Caleb Spare 但是做得很好而且也有被 InfluxDB 使用喔.

xxHash 是選定 64bit 輸出的通用 Hash Function ,使用範圍廣泛而且速度快.

結語:

本來想只是寫個簡單的推薦文,後來決定來跑跑看每個 Hash Function 的效能評比.跑完之後,又想去偷看是不是裡面都沒有使用除法.

發現其實 Hash Function 主要還是針對不同 CPU 的優化,讓他們的速度能夠更快.處理的資料類型能夠更多.

P.S.:

  • 其實 Damian Gryski 把幾乎所有 Google 出品的 Hash Function 都重寫成 Golang 版本.

  • Google 出了好幾個的 Hash Function 讓我覺得大公司對於 Hash Function 的注意.


Evan

Attitude is everything