ScaleCheck: A Single-Machine Approach for Discovering Scalability Bugs in Large Distributed Systemsを読んだ

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時代に発生するようになった新世代のバグであると呼んでいます。

実際に巨大なクラスタで発生するバグとしては以下のような実例が挙げられています。

https://www.usenix.org/sites/default/files/conference/protected-files/fast19_slides_stuardo.pdf#page=3 より

これを見るとたしかに100, 1000ノード単位で顕在化するバグが存在するようです。

例えばcassandraの内部処理でノード数依存でO(N³)の処理があり、計算に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台のマシンでテストを行えるようにしたいところです。 しかし実際にそれを行うためには下記のような様々な困難を解決する必要があります。

https://www.usenix.org/sites/default/files/conference/protected-files/fast19_slides_stuardo.pdf#page=11 より

STestでは上記をSPC+GEDA+PILというテクニックで解決し、１台での大規模テストを行えるようにしています。 詳しく説明すると長くなりすぎるため下記では要素のみの紹介とし、具体的な解説は論文に譲りますので興味がある方はそちらを御覧ください。

ナイーブに１台に複数プロセスを立てるのだと50ノード程度しか立たないため今回の目的には向かないようです。 そこでSingle Process Cluster（SPC）として１プロセスに複数ノードを立てる（つまりスレッドでノードを管理する）手法が導入されています。

しかし単純なSPCを行うと、イベントキューやワーカープールがノードごとに作られるためリソースを多大に消費します。（120ノード程度とのこと）

これらを節約するためにGlobal Event Driven Architecture(GEDA)を導入します。 GEDAはグローバルなイベントハンドラを用意し、ノードごとの通信をグローバルイベントキューへのキューイングとして表現します。 また各ノードはグローバルなキューからイベントを取得し処理を行うだけです。

https://www.usenix.org/sites/default/files/conference/protected-files/fast19_slides_stuardo.pdf#page=24 より

上記だけでも大規模テストができるとのことですが、 これだけだと特にCPU-intensiveなタスクの際に結果が正確でないケースがあるため、CPU intensiveな計算をsleepに置き換えるProcessing Illusion(PIL)というテクニックを導入しています。

PILは画像を見ると何をしたいかがわかりやすいと思います。

https://www.usenix.org/sites/default/files/conference/protected-files/fast19_slides_stuardo.pdf#page=28 より

検証

実際にいくつかのミドルウェアで検証を行い、既知のバグや新しいバグを検知しているようです。

新種のバグとしては以下の物が挙げられています。

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 より

作ってそこそこ便利だったボットとかまとめ

FOLIO Advent Calendar 2019 - Qiita 10日目代打です。

9日目はlotzさんの 挿入ソートと選択ソートは双対 - Qiitaでした。 recursion schemesの応用って融合変換くらいしか知らなかったんですが身近なアルゴリズムの性質を表現できるのは面白いですね。 自分で学ぶことで見通しよく効率化のアイディアを出せたりad-hocに見えていたアルゴリズムに横のつながりが見えてきて理解が深まりそうです。

