檜山正幸のキマイラ飼育記 このページをアンテナに追加 RSSフィード

キマイラ・サイトは http://www.chimaira.org/です。
トラックバック/コメントは日付を気にせずにどうぞ。
連絡は hiyama{at}chimaira{dot}org へ。
蒸し返し歓迎!
このブログの更新は、Twitterアカウント @m_hiyama で通知されます。
Follow @m_hiyama
ところで、アーカイブってけっこう便利ですよ。

2008-12-06 (土)

メーセージ配送の一般論

| 16:14 | メーセージ配送の一般論 - 檜山正幸のキマイラ飼育記 を含むブックマーク

Erlangは、プロセス指向とか並列指向とか形容されますが、メッセージ指向とも言えます。Erlangのメッセージ通信がなかなかに便利なので、これをErlang外の世界まで拡げて使いたいという願望が湧きます。それで、いろいろと試行錯誤してきたのですが、現状における一般的な枠組みを記しておきます。一般的すぎて具体性に乏しいきらいはありますが、具体例はおいおい追加します。

内容:

  1. エージェントとノード
  2. メッセージの封筒情報
  3. メッセージ中継のアルゴリズム
  4. ノード内のメッセージ配送
  5. 循環するメッセージへの対処
  6. 通信リンクとクラスター
  7. ノードの能力と分類
  8. Erlangノードとブラウザノード

●エージェントとノード

メッセージの送信(発信、発生)や受信の主体となるナニカをエージェントと呼びます。「エージェント」という言葉に深い意味は何もありません*1。送信者、受信者となり得るモノ(thing, entity)です。比喩としては、メッセージを手紙や荷物、エージェントを人間に例えてもいいでしょう。

エージェント達が居る場所をノードと呼びます。比喩で言うなら、マンションや会社のビルがノードです。とりあえず、エージェントは、活動中に今居るノードから別のノードに移ること(ローミング)はできないとします。これを比喩で言うと、勉強中は外出禁止とか仕事中は会社のビルから出ないとか。ただし、活動を終了して、別のノードで始動することはできます。これを、ローミングと区別してリロケーションと呼びます。リロケーションの実現はけっこう難しい問題となります。

エージェントもノードもたいていは識別子を持ちます*2。それぞれ、エージェント名ノードアドレスです。エージェント名はさらに2種類あり、固有名詞に当たるエージェントIDと、役職名にあたるエージェントロール名です。エージェントIDは、大域的な一意性が保証されます*3。それに対して、ロール名はノード内でしか一意性を持ちません、「課長」とか「お母さん」みたいなもの。会社部署ごとに課長はいるし、家族ごとにお母さんはいますから、「課長」「お母さん」を大域的一意識別には使えません。1つのエージェントが複数のロール名を持ってもかまいません(「係長=宴会部長」とか)。

ノードアドレスのほうは、各ノードを一意的に識別する名前です。名前の具体的な形は規定しません。メールアドレスやインターネットドメイン名のような構文とは限りません。通し番号や乱数値でもいいのです。なんでもいいのです。何らかの構文や構造を仮定してはいけません。

今述べた、エージェント名、エージェントID、エージェントロール、ノードアドレスの値の集合をそれぞれ、AgentName、AgentId、AgentRole、NodeAddr とします。AgentName = AgentID + AgentRole となります(+ は共通部分なしの合併)。これらは、データ型の名前だと考えられます。

●メッセージの封筒情報

メッセージの本体はデータですが、送信者から受信者に配送するためのメタデータを含んでいます。データが手紙や荷物の中身だとすると、配送用メタデータは封筒に書く情報です。それらは次のとおりです。

項目名 説明 値の型
to 受信者 AgentName
dest (destination) 受信者の居るノード NodeAddr
from 送信者 AgentName
orig (origin) 送信者の居るノード NodeAddr

もちろん、これに加えてデータ本体があります。実は、メッセージ自体やデータにもIDを付けることができます。正確に言うと、IDというよりは後で照合するための参照番号です。この参照番号の型をRefとして、次の項目を追加します。

項目名 説明 値の型
ref メッセージやデータに対する参照番号 Ref

refはrefereceの略でErlangの用語に基づくものです。refの値は、返信の照合・確認のときに使われます。

●メッセージ中継のアルゴリズム

