HN 日本語サマリー

← 一覧へ戻る
プログラミング

高性能配列ベース LRU ハッシュテーブル

High-Performance Array-Backed LRU Hash Table (github.com)

4 pointsby adanil_0 コメント

要約

このプロジェクトは、マルチコアのスケーラビリティ、予測可能なテールレイテンシ、NUMA アーキテクチャ、ゼロランタイムアロケーションに最適化された、高性能な並列 LRU ハッシュテーブルを提案しています。標準ライブラリのコンテナが競合下でパフォーマンスを低下させるような、キャッシングレイヤーやネットワークインフラストラクチャなどの要求の厳しいシステムプログラミングワークロード向けに設計されています。

全文翻訳

高性能配列バック型LRUハッシュテーブル

[画像: Platform: Windows | Linux | macOS] [画像: Language: C++20] [画像: Environment: User & Kernel Mode]

並行LRUハッシュテーブルで、以下に最適化されています。

  • マルチコアのスケーラビリティ
  • 予測可能なテールレイテンシ
  • NUMAアーキテクチャ
  • ゼロランタイムアロケーション

目次

  1. 問題点: 標準ライブラリのボトルネック
  2. 解決策: コアアーキテクチャとアルゴリズム
  3. ベンチマークとスケーリングパフォーマンス
  4. このテーブルが最適でない場合
  5. クイックスタートAPI概要
  6. プロジェクト構造
  7. テストコードのビルド
  8. 結論と将来のハードウェア予測
  9. ライセンス

要求の厳しいシステムプログラミングワークロード(キャッシングレイヤー、ネットワークインフラストラクチャ、カーネルコンポーネントなど)向けに設計された、高性能な並行LRUハッシュテーブルです。シャードベースの並列処理とキャッシュフレンドリーなメモリレイアウトを活用することで、標準ライブラリコンテナが競合下でパフォーマンスを低下させる環境でも、高いスループットを実現します。

主要なアーキテクチャのハイライト
  • ゼロランタイムアロケーション: 事前に割り当てられたフラット配列により、ヒープの断片化とOSレベルのロック遅延を排除します。
  • カスタムTTASスピンロック: std::shared_mutex(標準ライブラリの並行LRUベースラインで使用)を置き換え、OSコンテキストスイッチとリーダー・ライターロックのアップグレードの危険性を排除し、14倍以上のスループットとサブマイクロ秒のテールレイテンシを実現します。(注: ユーザモードではカスタムTTASスピンロックを、カーネルモードではEX_PUSH_LOCKを使用します)。
  • シャードアーキテクチャ: グローバルロックのコンボイを排除し、物理CPUコア数に比例してスケールします。
  • NUMA対応メモリ: シャードの割り当てを物理CPUソケット全体に分散させ、メモリコントローラーの帯域幅を最大化します。
  • ロックフリーの破棄: ペイロードは同期境界の外で明示的に破棄され、フラットなテールレイテンシを保証します。
  • 遅延LRUプロモーション: チューニング可能な「セーフゾーン」は、ホットリード時に高価なLRUプロモーション(従来のstd::shared_mutex設計で排他ロックアップグレードが必要で、複数のキャッシュラインをダーティにする)をバイパスし、約20%のスループット向上をもたらします。
  • カスタムアロケータ(ユーザモード): ドメイン固有のメモリ管理のために、自動キャッシュラインアライメントを備えたテンプレート注入アロケータをサポートします。
  • デュアル環境対応: クロスプラットフォームのユーザモードサポート(x86_64およびARM64)に加え、専用のWindows 10+カーネル実装(IRQL < DISPATCH_LEVEL)を備えています。

この実装は、メカニカルシンパシー、キャッシュ局所性、ロックのスケーラビリティ、予測可能なメモリ動作を優先しており、以下のような要求の厳しい環境に適しています。

  • 高頻度取引(HFT)インフラストラクチャ
  • ストレージサブシステムキャッシュ
  • リアルタイムネットワークルーティング
  • カーネル/ドライバコンポーネント
  • 高スループットWebサーバー

この実装は、挿入、検索、削除に対して平均O(1)時間操作を提供し、厳密または確率的なLeast Recently Used(LRU)エビクションポリシーを維持します。


問題点: 標準ライブラリのボトルネック

典型的な並行LRU実装(テストスイートのstd_lru_hash_table.hベースラインなど、std::unordered_map + std::listをstd::shared_mutexで保護したもの)は、最新のハイコア数CPUにおいて深刻なアーキテクチャ上の欠陥に悩まされています。

  1. グローバルロック競合とアップグレードの危険性: 単一のstd::shared_mutexは壊滅的な「ロックコンボイ」を作成し、リード時にアイテムをMRUに昇格させるには、共有リードロックを解放し、排他ライトロックを取得し、ABAの危険性に対して状態を再検証する必要があります。これにより、スレッドを追加すると実際の総スループットが低下します。
  2. ポインタチェイシング: ヒープを横断するノードのトラバーサルは、L1/L2キャッシュの局所性を破壊します。
  3. アロケータのオーバーヘッド: 各挿入/エビクションはヒープアロケーション/デアロケーション(new/delete)をトリガーし、メモリの断片化とOSレベルのロック遅延を引き起こします。
  4. 偽共有: アライメントされていないメモリ構造は、隣接するCPUコアがお互いのL1キャッシュラインを無効化し、パフォーマンスを静かに破壊します。

