A-A+

Quorum System的故障概率和负载

2018年11月13日 分布式系统 暂无评论 阅读 67 次

最近读到一个有趣的话题:Quorum System的故障概率和负载。

 

首先是一些概念:

节点集合 V=\{v_1, v_2, .., v_n\}

Quorum  Q\subseteq V

Quorum System \mathcal{S} \subseteq 2^V,且Q_1 \cap Q2 \neq \emptyset, \forall Q1,Q2 \in\mathcal{S}

故障概率Failure Probability: 假设每个节点故障概率为p,Quorum System  \mathcal{S}的故障概率记为F_p( \mathcal{S})等于每个Quorum都至少有一个节点发生故障的概率。

渐进故障概率Asymptotic Failure Probability: \lim\limits_{n \to \infty} F_p( \mathcal{S})

 

访问策略Access Strategy Z定义了访问每个Q的概率P_Z(Q), 其中 \sum_{Q\in\mathcal{S}}P_Z(Q)=1

Z在节点v_i上的负载 L_Z(v_i)=\sum_{Q\in\mathcal{S}, v_i\in Q}P_Z(Q)

Z在 \mathcal{S}上的负载 L_Z(\mathcal{S})=max_{v_i\in\mathcal{S}}L_Z(v_i)

 \mathcal{S}的负载 L(\mathcal{S})=min_ZL_Z(\mathcal{S})

简单地说,负载刻画了 \mathcal{S}中压力最大的节点的压力的极小值。

 

关于几种Quorum System可以参见重新审视Paxos协议的Quorum问题

B-Grid Quorum System:

n=hrd,布置成hr行,d列,每组r行组成一个band,同一个band的一列的r个celll称为mini-column。Quorum是每个band的一个mini-column和某个band的每个mini-column的每个元素组成,共d+hr-1个元素。

BGrid

结论1:Majority Quorum System的渐进故障概率是0。

结论2:Grid Quorum System的渐进故障概率是1。

结论3:Grid Quorum System负载最优,为\Theta(1/\sqrt{n})

结论4:B-Grid Quorum System拥有Majority Quorum System的渐进故障概率,和Grid Quorum System负载。Interesting...

 

 

给我留言