パーシステントメモリの揮発性メリット：パート2 - Dormando (2019年5月8日)
この全く新しい（私たちにとって）ハードウェアプラットフォームを考えると、新たな探求の方向性を見出せることを期待していました。しかし、発見したことは驚くべきものでした。問題は予想以上に退屈なものだったのです。
今後の展望：実験からの考察
データ構造の簡単な調査を行いました。DRAMとPMEMは非常によく似ていますが、PMEMのレイテンシは大きいです。Memcachedは従来のチェインハッシュテーブルを使用しています。PMEMへのラウンドトリップ数を減らして大きな違いを生み出す、より現代的なデータ構造は存在するでしょうか？
（まだ！）大きな改善をもたらすものは見つかりませんでした。この投稿の残りの部分では、これらのアイデアとその結果について説明します。
既存のデータ構造は、PMEMを考慮しても十分に最適化されていることがわかりました。LRUアルゴリズムは、頻繁にアクセスされるアイテムに対するLRUの変更を最小限に抑えようとします。そこから、ほとんどのメモリアクセスはDRAMキャッシュライン（64b）に収まるアイテムメタデータで発生します。PMEM独自のキャッシュラインは256バイトで、多くの場合、メタデータとキー全体を網羅します。つまり、一致するキーを比較し、結果のメタデータをチェックすることで、基盤となるPMEMへのフェッチが1回で済みます。
頻繁にアクセスされるアイテムはプロセッサキャッシュからも恩恵を受けるため、ホットキーまたはごく最近のキーは、さらなる作業を行うことなくパフォーマンスが向上します。
チェインハッシュテーブル
理論：チェインハッシュテーブルは、バケットが深い場合、パフォーマンスが低下します。これはPMEMのレイテンシによって悪化する可能性があります。
現実：memcachedは、バケットあたりの平均深度が1.5アイテムを超える前に、ハッシュテーブルのサイズを自動的に調整します。パフォーマンスの違いはわずかです。
主な懸念事項は、チェインハッシュテーブルでした。ハッシュテーブルは、ポインタのフラット配列を介して実装されます。キーはバケット番号にハッシュされ、バケットがNULLでない場合はアイテムが見つかります。次に、要求されたアイテムと完全に一致することを確認するために、キーをリクエストと比較する必要があります。
衝突が発生した場合、バケットは単方向連結リストを介してより深く「成長」します。アイテム構造内のポインタは、次のハッシュテーブルアイテムを指します。これは、見つかったアイテムが目的のアイテム*ではない*場合、PMEMへの追加のラウンドトリップが発生することを意味します。
Memcachedは、エントリの数（「負荷」）が元の配列のサイズの150％になった後、ハッシュテーブルのサイズを自動的に2倍にします。ハッシュテーブルの密度は、50％から150％の負荷の間で変化します。ハッシュアルゴリズムが完全に公平であれば、平均バケット深度は最悪の場合1.5になります。実際には、最悪のケースは1.5よりも高くなりますが、それほど高くはありません。
簡単なテストとして、memcachedに201,326,591個のアイテムを格納しました。これは、ハッシュテーブルの負荷が150％をわずかに下回るのに十分な量です。次に、ハッシュテーブルを強制的に拡張し、負荷を50％に落としました。この設定で、多数のクライアント接続を使用する、以前の「現実的な」ペースの負荷テストを実行しました。
ここでは、システムコールを多用するテストの平均レイテンシを見て、ハッシュテーブルのサイズのみを変更しています。すべてのリクエストはパーシステントメモリから提供されています。レイテンシは、サーバーがビジーになりクロックが安定するにつれてわずかに低下し、過負荷になると上昇し始めます。これらのテストのp99レイテンシは、多数のキューに入れられた接続とパフォーマンスが近いためランダムでした。複数回のテスト実行で一貫した違いを示したのは、実際の平均のみでした。
特大のハッシュテーブルが勝利したことがわかります。レイテンシがどれほど近いか注意してください。最悪の場合のハッシュテーブルは、平均で5マイクロ秒遅れる傾向があります。パフォーマンスを最大限に引き出す必要がある場合は、ハッシュテーブルのサイズを大きくすると役立ちます。そうでなければ、大きなメリットはありません。
参照カウントの消費
理論：すべての読み取り操作は、パーシステントメモリへの書き込み（参照カウントの更新、LRUの変更など）を引き起こします。大きな問題につながる可能性があります。
現実：ほとんど違いはありません。参照カウントとLRUシャッフルを無効にしたベンチマークでは、わずか5％の改善しか示されませんでした。
ほとんどのメモリアクセスは、アイテムメモリ以外で行われます。接続バッファ、統計カウンター、さらにはハッシュ計算でさえ、ほとんどの場合、アイテムメモリではなく*リクエスト入力バッファ*に対して実行されます。
GETリクエストを満たすために、アイテムメモリはほとんど触れられません
- ハッシュテーブルルックアップを完了するために、アイテムキーがリクエストバッファと比較されます。
- 有効期限がテストされます。
- 一致する場合、参照カウンターが増加します。
- 一部のビットフラグと「最終アクセス時刻」は、最近更新されていない場合に更新される場合があります。
- キーと値は、クライアントソケットに非同期的に書き込まれます。
- 参照カウンターが減少します。
Intel PMEMはメモリを256バイトのスライスでロードするため、小さなアイテムはほとんどの作業で1回の読み取りしか発生しない場合があります。残りの小さな読み取りはCPUキャッシュによって処理されます。LRU、最終アクセス時刻、およびフラグは、読み取り時に常に更新されるわけではありません。ビジー状態のアイテムの場合、2バイトの参照カウントのみが調整されます。アイテムメタデータはコード内で数回参照されますが、PMEMにアクセスすることによるレイテンシペナルティは固定されています。
階層型メモリ
理論：最近挿入されたアイテムは、アクセスまたは置換される可能性が最も高くなります。使用頻度が低いときにアイテムをPMEMにフラッシュすると、パフォーマンスが向上するはずです。
現実：*遅くなります*
LRUアルゴリズムは、メモリをHOT（新規）、WARM（頻繁にアクセスされる）、COLD（アクセス頻度が低い）に便利に分割します。COLDアイテムがPMEM上にあり、HOT / WARMがDRAMに残っていたらどうでしょうか？
フルキャッシュでは、新しいSETごとに次のようになります。
- HOTの*末尾*はCOLDに移行し、PMEMにコピーする必要があります。
- これを行うには：HOTからのアイテムのためのスペースを作るために、COLDの*末尾*を削除する必要があります。
- 最後に、HOTはアイテムデータを取得します。
これにより、設定にかかる時間が2倍になり、読み取りパフォーマンスの向上はこれを相殺するほど高くありません。非常に頻繁にヒットするアイテムはプロセッサキャッシュに配置されるため、PMEMのパフォーマンスは無関係になります。
バッファキャッシュ
理論：頻繁にアクセスされるアイテムは、RAMバッファキャッシュを使用します。
現実：おそらく実際には良くなりますが、大きな変更です。
階層化アプローチとは対照的に、新しいアイテムからのSETは変更されません。アイテムにアクセスすると、確率的にDRAMのバッファキャッシュにプルされる可能性があります。さらに読み取ると、キャッシュされたアイテムにヒットします。ランダムな機会を利用することで、アクセス頻度の低いアイテムのバッファプールからメモリを削除するオーバーヘッドを削減できます。
元のアイテムはPMEMに残り、偽のアイテムがハッシュテーブルにリンクされます。偽のアイテムは実際のアイテムを指し示します。DELETEまたはOVERWRITE、またはバッファプールからの削除時に、元のメモリは復元または解放されます。
実現するには大幅なコード変更が必要であり、読み取りパフォーマンスの向上はわずかです。非常に機密性の高いアプリケーションにのみ役立つ可能性があります。非常にホットになるキーは、バッファキャッシュがない場合と同じパフォーマンスになります。これもCPUキャッシュによるものです。
適応型基数木
理論：ARTは、大量のメモリを使用せずに、ルックアップ中にPMEMをチェックしてキーを比較することを回避するために、DRAMで使用できます。
現実：機能する可能性がありますが、スケーリングが難しく、チェインテーブルは現在うまく機能しています。
適応型基数木は、非常に興味深い比較的新しいデータ構造です。ARTを使用すると、キーをルックアップするためにハッシュする必要はありません。また、一致が良好かどうかを判断する前に、完全なキーを最終ノードと比較する必要もありません。Memcachedの既存のチェインハッシュテーブルは、アイテムを見つけるためだけにPMEMに複数回フェッチする必要がある場合があります。ARTはDRAM全体に留まり、一致した場合にのみアイテムデータをフェッチします。さらに、ソートされた性質のため、ARTをPMEMで直接実行することさえ理にかなっている場合があります。
An Inefficient Memcached Key
departmentname:appname:subsystem:userdata:picnum:{id}
ART Prefix Compression
[departmentname:][appname:][subsystem:][userdata:][picnum:]{id}
残念ながら、ARTは詳細で劣っています。memcachedは、接頭辞が類似した数億個のキーを格納できますが、末尾の数桁が異なります。これは、エントリを見つける前に、DRAM周辺で複数回のホップが発生する可能性があります。さらに、そのような構造の同時実行性に関する研究はまばらです。既存のメソッドでは、ルックアップの各段階でロックが必要です。同時書き込みにより、ルックアップが完全に再開される可能性があります。比較すると、memcachedのチェインハッシュテーブルは、ルックアップを行うために単一のミューテックスロックを必要とし、回避できたハッシュ計算は、ロックが取得される前に行われます。
将来的には可能性があるかもしれません。私たちは、この分野に注目しています。
外部参照カウンター
理論：アイテムをルックアップするには、参照カウントに2回書き込む必要があります。これをDRAMに移動すると、パフォーマンスとデバイスの寿命を節約できます。
現実：間接参照は遅く、パフォーマンスのメリットは最大5％です。実験する価値はあるかもしれません。
多くのアイテムを同時にリクエストできるため、ハザードポインタや同様の構造はmemcachedではうまくスケーリングしません。当面は、参照カウントに固執しています。一部の学術論文の考えとは反対に、参照カウンターはロックや同時実行性のためではなく、安全性と正確性のためです。キーと値は、scatter-gatherネットワーキングを介してクライアントにコピーされます。クライアントがデータの読み取りに時間がかかると、アイテムのメモリがクライアントに送信されるまでに長い時間がかかる場合があります。コピーオンライトと参照カウントがないと、アイテムのメモリが「削除」され、再利用される可能性があります。その場合、*間違ったデータ*がクライアントに送信されます。壊滅的なバグです。
1つのアイデアは、アイテムのキーと値が十分に小さい場合、アイテムがロックされている間に値をバッファにコピーする方が、参照カウントを2回バンプするよりも高速になるサイズカットオフポイントがあるということです。これは特に、現在、参照カウンターをデクリメントするには完全なミューテックスロックが必要であるためです（ただし、これは将来修正される可能性があります）。
アイテムは独自のミューテックスを持ち運びません。ミューテックスの別の小さなテーブルがチェックされ、同様のハッシュビットを持つアイテムはミューテックスを共有します。このテーブルは、必要に応じて拡張または縮小される各ロックの[POINTER、refcount]の配列で拡張できます。アイテムに参照がない場合、参照カウントメモリはありません。これにより、アイテムごとに2バイト節約できます。
これは複雑な変更であり、最大の影響は5％未満のパフォーマンスと2バイトのメモリです。外部参照カウンターを使用すると、DRAMへのアクセスが増える可能性があります。最終的に、DRAMの外部参照カウンターは、PMEMを介してアイテムメタデータにインラインでアクセスするよりも遅くなる可能性があります。
結論
既存のmemcachedは、Intel® Optane™ DC Persistent Memory Modulesと非常に良好に連携します。パフォーマンスの向上は困難となるでしょう。そのため、実施する価値がない可能性もあります。これにより、サービスを「PMEM互換」にするために多くの時間を費やすことなく、機能と安定性に集中できます。
それでも、最新のパーシステントメモリの登場はまだ初期段階です。現在、ハッシュテーブルはRAMに配置されていますが、これもPMEMに移動できる可能性があります。クライアント接続バッファでさえPMEMを単純に使用できるシナリオはありますか？
メモリを節約するためだけに、これまでどのような機能をスキップまたは見落としてきたのでしょうか？