分布式-全序广播与共识

概述

本文将简要概括全序广播与共识,清楚的理解这两个概念,将有助于理解raft、paxos等共识算法。

全序广播的要点是:消息按照相同的顺序发送到所有节点,有且只有一次。 仔细想想,这相当于进行多轮的共识过程:在每一轮,节点提出他们接下来要发送的消息,然后决定下一个消息的全局顺序。

主从复制与共识

主从复制是single master replication,master接收信息并广播给从节点,可以对标为一种fixed-sequencer的total order broadcast的实现方式(即[1]中的section4.1 fixed sequencer)。

但当主节点出故障时,我们需要重新选主。选主就涉及到共识,通过选举的方式将某个从节点提升为新的主节点。 同时还需要考虑脑裂,我们需要共识算法来选出一位主节点。 但如果共识算法是全序广播的话,又需要主节点,陷入奇怪循环。 如何解决呢?

Epoch and Quorum

目前讨论的共识协议在内部使用了某种形式的主节点,虽然主节点不是固定的。 相反,他们都采用了一种弱化的保证:协议定义一个世代编号(epoch number,对应raft中的term、paxos中ballot number) .

  • 如果当前主节点失效,那么开始新的一轮选举, 选举赋予一个单调递增的epoch号。如果两个不同主节点对应于不同epoch号码,则具有更高epoch号码的主节点将获胜
  • 在主节点作出任何决定之前,必须首先检查是否存在比它更高的epoch号码,否则就会产生冲突的决定
    • 节点不能依靠自己所掌握的信息来决策。比如出现分区,老的主节点在分区的小集群上,新的主节点在多数集群上产生,这时候老的主节点其实已经失效。
    • 这里面实际有两轮不同的投票:首先是投票决定谁是主节点,然后是对主节点的提议进行投票。
    • 在raft的读取中,这是 read index.

投票过程与两阶段提交2PC

  • 2PC的协调者并不是依赖选举产生
  • 容错共识算法只需要收到多数节点的投票结果即可通过决议,而2PC则要求每个参与者都必须做出“是”才能最终通过。

共识算法与全序广播

全序关系广播的要点是:所有节点按照相同顺序接收消息,有且只有一次。 如果仔细想想,这其实相当于进行了多轮的共识过程。在每一轮中,节点提出他们接下来想要发送的消息,然后决定要以全序的方式接收的下一个消息。

所以,全序关系广播相当于持续的多轮共识(每一轮共识的决定对应于一条消息的接收):

  • 由于共识的一致性属性(agreement property),所有节点以相同顺序接收相同消息
  • 由于诚实性,消息不能重复
  • 由于合法性,消息不会被破坏,也不会凭空捏造
  • 由于可终止性,消息不会丢失。

对标到raft协议中的日志复制

raft协议中的日志复制是否可以对标全序广播

我们看一下全序广播:

  • 尽最大努力可靠的广播,通过重发丢失的消息
  • 基于可靠广播,保证接收顺序

total order broadcast protocol 要满足下面四个属性:

  • validity (正确性):如果一个正确的进程广播了一条消息,那么其他所有正确的进程都接收到这条消息
  • uniform agreement: 如果一个进程接收到消息m,那么所有正确的进程都接收到消息m
  • uniform integrity: 一个进程最多接收一次消息m
  • uniform total order: 如果进程p和q都接收到消息m和m’,当且仅当q接收消息m早于m’时,进程p接收消息m早于m’

综上所述, raft的日志保证是满足上述属性的。

  • 尽最大努力可靠的广播:如果失败,则一直发送 附加条目rpc
  • 基于可靠广播,保证接收顺序:接收到一条信息,leader会广播,然后作出决定 是否可以提交。

raft的实现中:

  1. leader 处理不一致是 通过强制跟随者直接复制自己的日志来解决的。 leader从来不会覆盖或者删除自己的日志。
  2. 安全性保证:当出现分区(或leader崩溃)时,只有拥有最新已提交记录的候选者才能成为leader。

特别注意:

在<数据密集型应用系统设计>中 将delivery翻译为发送,这实际是错误的。 在分布式-广播中介绍了,广播协议中 broadcast/deliver 对应的是发送和接收。 全序广播实际是指接收者要保持全序,与发送者的顺序无关。

参考:

分布式-广播

概述

本文将介绍什么是广播、为什么有广播、广播有哪些分类、如何实现广播,广播有哪些应用。

为什么要有广播?

构建分布式的难点在于不可避免的并发以及提供全局控制,这可以通过group communication来降低难度。相比点对点通信,group communication原语提供了更高的保证。

broadcast protocols 广播协议将消息发送给组内全部节点。组内成员可以是固定的,也可以加入或离开。

broadcast 是一个 group communication ,total order broadcast是一种broadcast。

当应用给组内全部节点发送消息时,可以使用一种算法去broadcast。

broadcast和delivery理解

broadcast和delivery 是更高维度的概念。send/receive是点对点的维度。

