学习笔记6

2017-12-28  本文已影响0人  molscar

1. 分布式系统核心问题

参考书籍：《区块链原理、设计与应用》

  1. 一致性问题

    例子：两个不同的电影院买同一种电影票，如何避免超售？如何保持两个电影院数据一致？

    挑战

    • 节点之间的网络通讯是不可靠的，包括任意延迟和内容故障；
    • 节点的处理可能是错误的，甚至节点自身随时可能宕机；
    • 同步调用会让系统变得不具备可扩展性。

    要求

    • 可终止性（Termination）：一致的结果在有限时间内能完成；

    • 共识性（Consensus）：不同节点最终完成决策的结果应该相同；

      eg：现在就剩一张票了，两个电影院也分别刚确认过这张票的存在，然后两个电影院同时来了一个顾客要买票，从各自“观察”看来，自己的顾客都是第一个到的……怎么能达成结果的共识呢？记住我们的唯一秘诀：核心在于需要把两件事情进行排序，而且这个顺序还得是大家都认可的。

    • 合法性（Validity）：决策的结果必须是其它进程提出的提案。

  2. 共识算法

    保障分布式系统的一致性，需要通过共识算法来实现。

    简述：对某个提案，大家达成一致的过程。

  3. FLP 不可能性原理

    FLP 不可能原理：在网络可靠，存在节点失效（即便只有一个）的最小化异步模型系统中，不存在一个可以解决一致性问题的确定性算法。

    eg: 三个人在不同房间，进行投票（投票结果是 0 或者 1）。三个人彼此可以通过电话进行沟通，但经常会有人时不时地睡着。比如某个时候，A 投票 0，B 投票 1，C 收到了两人的投票，然后 C 睡着了。A 和 B 则永远无法在有限时间内获知最终的结果。

    FLP原理只是最坏的情况下，但是我们可以付出一些代价来提高成功的概率。

  4. CAP 原理

    分布式计算系统不可能同时确保一致性（Consistency）、可用性（Availablity）和分区容忍性（Partition），设计中往往需要弱化对某个特性的保证。

    • 一致性（Consistency）：任何操作应该都是原子的，发生在后面的事件能看到前面事件发生导致的结果，注意这里指的是强一致性；

    • 可用性（Availablity）：在有限时间内，任何非失败节点都能应答请求；

    • 分区容忍性（Partition）：集群中的某些节点在无法联系后，集群整体是否还能继续进行服务。

      分隔容忍(Partition tolerance) (系统中任意信息的丢失或失败不会影响系统的继续运作)

    应用：

    网络中会经常会出现延迟丢包等问题，所以分区容忍性一般不会弱化。

    • 弱化一致性

      对结果一致性不敏感的应用，可以允许在新版本上线后过一段时间才更新成功，期间不保证一致性。

    • 弱化可用性

      对结果一致性很敏感的应用，例如银行取款机，当系统故障时候会拒绝服务。

  5. ACID 原则

    ACID 原则描述了对分布式数据库的一致性需求，同时付出了可用性的代价。

    • 原子性（Atomicity）：每次操作是原子的，要么成功，要么不执行；
    • 一致性（Consistency）：数据库的状态是一致的，无中间状态；
    • 隔离性（Isolation）：各种操作彼此互相不影响；
    • 持久性（Durability）：状态的改变是持久的，不会失效。

    一个与之相对的原则是 BASE（Basically Available（基本可用）、Soft state（软状态）和Eventually consistent（最终一致性）），牺牲掉对一致性的约束（最终一致性），来换取一定的可用性。

  6. Paxos 与 Raft

    • Paxos

      问题背景：古希腊 Paxon 岛上的多个法官在一个大厅内对一个议案进行表决，如何达成统一的结果。他们之间通过服务人员来传递纸条，但法官可能离开或进入大厅，服务人员可能偷懒去睡觉。

      算法中将节点分为三种类型：

      • proposer：提出一个提案，等待大家批准为结案。往往是客户端担任该角色；
      • acceptor：负责对提案进行投票。往往是服务端担任该角色；
      • learner：被告知结案结果，并与之统一，不参与投票过程。可能为客户端或服务端。

      算法需要满足 safety 和 liveness 两方面的约束要求：

      • safety：保证决议结果是对的，无歧义的，不会出现错误情况。
        • 决议（value）只有在被 proposers 提出的 proposal 才能被最终批准；
        • 在一次执行实例中，只批准（chosen）一个最终决议，意味着多数接受（accept）的结果能成为决议；
      • liveness：保证决议过程能在有限时间内完成。
        • 决议总会产生，并且 learners 能获得被批准（chosen）的决议。

      基本过程包括 proposer 提出提案，先争取大多数 acceptor 的支持，超过一半支持时，则发送结案结果给所有人进行确认。一个潜在的问题是 proposer 在此过程中出现故障，可以通过超时机制来解决。极为凑巧的情况下，每次新的一轮提案的 proposer 都恰好故障，系统则永远无法达成一致（概率很小）。

      Paxos 能保证在超过 img

      的正常节点存在时，系统能达成共识。

    • Raft

      Raft 算法是Paxos 算法的一种简化实现。

      包括三种角色：leader、candidate 和 follower，其基本过程为：

      1. Leader 选举：每个 candidate 随机经过一定时间都会提出选举方案，最近阶段中得票最多者被选为 leader；
      2. 同步事件记录 log：leader 会找到系统中 log 最新的记录，并强制所有的 follower 来刷新到这个记录。

  7. 拜占庭问题

    拜占庭是古代东罗马帝国的首都，由于地域宽广，守卫边境的多个将军（系统中的多个节点）需要通过信使来传递消息，达成某些一致的决定。但由于将军中可能存在叛徒（系统中节点出错），这些叛徒将努力向不同的将军发送不同的消息，试图会干扰一致性的达成。

    拜占庭问题即为在此情况下，如何让忠诚的将军们能达成行动的一致?

    Byzantine Fault Tolerant (BFT) 算法

    ​ BFT算法保证所有正常的replicas节点执行相同序列的操作。因为所有的replicas节点都是deterministic，而且初始状态都相同，根据状态机原理（state machine replication），这些replicas会产生相同的结果状态。当Client收到f+1个replicas节点返回的结果时，如果这些结果都一样，因为BFT算法确保了最多有f个replicas出现问题，所以至少有一个replicas是正确的，那么Client收到的这些结果都是正确的。

    其他解决思路：

    问题由来：系统存在多个提案，一致确认困难

    PoW（Proof of Work） 算法思路：

    1. 增加提案成本（限制了提案数量）
    2. 放宽对最终一致性确认的需求，约定好大家都确认并沿着已知最长的链进行拓宽。

    注：系统的最终确认是概率意义上的存在。这样，即便有人试图恶意破坏，也会付出很大的经济代价（付出超过系统一半的算力）。

  8. 可靠性指标

    下表给出不同指标下，每年允许服务出现不可用时间的参考值。

    指标 概率可靠性 每年允许不可用时间 典型场景
    一个九 90% 1.2 个月 不可用
    二个九 99% 3.6 天 普通单点
    三个九 99.9% 8.6 小时 普通企业
    四个九 99.99% 51.6 分钟 高可用
    五个九 99.999% 5 分钟 电信级
    六个九 99.9999% 31 秒 极高要求
    七个九 99.99999% 3 秒 N/A
    八个九 99.999999% 0.3 秒 N/A
    九个九 99.9999999% 30 毫秒 N/A