解決策: コアアーキテクチャとアルゴリズム

このプロジェクトは、シャード分割、フラットアレイメモリ管理、ロックフリー破棄技術の組み合わせにより、標準ライブラリのボトルネックを解決します。

この図は、データ​​を独立したキャッシュアラインされたシャードにパーティショニングすることで、グローバルロック競合を排除するLRUハッシュテーブルのアーキテクチャを示しています。各シャードは、独自の排他TTASスピンロック(KMではプッシュロック)とメタデータカウンター、およびバケットとノード配列を含む連続した「メガブロック」で自律的に動作します。これらの配列内では、ハッシュ衝突チェーンと双方向LRUキューの両方が、標準の64ビットポインタではなく32ビット配列インデックスを使用して構築されています。これにより、構造メモリのオーバーヘッドが半分になり、ホットパス操作中のL1/L2キャッシュの局所性が向上します。

高レベルでは、テーブルは独立したシャードにパーティショニングされ、各シャードが独自のハッシュテーブルとLRUチェーンを管理します。

=============================================================================
                      [ マスターハッシュテーブルオブジェクト ]                      
=============================================================================
      |
      +---> [ シャード配列 ] (連続アラインブロック、CPUコア数 * 32 にスケール)
              |
              +--- [ シャード 0 ] (偽共有を防ぐため 64/128 バイトアライン)
              |      |
              |      +-- 同期 : 排他TTASスピンロック (UM) / EX_PUSH_LOCK (KM)
              |      |
              |      +-- メタデータカウンター   : ActiveCount, Capacity, Generation, ThresholdAge
              |      |
              |      +-- チェーンポインタ  : LruHead, LruTail, FreeHead (32ビットインデックス)
              |      |
              |      |                     (ハッシュ衝突チェーンは HashNext 経由)
              |      +-- バケット配列   : [ Head_Idx ] [ INVALID ] [ Head_Idx ] ...
              |      |                           |
              |      |                           v
              |      +-- ノード配列     : [ Node 0 ]                 [ Node 4 ]
              |          (メガブロック)
              |                            [ Node 1 ] <--- FreeHead       |
              |                            [ Node 2 ] <--- LruHead        v
              |                            [ Node 3 ]                 [ Node 5 ]
              |                            ...
              |                            [ Node N ] <--- LruTail (次のエビクション)
              |                            
              |     (LruNode内) --> +-----------------------------------+
              |                          | HOT PATH: Hash, HashNext, LruPrev |
              |                          | MATCH:    union { TKey Key; }     |
              |                          | COLD:     TValue*, LastPromoted,  |
              |                          |           LruNext                 |
              |                          +-----------------------------------+
              |
              +--- [ シャード 1 ] (独立したロックと容量制限)
              |      |
              |      +-- 同期 : ...
              |      +-- バケット配列   : [ ... ]
              |      +-- ノード配列     : [ ... ]
              |
              +--- [ シャード 2 ]
              |
             ...
              |
              +--- [ シャード N ]
ノードメモリレイアウト(メカニカルシンパシー)

L1/L2キャッシュヒット率を最大化するため、内部ノード構造はアクセス頻度に基づいてデータを明示的に分離します。

ホットパス(最初のキャッシュライン): 衝突チェーンのナビゲートと一致の検証に重要な変数(Hash, HashNext, LruPrev, Key)は、最初のハードウェアキャッシュライン(アーキテクチャに応じて64バイトまたは128バイト)に密にパックされています。これにより、CPUは高価なメインメモリの遅延をトリガーすることなく、単一のメモリフェッチで深いハッシュバケットをスキャンできます。

コールドパス: キーの一致またはエビクション後にのみ必要な変数(Value*, LastPromoted, LruNext)は、セカンダリフィールドにオフセットされます。これにより、検索スキャン中に単にスキップされるノードのペイロードポインタや年齢メトリックを取得する際に、メモリコントローラーが無駄な帯域幅を使用しないことが保証されます。

-------------------------------------------------
| Hash | HashNext | LruPrev | Key |              |
-------------------------------------------------
| Value* | LastPromoted | LruNext |              |
-------------------------------------------------
HOT PATH (キャッシュライン)     COLD PATH
1. シャード並列処理

テーブルは独立した、分離されたシャードに分割されます。各シャードには、独自のハッシュバケット、LRUリスト、スピンロック、および容量制限が含まれます。

  • シャード数は、プロセッサトポロジ(shards ≈ CPUコア数 × 32、最大4096)に基づいて動的にスケーリングされます。
  • スレッドと内部バケットは、ハードウェアアクセラレーテッド128ビット乗算・折り畳みミキサー(MixHash、wyhashスタイルMUM)と64ビット素数定数(0x8bb84b93962eacc9ULL)を使用してルーティングされます。ネイティブ64ビット乗算命令(x64では_umul128、ARM64では__umulh、GCC/Clangではunsigned __int128)を活用することで、ミキシング依存チェーンをわずか2〜3命令(乗算+XOR)に短縮します。
  • これにより、高次エントロピーがすべてのビットに徹底的に分散され、ミキシングされたハッシュの異なるビット範囲が、ビットオーバーラップ相関なしにシャードとシャード内のバケットの両方を独立してルーティングできるようになります(shard = MixHash(hash) & (ShardCount - 1)およびbucket = (MixHash(hash) >> 12) & BucketMask)。
  • これにより、弱い、アラインされた、またはシーケンシャルなキーでのクラスタリングが防止され、検索ごとに約3〜4 CPUサイクルが節約され、ワーストケースのP99.99テールレイテンシのスパイクが大幅に削減され、設計上グローバルロック競合が回避されます。
