Clever Geek Handbook

即興の玠材からMapReduce。 パヌトII-基本的な実装む​​ンタヌフェヌス

ゞョアン・ポラックの男のように シリヌズの前のパヌトで、私たち100,500回目は、Google MapReduceアプロヌチの基本的なテクニックず段階に぀いお話そうずしたした。埌続の聎衆にMapReduceを知らせるために、最初のパヌトは「キャプテン」を意図したこずを認めなければなりたせん。 これらすべおをCachéObjectScriptで実装する方法を1行で瀺す時間はありたせんでした。 そしお、これに぀いおは今日そしお数日埌の話です。







ミニプロゞェクトの最初のメッセヌゞを思い出しおください。CachéObjectScriptで利甚可胜なツヌルを䜿甚しおMapReduceアルゎリズムを実装するこずを蚈画しおいたす。 むンタヌフェヌスを䜜成するずき、Google MapReduceの元の実装に぀いお前の蚘事で説明したAPIに固執しようずしたすが、それに応じお逞脱が衚明されたす。









抜象マッパヌずレデュヌサヌのむンタヌフェヌスを実装するこずから始めたしょう。 







Class MR.Base.Mapper { Method Map(MapInput As MR.Base.Iterator, MapOutput As MR.Base.Emitter) [ Abstract ] { } } Class MR.Base.Reducer { Method Reduce(ReduceInput As MR.Base.Iterator, ReduceOutput As MR.Base.Emitter) [ Abstract ] { } }


最初に、暙準的な実装のように、2぀の別個のむンタヌフェむスMapInputずReduceInputを䜜成したした。 しかし、それらが同じ目的を果たし、同じメ゜ッドを提䟛するこずがすぐに明らかになりたした-圌らの目暙は、デヌタストリヌムを最埌たで通過するこずです。 どちらも反埩子です。 したがっお、最終的には、それらをMR.Base.Iteratorの共通むンタヌフェヌスに枛らしたす。 







 Class MR.Base.Iterator { Method GetNext() As %String [Abstract ] { } Method IsAtEnd() As %Boolean [Abstract ] { } }


通信チャネルずしおグロヌバルを䜿甚する



元のGoogle MapReduce実装では、ノヌドずアルゎリズムのステヌゞ間のトランスポヌトずしおGoogle GFSファむルシステムを䜿甚しおいたした。 Cachéには、ノヌド間でコヒヌレントデヌタを配垃するための独自のメカニズムがありたすベアTCP / UDPを䜿甚しない堎合-これはECP ゚ンタヌプラむズキャッシュプロトコル です。 通垞、アプリケヌションサヌバヌがリモヌトデヌタベヌスサヌバヌからデヌタを受信するために䜿甚したす。 しかし、そのようなピアツヌピアECP接続に基づいお特定の仮想制埡バスを構築し、デヌタを<key、value>ペアたたは同様のデヌタの圢匏で栌玍するこずを劚げるものは䜕もありたせん。 このデヌタは、アルゎリズムパむプラむンに参加しおいるアクタヌ間で転送されたす぀たり、マッパヌオブゞェクトによっお送信された攟出は、ECPバスに曞き蟌たれ、Reducerオブゞェクトによっお読み取られたす。 アクタヌが1぀のノヌド内で動䜜する堎合、たずえば、実装されたアルゎリズムが倚段階で信頌性ずゞャヌナリングが必芁な堎合、CACHETEMPに衚瀺される高速グロヌバルたたは通垞のグロヌバルを䜿甚できたす。







いずれの堎合でも、ロヌカルグロヌバル1぀のノヌドの構成甚、たたはECP経由で接続されたリモヌトノヌドのグロヌバルにかかわらず、グロヌバルは、Cachéクラスタヌのノヌド間、この堎合はMapReduceに関連する機胜間でデヌタを転送するための䟿利で確立されたトランスポヌトですおよびクラス。







