0
0

后分布式时代: 多数派读写的’少数派’实现

张炎泼(xp) 发表于 2020年10月18日 08:00 | Hits: 91
Tag: algo | distributed | quorum | majority | replication | paxos | raft | 分布式 | 多数派

前言

paxos可以看做是2次多数派读写完成一次强一致读写. 多数派要求半数以上的参与者(paxos中的Acceptor)接受某笔操作. 但多数派读写并不一定需要多于半数的参与者, 分布式系统中某些场合的优化, 可以通过减少参与者数量来完成的.

多数派读写:分布式系统的基础

分布式系统中, 其中一个基础的问题是如何在不可靠硬件(低可用性)基础上构建可靠(高可用性)的服务, 要达成这个目标, 核心的手段就是复制(例如一份数据存3个副本). 而复制过程中的一致性问题, 最后都归结为paxos的解决方案. 这些我们在paxos的直观解释中做了详细的介绍.

paxos的直观解释slide-20中, 我们了解到, paxos是通过2次多数派读写来完成强一致的读写:

这个方法之所以能工作也是因为多数派写中, 一个系统最多只能允许一个多数派写成功. paxos也是通过2次多数派读写来实现的强一致.

也就是说,多数派读写在分布式领域是一个更基础的问题. 在paxos的直观解释中也简单介绍了一下多数派读写:

slide-10 为了解决半同步复制中数据不一致的问题, 可以将这个复制策略再做一改进:多数派读写 : 每条数据必须写入到半数以上 的机器上. 每次读取数据都必须检查半数以上 的机器上是否有这条数据.

在这种策略下, 数据可靠性足够, 宕机容忍足够, 任一机器故障也能读到全部数据.

img

多数派读写, 也可称作 quorum-rw, wikipedia上的描述如下:

在有冗余数据的分布式存储系统当中,冗余数据对象会在不同的机器之间存放多份拷贝。但是同一时刻一个数据对象的多份拷贝只能用于读或者用于写。

算法来源于Gifford, 1979。 分布式系统中的每一份数据拷贝对象都被赋予一票。每一个读操作获得的票数必须大于最小读票数(read quorum)(Vr),每个写操作获得的票数必须大于最小写票数(write quorum)(Vw)才能读或者写。如果系统有V票(意味着一个数据对象有V份冗余拷贝),那么最小读写票数(quorum)应满足如下限制:

  1. Vr + Vw > V
  2. Vw > V/2

原文链接: https://blog.openacid.com/algo/quorum/

0     0

我要给这篇文章打分:

可以不填写评论, 而只是打分. 如果发表评论, 你可以给的分值是-5到+5, 否则, 你只能评-1, +1两种分数. 你的评论可能需要审核.

评价列表(0)