プログラミング

Goの組み込みマップにおけるSwiss Tableの仕組み

How Swiss tables work in Go built-in map (victoriametrics.com)

87 pointsby valyala2026年9月3日7 コメント

要約

Go 1.24で導入された組み込みマップの新しい実装であるSwiss Tableについて解説します。Swiss Tableは、キーと値のエントリを格納する「グループ」という単位を使用し、各グループにはキーのハッシュ値の一部（H2）を格納する制御バイトが含まれます。これにより、キーの検索や挿入が効率化され、特にSIMD命令を用いた並列処理によって高速化されています。

全文翻訳

Goの組み込みマップにおけるSwiss Tableの仕組み

Goのマップとその古いランタイム実装については、以前の記事「Go Maps Explained: How Key-Value Pairs Are Actually Stored」で既に解説しました。Go 1.24では、Swiss Tableに基づいた設計にその実装が置き換えられたため、更新の時期が来ました。

古い記事を読み返す必要はありません。新しいランタイムの内部構造をステップバイステップで解説し、必要に応じて各概念を紹介していきます。

Goのブログにも素晴らしい記事「Faster Go maps with Swiss Tables」があります。こちらはより深く掘り下げており、ある程度の背景知識を前提としています。私たちは異なるアプローチを取り、同じ実装をより段階的に、視覚的に説明することで、読者の皆様がリラックスしながらGoの動作を理解できるようにします。

## ランタイムにおけるマップとは？

まず、マップが実際には何であるかから始めましょう。

m := make(map[string]int)

makeはマップを初期化します。map[string]intは言語レベルの型であり、マップが文字列をキー、整数を値として使用することを示しています。この型の配下では、mのランタイム表現はinternal/runtime/maps.Mapへのポインタです。

type Map struct {
	used uint64
	seed uintptr

	dirPtr unsafe.Pointer
	dirLen int
	...
}

printlnを使ってこれを簡単に確認できます。これはポインタを出力します。

m := make(map[string]int)
m2 := m

println(m)  // 0x14000122000
println(m2) // 0x14000122000

mを別のマップ変数にコピーすると、このポインタもコピーされるため、両方の変数が同じランタイムMapとエントリを参照します。

［画像: マップ変数をコピーすると、mとm2は同じランタイムMapを指します。］

マップ変数をコピーすると、mとm2は同じランタイムMapを指します。

先頭の2つのフィールドは、エントリのストレージではなく、マップ自体を記述しています。

type Map struct {
	used uint64
	seed uintptr
	...
}

usedは現在格納されているエントリの数をカウントします。Goはエントリの数を正確に把握しているため、len(m)と書くと、Goはこの呼び出しをMapの最初のフィールドへのアクセスに置き換え、それをintに変換します。そのため、len(m)はマップ全体をスキャンするのではなくO(1)で実行されます。

seedは興味深いフィールドであり、異なるマップが同じキーを異なる方法で分散させる原因となります。Goは各マップに対してこのフィールドをランダムな数値で初期化します。

［画像: マップが異なるシードを使用すると、同じエントリが異なる配置になります。］

マップが異なるシードを使用すると、同じエントリが異なる配置になります。

上記の配列は、この説明のための簡略化された表現にすぎません。実際のデータ構造はより複雑です。

Goがキーをハッシュして格納場所を見つける際、キーとマップのシードの両方を使用してハッシュを計算します。各マップは独自のシードを受け取るため、同じキーが2つのマップで異なるハッシュ値を生成し、異なるストレージ場所に格納される可能性があります。

### ストレージレイアウト

Goはマップごとに同じストレージレイアウトを使用するわけではありません。レイアウトはマップが格納するキー・バリューペアの数に基づいて変化します。

詳細に入る前に、マップが3つの主要なケースでどのように見えるかをネタバレします。

［画像: 4、100、1,000個のキーを持つマップの3つの例示レイアウト。］

マップは、より多くのエントリを格納するにつれて、テーブルとディレクトリを追加します。

ここでは、データ構造の3つの主要部分、すなわちディレクトリ、1つ以上のテーブル、そして各テーブル内のグループを既に確認できます。グループは最小のストレージ単位であり、Goがキー・バリューペアを格納する場所です。

### グループ

キー・バリューペアを格納するために1つのグループしか必要としない小さなマップから始めます。1つのグループは最大8ペアを保持できるため、マップはまだディレクトリやテーブルを必要としません。代わりに、dirPtrは直接グループを指します。

グループは、GoのSwiss Table実装が一度にチェックする最小のストレージピースです。各グループには以下が含まれます。

キー・バリューエントリ用の8つのスロット。
各スロットに対応する8つの制御バイト。Goはこれらの8バイトをまとめて1つのuint64に格納します。

［画像: グループは、各制御バイトをその下のキー・バリューペアとペアにします。］

