30分で論文流し読みシリーズ6「Gleaner: Mitigating the Blocked-Waiter Wakeup Problem for Virtualized Multicore Applications」

https://www.usenix.org/system/files/conference/atc14/atc14-paper-ding.pdf

実際の所要時間: 1時間

課題 - VMにおいて頻繁にvCPUがidleになるワークロードのnative環境に比べての性能劣化が激しい - 理由はvCPUがアイドルになる処理、およびその後再びidleが解除される処理がpCPUに比べてとても遅い。理由は次の通り - idle化: pCPUは「何もすることが無い」->「省電力状態にするための特殊な命令を実行」->「アイドル」だが、vCPUの場合は「何もすることがない」->「特殊な命令を実行」->「VMMに制御が移ってなんやかんや」、と、手番が多いから - idleからの復帰: pCPUは「割り込みないしIPI食らって起きる」->「動作の再開」だが、vCPUの場合は「VMMが割り込みないしIPIをvCPUに送る」->「vCPUプロセス起こす」->「vCPUプロセスが起床」->「動作の再開」と、手番が多いから

解決方法概要 - vCPUをなるべくidle状態にしない

解決方法詳細 - idleになろうとするときに省電力状態にするための特殊な命令を実行せずにspin loopする、あるいはguestから直接物理CPUを省電力状態にできる命令を実行 - delayed scheduling: vCPU1上のプロセスAがアイドルなvCPU2上のプロセスBを起こす場合、通常プロセスBをvCPU2上で起こすが、あえてvCPU1上で起こす。これによってidleから非idleへの状態遷移を減らせる - imbalanced scheduling: runnableなプロセスをなるべく特定のvCPUに固めて、その他のvCPUをidle状態にとどめることによって、idleと非idleの状態遷移を減らす

効果 - 時間切れで見られなかった

感想 - imbalanced schedulingは現在省電力のためによく使われているやつ。このアイデアは組み込み用途かVM用途か、どちらが先に考えられたのだろうか

「イベント無線LAN完全自壊マニュアル vol. 1」を読んだ

大規模イベントにおいて参加者に提供する無線LANサービスを構築するノウハウについて書いた本です。著者のえぬかねさんに献本いただいたときは「この全く知見が無い分野の本をいただいたが理解できるだろうか」と心配していましたが、案の定専門的なところは全く理解できませんでした。しかし、わからないならわからないなりに、本書はわたしにはとても楽しめる本でした。筆者の簡潔明快な文体、血と汗の臭いがする具体的な話の数々、大量のデータ、どれもこれもわたしの好みのど真ん中でした。こういうのもっと読みたい。

「OS Girls 2」を読んだ

技術書典7において販売されていた本の読書感想文です。BOOTHで電子版を販売中です。

hikalium.booth.pm

「OS GIrls」の続編です。前作の読書感想文はこちら。

satoru-takeuchi.hatenablog.com

わりと真面目な感想文は前回書いているし今回も同様の感想なので省略。今回はその他の感想を主に書きます。

前回同様、相変わらずかっ飛ばしていて、いい意味での突っ込みみどころがたくさんあります。ネタをそのまま書いてしまうと全然面白くなくなるで私の突っ込み部分だけを書いておきます。

  • 「この事象からOSの話につなげるのか…」
  • 「これは早口で自分の言いたいことをまくしたてるタイプのオタク」
  • 「まさか、まさか、この流れ…初級者の前でこの技術に言及するつもりでは………でししたね、ですよね、この子ならそういうこと言っちゃうよね」

続編に期待です。気長に待ってます。

「OpenCVデバッグ探偵記」を読んだ

技術書典7で著者の@tomoaki_teshimaさんに献本いただいた本です。

本書はOpenCVを題材にバグを見つけてからデバッグ、そのあとOpenCVのupstreamに還元するための技術について解説してくれています。このデバッグをする流れを筆者は探偵による調査に見立てています*1。経験豊富なソフトウェア技術者であり、かつ、OpenCVというOSSに幾多の貢献をしてきた筆者による迫力満点なトラブルシューティングは見どころ一杯です。題材は特定のソフトウェアですが、あらゆるトラブルシューティングに通じる内容です。ひたすら解析が続くだけではなく、ときおり箸休めのための余談が入ったり、コラムが入ったりというのもうれしいところです。

本書はこちらから電子版を購入できるようです。わたしが以前書いた以下のOSSトラブルシュート記事を面白いと思うかたであれば本書もきっと気に入るでしょう。

qiita.com

