Blog

如何使用CAP理论

Content #

只要有网络交互就一定会有延迟和数据丢失,而这种状况我们必须接受,还必须保证系统不能挂掉。节点间的分区故障是必然发生的。也就是说,分区容错性(P)是前提,是必须要保证的。

现在就只剩下一致性(C)和可用性(A)可以选择了:要么选择一致性,保证数据正确;要么选择可用性,保证服务可用。那么 CP 和 AP 的含义是什么呢?

  1. CP的含义一定会读到最新的数据,不会读到旧数据。如果发生了网络分区,那么集群节点接收到来自客户端的读请求时,为了不破坏一致性,可能会因为无法响应最新数据,而返回出错信息。
  2. AP的含义系统将始终处理客户端的查询,返回特定信息。如果发生了网络分区,一些节点将无法返回最新的特定信息,它们将返回自己当前的相对新的信息。

大部分人对 CAP 理论有个误解,认为无论在什么情况下,分布式系统都只能在 C 和 A 中选择 1 个。

在不存在网络分区的情况下,也就是分布式系统正常运行时(这也是系统在绝大部分时候所处的状态),就是说在不需要 P 时,C 和 A 能够同时保证。

只有当发生分区故障的时候,也就是说需要 P 时,才会在 C 和 A 之间做出选择。而且如果读操作会读到旧数据,影响到了系统运行或业务运行(也就是说会有负面的影响),推荐选择 C,否则选 A。

CA 模型,在分布式系统中不存在。因为舍弃 P,意味着舍弃分布式系统,就比如单机版关系型数据库 MySQL,如果 MySQL 要考虑主备或集群部署时,它必须考虑 P。

Viewpoints #

From #

02 | CAP理论:分布式系统的PH试纸,用它来测酸碱度

拜占庭将军问题公式

Content #

这个解决办法,其实是兰伯特在论文《The Byzantine Generals Problem》中提到的口信消息型拜占庭问题之解:如果叛将人数为 m,将军人数不能少于 3m + 1 ,那么拜占庭将军问题就能解决了。

这个算法有个前提,也就是叛将人数 m,或者说能容忍的叛将数 m,是已知的。在这个算法中,叛将数 m 决定递归循环的次数(也就是说,叛将数 m 决定将军们要进行多少轮作战信息协商),即 m+1 轮(所以,你看,只有楚是叛变的,那么就进行了两轮)。

你也可以从另外一个角度理解:n 位将军,最多能容忍 (n - 1) / 3 位叛将。

不过,这个算法虽然能解决拜占庭将军问题,但它有一个限制:如果叛将人数为 m,那么将军总人数必须不小于 3m + 1。

在二忠一叛的问题中,在存在 1 位叛将的情况下,必须增加 1 位将军,将 3 位将军协商共识,转换为 4 位将军协商共识,这样才能实现忠诚将军的一致性作战计划。

Viewpoints #

From #

01 | 拜占庭将军问题:有叛徒的情况下,如何才能达成共识?

BFT与CFT

Content #

拜占庭将军问题描述的是最困难的,也是最复杂的一种分布式故障场景,除了存在故障行为,还存在恶意行为的一个场景。在存在恶意节点行为的场景中(比如在数字货币的区块链技术中),必须使用拜占庭容错算法(Byzantine Fault Tolerance,BFT)。除了口信消息型和签名消息型解决方案以外,常用的拜占庭容错算法还有:PBFT 算法,PoW 算法。

而在计算机分布式系统中,最常用的是非拜占庭容错算法,即故障容错算法(Crash Fault Tolerance,CFT)。CFT 解决的是分布式的系统中存在故障,但不存在恶意节点的场景下的共识问题。 也就是说,这个场景可能会丢失消息,或者有消息重复,但不存在错误消息,或者伪造消息的情况。常见的算法有 Paxos 算法、Raft 算法、ZAB 协议。

那么,如何在实际场景选择合适的算法类型呢?答案是:如果能确定该环境中各节点是可信赖的,不存在篡改消息或者伪造消息等恶意行为(例如 DevOps 环境中的分布式路由寻址系统),推荐使用非拜占庭容错算法;反之,推荐使用拜占庭容错算法,例如在区块链中使用 PoW 算法。

Viewpoints #

From #

01 | 拜占庭将军问题:有叛徒的情况下,如何才能达成共识?

共识(Consensus)和一致性(Consistency)

Content #