グループは、各制御バイトをその下のキー・バリューペアとペアにします。

グループの具体的な型はマップのキーと値の型に依存するため、コンパイラは各マップ型に対して内部の匿名構造体を生成します。概念的には、map[string]intはこのレイアウトを持ちます。

type group struct {
	ctrl uint64

	slots [8]struct {
		key  Key
		elem Elem
	}
}

Goは、キー検索の局所性を改善し、重複するアライメントパディングを削除するために、キーと値の配列を分離した新しいグループレイアウトもテストしています。これは分割グループレイアウトセクションで説明されています。

#### 制御バイトと制御ワード

まず、グループの上部行を見てみましょう。これらは8つの制御バイトです。これらはまとめて8バイトの制御ワードを形成します。

各制御バイトは、その直接下のスロットを記述しています。つまり、制御バイト0はスロット0に、制御バイト1はスロット1に属し、この関係はスロット7まで続きます。

しかし、これらのバイトはどこから来るのでしょうか？

GoはMapのseedを使用してキーをハッシュし、そのハッシュを2つの部分に分割します。ほとんどの64ビットターゲットでは、上位57ビットがH1、下位7ビットがH2と呼ばれます。たとえば、私たちの例でH2が42を生成する別のキー"cow"があるとします。

［画像: 64ビットハッシュはH1と7ビットのH2を含みます。］

64ビットハッシュはH1と7ビットのH2を含みます。

H1は、Goがマップのストレージ内の検索開始位置を選択するために使用するハッシュの最初の部分です。小さなマップには1つのグループしかないため、選択するものがありません。マップが大きくなるまで、これを脇に置いておきましょう。

H2は、ライブスロットの上に格納される制御バイトの部分です。

しかし、制御バイトは8ビットですが、H2は7ビットしか使用しないため、まだ1ビット残っています。Goはこの最上位ビットを使用して、スロットにライブエントリが含まれているか、特別な状態であるかを伝えます。このビットが0の場合、下位7ビットにH2が含まれます。このビットが1の場合、制御バイト全体がemptyまたはdeletedを表します。

［画像: 制御バイトは、ライブ、空、または削除されたスロットを表します。］

制御バイトは、ライブ、空、または削除されたスロットを表します。

スロットにキー・バリューエントリが含まれている場合、最上位ビットは0であり、下位7ビットにはH2が含まれます。H2 42はバイナリで0101010なので、"cow"の完全な制御バイトは00101010になります。

最上位ビットが1の場合、制御バイトはH2の代わりに特別な値を格納します。空のスロットは10000000を使用します。削除されたスロットは11111110を使用し、tombstone（墓石）とも呼ばれます。どちらの状態もライブなキー・バリューエントリを含みませんが、ルックアップはemptyで停止できますが、deletedはスキップする必要があります。この区別については、削除セクションで再度説明します。

このレイアウトにより、制御バイトは、完全なキーをスロットから読み取る前に、Goが2つの質問に答えるのに役立ちます。

このスロットにはライブエントリが含まれていますか、それともemptyまたはdeletedですか？
スロットにライブエントリが含まれている場合、そのキーは探しているものと同じ可能性がありますか？

元のグループに戻りましょう。

［画像: グループは、各制御バイトをその下のキー・バリューペアとペアにします。］

グループは、各制御バイトをその下のキー・バリューペアとペアにします。

次に、H2 42を生成した"cow"キーに値を割り当てます。

m["cow"] = 4

"cow"を格納する前に、Goはこの代入が既存のキーを更新するのか、新しいキーを追加するのかを知る必要があります。H2を使用してキーが格納されている可能性のあるスロットを見つけ、各候補を完全なキー等価性チェックで確認します。

"cow"のH2は42であり、これは"dog"の制御バイトに格納されている値と同じです。
Goは完全なキーを等価性チェック（==）で比較しますが、"dog"は"cow"と等しくありません。
他のどの制御バイトもH2 42を含んでいないため、Goはこの代入が新しいキーを追加していることを知ります。

マップはグループ内の最初のエンプティスロットであるスロット2を選択し、そこに"cow"と4を書き込み、その直接上の制御バイト2にH2 42を書き込みます。

［画像: Cowは最初のエンプティスロットを使用し、その上にH2 42を格納します。］

Cowは最初のエンプティスロットを使用し、その上にH2 42を格納します。

これで、グループには同じH2値42を持つ2つの制御バイトが含まれます。1つは"dog"の上、もう1つは"cow"の上です。後で"cow"に別の値を割り当てたとします。

m["cow"] = 5

Goは値を更新する前に、既存のキーを見つける必要があります。ハッシュからH2 42を取得し、グループ内のすべての8つの制御バイトと比較します。

［画像: H2 42はdogとcowを候補キーとして選択します。］

H2 42はdogとcowを候補キーとして選択します。

