数百ものプログラムを同時に実行するには?

質問

並行処理の事を考えています。

初期のGoogleは１台のコンピュータで300ものクローラーを同時に動かしていたというようなことをある記事で読んだ記憶があります。
その事を思い出して考えてみたのですが、実装の方法が思いつきません。

例えばCなどのプログラミングでも、PHPなどのスクリプトでも、forkを使用すれば（for文などの中にクローラ用の関数入れてopenMPなどでも出来るかも）可能かもしれませんが、それだと処理が全て終わるまで待たないといけないのと、エラーがあった時の挙動は300も子プロセス使ってると実装が大変じゃないかなと思いました。

逆に、一つプログラムを書いて、cronにて大量に一気に実行する方が簡単じゃないかなと思いました。
でもそれでは終了時に止まって連続的な挙動はしないでしょう。

このような並行処理はどのようにして実行すればいいのでしょうか？
forkを使うとしても、いったいどのタイミングで呼び出せばいいのか思いつきません。
アドバイス頂けたらと思います。

クローラーに関する情報が自分の調べ方では出てこなかったのですが、何かいい資料などありましたら、そちらも教えていただけたらありがたいです。
英文サイトなどでも大丈夫です。

回答No.6

chie65536（@chie65535） · ベストアンサー

＞ただ、自分がお聞きしたかったことは、起動プログラムの事でした。

起動プログラムは以下のようになるでしょう。

pid_t pid[300],rpid;
int status;
for (int i = 0;i < 300;i++)
{
　pid[i] = fork();
　if (pid[i] < 0) {
　　//fork error
　　continue;
　} else if (pid == 0) {
　　//自分は子プロセス

　　//クローラーを起動。execl(),execv()などを使う
　　exec**(～～～);

　　//exec error
　　exit(-1);
　}
}

//子プロセスが常に300個になるように保つ処理
for(;;)
{
　//子プロセスのどれかが終了するまで待つ
　rpid = waitpid(-1,&status,0);

　//以降、rpidのプロセスの終了状態を調べ、後始末する

　//どのプロセスが終了したか、pid配列とrpidを比較
　for (int i = 0;i < 300;i++)
　{
　　if (rpid == pid[i])
　　{
　　　//pid[i]が終了してしまったプロセスなので、再起動
　　　pid[i] = fork();
　　　if (pid[i] < 0) {
　　　　//fork error
　　　　continue;
　　　} else if (pid == 0) {
　　　　//自分は子プロセス

　　　　//クローラーを起動。execl(),execv()などを使う
　　　　exec**(～～～);

　　　　//exec error
　　　　exit(-1);
　　　}
　　}
　}
}

なお、上記サンプルはデバッグもテストもしてない（というか、コンパイルさえしてない）ので、正常に動く保証はありません。手抜きで無限ループして終了する方法も無いですし。

なので「こういう風に書く」と言うサンプルとして参考にして下さい。

あと、起動プログラムとクローラープログラムは「別の実行ファイルにして、別々に作成」しましょう。

こうすると、クローラーは「致命的エラーが無い限り、クロールだけをし続け、致命的エラーがあったら後始末をしてから終了する」という作り方をすれば良いので、その方が簡単です。

お礼

サンプルのソースまであげて頂きまして、本当にありがとうございました。
やはりコードは分かりやすいです。
概要が見えました。
ありがとうございました。

回答No.5

wormhole

>つまり、起動させるプログラムは一つと言うことですよね。

そういうことです。

>で、その子プロセスのpidを管理し、エラーなどまで監視する。

「エラーなどまで監視する」というわけではなく
waitpidなどのwait系システムコールはステータスが変化したプロセスのpidと、
どういうステータス変化が起きたのかがわかりますから、
それで判断するだけです。

お礼

何度もお答えいただきまして、本当にありがとうございます。
ここの質問欄でだいたい自分の考えるべき筋道が見えてきました。
ありがとうございました。

回答No.4

chie65536（@chie65535）

追記と訂正。

＞すると

＞A－１：○年○月○日に解析して、今は誰も何もしてない。

＞Ａ－２：誰かがクロール中で、解析中になっている。

＞のどちらかの答えがデータベースから返ります。

Ａ－３：そのURLはデータベースに無い。

もありました。Ａ－３の場合は、データベースに「今、自分が解析中」とＵＲＬを登録してから、解析に入ります。

回答No.3

chie65536（@chie65535）

平行処理しても、単独処理しても「結果は１つ」です。

クローラーに限った話ではないですが、何をしたとしても「結果を１つ残す」のは間違いありません。

それら「結果」を格納する場所は、通常、排他制御されたデータベースを使います。

クローラーの誰か一人が「とあるURL」を調べようと思いました。

その場合、データベースに問い合わせて「このURLは、今、どうなってる？」と聞きます。

すると

A－１：○年○月○日に解析して、今は誰も何もしてない。

Ａ－２：誰かがクロール中で、解析中になっている。

のどちらかの答えがデータベースから返ります。

Ａ－１の答えだった場合は「今から俺がクロールする」とデータベースを更新して、解析し、解析が終わったら「今日、解析した」とデータベースを再更新します。