メッセージの送信者(センダー/ソースエージェント)は、ある特定の受信者(宛先/レシーバー/レシピエント/ターゲットエージェント)に向けてメッセージを送ります。メッセージがいくつかのノードを渡り歩いて目的地まで到着するとき、インターネットにおけるルーティングのような中継が必要になります。

ここで考えているメッセージは、すべての封筒情報が揃っているとは限りません。封筒情報が一部欠けているケースも考えます。中間地点でメッセージを受け取ったナニカは、次のような動作をしなくてはなりません。

if (destがある)
    destに、あるいはdestにより近いと思われるノードに
    メッセージを送る;
else // destがない
    if (toがあり、toの型がAgentId)
        toからdestを求める;
        if (成功)
            メッセージを送る;
        else //失敗 
            メッセージを捨てる;
    else if (refがある)
        refからdestを求める;
        if (成功)
            メッセージを送る;
        else //失敗 
            メッセージを捨てる;
    else
        メッセージを捨てる;

こんな動作をするナニカをルーター*4と呼ぶことにします。要約すると、ルーターはdest(ディステネーションノード指定)がないときは、to(ただし、値がID)かrefを頼りにガンバッテdestを決めろってことです。ただし、ガンバリはベストエフォートの意味なので、うまくいかないならあきらめます

[追記]「destに、あるいはdestにより近いと思われるノードにメッセージを送る」の部分は、もう少し手順があります。

if (destを直接知っている)
    destにメッセージを送る;
else if (destに送ってくれそうなノードを知っている)
    そのノードにメッセージを送る;
else // 書いてある送り先ノードがサッパリ分からない
    メッセージを捨てる;

[/追記]

他のノードにメッセージを送る具体的方式は色々あり得ます。IOポートみたいな出口にメッセージをポイッと投げればいいのかもしれません、他のポートノードを表現するオブジェクトやプロセスに依頼するのかも知れません。あるいはもっと複雑な手順かもしれません。とにかく、目的のノードに届くように送り出します。

●ノード内のメッセージ配送

ノード間(inter-node)配送の仕分けをしているルーターは、自ノード宛のメッセージを見つけると、他のノードに送り出すのではなくて、ノード内(intra-node)配送の担当に渡します。実装上は、ルーターがノード内配送までついでにやってしまってもかまいません。ルーターは、toを見てそれが自ノード内のエージェントだと分かったら、直接にそのエージェントにメッセージを渡すほうが早いでしょう。

ノード内配送は、toのエージェント名かrefの参照番号を頼りに行います。名前のスコープはノード内ローカルなので、エージェント名にロール名が使えます。無名のエージェント(そのノードのデフォルトエージェント)も1個だけ許されます。ノード内配送のアルゴリズムは次のとおりです。

if (toがある)
    toに対応するエージェントを探す; // toはロール名でもよい
    if (成功)
        メッセージを渡す;
    else // 失敗
        メッセージを捨てる;
else if (refがある)
    refを待っているエージェントを探す;
    if (成功)
        メッセージを渡す;
    else // 失敗
        メッセージを捨てる;
else // toもrefもない
    if (デフォルトエージェントがいる)
        メッセージを渡す;
    else // 失敗
        メッセージを捨てる;

●循環するメッセージへの対処

ノードどおしのトポロジーによっては、メッセージが無限にたらい回しされるかもしれません。こういう事態の予防や検出は難しいので、TTL(time to live)を使うのが現実的でしょう。

循環が起こりえないようなトポロジーでは、この問題を考える必要はありません。とりあえずは、十分に単純なトポロジーしか考えないとして、循環するメッセージの件は割愛します。

●通信リンクとクラスター

ノードAからノードBへとメッセージを送れる具体的・実効的・直接的な通信手段があるとき、AからBに向かう通信リンク(あるいは単にリンク)がある、と言います。リンクを絵に描くときは矢印を使うので、ノードとリンクの全体は有向グラフとして描けます。ノードAからノードBへと向かうリンクは高々1本(あるか、ないか)なので、このグラフは多重辺を持たず、単純有向グラフとなります。

メッセージ通信に参加するノードの集合を、そのリンクも込めてクラスターと呼びます。クラスターは単純有向グラフで描けますが、リンクの向きを無視すると連結グラフになります。つまり、孤立したノードがあったり、複数の島から成ることはありません。

クラスターはグラフなので、可達性、推移的閉包、サイクル(循環)、距離(ホップ数)などの概念を適用できますが、ここでは割愛します。

●ノードの能力と分類

