在2024月11月5日的Go compiler and runtime meeting notes^[1]中，我們注意到了一段重要內容，如下圖紅框所示：

圖片

這表明，來自字節的一位工程師在兩年多前提出的“使用Swiss table重新實現Go map^[2]”的建議即將落地，目前該issue已經被納入Go 1.24里程碑^[3]。

Swiss Table是由Google工程師于2017年開發的一種高效哈希表實現，旨在優化內存使用和提升性能，解決Google內部代碼庫中廣泛使用的std::unordered_map所面臨的性能問題。Google工程師Matt Kulukundis在2017年CppCon大會上詳細介紹了他們在Swiss Table上的工作^[4]：

圖片

目前，Swiss Table已被應用于多種編程語言，包括C++ Abseil庫的flat_hash_map(可替換std::unordered_map)^[5]、Rust標準庫Hashmap的默認實現^[6]等。

Swiss Table的出色表現是字節工程師提出這一問題的直接原因。字節跳動作為國內使用Go語言較為廣泛的大廠。據issue描述，Go map的CPU消耗約占服務總體開銷的4%。其中，map的插入（mapassign）和訪問（mapaccess）操作的CPU消耗幾乎是1:1。大家可千萬不能小看4%這個數字，以字節、Google這樣大廠的體量，減少1%也意味著真金白銀的大幅節省。

Swiss Table被視為解決這一問題的潛在方案。字節工程師初版實現的基準測試結果顯示，與原實現相比，Swiss Table在查詢、插入和刪除操作上均提升了20%至50%的性能，尤其是在處理大hashmap時表現尤為突出；迭代性能提升了10%；內存使用減少了0%至25%，并且不再消耗額外內存。

這些顯著的性能提升引起了Go編譯器和運行時團隊的關注，特別是當時負責該子團隊的Austin Clements。在經過兩年多的實驗和評估后，Go團隊成員Michael Pratt^[7]基于Swiss Table實現的internal/runtime/maps最終成為Go map的底層默認實現。

在本文中，我們將簡單介紹Swiss Table這一高效的哈希表實現算法，并提前看一下Go map的Swiss Table實現。

在進入swiss table工作原理介紹之前，我們先來回顧一下當前Go map的實現(Go 1.23.x)。

1. Go map的當前實現

map，也稱為映射，或字典，或哈希表^[8]，是和數組等一樣的最常見的數據結構。實現map有兩個關鍵的考量，一個是哈希函數(hash function)，另一個就是碰撞處理(collision handling)。hash函數是數學家的事情，這里不表。對于碰撞處理，在大學數據結構課程中，老師通常會介紹兩種常見的處理方案：

• 開放尋址法(Open Addressing)

在發生哈希碰撞時，嘗試在哈希表中尋找下一個可用的位置，如下圖所示k3與k1的哈希值發生碰撞后，算法會嘗試從k1的位置開始向后找到一個空閑的位置：

圖片

• 鏈式哈希法(拉鏈法, Chaining)

每個哈希桶(bucket)存儲一個鏈表（或其他數據結構），所有哈希值相同的元素(比如k1和k3)都被存儲在該鏈表中。

圖片

Go當前的map實現采用的就是鏈式哈希，當然是經過優化過的了。要了解Go map的實現，關鍵把握住下面幾點：

• 編譯器重寫

我們在用戶層代碼中使用的map操作都會被Go編譯器重寫為對應的runtime的map操作，就如下面Go團隊成員Keith Randall在GopherCon大會上講解map實現原理^[9]的一個截圖所示：

圖片

• 鏈式哈希

前面提過，Go map當前采用的是鏈式哈希的實現，一個map在內存中的結構大致如下：

圖片

來自Keith Randall的ppt截圖

我們看到，一個map Header代表了一個map類型的實例，map header中存儲了有關map的元數據(圖中字段與當前實現可能有少許差異，畢竟那是幾年前的一個片子了)，如：