2. Raft算法

参考学习链接：

Raft 算法实现推荐：

其他：状态机

1. 概述

Raft 是一种为了管理复制日志的一致性算法。它提供了和 Paxos 算法相同的功能和性能，但是它的算法结构和 Paxos 不同，使得 Raft 算法更加容易理解并且更容易构建实际的系统。Raft 将一致性算法分解成了几个关键模块，例如 领导人选举、日志复制和安全性 。

2. Raft基础

服务器节点的三种状态：

下面是这三种状态的转化过程：

图 4

跟随者只响应来自其他服务器的请求。如果跟随者接收不到消息，那么他就会变成候选人并发起一次选举。获得集群中大多数选票的候选人将成为领导者。在一个任期内,领导人一直都会是领导人直到自己宕机了。

3. 领导人选举

可参考 官方可视化动画1 官方可视化动画2

4. 日志复制

  1. 复制过程

    Leader选举出来后，就可以开始处理客户端请求。Leader收到客户端请求后，将请求内容作为一条log日志添加到自己的log记录中，并向其它server发送RPCs(添加日志)请求。其它server收到请求后，如果满足条件就将其添加到本地的log中，并给Leader发送添加成功的response。Leader在收到大多数server添加成功的response后，就将该条log正式提交到状态机中。

  2. 一致性保持

    当一个领导人刚获得权力的时候，他初始化所有的 nextIndex 值为自己的最后一条日志的index（索引）加1。如果一个跟随者的日志和领导人不一致，那么在下一次的附加日志 RPC 时的一致性检查就会失败。在被跟随者拒绝之后，领导人就会减小 nextIndex 值并进行重试。最终 nextIndex 会在某个位置使得领导人和跟随者的日志达成一致。当这种情况发生，附加日志 RPC 就会成功，这时就会把跟随者冲突的日志条目全部删除并且加上领导人的日志。一旦附加日志 RPC 成功，那么跟随者的日志就会和领导人保持一致，并且在接下来的任期里一直继续保持。

