LeeYzero的博客

自强不息,厚德载物

0%

channel是一种数据结构,在Go语言中用于协程间通信,是Go语言区别于其它语言的重要特性。Go语言原生支持channel,配合Go语言原生对并发的支持,让并发编程变得简单。正如Share Memory By Communicating对Go并发编程的建议:

Do not communicate by sharing memory; instead, share memory by communicating.

和传统并发编程使用同步原语共享内存不同,Go并发编程强调通过channel在协程间通信来共享内存,这实际上是对CSP(Communicating Sequential Processes)并发模型的一种实现。

从应用层面来讲,channel和协程(goroutine)是配合使用的,本文主要从实现层面介绍channel的内部原理,但不会涉及太多协程管理调度相关的知识。本文先介绍channel的基本用法,然后介绍channel内部数据结构以及实现原理,最后介绍使用channel时应该注意的一些问题。

Read more »

map又称映射表或关联数组,是一种常用的数据结构。它由一组<key, value>组成,每个key只出现一次。Go语言原生支持了map数据结构,正如 Go maps in action 中所说:

One of the most useful data structures in computer science is the hash table. Many hash table implementations exist with varying properties, but in general they offer fast lookups, adds, and deletes. Go provides a built-in map type that implements a hash table.

简单来说就是因为 hash table 是非常有用,并且提供了快速的查找、添加、删除特性,所以Go语言提供了map类型,它的底层是使用的hash table

刚接触Go语言时,有两点比较困惑:

  • 对map排序时,需要先对取出map中所有的key,对key排好序后,通过排好序的key查找value。
  • 遍历map时,每次得到的结果顺序都不一样。

随着对Go语言的了解,虽然这两个问题早以有了答案,但仍然想要了解一下map的内部实现原理,于是便有了这篇文章。

在这篇文章中,先简要介绍map的基本用法,再深入map的内部实现原理,最后介绍使用map时需要注意的问题。

Read more »

今年最后一天上班,下午没啥事,总结下Go语言的接口。接口是Go语言区别与其它语言的重要语言特性,也是我最喜欢的Go语言特性之一。Go的接口除了提供多态的能力外,它还是Go反射的基础。Go是一门静态语言,Go接口能够在编译期检查语法规则,同时具备像动态语言那样使用 ducking typing 实现接口。

我一直比较好奇Go的接口内部是如何实现。看了几篇文章,也看了runtime包中的部分实现。发现大部分文章都是从汇编的角度去分析,对我来说,我对汇编了解的不多,也不需要深入那么细节,我最终的目的是想通过了解Go接口的内部实现,让自己避免一些语言上的坑,同时能够写出更高效的代码。最终发现还是 Russ Cox 的文章 Go Data Structures: Interfaces 在一个相对高的层次介绍了Go的接口特性,但又没有深入汇编细节,比较容易理解,也达到了我的目的。

本文通过示例介绍接口的基本用法,然后引出接口的内部数据结构,再介绍接口的动态类型转换和接口派发原理以及效率,最后介绍一些需要注意的问题。

接口初识

接口是对实现的抽象。在Go语言中,接口是一组方法签名,使用interface关键字表示,Go中接口具有如下特点:

  • 接口实现是隐式的。
  • interface{}是一种静态类型。
  • 接口类型可以动态检查和转换
Read more »

在Go语言中,string是一种非常重要的数据结构。了解string的内部实现原理,有利于我们写出更高效的代码。本篇文章首先介绍string的实现原理,然后介绍string、bytes、runes和characters之间的关系,同时引出字符篇码Unicode和UTF-8,最后介绍使用string应该注意的一些问题。

先来看下面两个例子。

示例一

1
2
3
4
str := "中文abc"
for i := 0; i < len(str); i++ {
fmt.Printf("%d: %x\n", i, str[i])
}

示例二

1
2
3
4
str := "中文abc"
for index, runeValue := range str {
fmt.Printf("%d: %#U\n", index, runeValue)
}

上面例子中,%x 表示以16进行输出,%#U 表示输出Unicode字符的码点(code point)和其表现。你知道上面例子输出的结果是什么吗?如果理解了上面例子的输出,那基本了解了Go语言内部是如何实现的string,先来看string的内部数据结构。

Read more »

在Go语言中,slice是一种非常重要的数据结构,用于描述数组存储的连续部分,它本质上是对数组的引用。slice是建立在数组基础上,是对数组的一种封装,它屏蔽了数组底层细节,但使用起来更方便、灵活,再配合内建函数append和copy使得slice具有更强的表现力。

如果不了解slice的内部实现原理,可能会写出低效的代码,甚至会写出一些让你意想不到的BUG。本文先介绍slice的实现原理,再介绍slice一些经验和需要避免的问题。

在开始之前,先来看下面示例输出的结果是什么呢?如果你知道答案,说明你已经完全明白slice的实现原理,可以跳过原理部分介绍,后面的经验之谈可能会对你有帮助。

