Rosie Pattern Languageに入門(2)

Rosie Pattern Languageに入門(1) - だいたいよくわからないブログ

前回の続きです。

前回までだと、semverやらurlなどを取り出せて便利なツールといった印象でしたが、 その真の価値は簡単にパターンを記述できる点にあります。

パターン定義

Rosieでは正規表現ではなくPEGベースの記法でパターンを記述します。 表現力は正規表現を上回りますが、一方で基本は正規表現と同じなので、(完璧に使いこなそうとしなければ)そこまで覚えることは多くないはずです。

パターン定義の方法は公式ドキュメントにあります。 https://gitlab.com/rosie-pattern-language/rosie/blob/d861ffd5805f9988d9ad430e7f124216f11df44e/doc/rpl.md

PEGについては PEG基礎文法最速マスター - kmizuの日記 を読めば最速でPEGれるようになれそうです。

まずは major.minor で構成される劣化semverを作ってみましょう。 https://gitlab.com/rosie-pattern-language/rosie/blob/d861ffd5805f9988d9ad430e7f124216f11df44e/rpl/ver.rpl を参照して少し変えてみましょう。

package myver

-- version like semver but less feature

local alias numeric = [0] / { [1-9] [:digit:]* }

major = numeric
minor = numeric

myver = { major "." minor }

numeric = [0] / { [1-9] [:digit:]* }正規表現でいうと /0|[1-9]\d*/ になります。 0に関する分岐を入れることで 0 にはマッチするけど 012 にはマッチしないといった条件を表現しています。

{} でくくると区切り文字なしでのマッチになります。( [1-9] [:digit:]*"1 2" にマッチ。 { [1-9] [:digit:]* } は"12"にマッチ)((Rosieでは内部で入力をトークナイズしています。そのため "1 2" などにもマッチします。))

preleaseを追加して 1.2-alpha2 などに対応してみると以下のようになります。

prerelease = [[:alnum:]]+

myver = { major "." minor {"-" prerelease}? }

実行

実行時は以下のようにパターンを指定して行います。

$ cat vers
12.01
1
2.3.4
3.52
1.2-alpha2
1.3-b
1.4-

$ cat vers | rosie  -f myver.rpl match -o subs  '{myver.myver $}'
3.52
1.2-alpha2
1.3-b

12.011 , 1.4- などバージョンとしてふさわしくないものを除外できています。

パターンがファイルで管理でき、かつ個別のパターンの組み合わせで新しいパターンが構築できています。 また、aliasキーワードを付けずに宣言したパターンについては -o json の出力で前回のようにマッチした文字列のどこがmajorやminorなのかを把握することができるため、 その後の処理にも使えます。

テスト

先程のように毎回versのようなファイルを作ってtest.shのようなスクリプトを書くのはそこそこ大変です。 Rosieにはdoctestの仕組みがあるのでこれも書いてみましょう。

公式ドキュメントはここにあります。 https://gitlab.com/rosie-pattern-language/rosie/blob/d861ffd5805f9988d9ad430e7f124216f11df44e/doc/unittest.md

書き方は簡単で test pattern accepts/rejects 入力 を書いてやればOKです。

package myver

-- version like semver but less feature

local alias numeric = [0] / { [1-9] [:digit:]* }

-- test major accepts "0", "10", "99"
-- test major rejects "01", "1.2"
major = numeric
minor = numeric

-- test prerelease accepts "alpha1", "1"
-- test prerelease rejects "beta1.2", "1.2"
prerelease = [[:alnum:]]+

-- test myver accepts "3.52", "1.2-alpha2", "1.3-b"
-- test myver rejects "12.01", "1" "2.3.4", "1.4-"
-- test myver includes prerelease "1.2-alpha2"
-- test myver excludes prerelease "1.2"
myver = { major "." minor {"-" prerelease}? }

includes, excludesはmyverでマッチしたときにprereleaseが含まれているかどうか?をチェックします。

あとは以下のようにテストを実行してやればOKです。

$ rosie test myver.rpl
myver.rpl
    All 16 tests passed

パターン自体もわかりやすく、テストには具体例が列挙してある。 これで半年前の自分が書いた意味不明な正規表現から卒業できそうです。*1

今回使ったsampleはここにおいています。 https://github.com/matsu-chara/rosie-example

豆知識

find

