论文-spinnaker

Spinnaker是IBM & Linkedin Team在2011年VLDB发布的一个k/v存储服务,其设计实现基本上就是典型的paxos/raft的rsm(replicated-state-machine)的典型应用,系统实现思路很清晰,比较值得一读。

Spinnaker主要针对一个datacenter内的数据同步,考虑到datacenter内的网络分区概率极低,Spinnaker严格上说是一个CA系统。它采用3-way replica,跟传统的最终一致性的存储系统做对比,Spinnaker在读操作上甚至要更快,而在写操作上,它也只是有5-10%的性能损失。

数据模型

Spinnaker的数据模型及API跟Bigtable及Yahoo PNUTS非常类似,数据基于row及table组织,基本是如下的pattern:

row key -> { col name : col val, ……}

Data Model

作为k/v存储,其数据格式显然也没有做预设的schema,基于col name & col val来进行schema的变更;由于其数据模型里没有column family,其查询便利性上较之Bigtable还是有些差别。

基本APIs

  • insert
  • delete
  • get
  • test_and_set

前三个api自不必说,基本就是常规的kv操作;对于test_and_set, 由于数据存在版本,client端可以基于version做conditionalPut、conditionalDel等操作,从而实现test_and_set语义;

比如conditionalDelete(key, colname, v),只有当前数据版本为v时,才进行delete操作。

架构

数据分布层面,Spinnaker基于key-range进行分布;一个range内的数据集的多个replica集合叫cohort,cohort基于chained-declustering方式进行replica逻辑关联。

上图就是一个典型的数据分布架构,为了系统简化直接基于Zookeeper来做meta-data管理;

Cluster

对于单个节点,节点通过模块话组织进行数据commit, membership管理, election等动作,具体如下图:

Node

Replication Protocol

Spinnaker协议跟Raft, Zab比较类似,采用基于选举的paxos-like方案,其协议分为两个阶段:

  • p1: leader election
  • p2: quorum (using multi-paxos)

简单来说就是,首先选出cohort leader(leader crash会重新选举), 然后log发送给cohort leader,leader基于multi-paxos协议进行quorum的log一致性同步(注意此时节点未做commit,也就是未commit到RSM中)。 多数派节点ack后,leader commit然后返回client,之后发出async commit操作通知节点进行commit操作。

Protocal

显然在这个时序里,leader返回之后时间点,client->get(),到follower节点是可能拿到过期数据的,而leader节点是可以拿到最新数据。这就是Spinnnaker里的timeline consistency。

恢复

每个节点为所有的partition数据维护一个共享log(规避随机写问题),类似write-ahead-log,确保数据的可恢复性。

如果follower挂掉后又重新加入

  • leader传输log给follower,follower会追进度
  • 直到追上后,follower投入运行

如果leader挂掉

  • 触发p1的election
  • leader会重新propose所有的uncommited消息
  • 如果是quorum,开始update

需要指出的是,重新选举后leader会将所有的uncommit log进行重新的分发,这一块跟Raft协议有了比较大的简化,不确定正确性是否理论严格。

分布式一致性简史

来自 https://betathoughts.blogspot.com/2007/06/brief-history-of-consensus-2pc-and.html

第一个一致性问题是从 Lamport 大神的 1978年Time论文指出,虽然他没有明确提出consensus or agreement的概念, 但他提出了分布式状态机的概念(复制状态机, RSM), 一组确定状态机,从相同初始状态开始,确保他们以相同顺序处理相同消息,可以确保每个状态机都是其他的状态机的副本。 关键是,哪个消息是下一个需要处理的消息,达成一致, 这就是一致性问题。

1979年 Jim Gray描述了2PC,但是2PC会Block,随后,Dale Skeen在1981年提出3PC, 但是找到好的3PC算法花了近25年。

1985年 著名的FLP Impossiblility被提出。 即一个异步系统即使只有一个进程出错,分布式一致性也不可能达到。跟海森堡的测不准原理有些神识。此时 Consensus变成,让一系列处理器在一个value上达成共识的问题。 核心是没法区分,是低速执行,还是终止。

这时,人们意识到分布式算法有两个非常重要的属性, safety liveness 前者:坏的事情不会发生,后者:好的事情最终会发生。

