0、摘要

  • 下载论文PDF
  • 参考解析文章

  • docker

    0.1 Go并发现状

  • Go作为一个静态类型编程语言,宗旨在提供一个简单、高效和安全的方式构建多线程软件

  • Go可以通过消息传递的方式来实现进程间通信,提供多种并发机制和库来简化并发编程

  • 消息传递和共享内存同步在程序错误、Bug方面的比较很重要

  • 然而到目前为止,对于Go并发的Bug没有深入的学习

0.2 这篇paper的目的

  • 通过6个流行Go软件,系统地学习Go在并发中的Bug,软件包括:
    • 数据中心容器系统:Docker、Kubernetes
    • RPC库:gRPC
    • 分布式Key/Value存储系统:etcd
    • 数据库系统:CockroachDB
    • 数据库系统:BoltDB
  • 总共分析了171个并发bug,它们中有超过一半是非传统Go的特性问题。

  • 在追踪造成这些Bug的根本原因、修复情况,使用公开的两款Bug检测工具,并试验复现这些Bug,并查看修复的补丁

  • 研究提供了对Go的并发模型更好地理解,从业人员可以编写更好、更可靠的Go软件,以及Go的开发调试和诊断工具

1、Go并发的一些介绍

  Go语言设计的主要目的是比传统更容易、更少的错误的多线程。为了实现这个目的,Go核心多线程设计的原则是:

  • 通过轻量级线程goroutines,使更小、更容易创建
  • 通过channel,使goroutines之间的消息传递更加直接
  • 为此,Go提供了新的原语和新的库,还提出了现有语义的新实现

  由于以前没有研究Go并发错误的工作,导致到目前为止,仍然不清楚这些并发机制是否实际上使Go更容易编程,并且比传统语言更不容易出现混淆错误。总之,我们从这些应用中学习171个并发bug。我们分析产生它们的根本原因,执行检查来复现它们,并检查修复它们的patch。最后,我们通过公开的两个Go并发Bug检测器进行测试。

  我们侧重研究:在消息传递和共享内存中,哪些线程间通信机制不易出错。Go语言对于这个问题非常完美地实现了内存共享和消息传递,并鼓励在共享内存上使用channel,并认为显式消息传递不易出错。通过两个正交维度对并发错误分类:

  • 在原因维度上,将错误分类为由滥用共享内存和滥用消息传递引起的错误。
  • 第二个维度,将错误分成那些涉及(任意数量)无法继续的goroutine(我们称之为阻塞错误)和那些不涉及任何阻塞(非阻塞错误)的错误。
  • 与共享内存一样,通过消息传递可以很容易地产生交换错误,有时甚至更多
  • 除去违反Go channel使用规则的错误,许多错误是由于混淆使用消息传递新语法新依赖库,这些错误很容易被忽略并难以检测

消息传递示范实例1:From Kubernetes

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
func finishReq(timeout time.Duration) r ob { 
	// ch := make(chan ob)
	ch := make(chan ob, 1)
	go func() {
		result := fn()
		ch <- result // block
	}
	select {
		case result = <- ch:
			return result
		case <- time.After(timeout):
			return nil
	} 
}

  finishReq方法创建子goroutine,父goroutine阻塞在9行直到收到ch传递的消息或者时间Timeout(11行),子goroutine调用匿名函数,调用fn()返回result并通过ch传递给父goroutine,并阻塞在6行,直到父goroutine接收ch消息。当超时更早发生或者都有效时(非确定性地)选择了11行执行并退出,导致子goroutine永远阻塞

  解决方案是:将ch由非缓冲channel修改为缓冲channel,所以子goroutine总能够发送结果即使是父goroutine已经退出。

  这是Go语言的语言特性,很难写出正确的Go程序,程序员需要:

  • 清晰的理解使用匿名函数来创建goroutine;
  • buffered vs unbuffered channel的使用
  • select 等待多个通道操作的非确定性
  • 对time包的理解

  总的来说,我们的研究揭示了Go并发编程的新实践和新问题,它揭示了消息传递与共享内存访问争论的答案。我们的研究结果提高了对Go并发性的理解,并为未来的工具设计提供了有价值的指导。 本文作出以下重要贡献

  • 我们用现实中的6个生产级Go应用程序对Go混淆错误进行了第一次实证研究
  • 我们对Go并发错误原因,修复和检测做了九个高级关键观察。 它们对Go程序员的引用很有用。 我们进一步深入了解我们的研究结果的含义,以指导Go的开发,测试和错误检测的未来研究。
  • 我们提出了新的方法来根据错误原因和行为的两个维度对并发错误进行分类。 这种分类方法帮助我们更好地比较不同的并发机制以及错误原因和修复的相关性。 我们相信其他错误研究也可以使用类似的分类方法。

2、应用程序及背景

  本节简要介绍Go的并发机制,包括其线程模型,线程间通信方法和线程同步机制。以及选择的6种Go应用程序。

2.1 Goroutine

  Go的一种概念叫goroutine作为并发的单元。Goroutine是一种用户线程,它以M-N的方式映射到系统核心线程。Goroutine可以通过关键字Go放到Function前简单地创建。

  为了让goroutine简单地创建,Go也支持以匿名函数方式创建。在匿名函数之前声明的所有局部变量都可以被匿名函数访问,并且可能在父goroutine和使用匿名函数创建的子goroutine之间共享,导致数据竞争

2.2 共享内存同步

  Go支持跨goroutine传统的共享内存访问。

  • 互斥锁Mutex(lock/unlock)
  • 读写锁RWMutex(read/write lock):与C的pthread_rwlock_t不同,Go的读写锁,写操作的优先级高于读的操作
  • 条件变量Cond
  • 原子读写操作atomic(atomic read/write)
  • 一次操作Once(新特性):它被广泛地应用在多个goroutine的共享变量只被初始化一次
  • Go使用WaitGroup允许多个goroutine在等待goroutine之前完成共享变量访问。Goroutine通过Add方法添加到WaitGroup,通过Done方法提醒完成,Wait方法等待所有的goroutine通知完成。错误地使用WaitGroup会导致阻塞和非阻塞的bugs