5. 安全性

  1. 选举限制

    候选人为了赢得选举必须联系集群中的大部分节点，这意味着每一个已经提交的日志条目在这些服务器节点中肯定存在于至少一个节点上。如果候选人的日志至少和大多数的服务器节点一样新，那么他一定持有了所有已经提交的日志条目。请求投票 RPC 实现了这样的限制： RPC 中包含了候选人的日志信息，然后投票人会拒绝掉那些日志没有自己新的投票请求。

    Raft 通过比较两份日志中最后一条日志条目的索引值和任期号定义谁的日志比较新。如果两份日志最后的条目的任期号不同，那么任期号大的日志更加新。如果两份日志最后的条目任期号相同，那么日志比较长的那个就更加新。

  2. 提交之前任期内的日志条目

    领导人知道一条当前任期内的日志记录是可以被提交的，只要它被存储到了大多数的服务器上。如果一个领导人在提交日志条目之前崩溃了，未来后续的领导人会继续尝试复制这条日志记录。然而，一个领导人不能断定一个之前任期里的日志条目被保存到大多数服务器上的时候就一定已经提交了。图 8 展示了一种情况，一条已经被存储到大多数节点上的老日志条目，也依然有可能会被未来的领导人覆盖掉。

    图 8

    图 8：如图的时间序列展示了为什么领导人无法通过老的日志的任期号来判断其提交状态。在 (a) 中，S1 是领导者，部分的复制了索引位置 2 的日志条目。在 (b) 中，S1 崩溃了，然后 S5 在任期 3 里通过 S3、S4 和自己的选票赢得选举，然后从客户端接收了一条不一样的日志条目放在了索引 2 处。然后到 (c)，S5 又崩溃了；S1 重新启动，选举成功，开始复制日志。在这时，来自任期 2 的那条日志已经被复制到了集群中的大多数机器上，但是还没有被提交。如果 S1 在 (d) 中又崩溃了，S5 可以重新被选举成功（通过来自 S2，S3 和 S4 的选票），然后覆盖了他们在索引 2 处的日志。但是，在崩溃之前，如果 S1 在自己的任期里复制了日志条目到大多数机器上，如 (e) 中，然后这个条目就会被提交（S5 就不可能选举成功）。 在这个时候，之前的所有日志就会被正常提交处理。

    为了消除图 8 里描述的情况，Raft 永远不会通过计算副本数目的方式去提交一个之前任期内的日志条目。只有领导人当前任期里的日志条目通过计算副本数目可以被提交；一旦当前任期的日志条目以这种方式被提交，那么由于日志匹配特性，之前的日志条目也都会被间接的提交。在某些情况下，领导人可以安全的知道一个老的日志条目是否已经被提交（例如，该条目是否存储到所有服务器上），但是 Raft 为了简化问题使用一种更加保守的方法。

    当领导人复制之前任期里的日志时，Raft 会为所有日志保留原始的任期号, 这在提交规则上产生了额外的复杂性。在其他的一致性算法中，如果一个新的领导人要重新复制之前的任期里的日志时，它必须使用当前新的任期号。Raft 使用的方法更加容易辨别出日志，因为它可以随着时间和日志的变化对日志维护着同一个任期编号。另外，和其他的算法相比，Raft 中的新领导人只需要发送更少日志条目。

