# HG changeset patch # User one # Date 1287040503 -32400 # Node ID 596cc0a3beea44ba4701335840bfdff6929f11eb # Parent 2107530c3d727f24bd137ce970ad0a39c82db857 new Merge Algorithm diff -r 2107530c3d72 -r 596cc0a3beea Todo --- a/Todo Tue Oct 12 16:17:42 2010 +0900 +++ b/Todo Thu Oct 14 16:15:03 2010 +0900 @@ -1,7 +1,132 @@ +Thu Oct 14 14:27:22 JST 2010 + +でも単純ソートはうまくいかないはず。 + Tue Oct 12 10:37:38 JST 2010 やっぱり二周目に割り込んだコマンドが正しくsortされない。 + Editor3 Editor2 Editor1 + e(eid=2) + e(eid=2) + e(eid=2) + e(eid=2) c(eid=1) + ea(eid=2)* + c(eid=1) + ea(eid=2)* c(eid=1) + ea(eid=2)* c(eid=1) + ca(eid=1)* + ca(eid=1)* + ca(eid=1)* + + [e,c] [e,c] [c,e] + +うーん。 + + Editor3 Editor2 Editor1 + e(eid=2) a(eid=1) + a(eid=1) e(eid=2) + e(eid=2) a(eid=1) + e(eid=2)* c(eid=1) + a(eid=1)* + ea(eid=2)* + c(eid=1) + aa(eid=1)* c(eid=1) + ea(eid=2)* aa(eid=1)* c(eid=1)* + ca(eid=1)* + ca(eid=1)* + + [a,e,c] [a,e,c] [a,e,c] + +他のエディタのコマンドが来た時に、優先順位でいきなりソート(merge)して良い。o + 自分のコマンドは、過去の低い優先順位を追い越さない。 x + 一周(ack)が来たら、そこまでのundoは捨てて順位は固定。 x +既に他のコマンドを送信した後に、自コマンドが来たら、その前までの自編集以外の編集まで確定。o +自コマンドのackで、まだ確定してない場合は確定。o +他コマンドのackは何もしない o +merge 中の自コマンドは、確定させて処理(merge後に送信と同じ) + + Editor3 Editor2 Editor1 + c(eid=3) e(eid=2) a(eid=1) + a(eid=1) c(eid=3) e(eid=2) + e(eid=2) a(eid=1) c(eid=3) + c(eid=3)* e(eid=2)* d(eid=1) <- このd がsortされない必要があるらしい + d(eid=1) ca(eid=3) a(eid=1)* + aa(eid=1)* d(eid=1) ea(eid=2)* + ea(eid=2)* aa(eid=1)* ca(eid=3)* + d(eid=1)* + da(eid=1)* + da(eid=1)* + + [a,e,c,d] [a,e,c,d] [a,e,c,d] + +優先順位1でない場合 + + Editor1 Editor2 Editor3 + c(eid=1) e(eid=2) a(eid=3) + a(eid=3) c(eid=1) e(eid=2) + e(eid=2) a(eid=3) c(eid=1) + c(eid=1)* e(eid=2)* d(eid=3) <- このd がsortされない必要があるらしい + d(eid=3) ca(eid=1) a(eid=3)* + aa(eid=3)* d(eid=3) ea(eid=2)* + ea(eid=2)* aa(eid=3)* ca(eid=1)* + d(eid=3)* + da(eid=3)* + da(eid=3)* + + [c,e,a,d] [c,e,a,d] [c,e,a,d] + +優先順位に関係なく、他コマンドの後の自分のコマンドは +sort しないものらしい。 + +そこにさらに他コマンドが割り込んだ場合は? + + Editor1 Editor2 Editor3 + c(eid=1) a(eid=3) + a(eid=3) c(eid=1) + a(eid=3) c(eid=1) + c(eid=1)* e(eid=2) d(eid=3) <- このe,d がsortされない必要があるらしい + d(eid=3) ca(eid=1)* a(eid=3)* + aa(eid=3)* d(eid=3) e(eid=2) + e(eid=2) aa(eid=3)* ca(eid=1)* + e(eid=2)* d(eid=3)* + da(eid=3)* ea(eid=2)* + ea(eid=2)* da(eid=3)* + + [c,a,e,d] [c,a,e,d] [c,a,e,d] + +e(eid=2) は d(eid=3) を追い越す必要がある。 + + Editor1 Editor2 Editor3 + c(eid=1) a(eid=3) + a(eid=3) c(eid=1) + a(eid=3) c(eid=1) + c(eid=1)* e(eid=2) d(eid=3) <- このe,d がsortされない必要があるらしい + d(eid=3) a(eid=3)* + d(eid=3) e(eid=2) + e(eid=2) + e(eid=2)* d(eid=3)* + + [c,a,e,d] [c,a,e,d] [c,a,e,d] + +もしかして、ack って必要ないの? え〜 + + Editor1 Editor2 Editor3 + c(eid=1) e(eid=2) a(eid=3) + a(eid=3) c(eid=1) e(eid=2) + e(eid=2) a(eid=3) c(eid=1) + c(eid=1)* e(eid=2)* d(eid=3) <- このd がsortされない必要があるらしい + d(eid=3) a(eid=3)* + d(eid=3) + d(eid=3)* + + [c,e,a,d] [c,e,a,d] [c,e,a,d] + +4つの場合の特殊性はある? + + + + Mon Oct 11 22:12:35 JST 2010 あ、そうか。singleton case 中のコマンドは無視されてしまうわけね。SYNC すれば良いはずだが。 diff -r 2107530c3d72 -r 596cc0a3beea rep/handler/Editor.java --- a/rep/handler/Editor.java Tue Oct 12 16:17:42 2010 +0900 +++ b/rep/handler/Editor.java Thu Oct 14 16:15:03 2010 +0900 @@ -37,7 +37,7 @@ public static boolean noMergeMode=false; static final boolean doOptimize = false; private LinkedList writeQueue = new LinkedList(); - static boolean slowMerge = true; + static boolean slowMerge = false; public Editor(SessionManager manager,int editorNo){ // no translator case @@ -63,15 +63,13 @@ /* * Merge Protocol (0) Editor へのコマンドは、ack 以外は直接　Editor へ送られてしまう。(next.send(cmd)) - Editor から返ってくるコマンドをtranslatorが処理する。 - (1) Editor CommandをSession Ring 上に流し、それが戻って来るまでに、他のEditorから - 受け取った Editor Command をキューに入れておく。 - (2) 戻って来たタイミングで、キュー上のEditor Commandを、eid とCommandの - 順序を基にソートする。(self merge) - (3) 他のEditorにソートのタイミングを与えるために、Editor Command の - ack を、もう一周させる。 - (4) 他のEditorのCommandを受け取ってから、ack が来るまでのCommandをキューに - 入れておき、ack が来たら、eid とCommandの順序を基にソートする。(other merge) + Editor から返ってくるコマンドでないとundoできない + (1) 他のEditorからコマンドが来たら優先順位でsort-mergeする + (2) 自分のEditorの入力が来たら、直前のコマンドまでを確定。unMerge list/sentListをclear + (3) 自分の確定のタイミングを与えるために、Editor Command の ack を、もう一周させる + (4) 自ackが確定前のackなら何もしない +　 (5) 自ackの前の確定がないなら、そこまで確定 + (6) 他コマンドのackは何もしない Editor には、ソートした編集結果になるように、それまで行なった編集をUndo して、ソートした編集結果を適用する。Undo が無駄な動作をしないように最適化する。 @@ -135,7 +133,7 @@ //マージコマンドが返ってきた if(checkMergeConflict(command)){ //マージ中にエディタからの割り込みがあった場合 - getMergeAgain(this); + getMergeAgain(); } checkEndMerge(); return; @@ -152,17 +150,21 @@ } //他のエディタからの編集コマンド - transReceiveCmd(next,command); - - sendEditorCommand(command); + unMergedCmds.addFirst(new REPCommand(command)); + startMerge(command); return; default: assert(false); } } + /** + * エディタからの新たな編集コマンド + * 既に他コマンドを受け取っていたら、そこまで確定 + * @param command + */ private void userEditorCommand(REPCommand command) { - //エディタからの新たな編集コマンド + trancateUnMerge(command); if (next==this) return; // singleton case transSendCmd(command); sendEditorCommand(command); @@ -260,27 +262,22 @@ next.send(command); } - public List getSentList() { - return sentList; - } - - public void setSentList(LinkedList list) { - sentList = list; - } - /** * 一周して来たcommandの処理。 - * - * 　　INSERT/DELETEを受け取った時に、sentListに登録 - * INSERT_ACK/DELETE_ACKが来たら一周。そこで、Mergeする。 - * - * 自分が出したINSERT/DELETEが戻って来たら、ACKに変更して、Merge。 - * - * 途中から参加した場合、自分が受けとってないcommandのACKが先に来ることが - * ある。それは、無視して良い。 + * 自分が戻ってきた場合は、そこまで確定。そして、ack を廻す。 * @param command */ void checkReturnedCommand(REPCommand command) { + checkAck(command); + if (command.eid==eid) { + trancateUnMerge(command); + sendAck(command); + } else { + next.send(command); + } + } + + void startMerge(REPCommand command) { ServerMainLoop.logger.writeLog("Editor"+eid+": startMerge "+command); preMergeCommand = new REPCommand(command); // merge は必須だが、EditorのCommand実装をテストするには邪魔なので、off に出来るようにする。 @@ -351,30 +348,39 @@ private void endMerge() { - sortedEditCmds = null; - LinkedListu = new LinkedList(); - boolean flag=true; - for(REPCommand command:unMergedCmds) { - if (command.cmd==REP.REPCMD_MERGE_MARK) { - flag = false; - } - if (flag) u.addLast(command); - } - unMergedCmds = u; - REPCommand mergeEnd = new REPCommand(REP.SMCMD_END_MERGE,sid,eid,seq(),0,""); sendToEditor(mergeEnd); - checkAck(preMergeCommand); - if (preMergeCommand.eid==eid) { - if (!slowMerge) { - sendAck(preMergeCommand); + } + + /** + * 確定操作 + * command がackならば、unMergeList にあるかどうかを調べる。 + * なければ、もう終わっているので何もしない。 + * ack でなければ、自コマンドの直前までのunMergedListを削除 + * @param command + */ + private void trancateUnMerge(REPCommand command) { + LinkedListu = new LinkedList(); + if (command.cmd==REP.REPCMD_INSERT_ACK||command.cmd==REP.REPCMD_DELETE_ACK) { + boolean flag=false; + for(REPCommand c:unMergedCmds) { + if (c.sid==command.sid&&c.eid==command.eid&&c.seq==command.seq) + flag = true; } + if (flag) { + unMergedCmds = u; + } + return; } else { - ServerMainLoop.logger.writeLog("Editor"+eid+": send preMergeCommand "+preMergeCommand); - next.send(preMergeCommand); + for(REPCommand c:unMergedCmds) { + if (c.eid==eid) { + u.addLast(c); + } else { + u = new LinkedList(); + } + } + unMergedCmds = u; } - // sentList.clear(); - preMergeCommand = null; } private void sendAck(REPCommand command) { @@ -548,15 +554,13 @@ /** * My command is returned from the session ring, and START_MERGE_ACK - * is returned.　At this - * stage my writeQueue is empty, our editor is waiting for me. + * is returned.　At this stage my writeQueue is empty, our editor is waiting for me. * Start merge process. * @param cmd */ public boolean merge(Editor editor, REPCommand prev){ logger.writeLog("beforeMerge"+eid+":"+unMergedCmds); LinkedList output = new LinkedList(); - LinkedList newSentList = new LinkedList(); // merge queue上にあるコマンドを全部undoコマンドするのと同時に // sort したコマンド列を生成する for( REPCommand cmd0 : unMergedCmds) { @@ -564,30 +568,28 @@ } sortedEditCmds = new TreeSet(new REPCommandComparator(1)); - logger.writeLog("sentList"+eid+":"+editor.getSentList()); - for( REPCommand cmd0 : editor.getSentList()) { + logger.writeLog("sentList"+eid+":"+sentList); + for( REPCommand cmd0 : sentList) { if (cmd0.cmd==REP.REPCMD_INSERT || cmd0.cmd==REP.REPCMD_DELETE) { sortedEditCmds.add(cmd0); } } output.addAll(sortedEditCmds); - output.addLast(new REPCommand(REP.REPCMD_MERGE_MARK,0, editor.getSID(), REP.MERGE_EID.id, editor.seq(), "")); + // output.addLast(new REPCommand(REP.REPCMD_MERGE_MARK,0, editor.getSID(), REP.MERGE_EID.id, editor.seq(), "")); logger.writeLog("sortedMerge"+eid+":"+sortedEditCmds); // unMerged command のdeleteのundo string は、この時点で使えない。 // Editor 側から送り返して来たものを使う必要がある。 unMergedCmds.clear(); logger.writeLog("outputMerge"+eid+":"+output); - editor.setSentList(newSentList); - return optimizedSend(editor,output); + return optimizedSend(output); } /** * Sent optimized merged command list - * @param editor * @param output * @return if any sent commands output */ - public boolean optimizedSend(REPNode editor, LinkedList output) { + public boolean optimizedSend(LinkedList output) { /* * Optimized send の場合は、unMergedCommand のつじつまを合わせる必要がある。 */ @@ -600,9 +602,9 @@ for(REPCommand c:output1) { REPCommand m = new REPCommand(c); m.setEID(REP.MERGE_EID.id); - m.setSEQID(editor.seq()); + m.setSEQID(seq()); sentMergedList.addLast(m); - editor.sendToEditor(m); + sendToEditor(m); } logger.writeLog("OptimizedOutputMerge"+eid+":"+sentMergedList); merge_mode = true; @@ -636,15 +638,6 @@ } } - /** - * Translate Command that was received from SeMa. - * @param cmd the command to be translated. - * @return translated command. - */ - public void transReceiveCmd(REPNode nextEditor,REPCommand cmd){ - assert (cmd.eid != eid); - unMergedCmds.addFirst(new REPCommand(cmd)); - } public void setEid(int _eid){ eid = _eid; @@ -666,7 +659,7 @@ return mergeAgain; } - public void getMergeAgain(Editor editor) { + private void getMergeAgain() { if (sentMergedList.size()>0) return; // wait for previous merge completion LinkedList returnCommand = new LinkedList(); @@ -675,12 +668,12 @@ returnCommand.add(createUndo(command)); } returnCommand.addAll(sortedEditCmds); - returnCommand.addLast(new REPCommand(REP.REPCMD_MERGE_MARK,0, editor.getSID(), REP.MERGE_EID.id, editor.seq(), "")); - returnCommand.addAll(editor.getSentList()); + // returnCommand.addLast(new REPCommand(REP.REPCMD_MERGE_MARK,0, sid, REP.MERGE_EID.id, seq(), "")); + returnCommand.addAll(sentList); unMergedCmds.clear(); logger.writeLog("MergeAgain "+eid+" ret="+returnCommand.size()); mergeAgain = false; - optimizedSend(editor, returnCommand); + optimizedSend(returnCommand); } // // public boolean isFinished() { diff -r 2107530c3d72 -r 596cc0a3beea test/mergertest/TestMerger.java --- a/test/mergertest/TestMerger.java Tue Oct 12 16:17:42 2010 +0900 +++ b/test/mergertest/TestMerger.java Thu Oct 14 16:15:03 2010 +0900 @@ -46,7 +46,7 @@ } for(REPCommand command : othersCommandList){ Logger.print(command); - trans.transReceiveCmd(null, command); + // trans.transReceiveCmd(null, command); } for(int i = 0; i < commandList.size(); i++){ trans.merge(this,null);