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

ブログ / Goの組み込みマップはSwiss Tableでどのように動作するか Goの組み込みマップはSwiss Tableでどのように動作するかGo @ VictoriaMetricsオープンソース技術共有: 以前、Goマップとその古いランタイム実装について「Goマップ解説: キー・バリューペアは実際にどのように格納されるか」という記事で書きました。Go 1.24はこの実装をSwiss Tableに基づく設計に置き換えましたので、更新する時期が来ました。 古い記事を読み返す必要はありません。新しいランタイムの内部構造に入る前に、マップの動作と必要な概念を復習します。 Goブログには「Swiss TableによるGoマップの高速化」という優れた記事もあります。それはより深く掘り下げ、ある程度の予備知識を前提としています。私たちは異なるアプローチを取ります。同じ実装をより段階的に、視覚的に議論するので、少しリラックスして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を指すようにします。 トップにある2つのフィールドは、エントリのストレージではなく、マップ自体を記述しています。 type Map struct { used uint64 seed uintptr ... } usedは現在格納されているエントリの数をカウントします。Goはエントリの数をどこで見つけるか正確に知っているので、len(m)と書くと、Goはこの呼び出しをMapの最初のフィールドへのアクセスに置き換え、それをintに変換します。そのため、len(m)はマップ全体をスキャンするのではなくO(1)になります。 seedは興味深いフィールドです。なぜなら、異なるマップが同じキーを異なる方法で分散させる原因となるからです。Goは、すべてのマップに対してこのフィールドをランダムな数値で初期化します。 マップが異なるシードを使用すると、同じエントリは異なる方法で配置されます。 上の配列は、この説明のために使用された簡略化された表現にすぎません。実際のデータ構造はより複雑です。 Goがマップのストレージ内のキーを見つける必要があるときはいつでも、マップのシードを使用してそのキーをハッシュします。各マップは独自のシードを受け取るため、2つのマップで同じキーをハッシュすると、異なるハッシュ値、したがって異なるストレージ場所が生成される可能性があります。 グループ マップは、保持するキー・バリューペアの数に応じてストレージを異なる方法で配置します。 最小の形式では、マップはグループと呼ばれる構造体に最大8つのキー・バリューペアを格納します。これは、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はシードを使用してキーをハッシュし、そのハッシュを2つの部分に分割します。ほとんどの64ビットターゲットでは、上位57ビットがH1、下位7ビットがH2と呼ばれます。例として、「cow」という別のキーがあり、H2が42になると仮定しましょう。 A 64ビットハッシュにはH1と7ビットのH2が含まれます。 H1は、Goがマップのストレージ内の検索を開始する場所を選択するために使用するハッシュの最初の部分です。小さいマップにはグループが1つしかないため、選択するものがありません。マップが大きくなるまで、これを脇に置いておきましょう。 H2は、ライブスロットの上にある制御バイトに格納される部分です。 しかし、制御バイトは8ビットですが、H2は7ビットしか使用しないため、まだ1ビット残っています。Goはこの最上位ビットを使用して、スロットにライブエントリが含まれているか、特別な状態であるかを判断します。このビットが0の場合、下位7ビットはH2を含みます。このビットが1の場合、制御バイト全体が空または削除済みを表します。 A control byte represents a live, empty, or deleted slot. スロットにキー・バリューエントリが含まれている場合、最上位ビットは0で、下位7ビットはH2を含みます。H2 42はバイナリで0101010なので、「cow」の完全な制御バイトは00101010になります。 最上位ビットが1の場合、制御バイトはH2の代わりに特別な値を格納します。空のスロットは10000000を使用します。削除済みスロットは11111110を使用し、これは「墓石」とも呼ばれます。どちらの状態もライブなキー・バリューエントリを含みませんが、ルックアップは空のスロットで停止できますが、削除済みスロットはスキップする必要があります。この区別については、削除のセクションで再度説明します。 このレイアウトにより、制御バイトは、完全なキーをスロットから読み取る前に、Goが2つの質問に答えることができます。 このスロットにはライブエントリが含まれていますか、それとも空または削除済みですか？ スロットにライブエントリが含まれている場合、そのキーは探しているものですか？ 元のグループに戻りましょう。 A group pairs each control byte with the key-value slot below it. 次に、「cow」キーに値5を割り当てます。 m["cow"] = 5 値を更新する前に、Goは既存のキーを見つける必要があります。ハッシュからH2 42を取得し、グループ内のすべての8つの制御バイトと比較します。 H2 42はdogとcowを候補キーとして選択します。 Goは8つのスロットを1つずつ訪れてH2を各制御バイトと個別に比較するわけではありません。AMD64では、GoはSIMD命令を使用してH2 42をこれらの8つの制御バイトすべてと同時に比較します。 SIMDにより、CPUは同じ比較を複数のバイト値に並列に適用できます。AMD64では、結果は各スロットに1ビットを持つパックされたビットマップになります。 A control-word comparison produces the candidate bitmap. 私たちのグループでは、制御バイトに42が含まれているため、スロット0と2のビットが設定されています。他のビットはクリアされており、他の6つのスロットは完全なキーを読み取ることなくマスクされます。 他のアーキテクチャでは、算術演算とビット演算を使用して同じ候補マスクを生成します。