Goは8つのスロットを1つずつ訪れて個別にH2を各制御バイトと比較するわけではありません。AMD64では、GoはSIMD命令を使用して、H2 42をこれらの8つの制御バイトすべてと同時に比較します。

SIMDにより、CPUは同じ比較を複数のバイト値に並列に適用できます。AMD64では、結果は各スロットに1ビットを持つパックされたビットマップになります。

［画像: 1回の制御ワード比較で候補ビットマップが生成されます。］

1回の制御ワード比較で候補ビットマップが生成されます。

私たちのグループでは、ビット0とビット2のスロットが設定されています。なぜなら、両方の制御バイトが42を含んでいるからです。他のビットはクリアされており、他の6つのスロットを完全なキーを読み取ることなくマスクアウトします。

他のアーキテクチャでは、64ビット制御ワードに対する算術演算とビット演算を使用して同じ候補マスクを生成しますが、結果を8ビットにパックするのではなく、スロットごとに1バイトを使用します。

Goは次にスロット0と2の完全なキーを読み取り、"cow"と比較します。"dog"は等価性チェック（==）に失敗しますが、"cow"は一致するため、代入は"cow"に格納されている値を更新します。

### テーブル

1つのグループには8つのスロットしかないため、容量を超えてキー・バリューペアを追加し続ける場合、Goはそれらを格納するためにもう1つのストレージ構造を必要とします。

Goはグループの数を1から2に倍増させ、それらを管理するためにテーブルと呼ばれる新しい構造体を導入します。既存の8つのエントリをそのテーブルに移動し、2つのグループに再分散させてから、新しいエントリを格納します。

［画像: 9番目のエントリにより、1つのグループが2つのグループを持つテーブルに変わります。］

9番目のエントリにより、1つのグループが2つのグループを持つテーブルに変わります。

テーブルは、複数のグループをまとめて所有する完全なSwiss Tableです。

type table struct {
	used       uint16
	capacity   uint16
	growthLeft uint16
	...

	groups groupsReference
}

最初のテーブルはcapacity = 16、used = 9、そして2つのグループを持ちます。

groupsはグループを含む連続したメモリ割り当てを指します。
capacityは、それらのグループ全体のすべてのスロットをカウントします。
usedはこのテーブル内のライブエントリをカウントします。

では、最初のグループの既存のキー・バリューペアを再分散する必要があるのはなぜでしょうか？そして、Goは各ペアがどちらのグループに行くべきかをどのように知るのでしょうか？

H1を紹介しましょう。これはまさにこの目的のために使用されます。GoはH1を使用して各キーの開始グループを計算します。

starting group = H1 % number of groups

このテーブルには2つのグループがあるため、% 2はH1の最下位ビットのみを必要とします。H1を最上位ビットを左にして表示すると、最下位ビットは元のハッシュのH2のすぐ隣にある最も右のビットです。

たとえば、"cow"のH1が0で終わり、"dog"のH1が1で終わるとします。

［画像: 最下位H1ビットが2つのグループ間でエントリを再分散します。］

最下位H1ビットが2つのグループ間でエントリを再分散します。

グループ数が変更されたため、Goは既存の各キーに対してこの計算を再度実行します。一部のキー・バリューペアは新しいグループ0に挿入され、他のペアは新しいグループ1に挿入されます。

この計算は開始グループのみを提供します。16スロットと10個のライブエントリを持つ別のマップを使用して、これがなぜ重要なのかを見てみましょう。そのキーは不均一に分散されており、グループ0がいっぱいになり、グループ1にはまだ空きスロットがあります。

［画像: 1つのグループがいっぱいになる一方で、別のグループにはまだ空きスロットがあります。］

1つのグループがいっぱいになる一方で、別のグループにはまだ空きスロットがあります。

この場合、別のキーも上記の満杯のグループ0を開始グループとして選択する可能性があります。Goはそこにキーを格納できないため、次にグループ1をチェックします。Goがチェックするグループのリストと、チェックに使用される順序は三角プローブシーケンスと呼ばれます。

三角プローブシーケンスとは何でしょうか？

テーブルに8つのグループがあり、H1がキーの開始グループとしてグループ3を選択したとしましょう。グループ3に空きスロットがない場合、Goは他のグループをチェックする必要があります。

Goはグループ間で二次プローブを使用します。グループ3から開始して、+1、次に+2、次に+3と移動し、テーブルをラップアラウンドします。結果のシーケンスは3, 4, 6, 1, 5, 2, 0, 7です。

［画像: 8グループの三角プローブシーケンス。］

8グループの三角プローブシーケンス。

累積オフセットは0, 1, 3, 6, 10, ...、つまり三角数であり、これが名前の由来です。グループ数が2のべき乗であるため、Goはシーケンスが繰り返される前に、すべてのグループを正確に1回ずつ訪問します。

なぜ単純に次のグループを毎回チェックしないのでしょうか：3, 4, 5, 6, 7, 0, 1, 2？

