Go 中祕而不宣的數據結構 maphash：性能之王

哈希算法 (也稱散列算法) 是一種將任意長度的輸入數據轉換成固定長度輸出的數學算法。

Hash 算法的應用場景

Hash 算法常常用在以下的場景中：

1. 數據完整性驗證

• 可以爲文件生成唯一的哈希值，用於檢測文件是否被篡改

• 常見場景如軟件下載時的 MD5 校驗、區塊鏈中的數據驗證

1. 密碼存儲安全

• 不直接存儲用戶密碼原文, 而是存儲密碼的哈希值

• 即使數據庫被攻破, 黑客也無法直接獲取原始密碼

• 常用的密碼哈希算法有 bcrypt、PBKDF2 等

1. 數據結構優化

• 哈希表 (Hash Table) 使用哈希函數進行快速查找

• 能夠將查找時間複雜度從 O(n) 優化到 O(1)

• 在字典、緩存等場景廣泛應用

1. 數字簽名

• 在數字簽名中, 先對消息進行哈希計算

• 再對哈希值進行加密, 可以確保消息的完整性和來源

1. 去重和快速比較

• 可以快速判斷兩個文件或數據是否相同

• 用於文件去重、判斷重複內容等場景

1. 負載均衡

• 使用哈希算法可以將請求均勻分配到不同服務器

• 實現簡單且負載相對均衡

需要注意的重要特性：

• 哈希算法是單向的, 無法從哈希值反推原始數據

• 即使輸入數據只改變一位, 輸出的哈希值也會顯著不同

• 優秀的哈希算法應當儘量避免哈希衝突 (不同輸入得到相同輸出)

本文中哈希、hash 用詞混用，勿怪。

常見的 Hash 算法

1H9ItF

這些算法的安全性是不一樣的，像我們常見的 MD5 算法，山東大學王小云教授在坐月子期間成功破解 MD5、HAVAL-128、 MD4 和 RIPEMD 算法，王小云教授發現，可以很快的找到 MD5 的 “碰撞”，就是兩個文件可以產生相同的 “指紋”，後來還破解了 SHA-1。

Go 標準庫以及擴展庫提供了常用的 Hash 算法，如下表所列：

0bRGgy

自 Go 1.19 版本以後, hash 包中又增加了 maphash 一種新的哈希算法。

這個 maphash 本來屬於祕而不宣的一種 hash 算法，用在內部的 map 的 key 的 hash 計算中，性能優良，一些庫爲了提升性能，偷偷的引用這個實現，所以 Go 團隊乾脆把它公開了，放在了 hash 包中。

我在項目 hash-bench[1] 中評估了各種 Hash 算法的性能，maphash 無愧於性能之王。

“

如果你對 hash 算法很在意，或者你的項目中發現 hash 算法是瓶頸，我建議你在你自己的環境中測試，並且針對你的場景進行仔細的 benchmark 對比。正如這些算法的分類一樣，有些算法是偏重於安全的，有些算法偏重於速度，有些算法很容易產生碰撞，有些卻儘量避免。大家根據具體的場景選擇不同的 hash 算法，不能武斷的斷言某種 hash 算法比另外一種 hash 算法好。

性能測試

因爲算法非常多，代碼就非常長，我就不列出所有的代碼了，這裏值列出主要的代碼：

var n int64
var testBytes []byte

