RTS 是陈浩(网名左耳朵耗子)在极客时间专栏里发起的一个活动,目的是通过分享的方式来坚持学习。

每人每周写一个 ARTS:

Algorithm 是一道算法题,

Review 是读一篇英文文章,

Technique/Tips 是分享一个小技术,

Share 是分享一个观点。

Algorithm:

leetCode:

82

83

Review

Golang 大杀器之性能剖析 pprof

前言

写了几吨代码,实现了几百个接口。功能测试也通过了,终于成功的部署上线了
结果,性能不佳,什么鬼?😭

想做性能分析?

PProf

想要进行性能优化,首先瞩目在 Go 自身提供的工具链来作为分析依据,本文将带你学习、使用 Go 后花园,涉及如下:

  • runtime/pprof:采集程序(非 Server)的运行数据进行分析
  • net/http/pprof:采集 HTTP Server 的运行时数据进行分析

是什么

pprof 是用于可视化和分析性能分析数据的工具
pprof 以 profile.proto 读取分析样本的集合,并生成报告以可视化并帮助分析数据(支持文本和图形报告)
profile.proto 是一个 Protocol Buffer v3 的描述文件,它描述了一组 callstack 和 symbolization 信息, 作用是表示统计分析的一组采样的调用栈,是很常见的 stacktrace 配置文件格式

支持什么使用模式

  • Report generation:报告生成
  • Interactive terminal use:交互式终端使用
  • Web interface:Web 界面

可以做什么

  • CPU Profiling:CPU 分析,按照一定的频率采集所监听的应用程序 CPU(含寄存器)的使用情况,可确定应用程序在主动消耗 CPU 周期时花费时间的位置
    • 一旦启用CPU数据采样,Go运行时会每隔一段短暂的时间(10ms)就中断一次(由SIGPROF信号引发)并记录当前所有goroutine的函数栈信息(存入cpu.prof)。
  • Memory Profiling:内存分析,在应用程序进行堆分配时记录堆栈跟踪,用于监视当前和历史内存使用情况,以及检查内存泄漏
    • 堆内存分配的采样频率可配置,默认==每1000次==堆内存分配会做一次采样(存入mem.prof)。
  • Block Profiling:阻塞分析,记录 goroutine 阻塞等待同步(包括定时器通道)的位置
  • Mutex Profiling:互斥锁分析,报告互斥锁的竞争情况

一个简单的例子

我们将编写一个简单且有点问题的例子,用于基本的程序初步分析

编写 demo 文件

(1)demo.go,文件内容:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
package main
import (
"log"
"net/http"
_ "net/http/pprof"
"github.com/EDDYCJY/go-pprof-example/data"
)

func main() {
go func() {
for {
log.Println(data.Add("https://github.com/EDDYCJY"))
}
}()
http.ListenAndServe("0.0.0.0:6060", nil)
}

(2)data/d.go,文件内容:

1
2
3
4
5
6
7
8
package data
var datas []string
func Add(str string) string {
data := []byte(str)
sData := string(data)
datas = append(datas, sData)
return sData
}

运行这个文件,你的 HTTP 服务会多出 /debug/pprof 的 endpoint 可用于观察应用程序的情况

分析

一、通过 Web 界面

查看当前总览:访问 http://127.0.0.1:6060/debug/pprof/

1
2
3
4
5
6
7
8
/debug/pprof/
profiles:
0 block
5 goroutine
3 heap
0 mutex
9 threadcreate
full goroutine stack dump

这个页面中有许多子页面,咱们继续深究下去,看看可以得到什么?

  • cpu(CPU Profiling): $HOST/debug/pprof/profile,默认进行 30s 的 CPU Profiling,得到一个分析用的 profile 文件
  • block(Block Profiling):$HOST/debug/pprof/block,查看导致阻塞同步的堆栈跟踪
  • goroutine:$HOST/debug/pprof/goroutine,查看当前所有运行的 goroutines 堆栈跟踪
  • heap(Memory Profiling): $HOST/debug/pprof/heap,查看活动对象的内存分配情况
  • mutex(Mutex Profiling):$HOST/debug/pprof/mutex,查看导致互斥锁的竞争持有者的堆栈跟踪
  • threadcreate:$HOST/debug/pprof/threadcreate,查看创建新OS线程的堆栈跟踪

二、通过交互式终端使用

(1)go tool pprof http://localhost:6060/debug/pprof/profile?seconds=60