グループ3、4、5がすでに満杯になっていると想像してください。

グループ3から始まる新しいキーは、グループ6を使用できるようになる前に、これら3つのグループすべてを通過する必要があります。
グループ4または5から始まる新しいキーも、その前のグループが満杯であるため、グループ6に到達します。
グループ6が満杯になると、これらの新しい挿入はグループ7に続きます。

時間が経つにつれて、満杯の領域は一方向に成長し続け、Goはその中に開始する新しいキーを挿入するために、より多くのグループをチェックする必要があります。これはクラスタリングと呼ばれます。

三角シーケンスは、これらのキーを常に隣接するグループに押し込むのを回避します。ジャンプが大きくなるため、グループ3と4をチェックした後、グループ6にジャンプし、次にグループ1、次にグループ5にジャンプします。これにより、満杯の領域を拡張するのではなく、衝突をテーブル全体に分散させます。各グループ内では、Goは依然として8つのスロットすべてをまとめてチェックします。

Mapのストレージポインタも、小さなマップがテーブルベースのマップになったときに変更されます。dirPtrはもはや直接グループを指しません。これは1つのエントリを持つ配列を指し、そのエントリがテーブルを指します。

ランタイムは、このポインタ配列をディレクトリと呼びます。10エントリのマップがテーブルにどのように接続されるかは次のとおりです。

［画像: dirPtrはディレクトリエントリ0を介してテーブルに到達します。］

dirPtrはディレクトリエントリ0を介してテーブルに到達します。

上記のテーブルは2つのグループから始まります。各グループには8つのスロットが含まれているため、このテーブルは現在16スロットを持っています。

キーを追加し続けると、Goはそれを4つのグループ、次に8つ、次に16個のグループを持つより大きなテーブルに置き換えることができ、ストレージが必要になるたびにグループ数を倍増させ続けます。1つのテーブルは最大128グループまで成長でき、最大容量は1024スロットになります。

128 groups * 8 slots = 1024 slots

さらに挿入でストレージが必要になった場合、Goはテーブルを2つのテーブルに分割します。この分割については後で追跡します。

しかし、1つのグループを持つ小さなマップが2つのグループを持つテーブルになった後、Goは異なる成長しきい値を使用します。

テーブルが1024スロットに成長すると、分割する前にすべてのスロットが使用されるのを待たなくなります。
テーブルに2つのグループがある場合、グループ数を2から4、4から8などに倍増させる前に、テーブル内のすべてのグループがいっぱいになるのを待ちません。

通常のテーブルは、すべてのスロットが使用される前に挿入制限に達し、その制限はロードファクターによって制御されます。これはテーブルがいかにいっぱいであるかをGoに伝えます。Goはライブエントリと削除されたスロットの両方をこの計算に含めます。

load = (live entries + deleted slots) / table slots

私たちのテーブルには削除されたスロットがなく、16スロットと10個のライブエントリがあるため、ロードファクターは10 / 16、つまり62.5%です。

Goは、テーブルが100%に達するのを許可しません。最大ロードファクターは7 / 8、つまり87.5%です。これは、ライブエントリと削除されたスロットを合わせたものが、平均して8つのスロットのうち7つを占める可能性があることを意味します。この制限はテーブル全体に適用されます。

Goが7 / 8のロードファクターを使用する理由については、Why load factor?で説明します。

テーブルフィールドgrowthLeftは、テーブルがその制限に達する前に、新しいキーが消費できる追加の空きスロットの数を追跡します。

type table struct {
	used       uint16
	capacity   uint16
	growthLeft uint16
	...

	groups groupsReference
}

ライブエントリと空きスロットのみを持つ16スロットのテーブルは、14個のエントリの挿入制限があります。なぜなら16 * 7 / 8 = 14だからです。上記の10個のエントリが格納された後、growthLeftは4になります。

テーブルが14個のライブエントリを格納した後、growthLeftは0に達します。別の新しいキーが空きスロットを必要とする場合、Goはテーブルのグループ数を倍増させます（テーブルが1024スロット未満の場合）。

［画像: テーブルは1024スロットに達するまで倍増します。］

テーブルは1024スロットに達するまで倍増します。

テーブルがグループ数を倍増させるたびに、Goはそのテーブル内のすべてのライブキーを再度ハッシュし、すべてのエントリを新しいグループに再分散します。

1024スロットを持つテーブルは、すでに最大128グループを含んでいます。この場合、Goは代わりに選択されたテーブルを2つの新しいテーブルに分割します。各テーブルは128グループと1024スロットを持ちます。

なぜ同じテーブルにグループを追加し続けないのでしょうか？

テーブルが成長するたびに、Goは既存のキーを再度ハッシュし、エントリを新しいグループに移動する必要があります。1つの大きなテーブルでは、成長を引き起こす挿入は、それらのエントリすべてが移動するのを待つ必要があります。