func BenchmarkHash(b *testing.B) {
 sizes := []int64{32, 64, 128, 256, 512, 1024}
 for _, n = range sizes {
  testBytes = make([]byte, n)
  readN, err := rand.Read(testBytes)
  if readN != int(n) {
   panic(fmt.Sprintf("expect %d but got %d", n, readN))
  }
  if err != nil {
   panic(err)
  }

  b.Run(fmt.Sprintf("Sha1-%d", n), benchmarkSha1)
  b.Run(fmt.Sprintf("Sha256-%d", n), BenchmarkSha256)
  b.Run(fmt.Sprintf("Sha256SIMD-%d", n), BenchmarkSha256SIMD)
  b.Run(fmt.Sprintf("Sha512-%d", n), BenchmarkSha512)
  b.Run(fmt.Sprintf("MD5-%d", n), BenchmarkMD5)
  b.Run(fmt.Sprintf("Fnv-%d", n), BenchmarkFnv)
  b.Run(fmt.Sprintf("Adler32-%d", n), BenchmarkAdler32)
  b.Run(fmt.Sprintf("Crc32-%d", n), BenchmarkCrc32)
  b.Run(fmt.Sprintf("CityHash-%d", n), BenchmarkCityhash)
  b.Run(fmt.Sprintf("FarmHash-%d", n), BenchmarkFarmhash)
  b.Run(fmt.Sprintf("Farmhash_dgryski-%d", n), BenchmarkFarmhash_dgryski)
  b.Run(fmt.Sprintf("Murmur3-%d", n), BenchmarkMurmur3)
  b.Run(fmt.Sprintf("Highwayhash-%d", n), BenchmarkHighwayhash)
  b.Run(fmt.Sprintf("XXHash64-%d", n), BenchmarkXXHash64)
  b.Run(fmt.Sprintf("XXHash64_ASM-%d", n), BenchmarkXXHash64_ASM)
  b.Run(fmt.Sprintf("MapHash64-%d", n), BenchmarkMapHash64)
  b.Run(fmt.Sprintf("StdMapHash64-%d", n), BenchmarkStdMapHash64)
  b.Run(fmt.Sprintf("ChibiHash64-%d", n), BenchmarkChibiHash)
  b.Run(fmt.Sprintf("Blake2b-%d", n), BenchmarkBlake2b)
  fmt.Println()
 }

}

func benchmarkSha1(b *testing.B) {
 x := sha1.New()

 b.SetBytes(n)
 b.ResetTimer()

 for i := 0; i < b.N; i++ {
  x.Reset()
  x.Write(testBytes)
  _ = x.Sum(nil)
 }
}

... // 其它hash算法

這裏寫了一個通用的 hash benchmark 函數，用來測試不同 hash 算法在不同大小數據 (32, 64, 128, 256, 512, 1024字節) 下的性能。

同時將 benchmark 結果輸出到一個 csv 文件，便於生成圖表。

我找了一臺 Linux/AMD64 的服務器，進行了測試，方便測試 CPU 的高級性能。

• Intel(R) Xeon(R) Gold 6271C CPU @ 2.60GHz, 96 核

• Linux 5.10.0-1.0.0.40

• 796GB 內存

以 hash 1024 個字節爲例 (其它字節性能差不多)，以下是各種 hash 算法的性能對比 (包括吞吐)：

BenchmarkHash/Sha1-1024-96                      797005       1471 ns/op  695.96 MB/s
BenchmarkHash/Sha256-1024-96                    377248       3172 ns/op  322.82 MB/s
BenchmarkHash/Sha256SIMD-1024-96                378414       3176 ns/op  322.46 MB/s
BenchmarkHash/Sha512-1024-96                    507495       2353 ns/op  435.16 MB/s
BenchmarkHash/MD5-1024-96                       725233       1648 ns/op  621.33 MB/s
BenchmarkHash/Fnv-1024-96                       911083       1312 ns/op  780.48 MB/s
BenchmarkHash/Adler32-1024-96                  2734160        434.1 ns/op 2359.04 MB/s
BenchmarkHash/Crc32-1024-96                   15229868         78.35 ns/op 13069.26 MB/s
BenchmarkHash/CityHash-1024-96                 1774196        676.4 ns/op 1513.94 MB/s
BenchmarkHash/FarmHash-1024-96                 2465469        487.2 ns/op 2101.90 MB/s
BenchmarkHash/Farmhash_dgryski-1024-96        10912843        109.9 ns/op 9316.16 MB/s
BenchmarkHash/Murmur3-1024-96                  6018717        199.2 ns/op 5141.23 MB/s
BenchmarkHash/Highwayhash-1024-96              9591049        125.0 ns/op 8188.84 MB/s
BenchmarkHash/XXHash64-1024-96                11106692        108.0 ns/op 9477.11 MB/s
BenchmarkHash/XXHash64_ASM-1024-96            12232465         98.09 ns/op 10439.81 MB/s
BenchmarkHash/MapHash64-1024-96               25519408         47.02 ns/op 21777.23 MB/s
BenchmarkHash/StdMapHash64-1024-96             9233738        130.2 ns/op 7864.52 MB/s
BenchmarkHash/ChibiHash64-1024-96              2550945        470.3 ns/op 2177.50 MB/s
BenchmarkHash/Blake2b-1024-96                   952615       1258 ns/op  814.09 MB/s