6. Raft 算法实现指导

状态：

状态 所有服务器上持久存在的
currentTerm 服务器最后一次知道的任期号（初始化为 0，持续递增）
votedFor 在当前获得选票的候选人的 Id
log[] 日志条目集；每一个条目包含一个用户状态机执行的指令，和收到时的任期号
状态 所有服务器上经常变的
commitIndex 已知的最大的已经被提交的日志条目的索引值
lastApplied 最后被应用到状态机的日志条目索引值（初始化为 0，持续递增）
状态 在领导人里经常改变的 （选举后重新初始化）
nextIndex[] 对于每一个服务器，需要发送给他的下一个日志条目的索引值（初始化为领导人最后索引值加一）
matchIndex[] 对于每一个服务器，已经复制给他的日志的最高索引值

附加日志 RPC：

由领导人负责调用来复制日志指令；也会用作heartbeat

参数 解释
term 领导人的任期号
leaderId 领导人的 Id，以便于跟随者重定向请求
prevLogIndex 新的日志条目紧随之前的索引值
prevLogTerm prevLogIndex 条目的任期号
entries[] 准备存储的日志条目（表示心跳时为空；一次性发送多个是为了提高效率）
leaderCommit 领导人已经提交的日志的索引值
返回值 解释
term 当前的任期号，用于领导人去更新自己
success 跟随者包含了匹配上 prevLogIndex 和 prevLogTerm 的日志时为真

接收者实现：

  1. 如果 term < currentTerm 就返回 false （5.1 节）
  2. 如果日志在 prevLogIndex 位置处的日志条目的任期号和 prevLogTerm 不匹配，则返回 false （5.3 节）
  3. 如果已经存在的日志条目和新的产生冲突（索引值相同但是任期号不同），删除这一条和之后所有的 （5.3 节）
  4. 附加任何在已有的日志中不存在的条目
  5. 如果 leaderCommit > commitIndex，令 commitIndex 等于 leaderCommit 和 新日志条目索引值中较小的一个

请求投票 RPC：

由候选人负责调用用来征集选票（5.2 节）

参数 解释
term 候选人的任期号
candidateId 请求选票的候选人的 Id
lastLogIndex 候选人的最后日志条目的索引值
lastLogTerm 候选人最后日志条目的任期号
返回值 解释
term 当前任期号，以便于候选人去更新自己的任期号
voteGranted 候选人赢得了此张选票时为真

接收者实现：

  1. 如果term < currentTerm返回 false （5.2 节）
  2. 如果 votedFor 为空或者就是 candidateId，并且候选人的日志至少和自己一样新，那么就投票给他（5.2 节，5.4 节）

所有服务器需遵守的规则：

所有服务器：

跟随者（5.2 节）：

候选人（5.2 节）：

领导人：

3. 常识

4. golang 新手入门配置学习

bbs链接：https://newbbs.bingyan.net/topics/1111