2.3 消息传递同步

  通道是Go语言的新特性,用于在goroutines中发送数据和状态,并构建更复杂的功能。Go支持两种类型的channel,带有buffered和unbuffered。

  • 从unbuffered发送数据(或接收数据)会阻塞一个goroutine,直到另外的goroutine接收数据(或发送数据)
  • 对于buffered通道,当缓冲区满了时,发送数据才会被阻塞

  使用通道的几个基本规则,违反它们可能会产生并发错误。

  • channel只有初始化后使用
  • 发送数据到一个nil channel(从一个nil channel接收数据)会被永远阻塞
  • 发送数据到一个关闭的channel会触发运行时panic
  • close一个已经关闭的channel会触发运行时panic
  • select语句允许goroutine等待多个通道操作。select将阻塞,直到其中一个案例可以取得进展或者它可以执行默认分支。当select中的多个case有效时,Go将随机选择一个执行。这种随机性可能导致并发错误,这将在第6节中讨论
  • Go引入了几种新的语义,以简化多个goroutine之间的交互。context和Pipe都是传递消息的新形式,错误使用它们可以创建新类型的并发错误。
    • 为了通过产生一组协同工作的goroutine来协助服务用户请求的编程模型,Go引入了Context来跨goroutines传送特定于请求的数据或元数据。
    • Pipe旨在在Reader和Writer之间传输数据。

2.4 Go应用程序

  选择6款Go开源排名前100的项目,基本是中-大型项目,代码行数从9000到200万。Kubernetes和gRPC项目原始由Google的团队开发。

3、Go并发使用模型

  在研究Go并发Bug之前,理解Go并发像什么非常重要。

项目 常规函数 匿名函数 共计 每千行数
Docker 33 112 145 0.18
Kubernetes 301 233 534 0.23
etcd 86 211 297 0.67
CockroachDB 27 125 152 0.29
gRPC-Go 14 30 44 0.83
BoltDB 2 0 2 0.22
gRPC-C 5 - 5 0.03

表:创建goroutine/thread数量

  这章动态、静态地介绍goroutine的使用和Go并发语句在6个应用中的使用。

3.1 Goroutine的使用

  Goroutine设计哲学之一:轻量且易于使用。那么

  • 真正的Go程序员倾向于使用许多goroutine编写代码(静态)吗?
  • 真正的Go应用程序在运行时创建了很多goroutine(动态)吗?

  从上表可以看出,这些项目使用了大量的Goroutine。使用方式,除了Kubernetes和BoltDB常规函数比匿名函数使用的多外,其他的应用都是匿名函数比常规函数使用goroutine更多。

  对比gRPC-C项目,gRPC-C项目有140K行代码,同样是Google gRPC项目完成。gRPC-C项目使用很少的线程实现(共5个线程,每千行代码有0.03)。我们运行了gRPC-Go和gRPC-C来处理三个性能基准测试,旨在比较用不同编程语言编写的多个gRPC版本的性能。这些基准测试为gRPC配置了不同的消息格式,不同的连接数以及同步与异步RPC请求。由于gRPC-C比gRPC-Go更快[22],我们运行gRPC-C和gRPC-Go来处理相同数量的RPC请求,而不是相同的总时间。

  对于所有工作负载,goroutine的正常执行时间比线程短。

3.2 并发语句使用

项目 Mutex atomic Once WaitGroup Cond chan Misc Total
Docker 62.62% 1.06% 4.75% 1.70% 0.99% 27.87% 0.99% 1410
Kubernetes 70.34% 1.21% 6.13% 2.68 0.96% 18.48% 0.20% 3951
etcd 45.01% 0.63% 7.18% 3.95% 0.24% 42.99% 0 2075
CockroachDB 55.90% 0.49% 3.76% 8.57% 1.48% 28.23% 1.57% 3245
gRPC-Go 61.20% 1.15% 4.20% 7.00% 1.65% 23.03% 1.78% 786
BoltDB 70.21% 2.13% 0 0 0 23.40% 4.26% 47

表:并发语句的使用。Mutex包括Mutex和RWMutex

  上表中,共享内存同步的使用远远大于消息传递,而互斥锁是使用最广泛的语句。对于消息传送,channel是最频繁使用的原语句。使用频率范围18.48% 到 42.99%

  在gRPC-C中,有746处使用了lock。gRPC-Go中,8中类型共786处,显然,Go使用了更多种类和数量的并发原语句。

图片   总结:

  • 虽然,传统的共享内存同步比重最高,但是新语言特性的消息传递使用量也非常大。
  • 随着goroutine和新类型的并发原语的更多使用,Go程序可能会引入更多的并发错误

4、 Bug研究方法

  • 收集
  • 分类
  • 复现

4.1 收集并发Bug

  从Github历史提交日志中查询并发关键词(”race”,“deadlock”,“synchronization”,“concurrency”,“lock”,“mutex”,“atomic”,“compete”,“context”,“once”,“goroutine leak”)

4.2 Bug分类(Bug taxonomy)

项目 blocking non-blocking shared memory message passing
Docker 21 23 28 16
Kubernetes 17 17 20 14
etcd 21 16 18 19
CockroachDB 12 16 23 5
gRPC-Go 11 12 12 11
BoltDB 3 2 4 1
Total 85 86 105 66