先に、ルーティング、つまりメッセージ中継のアルゴリズムを示しましたが、すべてのノードがルーティング機能を備えているわけではありません。むしろ、大部分のノードはルーティングしません。ルーティング(フォーワード、ディスパッチ)するノードをハブノード、ルーティングしないノードを末端ノードと呼びましょう。これはやや誤解を招きやすい用語法で(よって、変更の可能性あり)、ノードがハブか末端かは、各ノード固有の能力の問題であり、クラスターのトポロジーとは関係ありません。グラフのトポロジーからハブのように見えていてもルーティングしないノードかもしれません(その逆のケースも)。

ルーティングしないノードAに、destの値がA以外のメッセージを送ってもすべて捨てられます。つまり、末端ノードに対してdestは無意味です。さらに、ノード内配送の能力さえ持たないノードもあり得ます。1つのノードに1つのデフォルトエージェントが居るだけなら、ノード内配送は無意味です。そのようなノードにtoを付けてメッセージを送っても、捨てられるか、toが無視されてデフォルトエージェントに渡されるでしょう。

ノードのなかには、片方向のリンクしか持たないものがあります。送信だけしかできないノードは、ノードアドレスも必要としないので、アドレスを持たない(無名、住所不明)ノードかもしれません。

「内部配送もできない、送信しかできない、アドレスを持たない」といった非力なノードもクラスターのメンバーとして許すのは、メッセージ通信への参加の敷居を出来るだけ下げたいからです。

Erlangノードとブラウザノード

ノードやエージェントの実体は何であるか? -- 何でもいいのです。あまり具体化してしまうと適用範囲や発想が狭まるのがイヤなんですが、そうはいっても具体例がないと実感がわかないので、2種類のノードを紹介します。

ひとつはErlangのERTSです。この例は、発想の源泉なのでトリビアルと言えます。ノードは単にErlangノード。ノードアドレスはErlangノード名。通信の基盤層はEDP(Erlang Distribution Protocol)です。メッセージは特定の(前もって約束された)形式を持つErlangタームで、エージェントはほぼプロセスです。

「ほぼ」と言ったのは、「エージェント=プロセス」ではないからです。エージェント名(通常は人間可読文字列)はPIDとは別に用意するので、エージェント名とPIDとの対応がどこかに必要です。また、エージェント名が指す実体が単一のプロセスである必要もなく、複数のプロセスの連合体でもかまいません。逆に、1つのプロセスが複数のエージェントの役割を果たすこともできます。時間と共にエージェントの実体であるプロセスがすり替わっても問題ありません(エージェントの同一性/寿命とプロセスの同一性/寿命はまったく別物です)。

Erlangノードをハブノードにしたいなら、ルーティング機能をErlangで実装しますが、Erlangだけの世界では特に原理的問題はないと思われます。

さて、ブラウザノードですが、これは、実行中のブラウザインスタンスを1つのノードとみなすものです。ノードアドレスは動的に割り当てるしかありません(ノードの寿命は短い)。ブラウザは当然ながらEDP通信はできないので、メッセージはテキスト形式にエンコードしてHTTPに乗せます。ブラウザ内に居るエージェントは、JavaScriptで実装されたプログラム/オブジェクトとなります。通常、ブラウザノードはルーティングしません(出来ないとは断言しませんが)。内部配送は出来るかもしれないけど、保証の限りではありません。

ErlangノードとErlangで実装されたエージェントは、安定した長い寿命の名前(アドレス、ID、ロール名)を持つことができ、ディスクやデータベースも自由に使えます。それに対して、ブラウザノードとブラウザ内エージェントは永続性のある資源を何も持てません。これではまともなことが出来ないので、ブラウザ内に棲息するエージェントにも永続性のサポートをしましょう、ということになります。-- そこらへんのハナシはこの次。

*1:「エージェント指向」なんて言葉がありますが、一切関係ありません。

*2:後で述べるように、無名のエージェント、無名のノードも認めます。

*3:大域的とは言っても、インターネット全体ではなくて、ある限定的な範囲です。

*4:個人的には、メッセージングサーバーと呼んでいるのですが、ルーターのほうが親しみがあるでしょうから、ここではルーターと呼びます。

jj1bdxjj1bdx 2008/12/06 23:51 現在の(R12B5)Erlang nodeは他のノードのメッセージの中継の機能までは持っていないですね.基本的に直接つながる(TCPでもUNIX socketでもいいんですが)のが前提です.ですからフォワーディングノードをErlangで書くとなると結構大変かも.

