Fast Disk Storage（SSD）による最適化のアルゴリズム？

Question

ソリッドステートディスク（SSD）の価格が低下し、システムドライブとしてまもなく普及することを考えると、アクセス速度が回転磁気メディアよりもはるかに高いことを考えると、標準アルゴリズムはローカルストレージ用のSSD？たとえば、SSDの高速ランダム読み取り速度により、ディスクベースのハッシュテーブルのようなものが大きなハッシュテーブルの実行可能性になります。 4GBのディスク容量がすぐに利用できるため、32ビット整数の全範囲へのハッシュが実行可能になります（ただし、ポピュレーションよりもルックアップの方が時間がかかります）。このサイズのハッシュテーブルは、アクセス速度のために回転メディアでの作業が禁止されますが、SSDではそれほど問題にはなりません。

SSDへの差し迫った移行により、アルゴリズムのパフォーマンスが向上する可能性のある他の領域はありますか？私はむしろ、意見ではなく、1つのことがどのように機能するかについての推論を望みます。これが論争になってほしくありません。

Answer 1

あなたのハッシュテーブルの例は、確かに重要なデータベース構造です。値を調べるために4GB以上のファイル全体をメモリにロードする代わりに、SSDを直接調べることができます。 SSDはRAMよりも桁違いに遅いですが、ディスクに50GBのハッシュテーブルを置くことはかなり合理的ですが、大きな鉄に大きなお金を払わない限りRAMには入れません。

例はチェスの位置データベースです。ハッシュ化された位置が50GB以上あります。ハッシュ内で互いに近い位置に関連する位置をグループ化しようとする複雑なコードがあるので、一度に10MBのテーブルをページングし、複数の同様の位置クエリでその一部を再利用したいと考えています。これを効率的にするためには、大量のコードと複雑さがあります。

SSDに置き換えて、クラスタリングの複雑さをすべてなくし、実際に愚かなランダム化ハッシュを使用することができました。また、大きな10MBのチャンクではなく、必要なデータのみをディスクからフェッチするため、パフォーマンスが向上しました。レイテンシーは確かに大きくなりますが、ネットのスピードアップは大幅に向上します。そして、非常にクリーンなコード（800行ではなく20行）は、おそらくさらに優れています。

Answer 2

SSDは、ランダムアクセスの場合に非常に高速です。ディスクへの順次アクセスは、主流の回転ドライブの2倍のパフォーマンスです。 こちら。

SSDは針をかなり動かしますが、CPUの動作や物理メモリよりもはるかに遅いです。 4GBハッシュテーブルの例では、ランダムハッシュテーブルバケットにアクセスするためにSSDから250 MB / sを超える速度を維持できる場合があります。回転ドライブの場合、1桁のMB / sを破ることができます。この4 GBのハッシュテーブルをメモリに保持できる場合、ギガバイト単位でアクセスできます-非常に高速なSSDよりもはるかに高速です。

参考資料には、MSがSSD上で実行されているときにWindows 7に対して行われたいくつかの変更が一覧表示されており、変更を検討できる種類のアイデアを知ることができます。まず、ディスクからデータをプリフェッチするためのSuperFetchは無効になっています。SSDによって緩和されるディスクへの遅いランダムアクセス時間を回避するように設計されています。ディスク全体にファイルが散らばっていてもSSDのパフォーマンスが低下することはないため、デフラグは無効になっています。

Answer 3

事実、多くのランダムディスクI / Oを必要とするすべてのアルゴリズム（ランダムはキーワードであり、鳥に局所性の原則を投げかけるのに役立つため、多くのキャッシュの有用性が排除されます）続く）。

特定のデータベースシステムがこれから利益を得ているのを見ることができました。 MySQL。たとえば、MyISAMストレージエンジンを使用します（データレコードは基本的にはCSVを美化します）。ただし、非常に大きなハッシュテーブルは、良い例のための最善の策になると思います。

Answer 4

SSDは、ランダム読み取りの場合はかなり速く、シーケンシャル読み取りの場合は少し速く、書き込みの場合は適切に遅くなります（ランダムまたはそうでない）。

そのため、ディスクベースのハッシュテーブルはSSDで適切に役に立たないようになりました。更新にかなりの時間がかかりますが、ディスクの検索は（通常のhddに比べて）非常に安くなります。

Answer 5

自分をからかわないでください。 SSDはまだシステムメモリよりもかなり遅いです。ハードディスク上でシステムメモリを使用することを選択したアルゴリズムは、他のすべての条件が同じであれば、さらに高速になります。