分类表:此表显示了我们研究的错误如何分布在不同的类别和应用程序中

  维度一:阻塞Bug和非阻塞。我们对阻塞的定义比死锁更广泛,并且包括没有循环等待的情况,但是一个(或多个)goroutines等待没有其他goroutines提供的资源。很多Go并发错误就是这种。我们相信,随着Go等新语言的新编程习惯和语义,我们应该更加关注这些非死锁阻塞错误,并扩展传统的并发错误分类机制。

  • 阻塞Bug:如果一个或多个goroutine无意中卡在执行中并且无法继续前进
  • 非阻塞Bug:相反,如果所有goroutine都可以完成他们的任务,但他们的行为是不可取的。

  维度二:共享内存和消息传递。这种分类可以帮助程序员和研究人员选择更好的方法来执行线程间通信,并在执行此类通信时检测并避免潜在的错误。

  当一个Bug添加到代码到修复关闭的过程中,时间是比较长的一个过程,大部分的bug是很难被触发或者检测,但一旦发现,它们被修复非常迅速。因此,我们认为这些错误非常重要,值得仔细研究。

4.3 重现并发Bug(Reproducing concurrency bugs)

  为了评估内部死锁和数据竞态检测,重现了21个阻塞bug和20个非阻塞bug。重现bug的步骤,首先把应用程序回滚到出现bug的版本,然后输入触发数据。由于它们的非确定性,并发错误很难再现。对于未被复制的错误,可能是因为我们没有找到某些依赖库,或者因为我们未能观察到所描述的症状。

4.4 威胁的有效性(Threats to validity)

  我们只研究了已修复的并发错误。 可能有其他并发错误很少被复制,并且永远不会被开发人员修复。 对于一些固定的并发错误,提供的信息太少,使得它们难以理解。 我们的研究中没有包含这些错误。 尽管有这些限制,我们已尽最大努力收集真实世界的Go并发错误并进行全面而公正的研究。 我们相信我们的研究结果足够通用,可以激励和指导未来针对Go并发错误的研究

5、阻塞Bugs

  本节介绍了我们关于阻止错误的研究结果,包括它们的根本原因,修复以及内置运行时Go死锁检测器在检测阻塞情况时的有效性。

5.1 阻塞的根本原因

  我们通过检查哪些操作阻止了goroutine以及为什么操作没有被其他goroutine阻止来研究阻塞bug的根本原因。使用我们的第二维错误分类,我们将阻塞错误分离为那些旨在保护共享内存访问和由消息传递操作引起的卡住操作引起的错误。

项目 Mutex RWMutex Wait Chan Chan w/ Lib
Docker 9 0 3 5 2 2
Kubernetes 6 2 0 3 6 0
etcd 5 0 0 10 5 1
CockroachDB 4 3 0 5 0 0
gRPC-Go 2 0 0 6 2 1
BoltDB 2 0 0 0 1 0
Total 28 5 3 29 16 4

  综上,42%的阻塞bug是在保护分享内存时出错(Mutex、RWMutex,Wait),58%的阻塞bug是在消息传递时出错。考虑共享内存比消息传递使用得更频繁可得知,使用消息传递操作更容易引起阻塞bug。

  观察得知:与普遍认为消息传递不太容易出错相比,我们研究的Go应用程序中的更多阻塞错误是由错误的消息传递引起的,而不是错误的共享内存保护引起的。

5.1.1 (不)保护共享内存

  众所周知,共享内存访问很难正确编程,并且一直是死锁研究的主要焦点之一[35,51,54]。 他们继续在Go中造成阻塞错误,包括传统模式和Go特定的新原因。

  • Mutex:双重锁定、获得锁的错误顺序、忘记解锁。此类别中的所有错误都是传统错误,我们相信传统的死锁检测算法应该能够通过静态程序分析来检测这些错误
  • RWMutex:第二章节所说,写锁的优先级高于读锁。当goroutine(th-A)通过读锁定两次获取一个RWMutex时,这种独特的锁实现可能导致阻塞错误,并且这两个读锁操作通过来自另一个goroutine的写锁操作交错(th-B)。当th-A的第一次读锁定操作成功时,它将阻止th-B的写锁定操作,因为写锁定是独占的。 然而,由于写锁定请求在Go的实现中具有更高的特权,因此th-B的写锁定操作也将阻止th-A的第二次读锁定操作。 th-A和th-B都无法继续进行。RWMutex阻塞错误类型意味着即使Go使用与传统语言相同的并发语义,由于Go的新语义实现,仍然可能存在新类型的错误。
  • Wait:三个阻塞错误是由于等待操作无法继续进行的。 与Mutex和RWMutex相关的错误不同,它们不涉及循环等待。 当Cond用于保护共享内存访问和一个goroutine调用Cond.Wait()时,会发生其中两个错误,但之后没有其他goroutine调用Cond.Signal()(或Cond.Broadcast())
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
// Figure 5. A blocking bug caused by WaitGroup

var group sync.WaitGroup
group.Add(len(pm.plugins))
for _, p := range pm.plugins {
	go func(p *plugin) {
		defer group.Done()
	}
//	group.Wait()
}
group.Wait()

  观察得知:由共享内存同步引起的大多数阻塞错误与传统语言具有相同的原因和相同的修复。 然而,由于Go对现有原语的新实现或其新的编程语义,它们中的一些与传统语言不同。

5.1.2 Misuse of Message Passing

  我们现在讨论阻止消息传递错误导致的错误,这与我们研究的应用程序中阻塞错误的主要类型相反。

  • Channel:错误使用Channel导致29个阻塞Bug。大部分错误发生是由于发送(或接收)一个channel或者关闭一个channel,
1
2
3
4
5
6
7
8
// hctx, hcancel := context.WithCancel(ctx)
var hctx context.Context
var hcancel context.CancelFunc
if timeout > 0{
	hctx, hcancel = context.WithTimeout(ctx, timeout)
} else {
	hctx, hcancel = context.WithCancel(ctx)
}

  在第一行中,一个新的context和hcancel被创建的同时,goroutine也被创建了。如果timeout大于0时,此时又另外创建一个context和hcancel,并被赋值给旧的对象。旧的对象就没有方式发送消息或者关闭goroutine。patch方式就是定义变量,并增加else语句。

  • Channel and other blocking primitives:其他语句造成16个阻塞Bug。
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
func goroutine1() {
	m.Lock()
	// ch <- request //blocks
	select {
		case ch <- request
		default:
	}
	m.Unlock()
}

