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

高性能配列ベース LRU ハッシュテーブル 並列 LRU ハッシュテーブルは、以下に最適化されています。 マルチコアのスケーラビリティ 予測可能なテールレイテンシ NUMA アーキテクチャ ゼロランタイムアロケーション 目次 問題：標準ライブラリのボトルネック 解決策：コアアーキテクチャとアルゴリズム ベンチマークとスケーリングパフォーマンス このテーブルが最適でない場合 クイックスタート API の概要 プロジェクト構造 テストコードのビルド 結論と将来 ハードウェアの外部推定 ライセンスと貢献 要求の厳しいシステムプログラミングワークロード（キャッシングレイヤー、ネットワークインフラストラクチャ、カーネルコンポーネントなど）向けに設計された高性能な並列 LRU ハッシュテーブルです。シャードベースの並列処理とキャッシュフレンドリーなメモリレイアウトを活用することで、標準ライブラリコンテナが競合下で劣化する環境で高いスループットを実現します。 主なアーキテクチャのハイライト ゼロランタイムアロケーション：事前に割り当てられたフラット配列により、ヒープの断片化と OS レベルのロック遅延が排除されます。 カスタム TTAS スピンロック：std::shared_mutex を置き換え、OS コンテキストスイッチを排除し、14 倍以上のスループットとサブマイクロ秒のテールレイテンシを実現します。（注：ユーザーモードはカスタム TTAS スピンロックを使用して生の速度を追求しますが、カーネルモードは EX_PUSH_LOCK に依存します）。 シャードアーキテクチャ：グローバルロックのコンボイを排除し、物理 CPU コア数に対して線形にスケーリングします。 NUMA 対応メモリ：シャード割り当てを物理 CPU ソケット全体に分散させ、メモリコントローラーの帯域幅を最大化します。 ロックフリーの破棄：ペイロードは同期境界の外で明示的に破棄され、フラットなテールレイテンシを保証します。 遅延 LRU プロモーション：調整可能な「セーフゾーン」は、ホットリード時の排他的ロックアップグレードをバイパスし、約 20% のスループット向上をもたらします。 カスタムアロケーター（ユーザーモード）：ドメイン固有のメモリ管理のためのテンプレート注入アロケーターをサポートします。 デュアル環境対応：専用の Windows 10+ カーネル実装（IRQL < DISPATCH_LEVEL）に加えて、完全なクロスプラットフォームのユーザーモードをサポートします。 この実装は、メカニカルシンパシー、キャッシュローカリティ、ロックのスケーラビリティ、予測可能なメモリ動作を優先しており、以下のような要求の厳しい環境に適しています。 高頻度取引（HFT）インフラストラクチャ ストレージサブシステムキャッシュ リアルタイムネットワークルーティング カーネル / ドライバーコンポーネント 高スループットWebサーバー この実装は、厳密または確率的な LRU（Least Recently Used）エビクションポリシーを維持しながら、挿入、検索、削除に対して平均 O(1) 時間の操作を提供します。 問題：標準ライブラリのボトルネック 典型的な並列 LRU 実装（例：グローバル std::shared_mutex で保護された std::unordered_map + std::list の組み合わせ）は、最新のハイコア数 CPU において深刻なアーキテクチャ上の欠陥に悩まされています。 グローバルロックの競合：単一のロックは壊滅的な「ロックコンボイ」を作成し、スレッドを追加すると総スループットが低下します。 ポインタチェイシング：ヒープ全体にわたるノードのトラバーサルは、L1/L2 キャッシュのローカリティを破壊します。 アロケーターのオーバーヘッド：すべての挿入/エビクションはヒープの割り当て/解放（new/delete）をトリガーし、メモリの断片化と OS レベルのロック遅延を引き起こします。 偽共有：アラインメントされていないメモリ構造は、隣接する CPU コアがお互いの L1 キャッシュラインを無効にし、パフォーマンスを静かに破壊します。 解決策：コアアーキテクチャとアルゴリズム このプロジェクトは、シャーディング、フラット配列メモリ管理、ロックフリー破棄技術の組み合わせにより、標準ライブラリのボトルネックを解決します。 この図は、データを独立したキャッシュアラインされたシャードに分割することにより、グローバルロックの競合を排除する LRU ハッシュテーブルのアーキテクチャを示しています。 各シャードは、独自の排他 TTAS スピンロック、メタデータカウンター、およびバケットとノード配列を含む連続した「メガブロック」メモリで自律的に動作します。 これらの配列内では、ハッシュ衝突チェーンと双方向 LRU キューの両方が、標準の 64 ビットポインタではなく 32 ビット配列インデックスを使用して構築されています。これにより、構造的なメモリオーバーヘッドが半分になり、ホットパス操作中の L1/L2 キャッシュのローカリティが向上します。 高レベルでは、テーブルは独立したシャードに分割され、それぞれが独自のハッシュテーブルと LRU チェーンを管理します。 ============================================================================= [ マスターハッシュテーブルオブジェクト ] ============================================================================= | +---> [ シャード配列 ] (連続ブロック、CPUコア数 * 32 にスケーリング) | +--- [ シャード 0 ] (偽共有を防ぐために 64/128 バイトアラインメント) | | | +-- 同期：排他 TTAS スピンロック | | | +-- メタデータカウンター：ActiveCount, Capacity, Generation | | | +-- チェーンポインタ：LruHead, LruTail, FreeHead (32 ビットインデックス) | | | | (ハッシュ衝突チェーンは HashNext 経由) | +-- バケット配列：[ Head_Idx ] [ INVALID ] [ Head_Idx ] ... | | | | | | v 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: TKey | | | COLD: TValue*, 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 リスト、スピンロック、および容量制限が含まれます。シャード数は、プロセッサトポロジに基づいて動的にスケーリングされます（シャード数 ≈ CPU コア数 × 32）。スレッドは、MurmurHash3 スタイルのアバランチミキサー（MixHash）を使用してルーティングされ、エントロピーを下位ビットに強制します。これにより、ユーザー提供のハッシュ関数の品質に関係なく、典型的なハッシュ品質の下で均一なシャード分布が保証されます：shard = MixHash(hash) & (ShardCount - 1)。これにより、均一なワークロード分散が保証され、設計上グローバルロックの競合が回避されます。 2. 配列ベースのメガブロックと 32 ビットインデックス ノードをヒープに個別に割り当てる代わりに、すべてのノードとバケットは連続したフラット配列（メガブロック）に事前に割り当てられます。 ゼロランタイムアロケーション：初期化後、テーブルは new または delete を呼び出しません。 相対 32 ビットインデックス：連結リスト（LRU チェーンとハッシュ衝突）は、64 ビットポインタの代わりに 32 ビット配列インデックスを使用して実装されます。これにより、構造的なメモリオーバーヘッドが半分になり、CPU の L1/L2 キャッシュに収まるノードの数が劇的に増加します。 NUMA 対応：ユーザーモードテーブルは、VirtualAllocExNuma（Windows）または libnuma（Linux）を使用して、シャード割り当てを物理 CPU ソケット全体に均等に分散させ、メモリコントローラーの帯域幅を最大化します。 3. メカニカルシンパシーとキャッシュ管理 メモリレイアウトは、x86_64 および ARM64 では 64 バイト、