BT

Scalaのアクターのための性能を犠牲にしないで競合安全性を確保する型システム

| 作者: Sadek Drobi フォローする 1 人のフォロワー , 翻訳者 徳武 聡 フォローする 0 人のフォロワー 投稿日 2009年7月26日. 推定読書時間: 7 分 |

原文(投稿日:2009/7/20)へのリンク

Philipp Haller氏とMartin Odersky氏は 投稿で、Scalaのアクターモデルの実装で安全にメッセージを転送する新しい方法を紹介している。メッセージを使って並行性を扱うのは並行処理をサポートする、拡張性のある設計をするのに役に立つが、性能や処理能力(柔軟性)、または競合に対する安全性の観点から見ると重大なトレードオフが生じてしまう。

理想的には、送られたメッセージは“送信側のメモリ領域から受信側のメモリ領域へ (ひょっとしたら分割されて)移動する”べきだが、“画像処理パイプラインやネットワークプロトコルスタックのような多数のメッセージを扱う重要なコード”の性能要件では、 “メモリを共有する同じコンピュータ上で動作するプロセスの間で、参照を使って”メッセージをやり取りしなければならない。このような状況でデータの競合の発生を回避するためには、メッセージの送受信に制約を課す必要がある。例えば、状態をかえられないメッセージやエイリアスフリーなメッセージを実装しなければならない。しかし、この方法だと性能に悪影響が出てしまう。なぜなら“オブジェクトグラフには送受信の制約を満たさないデータがあり、そのようなデータは必ず送信可能な形式にシリアライズしてから、送信しなければならない”からだ。

ScalaのアクターはErlangとは違って、メッセージはどんな種類でも構わない。不変のメッセージでも可変のメッセージでも、状態は“同じコンピュータ上でアクターの間でメッセージを送受信しているときは”メッセージの状態を複製しない。こうすることで、性能は上がり、柔軟性も確保できる。しかし、共有のメッセージに対する競合安全性を保証するのが難しくなってしまう。今までは、競合安全性が言語のライブラリによって強制されることはなく、むしろプログラミング上の規約として扱われていたが、その規約は、メッセージパッシングのメカニズムの能力を制限するものだった。

このような制約を取り払うため、Haller氏とOdersky氏が提唱するのは、能力(例えばオブジェクトに対するアクセス権限)の検証をもとにした型システムと、 “転送されたオブジェクトのエイリアスを管理し”参照が一意であることを保証するための外部向けの一意性だ。彼らは、メッセージをもとにした並列処理での状態の変化の中で、競合に対する安全性を確保するための中心的な概念が参照の一意性だ、と主張する。彼らが提示したサンプルは、アクターが “リンクリストの参照を受け取り”、そして“ローカルで作成した、あるいはどこかからか送られてきた”もうひとつのリンクリストを最初のリンクリストにつなげてから、そのリストをメッセージとして送信しています。”

actor {
	receive {
		case rlist: LinkedList =>
			val other: LinkedList = ...
			rlist.append(other)
			next.send(rlist)
	}
}
 
class Node {
	var el: Object
	var prev, next: Node
}
class LinkedList {
	var head: Node
	def append(other: LinkedList) {
		if (head == null)
			head = other.head
		else if (other.head != null) {
			var h = head
			while (h.next != null) h = h.next
			h.next = other.head
			h.next.prev = h
		}
	}
}

要素数が増えたリストをメッセージとして送信するには、“可変なメッセージに競合に対する安全性を侵すようなエイリアスがついていないか”を検証する必要がある。言い換えれば“このようなリストの参照は、リストに他のリストを連結したあとも、参照の一意性を維持する必要があるということです。”

彼らはこれを実現する仕組みを“オブジェクト能力型” (OCT)と名付け、EPFL Scalaのコンパイラの拡張として定式化する。これを実装するために、Haller氏とOdersky氏が導入したのは、単純で簡単な方法で型を検証できるために必要な情報を付加するアノテーションだ。これらのアノテーションはScalaの標準ライブラリのコレクション型のすべてのメソッドに作用する。これらのメソッドの実装を変更する必要もない。@unique、 @transient、そして@exposedの3つのアノテーションがあり、ローカル変数、メソッドの引数、メソッドの結果に付加します。