广播的分类

total order broadcast protocol 要满足下面四个属性:

  • validity (正确性):如果一个正确的进程广播了一条消息,那么其他所有正确的进程都接收到这条消息
  • uniform agreement: 如果一个进程接收到消息m,那么所有正确的进程都接收到消息m
  • uniform integrity: 一个进程最多接收一次消息m
  • uniform total order: 如果进程p和q都接收到消息m和m’,当且仅当q接收消息m早于m’时,进程p接收消息m早于m’

满足前三个属性的叫reliable broadcast。简要概括可靠广播:没有时间保证,所有消息都被没有错误的节点接收。

根据节点接收消息的顺序不同,可以得到几种广播:FIFO、causal、Total order Broadcast。

FIFO 广播

定义:如果同一个节点发送的消息m1和m2,m1早于m2,那么接收上m1要早于m2。
如下图黑线所示。但可能出现节点C接收m2早于m1,那么符合FIFO(m1早于m3),但不符合因果(因为节点B是接收m1后才广播m2)。

Causal 广播

定义:如果一个消息的广播 happens before 另外一个消息,那么所有节点的接收顺序也要保持这个顺序;如果两个消息并发,那么一个节点可以以任意接收。

如下图所示 broadcast(m1) -> broadcast(m2) 并且 broadcast(m1) -> broadcast(m3),那么有效的顺序是:
(m1,m2,m3) 或 (m1,m3,m2)

Total Order 广播,又叫atomic broadcast 原子广播

定义:保证节点的一致性,确保所有节点以相同顺序接收消息。

广播算法

广播算法可以分成两步骤:

  1. 尽最大努力可靠的广播,通过重发丢失的消息
  2. 基于可靠广播,保证接收顺序

可靠广播

尝试1:广播节点直接给其他节点发送消息

当消息丢失 并且 发送节点崩溃时,将会有节点无法收到该消息。

为了改善这种情况,我们需要依赖其他节点的帮助。已经收到消息的节点,可以将其全部消息广播给其他节点。但是该算法并不高效:没有错误时,每个消息要发送O(n^2)次,每个节点至少收到n-1次消息。

有很多算法可以进行优化。比如 Broadcast Protocols for Distributed Systems中的trans protocol
。当然最有名的是 gossip protocols

基于可靠广播(使用eager reliable broadcast or gossip protocol),我们可以构建FIFO,causal,total order 广播。

FIFO broadcast algo

sendSeq 是发送节点自增的序号;delivered:一个发送节点是一个向量,记录接收节点已经接收的发送节点的数据。buffer:记录收到的节点,直到能够被delivere。

算法核心:对于每个发送,检查是否有预期seq匹配的,如果有则deliver m 给application;反之则等待消息接收。

Causal broadcast algo

Total broadcast algo

采用共识算法

参考

  1. Dr. Martin Kleppmann 的Distributed Systems
  2. Broadcast Protocols for Distributed Systems
  3. total order broadcast and multicase algorithms taxonomy and survey

分布式-CAP理论

CAP 理论

CAP理论在互联网界有着广泛认知度,大家会将其作为衡量系统设计的标准。大家都能够清楚地讲出CAP理论:任何分布式系统在可用性、一致性、分区容错性方面,不能兼得,最多只能三选二,因此任何分布式系统设计只能在三者中进行不同取舍。

1. CAP历史

2000年, Eric Brewer教授在PODC研讨会上提出一个猜想[1]:一致性、可用性和分区容错性三者无法在分布式系统中被同时满足,并且最多只能满足其中两个!

这个猜想首次把一致性、可用性和分区容错三个因素提炼出来作为系统设计的重要特征,断言用此三者可以划分所有的分布式系统,并指明这三个特征之间的不可能性关系。

Brewer教授当时想象的分布式场景是webservice,一组webservice后台运行众多server,对service的读写会反应到后台的server集群,并且对CAP进行定义:

  • Strong consistency: means single-copy ACID consistency;
  • High availability: 通过冗余(比如副本)提供高可用。如果特定数据消费者能够一直访问一些副本,那么数据被认为是高可用。
  • Partition-resilience: 当出现数据副本分区时,系统可以存活。

Strong CAP Principle:Strong Consistency, High Availability, Partition-resilience:最多选择两个。

CAP猜想清晰表达在设计分布式应用的取舍,

  • CA without P: 在没有网络分区的情况下,数据库提供分布式事务语义。
  • CP without A: 有网络分区下,在分区恢复之前,更多的ACID数据库的事务都会被阻塞,从而避免引入合并冲突,并带来不一致。
  • AP without C: 出现分区时,数据出现不一致。 通常,任何分布式数据问题可以通过基于过期的caching来获得AP,或多数选举获得PC(少数人群是不可用的)。

Weak CAP Principle: 保证CAP的两个更强,那么意味着另外一个更弱。

2. CAP被上升为定理,

