日本ソフトウェア科学会第 34 回大会 (2017 年度) 講演論文集

アクターシステムを対象としたリバースデバッギングのためのフレームワーク
柴内 一宏

渡部 卓雄

アクターモデルは並行計算モデルの一つであり，アクターと呼ばれる計算主体間の非同期メッセージ通信により計算が行われる．アクターモデルでは原則として状態を共有しないため，データ競合やデッドロックといった単純な並行バグは回避できる．しかしながら，メッセージ到着順序の非決定性に起因するバグは依然として発生しうる．我々はこのようなバグの発見を容易にすることを目的として，アクターモデルにもとづく各種言語および実行系を対象としたデバッギングフレームワーク Actoverse を設計・実装した．Actoverse はリバースデバッギングおよびメッセージ到着順の制御機構を備えており，メッセージ到着順序の非決定性に伴うバグの発見を支援する．本稿では Actoverseの概要について述べ，Akka による例題を通してその有効性について議論する．

The Actor model is a concurrent computation model based on asynchronous communication among computational entities called actors. The inherent shared-nothing principle and the absence of locks guaranteethat actor-based programs can avoid simple concurrency bugs such as data races and deadlocks. However,they are not completely free from application level concurrency flaws that occur, for example, due to theindeterminate arrival order of messages. To assist discovering such bugs in actor-based systems, we designed
and implemented Actoverse, a debugger that adopts reverse debugging and provides an interactive aid forcontrolling the arrival order of messages upon re-execution. In this paper, we overview its architecture anddiscuss its eﬀectiveness by debugging Akka-based example applications.ては，アクターモデルに特有の並行バグが発現する可1 はじめに能性がある．そのほとんどはメッセージの到着順序に並行システムにおけるバグは，従来の決定的なプロ関連している．アクターモデルにおいては，送信されグラムとは異なった性質を持つ．デッドロックやデーたメッセージがその順序通りに受信されることは保証

タ競合といったスレッドベースのプログラムにおいてされていない．

一般的な並行バグは，同一のリソースに対して複数のプロセスが関与することによって発生する．

現在までに，スレッドベースの並行バグに関するデバッグ手法については多くの研究が行われてきた．ししかし，そのようなバグは（純粋な）アクターモデかしながら，昨今のアクターモデルに基づく言語やフルに基づくシステムでは発生しない．アクターモデル

レームワークの発展と実用化に比較して，アクターモ

では，アクター間で状態は共有されず，また待ち状態デルを対象としたデバッグに関する研究は相対的にごを保持するようなロックも持たないためである．

く少ないのが現状である．アクターモデルに基づく言

それでもなお，アクターモデルのプログラムにおい語やフレームワークのデバッガはいくつか存在するが，上で述べたアクター特有の並行バグに焦点を当て∗A Reverse-Debugging Framework for Actor-based
Systems
This is an unrefereed paper. Copyrights belong tothe Authors.
Kazuhiro Shibanai, Takuo Watanabe, 東京工業大学 情報理工学院 情報工学系, Dept. of Computer Science,
Tokyo Institute of Technology.

たデバッガーは稀であることが Lopez らによって指摘されている [7]．
本研究で我々は，リバースデバッグの手法を採用したデバッガ Actoverse†1 を提案する．リバースデバッ

において，以下のことを主張している [7]．

グとは，実行履歴を保存しておき，のちに実行中のあ

まず，複数のアクターが相互に待ち状態になり，暗る時点へと状態を遡るデバッグ機構である．加えて黙的なデッドロックが発生する可能性がある．例えActoverse は，アクター間のメッセージについて，そば，2 つのアクター A と B との間でメッセージののアドレスや内容に基づいたブレークポイントを定送受信を行うプロトコルを考える．ここでは A が B義する機構を提供することで，非決定的なバグの再現からのメッセージ x を待ち，B に応答を行うとする．

を可能にする．

しかし B が誤ったメッセージ y を送ると A は応答

本論文では，まず研究の背景を説明したのち，提案できず，結果としてプロトコルは進行しない．この種するデバッガ Actoverse の主機能について概説する．のバグは，アクターが実際にはブロックされずに，かその後，機能を実現する具体的な構成や手法について

つ他のアクターからのメッセージは通常通り処理するの説明を行う．最後に，デバッガのオーバーヘッドをことができるため，検出が困難である．

計測するメモリ消費に関する実験について述べる．

