Mercurial > hg > RemoteEditor > REPSessionManager

changeset 473:596cc0a3beea

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
new Merge Algorithm
author one
date Thu, 14 Oct 2010 16:15:03 +0900
parents 2107530c3d72
children a7a17508ba35
files Todo rep/handler/Editor.java test/mergertest/TestMerger.java
diffstat 3 files changed, 194 insertions(+), 76 deletions(-) [+]
line wrap: on
line diff
--- 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 すれば良いはずだが。
--- 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<REPCommand> writeQueue = new LinkedList<REPCommand>(); 
-	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<REPCommand> getSentList() {
-		return sentList;
-	}
-	
-	public void setSentList(LinkedList<REPCommand> 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;
-		LinkedList<REPCommand>u = new LinkedList<REPCommand>();
-		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) {
+		LinkedList<REPCommand>u = new LinkedList<REPCommand>();
+		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<REPCommand>();
+				}
+			}
+			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<REPCommand> output = new LinkedList<REPCommand>();
-		LinkedList<REPCommand> newSentList = new LinkedList<REPCommand>();
 		// merge queue上にあるコマンドを全部undoコマンドするのと同時に
 		// sort したコマンド列を生成する
 		for( REPCommand cmd0 : unMergedCmds) {
@@ -564,30 +568,28 @@
 		}
 
 		sortedEditCmds = new TreeSet<REPCommand>(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<REPCommand> output) {
+	public boolean optimizedSend(LinkedList<REPCommand> 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<REPCommand> returnCommand = new LinkedList<REPCommand>();
@@ -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() {
--- 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);