1
2
3
4
a := []int{1, 2, 3, 4, 5}
s1, s2 := a[:3], a[:3:3]
s1, s2 = append(s1, 100), append(s2, 101)
fmt.Println(a, s1, s2)

实现原理

由于slice是建立在数组的基础上,需要先了解Go中数组的一些概念,然后介绍slice的内部结构和分片操作,最后介绍内建append和copy函数在slice中的应用。

Read more »

上一篇 Lab2C: 持久化 中介绍了Raft持久化的实现,本篇介绍Raft日志压缩原理和实现。实验二共包含四个子实验:

本文是第四个子实验,需要实现Raft日志压缩,在开始实验前,先阅读以下材料:

基本原理

Raft的日志会随着接收客户端的请求数而不断增长,对实际生产环境中的系统而言,内存是有限的,较大的日志,在服务崩溃重启时需要较长时间加载恢复,这会造成服务的可用性问题。日志压缩主要解决这些问题。

Raft采用快照(Snapshot)来实现日志压缩。主要原理时,将当前整个系统的状态作为一个快照(可以理解为一个复本,相当于保证了当前的系统状态)持久化到稳定存储中,然后就可以丢弃这个快照点之前的所有日志了。论文中给出了一个快照示例如下:

上图中,在快照上,日志长度为7。在index=5处生成了一个快照(snaphot),快照中除记录了状态机的状态:x <- 0, y <- 9外,还记录了本次快照包含的最后一个日志记录的index和term(下面会解释为什么需要存储这两个信息)。快照成功后,我们就可以丢弃index=5之前(包括index=5)的所有日志了,日志压缩后长度为2,内存得以释放。

Read more »

上一篇 Lab2B: 日志复制 中介绍了Raft日志复制的实现,本篇介绍Raft持久化的原理和实现。实验二共包含四个子实验:

本文是第三个子实验,需要实现Raft持久化。持久化是指将Raft的部分状态存储到非易失的存储介质中,这样即便节点崩溃,也不至于丢失数据,当服务恢复后,可以从之前持久化的状态处开始工作。在开始实验前,先阅读以下材料:

Raft持久化本来是属于日志复制的一部分,但上一篇中我们已经看到,日志复制的原理和实现已经比较复杂了,所以课程将持久化单独拆分成了独立的一个子实验。

Lab2C比想象的简单,不是它本身就简单,而课程设置的比较简单。在实际生产环境中,持久化一般会将日志写入磁盘,涉及到磁盘I/O操作以及对内存状态的序列化与反序列化。在这个实验中不需要进行这样操作,实验中已经实现了一个Persister对象,将Raft状态的持久化封装成接口。它的实现也比较简单,只是模拟了持久化(实际上还是存储在内存)。

可能这个实验面向的人群主要是学生,主要实验目的是想让学生明白Raft持久化原理和意义,认为持久化到磁盘只是一种实现方式,并不是本实验的重点吧。但对一个软件工程师而言,熟练掌握磁盘I/O操作是一项基本功。

基本原理

Raft持久化是指将Raft状态序列化后存储到存储介质,本实验无需关心存储介质的问题,所以我们只需要对Raft状态进行序列化和反序列化。实现中提供了labgob包可能对任意类型的状态进行序列化和反序列化,这里就不展开了,大家看看labgob包的测试用例就会使用。

那我们需要持久化哪些Raft状态呢?

再次回顾论文Figure 8(这个图非常非常重要)中的左上图,需要对以下三个状态进行持久化:

  • currentTerm:当前任期,在Lab2A中已经介绍过了。
  • votedFor:当前任期中,投票给了谁,在Lab2A中已经介绍过了。
  • log[]:日志,每一项是一个LogEntry,在上一篇中已经定义过了。

那我们什么时候持久化Raft状态呢?

按照论文中的说明,节点在追加日志后,需要将日志持久化。追加日志有两种情况:一种是Leader接受客户端命令,将命令作为一条新的日志记录追加到日志中;另一种是Follower复制Leader的日志记录追加日志。所以我们只需要在这两种追加日志的情况下,持久化Raft状态即可。

Read more »

上一篇 Lab2A: 选主 中介绍了Raft选主的实现,本篇介绍Raft日志复制的原理和实现。实验二共包含四个子实验:

本文是第二个子实验,需要实现Raft日志复制。由于Raft的强领导人特性,命令都是通过Leader顺序追回到日志中,然后通过Leader复制到各Follower中,由于Raft的日志安全特性,使得集群节点中的日志最终达到一致。在开始实验前,先阅读以下材料:

Raft日志复制是Raft协议最核心的部分,也是最难的部分。论文中将日志复制和安全性是分开讨论的,实现的时候我们需要将这两部分结合起来。另外论文中对一些实现细节是空白的,如日志冲突的优化,这要求我们要实现的时候要考虑各种边界问题。

基本原理