また，アクターモデルでは，アクターが独立して動作しデータを共有しないため，データ競合あるいは不2 背景可分性違反といった「競合状態」は発生しない．しか2. 1 アクターモデル

し，メッセージ配信の順序は保証されないことから，アクターモデルは，Hewitt により提唱されその後不正なメッセージやクラッシュ等の予想外のイベント

Agha らによって発展されてきた並行計算モデルの一の発生や，想定したプロトコルとは異なった動作をつである [1]．アクターモデルでは，アクターと呼ばすることによって予期しない結果やシステムのクラッれる並行かつ独立に動作する計算主体が相互にメッシュを引き起こす可能性がある．

セージを送受信することによって計算を進行させる．
また，アクターは他のアクターの内部状態を直接アク2. 3 並行プログラムにおけるデバッグセスすることはできない．またメモリや時計などを共シングルスレッドで動作するような決定的なプロ有せず，ロックによる同期も行われない．
一般にアクターがメッセージを受信すると，以下のような振る舞いを行う．

グラムにおけるデバッグでは，バグが発生した場合，デバッグ対象を停止して再実行し，その挙動を再現することが行われる．また，そこではプログラムを特定• メッセージを他のアクターに送信する．の時点で一時停止するためにブレークポイントが用• 新たなアクターを生成する．

いられる場合がある．

• 自分自身の振る舞い（メッセージの処理方法）を変更する．

それに対し，並列計算や非同期 I/O 等を含む非決定的なプログラムでは，バグが常に再現されるとは限受信したメッセージの処理は任意の順番で行われる．

らない．アクターモデルでも同様に，システムが非同すなわち，メッセージの処理順に関する保証や制約は期的に動作するため，結果が常に同じであるという保存在しない．

証は無い．
これまでに並行計算等の非決定的なプログラムに

2. 2 アクター特有の並行バグ対するデバッグ手法は多く提唱されているが，ここでアクターモデルのシステムでは，単純な競合状態は，リバースデバッグとレコードアンドリプレイに焦やデッドロックとは異なった種類の並行バグが生じうる．Lopez らはアクターモデルの特有のバグの研究点を当てる．
リバースデバッグ（タイムトラベルデバッグ/双方向デバッグ）は，プログラムが実行される方向とは逆†1 Actoverse は Github で公開されている．
https://github.com/45deg/Actoverse

方向に実行ログを遡行し，過去の状態を復元するデバッグ手法である．リバースデバッグでは，プログラムの実行中にバグに遭遇した際，プログラムを最初かその他 Actoverse には，イベントの因果性を再現ら再実行することはせずに，発生直前の状態に戻してし再実行を行うレコード・アンド・リプレイ機能や，から，バグの詳細を精査する．

メッセージログの可視化，内部状態のインスペクタ等

リバースデバッグはいくらかのデバッガで実装されている．例えば，GDB†2 ，Microsoft IntelliTrace†3 ，が実装されている．以下，各機能の概要を示す．

TotalView ReplayEngine†4 等がある．リバースデ

3. 1 インスペクタ

バッグを実装する最も一般的な方法は，実行中の各スインスペクタには，デバッグ対象のシステムに存在テップで十分な状態を保存し，過去に戻るときに復元する各アクターの内部状態が表示される．表示されたするものである．リバースデバッグに関する詳しい実値はアクターの状態が変化した場合に更新が反映さ装と用途についての研究は， [2] で行われている．

れる．これにより，予期しないイベントによる状態の他の非決定的な並行バグに対する手法としては，レ変化に対し容易に気づくことが可能となる．

コードアンドリプレイが挙げられる．レコードアン
ドリプレイでは，命令の実行パスやプロセス間のメッ

3. 2 メッセージタイムライン

セージの流れが逐次記録され，デバッグの際には保存

アクター間のメッセージの流れは，時間軸に沿ったされた通りにプログラムを再実行する．リバースデシーケンス図として可視化される．

バッグとは違い，プログラムを最初から再実行する必

各アクターは垂直の線として表現され，アクター間要がある．一般的に，レコードアンドリプレイはリの各メッセージは送信アクターから受信アクターへのバースデバッグに比べ実装が簡単である．

矢印として表現される．また，内容に応じた色つけによりメッセージの種類の識別を容易にしている．

3 Actoverse の概要