func goroutine2() {
	for {
		m.Lock() //blocks
		m.Unlock()
		request <- ch
	}
}

  在goroutine1中阻塞在发送request中,goroutine2阻塞在m.Lock()请求锁的过程中。这时两个都在锁定状态。解决方案是在goroutine1中增加select,并使用default分支,让goroutine1不再阻塞。

  • Messaging libraries:传递数据和消息的库,有4个bug是由消息传递库造成。比如Pipe没有关闭,goroutine发送/拉取消息会被阻塞。

  观察得知:由消息传递引起的所有阻塞错误都与Go的新消息传递语义相关,如channel。 特别是当消息传递操作与其他同步机制一起使用时,它们很难被检测到。

5.2 修复阻塞Bug

阻塞类型 $Add_s$ $Move_s$ $Change_s$ $Remove_s$ $Misc.$
Mutex 9 7 2 8 2
Wait 0 1 0 1 1
RWMutex 0 2 0 3 0
Chan 15 1 5 4 4
Chanw/ 6 3 2 4 1
Messaging Lib 1 0 0 1 2
Total 31 14 9 21 10

Table 7 : 修复阻塞策略

  Go开发人员经常调整同步操作,包括添加(Add)缺失的操作,移动(Move)或更改(Change)错放/误用的操作,以及删除(Remove)多余的操作。lift值是A是错误分类,B是解决方式,当lift(AB)越大,说明两者当关联性越高,B越能解决A问题。Mutex和$Move_s$的lift值为1.52,Chan和$Add_s$的lift值为1.42,其他当阻塞bug值都小于1.16

5.3 检测阻塞Bug

  Go提供了内置的死锁检测在Goroutine的调度过程中,在Go的运行时的进程中没有goroutine可以取得进展。但是检测出来的bug远远小于真实的bug数。

  • 首先,当仍有一些正在运行的goroutine时,它不会将受监视的系统视为阻塞。
  • 其次,它只检查goroutine是否在Go并发原语中被阻止,但不考虑等待其他系统资源的goroutine。

  这两个限制主要是由于内置检测器最小运行时开销的设计目标。以后要考虑结合静态和动态阻塞模式检测。

6、非阻塞bug

6.1 非阻塞bug的根本原因

项目 traditional anon. waitgroup lib chan(p) lib(p)
Docker 9 6 0 1 6 1
Kubernetes 8 3 1 0 5 0
etcd 9 0 2 2 3 0
CockroachDB 10 1 3 2 0 0
gRPC-Go 8 1 0 1 2 0
BoltDB 2 0 0 0 0 0
Total 46 11 6 6 16 1

Table 9:非阻塞bug的根本原因(传统非阻塞bug、匿名函数非阻塞bug、错误使用waitgroup非阻塞bug、Go依赖库,错误使用channel)

6.1.1 保护共享内存失败

  我们80%的错误都是由于没有保护或者错误保护共享内存导致的数据竞态或者其他非死锁bug,但是并非所有这些与传统语言中的非阻塞错误具有相同性。

  • Traditional bugs:超过50%的错误是传统错误,和C、Java一样发生的原子操作违规,顺序违规和数据竞态。很有趣的是,非阻塞bug中有7例是由于对Go语言特性缺乏清晰的理解。比如,Docker#22985 和 CockroachDB#6111是由共享变量上的数据争用引起的,该共享变量的引用通过通道传递到goroutine。
  • Anonymous function:我们发现了11个这种类型的bug,其中9个是由父goroutine和使用匿名函数创建的子goroutine之间的数据竞态引起的。另外两个是由两个儿童goroutines之间的数据竞争引起的。
1
2
3
4
5
6
7
8
for i := 17; i <= 21; i++ { // write
	// go func() { /* Create a new goroutine */
	go func(i int) {
		apiVersion := fmt.Sprintf("v1.%d", i) // read
		...
	// }()
	}(i)
}

Figure 8. 匿名函数导致的数据竞态。

  Docker开发人员通过在每次迭代时复制共享变量i来修复此错误,并将复制的值传递给新的goroutines。

  • Misusing WaitGroup:WaitGroup有一个规则,就是在wait之前,Add一定要被添加,如果在Wait之前没有被添加则产生bug。
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
func (p *peer) send() {
	p.mu.Lock()
	defer p.mu.Unlock()
	switch p.status {
		case idle:
			p.wg.Add(1) //+
			go func() {
				p.wg.Add(1) //-
				...
				p.wg.Done()
			}()
		case stop:
	}
}

Figure 9 在Wait之前,Add不一定被添加,修复方式移动到Goroutine之外

1
2
3
4
5
6
func (p * peer) stop() {
	p.mu.Lock()
	p.status = stopped
	p.mu.Unlock()
	p.wg.Wait()
}

Figure 9

  在etcd中显示了一个这样的bug,其中不能保证func1的第8行的Add在func2的第5行等待之前发生。 修复是将Add移动到一个关键部分,这确保Add将在Wait之前执行或者不会执行。

  • Special libraries:context被设计用于多个goroutine被绑定到context。

  观察得知:大约三分之二的共享内存非阻塞错误是由传统原因引起的。 Go的新多线程语义和新库有三分之一的贡献。

6.1.2 消息传递时的错误

  • Misusing channel:由于误用channel导致16个非阻塞错误。如下违反了channel不能被关闭两次的原则。
1
2
3
4
5
6
7
select {  //-
	case <- c.closed:  //-
	default:  //-
	Once.Do(func() { //+
		close(c.closed)
	}) //+
} //-