- len: 當前map中鍵值對的數量。
- bucket array: 存儲數據的bucket數組，可以對比前面的鏈式哈希的原理圖進行理解，不過不同的是，Go map中每個bucket本身就可以存儲多個鍵值對，而不是指向一個鍵值對的鏈表。
- hash seed: 用于哈希計算的種子，用于分散數據并提高安全性。

通常一個bucket可以存儲8個鍵值對，這些鍵值對是根據鍵的哈希值分配到對應的bucket中。

• 溢出桶(overflow bucket)

每個bucket后面還會有Overflow Bucket。當一個bucket中的數據超出容量時，會創建overflow bucket來存儲多余的數據。這樣可以避免直接擴展bucket數組，節省內存空間。但如果出現過多的overflow bucket，性能就會下降。

• “螞蟻搬家”式的擴容

當map中出現過多overflow bucket而導致性能下降時，我們就要考慮map bucket擴容的事兒了，以始終保證map的操作性能在一個合理的范圍。是否擴容由一個名為load factor的參數所控制。load factor是元素數量與bucket數量的比值，比值越高，map的讀寫性能越差。目前Go map采用了一個經驗值來確定是否要擴容，即load factor = 6.5。當load factor超過這個值時，就會觸發擴容。所謂擴容就是增大bucket數量(當前實現為增大一倍數量)，減少碰撞，讓每個bucket中存放的element數量降下來。

擴容需要對存量element做rehash，在元素數量較多的情況下，“一次性”的完成桶的擴容會造成map操作延遲“突增”，無法滿足一些業務場景的要求，因此Go map采用“增量”擴容的方式，即在訪問和插入數據時，“螞蟻搬家”式的做點搬移元素的操作，直到所有元素完成搬移。

Go map的當前實現應該可以適合大多數的場合，但依然有一些性能和延遲敏感的業務場景覺得Go map不夠快，另外一個常被詬病的就是當前實現的桶擴容后就不再縮容(shrink)了^[11]，這會給內存帶來壓力。

下面我們再來看看swiss table的結構和工作原理。

2. Swiss table的工作原理

就像前面提到的，Swiss table并非來自某個大學或研究機構的論文，而是來自Google工程師在工程領域的"最佳實踐"，因此關于Swiss table的主要資料都來自Google的開源C++ library Abseil^[12]以及開發者的演講視頻^[13]。在Abseil庫中，它是flat_hash_map、flat_hash_set、node_hash_map以及node_hash_set等數據結構的底層實現，并且Swiss table的實現在2018年9月正式開源^[14]。

和Go map當前實現不同，Swiss table使用的不是拉鏈法，而是開放尋址，但并非傳統的方案。下面是根據公開資源畫出的一個Swiss table的邏輯結構圖(注意：并非真實內存布局)：

圖片

如果用一個式子來表示Swiss table，我們可以用：

A swiss table = N * (metdata array + slots array)

我們看到：swiss table將所謂的桶（這里叫slot）分為多個group，每個group中有16個slot，這也是swiss table的創新，即將開放尋址方法中的probing(探測key碰撞后下一個可用的位置(slot))放到一個16個slot的group中進行，這樣的好處是可以通過一個SIMD指令^[15]并行探測16個slot，這種方法也被稱為Group Probing。

在上圖中，我們看到一個Group由metadata和16個slot組成。metadata中存儲的是元數據，而slot中存儲的是元素(key和value)。Group probling主要是基于metadata實現的，Google工程師的演講有對group probing實現的細節描述。

當我們向swiss table插入一個元素或是查找一個元素時，swiss table會通過hash函數對key進行求值，結果是一個8字節(64bit)的數。和Go map的當前實現一樣，這個哈希值的不同bit功用不同，下圖是一個來自abseil官網的示例：

圖片