Ubuntu下 golang 安装与配置

  1. golang 项目目录结构

    一个Go项目在GOPATH下，会有如下三个目录：

    • src存放源代码 ( .go )
    • pkg编译后生成的文件
    • bin编译后生成的可执行文件 ( .a )

    ​

    <project>
      |--<bin>
      |--<pkg>
      |--<src>
         |--<a>
             |--<a1>
                 |--al.go
             |--<a2>
                 |--a2.go
         |--<b>
             |--b1.go
             |--b2.go

  2. PATH GOPATH 等简介

    • GOROOT

      GO 语言安装的路径，如我的 Ubuntu 下的是/usr/local/go，类似于JAVA中的JAVA_HOME

    • GOPATH

      GOPATH 表示代码包或项目所在的地址，可以设置多个，不同地址之间使用 : 分隔

      假设：GOPATH=~/project1:~/project2，GOROOT=/usr/local/go，在代码中引用了包：github.com/bitly/nsq/util

      GO程序在编译时会按先后次序到以下目录中寻找源码：

      ~/project1/github.com/bitly/nsq/util

      ~/project2/github.com/bitly/nsq/util

      /usr/local/go/github.com/bitly/nsq/util

    • PATH

      可执行程序的路径，在命令行执行命令时，系统默认会在PATH中指定路径里寻找。比如linux下我们用最常用的cd命令，执行时我们并未指定 cd 命令的路径，也没有切换到 cd 所在的目录下去执行该命令。这就是因为 cd 命令的可执行文件所在的目录在PATH中录入了。

      go 安装后，在GOROOT/bin目录，如 Ubuntu 的 /usr/local/go/bin 目录下会有 go 、godoc、gofmt 三个可执行命令。为了方便在编译go项目时方便的使用go build、go install 等命令，需要将GOROOT/bin目录加入到系统的PATH路径下。

    • GOARCH

      CPU 架构，如： amd64, 386

    • GOOS

      操作系统，如：linux

    • GOBIN

      工作目录下的bin文件夹

    • GOEXE

      生成的可执行文件后缀

    • GOHOSTARCH

      想要交叉编译的CPU架构

    • GOHOSTOS

      想要交叉编译的操作系统

  3. go 基本命令介绍

    Go命令一般格式：

    go command [arg]

    其中，command是操作命令，arg是该命令的参数

    常用命令介绍：

    • go get

      用于动态获取远程代码包，如果是从GitHub上获取，则需要现安装git，如果是从Google Code上获取，则需要安装hg。go get 获取的远程代码包将被下载到 GOPATH 目录下的src文件夹中

      eg: go get -u github.com/nsf/gocode

    • go install

      1. 编译导入的包文件，所有导入的包文件编译完才会编译主程序
      2. 将编译后生成的可执行文件放到bin目录下（GOPATH/bin），编译后的包文件放到pkg目录下（GOPATH/pkg）

    • go run

      用于编译并直接运行程序，它会生成一个临时文件（但不是一个标准的可执行文件），直接在命令行打印输出程序执行结果，方便用户调试。

      eg: go run main.go

    • go build

      用于测试编译包，可检查是否存在编译错误，如果被编译的是main包，会生成可执行文件。

      #编译
go build main.go
#运行
./main

    • go fmt

      用于格式化源码，有的IDE保存源码时自动执行该命令，比如subl，也可手动执行它。

      eg: go fmt main.go

    • go test

      用于运行测试文件，该命令会自动读取源码目录下的名为：*_test.go的文件，生成并运行测试用的可执行文件，测试成功会显示“PASS”、“OK”等信息。

    • 其他

      1. go clean：用来移除当前源码包里面编译生成的文件
      2. go env: 查看当前用户的go环境变量
      3. go fix: 用来修复以前老版本的代码到新版本
      4. go list: 列出当前全部安装的packge
      5. go version: 查看当前go版本

    hello world：

    main.go 代码：

    package main

import (
    "fmt"
)

