HackerTackle2018でPonyの発表をしてきました

HACKER TACKLE というイベントでPonyについて発表してきました。

タイトルの主張がやや強めになってしまった感がありますが、僕としてはPony自体というよりPonyがチャレンジしていること、それによって到来する未来に注目してもらえたらなーみたいな素朴な気持ちでつけました。

そんな感じの内容だったのでPony入門と見せかけてPonyのコードは少ししか出てきませんでした。 （でもスライド発表で文法の話しても文字が小さくて見えなかったりするしまあいいかみたいな気持ち・・（( ◜◡‾)）

既に発表したことのある内容と被りすぎず、でもそらし過ぎて上級者向きにならないように・・など色々考えました。が！入門的な内容を改定を重ねつつ発表するのはやっぱり難しいですね。　（マイナー言語エバンジェリストあるある（？））

次のセッションがRustコミッターの発表でタイトルが「Concurrency in Rust」という状況でConcurrencyに長所があるPonyの話をするのはなかなか緊張感のある形でしたが、 自分としてはConcurrencyの問題は型で（部分的には）解決できる！というのが世の中に伝わるのが一番（ある意味Ponyの繁栄よりも）重要だと思っているので、むしろ良かったのかなと思います。

現段階でのPonyは結構独自感がありますが、mutable/immutableやモナドのような概念が様々な言語に取り入れられて来ているのと同じ流れでPonyの取り組みの成果みたいなものもどんどん他の言語に取り入れられる流れができると良いなーと思っています。今かどうかは分かりませんがそのうちきっと出来るはず！
そういった流れをいち早くキャッチアップするために、新しい取り組みを行っている尖った言語に触ってみるというのも一興なのではないでしょうか。つまり今すぐponycをインストールしてIntroduction · Pony Tutorialをやりましょう！！

www.slideshare.net

consulの情報を取得するslack bot

consul公式のgo clientを見たらわりかし簡単にたたけそうだったのでノリで作りました。

GitHub - matsu-chara/conbot: consul reader slack bot

特にbot側では対応していないけど環境変数とかを与えるとauthとかhttpsとかやってくれるので楽。 https://github.com/hashicorp/consul/blob/v1.0.6/api/api.go#L282

catalogを見たり、各サービスのIP+portやNoteの一覧が見れたりします。 細かい絞り込みをやったり一覧で取ろうとするとN+1回呼ばないと行けないっぽいのがやや残念だけどゆっくり叩けば死なないかなという気持ち。

Jenkins Groovy ScriptでThrottle Concurrent Builds Pluginのカテゴリーを設定する

ジョブ設定が自動化されててもjenkins設定自体が自動化されてないと意味がない！ということでちょっと自動化してみました。

対象

今回の対象は Throttle Concurrent Builds Plugin - Jenkins - Jenkins Wiki 用のシステム設定で、以下のように表示される部分です。 ※ pluginは v2.0.1で確認しています。

f:id:matsu_chara:20171221132459p:plain

スクリプト

スクリプトコンソールで以下のスクリプトを実行するとカテゴリーや最大実効数が設定されます。

// jenkinsのスクリプトコンソールで実行する場合はimportは省略可能
import jenkins.*
import jenkins.model.*
import hudson.*
import hudson.model.*

def instance = Jenkins.getInstance()
def throttlePluginDescriptor = instance.getDescriptor("hudson.plugins.throttleconcurrents.ThrottleJobProperty")
def deployAllCategory = new hudson.plugins.throttleconcurrents.ThrottleJobProperty.ThrottleCategory("foo", 4, 4, [])

throttlePluginDescriptor.setCategories([deployAllCategory])
throttlePluginDescriptor.save()
throttlePluginDescriptor.load()

