golang http client 连接池

golang标准库net/http做为client时有哪些细节需要注意呢,这里做一个详细的分析。

net/http client工作流程

首先分析一下client的工作流程。 下面是一般我们进行一个请求时的代码事例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func DoRequest(req *http.Request) (MyResponse, error) {
client := &http.Client{}
resp, err := client.Do(req)
if resp != nil {
defer resp.Body.Close()
}
if err != nil {
return nil, err
}
body, err := ioutil.ReadAll(resp.Body)
if err != nil {
return nil, err
}

response := MyResponse{}
response.Header = resp.Header
...
response.Body = body

return response, nil
}

代码中我们首先创建一个http.Client, 所有的值都是默认值,然后调用client.Do发请求,req是我们请求的结构体。这里我们也可以用client.Get, client.Post等函数来调用,从他们的源码来看都是调用的client.Do
client.Do的实现在net/http包的go/src/net/http/client.go源文件中。可以看到函数内部主要是实现了一些参数检查,默认值设置,以及对于多跳请求的处理,最为核心的就是:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
...
if resp, didTimeout, err = c.send(req, deadline); err != nil {
// c.send() always closes req.Body
reqBodyClosed = true
if !deadline.IsZero() && didTimeout() {
err = &httpError{
err: err.Error() + " (Client.Timeout exceeded while awaiting headers)",
timeout: true,
}
}
return nil, uerr(err)
}

var shouldRedirect bool
redirectMethod, shouldRedirect, includeBody = redirectBehavior(req.Method, resp, reqs[0])
if !shouldRedirect {
return resp, nil
}
...

这里真正发请求的函数就是c.send, 这个函数的实现也比较简单, 主要是调用了send函数,这个函数的实现主要如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// didTimeout is non-nil only if err != nil.
func (c *Client) send(req *Request, deadline time.Time) (resp *Response, didTimeout func() bool, err error) {
if c.Jar != nil {
for _, cookie := range c.Jar.Cookies(req.URL) {
req.AddCookie(cookie)
}
}
resp, didTimeout, err = send(req, c.transport(), deadline)
if err != nil {
return nil, didTimeout, err
}
if c.Jar != nil {
if rc := resp.Cookies(); len(rc) > 0 {
c.Jar.SetCookies(req.URL, rc)
}
}
return resp, nil, nil
}
1
2
3
4
5
6
7
8
9
10
// send issues an HTTP request.
// Caller should close resp.Body when done reading from it.
func send(ireq *Request, rt RoundTripper, deadline time.Time) (resp *Response, didTimeout func() bool, err error) {
...
stopTimer, didTimeout := setRequestCancel(req, rt, deadline)
...
resp, err = rt.RoundTrip(req)
...
return resp, nil, nil
}

这里真正进行网络交互的定位到的函数是rt.RoundTrip,这个函数的定义是一个interface,从其注释也可以看出他的主要作用是:

1
2
// RoundTrip executes a single HTTP transaction, returning
// a Response for the provided Request.`

由于这个函数是一个interface我们需要知道是谁实现了这个函数,看一下send的参数就可以找到,实现这个函数的是c.transport()的返回值,这个函数的实现如下:

1
2
3
4
5
6
func (c *Client) transport() RoundTripper {
if c.Transport != nil {
return c.Transport
}
return DefaultTransport
}

这里可以看到,返回的对象是c.Transport或者DefaultTransport, 由于我们创建client的时候没有设置c.Transport参数,所以这里返回的应该是DefaultTransport对象, 这个对象对RoundTripper函数的实现大概如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// RoundTrip implements the RoundTripper interface.
//
// For higher-level HTTP client support (such as handling of cookies
// and redirects), see Get, Post, and the Client type.
func (t *Transport) RoundTrip(req *Request) (*Response, error) {
...
for {
...
pconn, err := t.getConn(treq, cm)
...
if pconn.alt != nil {
// HTTP/2 path.
t.setReqCanceler(req, nil) // not cancelable with CancelRequest
resp, err = pconn.alt.RoundTrip(req)
} else {
resp, err = pconn.roundTrip(treq)
}
}
...
}

里面具体的细节我们先不关系,对于HTTP/2的处理我们也先不关心。这里需要重点关注的是t.getConn这个函数。t.getConn的作用是获取一个链接,这个链接该怎么获取,是一个值得深究的问题。下面看一下这个函数的关键实现细节:

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
// getConn dials and creates a new persistConn to the target as
// specified in the connectMethod. This includes doing a proxy CONNECT
// and/or setting up TLS. If this doesn't return an error, the persistConn
// is ready to write requests to.
func (t *Transport) getConn(treq *transportRequest, cm connectMethod) (*persistConn, error) {
req := treq.Request
trace := treq.trace
ctx := req.Context()
if trace != nil && trace.GetConn != nil {
trace.GetConn(cm.addr())
}
if pc, idleSince := t.getIdleConn(cm); pc != nil {
if trace != nil && trace.GotConn != nil {
trace.GotConn(pc.gotIdleConnTrace(idleSince))
}
// set request canceler to some non-nil function so we
// can detect whether it was cleared between now and when
// we enter roundTrip
t.setReqCanceler(req, func(error) {})
return pc, nil
}
...
handlePendingDial := func() {
testHookPrePendingDial()
go func() {
if v := <-dialc; v.err == nil {
t.putOrCloseIdleConn(v.pc)
}
testHookPostPendingDial()
}()
}

cancelc := make(chan error, 1)
t.setReqCanceler(req, func(err error) { cancelc <- err })

go func() {
pc, err := t.dialConn(ctx, cm)
dialc <- dialRes{pc, err}
}()
idleConnCh := t.getIdleConnCh(cm)
select {
case v := <-dialc:
// Our dial finished.
if v.pc != nil {
if trace != nil && trace.GotConn != nil && v.pc.alt == nil {
trace.GotConn(httptrace.GotConnInfo{Conn: v.pc.conn})
}
return v.pc, nil
}
// Our dial failed. See why to return a nicer error
// value.
select {
case <-req.Cancel:
// It was an error due to cancelation, so prioritize that
// error value. (Issue 16049)
return nil, errRequestCanceledConn
case <-req.Context().Done():
return nil, req.Context().Err()
case err := <-cancelc:
if err == errRequestCanceled {
err = errRequestCanceledConn
}
return nil, err
default:
// It wasn't an error due to cancelation, so
// return the original error message:
return nil, v.err
}
case pc := <-idleConnCh:
// Another request finished first and its net.Conn
// became available before our dial. Or somebody
// else's dial that they didn't use.
// But our dial is still going, so give it away
// when it finishes:
handlePendingDial()
if trace != nil && trace.GotConn != nil {
trace.GotConn(httptrace.GotConnInfo{Conn: pc.conn, Reused: pc.isReused()})
}
return pc, nil
case <-req.Cancel:
handlePendingDial()
return nil, errRequestCanceledConn
case <-req.Context().Done():
handlePendingDial()
return nil, req.Context().Err()
case err := <-cancelc:
handlePendingDial()
if err == errRequestCanceled {
err = errRequestCanceledConn
}
return nil, err
}
}

下面是这个过程的流程图:

从上面可以看到,获取链接会优先从连接池中获取,如果连接池中没有可用的连接,则会创建一个连接或者从刚刚释放的连接中获取一个,这两个过程时同时进行的,谁先获取到连接就用谁的。
当新创建一个连接, 创建连接的函数定义如下:

1
func (t *Transport) dialConn(ctx context.Context, cm connectMethod) (*persistConn, error)

最后这个函数会通过goroutine调用两个函数:

1
2
go pconn.readLoop()
go pconn.writeLoop()

其中readLoop主要是读取从server返回的数据,writeLoop主要发送请求到server,在readLoop函数中有这么一段代码:

1
2
3
4
5
6
7
8
9
10
// Put the idle conn back into the pool before we send the response
// so if they process it quickly and make another request, they'll
// get this same conn. But we use the unbuffered channel 'rc'
// to guarantee that persistConn.roundTrip got out of its select
// potentially waiting for this persistConn to close.
// but after
alive = alive &&
!pc.sawEOF &&
pc.wroteRequest() &&
tryPutIdleConn(trace)

这里可以看出,在处理完请求后,会立即把当前连接放到连接池中。

上面说到连接池,每个client的连接池结构是这样的:idleConn map[connectMethodKey][]*persistConn。其中connectMethodKey的值就是client连接的server的host值, map的值是一个*persistConn类型的slice结构,这里就是存放连接的地方,slice的长度由MaxIdleConnsPerHost这个值指定的,当我们不设置这个值的时候就取默认的设置:const DefaultMaxIdleConnsPerHost = 2

另外这里我们插一个知识点,对于HTTP协议,有一个header值”Connections”, 这个值的作用就是clientserver端发请求的时候,告诉server是否要保持连接。具体的可以参考rfc2616。 这个协议头的值有两种可能(参考MDN文档):

1
2
Connection: keep-alive
Connection: close

当值为keep-alive时,server端会保持连接,一直到连接超时。当值为close时,server端会在传输完response后主动断掉TCP连接。在HTTP/1.1之前,这个值默认是close, 之后是默认keep-alive, 而net/http默认的协议是HTTP/1.1也就是默认keep-alive, 这个值可以通过DisableKeepAlives来设置。

从上面的介绍我们可以看出,net/http默认是连接复用的,对于每个server会默认的连接池大小是2。
接下来我们看一下连接是如何放进连接池的:

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
func (t *Transport) putOrCloseIdleConn(pconn *persistConn) {
if err := t.tryPutIdleConn(pconn); err != nil {
pconn.close(err)
}
}


// tryPutIdleConn adds pconn to the list of idle persistent connections awaiting
// a new request.
// If pconn is no longer needed or not in a good state, tryPutIdleConn returns
// an error explaining why it wasn't registered.
// tryPutIdleConn does not close pconn. Use putOrCloseIdleConn instead for that.
func (t *Transport) tryPutIdleConn(pconn *persistConn) error {
if t.DisableKeepAlives || t.MaxIdleConnsPerHost < 0 {
return errKeepAlivesDisabled
}
if pconn.isBroken() {
return errConnBroken
}
if pconn.alt != nil {
return errNotCachingH2Conn
}
pconn.markReused()
key := pconn.cacheKey

t.idleMu.Lock()
defer t.idleMu.Unlock()
waitingDialer := t.idleConnCh[key]
select {
case waitingDialer <- pconn:
// We're done with this pconn and somebody else is
// currently waiting for a conn of this type (they're
// actively dialing, but this conn is ready
// first). Chrome calls this socket late binding. See
// https://insouciant.org/tech/connection-management-in-chromium/
return nil
default:
if waitingDialer != nil {
// They had populated this, but their dial won
// first, so we can clean up this map entry.
delete(t.idleConnCh, key)
}
}
if t.wantIdle {
return errWantIdle
}
if t.idleConn == nil {
t.idleConn = make(map[connectMethodKey][]*persistConn)
}
idles := t.idleConn[key]
if len(idles) >= t.maxIdleConnsPerHost() {
return errTooManyIdleHost
}
for _, exist := range idles {
if exist == pconn {
log.Fatalf("dup idle pconn %p in freelist", pconn)
}
}
t.idleConn[key] = append(idles, pconn)
t.idleLRU.add(pconn)
if t.MaxIdleConns != 0 && t.idleLRU.len() > t.MaxIdleConns {
oldest := t.idleLRU.removeOldest()
oldest.close(errTooManyIdle)
t.removeIdleConnLocked(oldest)
}
if t.IdleConnTimeout > 0 {
if pconn.idleTimer != nil {
pconn.idleTimer.Reset(t.IdleConnTimeout)
} else {
pconn.idleTimer = time.AfterFunc(t.IdleConnTimeout, pconn.closeConnIfStillIdle)
}
}
pconn.idleAt = time.Now()
return nil
}

首先会尝试把连接放入到连接池中,如果不成功则关闭连接,大致流程如下:

如果DisableKeepAlivestrue表示不使用连接复用,所以请求完后会把连接关掉,但是这里需要注意的是,同时发请求的时候我们会设置Connections: close, 所以server端发送完数据后就会自动断开,所以这种情况的连接其实是server端发起的。

长连接与短连接

前面我们已经讲过net/http默认使用HTTP/1.1协议,也就是默认发送Connections: keep-alive的头,让服务端保持连接,就是所谓的长连接。
再看DefaultTransport的值:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// DefaultTransport is the default implementation of Transport and is
// used by DefaultClient. It establishes network connections as needed
// and caches them for reuse by subsequent calls. It uses HTTP proxies
// as directed by the $HTTP_PROXY and $NO_PROXY (or $http_proxy and
// $no_proxy) environment variables.
var DefaultTransport RoundTripper = &Transport{
Proxy: ProxyFromEnvironment, //代理使用
DialContext: (&net.Dialer{
Timeout: 30 * time.Second, //连接超时时间
KeepAlive: 30 * time.Second, //连接保持超时时间
DualStack: true, //
}).DialContext,
MaxIdleConns: 100, //client对与所有host最大空闲连接数总和
IdleConnTimeout: 90 * time.Second, //空闲连接在连接池中的超时时间
TLSHandshakeTimeout: 10 * time.Second, //TLS安全连接握手超时时间
ExpectContinueTimeout: 1 * time.Second, //发送完请求到接收到响应头的超时时间
}

当我们使用DefaultTransport时,就是默认使用的长连接。但是默认的连接池MaxIdleConns为100, MaxIdleConnsPerHost为2,当超出这个范围时,客户端会主动关闭到连接。
如果我们想设置为短连接,有几种方法:

  1. 设置DisableKeepAlives = true: 这时就会发送Connections:close给server端,在server端响应后就会主动关闭连接。
  2. 设置MaxIdleConnsPerHost < 0: 当MaxIdleConnsPerHost < 0时,连接池是无法放置空闲连接的,所以无法复用,连接直接会在client端被关闭。

Server端出现大量的TIME_WAIT

当我们在实际使用时,会发现Server端出现了大量的TIME_WAIT,要想深入了解其原因,我们首先先回顾一下TCP三次握手和四次分手的过程:


图中可以看出,TIME_WAIT只会出现在主动关闭连接的一方,也就是server端出现了大量的主动关闭行为。
默认我们是使用长连接的,只有在超时的情况下server端才会主动关闭连接。前面也讲到,如果超出连接池的部分就会在client端主动关闭连接,连接池的连接会复用,看着似乎没有什么问题。问题出在我们每次请求都会new一个新的client,这样每个client的连接池里的连接并没有得到复用,而且这时client也不会主动关闭这个连接,所以server端出现了大量的keep-alive但是没有请求的连接,就会主动发起关闭。

todo:补充tcpdump的分析结果

要解决这个问题以下几个方案:

  1. client复用,也就是我们尽量复用client,来保证client连接池里面的连接得到复用,而减少出现超时关闭的情况。
  2. 设置MaxIdleConnsPerHost < 0:这样每次请求后都会由client发起主动关闭连接的请求,server端就不会出现大量的TIME_WAIT
  3. 修改server内核参数: 当出现大量的TIME_WAIT时危害就是导致fd不够用,无法处理新的请求。我们可以通过设置/etc/sysctl.conf文件中的

    1
    2
    3
    4
    #表示开启重用。允许将TIME-WAIT sockets重新用于新的TCP连接,默认为0,表示关闭  
    net.ipv4.tcp_tw_reuse = 1
    #表示开启TCP连接中TIME-WAIT sockets的快速回收,默认为0,表示关闭
    net.ipv4.tcp_tw_recycle = 1

    达到快速回收和重用的效果,不影响其对新连接的处理。

另外需要注意的是,虽然DisableKeepAlives = true也能满足连接池中不放空闲连接,但是这时候会发送Connections: close,这时server端还是会主动关闭连接,导致大量的TIME_WAIT出现,所以这种方法行不通。

以上就是我总结的关于net/http中连接池相关的知识。

亿级流量网站架构核心技术总结

最近读了《亿级流量网站架构核心技术——跟开涛学搭建高可用高并发系统》这本书,总体感觉这本书很实用,作者根据自己负责的项目经历以及业务的发展过程和业界的理论基础相结合讲解了如何搭建一个具有高并发和高可用特征的电商网站。作者是京东的架构师,进来随着京东业务的不断发展,6.18和双十一活动规模的不断扩大,作者都亲身经历了整个电商网站的发展过程,相对于单纯的理论,这本书更多的是能够在业务中快速应用的经验总结。下面就这两方面我把作者的思维导图搬过来,不断提醒自己要注意的整体思想,并能够深入浅出,根据思维导图的每一项都有一个自己更发散更深入的认识。

高可用

高可用

高并发

高并发

golang channels 的串联,扇入扇出及控制

如果说goroutine是Go语言程序的并发体的话,那么channels则是它们之间的通信机制。 一个channel是一个通信机制,它可以让一个goroutine通过它给另一个goroutine发送值信息。 channel之间可以进行串联,并联等组合,组成我们想要的运行方式。 不同goroutine之间需要同步,也需要控制,具体该如何处理这些情况,下面分别进行介绍。

channel基础

使用内置的make函数,我们可以创建一个channel:

1
ch := make(chan int) // ch has type 'chan int'

当我们复制一个channel或用于函数参数传递时,我们只是拷贝了一个channel引用,因此调用者和被调用者将引用同一个channel对象。和其它的引用类型一样,channel的零值也是nil。
两个相同类型的channel可以使用==运算符比较。如果两个channel引用的是相同的对象,那么比较的结果为真。一个channel也可以和nil进行比较。
一个channel有发送和接受两个主要操作,都是通信行为。

1
2
3
ch <- x  // a send statement
x = <-ch // a receive expression in an assignment statement
<-ch // a receive statement; result is discarded

Channel还支持close操作,用于关闭channel,随后对基于该channel的任何发送操作都将导致panic异常。对一个已经被close过的channel进行接收操作依然可以接受到之前已经成功发送的数据;如果channel中已经没有数据的话将产生一个零值的数据。

1
close(ch)

以最简单方式调用make函数创建的是一个无缓存的channel,但是我们也可以指定第二个整型参数,对应channel的容量。如果channel的容量大于零,那么该channel就是带缓存的channel。

1
2
3
ch = make(chan int)    // unbuffered channel
ch = make(chan int, 0) // unbuffered channel
ch = make(chan int, 3) // buffered channel with capacity 3

不带缓存的Channels

一个基于无缓存Channels的发送操作将导致发送者goroutine阻塞,直到另一个goroutine在相同的Channels上执行接收操作,当发送的值通过Channels成功传输之后,两个goroutine可以继续执行后面的语句。反之,如果接收操作先发生,那么接收者goroutine也将阻塞,直到有另一个goroutine在相同的Channels上执行发送操作。
基于无缓存Channels的发送和接收操作将导致两个goroutine做一次同步操作。因为这个原因,无缓存Channels有时候也被称为同步Channels。当通过一个无缓存Channels发送数据时,接收者收到数据发生在唤醒发送者goroutine之前。

对于不带缓存的Channels,我们使用的是有必须放到goroutine,因为如果直接调用chanx <- 1时,会报错fatal error: all goroutines are asleep - deadlock!

1
2
3
4
5
6
package main