這裏面MapHash明顯是最優秀的一種哈希算法:47.02 ns/op, 每秒可以處理21777.23 MB的數據。

MapHash算法就是 Go 運行時中爲 Map 的哈希所實現的 hash 算法。即使標準庫暴露了這個算法，但是還是沒有直接通過 hack 的方式使用它性能更高。

maphash(runtime·memhash) 算法

在 Go 運行時中 MapHash 算法叫做memhash, 我想它暴露出來叫做 MapHash 算法主要是因爲它最初就是爲了 map 使用的吧。

我在 benchmark 代碼通過下面的 hack 方式使用了 maphash 算法，如果你在項目中使用它，你也可以這樣使用：

//go:noescape
//go:linkname memhash runtime.memhash
func memhash(p unsafe.Pointer, h, s uintptr) uintptr

type stringStruct struct {
 str unsafe.Pointer
 len int
}

func MemHash(data []byte) uint64 {
 ss := (*stringStruct)(unsafe.Pointer(&data))
 return uint64(memhash(ss.str, 0, uintptr(ss.len)))
}

這裏我們不考慮安全和碰撞，總是把種子設置爲 0。

你也看到了，這個算法實際是在runtime.memhash中實現的。找到它：

// memhash should be an internal detail,
// but widely used packages access it using linkname.
// Notable members of the hall of shame include:
//   - github.com/aacfactory/fns
//   - github.com/dgraph-io/ristretto
//   - github.com/minio/simdjson-go
//   - github.com/nbd-wtf/go-nostr
//   - github.com/outcaste-io/ristretto
//   - github.com/puzpuzpuz/xsync/v2
//   - github.com/puzpuzpuz/xsync/v3
//   - github.com/authzed/spicedb
//   - github.com/pingcap/badger
//
// Do not remove or change the type signature.
// See go.dev/issue/67401.
//
//go:linkname memhash
func memhash(p unsafe.Pointer, h, s uintptr) uintptr

func memhash32(p unsafe.Pointer, h uintptr) uintptr

func memhash64(p unsafe.Pointer, h uintptr) uintptr

文件不太好找，在src/runtime/alg.go文件中。注意有趣的註釋，被點名的使用了這個函數的庫。Go 團隊正在推進拒絕 hack 使用這些內部函數的go:linkname方式，但是當前 Go 生態圈的庫有很多都這麼使用，不好搞。

很明顯，這個實現是通過 C 或者 ASM 實現的。找到它。

具體都在src/runtime/asm_xxx.s文件中，比如src/runtime/asm_amd64.s文件中有memhash的實現：

TEXT runtime·memhash<ABIInternal>(SB),NOSPLIT,$0-32
	// AX = ptr to data
	// BX = seed
	// CX = size
	CMPB	runtime·useAeshash(SB), $0
	JEQ	noaes
	JMP	aeshashbody<>(SB)
noaes:
	JMP	runtime·memhashFallback<ABIInternal>(SB)

可以看到，如果 CPU 支持 Aes 指令，它會使用 Aes 指令來實現 hash 算法，否則會使用runtime·memhashFallback純內存算法的函數實現。

也正是使用了 Aes 指令，所以 maphash 的性能非常高，無愧於性能之王。

AES 指令集（AES-NI，Advanced Encryption Standard New Instructions）是由英特爾和 AMD 引入的一組指令，用於硬件加速 AES 加密和解密操作。AES 是對稱加密標準，廣泛應用於數據保護領域，如 HTTPS、VPN、磁盤加密等。Go 在 AMD64 架構中使用下面的彙編實現了 memhash:

// AX: data
// BX: hash seed
// CX: length
// At return: AX = return value
TEXT aeshashbody<>(SB),NOSPLIT,$0-0
...

具體我們就不解讀了，不可讀，主要判斷要 hash 的數據的長度，走到不同的分支中，使用種子和數據進行異或操作 (PXOR)、使用AESENC指令執行多輪 AES 加密。

你可以通過cat /proc/cpuinfo | grep -m 1 -i aes查看你的 CPU 是否支持 aes 指令：

蘋果電腦中可以使用sysctl -a | grep aes查看 CPU 是否支持 AES:

通過本次解密，你又瞭解了一種 Go 祕而不宣的數據結構和函數。

參考資料

[1] hash-bench: https://github.com/smallnest/hash-bench

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/ikL6I8GplE_2KYJ-3VvmmQ