2. 配列バック型メガブロックと32ビットインデックス

ノードをヒープに個別に割り当てる代わりに、すべてのノードとバケットは連続したフラット配列(メガブロック)に事前に割り当てられます。

  • ゼロランタイムアロケーション: 初期化後、テーブルはヒープまたはプールメモリを割り当てるためにnewまたはdeleteを呼び出しません。
  • 相対32ビットインデックス: リンクリスト(LRUチェーンとハッシュ衝突)は、64ビットポインタの代わりに32ビット配列インデックスを使用して実装されます。これにより、構造メモリのオーバーヘッドが半分になり、CPUのL1/L2キャッシュに収まるノードの数が劇的に増加します。
  • NUMA対応: ユーザモードテーブルはVirtualAllocExNuma(Windows)またはlibnuma(Linux)を使用し、カーネルモードテーブルはExAllocatePool3を使用して、シャードの割り当てを物理CPUソケット全体に均等に分散させ、メモリコントローラーの帯域幅を最大化します。
3. メカニカルシンパシーとキャッシュ管理

メモリレイアウトは、ハードウェア固有のキャッシュアライメントを尊重するように厳密に制御されます。ユーザモード(UM)実装は、アライメント(x86_64/標準ARM64では64バイト、Apple Siliconでは128バイト)を動的に調整しますが、カーネルモード(KM)実装は、標準Windowsアーキテクチャ(x64およびARM64)に対して64バイトアライメントを静的にターゲットとします。Shard配列とシャードごとのメガブロックの両方がオーバーアロケートされ、正確なキャッシュライン境界にアラインされます。

偽共有防止:

struct alignas(CACHE_LINE_SIZE) Shard { ... }; // UMでは64または128バイト、KMでは厳密に64バイト

シャードはこれらのハードウェア固有のキャッシュライン境界に明示的にパディングされます。シャードAをロックするスレッドは、シャードBにアクセスするスレッドのキャッシュラインを無効化しません。

ホット/コールドパス構造パッキングとC++20ライフタイム安全性:

struct alignas(CACHE_LINE_SIZE) LruNode 
{
    // --- HOT PATH (最初のキャッシュライン) ---
    uint64_t Hash;         // 再ハッシュを避けるためにキャッシュ
    uint32_t HashNext;     // ハッシュ衝突チェーンインデックス
    uint32_t LruPrev;      // LRUチェーンインデックス
    union
    {
        TKey Key;          // 16バイト境界から開始
    };
    
    // --- COLD PATH ---
    TValue* Value;         // 正確な一致でのみアクセス
    uint64_t LastPromoted; // 年齢追跡
    uint32_t LruNext;      // LRUチェーンインデックス
};

ハッシュトラバーサルに必要な変数は、最初のキャッシュラインの最初の部分にパックされています。CPUはこれらを単一の読み取りでまとめてフェッチし、深い衝突チェーンプロービング中のキャッシュヒットを保証します。一方、Lookup()、Add()、Remove()は、ロック取得前にバケットヘッドのソフトウェアプリフェッチヒント(CACHE_PREFETCH)を発行します。Keyを制限のない匿名unionでラップすることで、LruNode配列を事前に割り当てても、配置newの前に非自明なTKey型が暗黙的に構築/破棄されないことが保証されます。

4. 高度な並行制御
  • ロック外での破棄と高速パスインプレース構築: デッドロックとレイテンシスパイクは、高価なユーザー破棄コードが同期境界の外で実行されることを保証することで回避されます。エビクトされたノードはデタッチされ、ロックが解放され、その後ペイロードが破棄/解放されます。Add()中にフリーノードが利用可能な場合、自明にコピー可能なキー(UMではstd::is_trivially_copy_constructible_v<TKey>、KMでは__is_trivially_copyable(TKey))は単一のロック取得内でインプレース構築されますが、非自明なキーはコピー構築中にロックを解放します。

  • 同期列挙の警告: デストラクタはロックフリーで実行されますが、Enumerate() constメソッドはアクティブなシャードの排他ロックを保持しながらユーザーコールバックを同期的に実行します(ハッシュ不変性を保護するためにconst TKey&を渡します)。再帰的デッドロックを防ぐため、ユーザーコールバックはテーブルを変更しようとしてはいけません。

  • 遅延LRUプロモーション(世代カウンター): std::shared_mutexに基づく従来の並行LRUは、すべてのリードでアイテムをMRUヘッドに昇格させますが、これは高価な共有から排他へのロックアップグレードとABA再検証ループを必要とします。代わりに、この実装は微小な排他シャードロックを取得し、確率的なGenerationカウンターを使用します。リードが「ホット」なアイテムにヒットし、その年齢差(Generation - LastPromoted)がしきい値内にある場合、プロモーションはスキップされます。これにより、リーダー・ライターのアップグレードの危険性が回避され、LRUリストと隣接ノードのキャッシュラインのダーティ化が回避され、スレッドはリードを即座に完了できます。

  • オプションのプロアクティブトリミング(パイプライン実行): テーブルは完全に自律的です。シャードが容量に達すると、Add()は自動的にインラインLRUエビクションを実行してスペースを確保します。したがって、継続的な操作のために専用のバックグラウンドトリミングスレッドは必要ありません。ただし、超フラットなP99/P99.9テールレイテンシをフォアグラウンドホットパスで保証するために、比較的アイドルなサイクル中または低優先度のバックグラウンドワーカーからTrim()をオプションで呼び出すことができます。90%の高水準マークを超えたシャードからアクティブなアイテムを85%の低水準マークまでプロアクティブにトリミングすることで、フォアグラウンド挿入が常にウォームで事前に割り当てられたフリーノードにヒットすることが保証されます。Trim()がシャードロックを長時間保持しないようにするために、一度に1つのノードをデタッチし、ロックを解放してキーを破棄し値を解放し、ロック解除中にハードウェアポーズ(CPU_PAUSE() / YieldProcessor())を実行してフォアグラウンドスレッドがキャッシュライン調停に勝てるようにし、クリーンアップされたノードのFreeHeadへの返却を次のイテレーションのロック取得にパイプライン処理します(エビクトされたノードあたりのロック取得回数を半分に削減)。