Figure 10. A bug caused by closing a channel twice.

  对于channel和select配合使用,在Go中,当select收到多条消息时,无法保证哪一条消息会被优先执行。这导致了3个bug。select语句的判断条件必须是阻塞的,它会判断每个case是否可以执行,如果几条可以执行,就随机执行其中一条;如果没有可以执行,但有default语句,则执行default流程;如果没有任何语句可执行,则会发生阻塞

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
ticker := time.NewTicker()
for{
	select{ //+
		case <- stopCh: //+
			return //+
		default: //+
	} //+
	f()
	select {
		case <- stopCh:
			return
		case <- ticker:
	}
}

Figure 11. A non-blocking bug caused by select and channel.

  当stopCh和ticker同时到达时,如果选择的ticker,那么就会再执行一次f()函数,一个办法时在前面增加一个select再判断一次是否有stopCh信息。

  • Special libraries:
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
timer := time.NewTimer(0) //-
var timeout <- chan time.Time //+
if dur > 0 {
	timer = time.NewTimer(dur) //-
	timeout = time.NewTimer(dur).C //+
}
select {
	case <- timer.C: //-
	case <- timeout: //+
	case <- ctx.Done():
		return nil
}

Figure 12. A non-blocking bug caused by Timer.

  当timer创建的时候,无论dur是否大于0都会发送signal time.C,导致会直接执行select的的语句。所以不能直接用,重新定义timeout通道变量,作为接收信息。

  观察得知:消息传递导致的非阻塞错误比共享内存访问少得多。 使用通道与其他特定于Go的语义和库的通道规则和复杂性是这些非阻塞错误发生的原因。如果使用正确,消息传递可能比共享内存访问更不容易出现非阻塞错误。 但是,在与其他语言特定功能组合时,使用某种语言传递消息的复杂设计可能会导致这些错误特别难以找到。

6.2 修复非阻塞bug

阻塞类型 Timing
Add_s
Timing
Move_s
Instruction
Bypass
Data
Private
Misc.
traditional 27 4 5 10 0
waitgroup 3 2 1 0 0
anonymous 5 2 0 4 0
lib 1 2 1 0 2
chan(pass) 6 7 3 0 0
lib(pass) 0 0 0 0 1
Total 42 17 10 14 3

Table 10. Fix strategies for non-blocking bugs

  大约69%的非阻塞错误是通过限制时序来修复的, - 可以通过添加同步原语(如Mutex),也可以通过移动现有原语(如图9中的移动添加)来实现。 - 通过消除访问共享变量的指令或绕过指令来修复10个非阻塞错误(例如,图10)。 - 通过值传递共享变量的私有副本(例如,图8)来修复14个错误,并且这些错误都是共享内存的。

项目 Mutex Channel Atomic WaitGroup Cond Misc. None
traditional 24 3 6 0 0 0 13
waitgroup 2 0 0 4 3 0 0
anonymous 3 2 3 0 0 0 3
lib 0 2 1 1 0 1 2
chan(mpass) 3 11 0 2 1 2 1
lib(mpass) 0 1 0 0 0 0 0
Total 32 19 10 7 4 3 19

Table 11. Synchronization primitives in patches of non-blocking bugs.

  mutex是使用最广泛的语句,channel是第二广泛使用的,它被用来替换共享变量来修复数据竞态,也被用来控制两个goroutine之间的执行顺序,如果不适当地使用,也会造成新的bug。channel不止用在修复消息传递,也使用在传统的共享内存上。我们怀疑这是因为一些Go程序员将消息传递视为比共享内存同步更可靠的方式或更容易编程的线程间通信方式。

  最后,24个bugs使用其他并发语句修复,19个bugs使用非并发语句修复。我们通过lift来分析,

  • misusing channelchannel的lift值高达2.7
  • anonymous functiondata private的lift值为2.23;
  • Misusing channelMoves的lift值为2.21;

  观察得出:传统的共享内存同步技术仍然是Go中非阻塞错误的主要修复,而通道被广泛用于修复与通道相关的错误以及共享内存错误。虽然Go程序员继续使用传统的共享内存保护机制来修复非阻塞错误,但他们更喜欢在某些情况下使用消息传递作为修复,可能是因为他们将消息传递视为跨线程通信的更安全的方式。

6.3 检测非阻塞Bug

  Go提供了一个数据竞争检测器,它使用与ThreadSanitizer算法相同的算法。在程序执行期间,竞争检测器为每个存储器对象创建最多四个阴影字,以存储对象的历史访问。它将每个新访问与存储的影子字值进行比较,以检测可能的种族。

| Root Cause | # of Used Bugs | # of Detected Bugs | | —————— | ————– | —————— | | Traditional Bugs | 13 | 7 | | Anonymous Function | 4 | 3 | | Lib | 2 | 0 | | Misusing Channel | 1 | 0 | | Total | 20 | 10 | Table 12. Benchmarks and evaluation results of the data race detector.

  数据竞争检测器成功检测到7/13传统错误和由匿名函数引起的3/4错误。对于其中六次成功,数据竞争检测器报告每次运行中的错误,而其余四次,在检测器报告错误之前需要大约100次运行。

  观察得知:简单的传统数据竞争检测器无法有效检测所有类型的Go非阻塞错误。 未来的研究可以利用我们的错误分析来开发更具信息性,特定于Go的非阻塞错误检测器。

