🏅 🐇 📝 スマートフェイスコントロール：SSDでデータを効果的にキャッシュするための機械学習アルゴリズム 🍽️ 👨🏿‍🤝‍👨🏽 🦃

この記事はSECR2017カンファレンスで発表され、Bertrand Meyer Award for Best Research Reportを受賞しました。

この記事では、Reydiks研究所のスヴェトラーナ・ラザレヴァ長が、機械学習アルゴリズムに基づくストレージシステムの並列キャッシュを満たす新しいアルゴリズムについて語っています。

オリジナル記事とプレゼンテーション。

ハイブリッドシステム

顧客がデータストレージシステムに求める主な要件は、ソリッドステートドライブ（SSD）が提供するI / O操作の高いパフォーマンスと、ディスクドライブ（HDD）が保証する低コストの操作です。ハードドライブとソリッドステートドライブの違いの理由は、内部デバイスの動作にあります。特定のデータブロックにアクセスするには、HDDはヘッドを移動し、磁気ディスクをスピンする必要があります。これは、多くのランダムリクエストの場合、コストが高くなりますが、SSDには機械部品がなく、シーケンシャルリクエストとランダムリクエストの両方を同じ高速で処理できます。

しかし、ソリッドステートドライブの高性能には欠点があります。まず、寿命が限られています。第二に、これは価格であり、単位容量あたりは従来のHDDよりもはるかに高いです。このため、SSDのみで構築されたデータストレージシステムの配信は限定的であり、データアクセス時間が高価な特に負荷の高いシステムに使用されています。

ハイブリッドシステムは、HDDの安価だが低速のストレージとSSDの高性能だが高価なストレージの妥協点です。このようなシステムでは、ソリッドステートドライブが（RAMに加えて）追加のキャッシュまたはティアリングの役割を果たします。この記事では、特定の技術を選択するための議論を行いました。

限られた数の書き換えサイクルと組み合わせて、キャッシュデバイスとしてソリッドステートドライブを使用すると、従来のキャッシュアルゴリズムのロジックが原因でキャッシュが大量に使用されるため、摩耗が大幅に加速します。したがって、ハイブリッドストレージシステムには、使用するキャッシュデバイスの機能（SSD）を考慮した特別なキャッシングアルゴリズムが必要です。

ハイブリッドアレイの考え方の最も単純な実装は、RAMの後のすべての要求がSSDに送られる2次キャッシュです（図1を参照）。このアプローチの基礎は、時間的局所性の特性です。同じデータを要求する確率は、最後の呼び出しの時間が短いほど高くなります。したがって、SSDキャッシュを2次キャッシュとして使用すると、RAMの量が増加するようです。しかし、一時的な局所性を処理するのに十分なRAMがある場合、この方法は効果的ではありません。別のアプローチは、SSDキャッシュを並行して使用することです（図2を参照）。つまり一部の要求はRAMに送信され、一部の要求は直ちにSSDキャッシュに送信されます。これは、異なるキャッシュが異なるロケールを処理するという事実を目的とした、より複雑なソリューションです。パラレルレベルキャッシュを実装する上で最も重要な側面の1つは、SSDキャッシュを埋めることを選択することです。この記事では、新しい並列キャッシュフィルアルゴリズム-機械学習アルゴリズムに基づく顔制御について説明します。

提案されたソリューションの基本は、クエリ履歴から長期間にわたって記録されたデータストレージシステムへのデータの使用です。この決定は、次の2つの仮説に基づいています。

クエリ履歴は、少なくとも限られた期間のストレージの一般的な負荷を示します。
ストレージシステムの負荷には、要求されるブロックと頻度を決定する何らかの内部構造が格納されます。

最初の仮説は疑いの余地がほとんどなく、仮定のままですが、2番目の仮説は実験的検証が必要です。

図 1.レイヤー2キャッシュ

図 2.並列キャッシュ

ソリューションのアーキテクチャ

提案されたソリューションのアーキテクチャを図に示します。 3.顧客からのすべてのリクエストは、最初にアナライザーを通過します。その機能は、システムへの複数の連続した要求を検出することです。

図 3.ソリューションのアーキテクチャ

タイプに応じて、処理方法が異なります。