2002年,Lynch与其他人[2]证明了Brewer猜想,从而把CAP上升为一个定理。但是只是证明了CAP三者不可能同时满足,并没有证明任意二者都可满足的问题,所以,该证明被认为是一个收窄的结果。

Lynch的证明采用反证法:如果三者同时满足,则因为P的存在,那么一定存在Server之间丢包,那么就不能保证C,证明简洁而严谨。

在该证明中,CAP进行更明确的声明:

  • C:一致性被称为原子对象,任何读写都应该看起来是原子的,又叫线性化。写后面的读一定能读到前面写的内容。所有的读写请求都好像被全局排序。
  • A:对任何非失败节点都应该在有限时间内给出响应。(请求的可终止性)
  • P:允许节点之间丢失任意多的消息,当网络分区发生时,节点之间的消息可能会完全丢失。

3. CAP的质疑

CAP理论考虑的场景很少,提供的是一个大的思路;不同论文/文章针对具体场景去质疑时,总能够指出CAP不合理的地方。

但一个比较重要的地方就是不要真的只是进行三选二。比如在没有网络分区时,一致性和可用性也只能二选一。

以下是几篇论文和文章对CAP的质疑,有兴趣的可以了解一下

3.1 质疑1:

文章[8]中对CAP有一系列描述,没太明白在说什么。

3.2 质疑2: 不要快速丢弃掉C

[3]中,其质疑的主张是:CAP必须放弃某一个目标。从错误中恢复有很多维度要考虑,该文章解释了很多种错误。结论是:不要轻易放弃C。因为分区容错在局域网中很少发生,在广域网中也有各种备选方案。

3.3 质疑3 构建不可避免模型避免CAP的复杂性

文章[4]的标题是锤死CAP。
作者认为CAP困境在于允许数据变更,每次变更都得数据同步,保持一致性,他认为数据是客观存在的,维护增删操作(译注:我个人认为是LSM log-structured message tree的理念)。
作者认为数据模型可以抽象为Query=Function(all data),完全抛弃CAP中繁琐且模糊的定义。

我个人觉得:这篇文章只是换了一个角度来说明分布式系统,与CAP没啥关系。

4. 对质疑的回应

面对大量的质疑,Brewer和Lynch进行重申,

Brewer在2012你那重申[5]:

  • 3选2这个表述是不准确的,在某些分区极少发生的情况下,三者能顺畅在一起配合。没有P时是CA,发生P时是PC或PA
  • CAP不仅仅发生在整个系统中,可能是发生在某个子系统或系统的某个阶段
  • CAP中每一个都是连续取值,而不是0-1关系。

Lynch在10年后的2012年重写了论文[9],该论文主要做了几件事:

  • 一致性场景不会引入用户agent,只发生在后台集群之内
  • 引入了活性(liveness)和安全属性(safety),在一个更抽象的概念下研究分布式系统,并认为CAP是活性与安全熟悉之间权衡的一个特例。其中的一致性属于liveness,可用性属于safety
  • 把分区容错归结为一个对网络环境的陈述,而非之前一个独立条件。这实际上就是更加明确了概念
  • 把CAP的研究推到一个更广阔的空间:网络存在同步、部分同步;一致性性的结果也从仅存在一个到存在N个(部分一致);引入了通信周期round,并引用了其他论文,给出了为了保证N个一致性结果,至少需要通信的round数。也介绍了其他人的一些成果,这些成果分别都对CAP的某一个方面做出了特殊的贡献!

其实Lynch论文主要做了两件事:

  • 缩小CAP适用的定义,消除质疑的场景;
  • 展示了CAP在非单一一致性结果下的广阔研究成果!并顺便暗示CAP定理依旧正确!

5. 很多系统既不是线性化 也不是CAP-Available [6]

基于严格的CAP定义,很多系统既不是线性化、也不是CAP-Available。

举例,考虑单主的多副本数据库,这是大多数关系型数据库创建副本的标准方式。在这种配置下,如果一个client与leader分离,那么它就不能再向数据库写入数据。即使可以从follower读取数据,但已经不能写入,这就不符合CAP-Avaible。当然这种配置常常被叫做“高可用性”。

如果单主复制不是CAP-Avaible,那么是不是CP呢?并不一定是。如果运行应用从follower读取数据,并且复制是异步的,那么副本可能会落后于leader,这时候读取就不是线性的,不符合CAP-consistent。

所以这些系统既不是CAP-consistent,也不是CAP-avaible。他们只是P。

以Zookeeper为例:

zookeeper使用consensus algorithm,所以人们常常将其看做是选择一致性高于可用性的例子,但事实上,zk默认是不提供线性读取。连接到数据库某个节点的client,读取的是该节点上的数据,即时最新的数据在其他节点。 默认Zookeeper不满足CAP中的C。

关于Zookeeper的Availablility?

zk采用法定人数的方式实现共识。那么多数节点是可用的,而少数节点的集群是不能写入的,不符合ZK的CAP-available。