最近ブログ書かなさすぎて書き方を忘れていた まっちゃら (@matsu_chara) | Twitterです(´･_･`)

今回は今まで作ってきたボットや社内用サービスをまとめようと思います。 やや内輪ネタっぽいですが、こういうのあると便利かもしれないというアイデアのきっかけになればと思います。 似たようなのあるけどうちはもっと便利だぜ！っていうのあったらぜひ教えて下さい。

社内ブックマーク gol

新しく入社したメンバーに、consulのurlはこれで、prometheusはこれで、ああサービス画面はこっちで。 と教えることはよくあると思いますが、それぞれのリンクを覚えるのは結構大変だったりします。

ドキュメント管理ツールにブックマーク集みたいなページを追加しても慣れてる人は使わないからメンテされない。なんてこともよく起こります。

golはそれらの問題を解決するブックマーク共有＆検索サービスです。
まあ実際はただの管理画面付きkvsなんですが、結構便利だったりします。

例えば画像のように、consulと検索するだけで各環境のconsulがすぐに出てきたり

chrome拡張（これは同僚が作ってくれました！）を使うとgolのページに行かなくてもcommand + gとかでさっと検索できます。

検索キーワードをかなり雑に指定してもヒットするようになっていて、 space区切りで適当に「cons stg」と入れれば「consul_stg」だろうが「stg-consul」だろうがヒットしてくれるのが割と気に入っています。 こういう規約とか覚えるの面倒ですしね。

ちなみにgoを書き始めて初めて作ったものなので実装はあれな感じになっています。 許して

slack_user_avatar_emojis

GitHub - matsu-chara/slack_user_avatar_emojis: register slack user avatars to emoji

slackの全ユーザーのiconを取得して、slackのemojiとして登録するものです。 本文に含めてもいいですし、emoji reactionにしても良しで社内の文化作り的にも良いです。 emojiだと名字よりもちょっとほんわかしますしね。

アイコン変更イベントを取ってきて自動で更新し続けてくれるデーモンにしようと思って100年くらいたってるので誰かお願いします(他力本願)

というかこのemoji、公式で実装されて欲しいですね。

ちなみにトークン設定とかが結構必要なので動かすのは結構ダルめです(´･_･`)

reacjira

emoji reactionをつけると特定のチャンネルに通知してくれるreacji-channelerにインスパイアされた、 emoji reactionをつけると特定のjira projectにチケットを切ってくれるボットです。

reaction + jira で reacjiraってわけですね。

アイコンはいらすとやで見つけたかわいいクジラです。（ダジャレ・・・）

↓の感じで、 :○○_story: みたいなemojiをつけてやるとチケットが作成されスレッドとして投稿されます。

この際、チケットの中身として↓の画像のようにdescription欄にslackのスレッドのリンクがデフォルトで記載されます。

reacjiraを使うと依頼を受けた際にすぐチケットを作成できて以下のようなメリットが生まれます。

• 頼んだ人: どのチケットを見れば進捗が分かるのか分かりやすい
• 頼まれた人: 詳細を書くのを忘れてしまっても、slackリンクがあるのでどういう文脈で作られたチケットなのか最悪分かる*1

一説によるとzappierとかでできるらしいという話があったりなかったりするんですが、 自作botだとjiraのあらゆるフィールドをいじったり、結構強引なルールを設定したりできるので便利です。

ちなみにjiraの公式integrationとかが進化してくると要らなくなる存在になりそうです(´･_･`) *2

jobdiff

これはかなり社内限定で便利なやつで、jenkins-job-dsl*3のjenkins反映済みcommit ~ 最新masterまでのcompareリンクを生成してくれるというただそれだけのものです。*4

正直bot化するものでもないんですが、jenkins見る => compareリンク作るみたいなのは手間だったので一発で生成してくれるようにしました。

jenkins叩くコードがすでに手元にあったので5秒くらいで完成したし、botデプロイ環境+token登録環境が割と整備されてるので思いついてサクッと作ってすぐデプロイみたいなことがしやすいんでこういう、微妙〜〜〜に不便ってのも解決できていいですね。（環境整備してくれているチームに感謝）

ところでjenkins-job-dslのリポジトリが大きくなりすぎて、job-seedに時間がかかりすぎたりいろいろな問題があるので 脱jenkinsも含めて最高のジョブ基盤を作ろうとしています。

それができたらjobdiff君は消え去ることになります。（宿命）

consul bot

これも社内限定で便利なやつで、サービスディスカバリとして利用しているconsulから情報をとってきて、各環境の各サービスのバージョンを一覧として取ってきたり、ip+portを取ってきたりするやつです。

version stg,prod ac のように書くと「stg,prod環境」にある 「acから始まるサービス」のバージョン情報を取得します。*5

サービス名は省略してもいいしフルネームでも大丈夫です。

デプロイしたあとにちゃんと切り替わってるよね？といった確認に使ったり、トラブルシュートする際に参照したりしています。

consulは今の所困っていないんですがServicMeshとか入ってきた時にうちのconsulが生き残るかは不明です。頑張って(´･_･`)