m-hiyamam-hiyama 2008/12/08 08:52 jj1bdxさん、
> フォワーディングノードをErlangで書くとなると結構大変かも.
Erlangの観点から真面目に考えると大変ですが、当面の目的は、Erlangノード(ハブ)を中継しての「ブラウザ<-->ブラウザ」通信です。すごく単純化すれば、なんとかなるかと。

2008-12-01 (月)

風邪ひいた

| 09:39 | 風邪ひいた - 檜山正幸のキマイラ飼育記 を含むブックマーク

寝込むほどではないですが、目と頭がドヨーン。

2008-07-22 (火)

親知らず抜いてきた

| 13:19 | 親知らず抜いてきた - 檜山正幸のキマイラ飼育記 を含むブックマーク

アグー。なにもしたくない。

内海内海 2008/07/22 13:42 檜山さんこんにちは。
>親知らず抜いてきた

本当にご愁傷様です(いや、この場合治療が進んだんだから慶賀の至りと言ったほうがいいのかな?)。

なにもしたくない気持ちは解りますf^_^;
ゆっくり休んでください。
私も親知らずを抜いた日はほとんど一日中ボーッとしました。
やる気も湧いてこないし、食欲もあまりなくなったりして。

それにしても何故21世紀にもなって、歯を抜くのにあんなペンチのような道具が主流なんでしょうね。
現代のテクノロジーで何とか別の痛みの少ない方法で歯を抜く事が出来ないんでしょうか?
人類の進歩の遅れを痛切に感じます(今一番痛切に感じているのは檜山さんなんでしょうけど(^-^))

m-hiyamam-hiyama 2008/07/22 17:24 内海さん
しゃべるのは難しいがキーボードたたくなら関係ない、と思いきや、キーボードたたく気力もわかない。
> それにしても何故21世紀にもなって、
僕の気持ちを代弁していただいてありがとうございます。まったく、ふんとにむう。

2008-01-25 (金)

しばらくバタバタしている

| 12:28 | しばらくバタバタしている - 檜山正幸のキマイラ飼育記 を含むブックマーク

きょうあたりから、来週にかけては、余分に(追加的に)やることやら、外出する用事やらでオタオタ、バタバタ。

bonotakebonotake 2008/01/27 04:11 ピースってもしかして、あの、動物園の飼育員の人が引き取って育ててた白熊から取ってます?
アレ特集してたNHKの番組、ウチでは永久保存版です。

m-hiyamam-hiyama 2008/01/28 09:06 bonotakeさん、
> あの、動物園の飼育員の人が引き取って育ててた白熊から取ってます?
はい、あのピースちゃんです。飼育ドキュメンタリーは市販もされてます。
飼育員のかたは、冬でも窓開けて寝てましたね、寒すぎ! 僕なら死ぬなぁ。

2007-10-10 (水)

目医者さんでドキッ

| 12:53 | 目医者さんでドキッ - 檜山正幸のキマイラ飼育記 を含むブックマーク

先週半ばから目が充血していたのは結膜炎でした。「はやり目」(流行性急性結膜炎)の懸念もあったのですが、結局は普通の結膜炎で、今はだいたい直ってます。

先週の金曜日、近くの女医さん(美人)が休みだったので、別の目医者さんに行ったのだけど、そっちも女医さん(若い)。これがまた不思議なセンセイでね、

「この目薬をガッツリつけてね。」
ウチラはこんなの使うんだけど。」

とかしゃべる。「今晩はお風呂入らないで。」のときは、両手で大きなバッテン作るし、「明日充血がおさまれば」と、僕の目の前に親指立ててグーッ!」と叫ぶし。

お医者さんにこういう対応されるの初めてで、オジサンとまどって疲れちゃったよ。

あっ、そうそう。帰り際に小さな紙片を手に渡されてドキッとしたら、併設のコンタクト屋のチラシでした。

2007-10-01 (月)

秋が来た、あーダメだ

| 17:20 | 秋が来た、あーダメだ - 檜山正幸のキマイラ飼育記 を含むブックマーク

気温の変化に非常に弱い僕は、案の定、夜明けの寒さで風邪ひいた。

喉痛い、あしたはたぶん休息してます。

2007-07-20 (金)

求人予定

| 11:44 | 求人予定 - 檜山正幸のキマイラ飼育記 を含むブックマーク