5. ポリシー駆動スピンロック(ユーザモード)

配列バック型テーブルは、微小なクリティカルセクション専用に設計されたカスタムSpinLockでstd::shared_mutexを置き換えます。非競合の高速パスでは即座にexchange(true, acquire)を試行し、競合下ではTTASパターンを実装して、マルチソケット/マルチコアシステムでのMESIプロトコルバスフラッド(「キャッシュラインバウンス」)を厳密に防止します。標準のyield命令がシングルスレッドコアで1サイクルNOPとして実行されるARM64では、CPU_PAUSE()はバストラフィックなしでパイプラインを約15〜30サイクル一時停止する命令同期バリア(isb)を使用し、早期のOSスリープストームを防ぎます。

サポートされるスピンポリシー: 異なる実行環境に対応するため、ロックの動作はコンパイル時に注入されます。

  • AdaptiveSpinPolicy (デフォルト): ユーザースペースで最大4,000回のハードウェアポーズをスピンすることでスループットを最大化し、深刻な競合下でのデッドロックとLHP遅延を防ぐために、強制的なOSデスケジュール(WindowsではSwitchToThread、macOSではsched_yield、Linuxでは500ns nanosleep)にフォールバックします。
  • ExponentialBackoffPolicy (オプトイン): 高競合環境向けに動的な自己調整バックオフ戦略を実装します。一定レートでロックをポーリングする代わりに、待機スレッドは最大4,000回のポーズまで、失敗したチェックごとにハードウェアポーズバッチ(1, 2, 4, 8)を倍増させてから、OSスケジューラに譲ります。
6. 適応型シャードスケーリング(小規模テーブル)

小規模データセットでの同期オーバーヘッドを回避するため、実装は小容量に対してアクティブシャードを自動的にスケールダウンします。シャード計算アルゴリズムは統計的なハッシュクラスタリングを安全に吸収するために約64アイテム/シャードをターゲットとしていますが、テーブルはシャードあたり最低8アイテムを強制します。

これにより、小規模テーブルは不要なロックまたはメモリ断片化コストを被ることなく、同じAPIと動作を維持できます。


ベンチマークとスケーリングパフォーマンス

アーキテクチャを証明するため、カスタム配列テーブルは、3つの異なるハードウェアトポロジにわたって標準ライブラリベースライン実装(test_common/std_lru_hash_table.h、std::unordered_map + std::list + std::shared_mutexを使用)と比較してベンチマークされました。

  • Intel Core i7-1165G7(4コア/8スレッド、低電力)
  • Intel Core i7-8086K(6コア/12スレッド、高クロック)
  • Intel Core i7-12700H(14コア/20スレッド、Big.LITTLE)

ワークロード: 容量1,000,000、Add/Lookup/Remove/Trimの混合、セーフゾーン0%。マルチスレッドスケーリング(「ロックコンボイ」の崩壊)

1. マルチスレッドスケーリング(「ロックコンボイ」の崩壊)

配列バック型テーブルはハードウェアの増加に伴って正にスケールしますが、標準ライブラリ実装は重い混合競合下で負のスケーリングを示します。

実装i7-1165G7(モバイル、8スレッド)i7-8086K(デスクトップ、12スレッド)i7-12700H(ハイブリッド、20スレッド)
標準: Map+List0.70倍(負のスケーリング)0.67倍(負のスケーリング)0.49倍(負のスケーリング)
配列テーブル3.41倍(8スレッド時)7.28倍(12スレッド時)7.51倍(20スレッド時)
スレッドスケーリングスイープグラフ(Intel Core i7-8086K)

[画像: Thread Scaling Sweep]

2. 予測可能なテールレイテンシ(P99.9、P99.99)

極端なパーセンタイルでは、配列バック型テーブルは低マイクロ秒レイテンシを維持し、標準OS仲介ロック(std::shared_mutex)に特徴的な深刻なレイテンシスパイクを回避します。

