外部ソート

外部ソートは、大量のデータを処理できるソート アルゴリズムの一種です。ソートするデータがコンピューティング デバイスのメイン メモリ(通常はRAM ) に収まらず、代わりに低速の外部メモリ(通常はディスク ドライブ) に格納する必要がある場合に、外部ソートが必要になります。したがって、外部ソート アルゴリズムは外部メモリ アルゴリズムであり、外部メモリモデルの計算に適用できます。

外部ソート アルゴリズムは、一般的に、クイックソートに似た分散ソートと、マージソートに似た外部マージソートの 2 種類に分類されます。外部マージソートでは、通常、ハイブリッドソート マージ戦略が使用されます。ソート フェーズでは、メイン メモリに収まるほど小さいデータのチャンクが読み取られ、ソートされ、一時ファイルに書き出されます。マージ フェーズでは、ソートされたサブファイルが 1 つの大きなファイルに結合されます。

外部ソート アルゴリズムは、外部メモリ モデルで分析できます。このモデルでは、サイズMのキャッシュまたは内部メモリと無制限の外部メモリがサイズBのブロックに分割され、アルゴリズムの実行時間は内部メモリと外部メモリ間のメモリ転送回数によって決まります。キャッシュを無視するアルゴリズムと同様に、漸近的に最適な外部ソート アルゴリズムは、の実行時間( Big O 表記) を実現します。 ${\displaystyle O\left({\tfrac {N}{B}}\log _{\tfrac {M}{B}}{\tfrac {N}{B}}\right)}$

外部ソートの一例としては、 K-wayマージアルゴリズムを使用する外部マージソートアルゴリズムがあります。これは、RAMに収まるチャンクをソートし、ソートされたチャンクをマージします。^{[1] [2]}

このアルゴリズムは、まずM個の項目を一度にソートし、ソートされたリストを外部メモリに戻します。ソートされたリストに対して- 方向のマージを実行し、1 回のパスで効率的にマージするのに十分なメイン メモリがない場合は再帰的にマージします。マージ パス中、ソートされた各リストのB個の要素が内部メモリにあり、最小値が繰り返し出力されます。 ${\displaystyle {\tfrac {M}{B}}}$

たとえば、100 メガバイトの RAM のみを使用して 900メガバイトのデータをソートする場合:

1. メインメモリ内の 100 MB のデータを読み取り、クイックソートなどの従来の方法でソートします。
2. ソートされたデータをディスクに書き込みます。
3. すべてのデータがソートされた 100 MB のチャンク (900 MB / 100 MB = 9 個のチャンク) になるまで手順 1 と 2 を繰り返し、これを 1 つの出力ファイルにマージする必要があります。
4. ソートされた各チャンクの最初の 10 MB (= 100MB / (9 チャンク + 1)) をメイン メモリの入力バッファに読み込み、残りの 10 MB を出力バッファに割り当てます。(実際には、出力バッファを大きくし、入力バッファを少し小さくすると、パフォーマンスが向上する可能性があります。)
5. 9 方向のマージを実行し、結果を出力バッファに保存します。出力バッファがいっぱいになると、それを最終的なソート済みファイルに書き込んで空にします。9 つの入力バッファのいずれかが空になると、そのチャンクからデータがなくなるまで、関連する 100 MB のソート済みチャンクの次の 10 MB でそれを埋めます。

マージ パスは、外部マージ ソートを外部で動作させるための鍵です。マージ アルゴリズムは各チャンクを 1 回だけ通過するため、チャンクを一度にすべてロードする必要はありません。チャンクの連続した部分が必要に応じてロードされます。また、読み取られるブロックが比較的大きい限り (この例では 10 MB など)、ハード ドライブなどのランダム読み取りパフォーマンスが低いメディアでも、読み取りは比較的効率的になります。

歴史的には、ソートの代わりに置換選択アルゴリズム^[3]を使用して初期分散を実行し、平均して2倍の長さの出力チャンクを半分の数だけ生成することがありました。

前の例は 2 パス ソートです。最初にソートし、次にマージします。ソートは、一般的なインメモリ マージ ソートのように一連の 2 方向マージ パスではなく、単一のk方向マージで終了します。これは、各マージ パスでディスクからすべての値を読み取ってディスクに書き込むため、パスの数を減らすことでk方向マージの追加コストを補うことができるためです。

