转载

关于Replicated State Machines的一些笔记

当同一个数据存在多个副本的时候，怎么管理它们就成了问题。在Map-Reduce的场景下，数据都是一次写入永不更改，那么问题就变得非常简单，让每一份数据都有多个拷贝，然后处理好分发和读取的细节问题就行了。这些细节问题包括：

所有的拷贝不能处于同样的环境下。这样单一环境的故障不至于引起所有拷贝都损坏。具体来说，如果你想容忍整个IDC的停机故障，那么就得让数据有跨IDC的副本。
读取的算法能容忍某些副本是坏的，它能检测数据的完整性，当遇到错误时，从其它副本位置重试
有一个监控程序能有效的检测数据完整性并为损坏的数据创建新的副本

在上述场景下，因为数据都是只读的，所以没有一致性问题。这也是为什么Map-Reduce能这么流行这么备受推崇的原因之一。

Replicated State Machines用于支持数据可被修改。比如分布式系统中的元数据信息。具体例如，一个分布式系统中，一个目录下有哪些文件。虽然文件本身可以做到一次写入永不修改，但是目录不可能。目录的内容总是动态变化的。

Replicated State Machines（后面简称RSM）的最早提出是在图灵奖得主Leslie Lamport的著名论文“Time, clocks, and the ordering of events in a distributed system(1978)”论文中，比较系统性的阐述是在Fred Schneider的论文"Implementing fault-tolerant services using the state machine approach(1990)"中。Fred Schneider现在是Cornell大学计算机系主任。

它的基本思想是一个分布式的RSM系统由很多个replica组成，每个replica是一个状态机，它的状态保存在一组状态变量中。状态机的状态通过并且只能通过外部命令（commands)来改变。比如你可以把MySQL服务器想像成一个状态机。它每接收到一条带修改功能的SQL语句（比如update/insert)就会改变它的状态。一组配置好replication的MySQL servers就是典型的RSM。

RSM能够工作基于这样的假设：如果一些状态机具有相同的初始状态，并且他们接收到的命令也相同，处理这些命令的顺序也相同，那么它们处理完这些命令后的状态也应该相同。因为replica都具有相同的状态，所以坏掉任何一个也没有关系。有了RSM之后理论上可以做到永远不会因为机器的物理故障而丢失数据。实际上，这就是做梦啊！

像Paxos这样的分布式选举协议是实现RSM系统的常见手段。关于paxos协议可见我之前的文章 http://www.sunchangming.com/blog/post/4655.html 它的想法是，这个RSM系统有一个全局的线性增长的日志，记录着它所收到的每条命令。利用分布式选举协议来决定每条命令在这个日志中的index（即先后顺序）。

Fred的那篇论文中指出了这样一个基本假设：

一个RSM系统若要容忍t个Byzantine failures，那么它至少应该有2t+1个replica(因为要选举）。如果把错误的类型局限小，若要容忍t个fail-stop failures，那么至少应该有t+1个replica。Fred给出是一个必要性条件，即replica数量的理论下限。

paxos协议替RSM实现了增量日志，但是现实场景中光有增量日志还不够，必须要有定期的snapshot。snapshot可以大大缩短故障恢复时间。假如一个replica断电重启了，那么它可以从上一个snapshot处继续做log的replay。并且，因为有snapshot，所以我们可以清理掉老的日志，否则硬盘迟早有一天要爆掉。关于这方面的讨论请参见MySQL的用户手册，MySQL社区在这方面积攒了非常多的经验。这些经验在NoSQL时代依然非常宝贵。

Take snapshot意味着一次stop the world的停顿。如果一个数据库系统并未采用版本化的数据存储，那么在对它做snapshot的时候，就必须暂停所有的写入操作。这方面有非常多的技巧可以减少停顿，但是我尚未发现出什么办法可以彻底消除停顿。而对使用paxos协议的RSM来说，这种停顿会令master陷入不可用，细节上若没有处理好甚至可能导致系统发生颠簸。

命令在状态机上的执行顺序并不一定等同于命令的发出顺序或接收顺序。RSM只是保证所有的状态机都以同样的顺序执行这些命令。在以RSM模式实现的primary-backup系统中，如果primary坏掉了，那么backup有权以任意顺序执行uncommitted requests。zookeeper认为这样做不妥，它采用了另外的方式：它采用的是原子化的广播协议及增量式的状态更新。状态更新的消息由primary发给backups，一旦primary坏掉了，backups必须依然执行primary的遗嘱。zookeeper使用的是原子化的广播协议，它并没有采用paxos。

正文到此结束