Zenn
🐷

コンピュータ技術の「似たようなものは続くよどこまでも」

2021/01/21に公開
#
cache
#
queue
#
outoforder
#
pagecache
#
ioscheduler
tech

はじめに

コンピュータの世界にはさまざまな技術があります。このため、全体を全部把握しようとするのは至難の業、もしくはほとんど不可能です。ただし、まったく別に見える分野でもその奥底では似たような技術が使われていることが多々あります。本記事ではそのうちの一部、データのキャッシュと処理の並び替えについて述べたいと思います。扱う分野はCPUとストレージI/Oです。

本記事ではあまり技術的に込み入ったことは書かずに各技術について概要を知ってもらうことが目的です。このため、けっこう説明を省いている部分がありますのでご容赦ください。正確なところは機能や技術の名前などを使って検索したり適当な文献にあたるなどしてください。

説明の中でソフトウェアについて書いている部分は基本的には筆者のLinuxカーネルの知識に基づいています。他のOSならまた少し違うかもしれません。

CPU

キャッシュメモリによるデータのキャッシュ

CPUは簡単に書くと次のような動きをします。

  1. メモリからCPUのレジスタにデータを読み出す
  2. レジスタ上の値をもとに計算
  3. 計算結果をメモリに書き込む

ここでメモリとデータ間のデータ転送にかかる時間は計算処理の時間の100倍ほど遅いため、いくら計算が速いCPUでもデータ転送速度がネックになって全然性能が出ません。

この問題を解決するために生まれたのが、メモリとCPUの間にあるキャッシュメモリという機構です。キャッシュメモリはかなり雑にいうと次のような特徴があります。

  • メモリとCPUのレジスタの間に存在するハードウェア機能。典型的にはCPUの中にある
  • メモリとレジスタ間のデータ転送をするときはいったんキャッシュメモリを経由する。別のいいかたをするとキャッシュメモリ内にキャッシュする
  • CPUがキャッシュメモリに乗っているデータにアクセスするとメモリ上にはアクセスせず、キャッシュメモリ上のデータにのみアクセスする。つまりメモリアクセスよりもはるかに高速にデータ転送ができる
  • プロセスからは基本的にキャッシュメモリの存在は隠蔽されている。メモリアクセスするたびに内部的に使われている
  • メモリよりも高価で容量も小さいが、CPUとキャッシュメモリ間のデータ転送速度はキャッシュメモリとメモリ間の転送速度よりもはるかに高速

上記の特徴があるため、一定時間内に処理するデータがキャッシュに乗っていれば、そうでない場合よりも見かけ上の処理速度をはるかに上げられます。

Out-of-Order実行による処理の並び替え

CPUの命令は単純に書くと以下のように処理されます。

  1. 命令を読み込む
  2. 命令実行に必要なデータが揃う(命令実行に使うレジスタにメモリからデータが読みだされる)のを待つ
  3. 命令を実行ユニット(整数演算、浮動小数点演算、など)に送る
  4. 命令実行

これをIn-order実行と呼びます。このしくみはCPUのつくりをシンプルにできるものの、実行効率が悪いです。たとえば二つの連続した命令が次のように互いに関係ないものだとします。

  • 命令1: レジスタR1の値を1増やす
  • 命令2: レジスタR2の値を1増やす

この場合、命令2の実行は命令1が完全に終わるまで待たされます。

この問題を解決するために生まれたのがOut-of-Order実行です。Out-of-Order実行をするプロセッサの命令処理は次のようになります。

  1. 命令を読み込む
  2. 命令をキューに送る
  3. 命令実行に必要なデータが揃った準備ができた順に実行ユニットに送って実行する。

この場合、たとえば上記命令1,2を実行する場合、命令1についてR1にデータが読み込まれる前にR2にデータがすでに読み込まれていた場合は命令2を先に実行することになります。命令の実行順がかわることがありうるためOut-of-Orderという名前がついているわけです。このOut-of-Order実行によって効率的に命令を実行できます。

ストレージ

ストレージといってもいろいろありますが、ここでは分散ストレージなどは考えずに以下のレイヤのみ扱います。

  • キャッシュメモリ
  • ブロックデバイス層
  • デバイスドライバ
  • ストレージデバイス

簡単に書くとユーザがブロックデバイスに直接、あるいはファイルシステム経由でデータを書き込むとキャッシュメモリ、ブロックデバイス層、デバイスドライバ、ストレージデバイスの順番にデータがわたります。読み出しの場合は逆です。ここでは簡単のため書き込みについてのみ扱います。