func main() {
chanx := make(chan int)
chanx <- 1 //fatal error: all goroutines are asleep - deadlock!
<-chanx

由于主goroutine调用了 chanx <-1, 但是由于是顺序往下执行,执行时还不存在监听chanx的方法存在,所以数据放入chanx后无法唤醒接收的方法,只能等待下去,所以就产生了deadlock。
可以修改为下面的形式,把chanx <- 1放入到一个goroutine里,然后主goroutine监听了这个chanx,当往chanx放数据的时候就会有接收的方法被调用。

1
2
3
4
5
6
package main

func main() {
chanx := make(chan int)
go func() {chanx <- 1}() //right
<-chanx

当使用range遍历chan时别忘了close, 下面当没有使用close时:

1
2
3
4
5
6
7
8
9
10
11
12
13
package main
import "fmt"
func main() {
chanx := make(chan int)
go func() {
for i := 0; i < 3; i++ {
chanx <- i
}
}()
for v := range chanx {
fmt.Println(v)
}
}

output:

1
2
3
4
5
0
1
2
fatal error: all goroutines are asleep - deadlock!
goroutine 1 [chan receive]:

range会从channel中接收数据直到channelclose为止,正常情况下close并不是必须的,只有在接收者需要知道没有更多的数据进入的时候才需要,而range正是需要知道这个信息的。所以代码改成下面这样就没问题了:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
package main
import "fmt"
func main() {
chanx := make(chan int)
go func() {
for i := 0; i < 3; i++ {
chanx <- i
}
close(chanx)
}()
for v := range chanx {
fmt.Println(v)
}
}

带缓存的Channels

带缓存的Channel内部持有一个元素队列。队列的最大容量是在调用make函数创建channel时通过第二个参数指定的。下面的语句创建了一个可以持有三个字符串元素的带缓存Channel。

1
ch = make(chan string, 3)

向缓存Channel的发送操作就是向内部缓存队列的尾部插入元素,接收操作则是从队列的头部删除元素。如果内部缓存队列是满的,那么发送操作将阻塞直到因另一个goroutine执行接收操作而释放了新的队列空间。相反,如果channel是空的,接收操作将阻塞直到有另一个goroutine执行发送操作而向队列插入元素。

队列元素为1的带缓存Channels与不带缓存的Channels是不同的,下面的例子可以看出:

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

func main() {
chan_nobuffer := make(chan int)
chan_nobuffer <- 1 //error 必须放到goroutine中
<-chan_nobuffer

chan_buffer := make(chan int, 1)
chan_buffer <- 1 //right
<-chan_buffer
}

单方向的Channel

channel还有两种语法:<-chan intchan<- int,其意思是单方向的channel, 当定义为out chan<- int表示out只能被往里面放数据,不允许从out拿数据,否则程序会报错receive from send-only type chan<- int,如果定义为in <-chan intin只能往外输出数据,不允许往in里面放数据,否则报错send to receive-only type <-chan int

channel串联

Channels也可以用于将多个goroutine连接在一起,一个Channel的输出作为下一个Channel的输入。 这种串联的Channels就是所谓的管道(pipeline)。下图就是一个串联的channel示意:
串联channel
第一个goroutine Counter负责生成一个0,1,2,3,…形式的整数序列,然后把整数序列输入到一个channel中,通过这个channel传递个下一个goroutine Squarer, 负责将从channel接收到的数求平方,然后再把得出的结果通过channel传递给goroutine Printer, Printer负责将从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
26
27
28
29
30
31
32
33
34
package main

import (
"fmt"
)

func main() {
chan1 := make(chan int)
chan2 := make(chan int)
go Counter(chan1)
go Squarer(chan2, chan1)
Printer(chan2)

}

func Counter(out chan<- int) {
for i := 1; i < 10; i++ {
out <- i
}
close(out)
}

func Squarer(out chan<- int, in <-chan int){
for v := range in {
out <- v * v
}
close(out)
}

func Printer(in <-chan int) {
for v := range in {
fmt.Println(v)
}
}

上面代码中我们创建了两个chan, 然后调用了CounterSquarer, 由于上面说:当我们复制一个channel或用于函数参数传递时,我们只是拷贝了一个channel引用,因此调用者和被调用者将引用同一个channel对象。所以我们对chan1和chan2的修改都是全局的。
Counter往chan1中陆续放入了0,1,2,3,...等数列,然后同步的Squarer接收到数据对其平方并放入chan2,最后Printerchan2中输出这些数据。
对于串联的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
26
27
28
29
30
31
32
33
34
35
36
package main

import (
"fmt"
)

func main() {
c := gen(2,3)
out := sq(c)

for v := range out {
fmt.Println(v)
}
}

func gen(nums ...int) <-chan int {
out := make(chan int)
go func() {
for _, n := range nums {
out <- n
}
close(out)
}()
return out
}

func sq(in <-chan int) <-chan int {
out := make(chan int)
go func() {
for n := range in {
out <- n*n
}
close(out)
}()
return out
}

上面的gen函数用到了golang的可变参数这个特性,跟上面的Counter不一样的是,这个gen会把chan当做返回值返回,而不是作为参数传入。sq函数也跟Squarer函数不一样了:把上一个函数的chan最为参数,下一个输出的chan作为返回值。

channel扇入扇出

扇出:同一个 channel 可以被多个函数读取数据,直到channel关闭。 这种机制允许将工作负载分发到一组worker,以便更好地并行使用 CPU 和 I/O。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func main() {
c := gen(2,3)
c1 := sq(c)
c2 := sq(c)

for v := range c1 {
fmt.Println(v)
}
fmt.Println("-------------")

for v := range c2 {
fmt.Println(v)
}

}

下面是几种输出样式,可以知道当调用两次sq时,其实是对chan的扇出操作,既一个channel被多个函数读取了。每次读取的顺序和个数都不能保证。

1
2
3
4
5
6
7
8
9
10
11
12
13
#1 
4
------------------
9
#2
4
9
------------------
#3
9
4
------------------
...

扇入:多个 channel 的数据可以被同一个函数读取和处理,然后合并到一个 channel,直到所有 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 merge(cs ...<-chan int) <-chan int {
var wg sync.WaitGroup
out := make(chan int)

// Start an output goroutine for each input channel in cs. output
// copies values from c to out until c is closed, then calls wg.Done.
output := func(c <-chan int) {
for n := range c {
out <- n //对于每个chan其中的元素都放到out中
}
wg.Done() //减少一个goroutine
}
wg.Add(len(cs)) //要执行的goroutine个数
for _, c := range cs {
go output(c) //对传入的多个channel执行output
}

// Start a goroutine to close out once all the output goroutines are
// done. This must start after the wg.Add call.
go func() {
wg.Wait() //等待,直到所有goroutine都完成后
close(out) //所有的都放到out后关闭
}()
return out
}

merge函数的参数也是变长的,类型是chan, 这个函数还用到了sync这个包,这里主要的作用就是对一组goroutines进行同步。首先把传入的cs都通过output调用放入out中,每处理完一个c就调用wg.Done()更新剩余的次数, wg.Wait()等到所有的channels把数据放到out中,然后关闭out

1
2
3
4
5
6
7
8
func main() {
c := gen(2, 3, 4, 5, 6, 7, 8)
out2 := sq(c)
out1 := sq(c)
for v := range merge(out1, out2) {
fmt.Println(v)
}
}

下图就展示了扇入扇出的过程:
串联channel

goroutines控制

参考

golang的webserver是如何工作的

我们知道golang实现一个webserver非常简单,但是其内部是如何工作的呢,我们深入探究一下其原理。

实现一个webserver服务

下面我们就用golang内置的服务实现一个简单的webserver:

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
package main

import (
"fmt"
"log"
"net/http"
"strings"
)

func sayhelloName(w http.ResponseWriter, r *http.Request) {
r.ParseForm() //解析参数,默认是不会解析的
fmt.Println(r.Form) //这些信息是输出到服务器端的打印信息
fmt.Println("path", r.URL.Path)
fmt.Println("scheme", r.URL.Scheme)
fmt.Println(r.Form["url_long"])
for k, v := range r.Form {
fmt.Println("key:", k)
fmt.Println("val:", strings.Join(v, ""))
}
fmt.Fprintf(w, "Hello astaxie!") //这个写入到w的是输出到客户端的
}

func main() {
http.HandleFunc("/", sayhelloName) //设置访问的路由
http.HandleFunc("/hello", sayhelloName) //设置访问的路由
err := http.ListenAndServe(":8090", nil) //设置监听的端口
if err != nil {
log.Fatal("ListenAndServe: ", err)
}
}

我们可以通过go run main.go来开启Server服务, 当我们访问http://localhost:8090/http://localhost:8090/hello都会得到Hello astaxie!, 也就是都执行了sayhelloName函数。
下面让我们来分析一下服务的代码:
首先我们从main函数入口进入程序执行,首先执行了http.HandleFunc("/", sayhelloName)http.HandleFunc("/hello", sayhelloName)两个方法,这两个方法其实就是设置路由及其对应的处理函数。
然后执行http.ListenAndServe(":8090", nil)这个函数开始监听8090端口并把用户的请求根据之前设置的路由规则交给特定的函数进行处理。
下面我将针对这两个函数进行深入的分析。

http.HandleFunc

这个函数是net/http包中定义的, 第一个参数patternstring类型,表示匹配的URL, 第二个参数handler这是个函数类型,表示一个处理函数。其定义在net/http/server.go中,第一如下:

1
2
3
func HandleFunc(pattern string, handler func(ResponseWriter, *Request)) {
DefaultServeMux.HandleFunc(pattern, handler)
}

这个函数调用了下面这个函数:

1
2
3
func (mux *ServeMux) HandleFunc(pattern string, handler func(ResponseWriter, *Request)) {
mux.Handle(pattern, HandlerFunc(handler))
}

HandelrFunc定义如下, 声明为一个函数类型, HandlerFunc(handler)就是把handler强制类型转化为HandlerFunc类型

1
type HandlerFunc func(ResponseWriter, *Request)

mux.Handle的定义如下:

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
func (mux *ServeMux) Handle(pattern string, handler Handler) {
mux.mu.Lock()
defer mux.mu.Unlock()

if pattern == "" {
panic("http: invalid pattern " + pattern)
}
if handler == nil {
panic("http: nil handler")
}
if mux.m[pattern].explicit {
panic("http: multiple registrations for " + pattern)
}

if mux.m == nil {
mux.m = make(map[string]muxEntry)
}
mux.m[pattern] = muxEntry{explicit: true, h: handler, pattern: pattern}

if pattern[0] != '/' {
mux.hosts = true
}

// Helpful behavior:
// If pattern is /tree/, insert an implicit permanent redirect for /tree.
// It can be overridden by an explicit registration.
n := len(pattern)
if n > 0 && pattern[n-1] == '/' && !mux.m[pattern[0:n-1]].explicit {
// If pattern contains a host name, strip it and use remaining
// path for redirect.
path := pattern
if pattern[0] != '/' {
// In pattern, at least the last character is a '/', so
// strings.Index can't be -1.
path = pattern[strings.Index(pattern, "/"):]
}
url := &url.URL{Path: path}
mux.m[pattern[0:n-1]] = muxEntry{h: RedirectHandler(url.String(), StatusMovedPermanently), pattern: pattern}
}
}

可以看出这个函数会把patternhandler的对应关系读存储到mux.m这个map里了,mux类型是ServeMux,其定义如下:

1
2
3
4
5
type ServeMux struct {
mu sync.RWMutex
m map[string]muxEntry
hosts bool // whether any patterns contain hostnames
}

经过上面的处理后通过http.HandleFunc设置的patternhandler的对应关系都被存储到了DefaultServeMux这个对象的m中。

http.ListenAndServe

这个函数也是在net/http/server.go中定义的,其定义如下:

1
2
3
4
func ListenAndServe(addr string, handler Handler) error {
server := &Server{Addr: addr, Handler: handler}
return server.ListenAndServe()
}

上面函数最终对调用到下面这个函数:

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
func (srv *Server) Serve(l net.Listener) error {
defer l.Close()
if fn := testHookServerServe; fn != nil {
fn(srv, l)
}
var tempDelay time.Duration // how long to sleep on accept failure

if err := srv.setupHTTP2_Serve(); err != nil {
return err
}

srv.trackListener(l, true)
defer srv.trackListener(l, false)

baseCtx := context.Background() // base is always background, per Issue 16220
ctx := context.WithValue(baseCtx, ServerContextKey, srv)
ctx = context.WithValue(ctx, LocalAddrContextKey, l.Addr())
for {
rw, e := l.Accept()
if e != nil {
select {
case <-srv.getDoneChan():
return ErrServerClosed
default:
}
if ne, ok := e.(net.Error); ok && ne.Temporary() {
if tempDelay == 0 {
tempDelay = 5 * time.Millisecond
} else {
tempDelay *= 2
}
if max := 1 * time.Second; tempDelay > max {
tempDelay = max
}
srv.logf("http: Accept error: %v; retrying in %v", e, tempDelay)
time.Sleep(tempDelay)
continue
}
return e
}
tempDelay = 0
c := srv.newConn(rw)
c.setState(c.rwc, StateNew) // before Serve can return
go c.serve(ctx)
}
}

这里通过一个for循环不停的接收请求l.Accept()来得到接收的请求,然后再通过go c.serve(ctx)进行请求的处理。这里用到了协程,也就是每个请求其实是由单独的协程进行处理的,这也是golang作为webserver高效的原因所在。c.serve函数中有一个for循环,会不断读取同一个请求的数据,直到出现问题或者正确读取完毕。读取完请求后会调用serverHandler{c.server}.ServeHTTP(w, w.req)这个函数来处理请求。这个函数定义如下:

1
2
3
4
5
6
7
8
9
10
func (sh serverHandler) ServeHTTP(rw ResponseWriter, req *Request) {
handler := sh.srv.Handler
if handler == nil {
handler = DefaultServeMux
}
if req.RequestURI == "*" && req.Method == "OPTIONS" {
handler = globalOptionsHandler{}
}
handler.ServeHTTP(rw, req)
}

当 handler 为 nil:

可以看到当我们不在ListenAndServe中传递handler时,也就是sh.srv.Handler = nilhanlder=DefaultServeMux,这个 DefaultServeMux正式我们前面通过http.HandleFunc来设置的。 下面调用了hanlder.ServeHTTP,这里也就是调用了DefaultServeMux.ServeHTTP, 这个函数定义如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
// ServeHTTP dispatches the request to the handler whose
// pattern most closely matches the request URL.
func (mux *ServeMux) ServeHTTP(w ResponseWriter, r *Request) {
if r.RequestURI == "*" {
if r.ProtoAtLeast(1, 1) {
w.Header().Set("Connection", "close")
}
w.WriteHeader(StatusBadRequest)
return
}
h, _ := mux.Handler(r)
h.ServeHTTP(w, r)
}

这个函数中的mux.Handler从请求r中找到请求的URL然后在去mux.m的map结构中找到对应的映射关系从而得出h这个处理函数名。
由于上面说过h是转换为类型HandlerFunc, 这个类型定义的ServeHTTP函数如下:

1
2
3
4
// ServeHTTP calls f(w, r).
func (f HandlerFunc) ServeHTTP(w ResponseWriter, r *Request) {
f(w, r)
}

所以调用h.ServeHTTP(w,r)就等于调用h(w,r),也就是我们调用我们自己的写的处理函数。
这些都完成后会执行收尾工作,并把得到的结构返回给请求用户。

当 handler 不为 nil:

这时调用h.ServerHTTP(w,r)其实就是调用自己传入的handlerServerHTTP函数,例如web框架revel的源码github.com/revel/cmd/harness/harness.go中执行revel run app是就会执行下面的函数:

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
// Run the harness, which listens for requests and proxies them to the app
// server, which it runs and rebuilds as necessary.
func (h *Harness) Run() {
var paths []string
if revel.Config.BoolDefault("watch.gopath", false) {
gopaths := filepath.SplitList(build.Default.GOPATH)
paths = append(paths, gopaths...)
}
paths = append(paths, revel.CodePaths...)
watcher = revel.NewWatcher()
watcher.Listen(h, paths...)

go func() {
addr := fmt.Sprintf("%s:%d", revel.HTTPAddr, revel.HTTPPort)
revel.INFO.Printf("Listening on %s", addr)

var err error
if revel.HTTPSsl {
err = http.ListenAndServeTLS(
addr,
revel.HTTPSslCert,
revel.HTTPSslKey,
h)
} else {
err = http.ListenAndServe(addr, h)
}
if err != nil {
revel.ERROR.Fatalln("Failed to start reverse proxy:", err)
}
}()

// Kill the app on signal.
ch := make(chan os.Signal)
signal.Notify(ch, os.Interrupt, os.Kill)
<-ch
if h.app != nil {
h.app.Kill()
}
os.Exit(1)
}
```
这里也调用了`http.ListenAndServe`但是第二个参数`hanlder`传入了`h`,所以最终会调用`h.ServerHTTP`函数, 这个函数`revel`中是这么实现的:

```golang
// ServeHTTP handles all requests.
// It checks for changes to app, rebuilds if necessary, and forwards the request.
func (h *Harness) ServeHTTP(w http.ResponseWriter, r *http.Request) {
...
// Reverse proxy the request.
// (Need special code for websockets, courtesy of bradfitz)
if strings.EqualFold(r.Header.Get("Upgrade"), "websocket") {
proxyWebsocket(w, r, h.serverHost)
} else {
h.proxy.ServeHTTP(w, r)
}
}

Redis设计与实现总结——独立功能的实现

发布与订阅

通过执行SUBSCRIBE命令,客户端可以订阅一个或多个频道,从而成为这些频道的订阅者(subscriber):每当其他客户端向被订阅的频道发送消息时,频道的所有订阅者都会收到这条消息。
除了订阅频道之外,客户端还可以通过执行PSUBSCRIBE命令订阅一个或多个模式,从而成为这些模式的订阅者:每当有其他客户端祥某个频道发送消息时,消息不仅会被发送给这个频道所有订阅者,它还会被发送给所有与这个频道匹配的模式的订阅者。
Redis将所有频道的订阅管系都保存在服务器状态的pubsub_channels字典里面,这个字典的键是某个被订阅的频道,而键的值则是一个链表,链表里面记录了所有订阅这个频道的客户端。每当执行订阅命令时服务器都会将客户端与被订阅的频道着pubsub_channels字典中进行关联。如果执行退订命令,那么就会从pubsub_channels中删除这个客户端。
模式的订阅则是保存在服务器pubsub_patterns这个属性中,其操作过程与上面相同。
发送消息是就会遍历频道的pubsub_channelspubsub_patterns的客户端,将消息发送给订阅了这些频道和模式的客户端。

事务

Redis通过MULTI,EXEC,WATCH等命令来实现事务(transaction)功能。事务提供了一种将多个命令请求打包,然后一次性,按顺序地执行多个命令的机制,并且在事务执行期间(当接收到EXEC命令后才开始真正执行, 之前只是命令输入),服务器不会中断事务而改去执行其他客户端的命令请求,它会将事务中的所有命令都执行完毕,然后才去处理其他客户端的命令请求。
MULTI命令标识事务的开始,除了EXEC,DISCARD,WATCH,MULTI四个命令外的其他命令都会进入事务的队列中,当接收到EXEC命令时开始执行事务队列中的命令。
WATCH命令是一个乐观锁(optimistic locking), 它可以在EXEC命令执行之前,监视任意数量的数据库键,并在EXEC命令执行时,检查被监视的键是否至少有一个已经被修改过了,如果是的话,服务器将拒绝执行事务,并向客户端返回代表事务执行失败的回复。 (注意WATCH命令执行的顺序是在MULTI之前)。
WATCH命令执行的过程是:

  1. 将监控的键保存到watched_keys字典中,字典的值是所有监视相应数据库键的客户端。
  2. 所有对数据库进行修改的命令都会对watched_keys进行检查,如果键被修改了,就会把客户端的REDIS_DIRTY_CAS标识打开。
  3. 当接收到EXEC执行命令时,如果判断客户端的REDIS_DIRTY_CAS被打开了,标识客户端提交的事务已经不再安全,服务器拒绝客户端提交的事务。

事务的ACID性质: Redis中,事务总是具有原子性(Atomicity), 一致性(Consistency)和隔离性(Isolation),并且当Redis运行在某种特定持久化模式下时,事务也具有耐久性(Durability)

  • 事务的原子性指的是,数据库将事务中的多个操作当做一个整体来执行,服务器要么就执行事务中的所有操作,要么就一个操作也不执行。但是Redis的事务和传统的关系型数据库事务的最大区别在于,Redis不支持事务回滚机制(rollback),即事务队列中的某个命令在执行期间出现了错误,整个事务也会继续执行下去,知道将事务队列中的所有命令都执行完毕为止。
  • 事务具有一致性指的是,如果数据库在执行事务之前一致的,那么事务在执行之后,无论事务是否执行成功,数据库也应该仍然是一致的。一致指的是数据符合数据库本身的定义和要求,没有包含非法或者无效的错误数据。
  • 事务的隔离性指的是,即时数据库中有多个事务并发地执行,各个事务之间也不会相互影响,并且在并发状态下执行的事务和串行执行的事务产生的结果完全相同。因为Redis是使用单线程的方式执行事务,并且服务器保证,在执行事务期间不会对事务进行中断,因此,Redis中的事务总是以串行的方式运行的,并且事务也总是具有隔离性的。
  • 事务的耐久性指的是,当一个事务执行完毕时,执行这个事务所得的结果已经被保存到永久性存储介质里面了,即使服务器在事务执行完毕后停机,,执行事务所得的结果也不会丢失。Redis有RDBAOF两种持久化方案,但是要持久化方案要和性能进行兼顾。

Lua脚本

Redis从2.6版本开始引入对Lua脚本的支持,通过在服务器中嵌入Lua环境,Redis客户端可以使用Lua脚本,直接在服务器端原子地执行多个Redis命令。使用EVAL命令可以直接对输入的脚本进行求值,而EVALSHA命令则可以根据脚本的SHA1校验和来对脚本进行求值。
为了在Redis服务器中执行Lua脚本,Redis在服务器内嵌了一个Lua环境,并对这个Lua环境进行了一系列修改,从而确保这个Lua环境可以满足Redis服务器的需要。
Redis服务器创建并修改Lua环境的整个过程由以下步骤组成:

  1. 创建一个基础的 Lua环境(通过调用lua_open函数)
  2. 载入函数库(基础库,表格库,字符串库等), 让Lua脚本可以使用这些函数库来进行数据操作。
  3. 创建全局表格Redis,这个表格包含了对Redis进行操作的函数,比如用于在 Lua脚本中执行Redis命令的redis.call函数
  4. 使用Redis自制的随机函数来替换Lua原有的代有副作用的随机函数,从而避免在脚本中引入副作用。(关于副作用,纯函数的概念参考:wiki
  5. 创建排序辅助函数,Lua环境使用这个辅助函数来对一部分Redis命令的结果(比如集合)进行排序,从而消除这些命令的不确定性。
  6. 创建redis.pcall函数的错误报告辅助函数,这个函数可以提供更详细的出错信息。
  7. 对Lua环境中的全局环境进行保护,防止用户在执行Lua脚本过程中,将额外的全局变量添加到Lua环境中。
  8. 将完成修改的Lua环境保存到服务器状态的Lua属性中,等待执行服务器传来的Lua脚本。

除了创建并修改Lua环境之外,Redis服务器还创建了两个用于与 Lua环境进行协作的组件,它们分别是负责执行Lua脚本中的Redis命令的伪客户端,以及用于保存Lua脚本的lua_scripts字典。

  • 伪客户端: 执行Redis命令必须有响应的客户端状态,所以为了执行Lua脚本中包含的Redis命令,Redis服务器专门为Lua环境创建了一个伪客户端,并由这个伪客户端负责处理Lua脚本中包含的所有Redis命令。下图是Lua脚本执行Redis命令时的通信步骤:
    redis_lua命令执行步骤
  • lua_scirpts字典: 这个字典的键为某个Lua脚本的SHA1校验和,而字典的值则是SHA1校验和对应的Lua脚本。
    EVAL命令的执行过程可以分为以下三个步骤:
  1. 根据客户端给定的Lua脚本,在Lua环境中定义一个Lua函数。
  2. 将客户端给定的脚本保存到lua_scripts字典中,等待将来进一步使用。
  3. 执行刚刚在Lua环境中定义的函数,以此来执行客户端给定的Lua脚本。

Redis还有四个有关Lua脚本的命令:SCRIPT FLUSH, SCRIPT EXISTS, SCRIPT LOADSCRIPT KILL命令。

排序

Redis的SORT命令可以对列表建,集合键或者有序集合键的值进行排序。
SORT命令的实现原理是(以SORT numbers为例):

  1. 创建一个和要排序的对象numbers长度相同的数组,该数组的每个项都是一个redis.h/redisSortObject结构。
  2. 遍历数组,将各个数组项的obj指针分别指向numbers列表的各个项,构成obj指针和列表项之间一对一关系
  3. 遍历数组,将各个obj指针所指向的列表项转换成一个double类型的浮点数,并将这个浮点数保存在相应数组项的u.score属性里面
  4. 根据数组项u.score属性的值,对数组进行数字值排序(快速排序算法),排序后的数组项按u.score属性的值从小到大排列
  5. 遍历数组,将各个数组项的obj指针所指向的列表项作为排序结果返回给客户端。

其他的排序方式,比如按照字母顺序排列,降序排列,通过外部键进行排序等原理都差不多,变化的是排列的顺序,排列的依据u.score不一样。
更多SORT命令的具体使用和参数可以参考文档:Redis SORT命令

二进制位数组

Redis提供了SETBIT,GETBIT, BITCOUNT, BITOP四个命令用于处理二进制位数组(bit array, 又称为”位数组”)
Redis使用字符串对象来表示位数组,因为字符串对象使用的SDS数据结构是二进制安全的,所以程序可以直接使用SDS结构来保存位数组,并使用SDS结构的操作函数来处理位数组。
具体使用方法参考官方文档。

慢查询日志

Redis的慢查询日志功能用于记录执行时间超过给定时长的命令请求,用户可以通过这个功能产生的日志来监视和优化查询速度。
服务器有两个和慢查询有关的选项:

  • slowlog-log-slower-than选项执行执行时间超过多少微秒的命令请求会被记录到日志上。(可以通过CONFIG SET slowlog-log-slower-than N设置)
  • slowlog-max-len选项执行服务器最多保存多少条慢查询日志。(可以通过CONFIG SET slowlog-max-len N设置)

使用SLOWLOG GET命令可以查看服务器所保存的慢查询日志, 使用SLOWLOG LEN可以查看当前日志的数量。

监视器

通过执行MONITOR命令,客户端可以将自己变为一个监视器,实时地接收并打印服务器当前处理的命令请求的相关信息。当一个客户端使用MONITOR向服务器发送命令时,这个客户端的REDIS_MONITOR标识会被打开,并且客户端本身会被服务器添加到monitors链表的表尾。当服务器每次接收到请求时(处理命令之前), 都会调用replicationFeedMonitors函数,由这个函数将被处理的命令请求的相关信息发送给各个监视器。

Redis设计与实现总结——多机数据库的实现

复制

在Redis中用户可以通过执行SLAVEOF命令或者设置slaveof选项,让一个服务器去复制(repliacte)另一个服务器,被复制的服务器称为主服务器(master),而对服务器进行复制的服务器被称为从服务器(salve)。
复制功能分为同步(sync)和命令传播(command propagate)两个操作:

  • 同步操作用于将从服务器的数据库状态更新至主服务器当前所处的数据库状态。(从服务器主动向主服务器请求数据)
  • 命令传播操作用于在主服务器的数据库状态被修改,导致主从服务器数据库状态出现不一致时,让主服务器的数据库重新回到一致状态。

redis旧版复制

  • 同步过程:
    • 主服务器接收到从服务器发来的SYNC命令,执行BGSAVE命令,创建RDB文件,并使用缓冲区记录接下来执行的所有写命令。
    • 从服务器接收并载入主服务器发来的RDB文件。
    • 主服务器接着发送缓冲区的写命令到从服务器。
    • 从服务器接收命令。
  • 命令传播:
    每当主服务器执行写命令时,主服务器的数据库状态就可能被修改,并导致主从服务器不一致。为了再次回到一致状态,主服务器需要对从服务器执行命令传播操作: 主服务器会将自己执行的写命令发送给从服务器执行,当从服务器执行了相同的写命令后,主从服务器再次回到一致状态。

从服务器初次复制主服务器或者从服务器当前要复制的主服务器和上一次不一样时,RDB文件会完整的传输。在处于命令传播阶段的主从服务器因为网络原因而中断了复制,再次连接上时会重头开始复制。但是第二种情况的效率非常低,很多已经复制过的数据需要再次进行复制。这就是旧版复制功能的缺陷。
新版复制功能为了解决重复复制的问题,提出了一个PSYNC命令代替之前的SYNC命令。完整的复制与上面的第一种情况初次复制是一样的,部分重同步则用于处理断线后的情况: 断线再连接后,主服务器只发送断线期间的写命令到从服务器。
部分重同步的实现是通过复制偏移量:

  • 主服务器每次向从服务器转播N个字节的数据时,就将自己的复制偏移量的值+N
  • 从服务器每次收到主服务器传播来的N个字节数据时,就将自己的复制偏移量的值+N

通过对比主从服务器的复制偏移量,程序可以很容易地知道主从服务器是否处于一致状态:

  • 如果主从服务器处于一致状态,那么主从服务器两者的偏移量总是相同的
  • 相反,如果主从服务器两者的偏移量并不相同,那么说明主从服务器并未处于一致状态

复制积压缓冲区是一个由主服务器维护的固定长度,先进先出队列,默认大小为1MB。当主从断开连接,再次连接时,从服务器会通过PSYNC将自己的复制偏移量offset发送给主服务器:

  • 如果offset偏移量之后的数据存在于复制积压缓冲区,那么主服务器将对从服务器执行部分重同步操作。
  • 如果offset偏移量之后的数据已经不存在于复制积压缓冲区,那么主服务器会对从服务器执行完整重同步操作。

在命令传播阶段,从服务器默认会以每秒一次的频率,祥主服务器发送命令REPLICONF ACK <replication_offset>, 其中replication_offset是当前从服务器的复制偏移量, 这个心跳检测的作用如下:

  • 检测主从服务器的网络状态:如果主服务器超过一秒钟没收到从服务器发送的REPLICONF ACK命令,那么主服务器就知道主从服务器之间的连接出现问题了。
  • 辅助实现min-slaves选项:Redis的min-slaves-to-writemin-slaves-max-log两个选项可以防止主服务器在不安全的情况下执行写命令。
  • 检测命令丢失:如果因为网络故障,主服务器传播给从服务器的写命令半路丢失,那么从服务器发送的偏移量就会小于主服务器的偏移量,这时候主服务器会从复制积压缓冲区中重新把命令发送给从服务器。(2.8版本之前没有这个功能,所以会出现丢失的情况)

Sentinel

Sentinel(哨岗,哨兵)是Redsi的高可用性(high availability)解决方案:由一个或多个Sentinel实例(instance)组成的Sentinel系统可以监视任意多个主服务器,以及这些主服务器属下的所有从服务器,并在被监视的主服务器进入下线状态时,自动将下线的主服务器属下的某个从服务器升级为新的主服务器,然后由新的主服务器代替已下线的主服务器继续处理命令请求。另外Sentinel还会继续监视已下线的服务器,并在它重新上时,将它设置为新的主服务器的从服务器(降级)。
启动Sentinel可以使用命令: redis-sentinel /path/to/your/sentinel.confredis-server /path/to/your/sentinel.conf --sentinel, 启动时需要执行一下步骤:

  • 初始化服务器: Sentinel本质上是一个运行在特殊模式下的Redis服务器,启动初始换与原来有所不同。
  • 将普通Redis服务器使用的代码替换成Sentinel专用代码:初始换Sentinel可以执行的命令,替换之前的默认命令。
  • 初始化Sentinel状态:初始化sentinel.c/sentinelState结构,这个结构保存了服务器中所有Sentinel相关的状态。
  • 根据跟定的配置文件,初始化Sentinel的监视主服务器列表:Sentinel状态中的masters字典记录了所有被Sentinel监视的主服务器的相关信息,其中字典的键是被监视主服务器的名字;而字典的值则是被监视主服务器对应的sentinel.c/sentinelRedisInstance结构。
  • 创建连向主服务器的网络连接: 最后一步是创建连向被监视主服务器的网络连接,Sentinel将成为主服务器的客户端,可以向主服务器发送命令,并从命令回复中获取相关的信息。对于每个被Sentinel监视的主服务器来说,Sentinel会创建两个连向主服务器的异步网络连接:
    • 一个是命令连接,这个连接专门用于向主服务器发送命令,并接收命令回复。
    • 另一个是订阅连接,这个链接专门用于订阅主服务器的__sentinel__:hello频道。

为什么有两个连接?
在Redis目前的发布与订阅功能中,被发送的信息不回保存在Redis服务器里,如果发送信息时,接收信息的客户端不在线或者断线,那么这个客户端就会丢失这条信息。为了不丢失任何信息,必须专门用一个订阅连接来接收该频道的信息(原理?)。另外除了订阅频道,Sentinel还必须向主服务器发送命令,以此来与主服务器进行通信,所以Sentinel还必须向主服务器创建命令连接。

Sentinel网络拓扑

Sentinel与主服务器,从服务器及其他Sentinel之间都是彼此连接的:

  • 首先Sentinel默认每10秒一次向主服务器发送INFO命令,Sentinel可以得到主服务器信息以及主服务器的从服务器信息;
  • Sentinel会更新自己的主服务器和从服务器信息,还会创建连接到从服务器的命令连接和订阅连接。
  • Sentinel还会默认每2秒一次通过命令连接向所有被监视的主服务器和从服务器发送命令,这条命令会向服务器的__sentinel__:hello频道发送一条信息
  • 由于Sentinel订阅了主服务器和从服务器的消息,所以所有订阅的Sentinel都会收到上面的信息,接收消息的Sentinel就会感知到发消息的Sentinel存在,并记录到sentinels属性中(可以实现自动发现功能)

故障处理

检测主观下线状态

默认情况下Sentinel会以每秒一次的频率向所有与它创建了命令连接的实例(包括主服务器,从服务器,其他Sentinel等)发送PING命令, 并通过实例返回的PING命令回复判断是否在线。由于每个Sentinel设置的下线时间标准可能不一样,所以会出现不同的Sentinel认为服务器的状态不一致,所以这种情况称为主观下线状态。

检测客观下线状态

当Sentinel从其他Sentinel那里接收的足够数量的已下线判断之后,Sentinel就会认为将主服务器判定为客观下线状态,并对主服务器执行故障转移操作。

选举领头Sentinel

当主服务器被判断为客观下线时,监视这个下线主服务器的各个Sentinel会进行协商,选举出一个领头的Sentinel,并由领头Sentinel对下线服务器执行故障转移。
选举策略是每个检测到主服务器下线的Sentinel都向其他Sentinel发送想要成为领头的命令,收到命令的Sentinel会将发送命令的Sentinel设置为局部领头,如果一个Sentinel被半数以上的Sentinel设置为局部领头,它就胜出,否则会进行再次选举。

故障转移

选举出领头Sentinel后,领头Sentinel将对已下线的主服务器执行故障转移操作:

  • 在已下线服务器属下的所有从服务器里面,挑选出一个从服务器,并将其转换为主服务器: 选择优先级高,复制偏移量大的从服务器,使用命令SLAVE of one使其变为主服务器。
  • 让已下线主服务器属下的所有从服务器改为复制新的主服务器: 领头Sentinel向其他从服务器发送SLAVEOF命令。
  • 将已下线的主服务器设置为心的主服务器的从服务器,当这个旧的主服务器重新上线时,它就会成为新的主服务器的从服务器。

集群

Redis集群是Redis提供的分布式数据库方案,集群通过分片(sharding)来进行数据共享,并提供复制和故障转移功能。

节点与槽

Redis集群通常由多个节点(node)组成,开始每个节点都是图例的,它们都处于一个只包含自己的集群中,当要组建一个真正可工作的集群,我们必须将节点连接起来,构成一个包含多个节点的集群。使用CLUSTER MEET <ip> <port>命令来完成。另外Redis服务器启动时也可以根据cluster-enabled配置选项来判断是否开启集群模式。节点信息保存在cluster.h/clusterNode结构中,clusterNode结构保存了一个节点的当前状态,比如节点的创建时间,节点的名等;clusterNodelink属性是一个clusterLink结构,该结构保存了连接节点所需的有关信息,比如套接字描述符,输入缓冲区和输出缓冲区; 每个节点都保存着一个clusterState结构,这个结构记录了当前节点的视角下,集群目前所处的状态,例如机器是在线还是下线,集群包含多少节点等。
Redis集群通过分片的方式来保存数据库中的键值对:集群的整个数据库被分为16384(=2048*8)个槽(slot),数据库中的每个键都属于这16384个槽的其中一个,集群中的每个节点可以处理0个或最多16384个槽。当数据库中的16384个槽有节点在处理时,集群处于一个上线状态(ok);相反地,如果数据库中任何一个槽没有得到处理,那么集群处于下线状态(fail)。
槽指派信息记录在clusterNode.slots[16384/8]属性中, numslots记录了节点负责处理的槽的数量。Redis以0为起始索引,16383为终止索引,对slots数组中的16384个二进制位进行编号,并根据索引i上的二进制位来判断节点是否负责处理槽i:

  • 如果slots数组在索引i上的二进制位值为1,那么表示节点负责处理槽i。
  • 如果slots数组在索引i上的二进制位值为0, 那么表示节点不负责处理槽i。

节点会把自己处理的槽信息发送给其他集群中的其他节点,因此集群中的每个节点都会知道数据库中16384个槽分别被指派给了集群中哪些节点。
clusterState结构中的slots[16384]数组则更上面的正好反过来,它记录了每个槽是由哪个节点在管理的。之所以会有这两种结构是为了在查找节点管理了哪些槽和槽由哪个节点管理的复杂度都降低了。

集群中的执行命令

当客户端向节点发送与数据库键有关的命令时,接收命令的节点会计算出命令要处理的数据库键属于哪个槽(使用crc16(key)&16383算法得出槽位置),并检查这个槽是否指派给了自己(clusterState.slots[i]是否为自己):

  • 如果键所在的槽正好指派给了当前节点,那么节点直接执行这个命令。
  • 如果键所在的槽没有指派给了当前节点,那么节点回向客户端返回一个MOVED错误,指引客户端转向(redirect)至正确的节点,并再次发送之前想要执行的命令。

节点与单机服务器在数据库方面的区别是,节点只能使用0号数据库,而单机Redis服务器则没有这一限制。
节点还会使用clusterState结构中的slots_to_keys跳跃表来保存槽和键之间的关系,主要目的是方便节点对属于某个或某些槽的所有数据库键进行批量操作。

重新分片

Redis集群的重新分片操作可以将任意数量已经指派给某个节点(源节点)的槽改为指派给另一个节点(目的节点),并且相关槽所属的键值对也会从源节点移动到目的节点。这个过程可以在线进行,在重新分片过程中,集群不需要下线,并且源节点和目的节点都可以继续处理命令请求。
Redis的重新分片操作是由Redis的集群管理软件redis-trib负责执行的。迁移过程如下:
redis-trib
在执行第四步迁移的过程中,如果客户端向源节点发送一个与数据库键有关的命令,那么:

  • 源节点先在自己数据库里查找指定的键,如果找到就直接执行客户端发送的命令.
  • 如果没找到,那么这个键可能已经被迁移到了目标节点,源节点向客户端返回一个ASK错误,指引客户端转向正在导入槽的目的节点,并再次发送之前想要执行的命令。
    当客户端接收到ASK错误并转向正在执行导入槽节点时,客户端会先向节点发送一个ASKING命令,然后才重新发送想要执行的命令。ASKING命令会打开发送客户端的REDIS_ASKING标识。
    一般情况下如果客户端向节点发送一个关于槽i的命令,如果节点没有这个槽,那么就会返回MOVED,但是如果节点的clusterState.importing_slots_from[i]显示节点正在导入槽i,并且发送命令的客户端带有REDIS_ASKING(通过ASKING命令打开)标识,那么节点将执行这个关于槽i的命令一次

关于ASK错误与MOVED错误的区别:

  • MOVED错误代表槽的负责权已经从一个节点转移到了另一个节点,客户端收到关于槽i的MOVED错误后,每次遇到槽i请求是,都可以直接将命令发送至MOVED错误所指向的节点。
  • ASK错误只是两个节点在迁移槽的过程中使用的一种临时措施, 不会影响后面命令的发送。

复制与故障转移

Redis集群中的节点分为主节点(master)和从节点(slave),其中主节点用于处理槽,而从节点则用于复制某个主节点,并在被复制的主节点下线时,代替下线主节点继续处理命令请求。设置从节点的命令:CLUSTER REPLICATE <node_id>
集群中的每个节点都会定期地祥集群中其他节点发送PING消息,以此来检测对方是否在线,如果接收PING消息的节点没有在规定时间内,向发送PING消息的节点返回PONG消息,那么发送PING消息的节点就会将接收PING消息的节点标记位疑似下线(probable fail, PFAIL)。如果一个集群里,半数以上负责处理槽的主节点都将某个主节点X报告为疑似下线,那么这个主节点X将被标记为已下线(FAIL), 将主节点X标记为已下线的节点会向集群广播一条关于主节点X的FAIL消息,所有收到这条FAIL消息的节点都会立即将主节点X标记为下线。
当一个从节点发现自己正在复制的主节点进入了已下线状态,从节点将开始对下线主节点进行故障转移,下面是故障转移执行的步骤:

  1. 复制下线主节点的所有从节点里面,会有一个从节点被选中:选举过程和Sentinel差不多。
  2. 被选中的从节点会执行SLAVEOF no one命令,成为新的主节点
  3. 新的主节点会撤销所有对已下线主节点的槽指派,并将这些槽全部指派给自己
  4. 新的主节点向集群广播一条PONG消息,可以让集群中其他节点立即知道这个节点从从节点变为了主节点,并且这个主节点已经接管了原本由已下线主节点负责处理的槽。
  5. 新的主节点开始接收和自己负责处理的槽有关的命令请求,故障转移完成。

总结

前面主要讲了Redis在多机数据库下的功能特性,其中复制是实现数据备份,数据可靠性的保证。Sentinel实现高可用性的保证。在3.0版本之前的分布式方案都是自己实现的,然后利用Sentinel进行监控。后来Redis自己实现了集群方案,可以用其默认的集群方案来代替之前的自己实现方案。他们之间是相辅相成的,根据自己的需要进行选择。

参考

  1. Redis集群方案应该怎么做?
  2. 如何部署高可用的Redis集群架构

Redis设计与实现总结——单机数据库的实现

数据库

一个Redis Server可以有多个Redis数据库,这点类似于MySQL, 从Redis Server的源代码中可以看到,redisDb是Server数据库的指针,指向一个数据库组成的数组,而数据库的数量则由dbnum属性来表示。客户端可以通过SELECT命令选择当前要操作的数据库。

1
2
3
4
5
6
7
8
9
10
11
12
struct redisServer {

// ...

// 数据库数组指针
redisDb *db;

// 服务器的数据库数量
int dbnum;

// ...
}

数据库的定义在redis.h/redisDb中,定义如下:

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
typedef struct redisDb {

// 数据库键空间,保存着数据库中的所有键值对
dict *dict; /* The keyspace for this DB */

// 键的过期时间,字典的键为键,字典的值为过期事件 UNIX 时间戳
dict *expires; /* Timeout of keys with a timeout set */

// 正处于阻塞状态的键
dict *blocking_keys; /* Keys with clients waiting for data (BLPOP) */

// 可以解除阻塞的键
dict *ready_keys; /* Blocked keys that received a PUSH */

// 正在被 WATCH 命令监视的键
dict *watched_keys; /* WATCHED keys for MULTI/EXEC CAS */

struct evictionPoolEntry *eviction_pool; /* Eviction pool of keys */

// 数据库号码
int id; /* Database ID */

// 数据库的键的平均 TTL ,统计信息
long long avg_ttl; /* Average TTL, just for stats */

} redisDb;

  • dict: 是一个字典,保存了数据库中的所有键值对,我们将这个字典称为键空间(key space)。
  • expires: 也是一个字典,保存的是键值与这个键值过期时间的键值对。

一个简化的结构图如下:
db结构
设置生存时间和过期时间时,最终都是计算出最后生存时间,然后把这个值存入expires字典中。过期字典中找不到证明没有设置过期时间。过期删除策略Redis主要是使用惰性删除策略与定期删除两种策略。所谓惰性删除策略就是当用户获取键时,先判断其是否过期,如果过期则删除键,返回失败,如果没过期则正常返回。定期删除策略是Redis会周期行的从过期字典中随机出一部分键值,如果过期则删除键,否则保留。

持久化

RDB持久化

RDB(redis database)持久化既可以手动执行,也可以根据服务器配置选项定期执行,该功能可以将某个时间点上的数据库状态保存到一个RDB文件中(RDB文件默认的文件名为dump.rdb)。RDB持久化功能锁生成的RDB文件是一个经过压缩的二进制文件,通过该文件还可以还原生成RDB文件时的数据库状态。
有两个Redis命令可以用于生成RDB文件,一个是SAVE, 另一个是BGSAVESAVE会阻塞Redis服务进程,知道RDB文件创建完毕为止,在服务器进程阻塞期间,服务器不能处理任何请求。BGSAVE命令会派生出一个子进程,然后由子进程负责创建RDB文件,服务器进程(父进程)继续处理命令请求。
RDB文件是在服务器启动时自动执行的,只要Redis服务器启动时检测到RDB文件存在,它就会自动载入RDB文件。但是如果服务器开启了AOF持久化功能,就会优先使用AOF文件。因为AOF文件的更新频率通常比RDB文件高,所以数据是最新的可能性高。
用户可以通过save选项设置多个保存条件,但只要其中任意一条被满足,服务器就会执行BGSAVE命令。例如配置为下面三个:

1
2
3
save 900 1
save 300 10
save 60 10000

只要满足900s内至少一次修改,或300s内至少10次修改,或60s内10000次修改就会自动执行BGSAVE命令。
服务器维护一个dirty计数器,用于记录距离上次成功执行SAVEBGSAVE命令之后,服务器对数据库状态进行了多少次修改(包括写入,删除,更新等操作)。
服务器还维护一个lastsave属性,记录服务器上一次成功执行SAVEBGSAVE命令的时间。
RDB文件结构:

1
2
3
4
5
+-----+----------+---------+---+---------+
| | | | | |
|REDIS|db_version|databases|EOF|check_sum|
| | | | | |
+-----+----------+---------+---+---------+

  • REDIS: RDB文件开头是REDIS部分,这个部分长度为5字节,保存着”REDIS”五个字符。通过五个字符,快速检测是否为RDB文件。
  • db_version: 长度为4字节,它的值是一个字符串表示的整数,记录了RDB文件的版本号。
  • databases: 包含着零个或任意多个数据库,以及各个数据库中的键值对数据。
  • EOF: 长度为1字节,这个常量标志着RDB文件正文内容的结束,当读入程序遇到这个值的时候,它知道所有数据库的所有键值对都已经载入完毕。
  • check_sum: 8字节长的无符号整数,保存着一个校验和,这个校验和是程序通过对前面四部分的内容计算得出的。服务器载入RDB文件时,会将载入数据所计算出的校验和与check_sum所记录的检验和进行对比,以此来检查RDB文件是否出错或者有损坏的情况。
    可以使用od -c dump.rdbod -cx dump.rdb命令来对RDB文件内容进行分析。

AOF持久化

AOF(Append Only File)持久化功能是通过保存Redis服务器所执行的写命令来记录数据库状态的。AOF持久化功能的实现可以分为命令追加(append), 文件写入,文件同步(sync)三个步骤:

  • 命令追加: 服务器执行完一个写命令后,会以协议格式将被执行的写命令追加到服务器状态的aof_buf缓冲区的末尾。
  • AOF文件的写入与同步: 服务器的每次时间循环结束之前,都会调用flushAppendOnlyFile函数,考虑是否需要将aof_buf缓冲区中的内容写入和保存到AOF文件里。
    flushAppendOnlyFile函数的行为由服务器配置的appendfsync选项的值来决定:
appendfsync选项的值 flushAppendOnlyFile函数的行为 影响
always 将aof_buf缓冲区中的所有内容写入并同步到AOF文件 性能最低,但是安全性最高,发生故障停机最多丢失一个循环事件所产生的在缓冲区中的命令
everysec(默认值) 将aof_buf缓冲区中的所有内容写入到AOF文件,如果上次同步AOF文件的时间距离现在超过1s,那么再次对AOF文件进行同步,并且这个同步操作是由一个线程专门负责执行的 性能足够快,并且出现故障停机,最多丢失一秒钟的命令数据
no 将aof_buf缓冲区中的所有内容写入到AOF文件,但并不对AOF文件进行同步,何时同步由操作系统决定 性能最好,写入AOF速度最快,但是单次同步时间最长,出现故障丢失的命令最多

由于AOF文件记录了重建数据库所需的所有写命令,所以服务器只要读入并执行一遍AOF文件里么保持的写命令,就可以还原服务器关闭之前的状态。
由于AOF持久化是通过保存被执行的写命令来记录数据库状态的,随着时间的推移,写命令越来越多,这时候就需要AOF重写来减轻文件体积的膨胀。
AOF重写首先从数据库中读取键现在的值,然后用一条命令去记录键值对,代替之前记录的这个键值对的多条命令。但是在重写列表,哈希表,集合,有序集合等多个元素的键时,如果元素的数量超过了redis/REDIS_AOF_REWRITE_ITEMS_PER_CMD常量的值,会通过多条命令来记录键的值。
一个问题是在AOF重写期间,服务器还需要处理命令请求,而新的命令可能会对现有的数据库状态进行修改,从而使得服务器当前的数据库状态和重写后的AOF文件所保存的数据库状态不一致。为了解决这个问题,Redis服务器设置了一个AOF重写缓冲区,这个缓冲区在服务器创建子进程进行重写是开始使用,当Redis服务器执行完一个写命令后,它会同事将这个命令发送给AOF缓冲区和AOF重写缓冲区。当AOF重写工作完成后,向父进程发送信号,父进程就会将AOF重写缓冲区中的所有内容写到新的AOF文件中,对新的AOF文件进行改名,原子地 (atomic)覆盖现有的AOF文件,完成新旧两个AOF文件的替换。

事件

文件事件

文件事件(file event): Redis服务器通过套接字与客户端(或其他Redis服务器)进行连接,而文件事件就是服务器对套接字操作的抽象。服务器与客户端(或其他服务器)的通信会产生相应的文件事件,而服务器则通过监听并处理这些事件来完成一系列网络通信操作。
下图是Redis自己实现的文件事件处理器的四个组成部分:
db结构

  • 文件事件处理器使用I/O多路复用(multiplexing)程序来同时监听多个套接字,并根据套接字目前执行的任务来为套接字关联不同的事件处理器。
  • 当被监听的套接字准备好执行连接应答(accept),读取(read),写入(write),关闭(close)等操作时,与操作相对应的文件事件就会产生,这时文件事件处理器就会调用套接字之前关联好的事件处理器来处理这些事件。

虽然文件事件处理器以单线程方式运行,但通过使用I/O多路复用程序来监听多个套接字,文件事件处理器既实现了高性能的网络通信模型,又可以很好地与Redis服务器中其他同样以单线程方式运行的模块进行对接,着保持了Redis内部单线程设计的简单性。
尽管多个文件事件可能会并发地出现,但I/O多路复用程序总会将所有产生事件的套接字都放在一个队列里,然后通过这个队列,以有序(sequentially),同步(synchronously),每次一个套接字的方式向文件事件分派器传送套接字。
Redis的I/O多路复用程序的所有功能都是通过包装常见的select,epoll,evportkqueue这些I/O多路复用函数库来实现的,编译时会自动选择性能高最高的I/O多路复用函数库来作为Redis的I/O多路复用程序的底层实现。

时间事件

时间事件(time event): Redis服务器中的一些操作(如serverCron函数)需要在给定的时间点执行,而时间事件就是服务器对这类定时操作的抽象。
Redis的时间事件分为两类:

  • 定时事件: 让程序在指定的时间之后执行一次。
  • 周期性事件: 让一端程序每隔指定的时间就执行一次。

一个时间事件主要由以下三个属性:

  • id: 服务器为时间事件创建的全局唯一ID(标识号)。ID号按从小到大的顺序递增,新事件的ID号比旧事件的ID号要大。
  • when: 毫秒精度的UNIX时间戳,记录了时间事件的到达(arrive)时间。
  • timeProc: 时间事件处理器,一个函数。当时间事件到达时,服务器就会调用响应的处理器来处理事件。

一个时间事件是定时事件还是周期性事件取决于时间事件处理器的返回值:

  • 如果事件处理器返回ae.h/AE_NOMORE,那么这个事件为定时事件:该事件在达到一次之后就会被删除,之后不再到达。
  • 如果事件处理器返回一个非AE_NOMORE的整数值,那么这个事件为周期性时间:当一个时间事件到达之后,服务器会根据事件处理器返回的值,对时间事件的when属性进行更新,让这个事件在一段时间后再次到达,并以这种方式一直更新运行下去。

服务器将所有时间事件都放在一个无序链表中,每当时间事件执行器运行时,它就遍历整个链表,查找所有已到达的时间事件,并调用相应的事件处理器。

事件的调度与执行

事件的调度和执行由ae.c/aeProcessEvents函数负责,下面是这个函数的伪代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def aeProcessEvents():

// 获取到达时间离当前最接近的时间事件
time_event = aeSearchNearestTimer()

// 计算最接近的时间事件距离到达还有多少毫秒
remaind_ms = time_event.when - unix_ts_now()

// 如果事件已到达,那么remaind_ms的值就可能为负数,将它设定为0
if remaind_ms < 0:
remaind_ms = 0

// 根据remaind_ms的值,创建timeval结构
timeval = create_timeval_with_ms(remaind_ms)

// 阻塞并等待文件事件产生,最大阻塞时间由传入的timeval结构决定
// 如果remaind_ms的值为0,那么aeApiPoll调用之后马上返回,不阻塞
aeApiPoll(timeval)

// 处理所有已产生的文件事件
processFileEvents()

// 处理所有已到达的时间事件
processTimeEvents()

事件的调度和执行规则:

  1. aeApiPoll函数的最大阻塞时间由到达时间最接近的当前时间的时间事件决定,这个方法既可以避免服务器对时间事件并行频繁的轮询,可以确保aeApiPoll函数不会阻塞时间过长。
  2. 因为文件事件是随机出现的,如果处理完文件事件后时间事件仍未到达,继续等待并处理下一个文件事件。
  3. 对文件事件和时间事件的处理都是同步,有序,原子地执行的,服务器不会中途中断事件处理,也不会对事件进行抢占。因此耗时的事件会影响整个服务的性能。
  4. 因为时间事件是在文件事件之后执行,并且事件之间不会抢占,所以时间事件的实际处理时间通常回避时间事件设定的到达时间稍微晚一些。

客户端

通过使用I/O多路复用技术实现的文件事件处理器,Redis服务器使用单线程单进程的方式来处理命令请求,并与多个客户端进行网络通信。
关于redisClient的定义可以从redis.h中看到,客户端有很多属性。这些属性可以分为两类:

  • 比较通用的属性,这些属性很少特定功能相关,无论客户端执行的是什么工作,它都需要这些属性。
  • 和特定功能相关的属性。下重点介绍这些。

属性

  • fd(fake client): 伪客户端的fd属性的值为-1,伪客户端处理的命令请求来自于AOF文件或者lua脚本; 普通客户端fd属性值是大于-1的整数,使用套接字与服务器通信,所以fd用来记录客户端套接字的描述符。
  • name: 默认情况下一个连接到服务器的客户端是没有名字的,但是可以使用CLIENT setnaem命令设置一个名字,可以通过CLIENT list查看。
  • flags: 一部分标志记录了客户端的角色(如REDIS_MASTER代表主服务器, REDIS_SLAVE代表从服务器), 另一部分标志记录了客户端目前所处的状态(REDIS_MONITOR正在执行monitor, REDIS_MULTI标志客户端正在执行事务)。
  • querybuf: 用于保存客户端发送的命令请求。输入缓冲区的大小会根据输入内容动态调整,但是最大不能超过1GB,否则服务器将关闭这个客户端。
  • argvargc: 服务器将客户端发送的名保存到querybuf后,对命令内容进行分析,得出命令参数及命令的参数个数分别保存到argvargc中。
  • authenticated: 记录客户端是否通过了身份验证,未通过用0表示,通过用1表示。
  • ctime: 记录创建客户端的时间。
  • lastinteraction: 记录客户端与服务器最后一次进行互动的时间。
  • obuf_soft_limit_reached_time: 记录输出缓冲区第一次到达软性显示的时间。

执行命令所得的命令回复会被保存到客户端状态的输出缓冲区里,每个客户端都有两个输出缓冲区可用

  • bufbufpos: 固定的换缓冲区,用于保存那些长度比较小的回复,如:OK, 简短的字符串值,整数值或错误回复等。buf是缓冲区,bufpos记录buf数组目前已经使用的字节数量。
  • reply: 可变大小的缓冲区是一个链表,用于保存比较大的回复,比如一个非常长的字符串值,列表等。

创建与关闭

  • 创建不同客户端: 如果客户端是通过网络连接与服务器进行连接的普通客户端,那么在客户端connect函数连接到服务器时,服务器就会调用连接事件处理器为客户端创建响应的客户端状态,并将这个新的客户端状态添加到服务器状态结构clients链表的末尾。
  • 关闭客户端: 一个普通客户端被关闭的原因有很多:
    • 客户端进程退出或被杀死
    • 客户端向服务器发送了带有不符合协议格式的命令请求
    • 客户端成了CLIENT KILL命令的目标
    • 用户为服务器设置了timeout配置选项,客户端空转时间超过timeout选项设置的值
    • 客户端发送的命令请求大小超过了输入缓冲区的限制大小(1GB)
    • 发送给客户端的命令回复超过输出缓冲区的限制大小。按理说输出缓冲区是没有大小限制的,但是为了防止过多占用服务器资源,采用硬性限制和软性限制两种方案限制大小。
  • Lua脚本的伪客户端: 服务器在初始化时负责创建Lua脚本中包含的Redis命令的伪客户端,在服务器运行的整个周期中都会存在。
  • AOF文件的伪客户端: 服务器载入AOF文件时,会创建用于执行AOF文件包含的Redis命令的伪客户端,并在载入完成后关闭。

服务器

命令请求的执行过程

前面讲了,客户端发送的请求会被放到输入缓冲区,然后服务器对命令进行解析,转换成协议格式,服务器将通过调用命令执行器来完成余下的步骤:

  • 查找命令
    根据上面说的argv[0]参数中对应的命令在命令表中查找参数所指定的命令,并将找到的命令保存到客户端状态的cmd属性里。
    命令表是一个字典,字典的键是一个个命令名字,比如”set”,”get”,”del”等;而字典的值则是一个个redisCommand结构,每个redisCommand结构记录了一个Redis命令的实现信息。

redisCommand结构的主要属性:

属性名 类型 作用
name char * 命令的名字,比如”set”
proc redisCommandProc * 函数指针,指向命令的实现函数
arity int 命令参数的个数,用于检查命令请求的格式是否正确
sflags char * 字符串形式的标识值,这个值记录了命令的属性
例如:
w:表示写入命令
r:只读命令
m:可能会占用大量内存的命令
a:这是一个管理命令
flags int 对sflags标识进行分析得出的二进制标识,由程序自动生成
calls long long 服务器总共执行了多少次这个命令
milliseconds long long 服务器执行这个民两个所耗费的总时长
  • 执行预备操作
    到目前为止,服务器已经将执行命令所需的命令实现函数,参数等都收集齐了,真正执行命令之前还需要一些预备操作:

    • 检查客户端状态的cmd指针是否执行NULL
    • 检查命令请求所给定的参数个数是否正确
    • 检查客户端是否已经通过了身份验证
    • 如果服务器打开了maxmemory功能,需要检查服务器的内存占用情况,在有需要的时候进行内存回收
    • 其他检查和限制执行的操作等
  • 调用命令的实现函数
    当服务器决定要执行命令是client->cmd->proc(client);, 执行函数后会把回复保存到客户端的输出缓冲区,之后实现函数还会为客户端的套接字关联命令回复处理器,这个处理器负责将回复返回给客户端。

  • 执行后续工作
    在执行完实现函数后,服务器还需要执行一些后续工作:
    • 如果服务器开启了慢查询日志功能,那么慢查询日志模块会坚持是否需要为刚刚执行完的命令请求添加一条新的慢查询日志。
    • 根据刚刚执行命令所耗费的时长,更被执行命令redisCommand结构的milliseconds属性,并将calls计数器加一
    • 如果服务器开启了AOF持久化功能,那么AOF持久化模块会将刚刚执行的命令请求写入到AOF缓冲区里。
    • 如果有其他从服务器正在复制当前这个服务器,那么服务器会将刚刚执行的命令传播给所有从服务器
    • 根据刚刚执行命令所耗费的时长,更被执行命令redisCommand结构的milliseconds属性,并将calls计数器加一
    • 如果服务器开启了AOF持久化功能,那么AOF持久化模块会将刚刚执行的命令请求写入到AOF缓冲区里。
    • 如果有其他从服务器正在复制当前这个服务器,那么服务器会将刚刚执行的命令传播给所有从服务器。

回复发送完毕后,回复处理器会清空客户端状态的输出缓冲区,未处理下一个命令请求做好准备。当客户端接收到协议格式的命令回复后,它会将这些回复转换成人类可读的格式,并打印给用户观看。

serverCron函数

Redis服务器中的serverCron函数默认每隔100毫秒执行一次,这个函数负责管理服务器的资源,并保持服务器自身的良好运转。serverCron的函数主要功能如下面所列:

  • 更新服务器时间缓存: 为了减少获取服务器时间而进行系统调用的次数,服务器状态中的unixtimemstime属性被用作当前时间的缓存,serverCron函数默认每100ms的频率更新这两个字段。对于设置键值过期时间,慢查询日志这种需要高精度时间的功能来说,服务器还是会再次执行系统调用。
  • 更新LRU时钟: 服务器状态中的lruclock属性保存了服务器的LRU时钟;每个Redis对象都会有一个lru属性,保存了对象最后一次被访问的时间。这个值也是用serverCron来更新。
  • 更新服务器每秒执行命令次数: serverCron函数中的trackOperationsPerSecond函数会以每100ms一次的频率执行,这个函数的功能是以抽样计算的方式,估算并记录服务器在最近一秒钟处理的命令请求数量。可以通过INFO stats查看。
  • 更新服务器内存峰值记录:serverCron每次都会查看服务器当前使用的内存数量,并与stat_peak_memory保持的值进行比较,如果当前的数据比较大就更新这个值。INFO memory命令可以查看具体的数据。
  • 处理SIGTERM信号:服务器启动时,Redis会为服务器进程的SIGTERM信号关联处理器sigtermHandler函数,这个信号处理器负责在服务器接到SIGTERM信号时,打开服务器状态的shutdown_asap标识。如果不拦截这个信号,可能会造成比如RDB持久化操作时关闭服务器。
  • 管理客户端资源:serverCron函数每次执行都会调用clientsCron函数,clientsCron函数会对一定数量的客户端进行以下两个检查:
    • 如果客户端与服务器之间的连接已经超时,那么程序释放这个客户端。
    • 如果客户端在上一次执行命令请求后,输入缓冲区的大小超过了一定的长度,那么程序会释放客户端当前的输入缓冲区,并重新创建一个默认大小的输入缓冲区,从而防止客户端的输入缓冲区耗费了过多的内存。
  • 管理数据库资源: 每次调用databasesCron函数,对服务器中一部分数据库进行检查,删除其中的过期键,并在需要时,对字典进行收缩操作。
  • 执行被延迟的BGREWRITEAOF
  • 检查持久化操作的运行状态
  • 将AOF缓冲区的内容写入到AOF文件
  • 关闭异步客户端
  • 增加cronloops计数器的值:cronloops记录了serverCron函数执行的次数。

初始化服务器

一个Redis服务器从启动到能够接受客户端的命令请求,需要经过一系列的初始化和设置过程。过程如下:

  • 初始化服务器状态结构:包括设置服务器的运行ID,设置服务器的默认运行频率,设置服务器的默认配置文件路径,设置服务器默认端口号,设置服务器默认持久化条件等。
  • 载入配置选项: 可以通过给定配置函数或指定配置文件来修改服务器的默认配置。
  • 初始化服务器数据结构:包括初始化server.clients链表,初始化执Lua脚本的执行环境server.lua等;还进行了创建共享对象,打开服务器的监听端口等操作。
  • 还原数据库状态: 完成初始化后,服务器需要载入RDB文件或者AOF文件,并根据文件记录的内容来还原服务器的数据库状态。
  • 执行事件循环: 初始完成后,开始执行服务器的事件循环(loop)。

Redis设计与实现总结——数据结构与对象

基本数据结构

简单的动态字符串

Redis自己构建的一种名为简单动态字符串(simple dynamic string, SDS)的抽象类型,并将SDS用做Redis的默认字符串表示。
SDS的定义在sds.h/sdshdr结构中:

1
2
3
4
5
6
7
8
9
10
11
struct sdshdr {
// 记录buf数组中已使用的字节的数量
// 等于SDS所保存字符串的长度
int len;

// 记录buf数组中未使用字节的数量
int free;

// 字节数组,用于保存字符串
char buf[];
}

SDS结构
C字符串和SDS之间的区别:

C字符串 SDS
获取字符串长度的复杂度为O(N) 获取字符串长度的复杂度为O(1)
API是不安全的,可能会造成缓冲区溢出 API是安全的,不会造成缓冲区溢出
修改字符串长度N次必然需要执行N次内存重分配 修改字符串长度N次最多需要执行N次内存重分配
只能保持文本数据 可以保持文本或者二进制数据
可以使用所有<string.h>库中的函数 可以使用一部分<string.h>库中的函数

链表

链表提供了高效的节点重排能力,以及顺序性的节点访问方式,并且可以通过增删节点来灵活地调整链表的长度。链表在redis链表键,发布与订阅,慢查询,监视器等功能都用到了。
链表结构分为链表和链表节点,每个链表由多个链表的节点组合而成。每个节点都有一个指向前置节点和后置节点的指针,所以Redis的链表实现是一个双端链表。表头节点和表尾节点都指向NULL, 是一个无环链表。保存链表值的类型是void, 可以保持不同类型的值。

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
// 链表定义adlist/list
typedef struct list {
// 表头节点
listNode *head;

// 表尾节点
listNode *tail;

// 链表所浩瀚的节点数量
unsigned long len;

// 节点复制函数
void *(*dup) (void *ptr);

// 节点释放函数
void (*free) (void *ptr);

// 节点值对比函数
int (*match) (void *ptr, void *key);
} list;

//链表节点定义adlist.h/listNode
typedef struct listNode {
// 表头节点
struct listNode *prev;

// 表尾节点
struct listNode *next;

// 节点值
void *value;
} listNode;

list结构

字典

字典又称为符号表(symbol table), 关联数组(associative array)或映射(map),是一种用于保存键值对(key-value pair)的抽象数据结构。字典中的每一个键都是独一无二的。字典在Redis中应用相当广泛,比如Redis的数据库就是使用字典作为底层实现的,对数据库的CRUD也是建立在字典的操作上。字典还是哈希键的底层实现之一。
dict结构
字典的结构如上图所示,字典是由多个结构连接而成,首先是字典结构dict.h/dict

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
typedef struct dict {

// 类型特定函数, 保存了一簇用于操作特定类型键值对的函数,
// Redis会为用途不同的字典设置不同的类型特定函数
dictType *type;

// 私有数据, 保存了需要传给那些类型特定的函数的可选参数
void *privdata;

// 哈希表, 注意这里hash表定义两个,其中一个是实际中使用的,
// 另一个是在扩展或收缩的时候使用的,类似于GC复制算法的原理
dictht ht[2];

// rehash 索引, 记录rehash目前的进度
// 当rehash不在进行时,值为-1
int trehashidx;
} dict;

字典所使用的哈希表dict.h/dictht

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
typedef struct dictht {

// 哈希表数组
dictEntry **table;

// 哈希表大小
unsigned long size;

// 哈希表大小掩码,用于计算索引值
// 总是等于size-1
unsigned long sizemark;

// 该哈希表已有节点的数量
unsigned long used;
} dictht;

哈希表节点:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
typedef struct dictEntry {

// 键
void *key;

// 值
union {
void *val;
uint64_t u64;
int64_t s64;
} v;

// 指向下个哈希表节点,形成链表
// 使用next指针解决哈希冲突的问题
// 哈希算法为MurmurHash2
struct dictEntry *next;
} dictEntry;

随着操作的不断执行,哈希表保存的键值对会逐渐的增多或减少,为了让哈希负载因子(load factor)维持在一个合理的范围之内,当哈希表保持的键值对对数量太多或太少时,程序需要对哈希表的大小进行相应的扩展或收缩。
为了避免rehash对服务器性能造成影响,服务器不是一次性将ht[0]里面的所有键值对全部rehashht[1],而是分多次,渐进式地将ht[0]里面的键值对慢慢地rehashht[1]

跳跃表

跳跃表(skiplist)是一种有序数据结构, 它通过在每个节点中维持多个指向其他节点的指针,从而达到快速访问节点的目的。跳跃表支持平均O(longN),最坏O(N)复杂度的节点查找,还可以通过顺序性操作来批量处理节点。更多介绍参考wiki
Redis使用跳跃表作为有序集合键的底层实现之一,如果一个有序集合包含的元素数量比较多,又或者有序集合中元素的成员是比较长的字符串时,Redis就会使用跳跃表来作为有序集合键的底层实现。跳跃表的另一个应用就是作为集群节点中的内部数据结构。除了这两个地方,其它地方没有用到。
跳跃表有redis.h/zskiplistNoderedis.h/zskiplist两个结构定义,其中zskiplistNode结构用于表示跳跃表节点,而zskiplist结构则用于保存跳跃表节点信息。

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
/*
* 跳跃表
*/
typedef struct zskiplist {

// 表头节点和表尾节点
struct zskiplistNode *header, *tail;

// 表中节点的数量
unsigned long length;

// 表中层数最大的节点的层数
int level;

} zskiplist;

/*
* 跳跃表节点
*/
typedef struct zskiplistNode {

// 成员对象
robj *obj;

// 分值
double score;

// 后退指针
struct zskiplistNode *backward;

// 层
struct zskiplistLevel {

// 前进指针
struct zskiplistNode *forward;

// 跨度
unsigned int span;

} level[];

} zskiplistNode;

skiplist结构

  • 层: 每个层带有两个属性,前进指针和跨度。前进指针用于访问表尾方向的其节点,而跨度则记录了前进指针所指向节点和当前节点的距离。上图中连线数字上带有数字的箭头就代表前进指针,而那个数字就是跨度。当程序从表头向表尾进行遍历时,访问就会沿着层的前进指针进行。每次创建一个新跳跃表节点的时候,程序根据幂次定律(power law, 越大的数出现的概率越小)随机生成一个介于1和32之间的值作为level数组的大小,这个大小就是层的高度。
  • 前进指针: 每个层都有一个指向表尾方向的前进指针(level[i].forward属性), 用于从表头向表尾方向的访问节点。
  • 后退指针: 节点中用BW字样标记节点的后退指针,它指向位于当前节点的前一个节点。后退指针在程序从表尾向表头遍历时使用。
  • 分值: 各个节点中的1.0,2.0和3.0是节点所保存的分值。在跳跃表中,节点各自所保存的分值从小到大排列。 跳跃表中的节点按照分值进行排序,当分值相同时,节点按照成员对象的大小进行排序。
  • 成员对象: 各个节点中的o1, o2和o3是节点所保存的成员对象。

具体的操作过程参考http://blog.csdn.net/ict2014/article/details/17394259

整数集合

整数集合(intset)是集合键的底层实现之一,当一个集合只包含整数值元素,并且这个集合的元素数量不多时,Redis就会使用整数集合键的底层实现。
每个intset.h/intset结构表示一个整数集合:

1
2
3
4
5
6
7
8
9
10
tyepdef struct intset {
// 编码方式, 决定contents的类型
uint32_t encoding;

// 集合包含的元素数量
uint32_t length;

// 保持元素的数组
int8_t contents[];
} intset;

intset结构
contents数组是整数集合的底层实现: 整数集合的每个元素都是contents数组的一个数组项(item), 各个项在数组中按值的大小从小到大有序地排列,并且数组中不包含任何重复项。虽然contetns声明为int8_t类型的数组,但实际上contents并不保存任何int8_t类型的值,contents数组的真正类型取决于encoding属性的值。
每当我们要将一个新元素添加到整数集合里面,并且新元素的类型比整数集合现有所有元素的类型都要长时,整数集合需要先进行升级(upgrade), 然后才能将新元素添加到整数集合里面。整数集合不支持降级操作, 一旦对数组进行了升级,编码就会一致保持升级后的状态。

压缩列表

压缩列表(ziplist)是列表建和哈希键的底层实现之一。当一个列表建只包含少量列表项,并且每个列表项要么就是小整数值,要么就是长度比较短的字符串,那么Redis就会使用压缩列表来做列表建的底层实现。
压缩列表是Redis为了节约内存而开发的,是由一系列特殊编码的连续内存块组成的顺序型(sequential)数据结构。一个压缩列表可以包含任意多个节点(entry),每个节点可以保持一个字节数组或一个整数值。
ziplist结构
压缩列表各个组成部分的详细说明:

属性 类型 长度 用途
zlbytes uint32_t 4字节 记录整个压缩列表占用的内存字节数:在对压缩列表进行内存重分配,或者计算zlend的位置时使用
zltail uint32_t 4字节 记录压缩列表表尾节点距离压缩列表的起始地址有多少字节:通过这个偏移量,程序无须遍历整个压缩列表就可以确定表尾节点的地址
zllen uint16_t 2字节 记录了压缩列表包含的节点数量,当节点数小于UINT16_MAX时取这个值,大于时需要遍历列表才能得出
entryX 列表节点 不定 压缩列表包含的节点,节点的长度由节点保存的内容决定
zlend uint8_t 1字节 特殊值0xFF(十进制255),用于标记压缩列表的末端

压缩列表的节点构成:

  • previous_entry_length: 以字节为单位,记录了压缩列表中前一个节点的长度。只要我们拥有了一个指向某个节点的起始地址的指针,那么通过这个指针及这个节点的previous_entry_length属性,程序就可以一直向前一个节点回溯,最终达到压缩列表的表头节点。
  • encoding: 记录了节点的content属性所保存数据的类型及长度。
  • content: 负责保存节点的值,节点值可以使一个字节数组或整数,值的类型和长度由节点的encoding属性决定。

连锁更新问题是指当插入新节点或删除节点后,previous_entry_length属性所记录的长度不能够满足改变后的节点的记录,需要扩容以便记录,最差的情况是后面的每个节点都会改变位置。最差的复杂度为O(N^2)。但是这种情况很少见,一般复杂度为O(N)。

对象

前面介绍了Redis的主要数据结构,但是Redis并没有直接使用这些数据结构实现键值对数据库,而是基于这些数据结构创建了一个对象系统, 这个系统包含字符串对象,列表对象,哈希对象,集合对象和有序集合对象这五种类型的对象,每种对象都用到了至少一种我们面前所介绍的数据结构。我们可以针对不同的使用场景,为对象设置多种不同的数据结构实现,从而优化对象在不同场景下的使用效率,而这些对用户是透明的。
Redis的对象系统还实现了基于引用计数技术的内存回收机制(GC), 当程序不再是由某个对象的时候,这个对象所占用的内存就会被自动释放;另外Redis还通过引用计数法实现了对象共享机制,这一机制可以在适当的条件下,通过让多个数据库键共享同一个对象来节约内存。
每当我们在Redis数据库中新创建一个键值对时,我们至少会创建两个对象,一个对象用作键值对的键(键对象),另一个对象用作键值对的值(值对象)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
typedef struct redisObject {

// 类型
unsigned type:4;

// 编码
unsigned encoding:4;

// 对象最后一次被访问的时间
unsigned lru:REDIS_LRU_BITS; /* lru time (relative to server.lruclock) */

// 引用计数
int refcount;

// 指向实际值的指针
void *ptr;

} robj;

使用TYPE命令可以看到对象的类型,对象的类型及type属性的值对应关系如下表:

type类型常量 对象的名称 TYPE命令的输出
REDIS_STRING 字符串对象 “string”
REDIS_LIST 列表对象 “list”
REDIS_HASH 哈希对象 “hash”
REDIS_SET 集合对象 “set”
REDIS_ZSET 有序集合对象 “zset”

每种TYPE对象的底层编码都是由上面说的数据结构组成的,使用OBJECT ENCODING命令可以查看一个数据库键的值对象的编码,具体的对应关系如下表:

对象所使用的底层数据结构 编码常量 OBJECT ENCODING命令输出
整数 REDIS_ENCODING_INT “int”
embstr编码的简单动态字符串(SDS) REDIS_ENCODING_EMBSTR “embstr”
简单动态字符串 REDIS_ENCODING_RAW “raw”
字典 REDIS_ENCODING_HT “hashtable”
双端链表 REDIS_ENCODING_LINKEDLIST “linkedlist”
压缩列表 REDIS_ENCODING_ZIPLIST “ziplist”
整数集合 REDIS_ENCODING_INTSET “intset”
跳跃表和字典 REDIS_ENCODING_SKIPLIST “skiplist”

每种类型对象可以使用哪些数据结构,下面做了一个总结:

对象类型 “int” “embstr” “raw”
“string” 如果字符串对象保存的是整数值,并且其可以用long类型来表示 如果字符串对象保持的是一个字符串值,并且其长度小于39字节 如果字符串对象保持的是一个字符串值,并且其长度大于39字节
对象类型 “linkedlist” “ziplist”
“list” 不满足ziplist的条件的情况 同时满足:
1. 所有字符串元素的长度都小于64字节;
2. 元素数量小于512个
对象类型 “hashtable” “ziplist”
“hash” 不满足ziplist的条件的情况 同时满足:
1. 哈希对象保存的所有键值对的键和值的字符串长度都小于64字节;
2. 哈希对象保存的键值对数量小于512个
对象类型 “intset” “hashtable”
“set” 同时满足:
1. 集合对象保存的所有元素都是整数值;
2. 集合对象保存的元素数量不超过512个
不满足”intset”的条件的情况
对象类型 “ziplist” “skiplist”
“zset” 同时满足:
1. 有序集合保持的元素数量小于128个;
2. 有序集合保持的所有元素成员的长度都小于64字节
不满足”ziplist”的条件的情况

redisObject有一个lru属性,这个属性记录了对象最后一次被命令程序访问的时间,OBJECT IDLETIME命令可以打印出给定键的空转时长(当前时间-lru时间), 另外当开启maxmemory选项,并且服务器用于内存回收的算法为volatile-lru或者allkeys-lru,那么当服务器占用的内存数超过了maxmemory选项所设置的上限值时,空转时长较高的那部分键会优先被服务器释放,从而回收内存。

垃圾回收进阶算法

了解GC的基本算法后,还需要了解各种改进的GC算法,这些算法是在之前的基础上进行扩展和组合的。主要包括GC标记-压缩算法, 保守式GC, 分代垃圾回收增量式垃圾回收RC Immix算法等。

GC标记-压缩算法

GC标记-压缩算法(Mark Compact GC)是将GC标记-清除算法与GC复制算法相结合的产物。 GC标记-压缩算法由标记阶段和压缩阶段构成。标记阶段和GC标记-清除算法提到的标记阶段一样。接下来需要搜索数次的堆来进行压缩。压缩阶段通过数次搜索堆来重新装填活动对象。

Lisp2算法

标记阶段的代码就不重复了,这里主要看压缩阶段的代码,下面可以看出压缩阶段主要分为三个步骤:

  1. 第一步是set_forwarding_ptr, 主要是按顺序遍历堆内的活动对象,每个活动对象的forwarding指针指向的是以后这个活动对象需要移动到的位置。
  2. 第二步是adjust_ptr, 遍历整个活动对象,复制他们之间的引用关系, 这个步骤只更新指针。
  3. 第三步move_obj, 遍历整个堆,对活动对象进行移动。
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
compaction_phase() {
set_forwarding_ptr()
adjust_ptr()
move_obj()
}

set_forwarding_ptr() {
scan = new_address = $head_start
while(scan < $head_end)
# 对被标记的对象,forwarding指针指向应该移动到的位置
if(scan.mark == TRUE)
scan.forwarding = new_address
new_address += scan.size
# 遍历整个堆
scan += scan.size
}

adjust_ptr() {
# 移动根指针
for(r : $roots)
*r = (*r).forwarding

scan = $head_start
while(scan < $head_end)
# 每个活动对象,原来指向子节点的指针改为指向直接点的forwarding指向的地址
if(scan.mark == TRUE)
for(child : children(scan))
*child = (*child).forwarding
scan += scan.size
}


move_obj() {
scan = $free = $head_start
# 遍历堆
while(scan < $head_end)
if(scan.mark == TRUE)
new_address = scan.forwarding
# 移动当前对象到对象forwarding指针指向的地址
copy_data(new_address, scan, scan.size)
# 移动完活动对象后清空指针和标记,防止再次移动
new_address.forwarding = NULL
new_address.mark = FALSE
# $free最终是压缩后可分配空间的开始
$free += new_address.size
scan += scan.size
}

上面的步骤可以用下面的图形化的例子来描述:
首先假设原始状态如下:
原始状态
先对其进行标记:
标记后
设定forwarding指针:
设定forwarding指针
更新指针:
更新指针
移动对象:
移动对象
上面可以看出,整个过程只是把活动对象往一边移动,活动对象之间的顺序不变。

  • 优点: 这个算法相对其他算法而言,堆利用率高,而且所有活动对象压缩到一端,不存在碎片化,能够充分的利用堆。
  • 缺点: 整个压缩过程需要3遍对堆的搜索,也就是执行该算法所花费的时间与堆大小成正比,吞吐量要劣于其他算法。

Two-Finger算法

Two-Finger算法由两个步骤构成:

  1. 移动对象
  2. 更新指针

我们知道Lisp2算法是把所有对象向右滑动,不改变活动对象的顺序,而Two-Finger算法则是真正的移动对象,把后面的活动对象移动到前面的空间。为了防止对象相互覆盖,必须要将所有对象整理成大小一致, 这个该算法的一个前提条件。另外Lisp2算法需要单独设置forwarding指针,但是Two-Finger算法可以利用对象的域来设定forwarding指针,不要单独占空间。
两个步骤对象的伪代码如下, 要说明的是move_obj函数有两个指针:$free, 从头往后找,找空闲的空间; live,从后往前找,找活动对象。这两个指针就是Two-Finger的名称由来。

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
move_obj() {
#从头开始找空闲空间
$free = $heap_start
#从尾开始找活动对象
live = $heap_end - OBJ_SIZE
while(TRUE)
#free, 是活动对像就略过,继续往后找
while($free.mark == TRUE)
$free += OBJ_SIZE
#live, 是活动对象就略过,继续往前找
while(live.mark == FALSE)
live -= OBJ_SIZE
# free 指针 比 live小,证明还没有结束,否则证明查找结束了
if($free < live)
#把live指向的对象复制到free地址
copy_data($free, live, OBJ_SIZE)
#live指向的对象的forwarding指针指向新地址,为下一步更新指针做准备
live.forwarding = $free
#移动过的对象标记位FALSE
live.mark = FALSE
else
break
}

adjust_ptr() {
for(r : $roots)
#*r>=$free的条件是对于被移动过的对象执行指针更新,没有移动过的对象保持原样
if(*r >= $free)
*r = (*r).forwarding

scan = $head_start
#scan < $free 是因为对于大于scan的节点已经失效,只对当前活动对象更新
while(scan < $free)
#更新过的标记一下
scan.mark = FLASE
for(child : children(scan))
#*child >= $free 的条件是对于被移动过的对象执行指针更新,
# 没有移动过的对象保持原样
if(*child >= $free)
*child = (*child).forwarding
scan += OBJ_SIZE
}
  • 优点: 不需要额外的内存存储forwarding指针,内存使用效率比Lisp2高,只搜索两次堆,吞吐量也更好.
  • 缺点: 压缩后对象的顺序发生了很大变化,不利于缓存的使用。而且每个对象大小必须一致,限制比较多。

表格算法

表格算法是综合了Lisp2和Two-Finger两种算法优点的算法。其主要步骤也是有两部分:

  1. 移动对象(群)以及构筑间隙表格(break table)
  2. 更新指针

前面两个每次都是移动一个活动对象,而在表格算法种每次移动的是一个群连续的活动对象,更新指针所有的信息也不再是forwarding指针,而是是有个一个叫间隙表格的方法。间隙表是由两个值组成的,其中每个表格代表的是一个活动对象群的入口,左值代表活动对象群的首地址,右值代表活动对象群所相邻的前面的空间占分块的总大小。
第一步过程可以用伪代码来表示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
movie_obj(){
#从头开始遍历
scan = $free = $heap_start
size = 0
while(scan < $head_end)
while(scan.mark == FLASE)
# size 记录相邻的非活动对象的大小
size += scan.size
scan += scan.size
# 记录活动对象的首地址
live = scan
while(scan.mark == TRUE)
scan += scan.size
# 上面两个while后,找到了第一个连续的非活动空间和第一个连续的活动空间
# 移动活动对象群,并构筑间隙表格
slide_objs_and_make_bt(scan, $free, live, size)
# 移动后记录下一个空闲空间地址
$free += (scan -live)
}

slide_objs_and_make_bt函数是一个比较复杂的过程,它主要由两部分组成:

  1. 移动对象群
  2. 移动间隙表格

可以用下面的图表示:
首先执行完上面代码到slide_objs_and_make_bt之前:
间隙表格
执行slide_objs_and_make_bt后, 移动了对象群,并且在空出来的空间里记录了间隙表格, 左值100表示对象群首地址B的地址,右值100表示B之前的空白块长度为100
间隙表格
再次执行slide_objs_and_make_bt后,F开头的对象群也进行了移动,并且把两个活动对象群对应的间隙表格都放到了空白块中,第二个间隙表格的550表示F的起始地址,右值300表示第一次执行slide_objs_and_make_bt后,第一个活动对象群的末尾到第二个活动对象群的开始,正好是6块,也就是上图$freelive的size大小是300。执行完最终结果如下:
间隙表格

第二步更新指针的伪代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
adjust_ptr() {
for(r : $roots)
*r = new_address(*r)

scan = $heap_start
# 对活动对象更新指针
while(scan < $free)
scan.mark = FALSE
for(child : children(scan))
*child = new_address(*child)
scan += scan.size
}

# 找到活动对象对应的应该跟新到的指针地址
new_address(obj) {
best_entry = new_bt_entry(0,0)
for(entry : break_table)
if(entry.address <= obj && $best_entry.address < entry.address)
best_entry = entry
return obj - best_entry.size
}

上面的new_address函数比较难理解,就是需要从多个间隙表格中找到活动对象群所对应的,然后利用obj-best_entry.size 就返回节点对应的新地址。

优点: 首先内存利用率和Two-Finger一样,但是由于是保持了原来的顺序,所以可以利用缓存。
缺点: 每次移动都要进行表格的移动和更新,代价比较高。

ImmixGC 算法

暂略……

保守式GC

前面提到过GC是根据对象的指针指向去搜寻其他对象的。另一方面,GC对非指针不进行任何操作。另外可以认为调用栈、寄存器以及全局变量空间都是根。对于上面存在一个问题就是: 如何识别一个变量是否是指针? 这里所说的保守式GC就是指”不能识别指针和非指针的GC”, 而准确式GC指的就是能够正确识别指针和非指针的GC。

保守式GC

之前说的下面这些空间都是根:

  • 寄存器
  • 调用栈
  • 全局变量空间

但是事实上他们都是不明确的根(ambiguous roots)。
保守式GC对检查不明确的根时,所进行的基本项目是:

  • 是不是被正确对齐的值? (32位CPU,为4的倍数;64位CPU为8的倍数; 其他情况被视为非指针)
  • 是不是指着堆内? (分配了GC专用堆,对象就会被分配到堆里,指向对象的指针按道理肯定指向堆内,否则就是非指针)
  • 是不是指着对象的开头?(如果把对象固定大小对齐,例如”BiBOP”法,如果对象的值不是固定大小的倍数,就是非指针)

当不明确的根运行GC时,偶尔会出现非指针和堆里的对象的地址一样的情况,这时就无法识别这个值是非指针,这就是“貌似指针的非指针”(false pointer), 保守式GC这种把”貌似指针的非指针”看成”指向对象的指针”叫做”指针的错误识别”。在采用GC标记-清除算法,这种非指针会被错误的识别为活动对象,不会被回收。这样采取的是一种保守的态度,这样处理也不会出现问题。

  • 优点: 容易编写语言处理程序
  • 缺点: 识别指针和非指针需要付出成本;错误识别指针会压迫堆, 会占用堆空间;能够使用的GC算法有限,不能使用移动对象的GC算法,否则就会重新非指针,照成意想不到的BUG

准确式GC

准确式GC是基于正确识别指针和非指针的“正确的根”(exact roots)来执行GC的。要想创建正确的根,就需要”语言处理程序的支援”, 依赖语言处理程序的实现。常见的方法这里介绍两种:

  • 打标签: 通过打标签的方法把不明确的根里的所有非指针和指针都区别开来。
  • 不把寄存器和栈当做根: 创建一个正确的根来管理,这个正确的根在处理程序里只集合了mutator可能到达的指针,然后以它为基础执行GC。 参考Rubinius语言处理程序的实现。

  • 优点: 相对于保守式GC,能够正确识别指针和非指针,适用的GC方法也更广泛。

  • 缺点: 需要语言处理程序的支援,给实现者带来负担。

间接引用

保守式GC有一个缺点就是”不能使用GC复制算法等移动对象的算法”, 因为如果是非指针的对象发生移动,其值就会发生变化,使用这个对象就会出现问题。解决这个问题的方法就是使用”间接引用”
结合下图来说明:
复制前可以看到根和对象之间有句柄。每个对象都有一个句柄,它们分别持有指向这些对象的指针。并且局部变量和全局变量这些不明确的根里没有指向对象的指针,只装着指向句柄的指针(如图中的1,2,3), 下图中的1,2表示指针,3表示非指针。
间接引用1
复制之后移动了引用目标的对象,只修改了1,2是指针的值,非指针3的值并没有发生改变。
间接引用2

  • 优点: 可以适用于更多的GC算法
  • 缺点: 所有对象都要经由句柄间接引用,回拉低访问对象内数据的速度。

MostlyCopyingGC

又是一个为了能够执行GC复制算法的保守式GC, 这个算法的核心思想就是抛开那些不能移动的对象,将其他”大部分”的对象都进行复制的GC算法,目的是为了保证不能移动的对象一定不会移动,可以移动的对象大部分都移动了,保证不出现BUG。
这个算法执行的前提条件:

  1. 根是不明确的根
  2. 没有不明确的数据结构
  3. 对象大小随意

执行这个算法的要点是把堆分配成一定大小的页(page)组成,执行分配的时候从正在使用的页里分配,如果空间不够则使用空页,如果一个页放不下,则会跨页存储。
执行GC时把所有根直接引用的页升级为To空间,然后再把To页对象的子对象复制到空页。这个过程会保留根直接引用的对象,所以不会复制非指针对象。同时升级的页中也包含了垃圾对象吗,无法清除。

黑名单

保守式GC指针的错误识别所带来害处和这个对象的大小及其子对象的数量有关系,如果一个对象很大,或者子对象很多,却被识别为”还活着”, 那就会在占用很多的堆空间。
这里的黑名单记录的是”不明确的根内的非指针,其指向的是有可能被分配对象的地址”, 这里说的”有可能被分配对象的地址”指的是”堆内未使用的对象的地址”。mutator无法引用至今未使用过的对象。也就是说,如果根里存在有这种地址的指针,那它肯定就是”非指针”,就会被记入黑名单中。在分配对象过程中,如果要分配的地址在黑名单中,这个对象有可能被非指针值所引用。也就是说,及时分配后对象成了垃圾,也很有可能被错误识别为”还活着”。为此,对象分配到这种地址是要满足:

  • 小对象
  • 没有子对象的对象

这样及时错误识别了,对整个堆的影响也不大,把对堆的压迫控制在最低限度。

分代垃圾回收

分代垃圾回收(Generational GC)把对象按“年龄”进行分类,使用不同的GC算法, 提高垃圾回收的效率。年龄的概念就是指对象的生存时间,经历一次GC后活下来的对象年龄就是1,依次类推。 新生成的对象和年龄小于一定值得对象都称为新生代对象, 年龄大于一定值得对象则称为老年代对象, 这就是所谓的分代。新生代对象经历一定GC后会变成老年代对象,这个过程就叫晋升(promotion)

Ungar 的分代垃圾回收

Ungar 的垃圾回收是针对新生代执行GC复制算法,针对老年代执行标记-清除算法。Ungar 将堆结构分为四个部分,分别是生成空间、2个大小相等的幸存空间以及老年代空间,并分别用$new_start$survivor1_start$survivor2_start$old_start这4个变量引用它们的开头。将生成空间和幸存空间合称为新生代空间。
当生成空间满了的时候,新生代GC就会启动,将生成空间的所有活动对象复制,这根GC复制算法是一个道理。目标空间是幸存空间中空闲的一个。

      记 录 集
    +---+---+---+---+
$rs |   |   |   |   |
    +---------------+
    +------------------------+ $new_start
    |              +--------------+   $survivor1_start
    |              |     +-------------+ $survivor2_start
    |              |     |     +-----------+  $old_start
    |              |     |     |                           堆
    v--------------v-----v-----v-----------------------------+
    |              |     |     |                             |
    |              |     |     |                             |
    |              |     |     |                             |
    +--------------+-----+-----+-----------------------------+
     生 成 空 间     幸 存 空 间            老 年 代 空 间
           新 生 代 空 间

分代垃圾回收的优点是只将垃圾回收的重点放在新生代对象上,以此来缩减GC所需的时间。但是老年代有可能引用了新生代对象,所以还需要遍历老年代对象,这样就大大削减了分代垃圾回收的优势,所以为了解决这个问题,又增加了一个记录集。记录集里记录的是对新生代有引用的老年代对象。这样在新生代GC时,只需要再对记录集进行遍历就行了。
为了将老年代对象记录到记录集里,我们利用写入屏障(write barrier)。在mutator更新对象间的指针操作中,写入屏障是不可或缺的。

1
2
3
4
5
6
7
8
9
write_barrier(obj, field, new_obj) {
if(obj >= $old_start #发出引用的对象在老年代里
&& new_obj < $old_start #新生成的对象在新生代里
&& obj.remembered == FALSE) #老年代对象没有被记录
$rs[$rs_index] = obj #老年代对象加入记录集
$rs_index++
obj.remembered = TRUE #表示已经被记录过
*field = new_obj #field是obj的指针,更新指针new_obj成为引用目标的对象
}

分配是在生成空间进行的,执行分配的new_obj()函数伪代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
new_obj(size) {
if($new_free + size >= $survivor1_start)
# 生成空间不够用,执行新生代GC
minor_gc()
if($new_free + size >= $survivor1_start)
# 执行GC后仍然不够用,返回错误
allocation_fail()

obj = $new_free #$new_free 是指向生成空间的分块开头的指针
$new_free += size
obj.age = 0 #年龄默认值
obj.forwarded = FALSE #防止重复复制相同对象的标志,跟GC复制算法和GC标记-压缩算法中的作用一样
obj.remembered = FALSE #是否在记录集里,只用于老年代对象
obj.size = size
return obj
}

新生代GC的伪代码如下:

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
minor_gc() {
$to_survivor_free = $to_survivor_start
#根在新生代的对象进行GC复制
for(r : $roots)
if(*r < $old_start)
*r = copy(*r)

i = 0
#对记录集里的对象的子节点进行GC复制
while(i < $rs_index)
has_new_obj = FALSE
for(child : children($rs[i]))
if(*child < $old_start)
*child = copy(*child)
if(*child < $old_start)
has_new_obj = TRUE
# TRUE表示复制后的对象在新生代,FALSE表示复制后的对象在老年代
# 复制后的对象在老年代,则需要把这个对象从记录集里去掉
if(has_new_obj == FALSE)
$rs[i].remembered = FALSE
$rs_index--
#最后一位与当前节点交换,交换后,最后一位无法在访问到,可以认为是从记录集里去掉了
swap($rs[i], $rs[$rs_index])
else
i++
#交换From空间和To空间
swap($from_survivor_start, $to_survivor_start)
}

# 对象的复制
copy(obj) {
#没有被复制
if(obj.forwarded == FALSE)
#年龄没有达到
if(obj.age < AGE_MAX)
copy_data($to_survivor_free, obj, obj.size)
# 标识已经被复制
obj.forwarded = TRUE
# 被复制到的地址
obj.forwarding = $to_survivor_free
# age++
$to_survivor_free.age++
$to_survivor_free += obj.size
for(child : children(obj))
*child = copy(*child)
else
# 年龄达到,晋升到老年代
promote(obj)
return obj.forwarding
}

# 对象从新生代晋升到老年代
promote(obj) {
#从老年代找空间
new_obj = allocate_in_old(obj)
if(new_obj == NULL)
#空间不够执行老年代的GC,跟GC标记-清除法一样
major_gc()
new_obj = allocate_in_old(obj)
if(new_obj == NULL)
allocation_fail()
obj.forwarding = new_obj
obj.forwarded = TRUE

for(child : children(new_obj))
if(*child < $old_start)
$rs[$rs_index] = new_obj
$rs_index++
new_obj.remembered = TRUE
return
}

分代垃圾回收是建立在”很多对象年纪轻轻就会死”的基础上的,所以满足这种条件时,可以改善GC所花费的时间,提高吞吐量。是但是因为老年代GC很费时,所以没办法缩短mutator的最大暂停时间。并且如果不满足上面的条件时,就没办法利用到分代垃圾回收的优势。

记录各代之间的引用的方法

Ungar 分代垃圾回收的记录集是不可少的,但是这个记录集会浪费很多空间,为了提高内存利用率,可以通过下面两种方法:

  • 卡片标记: 把老年代空间等分成N个卡片,每份假设129字节(1024位),可以用表格表格中位图的一位表示一个卡片,这样能够有效提高内存空间(只需老年代的1/1024)。当标记表格设置很多位时,可能就会在搜索卡片上花费大量时间。
  • 页面标记: 利用OS的页面管理,如果在卡片标记中奖卡片和页面设置为同样大小,我们就能得到OS的帮助。一旦mutator对堆内的某一个页面进行写入操作,OS就会设置跟这个页面对应的位,我们把这个位叫做页面重写标志位(dirty bit)。卡片标记中是搜索标记表格,而页面标记则是搜索这个页面的重写标志位。

多代垃圾回收

分代垃圾回收是把对象分为新生代和老年代两个,也可以分成3个及更多个, 分代越多,对象变成垃圾的机会也就越大,所以这个方法确实能够减少活到最老代的对象。但是每代的空间也就相应的变小了,这样一来各代之间的引用就变多了,各代中垃圾回收花费的时间也就越来越长了。综合来看,少设置一些分代能得到更优秀的吞吐量,据说分为2代或3代是最好的。

列车垃圾回收

Ungar 分代垃圾回收的一个问题是不能够减少最大暂停时间,而列车垃圾回收(Train GC)就是为了控制老年代GC中暂停时间的增长而设计的。列车垃圾回收中将老年代空间按照一定的大小划分,每个划分出来的空间称为车厢,多个车厢有组成列车,多个列车一起组成了老年代空间。1次老年代GC不再是对整个老年代空间进行,而是以1个车厢作为GC对象。
下面这幅图反应的是列车垃圾回收的堆结构:
列车垃圾回收堆结构
具体过程省略……

  • 优点: 缩减了老年代GC照成的mutator的最大暂停时间。还能回收循环的大型垃圾。
  • 缺点: 执行写入屏障的额外负担要比Ungar的分代垃圾回收中执行时所产生的更大,因此吞吐量上要弱一些。

增量式垃圾回收

增量式垃圾回收(Incremental GC)是一种通过逐渐推进垃圾回收来控制mutator最大暂停时间的方法。之前介绍的GC算法,一旦GC开始执行,mutator就没有办法执行了,像这样的GC叫做听执行GC。为了改变这种方式,想出了一种GC和mutator交替运行的方式,这就是增量垃圾回收。

三色标记算法

这个算法将GC中的对象按照各自情况分成三种:

  • 白色: 还未搜索过的对象
  • 灰色: 正在搜索的对象
  • 黑色: 搜索完成的对象

以GC标记-清除算为例,应用到三色标记算法中。默认对象都是白色,GC一旦运行,所有从根能够到达的对象都会被标记,然后放到栈里。放到栈里的对象被标记成灰色,然后栈里的对象依次弹出,搜索其子对象,子对象也被标记成灰色。当其所有的子对象都被标记成灰色时,该对象就被标记成黑色。当GC结束时已经不存在灰色对象了,活动对象全部为黑色,垃圾对象则为白色。
增量式的GC标记-清除算法可以分为以下三个阶段:

  • 根查找阶段
  • 标记阶段
  • 清除阶段

下面是过程的伪代码,所谓标记为灰色并不是真正的标记为灰色,而是标记位TRUE,并放到栈中;置为黑色则只是标记为TRUE; 标记位白色的就是obj.mark=FALSE

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
incremental_gc() {
case $gc_phase
when GC_ROOT_SCAN
root_scan_phase() #根查找阶段
when GC_MARK
incremental_mark_phase() #增量标记阶段
else
incremental_sweep_phase() #增量清除阶段
}

#根查找函数
root_scan_phase() {
for(r : $roots)
mark(*r)
$gc_phase = GC_MARK
}

mark(obj) {
if(obj.mark == FALSE)
obj.mark = TRUE
push(obj, $mark_stack) #灰色对象放到栈里
}

#增量标记
incremental_mark_phase() {
for(i : 1..MARK_MAX) # MARK_MAX每次从栈中弹出对象的次数
if(is_empty($mark_stack) == FALSE)
obj = pop($mark_stack) #从栈中弹出灰色对象, 标记其子对象
for(child : children(obj))
mark(*child)
else
#栈为空,重新从根开始查找
for(r : $roots)
mark(*r)
#从根查找完继续标记
while(is_empty($mark_stack) == FALSE)
obj = pop($mark_stack)
for(child : children(obj))
mark(*child)
#为清除阶段做准备
$gc_phase = GC_SWEEP
$sweeping = $heap_start
return
}

#写入屏障,对于新节点,需要标记为灰色
#如果没有这一步,标记阶段进行到一半有可能不会对新的节点进行搜索
write_barrier(obj, field, newobj) {
if(newobj.mark == FALSE)
newobj.mark = TRUE
push(newobj, $mark_stack)

*field = newobj
}

#清除阶段
incremental_sweep_phase() {
swept_count = 0
while(swept_count < SWEEP_MAX) #每次清除SWEEP_MAX个对象
if($sweeping < $heap_end)
if($sweeping.mark == TRUE)
$sweeping.mark = FALSE
else
#mark=false表示白色,放入到空闲链表中
$sweeping.next = $free_list
$free_list = $sweeping
$free_size += $sweeping.size

$sweeping += $sweeping.size
swept_count++
else
$gc_phase = GC_ROOT_SCAN
return

}

#分配
newobj(size) {
#$free_siz 小于一定量时就执行GC, 而不是等到空间枯竭
if($free_size < HEAP_SIZE * GC_THRESHOLD)
incremental_gc()

chunk = pickup_chunk(size, $free_list)
if(chunk != NULL)
chunk.size = size
$free_size -= size
#chunk如果在清除阶段在要清除的空间,需要涂黑,表示不可回收
if($gc_phrase == GC_SWEEP && $sweeping <= chunk)
chunk.mark = TRUE
return chunk
else
allocation_fail()
}

可以看到上面整个过程,分配和GC是交替进行的,而且GC的三个阶段也是按顺序循环进行的,每次执行incremental_gc()都会进入下一个阶段。

  • 优点: 增量式垃圾回收不是一口气运行GC,而是和mutator交替运行的,因此不会长时间妨碍到mutator的运行。
  • 缺点: 牺牲了吞吐量。吞吐量和最大暂停时间是互相权衡的,一方面做的好另一方面就会变差。

Steele的算法

这个算法中使用的写入屏障要比上面(Dijkstra)的写入屏障条件更严格,它能减少GC中错误的标记的对象。
这个算法的标记函数如下:

1
2
3
4
mark(obj) {
if(obj.mark == FALSE)
push(obj, $mark_stack)
}

可以看出在放入栈时并没有标记obj.mark=TRUE, 也就是说这个算法的灰色对象是指”堆在标记栈里的没有设置标志位的对象”, 黑色对象是”设置了标志位的对象”。
写入屏障的伪代码也不一样:

1
2
3
4
5
6
7
8
9
write_barrier(obj, field, newobj) {
if($gc_phase == GC_MARK &&
obj.mark == TRUE &&
newobj.mark == FALSE)
obj.makr = FALSE
push(obj, $mark_stack)

*field = newobj
}

上面代码主要是判断如果在标记过程中发出引用的对象是黑色对象,且新的引用的目标对象为灰色或白色,那么我们就把发出引用的对象涂成灰色。Steele的写入屏障通过限制标记对象来减少被标记的对象,从而防止了因疏忽而造成垃圾残留的后果。 (详情参见P175)

汤浅的算法

汤浅的算法中标记阶段并没有在搜索根,遵循了”以GC开始时对象间的引用关系为基础执行GC”这项原则。

1
2
3
4
5
6
7
8
9
10
11
incremental_mark_phase() {
for(i : 1..MARK_MAX)
if(is_empty($mark_stack) == FALSE)
obj = pop($mark_stack)
for(child : children(obj))
mark(*child)
else
$gc_phrase = GC_SWEEP
$sweeping = $heap_start
return
}

上面通过写入屏障防止产生从黑色对象指向白色对象的指针,而汤浅的算法中却允许黑色对象指向白色对象的指针。汤浅算法是基于在GC开始时保留活动对象这项原则,就没有必要在生成新指针时标记引用对象的目标了。及时出现了从黑色对象指向白色对象的指针,只要保留了GC开始时的指针,作为引用目标的白色对象早晚会被标记。但是在删除指针时无法保留指针,因此写入屏障要进行一些特殊处理:

1
2
3
4
5
6
7
8
9
write_barrier(obj, field, newobj) {
oldobj = *field
#在标记阶段中如果指针更新前引用的oldobj是白色对象,就将其涂成灰色
if(gc_phase == GC_MARK && oldobj.mark == FALSE)
oldobj.mark = TRUE
push(oldobj, $mark_stack)

*field = newobj
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#分配
newobj(size) {
if($free_size < HEAP_SIZE * GC_THRESHOLD)
incremental_gc()

chunk = pickup_chunk(size, $free_list)
if(chunk != NULL)
chunk.size = size
$free_size -= size
#这里跟之前不一样,分配后会设置obj为黑色
if($gc_phase == GC_MARK)
chunk.mark = TRUE
else if($gc_phase == GC_SWEEP && $sweeping <= chunk)
chunk.mark = TRUE
return chunk

else
allocation_fail()
}

RC Immix算法

垃圾回收基本算法

本章介绍GC的基本算法:GC标记-清除法,引用计数法, GC复制算法。这三种我认为是GC的三个方向的基本思维。其他方法都是围绕这个些基本方法展开的。

GC标记-清除法

基本方法

所谓的标记-清除法,依据其字面意思就是,先做标记,然后在清除。这个过程分为两个阶段,标记阶段就是把所有活动对象坐上标记,清除阶段就是把那些没有做标记的对象,也就是非活动对象回收的阶段。利用伪代码表示就是:

1
2
3
4
mark_sweep() {
mark_phase()
sweep_phase()
}
  • 标记阶段: 这个阶段从出发,利用深度优先遍历(不用广度优先是因为深度优先搜索比广度优先搜索更能压低内存使用量。), 对每个能到达的活动对象都做上标记(用一个位来表示)。这个阶段所花费的时间与”活动对象的总数”成正比。标记阶段伪代码:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    mark_phase() {
    #遍历根节点, 进行标记
    for(r: $roots)
    mark(*r)
    }
    #标记函数
    mark(obj) {
    if(obj.mark == FALSE)
    obj.mark = TRUE
    #深度优先遍历
    for(child : children(obj))
    mark(*child)
    }
  • 清除阶段: 清除阶段主要工作是通过遍历整个堆,把未被标记的对象(非活动对象)回收再利用。回收对象就是把对象作为分块,连接到被称为”空闲链表”的单向链表。之后进行分配时遍历空闲链表就可以找到分块了。两个相邻的分块如果地址是连续的,就会对其进行合并, 合并操作可以减少碎片的发生。清除阶段的伪代码:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    sweep_phase() {
    sweeping = $heap_start
    #遍历堆
    while(sweeping < $head_end)
    if(sweeping.mark == TRUE)
    sweeping.mark == FALSE
    else
    #放入空闲链表
    if(sweeping.mark == $free_list + $free_list.size)
    #合并
    $free_list.size += sweeping.size
    else
    sweeping.next = $free_list
    $free_list = sweeping
    sweeping += sweeping.size
    }
  • 分配: 进行mutator申请分块时,搜索空闲链表并找到合适大小的分块,这个过程就叫做分配。找到合适的分块大小有三种策略:

    1. First-fit: 找到最初发现大于等于size的分块就立刻返回。考虑到分配所需的时间,标记清除法选择的就是这种方法。
    2. Best-fit: 遍历空闲链表,找到大于等于size的最小分块返回。
    3. Worst-fit: 找出最大的分块,把分块分割成size大小和剩余分块。
      分配阶段的伪代码:
      1
      2
      3
      4
      5
      6
      7
      new_obj(size) {
      chunk = pickup_chunk(size, $free_list)
      if(chunk != NULL)
      return chunk
      else
      allocation_fail()
      }

优点/缺点

  • 优点:
    1. 实现简单
    2. 与保守式GC算法兼容: 保守式算法就是不知道对象是否是指针,所以移动对象会造成错误(后面会讲到), 而标记清除算法是不会移动对象的,所以是兼容的。
  • 缺点:
    1. 碎片化: 由于非活动对象分布不均匀,容易照成堆内的内存空间碎片化,不利于mutator的执行。
    2. 分配速度: 由于分配时需要遍历空闲链表,查找速度取决于要分配的块和空闲链表的分布。后面要讲到的复制算法和标记-压缩算法由于分块是连续内存分布的,所以速度要快。
    3. 与写时复制技术不兼容: 因为每次GC都要修改活动对象的标记位,导致写操作的发生,从而产生复制。

多个空闲链表

为了提高分配速度,一个改进就是把分块按照大小分为多个空闲链表,这样在分配的时候就可以根据要分配的空间的大小去对应的空闲链表中寻找,大大减少了查找分块的时间。
下面是利用多个空闲链表的new_obj()函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
new_obj(size){
#index 是一个要分配的字的大小
index = size / (WORD_LENGTH / BYTE_LENGTH)
#空闲链表一共有101个,0-100都是按照字精确分配到对应的$free_list[index]中,
#大于100的字都分配到$free_list[101]中
if(index <= 100)
if($free_list[index] != NULL)
#直接找到对应的空闲链表
chunk = $free_list[index]
$free_list[index] = $free_list[index].next
return chunk
else
#大于100的需要遍历$free_list[101]找到合适大小的块
chunk = pickup_chunk(size, $free_list[101])
if(chunk != NULL)
return chunk

allocation_fail()
}

BiBOP法

针对标记-清除算法的碎片化问题, 可以把堆先分割成大小固定的块,让每个块只能配置同样大小的对象,这就是BiBOP法。如果某个大小字的活动对象很少,其他的字活动对象很多的话,这种情况也不能提高堆的利用率,无法解决碎片化的问题。

位图标记法

上面还说道标记-清除法不能够与写时复制技术兼容是因为修改标记位会引起复制发生,为了解决这个问题,位图标记法采用只收集各个对象的标志位并表格化,不跟对象一起管理。也就是把对象和标记位进行了分离。这样做有两个好处:

  1. 与写时复制技术兼容: 因为GC的时候改变了标记位也不会引起对象的复制, 而位图表格非常小,所以即使被复制也不会有什么大的影响。
  2. 清除操作更高效: 在遍历堆的时候不需要取消标志位,可以最后在位图表格中设置。

延迟清除法

延迟清除法(Lazy Sweep)是缩减因清除操作而导致的mutator最大暂停时间的方法。这个方法的伪代码如下:

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
new_obj(size){
#用延迟清除法找到对应的块
chunk = lazy_sweep(size)
if(chunk != NULL)
return chunk
#没有找到合适的,进行一次标记操作
mark_phase()
#再用延迟清除法找到对应的块
chunk = lazy_sweep(size)
if(chunk != NULL)
return chunk

allocation_fail()
}

lazy_sweep(size){
while($sweeping < $head_end)
if($sweeping.mark == TRUE)
$sweeping.mark == FALSE
#找到和大小合适的块
else if($sweeping.size > size)
chunk = $sweeping
$sweeping += $sweeping + $sweeping.size
return chunk
#没找到继续往下找
$sweeping += $sweeping + $sweeping.size
#遍历完了也没找到,$sweeping置为从头开始
$sweeping = $heap_start
return NULL
}

这里跟之前不同的是$sweeping是一个全局变量,每次执行lazy_sweep的时候都会从当前$sweeping的位置往后查找。如果第一次没有找到,第二次就会从头开始查找,如果第二次也没有查到,那就是没有可以分配的块了。一般情况下第一次查找范围变小了,mutator的执行时间就短了。但是有一个问题是就是当数据分配不均,比如说后面的都是活动对象,前面的都是空的,反而会增加mutator的时间。如何改善这个问题,后面会再说到。

引用计数法

GC的目的是为了释放无法被引用的对象,自然就会想到让每个对象记录下自己被引用的个数,如果个数为0表示无法被引用,那就可以对其进行回收。这种思路就是引用计数法(Reference Counting)。

基本方法

引用计数法最重要的就是引入了一个计数器,用来记录被引用的个数。首先先看一下引用计数法的伪代码实现:

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
#生成新对象
new_obj(size){
#从空闲链表中找到合适的块
obj = pickup_chunk(size, $free_list)

if(obj == NULL)
allocation_fail()
else
#对象有一个计数器,成功生成后计数器值是1
obj.ref_cnt = 1
return obj
}

#更新ptr指针,使其指向新对象obj
update_ptr(ptr, obj){
#被指向的对象计数器+1
inc_ref_cnt(obj)
#原来指向的对象计数器-1
dec_ref_cnt(*ptr)
#指向新对象
*ptr = obj
}

#计数器+1
inc_ref_cnt(obj){
obj.ref_cnt++
}

#计数器-1
dec_ref_cnt(obj){
#obj计数器-1
obj.ref_cnt--
#obj计数器为0,说明对象变成了"垃圾", 需要对其子对象计数器都-1, 因为这个对象不存在了。
if(obj.ref_cnt == 0)
for(child : children(obj))
dec_ref_cnt(*child)
#将obj连接到空闲链表中
reclaim(obj)
}

上面需要注意的一点是执行update_ptr的时候先执行了inc_ref_cnt后执行了dec_ref_cnt, 这是因为当update_ptr的前后两个对象是同一个时,如果先指向了dec_ref_cnt就会把这个对象删除,再执行inc_ref_cnt时就会出错,而顺序反过来就不会存在这个问题了。还有一点是引用计数法和标记清除法不一样的地方:引用计数法会在指针变动时发现是否是垃圾,从而立即回收,而标记清除法则即使发现了也不会立即回收,而是标记完后一起回收。

优点/缺点

  • 优点

    1. 可以即刻进行垃圾回收
    2. 最大暂停时间短: 只在发生引用关系变化时立即回收。
    3. 没有必要沿指针查找: 根据每个变量的引用计数来回收,不需要进行遍历。
  • 缺点

    1. 计数器值的增减处理繁重
    2. 计数器需要占用很多位: 计数器需要记录被引用的个数,这个记录位会占用不少的内存空间。
    3. 实现繁琐复杂
    4. 循环引用无法回收:
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      class Person {
      string name
      Person lover
      }

      taro = new Person("太郎") //执行后taro的引用计数为1
      hanako = new Person("花子") //执行后hanako的引用计数为1
      taro.lover = hanako //执行后hanako的引用计数为2
      hanako.lover = taro //执行后taro的引用计数为2
      taro = null //taro指向null, hanako引用计数-1,变为1
      hanako = null //hanako指向null, taro引用计数-1, 变为1
      //全部执行完后taro与hanako的引用计数都为1,不能被回收,但是又无法被引用, 照成了内存泄露的情况

用图来说请其中的过程如下:
循环引用图解

延迟引用计数法

上面说到引用计数法的计数器值得增减处理很繁重,为了改善这个缺点,引入了延迟引用计数法(Deferred Reference Counting)。延迟引用计数法利用ZCT(Zero Count Table)来记录计时器值在dec_ref_cnt()作用下变为0的对象, zct表内的值是指向这些对象的指针。

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
#update_ptr($ptr, obj)调用不变,只是dec_ref_cnt不会递每次都递归处理子节点的引用计数
dec_ref_cnt(obj){
obj.ref_cnt--
if(obj.ref_cnt == 0)
#$zct满了就执行一次扫描
if(is_full($zct) == TRUE)
scan_zct()
push($zct, obj)
}

new_obj(size){
obj = pickup_chunk(size, $free_list)

if(obj == NULL)
#空间不够执行一次扫描, 释放空间
scan_zct()
obj = pickup_chunk(size, $free_list)
if(obj == NULL)
allocation_fail()

obj.ref_cnt = 1
return obj
}
#扫描zct
scan_zct(){
#对根直接引用的对象都进行增量, 把根引用反映到计数器的值上
for(r : $roots)
(*r).ref_cnt++
#对子对象的计数器进行减量操作,回收
for(obj : $zct)
if(obj.ref_cnt == 0)
remove($zct, obj)
delete(obj)
#恢复根节点直接引用的对象计数器的值
for(r : $roots)
(*r).ref_cnt--
}

#减量操作和回收
delete(obj){
for(child : children(obj))
(*child).ref_cnt--
if((*child).ref_cnt == 0)
delete(*child)

reclaim(obj)
}

书举例说update_ptr($ptr, obj)改写成*$ptr = obj, 我理解这只是举了一个例子说明不需要增减计数器。实际后面的代码中可以看出,还是使用的update_ptr($ptr, obj),否则就没有对dec_ref_cnt(obj)的调用了。变化比较大的是dec_ref_cnt(obj函数,它不再递归调用子节点的计数器减量,而是直接把它放到zct结构中,在必要时调用scan_zct, 这就大大减少了计数器值得增减。

  • 优点: 延迟了根引用的技术,将垃圾一并回收,减轻了因根引用频发发生的变化导致计数器增减所带来的额外负担。
  • 缺点: 失去了引用计数法的一大优点–可即可回收垃圾。另外scan_zct()导致最大暂停时间延长了。

Sticky引用计数法

引用计数法有一个问题就是计数器要设置多大的位宽。如果设置的小了,有可能会出现存不下而溢出的情况;如果设置的大了,又会占用过多的空间。Sticky的思想就是设置一个固定大小的位数,这个位数要比较小,对于溢出的情况下面两种处理方式:

  • 什么都不做
    当计数器出现溢出时,不对其进行任何操作,其值就是能存储的最大值,一般情况下这个值很难达到,如果达到了这个值,证明其非常重要,其成为垃圾的可能性也非常小,对其计数不增也不减,不会存在什么大的问题。
  • 使用GC标记-清除算法进行管理
    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
    mark_sweep_for_counter_overflow(){
    #所有计数器清零
    reset_all_ref_cnt()
    mark_phase()
    sweep_phase()
    }

    #对所有可以达到的节点进行标记,每个节点及其子节点只会进栈一次,所以引用计数的值最多为2, 不会出现溢出的情况
    mark_phase(){
    for(r : $roots)
    #所有根节点放到标记栈中
    push(*r, $mark_stack)

    while(is_empty($mark_stack) == FALSE)
    obj = pop($mark_stack)
    #弹出栈,引用计数+1
    obj.ref_cnt++
    #只有引用计数为1才让其子节点进栈,已经进过的不会再进
    if(obj.ref_cnt == 1)
    for(child : children(obj))
    push(*child, $mark_stack)
    }

    #清除节点遍历堆,所有标记位为0的节点进行回收
    sweep_phase(){
    sweeping = $heap_top
    while(sweeping < $head_end)
    if(sweeping.ref_cnt == 0)
    reclaim(sweeping)
    sweeping += sweeping.size
    }

这么做可以在溢出后依然回收,而且没有对循环引用页适用,但是需要重置计数器。查找对象时没有设置标记位,而只是增量计数器,会出现多次查找活动对象的问题。比起一般的GC标记-清除算法需要更多的时间,吞吐量也会变小。

1位引用计数法

1位引用计数法(1 bit Reference Counting)是Sticky引用计数法的极端例子,计数器只有1位大小。这里的计数器不在表示引用的个数,而是表示有一个引用还是多个引用。

  1. 当计数器值为0,表示对象引用数为1,这种状态称为UNIQUE
  2. 当计数器值为1, 表示引用数为复数, 这种状态称为MULTIPLE

相关伪代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#指针复制 
#dest_ptr: 目的指针
#src_ptr: 源指针
copy_ptr(dest_ptr, src_ptr){
#由于目的指针原来指向的内容不再指向,需要对目的指针指向删除操作
delete_ptr(dest_ptr)
#执行复制
*dest_ptr = *src_ptr
#目的指针由于和源指针指向了同一个对象,目的指针需要设置为MULTIPLE
set_multiple_tag(dest_ptr)
#源指针如果原来是UNIQUE, 现在多了一个目的指针,需要设置为MULTIPLE
if(tag(src_ptr) == UNIQUE)
set_multiple_tag(src_ptr)
}

#删除目的指针原来的指向对象
delete_ptr(ptr){
#如果原来是UNIQUE,说明对象只有一个指针,删除后需要回收
if(tag(ptr) == UNIQUE)
#回收
reclaim(ptr)
}

其过程可以参考下图:
1bit_rc

  • 优点:
    1. 不容易出现高速缓存缺失, 如上图所示,在更新计数器的时候不需要读取元素的值到内存中(C,D完全没有读), 只需要更新指针的计数器,所以不会出现内存中离得远找出缓存缺失。
    2. 计数器所占空间很小,节省内存。
  • 缺点: 1位引用计数器是在大量计数器都不足2的前提下来做的,当出现大量大于2的计数器时,1位引用计数器方法就无法回收这些对象,给堆带来巨大负担。

部分标记-清除算法

部分标记清除法主要是针对之前的无法回收循环引用的缺点而产生的。之前讲的延迟引用计数法可以处理循环引用的情况,但是效率太低。部分-标记清除算法只针对有可能是循环引用的对象上执行,在一般的对象上还是执行引用计数法。下面结合代码图图示说明一下部分标记-清除算法的过程。

部分标记-清除算法中,对象被涂成四种颜色来管理。每个颜色的含义如下:

  1. 黑(BLACK): 绝对不是垃圾的对象(对象产生时的初始颜色)
  2. 白(WHITE): 绝对是垃圾的对象
  3. 灰(GRAY): 搜索完毕的对象
  4. 阴影(HATCH): 可能是循环垃圾的对象

首先我们假设有一个循环引用对象群,初始状态如下:
初始状态
图中A和D是由根引用。所有对象在初始状态下都为黑色。
对应的初始代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
new_obj(size){
obj = pickup_chunk(size)
if(obj != NULL)
#初始颜色会BLACK
obj.color = BLACK
obj.ref_cnt = 1
return obj
else if(is_empty($hatch_queue) == FALSE)
#当空间不够用时扫描可能是循环引用的对象,然后释放出新的空间, 再次调用new_obj
scan_hatch_queue()
return new_obj(size)
else
allocation_fail()
}

当执行dec_ref_cnt()时, 引用计数为0, 则回收。不为0时都认为是可能存在循环引用的对象, 都标记成HATCH, 并且把这个对象放到$hatch_queue当中。代码如下:

1
2
3
4
5
6
7
8
9
10
dec_ref_cnt(obj){
obj.ref_cnt--
#ref_cnt == 0, 回收对象
if(obj.ref_cnt == 0)
delete(obj)
#ref_cnt != 0 认为是可能存在循环引用的对象
else if(obj.color != HATCH)
obj.color = HATCH
enqueue(obj, $hatch_queue)
}

针对上面的图,如果A的引用被删除了,则执行dec_ref_cnt()之后的状态如下图:

执行dec_ref_cnt

这是对象群在调用new_obj()时已经没有心的内存空间可以使用,所以会触发scan_hatch_queue()函数的调用。对应代码如下:

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

scan_hatch_queue(){
#可能是循环引用的对象出队列
obj = dequeue($hatch_queue)
#如果颜色为HATCH, 依次调用下面的函数
if(obj.color == HATCH)
paint_gray(obj)
scan_gray(obj)
collect_white(obj)
##如果颜色不为HATCH, 证明不是循环引用对象,继续下一个元素
else if(is_empty($hatch_queue) == FALSE)
scan_hatch_queue()
}

上面需要调用的paint_gray(obj)函数主要作用是深度遍历对象,搜索过的对象标记位GRAY:

1
2
3
4
5
6
7
8
9
paint_gray(){
#对原来是BLACK或HATCH的对象标记为GRAY
if(obj.color == (BLACK | HATCH))
obj.color = GRAY
#深度遍历子节点,引用计数减量, 递归调用paint_gray记性标记
for(child : children(obj))
(*child).ref_cnt--
paint_gray(*child)
}

执行完上面的函数后,对象的状态如下图:
执行dec_ref_cnt
下面scan_gray(obj)的目的是扫描刚才的GRAY节点,把其中的垃圾对象找出来,标记成WHITE:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
scan_gray(obj){
if(obj.color == GRAY)
if(obj.ref_cnt > 0)
#ref_cnt>0, 不是垃圾,需要标记成BLACK
paint_black(obj)
#ref_cnt == 0, 是垃圾对象,标记成WHITE
else
obj.color = WHITE
for(child : children(obj))
scan_gray(*child)
}

paint_black(obj){
obj.color = BLACK
for(child : chidren(obj))
#由于执行paint_gray的时候ref_cnt--, 这里要恢复ref_cnt
(*child).ref_cnt++
if((*child).color != BLACK)
paint_black(*child)
}

标记后的对象如下:
执行dec_ref_cnt
到上面的步骤后,可以看出已经知道那些颜色为WHITE的对象就是垃圾对象,这些对象需要回收,回收代码入下:

1
2
3
4
5
6
7
collect_white(){
if(obj.color == WHITE)
obj.color = BLACK
for(child : children(obj))
collect_white(*child)
reclaim(obj)
}

回收后的图如下:
执行dec_ref_cnt
上面就是部分标记-清除算法的过程。这个算法的优点就是,只搜索可能是循环垃圾的对象群,就是阴影部分,如何确定这个范围呢?首先产生垃圾循环的条件有两个:

  1. 产生循环引用。
  2. 删除从外部到循环引用的引用。

部分标记-清除算法就利用dec_ref_cnt()函数来判断,如果引用计数减值后不为0, 那这个对象有可能就是循环对象的一份子。
这个算法的缺点就是需要三次查找对象,而每次查找的数量不少,所以付出的成本比较大。

GC复制算法

GC复制算法把原来的内存空间分为两部分(From空间和To空间), 当From空间不够分配时,就会执行GC复制算法,把From空间的活动对象复制到To空间,复制完成后交换From和To空间,GC结束,分配时去心的From空间查找。

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
copying(){
#$to_start To空间的起始地址
#$free 要copy到的起始地址
$free = $to_start
for(r : $roots)
*r = copy(*r)
#交换From 和 To 空间
swap($from_start, $to_start)
}

#执行From 到 To 的 copy
copy(obj){
# 如果obj.tag != COPIED, 此对象还没有被执行过COPY, 对其执行COPY
if(obj.tag != COPIED)
copy_data($free, obj, obj.size)
#执行完后改变tag值,下次不再对其执行COPY
obj.tag = COPIED
#forwarding是原来对象指向复制后的对象的指针,便于新老节点对应起来,下面递归查询的时候好查找
obj.forwarding = $free
#free是要复制到的起始地址,当复制完一个对象后,需要前进size, 到达新的地址(To空间空闲的起始地址)
$free += obj.size

#对执行过的对象执行深度遍历,全部活动子节点都COPY到TO空间
for(child : children(obj.forwarding))
*child = copy(*child)
#注意,当对根节点的元素执行时,返回的是根节点执行的obj.forwarding,
#所以全部执行完后,根节点结合就是原来的根节点集合的forwarding指针指向的元素
return obj.forwarding
}
1
2
3
4
5
6
7
8
9
10
11
12
13
new_obj(){
#这里FROM和TO等分,如果空间不够,执行GC
if($free + size > $from_start + HEAP_SIZE/2)
copying()
#执行完GC后空间还不够,返回失败
if($free + size > $from_start + HEAM_SIZE/2)
allocation_fail()

obj = $free
obj.size = size
$free += size
return obj
}

GC复制算法过程参考下面的图:
GC复制算法
GC复制算法
GC复制算法
GC复制算法

  • 优点:
  1. 优秀的吞吐量: 只需要搜索活动对象,不需要其他的搜索。
  2. 可实现高速分配: 不需要空闲链表,只移动$free指针,快速分配。
  3. 不会发生碎片化: 因为分配的都是连续的,GC之后也是连续的,对象都放在了堆的一端(叫做压缩)。
  4. 与缓存兼容: 深度优先遍历,关联的节点都被放到了相邻的位置。
  • 缺点:
  1. 堆使用效率低下: GC复制算法通常把堆分为二等分,只有一半可以来安排对象。
  2. 不兼容保守式GC算法: 会发生对象的移动。
  3. 递归调动函数: 递归复制,每次调用都会消耗栈,会有栈溢出的可能。

Cheney的GC复制算法

上面提到GC复制算法用递归复制,会有栈溢出的可能。Cheney的GC复制算法则采用广度优先的方式,用循环代替递归,解决栈溢出的问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
copying(){
scan = $free = $to_start
for(r : $roots)
*r = copy(r)
#广度优先遍历需要一个队列保,scan 到 $free 就是这个隐藏的队列
while(scan != $free)
for(child : children(scan))
*child = copy(*child)
scan += scan.size

swap($from_start, $to_start)
}

copy(){
#如果obj.forwarding是指向To空间指针则返回TRUE, 如果不是则返回FALSE
if(is_pointer_to_heap(obj.forwarding, $to_start) == FALSE)
copy_data($free, obj, obj.size)
obj.forwarding = $free
$free += obj.size
return obj.forwarding
}

Cheney复制算法
Cheney复制算法
Cheney复制算法
Cheney复制算法

这个算法的缺点是不能利用局部缓存,因为有关系的节点不是相邻的。

近似深度优先搜索方法

为了解决Cheney算法不能利用局部缓存,这里进行了一个改进,对于每个“页面”内部都是广度优先搜索。下面通过一个例子,看一下Cheney与近似深度优先搜索的方法对比:
图1,原始的引用关系:
近似深度优先搜索方法
图2,假设每三个节点占用一个”页面”的空间,下面就是Cheney方法,广度优先遍历后的ji结果:
近似深度优先搜索方法
可以看出,上图中相互引用的节点之间存储的比较分散,不容里利用局部缓存。
图3是利用近似深度优先搜索方法后的结果,可以看出分布比较集中,可以很好利用局部缓存。
近似深度优先搜索方法

多空间复制算法

上面降到复制算法的一个明显的特征就是堆的利用率低。为了改善这个问题,多空间复制的算法的思想就是把一个堆N等分,只对其中2块空间执行GC复制算法,对剩下的(N-2)块空间执行GC标记-清除算法,也就是把这两种算法组合起来使用。具体细节不再展开。这个方法的优点是可以更有效的利用堆,但是缺点也很明显,就是标记-清除算法的缺点:分配耗费时间,分块碎片化等。

总结

基本算法是进行GC的基本思想,每个算法都有其缺点和优点,没有算法能够完美解决所有问题。所以后面的算法利用这几种基本算法的组合和变形,更好的提高GC的性能。