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

摘要:

权利要求书:

1.一种低延迟的分布式计算共识算法,包括:

(1)执行EPaxos算法模式;

(2)根据算法运行过程中客户端的负载情况、并发客户端的命令冲突情况以及网络的实时情况,每隔时间段ts(ts可取15秒)计算EPaxos算法模式下系统的平均延迟Lat1(EPaxos)以及估计Multi-Paxos算法模式下系统的平均延迟Lat1(Multi-Paxos):(2.1)计算Lat1(EPaxos):统计副本Ri(Ri表示第i个副本,其中i∈[1,N],N表示副本总数)处理的客户端提交的命令总数Ti,执行slow-path的命令数Ci,从客户端到副本Ri所需的时间tci,从副本Ri到所有副本所花时间中第k少的时间min_k{i}(k表示fast path中的法定人数),从副本Ri到所有副本所花时间中第p少的时间min_p{i}(p表示slow path中的法定人数,也为Multi-Paxos算法模式下的法定人数),则EPaxos算法模式下系统的平均延迟为:(2.2)估计Lat1(Multi-Paxos):分别估计各个副本Rr(r∈[1,N])为领导者时,Multi-Paxos算法模式下系统的平均延迟(tir表示从副本Ri到副本Rr所需的时间):取最小的Lat1(Multi-Paxos)r作为Multi-Paxos算法模式下系统的平均延迟Lat1(Multi-Paxos),令领导者Rl为此时的Rr;

(3)比较Lat1(EPaxos)和Lat1(Multi-Paxos)的大小,若Lat1(Multi-Paxos)<Lat1(EPaxos),从EPaxos算法模式转换至Multi-Paxos算法模式,转至步骤(4),否则,转至步骤(1);

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

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

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

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

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

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

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

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

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

否则,副本Ri跳出转化状态,返回Multi-Paxos算法模式。