線上にある各点は，アクターがメッセージを受信しActoverse は，本研究で提案するアクターシステムた時点を表している．点にマウスカーソルを重ねるを対象としたライブデバッガである．Actoverse の主と，その時点でのアクターの状態のスナップショットな特徴として，アクターに特化したリバースデバッグがポップアップで表示され，アクターの状態の変化を機構がある．これは，メッセージ到達時の各時点での通時的に確認できる．

アクターの内部状態のスナップショットを取得することにより実現されている．
さらに，メッセージ指向のブレークポイントにより，アクターに対するメッセージの到達順序をユーザ

タイムラインの点と矢印は，実際の時間の尺度ではなく，因果の半順序関係を整数値で表現する Lamport
タイムスタンプ [6] を基準に配置され，イベントまたはメッセージの順序を定めている．

が制御することが可能となる．その「ブレークポイン

この抽象化により，システムの開発者が明示的にグ

ト」はユーザが指定したメッセージの内容に関する条

ローバルな同期クロックを導入することなく，因果関件で設定され，該当するメッセージはアクターに到達係の時系列に沿ってメッセージをトレースすることがする以前に保留される．リバースデバッグとブレーク可能となる．

ポイントの機能を利用することにより，並行的なアクターシステムのプログラムに対して決定的なデバッグ

3. 3 状態の復元機構を行うことが可能となった．

タイムライン上のイベントを表す点をクリックする†2 https://sourceware.org/gdb/news/reversible.
html†3 https://msdn.microsoft.com/library/mt228143.
aspx†4 http://www.roguewave.com/products-services/
totalview/features/reverse-debugging

ことで，アクターがその時点での状態に復元される．
復元の処理は，先述の Lamport のタイムスタンプに基づいて実行されるため，復元対象のアクターの他に，そのアクターがメッセージ送信により影響を及ぼした別のアクターに関しても状態がロールバックさ図1

デバッガの UI 画面れる．
復元処理が実行された後では，復元ポイント以降

Actoverse ホスト部
Actoverse UIWebSocket
通信ハンドラの記録（メッセージ，アクターの状態等）は，メモリコマンドリークを避けるために消去される．しかし，Actoverseイベント

メッセージ

レポートセッション

履歴解析部

状態やメッセージのでは，メッセージの履歴の消去されない保存を可能とスナップショット

アクターの制御対象システムするセッションリプレイ機能が提供されている．これ…

については後の章で述べる．
図2

3. 4 メッセージ指向のブレークポイント

デバッガの構成

メッセージ指向ブレークポイントは，ユーザによっは「セッションリプレイ」という名前で実装され，各て指定された条件に合致するメッセージを受信時に退セッションはメッセージの一連の履歴を保持している．

避させ，処理を保留する機構である．

Actoverse が起動している間，セッションは永続的以下の様なメッセージ条件が指定できる．

であり消失することは無い．そのため，プログラムが• 送信者のアクターの名前修正された後に対象システムに対し再実行・再接続さ• 受信者のアクターの名前れた場合でも問題の状況の復元が可能となる．さら• メッセージデータの部分一致及び完全一致に，複数のセッションを保持することができるため，処理の保留はメッセージ単位で行われ，条件に合致

ユーザは複数の状況を再現しテストすることが可能

しないメッセージは通常の方法でアクターに到着し，となる．

処理が進行される．

4 実装
3. 5 セッションリプレイ

4. 1 アーキテクチャ

ある特定のメッセージ順序でバグが発生した場合，Actoverse は UI 部とホスト部の 2 部で構成されてプログラムの修正後の検証の際に，同じメッセージ順いる．

序でプログラムを再実行する必要がある．この場合，UI 部では，メッセージの履歴やそれぞれのアクターレコードアンドリプレイが有効となる．Actoverse での現在および過去の状態の表示を行う．また，対象システムの制御パネルとしても用いられ，過去の状態のである Akka†5 上にリファレンス実装を行った．な

遡行や，メッセージブレークポイントの設定をこのイお，Akka は Java と Scala で利用できるが，以降でンターフェースで行う．

は Scala の場合における説明を行う．

ホスト部では，対象システムの内部においてアク4. 3. 1 Akka フレームワークの拡張ターの監視や制御を行う．ホスト部は，アクターの状態の更新を UI に通知し，また UI から制御コマンド処理内容を受信した際に，アクターの状態の操作やメッセージ情報の書込添加されているかの再送等を行う．

条件分岐

いいえ

UI とホスト部の通信は，TCP 上の双方向通信プロトコルである WebSocket によって行われ，アクターデータストア

メッセージにメタ情報がメッセージにデフォルトのはいメタ情報を付加する