7、讨论以及未来的工作

  Go拥护者可以轻松创建线程,并使用通过共享内存传递消息进行线程间通信。 实际上,我们看到Go程序中创建的goroutine比传统线程更多,并且Go通道和其他消息传递机制有很多用法。 但是,我们的研究表明,如果使用不当,这两种编程实践可能会导致并发错误。

  • Shared memory vs. message passing:消息传递比共享内存产生的错误更多。实际上,消息传递是阻塞bug主要产生者,并且这种新语句产生的阻塞bug很难检测。不过消息传递确实比共享内存产生的非阻塞bug更少,我们相信消息传递提供了一种干净的线程间通信形式,可用于传递数据和信号。但它们只有在正确使用时才有用,这要求程序员不仅要很好地理解消息传递机制,还要了解Go的其他同步机制。
  • Implication on bug detection:我们的研究揭示了许多可用于执行并发错误检测的错误代码模式。 作为初步努力,我们构建了一个针对匿名函数引起的非阻塞错误的检测器(例如图8)。 我们的探测器已经发现了一些新的错误,其中一个已经被真正的应用程序开发人员证实[12]。

8、相关工作

  • Studying Real-World Bugs:关于现实世界的错误有许多实证研究[9,24,25,29,40,44,45]。 这些研究成功地指导了各种错误训练技术的设计。 据我们所知,我们的工作是第一个专注于Go中的并发错误的研究,第一个研究在访问共享内存时由错误引起的错误和传递消息时的错误。
  • Combating Blocking Bugs:作为一个传统的问题,有许多研究工作在C和Java中打击僵局[7,28,33-35,51,54,55,58,59]。 尽管有用,但我们的研究表明Go中存在许多非死锁阻塞错误,这些错误并不是这些技术的目标。 提出了一些技术来检测由于误用信道引起的阻塞错误[38,39,49,56]。 但是,阻止错误可能是由其他原语引起的。 我们的研究揭示了许多用于阻止错误的代码模式,这些模式可以作为未来阻塞错误检测技术的基础。
  • Combating Non-Blocking Bugs:许多以前的研究工作是为了检测,诊断和修复由于未能同步共享内存访问而引起的非死锁错误[4,5,8,14,16,17,30-32,43,46,47,52,62-64]。 他们承诺将应用于Go并发错误。 但是,我们的研究发现,在消息传递过程中由错误引起的非阻塞错误的数量不可忽略,并且这些错误不在以前的工作中。 我们的研究强调在消息传递过程中需要新技术来对抗错误。

9、Conclusion

  作为一种为并发性设计的编程语言,Go在goroutines之间提供了轻量级goroutine和基于通道的消息传递。 针对Go在各类应用中的应用越来越多,本文从两个正交维度对171个真实世界的Go并发错误进行了第一次全面的实证研究。 我们的研究中提供了许多有趣的发现和含义。 我们希望我们的研究能够加深对Go并发错误的理解,并引起对Go并发错误的更多关注。

