Edited at

並列プログラミング言語 Elixir (エリクサー) におけるソフトウェアテスト〜基礎から最新展望まで

(この記事は「ソフトウェアテスト #2 Advent Calendar 2018」の7日目です)

「ソフトウェアテスト #2 Advent Calendar 2018」6日目は @kokotatata さんの「アジャイルもテスト自動化も当たり前?! ~AIがテスト設計をする日が来るかも~」でした。

「ソフトウェアテスト #2 Advent Calendar 2018」7日目の今日は,残念ながら行けなかった JaSST'18 Kyushu にて事例発表を検討していたネタを披露しようと思います。最近「推し」の並列プログラミング言語 Elixir (エリクサー)におけるソフトウェアテストについてです。


Elixir(エリクサー)の特長

なぜ Elixir に注目しているかというと,Elixir の持つ並列処理性能耐障害性が高い上に,文法が平易で記述が容易であるから,そして Phoenix(フェニックス)という最速のウェブフレームワークを持つからです。


Elixir における並列処理

まず Elixir における並列処理について説明しましょう。

1..1_000_000

|> Enum.map(foo)
|> Enum.map(bar)


  • 1行目の1..1_000_000は,1から1,000,000までの要素からなるリストを生成します。なお,数字の間の_(アンダースコア)によって,数字を分割するコンマを表します。

  • 2,3行目の先頭にある|>パイプライン演算子で,パイプライン演算子の前に書かれている記述の値を,パイプライン演算子の後に書かれた関数の第1引数として渡します。すなわち,このような記述と等価です。Enum.map(Enum.map(1..1_000_000, foo), bar)

  • 2,3行目に書かれている Enum.mapは,第1引数に渡されるリスト(など)の要素1つ1つに,第2引数で渡される関数を適用します。ここでは関数 foo を各要素に適用した後,関数 bar を各要素に適用します。もし,fooが2倍する関数で,barが1加える関数だった時には,これらの記述により,2倍してから1加える処理を1から1,000,000までの要素に適用したリスト,[3, 5, 7, ...] を生成します。

このようなMapReduceによる記述は並列処理にとても向いています。この例だと,リストの1つ1つの要素に対して,関数 foobar を順番に適用するわけですが,それぞれの要素に対する計算は互いに干渉しません。そのため,各要素の計算を異なるコアに配置して独立させて計算しても結果は変わらないですし,互いにコミュニケーションを取り合いながら同期させて計算する必要もありません。

このことを利用して,Elixir では Flow という並列処理ライブラリが開発されてきました。 Enum.map のときとコードはとても似ています。

1..1_000_000

|> Flow.from_enumerable() # リストの要素を各コアに分配する
|> Flow.map(foo)
|> Flow.map(bar)
|> Enum.to_list() # リストに戻す

このように書くだけで,並列処理をしてくれます。

並列処理ができるということは,並列処理によって実行順序が不定になるということを意味します。ソフトウェアテストをする上で重要な特性となってきます。


Elixir/Phoenix の耐障害性

つぎに Elixir/Phoenix の耐障害性について説明します。

Javaなどのプログラミング言語では,GCなどのメモリ管理は処理系(VM)全体にわたって行われてきました。このことにより,しばしば処理系(VM)全体が停止してしまう問題が起こります。

また,Javaなどのプログラミング言語では,例外処理は try/catch によるものでした。このような例外処理は,時として適当に書かれることがあり,不適切な例外処理がなされることによってメモリリークや不整合の原因となります。また例外処理を含めてきちんとテストすることは時として困難です。

しかしこれらの問題は Elixir では解消されます。

Elixir ではGCなどのメモリ管理はプロセス単位で独立しています。したがって,障害が発生した時には基本的に該当プロセスがダウンするのみで,めったに処理系(VM)全体がダウンすることがありません。したがって,Full GC が働いて Stop the world すなわち処理系を利用するすべてのプログラムの動作が一斉停止することは、原理上ありません

また,Elixir では,try/rescue による例外処理機能も備えてはいるのですが,基本的に例外が発生しても例外をrescueせずにプロセスごと落ちるように設計しておき,監視プロセスにより該当プロセスを再起動することで復旧させることが一般的です。これにより,煩雑なtry/rescueによる例外処理を記述することなく,シンプルに障害復旧をすることができます。

参考記事: Elixirで遠隔PCに侵入#3風「OTPスーパーバイザで例外処理をシンプルに作る」

Elixir

(追記: これらについて Twitter で質問が寄せられました。末尾の追記にて補足説明しています。また少し私の認識が間違えていたことがわかったので一部書き換えました)

これらの特性により,Elixir / Phoenix は極めて高い耐障害性を備えています。これは品質保証担当としては嬉しい!


イミュータブル特性

Elixir がなぜこのような画期的な特長を備えているかというと,Elixir で記述された変数の実体は基本的に一度値が決まったら不変である,すなわちイミュータブルであることを強制していることに起因します。

イミュータブルであるからこそ,並列処理をした時に値の同期や排他制御をする必要がなく,並列処理性能が向上します。また,イミュータブルであるからこそ,プロセスごとに変数をコピーしても問題がなくなるので,メモリ管理をプロセスごとに閉じることができます。

Elixir の強みである並列処理性能と耐障害性は,すべてがイミュータブルであることに支えられています。

イミュータブルであるがゆえに,内部状態を記述するには次の2つの方法のどちらかを採るしかありません(具体的な方法については割愛します)。


  • 関数の引数の中に内部状態を表すための引数を与える

  • Mnesia や FastGlobal などのデータベースを用いる

このことによりソフトウェアテストが容易になります。


  • 関数の引数として内部状態が現れる場合には,テストコードから内部状態が制御可能・観測可能であることを意味します。

  • またデータベースを用いて内部状態を表現する場合も,テストコードから内部状態が制御可能・観測可能です。加えて,ソースコードレビューで機械的に見分けることができます。


統合ビルドツール mix の存在

Elixir は統合ビルドツール mix があり,ビルドと自動テストを標準化された方法で実施することができます。

mix test というコマンドを実行するだけで,プロジェクトに記述された全てのテストを実行してレポートを得ることができます。

プロジェクトのディレクトリ以下にある test ディレクトリの中にテストコードを記述します。標準的には xUnit スタイルのテストコードを記述できます。ESpec を導入すれば BDD スタイルのテストコードを記述できるようになります。


doctest

私が中でも重宝しているのは doctest です。これはプログラム中に Markdown でドキュメントを書くことができるのですが,その中で下記のようにサンプルコードを記述すると,テストコードとして自動実行してくれるのです!!!

defmodule Foo do

@moduledoc """
Documentation for Foo.
"""

@doc """
Hello world.

## Examples

iex> Foo.hello()
:world

"""
def hello do
:world
end
end

ここに注目ください。

  ## Examples

iex> Foo.hello()
:world

Foo.hello() を実行すると :world という結果が得られるというサンプルコードを表しています。mix test を実行するときちんとこのコードをテストケースの1つとして扱ってくれますよ!


@spec@type

Elixir は契約プログラミング(Programming By Contract)あるいは契約による設計(Design By Contract)をサポートします。こんな感じ。

@spec sum_product(number) :: number

def sum_product(a) do
[1, 2, 3]
|> Enum.map(fn el -> el * a end)
|> Enum.sum()
end

sum_producta を引数にとって,リスト[1, 2, 3] それぞれの要素を a 倍して合計を計算します。

@spec により,sum_product が1つの number 型の引数をとって number 型を返すことを宣言しています。コンパイル時にチェックされるほか,Dialyzer という静的解析ツールを使うことで型検査的なことを行うことができます。


@zacky1972 の研究について

このように Elixir がもともと持つソフトウェアテストの能力はとても高いものです。快適な TDD を行うことができますね。

@zacky1972 こと山崎進は,さらに Elixir のソフトウェアテストや品質保証の能力を高めるための研究をしています。


AST を使った自動回帰テストの最適化

こんな記事があります。「20 万行超のコードベースをテストせずにリファクタリングリリースした話」

アイデアとしては「プログラムコードの抽象構文木(AST)が変化しないならば,そのプログラムのオブジェクトコードは変化しないので,テストしない」というものです。

このアイデアを micro Elixir / ZEAM に盛り込もうと思っています。すなわち,関数レベルで AST に変化があったかどうかを出力できるようにして,mix test で実施するテストケースを削減するというアイデアです。

また micro Elixir / ZEAM は最適化コンパイラでもありますので,AST に変化があるかどうかで最適化をやり直すかどうかを判断するということもできます。

このアイデアは,DBやI/O等からの外部入力がない場合のみ適用できます。もし外部入力がある場合にはASTに変化がなくても結果が変わらないことを保証できません。


並列処理の実行順序の復元

前述のように doctest はシンプルかつ非常に強力ですが,並列処理をすると実行順序が不定になることで,実行結果も不定になってしまうような場合に,容易に doctest を記述できません。

たとえば下記のような並列処理のコードは実行順が保証されないので,実行結果が不定になってしまいます。

1..1_000_000

|> Flow.from_enumerable
|> Flow.map(& foo(&1))
|> Enum.to_list



  1. 1..1_000_000 は 1から1,000,000までの要素を持つリストを生成します。


  2. |> Flow.from_enumerable により各プロセッサに分配します。


  3. |> Flow.map(& foo(&1)) はリストの各要素に関数 foo を適用するのを並列で行います。


  4. |> Enum.to_list により並列処理は終了でリストに集計し直します。

そこで,並列処理実行前に,あらかじめデータとして与えるリストに番号付けをしてから並列実行を行い,結果を番号順にソートしてから比較するということを行います。

こんな感じです。

1..1_000_000

|> Stream.with_index
|> Flow.from_enumerable
|> Flow.map(& {foo(elem(&1, 0)), elem(&1, 1)})
|> Enum.to_list
|> Enum.sort(& elem(&1, 1) < elem(&2, 1))
|> Enum.map(& elem(&1, 0))



  1. 1..1_000_000 は 1から1,000,000までの要素を持つリストを生成します。


  2. |> Stream.with_index により,通し番号をつけます。


  3. |> Flow.from_enumerable により各プロセッサに分配します。


  4. |> Flow.map(& {foo(elem(&1, 0)), elem(&1, 1)}) について



    • |> Flow.map(& ...) はリストの各要素についてカッコ内の処理を並列に行います。


    • elem(&1, 0) は結果的に 1 で生成したリストの各要素を取り出します。


    • elem(&1, 1) は結果的に 2 で生成した通し番号の部分を取り出します。


    • foo(elem(&1, 0)) は1で生成したリストの各要素に関数 foo を適用します。

    • したがって全体として,通し番号を維持したまま,1で生成したリストの各要素に関数 foo を適用するのを並列に行います。

    • 並列処理により実行順が保証されないので,リストの順番が乱れる可能性があります。




  5. |> Enum.to_list により並列処理は終了でリストに集計し直します。


  6. |> Enum.sort(& elem(&1, 1) < elem(&2, 1)) により,通し番号順にソートし直します。これにより,並列処理によりリストの順番が乱れても元に戻ります。


  7. |> Enum.map(& elem(&1, 0)) により,通し番号を取り除き,計算結果のみを取り出します。

以上によって,並列処理によって実行順が保証されない環境下でも,逐次処理と同じ実行結果を得られます。

しかし,このようにコーディングするのは,いかにも煩雑ですよね。また,けっこう重たい処理になってしまうので,実行時間が余計にかかってしまいます。

そこで,このような処理を簡便に記述し,かつ高速に実行できるようなライブラリを開発しようと考えています。

記述のイメージはこのような感じです。

1..1_000_000

|> Order.ensure(
fn l -> (
l
|> Flow.from_enumerable
|> Flow.map(& foo(&1))
|> Enum.to_list
))



  • Order.ensure により,中の実行順序を保証することを宣言します。


  • l にはパイプライン演算子で流れてきたリストがそのまま入ります。

実装してみないと確かなことは言えませんが,おそらくメタプログラミングをする必要があるんじゃないかなと思います。また,高速化のためネイティブコード呼び出しが必要になってくるものと思われます。

これにより,doctest で並列処理を扱っても実行結果を一意に定めることができますね。


モデル検査との連携

並列プログラミングでは,モデル検査のようなアプローチが有効です。

たとえばモデル検査により,どのような順番で実行されたとしても,ある特定の性質を満たすことを保証できるかどうかを,全ての場合を調べ尽くすことにより証明することができます。典型的には,デッドロックや公平性などを確認することができます。

そこで,Elixir とモデル検査を連携させることにより,どのような価値を提供できるか,またどのように連携すればいいかを研究しているところです。

ちなみにモデル検査の代表的な応用であるデッドロックについては,Elixir がイミュータブルでアクターモデルを採用していることにより,ほぼデッドロックで困ることはないです。


リアルタイム性の保証

Enum や Flow などの MapReduce スタイルのプログラム記述で統一することで,実行時間を推定することができ,結果としてリアルタイム性,すなわち定められたデッドラインまでに実行が完了することを保証できるようになるのではないかと期待しています。

このようなことが今までできなかったのは,停止性問題に起因します。停止性問題とは「任意のプログラムが有限時間内で終了(停止)するかどうかを,アルゴリズムによって証明することはできない」という定理です。この証明は背理法によってなされます。すなわち,もし証明できるとしたら,ある条件下で矛盾が生じる,というような証明です。

この定理を学生時代に初めて知った時から,この限界を何とかして超えられないか,ずっと考え続けてきました。

私のアイデアはこうです。たしかに任意のプログラムでは停止するかどうかを証明できない。しかし,たとえば有限長のリストを Enum.map のように走査するだけのプログラムで,かつ Enum.map 内が有限時間内で必ず停止するならば,プログラム全体が有限時間内で完了するではないか。MapReduce スタイルでこのように帰納的に組み立てるように統一したならば,必ず有限時間内に完了することを保証できるのではないか?

さらに進めて,Enum.map のような内部イテレータを全てのデータ構造に整備し,それらの計算量をあらかじめ与えたならば,MapReduceスタイルで書かれたプログラム全体の計算量を証明することができるのはないか?

さらにさらに,アセンブリコードレベルで各インストラクションの実行時間を計算し,積算していくことで,プログラムの実行時間の数理モデルを作ることができるのではないか?


おわりに

本記事では並列プログラミング言語 Elixir とソフトウェアテストとの関連を述べました。ぜひこの機会に Elixir に触れてみてください!

また,私 @zacky1972 こと山崎進が進めようとしている研究構想についても披露しました。一緒に研究してくださる方を募集しています。ご連絡ください。

次にアドベントカレンダーの記事を書くのは,明日12/8公開予定の「Rust Advent Calendar 2018」8日目の「ElixirとRustをつなぐRustlerを使った事例紹介」です。お楽しみに!

明日の「ソフトウェアテスト #2 Advent Calendar 2018」8日目は @mhlyc さんです。こちらもお楽しみに!


追記

次のような質問が寄せられました。


Elixir で例外を吐いたらプロセスごと再起動すれば良いという話ですが,単に再起動するだけだと例外の原因が直っていないので永遠に例外を吐き続けるのでは?


例外が直らない前提で考えていませんか?

「プロセスごと再起動」で前提にしているのは,たとえば Phoenix で特定リクエストのみ異常データが含まれているというようなケースです。そのリクエストのみ異常系として落とすことで無視し(もちろん障害検出としてエラーログには残す),プロセスを再起動して再びリクエストを受け付けるというようにするというような使い方をします。

逆に「直らない例外」が繰り返されるということは,それは異常系ではなく準正常系(すなわち,正常系ではないが,ありうる事態として想定しなければならない場合)として扱うべきです。Elixir ではこのようなケースは try / rescue で扱うのではなく,{:ok, result}, {:error, message} のようなアトムとタプルを組み合わせた値を戻すことで対応することを推奨しています。

そのあたりの思想は,次のような記事に書かれています。