シーケンシャル録音 。このタイプのリクエストは問題を引き起こさず、迅速に処理されるため、アクセスするデータはSSDキャッシュに分類されません。
シーケンシャルリーディング 。先読みアルゴリズムにより、このタイプのリクエストは迅速に処理されます。通常、このようなリクエストは一意であるため（つまり、同じデータの連続した読み取りはほとんどありません）、そのようなデータをSSDにキャッシュする必要はありません。
ランダム記録 。このようなリクエストは、エンドツーエンドの記録中とRAMに落ちるときの両方で顕著なオーバーヘッドを引き起こします。キャッシュから排出されるデータは、ハードドライブへの書き込みが必要です。したがって、RAMをバイパスしてすぐにSSD書き込みキャッシュに送信され、ログ構造の方法で保存され、可能な限り順次置き換えられて、ハードディスクアレイにさらに効率的に記録されます。
ランダム読み取り 。データは、顔制御アルゴリズムに応じて、RAMまたはSSDにキャッシュされます。

このシステムでは、ランダムな要求のみがSSDの摩耗に影響します。ランダム書き込みリクエストは最適化できません。したがって、SSDの寿命を延ばす唯一の方法は、ランダム読み取り要求の処理を最適化することです。特定のデータをキャッシュすることの潜在的な影響を評価する方法があれば、「不要な」データをキャッシュする必要性を取り除くことができます。

一般にハイブリッドストレージシステムのSSDの寿命を延ばすソリューションを提供する作品は、2つのグループに分類できます。最初のグループは、作業の内部ロジックと技術的機能を使用することにより、ソリッドステートドライブに基づいてキャッシュの効率を改善する可能性を検討します[5、1]。このようなアルゴリズムは、特定のデバイスの仕様に大きく依存しているため、これ以上は取り上げません。

2番目のグループの作業は、新しいキャッシュアルゴリズムの作成に焦点を当てています。みんなの考えは一般的です。めったに使用されないデータはキャッシュに入れてはいけません。これにより、第1に、従来のアルゴリズムと比較してエントリ数が減り、第2に、使用頻度の低いブロックによるキャッシュの目詰まりが少なくなるため、キャッシュヒットの数が増えます。

LARC-遅延適応置換キャッシュ [4]。アルゴリズムは単純なロジックを使用します。ブロックが特定の期間に少なくとも2回要求された場合、おそらく将来必要になり、SSDキャッシュに入れられます。候補のブロックの追跡は、RAM内の追加のLRUキューを使用して実行されます。このアルゴリズムの利点には、比較的少ないリソース要件が含まれます。
WEC-書き込み効率の高いキャッシュアルゴリズム [6]。標準のキャッシュアルゴリズムは、頻繁に使用されるブロックが継続的にキャッシュされるのを防ぎます。このアルゴリズムは、そのようなブロックを分離し、それらのブロックへのアクティブなアクセスの間、キャッシュ内にあることを保証するように設計されています。この作業では追加のキャッシュキューも使用しますが、候補ブロックを決定するためのより複雑なロジックを使用します。
エラスティックキュー [2]。以前に提案されたすべてのキャッシングアルゴリズムの欠点、つまり、さまざまな負荷への適応性の欠如を示します。優先度キューを使用した作業を共通の基盤と見なし、優先度を割り当てるロジックの違いを考慮し、この観点から一般的なキューの改善を提供します。

上記のアルゴリズムの根底にあるのは、コンピューターサイエンスの自然な方法です。多くの場合、既存の条件と仮定の分析に基づいたヒューリスティックなアルゴリズムの開発です。この作業は、データストレージシステムのワークロードが自己相似であるという事実に基づいて、根本的に異なるアプローチを提供します。つまり過去のクエリを分析することで、将来の行動を予測できます。

機械学習アルゴリズム

この問題には2つの側面からアプローチできます：機械学習または表現の指導（表現学習）の従来の方法を使用します。前者は最初にデータ処理を必要とし、それらから関連する特徴を抽出し、モデルを訓練するために使用されます。 2番目のアプローチの方法では、最小限の前処理を行った初期データを直接使用できます。しかし、原則として、これらの方法は非常に複雑です。