Goは複数の小さなテーブルを使用してこれを回避します。1つのテーブルがスペースを必要とする場合、Goはそのテーブルのみを再構築します。他のテーブルのエントリはそのままです。各テーブルは最大1024スロットを持ち、これにより各再構築で移動する必要のあるエントリの数が制限されます。

ここで、分割と言うとき、テーブルの数が倍増することを意味するのではありません。テーブルの数は徐々に増加します。なぜなら、スペースが必要なテーブルのみが2つの新しいテーブルに分割されるからです。他のテーブルは変更されません。

この分割は、グループを選択する計算とは異なるH1の端を使用します。グループ数が倍増するとき、GoはH1の右側（下位ビットがある場所）から1ビット多く使用して、同じテーブル内の開始グループを計算します。

したがって、テーブルが分割されるとき、GoはH1の左側（上位ビットがある場所）から次の未使用ビットを使用して、2つの新しいテーブルのどちらかを選択します。

"dog"のH1が0で始まり、"cat"のH1が1で始まると仮定します。0は"dog"をテーブル0に送り、1は"cat"をテーブル1に送ります。

［画像: 最左端のH1ビットが最初の2つのテーブルを分離します。］

最左端のH1ビットが最初の2つのテーブルを分離します。

したがって、マップはキーをシードで再度ハッシュし、同じ最左端のH1ビットを読み取り、キー・バリューペアを選択された新しいテーブルに挿入します。すべてのライブエントリが移動した後、Goはグループ数を倍増するときと同じように、分割を引き起こした挿入を再試行します。

### ディレクトリ

ディレクトリに入る前に、それが解決する問題を理解しましょう。

#### 再分散

Goが1つのテーブルがストレージをさらに必要としたときにマップ内のすべてのキー・バリューペアを再分散した場合、マップが大きくなるにつれて各成長操作はますます高価になります。代わりに、Goはストレージを必要とするテーブルのみを再構築します。

テーブルのグループ数が倍増するとき、Goはそのテーブルからライブキー・バリューペアのみを新しいグループに再分散します。

最上位のH1ビットはテーブルを選択し、最下位のH1ビットはテーブル内のグループを選択します。

グループ数が変更されると、Goはそのテーブルがグループ選択に使用する最下位のH1ビットの数を変更するだけです。

［画像: H1の左端と右端がテーブルとグループを選択します。］

H1の左端と右端がテーブルとグループを選択します。

それはテーブルを選択した最上位のH1プレフィックスを変更しません。別のテーブルに格納されているキーは異なる最上位のH1プレフィックスを持つため、そのテーブルを選択し続け、この再分散に参加しません。

テーブルが2つのテーブルに分割されるとき、Goは元のテーブルからライブキー・バリューペアのみを2つの新しいテーブル間で再分散します。

マップに2つのテーブルがある場合、ディレクトリは最上位のH1ビットを使用してそれらを切り替えます：0はテーブル0を指し、1はテーブル1を指します。テーブル1が分割されると、ディレクトリは読み取る最上位のH1ビットの数を1から2に増やします。

［画像: テーブル1を分割すると、テーブル0は変更されません。］

テーブル1を分割すると、テーブル0は変更されません。

H1プレフィックス00と01はそれぞれディレクトリエントリ0と1を選択し、どちらもテーブル0を指します（テーブル0は分割されていないため）。プレフィックス10はエントリ2を選択し、新しいテーブル1を指し、プレフィックス11はエントリ3を選択し、新しいテーブル2を指します。

マップには現在3つのテーブルがありますが、2つの最上位H1ビットは4つの可能な組み合わせを生成しますよね？

ここでディレクトリが役立ちます。4つのエントリがあり、各ビット組み合わせに対応しますが、それらのエントリは4つの異なるテーブルを指す必要はありません。

［画像: 4つのディレクトリエントリが3つのテーブルを指すことができます。］

4つのディレクトリエントリが3つのテーブルを指すことができます。

ルックアップ中、Goは最上位の2つのH1ビットを使用してディレクトリエントリを選択し、そのエントリが検索すべきテーブルをGoに伝えます。これにより、他のすべてのテーブルを分割することなく、1つのテーブルを分割できます。

言い換えれば、最上位のH1ビットはテーブルを直接選択するのではなくディレクトリエントリを選択し、そのディレクトリエントリがキーを含む可能性のあるテーブルをGoに伝えます。

### グローバルデプスとローカルデプス

テーブル0が挿入制限に達し、分割が必要になったとしましょう。しかし、2つのディレクトリエントリがテーブル0を指しているため、テーブル1を分割したときのように単純に分割することはできません。

したがって、テーブル0は次のことを知る必要があります。

いくつのディレクトリエントリがそれを指していますか？
ディレクトリはすでに2つの新しい子テーブルのための十分なエントリを持っていますか？

