Google Megastore分布式存储技术

jieforest · 发表于 2014-5-1 10:13

在一个current读的准备阶段(写之前也一样)，必需有一个副本要是最新的：所有之前更新必需提交到那个副本的日志并且在该副本上生效。我们叫这个过程为catchup。
省略一些截止超时的管理，一个current读算法步骤如下：

1. 本地查询：查询本地副本的Coordinator，判定当前副本的Entity Group是最新的

2. 查找位置：确定最高的可能已提交的日志位置，然后选择一个己经将这个日志位置生效的副本

a.(Local read) 如果步骤1发现本地副本是最新的，那么从本地副本中读取最高的被接受(accepted)的日志位置和时间戳。

b.(Majority read)如果本地副本不是最新的(或者步骤1或步骤2a超时)，那么从一个多数派副本中发现最大的日志位置，然后选取一个读取。我们选取一个最可靠的或者最新的副本，不一定总是是本地副本

jieforest · 发表于 2014-5-1 10:13

3. 追赶：当一个副本选中之后，按照下面的步骤追赶到已知的日志位置:

a.对于被选中的不知道共识值的副本中的每一个日志位置，从另外一个副本中读取值。对于任何一个没有已知已提交的值的日志位置，发起一个没有操作的写操作。Paxos将会驱动多数副本在一个值上打成共识—–可能是none-op的写操作或者是之前提议的写操作

b.顺序地将所有没有生效的日志位置生效成共识的值，并将副本的状态变为到分布式共识状态(应该是Coordinator的状态更新)
如果失败，在另外一个副本上重试。

4. 验证：如果本地副本被选中并且之前没有最新，发送一个验证消息到coordinator断定(entity group,replica)能够反馈(reflects)所有提交的写操作。不要等待回应—-如果请求失败，下一个读操作会重试。

5. 查询数据：从选中的副本中使用日志位置所有的时间戳读取数据。如果选中的副本不可用，选取另外一个副本重新开始执行追赶，然后从它那里读取。一个大的读取结果有可能从多个副本中透明地读取并且组装返回

注意在实际使用中 1和2a通常是并行执行的。

jieforest · 发表于 2014-5-1 10:14

在完整的读操作算法执行后，Megastore发现了下一个没有使用的日志位置，最后一个写操作的时间戳，还有下一个leader副本。在提交时刻，所有更新的状态都变为打包的(packaged)和提议(proposed)，并且包含一个时间戳和下一个leader 候选人，做为下一个日志位置的共识值。如果这个值赢得了分布式共识，那么这个值将会在所有完整的副本中生效。否则整个事务将会终止并且必需重新从读阶段开始。

就像上面所描述的，Coordinators跟踪Entity Groups在它们的副本中是否最新。如果一个写操作没有被一个副本接受，我们必需将这个Entity Group的键从这个副本的Coordinator中移除。这个步骤叫做invalidation(失效)。在一个写操作被认为提交的并且准备生效，所有副本必需已经接受或者让这个Entity Group在它们coordinator上失效。

jieforest · 发表于 2014-5-1 10:15

写算法的步骤如下：

1.接受Leader：请求Leader接受值做为0号提议的值。如果成功。跳到第三步

2.准备：在所有副本上执行Paxos Prepare阶段，使用一个关于当前log位置更高的提议号。将值替换成拥有最高提议号的那个值。[Replace the value being written withthe highest-numbered proposal discovered, if any]

3.接受：请求余下的副本接受这个值。如果多数副本失败，转到第二步。

4.失效：将没有接受值的副本coordinator失效掉。错误处理将在接下来描述

5.生效：将更新在尽可能多的副本上生效。如果选择的值不同于原始提议的，返回冲突错误[？]

jieforest · 发表于 2014-5-1 10:15

Coordinator进程在每一个数据中心运行并且只保持其本地副本的状态。在上述的写入算法中，每一个完整的副本必需接受或者让其 coordinator失效，所以这个可能会出现任何单个副本失效就会引起不可用。在实际使用中这个不是一个寻常的问题。Coordinator是一个简单的进程，没有其他额外的依赖并且没有持久存储，所以它表现得比一个BigTable服务器更高的稳定性。然而，网络和主机失败仍然能够让 coordinator不可用。

Megastore使用了Chubby锁服务：Coordinators在启动的时候从远程数据中心获取指定的Chubby locks。为了处理请求，一个Coordinator必需持有其多数locks。一旦因为宕机或者网络问题导致它丢失了大部分锁，它就会恢复到一个默认保守状态—-认为所有在它所能看见的Entity Groups都是失效的。随后(该Coordinator对应的)副本中的读操作必需从多数其他副本中得到日志位置直到Coordinator重新获取到锁并且Coordinator的Entries重新验证的。

写入者通过测试一个Coordinator是否丢失了它的锁从而让其在Coordinator不可用过程中得到保护：在这个场景中，一个写入者知道在恢复之前Coordinator会认为自己是失效的。

在一个数据中心活着的Coordinator突然不可用时，这个算法需要面对一个短暂(几十秒)的写停顿风险—所有的写入者必需等待 Coordinator的Chubby locks过期(相当于等待一个master failover后重新启动)，不同于master failover，写入和读取都能够在coordinator状态重建前继续平滑进行。

除了可用性问题，对于Coordinator的读写协议必需满足一系列的竞争条件。失效的信息总是安全的，但是生效的信息必需小心处理。在 coordinator中较早的写操作生效和较晚的写操作失效之间的竞争通过带有日志位置而被保护起来。标有较高位置的失效操作总是胜过标有较低位置的生效操作。一个在位置n的失效操作和一个在位置m<n的生效操作之间的竞争常常和一个crash联系在一起。Megastore通过一个具有时间期限的数字代表Coordinator来侦测crashes：生效操作只允许在最近一次对Coordinator进行的读取操作以来时间期限数字没变化的情况下修改Coordinator的状态。

jieforest · 发表于 2014-5-2 12:12

总体来说，使用Coordinator从而能够在任何数据中心进行快速的本地读取对于可用性的影响并不是完全没有的。但是实际上，以下因素能够减轻使用Coordinator所带来的问题。

1.Coordinators是比任何的BigTable 服务器更加简单进程，机会没有依赖，所以可用性更高。

2.Coordinators简单，均匀的工作负载让它们能够低成本地进行预防措施。

3.Coordinators轻量的网络传输允许使用高可用连接进行服务质量监控。

4.管理员能够在维护期或者非安全期集中地让一批Coordinators失效。对于默写信号的监测是自动的。

5.一个Chubby qunrum能够监测到大多数网络问题和节点不可用。