参考

  • [1] Principles of designing Go APIs with channels. https://inconshreveable.com/07-08-2014/principles-of-designing-go- apis-with-channels/.

  • [2] The Go Blog: Share Memory By Communicating. URL: https://blog.golang.org/share-memory-by-communicating.

  • [3] Sameer Ajmani. Advanced Go Concurrency Patterns. URL: https://talks.golang.org/2013/advconc.slide.

  • [4] Joy Arulraj, Po-Chun Chang, Guoliang Jin, and Shan Lu. Production- run software failure diagnosis via hardware performance counters. In Proceedings of the 18th International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS ’13), Houston, Texas, USA, March 2013.

  • [5] Joy Arulraj, Guoliang Jin, and Shan Lu. Leveraging the short-term memory of hardware to diagnose production-run software failures. In Proceedings of the 19th International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS ’14), Salt Lake City, Utah, USA, March 2014.

  • [6] boltdb. An embedded key/value database for Go. URL: https://github.com/boltdb/bolt.

  • [7] Yan Cai and W. K. Chan. Magiclock: Scalable detection of potential deadlocks in large-scale multithreaded programs. IEEE Transactions on Software Engineering, 40(3):266-281, 2014.

  • [8] Lee Chew and David Lie. Kivati: Fast detection and prevention of atomicity violations. In Proceedings of the 5th European Conference on Computer systems (EuroSys ’10), Paris, France, April 2010.

  • [9] Andy Chou, Junfeng Yang, Benjamin Chelf, Seth Hallem, and Dawson Engler. An empirical study of operating systems errors. In Proceedings of the 18th ACM symposium on Operating Systems Principles (SOSP ’01), Banff, Alberta, Canada, October 2001.

  • [10] Cockroach. CockroachDB is a cloud-native SQL database for build- ing global, scalable cloud services that survive disasters. URL: https://github.com/cockroachdb/cockroach.

  • [11] Russ Cox. Bell Labs and CSP Threads. URL: http://swtch.com/ rsc/thread/.

  • [12] Graphql Developers. A thread-safe way of appending errors into Result.Errors. URL: https://github.com/graphql-go/graphql/pull/434.

  • [13] Docker. Docker - Build, Ship, and Run Any App, Anywhere. URL: https://www.docker.com/.

  • [14] John Erickson, Madanlal Musuvathi, Sebastian Burckhardt, and Kirk Olynyk. Effective data-race detection for the kernel. In Proceedings of the 9th USENIX Conference on Operating Systems Design and Imple- mentation (OSDI ’10), Vancouver, BC, Canada, October 2010.

  • [15] ETCD. A distributed, reliable key-value store for the most critical data of a distributed system. URL: https://github.com/coreos/etcd.

  • [16] CormacFlanaganandStephenNFreund.Atomizer:Adynamicatomic- ity checker for multithreaded programs. In Proceedings of the 31st ACM SIGPLAN-SIGACT symposium on Principles of programming languages (POPL ’04), Venice, Italy, January 2004.

  • [17] Qi Gao, Wenbin Zhang, Zhezhe Chen, Mai Zheng, and Feng Qin. 2nd- strike: Toward manifesting hidden concurrency typestate bugs. In Proceedings of the 16th International Conference on Architectural Sup- port for Programming Languages and Operating Systems (ASPLOS ’11), Newport Beach, California, USA, March 2011.

  • [18] GitHub. The fifteen most popular languages on GitHub. URL: https://octoverse.github.com/.

  • [19] Google.Ahighperformance,opensource,generalRPCframeworkthat puts mobile and HTTP/2 first. URL: https://github.com/grpc/grpc-go.

  • [20] Google. Effective Go. URL: https://golang.org/doc/effective_go.html.

  • [21] Google. Effective Go: Concurrency. URL:https://golang.org/doc/effective_go.html#concurrency.

  • [22] Google. RPC Benchmarking. URL:https://grpc.io/docs/guides/benchmarking.html.

  • [23] Google. The Go Programming Language – Release History. URL: https://golang.org/doc/devel/release.html.

  • [24] Rui Gu, Guoliang Jin, Linhai Song, Linjie Zhu, and Shan Lu. What change history tells us about thread synchronization. In Proceedings of the 2015 10th Joint Meeting on Foundations of Software Engineering, Bergamo, Italy, August 2015.

  • [25] Haryadi S. Gunawi, Mingzhe Hao, Tanakorn Leesatapornwongsa, Tiratat Patana-anake, Thanh Do, Jeffry Adityatama, Kurnia J. Eliazar, Agung Laksono, Jeffrey F. Lukman, Vincentius Martin, and Anang D. Satria. What bugs live in the cloud? a study of 3000+ issues in cloud systems. In Proceedings of the ACM Symposium on Cloud Computing (SOCC’ 14), Seattle, Washington, USA, November 2014.

  • [26] Hectane. Lightweight SMTP client written in Go. URL: https://github.com/hectane.

  • [27] C.A.R.Hoare.CommunicatingSequentialProcesses.Communications of the ACM, 21(8):666-677, 1978.

  • [28] Omar Inverso, Truc L. Nguyen, Bernd Fischer, Salvatore La Torre, and Gennaro Parlato. Lazy-cseq: A context-bounded model checking tool for multi-threaded c-programs. In 30th IEEE/ACM International Confer- ence on Automated Software Engineering (ASE ’15), Lincoln, Nebraska, USA, November 2015.

  • [29] Guoliang Jin, Linhai Song, Xiaoming Shi, Joel Scherpelz, and Shan Lu. Understanding and detecting real-world performance bugs. In Proceedings of the 33rd ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI’ 12), Beijing, China, June 2012.

  • [30] Guoliang Jin, Linhai Song, Wei Zhang, Shan Lu, and Ben Liblit. Au- tomated atomicity-violation fixing. In Proceedings of the 32nd ACM SIGPLAN Conference on Programming Language Design and Implemen- tation (PLDI’ 11), San Jose, California, USA, June 2011.

  • [31] Guoliang Jin, Aditya V. Thakur, Ben Liblit, and Shan Lu. Instrumenta- tion and sampling strategies for cooperative concurrency bug isolation. In Proceedings of the ACM International Conference on Object oriented programming systems languages and applications (OOPSLA ’10), Reno/- Tahoe, Nevada, USA, October 2010.

  • [32] Guoliang Jin, Wei Zhang, Dongdong Deng, Ben Liblit, and Shan Lu. Automated concurrency-bug fixing. In Proceedings of the 10th USENIX Conference on Operating Systems Design and Implementation (OSDI’12), Hollywood, California, USA, October 2012.

  • [33] Pallavi Joshi, Chang-Seo Park, Koushik Sen, and Mayur Naik. A ran- domized dynamic program analysis technique for detecting real dead- locks. In Proceedings of the 30th ACM SIGPLAN Conference on Program- ming Language Design and Implementation (PLDI ’09), Dublin, Ireland, June 2009.

  • [34] Horatiu Jula, Daniel Tralamazza, Cristian Zamfir, and George Candea. Deadlock immunity: Enabling systems to defend against deadlocks. In Proceedings of the 8th USENIX Conference on Operating systems design and implementation (OSDI ’08), San Diego, California, USA, December 2008.

  • [35] Daniel Kroening, Daniel Poetzl, Peter Schrammel, and Björn Wachter. Sound static deadlock analysis for c/pthreads. In 31st IEEE/ACM In- ternational Conference on Automated Software Engineering (ASE ’16), Singapore, Singapore, September 2016.

  • [36] Kubernetes. Production-Grade Container Orchestration. URL: https://kubernetes.io/.

  • [37] Leslie Lamport. Concurrent Reading and Writing. Communications of the ACM, 20(11):806-811, 1977.

  • [38] Julien Lange, Nicholas Ng, Bernardo Toninho, and Nobuko Yoshida. Fencing off go: Liveness and safety for channel-based programming. In Proceedings of the 44th ACM SIGPLAN Symposium on Principles of Programming Languages (POPL ’17), Paris, France, January 2017.

  • [39] Julien Lange, Nicholas Ng, Bernardo Toninho, and Nobuko Yoshida. A static verification framework for message passing in go using be- havioural types. In IEEE/ACM 40th International Conference on Software Engineering (ICSE ’18), Gothenburg, Sweden, June 2018.

  • [40] Tanakorn Leesatapornwongsa, Jeffrey F. Lukman, Shan Lu, and Haryadi S. Gunawi. Taxdc: A taxonomy of non-deterministic concur- rency bugs in datacenter distributed systems. In Proceedings of the 21th International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS ’16), Atlanta, Georgia, USA, April 2016.

  • [41] Zhenmin Li, Lin Tan, Xuanhui Wang, Shan Lu, Yuanyuan Zhou, and Chengxiang Zhai. Have things changed now?: An empirical study of bug characteristics in modern open source software. In Proceedings of the 1st workshop on Architectural and system support for improving software dependability (ASID ’06), San Jose, California, USA, October 2006.

  • [42] Ziyi Lin, Darko Marinov, Hao Zhong, Yuting Chen, and Jianjun Zhao. Jacontebe: A benchmark suite of real-world java concurrency bugs. In 30th IEEE/ACM International Conference on Automated Software Engineering (ASE ’15), Lincoln, Nebraska, USA, November 2015.

  • [43] Haopeng Liu, Yuxi Chen, and Shan Lu. Understanding and generating high quality patches for concurrency bugs. In Proceedings of the 2016 24th ACM SIGSOFT International Symposium on Foundations of Software Engineering (FSE ’16), Seattle, Washington, USA, November 2016.

  • [44] Lanyue Lu, Andrea C. Arpaci-Dusseau, Remzi H. Arpaci-Dusseau, and Shan Lu. A study of linux file system evolution. In Proceedings of the 11th USENIX Conference on File and Storage Technologies (FAST ’13), San Jose, California, USA, February 2013.

  • [45] Shan Lu, Soyeon Park, Eunsoo Seo, and Yuanyuan Zhou. Learning from mistakes – a comprehensive study of real world concurrency bug characteristics. In Proceedings of the 13th International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS ’08), Seattle, Washington, USA, March 2008.

  • [46] ShanLu,JosephTucek,FengQin,andYuanyuanZhou.Avio:Detecting atomicity violations via access interleaving invariants. In Proceedings of the 12th International Conference on Architectural Support for Pro- gramming Languages and Operating Systems (ASPLOS ’06), San Jose, California, USA, October 2006.

  • [47] Brandon Lucia and Luis Ceze. Finding concurrency bugs with context- aware communication graphs. In Proceedings of the 42nd Annual IEEE/ACM International Symposium on Microarchitecture (MICRO ’09), New York, USA, December 2009.

  • [48] Kedar S. Namjoshi. Are concurrent programs that are easier to write also easier to check? In Workshop on Exploiting Concurrency Efficiently and Correctly, 2008.

  • [49] Nicholas Ng and Nobuko Yoshida. Static deadlock detection for con- current go by global session graph synthesis. In Proceedings of the 25th International Conference on Compiler Construction (CC ’16), Barcelona, Spain, March 2016.

  • [50] Rob Pike. Go Concurrency Patterns. URL: https://talks.golang.org/2012/concurrency.slide.

  • [51] Dawson R. Engler and Ken Ashcraft. Racerx: Effective, static detection of race conditions and deadlocks. In Proceedings of the 19th ACM symposium on Operating systems principles (SOSP ’03), Bolton Landing, New York, USA, October 2003.

  • [52] Stefan Savage, Michael Burrows, Greg Nelson, Patrick Sobalvarro, and Thomas Anderson. Eraser: A dynamic data race detector for multithreaded programs. ACM Transactions on Computer Systems,15(4):391-411, 1997.

  • [53] Konstantin Serebryany and Timur Iskhodzhanov. Threadsanitizer: Data race detection in practice. In Proceedings of the Workshop on Binary Instrumentation and Applications (WBIA ’09), New York, USA, December 2009.

  • [54] Vivek K Shanbhag. Deadlock-detection in java-library using static- analysis. In 15th Asia-Pacific Software Engineering Conference (APSEC ’08), Beijing, China, December 2008.

  • [55] Francesco Sorrentino. Picklock: A deadlock prediction approach under nested locking. In Proceedings of the 22nd International Symposium on Model Checking Software (SPIN ’15), Stellenbosch, South Africa, August 2015.

  • [56] Kai Stadtmüller, Martin Sulzmann, and Peter” Thiemann. Static trace- based deadlock analysis for synchronous mini-go. In 14th Asian Sym- posium on Programming Languages and Systems (APLAS ’16), Hanoi, Vietnam, November 2016.

  • [57] Jie Wang, Wensheng Dou, Yu Gao, Chushu Gao, Feng Qin, Kang Yin, and Jun Wei. A comprehensive study on real world concurrency bugs in node.js. In Proceedings of the 32nd IEEE/ACM International Conference on Automated Software Engineering (ASE ’17), Urbana-Champaign, Illinois, USA, October 2017.

  • [58] Yin Wang, Terence Kelly, Manjunath Kudlur, Stéphane Lafortune, and Scott A Mahlke. Gadara: Dynamic deadlock avoidance for multi- threaded programs. In Proceedings of the 8th USENIX Conference on Operating systems design and implementation (OSDI ’08), San Diego, California, USA, December 2008.

  • [59] Yin Wang, Stéphane Lafortune, Terence Kelly, Manjunath Kudlur, and Scott A. Mahlke. The theory of deadlock avoidance via discrete control. In Proceedings of the 36th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages (POPL ’09), Savannah, Georgia, USA, January 2009.

  • [60] Wikipedia. Go (programming language). URL: https://en.wikipedia.org/wiki/Go_(programming_language).

  • [61] Weiwei Xiong, Soyeon Park, Jiaqi Zhang, Yuanyuan Zhou, and Zhiqiang Ma. Ad hoc synchronization considered harmful. In Pro- ceedings of the 9th USENIX Conference on Operating systems design and implementation (OSDI ’10), Vancouver, British Columbia, Canada, October 2010.

  • [62] JieYuandSatishNarayanasamy.Acaseforaninterleavingconstrained shared-memory multi-processor. In Proceedings of the 36th annual International symposium on Computer architecture (ISCA ’09), Austin, Texas, USA, June 2009.

  • [63] YuanYu,TomRodeheffer,andWeiChen.Racetrack:Efficientdetection of data race conditions via adaptive tracking. In Proceedings of the 20th ACM symposium on Operating systems principles (SOSP ’05), Brighton, United Kingdom, October 2005.

  • [64] Wei Zhang, Chong Sun, and Shan Lu. Conmem: detecting severe concurrency bugs through an effect-oriented approach. In Proceedings of the 15th International Conference on Architectural Support for Pro- gramming Languages and Operating Systems (ASPLOS ’10), Pittsburgh, Pennsylvania, USA, March 2010.