これがグローバルデプスとローカルデプスが示すものです。

type Map struct {
	dirPtr unsafe.Pointer
	dirLen int

	globalDepth uint8
	...
}

type table struct {
	localDepth uint8
	...
}

グローバルデプスはディレクトリ全体に属します。これは、1つのディレクトリエントリを選択するために使用されるハッシュビットの数です。この場合、H1の最上位2ビット（00、01、10、11）で選択される4つのディレクトリエントリがあるため、globalDepth = 2です。

ローカルデプスは各テーブルに属します。これは、そのテーブルを識別するために必要なハッシュビットの数です。この場合：

H1プレフィックス0を持つすべてのキーはテーブル0を選択します。テーブル0は最上位ビット（0）で識別されるため、localDepth = 1です。
H1プレフィックス10を持つすべてのキーはテーブル1を選択し、H1プレフィックス11を持つすべてのキーはテーブル2を選択します。テーブル1と2は最上位2ビットを必要とするため、それぞれlocalDepth = 2です。

［画像: 4つのディレクトリエントリが3つのテーブルを指します。］

4つのディレクトリエントリが3つのテーブルを指します。

テーブル0は、そのローカルデプス（1）がグローバルデプス（2）よりも小さいことを知っています。これは、ディレクトリがすでに分割のための十分なエントリを持っていることを意味します。Goは、ディレクトリを拡張することなく、エントリ0を1つの子に、エントリ1をもう1つの子にポイントさせることができます。

［画像: テーブル0はディレクトリを拡張せずにテーブル0と1に分割されます。］

テーブル0はディレクトリを拡張せずにテーブル0と1に分割されます。

もしテーブル1が挿入制限に達し、テーブル0の代わりに分割が必要になったらどうでしょうか？この場合、そのlocalDepth（2）はマップのglobalDepth（2）と等しくなります。マップはまずディレクトリを4エントリから8エントリに倍増させ、globalDepthを3に増やします。その後、テーブル1をテーブル1と2に分割します。

［画像: テーブル1を分割すると、テーブル1と2を作成する前にディレクトリが倍増します。］

テーブル1を分割すると、テーブル1と2を作成する前にディレクトリが倍増します。

ここまでは順調です。キーのハッシュのみを使用して、これまでに議論したことを要約しましょう。

H1の最上位ビットはディレクトリエントリ、したがってテーブルを選択します。H1の下位ビットはテーブル内の開始グループを選択します。H2はグループ内の8つのスロットをフィルタリングします。ディレクトリ選択とグループ選択の間にあるH1ビットは、現在のマップ形状では使用されない場合があります。

［画像: ハッシュは、ディレクトリエントリ、グループ、およびH2のビットを提供します。］

ハッシュは、ディレクトリエントリ、グループ、およびH2のビットを提供します。

## Go 1.24で何が変わったか？

新しい実装をグループからディレクトリまで追跡した後、Goがバージョン1.24より前に使用していた実装と比較してみましょう。

古い実装では、1つのバケットに最大8つのキー・バリューペアを格納していました。そのバケットがさらにエントリを保持できない場合、ランタイムはさらに8つのスロットを提供するオーバーフローバケットを接続できました。

オーバーフローバケットも満杯になった場合、別のオーバーフローバケットがそれに続く可能性がありました。

［画像: バケットはオーバーフローバケットのチェーンを指します。］

バケットはオーバーフローバケットのチェーンを指します。

オーバーフローバケットにより、他のバケットを再分散することなく、1つの満杯のバケットにスペースを追加できました。しかし、オーバーフローチェーンはいくつかのコストも導入しました。

ルックアップは、次の8つのスロットを見つけてチェックする前に、オーバーフローポインタをロードする必要がありました。
より長いチェーンは、各追加のオーバーフローバケットに対して、そのポインタロードとバケットスキャンを繰り返しました。
チェーンを拡張するには、別の割り当てが必要になる場合があります。

Goは、現在のバケットからポインタをロードするまでオーバーフローバケットを読み取ることができません。追加のオーバーフローバケットごとに、依存するポインタロードが追加されます。

bucket
  -> load pointer
overflow 1
  -> load pointer
overflow 2

新しい実装は、テーブルのグループを1つの配列にまとめて割り当てます。各グループがどこにあるかを正確に把握しており、開始グループに空きスロットがない場合にテーブル内の別のグループを見つけるために三角プローブシーケンスを使用します。

［画像: 古いマップはオーバーフローバケットを使用し、新しいマップはテーブルグループをプローブします。］

古いマップはオーバーフローバケットを使用し、新しいマップはテーブルグループをプローブします。

成長は2番目の主要な変更点です。

古い実装では、マップには1つのプライマリバケット配列がありました。バケット配列が倍増すると、Goは2倍のバケットを持つ新しい配列を作成しました。各古いバケットからのキー・バリューペアは、新しい配列の2つのバケットに分散されました。

