就单个数据连接来说,如果只有一个线程写,那么接收方收到的数据包天然就是有序的。扩展到两个线程,数据包的commit序号乱序的场景主要是如下情况:A线程在T1时刻获取commit token,延迟X ms发送,B线程在T2时刻获取commit token,延迟Y ms发送,(T1 < T2, Y < X <= 5 ms, X-Y > T2-T1)。所以在不考虑网络延迟的情况,收到每个包以后最多再等5ms,就可以确保收到乱序的commit包。不过网络延迟总是存在,所以上述属于理想条件并不成立。不过考虑到每个commit包在发送前都会提前发送一个prepare包,两者的最大间隔是2 * 5 = 10ms,最小间隔是2 * 1 = 2ms,那么在收到乱序的commit包之前,在数据流里必然会先看见一个孤立的prepare包,所以可以用这一点来检测乱序包的存在*。
扩展到两个数据连接,对于每个数据连接来说,只要我们可以检测乱序包的存在,就可以对一定数量的commit包进行单调递增排序。两个数据连接的排序结果需要做归并,具体做法是找到其中一个数据连接收到的commit包的最大commit值C,以此在另一个数据连接排序后的commit包中搜索,找到小于C的最大commit值,那么这两块排序的结果就可以进行进一步的归并返回全局排序结果。
流控可以设定对于每个数据连接来说,接受者每次只读M个包(再加上已经发现的乱序的包N,通过数据流里是否有孤立的prepare包确定),读到M+N个包以后对数据开始排序,排序完成后检查另一个数据连接完成的已排序数据包,如果存在可以归并的包,归并排序后输出,同时将已输出的数据包从两个连接的已接收数据包中清除。每个数据连接的已排序数据包的最大commit值较大的一方暂停,等待另一方接收到可以完成归并排序的时候再恢复读取,从而实现流控机制。
*形式化证明可以用反证法,每个包的生成和发送分成四个阶段,1生成prepare handle,2.发送prepare,3.生成commit handle,4.发送commit。
产生commit包乱序的场景是线程A在T1时刻生成commit handle,T4时刻发送commit包。线程B在T2时刻生成commit handle,T3时刻发送commit包。
如果想在乱序场景中不收到孤立的prepare包(孤立指没有和commit配对),线程A的prepare包必须要在T3时刻或者更晚发送才能满足条件,这就违背了之前的假设。所以只要收到孤立的prepare包,就说明还有乱序的包没有收到。