シングルパス マージの制限は、チャンクの数が増えると、メモリがより多くのバッファに分割されるため、各バッファが小さくなることです。最終的には、読み取りが非常に小さくなるため、データ転送よりもディスク シークに多くの時間がかかります。一般的な磁気ハード ディスク ドライブのアクセス時間は 10 ミリ秒で、データ転送速度は 100 MB/秒であるため、各シークには 1 MB のデータ転送と同じ時間がかかります。

したがって、たとえば 100 MB の RAM で 50 GB をソートする場合、単一の 500 ウェイ マージ パスを使用するのは効率的ではありません。一度に各チャンクから読み取れるのは 100 MB / 501 ≈ 200 KB だけなので、ディスクの時間の 5/6 がシークに費やされます。2 つのマージ パスを使用すると、問題は解決します。ソート プロセスは次のようになります。

1. 前と同じように初期チャンクソート パスを実行して、500×100 MB のソート済みチャンクを作成します。
2. 一度に 25×100 MB のチャンクを結合する最初のマージ パスを実行し、20×2.5 GB のソートされたチャンクを生成します。
3. 2回目のマージパスを実行して、20×2.5 GBのソートされたチャンクを1つの50 GBのソートされた結果にマージします。

これにはデータに対する追加のパスが必要ですが、各読み取りの長さは 4 MB になったため、ディスクのシークに要する時間は 1/5 のみになります。マージ パス中のデータ転送効率の向上 (16.6% から 80% はほぼ 5 倍の向上) は、マージ パスの数が 2 倍になったことを補って余りあります。

バリエーションとしては、いくつかのステージでソリッド ステート ディスクなどの中間媒体を使用することがあります。高速な一時ストレージは、データセット全体を保存できるほど大きくなくてもよく、使用可能なメイン メモリよりも大幅に大きくすればよいのです。上記の例を 1 GB の一時 SSD ストレージで繰り返すと、最初のパスでは、その一時領域から読み取られた 10×100 MB のソート済みチャンクをマージして、50×1 GB のソート済みチャンクを HDD に書き込むことができます。SSD の高帯域幅とランダム読み取りスループットにより、最初のパスが高速化され、2 番目のパスの HDD 読み取りは 2 MB になり、シークが読み取り時間の大部分を占めないほどの大きさになります。また、SSD は、マージ フェーズで読み取りバッファーとして使用できるため、HDD ストレージからの大きな読み取り (この例では 20 MB の読み取り) を少なくすることができます。RAM に比べて SSD 容量のコストが低いことを考えると、SSD は非常に限られたメモリで大きな入力をソートするための経済的なツールになり得ます。

メモリ内ソートと同様に、効率的な外部ソートにはO ( n log n ) 時間が必要です。つまり、指数関数的に増加するデータセットには、それぞれ O(n) 時間がかかるパスの数が線形に増加する必要があります。^[4]合理的な仮定の下では、ハードドライブに保存されている少なくとも 500 GB のデータは、3 回目のパスが有利になる前に 1 GB のメインメモリを使用してソートでき、4 回目のパスが有用になる前にその何倍ものデータをソートできます。^[5]

メインメモリのサイズは重要です。ソート専用のメモリを 2 倍にすると、チャンクの数とチャンクあたりの読み取り回数が半分になり、必要なシーク回数が約 4 分の 3 に減ります。サーバーの RAM とディスク ストレージの比率により、1 台のマシンで複数のパスを実行するよりも、マシンのクラスターで大規模なソートを実行する方が便利な場合が多くあります^{[6] 。}ソリッド ステート ドライブ(SSD)などのランダム読み取りパフォーマンスの高いメディアを使用すると、追加のパスでパフォーマンスが向上する前にソートできる量も増えます。