哈希值的高57bit被稱為H1，低7bit被稱為H2。前者用于標識該元素在Group內的索引，查找和插入時都需要它。后者將被用于該元素的元數據，放在metadata中存儲，用于快速的group probing之用，也被稱為哈希指紋。

每個Group的metadata也是一個16字節數組，每個字節對應一個slot，是該slot的控制字節。這個字節的8個bit位的組成如下：

圖來自abseil庫官網

metadata中的控制字節有三個狀態：

• 最高位為1，其余全零為**空閑狀態(Empty)**，即對應的slot尚未曾被任何element占據過；
• 最高位為0，后7位為哈希指紋(H2)，為對應的slot當前已經有element占據的已使用狀態；
• 最高位為1，其他位為1111110的，為對應的slot為已刪除狀態，后續可以被繼續使用。

下面是Abseil開發者演進slide中的一個針對swiss table的迭代邏輯：

圖片

通過這幅圖可以看出H1的作用。不過這里通過pos = pos + 1進行probing（探測）顯然是不高效的！metadata之所以設計為如此，并保存了插入元素的哈希指紋就是為了實現高效的probing，下圖演示了基于key的hash值的H2指紋通過SIMD指令從16個位置中快速得到匹配的pos的過程：

圖片

雖然有兩個匹配項，但這個過程就像“布隆過濾器”一樣，快速排除了不可能的匹配項，減少了不必要的內存訪問。

由于metadata僅有16個字節，它的內存局部性更好。16個控制字節正好填充一個64字節的緩存行(cache line)，使用SIMD指令一次性加載整組控制字節，預取效率高，幾乎沒有cache miss。

由此也可以看到：swiss table的16個條目的分組大小不是隨意選擇的，而是基于現代CPU的緩存行大小(64字節)優化的，保證了一個Group的控制字節能被單次SIMD指令處理。

此外swiss table也是通過load factor來判定是否需要對哈希表進行擴容，一旦擴容，swiss table通常是會將group數量增加一倍，然后重新計算當前所有元素在新groups中的新位置(rehash)，這個過程是有一定開銷的。如果不做優化，當表中元素數量較多時，這個過程會導致操作延遲增加。

最后，雖然多數情況是在group內做probing，但當元素插入時，如果當前Group已滿，就必須探測到下一個Group，并將元素插入到下一個Group。這樣，在該元素的查找操作中，probing也會跨group進行。

到這里，我們已經粗略了解了swiss table的工作原理，那么Go tip對swiss table當前的實現又是怎樣的呢？我們下面就來看看。

3. Go tip版本當前的實現

Go tip版本基于swiss table的實現在https://github.com/golang/go/blob/master/src/internal/runtime/maps下。

由于Go map是原生類型，且有了第一版實現，考慮到Go1兼容性，新版基于swiss table的實現也要繼承已有的語義約束。同時，也要盡量避免swiss table自身的短板，Go團隊在swiss table之上做了局部改進。比如為了將擴容帶來的開銷降到最低，Go引入了多table的設計，以支持漸進式擴容。也就是說一個map實際上是多個swiss table，而不是像上面說的一個map就是一個swiss table。每個table擁有自己的load factor，可以獨立擴容(table的擴容是一次性擴容)，這樣就可以將擴容的開銷從全部數據變為局部少量數據，減少擴容帶來的影響。

Go swiss-table based map的邏輯結構大致如下：

圖片

我們可以看出與C++ swisstable的最直觀不同之處除了有多個table外，每個group包含8個slot和一個control word，而不是16個slot。此外，Go使用了二次探測(quadratic probing), 探測序列必須以空slot結束。

為了實現漸進式擴容，數據分散在多個table中；單個table容量有上限(maxTableCapacity)，超過上限時分裂成兩個table；使用可擴展哈希(extendible hashing)根據hash高位選擇table，且每個table可以獨立增長。