ティーチング表現の例は、ディープニューラルネットワークです（詳細については、[3]を参照）。単純な基本モデルとして決定木を試すことができます。トレーニングが実施されるサインは次のとおりです。

平均スタック時間
読み取り/書き込み比率
クエリ履歴の固定セグメントで計算されるランダムクエリとシーケンシャルクエリの数の比率。

プレゼンテーションを教える有望な方法。利用可能なデータは時系列であり、適切なアルゴリズムを選択するときに考慮することができます。計算でシーケンシャルデータ構造に関する情報を使用するアルゴリズムの唯一のグループは、リカレントニューラルネットワークです[3]。したがって、このタイプのモデルは、タスクを解決するための主要な候補です。

データ

データは、ストレージクエリの履歴です。各リクエストについて、次の情報が確認されています。

到着時間をリクエストします。
最初のブロックの論理アドレス（論理ブロックアドレス-lba）。
リクエストサイズ（len）;
要求のタイプ-書き込みまたは読み取り。
リクエストのタイプはシーケンシャルまたはランダムです。

実験とデータ分析は、さまざまなクライアントから受信した実際の負荷で実行されました。クライアントからのリクエストの履歴を持つファイルは、今後ログと呼ばれます。

特定のキャッシュアルゴリズムの有効性を分析するには、メトリックを入力する必要があります。キャッシュヒット数や平均データアクセス時間などの標準的な指標は適切ではありません。キャッシュの使用は考慮されていません。したがって、キャッシュ効率のメトリックとして書き込み効率[6,2]を使用します。

W E = f r a c n u m b e r \： h i t s \： i n \： c a c h e n u m b e r \： e n t r i e s \： i n \： c a c h e

$WE = \ frac {number \：hits \：in \：cache} {number \：entries \：in \：cache}$

クエリ履歴は、順次クエリのブロックに分割されます。ブロックサイズはブロックサイズとして示されます。単一のリクエストの場合、メトリックは次のように計算されます。履歴では、最も近いウィンドウサイズのリクエストが表示され、同じデータに対するリクエストの数が元のリクエストと同じように計算されます。ブロックサイズのクエリからのブロックの場合、ブロックごとのメトリックの平均値が計算されます。

次に、ブロックは「良い」と「悪い」の2つのクラスに分割されます（図4を参照）。「不良」（赤）は、SSDキャッシュ（RAMに送信）に要求ブロックを送信することは推奨されないことを意味し、この要求ブロックがSSDキャッシュに送信されることはそれぞれ「良好」（緑）を意味します。係数WEがパラメーターmより大きいブロックは、「良好」と見なされます。残りのブロックは「不良」と見なされます。

図 4.ログをブロックに分割します

大きなウィンドウサイズ値のメトリックの計算には、かなりの時間がかかる場合があります。ブロックの再利用をどこまで再利用できるかには、計算上の制限が課されます。 2つの質問が発生します。

windowsizeオプションの選択方法は？
windowsize内でのブロックの再利用は、一般にこれらのブロックの再利用を判断するための代表的な値ですか？

それらに答えるために、次の実験が行われました。

クエリのランダムサンプルが取得されました。
非常に大きなwindowsizemax内でのこれらのブロックの再利用が計算されます。
windowsizemaxとwindowsize内のブロックの再利用の間のピアソン相関係数が計算されます。windowsizeは異なるテスト値です。

図図5は、サンプルの相関係数の経時変化を示しています。表1は、サンプル全体の相関係数の値を示しています。結果は重要です（P値がゼロに近い）。次のように解釈できます。次のwindowsize要求で需要があるブロックは、次のwindowsizemax要求でも需要がある可能性があります。

図 5. windowsizeとwindowsizemaxの間の相関係数のダイナミクス

図の解説 5.上から下へ、ウィンドウサイズ：100000、10000、30000、3000。サンプルサイズ：1,000,000リクエスト。 X軸：1000リクエストの実行ウィンドウ番号。 y軸：実行中のウィンドウの相関係数値。

表1.さまざまなウィンドウサイズのピアソン相関係数。

ウィンドウサイズ	3000	10,000	30000	100,000
1,000,000	0.39	0.61	0.82	0.87

したがって、メトリックを計算するには、100000に等しいwindowsize値を使用します。

確率モデルを構築するためのデータセットは標準です[3、p。 120]は3つの部分に分けられました。

