FOLIO Advent Calendar 2019 - Qiita 18日目です。 前日は krrrrさんの RustでもServer::Starterでhot deployをする - decadence でした。
毎年この時期にしかFASTを読めていない まっちゃら (@matsu_chara) | Twitterです(´･_･`)
今回はFAST '19からScaleCheck: A Single-Machine Approach for Discovering Scalability Bugs in Large Distributed Systems | USENIXを読んだときの勉強メモです。 自分が面白いと思ったところを中心にしたり、個人的に調べた内容が入っていたりするので正確かつ完全な情報は上記論文や関連文献等を直接読んでいただければと思います。
ざっくり
大規模ストレージシステムに関する新しい種類のバグである Scalability bugs を検出するScaleCheckという手法が提案されています。
Scalability bugsとはノードが数台〜数十台程度では顕在化せず、数百台以上の大規模クラスタになって初めて顕在化するようなバグのことを指しています。
ScaleCheckはこのScalability bugsを実際に数千台規模のクラスタを組むのではなく、１台のマシン上で上記のような問題を潜在的に抱えているかどうかを確認する方法を提供します。 論文ではScaleCheckの提案のみならず、実際に1台のマシンのみを用いてCassandra,Riak等のシステムに適用し、10個の既知のバグ＋4個の新しいバグを検出することに成功したことも述べられています。
背景
大規模サービスを運営する企業で運用されているクラスタは、そのノード数も巨大になりがちで論文では以下のような例が挙げられています。*1
- Netflix runs tens of 500-node Cassandra clusters [34]
- Apple deploys a total of 100,000 Cassandra nodes [2]
- Yahoo! revealed the largest Hadoop/HDFS cluster with 4500 nodes [35]
- Cloudera’s customers deploy Spark on 1000 nodes [24, 27].
本論文はこのような巨大クラスタを運用する際に顕在化するクリティカルなバグをscalability bugsと呼称し、cloud-scale時代に発生するようになった新世代のバグであると呼んでいます。
実際に巨大なクラスタで発生するバグとしては以下のような実例が挙げられています。
これを見るとたしかに100, 1000ノード単位で顕在化するバグが存在するようです。
例えばcassandraの内部処理でノード数依存でO(N3)の処理があり、計算に0.1~4sec程度時間が必要になった事例が挙げられています。 こういったことがあると、gossipプロトコルで最新のノード情報を取得するまでに時間がかかりすぎ、あるNodeが故障<->復旧の各状態を高速に繰り返すflappingと呼ばれる問題を引き起こします。 こういった問題はノード数が少ないと影響がでにくいため、クラスターが大きくなった時に初めて顕在化する問題だとされています。
このような問題を見つけるために実際に巨大なクラスタを組んで検証するのはハードルが高いため、 １台のマシンでその問題を検知するためのScaleCheckの提案につながったというわけです。
Scale Dependent Loops
Scalability bugsを検出するためには、Scalability bugsの原因は何なのか？を考える必要があります。
本論文ではまず Scale Dependent Loops が挙げられています。
これはノード数に依存するようなデータ構造のループのことです。
ScaleCheckのSFindでは、メモリ消費の増加傾向からこのループ構造を検出します。
実際には上記以外にもファイル、パーティション、テーブルなど様々な軸で、スナップショット、マイグレーションなど様々なワークロードについて問題を検出するようです。
large-scale testing (in one machine)
巨大なクラスタを使ってテストを行えば当然Scalability bugsを検出できると思われますが、一方で様々なハードルがあるため1台のマシンでテストを行えるようにしたいところです。 しかし実際にそれを行うためには下記のような様々な困難を解決する必要があります。
STestでは上記をSPC+GEDA+PILというテクニックで解決し、１台での大規模テストを行えるようにしています。 詳しく説明すると長くなりすぎるため下記では要素のみの紹介とし、具体的な解説は論文に譲りますので興味がある方はそちらを御覧ください。
ナイーブに１台に複数プロセスを立てるのだと50ノード程度しか立たないため今回の目的には向かないようです。 そこでSingle Process Cluster（SPC）として１プロセスに複数ノードを立てる（つまりスレッドでノードを管理する）手法が導入されています。
しかし単純なSPCを行うと、イベントキューやワーカープールがノードごとに作られるためリソースを多大に消費します。（120ノード程度とのこと）
これらを節約するためにGlobal Event Driven Architecture(GEDA)を導入します。 GEDAはグローバルなイベントハンドラを用意し、ノードごとの通信をグローバルイベントキューへのキューイングとして表現します。 また各ノードはグローバルなキューからイベントを取得し処理を行うだけです。
上記だけでも大規模テストができるとのことですが、 これだけだと特にCPU-intensiveなタスクの際に結果が正確でないケースがあるため、CPU intensiveな計算をsleepに置き換えるProcessing Illusion(PIL)というテクニックを導入しています。
PILは画像を見ると何をしたいかがわかりやすいと思います。
検証
実際にいくつかのミドルウェアで検証を行い、既知のバグや新しいバグを検知しているようです。
新種のバグとしては以下の物が挙げられています。
Cassandraのdecomission時の不安定性 *2
HDFSのsnapshot diff size, metasave
感想
問題設定として様々なミドルウェアに潜む巨大なクラスタで発生するバグを包括的に捉えるのは興味深く感じました。 実はScalability Bugsという問題設定はHotOS'17 Scalability Bugs: When 100-Node Testing is Not Enough において提案されています。 同一の著者グループによる研究のようなので、より深く問題を理解するためにはこちらもみておくと良いでしょう。
ScaleCheckは任意のミドルウェアにすぐ適用できるフレームワークではなく、ミドルウェア側の実装修正が必要になっています。 しかし各ミドルウェアに対して179 ~ 918 LOCレベルなので、そこまで大きな変更を加えずに対応することが可能そうです。
リアルワールドの問題を実際に発生させられるように大規模クラスタを模倣できる開発環境を作るという取り組みを論文中ではlarge-scale testingを民主化すると表現しているのですが、巨大企業に所属していなくても大規模ミドルウェアの開発に貢献しやすくなるという点で意義深いと思いました。*3
FASTあたりの論文を読むと堅牢な分散システムが崩壊していくのはよく見られる（？）*4のですが、実運用では細かいところを追いきれずある程度信用してしまっている側面もあるかと思います。 どのようなミドルウェア・ファイルシステムでも完璧に障害が起きないようにするのは非常に難しい（はずな）ので、どのような問題が起きうるのか？を研究を通して学んでいくだけでも、（実際にそのテクニックや技術を使うことがなくても）実運用に役立つ視点や、考え方を得られるのではないかなと思っています。って結びの言葉を書いてたら去年も同じようなことを書いていました。成長...
Replicated State Machinesでのストレージ故障からのリカバリー - だいたいよくわからないブログ
ところで、社内からそもそもgossip部分がスケールしないのはアーキテクチャ的に見えてるしループ改善してもすぐ帯域やCPUで限界が来そう*5という指摘がありました。そういった部分をどう乗り越えるかは論文の対象外ではありますが、現実の厳しさを感じつつこの記事を終わりたいと思います。
*1:1クラスタじゃないと思いますが10万のcassandraって何に使ってるのか気になりますね
*2:筆者はCassandraに詳しくないため前提や最新バージョンでの修正状況などを把握できていません。ご了承ください
*3:colocation factor=50のnaive packingでもEC2 10台程度で500ノード建てられるので、そちらでもみたいなところはありますが、ソロコントリビューターでも気軽に貢献できることを目指すとなるともう少しハードルを下げたいと思うので。
*4:当社比というか、自分がいろいろな前提を理解していないだけ...
*5:>This model works well for a system that contains couple of hundreds of nodes https://www.allthingsdistributed.com/2007/10/amazons_dynamo.html より
