MapReduceは強力なバッチ処理を行う分散システムですが、
現在はさまざまなシステムがWebサービスとして展開されており、
そして、
- サーバにぶら下がる多くのクライアントPC
- ↓
- サーバから見た場合、
多くのクライアントPC＝計算機リソース - ↓
- NameNodeにぶら下がるDataNode群
という関係性に置き換えられないだろうか？ という単純な発想の元、
システム概要
HadoopとJadoopの違いは図1のようになります。
Hadoopの場合はデータの保存時にデータブロックごとにDataNodeに分割保存されます。MapReduce指示を受け、
Jadoopの場合はデータの管理は全てサーバサイドで行っており、
Map処理について
サーバサイドではMapしたいデータについてPCからのリクエストに応じて分割ダウンロードさせます。データ形式はJSONを使用し、
PCではmap処理用のJavaScript関数により、
Mapしたいデータについて全て処理が終わったモノがMapの結果として保存され、
Reduce処理について
Reduceも基本的にMapと同じですが、
これで生成されたReduceしたいデータはMapと同じようにPCからの要求に応じて分割してダウンロードされます。このときのデータ形式はJSONですが、
PCではreduce処理用のJavaScriptの関数を通してキーとバリューのリストを処理し、
処理の流れと実装
以下はワードカウントのためのJadoopの実装となります。
入力データ
1, wakimoto takeshi
2, wakimoto hajime
3, beat takeshi
4, neet kiyoshiキーは行番号、
出力データ
hajime,1
kiyoshi,1
takeshi,2
beet,1
neet,1
wakimoto,2それぞれの単語と単語の出現個数がキーとバリューで表現されています。
コンストラクタ
今回はJadoop.
26 var j = new Jadoop("wordcount", //このクライアントで処理したい種別
34 "http://localhost/test-cgi/jadoop/cgi/mapGet.cgi", // mapするデータの取得
35 "http://localhost/test-cgi/jadoop/cgi/mapPost.cgi", // map関数の戻り値をポストする
36 "http://localhost/test-cgi/jadoop/cgi/redGet.cgi", // reduceするデータの取得
37 "http://localhost/test-cgi/jadoop/cgi/redPost.cgi", // reduce関数の戻り値をポストする
38 "http://localhost/test-cgi/jadoop/cgi/getTask.cgi" // 種別ごとのred, mapするタスクのIDを取得
39 );
40 ここではwordcoutという種別で各種入出力のためのCGIを定義しています。
Map関数
コンストラクタで定義したmapするデータの取得CGIで得られるデータのキーとバリューのペアごとに呼び出される関数です。この例では、
42 // map関数
43 var wordcoundMap = function(key, val)
44 {
45 var res = new Array();
46
47 // 分かち書きライブラリ
48 var segmenter = new TinySegmenter(); // インスタンス生成
49 var segs = segmenter.segment(val);
50
51 $.each(segs, function(i, a){
52 res.push([a,1]);
53 });
54
55 if ( segs.length == 0 )
56 {
57 res.push(["",1]);
58 }
59
60 return res;
61 }ここではTynySegmenterという分かち書きのjsライブラリを使用しています。与えた文字列をこのライブラリで分かち書きし、
1行目を例にすると、
- [[wakimoto,1],[takeshi, 1]]
という配列を生成していることになります。
mapするデータ全てに処理を適用後、
Reduce関数
Reduce関数はMap処理が全て済んでから呼び出されます。(サーバサイドで全てのMap処理が終わった事を検知してReduce用のデータをダウンロードさせる)
reduceするデータの取得で得られたデータはキーごとにグルーピングされ、
- [takeshi, [1,1]]
63 // reduce関数
64 function wordcoundRed(key, val)
65 {
66 var res = new Array();
67
68 var vals = val.length;
69
70 return [key, vals];
71 }この処理ではキーごとの出現回数をカウントするだけなので単純にvalのlengthを取得し、
全てのreduceするデータの処理が終わった後、
Jadoopへのセットと実行
Jadoopオブジェクトにmapper, reducerとして登録し、
74 j.setMap(wordcoundMap);
75 j.setRed(wordcoundRed);
80 setInterval('j.doMapRed()', 10000);この例では10秒ごとにmapデータのダウンロード、
このようなjsを自分のWebページに仕込むことで、
実装しての感想
キーとバリューというデータ構造、
今回作成したJadoopですが、
Hadoopとの違いは、
- リアルタイムでデータをダウンロードさせるため小さいサイズに限られる
- 大容量データを処理するにはより多数のクライアントが必要
- より多数のクライアントによってサーバ側がボトルネックになるかも
- JavaScriptに依存した処理しかできない
というところでしょうか。またサーバサイドの実装も必要なため、
最後に今回作成したJadoop.
var Jadoop = function(id, mapTaskGetURL, mapResPostURL, redTaskGetURL, redResPostURL, getTaskURL)
{
this.id = id;
this.maxCount = 100;
Jadoop.prototype.mapTaskGetURL = mapTaskGetURL;
Jadoop.prototype.mapResPostURL = mapResPostURL;
Jadoop.prototype.redTaskGetURL = redTaskGetURL;
Jadoop.prototype.redResPostURL = redResPostURL;
Jadoop.prototype.getTaskURL = getTaskURL;
Jadoop.prototype.mapOut = new Array();
Jadoop.prototype.redOut = new Array();
}
Jadoop.prototype.setMap = function(f)
{
Jadoop.prototype.map = f;
}
Jadoop.prototype.setRed = function(f)
{
Jadoop.prototype.red = f;
}
Jadoop.prototype._getTask = function(kind)
{
if ( kind == "map" )
{
$.getJSON(
Jadoop.prototype.getTaskURL,
{"proc":0, "id": this.id},
function(data){
if ( data[0] == "" ) return false;
Jadoop.prototype._doMap(data[0]);
}
);
}
else if ( kind == "red" )
{
$.getJSON(
Jadoop.prototype.getTaskURL,
{"proc":1, "id": this.id},
function(data){
if ( data[0] == "" ) return false;
Jadoop.prototype._doRed(data[0]);
}
);
}
}
Jadoop.prototype._doRed = function(tid)
{
$.getJSON(
this.redTaskGetURL,
{"tid":tid},
this._Red
);
}
Jadoop.prototype._Red = function(data)
{
Jadoop.prototype.redOut.length = 0;
$.each(data, function(i, d){
var tid = d[0];
var key = d[1];
var val = d[2];
var ret = Jadoop.prototype.red(key, val);
Jadoop.prototype.redOut.push([d[0], ret[0], ret[1]]);
});
var vars = $.toJSON(Jadoop.prototype.redOut);
$.ajax({
type:"POST",
url: Jadoop.prototype.redResPostURL,
data: "data="+vars,
success: function(msg){
}
});
}
Jadoop.prototype._doMap = function(tid)
{
$.getJSON(
this.mapTaskGetURL,
{"tid":tid},
this._Map
);
console.log(this);
}
Jadoop.prototype.doMapRed = function()
{
this._getTask("map")
this._getTask("red")
}
Jadoop.prototype._Map = function(data)
{
Jadoop.prototype.mapOut.length = 0;
$.each(data, function(i, d){
var tid = d[0];
var rid = d[1];
var key = d[2];
var val = d[3];
var ret = Jadoop.prototype.map(key, val);
$.each(ret, function(i, data){
Jadoop.prototype.mapOut.push([tid, rid, data[0], data[1]]);
});
});
var vars = $.toJSON(Jadoop.prototype.mapOut);
$.ajax({
type:"POST",
url: Jadoop.prototype.mapResPostURL,
data: "data="+vars,
success: function(msg){
}
});
}