トレーニングサンプル：80％;
テストサンプル：10％（モデルの最終テスト用）;
検証サンプル：10％（トレーニングサンプルに関係なく、トレーニング中にパラメーターを選択し、モデルの進行状況を追跡するため）。

ディープラーニングモデルの場合、サンプリングをランダムにすることはできません。この場合、リクエスト間の一時的な接続が破壊されるため、注目に値します。

深層学習モデル

深層学習モデルを構築するには、多くの決定が必要です。このホワイトペーパーでは、それぞれについて詳細に説明することはできません。それらのいくつかは、文献[3]および元の記事の推奨に従って選択されました。それらには、詳細な動機と説明があります。

一般的なパラメーター：

目的関数はクロスエントロピー（分類問題の標準選択）[3+、p。 75];
最適化アルゴリズム-Adam [7];
パラメータ初期化メソッド-Glorot [8];
正則化方法は、パラメーター0.5のドロップアウト[9]です。

テスト済みのパラメーター：

ニューラルネットワークの再帰層の数：2、3、4;
各lstmユニットの出力ニューロンの数：256、512。
リカレントニューラルネットワークのタイムステップ数：50,100;
ブロックサイズ（ブロック内のリクエストの数）：100、300、1000。

基本的な深層学習方法-LSTM RNN

さまざまな複雑さのモデルがテストされました。すべてについて、結果は負です。学習ダイナミクスは図に示されています。 6。

図6. LSTM RNN。 トレーニング中の損失関数の値の変化

図の解説 6.赤-トレーニングサンプル、緑-テスト。 3つの反復層を持つ中複雑度モデルのグラフ。

事前トレーニングとLSTM RNN

要求の流れをモデル化するタスクの事前トレーニング（次の要求を予測する）がテストされました。 lbaの予測値と現在の間の二乗平均誤差を目的関数として使用しました。結果は否定的です。サイドタスクの学習プロセスは収束しません。学習ダイナミクスは図に示されています。 7。

図7.次のクエリのlba予測問題の事前トレーニングトレーニング中の標準誤差の変化。

図の解説 7.赤-トレーニングサンプル、緑-テスト。 2つの繰り返し層を持つモデルのグラフ。

HRNN

モデルは、2つのレベルの異なるパラメーターセットでテストされました。1つは各ブロック、2つ目は多くのブロックです。実験の結果は否定的です。学習ダイナミクスは図に示されています。 8。

図8. HRNN。 トレーニング中の損失関数の値の変化。

図の解説 8.赤-トレーニングサンプル、緑-テスト。 2番目のレベルに2つの再帰層を持つ中複雑度モデルのグラフ。

ご覧のとおり、ニューラルネットワークでは良い結果が得られませんでした。そして、従来の機械学習の方法を試すことにしました。

従来の機械学習方法。属性と標識。

周波数特性とその微分

次の表記法を紹介します。

count_lba-ブロック内のlbaの使用回数。
count_diff_lba-現在のリクエストのlbaと以前のリクエストのlbaの差の頻度。
count_len-指定された長さlenのブロックへのリクエストの発生頻度。
count_diff_len-現在のリクエストと以前のリクエストのlen間の差異の発生頻度。

さらに、各記号について、統計が計算されます-モーメント：平均、標準偏差、非対称係数、および過剰係数。

差異特性とその派生物

現在のブロックと前のブロックのlbaの違い（これをdiff_lba_iと呼びましょう）は、新しい機能の基礎として役立ちます。このようなdiff_lba_iの各差は対称的に分布し、平均はゼロです。したがって、異なるiに対するdiff_lba_iの分布間の差は、この数量の標準偏差である単一の数値を使用して説明できます。したがって、各ブロックについて、n個の値std_diff_lba_iのセットが取得されます。ここで、i = 1..10（このセットをlba_interdiffsと呼びましょう）。仮説は、良好なクエリブロックの場合、これらの値の差は少ない、つまり、不良ブロックの場合よりも集中しているということです。値の集中は、平均と標準偏差を使用して特徴付けることができます。それらの違いは図に見ることができます。 9.10は、仮説が確認されたことを示しています。

同様に、要求されたデータの長さについて特性が計算されます。

