编程语言►Golang

Go为什么要做用户态调度

Go1.1中一个大的特性是Dmitry Vyukov实现的新的调度器. 新的调度器为并行的Go程序带来了巨大的性能提升.因此，我必须写这篇文章来介绍一下.

这里是原始的设计文档的链接.设计文档里有所有你想知道的细节，本篇文章通过更多的图片来使描述更加清晰.

为什么Go的运行时需要一个调度器?

在我们详细了解新的调度器之前，我们需要先来看看为什么的问题?

操作系统已经提供了线程调度的功能，为什么还要在用户态实现一个调度器?

POSIX线程API在很大程度上是对现有Unix进程模型的扩展,线程获得了许多和进程同样的控件.线程有它们自己的信号掩码,能够设置CPU亲和力,能够通过cgroups设置可以使用的资源.所有这些控制都增加了额外的开销，当你的程序使用100,000个线程时这些开销快速地增加,而这些对使用goroutines的go程序没有必要.

另外一个问题是:OS不能基于go模型对调度做出正确的决策.比如,Go的gc需要所有线程停止运行，而且内存必须处于一致的状态.这在Go中是通过等待运行的线程运行到某一点，我们知道这时内存处于一致的状态.

当你有很多可以在任意时间点调度的线程,那么你就需要等它们运行到一个一致状态的点.但是Go调度器可以知道内存一致的状态并只在此时进行调度.When you have many threads scheduled out at random points, chances are that you’re going to have to wait for a lot of them to reach a consistent state. The Go scheduler can make the decision of only scheduling at points where it knows that memory is consistent. This means that when we stop for garbage collection, we only have to wait for the threads that are being actively run on a CPU core.

Our Cast of Characters

There are 3 usual models for threading. One is N:1 where several userspace threads are run on one OS thread. This has the advantage of being very quick to context switch but cannot take advantage of multi-core systems. Another is 1:1 where one thread of execution matches one OS thread. It takes advantage of all of the cores on the machine, but context switching is slow because it has to trap through the OS.

Go tries to get the best of both worlds by using a M:N scheduler. It schedules an arbitrary number of goroutines onto an arbitrary number of OS threads. You get quick context switches and you take advantage of all the cores in your system. The main disadvantage of this approach is the complexity it adds to the scheduler.

为了完成调度任务,Go scheduler使用3个主要的实体:


The triangle represents an OS thread. It’s the thread of execution managed by the OS and works pretty much like your standard POSIX thread. In the runtime code, it’s called M for machine.

The circle represents a goroutine. It includes the stack, the instruction pointer and other information important for scheduling goroutines, like any channel it might be blocked on. In the runtime code, it’s called a G.

The rectangle represents a context for scheduling. You can look at it as a localized version of the scheduler which runs Go code on a single thread. It’s the important part that lets us go from a N:1 scheduler to a M:N scheduler. In the runtime code, it’s called P for processor. More on this part in a bit.


Here we see 2 threads (M), each holding a context (P), each running a goroutine (G). In order to run goroutines, a thread must hold a context.

The number of contexts is set on startup to the value of the GOMAXPROCS environment variable or through the runtime function GOMAXPROCS(). Normally this doesn’t change during execution of your program. The fact that the number of contexts is fixed means that only GOMAXPROCS are running Go code at any point. We can use that to tune the invocation of the Go process to the individual computer, such at a 4 core PC is running Go code on 4 threads.

The greyed out goroutines are not running, but ready to be scheduled. They’re arranged in lists called runqueues. Goroutines are added to the end of a runqueue whenever a goroutine executes a go statement. Once a context has run a goroutine until a scheduling point, it pops a goroutine off its runqueue, sets stack and instruction pointer and begins running the goroutine.

To bring down mutex contention, each context has its own local runqueue. A previous version of the Go scheduler only had a global runqueue with a mutex protecting it. Threads were often blocked waiting for the mutex to unlocked. This got really bad when you had 32 core machines that you wanted to squeeze as much performance out of as possible.

The scheduler keeps on scheduling in this steady state as long as all contexts have goroutines to run. However, there are a couple of scenarios that can change that.

Who you gonna (sys)call?

You might wonder now, why have contexts at all? Can’t we just put the runqueues on the threads and get rid of contexts? Not really. The reason we have contexts is so that we can hand them off to other threads if the running thread needs to block for some reason.

An example of when we need to block, is when we call into a syscall. Since a thread cannot both be executing code and be blocked on a syscall, we need to hand off the context so it can keep scheduling.


Here we see a thread giving up its context so that another thread can run it. The scheduler makes sure there are enough threads to run all contexts. M1 in the illustration above might be created just for the purpose of handling this syscall or it could come from a thread cache. The syscalling thread will hold on to the goroutine that made the syscall since it’s technically still executing, albeit blocked in the OS.

When the syscall returns, the thread must try and get a context in order to run the returning goroutine. The normal mode of operation is to steal a context from one of the other threads. If it can’t steal one, it will put the goroutine on a global runqueue, put itself on the thread cache and go to sleep.

The global runqueue is a runqueue that contexts pull from when they run out of their local runqueue. Contexts also periodically check the global runqueue for goroutines. Otherwise the goroutines on global runqueue could end up never running because of starvation.

This handling of syscalls is why Go programs run with multiple threads, even when GOMAXPROCS is 1. The runtime uses goroutines that call syscalls, leaving threads behind.

Stealing work

Another way that the steady state of the system can change is when a context runs out of goroutines to schedule to. This can happen if the amount of work on the contexts’ runqueues is unbalanced. This can cause a context to end up exhausting it’s runqueue while there is still work to be done in the system. To keep running Go code, a context can take goroutines out of the global runqueue but if there are no goroutines in it, it’ll have to get them from somewhere else.


hat somewhere is the other contexts. When a context runs out, it will try to steal about half of the runqueue from another context. This makes sure there is always work to do on each of the contexts, which in turn makes sure that all threads are working at their maximum capacity.

Where to go?

There are many more details to the scheduler, like cgo threads, the LockOSThread()function and integration with the network poller. These are outside the scope of this post, but still merit study. I might write about these later. There are certainly plenty of interesting constructions to be found in the Go runtime library.

原文链接

By Daniel Morsing

https://morsmachine.dk/go-scheduler

编程语言►Golang

怎么使用context

简介

context库是go 1.7中加入的，本篇文章主要是讲解如何正确的使用它。

缘起

一切有为法，让我们先来看看golang里加入context的缘由。

在一个go实现的服务器程序中，通常我们对每个请求使用一个goroutine来进行处理。在请求处理里，我们还有可能启动新的goroutine来访问一些后台程序，如进行数据库操作或发起RPC请求。这些处理这个请求相关的goroutines,经常需要访问与当前请求相关的信息，如用户ID，认证token,请求的截止时间等等。当请求被取消或者超时的时候，所有处理这个请求的goroutines都应该尽快退出，这样才能够对相关的资源进行快速地回收。

因此，在Google内部，开发了一个context包，用于把请求相关的值，取消信号，API截止日期等信息在所有处理这个请求相关的goroutines里进行方便地传递。这个包最终也发布到了go 1.7里.

如露亦如电

我们再来详细地了解一下context的接口。

context包的核心就是context接口.下面是从源码包里摘录的其核心部分。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// A Context carries a deadline, cancelation signal, and request-scoped values
// across API boundaries. Its methods are safe for simultaneous use by multiple
// goroutines.
type Context interface {
    // Done returns a channel that is closed when this Context is canceled
    // or times out.
    Done() <-chan struct{}

    // Err indicates why this context was canceled, after the Done channel
    // is closed.
    Err() error

    // Deadline returns the time when this Context will be canceled, if any.
    Deadline() (deadline time.Time, ok bool)

    // Value returns the value associated with key or nil if none.
    Value(key interface{}) interface{}
}

  • Done:这个方法返回一个只读的通道,这个通道可以被运行在当前context上的函数当作一个取消信号使用:当这个通道被关闭后，正在处理的函数应该终止操作并返回。

  • Err:Err方法返回一个错误信息用来说明context被取消的原因。

细心的你可能发现了Context没有Cancel方法，这是为什么呢？这和Done方法只返回了一个只读通道的原因是一样的:接收到取消信号的函数通常不会是发送取消信号的函数（isn’t it?).尤其是当父操作启动goroutines来处理子操作时，这些子操作不应该能够取消父操作.

  • WithCancel函数提供了取消一个新创建的Context的方法.

  • Context对于并发的多个goroutines是安全的。在代码里，我们可以将一个context传递给任意数量的goroutines然后取消Context并通知所有的gourintes.

  • Deadline:方法允许函数来判断它们是否应该启动;如果可用的时间不多了，可能就没必要干活了。在代码里，我们还可以利用deadline来对I/O操作设置超时。

  • Value方法允许Context设置请求范围内的值。这个数据应该能够被并发的多个goroutines安全地访问.

从Context继承

context包提供用来从已有的context继承产生出新的Context的函数。这些值构成了一棵树:当一个Context取消时，所有从其继承衍生出来的Contextx也被取消.

  • Background是Context树的根，它从来不会被取消.

下面是源码包里的描述:

1
2
3
4
// Background returns an empty Context. It is never canceled, has no deadline,
// and has no values. Background is typically used in main, init, and tests,
// and as the top-level Context for incoming requests.
func Background() Context
  • WithCancel和WithTimeout返回衍生出的Context值,可以在父Context之前被取消.当请求处理函数返回时，与这个请求相关的Context就被取消了.WithCancel对于需要取消使用多个副本处理冗余请求的场景也十分有用.WithTimeout用于为访问后端服务的请求设置deadline.

下面是源码包里的相关描述:

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
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
// WithCancel returns a copy of parent whose Done channel is closed as soon as
// parent.Done is closed or cancel is called.
func WithCancel(parent Context) (ctx Context, cancel CancelFunc)

// A CancelFunc cancels a Context.
type CancelFunc func()

// WithTimeout returns a copy of parent whose Done channel is closed as soon as
// parent.Done is closed, cancel is called, or timeout elapses. The new
// Context's Deadline is the sooner of now+timeout and the parent's deadline, if
// any. If the timer is still running, the cancel function releases its
// resources.
func WithTimeout(parent Context, timeout time.Duration) (Context, CancelFunc)

`WithValue`用于将一个请求范围相关的值设置到Context.

下面是源码包里的描述:

// WithValue returns a copy of parent whose Value method returns val for key.
func WithValue(parent Context, key interface{}, val interface{}) Context

## 实战

说了这么多道理，还是来个实际的例子理解起来容易。

我们实现一个HTTP服务程序，这个程序处理  `/search?q=golang&timeout=1s` 这个的URL。这个URL查询"golang"关键字的相关信息，超时时间是1s.我们将这个请求转给Google查询API处理，并对查询结果进行一些渲染工作。

我们的代码由以下3部分组成:

*   [server](https://blog.golang.org/context/server/server.go)提供了`main函数实现并处理/search URL.`
*   [userip](https://blog.golang.org/context/userip/userip.go) 提供了解析用户IP并将其关联到Context的功能.
*   [google](https://blog.golang.org/context/google/google.go) 提供了Search函数用于将请求发送给Google处理.

### server实现

server程序处理像`/search?q=golang`这样的url请求.我们注册handleSearch函数用于处理/search这个url.这个handler会创建一个初始的Context的名为ctx,并会在处理结束时调用cancel.如果请求URL里有timeout参数，Context会在超时时自动取消:.

下面是具体的代码：

func handleSearch(w http.ResponseWriter, req *http.Request) {
    // ctx是这个handler使用的Context.调用cancel来关闭ctx.Done channel,这个handler发起的所有操作都会收到取消信号.
    var (
        ctx    context.Context
        cancel context.CancelFunc
    )
    timeout, err := time.ParseDuration(req.FormValue("timeout"))
    if err == nil {
        // 请求里有timeout,因此创建一个有超时时间的context.
        ctx, cancel = context.WithTimeout(context.Background(), timeout)
    } else {
        ctx, cancel = context.WithCancel(context.Background())
    }
    defer cancel() // 函数返回里调用cancel().

handler会使用userip包里提供的函数从请求里取出用户IP并设置到context里，后面的请求会使用这个ip.

// 检查是否携带查询参数.
    query := req.FormValue("q")
    if query == "" {
        http.Error(w, "no query", http.StatusBadRequest)
        return
    }

    // 使用userip包里的函数取出userIP,并存储到ctx里.
    userIP, err := userip.FromRequest(req)
    if err != nil {
        http.Error(w, err.Error(), http.StatusBadRequest)
        return
    }
    ctx = userip.NewContext(ctx, userIP)

然后调用Google api进行查询.

// 调用google api进行查询.
    start := time.Now()
    results, err := google.Search(ctx, query)
    elapsed := time.Since(start)

查询成功,处理结果.

 if err := resultsTemplate.Execute(w, struct {
        Results          google.Results
        Timeout, Elapsed time.Duration
    }{
        Results: results,
        Timeout: timeout,
        Elapsed: elapsed,
    }); err != nil {
        log.Print(err)
        return
    }

### userip实现

userip包提供了解析用户IP的功能.Context提供了一个key-value map.key和value都是interface{}类型.key必须支持相等判断,values必须能够安全地并多个goroutines并发访问.userip包隐藏了这个map的细节,并提供了对Context值的强类型访问.

为了避免冲突,userip定义了未导出的key类型.

// key类型没有导出,为了防止和其它包里定义的context keys冲突.
type key int

// userIPkey是用户IP的key,它的值是0.如果要定义其它的context keys,需要使用不同的值.
const userIPKey key = 0

*   `FromRequest`从http.Request里解析userIP.

func FromRequest(req *http.Request) (net.IP, error) {
    ip, _, err := net.SplitHostPort(req.RemoteAddr)
    if err != nil {
        return nil, fmt.Errorf("userip: %q is not IP:port", req.RemoteAddr)
    }

*   `NewContext`返回一个设置了userIP的新Context:

func NewContext(ctx context.Context, userIP net.IP) context.Context {
    return context.WithValue(ctx, userIPKey, userIP)
}

*   `FromContext`从Context里获取userIP:

func FromContext(ctx context.Context) (net.IP, bool) {
    // ctx.Value对于不存在的key返回nil.
net.IP断言对于nil返回的ok=false.
    userIP, ok := ctx.Value(userIPKey).(net.IP)
    return userIP, ok
}

### google包

gooe.Search函数创建一个使用Google Web Search API的HTTP请求,并解析返回的JSON结果.它接受一个Context参数并在ctx.Done关闭时直接返回。

Google Web Search API需要使用user IP作为查询参数.

func Search(ctx context.Context, query string) (Results, error) {
    // 准备Google API请求.
    req, err := http.NewRequest("GET", "https://ajax.googleapis.com/ajax/services/search/web?v=1.0", nil)
    if err != nil {
        return nil, err
    }
    q := req.URL.Query()
    q.Set("q", query)

    // 从ctx里解析user IP并使用.
    if userIP, ok := userip.FromContext(ctx); ok {
        q.Set("userip", userIP.String())
    }
    req.URL.RawQuery = q.Encode()

*   Search使用了httpDo这个帮助函数用于提交http请求,并在ctx.Done时取消正在进行的处理.Search向httpDo传递了一个闭包函数用于处理HTTP响应:

 var results Results
    err = httpDo(ctx, req, func(resp *http.Response, err error) error {
        if err != nil {
            return err
        }
        defer resp.Body.Close()

        // Parse the JSON search result.
        // https://developers.google.com/web-search/docs/#fonje
        var data struct {
            ResponseData struct {
                Results []struct {
                    TitleNoFormatting string
                    URL               string
                }
            }
        }
        if err := json.NewDecoder(resp.Body).Decode(&data); err != nil {
            return err
        }
        for _, res := range data.ResponseData.Results {
            results = append(results, Result{Title: res.TitleNoFormatting, URL: res.URL})
        }
        return nil
    })
    
    return results, err

*   `httpDo`函数在一个新的goroutine里发起HTTP请求并处理响应.如果在goroutine退出之前ctx.Done则取消请求。

func httpDo(ctx context.Context, req *http.Request, f func(*http.Response, error) error) error {
    // 在一个goroutine里处理HTTP请求并将响应交给f处理.
    c := make(chan error, 1)
    req = req.WithContext(ctx)
    go func() { c <- f(http.DefaultClient.Do(req)) }()
    select {
    case <-ctx.Done():
        <-c // 等待f返回.
        return ctx.Err()
    case err := <-c:
        return err
    }
}

希望通过上面的例子，你能够理解并正确地使用Context包.

总结

在Google内部,要求Go程序员将Context作为请求和响应路径上所有函数的第一个参数.这样不同小组的程序员能够良好的合作在一起.这提供了一种简单的控制超时和取消的机制,并能够保证证书这种关键信息能够在程序里正确地传递.

希望使用Context这种机制的服务框架应该提供Context的实现，

用于在它们的包和那些使用Context参数的包之间建立一座桥梁.它们提供的库能够从调用代码里接受Context,这样就能够在请求相关的数据和取消上建立一种通用的接口。Context使包开发者能够更容易的共享代码来创建可伸缩的服务.

协议►HTTP2详解

HTTP/2简介

HTTP/2 可以让我们的应用更快、更简单、更稳定 - 这几词凑到一块是很罕见的！HTTP/2 将很多以前我们在应用中针对 HTTP/1.1 想出来的“歪招儿”一笔勾销，把解决那些问题的方案内置在了传输层中。 不仅如此，它还为我们进一步优化应用和提升性能提供了全新的机会！

HTTP/2 的主要目标是通过支持完整的请求与响应复用来减少延迟，通过有效压缩 HTTP 标头字段将协议开销降至最低，同时增加对请求优先级和服务器推送的支持。 为达成这些目标，HTTP/2 还给我们带来了大量其他协议层面的辅助实现，例如新的流控制、错误处理和升级机制。上述几种机制虽然不是全部，但却是最重要的，每一位网络开发者都应该理解并在自己的应用中加以利用。

HTTP/2 没有改动 HTTP 的应用语义。 HTTP 方法、状态代码、URI 和标头字段等核心概念一如往常。 不过，HTTP/2 修改了数据格式化（分帧）以及在客户端与服务器间传输的方式。这两点统帅全局，通过新的分帧层向我们的应用隐藏了所有复杂性。 因此，所有现有的应用都可以不必修改而在新协议下运行。

为什么不是 HTTP/1.2？

为了实现 HTTP 工作组设定的性能目标，HTTP/2 引入了一个新的二进制分帧层，该层无法与之前的 HTTP/1.x 服务器和客户端向后兼容，因此协议的主版本提升到 HTTP/2。

即便如此，除非您在实现网络服务器（或自定义客户端），需要使用原始的 TCP 套接字，否则您很可能注意不到任何区别：所有新的低级分帧由客户端和服务器为您执行。 可观察到的唯一区别将是性能的提升和请求优先级、流控制与服务器推送等新功能的出现。

SPDY 与 HTTP/2 简史

SPDY 是 Google 开发的一个实验性协议，于 2009 年年中发布，其主要目标是通过解决 HTTP/1.1 中广为人知的一些性能限制来减少网页的加载延迟。具体来说，这个项目设定的目标如下：

  • 页面加载时间 (PLT) 减少 50%。
  • 无需网站作者修改任何内容。
  • 将部署复杂性降至最低，无需变更网络基础设施。
  • 与开源社区合作开发此新协议。
  • 收集真实性能数据，验证实验性协议是否有效。

注：为了达到减少 50% 页面加载时间的目标，SPDY 引入一个新的二进制分帧层，以实现请求和响应复用、优先级和标头压缩，目的是更有效地利用底层 TCP 连接；请参阅延迟是性能瓶颈。

首次发布后不久，Google 的两位软件工程师 Mike Belshe 和 Roberto Peon 就分享了他们对这个新实验性 SPDY 协议的实现结果、文档和源代码：

目前为止，我们只在实验室条件下测试过 SPDY。 最初的成果 很激动人心：通过模拟的家庭网络 连接下载了 25 个最流行的网站之后，我们发现性能的提升特别明显，页面 加载速度最高加快了 55%。 （Chromium 博客）

到了 2012 年，这个新的实验性协议得到 Chrome、Firefox 和 Opera 的支持，而且越来越多的大型网站（如 Google、Twitter、Facebook）和小型网站开始在其基础设施内部署 SPDY。 事实上，在被行业越来越多的采用之后，SPDY 已经具备了成为一个标准的条件。

观察到这一趋势后，HTTP 工作组 (HTTP-WG) 将这一工作提上议事日程，吸取 SPDY 的经验教训，并在此基础上制定了官方“HTTP/2”标准。 在拟定宣言草案、向社会征集 HTTP/2 建议并经过内部讨论之后，HTTP-WG 决定将 SPDY 规范作为新 HTTP/2 协议的基础。

在接下来几年中，SPDY 和 HTTP/2 继续共同演化，其中 SPDY 作为实验性分支，用于为 HTTP/2 标准测试新功能和建议。 理论不一定适合实践（反之亦然），SPDY 提供一个测试和评估路线，可以对要纳入 HTTP/2 标准中的每条建议进行测试和评估。 最终，这个过程持续了三年，期间产生了十余个中间草案：

  • 2012 年 3 月：征集 HTTP/2 建议
  • 2012 年 11 月：第一个 HTTP/2 草案（基于 SPDY）
  • 2014 年 8 月：HTTP/2 草案 17 和 HPACK 草案 12 发布
  • 2014 年 8 月：工作组最后一次征集 HTTP/2 建议
  • 2015 年 2 月：IESG 批准 HTTP/2 和 HPACK 草案
  • 2015 年 5 月：RFC 7540 (HTTP/2) 和 RFC 7541 (HPACK) 发布

2015 年初，IESG 审阅了新的 HTTP/2 标准并批准发布。 之后不久，Google Chrome 团队公布了他们为 TLS 弃用 SPDY 和 NPN 扩展的时间表：

与 HTTP/1.1 相比，HTTP/2 的主要变化在于性能提升。 > 一些主要功能（例如复用、标头压缩、优先级和协议协商）演化自之前开放但不标准的协议 (SPDY)。 Chrome 自 Chrome 6 开始就支持 SPDY，但由于大部分优点都集中在 HTTP/2 中，是时候向 SPDY 说再见了。 我们计划于 2016 年初停止对 SPDY 的支持，还会停止对 TLS 的 NPN 扩展的支持，转而在 Chrome 中使用 ALPN。

强烈建议服务器开发者迁移到 HTTP/2 和 ALPN。 我们很高兴参与到最终催生了 HTTP/2 的开放式标准的制定过程，并且考虑到整个行业在标准化和实现过程中的参与热情，我们希望对这一标准的采纳越来越多。 （Chromium> 博客）

SPDY 与 HTTP/2 的共同演化让服务器、浏览器和网站开发者可以在新协议制定过程中获得真实体验。 因此，HTTP/2 标准自诞生之日起就成为最好并经过大量测试的标准之一。 到 HTTP/2 被 IESG 批准时，已经有很多经过完全测试并且可以立即投入生产的客户端与服务器。 事实上，在最终协议被批准的几周后，由于多款热门浏览器（和许多网站）都部署了完整的 HTTP/2 支持，大量用户都体会到了新协议的好处。

设计和技术目标

早期版本的 HTTP 协议的设计初衷主要是实现要简单： HTTP/0.9 只用一行协议就启动了万维网；HTTP/1.0 则是对流行的 HTTP/0.9 扩展的一个正式说明；HTTP 1.1 则是 IETF 的一份官方标准；请参阅 HTTP 简史。 因此，HTTP/0.9-1.x 实现了其目的：HTTP 是应用最广泛、采用最多的一个互联网应用协议。

然而，实现简单是以牺牲应用性能为代价的： HTTP/1.x 客户端需要使用多个连接才能实现并发和缩短延迟；HTTP/1.x 不会压缩请求和响应标头，从而导致不必要的网络流量；HTTP/1.x 不支持有效的资源优先级，致使底层 TCP 连接的利用率低下；等等。

这些限制并不是致命的，但是随着网络应用的范围、复杂性以及在我们日常生活中的重要性不断增大，它们对网络开发者和用户都造成了巨大负担，而这正是 HTTP/2 要致力于解决的：

HTTP/2 通过支持标头字段压缩和在同一连接上 进行多个并发交换，让应用更有效地利用网络资源，减少 感知的延迟时间。具体来说，它可以对同一连接上的请求和响应消息进行交错 发送并为 HTTP 标头字段使用 有效编码。 > HTTP/2 还允许为请求设置优先级，让更重要的请求更快速地完成，从而进一步 提升性能。

出台的协议更有利于网络，因为与 HTTP/1.x 相比，可以使用更少的 TCP 连接。 > 这意味着与其他流的竞争减小，并且连接的持续时间变长，这些特性反过来提高 了可用网络容量的利用率。 最后，HTTP/2 还可以通过使用二进制消息分帧对消息进行更高效 的处理。 （超文本传输协议版本 2，草案 17）

需要注意的是，HTTP/2 仍是对之前 HTTP 标准的扩展，而非替代。 HTTP 的应用语义不变，提供的功能不变，HTTP 方法、状态代码、URI 和标头字段等这些核心概念也不变。 这些方面的变化都不在 HTTP/2 考虑之列。 虽然高级 API 保持不变，仍有必要了解低级变更如何解决了之前协议的性能限制。 我们来简单了解一下二进制分帧层及其功能。

二进制分帧层

HTTP/2 所有性能增强的核心在于新的二进制分帧层，它定义了如何封装 HTTP 消息并在客户端与服务器之间传输。

HTTP/2 二进制分帧层

这里所谓的“层”，指的是位于套接字接口与应用可见的高级 HTTP API 之间一个经过优化的新编码机制：HTTP 的语义（包括各种动词、方法、标头）都不受影响，不同的是传输期间对它们的编码方式变了。 HTTP/1.x 协议以换行符作为纯文本的分隔符，而 HTTP/2 将所有传输的信息分割为更小的消息和帧，并采用二进制格式对它们编码。

这样一来，客户端和服务器为了相互理解，都必须使用新的二进制编码机制：HTTP/1.x 客户端无法理解只支持 HTTP/2 的服务器，反之亦然。 不过不要紧，现有的应用不必担心这些变化，因为客户端和服务器会替我们完成必要的分帧工作。

数据流、消息和帧

新的二进制分帧机制改变了客户端与服务器之间交换数据的方式。 为了说明这个过程，我们需要了解 HTTP/2 的三个概念：

  • _数据流_：已建立的连接内的双向字节流，可以承载一条或多条消息。
  • _消息_：与逻辑请求或响应消息对应的完整的一系列帧。
  • _帧_：HTTP/2 通信的最小单位，每个帧都包含帧头，至少也会标识出当前帧所属的数据流。

这些概念的关系总结如下：

  • 所有通信都在一个 TCP 连接上完成，此连接可以承载任意数量的双向数据流。
  • 每个数据流都有一个唯一的标识符和可选的优先级信息，用于承载双向消息。
  • 每条消息都是一条逻辑 HTTP 消息（例如请求或响应），包含一个或多个帧。
  • 帧是最小的通信单位，承载着特定类型的数据，例如 HTTP 标头、消息负载等等。 来自不同数据流的帧可以交错发送，然后再根据每个帧头的数据流标识符重新组装。

HTTP/2 数据流、消息和帧

简言之，HTTP/2 将 HTTP 协议通信分解为二进制编码帧的交换，这些帧对应着特定数据流中的消息。所有这些都在一个 TCP 连接内复用。 这是 HTTP/2 协议所有其他功能和性能优化的基础。

请求与响应复用

在 HTTP/1.x 中，如果客户端要想发起多个并行请求以提升性能，则必须使用多个 TCP 连接（请参阅使用多个 TCP 连接）。 这是 HTTP/1.x 交付模型的直接结果，该模型可以保证每个连接每次只交付一个响应（响应排队）。 更糟糕的是，这种模型也会导致队首阻塞，从而造成底层 TCP 连接的效率低下。

HTTP/2 中新的二进制分帧层突破了这些限制，实现了完整的请求和响应复用：客户端和服务器可以将 HTTP 消息分解为互不依赖的帧，然后交错发送，最后再在另一端把它们重新组装起来。

一个共享连接内的 HTTP/2 请求和响应复用

快照捕捉了同一个连接内并行的多个数据流。 客户端正在向服务器传输一个 DATA 帧（数据流 5），与此同时，服务器正向客户端交错发送数据流 1 和数据流 3 的一系列帧。因此，一个连接上同时有三个并行数据流。

将 HTTP 消息分解为独立的帧，交错发送，然后在另一端重新组装是 HTTP 2 最重要的一项增强。事实上，这个机制会在整个网络技术栈中引发一系列连锁反应，从而带来巨大的性能提升，让我们可以：

  • 并行交错地发送多个请求，请求之间互不影响。
  • 并行交错地发送多个响应，响应之间互不干扰。
  • 使用一个连接并行发送多个请求和响应。
  • 不必再为绕过 HTTP/1.x 限制而做很多工作（请参阅针对 HTTP/1.x 进行优化，例如级联文件、image sprites 和域名分片。
  • 消除不必要的延迟和提高现有网络容量的利用率，从而减少页面加载时间。
  • 等等…

HTTP/2 中的新二进制分帧层解决了 HTTP/1.x 中存在的队首阻塞问题，也消除了并行处理和发送请求及响应时对多个连接的依赖。 结果，应用速度更快、开发更简单、部署成本更低。

数据流优先级

将 HTTP 消息分解为很多独立的帧之后，我们就可以复用多个数据流中的帧，客户端和服务器交错发送和传输这些帧的顺序就成为关键的性能决定因素。 为了做到这一点，HTTP/2 标准允许每个数据流都有一个关联的权重和依赖关系：

  • 可以向每个数据流分配一个介于 1 至 256 之间的整数。
  • 每个数据流与其他数据流之间可以存在显式依赖关系。

数据流依赖关系和权重的组合让客户端可以构建和传递“优先级树”，表明它倾向于如何接收响应。 反过来，服务器可以使用此信息通过控制 CPU、内存和其他资源的分配设定数据流处理的优先级，在资源数据可用之后，带宽分配可以确保将高优先级响应以最优方式传输至客户端。

HTTP/2 数据流依赖关系和权重

HTTP/2 内的数据流依赖关系通过将另一个数据流的唯一标识符作为父项引用进行声明；如果忽略标识符，相应数据流将依赖于“根数据流”。 声明数据流依赖关系指出，应尽可能先向父数据流分配资源，然后再向其依赖项分配资源。 换句话说，“请先处理和传输响应 D，然后再处理和传输响应 C”。

共享相同父项的数据流（即，同级数据流）应按其权重比例分配资源。 例如，如果数据流 A 的权重为 12，其同级数据流 B 的权重为 4，那么要确定每个数据流应接收的资源比例，请执行以下操作：

  1. 将所有权重求和：4 + 12 = 16
  2. 将每个数据流权重除以总权重：A = 12/16, B = 4/16

因此，数据流 A 应获得四分之三的可用资源，数据流 B 应获得四分之一的可用资源；数据流 B 获得的资源是数据流 A 所获资源的三分之一。

我们来看一下上图中的其他几个操作示例。 从左到右依次为：

  1. 数据流 A 和数据流 B 都没有指定父依赖项，依赖于显式“根数据流”；A 的权重为 12，B 的权重为 4。因此，根据比例权重：数据流 B 获得的资源是 A 所获资源的三分之一。
  2. 数据流 D 依赖于根数据流；C 依赖于 D。 因此，D 应先于 C 获得完整资源分配。 权重不重要，因为 C 的依赖关系拥有更高的优先级。
  3. 数据流 D 应先于 C 获得完整资源分配；C 应先于 A 和 B 获得完整资源分配；数据流 B 获得的资源是 A 所获资源的三分之一。
  4. 数据流 D 应先于 E 和 C 获得完整资源分配；E 和 C 应先于 A 和 B 获得相同的资源分配；A 和 B 应基于其权重获得比例分配。

如上面的示例所示，数据流依赖关系和权重的组合明确表达了资源优先级，这是一种用于提升浏览性能的关键功能，网络中拥有多种资源类型，它们的依赖关系和权重各不相同。 不仅如此，HTTP/2 协议还允许客户端随时更新这些优先级，进一步优化了浏览器性能。 换句话说，我们可以根据用户互动和其他信号更改依赖关系和重新分配权重。

注：数据流依赖关系和权重表示传输优先级，而不是要求，因此不能保证特定的处理或传输顺序。 即，客户端无法强制服务器通过数据流优先级以特定顺序处理数据流。 尽管这看起来违反直觉，但却是一种必要行为。 我们不希望在优先级较高的资源受到阻止时，还阻止服务器处理优先级较低的资源。

每个来源一个连接

有了新的分帧机制后，HTTP/2 不再依赖多个 TCP 连接去并行复用数据流；每个数据流都拆分成很多帧，而这些帧可以交错，还可以分别设定优先级。 因此，所有 HTTP/2 连接都是永久的，而且仅需要每个来源一个连接，随之带来诸多性能优势。

SPDY 和 HTTP/2 的杀手级功能是，可以在一个拥塞受到良好控制的通道上任意进行复用。 这一功能的重要性和良好运行状况让我吃惊。 我喜欢的一个非常不错的指标是连接拆分，这些拆分仅承载一个 HTTP 事务（并因此让该事务承担所有开销）。 对于 HTTP/1，我们 74% 的活动连接仅承载一个事务 - 永久连接并不如我们所有人希望的那般有用。 但是在 HTTP/2 中，这一比例锐减至 25%。 这是在减少开销方面获得的巨大成效。 （HTTP/2 登陆 Firefox，Patrick McManus）

大多数 HTTP 传输都是短暂且急促的，而 TCP 则针对长时间的批量数据传输进行了优化。 通过重用相同的连接，HTTP/2 既可以更有效地利用每个 TCP 连接，也可以显著降低整体协议开销。 不仅如此，使用更少的连接还可以减少占用的内存和处理空间，也可以缩短完整连接路径（即，客户端、可信中介和源服务器之间的路径） 这降低了整体运行成本并提高了网络利用率和容量。 因此，迁移到 HTTP/2 不仅可以减少网络延迟，还有助于提高通量和降低运行成本。

注：连接数量减少对提升 HTTPS 部署的性能来说是一项特别重要的功能：可以减少开销较大的 TLS 连接数、提升会话重用率，以及从整体上减少所需的客户端和服务器资源。

流控制

流控制是一种阻止发送方向接收方发送大量数据的机制，以免超出后者的需求或处理能力：发送方可能非常繁忙、处于较高的负载之下，也可能仅仅希望为特定数据流分配固定量的资源。 例如，客户端可能请求了一个具有较高优先级的大型视频流，但是用户已经暂停视频，客户端现在希望暂停或限制从服务器的传输，以免提取和缓冲不必要的数据。 再比如，一个代理服务器可能具有较快的下游连接和较慢的上游连接，并且也希望调节下游连接传输数据的速度以匹配上游连接的速度来控制其资源利用率；等等。

上述要求会让您想到 TCP 流控制吗？您应当想到这一点；因为问题基本相同（请参阅流控制）。 不过，由于 HTTP/2 数据流在一个 TCP 连接内复用，TCP 流控制既不够精细，也无法提供必要的应用级 API 来调节各个数据流的传输。 为了解决这一问题，HTTP/2 提供了一组简单的构建块，这些构建块允许客户端和服务器实现其自己的数据流和连接级流控制：

  • 流控制具有方向性。 每个接收方都可以根据自身需要选择为每个数据流和整个连接设置任意的窗口大小。
  • 流控制基于信用。 每个接收方都可以公布其初始连接和数据流流控制窗口（以字节为单位），每当发送方发出 DATA 帧时都会减小，在接收方发出 WINDOW_UPDATE 帧时增大。
  • 流控制无法停用。 建立 HTTP/2 连接后，客户端将与服务器交换 SETTINGS 帧，这会在两个方向上设置流控制窗口。 流控制窗口的默认值设为 65,535 字节，但是接收方可以设置一个较大的最大窗口大小（2^31-1 字节），并在接收到任意数据时通过发送 WINDOW_UPDATE 帧来维持这一大小。
  • 流控制为逐跃点控制，而非端到端控制。 即，可信中介可以使用它来控制资源使用，以及基于自身条件和启发式算法实现资源分配机制。

HTTP/2 未指定任何特定算法来实现流控制。 不过，它提供了简单的构建块并推迟了客户端和服务器实现，可以实现自定义策略来调节资源使用和分配，以及实现新传输能力，同时提升网页应用的实际性能和感知性能（请参阅速度、性能和人类感知）。

例如，应用层流控制允许浏览器仅提取一部分特定资源，通过将数据流流控制窗口减小为零来暂停提取，稍后再行恢复。 换句话说，它允许浏览器提取图像预览或首次扫描结果，进行显示并允许其他高优先级提取继续，然后在更关键的资源完成加载后恢复提取。

服务器推送

HTTP/2 新增的另一个强大的新功能是，服务器可以对一个客户端请求发送多个响应。 换句话说，除了对最初请求的响应外，服务器还可以向客户端推送额外资源（图 12-5），而无需客户端明确地请求。

服务器为推送资源发起新数据流 (promise)

注：HTTP/2 打破了严格的请求-响应语义，支持一对多和服务器发起的推送工作流，在浏览器内外开启了全新的互动可能性。 这是一项使能功能，对我们思考协议、协议用途和使用方式具有重要的长期影响。

为什么在浏览器中需要一种此类机制呢？一个典型的网络应用包含多种资源，客户端需要检查服务器提供的文档才能逐个找到它们。 那为什么不让服务器提前推送这些资源，从而减少额外的延迟时间呢？ 服务器已经知道客户端下一步要请求什么资源，这时候服务器推送即可派上用场。

事实上，如果您在网页中内联过 CSS、JavaScript，或者通过数据 URI 内联过其他资产（请参阅资源内联），那么您就已经亲身体验过服务器推送了。 对于将资源手动内联到文档中的过程，我们实际上是在将资源推送给客户端，而不是等待客户端请求。 使用 HTTP/2，我们不仅可以实现相同结果，还会获得其他性能优势。 推送资源可以进行以下处理：

  • 由客户端缓存
  • 在不同页面之间重用
  • 与其他资源一起复用
  • 由服务器设定优先级
  • 被客户端拒绝

PUSH_PROMISE 101

所有服务器推送数据流都由 PUSH_PROMISE 帧发起，表明了服务器向客户端推送所述资源的意图，并且需要先于请求推送资源的响应数据传输。 这种传输顺序非常重要：客户端需要了解服务器打算推送哪些资源，以免为这些资源创建重复请求。 满足此要求的最简单策略是先于父响应（即，DATA 帧）发送所有 PUSH_PROMISE 帧，其中包含所承诺资源的 HTTP 标头。

在客户端接收到 PUSH_PROMISE 帧后，它可以根据自身情况选择拒绝数据流（通过 RST_STREAM 帧）。 （例如，如果资源已经位于缓存中，便可能会发生这种情况。） 这是一个相对于 HTTP/1.x 的重要提升。 相比之下，使用资源内联（一种受欢迎的 HTTP/1.x“优化”）等同于“强制推送”：客户端无法选择拒绝、取消或单独处理内联的资源。

使用 HTTP/2，客户端仍然完全掌控服务器推送的使用方式。 客户端可以限制并行推送的数据流数量；调整初始的流控制窗口以控制在数据流首次打开时推送的数据量；或完全停用服务器推送。 这些优先级在 HTTP/2 连接开始时通过 SETTINGS 帧传输，可能随时更新。

推送的每个资源都是一个数据流，与内嵌资源不同，客户端可以对推送的资源逐一复用、设定优先级和处理。 浏览器强制执行的唯一安全限制是，推送的资源必须符合原点相同这一政策：服务器对所提供内容必须具有权威性。

标头压缩

每个 HTTP 传输都承载一组标头，这些标头说明了传输的资源及其属性。 在 HTTP/1.x 中，此元数据始终以纯文本形式，通常会给每个传输增加 500–800 字节的开销。如果使用 HTTP Cookie，增加的开销有时会达到上千字节。 （请参阅测量和控制协议开销。） 为了减少此开销和提升性能，HTTP/2 使用 HPACK 压缩格式压缩请求和响应标头元数据，这种格式采用两种简单但是强大的技术：

  1. 这种格式支持通过静态霍夫曼代码对传输的标头字段进行编码，从而减小了各个传输的大小。
  2. 这种格式要求客户端和服务器同时维护和更新一个包含之前见过的标头字段的索引列表（换句话说，它可以建立一个共享的压缩上下文），此列表随后会用作参考，对之前传输的值进行有效编码。

利用霍夫曼编码，可以在传输时对各个值进行压缩，而利用之前传输值的索引列表，我们可以通过传输索引值的方式对重复值进行编码，索引值可用于有效查询和重构完整的标头键值对。

HPACK：HTTP/2 的标头压缩

作为一种进一步优化方式，HPACK 压缩上下文包含一个静态表和一个动态表：静态表在规范中定义，并提供了一个包含所有连接都可能使用的常用 HTTP 标头字段（例如，有效标头名称）的列表；动态表最初为空，将根据在特定连接内交换的值进行更新。 因此，为之前未见过的值采用静态 Huffman 编码，并替换每一侧静态表或动态表中已存在值的索引，可以减小每个请求的大小。

注：在 HTTP/2 中，请求和响应标头字段的定义保持不变，仅有一些微小的差异：所有标头字段名称均为小写，请求行现在拆分成各个 :method、:scheme、:authority 和 :path 伪标头字段。

HPACK 的安全性和性能

早期版本的 HTTP/2 和 SPDY 使用 zlib（带有一个自定义字典）压缩所有 HTTP 标头。 这种方式可以将所传输标头数据的大小减小 85% - 88%，显著减少了页面加载时间延迟：

在带宽较低的 DSL 链路中，上行链路速度仅有 375 Kbps，仅压缩请求标头就显著减少了特定网站（即，发出大量资源请求的网站）的页面加载时间。 我们发现，仅仅由于标头压缩，页面加载时间就减少了 45 - 1142 毫秒。 （SPDY 白皮书， chromium.org）

然而，2012 年夏天，出现了针对 TLS 和 SPDY 压缩算法的“犯罪”安全攻击，此攻击会导致会话被劫持。 于是，zlib 压缩算法被 HPACK 替代，后者经过专门设计，可以解决发现的安全问题、实现起来也更高效和简单，当然，可以对 HTTP 标头元数据进行良好压缩。

如需了解有关 HPACK 压缩算法的完整详情，请参阅 IETF HPACK - HTTP/2 的标头压缩。

深入阅读：

注：以上内容节选自《高性能浏览器网络》（出版社：O’Reilly，作者：Ilya Grigorik）。 要了解完整版本和相关内容，请访问 hpbn.co。

原谅链接:

https://developers.google.com/web/fundamentals/performance/http2/?hl=zh-cn

编程语言►Golang

Go语言调度器实现(二)----go scheduler

简介

在上一篇文章里，我介绍了OS调度方面的相关内容，我认为这些内容对理解Go调度器的语义很重要。本篇文章，我将从语义层面会介绍GO调度器是如何工作的，将会重点关注G调度器的高层行为。Go调度器是一个复杂的系统，小的细节是不重要的。重要的是我们要有一个对Go调度器如何工作和其调度行为的好的认知模型。这些有助于我们做出工程上的决策。

启动你的程序

当你的Go程序开始运行，会分配一个逻辑处理器（P)用于执行特定主机上的虚拟代码。如果你有一个支持每个物理核上跑多线程的处理器（超线程技术），每个硬件线程在你的Go程序里都是一个虚拟核。为了更好地理解这些内容，来看一下我的MacBook Pro上的系统报告：


可以看到一个处理器上有4个物理核心，这个报告看不到每个物理核上的硬件线程。i7处理器支持超线程技术，每个物理核上有2个硬件线程。这说明Go程序有8个可用的虚拟核用于并行地执行OS线程。

看下面的程序：

1
2
3
4
5
6
7
8
9
10
11
12
13
package main

import (
"fmt"
"runtime"
)

func main() {

    // NumCPU returns the number of logical
    // CPUs usable by the current process.
    fmt.Println(runtime.NumCPU())
}

在我的机器上运行上面的程序，会输出8.任何一个运行在我机器上的Go程序都会有8个虚拟核P.

每个P被分配一个OS线程(“M”).M代表machine.这个线程仍然被OS管理，仍然由OS负责将其放到某个核上执行，如上篇文章所讲的那样。这意味着，当我运行Go程序时，有8个线程可用于执行我的任务，每个都与一个P关联。

每个GO程序都会分配一个初始的Goroutine(“G”),代表了GO程序的执行路径。一上Goroutine本质上是一个Coroutine,但是是Go语言，因此将”C”替换为”G”.你可以将Goroutines看作是app级别的线程，它们和OS线程有很多相似点。OS线程会在一个cpu核上进行上下文切换，Goroutines会在M上进行上下文切换。

最后一个难点是运行队列。Go调度器有2种不同的运行队列：全局运行队列(GRQ)和本地运行队列 （LRQ）.每个P都有一个本地运行队列用于管理分配给它的Goroutines。这些Goroutines轮流在分配给P的M上进行上下文切换。GRQ用于还没有分配P的Goroutines.有一个专门的程序用于将Goroutines从GRQ移动到LRQ。

下图描述了这些组件之间的关系:


协作调度器

如上一篇文章中所讨论的，OS调度器是可抢占的。这在本质上意味着在任何时刻，你无法预测调度器会做什么。内核做的决定和事件是不确定的。运行在OS之上的应用程序无法控制内核调度器，除非使用原子指令和锁这些同步原语。

Go调度器是Go运行时的一部分，Go运行时与你的程序构建在一直。这意味着Go调度器运行在用户态。现在的Go调度器实现是不可抢占的，而是协作型的调度器。协作调度器意味着调度器需要定义良好的用户空间事件，这些事件需要在安全的时间点触发调度决策。

Go的协作型调度器实现的十分聪明，因为它看起来就像是可抢占的。你无法预测Go调度器将会如何调度。这是因为调度决策没有交给开发者，而是交给了Go的运行时。将Go调度器看成是可抢占的十分重要，因为它是不确定的，这一点并不难理解。

Goroutine状态

和线程类似，Goroutines也有3个状态。

Goroutine的3种状态包括:Waiting, Runnable 或者_Executing_.

Waiting: 意味着Goroutine因为要等待一些事件而停止。可能包括等待系统调用，同步调用（原子操作和锁操作）。这些类型的延迟是性能差的根源。

Runnable: 这意味着Goroutine希望在M上获取运行时间来执行指令。如果同时有很多Goroutines，每个Goroutine需要等待更长的时间，同样地，每个Goroutine获得时间就会减少。这种调度延迟也会造成性能较差。

Executing: 这意味着Goroutine已经在M上执行指令。这是每个人都希望的状态。

上下文切换

Go调度器需要定义良好的用户空间事件来在安全的时机进行上下文切勿。这些事件和安全的时机以函数调用的方式提供。函数调用对Go调度器的健康至关重要。现在（Go1.11和以前的版本中），如果你运行紧凑地循环代码而不进行这些函数调用，那么调度和垃圾回收就会产生延迟。在合适的时机调用这些函数是十分重要的。

注意: 1.12版本已经接受了go调度器实现抢占的建议，这样就能够抢占长时间的循环.

有4类事件会使go调度器进行调度决策。这并不意味着一定会发生新的调度，而是给调度器提供了调度的机会.

  • 使用go关键字
  • 垃圾回收
  • 系统调用
  • 同步和编排

使用go关键字

go关键字能够创建Goroutines. 一旦创建了新的Goroutine,调度器就有机会进行调度决策.

垃圾回收

由于GC使用自己的Goroutines运行，这些gorutines需要在M上获得执行时间.这会对调度产生影响。幸好，调度器非常聪明，它对Goroutine正在进行的工作十分了解能够做出聪明的决定。一个例子是：在GC期间，调度器调度那些不需要访问堆的goroutine，而将那些访问堆的goroutine切换出去。当运行GC时，会做出许多调度决策。

系统调用

如果一个Goroutine进行了一个会阻塞M的系统调用，有些时候调度器能够将其切出M并调度一个新的Goroutine。但是，有时候需要一个新的M来运行Goroutines并将其加入P的队列之中，这是如何工作的细节下一节将会详细介绍.

同步和编排

原子操作，锁，channel操作会引起Goroutine阻塞，调度器可以切换一个新Goroutine运行。当Goroutine双可以继续运行时，会被重新放入运行队列并最终切换回M运行。

异步系统调用

如果你的OS支持异步系统调用，比如网络poller,它可以更高效地处理系统调用。这是通过kqueue(MacOS),epoll(Linux),iocp(Windows)实现的。

现今的许多OS都支持异步的处理网络相关的系统调用。这也是network poller名字的由来，因为它最初产生是为了处理网络操作。通过使用network poller相关的系统调用，调度器能够防止Goroutines阻塞当前M。

这有助于M继续执行P的LRQ上的其它Goroutines，而不需要创建新的M。这能够降低OS的调度负荷。

下面的图很好的说明了上述情况：


上图中，G1正在M上运行，它想进行一次网络调用。

下图中，G1加入net poller中进行异步调用。M这时可以执行LRQ的另一个G2。当异步调用完成时，G1又放入P的LRQ之中。这是一个巨大的成功，因为不需要创建额外的M。net poller有专门的OS线程处理而且十分高效。


同步系统调用

当Goroutine进行不能进行异步处理的系统调用时会发生什么？这时，进行系统调用的Goroutine将会阻塞M，不幸地是没有办法阻止这种情况的发生。一种可以进行异步调用的系统调用是文件操作。如果你在使用CGO，那么有可能会因调用其它C函数而造成M阻塞。

注意: Windows没有提供异步读写文件的能力.当在Windows上运行时,可以net poller.

下面我们就来看一看如果进行同步调用(比如文件I/O)造成M阻塞的情况。


上图中G1将要进行同步调用。


在上图中，调用器将识别出G1将会造成M阻塞。这时，调度器将M1与P分离，G1仍然关联在M1上。然后调度器使用一个新的M2为P服务。G2被从P的LRQ中选出并切换到M2上运行。如果因为之前类似的情况已经有一个M存在，上面这种切换会更快，因为不需要新创建一个M.


如下图所示,G1完成了系统调用.这时，G1被移回P的LRQ继续由P服务。M1继续在一旁保留着用于将来再次发生类似情况时使用.

工作窃取

在另一方面，调度器还是一个工作窃取型的调度器。这能够在某些情况下保持调度的高效。比如，上面讲的M进入等待状态时，OS将会将M切换出当前核。这意味着即使还有可以运行的Goroutine,P也不能够进行任何工作，直到M切换回某个核。工作窃取能够在P之间平衡Goroutines，这样工作能够有较好的分派进而更高效的完成。

我们通过下面的图来看一下:


在上图中，我们有一个多线程程序，有2个P，每个P为4个Goroutines服务。还有一个GRQ在执行一个Groutine,如果有一个P工作较快，那么会发生什么？


在上图中，P1已经没有可运行的Goroutines了，而P2和GRQ上还有。这时，P1需要进行工作窃取。工作窃取的原则如下:

1
2
3
4
5
6
7
8
runtime.schedule() {
    // 只有1/61的时间从全局队列上查找一个G.
    // 如果没有找到,检查本地队列.
    // 如果还没有找到,
    //    尝试从其它P窃取.
    //     如果还没有,检查全局队列.
    //     如果仍然没有,poll network.
}

基于上述原则,P1将会从P2中窃取G,并窃取一半的可运行G.如下图所示:


如果这时P2工作完成，P1的LRQ上也没有G了，那么P2会怎么做？



如上图所示，P2会从GRQ上取走G9并执行。可以看出，窃取工作能够使M始终处于工作状态。

实际的例子

通过上面介绍的机制和语义，我想向你展示这些是如何作用在一起来使GO调度器执行更多的任务。假设现在有一个用C写的多线程的程序，它管理着2个OS线程并来回传递消息。


如上图所示，线程T1在核C1上运行并发送消息给T2.


当T1发送完消息以后，它需要等待T2的回应。这会使T1从核C1上切出并进入等待状态。一旦T2接收到消息通知，它进入可运行状态。现在OS执行一次上下文切换并在核C2上执行T2。接下来，T2处理完消息并向T1返回一个消息.


当T1接收到消息后，会再次进行上下文切换。现在T2进入等待状态，T1从等待状态进入可运行状态并最终执行，T1继续处理消息并发送新的消息.

所有这些上下文切换和状态变化需要时间，这限制了任务快速的完成。每次上下文切换都可能有约1000ns的延迟，通常硬件每ns执行12条指令，这就造成在上下文切换期间浪费了12K指令的执行。再加上这些线程绑定到不同的核上，缓存行失效问题也会造成额外的延迟。

让我们再来看看使用Goroutines的Go调度器如何处理这个例子:


如上图所示,有2个Goroutines用来相互发送消息.G1在M1上运行，发生在核C1上。

G1发送消息给G2.


G1发送完消息后，等待回应。G1从M1上切出并进入等待状态。G2接收到消息通知并进入可运行状态。这时Go调度器执行一次上下文切换在M1上执行G2，同样运行在核C1上。接下来，G2处理消息并向G1返回响应.


G1接收到G2的响应后，G2切出并进入等待状态。G1最终执行起来并发送响应.

所有这些事情从表面上看和多线程里没有任何不同。Goroutines上同样存在上下文切换和状态变化问题。但是，使用线程和Goroutines有一个主要的不同可能第一眼不易察觉。

使用Goroutines的场景，用一个OS线程和CPU核就处理了所有的事情。这就意味着，从OS的角度看，OS线程从来没有进入过等待状态。而且不止一次的，我们在上下文切换期间(Go调度器切换代价小的多)没有丢失指令执行的机会。

本质上，Go在OS层面上将I/O阻塞型任务转变为CPU密集型任务。由于这些上下文切换都发生在用户态，因此我们没有像使用线程时那样在每次上下文切换中损失12k指令（平均）。在Go里，同样的上下文切换花费约200ns或者说2.4指令。Go调度器还有助于提升缓存命中和NUMA.这也是为什么我们不需要大于虚拟核数量的线程。在Go里，同样的时间可能完成更多的任务，这是因为Go调度器尝试减少线程数量，并让每个线程干更多的活，这能够减少OS和硬件的负担。

总结

Go调度器在设计时考虑到了OS和硬件的工作方式，这很令人惊奇。

将I/O阻塞型工作转换为CPU密集型工作的能力使我们在利用多CPU上取得了巨大的胜利。这也是我们不需要大于虚拟CPU数量的线程个数的原因。你有理由相信你的所有工作（无论CPU密集还是IO密集）可以在每个VC(虚拟核)一个线程的情况下完成。这对于网络和其它不需要阻塞线程的系统调用的应用来说是有可能的。

作为一个开发者，你还是需要了解你的程序需要处理的工作类型。你不能创建无限多的Goroutines并期待高性能。少即是多仍然适用，但是了解了Go调度器的这些语义，你可以做出更好的工程决策。

在下一篇文章里，我将以保守的方式来展示如何利用并发性来获得更好的性能，同时平衡你可能向代码里添加进的复杂性。

编程语言►Golang

go语言调度器实现(一)---os调度

go语言最大的卖点在于并发编程,尤其是现在免费的午餐已经结束,这意味着要挖掘硬件的高性能,软件越来越重要.

而易于编写并发程序的go语言,调度器的实现是一关键因素.因此本系列文章希望探索go语言的调度器实现.

将分3篇文章进行讲述,分别是OS调度器,GO调度器以及如何进行并发编程.

介绍

Go调度器的设计和行为能够让Go多线程程序的编写更加高效和具有更高的性能。这要得益于Go调度器的设计深谙OS调度器的工作机制。即使你不了解这些调度机制，对于你设计的Go多线程程序也没有影响，但是，对OS和Go调度器，以及如何编写多线程程序有一个全面和深刻和理解，是十分重要的。

这3篇文章将会关注调度器高层次的工作机制和语义。将通过展示足够的细节让你看到事情是如何进行的，进而让你在设计程序时能够做出更好的决定。尽管在设计多线程程序时你需要做出许多工程上的抉择，但底层的工作机制和语义是基础的关键部分。

OS调度器

操作系统调度器是很复杂的软件模块。它必须考虑其运行的硬件布局和设置。包括多处理器和多核心，CPU缓存和NUMA等等。不了解这些内容，调度器不可能设计的高效。即使你不深入地了解这些主题，你也可以对OS调度器模型有一个好的了解。

你的程序是一系列需要顺序执行的指令。为了执行这些指令，OS使用了线程这个概念。顺序执行分配给它的指令是线程的任务。线程执行指令直到没有更多的指令为止。因此也可以将线程看作“执行的一条路径”。

你运行的每个程序创建一个进程，每个进程创建一个初始线程。线程有能力创建更多的线程。所有这些线程独立的运行，调度发生在线程级别，而不是进程级别（还记得操作系统课本上讲的吗？线程是系统调度的基本单位）。

线程能够并发执行（每个线程在同一个核上各自运行一段时间），也可以并行执行（每个线程运行在不同的核上）。线程持有它们各自的状态用于安全，独立的执行它们的指令。

OS调度器的职责是确保在有线程需要执行时CPU核心不能够空闲。它也必须让人们感觉到所有要执行的线程都在同时执行，同时调度器需要优先运行高优先级的线程。但是，低优先级的线程也不能被“饿死”。调度器还必须快速和聪明的做出决策以保证最小的延迟。

为了做到上述这些，需要用到很多算法，幸运地是，我们能够利用过去几十年行业的相关工作和经验。为了更好地理解这些内容，我们需要描述和定义一些重要的概念。

执行指令

PC寄存器，有时也称为IP，是用于跟踪线程要执行的下一条指令。在大多数处理器上，PC指向下一条指令而不是当前指令。


如果你看过GO程序的栈，你可能会注意到每行结尾处的十六进制数。比如下面的0x39,0x72.

1
2
3
4
5
goroutine 1 [running]:
   main.example(0xc000042748, 0x2, 0x4, 0x106abae, 0x5, 0xa)
       stack_trace/example1/example1.go:13 +0x39                 <- 看这里
   main.main()
       stack_trace/example1/example1.go:8 +0x72                  <- 看这里

这些数值代表了从当前函数顶PC的偏移量。

+0x39代表example函数里如果没有panic将要执行的下一条指令。

+0x72代表了main函数如果从example函数返回将要执行的下一条指令。更重要的是，前一条指令指出了正在执行的指令。

下面是造成产生这个栈的代码:

1
2
3
4
5
6
7
8
9
https://github.com/ardanlabs/gotraining/blob/master/topics/go/profiling/stack_trace/example1/example1.go

07 func main() {
08     example(make([]string, 2, 4), "hello", 10)
09 }

12 func example(slice []string, str string, i int) {
13    panic("Want stack trace")
14 }

通过objdump查看二进制程序的指令，可以看到下面的第12条指令(最后一条指令)就是距函数头+0x39处的指令。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
$ go tool objdump -S -s "main.example" ./example1
TEXT main.example(SB) stack_trace/example1/example1.go
func example(slice []string, str string, i int) {
  0x104dfa065488b0c2530000000MOVQ GS:0x30, CX
  0x104dfa9483b6110CMPQ 0x10(CX), SP
  0x104dfad762cJBE 0x104dfdb
  0x104dfaf4883ec18SUBQ $0x18, SP
  0x104dfb348896c2410MOVQ BP, 0x10(SP)
  0x104dfb8488d6c2410LEAQ 0x10(SP), BP
panic("Want stack trace")
  0x104dfbd488d059ca20000LEAQ runtime.types+41504(SB), AX
  0x104dfc448890424MOVQ AX, 0(SP)
  0x104dfc8488d05a1870200LEAQ main.statictmp_0(SB), AX
  0x104dfcf4889442408MOVQ AX, 0x8(SP)
  0x104dfd4e8c735fdffCALL runtime.gopanic(SB)
  0x104dfd90f0bUD2              <---这里就是PC(+0x39)

记住：PC是下一条指令，而不是当前的指令。上面的例子是基于amd64架构的GO程序线程的指令序列。

线程状态

另一个重要的概念是线程状态，这是调度器分配给线程的状态。

线程可以处于3种状态：Waiting,Runnable,Executing.

Waiting:线程由于等待一些条件而处于停止状态。比如等待硬件（磁盘，网络），等待系统调用或同步调用（原子操作，锁）。这些类型的延迟是造成低性能的根本原因。

Runnable: 线程期望在某个核上获得CPU时间片以运行分配给它的指令。如果你有许多线程需要获得时间片，线程必须等待更长的时间。同样，当有更多的线程竞争CPU时，每个线程获得的时间片就会减少。这种类型的调度延迟也是造成低性能的原因。

Executing: 这意味着线程已经在某个CPU上执行指令。这是我们都期望的状态。

工作类型

线程有2种类型的工作，一种是CPU密集型，另一种是IO密集型。

CPU密集型: 这种任务从不进入等待状态，处于持续地计算状态，典型的如计算PI值。

IO密集型: 这种任务会导致任务进入等待状态。这种任务通过网络发送请求或通过系统调用陷入内核。需要访问数据库的线程是IO密集型的。另外，需要等待同步事件（锁，原子操作）等的线程也属于这一类。

上下文切换

如果你在Linux,Mac或者Windows上运行程序，那么这些系统的OS是可抢占的。这意味着

  • 调度器选择哪个线程在任何时间运行是不可预知的。线程优先级和事件发生的时机（比如网络数据的达到）使预测调度器的行为更加不可能。

  • 你的代码不能依赖一些经验来预测调度器的行为，因此这不总是能保证的。如果你需要你的程序有确定的行为你需要编排线程并控制线程的同步。

在CPU核上切换另一个线程执行称为“上下文切换”。当调度器将一个正在执行的线程替换为另外一个可运行的线程时发生“上下文切换”。这时从运行队列里选择一个线程并使之处于执行状态。换下来的线程可能被重新放放运行队列（如果它仍然可以继续运行），也可能处于等待状态（因为I/O请求而被替换）。

“上下文切换”是昂贵的，因为这需要耗费CPU时间。“上下文切换”造成的延时是由不同因素决定的，是不可能预知的。但是平均大约需要1000–1500 ns,如果每个CPU核心每ns能够执行12条指令，那么上下文切换会造成12K到18K的指令延迟。根本上，在上下文切换期间你的程序将损失大量指令执行的能力。

如果你的程序是IO密集型的，那么上下文切换是有利的。一旦一个线程处于等待状态，另外一个处于可运行状态的线程可以执行。这可以使CPU始终处于工作状态。这是调度器一方面的任务，不要让CPU处于空闲状态。

如果你的程序是CPU密集型的，那么上下文切换是性能的噩梦。因为线程总是有工作要做，而线程切换打断了线程。这与IO密集型的任务形成了鲜明的对比。

少即是多

早期的CPU只有一个核心，这时的调度器还不十分复杂。因为一个CPU只有一个核心，同时只有一个线程可能执行。调度器需要定义调度周期，在调度周期内需要执行所有处于运行状态的线程。这很简单：将调度周期除以需要执行的线程数量。

举个例子，如果将调度周期定义10ms而你有2个线程，那么每个线程执行5ms.如果你有5个线程，每个线程执行2ms.但是，如果有100个线程呢？简单的给每个线程10us是不行的，因为你在上下文切换上将会消耗大量的时间。

你需要限制时间片的下限。如果最小时间片限制为2ms，那么调度周期就会变为2000ms，也就是2s.如果有1000个线程，调度周期将会变为20s.那么就需要20s才能将所有线程执行一次，假设所有的线程都需要消耗完时间片。

上面的例子只是一个很简化的例子。真实的调度器需要考虑更多的因素。你需要控制程序中使用的线程数量。当有更多的线程和I/O发生时，就会有更多混乱和不确定的行为发生，就需要更长的时间执行调度。

这就是”少即是多”原则。更少的线程意味着更少的调度开销，每个线程获得的运行时间就更多。越多的线程意味着每个线程获得的运行时间越少，也就意味着你的任务需要更多的时间才能完成。

找到平衡

为了使你的应用程序达到最高吞吐量你需要在CPU个数和线程个数之间找到平衡。这时，线程池是一个很好的选择。我将会在第2篇文章中告诉你GO不需要这个了。我认为这是GO为了使多线程编程更容易而做的一件好事。

使用C++和C#在NT系统上进行开发，使用IOCP线程池是开发多线程软件的关键能力。你需要通过CPU个数来给线程池设置合适的最大线程数量。

当编写与数据库打交道的WEB服务器时，在NT系统上每个CPU核3个线程通常是一个最好的选择。换句话说，每个CPU核3个线程能够最小化“上下文切换”带来的延迟，同时保证每个CPU核有最大的执行时间。当创建一个IOCP线程时，通常为每个CPU核设置最小线程数量为1，最大线程数量为3.

如果每个CPU核使用2个线程，那么完成任务需要花费更多的时间，因为CPU有空闲时间。如果每个CPU核使用4个线程，那么完成任务也需要花费更多的时间，因为“上下文切换”带来了更多的延迟。每个CPU核3个线程是一个平衡点，无论是什么原因，在NT系统上3看起来个是“魔术字”。

如果你的服务在做很多不同种类的工作，那应该如何？可能会产生许多不同和不确定的延时，也可能需要处理很多系统级的事件。这种情况下不太可能找到一个合适的魔术字。当使用线程池来提高系统性能时，找到一个合适固定的配置十分困难和复杂。

Cache Lines

从主存访问数据有很高的延迟（大约100300个时钟周期）。处理器用本地缓存来缓存线程所需的数据。从缓存访问数据消耗较低（约340个时钟周期）。如今，如何提高处理器访问数据的效率来减少延迟是性能优化的重要方面。编写拥有可变状态的多线程程序需要考虑缓存系统的相关机制。

下图是i7处理器的缓存系统示意图


主存和处理器之间通过缓存行来交换数据。一个缓存行是64字节的内存块。每个CPU核心都拥有所需缓存行的拷贝。这就是为什么在多线程程序中可变状态是性能的噩梦。

当多个线程并行访问同样的数据时，或者访问相邻的数据时，它们会访问同一个内存行。在任一CPU核心上的任一线程都会获得同样的缓存行拷贝。这就会产生“伪共享”问题。


如果其中一个线程修改了其内存行拷贝，缓存系统会将所有其它核上的相同内存行拷贝标记为“脏”。当另外的线程要读取或写“脏”的缓存行时，就需要访问主存获取新的内存行拷贝(参考我之前的文章<<SMP缓存一致性>>.
如果其中一个线程修改了其内存行拷贝，缓存系统会将所有其它核上的相同内存行拷贝标记为“脏”。当另外的线程要读取或写“脏”的缓存行时，就需要访问主存获取新的内存行拷贝(参考我之前的文章<<SMP缓存一致性>>.

如果上述情况只发生在2个CPU核心上可能问题还不大，但是如果运行在32个CPU核心上的32线程并行地访问同样的缓存行呢？这时情况就很糟糕了，因此处理器之间的通信会增加大量的延迟。应用程序会在内存上激烈地冲突，性能可能会很差，同时，你可能都无法理解为什么会这样。

这就是“缓存一致性”问题，还有相关的“伪共享”问题。当编写涉及可变状态的多线程程序时，必须考虑缓存系统。

调度决策场景

相像一下，如果你要基于上述知识涉及一个OS调度器。有一种你必须要考虑的场景。记住，这是调度器做出调度决策时需要考虑的很多有趣的问题的其中之一。

你的程序开始运行，主线程被创建并在核1上运行。线程在执行指令，由于数据访问缓存行被填充并使用。这时线程准备创建一个新线程来处理并发问题。那么，问题来了。

新线程创建成功之后，调度器该如何调度它？

  1. 将主线程切换出核1？这样做有利于性能提升，因为新线程需要访问同样的数据已经在缓存中了。但是主线程的时间片还未消耗完。
  2. 将新线程放到核1的运行队列中等待调度。这样主线程能够用完时间片，新线程所需的数据也在缓存中，但是需要等待。
  3. 挑选另外一个可用的核来运行新线程。这意味着缓存行需要重新建立。但是线程可以尽快的运行，同时主线程也可以运行完自己的时间片。

是不是越来越有趣了？OS调度器再做出调度决策时有很多有趣的问题需要考虑。幸运地是，我们不需要考虑这些。我们要知道的就是，如果有CPU核空闲，就要利用它。

总结

这篇文章告诉了你在写多线程程序时如何从线程和OS调度器的视角来考虑问题。这些问题GO调度器也同样也需要考虑。下一篇将介绍GO调度器所提供的语义，届时会和本篇文章介绍的知识有所关联。最后，你将通过编写一系列程序来实际理解这些知识。

软件工程►git

git对象

git是linus开发的一款版本控制工具，大神的作品果然不同凡响，git正在变得越来越流行。

在使用的过程中，也感觉到其易用和高效。因此想要探究一下其内部的原理。

git的高效得益于其存储系统的实现，它是一个内容寻址的文件系统。git的核心是一个键值数据库，你可以向这个数据库中插入任意类型的内容，它会返回一个键值作为唯一标识，通过该键值你可以检索插入的数据。我们来通过一个例子理解一下：

我们创建一个测试库

$ git init test
Initialized empty Git repository in U:/git/git-study/test/.git/

git会在test目录下创建一个.git目录，里面有一个objects目录，这就是数据库存储所有对象的地方，可以看到现在是空的。

$ find .git/objects/ -type f

现在我们存储一个数据对象

$ echo ‘test content’ git hash-object -w –stdin
d670460b4b4aece5915caf5c68d12f560a9fe3e4

通过上面的命令将’test content’存入对象数据库，存入成功后git给我们返回了一个键值。

–stdin表示从标准输入读入要存储的对象

-w表示将对象存入到对象数据库

再来看下对象数据库目录的变化

$ find .git/objects -type f
.git/objects/d6/70460b4b4aece5915caf5c68d12f560a9fe3e4

可以看到存入了我们刚才创建的对象，

 git会将待存储的数据外加一个头部信息（header）一起做 SHA-1 校验运算得到一个摘要。后文会简要讨论该头部信息。 摘要为40个字节，git用前2个字节作为子目录，后38个字节作为文件名，这样增加了一级索引能够加快查找。

git中的所有对象文件都可以用cat-file命令来查看，”-t”查看对象文件的类型，”-p”查看对象文件的内容，我们来看一下。

$ git cat-file -t d670
blob

通过”-t”选项可以看到这个对象文件是一个blob,后面会介绍git中的几种对象。

$ git cat-file -p d670
test content

通过”-p”选项可以查看文件内容，注意我们只指定了SHA-1摘要的前4个字节，只要能够唯一区分就可以，无需全部指出。

直接存储内容，用sha值来获取并不现实。因此我们需要文件名，我们再来看下git如何存储文件名。

我们创建一个’test content’内容的文件，再把它提交到git中，看看有什么变化。

$ echo ‘test content’ > test.txt

$ git add .

$ git commit -m “add test.txt”
add test.txt
1 file changed, 1 insertion(+)
create mode 100644 test.txt

我们再来看下对象库里的文件

$ find .git/objects/
.git/objects/
.git/objects/80
.git/objects/80/865964295ae2f11d27383e5f9c0b58a8ef21da
.git/objects/d6
.git/objects/d6/70460b4b4aece5915caf5c68d12f560a9fe3e4
.git/objects/e3
.git/objects/e3/b5f9d4884c0f93d3f9c69e6a94cee29c9d94b2
.git/objects/info
.git/objects/pack

可以看到里面多了2个对象，我们用cat-file命令来探究一下。

$ git cat-file -t 8086
tree

$ git cat-file -t e3b5
commit

可以看到一个对象类型为’tree’,另一个对象类型为’commit’.

我们再来看看对象的内容:

$ git cat-file -p e3b5
tree 80865964295ae2f11d27383e5f9c0b58a8ef21da
author happyAnager6 happyAnger6@163.com 1565186367 +0800
committer happyAnager6 happyAnger6@163.com 1565186367 +0800

add test.txt

这个commit的SHA值和git log里看到的是一致的

$ git log
commit e3b5f9d4884c0f93d3f9c69e6a94cee29c9d94b2
Author: happyAnager6 happyAnger6@163.com
Date: Wed Aug 7 21:59:27 2019 +0800

$ git cat-file -p 8086
100644 blob d670460b4b4aece5915caf5c68d12f560a9fe3e4 test.txt

可以看commit对象里包含了这个tree,并且还有作者和提交者以及提交注释。

tree对象里是test.txt文件名和其引用的blob对象。

我们可以得到下面的关系图：


到这里，我们可以学习到git里的3种对象，commit,tree,blob

commit对象存储的是提交点，里面包含提交的顶层tree对象.

tree对象用于表示文件系统中的文件和目录，存储文件名称和引用的blob对象。

blob对象用于存储实际的数据。

tree和blob模拟出了LINUX里文件系统的概念，tree类似于是dentry目录项，blob类似于是inode。

了解了git中几种对象各自的作用，我们再来看一下git存储实现的高效。

我们再创建一个test1.txt，文件内容和test.txt一样，那么提交后的对象数据库会怎样变化呢？

$ echo “test content” >> test1.txt

$ git add .

$ git commit -m “add test1.txt”
add test1.txt
1 file changed, 1 insertion(+)
create mode 100644 test1.txt

添加好后，我们再来看下对象库的内容。

$ find .git/objects/ -type f
.git/objects/41/402111639cba891703ae9b82e1cf92171f1418
.git/objects/76/7b3496b30214180609a493bbf8130012a4ef30
.git/objects/80/865964295ae2f11d27383e5f9c0b58a8ef21da
.git/objects/d6/70460b4b4aece5915caf5c68d12f560a9fe3e4
.git/objects/e3/b5f9d4884c0f93d3f9c69e6a94cee29c9d94b2

可以看到多了2个对象，我们再用cat-file看一下

$ git cat-file -t 4140
commit

$ git cat-file -t 767b
tree

$ git cat-file -p 4140
tree 767b3496b30214180609a493bbf8130012a4ef30
parent e3b5f9d4884c0f93d3f9c69e6a94cee29c9d94b2
author happyAnager6 happyAnger6@163.com 1565188008 +0800
committer happyAnager6 happyAnger6@163.com 1565188008 +0800

add test1.txt

$ git cat-file -p 767b
100644 blob d670460b4b4aece5915caf5c68d12f560a9fe3e4 test.txt
100644 blob d670460b4b4aece5915caf5c68d12f560a9fe3e4 test1.txt

我们再整理下这5个对象的关系图如下:


可以看到，新的commit对象是上一个commit对象的孩子，新的commit对象引用了一个新的tree对象，新的tree对象包含了2个blob对象的引用，存储了2个不同的文件名，由于文件内容相同，因此2个blob对象引用的是同一个blob对象。

通过上面这个例子，我们可以看到对于内容相同名字不同的文件，最终的文件内容只有一个blob对象，不同的文件通过引用来指向同一个blob。git就是这样使用指针来实现对象的高效复用的。

结合cat-file命令和上面介绍的3种对象你就可以分析git版本库对象存储的工作原理了，是不是有点儿feeling了？

最后再回答下对象存储的格式：

对象类型(blob,tree,commit)+空格+数据长度+NULL+内容

DevOps►Docker

docker镜像存储实现

为什么要写这篇文章？

网上已经有很多讲docker镜像存储原理的文章了，这篇文章还有必要吗？

网上关于docker镜像的文章大都偏原理，像什么镜像是分层的，是只读的，容器除了镜像的只读层还有自己的可写层等等。这些原理说出来大家好像都懂，但好像什么也没学到。因此我写了这篇偏实现的文章，讲述docker是如何利用联合文件系统存储容器镜像，以及如何建立容器的文件系统。

学习这篇文章之后，你将能够：

  • 通过镜像ID找到镜像所有层在磁盘上的存放位置

实战之前先说点基本原理：

docker存储支持多种文件系统。如果没有显示配置，docker按照以下优先级进行选择:

btrfs—->zfs——>overlay2———–>aufs———>overlay——->devicemapper———>vfs.

这些文件系统都是一种虚拟文件系统，需要在真实的文件系统之上使用。虚拟指的是不实际管理真正的磁盘。真实的文件系统称之为backing filesystem.

本篇文章以overlay2为基础进行讲解，可以很容易扩展到其它文件系统实现，如aufs.

overlay2能够使用的backing filesystems有以下限制:

  • 不支持aufs,zfs,overlay,ecryptfs

  • 使用btrfs最好在4.7.0内核之上

docker启动后会有一个rootdir,这个是存储管理的根目录，后面讲解的所有目录都以这个目录为基础（敲黑板^_^)。docker默认会使用/var/lib/docker作为rootdir.

从centos7开始，centos默认使用了xfs文件系统，因此使用overlay2的backing filesystem为xfs.由于xfs支持磁盘限额，因此docker会开启磁盘限额功能。这样，我们就能够通过overlay2.size选项来限制磁盘限额。

好了，准备工作差不多了，我们开始进入主题。

首先，我们可以通过docker images命令查看当前下载的镜像.

我本地有个kube-apiserver镜像，我们用到为例进行说明。

k8s.gcr.io/kube-apiserver v1.12.0 ab60b017e34f 10 months ago 194MB

可以看到这个镜像的ID为ab60b017e34f(缩写),下面我们来一步步找到这个镜像的所有layer.

通过docker inspect ab60命令查看这个镜像的详细信息。

我们直奔主题，下面的信息对我们有帮助:

“RootFS”: {
“Type”: “layers”,
“Layers”: [
“sha256:f9d9e4e6e2f0689cd752390e14ade48b0ec6f2a488a05af5ab2f9ccaf54c299d”,
“sha256:0721ca6c51792b8eb63ca980193076c474f474aace1fe56271040279c8147ec7”
]
},

这个RootFS信息就是此镜像的所有layers,可以看到这个镜像有2个layer,并且能看到他们的ID。这里有必要先讲述一个几个ID，先知道它们的作用，后面方便继续。

有4个ID需要知道:

  • DiffID:每个layer都有这个ID，是此layer内容的sha256摘要，上面RootFS里看到的ID即为DiffID.

  • ChainID:每个layer也有这个ID，从名字上也能猜出个大概，这是一个链式ID，由父layer递归计算而来。计算公式如下:


公式简单说明一下，如果是第0层layer，则ChainID=DiffID,否则由父layer的ChainID加上一个空格再加上本层的DiffID后做SHA256摘要。

ChainID才能唯一标识一个layer,即使2个layer的DiffID相同，但是由不同的父layerID构建而来则ChainID不会相同。

  • CacheID:一个随机值，产生之后不会改变，标识了layer在底层文件系统存放的目录，后面会更详细介绍
  • parent-id:父layer的ChainID.

由于这4个ID是后面的基础，因此再上2幅图加深理解,图来源于上面例子中的镜像:



首先，看下镜像信息在哪里存储。

/var/lib/docker/:这里的fs为使用的文件系统类型，这里是overlay2.

/var/lib/docker/image/overlay2:

├── distribution
├── imagedb
├── layerdb
└── repositories.json

repositories.json文件存储了当前所有的镜像和其镜像仓库的信息。

imagedb/content/sha256/目录下是每个镜像的详细信息，文件名即为镜像ID.这里面除了上面提到RootFS信息外，还有镜像的构建历史命令信息。

然后是layerdb/sha256/:这里面的每个目录即为镜像每layer的信息，文件名是layer的ChainID.

可以看到第0层f9d9目录，

drwx—— 2 root root 71 11月 27 2018 f9d9e4e6e2f0689cd752390e14ade48b0ec6f2a488a05af5ab2f9ccaf54c299d/

我们再计算下第1层的ChainID.通过python代码来计算一下:

import hashlib
s=hashlib.new(‘sha256’)
s.update(b’sha256:f9d9e4e6e2f0689cd752390e14ade48b0ec6f2a488a05af5ab2f9ccaf54c299d’+b’ ‘+b”sha256:0721ca6c51792b8eb63ca980193076c474f474aace1fe56271040279c8147ec7”)
s.hexdigest()
‘4c737d137c079edec3dd457b1a0a5ab1ec508cfec2bbc1ee141b9d207e5cd5df’

也能够找到第1层layer的ChainID的目录:

drwx—— 2 root root 85 11月 27 2018 4c737d137c079edec3dd457b1a0a5ab1ec508cfec2bbc1ee141b9d207e5cd5df/

我们再看看这些目录下有些什么东西。

f9d9e4e6e2f0689cd752390e14ade48b0ec6f2a488a05af5ab2f9ccaf54c299d/
├── cache-id
├── diff
├── size
└── tar-split.json.gz

4c737d137c079edec3dd457b1a0a5ab1ec508cfec2bbc1ee141b9d207e5cd5df/
├── cache-id
├── diff
├── parent
├── size
└── tar-split.json.gz

可以看到f9d9这个layer有4个文件，而4c73这个layer有5个文件，多了一个parent.

这里的文件就是我们上面介绍的4个ID

  • diff存储的是本layer的DiffID.

  • parent存储的是父layer的ChainID.

  • size是本layer的大小

  • cache-id即本layer在本地文件系统存放的实际目录

好了，通过上面的讲解我们就能够通过镜像ID找到所有layer的信息了，我们再来通过cache-id找下layer实际存储的位置。

/var/lib/docker/overlay2:这个目录下的文件就是对应cache-id的目录。

我们找下4c7e这一layer的目录:

通过cache-id:e0bb81486243dd55fe92dc0830816354507d48f149542e9d1cbf0ea9d4a24ee9

我们找到了对应的目录:

drwx—— 4 root root 55 11月 27 2018 e0bb81486243dd55fe92dc0830816354507d48f149542e9d1cbf0ea9d4a24ee9/

我们再看下这个目录下有什么东西:

.
├── diff
│   └── usr
│   └── local
│   └── bin
│   └── kube-apiserver
├── link
├── lower
└── work

可以看到4个目录:

diff:即为本layer的实际内容，可以看到只有一个kube-apiserver的可执行程序

link:这个文件存储的是指向本layer的一个符号链接文件。这个符号链接文件实际存放在/var/lib/docker/overlay2/l目录下。为什么要有这么一个符号链接呢？我们知道overlayfs的原理就是将多个layer挂载到一个目录下，而挂载的多个layer是通过mount options指定的，这个选项的最大长度有限制，通常为4096，如果我们直接使用上面的sha256目录，mount的layer个数就太少了，因此实际mount时使用的是这个符号链接，就能够多支持一些layer了。

lower:本layer的父layer的符号链接

work:overlayfs所使用的work目录

同理，我们可以查看第0层layer的实际内容:

.
├── diff
│   ├── bin
│   ├── dev
│   ├── etc
│   ├── home
│   ├── root
│   ├── tmp
│   ├── usr
│   └── var
└── link

可以看到实际的内容，因为是第0层，所以少了lower和worker目录.

通过上面的讲解，相信你对docker镜像如何存储的应该有了详细的了解，也能够通过镜像ID找到实际的layer了.

操作系统►linux

linux epoll实现分析

epoll的作用是进行I/O的多路复用，可以同时监听多个fd产生的事件。常结合异步处理实现单线程的高并发。在多核环境中，可以结合多线程实现负载分担。

本文主要分析一下linux epoll的实现。

API

epoll_create(int size);.

epoll_create1(int flags);

创建一个epoll实例,并返回与之关联的一个fd.这是后面我们继续使用epoll其它接口的基础。

从内核2.6.27开始，加入了一个新的epoll_create1,这个函数有一个flag参数，可以指定EPOLL_CLOEXEC标志，标识在exec之后关闭fd.

来看下创建epoll都做了些什么？

创建一个struct eventpoll结构，每个epoll使用这个结构管理其监听的所有fd以及就绪fd.

然后创建一个epoll对应的file结构，并将创建的epoll挂到file的private_data上（这是vfs的通常做法，将具体文件相关的结构挂到私有数据上）.

将file结构的f_op填充为epoll实现eventpoll_fops.这样利用多态实现以后对epoll文件file的相关操作就能映射到epoll具体的实现上。

int epoll_ctl(int epfd, int op, int fd, struct epoll_event *event);

typedef union epoll_data {
void *ptr;
int fd;
uint32_t u32;
uint64_t u64;
} epoll_data_t;

1
2
3
4
struct epoll_event {
    uint32_t     events;      /* Epoll events */
    epoll_data_t data;        /* User data variable */
};

通过此接口将我们关心的fd和相应的事件添加/删除/修改到epoll中。

通过event结构里的events添加我们关注的事件类型。

其中的events可以指定如下一些标志:

  • EPOLLIN:监听文件可读

  • EPOLLOUT:监听文件可写

  • EPOLLRDHUP(2.6.17添加):对于基于流的socket,标识对端关闭或者shutdown半关闭了连接（对端只读不写)。对于shutdown这种情况，这个标志在使用边缘触发模式进行写操作时能够有效地监控对端是否关闭了写端。关于EPOLL的水平触发和边缘触发模式后面会有详细介绍。

  • EPOLLPRI：有urgent data到达

  • EPOLLERR：这个事件epoll操作会始终进行监听，不管你有没有显式地指定

  • EPOLLHUP：epoll也会始终监听这个事件.标识对端关闭，当通道上剩余数据读完后，read会返回0.

  • EPOLLLET:使用边缘触发模式（ET)，epoll默认采用水平触发模式（LT）

为了说明LT和ET的区别，考虑下面的场景：

  • 有一代表pipe读端的rfd注册到epoll上。

  • pipe另一端写入了2KB的数据

  • epoll_wait返回标识rfd有数据可读

  • 调用read从rfd读取了1KB的数据

  • epoll_wait结束

对于ET模式，epoll_wait结束后，剩余的1KB数据有可能仍然保存在文件的buffer中，同时对端等待这些数据读取后的响应。这是因为ET模式仅仅在监控的文件发生变化时提交事件，因此epoll_wait继续等待有新的数据到来才能触发新的事件。

使用ET模式的程序应该使用非阻塞模式，这样不至于因为阻塞导致同时监听的其它fd被饿死。建议使用ET模式按照如下方式：

  • 使用非阻塞fd

  • 持续调用read或者write直到返回EAGAIN再继续等待新事件(epoll_wait).

相对的，使用LT模式（默认模式），epoll就相当于是一个更快的poll,它可以代替任何使用poll的地方，因为具有和poll相同的语义。对于上面的例子，只要buffer中还有未读的数据,epoll_wait就会一直通知事件。

  • EPOLLONESHOT（linux 2.6.2)

这个选项用的比较少，作用是当关心的fd上产生事件时，epoll将会停止关注和上报fd后续的事件，我们需要在处理完事件后再调用epoll_ctl重新安装关心的事件。我能想到这个选项的作用可能是在使用ET模式时提高效率，比如我们在读数据时，又有新数据到来，可以一直读取完而不用再产生和关注新事件。

  • EPOLLWAKEUP(linux 3.5)

这个选项很罕见，简单介绍下。当linux运行于autosleep模式时，当有事件产生时将设备从sleep状态唤醒，设备驱动在事件入队之后就继续sleep.如果要让设备等事件处理后再进行sleep状态就要设备此标志。

  • EPOLLEXCLUSIVE(linux 4.5)

设置独占唤醒模式。这个标志主要用在我们用多个epoll监听同一个fd时，保证当事件到来时只唤醒其中一个epoll.这个标志默认不会设置，因此会有“惊群效应”

如果多个epoll监听同一个fd,部分设置了此选项，部分没有设置此选项。那么到事件到来时，所有未设置此选项的epoll都会唤醒，设置此选项的至少唤醒一个。

这个选项只能在EPOLL_CTL_ADD时使用，EPOLL_CTL_MOD使用会报错。

int epoll_wait(int epfd, struct epoll_event *events, int maxevents, int timeout)

开始事件循环.

events参数会输出就绪的文件及其事件。

返回值标识就绪的events的个数。

maxevents指明最多返回多少个就绪事件，必须大于0

timeout指定等待超时时间，单位ms.-1标识不超时。

epoll_wait在以下情况会返回:

  • 监听的某个文件递交了一个事件

  • 被信号打断

  • 超时

epoll__ctl实现

来看一下向epoll中添加fd的流程。我们只分析添加的fd是普通文件的情况，因为可以向epoll中可以添加另一个epoll,这种情况的代码暂不分析。

epoll内部使用红黑树管理fd,在管理大量fd时效率依然很高。

添加fd的关键在于建立目标文件与epoll的关联，当fd产生事件时能够通知关心的epoll.

主要代码在ep_insert中，其中涉及的数据结构比较多，先上一张总图


对于每个fd都会关联一个epitem,这里面的ffd包含了实际的file,fd.

ep_queue结构的作用是在ep_ptable_queue_proc函数和epitem之间建立联系，调用ep_ptable_queue_proc的时候就能将epitem的等待队列加入到目标文件的等待队列中。

不同的文件系统要支持epoll,要实现file_operations的__poll_t (*poll) (struct file *, struct poll_table_struct *)接口。

通过调用对应文件的poll函数将epitem加入到目标文件的等待队列中。这个函数有2个参数，一个是目标文件，一个是poll_table结构。我们来看一个具体文件系统实现的poll函数，来了解下具体流程。

以fuse文件系统为例:

__poll_t fuse_file_poll(struct file *file, poll_table *wait)

poll_wait(file, &ff->poll_wait, wait);

调用poll_wait函数，ff->poll_wait即为目标文件的等待队列头。poll_wait函数是linux提供的函数，用于具体文件系统在poll中调用。这个函数调用poll_table里的_qproc函数，即上文提到的”ep_ptable_queue_proc”.

ep_ptable_queue_proc完成目标文件和epitem关系的建立。

static void ep_ptable_queue_proc(struct file *file, wait_queue_head_t *whead,
poll_table *pt)
{
struct epitem *epi = ep_item_from_epqueue(pt);
struct eppoll_entry *pwq;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
if (epi->nwait >= 0 && (pwq = kmem_cache_alloc(pwq_cache, GFP_KERNEL))) {
    init_waitqueue_func_entry(&pwq->wait, ep_poll_callback);
    pwq->whead = whead;
    pwq->base = epi;
    if (epi->event.events & EPOLLEXCLUSIVE)
        add_wait_queue_exclusive(whead, &pwq->wait);
    else
        add_wait_queue(whead, &pwq->wait);
    list_add_tail(&pwq->llink, &epi->pwqlist);
    epi->nwait++;
} else {
    /* We have to signal that an error occurred */
    epi->nwait = -1;
}

这个函数3个参数分别为目标文件，目标文件等待队列头，和poll_table.

通过poll_table找到对应的epitem,然后创建一个epoll_entry对象。

在这个对象上创建等待队列项pwq->wait,并设置回调ep_poll_callback.

调用add_wait_queue加入到目标文件中。

这里可以看到，如果对应的fd的events设置了前面提到的EPOLLEXCLUSIVE选项，则以独占方式加入到目标文件的完成队列中。

通过这一步操作，就建立了目标文件和对应fd epoll的关联，到目标文件有事件到来时，就能够调用ep_poll_callback函数通知epoll了。

事件递交流程

我们再来看一下，当有实际事件就绪时，通知epoll的流程。

其实上文已经提到了，会调用上面注册的ep_poll_callback函数。

主要代码如下:

首先判断对应fd的epi是否在就绪链表里，如果没有则添加到就绪链表尾。

if (!ep_is_linked(&epi->rdllink)) {
list_add_tail(&epi->rdllink, &ep->rdllist);
ep_pm_stay_awake_rcu(epi);
}

然后，判断是否有进程在epoll_wait,如果有则唤醒。

if (waitqueue_active(&ep->wq)) {
if ((epi->event.events & EPOLLEXCLUSIVE) &&
!(pollflags & POLLFREE)) {
switch (pollflags & EPOLLINOUT_BITS) {
case EPOLLIN:
if (epi->event.events & EPOLLIN)
ewake = 1;
break;
case EPOLLOUT:
if (epi->event.events & EPOLLOUT)
ewake = 1;
break;
case 0:
ewake = 1;
break;
}
}
wake_up_locked(&ep->wq);
}
if (waitqueue_active(&ep->poll_wait))
pwake++;

我们可以看到，如果有多个fd同时就绪，会以通知epoll的先后顺序添加到就绪队列中。

epoll_wait处理就绪事件

就绪事件已经添加到链表中，则就差epoll_wait获取并返回了。

主要是调用”ep_send_events”发送就绪事件

先将就绪链表放到一个临时链表中，然后发送事件。由于访问epoll的就绪链表需要自旋锁，因此这里通过临时链表来尽快释放自旋锁。

spin_lock_irqsave(&ep->lock, flags);
list_splice_init(&ep->rdllist, &txlist);
ep->ovflist = NULL;
spin_unlock_irqrestore(&ep->lock, flags);

发送事件主要是遍历临时链表，并将就绪事件拷贝到用户态。这里还有一个注意点，就是对应LT模式的处理:

else if (!(epi->event.events & EPOLLET)) {
/*

  • If this file has been added with Level
  • Trigger mode, we need to insert back inside
  • the ready list, so that the next call to
  • epoll_wait() will check again the events
  • availability. At this point, no one can insert
  • into ep->rdllist besides us. The epoll_ctl()
  • callers are locked out by
  • ep_scan_ready_list() holding “mtx” and the
  • poll callback will queue them in ep->ovflist.
  • /
    list_add_tail(&epi->rdllink, &ep->rdllist);
    ep_pm_stay_awake(epi);
    }

如果对应fd的epi是LT模式，则将其再次加入就绪链表，这样下次调用epoll_wait时就会再次检查是否还有事件可用。

好了，epoll的实现就分析完成了。通过学习你能回答下面几个问题吗？

  • 如果2个线程同时监听同一个epoll fd,那么有fd就绪时会都唤醒吗？

  • 如果2个线程使用不同的epoll fd,但是加入了相同的fd,又会是怎样的呢？

  • 如果同时有多个fd有就绪事件，epoll_wait返回的就绪events数组里顺序如何?

rpc►gRPC

gRPC当前epoll实现的问题和解决方案

gRPC当前的epoll实现并不十分高效，有很大的改进空间。这篇文章来分析一下。

epoll是gRPC实现pollset的基础。因此，你有必要先了解一下epoll即其发展史（至少了解EPOLLEXCLUSIVE是干什么的吧？）

如果文章中的内容不能理解，建议先看下我之前讲gRPC的相关文章。

介绍

当前gRPC中epoll的实现.

整体架构图:


一个gRPC客户端或者服务端都可以有多个completion queue(后面简称为cq),每个cq都会创建一个pollset.

gRPC核心库自己不会创建任何线程，线程的创建取决于使用gRPC核心库的应用程序。

线程通过调用APIgrpc_completion_queue_next()或者grpc_completion_queue_pluck()开始事件poll.

在同一个cq上可以有多个线程同时调用grpc_completion_queue_next().

一个文件描述符fd可以加入到多个cq中.

当epoll_set上有事件产生时，有多个线程可能被唤醒，不能保证哪个线程最终执行事件相关的callbacks.

执行工作的线程最终会向合适的cq中放入一个completion event（完成事件，后面简称ce）grpc_cq_completion，然后将对这个ce感兴趣的线程”kicks”(唤醒，一般使用eventfd实现).这里需要注意的是这个线程可能是自己。

举个例子：

假设上图中的fd_1变为可读状态，Thread1~ThreadK, ThreadP都有可能被唤醒。

我们假设ThreadP因为关心fd1上的事件而调用了grpc_completion_queue_pluck(),但是被唤醒的是Thread1。

在这种情况下，_Thread1_执行完相应的callbacks后并最终通过event_fd_P来唤醒”kicks “ ThreadP.

_ThreadP_被唤醒，然后知道有一个ce并将它返回给grpc_completion_queue_pluck()的调用者。

当前架构的问题

惊群效应

今天儿有点儿晚了，明天继续吧。^_^

作者：self-motivation
来源：CSDN
原文：https://blog.csdn.net/happyAnger6/article/details/97182780
版权声明：本文为博主原创文章，转载请附上博文链接！

自我修养►数据结构与算法

实现霍夫曼编码

class HuffmanNode:
def init(self, char, weight, left, right):
self.weight = weight
self.char = char
self.left = left
self.right = right

class Huffman:
def init(self):
self.root = None
def add_node(self, node):
if self.root is None:
self.root = node
else:
self.root = HuffmanNode(‘’, node.weight + self.root.weight, self.root, node) 

def codes(self):  
    def dfs(node, cur):  
        if node is None:  
            return

print(node.char, node.weight, cur)
dfs(node.left, cur+’0’)
dfs(node.right, cur+’1’)
return dfs(self.root, ‘’)

if name == “main“:
chars = [
(‘f’, 20),
(‘e’, 30),
(‘d’, 60),
(‘c’, 90),
(‘b’, 350),
(‘a’, 450),
] 

huffman = Huffman()  
for c in chars:  
    huffman.add_node(HuffmanNode(c[0], c[1], None, None))  

huffman.codes(