选主成功后,Leader就开始接收客户端的请求。每个请求是能够被复制状态机执行的命令(command)。Leader首先将命令作为一个日志记录(entry)追回到日志中,然后并行地向集群中的其它节点发起AppendEntries RPC请求。当日志记录被安全复制到其它节点后,Leader将该记录应用到状态机中,并将状态机执行的结果返回给客户端。如果Follower崩溃或网络丢包,Leader会不断重试向Follower发送AppendEntries RPC,走到Follower最终全部保存了Leader的日志记录。

以上就是Raft日志复制的全部流程,它涉及到很多细节,这里我主要说一下日志记录和安全性。

日志可以理解成是一个包含日志记录(entry)的列表,每个日志记录包含了三个信息:

  • Term:Leader生成日志记录时任期号
  • Index:日志记录在日志中的索引号
  • Command:可以被状态机执行的命令

Term和Index主要用于日志一致冲突检测(下面会介绍);Command是上层状态机的一个概念,Raft其实并不理解,只是Raft需要解决Command的一致性问题,所以Raft把Command当成一个上下文参数存储到一个日志记录中,当Raft认为一个日志记录在集群中已经达成一致后,Raft只是将这个Command再较交给状态机去执行。这个地方说的达成一致,就是指日志已经被安全复制。

在讨论什么叫安全复制之前,先直接抛出Raft给出的安全性保证,这些保证在论文中的详细论述和证明,在此不一一展开

Read more »

上一篇 Lab2: 概述 中简要介绍了Raft,本篇介绍Raft选主的原理和实现。实验二共包含四个子实验:

本文是第一个子实验,需要实现Raft选主。Raft具有强领导人特性,也就是说Raft需要先选举出领导人后才能进行后续操作。在开始实验前,先阅读以下材料:

基本原理

Raft有三种角色:领导人(leader)、候选人(candidate)和追随者(follower),每个Raft节点都可能是这三种状态中的一种,但大部情况下,集群中只有leader和follower两种角色的节点。三种角色的转换关系如下图:

节点启动时设置为follower状态,处于follower状态的节点如果在选举超时时间内没有收到leader的心跳消息将转换为candidate状态,candidate状态的结点会发起投票,首先会给自己投票,然后全网广播,让其它节点给自己投票,如果candidate节点收到了半数以上(majority)的投票,节点转换成leader状态。成为leader状态的节点会定时向全网发送心跳,以表示leader健在,让其它节点都安份点,别挑战leader的权威。集群中的candidate节点在收到leader的心跳后,转换为follower状态。

以上的节点的状态转移可以形象理解为,每个follower都有一颗不安分的心,如果在一段时间内(选举超时时间)没有收到leader的心跳消息,就跳出来参加竞选,让群集中的其它节点都选举它当leader,如果超时半数的节点都同意,那它就成为leader了。同样,为了不让其它节点再把自己推翻,它要不断地向群集广播心跳以维护自己的leader地位。

每次选举都有一个任期(Term),标识惟一的一次选举。一个candidate发起选举时,会出现三种情况:

1、赢得选举,成为leader。
2、集群中其它节点已经赢得选举,转换为follower。
3、投票发生分裂,均没有赢得选举,等待选举超时,重新选举。

前两种情况都比较容易理解,第3种情况发生在集群中有多个候选者时,候选者获得的选票均没有过半,相当于这个任期(Term)没有选举出领导人。任期相当于一个递增的时钟向量(Clock Vector),如果放在时间维度,每个任期包含选举周期和任期内的操作,其中任期内的操作是可选的,这种情况相当于这个任期没有选举出领导人,下图可以直观看出时间维度任期的变化过程:

上图中,正常情况下,每个任期(Term)都包含一个选举周期和任期内的普通操作,但任期3(Term=3)发生投票分裂,没有选举出领导人,任期4发生重新选举,选举出新领导人后,进行后续操作。

Read more »

6.824MIT推出的一个分布式系统课程,讲师是大名鼎鼎的Robert Tappan MorrisLab2 是课程中的第二个实验,实验要求需要用Go语言实现Raft。Raft是为可理解而设计的共识算法(consensus algorithm),它在性能和容错性上等价于Paxos,但结构却完全不一样。Raft通过减少状态空间和将问题分解为几个独立的子问题,使得Raft更容易理解,也更利于工程实现。

在开始实验前,需要先阅读以下材料:

以上材料是必读的,在YouTube上有一个配套的教学视频,英文比较吃力的同学可以在B站看翻译后的视频

共识算法是分布式系统最核心的部分,也是非常难的部分,Paxos的主要问题是难以理解,而且作者Leslie Lamport在论文中并没有给出具体的实现细节,正如Chubby的实现者所述:

There are significant gaps between the description of the Paxos algorithm and the needs of a real-world system. . . . the final system will be based on an unproven protocol.

大概意思是说,Paxos算法的描述和现实世界实际需求存在着显著差距,最终的系统都是基于未经证明的协议。

Read more »