図 9. count_lba属性の平均と標準偏差のクラスの違い

図 10.特性lba_interdiffsの平均と標準偏差のクラスの違い

機能分析

特徴に関するクラス間の違いを分析するために、箱ひげ図が作成されました。たとえば、図 9.符号count_lbaの1瞬間と2瞬間の差が表示されます。図10 図10は、クラス間のlba_interdiffs属性の違い1と2を示しています。

スパン図は、単一のサインが、クラスに基づいてのみ決定するのに十分な有意差を示さないことを示しています。同時に、弱い非相関機能の組み合わせにより、ブロックのクラスを区別できる場合があります。

特性を計算する場合、小さなクエリブロックでは多くの符号がゼロになるため、blocksizeパラメータの大きな値を取得する必要があることに注意することが重要です。

決定木のアンサンブル

従来の機械学習方法の例は、決定木の集合です。その効果的な実装の1つにXGBoostライブラリ[10]があり、これは多くのデータ分析コンテストで良好な結果を示しています。

学習プロセスのダイナミクスは図に見ることができます。 11.テストサンプルでは、約3.2％の分類エラーが達成されています。図 12テストサンプルでモデルの予測を確認できます。

図 11. XGBoost。 トレーニング全体で分類の精度を変更します。 赤-トレーニングサンプル、緑-テスト。

図12. XGBoost。 ランダムテストサンプルのモデル予測

図の解説 12.色はモデルの予測を示します。赤-キャッシュが不十分なブロック、緑-キャッシュが良好です。 色飽和度は、モデルによって導出される確率です。 X軸：テストセットのブロック番号、y軸：初期メトリック値。 破線は、モデルをトレーニングするためにブロックを2つのクラスに分割したメトリックバリアです。 分類エラー3.2％。

第一種のエラー

キャッシングの問題では、第1種の間違い、つまり誤検知の予測を避けることが重要です。つまり、キャッシュに書き込むよりも、キャッシュに適したブロックをスキップする方が良い

未請求データ。偽陽性と偽陰性の予測を発行する確率をバランスさせるために、確率障壁を変更できます。その後、予測は陽性と見なされます。これらの量の依存性を図に示します。 13。

図 13.確率障壁に応じて、偽陽性および偽陰性の予測を発行する確率の依存性。その後、予測は陽性と見なされます。

図の解説 13. X軸：確率障壁、y軸：エラーの確率。 破線は偽陽性エラーの確率であり、実線は偽陰性エラーの確率です。

最終アルゴリズム-顔制御

SSDキャッシュを満たす方法を説明する最終アルゴリズムについて説明します。クライアントのログからトレーニングセットを形成するアルゴリズム、予測モデル（アルゴリズム2）を形成するアルゴリズム、および着信リクエストブロックを「良い」と「悪い」に分類する最終的なオンラインアルゴリズムの3つの部分で構成されます。

アルゴリズム1.トレーニングセットの形成

利用可能な選択をブロックサイズのブロックに分割します。
各ブロックについて、3.3.1項および3.3.2項の記号を検討します。
各ブロックについて、係数WEを考慮します。
各ブロックについて、WE係数を使用して、ブロッククラスを決定します：良いか悪いか。
ペア（サイン-クラス）を作成します。 1つのブロックの特性には、次のブロックのクラスが割り当てられます。

アルゴリズム2.教師

入力：アルゴリズム1のリスト（機能クラス）。

メインループ： XGBoostアルゴリズム。

出力：予測子。

アルゴリズムフェイスコントロール

入力：ブロックサイズの長さのリクエストのブロック、m。

メインサイクル：教師アルゴリズムからの予測子。

出力：ブロックが正常であると判断された場合、要求の次のブロックはSSDに送られます。ブロックが不良であると判断された場合、要求の次のブロックはRAMに移動します。判断できなかった場合、頻度が1より大きい場合、次のブロックからの要求はSSDに移動します（LARCアルゴリズムのLRUキューメソッドが使用されます）。

顔制御アルゴリズムと一般的なSSDキャッシュ実装の比較

