Instanceof

简介： EPaxos（Egalitarian Paxos）作为工业界备受瞩目的下一代分布式一致性算法，具备广大的利用前景。但纵观业内，至今仍未呈现一个EPaxos的工程实现，甚至都没看到一篇能把EPaxos讲得艰深一点的文章。EPaxos算法实践虽好，但因为其实在艰涩难懂，工程实现上也有很多挑战，理论利用落地尚未成熟。本文将用通俗易懂的语言介绍EPaxos算法，由浅入深、一步一步的让只有Paxos或Raft等分布式一致性算法根底的同学都能轻易看懂EPaxos，真正将艰涩难懂的EPaxos，变的平易近人，带入千万家。 作者 | 祥光（严祥光）起源 | 阿里技术公众号 引言EPaxos（Egalitarian Paxos）作为工业界备受瞩目的下一代分布式一致性算法，具备广大的利用前景。但纵观业内，至今仍未呈现一个EPaxos的工程实现，甚至都没看到一篇能把EPaxos讲得艰深一点的文章。EPaxos算法实践虽好，但因为其实在艰涩难懂，工程实现上也有很多挑战，理论利用落地尚未成熟。 本文旨在通俗易懂地介绍EPaxos算法，由浅入深、一步一步的让只有Paxos或Raft等分布式一致性算法根底的同学都能轻易看懂EPaxos，真正将艰涩难懂的EPaxos，变的平易近人，带入千万家。 在《一文理解分布式一致性算法EPaxos》中，从Paxos的问题引出EPaxos，介绍了EPaxos的基本概念与直观了解，置信读者曾经对EPaxos有了整体的印象。 本文将从Paxos与EPaxos比照的角度，介绍EPaxos外围协定流程。上一篇文章最初留下的思考题，置信在浏览完本文后，都能找到答案。浏览本文须要一些Paxos或Raft等分布式一致性算法背景。 一 EPaxos根本思维EPaxos是一个Leaderless的一致性算法，无需选举Leader，任意正本均可发动提议。 Leaderless也能够看作每个正本都是Leader，从Multi-Paxos或Raft的角度看，如果应用多Group，将每个Leader划分到不同的Group，每个正本负责一个Group的Leader，同时负责其它所有Group的Follower，如同也能够做到相似Leaderless的成果。 应用多Group实现的Leaderless，每个Group独立的对一系列Instance达成统一，每个Group产生一条Instance序列，不同Group产生的Instance彼此独立，不能确定先后顺序。因而跨Group的一致性是一大问题，在一致性层面无奈解决，往往须要在下层应用分布式事务来解决。 EPaxos解决了这个问题，实现了真正的Leaderless。EPaxos通过跟踪Instance之间的依赖关系，确定不同Group产生的Instance的绝对程序，而后通过排序将多Group产生的多条Instance序列合并成一条全局的Instance序列，实现了跨Group的一致性，也即实现了真正的Leaderless。 EPaxos先运行共识协定，使各正本对Instance的值和Instance依赖的绝对程序达成统一，随后运行排序算法，基于后面曾经达成共识的Instance的绝对程序，对Instance进行全局排序，最终失去统一的全局Instance序列。 以上是站在Multi-Paxos或Raft应用多Group实现Leaderless的角度引出EPaxos的根本思维，理论Group是一致性算法之外的概念，这里引入Group只是为了不便介绍，理论EPaxos中并没有Group的概念，但与Paxos或Raft相似，能够在EPaxos之上实现多Group。 二 EPaxos的InstanceEPaxos的Instance与Paxos有所不同，Paxos的Instance当时调配序号，但EPaxos的Instance不当时调配序号，各正本能够并发的乱序提交，但跟踪记录Instance之间的依赖关系，最初依据依赖关系排序。这里先总结一下不同点： EPaxos的Instance与Paxos的不同点 Paxos的Instance由全局间断递增的InstanceID标识，InstanceID也是Instance的序号，全局惟一，间断递增。 EPaxos的Instance空间是二维的，每个正本领有其中一行，因而由二维的R.i标识，其中R为正本标识，i为正本内间断递增的整数，每开始一个新的Instance就加一。正本R领有的Instance序列为R.1，R.2，R.3，...... R.i，...... EPaxos的Instance绝对Paxos还有一些额定的属性： state标识Instance以后的状态，可取值pre-accepted、accepted、committed。因为EPaxos的Instance的状态比拟多，所以须要专门的state字段标识。deps为依赖的Instance汇合，寄存所有依赖的Instance的标识，即要在后面执行的Instance。deps保留了Instance之间的绝对程序，后续将基于deps对Instance进行排序。seq为Instance的序列号，其值为deps中所有Instance的seq的最大值加一，反映Instance提议的程序，后续排序的时候应用。EPaxos的Instance的deps和seq属性与Instance的值一样，也须要在各正本之间达成统一，后续各正本将独立的基于deps和seq对Instance进行排序。因为EPaxos的排序算法是确定性的，各正本基于雷同的deps和seq对Instance进行排序，最终会失去统一的全局Instance序列。 将Instance看作图的顶点，deps就是顶点的出边，图的顶点和边都确定并在各正本之间达成统一之后，各正本对图进行确定性的排序，最终失去统一的Instance序列。 三 EPaxos共识协定Paxos提交一个值须要两阶段，而EPaxos的Instance多了依赖汇合deps和序列号seq，为了确定这些属性的值，EPaxos比Paxos多了一个阶段。残缺的EPaxos有三阶段，但并非每个阶段都是必须的，下表将Paxos与EPaxos的协定流程进行比照： Paxos与EPaxos的协定流程比照 EPaxos与Paxos相比，Prepare阶段和Accept阶段相似，但EPaxos多了PreAccept阶段，也是EPaxos最要害的一个阶段。正因为EPaxos多了PreAccept阶段，Instance的状态更多了，所以引入专门的state属性来标识Instance以后所处的状态（pre-accepted、accepted、committed）。没有引入Prepare阶段的状态，是因为Prepare阶段没有提议值，能够通过本地有无提议值来与其它状态辨别。通常状况下，EPaxos只运行PreAccept阶段，即可Commit，Prepare阶段和Accept阶段都能跳过。 EPaxos与Paxos相似，在任意阶段如果发现Instance被抢占，都须要回退到Prepare阶段从新开始。 1 Prepare阶段Prepare阶段的作用，EPaxos与Paxos相似，都是为了争取提议权，同时学习之前曾经提议的最新值。在EPaxos中，因为每个正本都领有各自独立的Instance空间，在本人的Instance空间上提议，相当于Multi-Paxos的Leader，所以与Multi-Paxos相似，通常状况下可间接跳过Prepare阶段，间接从下一阶段开始。 2 PreAccept阶段PreAccept阶段是EPaxos特有的，其作用是确定Instance的依赖汇合deps和序列号seq，同时尽量让提议值、deps和seq在各正本间达成统一。若PreAccept阶段曾经达成统一，则间接到Commit阶段（Fast Path），否则须要运行Accept阶段，而后才到Commit阶段（Slow Path）。 PreAccept阶段是如何确定Instance的依赖汇合deps和序列号seq的呢？其实比较简单，从正本本地已存在的Instance中，收集须要在后面执行的Instance，即本地deps汇合，本地seq即本地deps中的所有Instance的seq的最大值加一。最终的依赖汇合deps取大多数正本的本地deps汇合的并集，最终的序列号seq则取他们的本地seq的最大值。 各正本并发提议的时候，不同正本的本地deps和本地seq都可能不一样，那么PreAccept阶段如何能力达成统一呢？如果有足够多的正本（Fast Quorum）的本地deps和本地seq都雷同，则曾经达成了统一。否则，最终的依赖汇合deps取大多数（Slow Quorum）正本的本地deps的并集，最终的序列号seq取它们的本地seq的最大值，而后运行Accept阶段达成统一。 PreAccept阶段的Fast Quorum始终蕴含提议者，会在前面探讨起因。Fast Quorum的值不小于Slow Quorum。假如正本总数为N，可容忍F个正本同时生效，N = 2F + 1，则Fast Quorum = 2F，优化后的EPaxos可优化至F + [ (F + 1) / 2 ]，Slow Quorum = F + 1。Fast Quorum取值的推导这里先不做介绍，会在后续文章中具体探讨，Slow Quorum即大多数正本，与Paxos的Accept阶段雷同。 ...