虽然,2pc保证safety,但是liveness非常不好。

同时:分布式系统被分为同步,异步两种, 同步看做异步的特例, 它的消息传输时间有上界。

1982年 Byzantine Generals Problem: 进程会说谎。

1986年,一致性和事务聚在一起。 最好的一致性算法是Byzantine Generals,但是代价太高,根部无法用于事务处理。

1987年 Jim Gray, 指出分布式事务是一个新的一致性问题,不是bg的退化版本,分布式事务是uniform consensus(2010年) 所有进程必须在一个value上达成一致,即使是那些出错进程。

进入90年代,曙光来临:

  • 1990年 Lamport提出 Paxos

  • 1996年 Lampson引用Paxos

  • 2001年 Lamport 发表 Paxos Made Simple

Paxos及Paxos-like的出现,大有一统分布式一致性的趋势。

而针对分布式系统的同步异步问题,人们发现:系统简单划分同步异步有些宽泛

1988年 Dwork Lynch Stockmeyer定义了部分同步系统:

进程已给点bound的速率运行,消息传输时间有界,但边界的实际取值无法得知
处理速度和传输的边界一直,只是在未来某个未知时间开始。

2005年 Lamport Jim Gray将Paxos应用的分布式事务提交中, 用于容错,解决block问题。进行了整体融合。

复杂系统

Complexity: A Guided Tour

这篇笔记断断续续写了很久,不是时间问题,不是理解问题,就是复杂性问题。复杂性理论作为泛理论,本质是对多个学科进行组合提炼,发展出思想。我们能读到的基本是思想,内在逻辑,但是如果基于表面提炼出的思想,探究其内在、本质等,显然还差了很多,至少这个理论现在也是这种状态…

复杂系统

17世纪,拉普拉斯时期开始,还原论成了科学的主导,大多数人认为,世界是客观的,给我们足够多的参数,我们可以还原整个客观的世界,更直观的说,如果你了解了整体的各个部分,以及把这些部分整合起来的机制,你就可以了解这个整体。 侯世达说,只要精神正常的人,就不会反对还原论。最近几十年开始,一些人开始尝试建立新的基础,包括控制论、协同学、系统科学,当然也包括本书的主题-复杂系统,这些人中包括了侯世达(圣塔菲实验室里的低调的研究者),而本书的作者米歇尔也是其中的一位。

什么是复杂性,现实世界太多直观的例子,单只行军蚁是已知行为最简单的生物,如果把100只行军蚁放在一个平面,它们会不断外围绕圈然后体力耗尽而死,但是如果把上百万只聚集在一起,群体形成整体,涌现出所谓的“集体智能”,于是蚁群变成了超生物。类似的还有免疫系统,市场经济,人类细胞,以及我们为之沉迷的“智能”和意识

这些系统都具有如下的共性:

  1. 复杂的集体行为
  2. 信号和信息处理
  3. 适应性

而复杂系统理论就是试图解释这种没有中央控制下的简单个体,如何通过自组织,形成产生模式处理信息甚至进化学习的整体。 这是个泛理论,研究的交叉学科领域。

用书中的定义:复杂系统是由大量组分组成的网络,不存在中央控制,通过简单运作规则产生出复杂的集体行为和复杂的信息处理,并通过学习和进化产生适应性。, 进一步抽象化:复杂系统是具有涌现和自组织行为的系统。

显然,涌现自组织行为产生的机制是复杂性理论研究者最关注的。

复杂综述

从伽利略开始,科学引入了实验观测,牛顿在伽利略基础上提出运动三定律,至此,牛顿为我们描绘了一个钟表宇宙:设定好初始状态,沿着三大定律一直走下去。上个世纪20年代,海森堡提出了测不准定律,钟表宇宙慢慢的崩塌。而进入60年代,混沌理论指出,系统的演进对初始条件有种敏感依赖度,即如果系统的混沌的,测量初始位置时如果产生极小的误差,在预测未来运动时,也会产生极其巨大的误差。庞加莱的三体问题就是一个典型的混沌系统。

量子理论的出现告诉我们,这个世界的基本组成本身是不确定的,而混沌理论告诉我们即使一个确定性系统,无任何随机源,因为一些初始条件敏感性,这个系统(的发展)仍然是不确定的