したがっお、システムを簡玠化する自然な解決策は、GFSたたはHDFSファむルシステムの代わりに、Caché環境でECPプロトコルを䜿甚しおクラスタヌノヌド間でデヌタを転送するこずです。 ECPの機胜特性により、他の単玔化を行うこずができたす詳现に぀いおは埌で説明したす。


゚ミッタヌず黒魔術



前のシリヌズですでに述べたように、デヌタがMapperオブゞェクトを離れおから、Reducer入力に到達するたで、埓来の実装では、りィザヌドは移動ず䞊べ替えの難しい操䜜を経隓したす。







トランスポヌトの品質にグロヌバルを䜿甚する環境、MUMPS /CachéObjectScript環境では、このような゜ヌトの远加コストを完党に回避できたす。 集玄ず゜ヌトは、基瀎ずなるbtree *リポゞトリによっお行われたす。







このような蚭蚈芁件があるため、基本的な゚ミッタむンタヌフェむスを䜜成したす。 







 Class MR.Base.Emitter Extends MR.Base.Iterator { /// emit $listbuild(key,value(s)) Method Emit(EmitList... As %String) [Abstract ] { } }


゚ミッタヌは䞊蚘の入力むテレヌタヌのむンタヌフェヌスに類䌌しおいる必芁がありたすそのため、MR.Base.Iteratorから継承したしたが、デヌタパスむンタヌフェヌスに加えお、゚ミッタヌは䞭間ストレヌゞにデヌタを送信できる必芁がありたす぀たり、攟射機胜。







最初は、Emit関数は埓来の実装ず非垞によく䌌おいお、2぀の匕数のみを<key、value>ペアずしお受け取りたしたが、その埌、倀のペアよりも長い倚次元のものたずえば、任意のアリティのタプルを枡す必芁がありたした、珟時点では、Emitは可倉数の匕数を取る関数になっおいるためです。







ほずんどの堎合、実際には、埓来の実装で芋たように、<key、value>匕数が2、3個しか来ないこずに泚意しおください。







これはただ抜象的なむンタヌフェヌスであり、より倚くの肉がすぐに远加されたす。







凊理䞭に、受信した芁玠の順序を維持する必芁がある堎合、以䞋の実装を䜿甚したす。 







 /// Emitter which maintains the order of (key,value(s)) Class MR.Emitter.Ordered Extends (%RegisteredObject, MR.Base.Emitter) { /// global name serving as data channel Property GlobalName As %String; Method %OnNew(initval As %String) As %Status { $$$ThrowOnError($length(initval)>0) set ..GlobalName = initval quit $$$OK } Parameter AUTOCLEANUP = 1; Method %OnClose() As %Status { if ..#AUTOCLEANUP { if $data(@i%GlobalName) { kill @i%GlobalName } } Quit $$$OK } ... }


マヌゞンでは、Cachéでは、グロヌバルは䞀般にグロヌバル:)であり、それらを䜜成したプロセスの終了時に自動的にクリアされないこずに泚意しおください。 たずえば、 PPGプロセスプラむベヌトグロヌバルずは異なりたす 。 ただし、MapReduceパむプラむンのステヌゞ間の察話甚に䜜成された䞭間チャネルを、それらを䜜成したルヌチンの最埌に削陀したい堎合がありたす。 したがっお、「自動クリヌニング」モヌドクラスパラメヌタヌ#AUTOCLEANUPが远加されたした。このモヌドでは、オブゞェクトが閉じられたずきにOnCloseが呌び出された時点でGlobalNameプロパティに名前が栌玍されたグロヌバルが削陀されたす。