ウチ(檜山事務所)で求人しようと思っています(アルバイト/パート可*1)。で、募集の文面を考えているんですが、どう書いていいかわからない。テンプレートみたいのを埋めても真意が伝わらないしなー。

ウチで(つまり檜山と)仕事するってことは相当にワケワカランことだし、世間的には「そんなバカなことやめなさい」みたいな。少し頭おかしい人のほうが向いていそうだしな…

あー、考えるのがストレスだ。とりあえず、うまい文面を考えたり面接をしてくれる人を募集したい*2

事務所再生計画

| 13:51 | 事務所再生計画 - 檜山正幸のキマイラ飼育記 を含むブックマーク

上のような事情/状況もあって、もっと広い事務所に引っ越そうかと思い立ちました。せめて今の1.5倍くらい。で、いろいろと調べたり考えたりしたあげく、やめました。

結局、比較的近くにもう一部屋(分室?)借りることに。広い一箇所と狭い二箇所では、後者が不利のように思えますが、まず金銭的には、1年・2年くらいのスパンで考えるなら、広い一箇所のほうが初期費用が高いのでトータルの負担が増えます。2年より先なんてわかんないから、長期の計算してもしょうがないし。

それと、いくつかの物件を見てるうちに、今のところを去るのは得策ではないと感じてきたのです。建物や部屋はあまり良くない(大家さん、ごめんなさい)のですが、とにかく便利:

  • 駅まで 1分15秒
  • 中規模書店まで 20秒
  • スターバックスまで 1分10秒
  • つけ麺屋まで 40秒
  • サンクスまで 10秒(お隣)
  • セブンイレブンまで 50秒
  • スーパー・ライフまで 35秒

今まで意識してなかったのですが、このロケーションのメリットはなかなか代え難い。他に、

  • 居酒屋は同じビル
  • キャバクラまで 20秒
  • もう一軒のキャバクラまで 40秒
  • パチンコ屋まで 20秒
  • マンガ喫茶まで 45秒

と、すばらしく仕事に身の入らない環境なのです(オイ、コラ)。

今の部屋はもともと広くはないですが、ガラクタとデッドスペースのせいで余計に狭くなっているので、整理すれば、もう少し仕事場っぽくできるでしょう。そもそもここは、(ほぼ一人でいるから当たり前だが)公私混同状態なので、分室のほうを檜山個人使用にして、今のところをofficialなofficeにしようかと考えてます。

それでしばらくは、ガラクタ破棄日記でも書こうか、と。

*1:工作員はいるんですが、工作員の任務は工作活動(って、ワケワカラン)なので別な話なのです。

*2:いやまー、結局僕がやらざるをえないんだけど。

bonotakebonotake 2007/07/22 01:49 そもそも、檜山さんの事務所ってどんな仕事があるんですか??
…それが書けるんだったら最初から求人広告出してる、とかそういう状況なんでしょうか。もしかして。

m-hiyamam-hiyama 2007/07/23 09:08 bonotakeさん、
> そもそも、檜山さんの事務所ってどんな仕事があるんですか??
やることは普通のことですよ。プログラミング、調べもの、資料・文書の作成とか。今までは、8割僕がやって、2割をアシスタントに手伝ってもらう感じだったんですが、今回事情が変わるのは、2割僕がやって、8割を任せられる人(人々)を求めていることですね。(ちなみに、外注は原理的に不可能なことです。)

> …それが書けるんだったら最初から求人広告出してる、とかそういう状況なんでしょうか。もしかして。
いや、そんなことではないです。プロジェクトにネタが含まれるので、ネタバレすると笑ってもらえない、ということはありますが、それを除いた情報は公開できます。

2007-01-23 (火)

スクリプティング

| 09:29 | スクリプティング - 檜山正幸のキマイラ飼育記 を含むブックマーク

やって、やって。

個人的には、ヘボでもなんでもコマンドラインシェルがあれば満足。

Homma_KainaHomma_Kaina 2007/01/24 01:29 やがて「すごく良い」→「気持ちいい」となり、語源がすっかり忘れ去られた後で、俗語辞典に、語源として「『キモイ』=『気持』ちい『い』の略」なんて書かれたりして。

m-hiyamam-hiyama 2007/01/24 09:30 Homma_Kainaさん、
で、『あるある俗語辞典』の語源はイイカゲンだ、とか問題になったりして。