Quorum System的故障概率和负载

最近读到一个有趣的话题：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个元素。

结论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...