Wu Fengguang: Linux を使って事前読み取りアルゴリズムを学ぶ

Linux は急速に発展し、今では Microsoft に追いついています。Linux をより良く適用するにはどうすればよいでしょうか?この記事では、Linux を使いやすくするための事前読み取りアルゴリズムについて説明します。皆さん、こんにちは。このレポートでは、過去 1 ～ 2 年間に先読みアルゴリズムに加えられた改善と、それが I/O パフォーマンスに与えた影響について簡単に説明します。

ご存知のとおり、ディスクはシークがあまり得意ではなく、シークのオーバーヘッドが非常に高いため、小さな IO を最小限に抑える必要があります。一般的なアプリケーションは小さな IO を実行し、小さなバッファを作成してから、4K、4K、8K などの読み取りを実行します。その後、カーネルが最適化して、小さな IO を大きな事前読み取りに変換します。

この事前読み取りは、下の図で確認できます。上はアプリケーションによる 4K の読み取りで、下はカーネルによる 16K 以上の事前読み取りです。この事前読み取りによる 2 つの主なパフォーマンス向上は、小さな読み取りを大きな事前読み取りに変換することでスループットを向上できることです。

同期読み取りを非同期事前読み取りに変換することで、IO の待機を実現します。この事前読み取りアルゴリズムの基本原理は、アプリケーションの読み取り要求シーケンスを検出することです。アプリケーションが順次読み取りを実行する場合は、事前読み取りが可能です。ただし、実際の実装では、非常に単純なシーケンシャル読み取りだけでなく、さまざまな IO アクセス モードが存在するため、そのバリエーションが検出されます。ジッターに対する処理もいくつかあります。

次の PPT では、主に 2 つの事前読み取りアルゴリズムを紹介します。まず、今回の改善は、連続読みの検出から始まります。最も単純な連続読みは、ページごとに読み進めるものなので、その判定条件は非常に単純です。その後、一部のページが繰り返し読み取られる場合があることが分かりました。これは、読み取り要求がページ境界に揃っていないため、同じページが複数回読み取られる場合に発生します。これは実際にはまだシーケンシャル読み取りであるため、判断条件を改善し、条件を追加することで対処できるはずです。その後の繰り返し読み取りはより複雑な状況であり、FTP や HTTP プログラムなどの多くのネットワーク アプリケーションで発生します。カーネルの AIO もあります。これらの IO では、比較的大きな読み取り要求を送信することが多く、その一部が完了した後に返されます。古いカーネルでは、アプリケーションが要求したページが事前読み取りの判断条件として使用されていたため、混乱が生じていました。新しい 2.6.23 では改善が行われました。事前読み取りアルゴリズムの入力として実際の読み取りページを使用するため、次の図は非常に良好なシーケンシャル読み取りです。

この改善により、一部のユーザーからパフォーマンスが大幅に向上したという報告がありました。たとえば、16 レベルのメモリを搭載し、HTTP を使用して 1,200 のクライアントにサービスを提供するサーバーがあります。古いカーネルと新しいカーネルでは、CPU IO が 17% 削減され、ネットワーク帯域幅、つまり実際のサービス量が 17% 増加しました。同時に、ディスクについては、ディスク使用率が 26% 削減され、ディスク帯域幅が 29% 増加しました。

これは別の HTTP ユーザー レポートで、IO ビターが 80% から 20% に低下したと報告されています。次の問題は、事前読み取りジッターです。これは、事前読み取りページが実際にリーダーによって使用される前にキャッシュからスワップアウトされるときに発生します。これを回避するには、リーダーが一度にページを 1 つずつ読み取るタイミングが 3 回あり、その後、事前読み取りジッターが発生します。事前読み取りジッターが発生した後、すべてのページがバッファーから完全に取り出されます。古いカーネルは、一度に 1 ページずつ IO を実行し、ここで赤色はディスク IO が発生したことを示し、非常に非効率的です。新しいバージョンでは、新しいウィンドウが再確立され、1 つの IO は 4K です。このように、順番に増やすことによって、効率はすぐに回復します。この図は、事前読み取りジッターが発生した後のパフォーマンス比較です。

私たちのコンピュータは 128 メガバイトのメモリを使用し、毎秒新しいリーダーを開きます。リーダーは 1 秒あたり 100K を読み取ります。これは約 20 秒から 30 秒後に徐々に発生します。この時点で、古いカーネルのネットワーク トラフィックは 1 秒あたり 5 メガバイトで、新しいトラフィックは 1 秒あたり 15 メガバイトであり、パフォーマンスは 3 倍、IO パフォーマンスは 8 倍向上します。

この図は、もう 1 つのあまり分かりにくい読み方です。 Linux のファイル構造の制限により、処理できるのは 1 つのファイルと 1 つのストリームだけです。プロセスは 2 つあり、それぞれ 2 つのファイル ディスクリプタを開いて読み取りを行うと、読み取りがスムーズであることは正しく検出されますが、ファイル全体が 2 つのストリームで共有されるため、相互干渉が発生します。下図からわかるように、カーネルの観点からは多くの変更が行われました。これにより先読みが無効になり、パフォーマンスが大幅に低下する可能性があります。これは内部ファイル構造であり、それぞれが開いている FD に対応しています。