保留メッセージ
リストやメッセージの情報や UI からのコマンドがやり取りされる．

メッセージはブレークポイントの条件に合致するか

4. 2 セッションの実装

はいメッセージを保留リストに保存するNo
メッセージをセッションは，一連の受信したメッセージのリストイベントログに追加イベントログとして UI 部に保存される．したがって，対象システ
メッセージ受信をムが終了して接続が失われた場合でも，セッションはUIに通知

WebSocket
ハンドラ破棄されないため，対象システムの修正後もセッショ対象の receiveンの再現が可能となる．

メソッドの呼び出し

セッションの復元の処理の概要を以下に示す．

現在の状態をスナップショットとして保存

1. UI は，「初期状態に戻す」コマンドを対象のホスト部に送信する．続けて，UI は全てのメッセースナップショット
リスト

内部状態の更新をUIに検知

ジを保留するブレークポイントの設定コマンドを送信する．

2. 対象システムが初期状態に戻った後，UI はセッ

図3

Akka 実装でのメッセージの流れションに保存されたメッセージ履歴の先頭からメッセージを再送する．ホスト部は，UI から受信したメッセージに一致するものを保留されたActoverse の機能を実装するため，Akka フレームワークに対する拡張を行った．†6

メッセージ群から取り出し，対象のアクターに転• メッセージの流れやイベントの因果関係を追跡す送する．もしメッセージが保留リストにない場るために，Lamport タイムスタンプやアクター合，このアルゴリズムは中断される．の名前等が送信時にメッセージにメタ情報として3. セッション内のすべてのメッセージが配信された場合，終了．

付加される．

• アクターシステム上の送受信等のイベントはActoverse のホスト部に通知される．また，ホス

4. 3 ホスト部の実装

ト部は UI からコマンドを受信し，対象のアクActoverse は，特定のアクターモデル実装に依存しターへの操作を行う．

ない設計となっている．アクターベースの言語やフ• 各アクターは，自身の生成時とメッセージの受レームワークは，要求されるプロトコルを実装すればActoverse で利用可能となる．
本研究では，アクターシステムのフレームワーク†5 http://akka.io/†6 https://github.com/45deg/Actoverse-Scala信時に自らの状態のスナップショットを記録する．

セージ指向のブレークポイントが実装されている．あ• アクターの内部状態は連想配列の形で保存され，るいは，アクターモデルをベースにした Erlang や過去の状態を復元する際に利用される．Akka のElixir などの言語に対するデバッガにおいても，並行実装においては，明示的に可変である変数にアノバグのデバッグをサポートしているものが存在する．

テーション @State を付加することで保存すべき

しかし，リバースデバッギングを実装しているアク対象を指定する必要がある．

ターベースのデバッガーはこれまで存在しなかった．

• 到着する全てのメッセージはユーザが指定した

さらに，前述したデバッガでは実装されていない，ロブレークポイントの条件に合致するか検査されグのグラフィカルな可視化やセッションの保存などのる．合致したメッセージは，アクターの処理メ機能も Actoverse では実装している．

ソッドへの受け渡しを行わず，ホスト部にある一時リストに保留される．そして，UI から「進行」

5. 2 モデル検査のコマンドを受け取った時に，一時からメッセー

モデル検査は，並行バグを検出する手法の一つであジが取り出され，対象のアクターのメソッドへ受り，プログラムが仕様（論理式で書かれていることがけ渡しが行われる．

多い）を満たしているかを論理計算により検証する形受信されたメッセージの流れを図 3 に示す．

4. 3. 2 実装上の制約式手法を指す．
検査器は，到達可能な状態を探索し，与えられた仕現在，Akka フレームワークや Scala の実装上の制様を満たさない反例があるか検査する．モデル検査

約から，以下の様なものに対してはデバッグが困難あは，古くから多くの研究がなされており，また産業的るいは不可能である．

な応用も広く知られている．

1. ファイル及びネットワークといった外部入出力代表的なモデル検査器として SPIN が挙げられる．

を取り扱うプログラム．現在，そういった変更をSPIN [5] は，分散アプリケーション用の汎用的な検査検知および状態の保存・復元する機構は実装され機であり，メッセージパッシングを含むさまざまな計ていない．

算モデルに対応している．McErlang [3] は，Erlang

2. アクターの停止及びクラッシュの取り扱い．Akka

を対象としたモデル検査器である．McErlang では，Actor のアクターのライフサイクル管理では，同状態のスナップショットを取り出せるように Erlang