1
2
3
4
5
6
7
$ go tool pprof http://localhost:6060/debug/pprof/profile\?seconds\=60
Fetching profile over HTTP from http://localhost:6060/debug/pprof/profile?seconds=60
Saved profile in /Users/eddycjy/pprof/pprof.samples.cpu.007.pb.gz
Type: cpu
Duration: 1mins, Total samples = 26.55s (44.15%)
Entering interactive mode (type "help" for commands, "o" for options)
(pprof)

执行该命令后,需等待 60 秒(可调整 seconds 的值),pprof 会进行 CPU Profiling。结束后将默认进入 pprof 的交互式命令模式,可以对分析的结果进行查看或导出。具体可执行 pprof help 查看命令说明

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
(pprof) top10
Showing nodes accounting for 25.92s, 97.63% of 26.55s total
Dropped 85 nodes (cum <= 0.13s)
Showing top 10 nodes out of 21
flat flat% sum% cum cum%
23.28s 87.68% 87.68% 23.29s 87.72% syscall.Syscall
0.77s 2.90% 90.58% 0.77s 2.90% runtime.memmove
0.58s 2.18% 92.77% 0.58s 2.18% runtime.freedefer
0.53s 2.00% 94.76% 1.42s 5.35% runtime.scanobject
0.36s 1.36% 96.12% 0.39s 1.47% runtime.heapBitsForObject
0.35s 1.32% 97.44% 0.45s 1.69% runtime.greyobject
0.02s 0.075% 97.51% 24.96s 94.01% main.main.func1
0.01s 0.038% 97.55% 23.91s 90.06% os.(*File).Write
0.01s 0.038% 97.59% 0.19s 0.72% runtime.mallocgc
0.01s 0.038% 97.63% 23.30s 87.76% syscall.Write
  • flat:给定函数上运行耗时

  • flat%:同上的 CPU 运行耗时总比例

  • sum%:给定函数累积使用 CPU 总比例

  • cum:当前函数加上它之上的调用运行总耗时

  • cum%:同上的 CPU 运行耗时总比例
    最后一列为函数名称,在大多数的情况下,我们可以通过这五列得出一个应用程序的运行情况,加以优化 🤔
    (2)go tool pprof [http://localhost](http://localhost/):6060/debug/pprof/heap

    1
    2
    3
    4
    5
    6
    7
    8
    9
    $ go tool pprof http://localhost:6060/debug/pprof/heap
    Fetching profile over HTTP from http://localhost:6060/debug/pprof/heap
    Saved profile in /Users/eddycjy/pprof/pprof.alloc_objects.alloc_space.inuse_objects.inuse_space.008.pb.gz
    Type: inuse_space
    Entering interactive mode (type "help" for commands, "o" for options)
    (pprof) top
    Showing nodes accounting for 837.48MB, 100% of 837.48MB total
    flat flat% sum% cum cum%
    837.48MB 100% 100% 837.48MB 100% main.main.func1
  • -inuse_space:分析应用程序的常驻内存占用情况

  • -alloc_objects:分析应用程序的内存临时分配情况
    (3) go tool pprof http://localhost:6060/debug/pprof/block
    (4) go tool pprof http://localhost:6060/debug/pprof/mutex

三、PProf 可视化界面

这是令人期待的一小节。在这之前,我们需要简单的编写好测试用例来跑一下

编写测试用例

(1)新建 data/d_test.go,文件内容:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
package data

import "testing"

const url = "https://github.com/EDDYCJY"

func TestAdd(t *testing.T) {
s := Add(url)
if s == "" {
t.Errorf("Test.Add error!")
}
}

func BenchmarkAdd(b *testing.B) {
for i := 0; i < b.N; i++ {
Add(url)
}
}

(2)执行测试用例

1
2
3
4
5
$ go test -bench=. -cpuprofile=cpu.prof
pkg: github.com/EDDYCJY/go-pprof-example/data
BenchmarkAdd-4 10000000 187 ns/op
PASS
ok github.com/EDDYCJY/go-pprof-example/data 2.300s

-memprofile 也可以了解一下

启动 pprof 可视化界面

方法一:

1
$ go tool pprof -http=:8080 cpu.prof

方法二:

1
2
$ go tool pprof cpu.prof 
$ (pprof) web

如果出现 Could not execute dot; may need to install graphviz.,就是提示你要安装 graphviz 了 (请右拐谷歌)

查看 PProf 可视化界面

(1)Top

(2)Graph

框越大,线越粗代表它占用的时间越大哦
(3)Peek

(4)Source

通过 PProf 的可视化界面,我们能够更方便、更直观的看到 Go 应用程序的调用链、使用情况等,并且在 View 菜单栏中,还支持如上多种方式的切换
你想想,在烦恼不知道什么问题的时候,能用这些辅助工具来检测问题,是不是瞬间效率翻倍了呢 👌

四、PProf 火焰图

另一种可视化数据的方法是火焰图,需手动安装原生 PProf 工具:
(1) 安装 PProf

1
$ go get -u github.com/google/pprof

(2) 启动 PProf 可视化界面:

1
$ pprof -http=:8080 cpu.prof

(3) 查看 PProf 可视化界面
打开 PProf 的可视化界面时,你会明显发现比官方工具链的 PProf 精致一些,并且多了 Flame Graph(火焰图)

它就是本次的目标之一,它的最大优点是动态的。调用顺序由上到下(A -> B -> C -> D),每一块代表一个函数,越大代表占用 CPU 的时间更长。同时它也支持点击块深入进行分析!

总结

在本章节,粗略地介绍了 Go 的性能利器 PProf。在特定的场景中,PProf 给定位、剖析问题带了极大的帮助
希望本文对你有所帮助,另外建议能够自己实际操作一遍,最好是可以深入琢磨一下,内含大量的用法、知识点

思考题

你很优秀的看到了最后,那么有两道简单的思考题,希望拓展你的思路
(1)flat 一定大于 cum 吗,为什么?什么场景下 cum 会比 flat 大?
(2)本章节的 demo 代码,有什么性能问题?怎么解决它?
来,晒出你的想法

深度优先算法 (Depth-First-Search)

深度优先搜索算法(Depth-First-Search),是搜索算法的一种。它沿着树的深度遍历树的节点,尽可能深的搜索树的分 支。
当节点v的所有边都己被探寻过,搜索将回溯到发现节点v的那条边的起始节点。
这一过程一直进行到已发现从源节点可达的所有节点为止。
如果还存在未被发 现的节点,则选择其中一个作为源节点并重复以上过程,整个进程反复进行直到所有节点都被访问为止。

深度优先搜索是图论中的经典算法,利用深度优先搜索算法可以产生目标图的相应拓扑排序表,利用拓扑排序表可以方便的解决很多相关的图论问题,如最大路径问题等等。一般用堆数据结构来辅助实现DFS算法。

DFS属于盲目搜索

深度优先遍历图算法步骤:

  • 访问顶点v;
  • 依次从v的未被访问的邻接点出发,对图进行深度优先遍历;直至图中和v有路径相通的顶点都被访问;
  • 若此时图中尚有顶点未被访问,则从一个未被访问的顶点出发,重新进行深度优先遍历,直到图中所有顶点均被访问过为止。

举个实例:

DFS 在访问图中某一起始顶点 v 后,由 v 出发,访问它的任一邻接顶点 w1;再从 w1 出发,访问与 w1邻 接但还没有访问过的顶点 w2;然后再从 w2 出发,进行类似的访问,… 如此进行下去,直至到达所有的邻接顶点都被访问过的顶点 u 为止。
接着,退回一步,退到前一次刚访问过的顶点,看是否还有其它没有被访问的邻接顶点。如果有,则访问此顶点,之后再从此顶点出发,进行与前述类似的访问;如果没有,就再退回一步进行搜索。重复上述过程,直到连通图中所有顶点都被访问过为止。

例如下图,其深度优先遍历顺序为 1->2->4->8->5->3->6->7

深度优先算法

1
2
3
4
5
6
7
8
func dfs(root *TreeNode) {
if root == nil {
return
}
fmt.Print(root.Val)
dfs(root.Left)
dfs(root.Right)
}

广度优先搜索算法(Breadth-First-Search)

广度优先搜索算法(Breadth-First-Search),是一种图形搜索算法

简单的说,BFS是从根节点开始,沿着树(图)的宽度遍历树(图)的节点。如果所有节点均被访问,则算法中止。
BFS同样属于盲目搜索。一般用队列数据结构来辅助实现BFS算法。

算法步骤:

  1. 首先将根节点放入队列中。
  2. 从队列中取出第一个节点,并检验它是否为目标。如果找到目标,则结束搜寻并回传结果。否则将它所有尚未检验过的直接子节点加入队列中。
  3. 若队列为空,表示整张图都检查过了——亦即图中没有欲搜寻的目标。结束搜寻并回传“找不到目标”。
  4. 重复步骤2。

如上图,其广度优先算法的遍历顺序为:1->2->3->4->5->6->7->8

代码实现

leetcode 真题

662. 二叉树最大宽度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
type AnnotatedNode struct {
node *TreeNode
dept,
ops int
}

type linkNode struct {
value *AnnotatedNode
next *linkNode
}

// 链表
type linkedAnnotatedNodeList struct {
head *linkNode //队首
tail *linkNode //队尾
count int //长度
}

// 初始化链表
func NewLinkedAnnotatedNodeList() *linkedAnnotatedNodeList {
return &linkedAnnotatedNodeList{head: nil, tail: nil, count: 0}
}

func (this *linkedAnnotatedNodeList) IsEmpty() bool {
return this.count == 0
}
func (this *linkedAnnotatedNodeList) Add(value *AnnotatedNode) {
node := new(linkNode)
node.value = value

this.count++
if this.tail == nil {
this.head = node
this.tail = node
node.next = nil
return
}

this.tail.next = node
node.next = nil
this.tail = node
}

func (this *linkedAnnotatedNodeList) Delete() *linkNode {
if this.head == nil {
return nil
}

this.count--
if this.head == this.tail {
node := this.head
this.head = nil
this.tail = nil

return node
}
node := this.head
this.head = this.head.next
return node
}

type Queue struct {
link *linkedAnnotatedNodeList
}

func NewQueue() *Queue {
return &Queue{link: NewLinkedAnnotatedNodeList()}
}

//加入队列
func (this *Queue) Put(value *AnnotatedNode) {
this.link.Add(value)
}

//pop出队列
func (this *Queue) Pop() *linkNode {
return this.link.Delete()
}

//获得队列的长度
func (this *Queue) GetSize() int {
return this.link.count
}

func (this *Queue) IsEmpty() bool {
return this.GetSize() == 0
}

func widthOfBinaryTree(root *TreeNode) int {
query := NewQueue()
query.Put(&AnnotatedNode{
node: root,
dept: 0,
ops: 0,
})
curDepth := 0
left := 0
ans := 0
for query.GetSize() != 0 {
a := query.Pop().value
if a.node != nil {
query.Put(&AnnotatedNode{
node: a.node.Left,
dept: a.dept + 1,
ops: a.ops * 2,
})
query.Put(&AnnotatedNode{
node: a.node.Right,
dept: a.dept + 1,
ops: a.ops*2 + 1,
})
if curDepth != a.dept {
curDepth = a.dept
left = a.ops
}
ans = Max(ans, a.ops-left+1)
}
}
return ans
}

func Max(a, b int) int {
if a > b {
return a
} else {
return b
}
}

103. 二叉树的锯齿形层次遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
type AnnotatedNode struct {
node *TreeNode
dept, //深度
ops int
}

type linkNode struct {
value *AnnotatedNode
next *linkNode
}

// 链表
type linkedAnnotatedNodeList struct {
head *linkNode //队首
tail *linkNode //队尾
count int //长度
}

// 初始化链表
func NewLinkedAnnotatedNodeList() *linkedAnnotatedNodeList {
return &linkedAnnotatedNodeList{head: nil, tail: nil, count: 0}
}

func (this *linkedAnnotatedNodeList) IsEmpty() bool {
return this.count == 0
}
func (this *linkedAnnotatedNodeList) Add(value *AnnotatedNode) {
node := new(linkNode)
node.value = value

this.count++
if this.tail == nil {
this.head = node
this.tail = node
node.next = nil
return
}

this.tail.next = node
node.next = nil
this.tail = node
}

func (this *linkedAnnotatedNodeList) Delete() *linkNode {
if this.head == nil {
return nil
}

this.count--
if this.head == this.tail {
node := this.head
this.head = nil
this.tail = nil

return node
}
node := this.head
this.head = this.head.next
return node
}

type Queue struct {
link *linkedAnnotatedNodeList
}

func NewQueue() *Queue {
return &Queue{link: NewLinkedAnnotatedNodeList()}
}

//加入队列
func (this *Queue) Put(value *AnnotatedNode) {
this.link.Add(value)
}

//pop出队列
func (this *Queue) Pop() *linkNode {
return this.link.Delete()
}

//获得队列的长度
func (this *Queue) GetSize() int {
return this.link.count
}

func (this *Queue) IsEmpty() bool {
return this.GetSize() == 0
}


func zigzagLevelOrder(root *TreeNode) [][]int {
result := make([][]int, 0)
query := NewQueue()

query.Put(&AnnotatedNode{node: root, dept: 0, ops: 0})
for query.GetSize() != 0 {
a := query.Pop().value
if a.node != nil {
if len(result) <= a.dept { //小于层数
temp := make([]int, 0)
temp = append(temp, a.node.Val)
result = append(result, temp)
} else {
result[a.dept] = append(result[a.dept], a.node.Val)
}
query.Put(&AnnotatedNode{a.node.Left, a.dept + 1, 0})
query.Put(&AnnotatedNode{a.node.Right, a.dept + 1, 0})
}
}
for k, v := range result {
if k%2 == 1 {
result[k] = stringReverse(v)
}
}
return result
}
func stringReverse(src []int) []int {
if src == nil {
panic(fmt.Errorf("the src can't be empty!"))
}
count := len(src)
mid := count / 2
for i := 0; i < mid; i++ {
tmp := src[i]
src[i] = src[count-1]
src[count-1] = tmp
count--
}
return src
}

链表提供了高效的节点重排能力, 以及顺序性的节点访问方式, 并且可以通过增删节点来灵活地调整链表的长度。

链表在 Redis 中的应用非常广泛, 比如列表键的底层实现之一就是链表: 当一个列表键包含了数量比较多的元素, 又或者列表中包含的元素都是比较长的字符串时, Redis 就会使用链表作为列表键的底层实现。

Read more »

SDS全拼为:simple dynamic string,解释为:简单动态字符串

​ C语言字符串使用长度为n+1的字符数组来表示长度为n的字符串,并且字符数组的最后一个元素总是空字符’\0’,因为这种字符串表示方式不能满足Redis对字符串在安全性、效率以及功能方面的要求,所以Redis自己构建了SDS,用于满足其需求。在Redis里,C语言字符串只用于一些无须对字符串值进行修改的地方,比如:日志。在Redis中,包含字符串值的键值对都是使用SDS实现的,除此之外,SDS还被用于AOF缓冲区、客户端状态的输入缓冲区。

Read more »

ARTS 是陈浩(网名左耳朵耗子)在极客时间专栏里发起的一个活动,目的是通过分享的方式来坚持学习。

每人每周写一个 ARTS:

Algorithm 是一道算法题,

Review 是读一篇英文文章,

Technique/Tips 是分享一个小技术,

Share 是分享一个观点。

Algorithm:

  • leetcode 206
  • leetcode 141
  • leetcode 19

Review

Kubernetes如何改变美团的云基础设施?

原文链接

Vincent Blanchon


本文基于 go 1.14

select 允许在一个goroutine中管理多个channel。但是,当所有channel同时就绪的时候,go需要在其中选择一个执行。go还需要处理没有channel就绪的情况,我们先从就绪的channel开始。

Order

select 不会按照任何规则或者优先级选择到达的channel。go标准库在每次访问的时候,都会将他们顺序打乱,也就是说不能保证任何顺序。

看一个有三个就绪的channel的例子:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
func main() {
a := make(chan bool, 100)
b := make(chan bool, 100)
c := make(chan bool, 100)
for i := 0; i < 10; i++ {
a <- true
b <- true
c <- true
}
for i := 0; i < 10; i++ {
select {
case <-a:
print("< a")

case <-b:
print("< b")

case <-c:
print("< c")

default:
print("< default")
}
}
}

这三个channel都有三个完整的buffer(不会阻塞),下面是程序的输出

1
< b< a< a< b< c< c< c< a< b< b

在 select 的每次迭代中,case 都会被打乱:

由于go 不会删除重复的channel,所以可以使用多次添加case来影响结果,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
func main() {
a := make(chan bool, 100)
b := make(chan bool, 100)
c := make(chan bool, 100)
for i := 0; i < 10; i++ {
a <- true
b <- true
c <- true
}
for i := 0; i < 10; i++ {
select {
case <-a:
print("< a")
case <-a:
print("< a")
case <-a:
print("< a")
case <-a:
print("< a")
case <-a:
print("< a")
case <-a:
print("< a")
case <-a:
print("< a")

case <-b:
print("< b")

case <-c:
print("< c")

default:
print("< default")
}
}
}

输出的结果:

1
< c< a< b< a< b< a< a< c< a< a

当所有channel同时准备就绪时,有80%的机会选择通道a。下面来看一下channel未就绪的情况。

Non-ready channels

select 运行时,如果没有一个case channel就绪,那么他就会运行default:,如果 select中没有写default,那么他就进入等待状态,如下面这个例子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func main() {
a := make(chan bool, 100)
b := make(chan bool, 100)
go func() {
time.Sleep(time.Minute)
for i := 0; i < 10; i++ {
a <- true
b <- true
}
}()

for i := 0; i < 10; i++ {
select {
case <-a:
print("< a")
case <-b:
print("< b")
}
}
}

上面那个例子中,将在一分钟后打印结果。select阻塞在 channel上。这种情况下,处理select的函数将会订阅所有channel并且等待,下面是一个goroutine#7在select中等待的示例,其中另一个goroutine#4也在等待channel:

Goroutine(G7)订阅所有频道并在列表末尾等待。 如果channel发送了一条消息,channel将通知已在等待该消息的另一个Goroutine。一旦收到通知,select 将取消订阅所有channel,并且返回到代码运行.

更多关于channel与等待队列的信息,请查看作者另外一篇文章Go: Buffered and Unbuffered Channels.

上面介绍的逻辑,都是针对于有两个或者以上的活动的channel,实际上如果只有一个活动的channel,go乐意简化select

Simplification

如果只有一个case 加上一个default,例子:

1
2
3
4
5
6
7
8
9
10
11
func main() {
t:= time.NewTicker(time.Second)
for {
select {
case <-t.C:
print("1 second ")
default:
print("default branch")
}
}
}

这种情况下。Go会以非阻塞模式读取channel的操作替换select语句。如果channel在缓冲区中没有任何值,或者发送方准备发送消息,将会运行default。就像下面这张图

如果没有default,则 Go 通过阻塞channel操作重写 select 语句。

原文链接: Go: How Does Go Stop the World? :
Author : Vincent Blanchon

本文基于 go 1.13

在垃圾回收算法中,Stop The Word(STW)是一个很重要的概念,他会中断程序运行,添加写屏障,以便扫描内存 ,现在一起来看看它内部的原理以及可能存在的问题

STW

停止程序运行意味着停止所有运行态的goroutines,一个简单的例子:

1
2
3
func main() {
runtime.GC()
}

运行垃圾回收算法将触发两个阶段的STW

有关垃圾回收的更多细节,请参考同作者的另外一篇文章Go: How Does the Garbage Collector Mark the Memory?

STW的步骤

第一步,抢占所有正在运行的goroutines

第二步,一旦 goroutines被抢占,正在运行的goroutines将在安全的地方暂停,然后所有的p[1]都将被标记为暂停,停止运行任何代码。

第三步,然后,go调度器将M[2]与P分离,并且将M放到空闲列表里面。

对于在每个M上运行的Goroutines,它们将在全局队列[3]>中等待:

那么,一旦所有的goroutines都停止了,那么唯一活跃的goroutines (垃圾回收goroutines)将会安全的运行,并且在垃圾回收完成后,重新拉起所有的goroutines。具体情况,可以通过 go trace查看。

System calls

STW时期可能会影响系统调用,因为系统调用可能会在stw时期返回,通过密集执行系统调用的程序来看看怎样处理这种情况,

1
2
3
4
5
6
7
8
9
func main() {
var wg sync.WaitGroup
wg.Add(10) for i := 0; i < 10; i++ {
go func() {
http.Get(`https://httpstat.us/200`)
wg.Done()
}()
} wg.Wait()
}

他的trace情况。

系统调用在STW时期返回,但是现在已经没有P在运行了。所以他会放到全局队列里面,等待STW结束后再运行。

Latencies

STW的第三步将所有的M与P分离。然而,go将等待调度程序运行、系统调用等自动停止。等待goroutine被抢占应该很快,但是在某些情况下会产生一些延迟,下面是一个极端的例子:

1
2
3
4
5
6
7
8
9
10
11
12
func main() {
var t int
for i := 0;i < 20 ;i++ {
go func() {
for i := 0;i < 1000000000 ;i++ {
t++
}
}()
}

runtime.GC()
}

STW时长达到了2.6S

没有函数调用的goroutine将不会被抢占,并且它的P在任务结束之前不会被释放。这将迫使STW等待他, 有几种解决方案可改善循环中的抢占,有关其的更多信息,可以查看作者另外一篇文章 [Go: Goroutine and Preemption).

Consul 是什么

Consul 是一个支持多数据中心分布式高可用的服务发现和配置共享的服务软件,由 HashiCorp 公司用 Go 语言开发, 基于 Mozilla Public License 2.0 的协议进行开源. Consul 支持健康检查,并允许 HTTP 和 DNS 协议调用 API 存储键值对.
命令行超级好用的虚拟机管理软件 vgrant 也是 HashiCorp 公司开发的产品.
一致性协议采用 Raft 算法,用来保证服务的高可用. 使用 GOSSIP 协议管理成员和广播消息, 并且支持 ACL 访问控制.

Consul 的使用场景

  • docker 实例的注册与配置共享
  • coreos 实例的注册与配置共享
  • vitess 集群
  • SaaS 应用的配置共享
  • 与 confd 服务集成,动态生成 nginx 和 haproxy 配置文件

Consul 的优势

  • 使用 Raft 算法来保证一致性, 比复杂的 Paxos 算法更直接. 相比较而言, zookeeper 采用的是 Paxos, 而 etcd 使用的则是 Raft.
  • 支持多数据中心,内外网的服务采用不同的端口进行监听。 多数据中心集群可以避免单数据中心的单点故障,而其部署则需要考虑网络延迟, 分片等情况等. zookeeper 和 etcd 均不提供多数据中心功能的支持.
  • 支持健康检查. etcd 不提供此功能.
  • 支持 http 和 dns 协议接口. zookeeper 的集成较为复杂, etcd 只支持 http 协议.
  • 官方提供web管理界面, etcd 无此功能.
    综合比较, Consul 作为服务注册和配置管理的新星, 比较值得关注和研究.

Consul 的角色

client: 客户端, 无状态, 将 HTTP 和 DNS 接口请求转发给局域网内的服务端集群.
server: 服务端, 保存配置信息, 高可用集群, 在局域网内与本地客户端通讯, 通过广域网与其他数据中心通讯. 每个数据中心的 server 数量推荐为 3 个或是 5 个.

什么是分布式锁

分布式锁,是控制分布式系统之间同步访问共享资源的一种方式。在分布式系统中,常常需要协调他们的动作。如果不同的系统或是同一个系统的不同主机之间共享了一个或一组资源,那么访问这些资源的时候,往往需要互斥来防止彼此干扰来保证一致性,在这种情况下,便需要使用到分布式锁。
目前几乎很多大型网站及应用都是分布式部署的,分布式场景中的数据一致性问题一直是一个比较重要的话题。分布式的CAP理论告诉我们“任何一个分布式系统都无法同时满足一致性(Consistency)、可用性(Availability)和分区容错性(Partition tolerance),最多只能同时满足两项。”所以,很多系统在设计之初就要对这三者做出取舍。在互联网领域的绝大多数的场景中,都需要牺牲强一致性来换取系统的高可用性,系统往往只需要保证“最终一致性”,只要这个最终时间是在用户可以接受的范围内即可。
在很多场景中,我们为了保证数据的最终一致性,需要很多的技术方案来支持,比如分布式事务、分布式锁等。有的时候,我们需要保证一个方法在同一时间内只能被同一个线程执行。
在这里我们使用Consul来管理分布式锁。Consul内置了服务注册与发现框 架、分布一致性协议实现、健康检查、Key/Value存储、多数据中心方案,不再需要依赖其他工具(比如ZooKeeper等)。

Sessions


session是一个远程进程和consul节点之间的链接,它由一个远程进程和可以显式无效或由于健康检查机制。根据会话配置,创建与已失效会话锁摧毁或释放。

Health checks

Consul支持多种检查 (如 HTTP、 TCP 等)。在session创建过程中可以定义的健康检查列表。这些检查将用于确定是否sessio需要使之失效。

TTL

除了健康检查,会话也具有内置支持的 TTL。当 TTL 过期session被视为无效。远程进程负责更新session之前 TTL 过期。

Golang API

Consul API client 提供一个方便的抽象,session和 K/V 存储。有是一个锁结构与锁定、 解锁和破坏的方法。也有用于帮助创建锁实例方法。API 客户端还负责更新会话。

Creating the Consul client

1
client, err := api.NewClient(&api.Config{Address: "127.0.0.1:8500"})

Creating Lock instance

1
2
3
4
5
6
7
8
9
10
11
12
type LockOptions struct {
Key string // Must be set and have write permissions
Value []byte // Optional, value to associate with the lock
Session string // Optional, created if not specified
SessionOpts *SessionEntry // Optional, options to use when creating a session
SessionName string // Optional, defaults to DefaultLockSessionName (ignored if SessionOpts is given)
SessionTTL string // Optional, defaults to DefaultLockSessionTTL (ignored if SessionOpts is given)
MonitorRetries int // Optional, defaults to 0 which means no retries
MonitorRetryTime time.Duration // Optional, defaults to DefaultMonitorRetryTime
LockWaitTime time.Duration // Optional, defaults to DefaultLockWaitTime
LockTryOnce bool // Optional, defaults to false which means try forever
}

LockOptions 是所有可能的选项的容器,可以用于设置键和值、 定制会话或设置TTL。

1
2
3
4
5
6
7
8
9
10
opts := &api.LockOptions{
Key: "webhook_receiver/1",
Value: []byte("set by sender 1"),
SessionTTL: "10s",
SessionOpts: &api.SessionEntry{
Checks: []string{"check1", "check2"},
Behavior: "release",
},
}
lock, err := client.LockOpts(opts)

另一种常用的方法是 LockKey,它创建一个锁与所有选项设置为默认条目名称除外。

1
lock, err := client.LockKey("webhook_receiver/1")

Acquiring lock

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
stopCh := make(chan struct{})
lockCh, err := lock.Lock(stopCh)
if err != nil {
panic(err)
}
cancelCtx, cancelRequest := context.WithCancel(context.Background())
req, _ := http.NewRequest("GET", "https://example.com/webhook", nil)
req = req.WithContext(cancelCtx)
go func() {
http.DefaultClient.Do(req)
select {
case <-cancelCtx.Done():
log.Println("request cancelled")
default:
log.Println("request done")
err = lock.Unlock()
if err != nil {
log.Println("lock already unlocked")
}
}
}()
go func() {
<-lockCh
cancelRequest()
}()

In computer science, an in-place algorithm is an algorithm which transforms input using no auxiliary data structure. However a small amount of extra storage space is allowed for auxiliary variables. The input is usually overwritten by the output as the algorithm executes. In-place algorithm updates input sequence only through replacement or swapping of elements. An algorithm which is not in-place is sometimes called not-in-place or out-of-place.——摘自原地算法的维基百科

一句话总结就是: 原地算法不依赖额外的资源或者依赖少数的额外资源,仅依靠输出来覆盖输入的一种算法操作。

原理

假设要将具有 n 项内容的数组 a 翻转过来。一种看似简单的方法是创建一个大小相等的新数组,用适当的顺序填充副本,然后再删除:

1
2
3
4
5
function reverse(a[0..n-1])
allocate b[0..n-1] # 额外设定一个数组
for i from 0 to n-1 # 从 0 到 n-1 遍历数组 a
b[n -1 - i] := a[i]
return b

这种方法虽然简单,但是需要 O(n) 的额外空间以使数组 a 和 b 同时可用。此外,分配存储空间和释放存储空间通常是缓慢的操作。如果我们不再需要数组 a 的话,可使用原地算法,用它自己翻转的内容来覆盖掉原先的内容。这样,无论数组有多大,它都只需要辅助变量 i 和 tmp:

1
2
3
4
5
function reverse_in_place(a[0..n-1])
for i from 0 to floor((n-2)/2)
tmp := a[i]
a[i] := a[n − 1 − i]
a[n − 1 − i] := tmp

这样既节省了存储器空间又加快了运算速度。

example:

leetCode 114

go 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func flatten(root *TreeNode)  {
if root == nil {
return
}
flatten(root.Left)
flatten(root.Right)
temp := root.Right
root.Right = root.Left
root.Left = nil
for root.Right != nil {
root = root.Right
}
root.Right = temp
}

其实就是使用前序遍历把右边的树节点移动到左边

第一趟,处理的节点为3,保持不变

第二趟,处理节点 4 保持不变

第三趟,处理节点2 需要把 节点3移动到2的右节点,然后把4 移动到2的最右的右节点

第四趟:处理节点6,不变。

第五趟处理节点 5 不变,

第六趟处理节点1 需要把 2 移动到 1 的右节点,然后把 5 移动到 1的最右右节点。

到此,移动完毕,全程只用了一个变量temp。满足原地算法。

0%