-
Notifications
You must be signed in to change notification settings - Fork 0
/
index.html
412 lines (383 loc) · 16.4 KB
/
index.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8" />
<title>mongoreading mapreduce 概観</title>
<script type="text/javascript" src="./js/shCore.js"></script>
<script type="text/javascript" src="./js/shBrushJScript.js"></script>
<script type="text/javascript" src="./js/shBrushBash.js"></script>
<script type="text/javascript" src="./js/shBrushCpp.js"></script>
<link href="./css/common.css" type="text/css" rel="stylesheet" media="Screen,projection" />
<link href="./css/shCore.css" type="text/css" rel="stylesheet" media="Screen,projection" />
<link href="./css/shThemeDefault.css" type="text/css" rel="stylesheet" media="Screen,projection" />
</head>
<body>
<div class="mod-page top"><div>
<h1 style="font-size: 20pt; text-align: left;">
<pre class="brush: js">> db.presentations.find({author: "muddydixon"})
{
"_id" : ObjectId("4e7c86b120247a53b722c0ae"),
"title": "mapreduce 概観",
"author": "Muddy Dixon",
"twitter": "@muddydixon",
}</pre></h1>
</div></div>
<div class="mod-page plain">
<div>
<h2>自己紹介</h2>
<ul>
<li>大学/大学院:<ul>
<li>自然言語処理:形態素列検索・置換システム</li>
<li>言語発達の計算機シミュレーション(ElmanNet+SOMみたいな)</li>
</ul>
</li>
<li>就職:
<ul>
<li>検索エンジン(の広告最適化とか</li>
<li>コンテンツマッチエンジンの設計開発とか</li>
<li><a href="http://twitter.com/nifty_engineer">エンジニアサポート</a>の中の人とか</li>
<li>データマイニング<s>部門</s>個人</li>
</ul>
</li>
</ul>
</div>
</div>
<div class="mod-page shout">
<div>
<p>僕はC++ができません。<br />できないなりに読んだ結果です。</p>
</div>
</div>
<div class="mod-page plain">
<div>
<h2>> db.pages.find({}, {title: 1})</h2>
<ul>
<li>ターゲットファイル</li>
<li>フロー概略</li>
<li>個別概略
<ul>
<li>State</li>
<li>Config</li>
<li>JSMapper</li>
<li>JSReducer</li>
</ul>
</li>
</ul>
</div>
</div>
<div class="mod-page plain">
<div>
<h2>> db.pages.find({title: "ターゲットファイル"})</h2>
<ul>
<li>mongo/db/commands/mr.cpp</li>
<li>mongo/db/commands/mr.h</li>
</ul>
</div>
</div>
<div class="mod-page plain">
<div>
<h2>> db.pages.find({title: "準備"})</h2>
<ul>
<li>とりあえずすべてのメソッドに下記コードを注入
<pre class="brush: cpp">log() << typeid(this).name() << "::" << __func__ << endl;</pre>
</li>
<li>これをやっておくと、logから「どのクラスのどのメソッドが呼ばれたか」をトレースできます。(デバッガ苦手です・・・)</li>
<li>最初はverbose切っておきます</li>
</ul>
</div>
</div>
<div class="mod-page plain">
<div>
<h2>> db.pages.find({title: "フロー概略"}).limit(1)</h2>
<pre class="brush: bash">Mon Oct 17 01:55:10 [initandlisten] connection accepted from 127.0.0.1:65122 #1 (1 connection now open)
Mon Oct 17 01:55:10 [conn1] PN5mongo2mr16MapReduceCommandE::run // <= MR起動
Mon Oct 17 01:55:10 [conn1] PN5mongo2mr6ConfigE::Config // <= Configオブジェクト作成
Mon Oct 17 01:55:10 [conn1] PN5mongo2mr10JSFunctionE::JSFunction // <= mapper用関数オブジェクト作成
Mon Oct 17 01:55:10 [conn1] PN5mongo2mr10JSFunctionE::JSFunction // <= reducer用関数オブジェクト作成
Mon Oct 17 01:55:10 [conn1] PN5mongo2mr5StateE::State // <= Stateオブジェクト作成
Mon Oct 17 01:55:10 [conn1] PN5mongo2mr5StateE::sourceExists // <= dbのリソース確認
Mon Oct 17 01:55:10 [conn1] PN5mongo2mr5StateE::init // <= State初期化
Mon Oct 17 01:55:10 [conn1] PN5mongo2mr8JSMapperE::init // <= Mapper初期化
Mon Oct 17 01:55:10 [conn1] PN5mongo2mr10JSFunctionE::init // <= (Mapper)関数初期化
Mon Oct 17 01:55:10 [conn1] PN5mongo2mr9JSReducerE::init // <= Reducer初期化
Mon Oct 17 01:55:10 [conn1] PN5mongo2mr10JSFunctionE::init //<= (Reducer)関数初期化
Mon Oct 17 01:55:10 [conn1] PN5mongo2mr5StateE::switchMode // <= jsModeのチェック
Mon Oct 17 01:55:10 [conn1] PN5mongo2mr5StateE::prepTempCollection // <= mr出力用一時コレクション作成
Mon Oct 17 01:55:10 [conn1] CMD: drop test.tmp.mr.in_0_inc // <= 一時コレクションdrop
Mon Oct 17 01:55:10 [conn1] build index test.tmp.mr.in_0_inc { 0: 1 } // <= 一時コレクションインデックス貼り
Mon Oct 17 01:55:10 [conn1] build index done 0 records 0 secs
Mon Oct 17 01:55:10 [conn1] CMD: drop test.tmp.mr.in_0
Mon Oct 17 01:55:10 [conn1] build index test.tmp.mr.in_0 { _id: 1 }
Mon Oct 17 01:55:10 [conn1] build index done 0 records 0 secs
Mon Oct 17 01:55:10 [conn1] PN5mongo2mr5StateE::insert // <= system.indexesにnsとかの情報を書き込み(たぶん、このへんで、mrのoutをshardする、みたいのがあると思うけど、未追跡・・・</pre>
</div>
</div>
<div class="mod-page plain">
<div>
<h2>> db.pages.find({"cls.mthd": "MapReduceCommand::run"})</h2>
<span>1040行目あたり</span>
<pre class="brush: cpp">state.init(); // (1)
state.prepTempCollection(); // (2) </pre>
<span>1060行目あたり</span>
<pre class="brush: cpp">shared_ptr<Cursor> temp = NamespaceDetailsTransient::getCursor( config.ns.c_str(), config.filter, config.sort ); // (3)
auto_ptr<ClientCursor> cursor( new ClientCursor( QueryOption_NoCursorTimeout , temp , config.ns.c_str() ) ); // (4)</pre>
<span>1070行目あたり</span>
<pre class="brush: cpp">while ( cursor->ok() ) { // (5)</pre>
<span>1070行目あたり</span>
<pre class="brush: cpp">state.reduceInMemory(); // (6)</pre>
<ol>
<li>
stateを初期化。内部では設定の各種読み込み(verboseやoutのモード、mapper/reducer/finalizer関数オブジェクト作成、query/sort/limit指定などを行う)
</li>
<li>
mr中にshow collectionsすれば見られるが、mr結果流し込み用の一時collectionを作成する
</li>
<li>
queryを満たす、documentのcursorのためのobjectを生成
</li>
<li>
queryを満たす、documentのcursorを取得
</li>
<li>
お待ちかねのmap処理
</li>
<li>
そしてreduce処理
</li>
</ul>
</div>
</div>
<div class="mod-page plain">
<div>
<h2>> db.pages.find({"cls.mthd": "Config::Config"})</h2>
<pre class="brush: cpp">mapper.reset( new JSMapper( cmdObj["map"] ) );
reducer.reset( new JSReducer( cmdObj["reduce"] ) );
if ( cmdObj["finalize"].type() && cmdObj["finalize"].trueValue() )
finalizer.reset( new JSFinalizer( cmdObj["finalize"] ) );</pre>
<p>
map/reduceクラスの生成や、outのオプションの処理、query生成、sort、limitとかを行う。
</p>
<p>
あんまり面白くない
</p>
</div>
</div>
<div class="mod-page plain">
<div>
<h2>> db.pages.find({"cls.mthd": "JSFunction::JSFunction"})</h2>
<pre class="brush: cpp">JSFunction::JSFunction( string type , const BSONElement& e ) {
_type = type;
_code = e._asCode();
if ( e.type() == CodeWScope ){
_wantedScope = e.codeWScopeObject();
}
}</pre>
<p>
関数定義を文字列で受け取ってクラス変数に格納
</p>
</div>
</div>
<div class="mod-page plain">
<div>
<h2>> db.pages.find({"cls.mthd": "JSFunction::init"})</h2>
<pre class="brush: cpp">void JSFunction::init( State * state ) {
_scope = state->scope();
assert( _scope );
_scope->init( &_wantedScope );
_func = _scope->createFunction( _code.c_str() );
uassert( 13598 , str::stream() << "couldn't compile code for: " << _type , _func );
// install in JS scope so that it can be called in JS mode
_scope->setFunction(_type.c_str(), _code.c_str());
}</pre>
<p>
スコープを初期化し、関数実体を生成
createFunction自体はengine(spidermonkey || v8 || java などに丸投げ)
</p>
</div>
</div>
<div class="mod-page plain">
<div>
<h2>> db.pages.find({"cls": "State"})</h2>
<pre class="brush: cpp">State::State( const Config& c )
State::~State()
void State::init()
void State::prepTempCollection()
long long State::postProcessCollection()
void State::appendResults( BSONObjBuilder& final )
long long State::postProcessCollectionNonAtomic()
void State::insert( const string& ns , const BSONObj& o )
void State::insertToInc( BSONObj& o )
void State::_insertToInc( BSONObj& o )
bool State::sourceExists()
long long State::incomingDocuments()
void State::switchMode(bool jsMode)
void State::bailFromJS()
void State::finalReduce( BSONList& values )
void State::finalReduce( CurOp * op , ProgressMeterHolder& pm )
void State::reduceInMemory()
void State::dumpToInc()
void State::emit( const BSONObj& a )
void State::_add( InMemory* im, const BSONObj& a , long& size )
void State::checkSize()</pre>
<p>
なんか、機能詰め込みすぎてイミフになってるクラス (全部は追っていません)
</p>
</div>
</div>
<div class="mod-page plain">
<div>
<h2>> db.pages.find({"cls.mthd": "State::State"})</h2>
<p>
Stateオブジェクトにいろんな情報があったり、emitがあったりするので、面白いですが、ここでは格別面白くないです。
</p>
<p>
一点面白いのは、下記の部分で、_onDiskというフラグを持っているところです。これは、あとあといろんな所で出てきます。(だから、なになのかは未追跡)
</p>
<pre class="brush: cpp">_onDisk = _config.outType != Config::INMEMORY;</pre>
</div>
</div>
<div class="mod-page plain">
<div>
<h2>> db.pages.find({"cls.mthd": "State::init"})</h2>
<pre class="brush: cpp">_scope.reset(globalScriptEngine->getPooledScope( _config.dbname ).release() );
_scope->localConnect( _config.dbname.c_str() );
_config.mapper->init( this ); // <= mapper初期化
_config.reducer->init( this ); // <= reducer初期化
if ( _config.finalizer ) // <= finalizerがあれば
_config.finalizer->init( this ); // <= finerlizer初期化
_scope->setBoolean("_doFinal", _config.finalizer);</pre>
<p>
</p>
<pre class="brush: cpp">// by default start in JS mode, will be faster for small jobs
_jsMode = _config.jsMode; // <= v2.0からのjsModeのフラグチェックとかもあります</pre>
</div>
</div>
<div class="mod-page plain">
<div>
<h2>> db.pages.find({title: "フロー概略"}).skip(1).limit(1)</h2>
<pre class="brush: bash">Mon Oct 17 01:55:10 [conn1] PN5mongo2mr5StateE::incomingDocuments
Mon Oct 17 01:55:10 [conn1] PN5mongo2mr8JSMapperE::map // <= map関数起動
Mon Oct 17 01:55:10 [conn1] fast_emit // <= mapperの中のemitはfast_emitに置換されている (injectNative)
Mon Oct 17 01:55:10 [conn1] PN5mongo2mr5StateE::emit // <= fast_emit内でState::emitをcall
Mon Oct 17 01:55:10 [conn1] PN5mongo2mr5StateE::_add // <= State::emit内で_addをcall
Mon Oct 17 01:55:10 [conn1] PN5mongo2mr8JSMapperE::map // <= 以下繰り返し
Mon Oct 17 01:55:10 [conn1] fast_emit
Mon Oct 17 01:55:10 [conn1] PN5mongo2mr5StateE::emit
Mon Oct 17 01:55:10 [conn1] PN5mongo2mr5StateE::_add
Mon Oct 17 01:55:10 [conn1] PN5mongo2mr5StateE::reduceInMemory // <= reduce処理開始
Mon Oct 17 01:55:10 [conn1] PN5mongo2mr9JSReducerE::reduce
Mon Oct 17 01:55:10 [conn1] PN5mongo2mr9JSReducerE::_reduce
Mon Oct 17 01:55:10 [conn1] PN5mongo2mr5StateE::_add
Mon Oct 17 01:55:10 [conn1] PN5mongo2mr5StateE::dumpToInc // <= memory(out: inline)の場合以外は、DISCに書きこむ
Mon Oct 17 01:55:10 [conn1] PN5mongo2mr5StateE::_insertToInc
Mon Oct 17 01:55:10 [conn1] PN5mongo2mr5StateE::finalReduce // <= うっかりtupleが複数ある場合の予防線? + finalizer
Mon Oct 17 01:55:10 [conn1] PN5mongo2mr5StateE::finalReduce
Mon Oct 17 01:55:10 [conn1] PN5mongo2mr9JSReducerE::finalReduce
Mon Oct 17 01:55:10 [conn1] PN5mongo2mr5StateE::insert</pre>
</div>
</div>
<div class="mod-page plain">
<div>
<h2>> db.pages.find({"cls.mthd": "JSMapper::map"})</h2>
<span>JSMapper::map</span>
<pre class="brush: cpp">if ( s->invoke( _func.func() , &_params, &o , 0 , true, false, true ) )</pre>
<span>fast_emit (emitがinjectNativeでfast_emitになっている)</span>
<pre class="brush: cpp">state->emit( b.obj() );</pre>
<span>State::emit</span>
<pre class="brush: cpp">_add( _temp.get() , a , _size );</pre>
<span>State::_add</span>
<pre class="brush: cpp">BSONList& all = (*im)[a];
all.push_back( a );</pre>
<p>
面白かったのは、mongodbのmapReduceで渡したmap関数のemitがinjectNativeでfast_emitされているところ。つまり、ここをいじればemitを思いのままにできたり、その他のメソッドを注入できたりする!
</p>
</div>
</div>
<div class="mod-page plain">
<div>
<h2>> db.pages.find({"cls.mthd": "State::reduceInMemory"})</h2>
<span>JSMapper::map</span>
<pre class="brush: cpp">for ( InMemory::iterator i=_temp->begin(); i!=_temp->end(); ++i ) {
BSONObj key = i->first;
BSONList& all = i->second;
if ( all.size() == 1 ) {
// only 1 value for this key
if ( _onDisk ) {
// this key has low cardinality, so just write to collection
writelock l(_config.incLong);
Client::Context ctx(_config.incLong.c_str());
_insertToInc( *(all.begin()) );
}
else {
// add to new map
_add( n.get() , all[0] , nSize );
}
}
else if ( all.size() > 1 ) {
// several values, reduce and add to map
BSONObj res = _config.reducer->reduce( all );
_add( n.get() , res , nSize );
}
}</pre>
<p>
噂のIterator処理です。一応、iteratorの残サイズをチェックしたりしているのがわかります。size != 1の時にReducerが走っています。言い換えると、すべてがユニークな場合は、reducerは呼ばれない!?
</p>
</div>
</div>
<div class="mod-page plain">
<div>
<h2>> db.pages.find({"cls.mthd": "State::finalReduce"})</h2>
<span>JSMapper::map</span>
<pre class="brush: cpp">if (tuples.size() == 1) {
// 1 obj, just use it
key = tuples[0];
BSONObjBuilder b(key.objsize());
BSONObjIterator it(key);
b.appendAs( it.next() , "_id" );
b.appendAs( it.next() , "value" );
res = b.obj();
}
else {
// need to reduce
int endSizeEstimate = 16;
_reduce( tuples , key , endSizeEstimate );
BSONObjBuilder b(endSizeEstimate);
b.appendAs( key.firstElement() , "_id" );
_func.scope()->append( b , "value" , "return" );
res = b.obj();
}
if ( finalizer ) {
res = finalizer->finalize( res );
}</pre>
<p>
(k, v)が複数存在した場合(shardの時かな?)にmergeする + finalizerがここで発動
</p>
</div>
</div>
<div class="mod-page plain">
<div>
<h2>> db.pages.find({title: "フロー概略"}).skip(2).limit(1)</h2>
<pre class="brush: bash">Mon Oct 17 01:55:10 [conn1] PN5mongo2mr5StateE::postProcessCollection // <= collectionの後処理
Mon Oct 17 01:55:10 [conn1] PN5mongo2mr5StateE::postProcessCollectionNonAtomic
Mon Oct 17 01:55:10 [conn1] CMD: drop test.out
Mon Oct 17 01:55:10 [conn1] PN5mongo2mr5StateE::appendResults // <= 結果(かかった時間とか、map数とか)をオブジェクトに突っ込む
Mon Oct 17 01:55:10 [conn1] PN5mongo2mr5StateE::~State // <= distructor
Mon Oct 17 01:55:10 [conn1] CMD: drop test.tmp.mr.in_0
Mon Oct 17 01:55:10 [conn1] CMD: drop test.tmp.mr.in_0_inc
Mon Oct 17 01:55:10 [conn1] command test.$cmd command: { mapreduce: "in", map: function () {
emit(1, 1);
}, reduce: function (k, vs) {
return vs.length;
}, out: "out" } ntoreturn:1 reslen:127 125ms
Mon Oct 17 01:55:10 [conn1] end connection 127.0.0.1:65122 (0 connections now open)</pre>
</div>
</div>
<hr />
<ul class="mod-pager" id="pager"> <li id="pager-L"><a href="#">L</a></li> <li id="pager-R"><a href="#">R</a></li> </ul>
<p class="mod-pageNum" id="pageNum"> <span class="current" id="pageNum-current">0</span> / <span class="total" id="pageNum-total">0</span> </p>
<script type="text/javascript" src="./js/jquery-1.5.2.min.js"></script>
<script type="text/javascript" src="./js/jquery.presentation.js"></script>
<script type="text/javascript">
SyntaxHighlighter.all();
</script>
</body>
</html>