Go使用Directory管理多個table，Directory是Table的數組，大小為2^globalDepth。如果globalDepth=2，那Directory最多有4個表，分為0x00、0x01、0x10、0x11。Go通過key的hash值的前globalDepth個bit來選擇table。這是一種“extendible hashing”，這是一種動態哈希技術，其核心特點是通過動態調整使用的哈希位數(比如上面提到的globalDepth)來實現漸進式擴容。比如：初始可能只用1位哈希值來區分，需要時可以擴展到用2位，再需要時可以擴展到用3位，以此類推。

舉個例子，假設我們用二進制表示哈希值的高位，來看一個漸進式擴容的過程：

• 初始狀態 (Global Depth = 1):

directory
hash前綴  指向的table
0*** --> table1 (Local Depth = 1)
1*** --> table2 (Local Depth = 1)

• 當table1滿了需要分裂時，增加一位哈希值 (Global Depth = 2):

directory
hash前綴  指向的table
00** --> table3 (Local Depth = 2)  // 由table1擴容而成
01** --> table4 (Local Depth = 2)  // 由table1擴容而成
10** --> table2 (Local Depth = 1)
11** --> table2 (Local Depth = 1)  // 復用table2因為它的Local Depth還是1

• 如果table2也滿了，需要分裂：

directory
hash前綴  指向的table
00** --> table3 (Local Depth = 2)
01** --> table4 (Local Depth = 2)
10** --> table5 (Local Depth = 2) // 由table2擴容而成
11** --> table6 (Local Depth = 2) // 由table2擴容而成

通過extendible hashing實現的漸進式擴容，每次只處理一部分數據，擴容過程對其他操作影響小，空間利用更靈活。

對于新版go map實現而言，單個Table達到負載因子閾值時觸發Table擴容。當需要分裂的Table的localDepth等于map的globalDepth時觸發Directory擴容，這就好理解了。

除此之外，Go版本對small map也有特定優化，比如少量元素(<=8)時直接使用單個group，避免或盡量降低swiss table天生在少量元素情況下的性能回退問題。

更多實現細節，大家可以自行閱讀https://github.com/golang/go/blob/master/src/internal/runtime/maps/下的Go源碼進行理解。

注：目前swiss table版的go map依然還未最終定型，并且后續還會有各種優化加入，這里只是對當前的實現(2024.11.10)做概略介紹，不代表以后的map實現與上述思路完全一致。

4. Benchmark

目前gotip版本中GOEXPERIMENT=swissmap默認已經打開^[16]，我們直接用gotip版本即可體驗基于swiss table實現的map。

字節工程師zhangyunhao的gomapbench repo^[17]提供了對map的性能基準測試代碼，不過這個基準測試太多，我大幅簡化了一下，只使用Int64，并只測試了元素個數分別為12、256和8192時的情況。

注：我基于Centos 7.9，使用Go 1.23.0和gotip(devel go1.24-84e58c8 linux/amd64)跑的benchmark。

// 在experiments/swiss-table-map/mapbenchmark目錄下
$go test -run='^$' -timeout=10h -bench=. -count=10 > origin-map.txt 
$GOEXPERIMENT=swissmap gotip test -run='^$' -timeout=10h -bench=. -count=10 > swiss-table-map.txt 
$benchstat origin-map.txt swiss-table-map.txt > result.txt

下面是result.txt中的結果：

goos: linux
goarch: amd64
pkg: demo
cpu: Intel(R) Xeon(R) Platinum
                                  │ origin-map.txt │         swiss-table-map.txt          │
                                  │     sec/op     │    sec/op     vs base                │