混沌理论的出现是突破性的,它告诉我们非线性是系统的关键因素,而还原论只关注线性

Logistic映射是一个非常直观的混沌表现:

x(t+1) = μx(t)(1-x(t))

Logistic映射描述了一个时间离散的动力系统,t为迭代时间步长,x(t) [0,1], μ是参数。 在这个系统里,μ的设置,将产生完全不同,不可预测的结果。

0<μ<1

1<μ<3

3<μ<3.6

μ=3.6

μ=4时,系统完全进入分叉

分叉

然后对混沌系统深入研究,发现其在宏观层面仍然是可预测的,这方面的研究包括倍周期之路,费根保姆常数等。

当人们开始探究复杂现象的本质时,人们慢慢跟可能是目前为止人类最伟大的理论联系在一起 – 熵增理论,显然,复杂系统关注的问题是这种逆熵的自组织系统是如何产生。从麦克斯韦妖,到西拉德将熵和信息联系在一起,再到玻尔兹曼的统计力学,作者带着我们走过了熵在宏观态和微观态的体现。然后信息出现了,香农的信息熵是信息源的可预测性,信息是用来计算的,所以,复杂性的一个很重要问题就是计算问题。计算问题由来已久,从莱布尼兹的符号系统,到希尔伯特问题,再到哥德尔不完备性,最后到图灵机,我们慢慢的认识到过去对数学和计算的期望可能只是幻想。

于是,我们发现,量子力学和混沌理论摧垮了精确预测的希望,而哥德尔和图灵的结果摧垮了数学和计算无所不能的希望。从历史的角度看,我们从来没有这么确信过,这个世界是复杂的。

之后,作者从进化,遗传,现代综合到角度进一步试图抓到复杂的本质。对于进化论,熵的减少是自然选择的结果,对于遗传学,进化的渐进过程,通过自然选择和个体细微随机变异产生,而宏观尺度的现象,如新物种诞生,可以用基因变异和自然选择微观过程解释。这不可避免的会触及生命本源问题,虽然通过DNA结构,我们越来越认清作为单个个体的本质,但是群体而言,元胞自动机,冯诺依曼自动复制机,可能给我们宏观上认识生命提供了更多的启示,显然,生命也是群体的涌现!

等待卡诺

总得来说,复杂系统明显表现出理论空泛,缺乏实质的特点,它的主题非常松散,而且核心定义又不明确,更关键的是由于理论工具的缺乏,无法形成体系。拿还原论来类比,它没有合适的定义和可以描述的数学工具,因此,无论是过去还是现在,都存在着瓶颈。这一点米歇尔也是直言不讳。可以说,复杂系统现在提供了一种新的思路,如果作为一门科学,还需要尼古拉卡诺这类的人出现,对于我们而言,能做的就是等待卡诺。

2017年度学习计划

技术

后端架构

  • 后端系统的docker化 【Docker相关】
  • 重构thor, java 8化,通用业务框架 【业务框架相关】
  • termite微服务框架 【服务框架相关,包括netty, ioc的深入了解】
  • api gateway重构 【LB相关】
  • extractor重构 【HA相关】
  • 系统化的架构理论【分布式存储相关】
  • 学习下go语言

机器学习

  • 深入理解主流的统计机器学习算法,包括SVM, 最大熵,AdaBoost,Random Forest,EM,条件随机场,HMM等。
  • 深入理解深度学习的内部运行原理,包括CNN, RNN, RCNN, LSTM
  • 机器学习平台搭建完成,完成基础的智能业务
  • 对caffe, tensorflow, mxnet等至少深入了解一种深度学习框架的技术架构

科学素养

数学

  • 微积分,至少可以看懂基本的证明
  • 数理统计,统计学的基本思想和概念
  • 随机过程, 随机过程的基本思想和概念
  • 线性代数, 熟练基本运算

物理

  • 量子力学,至少可以应对量子计算机的水准
  • 相对论,大体了解场方程的基本计算过程

生物

  • 神经生物学,神经的基本机制
  • 脑科学,脑工作的基本原理

个人

  • 读一本近代史
  • 读一本科学哲学相关著作
  • 读1-2本复杂系统、世界观相关的著作
  • 全年至少读15本书,可以产出10+的读书笔记