この時、もし「データベース内のページ最終更新日」と「実際に見に行ったページの更新日」が同じだったら、実際の解析はしません。

解析中に「データベースに無いＵＲＬのリンク先」を見付けたら、それをデータベースに登録し「まだ解析してない」と言う状態にします。

Ａ－２の答えだった場合は、何もせず、解析を終わります。

解析が終わって暇になったクローラーは、データベースに「まだ解析してない物が無いか？」と問い合わせて、その中から、最も古くにデータベースに登録した物を選び、次の解析に入ります。

もし、データベースに問い合わせた結果「解析してない物が無い」と言う場合は、データベースにある中から「最後に解析したのが最も古いもの」を選び、、次の解析に入ります。

クローラーを起動して管理するプログラムは「規定数に達するまで、ただ単にクローラーを起動するだけ」と「異常終了したクローラーが居たら、そいつの後始末」だけをします。

クローラーは「結果の集大成」であるデータベースを見ながら、そのデータベースを更新する」と言う作業を、延々と繰り返すだけです。

どんな並列処理プログラムであれ、必ず「たった一つの結果を更新する」に過ぎないので、その「結果の集大成」さえちゃんと「排他処理」しておけば、特に難しい事はありません。

お礼

詳細なご説明、ありがとうございました。
非常に勉強になりました。

ただ、自分がお聞きしたかったことは、起動プログラムの事でした。
数百ものプログラムを一気に動かす為には、一つのメインのプログラムファイル（例えばc言語で書かれたmain.c)を最初に実行して、その中からfork()により（例えば）crawl.cまたはfunction crawl()を子プロセスとして呼び出し実行するのか、

それとも、（1台のパソコンだと仮定して）crawl.cと同時にインデックスを作成するindex.cを一気に沢山実行する方がいいのかと言う事でした。
この場合、crawl.cは止まらない挙動になると思います。
あるサイトを見て解析後urlを確認、DBなどからurl訪問のフラグを確認し、未訪問ならそれらのページヘ自ら訪問、または子プロセスを作成し、自己関数呼び出しとか。

上の方のやり方の方がいいとは思うのですが。

回答No.2

wormhole

自分の考えていることはクローラではないのですが、同じような原理なのでクローラの話でいきますが、
しかし、クローラが終了後に次のurlへ行くのはどのようにしているのでしょうか？
>urlの判断後、同じプロセスが、または子プロセスが訪問しているのではないだろうかと思っていたのですが。
>それとも、１ページを判断、分析後、そのプロセスは終了し、分析して見つけたurlを訪問リストに送り、それを別のプロセスが同じように処理していくと言うことでしょうか?

分析して見つけたurlを記録しておいて、順次自プロセスで辿っていくとかではダメなんですか？
見つけたurlの保存と次に行くべきurlを管理するプロセスを用意しておいて、見つけたurlを記録して貰い次に行くべきurlを教えて貰うとかでもいいでしょうし。

>自分の中ではまとめ役はforkして子プロセスの管理というのしか思い浮かばないのですが。
>最初から300のプロセスを産みだし、正常終了確認後新たなプロセスをfork、エラー発生時はログったりエラー処理をしてexit、そして新たなfork。

エラー発生時のログやエラー処理は、クローラーに任せてはいけないのでしょうか？
まとめ役のプロセスはクローラーを必要な数だけ起動して異常終了したものがあれば起動し直す。
それくらいでいいと思うんですけど。
waitpid()とか使ったことありませんか？

お礼

ご回答ありがとうございます。

つまり、起動させるプログラムは一つと言うことですよね。
そのプログラムが起動中にクローラなど何か処理の実行を行うプログラムを子プロセスとしてfork()により同時実行させると。
で、その子プロセスのpidを管理し、エラーなどまで監視する。
waitpid()は使ったことはあります。

それとも、管理プログラムは置かず、数百ものプログラムを一気に別々に起動させ、（ここではスケーラリングなど分散していないと仮定して）検索エンジンであればインデックス処理などの実行プログラムも同時に別々に動かす...という事ではないですよね？

回答No.1

wormhole

それぞれのクローラーを独立したプロセスで動かし、
それに加えてまとめ役のプロセスが1つあればいいだけだと思いますが。

補足

ご回答ありがとうございます。

独立したプロセスですか。
自分の考えていることはクローラではないのですが、同じような原理なのでクローラの話でいきますが、
しかし、クローラが終了後に次のurlへ行くのはどのようにしているのでしょうか？
urlの判断後、同じプロセスが、または子プロセスが訪問しているのではないだろうかと思っていたのですが。
それとも、１ページを判断、分析後、そのプロセスは終了し、分析して見つけたurlを訪問リストに送り、それを別のプロセスが同じように処理していくと言うことでしょうか?

まとめ役のプロセスですか...
今自分にはイメージが出来ないのですが、そのプロセスはどのような挙動をするものなのでしょうか?
自分の中ではまとめ役はforkして子プロセスの管理というのしか思い浮かばないのですが。
最初から300のプロセスを産みだし、正常終了確認後新たなプロセスをfork、エラー発生時はログったりエラー処理をしてexit、そして新たなfork。
う～ん....