ストレージメモリへの参照が有する性質について

はじめに

過去に、某C央大の某T内教授のLabに所属していたときに書いたものの、よくわからない理由で投稿を許可されず、仕方ないのでここで供養します。
一度、個人名で学会投稿もしましたが、こういうのはネットに流す方が目にとまる数が多そうなので、こちらに放流しておきます。

MSR-Cambridge Traces

解析の対象ついて

まず、解析の対称となるMSR-Cambridge Tracesについて簡単にまとめます。
Microsoft Research Cambridgeが公開している、サーバ（おそらくWindows searverの)ディスクのアクセス履歴です。

ダウンロードはhttps://ci.nii.ac.jp/naid/20001651868/から可能です。

２つのgzipファイルを解凍すると、README.txtと36個の *.csv.gzが得られます。
ファイルは３６個ですが、ワークロード（Traceを取得したserver）は１３種類です。
各Traceファイルには、<hostname>_<disknumber>のような名前が付けられています。

例えば、hm_0.csvとhm_1.csvはhostname:hmから取得した、Disk0とDisk1です。
Disk0はsystemないしbootディスク（WindowsのCドライブ）に相当するとありますが、一部例外もあるとのこと。

csvファイルのフォーマットは、
Timestamp,Hostname,DiskNumber,Type,Offset,Size,ResponseTime
となっています。一例としてhm_0.csvを示すと

128166385295514663,hm,0,Write,9056014336,2048,2833
128166385295514878,hm,0,Write,11855351808,512,2617
128166385295515175,hm,0,Write,5548077056,4096,2320
128166385301451520,hm,0,Write,3163095040,40960,3438
128166385301453920,hm,0,Write,3154132992,4096,1037
...

となっています。
1. Timestampは"Windows filetime"という100ns単位のtimestamp
2. Hostname とDiskNumberはファイル名と同じ
3. Typeは"Read"もしくは”Write"
4. offset、lengthはbyte単位での読み書きの開始ポイントのoffsetと長さ。長さは最小で512byte単位（ブロック）
5. Response time はI/Oが発行されてから完了までの時間

アドレスデータが並んでいても分からないので、可視化してみましょう。

下準備

まず、扱いやすくするためにいくつかの加工を行います。

1. 不要な情報を消去する（workload名とかDisk No.などは、ファイル名を見れば良いだけなので不要です。またResponce timeも今回は使いません）
2. Timestampを記録開始時間を０に合わせ、ns(ナノ秒） -> s（秒）に変換
3. OffsetもRequest Lengthも最小で512Byte単位なので512で割る
4. Offset, Request Lengthというは使いにくいので全部アドレスに変換する。このとき、データ削減のため、16kB単位のアドレスとする。（これをPage Addressと呼ぶことにする）
5. Page Addressをリナンバリングする

複数のプログラムで上記の処理を実現しました。スッキリ書けたらどこかにアップするかも。

処理後のファイルの一例(hm_0)を示します。

0,Write,103883
2.15e-05,Write,124307
5.12e-05,Write,90871
5.12e-05,Write,90872
0.5936857,Write,83511

前から順にTimeStamp,Write/Read,PageAddresがずらずらと記載されています。
ブロックデバイスは、始点（Offset）とリクエスト長でアクセスするため、PageAddressが一個一個書いてある形式は冗長にはなっていますが、可視化するという目的では扱いやすくなっています。
（512Byte単位のBlockAddressのまま扱うと、ファイルサイズが大き過ぎてプロットするだけでも時間がかかるため16kB単位のPageAddressで扱います）

Traceの可視化

WriteとReadの区別はさておいて、一旦リクエストをプロットしてみましょう。
workload hmのDisk0とDisk1をプロットしてみます。

workload:hm (hm_0, hm_1)

workload:mds(mds_0, mds_1)

workload:prn(prn_0, prn_1)

workload:proj(proj_0,proj_1,proj_2,proj_3,proj_4)

workload:prxy(prxy_0, prxy_1)

workload:rsrch(rsrch_0, rsrch_1)

workload:src1(src1_0, src1_1, src1_2)

workload:src2(src2_0, src2_1, src2_2)

workload:std(stg_0, stg_1)

workload:ts(ts_0)

workload:usr(usr_0, usr_1)

workload:wdev(wdev_0, wdev_1, wdev_2)

worload:web(web_0, web_1, web_2, web_3)

ごちゃごちゃして何がなんだか分からないかもしれませんが、Diskが違っても似たような形をしていたり、アクセスが集中する時期が同じようなタイミングだったりと、やはり同一のWorkloadに起因していそうだなー、くらいのことは見て取れます。（定量的には議論しません）

また、prxy_0やrsrch_0、wdev_0などのTraceでは、ある範囲のアドレスが斜線で網掛けされたような模様になっていますが、これはその範囲のアドレスにループ的な参照が生じていることを表しています。メモリへのアクセス（参照）には、時間的局所性、空間的局所性、逐次的局所性の３つの局所性(locality）が知られていますが、これは逐次的局所性の一例と言えます。