まとめ

作ったけどボツになったやつとかも結構ある（公式機能で対応されてボツとか、使いにくかったりとか）んですが、 社内でも使ってもらえてるのを見るとちょっと嬉しいです。（新しく入ってきた方が早速使ってたりすると特に）

これからも地味だけどあるのが当たり前みたいな便利さを目指して頑張っていきます。

*1:もちろん書いたほうがいいんですが

*2:っていうか元から要らない感はあるんですがreacjiraっていう名前思いついたら作るしかなくない？？？

*3:groovyでjenkins jobを定義できるやつ。jenkins Pipelineとは異なるもの。

*4:なんでそんなものが必要なのか？みたいな背景書いたけど、社内でしか伝わらなさそうなので消しました。

*5:バージョンはconsulにregisterにするときにgit tagをconsul Noteに入れることで取得できるようにしています。

PFDS(純粋関数型データ構造)を読んだ

手を動かしたい気分だったのでだいぶ後回しになっていたPFDS (Purely Functional Data Structure, 純粋関数型データ構造)を読みながらScalaで実装を後追いしてみた。*1

少し時間がかかったがRedBlackTreeやTrieといった有名な物から、HoodMelvilleQueueやそれを利用したCatenableListなどちょっとおしゃれ（？）なデータ構造についての実装・計算量についての考え方を学ぶことができた。

本の前半はストーリーがあって、「永続的なデータ構造だと計算効率が悪い場合が多い！・・・が！償却計算量の考え方を使いながら実装を工夫していくと短命なデータ構造と同じくらいの性能が出る。（全てではないが償却だけでなく最悪計算量についても同じくらいにできるケースも多い）」ことを確認する旅になる。 軽くまとめてみたので興味がある人はちら見しつつ、実際に本を購入して読んでみてほしい。 https://gist.github.com/matsu-chara/75dd80e36172569343738153d0123bf2

後半は様々なデータ構造を設計するための考え方がまとまっている。 こちらについても雑多になっているわけではなく、前半の考え方（実装方法・計算量の証明方法）を踏襲しつつ、一個ずつ積み重ねになっているので読み応えがある。

2進数のゼロ無し表現というものが途中に出てくる。 これは以下のように普通の２進数では {0,1}で書くところを {1,2}を使って書く記法のことだ。

1,2,3,4,5 は 1, 2, 11, 21, 12, 22, 111 となる。

- 各桁が2^iを表すのは普通の2進数と同じ。
- 0を使わないのが前提になるので、ある数を表す表現は一位に定まる

一見特に意味のない記法に思えるが、これが記数法表現に基づくデータ構造の計算量の削減に役立つというのはなかなか面白かった。 気になる人は https://gist.github.com/matsu-chara/03fef6b59f60fefd5d052704cd578ac7 に概要をまとめたので読んでみて興味があれば本を買ってみてほしい。（ちなみにgistの内容の正確性については保証できない）

2-3 finger tree

2-3 finger treeといえばHaskellのData.Sequenceにも使われている（償却）計算量の優れたDequeだ。（追加・削除ともに償却定数時間で実行可能）

これはPFDSには載っていないが、ベースとなる 記数法表現 や 暗黙再帰減速 の考え方・実装の勘所はPFDSで学ぶ事ができる。*2

読み終わったあとにwikipediaを開いてみたら、以前なんとなく理解していた物よりはるかに解像度高く理解できたので勢い余って実装してみた。*3

https://github.com/matsu-chara/finger_scala