MapIter/Int/12-8                      179.7n ± 10%   190.6n ±  4%        ~ (p=0.436 n=10)
MapIter/Int/256-8                     4.328μ ±  5%   3.748μ ±  1%  -13.40% (p=0.000 n=10)
MapIter/Int/8192-8                    137.3μ ±  1%   123.6μ ±  1%   -9.95% (p=0.000 n=10)
MapAccessHit/Int64/12-8               10.12n ±  2%   10.68n ± 14%   +5.64% (p=0.000 n=10)
MapAccessHit/Int64/256-8              10.29n ±  3%   11.29n ±  1%   +9.77% (p=0.000 n=10)
MapAccessHit/Int64/8192-8             25.99n ±  1%   14.93n ±  1%  -42.57% (p=0.000 n=10)
MapAccessMiss/Int64/12-8              12.39n ± 88%   20.99n ± 50%        ~ (p=0.669 n=10)
MapAccessMiss/Int64/256-8             13.12n ±  6%   11.34n ±  7%  -13.56% (p=0.000 n=10)
MapAccessMiss/Int64/8192-8            15.71n ±  1%   14.03n ±  1%  -10.66% (p=0.000 n=10)
MapAssignGrow/Int64/12-8              607.1n ±  2%   622.6n ±  2%   +2.54% (p=0.000 n=10)
MapAssignGrow/Int64/256-8             25.98μ ±  3%   23.22μ ±  1%  -10.64% (p=0.000 n=10)
MapAssignGrow/Int64/8192-8            792.3μ ±  1%   844.1μ ±  1%   +6.54% (p=0.000 n=10)
MapAssignPreAllocate/Int64/12-8       450.2n ±  2%   409.2n ±  1%   -9.11% (p=0.000 n=10)
MapAssignPreAllocate/Int64/256-8     10.412μ ±  1%   6.055μ ±  2%  -41.84% (p=0.000 n=10)
MapAssignPreAllocate/Int64/8192-8     342.4μ ±  1%   232.6μ ±  2%  -32.05% (p=0.000 n=10)
MapAssignReuse/Int64/12-8             374.2n ±  1%   235.4n ±  2%  -37.07% (p=0.000 n=10)
MapAssignReuse/Int64/256-8            8.737μ ±  1%   4.716μ ±  4%  -46.03% (p=0.000 n=10)
MapAssignReuse/Int64/8192-8           296.4μ ±  1%   181.0μ ±  1%  -38.93% (p=0.000 n=10)
geomean                               1.159μ         984.2n        -15.11%

我們看到了除了少數測試項有不足外(比如MapAssignGrow以及一些元素數量少的情況下)，大多數測試項中，新版基于swiss table的map的性能都有大幅提升，有些甚至接近50%！

5. 小結

本文探討了Go語言中的map實現的重塑，即引入Swiss Table這一高效哈希表結構的背景與優勢。Swiss Table由Google工程師開發，旨在優化內存使用和提升性能，解決了傳統哈希表在高負載情況下的性能瓶頸。通過對比現有的鏈式哈希實現，Swiss Table展示了在查詢、插入和刪除操作上顯著提高的性能，尤其是在處理大規模數據時。

經過兩年多的實驗與評估，Go團隊決定將Swiss Table作為Go map的底層實現，預計將在Go 1.24^[19]中正式落地。新的實現不僅承繼了原有的語義約束，還通過引入多表和漸進式擴容的設計，進一步優化了擴容過程的性能。盡管當前實現仍在完善中，但Swiss Table的引入無疑為Go語言的性能提升提供了新的可能性，并為未來進一步優化奠定了基礎。

對于那些因Go引入自定義iterator^[20]而批評Go團隊的Gopher來說，這個Go map的重塑無疑會很對他們的胃口。

本文涉及的源碼可以在這里^[21]下載。

6. 參考資料