［画像: 古いバケット0のエントリが新しいバケット0と4に移動します。］

古いバケット0のエントリが新しいバケット0と4に移動します。

Goは、エントリを割り当てたり削除したりするにつれて、各古いバケットに対してこのプロセスを徐々に繰り返したため、すべてのキー・バリューペアが移動するまで両方の配列はアクティブなままでした。

対照的に、GoのSwiss Tableの成長は、前述のように1つのグループを一度に移動するわけではありません。新しい実装は、大きなマップを最大1024スロットのテーブルに分割します。

1つの代入で1つのテーブル全体が再構築される可能性がありますが、利点は他のテーブルのエントリストレージを再構築しないことです。

［画像: Swiss Tableの成長は、選択されたテーブルのみを再構築します。］

Swiss Tableの成長は、選択されたテーブルのみを再構築します。

Goチームのマイクロベンチマークでは、マップ操作はGo 1.23と比較して最大60%高速になりましたが、一部のエッジケースは遅くなりました。完全なアプリケーションベンチマークでは、幾何平均CPU時間の改善は約1.5%でした。

データ構造について議論したいのはこれだけです。設計と各部分がどのように役立つかを要約しましょう。

Part	What it helps with
Control bytes + groups of 8	Compare H2 with 8 control bytes together, then compare complete keys only in candidate slots.
Open addressing	Look for space in the same table array, without adding overflow buckets or following their pointers.
Triangular probing	Reduce the long runs of full groups that linear probing can build up.
Load factor of `7 / 8`	Keep empty slots so a missing lookup can stop early, before it has to check every group. We will explain this in Why load factor? below.
Directory + tables	Let one table grow or split without moving entries from every other table.
Maximum of 1024 slots per table	Limit the entries moved by each table rebuild, helping avoid long delays in the insertion that triggers it.

## ボーナス

### 削除

以前に紹介した3つの制御状態に戻り、今回はdeletedに焦点を当てましょう。

［画像: 削除された制御状態がこのセクションの焦点です。］

削除された制御状態がこのセクションの焦点です。

emptyスロットとdeletedスロットはどちらもライブなキー・バリューエントリを含んでいませんが、ルックアップ中に異なる意味を持ちます。

ルックアップ中：

Goはまず、現在のグループの候補スロットに要求されたキーが含まれているかどうかを確認します。
Goが候補スロットでキーを見つけられず、グループにempty制御バイトが含まれている場合、Goは早期に停止できます。
deleted制御バイトは同じ保証を提供できません。なぜなら、このスロットが削除される前に別のキーが後続のグループに挿入されている可能性があるため、Goはプローブシーケンス内の他のグループをチェックし続ける必要があるからです。

empty状態は、空きスロットの後や後続のグループにキーが存在しないことを意味するわけではありません。他のキーはまだそこに格納されている可能性があります。これは、要求されたキーが同じプローブシーケンスに沿って後続のグループに配置できないことだけを意味します。

しかし、キーを削除しても常にdeletedスロットが生成されるわけではありません。1つのグループしかない小さなマップでは、ルックアップには後続のグループがないため、削除されたスロットは常にemptyになります。

より大きなテーブルベースのマップでは、グループにすでに少なくとも1つの他のemptyスロットが含まれている場合、削除されたスロットもemptyになります。グループにemptyスロットがない場合、Goは削除されたスロットをdeletedとマークして、ルックアップが後続のグループに進めるようにします。

### なぜロードファクターか？

以前、Goは次の新しいキーがテーブルメンテナンスを必要とする前に、ライブエントリと削除されたスロットがテーブルの最大7 / 8を占めることを許可すると述べました。この比率がテーブルのロードファクターです。

load factor = (live entries + deleted slots) / table slots

現在のテーブルは16スロットで、削除されたスロットはありません。ロードファクター7 / 8は、14個のライブエントリのスペースを提供します。

14 / 16 = 7 / 8 = 87.5%

なぜGoはここで停止し、すべての16スロットを埋めないのでしょうか？

三角プローブシーケンスはグループインデックスを選択し、Goは選択されたグループを1つずつスキャンします。この作業はプローブされたグループ全体のリニアスキャンであるため、4つのグループをチェックするには4回の個別のグループチェックが必要です。

同じロードファクターを32スロットのテーブルに拡張してみましょう。これは28個のライブエントリを格納でき、4つの空きスロットを保持できます。4つの空きスロットすべてが1つのグループに配置され、他の3つのグループは満杯になっている可能性があります。

［画像: 空きスロットは、2つの後続グループの前にルックアップを停止させます。］

空きスロットは、2つの後続グループの前にルックアップを停止させます。