とはいえ、finger treeの実装は世界に一億個くらいありそうなので特に自慢にもならないし、パフォーマンスやメソッドの豊富さよりはわかりやすさを重視している。(が、やはりこういうのは自分で実装してみると理解度が違うと思う。）

ちなみに実用的なFingerTreeに関してはscalazの物などがおすすめ

wikipediaにあるシナリオ 通りのテストを書いてみたがいい感じな見た目になったので記念スクショを貼って終わりとする

テスト

next

本を読むなかでscalaでの実装をいくつかあたっていたところ以下のように、いくつかの実装には論文へのリンクがついていた。

読む予定があるわけじゃないけどscala collectionのコメントにある論文を集めてみた
ConcurrentTrie https://t.co/OYzQCB4Tjw
HashMap https://t.co/5ppRtytUFP
IntMap https://t.co/4gHFDLyHH4
RedBlackhttps://t.co/p5eEjsp9xD
RedBlack https://t.co/qWa2cqPtkQ
RedBlack https://t.co/FFIBO49Ay1

— まっちゃら (@matsu_chara) 2019年7月14日

PFDSでカバーされている物もややありそうだけど面白そうなのでいつか読みたい。（けどパタヘネ読み始めた）

*1:ちなみに実装するときはcats.Evalを使うと便利 https://typelevel.org/cats/datatypes/eval.html

*2:このデータ構造の実装自体は多少腕力があればwikipediaを見れば実装できそうだが、一方でなんでDigitといった名前が出てくるのか、このようなデータ構造での計算量の考え方はある程度背景知識がないと理解が難しい気がする。（個人の感想です）

*3:ちなみにwikipediaは英語版より日本語版のほうが図が多くて実装しやすかった

Rosie Pattern Languageに入門（３）

正直第2回で終わる予定だったんですが Rosie Pattern Languageに入門（２） - だいたいよくわからないブログ の続きです。

前回サンプルファイルのsemverをパースしてみたりしたと思うんですが、そんなにしっくり行く例でもないなと感じていたり、 かといってがっつりパースしたくなるログも特にないなーと思っていたりしました。

ところが、さっき何気なく自宅macで brew upgrade コマンドでいろいろなライブラリをがっつりアプデしていたところ ちょうどよい感じのログが出ていました。*1

==> Upgrading 100 outdated packages:
llvm@6 6.0.1 -> 6.0.1_1, ocaml 4.07.0_1 -> 4.07.1, git-lfs 2.5.2 -> 2.7.2, pyenv 1.2.8 -> 1.2.11, tig 2.4.1 -> 2.4.1_1, plantuml 1.2018.12 -> 1.2019.6, tree 1.7.0 -> 1.8.0, terraform 0.11.10 -> 0.12.1, php@7.1 7.1.23 -> 7.1.30, coreutils 8.30 -> 8.31, cppcheck 1.85 -> 1.87, wget 1.19.5 -> 1.20.3_1, ocaml-num 1.1_3 -> 1.1_4, mycli 1.16.0 -> 1.19.0, python@2 2.7.15_1 -> 2.7.16, go 1.11.2 -> 1.12.5, docker-machine 0.15.0 -> 0.16.1, ponyc 0.25.0 -> 0.28.1, gnu-getopt 1.1.6 -> 2.33.2, cmake 3.12.3 -> 3.14.5, opus 1.3 -> 1.3.1, freetype 2.9.1 -> 2.10.0, python 3.7.0 -> 3.7.3, elixir 1.7.4 -> 1.8.2, redis 5.0.0 -> 5.0.5, highlight 3.47 -> 3.52, boost 1.67.0_1 -> 1.69.0_2, cscope 15.8b -> 15.9, libyaml 0.2.1 -> 0.2.2, docker-completion 18.06.1 -> 18.09.6, jemalloc 5.1.0 -> 5.2.0, maven 3.5.4 -> 3.6.1, jo 1.1 -> 1.2, wata727/tflint/tflint 0.7.2 -> 0.8.2, shared-mime-info 1.10 -> 1.12, unzip 6.0_3 -> 6.0_4, zeromq 4.2.5 -> 4.3.1_1, composer 1.7.3 -> 1.8.5, perl 5.28.0 -> 5.30.0, nkf 2.1.4 -> 2.1.5, rust 1.30.0 -> 1.35.0, zsh-completions 0.29.0 -> 0.30.0, readline 7.0.5 -> 8.0.0_1, erlang 21.1.1 -> 22.0.2, llvm 7.0.0 -> 8.0.0_1, awscli 1.16.40 -> 1.16.170, teleport 3.0.0 -> 3.2.6, binutils 2.31.1_1 -> 2.32, gcc 8.2.0 -> 9.1.0, crystal 0.26.1_1 -> 0.29.0, webp 1.0.0 -> 1.0.2, ruby-build 20181019 -> 20190423, sqlite 3.25.2 -> 3.28.0, gobject-introspection 1.58.0 -> 1.60.1, eigen 3.3.5 -> 3.3.7, yarn 1.12.1 -> 1.16.0, numpy 1.15.3 -> 1.16.4, grep 3.1 -> 3.3, emacs 26.1_1 -> 26.2, docker-compose-completion 1.23.0 -> 1.24.0, moreutils 0.62 -> 0.63, thrift 0.11.0 -> 0.12.0, gradle 4.10.2 -> 5.4.1, llvm@3.9 3.9.1_1 -> 3.9.1_2, ansible 2.7.1 -> 2.8.1, llvm@5 5.0.2 -> 5.0.2_1, leiningen 2.8.1 -> 2.9.1, openblas 0.3.3 -> 0.3.6_1, curl 7.62.0 -> 7.65.1, ghc 8.4.4 -> 8.6.5, opencv 3.4.3 -> 4.1.0_2, gnu-sed 4.5 -> 4.7, consul 1.3.0 -> 1.5.1, llvm@4 4.0.1 -> 4.0.1_1, ghq 0.8.0 -> 0.12.6, source-highlight 3.1.8_9 -> 3.1.8_11, nginx 1.15.5 -> 1.17.0, gawk 4.2.1 -> 5.0.0, hadolint 1.15.0 -> 1.16.3, haskell-stack 1.7.1 -> 1.9.3, mercurial 4.8 -> 5.0.1, shellcheck 0.5.0 -> 0.6.0_1, clisp 2.49_1 -> 2.49_2, oniguruma 6.9.0 -> 6.9.2, httpie 0.9.9_4 -> 1.0.2, groovy 2.5.3 -> 2.5.7, node 11.0.0 -> 12.4.0, zsh 5.6.2_1 -> 5.7.1, neovim 0.3.1 -> 0.3.7, ripgrep 0.10.0 -> 11.0.1, coq 8.8.2 -> 8.9.1, fish 2.7.1 -> 3.0.2, hub 2.6.0 -> 2.11.2, bison 3.2 -> 3.4.1, protobuf 3.6.1 -> 3.7.1, rbenv 1.1.1 -> 1.1.2, git 2.19.1 -> 2.22.0, ctop 0.7.1 -> 0.7.2, ethereum/ethereum/ethereum 1.8.17 -> 1.8.27, gnutls 3.5.19 -> 3.6.8, diff-so-fancy 1.2.0 -> 1.2.5, libvterm 681 -> 726, packer 1.3.2 -> 1.4.1, flyway 5.2.1 -> 5.2.4, pony-stable 0.1.6 -> 0.2.0

一行で出るとちょっと読みづらい感じとか前後のバージョンを取り出すのとか難しそうな感じが、マシンリーダブルではないけどちょっと頑張るとマシンリーダブルになりそうないい塩梅のログになっていそうです。

普段なら以下のように改行を突っ込んでヒューマンリーダブルにするところで終わりにしちゃうんですが、今回はパースしてマシンリーダブルにしたいと思います。

$ cat brewout | gsed 's/, /\n/g'
cat brewout | gsed 's/, /\n/g' | head
llvm@6 6.0.1 -> 6.0.1_1
ocaml 4.07.0_1 -> 4.07.1
git-lfs 2.5.2 -> 2.7.2
pyenv 1.2.8 -> 1.2.11
tig 2.4.1 -> 2.4.1_1
plantuml 1.2018.12 -> 1.2019.6
tree 1.7.0 -> 1.8.0
terraform 0.11.10 -> 0.12.1
php@7.1 7.1.23 -> 7.1.30
coreutils 8.30 -> 8.31

といっても簡単なもんで以下のようにするだけです。

package brew

-- test package accepts "llvm@6", "ocaml", "php@7.1"
package = [[:alnum:] [@.] ]+

local alias brewver = { [:digit:]+ "." [:digit:]+ "." [:digit:]+ [^ [:space:] [,] ]* }

-- test before accepts "6.0.1", "23.0.1_1", "4.07.0_1", "7.1.30"
-- test after accepts "6.0.1", "23.0.1_1", "4.07.0_1", "7.1.30"
before = brewver
after = brewver

-- test brew accepts "llvm@6 6.0.1 -> 6.0.1_1", "ocaml 4.07.0_1 -> 4.07.1,", "php@7.1 7.1.23 -> 7.1.30,"
-- test brew rejects "12.01 -> 2.3.4",
brew = package before "->" after ","?

brewに登録されるパッケージのバージョンは厳密なsemverとは異なり07や0_1のような文字列が利用されるので標準のver.semverは使わず空気を読んでパースしています。（brew公式docとか見てないので今回のでパースできない例はいっぱいありそう）

llvm@6 や php@7.1, 23.0.1_1 など 怪しい部分は都度テストに突っ込むとデグレチェックにもなるので便利です。（実際php@6.1をパースしようとして [@.] とすべきところを [@ .] としてしまいスペースもpackageに飲み込まれるというデグレが起きるのを検知しました。）*2

テストは以下のように行います。

$ rosie test brew.rpl
brew.rpl
    All 15 tests passed

肝心のパースは以下のようにできます

 $ cat brewout | rosie  -f brew.rpl match -o jsonpp 'findall:brew.brew'
{"type": "*",
 "subs":
   [{"type": "brew",
     "subs":
       [{"type": "package",
         "s": 1,
         "data": "llvm@6",
         "e": 7},
        {"type": "before",
         "s": 8,
         "data": "6.0.1",
         "e": 13},
        {"type": "after",
         "s": 17,
         "data": "6.0.1_1",
         "e": 24}],
     "s": 1,
     "data": "llvm@6 6.0.1 -> 6.0.1_1,",
     "e": 25},
    {"type": "brew",
     "subs":
       [{"type": "package",
         "s": 26,
         "data": "ocaml",
         "e": 31},
        {"type": "before",
         "s": 32,
         "data": "4.07.0_1",
         "e": 40},
        {"type": "after",
         "s": 44,
         "data": "4.07.1",
         "e": 50}],
     "s": 26,
     "data": "ocaml 4.07.0_1 -> 4.07.1,",
     "e": 51},
...(snip)
}

ASTがあるのでpackageだけ取り出すやらなんやらは自由にできます。

$ cat brewout | rosie  -f brew.rpl match -o json 'findall:brew.brew' | jq -r '.subs | map(.subs) | flatten | map(select(.type == "package") | .data)[]'
llvm@6
ocaml
lfs
pyenv
tig
...

という感じで、日常にあるちょっとだけ取扱に困るログを取り扱ってみる回でした。

*1:なんかllvmがたくさん入ってるとか、こんなに一気に上げて大丈夫なのかとかはスルーで

*2:local のテストはかけるけどlocal aliasのテストがかけないような気がするけどもしかしたら書けるかも。

Rosie Pattern Languageに入門（２）

Rosie Pattern Languageに入門（１） - だいたいよくわからないブログ

前回の続きです。

前回までだと、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.01 や 1 , 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の利点が失われるわけではありません。