99.9パーセンタイルでは、ワーストケースのアルゴリズム競合(例: std::shared_mutexベースラインでの深いハッシュ衝突またはロックアップグレード)を測定します。カスタム配列は低マイクロ秒レイテンシを維持します。

メトリック(P99.9レイテンシ)i7-1165G7(モバイル)i7-8086K(デスクトップ)i7-12700H(ハイブリッド)
標準: Map+List1,039,800 ns575,600 ns659,800 ns
配列テーブル4,900 ns1,600 ns2,600 ns
安定性優位性212倍安定360倍安定253倍安定

99.99パーセンタイル(P99.99)では、OS仲介ロックの真のコストを観察します。

メトリック(P99.99レイテンシ)i7-1165G7(モバイル)i7-8086K(デスクトップ)i7-12700H(ハイブリッド)
標準: Map+List2,017,400 ns983,100 ns1,078,800 ns
配列テーブル12,000 ns6,400 ns20,600 ns
安定性優位性168倍安定153倍安定52倍安定

(注: i7-12700HでのP99.99における20.6µsへのジャンプは、OSスレッドディレクターがPコアとEコア間でスレッドを移行し、L1/L2キャッシュフラッシュを強制したハードウェアシグネチャです)。

3. 総スループット速度向上(混合競合)

重い混合ワークロード(同時読み取り、書き込み、エビクション)下では、アーキテクチャの違いが累積的なパフォーマンスギャップを生み出します。コア数が増加するにつれて、標準テーブルは競合によりスループットを失いますが、シャード化された配列バック型テーブルは加速します。

システムプロファイル配列テーブル Ops/秒標準 Ops/秒総速度向上
モバイル(4コア/8スレッド)26.7 Million3.0 Million約8.9倍高速
デスクトップ(6コア/12スレッド)53.0 Million3.1 Million約17.1倍高速
ハイブリッド(14コア/20スレッド)48.0 Million2.3 Million約20.9倍高速
4. 遅延LRUプロモーションの影響(LRU更新の遅延)

リーダーライターロック(std::shared_mutex)に基づく厳密なLRUキャッシュは、重いリード競合下でパフォーマンスが低下します。なぜなら、すべてのリードでLRUヘッドを更新するために排他ロックアップグレードが必要であり、排他ロック設計であっても、すべてのプロモーションで複数のキャッシュライン(LruHead、LruTail、および隣接ノードのLruPrev/LruNextインデックス)がダーティになるからです。

Generationカウンターを使用することで、キャッシュはアイテムを確率的に「エイジング」させます。アイテムがアクセスされたが、しきい値を超えてエイジングしていない場合、プロモーションはスキップされ、スレッドはノードやLRU状態キャッシュラインをダーティにすることなくリードを即座に完了できます。微小な排他ロックとリーダー・ライターアップグレードの危険性のオーバーヘッドなしに使用することで、従来のリーダー・ライターロック(std::shared_mutex)実装よりも高いスループットを実現します。

ワークロード: 6コアi7-8086Kで95%リード/5%ライト。

プロモーションしきい値動作Ops/秒パフォーマンスリフト
0%(厳密LRU)すべてのリードでプロモート71.4 Millionベースライン
25%(セーフゾーン)より古いアイテムのみプロモート79.6 Million+ 11.5%
50%(セーフゾーン)より古いアイテムのみプロモート82.8 Million+ 16.0%
100%(FIFO)リード時にプロモートしない86.2 Million+ 20.7%
5. クラウドと仮想化環境: ロックホルダープリエンプション(LHP)の克服

仮想化環境(VMware、AWS、Azure)のLinuxゲストでは、ロックホルダーがハイパーバイザーによってプリエンプトされると、スピンするvCPUはVM-Exitストームを引き起こす可能性があります(LHP)。標準ライブラリロック(std_lru_hash_table.hのstd::shared_mutex)は、重いOSコンテキストスイッチにより、この問題に深刻な影響を受けます。

これを克服するため、テーブルはカスタムスピンロックに依存しており、これは4,000回のハードウェアポーズの後、Linuxで500ナノ秒のnanosleepにフォールバックして、ハイパーバイザーにプリエンプトされたロックホルダーvCPUをスケジュールさせます。両方の利用可能なポリシーは、標準ライブラリstd::shared_mutexベースラインと比較してLHPを効果的に軽減しますが、パフォーマンス特性はゲストLinuxディストリビューションとその基盤となるCPUスケジューラによって大きく異なります。

ベンチマーク: VMware上のLinuxゲスト(Windows 10ホスト、4 vCPU)

異なるディストリビューションでのテストにより、最適なロック戦略はゲストOSに大きく依存することが明らかになりました。

  • Ubuntu: ExponentialBackoffPolicyは、ピークスケーリングスループットと引き換えに、より厳密なレイテンシバウンドを提供する、わずかに優れたP99.9テールレイテンシ安定性を提供します。
  • Fedora: AdaptiveSpinPolicyは、指数バックオフアプローチをあらゆる面で上回り、より優れたP99.9安定性とP99.99テールレイテンシを提供します。