ページキャッシュによるデータのキャッシュ

CPUとメモリの間にキャッシュメモリがあるように、メモリとストレージデバイスの間にも似たような仕組み、ページキャッシュがあります。なぜ存在するかという理由も似ていて、メモリ上のデータをストレージデバイスに書き込む速度はメモリアクセス速度に比べて数桁倍遅い(デバイスによってかなり違います)問題を解決するためにページキャッシュはあります。

ページキャッシュは次のようなものです。

  • OSカーネルの機能
  • メモリ上に存在する
  • ユーザがデータを書き込むといったんページキャッシュを経由して、そのあとストレージデバイスに書き込まれる。
  • ユーザが次回同じ領域に書き込むとストレージデバイスにはアクセスせず、ページキャッシュにのみデータを書き込んで復帰する。つまり見かけ上のアクセス速度が数桁倍早くなる
  • プロセスからはページキャッシュの存在は隠蔽されている。プロセスはページキャッシュは基本的に意識しなくて済む。

ページキャッシュははるか昔からコンピュータシステム全体の処理性能向上のために大きな役割を果たしてきましたが、ここ数年出てきたNVDIMMなどの超高速ストレージデバイスについてはページキャッシュが邪魔になることもありうるため、ファイルシステムやデバイスによってはページキャッシュを使わないDirect Access Mode(DAX)という機能も使えるようになってきました。

ブロックデバイス層による処理の並び替え

ブロックデバイス層に届いたデータはそのままデバイスドライバに渡されるのではなく、いったんI/Oスケジューラという機能のキューに溜められます。ここで次のような目的のために整合性を保てる範囲で並び替えられます。

  • 個々のプロセスに与えるデータ転送量を平等にする(CFQ I/Oスケジューラ)
  • 各I/Oがなるべく所定の時間以内に処理を完了できるようにする(deadline I/Oスケジューラ)
  • 同じ領域に対する連続した書き込みを一つのI/Oにまとめる
  • HDDの特性を活かすために連続する領域へのI/Oをマージしたり、連続するI/Oをセクタ順に並び替える

I/OスケジューラについてはNVMe SSDなどの高速デバイスについては邪魔になることが多々あるため、ほとんど何もしないnoopスケジューラというものもあります。

ストレージデバイス層

write cacheによるデータのキャッシュ

ストレージデバイスによってはwrite cacheという機能を備えています。write cacheは次のような機能です。

  • デバイスの機能
  • デバイスドライバがストレージにデータを書き込むためのメモリ(ページキャッシュなど)とデバイスの記憶素子の間に存在する。位置的にはストレージデバイスの中
  • メモリからストレージの転送には時間がかかるので、いったんwrite cache領域に書くだけでドライバから見ると処理が完了したように見せる
  • ストレージデバイスのコントローラはwrite cache上のデータを後から記憶素子上に書き込む

これによってとくにメモリアクセスに比べてアクセス速度が数桁遅いHDDにおいては見かけ上の速度が劇的に上がります。ただし例によってNVMe SSDなどの高速なデバイスにおいてはHDDに比べると大きな効果は期待できません。また、DIMMなどの揮発性のあるものをwrite cacheとして使っている場合はディスクにデータ書き込んでもデータを失う可能性がありますので、それを嫌って性能向上はあきらめてでもwrite cacheを無効化することもあります。

コマンドキューによる処理の並び替え

ストレージデバイスへのI/Oもデバイスドライバが発行した順番に処理されるとは限らず、デバイス(正確にはデバイスのコントローラ)への支持はコマンドキューという領域にいったん溜められて、デバイスにとって都合のよい順番に並び替えられた上で実際のデータ転送をします。

おわりに

本記事ではCPUとストレージI/Oを題材として、データのキャッシュ、および処理の並び替えという技術が複数の分野にまたがって使われていることを学びました。これと同じような技術はデータベースエンジンであったりネットワークの各レイヤであったり、いろんな場所で使われています。

このようにコンピュータ業界では一つの分野についてある程度くわしくなると他の分野にも応用できる知識がたくさんあります。本記事をきっかけとして、読者のみなさんが主戦場としている分野から一歩離れて別分野を学んだときに「これ〇〇で見たことあるやつ！」という知識がリンクする気持ち良い体験をしてみたくなること、および、それによって広範囲の知識を得られるようになることを願っています。

Discussion