グループ0から始まる欠落ルックアップを想定します。4つのグループでは、三角プローブシーケンスは0 -> 1 -> 3 -> 2です。Goはグループ0、次にグループ1をチェックします。グループ1の空の制御バイトがルックアップを停止させるため、Goはグループ3と2の両方にエントリが含まれているにもかかわらず、それらをチェックしません。

テーブルがいっぱいになるにつれて、空きスロットを見つけるのが難しくなります。欠落ルックアップは、空の制御バイトに到達する前に、より多くのグループをスキャンする可能性があります。すべてのスロットが満杯の場合、空の制御バイトはスキャンを停止できないため、Goは欠落キーを報告する前にすべてのグループをチェックする必要があります。

7 / 8の制限により、このスキャンコストが高くなりすぎる前に、テーブル内にいくつかの空きスロットが保持されます。

Goは別の制限を選択できますか？はい。

より低い制限はより多くのメモリを使用しますが、通常はプローブシーケンスを短縮します。
より高い制限は、より少ない未使用メモリを残しますが、通常はプローブシーケンスを長くします。

Goは現在、AbseilのSwiss Tableと同じ7 / 8の制限を使用しています。

### 分割グループレイアウト

議論する価値のあるもう1つのマップの変更点があります。Go 1.27にはmapsplitgroupという実験的なグループレイアウトが含まれており、GOEXPERIMENT=mapsplitgroupで有効にできます。

名前にもかかわらず、この実験はマップアルゴリズム、ハッシュ分割、またはプローブシーケンスを変更しません。これは、1つのグループがメモリ内で8つのキーと値をどのように配置するかを変更するだけです。

デフォルトでは、Go 1.27は各キーを値の隣に格納します。

control:  42     17     -      -
slots:    dog:1  cat:2  empty  empty

内部レイアウトはおおよそ次のようになります。

slots [8]struct {
	key  string
	value int
}

実験的なレイアウトはキーを値から分離します。

keys   [8]string
values [8]int

2つの配列は依然として同じエントリを記述しています。インデックス1では、keys[1]は"cat"を格納し、values[1]は2を格納します。

"cat"を見てみましょう。その制御バイトはインデックス1を候補として識別するため、Goはkeys[1]を読み取り、"cat"と比較します。しかし、この時点でvalues[1]が必要でしょうか？いいえ。

［画像: ルックアップはvalues[1]の前にkeys[1]を読み取ります。］

ルックアップはvalues[1]の前にkeys[1]を読み取ります。

Goはキーが一致した後でのみvalues[1]を読み取ります。これが新しいレイアウトがキーをまとめている理由です。検索中、Goは候補キーを読み取りますが、値はキーの読み取り後にのみ役立ちます。値はもはやそれらのキーの読み取り間に配置されません。

分割レイアウトはメモリ使用量も削減できます。map[int64]struct{}、セットとしてよく使用されるマップを考えてみましょう。各キーは8バイトを必要とし、空の値はデータを格納しません。しかし、古いレイアウトでは、空の値が8バイトのパディングを追加するため、各{key, value}スロットに16バイトが使用されます。

制御ワードは変更されていないため、その下のストレージのみを比較する必要があります。

［画像: 古いレイアウトは制御ワードの下に128バイトを使用します。］

古いレイアウトは制御ワードの下に128バイトを使用します。

古いスロットレイアウトは8つのスロット全体で128バイトを使用します。8つのキーは64バイトを使用しますが、各スロットには8バイトのパディングも含まれており、さらに64バイトを追加します。

分割レイアウトは、8つのキーをまとめて保持します。

［画像: 分割レイアウトは制御ワードの下に72バイトを使用します。］

分割レイアウトは制御ワードの下に72バイトを使用します。

8つのキーは依然として64バイトを使用します。空の値配列は要素データを追加しませんが、Goはその後ろに1つの8バイトの末尾パディング領域を追加します。したがって、制御ワード下のストレージは合計72バイトを使用し、1つのグループで56バイトを節約します。

GoはCL 711560でGOEXPERIMENT=mapsplitgroupの背後でこのレイアウトを導入し、CL 820500で開発ブランチでデフォルトで有効にしました。

## リソース

The Go specification: Map types
Go 1.24 release notes: Runtime
Faster Go maps with Swiss Tables
Go 1.27 runtime source: map.go, table.go, group.go, and runtime.go
Go 1.27 map ABI and group layout
Go 1.23.12 map implementation
Abseil Swiss Tables Design Notes
Split group layout: CL 711560 and CL 820500
Go Maps Explained: How Key-Value Pairs Are Actually Stored

## 私たちについて

私たちはVictoriaMetricsです。世界中のユーザーに信頼され、オブザーバビリティコストを削減する、オープンソースでスケーラブルかつコスト効率の高いモニタリング、ロギング、トレーシングソリューションを提供するチームです。詳細については、VictoriaMetrics、VictoriaLogs、およびVictoriaTracesをご覧ください。