6. 该如何看待CAP

  • 当我们提到CAP的时候,首先我们指的是严格的CAP定义;
  • 首先肯定的是,CAP并不适合再作为一个适应任何场景的定理,它的正确性更适合基于原子读写的NoSQL场景
  • 无论如此,C、A、P三个概念始终存在于任何分布式系统,只是不同模型会有不同呈现;一个系统的不同子模块会有不同关系;
    • 在没有出现P(分区时),可以实现CA;
    • 在出现P时,CA二选一,或者实现的是 C+HA
  • 当我们分析一个系统的时候,要从多个维度去分析,比如etcd是CP+HA [10]
  • 有一个CAP理论的扩展叫PACELC理论

论文

  1. Harvest, Yield, and Scalable Tolerant Systems
  2. Brewer’s Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web
  3. Errors in Database Systems, Eventual Consistency, and the CAP Theorem
  4. How to beat the CAP theorem
  5. CAP Twelve Years Later: How the “Rules” Have Changed
  6. Please stop calling databases CP or AP
  7. CAP理论
  8. Deconstructing the `CAP theorem’ for CM and DevOps
  9. Perspectives on the CAP Theorem
  10. understanding etcd3 (需要翻墙)

分布式-事务

本文是《数据密集型应用系统设计》(英文:Designing Data-Intensive Applications) 第7章学习总结。

在总结之前,提问几个问题:

  1. 什么是事务?
  2. 为什么引入事务
  3. 事务中最核心的问题是什么?
  4. 事务中隔离级别有哪些级别,级别划分依据是什么?
  5. 隔离级别解决了哪些问题,哪些没有解决
  6. 如何实现这些隔离级别

一、事务

什么是事务

在应用程序中,将一组数据库的读写组成一个逻辑操作单元;即事务中所有读写是一个执行的整体,整个事务要么成功(提交),要么失败(中止或回滚)。如果失败,应用程序可以安全地重试。

为什么引入事务

简化应用层的编程模型:当一组读写中部分写入成功,部分写入失败时,我们需要将成功的进行回滚;如果数据库不引入事务,就需要业务层自己处理。

如何判断是否需要事务?

我们需要确切地理解事务能够提供哪些安全性保证,背后的代价又是什么。

事务提供的安全性保证

事务提供的安全性保证即大家熟悉的ACID。

  • Atomic(原子性):执行要么全部成功,要么全部失败。在出错时中止事务,并将部分完成的写入全部丢弃。
  • Consistency(一致性):这儿的一致性是符合数据的约束条件(比如数据x=y,x+y=100等)
  • Isolation(隔离):意味着并发执行的多个事务相互隔离,他们不能互相交叉。经典数据库教材中把隔离定义为可串行化。
  • Duration(持久化):数据持久化

其中AID是数据库自身属性,C是应用层属性,AID来保证C。

二、隔离级别

2.1 什么时候需要隔离?

如果两个事务操作的是不同的数据,即不存在数据依赖关系,那么就可以安全地并行。

只有出现某个事务修改数据而另外一个事务同时读取该数据,或者两个事务同时修改相同数据时,才会引起并发问题。

2.2 隔离级别的定义

ANSI/ISO SQL-92中定义了四种隔离级别Read-Commited, Repeatable Read, Snapshot Isolation, Seriable。这些隔离级别是通过经典的序列化定义和三种被禁止的子序列来定义的。三种被禁止的子序列是Dirty Read, Non-repeatable Read 和 phantom(幻象)。

通俗来讲,就是禁止了哪些问题就达到了某个隔离级别;隔离级别也都是与特定的锁有对应关系的

隔离级别也是与lock有关的。

2.3 异常现象(异常子序列)

这些异常现象将会用如下格式进行详细描述:

  • 问题的文字描述
  • 问题的序列化表示
  • 问题的例子
  • 问题的解决方案

关于锁的解释

  1. long-duration vs short duration
    • 长期锁是在加锁以后,直到事务结束或回滚才释放锁
    • 短期锁是在动作结束以后,就立即释放锁
  2. predict vs 行锁

    • predict lock是针对一个查询条件加锁
    • 行锁是针对特定一行记录加锁

脏写 Dirty Write P0

  1. 问题的文字描述:一个正在进行的事务覆盖了另外一个事务尚未提交的写入。
  2. 问题的序列化表示:W1(x)…W2(x) … (c1 or a1)
  3. 问题的解决办法:对写入加一个long-duration write lock。
  4. 说明:
    • Dirty write是ANSI/ISO SQL-92中没有提到的,但是需要避免,是基础。
    • 如果有脏写,那么会没有办法回滚,也可能影响数据约束(x=y or x+y=100)
  5. 举例:Suppose T1 writes x=y=1 and T2 writes x=y=2, the following history violates the integrity constraint.

脏读 Dirty Read P1

  1. 问题的文字描述:一个正在进行的事务读取了另外一个事务未提交的写入。
  2. 问题的序列化表示:W1(x)..R2(x) ..(c1 or a1)
  3. 问题的解决办法:加入一个short-duration read lock。
    • 写是long-duration write lock, 读是short-duration read lock,当正在发生写入的事务占有锁时,读取的事务因为没有办法获得读锁,只能等待。
    • 注明:1中使用读锁来实现,但是在最新的数据库中数据库维护新旧两个取值,事务提交之前读取旧值;仅当写事务提交以后,才会切换到读取新值。
  4. 说明:
    • 解决该问题的隔离级别就是 Read-Commited(读-提交) 隔离级别
  5. 举例:
    • 序列化:H1: r1[x=50]w1[x=10]r2[x=10]r2[y=50]c2 r1[y=50]w1[y=90]c1
    • 如下图所示 t2中 x+y=60,其中x=10是脏读,

不可重复读 unrepeatable-read P2

  1. 问题的文字描述:事务在不同的时间点看到不同值。事务T2修改了之前事务T1读过的数据,不管T1、T2是提交还是回滚,就认为是nonrepeatable-read
  2. 问题的序列化表示:R1(x)..W2(x)..(c1 or a1)
  3. 问题的解决办法:snapshot isolation,多版本
  4. 说明:不可重复读实际是 读倾斜的x等于y的一个特例
  5. 举例:因为不可重复读可以看做是读倾斜x等于y的一个特例,可以去看 读倾斜的例子。

幻象 phantom P3

  1. 问题的文字描述:

    事务T1读取一组数据集合满足条件。事务T2创建了满足T1中的数据集合并提交,那么T1重复读取时,将会获取到跟之前不同的数据

  2. 问题的序列化表示:R1(P)… W2(y in P)…(c1 or a1)

  3. 问题的解决办法:采用区间范围锁 index-range lock,又叫next-key lock
  4. 说明:
    • Nonrepeatable和幻象的区别 一个单个对象,一个是多个对象
严格意义的幻象 A3
  1. 问题的序列化表示:R1(p)..W2(y in p)..c2..r1(p)…c1
  2. 与P3相比更加严格,有一次T1的读取操作。
  3. 问题解决办法:使用snapshot isolation即可解决

更新丢失 Losst update P4

  1. 问题的文字描述:事务T2对X的修改被事务T1的修改覆盖。之后事务T1提交,从外界看来,T1对X的修改丢失
  2. 问题的序列化表示:R1(x)..W2(x)..W1(x)..C1
  3. 问题的解决办法:snapshot isolation,多版本
  4. 举例:
    • 序列化是 H4: r1[x=100]r2[x=100]w2[x=120 c2 w1 [x=130] c1
    • 预期是从100经过+20,+30,最后取值是150;实际是130。如图所示

更新丢失 Cursor Lost update P4C

P4C is a variation of the Lost Update phenomenon that involves a SQL cursor. In the history below, let rc(x) represent a read of the data item x under the cursor, and wc(x) a write of the data item x under the cursor. If we allow another transaction T2 to write to x in between the read-cursor and write-cursor actions of T1, then its update will be lost.

序列化表示:P4C: rc1[x]..w2[x] ..w1[x] ..c1

数据不一致 data item constraint violation A5

  1. 问题的文字描述:两个数据X和Y满足某些限制,可能有以下异常情况出现:
    • A5A Read Skew: 假设T1读取X,之后T2更新x和y到了新的取值,并提交;之后T1读取y,则x和y的限制被打破。
    • A5B Write Skew: 假设T1读取X和Y,之后T2读取X和Y,并写入X,然后提交;之后T1 写入Y,那么存在X和Y的限制被打破的可能

A5A Read Skew:

  1. 序列化表示:A5A: R1(x)..W2(x)..W2(y)..C2 …R1(y) .. (c1 or a1)
  2. 举例:
    以银行转账为例,初始化x=y=50,从x转走40到y,最终预期是x=10,y=90。
    出现脏读时,其读取数据是 r1[x=5]r2[x=50]w2[x=10]r2[y=50]w2[y=90]c2r1[y=90]c1
    数据如图所示,t1中x+y=140不满足100的限制。 ![](分布式-事务/repeatable read.jpeg)
    

A5B Write Skew:

  1. 序列化表示:A5B:R1(x)..R2(y)..W1(y)..W2(x)..(c1 and c2 occur)
  2. 举例:

2.4 隔离级别

可以通过刻画他们禁止的异常情况来刻画隔离级别

他们之间的关系如下图所示

我们可以通过他们允许的非序列化历史来比较隔离级别:

  • L1 is weaker than L2 if L1 permits non-serializable histories that L2 does not, and every non-serializable history under L2 is also a non-serializable history under L1. We write L1 << L2.
  • L1 and L2 are equivalent if the sets of non-serializable histories permitted by them both are identical. We write L1 == L2
  • L1 and L2 may also be incomparable. If L1 permits a non-serializable history that L2 does not, and vice-versa, then L1 is not weaker than L2, but L2 is also not weaker than L1. We write L1 <> L2.

结论1:

我们可以得到

Degree 0 (everything goes) << Read Uncommitted << Read Committed << Cursor Stability << Repeatable Read << Serializable.

重点解释一下 Cursor Stability,Cursor Stability是扩展Read Commited锁行为。//TODO 待补充

结论2:

Read commited << snapshot isolation

ANOMALY Serializable << Snapshot isolation

repeatable read <> snapshot isolation 这两个是不可比较的。

许多应用通过使用cursor stability 或 oracle’s read consistency isolation 来避免锁竞争。对于这些应用而言,使用Snapshot Isolation会更好:

  • 避免lost update
  • 严格意义的幻象(如上面所说明的A3,但不能定义更广的P3)
  • 从不阻塞只读的事务,读取不会阻塞更新

参考文章

  1. Hal Berenson, Philip A. Bernstein, Jim N. Gray, et al.: “A Critique of ANSI SQL Isolation Levels,” at ACM International Conference on Management of Data (SIG‐ MOD), May 1995
  2. A Critique of ANSI SQL Isolation Levels 解释
  3. A Critique of ANSI SQL Isolation Levels 阅读笔记
  4. 数据密集型应用系统设计 chapter 7 事务

golang继承

项目中已经经常使用golang继承,现在总结一下,主要摘在Golang中的面向对象继承

总结如下:

  1. golang使用组合,可以将两个结构体简单组合形成一个新的数据类型
  2. 可以通过匿名嵌入方式实现继承,从而共享代码和数据
  3. 匿名嵌入有三种方式

    • 接口类型
    • 结构体实例
    • 结构体实例指针

    接口类型更加灵活,只要实现这个接口的方法都可以进行赋值。

    继承自其它结构体的struct类型可以直接访问父类结构体字段/方法

  4. 嵌入继承机制的局限

    Golang从根本上阻止了抽象方法的使用。

  5. 多态性

    golang不支持多态,即不能用子类替换父类。
    但是golang支持接口类型的多态机制,只要结构体实现了接口的方法就可以进行赋值。

spark quick start

注意, Spark2.0 之前的版本,Spark的主要编程接口是RDD(Resilient Distributed Dataset)。2.0以后的版本,主要编程接口替换为Dataset。当然了RDD接口依然支持,可以从RDD programming guide。但是,我们强烈建议你切换到Dataset,比RDD有更好的性能。 关于Dataset可以从SQL programming guide获得更多细节。

使用SparkShell进行交互分析

基础内容

启动 ./bin/spark-shell

基本执行:

val textFile = spark.read.textFile("README.md")
textFile.count() // Number of items in this Dataset
textFile.first() // first item in this Dataset

将一个Dataset转换为新的一个。 调用filter返回新的Dataset,是原始文件的一个子集

val linesWithSpark = textFile.filter(t => t.contains("Spark"))

这儿有个疑问,如何打印出dataset中内容??

更多的Dataset的操作

Dataset的actions和transformation 可以用于更多的复杂运算。

textFile.map(line => line.split(" ").size).reduce((a,b) => if (a > b) a else b)
res4: Long = 15

map和reduce的参数都是scala的匿名函数,还可以使用scala/java 库。例如 可以使用Math.max()函数。

import java.lang.Math
textFile.map(line => line.split(" ").size).reduce((a, b) => Math.max(a,b))

一个通用的数据处理流程是MapReduce。Spark可以很容易的实现MapReduce流。

val wordCounts = textFile.map(line => line.split(" ")).groupByKey(identity).count()

Caching

spark支持将dataset写入cluster-wide in-memory cache。
当数据重复获取时,这还是很有用的。

Self-Contained Application

使用SparkAPI创建一个self-contained应用。

import org.apache.spark.sql.SparkSession

object SimpleApp {
  def main(args: Array[String]) {
    val logFile = "README.md" // Should be some file on your system
    val spark = SparkSession.builder.appName("Simple Application").getOrCreate()
    val logData = spark.read.textFile(logFile).cache()
    val numAs = logData.filter(line => line.contains("a")).count()
    val numBs = logData.filter(line => line.contains("b")).count()
    println(s"Lines with a: $numAs, Lines with b: $numBs")
    spark.stop()
  }
}

其中SparkSession.builder构造一个[[SparkSession]],使用设置application name,最后调用getOrCreate获取[[SparkSession]]实例。

也可以使用maven来进行包管理。

目录结构:

./pom.xml
./src
./src/main
./src/main/scala
./src/main/scala/didi
./src/main/scala/didi/map
./src/main/scala/didi/map/pointsys
./src/main/scala/didi/map/pointsys/App.scala
./src/test
./src/test/scala
./src/test/scala/didi
./src/test/scala/didi/map
./src/test/scala/didi/map/pointsys

App.scala内容:

package didi.map.pointsys

import org.apache.spark.sql.SparkSession
object MyFunctions {
  def func1(s: String): String = {
    s.concat("yankai")
  }
}
// spark-submit --class="didi.map.pointsys.SimpleApp" parking-user-profile-1.0-SNAPSHOT.jar
object SimpleApp {
  def main(args: Array[String]) {
    val logFile = "README.md" // Should be some file on your system
    val ss = SparkSession.builder().appName("Simple Application").enableHiveSupport().getOrCreate()
    val logData = ss.read.textFile(logFile)
    //val pairs = logData.map(s => (s, 1))

    val numAs = logData.filter(line => line.contains("a")).count()
    val numBs = logData.filter(line => line.contains("b")).count()
    println(s"Lines with a: $numAs, Lines with b: $numBs")
    ss.stop()
  }
}

pom.xml

<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/maven-v4_0_0.xsd">
  <modelVersion>4.0.0</modelVersion>
  <groupId>didi.map.pointsys</groupId>
  <artifactId>parking-user-profile</artifactId>
  <version>1.0-SNAPSHOT</version>
  <inceptionYear>2008</inceptionYear>
  <properties>
    <encoding>UTF-8</encoding>
    <scala.binary.version>2.11</scala.binary.version>
    <scala.major.version>2.11</scala.major.version>
    <deploy.scala.version>2.11</deploy.scala.version>
    <scala.version>2.11.8</scala.version>
    <scala.compat.version>2.11</scala.compat.version>
    <spark.version>2.2.0</spark.version>
  </properties>

  <dependencies>
    <dependency>
      <groupId>junit</groupId>
      <artifactId>junit</artifactId>
      <version>4.12</version>
      <scope>test</scope>
    </dependency>

    <dependency>
      <groupId>org.apache.spark</groupId>
      <artifactId>spark-core_2.11</artifactId>
      <version>2.3.0</version>
      <scope>provided</scope>
    </dependency>
    <dependency>
      <groupId>org.apache.spark</groupId>
      <artifactId>spark-sql_2.11</artifactId>
      <version>2.3.0</version>
      <scope>provided</scope>
    </dependency>
    <dependency>
      <groupId>org.apache.hadoop</groupId>
      <artifactId>hadoop-client</artifactId>
      <version>2.7.2</version>
      <scope>provided</scope>
    </dependency>

  </dependencies>
  <build>
    <sourceDirectory>src/main/scala</sourceDirectory>
    <testSourceDirectory>src/test/scala</testSourceDirectory>
    <plugins>
      <!-- bind the maven-assembly-plugin to the package phase this will create
          a jar file without the storm dependencies suitable for deployment to a cluster. -->

      <plugin>
        <groupId>net.alchim31.maven</groupId>
        <artifactId>scala-maven-plugin</artifactId>
        <version>3.2.0</version>
        <executions>
          <execution>
            <goals>
              <goal>compile</goal>
              <goal>testCompile</goal>
            </goals>
          </execution>
        </executions>
        <configuration>
          <scalaVersion>${scala.version}</scalaVersion>
        </configuration>
      </plugin>

      <plugin>
        <groupId>org.apache.maven.plugins</groupId>
        <artifactId>maven-assembly-plugin</artifactId>
        <version>2.2-beta-5</version>
        <configuration>
          <descriptorRefs>
            <descriptorRef>jar-with-dependencies</descriptorRef>
          </descriptorRefs>
        </configuration>
        <executions>
          <execution>
            <phase>package</phase>
            <goals>
              <goal>single</goal>
            </goals>
          </execution>
        </executions>
      </plugin>

      <plugin>
        <groupId>org.apache.maven.plugins</groupId>
        <artifactId>maven-compiler-plugin</artifactId>
        <version>3.5.1</version>
        <configuration>
          <source>1.8</source>
          <target>1.8</target>
        </configuration>
      </plugin>
      <!-- disable surefire -->
      <plugin>
        <groupId>org.apache.maven.plugins</groupId>
        <artifactId>maven-surefire-plugin</artifactId>
        <version>2.7</version>
        <configuration>
          <skipTests>true</skipTests>
        </configuration>
      </plugin>
      <!-- enable scalatest -->
      <!-- <plugin>
        <groupId>org.scalatest</groupId>
        <artifactId>scalatest-maven-plugin</artifactId>
        <version>1.0</version>
        <configuration>
          <reportsDirectory>${project.build.directory}/surefire-reports</reportsDirectory>
          <junitxml>.</junitxml>
          <filereports>WDF TestSuite.txt</filereports>
        </configuration>
        <executions>
          <execution>
            <id>test</id>
            <goals>
              <goal>test</goal>
            </goals>
          </execution>
        </executions>
      </plugin>
      -->
    </plugins>

    <resources>
      <resource>
        <directory>src/main/resources</directory>
      </resource>
    </resources>

  </build>
</project>

在target目录下会生成jar文件,使用spark-submit进行提交。

spark-submit --class="didi.map.pointsys.SimpleApp" parking-user-profile-1.0-SNAPSHOT.jar

golang包导入

golang包导入

go源代码是按package方式组织,再通过import引入使用。

工作目录

在Go中代码保持在称之为workspace的系统文件夹中。这个工作目录有三个根目录:

  • bin:包含可执行文件
  • pkg:包含不同操作系统架构的包二进制文件。
  • src:包含按包方式组织的源代码

其中bin和pkg文件夹是在调用go命令安装和编译源代码时自动生成。

必须让Go知道工作目录的位置,这样才能知道包的具体位置。 通过设置环境变量GOPATH来指定。

导入包

  1. $GOPATH/src/importpackage/lib/lib.go

    package lib
    
    import "fmt"
    
    func SayHello() {
        fmt.Println("Hello,I'm in myLib :) ")
    }
    
  2. $GOPATH/src/importpackage/app/main.go

    package main
    
    import "importpackage/lib"
    
    func main() {
        lib.SayHello()
    }
    
  3. 目录结构:

    .
    └── src
        └── importpackage
            ├── app
            │   └── main.go
            └── lib
                └── lib.go
    

    go build -o main src/importpackage/app/main.go

导入包的多种方式

  • 代码统一存储在工作目录下
  • 工作目录里面有多个包,不同包按目录组织,包下面由多个代码文件组成。
  • 导入包时按包的唯一路径进行导入,导入的包默认是必须要使用,如果不使用则编译失败,需要移除,减少不必要代码的引入,当然还有其他使用场景。默认情况下,我们使用文件名做为包名,方便理解。不同包组织不同的功能实现,方便理解。

golang-面向对象编程

理解golang面向对象

面向对象编程的三个核心是:封装、继承、多态。

  1. 封装(encapsulation)

    封装就是将抽象得到的数据和行为(或功能)相结合,形成一个有机的整体,也就是将数据与操作数据的源代码进行有机的结合,形成“类”,其中数据和函数都是类的成员。

    封装的目的是增强安全性和简化编程,使用者不必了解具体的实现细节,而只是要通过 外部接口,一特定的访问权限来使用类的成员。
    即不直接暴露数据,而暴露的是接口.

    go封装是package层面的。小写开头的Names只能在包内可见。在一个private package可以隐藏所有东西,并只暴露特定类型、接口、工厂函数。

  1. 继承

    继承是指一个对象直接使用另一对象的属性和方法。事实上,我们遇到的很多实体都有继承的含义。例如,若把汽车看成一个实体,它可以分成多个子实体,如:卡车、公共汽车等。这些子实体都具有汽车的特性,因此,汽车是它们的“父亲”,而这些子实体则是汽车的“孩子”。

现代语言认为实现继承更好的方式是组合(composition)。go采用这种理念,并且没有任何等级内容(hierarchy)。 这允许你使用组合来共享实现的细节。go是通过嵌入(embedding)的方式来实现匿名组合的(anonymous composition)。 

通过嵌入一个匿名类型的组合实现了继承。 嵌入的结构体等同于基类(base class)。当然了也可以嵌入一个接口,但是必须注意,嵌入一个接口时,该结构体必须实现这个接口的方法,不然会报runtime error。

报错:panic: runtime error: invalid memory address or nil pointer dereference
  1. 多态(polymorphism)

    多态是允许你将父对象设置成为和一个或更多的子对象相等的技术。赋值会后,父对象就可以根据当前赋值给它的子对象以不同的方式运作。简单来说,允许将子类类型的指针赋值给父类类型的指针。 在C++中都是通过虚函数(Virtual Function)实现的。golang允许接口的子类的多态,但不允许子类替换为父类

实际例子

在我们实际项目中用到多态的地方很多,举一个例子 获取下游服务的节点列表:
需求:

  • 希望支持多种方式获取节点列表,比如配置文件、服务发现、http请求等;
  • 希望通过配置获取顺序的方式来实现优先级,比如配置是get_type=服务发现,配置文件,http请求。那么当服务发现获取节点成功时,则使用服务发现;反之如果服务发现获取节点列表失败,则需要使用配置文件的方式。

抽象:

  • 定义一个接口IConfObj:
  • check函数:为了检查配置文件的配置项是否完备,因为不通获取方式,配置文件不一样;

    + run函数:执行节点获取,并执行 InterfaceAction来执行节点更新。
    
    • 定义一个获取节点后动作的func,目的就是在获取节点后,通过该func进行操作。

      type IConfObj interface {
          check() error
          run() (bool, error)
      }
      
      type InterfaceAction func(hosts []string, is_high_node, is_primary bool) (bool, error)
      
    • 实现节点列表获取配置化

      • 不同的获取获取方式实现这个接口,并进行注册。
      • 根据注册先后顺序执行run,如果run成功则结束遍历,反之继续执行直至成功。

参考文章:

https://code.tutsplus.com/tutorials/lets-go-object-oriented-programming-in-golang--cms-26540