ここで本書を読むのに必要な前提知識について述べておきます。主にC++アセンブリ言語のソースをもとにした解説なので、これらの言語を知っているのが好ましいと思います。しかし、解説が丁寧なので流し読みするくらいであればなくても大丈夫だと思います。

脱線ですが、なぜ献本いただいたかというと、著者がわたしの過去の活動Ryzen SEGV Battleを気に入ってくれたからだそうです。書籍でも触れてくれています。ご興味のあるかたはごらんください。書籍化もされています

最後になりますが、もう一度。とてもいい本でした、献本ありがとうございました。

*1:わたしを含め、このたとえは非常に的を射ているのでけっこう使う人が多いです

30分で論文流し読みシリーズ5「Replication Under Scalable Hashing: A Family of Algorithms for Scalable Decentralized Data Distribution」

Replication Under Scalable Hashing: A Family of Algorithms for Scalable Decentralized Data Distribution

↓の参考として挙げられているもの satoru-takeuchi.hatenablog.com

  • 実際の所要時間: 1時間半
  • 課題
    • 分散ストレージにおいてオブジェクトの配置情報を中央集権型でなくするには、かつては実際のデータ配置前にすべての配置位置を決めて、その後のディスク増減コストは大量のデータ移動が必要な高コストなものだった
  • 解決方法概要
    • RUSHというアルゴリズムセットを開発した*1
    • RUSHはディスクの追加削除も低コストでできる
  • 解決方法詳細
  • 効果
    • 図5~8あたりを参照
  • 感想
    • CRUSHの論文にRUSHには問題があるようなことが書かれていたが、たしかにこれだけだとけっこうつらそう。以下理由
      • あるオブジェクトのレプリカを同じラックに配置するようなtopology awareな配置ができない
      • ちょこちょこストレージを足していくとサブクラスタの数が増えて色々な処理が低速化しそう

*1:正確にはRushPは以前の論文に既に書かれている

30分で論文流し読みシリーズ4「CRUSH: Controlled, Scalable, Decentralized Placement of Replicated Data」

CRUSH: Controlled, Scalable, Decentralized Placement of Replicated Data

  • 実際の所要時間 1時間半
  • 課題
    • オブジェクトストレージにおいて、どのストレージデバイスにどのようにデータをを配置するかには様々な方法がある
    • 既存のものは巨大なメタデータ(およびそれを置くメタデータサーバ)が必要だったりストレージデバイスの故障や追加/削除によって大量のデータの移動が必要だったりと一長一短
    • RUSHという計算によってオブジェクトの配置場所を決めるいいかんじのアルゴリズムがあるが、あんまり効率がよくない
  • 解決方法概要
    • CRUSHと言うアルゴリズムを開発した
      • データを各ストレージデバイス疑似ランダムに配置できる
      • レプリカやイレージャコーディングも可能
      • ストレージデバイスの故障や追加/削除によるデータの再配置が少なくて済む
      • バイスごとにweightも変えられる。たとえば大容量のストレージデバイスのweightを上げて小容量のものはweightを下げる、など
      • トポロジーを意識したデータ配置ができる。この構成のことをcrush mapと呼ぶ
      • crush mapに対して、あるオブジェクトのレプリカを同じノードに置かないとかいうルールが作れる。これをplacement ruleと呼ぶ
  • 解決方法詳細
    • 論文の中のAlgorithm 1、figure 1~4あたりを見てね!
    • 細かいところではinternal nodeに相当するbucketの種類が複数ある(uniform buckets, list buckets, tree buckets, straw buckets)
    • それぞれオブジェクトをストレージデバイスにmapする速度、デバイス追加/削除時の処理の効率が違う(table 2参照)
  • 効果
    • 様々な性能をbucketの種類ごとに、場合によってはそれに加えてRUSHのものと比較してある(figure 5~8)

感想 - Ceph(データ配置にCRUSHを使っている)の内部を知るには読んどかないとまずい - 魔法のようである。うまくやるものだ - RUSHの論文も読んでおかないとうまく解釈できないと思う

Cephとの比較 - Cephにおいては、いまではbucketは上記4つとはまた違うstraw2というのがデフォルトで使われている。もはや他のものをあえて使う必要はないだろう - placement ruleはCephにおいてはcrush ruleと呼ばれることが多い - オブジェクトは直接ストレージデバイス(正確にはOSD)にマップされるのではなく、Placement Groupというものにマップされる。同じplacement groupに属する全オブジェクトは、placement groupに対応するOSDにレプリカを配置する。たぶん組み合わせ数が死ぬほど増えるのを防ぐためにこうなってる