クラウドデプロイメントの推奨事項: ハイパーバイザー構成とLinux CPUスケジューラ(CFSまたはEEVDF)は、定率スピンと指数バックオフの反応が異なるため、Linuxでは一方のポリシーを盲目的にデフォルトにしないでください。特定のターゲットOSとハイパーバイザーの組み合わせで両方のポリシーをプロファイルし、どちらがワークロードに最適なテールレイテンシをもたらすかを判断することを強くお勧めします。

ポリシーの切り替え方法(Linuxのみ): WindowsはLHPをネイティブに処理するため、この軽減策はLinuxデプロイメント専用です。デフォルトでは、ビルドはAdaptiveSpinPolicyを使用します。ビルドステップ中に条件付きコンパイルを使用して、指数バックオフロックをオプトインできます。

# Linuxハードウェア(例: Ubuntuターゲット)の仮想化用にExponentialBackoffPolicyを有効にする
cmake .. -DUSE_EXPONENTIAL_BACKOFF=ON
6. ベンチマークの再現

すべてのベンチマークは、Windows 10/11で、AdaptiveSpinPolicyスピンロック待機ポリシーでコンパイルされた、このリポジトリに含まれるtest_umスイートを使用して生成されました。


このテーブルが最適でない場合

このアーキテクチャは重い並行ワークロードで優れていますが、万能ではありません。いくつかのシナリオでは、標準ライブラリの構成(std::unordered_map + std::listなど)がより適切な選択肢となる場合があります。

  • 巨大なデータセット(シャードあたり40億アイテム以上): キャッシュ局所性を最大化するため、テーブルはリンクリストに64ビットポインタの代わりに32ビット配列インデックスを使用し、0xFFFFFFFF(INVALID_INDEX)をリスト終端センチネルとして予約します。したがって、単一のシャードはUINT32_MAX - 1アイテムを超えることは物理的にアドレス指定できません。データセットがこの容量/シャードを超える場合、初期化は安全に中止されます。
  • 非常に小さなテーブル(〜100アイテム未満): テーブルは内部的に容量が小さい場合にシャード数を減らしますが(シャードあたり最低64アイテムを強制し、128エントリ未満で単一シャードに折り畳みます)、ハードウェアハッシュミキシング(MixHash)、アトミック参照カウント、シャードルーティングのベースラインオーバーヘッドは、微小なデータセットでは支配的になる可能性があります。これらの場合、std::mutexで保護された単純なSTLベースのLRUの方が高速な場合が多いです。
  • 厳密にシングルスレッドのワークロード: このテーブルは、マルチスレッドロックのボトルネックを解決するために明示的に設計されています。純粋なシングルスレッド環境では、標準のSTLベースLRUがこれを上回る可能性があります。標準コンテナは非競合実行に高度に最適化されていますが、配列バック型テーブルはアトミック操作、メモリバリア、スピンロック/プッシュロック取得の固定オーバーヘッドを依然として発生させます。
  • メモリ制約の厳しい環境: OSヒープ割り当てをゼロにし、ロック遅延を防ぐため、このテーブルは最大容量全体に対して事前にフラットな「メガブロック」を割り当てます。(注: ランタイム配置newは、キーを構築するためにこれらのブロック内でまだ実行されます)。環境が最大潜在メモリフットプリントを事前に割り当てられない場合、オンデマンドでメモリを割り当てる従来のノードベースコンテナを使用する必要があります。

クイックスタートAPI概要

値は、イントラジブ、スレッドセーフな参照カウントインターフェース(AddRef()とRelease()はnoexceptで宣言され、Release()はアキュア/リリースアトミックバリアを使用する必要があります)を継承または実装する必要があります。テーブルのコピー構築は無効化(= delete)されていますが、ムーブセマンティクスはサポートされています。

// 1. 初期化
using CustomTable = LruHashTable<uint64_t, RefCountedPayload, MyHasher>;
CustomTable table;

// 容量1M、LRUプロモーションセーフゾーン25%で初期化
table.Initialize(1000000, 25); 

// 2. プロアクティブトリミング(オプションの最適化でフラットテールレイテンシを維持)
// アイドル期間中または軽量バックグラウンドワーカー経由でスケジュールして実行できます。
std::jthread trimThread([&table](std::stop_token stoken) 
{
    while (!stoken.stop_requested()) 
    {
        // 最大5000個のLRUアイテムをエビクトしますが、90%の高水準マークを超えたシャードからのみ、85%で停止します。
        table.Trim(5000); 
        std::this_thread::sleep_for(std::chrono::milliseconds(350));
    }
});

// 3. 挿入
RefCountedPayload* payload = new RefCountedPayload(data);
payload->AddRef();
table.Add(key, payload);
payload->Release(); // ローカル参照を安全に解放

// 4. 検索
RefCountedPayload* out = nullptr;
if (table.Lookup(key, out)) 
{
    // ペイロードを使用...
    out->Release(); // 完了したら必ず解放する必要があります
}

// 5. 削除
table.Remove(key);

プロジェクト構造