一の参照 (ActorRef) を保ったままアクターを再言語を拡張し，到達可能な状態の探索を可能として生成することはできない．したがって，内部変数いる．

でアクターの参照を保持していた場合，状態復元

しかし，モデル検査器は「デバッガ」とは性質が異の際に元のアクターの参照が失われている可能なる．モデル検査では，プログラム実行以前の段階性がある．

で，ソースコード等を解析しバグを検出するような設計となっている．一方デバッガは，実際に実行されて5 関連研究
5. 1 アクターモデルのためのデバッガいるプログラムにおいて発生するバグを検出する．
そのほか，デバッガでは起こりうる可能性のあるアクターモデルのプログラムに特化した発展的な機全てのバグを検出できないが，仕様外の想定されて能を持つデバッガがこれまで複数提唱されている [7]．

いないバグに関しても対処が可能となる性質もある．

Causeway [8] は E 言語のための 事後検知デバッガで一方モデル検査では，モデリング言語自身の知識のみある．Causeway は，メッセージの因果関係を示し，ならず，検証されるプログラムの仕様を把握し記述すバグの原因の特定が可能となっている．

る必要がある．

REME-D [4] は AmbientTalk 言語のデバッガであり，Causeway のようなメッセージ追跡の他，メッムワークとそのケーススタディについてもさらなる研6 結論と今後の課題究が必要である．Actoverse の API を実装する際に，本研究では，アクターモデルのプログラムをデバッ

解決すべき実装上の問題は少なくない．例えば，アクグするための手法を提案し，その実装を行った．アクターの内部状態を取り出し保存する手法や，過去の状ターの状態の独立性を利用することで，リバースデ態に遡る機構の実装などが挙げられる．

バッギングをアクターベースのデバッグに適用することができ，並行バグに対し効果的であることが示さ謝辞れた．また，メッセージ指向のブレークポイントによ本研究は JSPS 科研費 15K00089 の助成を受けてり，非決定性のある動作に関しても再現性を保ちながらデバッグが可能となることが示された．
さらに，Actoverse のユーザーインターフェイスにより，アクターの状態の検査や操作といったシステムとの直感的なインタラクションが可能となり，並行バグの特定と修正が可能となった．

Actoverse デバッガの対象であるサンプルプログラ
ムは Github に公開されている †7 ．サンプルには，不正なメッセージの割り込みやプロトコル違反などの並行バグが含まれている．
現在このデバッガには取り組むべき課題が残されている．まずスケーラビリティの問題である．アクターモデルのシステムでは，多くのアクターが膨大な数のメッセージを送受信するような物が珍しくない．このようなシステムの場合，ユーザーインターフェースに大量のメッセージが表示されるためデバッグは困難となる．この問題に対処するためには，多くのプロセスとメッセージを可視化する手法に関するさらなる研究が必要となる．
また，Actoverse の API を実装する言語やフレー†7 https://github.com/45deg/Actoverse-Scala-Demosいる．
参 考 文 献[1] Agha, G.: Actors: A model of concurrent computation in distributed systems, MIT Press, 1986.
[2] Engblom, J.: A review of reverse debugging, Proceedings of the 2012 System, Software, SoC and Silicon Debug Conference (S4D), (2012), pp. 28–33.
[3] Fredlund, L.-c. and Svensson, H.: McErlang:A Model Checker for a Distributed Functional
Programming Language, SIGPLAN Not., Vol. 42,No. 9(2007), pp. 125–136.
[4] Gonzalez Boix, E., Noguera, C., and De Meuter,W.: Distributed Debugging for Mobile Networks, J.
Syst. Softw., Vol. 90(2014), pp. 76–90.
[5] Holzmann, G. J.: The Model Checker SPIN,IEEE Trans. Softw. Eng., Vol. 23, No. 5(1997),
pp. 279–295.
[6] Lamport, L.: Time, Clocks, and the Ordering of
Events in a Distributed System, Commun. ACM,Vol. 21, No. 7(1978), pp. 558–565.
[7] Lopez, C. T., Marr, S., and Gonzalez Boix, E.:Towards Advanced Debugging Support for Actor
Languages Studying Concurrency Bugs in Actorbased Programs, AGERE! 2016, 2016.
[8] Stanley, T., Close, T., and Miller, M. S.: Causeway: a message-oriented distributed debugger,
Technical report, HP Labs, 2009. HP Labs techreport HPL-2009-78.