テストステ論

高テス協会会長が, テストステロンに関する情報をお届けします.

(writeboost report) 複数スレッドから同時にseqreadされてもスレッショルドを有効にする

前回の記事で, 複数スレッドからseqreadされた場合, そのsplitされたchunkがinterleaveしてしまい, 結果としてシーケンシャル検知が出来なくなるという問題があると述べた.

前回までに実装したシーケンシャル検知の方法を私はforeground cancellationと呼んでいる. foregroundの意味は, mapフックへの入力に対して行うということである. 入力されてきたclone bioのセクタを追っていき, スレッショルド以上にシーケンシャルな場合はステージング用のcellをキャンセルするという仕組みになっている.

今回はこれに加えてbackground cancellationを実装した. これは, 実際にRAMバッファにリードデータを流しこむ時(endioからキックされるスレッドで行う. これがbackgroundの由来), cellをセクタ順にソートしてもう一度シーケンシャルを調べあげるという手法である.
例として, cellの数が4つであって, 長さ2のリードはシーケンシャルとみなすとする. ここでforegroundで[0, 100, 1, 101]というリードを受け取ったとする. これはforegroundでは完全ランダムに見えるのでキャンセル不可能だが, backgroundではソート後に[0,1,100,101]となって, 全部キャンセル出来る.

もともと, cellを管理するデータ構造をハッシュテーブルとしていたが, この方式だとbackground cancellationがうまく実装出来ないことがわかったため, 本日, (泣きながら)RBツリーで管理するように再実装した. RBツリーであれば, rb_firstからrb_nextして辿っていくとセクタ昇順であることが保証されるため, sortルーチンなどを呼んでデータ構造を変更せずに済む. foregroundからcell管理用のデータ構造を参照される可能性がある状況下でそのデータ構造を変更することは禁忌であり(そしてロックをとるのも強引すぎるし, きっとどこかで綻ぶ感じ), 元からソートされているデータ構造に変更する必要があった. シーケンシャルなキーをRBツリーに入力していくのはワーストケースであるが, オーダは変わらないため問題は少ない.

検証のため, 2つのスレッドからddする実験で, background cancellationなし/ありを比較する. 「なし」の場合は, HDD(252-32)からのリードの一部がSSD(252-16)にステージングされてしまってるが(なぜ一部かというと, foreground cancellationで弾かれるケースもあるからである), 「あり」の場合はこのステージングがすべてキャンセルされている.

dd if=/dev/mapper/wbdev iflag=direct of=/dev/null bs=1M &
dd if=/dev/mapper/wbdev iflag=direct of=/dev/null skip=1000 bs=1M &
wait

background cancellationなし:

21:14:41          DEV       tps  rd_sec/s  wr_sec/s  avgrq-sz  avgqu-sz     await     svctm     %util
21:14:42     dev252-0      0.00      0.00      0.00      0.00      0.00      0.00      0.00      0.00
21:14:42    dev252-16     14.00      0.00   7168.00    512.00      0.44     32.86     17.86     25.00
21:14:42    dev252-32   2438.00  19504.00      0.00      8.00    124.22     50.58      0.41    100.00
21:14:42     dev251-0   2440.00  19520.00      0.00      8.00    125.31     50.98      0.41    100.00
21:14:42     dev251-1      0.00      0.00      0.00      0.00      0.00      0.00      0.00      0.00
21:14:42     dev251-2      0.00      0.00      0.00      0.00      0.00      0.00      0.00      0.00
21:14:42     dev251-3     12.00      0.00   6144.00    512.00      0.44     38.33     20.83     25.00
21:14:42     dev251-4   2441.00  19528.00      0.00      8.00    125.41     51.00      0.41    100.00

background cancellationあり:

20:47:54          DEV       tps  rd_sec/s  wr_sec/s  avgrq-sz  avgqu-sz     await     svctm     %util
20:47:55     dev252-0      0.00      0.00      0.00      0.00      0.00      0.00      0.00      0.00
20:47:55    dev252-16      0.00      0.00      0.00      0.00      0.00      0.00      0.00      0.00
20:47:55    dev252-32   2498.00  19984.00      0.00      8.00    124.54     50.29      0.40    100.00
20:47:55     dev251-0   2498.00  19984.00      0.00      8.00    125.71     50.76      0.40    100.00
20:47:55     dev251-1      0.00      0.00      0.00      0.00      0.00      0.00      0.00      0.00
20:47:55     dev251-2      0.00      0.00      0.00      0.00      0.00      0.00      0.00      0.00
20:47:55     dev251-3      0.00      0.00      0.00      0.00      0.00      0.00      0.00      0.00
20:47:55     dev251-4   2498.00  19984.00      0.00      8.00    125.81     50.80      0.40    100.00

ここまで読んで, 読者は1つの疑問を持ったと思う. 「background cancellationがあるならば, foreground要らないのでは?」. 答えは完全にNo. ステージングするためのデータはendioでコピーしているのだが, foreground cancellationでキャンセルしたデータは, かなりの確率で, endioでのコピーを省ける. 予め要らないとわかっていればコピーする必要がないからである. 対して, background cancellationは, データをコピーした後の話である. メモリコピーをそこまでして省く意味があるかは分からないが, foreground cancellationの実装はあまり重くないので, 通常のケースではペイするだろうと思って削除していない.

最後に, この実装は現実的にはほぼ100%ワークすると思うが, 極端な状況ではワークしない. 現実的には例えば, 256KB大のリードはシーケンシャルとみなしてキャッシュしたくないという設定になるだろうが, 例えば100スレッドから同時にリードを行った場合は今の実装は耐えられない. しかし, 8スレッド程度であれば十分に耐えられる. background cancellationをする前にもっと多くのcellをためこんで決定を遅らせれば解決にはなる(foregroundがblockされる時間が伸びるという悪影響はある)のだが, 単なるいたちごっことなる. 現実的には, 8スレッドで並行seqreadするケースですらそれほど多くないだろうし, そもそも100個もコアがあるマシンのストレージを担うことをライトブーストは想定していないので, これで十分と判断した.