リポジトリは、コアハッシュテーブルロジックを環境固有のラッパーやテストスイートから分離するために、明確なレイヤーに編成されています。

  • km/: カーネルモードLRUハッシュテーブル実装が含まれています。

    • LRUHashTable.h: Windowsドライバ環境(x64およびARM64)で使用するための主要ヘッダーです。
  • um/: ユーザモードLRUハッシュテーブル実装が含まれています。

    • lru_hash_table.h: Linux、macOS、Windowsアプリケーション(x86_64およびARM64)用のクロスプラットフォームヘッダーです。
    • lru_string_key.h: 高性能な文字列ベースのキー実装です。
  • test_common/: カーネルモードとユーザモードの両方のパフォーマンステストで使用される共有テストロジックです。

    • std_lru_hash_table.h: ベンチマーク比較のベースラインとして使用される標準ライブラリラッパー(std::unordered_map + std::list + std::shared_mutex)です。
    • test_lru_hash_common.h: 共有パフォーマンステストと検証ロジックです。
  • test_km/: ユーザモードパフォーマンステストハーネス内でカーネルモードロジックを検証するためのテストコードです。

    • TestLRUHashKm.cpp: ドライバロジックテストハーネス。MSVC 2026(Windows)が必須です。
  • test_um/: クロスプラットフォームユーザモードパフォーマンステストスイートです。

    • test_lru_hash.cpp: Linux、macOS、Windowsで使用される主要なベンチマークおよび検証ツールです。
  • test_drv/: ターゲットシステムにデプロイするための実際のWindowsカーネルドライバパフォーマンステストコードです。

    • TestLruDrv.cpp: Windowsカーネルドライバパフォーマンステストコードです。
  • sample_um/: ユーザモードサンプルコード。

    • sample_lru_hash.cpp: LRUハッシュテーブルで効率的な文字列ベースキーの使用方法を示すユーザモードC++サンプルです。

テストコードのビルド

Linux / macOS

C++20準拠のコンパイラ(GCCまたはClang)が必要です。

Linux依存関係: Linuxユーザモード実装は、libnumaを使用してシャード割り当てを物理CPUソケットにバインドし、Windowsカーネル実装のメモリコントローラールーティングを模倣します。ビルド前にNUMA開発ヘッダーをインストールする必要があります。

# Ubuntu / Debian
sudo apt-get update
sudo apt-get install libnuma-dev numactl

# RHEL / Fedora / CentOS
sudo dnf install numactl-devel

ビルドスクリプトの使用(推奨)

./build.sh [--clean | -c] [--hybrid] [--type Release | Debug] [--compiler g++ | clang++]

デフォルト:
 - ビルドタイプ: Release
 - コンパイラ: g++
 - ハイブリッドモード: OFF
 - 既存のビルド/を再利用

オプション:
-c, --clean → ビルド前にbuild/を削除
--hybrid    → Lock Holder Preemption (LHP) を仮想化ハードウェアでより良く軽減するためにLRU_USE_EXPONENTIAL_BACKOFFを有効にします。Linuxでビルドする場合、インストールされていればjemallocもリンクします。
-t, --type  → ビルドタイプを設定(ReleaseまたはDebug)
--compiler  → コンパイラを選択(g++またはclang++)
-h, --help  → ヘルプを表示して終了
# パーミッション設定(一度だけ):
chmod +x ./build.sh

# 標準リリースビルド(デフォルトC++コンパイラ使用)
./build.sh

# クリーンリリースビルド(clang++使用、macOSまたは特定のLinuxテストに最適化)
./build.sh --clean --type Release --compiler clang++

# デバッグビルド(トラブルシューティング用)
./build.sh --clean --type Debug

CMakeの使用 含まれているCMakeLists.txtは、プラットフォームを自動的に検出し、Linuxでlibnumaのリンクを処理し、最適化されたビルドフラグを設定します。

mkdir build && cd build
# 仮想化環境(VMware/AWS/Azure)用に-DUSE_EXPONENTIAL_BACKOFF=ONを使用
cmake .. -DCMAKE_BUILD_TYPE=Release
cmake --build . -j $(nproc)

手動コンパイル CMakeなしでビルドする場合、適切なリンクのために-pthreadおよび-lnuma(Linuxのみ)フラグを含めることを確認してください。

# GCC (Linux)
g++ -std=c++20 -O3 -march=native -flto=auto -funroll-loops -fomit-frame-pointer -fno-rtti -fexceptions -pthread \
    -I./um -I./test_um -I./test_common test_um/test_lru_hash.cpp -o bin/test_lru_hash -lnuma
	
# Clang (Linux/macOS - Macでは-lnumaを省略)
clang++ -std=c++20 -O3 -march=native -flto -funroll-loops -fomit-frame-pointer -fno-rtti -fexceptions -pthread \
    -I./um -I./test_um -I./test_common test_um/test_lru_hash.cpp -o bin/test_lru_hash -lnuma

# 仮想化環境(VMware/AWS/Azure)用に-DUSE_EXPONENTIAL_BACKOFF=ONを使用

LinuxゲストVMの最適化: 仮想マシン内のクロスプラットフォームスレッドスケーリングは、ゲストOSスケジューラ動作と標準ライブラリアロケータの競合により、しばしばボトルネックに遭遇します。この実装はこれらのボトルネックに対処し、2つの特定の軽減策を通じてマルチスレッドスケーリングを改善します。

  • ハードvCPUイールド: 標準のsched_yield()(std::this_thread::yield()経由)は、そのvCPUで待機している他のスレッドがない場合、Linux CFSスケジューラによってしばしばNOPとして扱われます。これにより、「ビジースピン」が発生し、VM-Exitストームがトリガーされます。スピンロックポリシーは、Linuxで4,000ポーズ閾値を超えると500ナノ秒のnanosleepにフォールバックすることでこれを軽減します。一方、ExponentialBackoffPolicyはハードウェアポーズ(1, 2, 4, 8)をバッチ処理してポーリングスレッドを非同期化します。

  • アロケータ競合(jemalloc): デフォルトのglibc mallocは、ベンチマークスイートでの同時アロケーションを大幅にスロットルします。Linuxでのアロケータボトルネックを防ぐため、jemallocにリンクすることを強くお勧めします。これにより、競合の激しいシステムヒープが、テーブルの内部シャード分割を補完するシャード化されたロックフリーアロケーション戦略に置き換えられます。