顔制御アルゴリズムは数学モデルでテストされ、有名なSSDキャッシュの実装と比較されました。結果を表2に示します。RAMでは、LRUクラウディングアウトアルゴリズムはどこにでもあります。 SSDキャッシュでは、LRU、LRFU、LARCプリエンプティブテクニック。ヒットとは、ヒット数を百万単位で表したものです。顔制御はLRFU変位技術とともに実装され、顔制御とともに最高の結果を示しました。

ご覧のとおり、フェイスコントロールを実装すると、SSDのエントリ数が大幅に削減され、ソリッドステートドライブの耐用年数が長くなります。WEメトリックによると、フェイスコントロールを使用したアルゴリズムが最も効果的です。

表2.さまざまなSSDキャッシュ実装の比較

	LRU	ラルフ	ラーク	フェイスコントロール+ LRFU
RAMヒット	37	37	37	36.4
RRCヒット	8.9	8	8.2	8
HDDヒット	123.4	124.3	124.1	124.9
SSD書き込み	10.8	12.1	3.1	1.8
WE	0.8	0.66	2.64	4.44

おわりに

ハイブリッドストレージシステムは、1ギガバイトの最適な価格のため、市場で非常に人気があります。ソリッドステートドライブをバッファとして使用することにより、より高いパフォーマンスが実現します。

ただし、SSDのレコード数は限られているため、書き換えが行われます。したがって、SSDはすぐに消耗して交換が必要になるため、標準的な手法を使用してバッファーを実装することは経済的に有益ではありません。表2を参照してください。

提案されたアルゴリズムは、最も単純なLRU技術と比較してSSDの寿命を6倍に延長します。

顔制御は、機械学習方法を使用して着信要求を分析し、「不要な」データをSSDキャッシュに入れないため、キャッシング効率メトリックが数回改善されます。

将来的には、ブロックサイズパラメーターを最適化し、押し出し手法を改善するとともに、SSDキャッシュとRAMで押し出し手法の他の組み合わせを試す予定です。

参照資料

キャッシュを少なくしてパフォーマンスを向上：ハイブリッドストレージシステムのキャッシュサイズとフラッシュメモリキャッシュの更新コストのバランスを取ります。 / Yongseok Oh、Jongmoo Choi、Donghee Lee、Sam H Noh // FAST。 -Vol。 12.-2012。
Elastic Queue：キャッシュ置換アルゴリズム用のユニバーサルSSDライフタイム拡張プラグイン/ Yushi Liang、Yunpeng Chai、Ning Bao et al。 //第9回ACM International on Systems and Storage Conference / ACMの議事録。 -2016。-P. 5。
グッドフェローイアン、ベンジオヨシュア、クールビルアーロン。深層学習 -2016 。–– MIT Pressの準備中の本。 URL
遅延適応置換によるフラッシュベースのディスクキャッシュの改善/ Sai Huang、Qingsong Wei、Dan Feng et al。 //ストレージ上のACMトランザクション（TOS）。 -2016。-Vol。 12、いいえ。 2.-P. 8。
Kgil Taeho、Roberts David、Mudge Trevor。 NANDフラッシュベースのディスクキャッシュの改善//コンピューターアーキテクチャ、2008年。ISCA'08。第35回国際シンポジウム/ IEEE。 -2008。-P. 327–338。
WEC：WriteEfficient DataのキャッシュによるSSDキャッシュドライブの耐久性の向上/ Yunpeng Chai、Zhihui Du、Xiao Qin、David A Bader // IEEE Transactions on Computers。 -2015。-Vol。 64、いいえ。 11.-P. 3304– 3316。
キングマ・ディーデリク、バ・ジミー。 Adam：確率的最適化の方法// arXiv preprint arXiv：1412.6980。 -2014。
グロロットザビエル、ベンジオヨシュア。ディープフィードフォワードニューラルネットワークのトレーニングの難しさを理解する。 // Aistats。 -Vol。 9.-2010。-P. 249–256。
アレックス。リカレントニューラルネットワークによる教師付きシーケンスラベル付け。 -スプリンガー、2012。-P. 5–13。
チェン・ティアンチー、ゲストリン・カルロス。 XGBoost：スケーラブルなツリーブースティングシステム// CoRR。 -2016。-Vol。 abs / 1603.02754。 -URL

スマートフェイスコントロール：SSDでデータを効果的にキャッシュするための機械学習アルゴリズム