func main() {
    fmt.Println("Hello World!")
}

    进入该文件所在目录，尝试编译运行：

    go run main.go

    终端会输出 Hello World! ，则运行成功

  4. sublime 配置 golang 环境

    • 安装 GoSublime

      运行：Ctrl + B

      个人 GoSublime 配置：

      {
    "env": {
        "PATH": "$PATH",
        // "GOPATH": "$HOME/Projects/Go/test",
        // "GOPATH": "$GOPATH:$GS_GOPATH",
        "GOPATH": "$GS_GOPATH"
    },
    "comp_lint_enabled":true,
    "lint_enabled": true,
    "autocomplete_builtins": true,
    "fmt_cmd" :[ "goimports"],
    "snippets": [
        {
            "match": {"global": true, "pkgname": "."},
            "snippets": [
                {
                    "text":"type",
                    "title":"type struct {}",
                    "value":"type ${1:name} struct {\n\t$0\n}"
                },{
                    "text":"type",
                    "title":"type interface {}",
                    "value":"type ${1:name} interface {\n\t$0\n}"
                },{
                    "text":"var",
                    "title":"var struct {}",
                    "value":"var ${1:name} struct {\n\t$0\n}"
                },{
                    "text":"map",
                    "title":"map[...]...",
                    "value":"map[${1:string}]${2:interface{}}"
                },{
                    "text":"interface",
                    "title":"interface{}",
                    "value":"interface{}"
                },{
                    "text":"if",
                    "title":"if err != nil {...}",
                    "value":"if ${1:err} ${2:!=} ${3:nil} {\n\t$0\n}"
                },{
                    "text":"if",
                    "title":"if ret,ok := func(); ok {...}",
                    "value":"if ${1:ret,} ${2:ok} ${3::=} ${4:func()}; ${5:!ok} {\n\t$0\n}"
                },{
                    "text":"break",
                    "title":"break",
                    "value":"break"
                },{
                    "text":"continue",
                    "title":"continue",
                    "value":"continue"
                },{
                    "text":"defer",
                    "title":"defer func()",
                    "value":"defer ${0:func()}"
                },{
                    "text":"for",
                    "title":"for k,v := range func() {...}",
                    "value":"for ${1:k,}${2:v} := range ${3:func()} {\n\t$0\n}"
                },{
                    "text":"switch",
                    "title":"switch ... {...}",
                    "value":"switch ${1:name} {\ncase ${2:v}:\n\t$3\ndefault:\n\t$0\n}"
                }
            ]
        }
    ],
}

      注：

      GS_GOPATH is a pseudo-environment-variable. It's changed to match a possible GOPATH based on:

      • the current working directory, e.g. ~/go/src/pkg then $GS_GOPATH will be ~/go/
      • or the path the current .go file (or last activated .go file if the current file is not .go) e.g. if your file path is /tmp/go/src/hello/main.go then it will be /tmp/go

      简单说就是 GS_GOPATH 是用来自动根据当前目录设置 GOPATH 的

    • 安装 gocode

      go get -u github.com/nsf/gocode
go install github.com/nsf/gocode

      安装完成后，我们可以在 $GOPATH/bin 目录下，发现多出了个 gocode 文件

  5. 常用 tools

    • gocode 提供代码补全

      go get -u github.com/nsf/gocode

    • godef 代码跳转

      go get -v code.google.com/p/rog-go/exp/cmd/godef
go install -v code.google.com/p/rog-go/exp/cmd/godef

    • gofmt 自动代码整理

    • golint 代码语法检查

      go get github.com/golang/lint
go install github.com/golang/lint

    • goimports 自动整理imports

      go get golang.org/x/tools/cmd/goimports

  6. 安装 echo

    官方教程

    安装：go get -u github.com/labstack/echo/...

    注：如果无法翻墙可能会报错 package golang.org/x/crypto/acme/autocert: unrecognized import path "golang.org/x/crypto/acme/autocert"

    解决方案:

    分析错误，我们缺少crypto组件，需要下载，使用go get golang.org/x/crypto/acme/autocert来下载，但是 crypto 官方地址在外网

    好在 golang.org 在 github.com 上有备份仓库，所以缺少的组件可以在 github 上下载

    eg: 安装 crypto 组件

    github 地址： https://github.com/golang/crypto

    过程：

    mkdir -p /usr/local/go/src/golang.org/x/
git clone git@github.com:golang/crypto.git
mv crypto /usr/local/go/golang.org/x/

    **测试示例: **

    main.go

    package main

import (
 "net/http"
 
 "github.com/labstack/echo"
)

func main() {
 e := echo.New()
 e.GET("/", func(c echo.Context) error {
     return c.String(http.StatusOK, "Hello, World!")
 })
 e.Logger.Fatal(e.Start(":1323"))
}

    启动： go run server.go

    Browse to http://localhost:1323 and you should see Hello, World! on the page.

    更多echo 请参照学习官方教程：https://echo.labstack.com/guide

上一篇下一篇

猜你喜欢

热点阅读