很多同学经常误解的一个点,就是将 Consensus(共识)当成了一致性,也就是称为 Paxos、Raft 为一致性算法,其实 Paxos 和 Raft 是共识算法。而之所以出现这个问题,是因为在很多中文文章中,将 Consensus 和 Consistency 都翻译成了一致性,其实这样是不合适的,因为共识(Consensus)和一致性(Consistency)是两个完全不同的概念。

  1. 共识各节点就指定值(Value)达成共识,而且达成共识后的值,就不再改变了。
  2. 一致性是指写操作完成后,能否从各节点上读到最新写入的数据,如果立即能读到,就是强一致性,如果最终能读到,就是最终一致性。

提到共识算法,Paxos 是一个必须要提及的话题,而且 ZAB 协议、Raft 算法都可以看作是 Paxos 变种,所以,你需要了解 Paxos 算法。

但因为 Paxos 算法的可理解性和可编程性痛点突出,所以在实际场景中,最常的共识算法是 Raft,我们可以基于 Raft 实现强一致性系统。

Viewpoints #

From #

学习路径 | 分布式协议与算法你应该这么学

实现读写锁的三种方案

Content #

readers-writers 问题一般有三类,基于对读和写操作的优先级,读写锁的设计和实现也分成三类。

  1. Read-preferring 读优先的设计可以提供很高的并发性,但是,在竞争激烈的情况下可能会导致写饥饿。这是因为,如果有大量的读,这种设计会导致只有所有的读都释放了锁之后,写才可能获取到锁。
  2. Write-preferring 写优先的设计意味着,如果已经有一个 writer 在等待请求锁的话,它会阻止新来的请求锁的 reader 获取到锁,所以优先保障 writer。当然,如果有一些 reader 已经请求了锁的话,新请求的 writer 也会等待已经存在的 reader 都释放锁之后才能获取。所以,写优先级设计中的优先权是针对新来的请求而言的。这种设计主要避免了 writer 的饥饿问题。
  3. 不指定优先级这种设计比较简单,不区分 reader 和 writer 优先级,某些场景下这种不指定优先级的设计反而更有效,因为第一类优先级会导致写饥饿,第二类优先级可能会导致读饥饿,这种不指定优先级的访问不再区分读写,大家都是同一个优先级,解决了饥饿的问题。

Go 标准库中的 RWMutex 设计是 Write-preferring 方案。一个正在阻塞的 Lock 调用会排除新的 reader 请求到锁。

Viewpoints #

From #

05| RWMutex:读写锁的实现原理及避坑指南

sub:认知失调(cognitive dissonance)

Content #

当两种想法或信念(“认知”)在心理上不一致时,我们就会感到紧张(“失调”)。费斯廷格的研究表明,为了减少这种不愉快的感觉体验,我们经常会调整自己的想法。

这类似于减少饥饿或口渴等内驱力因素的过程——只不过在这里,内驱力来自认知上的不适,而不是生理需要。持有两种相互矛盾的观点就是与荒谬搞暧昧,正如存在主义哲学家阿尔贝·加缪(Albert Camus)所言,人类是这样一种生物,他们一生都在试图说服自己他们的存在不是荒谬的。

我们如何让自己相信我们的生活不是荒谬的?也就是说,我们如何减少认知失调呢?我们的常用方式是改变一种或两种认知,使它们彼此之间更加一致,或者增加更多的认知,帮助弥合原有认知之间的差距。

自我辩护的本质 认知失调是两种基本动机冲突的结果 面对不一致的信息时大脑的推理区域会被关闭 不可挽回假设 改变已经作出的决定也会感受到失调 在金字塔的不同方向之间变换 诱设(entrapment) 失调和自我概念的一般原则 通过改变你所拥有的,来得到你希望得到的 制度的正当性 一些技巧: 登门槛技术 怎样让小男孩不打自己的妹妹

使失调感最小化的方法之一是 选择性接触(selective exposure)与自己观点一致的信息。 费斯廷格的认知失调实验揭示了理由不足原则,可以把它用到家庭教育中: 以非强制的方式诱发期望行为 怎样让小男孩不打自己的妹妹 贴纸评分实验

为什么“自愿”去说或做令人不快的事会激活失调呢?

获取 goroutine id

Content #

获取 goroutine id的方式有两种,分别是简单方式和 hacker 方式。

简单方式 #

通过 runtime.Stack 方法获取栈帧信息,栈帧信息里包含goroutine id。你可以看看上面 panic 时候的贴图,goroutine id 明明白白地显示在那里。 runtime.Stack 方法可以获取当前的 goroutine 信息,第二个参数为 true 会输出所有的 goroutine 信息,信息的格式如下:

goroutine 1 [running]:
main.main()
        ....../main.go:19 +0xb1

第一行格式为 goroutine xxx,其中 xxx 就是 goroutine id,你只要解析出这个 id 即可。解析的方法可以采用下面的代码:

func GoID() int {
    var buf [64]byte
    n := runtime.Stack(buf[:], false)
    // 得到id字符串
    idField := strings.Fields(strings.TrimPrefix(string(buf[:n]), "goroutine "))[0]
    id, err := strconv.Atoi(idField)
    if err != nil {
        panic(fmt.Sprintf("cannot get goroutine id: %v", err))
    }
    return id
}

Hacker方式 #

了解了简单方式,接下来我们来看 hacker 的方式,这也是我们方案一采取的方式。

...

实现一个可重入的锁

Content #

虽然标准库 Mutex 不是可重入锁,但是如果我就是想要实现一个可重入锁,可以吗?

可以,那我们就自己实现一个。这里的关键就是,实现的锁要能记住当前是哪个 goroutine 持有这个锁。我来提供两个方案。

  1. 方案一:通过 hacker 的方式获取到 goroutine id,记录下获取锁的 goroutine id,它可以实现 Locker 接口。
  2. 方案二:调用 Lock/Unlock 方法时,由 goroutine 提供一个 token,用来标识它自己,而不是我们通过 hacker 的方式获取到 goroutine id,但是,这样一来,就不满足 Locker 接口了。

可重入锁(递归锁)解决了代码重入或者递归调用带来的死锁问题,同时它也带来了另一个好处,就是我们可以要求,只有持有锁的 goroutine 才能 unlock 这个锁。这也很容易实现,因为在上面这两个方案中,都已经记录了是哪一个 goroutine 持有这个锁。

下面我们具体来看这两个方案怎么实现。

方案一:goroutine id 获取 goroutine id 知道了如何获取 goroutine id,接下来就是最后的关键一步了,我们实现一个可以使用的可重入锁:

// RecursiveMutex 包装一个Mutex,实现可重入
type RecursiveMutex struct {
    sync.Mutex
    owner     int64 // 当前持有锁的goroutine id
    recursion int32 // 这个goroutine 重入的次数
}

func (m *RecursiveMutex) Lock() {
    gid := goid.Get()
    // 如果当前持有锁的goroutine就是这次调用的goroutine,说明是重入
    if atomic.LoadInt64(&m.owner) == gid {
        m.recursion++
        return
    }
    m.Mutex.Lock()
    // 获得锁的goroutine第一次调用,记录下它的goroutine id,调用次数加1
    atomic.StoreInt64(&m.owner, gid)
    m.recursion = 1
}

func (m *RecursiveMutex) Unlock() {
    gid := goid.Get()
    // 非持有锁的goroutine尝试释放锁,错误的使用
    if atomic.LoadInt64(&m.owner) != gid {
        panic(fmt.Sprintf("wrong the owner(%d): %d!", m.owner, gid))
    }
    // 调用次数减1
    m.recursion--
    if m.recursion != 0 { // 如果这个goroutine还没有完全释放,则直接返回
        return
    }
    // 此goroutine最后一次调用,需要释放锁
    atomic.StoreInt64(&m.owner, -1)
    m.Mutex.Unlock()
}

它相当于给 Mutex 打一个补丁,解决了记录锁的持有者的问题。可以看到,我们用 owner 字段,记录当前锁的拥有者 goroutine 的 id;recursion 是辅助字段,用于记录重入的次数。

...

Mutex不是可重入的锁

Content #

因为 Mutex 的实现中没有记录哪个 goroutine 拥有这把锁。理论上,任何 goroutine 都可以随意地 Unlock 这把锁,所以没办法计算重入条件,毕竟,“臣妾做不到啊”!

所以,一旦误用 Mutex 的重入,就会导致报错。下面是一个误用 Mutex 的重入例子:

func foo(l sync.Locker) {
    fmt.Println("in foo")
    l.Lock()
    bar(l)
    l.Unlock()
}


func bar(l sync.Locker) {
    l.Lock()
    fmt.Println("in bar")
    l.Unlock()
}


func main() {
    l := &sync.Mutex{}
    foo(l)
}

写完这个 Mutex 重入的例子后,运行一下,你会发现类似下面的错误。程序一直在请求锁,但是一直没有办法获取到锁,结果就是 Go 运行时发现死锁了,没有其它地方能够释放锁让程序运行下去。

Viewpoints #

From #

03|Mutex:4种易错场景大盘点

可重入锁

可重入锁

Content #

当一个线程获取锁时,如果没有其它线程拥有这个锁,那么,这个线程就成功获取到这个锁。之后,如果其它线程再请求这个锁,就会处于阻塞等待的状态。

但是,如果拥有这把锁的线程再请求这把锁的话,不会阻塞,而是成功返回,所以叫可重入锁(有时候也叫做递归锁)。

只要你拥有这把锁,你可以可着劲儿地调用,比如通过递归实现一些算法,调用者不会阻塞或者死锁。

Viewpoints #

From #

03|Mutex:4种易错场景大盘点