# jemallocのインストール(Ubuntu / Debian)
sudo apt-get install libjemalloc-dev

# RHEL / Fedora / CentOSでjemallocをインストール
sudo dnf install jemalloc-devel

推奨ステップ: Linuxでのベンチマーク実行 テストスイートがテールレイテンシを正確にベンチマークし、スレッド優先度を管理するためにルート権限を必要とせずにNUMAノードアフィニティを適用できるようにするため、実行前にtest_lru_hash実行可能ファイルにCAP_SYS_NICEケーパビリティを付与することを強くお勧めします。

# Ubuntu / Debian
sudo apt install libcap2-bin 

# RHEL / Fedora / CentOS
sudo dnf install libcap          

sudo setcap cap_sys_nice+ep ./build/bin/test_lru_hash
Windows(ユーザモードとカーネルモード)

ネイティブVisual Studioソリューション(.slnx)とプロジェクト(.vcxproj)ファイルがリポジトリに含まれています。

ユーザモード: Visual Studio 2026(またはv143 Platform Toolsetを持つVisual Studio 2022)を使用してビルドします。

  • C++20が必要です(x64およびARM64をサポート)。
  • NUMAサポートはVirtualAllocExNumaを介してネイティブに処理されます。

カーネルモード: Visual Studio 2026とWindows Driver Kit(WDK 11)を使用してビルドします。

  • C++20が必要です(x64およびARM64をサポート)。
  • 実装はEX_PUSH_LOCKを使用し、64バイトアラインされたNUMA対応の非ページプール割り当てをExAllocatePool3を介して実行します。
  • IRQL制限: 同期境界はプッシュロックを使用するため(<= APC_LEVELで動作)、現在のカーネル実装はIRQL < DISPATCH_LEVEL(つまりPASSIVE_LEVELまたはAPC_LEVEL)でのみ使用できます。極端な競合下で、すべてのシャードノードが同時にインフライトの場合、バックオフは自動的に現在のIRQL(PASSIVE_LEVELではKeDelayExecutionThread、APC_LEVELではYieldProcessor())に適応します。DPCルーチンまたはハードウェア割り込みハンドラでの使用は安全ではありません。

結論と将来のハードウェア予測

Amdahlの法則によれば、標準的なグローバルロックLRU実装(std::unordered_map + std::list + std::shared_mutexなど)は、その逐次同期オーバーヘッドによって大きく制限され、重い競合下では必然的にロックコンボイにつながります。シャードアーキテクチャを使用して同期を分離することにより、配列バック型テーブルはその逐次部分を最小限に抑え、スループットを並列負荷に対して正にスケールさせます。

このメカニカルシンパシーに基づき、このアーキテクチャのパフォーマンス上の利点は、最新のハードウェアトポロジでさらに顕著になるでしょう。

  • 大規模L3キャッシュ(例: AMD 3D V-Cache / Server CPU): 32ビット配列インデックスを使用することで、構造メモリフットプリントが半分になります。これにより、はるかに大きなワーキングセットがL3 SRAM内に収まり、メインメモリのレイテンシペナルティが遅延します。

  • 高並列性とNUMA(Threadripper / EPYC / Xeon / Graviton): 分離された128ビット乗算・折り畳みミキシング(MixHash)とNUMA対応の物理メモリ割り当ては、ワークロードを物理ソケットとシャード内バケット全体に均等に分散させます。これにより、標準実装が劣化する閾値をはるかに超えて、ほぼ線形のスケーリングが維持されます。

  • 対称コアスケーリングとキャッシュコヒーレンシ(Ryzen / Threadripper / ARM64): 極端なコア数では、「遅延プロモーション」最適化は、リーダー・ライターロック設計(std::shared_mutex)で必要な排他ロックアップグレードをバイパスし、ホットリードでのLRUリンクリストミューテーションをスキップします。これにより、ターゲットのBucketsとLruNodeキャッシュラインが、MESIプロトコル内の共有(S)状態にクリーンに保たれ、複数のコアが異なるチップレットを横断して同じノードをローカルにキャッシュできるようになり、クロスダイ書き込み無効化トラフィックがトリガーされなくなります。


ライセンス

このプロジェクトはApache License, Version 2.0の下でライセンスされています。

ライセンスに従わない限り、このファイルを使用することはできません。ライセンスのコピーは以下から入手できます: http://www.apache.org/licenses/LICENSE-2.0

適用法により要求されるか、書面で合意されない限り、ライセンスの下で配布されるソフトウェアは、明示的か黙示的かを問わず、いかなる種類の保証または条件もなく「現状有姿」で配布されます。ライセンスについては、LICENSEファイルを参照してください。