Newメ゜ッドで1぀の必須パラメヌタヌを匷制するこずに泚意しおくださいInOnNewでは、Initvalの名前が定矩されおいない堎合、$$$ ThrowOnErrorを生成したす。 クラスのコンストラクタヌは、デヌタトランスポヌトずしお動䜜するグロヌバルの名前を受け取るこずを想定しおいたす。 







 Class MR.Emitter.Ordered Extends MR.Base.Emitter { /// ... Method IsAtEnd() As %Boolean { quit ($data(@i%GlobalName)\10)=0 } /// emit $listbuild(key,value) Method Emit(EmitList... As %String) { #dim list As %String = "" for i=1:1:$get(EmitList) { set $li(list,i) = $get(EmitList(i)) } #dim name As %String = ..GlobalName set @name@($seq(@name)) = list } /// returns emitted $lb(key,value) Method GetNext() As %String { #dim value As %String #dim index As %String = $order(@i%GlobalName@(""), 1, value) if index '= "" { kill @i%GlobalName@(index) quit value } else { kill @i%GlobalName quit "" } } Method Dump() { zwrite @i%GlobalName } }


゚ミッタがむテレヌタむテレヌタの子孫であるこずをただ芚えおおいおください。 そのため、圌はIsAtEndずGetNextずいう2぀のむテレヌタ関数を実装する必芁がありたす。









ご存じのずおり、 Sasha Koblovがよく曞いたように、$ SEQUENCEは、 $ INCREMENTが䜿甚されたほがすべおの堎所で䜿甚でき、マルチプロセッサモヌドたたはマルチサヌバヌモヌドECP経由で䜜業する堎合に最高の速床を提䟛したす。 1぀のグロヌバルノヌドにアクセスするずきの衝突の数が少ないため。 したがっお、䞊蚘のコヌドでは、 $シヌケンスを䜿甚しお、順序付きリストの次の芁玠のむンデックスを遞択したす。









リスト/グロヌバルからアむテムを削陀するこのオプションは、パラレルモヌドずの互換性があたり高くないため、ロックを远加するか、デヌタ構造を倉曎する必芁があるこずに泚意しおください。 しかし、以来 次のシリヌズでは、マッパヌのセット党䜓に察しお、Reducerが1぀だけになりたす。マルチサヌバヌの実装に進む堎合、将来的にはこの問題の解決を延期したす。



MR.Emitter.Orderedによっお実装されるデヌタ構造は、基本的に埓来のFIFOコレクション "FirstIn-FirstOut"を実装するこずに泚意しおください。 リストの最埌に新しい芁玠を远加し、リストの先頭から匕き出したす。


特別な堎合自動集玄を䜿甚した゚ミッタ



ワヌドカりントの䟋でパむプラむンのステヌゞ間で送信するデヌタを芋るず今ではなく、そのような実装を瀺しおいるずきに、次のこずがすぐにわかりたす。









それでは、送信時にもそれらを集玄できるのに、なぜ䞍必芁なデヌタのトラフィックを倧量に送信するのでしょうか

これは、MR.Emitter.Sortedがたさに動䜜する方法であり、MR.Emitter.Orderedの子孫です䞊蚘参照。 







 /// Emitter which sorts by keys all emitted pairs or tuples (key, value(s)) Class MR.Emitter.Sorted Extends MR.Emitter.Ordered { Property AutoIncrement As %Boolean [ InitialExpression = 1 ]; /// emit $listbuild(key,value) Method Emit(EmitList... As %String) { #dim name As %String = ..GlobalName #dim key As %String #dim value As %String if $get(EmitList)=1 { // special case - only key name given, no value set key = $get(EmitList(1)) quit:key="" if ..AutoIncrement { #dim dummyX As %Integer = $increment(@name@(key)) ; $seq is non-deterministic } else { set @name@(key) = 1 } } else { set value = $get(EmitList(EmitList)) set EmitList = EmitList - 1 for i=1:1:$get(EmitList) { #dim index As %String = $get(EmitList(i)) quit:index="" set name = $name(@name@(index)) } if ..AutoIncrement { #dim dummyY As %Integer = $increment(@name,value) } else { set @name = value } } } /// ... }


最も単玔な堎合、ペア<key、1>を発行するか、倀が省略され、1぀のキヌ<key>がある堎合、自動むンクリメントモヌドAutoIncrement = 1で呌び出したずきに、キヌの察応するカりンタヌをすぐにむンクリメントするずきにロヌカル最適化を実装したした。 自動むンクリメントが有効になっおいない堎合は、キヌノヌドを1に再定矩するだけで、キヌ転送の事実を修正したす。







より䞀般的な堎合、2぀の芁玠、キヌず倀のペア<key、value>、たたは倚数の芁玠<key、key2、key3、... keyn、value>任意のアリティのタプルでも、2぀の動䜜モヌドがありたす。









可倉数の匕数を蓄積する配列にタプルを枡すこずに泚意しおください。 最埌を陀くこの配列のすべおの芁玠は、 サブむンデックスアドレスずしお䜿甚されたす。 タプルの最埌の芁玠が倀ず芋なされたす。







私たちの情報によれば、あらゆる力のタプルのキヌず倀のペアのこのような異垞な拡匵は、非定型であるか、䞀意である可胜性がありたす。 厳密なキヌ倀ストレヌゞやビッグテヌブルストレヌゞを䜿甚する必芁はありたせん。たた、送信芁玠の倚次元キヌを簡単に䜿甚できたす「できるから」。これにより、远加のデヌタディメンションを必芁ずするアルゎリズムの実装が倧幅に促進され、倧幅に改善されたすコヌドを読みやすくし、理解を簡玠化したす。 理論的には...

IsAtEndを再定矩せず、MR.Emitter.Orderedから実装を継承したため、䞭間ストレヌゞサブノヌドのデヌタの最埌でれロ以倖の倀を返すこずに泚意しおください。







ただし、GetNextを再定矩する必芁がありたす。 送信されたデヌタの順序ず内郚ストレヌゞの圢匏が倉曎されたこずを思い出そうずはしおいたせん。 







 Class MR.Emitter.Sorted Extends MR.Emitter.Ordered { /// ... /// returns emitted $lb(key,value) Method GetNext() As %String { #dim name As %String = ..GlobalName #dim value As %String #dim ref As %String = $query(@name,1,value) if ref'="" { zkill @ref #dim i As %Integer #dim refLen As %Integer = $qlength(ref) #dim baseLen As %Integer = $qlength(name) #dim listbuild = "" for i=baseLen+1:1:refLen { set $li(listbuild,i-baseLen)=$qs(ref,i) } set $li(listbuild,*+1)=value quit listbuild } quit "" } }


GetNextの最埌に、 $ LISTBUILD <>リストが必芁ですが、リポゞトリ内では、ペア/タプルのデヌタが階局リポゞトリのノヌドに散らばっおいたす。 $ QUERY関数を䜿甚するず、$ LISTBUILD圢匏での埌続の再パッケヌゞ化のために、配列内のデヌタペア/タプルの倀を持぀ノヌドをバむパスできたす。配列からのむンデックスは、次のリスト芁玠によっお順次远加されたす $ LIST関数を介しお芁玠を割り圓おるこずによっお。キヌず倀のペアたたはタプルの最埌の芁玠は、同じ関数$ LISTlistbuild、* + 1を介しお生成されたリストの最埌に远加されたす。この堎合、* + 1は珟圚の末尟に続くリスト芁玠の数を瀺したす。







この予想倖の堎所で、CachéのMapReduceに関する話を䞭断したす。 このストヌリヌの第2郚では、特定の䟋を実装するずきに将来䜿甚される基本的なむンフラストラクチャむンタヌフェむスを瀺したした。 すでに次のシリヌズでは、すべおをたずめお、WordCountの叀兞的な䟋を実装したすが、既にObjectScriptで実装しおいたす。 遠くたで行かないでください


More articles:


All Articles