現時点では、古いアルゴリズムは 1 つしかなく、2 つの異なるストリームに送信されます。それらの間には相関関係がなく、連続性は検出できません。改善された方法は、機能を使用することです。つまり、任意のページがメモリに読み込まれると、一定期間キャッシュされるため、前のページをチェックして、そのページがキャッシュ内にあるかどうかを確認できます。そうであれば、それは連続読み取りです。順次読み取りの後に事前読み取りが実行されることはわかっていますが、その後、どの程度の事前読み取りを実行するかという問題を解決する必要があります。この事前読み取りサイズは安全でなければなりません。事前読み取りが大きすぎると、事前読み取りジッターが発生するため、推定値を作成するためのいくつかの式が導出されます。この推定値は正確であり、その前提はストリーム数が安定しているという 1 つの条件のみです。最初の 2 つの主な問題を解決した後、事前読み取りアルゴリズムを取得できます。

下の図を見てみましょう。まず、開始状況は前に一連の待機があり、これはリーダーがページを読み取ったことを意味します。ポンド記号はリーダーが読んでいるページを示し、前の下線は先読みウィンドウを示します。最初のステップは、この場所にページがあるかどうかを判断することです。このページがキャッシュされている場合、これはシーケンシャルストリームであることを意味し、先読みを実行できます。事前読書をするためには、どこから始めてどこで終わるかを知っておく必要があります。先に進み、履歴ページを収集し、履歴ページの数を決定して、H を取得します。この H は逆に反映され、4 番目のステップで END 記号を取得します。これで、開始基準と終了基準が得られたので、事前読み取りを行うことができます。

以下は、3 つの先読みアルゴリズムの比較です。古いカーネルでは、1 つの FD のみを順番に読み取ることができます。 1 つのファイルは約 32 ストリームをサポートできます。この 32 ストリームは拡大できますが、サイズが大きくなると効率が低下します。コンテキスト先行読み取りはリージョンに基づいて実装されるため、ストリームの数によって効率が影響を受けず、無限の数のストリームをサポートできます。この機能は、シーケンシャル読み取りとランダム読み取りが混在する場合の事前読み取りに非常に適しています。この場合、各ランダム読み取りは新しい読み取りを開くことに相当するため、このグラフには多数存在し、対処することは不可能です。内部的に処理されるのはデフォルトの 32 個だけだからです。このコンテキストの事前読み取りは、科学計算にも適用できます。科学計算では、核分裂力は大規模な行列に対して実行されることが多いです。間隔は等しいですが、読み取りサイズは改善できません。IOサイズを改善できない場合は、パフォーマンスは依然として影響を受けます。上記の記事によると、事前読み取りはストリームが多いです。最初の分裂中のこれらのストリームのパワーはまだわかっていませんが、確かに存在します。最初に 4 ページが事前に読み込まれ、次に 8 ページが事前に読み込まれるため、効率が向上します。

次は FNS サーバーの読み取りです。クライアントは通常、比較的大きな事前読み取りを実行しますが、この事前読み取りは小さな要求に分割されます。要求がサーバーに到着する時間は混乱する可能性があります。サーバーは、多数の FNSD を実行する複数の CPU を備えた SMP サーバーである可能性があります。特定の要求が実際に受信されると、混乱が悪化します。これは、読み取り要求が順序どおりに実行されなかったり、同時に実行されたりすることと同じです。この場合、6.2.23 の新しい先読みアルゴリズムは、このタイプのカオス読み取りに対する感度が低く、適応性が向上しているため、NFS 読み取りパフォーマンスが 1.8 倍向上します。コンテキスト先読みを使用すると、パフォーマンスが 2 倍になり、さらに向上します。

次はスパース読み取りです。スパース読み取りは、ファイルの一部 (おそらく 1/2) がアプリケーションによって読み取られるときに発生します。これにより、スパース読み取りをサポートするために順次検出条件が変更される可能性があります。

これはユーザーサーバーです。8K の読み取りにジャンプし、再び 8K にジャンプして、バックアップするという特徴があります。これは古いカーネルでは検出できないため、事前読み取りは行われません。コンテキスト事前読み取りではパフォーマンスが非常に良くなり、40 ～ 50 倍のパフォーマンス向上が期待できます。

最後に、ランダム読み取りは頻繁に使用できないと一般的に考えられていますが、現実には非常に人気のある領域があり、ランダム読み取りが非常に多く、つまり密度が非常に高いため、先読みヒット率が非常に高くなります。この場合、先読みを行うことができ、前述のコンテキストベースおよびスパース先読みアルゴリズムをここで使用できます。これについてはユーザーテストもあります。ロード中、ユーザーはランダムに大きなファイルをメモリにロードします。 2 つの曲線から、前半部分がまばらに読み込まれる場合、パフォーマンスは平坦になることが多く、大幅な低下や改善は見られません。ただし、読み取り密度が高くなると、パフォーマンスは 3 倍向上します。

この集中的なアルゴリズムは、再生トラック データベースなどの他のデータベースにも適用でき、さまざまな程度に改善できます。事前読み取りアルゴリズムを学んでいただければ幸いです。