欢迎来到知嘟嘟! 联系电话:13095918853 卖家免费入驻,海量在线求购! 卖家免费入驻,海量在线求购!
知嘟嘟
我要发布
联系电话:13095918853
知嘟嘟经纪人
收藏
专利号: 2017114146572
申请人: 江南大学
专利类型:发明专利
专利状态:已下证
专利领域: 计算;推算;计数
更新日期:2024-08-26
缴费截止日期: 暂无
价格&联系人
年费信息
委托购买

摘要:

权利要求书:

1.一种低延迟的分布式计算共识算法,包括:(1)执行EPaxos算法模式;

(2)根据算法运行过程中客户端的负载情况、并发客户端的命令冲突情况以及网络的实时情况,每隔时间段ts计算EPaxos算法模式下系统的平均延迟Lat1(EPaxos)以及估计Multi‑Paxos算法模式下系统的平均延迟Lat1(Multi‑Paxos),其中ts取15秒:(2.1)计算Lat1(EPaxos):统计副本Ri处理的客户端提交的命令总数Ti,执行slow‑path的命令数Ci,从客户端到副本Ri所需的时间tci,从副本Ri到所有副本所花时间中第k少的时间min_k{i},从副本Ri到所有副本所花时间中第p少的时间min_p{i},则EPaxos算法模式下系统的平均延迟为:

其中,Ri表示第i个副本,i∈[1,N],N表示副本总数;k表示fast path中的法定人数;p表示slow path中的法定人数,也为Multi‑Paxos算法模式下的法定人数;

(2.2)估计Lat1(Multi‑Paxos):分别估计各个副本Rr为领导者时,Multi‑Paxos算法模式下系统的平均延迟:

取最小的Lat1(Multi‑Paxos)r作为Multi‑Paxos算法模式下系统的平均延迟Lat1(Multi‑Paxos),令领导者Rl为此时的Rr;

其中,r∈[1,N];tir表示从副本Ri到副本Rr所需的时间;

(3)比较Lat1(EPaxos)和Lat1(Multi‑Paxos)的大小,若Lat1(Multi‑Paxos)

(4)执行Multi‑Paxos算法模式,即在Multi‑Paxos算法模式下客户端将命令提交给最近的副本,副本再将命令传递给领导者;

(5)根据算法运行过程中客户端的负载情况、并发客户端的命令冲突情况以及网络的实时情况,每隔时间段ts计算Multi‑Paxos算法模式下系统的平均延迟Lat2(Multi‑Paxos)以及估计EPaxos算法模式下系统的平均延迟Lat2(EPaxos):(5.1)计算Lat2(Multi‑Paxos):统计副本Ri传递的客户端提交的命令总数Ti,从客户端到副本Ri所需的时间tci,从副本Ri到领导者Rl所需的时间til,从领导者Rl到所有副本所花时间中第p少的时间min_p{l},则Multi‑Paxos算法模式下系统的平均延迟为:(5.2)估计Lat2(EPaxos):统计从副本Ri到所有副本所花时间中第k少的时间min_k{i},到所有副本所花时间中第p少的时间min_p{i},传递的命令中对各个关键字Km操作的命令数CKim,则在EPaxos算法模式下,含有最大CKim的副本Ri传递的关于关键字Km的命令中执行slow path的命令数Sim近似为min{SKim,∑r∈[1,N],r!=iCKrm},其余副本Ri传递的关于关键字Km的命令中执行slow path的命令数Sim近似为CKim,则对任意副本Ri,执行slow path的命令总数Ci近似为∑mSim,故EPaxos算法模式下系统的平均延迟近似表示为:其中,m∈[1,M],M表示关键字总数;

(6)比较Lat2(EPaxos)和Lat2(Multi‑Paxos)的大小,若Lat2(EPaxos)≤Lat2(Multi‑Paxos),从Multi‑Paxos算法模式转换至EPaxos算法模式,转至步骤(1),否则,转至步骤(4)。

2.根据权利要求书1所述的一种低延迟的分布式计算共识算法,其中,步骤(3)所述的从EPaxos算法模式转换至Multi‑Paxos算法模式,按如下过程进行:(2.1)算法转换的发起者给各个副本Ri发送更改协议的通知并设置一个超时;

(2.2)各个副本Ri确认收到通知,发送确认消息以及已经开始处理的最大实例编号Ii给算法转换的发起者,进入转化状态,并设置一个超时;副本在转化状态时,不会分配新实例,即,对于收到的客户端命令,放入缓存,在非转化状态时再进行处理;

(2.3)若算法转换的发起者在超时之前收到所有副本的确认消息以及Ii,则对Ii进行统计,统计结果记为IMAX={Ii|i∈[1,N]},发送统计结果IMAX以及算法转换的执行命令给所有副本;否则,发送算法转换的取消命令给所有副本;

(2.4)若副本Ri在超时之前收到算法转换的执行命令以及IMAX,Ri执行各个副本Rr所有提交的实例,其中各个副本Rr所有提交的实例中最大实例编号应为Ir,Ir∈IMAX,如果副本Ri的本地存储中缺少某一实例,则Ri询问其他副本,直至执行完各个副本Rr所有提交的实例,之后跳出转化状态,进入Multi‑Paxos算法模式;否则,副本Ri跳出转化状态,返回EPaxos算法模式。

3.根据权利要求书1所述的一种低延迟的分布式计算共识算法,其中,步骤(6)所述的从Multi‑Paxos算法模式转换至EPaxos算法模式,按如下过程进行:(3.1)算法转换的发起者给各个副本Ri发送更改协议的通知并设置一个超时;

(3.2)各个副本Ri确认收到通知,发送确认消息给算法转换的发起者;其中,领导者Rl还需发送已经开始处理的最大实例编号Il,进入转化状态,并设置一个超时;

(3.3)若算法转换的发起者在超时之前收到所有副本的确认消息以及Ii,发送Il以及算法转换的执行命令给所有副本;否则,发送算法转换的取消命令给所有副本;

(3.4)若副本Ri在超时之前收到算法转换的执行命令以及Il,Ri执行所有提交的实例,其中所有提交的实例中最大实例编号应为Il,如果副本Ri的本地存储中缺少某一实例,则Ri询问其他副本,直至执行完所有提交的实例,之后跳出转化状态,进入EPaxos算法模式;否则,副本Ri跳出转化状态,返回Multi‑Paxos算法模式。