setCategoriesなどのメソッドはソース ( https://github.com/jenkinsci/throttle-concurrent-builds-plugin/blob/throttle-concurrents-2.0.1/src/main/java/hudson/plugins/throttleconcurrents/ThrottleJobProperty.java ) から探すのが良さそうです。（descriptorを呼んでやればよいということを探し当てるのに時間がかかった・・。）

プラグイン設定の自動化は他にも https://github.com/glenjamin/jenkins-groovy-examples のような方法もありそうでした。

まとめ

実行はansibleのjenkins_scriptプラグインjenkins_script - Executes a groovy script in the jenkins instance — Ansible Documentationなんかを使えそうです。

ansibleならpluginは jenkins_plugin - Add or remove Jenkins plugin — Ansible Documentation を使えば自動化できますし、 環境変数やクレデンシャルなども Jenkinsの構築それ全部自動でできるよ - Qiita を参考にjenkins_scriptプラグインで自動化できそうなので、だいたいのものは設定できそうです。

CombiningTreeで数を数える

第二のドワンゴアドベントカレンダー10日目です。 昨日は @yyuさんのブロックチェーンを利用した公平なガチャでした。 公平なガチャシリーズは全部おもしろいのでおすすめです。

今回はCombiningTreeによる高速なカウンターを紹介したいと思います。

ベースはThe Art of Multiprocessor ProgrammingとScalable Concurrent Counting. 1994にある内容です。

高速なカウンター

1,2,3,...と数を数えることはよくあると思いますが、マルチコア環境で高速に数えたいケースについて考えてみます。 javaなどでは AtomicIntegerなどがよく利用されると思いますが、ここでは更にスケールするカウンターを考えてみたいと思います。

ComibiningTree

スケールすると言っても、一つのアドレスを書き換えあうアプローチでは、値を正確に数えるために必要となる同期がボトルネック（逐次ボトルネック）となってしまいます。 そのため、より高速なカウンターを実現するためには、何らかの意味で並列度を高くする必要があります。

そこで、複数のincrementリクエストを結合することで並列化を達成するCombiningTree（結合ツリー）を使ったカウンターを考えます。

CombiningTreeは下図のような二分木で、各leafには最大２つのスレッドが割り当てられます。 rootにはカウンタが配置されています。図では0に初期化してあります）

f:id:matsu_chara:20171209211051p:plain

割り当てられたスレッドはincrementリクエストをleafからrootに向けて上昇していきます。(precombineフェーズ） 下図ではスレッドA,Bがincrementを開始しようとしています。

f:id:matsu_chara:20171209211124p:plain

上昇の途中で別スレッドとほぼ同時に同じnodeに到達した場合にお互いのincrement値を合算する結合処理が行われます。(combineフェーズ）

具体的には後に到達したスレッド（パッシブスレッド）は結合操作が完了するまで待機し、先に到達したスレッド（アクティブスレッド）がパッシブスレッドの分も含めてincrementリクエストを上位のnodeに伝達します。

f:id:matsu_chara:20171209211147p:plain

この上昇を繰り返し、最終的にrootまで到達した後、加算を行えばincrementは完了です。(opフェーズ）

f:id:matsu_chara:20171209211208p:plain

このように処理を分散させることで１箇所がホットスポットになったり逐次ボトルネックが発生してしまうことを回避し、並列度を稼いでいます。

ただし、これで終わりではなく返り値を返すことも考えなければなりません。incrementAndGetのようなカウンタを増やす前の値(prior)を返すインターフェースを考えると待機したスレッドに値を返す必要があります。(distributeフェーズ）

具体的にはrootまで進んだアクティスレッドは木をleaf側へ下降をしながら、パッシブスレッドにincrement完了を通知します。このとき通知される値は上位レベルから得られたpriorにアクティブスレッドの値を加算した数になります。

例としてrootがすでに３のときに、更に２つのスレッドがincrementを行ったときの例を考えてみます。

f:id:matsu_chara:20171209211228p:plain

スレッドAがrootに到達するとカウンタの値は3+2で5になります。 このときpriorは加算する前の値となるので3になります。

f:id:matsu_chara:20171209211249p:plain

ここから１段ずつ下降していき、待機しているパッシブスレッドにprior + 自分の値を通知します。

f:id:matsu_chara:20171209211315p:plain

leafまで到達したら結果を返せば終了です。 例ではスレッドAは3をそのまま返し、スレッドBはAから通知された4をそのまま返しています。

f:id:matsu_chara:20171209211339p:plain

こうすることで、処理を結合したとしてもパッシブスレッドの前にアクティブスレッドがincrementを終えたという状況が返り値に反映されます。もっとNode数が増えても、リクエストが増えても同じ処理を行えば順番に加算前の値が返されます。

もう少し詳しく

ここでは参考文献2のFigure 2,Figure 3を参照します。 詳しい実装コードはTAoMPのサイト https://booksite.elsevier.com/9780123705914/?ISBN=9780123705914 のChapter 12においても配布されています。

f:id:matsu_chara:20171209211408p:plain)

f:id:matsu_chara:20171209211424p:plain

Part One(precombineフェーズ)

Part Oneではnodeをロックしてからnodeのステータスにより分岐しています。 node.status = FREE の場合にはステータスをCOMBINEに差し替えながらgoing_upがFALSEになるまでツリーを上昇していきます。 node.status = COMBINE または　ROOT の場合、そこでそのスレッドの上昇は停止します。(ここでunlockをしないことがCOMBINEのポイントになります。)

node.status = RESULT の場合はRESULT状態が解除されるまでループします。

Part Two(combineフェーズ)

Part Twoでは、先程アクセスしたノードに再びアクセスし、first_incrに今までの値を格納します。スレッドが visited.wait_flag = TRUE の場合はtotalにsecond_incr（他のスレッドが残した値）を追加（combine）していきます。

Part Three(opフェーズ)

Part Threeでは、まずCOMBINEか否かで分岐があります。（ただしスレッドの上昇が止まるのはCOMBINEかROOTだけなのでelse説はROOTに対する処理です）

まずはわかりやすいelseから見ると、node.resultにtotalを足しています。つまり今まで結合してきたgetAndIncrementの本処理(rootの値の更新)を行っています。

次にnodeがCOMBINEだった場合を見ます。今まで足してきた分を先行スレッドに引き渡す必要があるためsecond_incrとして値を格納しCOMBINEが解除されるまで待機します。

Part Four(distributeフェーズ)

rootまでたどり着くと今度は下降しながら結果を通知していくフェーズになります。 下降しながらwait_flag = TRUEのnodeを見つけたらstatusをRESULTに変更してやり、first_incrを結果に加算します。（前述したようにこうすることでfirst_incr分の加算が先に行われたように見せることができます）

また、wait_flagがFALSEの場合は単にFREEにして初期状態に戻しています。 これを下降しながら最後まで辿りつき、各スレッドがsaved_resultを返すことによりgetAndIncrementが順番に行われたかのように値を返すことができます。

lock順が複雑なので様々なシナリオを考えてコードを追う必要があります。TAoMPの方はJavaなのでもう少し読みやすいかもしれません。

スケールするカウンター

ここまでCombiningTreeについて考えてみましたが、このCombiningTreeは確かにスループットは出ます1し、スレッド数の増加にも強いのですがlatencyという意味ではあまり性能が良いとは言えません。

例えば単にロックを使用したカウンターを考えると1回の呼び出しにかかる時間は O(1) です。 一方でCombiningTreeを使ったカウンターでは１回呼び出すのに O(log p) かかります。2,3

ただしスループットを考えてみると、ロックベースのカウンターではN回の呼び出しにかかる時間が O(N) になるの対して、 CombiningTreeを使ったカウンターでのN回の呼び出しは理想的な状況では O(log p) ですみます。4

このようにCombiningTreeでは高いスループットが出ますが、それは必ずしも低遅延を保証するものではありません。 最適なカウンターはアプリケーションによって異なるので、各方式の特性を理解して適切なカウンターを使うことが望ましいです。

まとめ

今回は並列に数をカウントするCombining Treeの紹介を行いました。 本当はカウンティングネットワークについても書こうと思ったのですが、 論文が読み終わらなかった長くて書ききれなかったので、また次の機会に。

TAoMPでは今回紹介したCombiningTreeやカウンティングネットワーク、その他諸々の面白いアルゴリズム・データ構造が載っているのでぜひ読みましょう！というTAoMPの宣伝記事でした。 冒頭で紹介した論文も俯瞰的にcountingについて書いてあって面白いのでぜひ！

参考文献

  1. ベンチマークについては http://people.csail.mit.edu/shanir/publications/HLS.pdf#page=18 の4章を見てください。（shared-memoryとmessage-passingの２つの実装で結構パフォーマンスが違うので注意）↩

  2. pは物理プロセッサの数です。↩

  3. ベンチマークを踏まえた議論は https://pdfs.semanticscholar.org/52a9/f8d07bbe6cc905aa94930e7792f12f4ebbc5.pdf を御覧ください。(こちらも同じ実装ではないので参考までに。)↩

  4. 結合が行われない絶妙なタイミングでincrementが呼ばれるようなベンチマークではこのような結果になりません。ここでの結果はすべてのincrementで結合が行われるような理想的な状況下での話です。↩

Application Crash Consistency and Performance with CCFSを読んだ

FOLIOアドベントカレンダー 9日目です。 昨日は quantroさんの バリュー投資とかグロース投資とかの整理 でした。

NewSQLを調べつつ最近はストレージ周りにも手を出してみたいバックエンドエンジニアの @matsu_chara です。

今回はFAST '17のBest PaperであるApplication Crash Consistency and Performance with CCFS を紹介します。

内容はアプリケーションレベルでのCrash Consistencyの正確性を向上させるための仕組みを持ったファイルシステム CCFS(Crash-Consistent File System)の提案です。

ざっくり

重要な情報や機能を持ったアプリケーションでは突然の電源断やカーネルのバグなどによるクラッシュに対してロバストであることが求められます。（例：DBのトランザクション）

ところがアプリケーションレベルでは、クラッシュに備えた処理に問題がある実装がよくあります。1 これらの間違った実装による影響はファイルシステムの振る舞いによっては影響を軽減したり、無くしたりすることが出来ます。2

ファイルシステムでクラッシュを考える際は、処理のatomicityとorderingが重要となります。

一貫性の観点からは、この２つが保証されていることが重要です。 このうち、atomicityについては既存のファイルシステムでも上手くサポートされています。

しかしorderingを保証しようとすると性能上のボトルネックになることがあるため、モダンなファイルシステムでは強力な保証は行わず制約を緩めていることが多いです。

例えばext4, xfs, btrfsなどではwriteの順番を並べ替えることがありますし、btrfsではディレクトリ操作の順番が入れ替わることがあります。

このような順序の入れ替えはシーク時間の削減につながるなど性能の面では有意義です。 一方でアプリケーションから見ると、書き込み順が入れ替わることにより生じる問題をケアすることが求められるため、誤った実装をしてしまいやすくなるという問題があります。

書き込み順の入れ替わりによって生じる問題の多くはテストが難しく、設定によっては正しくリカバリーされない実装のアプリケーションが多く存在します。

本論文では性能とordering保証を両立させるための鍵となるStream abstractionと、Stream abstractonを実装したファイルシステムであるCCFSが提案されています。

Stream abstractonの特長は以下のようなものです。

  • ファイルシステムレベルのorderingを少ないオーバーヘッドで提供
  • ユーザーコードの変更を最小限に抑えて利用を開始可能
  • さらにコードを変えると、さらなる性能を得られるといった柔軟性

CCFSの特長は以下です。

  • ext4をベースにStream abstractionを実装したファイルシステム
  • ext4と比べ遜色ない高性能を達成
  • アプリケーションに対し、より強力なcrash consistencyを提供

Background

前述したとおり、クラッシュを考慮する際のファイルシステムの性質を考える上ではatomicityとorderingの2つが重要となります。

一口にatomicity, orderingと言っても、「atomicityはシステムコールレベルで？セクタレベルで？」、「orderingはメタデータのみ？それとも全て？」といった議論すべき点がいくつかあります。

次のセクションでは、どのようなatomicity, orderingが適切かを検討していきます。

理想的な挙動

論文では"ordering", “weak atomicity”が達成されていれば、既存のアプリケーションの大部分が上手くリカバリーできるだろうとされています。(The Ordering Hypothesis)

この仮説は具体的には以下のようになります。

  • 全てのファイルシステムに対する更新はin-orderで行われる(ordering)
  • 書き込みはセクタ単位でatomicに、その他は全てatomicに行われる。(weak atomicity)

これらの制約はアプリケーションで考えなければいけない状態の数を制限するために存在します。

例えば Nセクタに対する更新がある場合、orderingとweak atomicityがあればクラッシュ時に取りうる状態はNです。 一方で並べ替えがある場合、クラッシュ時に取りうる状態は一気に 2N まで増加します。

実際のファイルシステムを見てみると、ext4, btrfs, xfsなどのモダンなファイルシステムでは"weak atomicity"については既に提供されています。 一方でorderingについての保証は稀です。(ext4, ext3のData-journaling modeでは提供されている） 保証が稀なのはorderingの保証を行うことによって性能が減ってしまうことに起因しています。

performance overhead

orderingを保証する場合の性能低下の原因としてFalse ordering dependenciesが挙げられます。

次節ではこのFalse ordering dependenciesについて検討していきます。

False ordering dependencies

例えば全く関係のないApplication A, Application Bが同時に動いているとします。 この時、以下のような動作が順番に起こることを想定します。

  1. Application Aで数百MB程度の大きなwriteがある
  2. Application Bで数Byte程度の小さいwriteを行った後、fsyncを行う

Application Bは通常一瞬でfsyncが終わりますが、orderingがグローバルに保証されているファイルシステムではApplication Aのwriteが終わるまで書き込みを開始することが出来ません。 そのため、結果として長い時間がかかってしまいます。

一方でApplication Bの一貫性の観点からはApplication Aの書き込みを待つ必要はありません。 たしかにApplication Aの書き込みのほうが順番としては早いですが、この２つはそもそも関係のないアプリケーションなのでそれぞれの書き込み順序の保証は本来不要のはずです。

このような不要な順序依存がFalse ordering dependenciesの正体です。 グローバルに順序を保証するファイルシステムではこのような不要な順序依存があちこちで起こってしまい性能が低下してしまいます。3

Stream abstraction

このような性能低下を防ぐために、Stream という概念を導入します。

具体的にはまず、各アプリケーションで行われる更新をいくつかのStreamに分割します。 そして、１つのStreamの中での更新は全て順序どおりに行われることを保証します。

例えば先程の例で、Application AではStream A, Application BではStream Bを使うと言った具合にStreamを分割します。 順序が保証されるのは同一Streamの中だけであるため、Stream Aが大きなデータをwriteしていても、Stream Bが順番待ちになることはありません。

このようにアプリケーション側でFalse ordering dependenciesを回避できるようにするための仕組みがStreamです。

Streamを作成するためには set_stream() を利用します。 Streamを利用するプログラムが既存のコードと異なる点は writeの前に set_stream(A) や set_stream(B) を呼び出す点だけです。 set_streamを呼び出すと、その後の更新は全て指定したStreamに含まれるようになります。4

基本的にはアプリケーション起動時に、そのアプリケーション用のStreamを作成することで不要な順序依存をある程度取り除くことが可能です。 また、Streamはアプリケーション内に複数存在しても良いので、例えばスレッドごとにStreamを割り当てたり、一つのスレッドがStreamを切り替えたりするような最適化も可能です。

この柔軟性により、「粒度の大きいStreamを用意することにして既存のコードは殆ど変えずに安全性を保証したい」といった要求や「細粒度のStreamを用意して適宜使い分けて性能を向上させたい」といった要求など、様々なケースに対応出来るようになります。

CCFS

CCFSはext4のdata-journaling modeをベースに上記のStreamの概念が取り入れられたファイルシステムです。

ext４のjournaingではメモリ上に "Running Transaction", ディスク上に"journal"を保持します。 更新はRunning Transactionに保存され、コミット時にjournalに保存されます。

CCFSではTransactionの保存領域をStreamごとに分け、コミット時にはStream単位でjournalに格納します。 このようにすることで、全ての更新の順序を保存するのではなくStreamごとに順序を保証することが可能になります。5

Evaluation

実装の試験としてext4とCCFSの比較が載っています。

まず、クラッシュ時の挙動に関する試験です。 ext4とCCFSで発見された問題は以下のようになります。

ext4では９個の問題が発見されましたが、CCFSでは2つ(Mercurialでdirstateが破損）に留められました。

ext4 CCFS
LevelDB 1 0
SQLite-Roll 0 0
Git 2 0
Mercurial 5 2
ZooKeeper 1 0

また性能面での試験も行われています。 詳細は割愛しますが性能面も同等レベルになっています。 性能比較の結果は論文Figure 6などを参照してください。

まとめ

streamごとの順序を保証することでアプリケーションを堅牢に保つCCFSを紹介しました。 本記事ではあっさりした内容になっていますが、論文ではStreamを導入したときの様々な最適化について詳細が記してあります。それらを紹介しようとするとext4で行われている最適化についても述べる必要があり、記事が長大になってしまうので割愛しました。 Block Level Journalingやdelta journaling、Pointer-less data structuresなどの面白い要素がたくさん紹介されているのでぜひ論文を読んでいただければ幸いです。

ちなみに現在FOLIOではエンジニア絶賛募集中なので興味がある人がいればぜひお声がけください。みんなで技術的な話とか出来たらなーと思いますので遊びに来るだけでもぜひお声がけください ₍₍ (ง´･_･`)ว ⁾⁾ Wantedly: Scala☓マイクロサービスで次世代証券システムを作りたいエンジニア募集

  1. 例えばファイルシステムは書き込みの順番を入れ替えることがありますがアプリケーションレベルでのfsyncによる制御などが順序の入れ替えを考慮しきれていない場合に間違った実装となります。この場合クラッシュしたタイミングによってはアプリケーションが起動しないなどの問題に発展する可能性があります。 詳細は https://www.usenix.org/node/186195 で。↩

  2. filesystemの種類・設定で決まります。最悪ケースでは60種の問題が発見されるようなテストでも、良い種類・設定では10種に収まったという結果が論文で報告されています。↩

  3. 不要な順序依存の他にも、順序入れ替えによる最適化が行えないといった問題もあります。CCFSには、これらについての工夫もたくさん取り込まれていますが今回は割愛しています。↩

  4. 後方互換性を保つためにset_streamは古いファイルシステムに対しては何もしません。そのためstreamが導入されたアプリケーションは古いファイルシステムでも正常に動作します。（もちろんその場合は順序の保証は行われません）↩

  5. 同じブロックを異なるStreamで同時に更新した場合にどうするのかみたいな話はあるのですが、その辺はがっつり省いています。気になる方は論文をお読みください。↩