1. instanceof关键字如果你之前始终没有怎么认真理解过instanceof关键字，当初就来理解一下： instanceof其实是java的一个二元操作符，和=,<,>这些是相似的，同时它也是被保留的关键字，次要的作用，是为了测试右边的对象，是不是左边的类的实例，返回的是boolean值。 A instanceof B留神：A是实例，而B则是Class类 上面应用代码测试一下： class A{}interface InterfaceA{}class B extends A implements InterfaceA{}public class Test { public static void main(String[] args) { B b = new B(); System.out.println(b instanceof B); System.out.println(b instanceof A); System.out.println(b instanceof InterfaceA); A a = new A(); System.out.println(a instanceof InterfaceA); }}输入后果如下： truetruetruefalse从下面的后果，其实咱们能够看出instanceof，相当于判断以后对象能不能装换成为该类型，java外面上转型是平安的，子类对象能够转换成为父类对象，接口实现类对象能够装换成为接口对象。 对象a和Interface没有什么关系，所以返回false。 那如果咱们装换成为Object了，它还能认出来是哪一个类的对象么？ public class Test { public static void main(String[] args) { Object o = new ArrayList<Integer>(); System.out.println(o instanceof ArrayList); String str = "hello world"; System.out.println(str instanceof String); System.out.println(str instanceof Object); }}下面的后果返回都是true，也就是认出来还是哪一个类的对象。同时咱们应用String对象测试的时候，发现对象既是String的实例，也是Object的实例，也印证了Java外面所有类型都默认继承了Obejct。 ...