.* のような指定があると入力をすべてconsumeしてしまうので、 { .* "something" } のように書きたくなった場合は {find:something} と書きましょう。((findはmacroで、{ !"something" . }* "something" に展開されます。 https://gitlab.com/rosie-pattern-language/rosie/blob/d861ffd5805f9988d9ad430e7f124216f11df44e/doc/i-know-regex.md))

この辺の正規表現との違いは以下のドキュメントに書いてあります。 https://gitlab.com/rosie-pattern-language/rosie/blob/d861ffd5805f9988d9ad430e7f124216f11df44e/doc/i-know-regex.md

look ahead, look behind

look ahead, look behindは以下のように書けます

## look ahead. 先頭がhttpのみを出力
curl -s https://matsu-chara.hatenablog.com | rosie grep -o subs '{ >"http:" net.url }'

## look behind. 末尾が/aboutのみを出力
curl -s https://matsu-chara.hatenablog.com | rosie grep -o subs '{ net.url <"/about" }'

look aheadではパースした位置で、"https://matsu" があるかを確かめ、成功したら(解析する文字の位置は変えずに)そのままnet.urlでのマッチを試みる。 look behindはnet.urlでのマッチに成功したら、(解析する文字の位置は変えずに)戻って "/about" にマッチするかをチェックし、成功したら全体をマッチさせる。 という意味で、正規表現よりわかりやすいんじゃないかな?と思ったりしています。(もちろんこの辺は主観ですが)

ということでRosieの紹介でした。

次回 matsu-chara.hatenablog.com

*1:とはいえ、ワンライナーで使おうとすると少し難しい時があるのでgrepの利点が失われるわけではありません。

Rosie Pattern Languageに入門(1)

Rosie Pattern Languageを触ってみたのでメモを残します。

なおversion 1.1.0の情報なので詳細・更新後の情報は Rosie Pattern Language / Rosie · GitLab を御覧ください。

Rosie Pattern Languageとは

RosieはPEG(Parsing Expression Grammars)を使ってパターンを記述することで、正規表現よりも強力に検索や置換・パースなどを行うための言語・ツール群です。

作ったパターンのテストも可能であり、ad-hocな正規表現拡張を駆使するよりも、より保守しやすく・より複雑なデータを処理することを可能にすることを目的としているようです。

使ってみる

インストール

まずはインストール

$ brew tap rosie-community/rosie https://gitlab.com/rosie-community/packages/homebrew-rosie.git
$ brew install rosie

簡単な使い方

そして、以下のコマンドを実行します。

$ curl -s https://github.com | rosie grep -o color net.url

※ わかりやすくするためにoutputオプションとしてcolorをつけたりheadで行数を絞っています

f:id:matsu_chara:20190525151423p:plain

URLだけ欲しいという場合はoutputオプションとしてsubsを指定します。*1

$ curl -s https://github.com | rosie grep -o subs net.url

f:id:matsu_chara:20190525152938p:plain

subsは grep -o に似ていますが、httpだったりhttpsだったり、urlの終端判定はどうするのか?などを考えるとなかなか面倒です。 以下のようにすると一見うまくいきそうですが・・・

$ curl -s https://github.com | grep -o 'https\?://[^"]*'
...
https://github.githubassets.com/favicon.ico
https://github.com/
https://github.com/&quot;,&quot;referrer&quot;:null,&quot;user_id&quot;:null}}
...

と地味に目的どおりに行かない場合があります。

net.url以外にも例えば

  • "6.02e23", "3.00E08", "0.123"なども拾えるfloatを含めたnumber
  • "2015-10-14T22:11:20+00:00" などrfc3339や、その他いろいろにマッチできるtimestamp
  • "1.2.3-alpha.7.8.9" など1.2.3以外をパースしようとすると意外とサクッとできないsemver

など様々なパターンが標準で組み込まれています。

使い方は例えば以下です。

$ cat vers
1.2.3-alpha2.4
12.0.5
1
2.3.4

$ cat vers | rosie grep ver.semver
1.2.3-alpha2.4
12.0.5
2.3.4

このような便利な標準パターンが組み込まれていて便利ですね!

RPL

便利ですね!・・・で終わっても十分に便利なんですが、rosieはプログラミング言語のようにパターンを記述したファイル(.rpl)を用意して、 自分の欲しいパターンを柔軟に記述できる点を特徴としています。 正規表現みたいですがrosieはPEGベースで記述できるのでより強力です。*2

semverパターンを定義しているrplファイルの中では semverは以下のように定義されています。

local alias numeric = [0] / { [1-9] [:digit:]* }

major = numeric
minor = numeric
patch = numeric 

-- prerelease,buildmetadataの定義は省略...

semver = { major "." minor "." patch {"-" prerelease}? {"+" buildmetadata}? }

このようにaliasや各パターンを個別に定義して、連結させていくことでパターンを定義しています。

キャプチャ

パターンの書き方に入る前に、rosieは入力に対してどのようにパターンをマッチさせているのか?を見るために、 semverの中でminorバージョンだけ取り出したい!といったケースを考えてみます。

正規表現ではcaptureを使いますが、rosieではマッチした情報を以下のように出力することが可能です。

$ echo "1.2.3-alpha" | rosie match -o jsonpp ver.semver
{"s": 1,
 "e": 12,
 "type": "ver.semver",
 "subs":
   [{"s": 1,
     "e": 2,
     "type": "ver.major",
     "data": "1"},
    {"s": 3,
     "e": 4,
     "type": "ver.minor",
     "data": "2"},
    {"s": 5,
     "e": 6,
     "type": "ver.patch",
     "data": "3"},
    {"s": 7,
     "e": 12,
     "type": "ver.prerelease",
     "data": "alpha"}],
 "data": "1.2.3-alpha"}

余談: ところで rosie greprosie match は行内でもマッチするか行頭からマッチするかの違いがありそうです。 例えば"xxx1.2.3-alphabbb"rosie grep ではマッチしますが、 rosie match ではマッチしません。 実装的には rosie grep patrosie match findall:pat になりそうです。(多分) https://gitlab.com/rosie-pattern-language/rosie/blob/d861ffd5805f9988d9ad430e7f124216f11df44e/src/lua/builtins.lua#L98

キャプチャの話に戻りますが、json内にあるtypeに一致したpatternの情報が入っているので、あとは適当に取り出してやれそうです。

$ cat vers
1.2.3-alpha2.4
12.0.5
1
2.3.4
xx1.2.3mmm

$ cat vers | rosie grep -o json 'ver.semver'
{"type":"*","s":1,"subs":[{"type":"ver.semver","s":1,"subs":[{"type":"ver.major","s":1,"e":2,"data":"1"},{"type":"ver.minor","s":3,"e":4,"data":"2"},{"type":"ver.patch","s":5,"e":6,"data":"3"},{"type":"ver.prerelease","s":7,"e":15,"data":"alpha2.4"}],"e":15,"data":"1.2.3-alpha2.4"}],"e":15,"data":"1.2.3-alpha2.4"}
{"type":"*","s":1,"subs":[{"type":"ver.semver","s":1,"subs":[{"type":"ver.major","s":1,"e":3,"data":"12"},{"type":"ver.minor","s":4,"e":5,"data":"0"},{"type":"ver.patch","s":6,"e":7,"data":"5"}],"e":7,"data":"12.0.5"}],"e":7,"data":"12.0.5"}
{"type":"*","s":1,"subs":[{"type":"ver.semver","s":1,"subs":[{"type":"ver.major","s":1,"e":2,"data":"2"},{"type":"ver.minor","s":3,"e":4,"data":"3"},{"type":"ver.patch","s":5,"e":6,"data":"4"}],"e":6,"data":"2.3.4"}],"e":6,"data":"2.3.4"}
{"type":"*","s":1,"subs":[{"type":"ver.semver","s":3,"subs":[{"type":"ver.major","s":3,"e":4,"data":"1"},{"type":"ver.minor","s":5,"e":6,"data":"2"},{"type":"ver.patch","s":7,"e":8,"data":"3"}],"e":8,"data":"1.2.3"}],"e":8,"data":"xx1.2.3"}

cat vers | rosie grep -o json 'ver.semver' | jq -r '.subs | map(.subs | map(select(.type=="ver.minor") | .data))[][]'
2
0
3
2

※ 先程の例では-o jsonppでしたがpretty printする必要もないので-o jsonとしています。

少しjqが複雑ですが、ここまで情報があればpatch以降を切り落とした上で、patchバージョンをincrementしたsemerを作ることも可能です。

$ cat vers | rosie grep -o json 'ver.semver' | jq -r '.subs | map(.subs | map(select(.type=="ver.major")))[][] as $major | map(.subs | map(select(.type=="ver.minor")))[][] as $minor |map(.subs | map(select(.type=="ver.patch")))[][] as $patch | $major.data + "." + $minor.data + "." + ($patch.data | tonumber | .+1 | tostring)'
1.2.4
12.0.6
2.3.5
1.2.4

language support

と、ここまでいくとjqが複雑すぎますが、なんとrosieはCやgo, haskellpythonバインディングがあるので解析結果を各種プログラミング言語で扱うことができます。

goだとこんな感じになります。 https://gitlab.com/rosie-community/clients/go/blob/18b09df4802ba6018bf816cf05a48ed777396c40/src/rtest/rtest.go#L113-121

本格的にやる場合は使えそうですね。

さらに余談: gronというツール(JSONをgrepしやすくするコマンドラインツールgronの紹介 - Qiita)を使うという手もあります。*3

node -i -e "$(cat vers | rosie grep -o json 'ver.semver'  | gron)"
> let major = json.subs[0].subs.find(s => s.type == "ver.major").data;
> let minor = json.subs[0].subs.find(s => s.type == "ver.minor").data;
> let patch = json.subs[0].subs.find(s => s.type == "ver.patch").data;
> `${major}.${minor}.${Number(patch) + 1}`;
"1.2.4"

このあと、パターン定義や実行、テストについても書きたかったんですがボリューミーになってしまったので一旦ここで区切ります。

次回は Rosie Pattern Languageに入門(2) - だいたいよくわからないブログ

*1:オプションにはsubs, data, jsonpp, byte, bool, color, json, lineが指定できます。

*2:なのでJSONのような再帰的な構造にもマッチできるわけですね https://gitlab.com/rosie-pattern-language/rosie/blob/master/rpl/json.rpl

*3:というかgoでやるかーと思ったけどgronすればいいなと思ってgoでやるのをやめたレベル

amazoncorreto, openjdkの各バージョンをdocker container上で走らせた場合のCPU数, メモリーを確認した

Java 8でも安心。Dockerに対するCPU・メモリ対応。(2018年11月現在) - Mitsuyuki.Shiiba で紹介されているように8u191以降であれば、 コンテナでJVMを動かしたときのメモリ・CPU数に関する問題は解消されているはず。

openjdkにパッチが入っていれば基本的に確認する必要はなさそうだがamazon corretoのパッチリストには載ってなかったので一応確認してみた。 (とかいいつつdockerhubにあがってる最古のjdk8のバージョンが8u192になっているので、わざわざ確認する必要はなかった気がする。)

https://github.com/matsu-chara/jvm_docker_check/blob/master/result.txt

途中から確認自体がいらなさそうな予感を激しく感じつつも今後もこういう動かし方したいことがあるかもしれないと思って適当なイメージで回せるスクリプトを用意した。(今後に期待)

1on1と信頼残高

最近思ったことを書いておく備忘録的なものです。 特に1on1経験が豊富なわけではなく、むしろ経験が浅いので、何を学びながら進めばいいのやらという段階でのものです。

1on1と困りごと

1on1に何を求めるのか?というのはベースになる考え方はありつつも、個人・チーム・組織の状況によって異なると思います。 将来のキャリアパスについての相談やポジティブなことの共有などもあると思いますが、それと同じくらい困ったことを聞くことが多いと思います。

「困ったことを聞いて、(個人が解決できるように or マネージャーが or ...)解決に導く。」これが、チームの生産性向上に寄与するというのはある程度自明に思えますし、 困ったことを話して、解決してくれるマネージャー*1は頼りがいがあり、まさに信頼できる優秀なマネージャー像にピッタリではないでしょうか。

理想と現実

一方で組織の全権を持っているわけでもないマネージャーは、全ての問題を瞬時に解決できるわけではありません。*2 合理的に見えるような解決方法を提案してもらってもなお、すぐに実行に移せないことは多いと思います。 情報の非対称性があったり、単純にリソースの問題でもあり、日々の忙しさにかまけているという場合もあります。(最後のはできるだけなくしたいけど、人間だし早く帰って熱々緑茶を飲みたいというのが人情ってものよ・・・)

開発プロセスを変えたい。差し込みやボトルネックをなんとかしたい。こういった課題には常に挑戦し続けるべきではありますが、一方で次回の1on1までに何か進んでいるのかと言われるとそうではないことのほうが多いのではないかと思います。

そもそもの話

ここまで読んだ方は以下のような疑問をお持ちかと思います。

  • 組織的な問題はともかく個人の問題をマネージャーが”解決する”ってのは違和感があるよね
  • そもそも1on1で出た課題はマネージャーが解決するんじゃなくてコーチングしたりするのが重要でしょ
  • 問題みたいなものが1on1で初めてでるのは普段のコミュニケーションや、ふりかえり(やKPT)などに問題があるのでは?

こういった話もあると思います。そしておそらくこちらの方がより本質的な目的に沿うと思いますが、今回は「僕個人の気づきを記す」ことを目的にしているためこれらの話には触れません。 それらの問題がどうでも良いと思っているわけではなく、単にそういう気付きがあったのでそこをメモしているというスタンスです。(また、結論の部分については個人の掘り下げという意味での1on1の目的にもある程度沿うよねという思いもあります。)

今回は自分の気付きを残すために、もしマネージャーがアクションをとるべき課題が1on1で初めて言われたら?という想定でお読みください。 繰り返しになりますが、これは以下のような状況を意味しません。

  • 心理的安全性が無くて、ふりかえりでは問題が全然出ない
  • 1on1は問題を教えてもらう場で、それ以外のことは全く話されないし目的ではない

想定としては以下です。

  • ふりかえりの場では思いつかなかったけど1on1で話が弾むうちにポロッとでた
  • ふりかえりでも議論してたけど、そこからまた考えが変わったりしていて、実はねといった感じでより深く教えてくれた

ということで”もし、こういうことがあったら”、”あなたはどうする?私はこうする!”形式でお読みください!

マネージャーはスーパーマンではないという話

つい最近までは、「こういった現実の中で、じゃあ理想にどれだけ近づけるのか?」が腕の見せ所だと考えていました。 (マネージャーが解決すべき課題を)10個中3個解決できたからあなたのマネージャー能力は3です。10個中7個解決できたからあなたのマネージャー能力は7です。のように。*3

一方でこうした考え方は、減点法による評価を招きがちではないかと思います。 あれはまだ解決しないのか・これはまだ解決してないのか、いつ解決するのか・・・。 「課題があって、解決できないと信頼残高が少しずつ減って、0になるとチームが崩壊。」これは避けるべきことだと思います。

では、10個課題があって10個課題を解決すれば信頼残高も減らずに済むのでしょうか? たしかにそうだと思いますが、そんな事できる人少ないですよね。 それでもなお、ミスが許されないので心理的安全性もあまりなさそうに見えます。

ちょうど、こういった議論はem.fmやその他の記事でも言及されています。 ep2. Engineering Managerをスーパーマンだと思わないで by EM . FM #EMFM • A podcast on Anchor

理想を変えよう

そもそも「Xという課題があります」に対して、自分は「そうだね、課題だと思う。解決したいな。どうすればいいだろう」と自分の中で勝手に課題認定を行い、解決策を考えはじめてしまっていました。1on1中にactionが決まればハッピーだし、安心感もありますしね。共感力!

一方で、この人は何故Xが課題だと考えたのかについては全然聞かずに勝手に補完していました。 MTGが長いという課題なら、自分の時間が取られるのが嫌なのか、空中戦になって論理的じゃない議論が嫌いなのか、チーム全体の生産性低下を危惧しているのか、興味のない事柄に巻き込まれたくないのか・・とかいろいろ考えられる要因があって、まあ全体的に正論だしそんなに大きくハズレてはいないのだろうけど、一方でその人の価値観や考え方は置き去りです。

そこで、「Xが課題だと思う」という会話に対して、何故Xが課題だと思うのか?という考えを聞くことが大切だと考えるようになりました。

そうすれば、「何を大事にしているのか・何に価値を感じるのか」に踏み込んでいくきっかけになる。そして、価値観や考え方が(部分的にでも)つかめてくれば次の課題が出たときに、「言われて初めて気づいて行動する」のではなく、よりproactiveに行動を起こすことができるようになるはずです。

これは1on1を 課題報告機課題解決機 の同期会場にしないための工夫でもあるし、課題解決の成功・失敗を含めた少しのイベントで容易に増えたり減ったりする信頼(残高)ではなく、「自分のことがある程度分かっていて、それに基づいて行動してるはずだ」という長期的に安定した信頼関係につながるのではないかと思っています。 (もちろん、何か質問を増やした程度である人の価値観が全部わかるなんて到底あり得ないので程度の問題ではあります。)

ということで、そもそもたくさん課題を解決するのがマネージャー力だ!とか、困ったことがあったらできる限り多く解決するのが1on1の理想形だ!といった考え方をそもそも変えるのは大事だなという話でした。(後半の方はなんかいい感じに気持ち良いこと書いてわかったような感じですが、そこまで達観した何かではなく、「課題ですね」に対して「そうですね」と思考停止してスタートするのでは限界があるなという考えを少しだけ掘り下げてみただけです。)

とはいえ、困ったことを聞くということ自体は1on1の役割のうちの1つでしかないですし、困ったことを聞いたとしてもマネージャーが解決するべきものもあれば、コーチング・ティーチングを通して各自に解決を促す・問題解決に向けた話相手だけになれば十分なものなどがあるため、この記事ではそのうちのほんの一部にしか焦点を当てていません。総合的にいろいろ学んでいく必要があるなと感じています。

*1:上司・リーダー・テックリードなど、1on1する人の役職が違う場合もありますね

*2:組織の全権を持ってたとしても難しいですよね

*3:解決と書いていますが、解決以外にも、今は優先度が低いと言った意思決定についての説明をきっちり行うみたいなのも含まれると思います。

Replicated State Machinesでのストレージ故障からのリカバリー

FOLIOアドベントカレンダー2018 17日目です。 昨日はyasuharu519さんのDocker stop 時に別のコマンドを実行して Graceful shutdown を実現するでした。

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

今回はFAST '18のBest PaperであるProtocol-Aware Recovery for Consensus-Based Storage を読んだので紹介や感想を書きたいと思います。 自分が面白いと思ったところを中心にしたり、個人的に調べた内容が入っていたりするので正確かつ完全な情報は上記論文や関連文献等を直接読んでいただければと思います。

ざっくり

プロトコル特有の知識を利用した分散システムにおけるストレージ障害からの回復方法(PAR=protocol-aware recovery)である、CTRL (Corruption-Tolerant RepLication)の提案です。

多くのモデルでは、 クラッシュ, ネットワーク断 を想定することが多いですが、今回はこれらの障害に加え、ストレージ故障も含めます。 ここでのストレージ故障は、何らかのストレージレイヤーでの故障によりデータ破損(数byteが読み取れないetc)・アクセス不可能(read error)などが発生するケースを指しています。

この ストレージ故障 が発生したときに、合意アルゴリズム特有の知識を利用することで データが一つ以上コピーされている場合は安全に復旧する, すべてのデータが破損している場合は(間違ったデータを返すのではなく)利用不可 といった保証を実現するのがCTRLです。 ただし、特定のconsensus algorithm(今回の場合はRSM=Replicated state machines)での知識に依存しているので全てのシステムに適用できるわけではありません。 適用範囲こそ限定されてはいますが、RSMはpaxos, raftやzab(zookeeper)など幅広く使われているので、これについてより安全性が高まるのは重要な成果と言えそうです。

モチベーション

前述しましたが、クラッシュとネットワーク断以外にもストレージ故障によってデータ破損やアクセス不可能などの障害が発生する可能性があります。 ext2,3,4などではデータ破損時に破損したデータが読み取られることがありますし、btrfsではデータ破損時にアクセス不可能になります。(どちらのfilesystemでもアクセス不可能になるような障害はありうる) またデータだけでなくinodeなどのメタデータももちろん破損することがあります。

このような状況下で、分散システムの1ノードについてデータ破損が発生した場合、あるあるなパターンではデータを完全削除して再起動(=まっさらなノードとして立てる)という方法があります。*1

さて、これで安全に復旧可能かと言われるとそうではありません。むしろこのリカバリー中にコミット済みのデータが失われることすらあります。

5台のクラスタについて下記のシナリオを考えます。

f:id:matsu_chara:20181130203110p:plain
https://www.usenix.org/system/files/conference/fast18/fast18-alagappan.pdf より

  1. データ破損が発生したノードS1のデータを削除して再起動
  2. 何らかの理由で最新commitedなデータを持ったノードS2,S3がcrash。(このときS1,S4,S5は最新データを持ってないとする)
  3. 残ったS4,S5+S1でmajorityを構成できるのでS1,S4,S5のクラスタが誕生

このときS1,S4,S5は前述の通り最新commitedなデータを持ってないので、同時にcrashしたのは2/5台なのにcommit済みデータが失われました。(= globally data loss)*2

このような問題は当然困るので、これらを防ぐための方法が必要です。 ここで、protocolに依存しない( protocol-oblivious な)方法ではなくprotocolに依存した( protocol-aware な)方法を採用しているようです。*3

今回の論文ではRSMに対応したprotocol-awareなrecovery手法(PAR)を考えます。 冒頭でRSMはpaxos, raftやzab(zookeeper)で使われていると述べましたが、これらの合意KafkaやHDFS、GFSやBigTableなど様々な分散システムを構成する際に用いられる基礎的なパーツの一つになっており、これの信頼性を上げるというのは一つの大きなチャレンジと言えそうです。

CTRL (Corruption-Tolerant RepLication)

ストレージ故障はメディアエラー以外にもファームウェアデバイスドライバー・ファイルシステムのバグなどいろいろな事象から発生します。 今回の故障モデルでは通常のエラーに加えストレージ故障として2つのエラー(block errors, corruption)を追加します。

すでに知られている対処方法

No Detection

checksumを見ない方法。間違ったデータをクライアントに返すことがある。(多くのシステムでは基本的にはchecksum見ている。がLogCabinはsnapshotを読み取るときにchecksumを見ていないらしい)

Crash

checksum等を見ておかしかったら、そのノードをクラッシュさせる。(LogCabin, Zookeeper, etcd, ...etc。例えばzookeeperはsnapshotが壊れていた場合はcrashする。LogCabinはsnapshotではチェックしていないがlog entryではチェックしているらしい) 間違ったデータを返すことはないがどこか一箇所でも壊れていることを検知したらcrashするのでクラスター全体がunavailableになるリスクが増している。 ディスク故障の場合、crashしたあとそのまま再起動しても治らないケースもあるのでマニュアルで治すまで障害が続くのも特徴。

Truncate

壊れていたデータの後続を捨てる。(RSMなので後続ログを捨てるイメージ)

自動で復旧してくれそうに見えて、comittedなデータを失うことがある。 truncateしたノードとlagがある複数台のノードでmajorityを構成できるようなケースではtruncate後のログが正になりうる。その場合一度commitしたはずのデータが(特にエラーなどを出さずに)上書きされる。*4

また、ログの先頭の方でストレージ故障が発生した場合、多くのデータをリーダーから貰う必要がありネットワーク帯域を消費したり、リカバリー時間の増加につながるといった問題がある。

safetyとfast recoveryに問題があるTruncateですが、一方でavailabilityは高いですしマニュアル作業などは不要。

DeleteRebuild

Truncateだが、異常を発見したら完全にまっさらにしてnodeを立て直す方法。*5 メリット・デメリットは基本的にTruncateと同じ。

MarkNonVoting

GoogleのPaxosベースのシステムで使われているらしい。*6

レプリケーションが追いつくまでvotingの権限を奪うことでTruncateで起きたようなsafety violationを回避することができます。 が、それでも安全でない場合がある様子。*7

またストレージ故障時にvoteできなくなるので可用性にも問題が出る可能性がある。

Reconfigure

壊れたノードを取り除いて新しいノードをjoinさせる方法。 新しいnodeをjoinさせるためにはマジョリティのコミットが必要なので、可用性に問題が出るケースがある。

BFT

究極的にはByzantine障害耐性のあるアルゴリズムを使えばストレージ故障があっても一貫性のある値をクライアントに返すことができる。 が、コストが高い(スループットが半分になる可能性もある)。また故障数fに対して3f+1ノードが必要なのもネック。

CTRL

CTRLが利用するRSM特有の知識

  • leader base: すべての更新はまずリーダーが受け取る
  • epoch: 1epochにつきリーダーは一人。ログは<epoch, index>の組でユニークに特定できる。(indexはログエントリーに振られる番号)
  • leader completeness: leaderはすべてのcommitedなログを持っている。

CTRLではlocal storage layerdistributed recovery protocol の2つがセットになって復旧を行う。 具体的にはstorage layerがストレージ故障を検出し、distributed recovery protocolが冗長化されたデータから復元する役割分担になっている。

CTRLが保証すること

  • コミット済みの正しいデータが最低一つあれば、それを使って修復を行う
  • コミット済みのデータは消失しない。
  • すべてのコピーが故障した場合、unavailable状態になる(暗黙に上書きなどを行わない)
  • さらなる保証:uncommittedなデータの故障についても可能な限り早期に決定を行う(可用性向上)

ストレージはログ・スナップショット・メタデータの3つを永続化する。

  • ログはRSMのエントリー単位で故障を検知する(protocol aware)
  • snapshotは大きくなるのでチャンク単位で故障を検知する
  • メタデータはノード固有の情報を持つので他ノードからのリカバリーは不可能である。そのためローカルに2つのコピーを持って復旧を行う。

storage faultの検知はreadのreturn codeとchecksumで行う。メタデータのエラーもopen時のエラーハンドリングで検知可能。*8

大抵のケースで、メタデータfault時はcrashさせる。 これはsafetyには影響しないがunavaiableになる時間が増える。 ただデータブロックのほうがメタデータブロックに比べて圧倒的に多いので、相対的には許容可能な停止時間になるだろうとの見込み。

CTRLで行われる故障の分離

単にchecksumミスマッチを起こした場合でも下の2つの場合を分離可能

  • 更新途中でノードがクラッシュした場合(crashed)
  • 古いログが壊れた場合(corrupted)

前者の場合はackを返してないはずなので安全にログをdiscardできる。 コミットされているかどうかはpersist record p_i をevent entry e_iの後のタイミングで書きこむことで確認できるようになる。

通常は write(ei), fsync(),write(pi), fsync() のようにするが、厳密な判断をしたいわけでなくcrashのケースを拾いたいだけなので、パフォーマンスのネックになるfsyncを除いてwrite(ei),write(pi),fsync() としている。

e_i, p_iの順序が入れ替わるかもしれないことに注意。(今回のケースでは大丈夫ですが、fsyncを入れないと、どうなるか?といった議論はちょうど去年のアドベントカレンダーに書いた内容で議論されているのでぜひ https://matsu-chara.hatenablog.com/entry/2017/12/09/110000 という脱線)

つまり、persist recordが存在しなければcrashであることがわかる。存在する場合にeが最後のイベントだと判定が行えなくなるがその場合はcorruptと判定して他ノードからリカバリーする。*9 *10

なおsnapshot等はtemporary fileに書いたあとatomicにrenameを行うことで破損を避けています。

CTRLで行われる故障箇所のidentify

故障したデータが何だったのか?という特定(identify)を行う必要があるため、identifierを別途保存してどのログやデータが壊れたか分かるようにしている(ついでにpersist recordも兼ねる)。内容としては <epoch, index> のペアがあればログエントリーを一意に特定できる。 identifierは物理的にデータとは別の場所に保存されるため、基本的に同時に壊れる可能性は低い。もし同時に壊れていた場合はnodeをcrashさせる。(unavailableにはなるが、頻度が低いため許容可能)

CTRLでの具体的なリカバリー方法

ナイーブな方法としてLeader Restriction. リーダーになる際にfaultyでないことを保証する方法がある。 リーダーがすべてのイベントを持っているので、フォロワーのストレージ故障時は基本的にはリーダーからコピーすればOK。 ログを問い合わせ(<epoch, index>でユニーク)て、リーダーが知らない場合は正式にcommitされたものではないのでdiscardする。

ただし、この方法だとリーダーになる前にすべてを保証しないといけなくてunavailableになる可能性が高くなる。 一つでも無事なコピーが存在していればクラスタ全体は継続して利用可能にしたい。 そのため以下のようにクラスターから情報を収集して判断を行う。

リーダーが正常で、フォロワーが故障している場合

修正は容易。

  • リーダーからコピーする
  • リーダーが知らない場合は、uncomittedなものなのでdiscardする
リーダーが故障している場合

リーダーはフォロワーに<epoch, index>を問い合わせる。レスポンスは以下の3種が考えられる

  1. (have) フォロワーが壊れていないログを持っている
  2. (dontHave) フォロワーがログを持っていない
  3. (haveFaulty)フォロワーはログを持っているが、壊れている。

リーダーはこれらのレスポンスを集めて以下の判断をする

  1. 一つ以上のフォロワーから壊れていないログが帰ってきた(have)場合はログを修復する。
  2. フォロワーの過半数がログを持っていない場合(dontHave)、未コミットなので該当イベントとその後続を捨てる
  3. haveFaultyが帰ってきた場合は1, 2のどちらかになるのを待つ*11

Snapshotリカバリ

ログ同様snapshotも壊れる可能性がある。ZooKeeperとLogCabinはどちらもsnapshotが壊れていた場合に正しくハンドルできないケースがある(らしい)。 スナップショットは本質的にコミット済みの物のみを含むのでdiscardできない点がログと異なる。

また各ノードが独立してsnapshotを取るので、uniqueなidentifierで取得といったことができない(そのidで必ずsnapshotを取るわけではないので)し、その場合chunk単位で持ってくるのも難しいのがハードル。まるっとsnapshotを送ると帯域を消費するため避けたい。

これを解決するためにリーダーがsnapshotを取るindexについて合意を取ることで同一のsnapshotを生成する。 過半数がsnasphotを取り終えたらGC markerを挿入して再び合意を取りつつログをGCする。

リカバリー時は以下のように判断する。

  • ローカルログがGCされずに残っている場合はそこから復旧
  • GCされている場合は、他ノードでsnapshotがあることが保証されているので、そこからコピー
  • フォロワーがリーダーの知らないindexを問い合わせた場合(フォロワーが古いindexを送る場合など)は、リーダーが最新のsnapshot全体を送ります。*12

まとめ

今回の論文では以下のようなテクニックが使われていました。

  • a crash/corruption disentanglement
  • a global-commitment determination
  • leader-initiated snapshotting

この後、実装についてとパフォーマンス評価が続いていますが今回は割愛したいと思います。興味が出たらぜひ読んでみてください! Pythonベースのモデル検査やTLA+ specification of RaftにCTRLのログリカバリーを追加して検査もしているようです。*13

related worksにはいくつかのstorage fault対策をほどこした研究が挙げられています。基本的には故障台数の上限を決めて動かしているようです。(わりと自然な仮定なような気もします)CTRLは一つでもコピーが残っていればなんとか復旧してくれるのでそういう実用面では優位性がありそうです。 一方でPASCはメモリエラーにも対応できるようです。(CTRLでstorage faultに耐え、PASCでメモリーエラーに耐えるなどの併用による強化も可能らしいです。)

感想

FASTは普段はあまり読まないんですが、たまに読むと課題設定からして勉強になることが多いのでFileSystemマイスター以外の方にもおすすめです。

zookeeperがお手軽にinconsistentにされることが多い気がするんですが・・不憫。(それだけ使われているということでもあります)

分散システムのみならずアプリケーションの整合性を考えるという意味ではファイルシステムの整合性は切っても切り離せません。 うまく動くでしょ、と思っていたらファイルが破損して・・みたいなことは実運用にでかいシステムを乗せると 稀によくある ことだと思うので、 本番で論文に出てくるようなものを直近で使う予定がなくても、ここでおかしなことになるといった知見や、それに対する解決方法などから得た新しい概念はどこかで活かせるのではないかと思います₍₍ (ง´・_・`)ว ⁾⁾

*1:本番で愚直にやるとレプリケーション負荷で死ぬシステムもあるのでご利用は計画的になやつ

*2:リカバリして最新に追いつくまでhealthyなnodeとしてカウントしなければ、そもそも前提エラーになるような気もしなくもない?と思った人!(僕がそうなんですが・・)この後その方式が出てくるのでご期待ください

*3:protocol-obliviousだと何故だめなのかに関する議論はあまりなかったように読めました。要勉強。

*4:この辺は前述したまっさらにして再起動パターンで起こる現象と同じですね。

*5:検証中とかによくわかんなくなったらとりあえずこれやりますよね

*6:引用されてる文献はリアルワールドPaxosノウハウ集で有名なやつ(?)ですね https://www.cs.utexas.edu/users/lorenzo/corsi/cs380d/papers/paper2-1.pdf

*7:リーダー入れ替え後に古いリーダーからのエントリーを受け入れてしまうようです。詳しくは文献70を参照

*8:メタデータ破損時はそもそもファイルが開けなくなるという想定

*9:crashedにするのはあくまでも最適化なので、crashedなものをcorrupt判定してしまっても保証にとっては影響がないということですね。

*10:pもcorruptedになるのでは?と思うが、pもchecksumにより検査されるのと、p自体は小さいのでatomicに書かれるためcrashによってはcorruptedにならないだろうとのこと。なおeとpが同時にcorruptedになった場合は後者と判断し、慎重にリカバリーを行う。

*11:過半数がhaveFaultyで、残りがdontHaveを返してきた場合と、全体がhaveFaultyを返してきた場合について記載がないように思える(見落としかも)ものの、corruptedであるというエラーを返すのが目的だったと思うのでそのようにするのかなと思っています。

*12:すべてのノード上でsnasphotが壊れていた場合のケースがなさそうでしたが、その場合はもはやどうしようもなさそうですね・・。

*13:そこも気になったんですがさらっと書いてあるだけでした。