class Node {
	var el: Object
	var prev, next: Node
}
class LinkedList {
	var head: Node
	@transient
	def append(other: LinkedList @unique) {
		expose (this) { xl =>
			val ol = localize(other, xl)
			if (xl.head == null)
				xl.head = ol.head
			else if (ol.head != null) {
				var h = xl.head
				while (h.next != null) h = h.next
				h.next = ol.head
				h.next.prev = h
			}
		}
	}
}

例えば上記のように@transientアノテーションを[…]受信者に適用します。こうすることでリンクリストの参照は一意であることが要求されます。また、メソッドを呼び出しても、参照がなくなってしまうことはありません。つまり、呼び出した後も(一意な)参照を利用できます。この方法なら、appendメソッドを呼び出したときの参照の所有者の変更を安全に行いたい、という要求を満たせます。引数に付加されている@unique アノテーションが要求するのは、その引数が一意であることです。さらにこのアノテーションを付加すると、メソッドは引数を消費する権利を与えられます。つまり、メソッドを呼び出したあとは、引数にアクセスすることが無効になります。

[…]

参照の一意性を侵すようなエイリアスを防ぐためには、そのオブジェクトのフィールドにアクセスできるようになる前に、一意なオブジェクトにとして公開されなければなりません。

複雑に参照されていることが多いサブオブジェクトを含むオブジェクトを転送する場合の問題を扱うため、彼らはクラスタの概念を導入している。といっても、クラスタは“オブジェクトが作成されて処理が行われるのに従って、型システムがクラスタをの属性を検証する”ことをはっきりと宣言するものではない。

私たちが考案したこの仕組みでは、オブジェクトを安全に転送できるという事実を保証しているのはそのオブジェクトから到達できるオブジェクトです。オブジェクトO1がオブジェクト02から到達できるのは02のフィールドが01を参照しているか、02に到達できる他のオブジェクトが01を参照しているときだけです。この仕組みはオブジェクトグラフをクラスタとして特徴づけることで、そのオブジェクトグラフを安全な転送を保証します。[…] 

[この仕組みは]オブジェクトを転送するとき、そのオブジェクトのクラスタが一意であることを静的に保証します。このことはタイプセーフであるということも意味します。

OCTの仕組みが表すのは、メッセージの送受信において、既存の方法で発生してしまう重大な限界を取り除き、大量のメッセージを扱うアプリケーションでも性能を犠牲にしないで、競合に対する安全性を強制できる方法だ。もっともこの方法は 簡易な拡張としてすでにScalaに実装されているが、さらに使いやすくするために、Philipp Haller氏とMartin Odersky氏が導入したいと考えているのは、開発者の労力を節約できる型推論の仕組みだ。 

この記事に星をつける

おすすめ度
スタイル

こんにちは

コメントするには InfoQアカウントの登録 または が必要です。InfoQ に登録するとさまざまなことができます。

アカウント登録をしてInfoQをお楽しみください。

あなたの意見をお聞かせください。

HTML: a,b,br,blockquote,i,li,pre,u,ul,p

このスレッドのメッセージについてEmailでリプライする
コミュニティコメント

HTML: a,b,br,blockquote,i,li,pre,u,ul,p

このスレッドのメッセージについてEmailでリプライする

HTML: a,b,br,blockquote,i,li,pre,u,ul,p

このスレッドのメッセージについてEmailでリプライする

ディスカッション

InfoQにログインし新機能を利用する


パスワードを忘れた方はこちらへ

Follow

お気に入りのトピックや著者をフォローする

業界やサイト内で一番重要な見出しを閲覧する

Like

より多いシグナル、より少ないノイズ

お気に入りのトピックと著者を選択して自分のフィードを作る

Notifications

最新情報をすぐ手に入れるようにしよう

通知設定をして、お気に入りコンテンツを見逃さないようにしよう!

BT