外部分散ソートは、クイックソートに似ています。アルゴリズムは、近似的にピボットを見つけ、それを使用してN個の要素をほぼ等しいサイズのサブ配列に分割します。サブ配列の各要素はすべて次の要素よりも小さくなり、サブ配列のサイズがブロック サイズよりも小さくなるまで再帰的に処理されます。サブ配列がブロック サイズよりも小さい場合、すべての読み取りと書き込みがキャッシュ内で行われ、外部メモリ モデルでは操作が必要になるため、ソートは迅速に実行できます。 ${\displaystyle {\tfrac {M}{B}}}$${\displaystyle O(1)}$

しかし、ピボットを正確に見つけるだけでは、外部分布ソートを漸近的に最適化するのに十分な速さではありません。代わりに、わずかに少ない数のピボットを見つけます。これらのピボットを見つけるために、アルゴリズムはN個の入力要素をチャンクに分割し、すべての要素を取得し、中央値のアルゴリズムを再帰的に使用してピボットを見つけます。^[7]${\displaystyle {\tfrac {M}{B}}}$${\displaystyle {\tfrac {N}{M}}}$${\displaystyle {\sqrt {\tfrac {M}{16B}}}}$${\displaystyle {\sqrt {\tfrac {M}{B}}}}$

マージベースのアルゴリズムと分散ベースのアルゴリズムの間には二重性、あるいは根本的な類似点がある。 ^[8]

コンピューター科学者のジム・グレイが作成したソートベンチマークは、細かく調整されたハードウェアとソフトウェアを使用して実装された外部ソートアルゴリズムを比較します。優れた実装では、いくつかの手法が使用されています。

• 並列処理の使用
  • 複数のディスクドライブを並列に使用することで、シーケンシャルな読み取りと書き込みの速度を向上させることができます。これは非常にコスト効率の高い改善です。コスト重視のペニーソート部門のソートベンチマーク優勝者は、ミッドレンジマシンに6台のハードドライブを使用しています。^[9]
  • ソート ソフトウェアは複数のスレッドを使用して、最新のマルチコア コンピューターでの処理を高速化できます。
  • ソフトウェアは非同期 I/O を使用することで、1 つのデータ実行をソートまたはマージしながら、他の実行をディスクから読み取ったり、ディスクに書き込んだりすることができます。
  • 高速ネットワークリンクで接続された複数のマシンは、それぞれが巨大なデータセットの一部を並列にソートすることができます。^[10]
• ハードウェア速度の向上
  • ソートに RAM を多く使用すると、ディスク シークの回数が減り、パスを増やす必要がなくなります。
  • ソリッド ステート ドライブなどの高速な外部メモリを使用すると、データが SSD に完全に収まるほど小さい場合、またはまれに、3 パス ソートで SSD サイズのチャンクのソートを高速化する場合、ソートを高速化できます。
  • ハードウェアの最大ソート速度には、CPU 速度とコア数、RAM アクセス待ち時間、入出力帯域幅、ディスク読み取り/書き込み速度、ディスク シーク時間など、他の多くの要因が影響します。ボトルネックを最小限に抑えるためにハードウェアを「バランス調整」することは、効率的なソート システムを設計する上で重要な部分です。
  • 特にノード コストが低いためより多くのノードを購入できるクラスター環境では、コスト効率と絶対的な速度が重要になります。
• ソフトウェアの速度向上
  • ソート ベンチマークの参加者の中には、ソートの最初のフェーズで基数ソートのバリエーションを使用する人もいます。つまり、値の始まりに基づいて、データを多数の「ビン」の 1 つに分割します。ソート ベンチマーク データはランダムであり、この最適化に特に適しています。
  • 入力、中間ファイル、および出力を圧縮すると、I/O に費やされる時間を短縮できますが、ソート ベンチマークでは許可されません。
  • ソート ベンチマークでは、短い (10 バイト) キーを使用して長い (100 バイト) レコードをソートするため、ソート ソフトウェアでは、メモリ I/O 量を削減するために、キーを値とは別に並べ替えることがあります。

• メインフレームのソートマージ
• 外部メモリアルゴリズム
• ファンネルソート
• キャッシュを無視した分散ソート

• STXXL、外部マージソートを含むアルゴリズムツールキット
• 外部マージソートの例
• K-Wayマージ実装
• Java での外部メモリソート
• Judy Arrays を使用したペニーソートの実装例
• ソートベンチマーク