• runtime: use SwissTable^[22] - https://github.com/golang/go/issues/54766
• swiss table benchmark result^[23] - https://gist.github.com/aclements/9fb32ac0a287d2ff360f1bc166cdf4b8
• Swisstable, a Quick and Dirty Description^[24] - https://faultlore.com/blah/hashbrown-tldr/
• Swiss Tables Design Notes^[25] - https://abseil.io/about/design/swisstables
• Designing a Fast, Efficient, Cache-friendly Hash Table, Step by Step^[26] - https://www.youtube.com/watch?v=ncHmEUmJZf4
• Abseil's Open Source Hashtables: 2 Years In^[27] - https://www.youtube.com/watch?v=JZE3_0qvrMg
• Swiss Tables and absl::Hash^[28] - https://abseil.io/blog/20180927-swisstables
• SwissMap: A smaller, faster Golang Hash Table^[29] - https://www.dolthub.com/blog/2023-03-28-swiss-map/
• What is a Hash Map?^[30] - https://www.freecodecamp.org/news/what-is-a-hash-map/
• Inside the Map Implementation^[31] - https://www.youtube.com/watch?v=Tl7mi9QmLns

參考資料

[1] 2024月11月5日的Go compiler and runtime meeting notes: https://github.com/golang/go/issues/43930#issuecomment-2458068992

[2] 使用Swiss table重新實現Go map: https://github.com/golang/go/issues/54766

[3] Go 1.24里程碑: https://github.com/golang/go/milestone/322

[4] Google工程師Matt Kulukundis在2017年CppCon大會上詳細介紹了他們在Swiss Table上的工作: https://www.youtube.com/watch?v=ncHmEUmJZf4

[5] C++ Abseil庫的flat_hash_map(可替換std::unordered_map): https://abseil.io/about/design/swisstables

[6] Rust標準庫Hashmap的默認實現: https://github.com/rust-lang/hashbrown

[7] Michael Pratt: https://github.com/prattmic

[8] 哈希表: https://en.wikipedia.org/wiki/Hash_table

[9] map實現原理: https://www.youtube.com/watch?v=Tl7mi9QmLns

[10] 《Go語言第一課》: http://gk.link/a/10AVZ

[11] 不再縮容(shrink)了: https://github.com/golang/go/issues/20135

[12] Google的開源C++ library Abseil: https://abseil.io/

[13] 開發者的演講視頻: https://www.youtube.com/watch?v=ncHmEUmJZf4

[14] Swiss table的實現在2018年9月正式開源: https://abseil.io/blog/20180927-swisstables

[15] SIMD指令: https://tonybai.com/2024/07/21/simd-in-go

[16] GOEXPERIMENT=swissmap默認已經打開: https://github.com/golang/go/commit/99d60c24e23d4d97ce51b1ee5660b60a5651693a

[17] gomapbench repo: https://github.com/zhangyunhao116/gomapbench

[18] 《Go語言第一課》: http://gk.link/a/10AVZ

[19] Go 1.24: https://github.com/golang/go/milestone/322

[20] 自定義iterator: https://tonybai.com/2024/06/24/range-over-func-and-package-iter-in-go-1-23/

[21] 這里: https://github.com/bigwhite/experiments/tree/master/swiss-table-map

[22] runtime: use SwissTable: https://github.com/golang/go/issues/54766

[23] swiss table benchmark result: https://gist.github.com/aclements/9fb32ac0a287d2ff360f1bc166cdf4b8

[24] Swisstable, a Quick and Dirty Description: https://faultlore.com/blah/hashbrown-tldr/

[25] Swiss Tables Design Notes: https://abseil.io/about/design/swisstables

[26] Designing a Fast, Efficient, Cache-friendly Hash Table, Step by Step: https://www.youtube.com/watch?v=ncHmEUmJZf4

[27] Abseil's Open Source Hashtables: 2 Years In: https://www.youtube.com/watch?v=JZE3_0qvrMg

[28] Swiss Tables and absl::Hash: https://abseil.io/blog/20180927-swisstables

[29] SwissMap: A smaller, faster Golang Hash Table: https://www.dolthub.com/blog/2023-03-28-swiss-map/

[30] What is a Hash Map?: https://www.freecodecamp.org/news/what-is-a-hash-map/

[31] Inside the Map Implementation: https://www.youtube.com/watch?v=Tl7mi9QmLns