统计一个数字二进制位1的个数

Tag Go
Posted on
View

最近一个需求需要使用golang实现一个兼容redis的无压缩的bitmap,需要提供一个bitcoun函数来统计这个bitmap中二进制位1的个数,查了一圈并没有找到类似的第三方库,因此决定自己实现一个.(利用一切机会造轮子

1. 问题简化

问题本质实际就是给定一个数字,比如一个二进制数10101101,计算出这个数字中二进制位1的个数,对于10101101这个数字来说它有5个位为1,即:10101101

对于这个问题,最简单的办法就是挨位数,不过这个办法太笨了,没有逼格。

那么有没有银弹呢?答案是肯定的,而且还不止一种。 退后 ,我要开始装逼了

2. 查表法

对于一个8位的数字来说,它只有256个值,因此完全可以预先计算好每个值的二进制位1个个数写入到映射表中,使用时直接查询这张映射表即可。

伪代码如下所示:

var count1map = map[uint8]uint8 {
    0b0000_0000: 0,
    0b0000_0001: 1,
    ...
    0b1111_1111: 8,
}

func bitcount(x uint8) uint8 {
    return count1map[x]
}

3. 移位法

查表法虽然可以应对8位这样值数量有限的数字,但是对于uint64 or int64这样64位的数字来说,它的值数量是非常多的,我们无法在内存中维护这样巨大的映射表,因此不能使用查表法来解决

Golang在bits包中提供一个OnesCount64(x uint64) int的函数,可以计算一个64位数字中二进制为1的个数,其源码如下:

const m0 = 0x5555555555555555 // 01010101 ...
const m1 = 0x3333333333333333 // 00110011 ...
const m2 = 0x0f0f0f0f0f0f0f0f // 00001111 ...
const m3 = 0x00ff00ff00ff00ff // etc.
const m4 = 0x0000ffff0000ffff

func OnesCount64(x uint64) int {
	const m = 1<<64 - 1
	x = x>>1&(m0&m) + x&(m0&m)
	x = x>>2&(m1&m) + x&(m1&m)
	x = (x>>4 + x) & (m2 & m)
	x += x >> 8
	x += x >> 16
	x += x >> 32
	return int(x) & (1<<7 - 1)
}

初看起来是有点懵逼的,一顿位运算操作怎么就能把1的个数算出来了呢?

这段代码注释中标明其来源于Hacker’s Delight第5章

骚操作

别着急,我们还是采用自底向上的思想来拆解下。

3.1 2位数字二进制位1的个数

我们先想一下如何计算2位的数字二进制位1的个数,答案是非常简单的:

func OnesCount2(x uint2) int {
    return (x & 0b01) + ((x >> 1) & 0b01)
}

x & 0b01就是求第0位是不是1,((x >> 1) & 0b01)就是求第1位是不是1,加起来就是x这个2位数字二进制位1的个数。

3.2 4位数字二进制位1的个数

对于一个4位数字,如1011,我们先按照3.1中的算法分别求出第3位与第2位即10 和 第1位与第0位即11的二进制位1的个数,然后再加起来就得出这个4位数字的二进制位1的个数了。

伪代码如下所示:

func OnesCount4(x uint4) int {
    x = x & 0b0101 + x >> 1 & 0b0101
    return x & 0b0011 + x >> 2 & 0b0011
}

计算过程如图: image.png

3.3 8位数字二进制位1的个数

8位数字计算过程与4位计算过程本质是相同的,都是拆解组合,伪代码如下:

func OnesCount8(x uint8) int {
    x = x & 0b01010101 + x >> 1 & 0b01010101
    x = x & 0b00110011 + x >> 2 & 0b00110011
    return x & 0b00001111 + x >> 4 && 0b00001111
}

计算过程如下: image.png

64位数字重复这个过程即可,回头看golang的代码应该就可以看懂了,这里就不再详细解释了。

另外这个算法过程还可以进一步优化,详细可以参考下:计算汉明权重的SWAR(SIMD within a Register)算法 感兴趣的可以研究一下,这里就不赘述了。

4. POPCNT指令

一些较新的CPU上支持POPCNT指令,可以通过硬件直接进行计算,Golang代码示例如下:

main.go文件

package main

import (
    "fmt"
    "math/bits"
    "math/rand"
    "time"
)

func main() {
    rand.Seed(time.Now().Unix())
    for i := 0; i < 100; i++ {
        var num = rand.Uint64()
        if popcnt(num) != bits.OnesCount64(num) {

            panic(fmt.Sprintf("i: %d, popcnt(%b) = %d, bits.OnesCount64(%b) = %d", i, num, popcnt(num), num, bits.OnesCount64(num)))
        }
    }
    fmt.Println("ok")
}

func popcnt(x uint64) int

amd64.s 文件

#include "textflag.h"

TEXT main·popcnt(SB), NOSPLIT, $0-8
    MOVQ x+0(FP), AX // 将参数x移到AX寄存器
    BYTE $0xf3; BYTE $0x48; BYTE $0x0f; BYTE $0xb8; BYTE $0xc0  // 计算二进制X中1的个数,golang编译器不支持POPCNT指令,这行对应于POPCNT AX, AX
    MOVQ AX, ret+8(FP) // 将结果存入ret
    RET

...

阅读全文 »

Go数据库连接池设置不合理导致大量TIME_WAIT连接占满端口问题排查与解决

Category Golang
Tag Go
Posted on
View

1. 问题与背景

最近公司内部准备尝试使用下腾讯的TDSQL,因此组内同学写了一段很简单的查询TDSQL的go web程序,使用ab对其进行一个简单压测以获取TDSQL的性能表现,go代码如下:

package main

import (
    "crypto/md5"
    "database/sql"
    "fmt"
    "log"
    "math/rand"
    "net/http"
    "strconv"
    "time"

    "github.com/gin-gonic/gin"
    _ "github.com/go-sql-driver/mysql"
)

func main() {
    r := gin.New()
    r.Use(gin.Logger())
    r.GET("/test", func(c *gin.Context) {
        c.JSON(200, gin.H{
            "message": "test",
        })
    })

    dbconnect, err := sql.Open("mysql", "user:passwd@tcp(10.43.0.43:3306)/dbname")
    if err != nil {
        panic(err)
    }
    dbconnect.SetMaxIdleConns(5)
    dbconnect.SetMaxOpenConns(10)
    dbconnect.SetConnMaxLifetime(time.Hour)
    dbconnect.SetConnMaxIdleTime(time.Hour)
    r.GET("tdsql_test", func(context *gin.Context) {
        muid := fmt.Sprintf("%x", md5.Sum([]byte(strconv.Itoa(rand.Intn(1000000000000)))))
        rows, err := dbconnect.Query(fmt.Sprintf("select muid from rtb_channel_0 where muid='%s'", muid))
        if err != nil {
            log.Fatal(err)
            context.JSON(http.StatusInternalServerError, gin.H{
                "error_code": -3,
            })
            return
        }

        rows.Close()

        context.JSON(http.StatusOK, gin.H{
            "error_code": 0,
            "error_msg":  muid,
            "data":       "result",
        })
    })

    r.Run(":9000")
}

ab压测命令如下:

ab -c 10 -n 500000 "http://127.0.0.1:9000/tdsql_test"

压测开始不久之后代码log.Fatal(err)就打印出了错误信息并退出了: image.png

dial tcp 10.43.0.43:3306: connect: cannot assign requested address

这段错误信息是说无法连接到10.43.0.43:3306 ,原因是无法分配请求地址号,就是说本地端口号都被占用了。那么我们就开始进行排查,端口号究竟是被谁占满的?

2. 排查过程

2.1 通过netstat命令查看端口都被谁占用

netstat -nta | grep 10.43.0.43

有如下输出: image.png 可以看到有大量处于TIME_WAIT状态的TCP连接,这些连接占用了大量的端口。那么这些TIMI_WAIT状态的TCP连接是从哪来的呢?

为了弄清楚这个问题,我们必须知道TIME_WAIT状态是怎么回事。

2.1.1 TIME_WAIT

image.png

上图是经典的TCP四次挥手断开连接的过程。可以看到在四次挥手的过程中,主动关闭连接的一端在收到对端发送的FIN包之后会进入TIME_WAIT状态,会等待2MSL之后才能真正关闭连接。

MSL: 最长报文段寿命(Maximum Segment Lifetime),是一个工程值(经验值),RFC标准是2分钟,不过有点太长了,一般是30秒,1分钟,2分钟。

为什么客户端TIME_WAIT状态等待2MSL呢?四次握手最后一步客户端向服务端响应ACK,后有两种情况:

  1. 服务端没有收到ACK,这时服务端会超时重传FIN
  2. 服务端收到了ACK,但是客户端不知道服务端有没有收到

无论1还是2,客户端都需要等待,要取这两种情况等待的最大值以应对最坏情况的发生,这个最坏的情况就是: 去向ACK消息的最大生存时间(MSL) + 来向FIN消息的最大生存时间(MSL) 。可以看到加起来正好是2MSL。等待2MSL,客户端就可以放心大胆的释放TCP连接了,此时可以使用该端口号连接任何服务器。

如果没有TIME_WAIT,新连接直接复用该连接占用的端口话,恰好回复的ACK包没有达到对端,导致对方重传FIN包,这时新连接就会被错误的关闭。

2.1.2 使用了连接池为什么还会出现大量的TIME_WAIT连接呢

首先大量的TIME_WAIT连接说明了我们的go程序建立了大量的连接然后又关闭了,但是理论上使用了连接池连接都应该得到复用,不会建立大量的连接才对。

这时我首先检查了是不是连接池的ConnMaxLifetimeConnMaxIdleTime设置的太小导致连接被关闭。我回看了代码发现同事设置了一个小时的时长,那么就不可能是这个原因了。

然后我将怀疑的矛头指向了TDSQL,因为TDSQL是我们首次使用,之前使用Mysql时也没有遇到过这个问题,会不会是TDSQL发送/回复了某个特殊的包导致了客户端主动断开呢?

2.2 验证是否是TDSQL的问题

为了验证上述的猜想,使用tcpdump在服务器上抓了个包

tcpdump -i any host 10.43.0.43 -w output.pcap

然后将抓到的outout.pcap包down下来后丢到本机wireshark中进行分析,选择一个端口过滤下可以看到整个tcp连接的所有包。

image.png

可以看到TDSQL发送的都是正常的mysql协议包,并没有什么特殊的包,因此到这里基本可以确认不是TDSQL的锅。

那么排查的重点又回到了golang连接池,golang连接池为什么会主动断开连接?

2.3 golang为什么会主动断开连接?

由于golang整个sql包非常复杂,我们可以自底向上的思路来排查问题,首先我们找到mysql驱动包go-sql-driver/mysql中关闭连接的函数:

func (mc *mysqlConn) Close() (err error)

它位于connection.go文件中。

下面我们使用dlv 来启动上面的go程序

$ dlv debug main.go

进入到dlv控制台,然后在控制台中输入break mysql.(*mysqlConn).Close在这个函数上打个断点,继续输入c 命令让程序继续执行,然后使用ab命令进行这个web程序进行压测。

不出所料程序断在了mysql.(*mysqlConn).Close。然后我们使用bt命令来打印下调用栈: image.png

可以清楚的看到整个核心调用链是:

rwos.Close -> driverConn.releaseConn -> DB.putConn -> driverConn.Close -> mysqlConn.Close

问题的关键是DB.putConn ,我们可以分析下源码:

func (db *DB) putConn(dc *driverConn, err error, resetSession bool) {
    ...
    added := db.putConnDBLocked(dc, nil)
    db.mu.Unlock()

    if !added {
        dc.Close()
        return
    }
}

func (db *DB) putConnDBLocked(dc *driverConn, err error) bool {
    if db.closed {
        return false
    }
    if db.maxOpen > 0 && db.numOpen > db.maxOpen {
        return false
    }
    if c := len(db.connRequests); c > 0 {
        var req chan connRequest
        var reqKey uint64
        for reqKey, req = range db.connRequests {
            break
        }
        delete(db.connRequests, reqKey) // Remove from pending requests.
        if err == nil {
            dc.inUse = true
        }
        req <- connRequest{
            conn: dc,
            err:  err,
        }
        return true
    } else if err == nil && !db.closed {
        if db.maxIdleConnsLocked() > len(db.freeConn) { // db.maxIdleConnsLocked()取自db.maxIdleCount
            db.freeConn = append(db.freeConn, dc)
            db.startCleanerLocked()
            return true
        }
        db.maxIdleClosed++
    }
    return false
}

从源码中我们可以得知是DB.putConnDBLocked返回了false导致了连接关闭。为了验证这一点可以继续使用dlv 在dc.Close()这一行打个断点,然后重新压测这个程序: image.png 可以看到程序确实是走到了dc.Close()这一行,我们继续打印上下文的数据: image.png

到这里我们就知道了是由于db.maxIdleCount == len(db.freeConn)导致了连接没有被复用。

db.maxIdleCount是我们代码中设置的dbconnect.SetMaxIdleConns(5)也就是5

那么问题的原因其实就很简单了,我们设置了最大闲置连接数为5,最大可建立连接数为10,那么进程中最多可出现10个连接,这10个连接中只有5个可以被丢回到连接池中复用,而另外5个连接由于超过了我们设置最大闲置连接数5所以不会被丢回到连接池中复用,因此使用完就close了。当并发高的情况下就会出现大量的连接打开与关闭。

3. 解决

最大闲置连接数设置成一个大于等于最大连接数的值即可,比如下面这样:

dbconnect.SetMaxIdleConns(10)
dbconnect.SetMaxOpenConns(10)

...

阅读全文 »

与世界分享我刚编的mysql http隧道工具-hersql原理与使用

Category Mysql
Tag Mysql
Tag Go
Posted on
View

原文地址:https://blog.fanscore.cn/a/53/

1. 前言

本文是与世界分享我刚编的转发ntunnel_mysql.php的工具的后续,之前的实现有些拉胯,这次重构了下。需求背景是为了在本地macbook上通过开源的mysql可视化客户端(dbeaver、Sequel Ace等)访问我司测试环境的mysql,整个测试环境的如图所示:

image.png

那么就有以下几种方式:

  • 客户端直连mysql #Pass# 测试环境mysql只提供了内网ip,只允许测试环境上的机器连接,因此不可行
  • 通过ssh隧道连接 #Pass# 测试环境机器倒是可以ssh上去,但是只能通过堡垒机接入,且堡垒机不允许ssh隧道,因此不可行
  • navicat http隧道连接 #Pass# 测试环境有机器提供了公网ip开放了http服务,因此技术上是可行的,但navicat非开源免费软件,我司禁止使用,因此不可行
  • 测试环境选一台机器建立mysql代理转发请求 #Pass# 测试环境机器只开放了80端口,且已被nginx占用,因此不可行
  • 内网穿透 这个想法很好,下次不要再想了

image.png

既然上面的方式都不行,那怎么办呢?因此我产生了一个大胆的想法

2. 一个大胆的想法

大概架构如下 image.png

首先,在本地pc上启动一个sidecar进程,该进程监听3306端口,实现mysql协议,将自己伪装为一个mysql server。本地pc上的mysql客户端连接到sidecar,发送请求数据包给sidecar,从sidecar读取响应包。

然后在测试环境某台机器上启动transport进程,该进程启动http服务,由nginx代理转发请求,相当于监听在80端口,然后连接到测试环境的mysql server。

sidecar会将来自客户端的请求包通过http请求转发给transporttransport将请求包转发到测试环境对应的mysql server,然后读取mysql的响应数据包,然后将响应数据包返回给sidecarsidecar再将响应包返回给mysql客户端。

遵循上述的基本原理,我将其实现出来: https://github.com/Orlion/hersql。但是在描述hersql的实现细节之前我们有必要了解下mysql协议

3. mysql协议

mysql客户端与服务端交互过程主要分为两个阶段:握手阶段与命令阶段。交互流程如下: image.png

在最新版本中,握手过程比上面要复杂,会多几次交互

3.1 握手阶段

在握手阶段,3次握手建立tcp连接后服务端会首先发送一个握手初始化包,包含了 * 协议版本号:指示所使用的协议版本。 * 服务器版本:指示MySQL服务器版本的字符串。 * 连接ID:在当前连接中唯一标识客户端的整数。 * 随机数据:包含一个随机字符串,用于后续的身份验证。 * 服务器支持的特性标志:指示服务器支持的客户端功能的位掩码。 * 字符集:指示服务器使用的默认字符集。 * 默认的身份验证插件名(低版本没有该数据)

随后客户端会发送一个登录认证包,包含了:

  • 协议版本号:指示所使用的协议版本。
  • 用户名:用于身份验证的用户名。
  • 加密密码:客户端使用服务端返回的随机数对密码进行加密
  • 数据库名称:连接后要使用的数据库名称。
  • 客户端标志:客户端支持的功能的位掩码。
  • 最大数据包大小:客户端希望接收的最大数据包大小。
  • 字符集:客户端希望使用的字符集。
  • 插件名称:客户端希望使用的身份验证插件的名称。

服务端收到客户端发来的登录认证包验证通过后会发送一个OK包,告知客户端连接成功,可以转入命令交互阶段

在mysql 8.0默认的身份验证插件为caching_sha2_password,低版本为mysql_native_password,两者的验证交互流程有所不同个,caching_sha2_password在缓存未命中的情况下还会多几次交互。另外如果服务端与客户端的验证插件不同的话,也是会多几次交互。

3.2 命令阶段

在命令阶段,客户端会发送命令请求包到服务端。数据包的第一个字节标识了当前请求的类型,常见的命令有:

  • COM_QUERY命令,执行SQL查询语句。
  • COM_INIT_DB命令,连接到指定的数据库。
  • COM_QUIT命令,关闭MySQL连接。
  • COM_FIELD_LIST命令,列出指定表的字段列表。
  • COM_PING命令,向MySQL服务器发送PING请求。
  • COM_STMT_系列预处理语句命令

请求响应的模式是客户端会发一个请求包,服务端会回复n(n>=0)个响应包

最后客户端断开连接时会主动发送一个COM_QUIT命令包通知服务端断开连接

4. hersql数据流转过程

在了解mysql协议之后我们就可以来看下hersql的数据流转过程了。

image.png

transport连接mysql server时必须要知道目标数据库的地址与端口号(mysql client连接的是sidecar),所以hersql要求mysql client需要在数据库名中携带目标数据库的地址与端口号。

transport发给mysql server的登录请求包中需要包含用mysql server发来的随机数加密之后的密码,但是mysql client给到sidecar的登录请求包中的密码是用sidecar给的随机数加密的,因此无法直接拿来使用,所以hersql要求mysql client需要在数据库名中携带密码原文,transport会用mysql server给的随机数进行加密, 这也是hersql的局限。

5. hersql使用

上面介绍了一堆原理性的东西,那么如何使用呢?

5.1 在一台能够请求目标mysql server的机器上部署hersql transport

首先你需要下载下来hersql的源码:https://github.com/Orlion/hersql,还需要安装下golang,这些都完成后你就可以启动hersql transport了。但是先别着急,我先解释下transport的配置文件tranport.example.yaml:

server:
  # transport http服务监听的地址
  addr: :8080

log:
  # 标准输出的日志的日志级别
  stdout_level: debug
  # 文件日志的日志级别
  level: error
  # 文件日志的文件地址
  filename: ./storage/transport.log
  # 日志文件的最大大小(以MB为单位), 默认为 100MB。日志文件超过此大小会创建个新文件继续写入
  maxsize: 100
  # maxage 是根据文件名中编码的时间戳保留旧日志文件的最大天数。 
  maxage: 168
  # maxbackups 是要保留的旧日志文件的最大数量。默认是保留所有旧日志文件。
  maxbackups: 3
  # 是否应使用 gzip 压缩旋转的日志文件。默认是不执行压缩。
  compress: false

你可以根据你的需求修改配置,然后就可以启动transport

$ go run cmd/transport/main.go -conf=transport.example.yaml

一般情况下都是会先编译为可执行文件,由systemd之类的工具托管transport进程,保证transport存活。这里简单期间直接用go run起来

5.2 在你本地机器部署启动hersql sidecar

同样的,你需要下载下来hersql的源码:https://github.com/Orlion/hersql,提前安装好golang。修改下sidecar的配置文件sidecar.example.yaml:

server:
  # sidecar 监听的地址,之后mysql client会连接这个地址
  addr: 127.0.0.1:3306
  # transport http server的地址
  transport_addr: http://x.x.x.x:xxxx
log:
  # 与transport配置相同

就可以启动sidecar

$ go run cmd/sidecar/main.go -conf=sidecar.example.yaml

同样的,一般情况下也都是会先编译为可执行文件,mac上是launchctl之类的工具托管sidecar进程,保证sidecar存活。这里简单期间直接用go run起来

5.3 客户端连接

上面的步骤都执行完成后,就可以打开mysql客户端使用了。数据库地址和端口号需要填写sidecar配置文件中的addr地址,sidercar不会校验用户名和密码,因此用户名密码可以随意填写

重点来了: 数据库名必须要填写,且必须要按照以下格式填写

[username[:password]@][protocol[(address)]]/dbname[?param1=value1&...&paramN=valueN]

举个例子:

root:123456@tcp(10.10.123.123:3306)/BlogDB

如图所示: image.png

5.4 举个例子

目标mysql服务器

  • 地址:10.10.123.123:3306
  • 数据库:BlogDB
  • 用户名:root
  • 密码:123456

可以直连目标mysql服务器的机器

  • 地址:10.10.123.100
  • 开放端口:8080

那么transport可以配置为

server:
  addr: :8080

sidecar可以配置为

server:
  addr: 127.0.0.1:3306
  transport_addr: http://10.10.123.100:8080

客户端连接配置

  • 服务器地址:127.0.0.1
  • 端口: 3306
  • 数据库名root:123456@tcp(10.10.123.123:3306)/BlogDB

5.5 局限

hersql目前只支持mysql_native_password的认证方式,mysql8默认的认证方式是caching_sha2_password,所以如果要通过hersql连接mysql8需要注意登录用户的认证方式是否是mysql_native_password,如果是caching_sha2_password那暂时是无法使用的。

6. 参考资料

如果hersql对你有帮助欢迎点个star

...

阅读全文 »

redis georadius源码分析与性能优化

Category Redis
Tag Redis
Tag Go
Posted on
View

背景

最近接到一个需求,开发中使用了redis georadius命令取附近给定距离内的点。完工后对服务进行压测后发现georadius的性能比预期要差,因此我分析了georadius的源码,并对原始的实现方案进行了优化,总结成了本文。

我们生产环境使用的redis版本为4.0.13,因此本文redis源码皆为4.0.13版本的源码

redis geo原理

往redis中添加坐标的命令是GEOADD key longitude latitude member [longitude latitude member ...],实际上redis会将经纬度转成一个52bit的整数作为zsetscore,然后添加到zset中,所以实际上redis geo底层就是个zset,你甚至可以直接使用zset的命令来操作一个geo类型的key。

那么经纬度是如何转成52bit整数的呢?业内广泛使用的方法是首先对经纬度分别按照二分法编码,然后将各自的编码交叉组合成最后的编码。我们以116.505021, 39.950898这个坐标为例看下如何编码:

  • 第一次二分操作,把经度分为两个区间:[-180,0)[0,180]116.505021落在右区间,因此用1表示第一次编码后的值
  • 第二次二分操作,把[0,180]分为两个区间[0,90)[90,180]116.505021落在右区间,因此用1表示第二次编码后的值
  • 第三次二分操作,把[90,180]分为两个区间[90,135)[135,180]116.505021落在左区间,因此用0表示第二次编码后的值
  • 按照这种方法依次处理,做完5次后,得到经度值的5位编码值:11010
分区次数 左区间 右区间 经度116.505021在区间 编码值
1 [-180, 0) [0, 180] [0, 180] 1
2 [0, 90) [90, 180] [90, 180] 1
3 [90, 135) [135, 180] [90, 135]) 0
4 [90, 112.5) [112.5, 135] [112.5, 135] 1
5 [112.5, 123.75) [123.75, 180] [112.5, 123.75] 0
  • 按照同样的方法对纬度值进行编码,得到纬度值的5位编码值:10111
分区次数 左区间 右区间 纬度39.950898在区间 编码值
1 [-90, 0) [0, 90] [0, 90] 1
2 [0, 45) [45, 90] [0, 45] 0
3 [0, 22.5) [22.5, 45] [22.5, 45]) 1
4 [22.5, 33.75) [33.75, 45] [33.75, 45] 1
5 [33.75, 39.375) [39.375, 45] [39.375, 45] 1

然后将经度编码11010和纬度编码值10111交叉得到最终geohash值1110011101

image.png

通常会使用base32将编码值转成字符串表示的hash值,与本文无关这里不多做介绍

根据如上的算法通常可以直观的写出如下的代码:

// 该代码来源于https://github.com/HDT3213/godis/blob/master/lib/geohash/geohash.go
func encode0(latitude, longitude float64, bitSize uint) ([]byte, [2][2]float64) {
	box := [2][2]float64{
		{-180, 180}, // lng
		{-90, 90},   // lat
	}
	pos := [2]float64{longitude, latitude}
	hash := &bytes.Buffer{}
	bit := 0
	var precision uint = 0
	code := uint8(0)
	for precision < bitSize {
		for direction, val := range pos {
			mid := (box[direction][0] + box[direction][1]) / 2
			if val < mid {
				box[direction][1] = mid
			} else {
				box[direction][0] = mid
				code |= bits[bit]
			}
			bit++
			if bit == 8 {
				hash.WriteByte(code)
				bit = 0
				code = 0
			}
			precision++
			if precision == bitSize {
				break
			}
		}
	}
	if code > 0 {
		hash.WriteByte(code)
	}
	return hash.Bytes(), box
}

可以看到基本就是上述算法的实际描述,但是redis源码中却是另外一种算法:

int geohashEncode(const GeoHashRange *long_range, const GeoHashRange *lat_range,
                  double longitude, double latitude, uint8_t step,
                  GeoHashBits *hash) {
    // 参数检查此处代码省略
    ...
    
    double lat_offset =
        (latitude - lat_range->min) / (lat_range->max - lat_range->min);
    double long_offset =
        (longitude - long_range->min) / (long_range->max - long_range->min);

    lat_offset *= (1 << step);
    long_offset *= (1 << step);
    // lat_offset与long_offset交叉
    hash->bits = interleave64(lat_offset, long_offset);
    return 1;
}

那么该如何理解redis的这种算法呢?我们假设经度用3位来编码 image.png 可以看到编码值从左到右实际就是从000111依次加1递进的,给定的经度值在这条线的位置(偏移量)就是其编码值。假设给定经度值为50,那么它在这条线的偏移量就是(50 - -180) / (180 - -180) * 8 = 5即101

georadius原理

georadius命令格式为GEORADIUS key longitude latitude radius m|km|ft|mi [WITHCOORD] [WITHDIST] [WITHHASH] [COUNT count] [ASC|DESC] [STORE key] [STOREDIST key],以给定的经纬度为中心, 返回键包含的位置元素当中, 与中心的距离不超过给定最大距离的所有位置元素。

image.png

首先需要明确一点的是并非两个坐标点编码相近其距离越近,以上图为例,虽然A所在区块的编码与C所在区块编码较之B更相近,但实际B点距离A点更近。为了避免这种问题redis中会先计算出给定点东南西北以及东北、东南、西北、西南八个区块以及自己身所在的区块即九宫格区域内所有坐标点,然后计算与当前点的距离,再进一步筛选出符合距离条件的点。

假设要查附近100km的点,那么要保证矩形的边长要大于100km,才能保证能获取到所有符合条件的点,地球半径约6372.797km,第一次分割后可以得到四个东西长6372.797*π,南北长3186.319*π,继续切割:

分割次数 东西长(km) 南北长(km)
1 6372.797*π 3186.319*π
2 3186.319*π 1593.160*π
3 1593.160*π 796.58*π
4 796.58*π 398.29*π
5 398.29*π 199.145*π
6 199.145*π 99.573*π
7 99.573*π 49.787*π

分割到第七次时南北长49.787*π,如果再切分长度为24.894*π,长度小于100km,因此停止分割,所以如果要查附近100km的点,我们需要的精度为7

redis中根据给定的距离估算出需要的精度的代码如下

const double MERCATOR_MAX = 20037726.37;

uint8_t geohashEstimateStepsByRadius(double range_meters, double lat) {
    if (range_meters == 0) return 26;
    int step = 1;
    while (range_meters < MERCATOR_MAX) {
        range_meters *= 2;
        step++;
    }
    step -= 2;
    // 高纬度地区地球半径小因此适当降低精度
    if (lat > 66 || lat < -66) {
        step--;
        if (lat > 80 || lat < -80) step--;
    }

    if (step < 1) step = 1;
    if (step > 26) step = 26;
    return step;
}

调用encode0函数就能计算出给定点在step = geohashEstimateStepsByRadius()精度级别所在矩形区域的geohash值。接下来计算该矩形区域附近的八个区域。

...
// 调用encode0函数计算geohash
geohashEncode(&long_range,&lat_range,longitude,latitude,steps,&hash);
// 计算出附近八个区域
geohashNeighbors(&hash,&neighbors);
...

一个区域的东侧区域只要将经度的编码值+1即可,反之西侧区域只要将经度编码值-1即可,北侧区域只要将纬度的编码值+1即可,南侧区域只要将纬度的编码值-1即可。对应redis源码如下:

void geohashNeighbors(const GeoHashBits *hash, GeoHashNeighbors *neighbors) {
    neighbors->east = *hash;
    neighbors->west = *hash;
    neighbors->north = *hash;
    neighbors->south = *hash;
    neighbors->south_east = *hash;
    neighbors->south_west = *hash;
    neighbors->north_east = *hash;
    neighbors->north_west = *hash;
    // 纬度加1就是东侧区域
    geohash_move_x(&neighbors->east, 1);
    geohash_move_y(&neighbors->east, 0);
    // 纬度减1就是西侧区域
    geohash_move_x(&neighbors->west, -1);
    geohash_move_y(&neighbors->west, 0);
    // 精度减1就是南侧区域
    geohash_move_x(&neighbors->south, 0);
    geohash_move_y(&neighbors->south, -1);

    geohash_move_x(&neighbors->north, 0);
    geohash_move_y(&neighbors->north, 1);

    geohash_move_x(&neighbors->north_west, -1);
    geohash_move_y(&neighbors->north_west, 1);

    geohash_move_x(&neighbors->north_east, 1);
    geohash_move_y(&neighbors->north_east, 1);

    geohash_move_x(&neighbors->south_east, 1);
    geohash_move_y(&neighbors->south_east, -1);

    geohash_move_x(&neighbors->south_west, -1);
    geohash_move_y(&neighbors->south_west, -1);
}

image.png 如上图所示,当给定点在中心区域的东北侧时,西北、西、西南、南、东南五个方向的区域中的所有点距离给定点肯定超过了给定距离,所以可以过滤掉,redis代码如下所示:

if (steps >= 2) {
    if (area.latitude.min < min_lat) {
        GZERO(neighbors.south); // 南侧区域置零,过滤南侧区域
        GZERO(neighbors.south_west);
        GZERO(neighbors.south_east);
    }
    if (area.latitude.max > max_lat) {
        GZERO(neighbors.north);
        GZERO(neighbors.north_east);
        GZERO(neighbors.north_west);
    }
    if (area.longitude.min < min_lon) {
        GZERO(neighbors.west);
        GZERO(neighbors.south_west);
        GZERO(neighbors.north_west);
    }
    if (area.longitude.max > max_lon) {
        GZERO(neighbors.east);
        GZERO(neighbors.south_east);
        GZERO(neighbors.north_east);
    }
}

计算出区块后下一步就需要将九宫格区域中的所有坐标点拿出来,依次计算与给定点的距离,然后过滤出符合给定距离的点

// 遍历九宫格内所有点,依次计算与给定点的距离,然后过滤出符合给定距离的点添加到ga中
int membersOfAllNeighbors(robj *zobj, GeoHashRadius n, double lon, double lat, double radius, geoArray *ga) {
    GeoHashBits neighbors[9];
    unsigned int i, count = 0, last_processed = 0;
    int debugmsg = 1;

    neighbors[0] = n.hash;
    neighbors[1] = n.neighbors.north;
    neighbors[2] = n.neighbors.south;
    neighbors[3] = n.neighbors.east;
    neighbors[4] = n.neighbors.west;
    neighbors[5] = n.neighbors.north_east;
    neighbors[6] = n.neighbors.north_west;
    neighbors[7] = n.neighbors.south_east;
    neighbors[8] = n.neighbors.south_west;

    // 遍历九宫格
    for (i = 0; i < sizeof(neighbors) / sizeof(*neighbors); i++) {
        ...
        // 当给定距离过大时,区块可能会重复
        if (last_processed &&
            neighbors[i].bits == neighbors[last_processed].bits &&
            neighbors[i].step == neighbors[last_processed].step)
        {
            continue;
        }
        // 取出宫格内所有点,依次计算距离,符合条件后添加到ga中
        count += membersOfGeoHashBox(zobj, neighbors[i], ga, lon, lat, radius);
        last_processed = i;
    }
    return count;
}

int membersOfGeoHashBox(robj *zobj, GeoHashBits hash, geoArray *ga, double lon, double lat, double radius) {
    GeoHashFix52Bits min, max;
    // 根据区块的geohash值计算出对应的zset的score的上下限[min,max]
    scoresOfGeoHashBox(hash,&min,&max);
    // 取出底层的zset中的[min,max]范围内的元素,依次计算距离,符合条件后添加到ga中
    return geoGetPointsInRange(zobj, min, max, lon, lat, radius, ga);
}

georadius优化

从上一节中可以看到,给定距离范围越大,则九宫格区域越大,九宫格区域内的点就越多,而每个点都需要计算与中间点的距离,距离计算又涉及到大量的三角函数计算,所以这部分计算是十分消耗CPU的。又因为redis工作线程是单线程的,因此无法充分利用多核,无法通过增加redis server的CPU核数来提升性能,只能添加从库。

距离计算算法及优化可以看下美团的这篇文章: https://tech.meituan.com/2014/09/05/lucene-distance.html

对于这个问题,我们可以将九宫格以及距离计算部分提升到我们的应用程序即redis客户端来进行,步骤如下: * 在客户端计算出九宫格区域,然后转为zset score的范围 * 使用zrangebyscore命令从redis取出score范围内的所有点 * 遍历所有点依次计算与给定点的距离,筛选出符合距离条件的点

陌陌好像也是使用了这种方案:https://mp.weixin.qq.com/s/DL2P49y4R1AE2MIdkxkZtQ

由于我们使用golang进行开发,因此我将redis中的georadius部分代码转为了golang代码,并整理成一个库开源在了github:https://github.com/Orlion/go-georadius

原本的写法是:

client.GeoRadius(key, longitude, latitude, &redis.GeoRadiusQuery{
	Radius:    1000,
	Unit:      "m", // 距离单位
	Count:     1,          // 返回1条
	WithCoord: true,       // 将位置元素的经纬度一并返回
	WithDist:  true,       // 一并返回距离
})

改造后:

ga := make([]redis.Z, 0)
ranges := geo.NeighborRanges(longitude, latitude, 1000)
for _, v := range ranges {
    zs, _ := client.ZRangeByScoreWithScores(key, redis.ZRangeBy{
		Min: strconv.Itoa(int(v[0])),
		Max: strconv.Itoa(int(v[1])),
	}).Result()
	for _, z := range zs {
	    dist := geox.GetDistanceByScore(longitude, latitude, uint64(z.Score))
		if dist < 1000 {
		    ga = append(ga, z)
		}
	}
}

压测结果对比

43w坐标点,取附近50000m(九宫格内有14774点,符合条件的点约6000个)

50km优化前

Concurrency Level:      5
Time taken for tests:   89.770 seconds
Complete requests:      5000
Failed requests:        0
Write errors:           0
Total transferred:      720000 bytes
HTML transferred:       0 bytes
Requests per second:    55.70 [#/sec] (mean)
Time per request:       89.770 [ms] (mean)
Time per request:       17.954 [ms] (mean, across all concurrent requests)
Transfer rate:          7.83 [Kbytes/sec] received

Connection Times (ms)
              min  mean[+/-sd] median   max
Connect:        0    0   0.0      0       0
Processing:    23   90  10.7     90     159
Waiting:       23   89  10.7     89     159
Total:         23   90  10.7     90     159

Percentage of the requests served within a certain time (ms)
  50%     90
  66%     93
  75%     96
  80%     97
  90%    102
  95%    107
  98%    111
  99%    116
 100%    159 (longest request)

50km优化后

Concurrency Level:      5
Time taken for tests:   75.447 seconds
Complete requests:      5000
Failed requests:        0
Write errors:           0
Total transferred:      720000 bytes
HTML transferred:       0 bytes
Requests per second:    66.27 [#/sec] (mean)
Time per request:       75.447 [ms] (mean)
Time per request:       15.089 [ms] (mean, across all concurrent requests)
Transfer rate:          9.32 [Kbytes/sec] received

Connection Times (ms)
              min  mean[+/-sd] median   max
Connect:        0    0   0.0      0       0
Processing:    21   75  14.2     75     159
Waiting:       21   75  14.1     75     159
Total:         21   75  14.2     75     159

Percentage of the requests served within a certain time (ms)
  50%     75
  66%     80
  75%     84
  80%     86
  90%     92
  95%     98
  98%    104
  99%    111
 100%    159 (longest request)

可以看到性能并没有巨大的提升,我们减小距离范围到5km(符合条件的点有130个)再看下压测结果

5km优化前

Concurrency Level:      5
Time taken for tests:   14.006 seconds
Complete requests:      5000
Failed requests:        0
Write errors:           0
Total transferred:      720000 bytes
HTML transferred:       0 bytes
Requests per second:    356.99 [#/sec] (mean)
Time per request:       14.006 [ms] (mean)
Time per request:       2.801 [ms] (mean, across all concurrent requests)
Transfer rate:          50.20 [Kbytes/sec] received

Connection Times (ms)
              min  mean[+/-sd] median   max
Connect:        0    0   0.0      0       0
Processing:     2   14   5.5     12      33
Waiting:        2   14   5.5     12      33
Total:          2   14   5.5     12      34

Percentage of the requests served within a certain time (ms)
  50%     12
  66%     16
  75%     19
  80%     20
  90%     22
  95%     23
  98%     27
  99%     28
 100%     34 (longest request)

5km优化后

Concurrency Level:      5
Time taken for tests:   16.661 seconds
Complete requests:      5000
Failed requests:        0
Write errors:           0
Total transferred:      720000 bytes
HTML transferred:       0 bytes
Requests per second:    300.11 [#/sec] (mean)
Time per request:       16.661 [ms] (mean)
Time per request:       3.332 [ms] (mean, across all concurrent requests)
Transfer rate:          42.20 [Kbytes/sec] received

Connection Times (ms)
              min  mean[+/-sd] median   max
Connect:        0    0   0.0      0       0
Processing:     3   17   5.8     16      66
Waiting:        3   16   5.8     16      66
Total:          3   17   5.8     16      66

Percentage of the requests served within a certain time (ms)
  50%     16
  66%     20
  75%     21
  80%     22
  90%     24
  95%     26
  98%     28
  99%     30
 100%     66 (longest request)

可以看到当优化后性能更差了

image.png

猜测造成这个结果的原因应该是附近5km九宫格内的点比较少,所以优化后实际没减少多少距离计算,但多了n(n<=9)倍的请求数,多了额外的命令解析与响应内容的消耗,因此这种优化方案仅仅适用于附近点特别多的情况

参考资料

...

阅读全文 »

网络编程中的tips

Category 计算机网络
Posted on
View

Connection reset by peer

网络编程中某一端可能会产生Connection reset by peer的报错,这是因为收到了对端发送的RST包。RST包是在tcp异常关闭时发出的,产生的情形很多。 我在写cat-agent 也遇到了这个报错,经排查发现是客户端发送数据后没有读取服务端的响应而直接关闭了连接(之所以不读取就关闭是因为客户端为提高发送效率不care服务端返回,后来为避免大量的RST包选择服务端不回包来解决)

EPOLL_CLOEXEC

epoll_create1() flags中有个EPOLL_CLOEXEC,类似的还有open()函数的O_CLOEXEC,它们的用处在于:当父进程fork出子进程之后,子进程会继承父进程的文件描述符,当子进程执行exec系统调用之后保存文件描述符的变量就不存在了,这些继承过来的文件描述符将无法关闭。 xxx_CLOEXEC选项就可以标识当子进程执行exec系统调用之后就内核自动关闭继承过来的文件描述符。

syscall.Forklock

在go标准库和其他一些网络库创建socket通常会有如下的代码: syscall.ForkLock.RLock() s, err = socketFunc(family, sotype, proto) if err == nil { syscall.CloseOnExec(s) } syscall.ForkLock.RUnlock() syscall.CloseOnExec(s)与上一节的xxx_CLOEXEC选项作用的相同的。这里ForkLock的作用是保证fork操作时socket的创建与设置CloseOnExec原子性。

持续更新中

...

阅读全文 »

与世界分享我刚编的转发ntunnel_mysql.php的工具

Category 杂文
Tag 杂文
Posted on
View

背景

先说背景吧,我司目前是通过phpMyAdmin来操作mysql,phpMyAdmin每次都要输入账号密码,而且我们的数据库实例又非常多,每次登录还要先搜索一番。虽然搞了一些chrome插件来简化这个过程,但是个人还是不太满意,所以考虑使用桌面客户端来代替。 然而测试环境的mysql是无法直连的,虽然有些桌面客户端(比如navicat)提供了ssh隧道或者http代理来连接,但是我们开发机只开放了http server的端口,没有开放ssh(只能通过跳板机连接)。所以一些桌面客户端直连和通过ssh隧道来连接是不可能了,http代理方式倒是可以连接,但是貌似只有navicat提供了这个功能,而navicat是收费的。得,所有常规道路都不通了。 只能靠骚操作了

方案

1、内网穿透!把内网ssh服务暴露到公网去!

image.png 如上图 1. 首先开发机上agent进程同时连接代理服务器proxy server与本地ssh,做双向转发 2. 然后代理服务器proxy server监听来自我的mac上的桌面客户端的ssh隧道连接,做该连接和proxy server <=> agent这个tcp连接的双向转发 3. 这样mac上的桌面客户端就能建立到内网开发机的ssh隧道了 很好!我们现在就能通过ssh隧道连接到测试环境mysql了! 不过,过不了多久我们可能会遇到下面的情况↓↓↓

2、用http隧道代理tcp连接进而在80端口上提供ssh服务

先简单提下http隧道的原理吧: 1. 首先客户端会发放CONNECT请求给代理服务器,告诉代理服务器它要连接的目标ip+port 2. 代理服务器建立与目标ip+port的tcp连接然后返回给客户端HTTP 200 Connection Established报文 3. 这时候就建立起了连接,后续客户端到代理服务器的所有tcp报文都会被代理服务器转发到目标ip+port的tcp连接上 > 详情可以参考这篇文章:HTTP 隧道代理原理和实现 这个方案存在以下两个问题: 第一、80端口被nginx监听,而nginx不支持http tunnel,虽然有些插件可以实现,但是考虑到开发机许多同学都在使用,添加插件还是有风险的。 第二、与方案1同样的,偷开放ssh服务这件事就不能干🙈

3、做一个mysql server,解析客户端请求转发到http代理

先看图: image.png 在我的mac上起一个服务:hersql,“伪装”成mysql server,接收来自桌面客户端的连接,按照mysql协议从报文中解析出请求的dbsql,然后请求开发机上的navicat提供的代理工具:ntunnel_mysql.phpntunnel_mysql.php连接到db并执行sql,将结果返回给hersqlhersql将查询结果按照mysql协议包装成报文返回给桌面客户端。 完美!

hersql

在方案3中我实现了hersql并开源到了github: github.com/Orlion/hersql,供大家借鉴

...

阅读全文 »

golang sync.Pool分析

Category Golang
Tag Go
Posted on
View

如何使用就不讲了,网上很多文章

1. 结构

type Pool struct {
	noCopy noCopy // 用于保证pool不会被复制
	local     unsafe.Pointer // 实际类型是 [P]poolLocal
	localSize uintptr        // local的size
	victim     unsafe.Pointer // 在新一轮GC来临时接管local,用于减少GC之后冷启动之后的性能抖动
	victimSize uintptr        // 在新一轮GC来临时接管localSize
	New func() interface{} // 当pool中没有对象时会调用这个函数生成一个新的
}

type poolLocal struct {
	poolLocalInternal
	// 避免false sharing问题
	pad [128 - unsafe.Sizeof(poolLocalInternal{})%128]byte
}

type poolLocalInternal struct {
    // P的私有缓存区,使用时无需加锁,Put对象时优先放到这里
	private interface{}
	// 公共缓存区,本地P可以pushHead/popHead,其他P只能popTail
	shared  poolChain
}

// 双端队列
type poolChain struct {
	head *poolChainElt
	tail *poolChainElt
}

type poolChainElt struct {
	poolDequeue
	next, prev *poolChainElt
}

// 环形队列
type poolDequeue struct {
	headTail uint64 // 头尾指针,之所以用一个变量持有两个字段大概率是为了方便原子操作一次性修改两个值吧
	vals []eface // 容量从8开始,依次x2,上限为2 ^ 30
}

type eface struct {
	typ, val unsafe.Pointer
}

image.png

2. Get

2.1 主流程

func (p *Pool) Get() interface{} {
    // 当G与P绑定禁止抢占,返回P对应的poolLocal以及P的id
	l, pid := p.pin()
	x := l.private
	l.private = nil
	if x == nil {
	    // 如果private为空则从shared头部pop出一个
		x, _ = l.shared.popHead()
		if x == nil {
		    // 如果shared中也没有则尝试从其他P的shared尾部偷一个
			x = p.getSlow(pid)
		}
	}
	// 解除非抢占
	runtime_procUnpin()
	if x == nil && p.New != nil {
	    // 如果上面的步骤都没有取到则New个出来
		x = p.New()
	}
	return x
}

其中涉及到了一些函数,我们再看下具体实现

2.2 pin

pin的作用是将当前G与P绑定,禁止被抢占。那么为什么要禁止被抢占呢?原因是G被抢占后再恢复执行之后再绑定的可能就不是被抢占之前的P了

func (p *Pool) pin() (*poolLocal, int) {
    // 执行绑定并返回当前pid
	pid := runtime_procPin()
	s := atomic.LoadUintptr(&p.localSize) 
	l := p.local
	if uintptr(pid) < s { // pid<localSize说明已经完成了poolLocal的创建,可以取
		return indexLocal(l, pid), pid
	}
	// pid>=localSize说明poolLocal还没有创建或者用户通过runtime.GOMAXPROCS(X)增加了p的数量,需要先创建
	return p.pinSlow()
}

// 返回local[i]即当前P的poolLocal
func indexLocal(l unsafe.Pointer, i int) *poolLocal {
	lp := unsafe.Pointer(uintptr(l) + uintptr(i)*unsafe.Sizeof(poolLocal{}))
	return (*poolLocal)(lp)
}

// runtime/proc.go
func procPin() int {
	_g_ := getg()
	mp := _g_.m
    // 完成禁止抢占
    // 调度器执行抢占g之前会canPreemptM(mp *m)判断是否可以执行抢占,而canPreemptM有一个条件为m.locks==0
	mp.locks++
	return int(mp.p.ptr().id)
}

2.2.1 pinSlow

pinSlow主要用来在poolLocal还未创建时创建新poolLocal

func (p *Pool) pinSlow() (*poolLocal, int) {
    // 解除禁止抢占
	runtime_procUnpin()
	// 上锁
	allPoolsMu.Lock()
	defer allPoolsMu.Unlock()
	// 禁止抢占
	pid := runtime_procPin()
	s := p.localSize
	l := p.local
	if uintptr(pid) < s {
	    // 上锁之前可能其他线程已经进入到pinSlow了,所以再判断一下
		return indexLocal(l, pid), pid
	}
	if p.local == nil {
	    // 说明local第一次初始化,需要将pool加到allPools中
		allPools = append(allPools, p)
	}
	// 获取p的数量
	size := runtime.GOMAXPROCS(0)
	// 创建local
	local := make([]poolLocal, size)
	atomic.StorePointer(&p.local, unsafe.Pointer(&local[0]))
	atomic.StoreUintptr(&p.localSize, uintptr(size))
	return &local[pid], pid
}

2.3 poolChain.popHead

我们再看下Get主流程中从shared中通过popHead从shared头部pop出一个对象的实现

func (c *poolChain) popHead() (interface{}, bool) {
	d := c.head
	for d != nil { // 从链表头开始遍历,d的type为*poolDequeue
		if val, ok := d.popHead(); ok {
			return val, ok
		}
		d = loadPoolChainElt(&d.prev)
	}
	return nil, false
}

2.3.1 poolDequeue.popHead

poolDequeue.popHead用来从环形队列头部pop出一个缓存对象

func (d *poolDequeue) popHead() (interface{}, bool) {
	var slot *eface
	for {
		ptrs := atomic.LoadUint64(&d.headTail)
		head, tail := d.unpack(ptrs)
		if tail == head {
		    // 如果头尾指针相等则队列为空
			return nil, false
		}

        // 通过不断重试来实现无锁编程
        // 尝试将head-1然后修改poolDequeue.headTail
		head--
		ptrs2 := d.pack(head, tail)
		if atomic.CompareAndSwapUint64(&d.headTail, ptrs, ptrs2) {
		    // 取到head对应的槽
			slot = &d.vals[head&uint32(len(d.vals)-1)]
			break
		}
	}

	val := *(*interface{})(unsafe.Pointer(slot))
	if val == dequeueNil(nil) {
		val = nil // 通过3.2.1 poolDequeue.pushHead分析,貌似val不可能为nil
	}
	
	// 清空槽
	*slot = eface{}
	return val, true
}

func (d *poolDequeue) unpack(ptrs uint64) (head, tail uint32) {
    // dequeueBits=32
	const mask = 1<<dequeueBits - 1
	head = uint32((ptrs >> dequeueBits) & mask) // &mask为了将高32位清零
	tail = uint32(ptrs & mask)
	return
}

func (d *poolDequeue) pack(head, tail uint32) uint64 {
	const mask = 1<<dequeueBits - 1
	return (uint64(head) << dequeueBits) |
		uint64(tail&mask)
}

type dequeueNil *struct{}

2.4 getSlow

再看下主流程中的getSlow函数的实现,getSlow用于在当前P缓存中没有时从其他P的共享缓存区偷缓存对象

func (p *Pool) getSlow(pid int) interface{} {
	size := atomic.LoadUintptr(&p.localSize) 
	locals := p.local
	// 从其他P偷
	for i := 0; i < int(size); i++ {
		l := indexLocal(locals, (pid+i+1)%int(size))
		// 从其他P的共享区的尾部偷
		if x, _ := l.shared.popTail(); x != nil {
			return x
		}
	}

    // 如果没有偷到,则尝试victim cache。我们将在尝试从所有主缓存中偷取之后这样做,因为我们想让victim cache中的对象尽可能的老化
	size = atomic.LoadUintptr(&p.victimSize)
	if uintptr(pid) >= size {
		return nil
	}
	locals = p.victim
	l := indexLocal(locals, pid)
	if x := l.private; x != nil {
		l.private = nil
		return x
	}
	for i := 0; i < int(size); i++ {
		l := indexLocal(locals, (pid+i)%int(size))
		if x, _ := l.shared.popTail(); x != nil {
			return x
		}
	}

    // 走到这里说明victim cache中也没有对象
	// 将victim cache标记为空,下次就不用尝试victim cache了
	atomic.StoreUintptr(&p.victimSize, 0)

	return nil
}

2.4.1 poolChain.popTail

getSlow中会通过poolChain.popTail从双端队列尾部pop对象,看下具体是如何操作的

func (c *poolChain) popTail() (interface{}, bool) {
    // 先获取双端队列的尾节点,因为这时被偷的P与当前P在并行,所以需要通过原子操作获取
	d := loadPoolChainElt(&c.tail)
	if d == nil {
	    // 尾节点为空说明被偷的P的双端队列为空直接返回即可
		return nil, false
	}

	for {
	    // 在pop tail之前load下一个指针是非常重要的,通常,d可能暂时为空,但是如果
	    // 在pop之前next非nil并且pop失败,那么d永远为空,这是唯一可以安全的从链表
	    // 中删除d的方法
		d2 := loadPoolChainElt(&d.next)

		if val, ok := d.popTail(); ok {
			return val, ok
		}

		if d2 == nil {
		    // next为空遍历终止
			return nil, false
		}
		
		// 走到这里说明当前尾节点为空,并且有下一个节点
		// 此时当前尾节点不可能有新对象被push进来了,可以删除掉了
		// 尝试将环形队列的尾节点指针改成它的下一个节点
		if atomic.CompareAndSwapPointer((*unsafe.Pointer)(unsafe.Pointer(&c.tail)), unsafe.Pointer(d), unsafe.Pointer(d2)) {
			// 走到这里说明赢得了race,清除prev指针以便gc能够收集空dequeue
			// 因此popHead不会在必要时再次备份
			storePoolChainElt(&d2.prev, nil)
		}
		d = d2
	}
}

要修改poolChain的空尾节点指针为尾节点的下一个节点必须同时满足下面两个条件(即删除当前尾节点) * 当前尾节点环形队列为空 * 当前尾节点必须有下一个节点

我们注意到golang中先获取了当前尾节点的next再popTail,这是为什么呢?如果先popTail再获取next有可能遇到这样的情况:

  1. d的队列为空popTail没有获取到数据
  2. 另外一个线程向d中push了n个对象,此时d不为空,并且生成了下一个节点
  3. 原子获取next,next不为空
  4. 误将还有缓存对象的d删除

2.4.1.1

func (d *poolDequeue) popTail() (interface{}, bool) {
	var slot *eface
	for {
		ptrs := atomic.LoadUint64(&d.headTail)
		head, tail := d.unpack(ptrs)
		if tail == head {
			// 说明队列为空
			return nil, false
		}

		ptrs2 := d.pack(head, tail+1)
		if atomic.CompareAndSwapUint64(&d.headTail, ptrs, ptrs2) {
			// 修改成功,这个solt就被我们占有了
			slot = &d.vals[tail&uint32(len(d.vals)-1)]
			break
		}
	}

    // 从槽中取值
	val := *(*interface{})(unsafe.Pointer(slot))
	if val == dequeueNil(nil) {
		val = nil
	}

	slot.val = nil
	atomic.StorePointer(&slot.typ, nil)

	return val, true
}

3. Put

3.1 主流程

// sync/pool.go
func (p *Pool) Put(x interface{}) {
	if x == nil {
		return
	}
	l, _ := p.pin() // 禁止G被抢占,并返回当前P对应的poolLocal
	if l.private == nil {
	    // 如果私有缓存为空则直接放到私有缓存区
		l.private = x
		x = nil
	}
	if x != nil {
	    // 如果私有缓存已经被占了,则放到共享缓存区头
		l.shared.pushHead(x)
	}
	runtime_procUnpin() // 解除禁止抢占
}

接下来我们看下新元素具体是如何放到共享缓冲区头部的

3.2 poolChain.pushHead

func (c *poolChain) pushHead(val interface{}) {
	d := c.head
	if d == nil {
	    // 头结点为空则需要进行初始化
		const initSize = 8 // 第一个节点的环形队列的长度为8
		d = new(poolChainElt)
		d.vals = make([]eface, initSize)
		// 其他P可能会从尾部偷对象,所以poolChain的tail需要用atomic set,保证对其他P可见
		c.head = d
		storePoolChainElt(&c.tail, d)
	}

    // push到头结点双端队列的头部
	if d.pushHead(val) {
		return
	}

	// 走到这里说明当前头节点的环形队列已经满了,所以申请一个新的节点
	// 新节点环形队列的长度为旧队列的两倍,但如果大于1 << 32 / 4则长度为1 << 32 / 4
	newSize := len(d.vals) * 2
	if newSize >= dequeueLimit {
		newSize = dequeueLimit
	}

	d2 := &poolChainElt{prev: d}
	d2.vals = make([]eface, newSize)
	// 修改双端队列的头节点为新创建的节点
	c.head = d2
	// 其他P可能会用到next所以需要原子store
	storePoolChainElt(&d.next, d2)
	d2.pushHead(val)
}

3.2.1 poolDequeue.pushHead

poolDequeue.pushHead用于将对象放到环形队列上

func (d *poolDequeue) pushHead(val interface{}) bool {
	ptrs := atomic.LoadUint64(&d.headTail)
	head, tail := d.unpack(ptrs)
	// dequeueBits = 32
	if (tail+uint32(len(d.vals)))&(1<<dequeueBits-1) == head {
		// 如果环形队列tail加上长度等于head,说明队列实际已经满了
		return false
	}
	// 找到head对应的槽,slot的类型为*eface
	slot := &d.vals[head&uint32(len(d.vals)-1)]

	typ := atomic.LoadPointer(&slot.typ)
	if typ != nil {
		return false
	}

	if val == nil {
		val = dequeueNil(nil) // 追了下代码调用链貌似val不可能为nil
	}
	// 将val放到槽上
	*(*interface{})(unsafe.Pointer(slot)) = val

	// 增加头指针
	atomic.AddUint64(&d.headTail, 1<<dequeueBits)
	return true
}

4. GC

上面的流程中我们清楚了对象是如何被缓存已经如何被写入和获取的,但是缓存池容量不是无限的,何时清理呢?答案是GC时。

sync/pool.go中有个init函数,在这个函数中注册了GC时如何清理Pool的函数

func init() {
    // 编译器会将poolCleanup赋值给runtime/mgc.go文件中`poolcleanup`变量
    // 在runtime.clearpools()函数中会调用poolcleanup,而在gcStart函数中在开始标记之前会调用clearpools()
	runtime_registerPoolCleanup(poolCleanup)
}

func poolCleanup() {
	for _, p := range oldPools {
	    // 先清除所有旧pool中的victim
	    // 之后gc就能标记清理旧pool中缓存的对象了
		p.victim = nil
		p.victimSize = 0
	}

	for _, p := range allPools {
	    // 用victim接管pool
		p.victim = p.local
		p.victimSize = p.localSize
		p.local = nil
		p.localSize = 0
	}

	oldPools, allPools = allPools, nil
}

当时看到这里时还有一点疑惑,poolCleanup为什么不写成下面这样:

func poolCleanup() {
	for _, p := range allPools {
	    // 用victim接管pool
		p.victim = p.local
		p.victimSize = p.localSize
		p.local = nil
		p.localSize = 0
	}
}

看起来也能清理缓存队列。但实际有个非常浅而已见的坑,那就是allPools这个切片一直在增长,必须将allPools设置为nil清理下才行,所以就必须引入oldPools。

5. 总结

sync.Pool为每个P搞一个缓存队列,避免所有线程共用同一个队列引发的锁竞争问题。

5.1 Put流程

  1. push到双端队列的头部的环形队列头部,如果环形队列已满则创建一个新的环形队列
  2. 将环形队列作为双端队列的新头部

5.2 Get流程

  1. 先从当前P缓冲区的私有缓存取
  2. 如果私有缓存没有从共享缓存区的双端队列的环形队列的头部pop
  3. 还没获取到则从其他P的共享缓存区的双端队列的环形队列的尾部pop
  4. 还没获取到则从victim cache中取

5.3 总结

总的来说只要清楚了sync.Pool的数据结构基本都理解的大差不差了,还是很简单的。

...

阅读全文 »

bitcask的设计与实现

Category 存储引擎
Tag LSM
Posted on
View

背景

最近在研究LSM tree,听闻bitcask在LSM tree各种各样的应用中是一个比较简单的实现,所以就以它为突破口,了解下LSM tree真实世界的实现。

bitcask存储模型由Riak提出,github上有各种语言的实现,本人挑选了一个golang版本的实现来进行研究,源码地址是:git.mills.io/prologic/bitcask,学习过程中我添加了一些注释,有需要的同学可以参考下:github.com/Orlion/bitcask

存储模型

与LSM tree的基本思想一样,bitcask中所有增删改操作都是追加写磁盘中的datafile,其数据结构如图: image.png

实际文件中是没有换行的,每个entry都是与前一个entry紧密串联在一起的,这里只是为了体现出来一个一个的entry。

datafile由一个一个的entry组成,每个entry的前4个字节存储key的size,第二个8字节存储value的size,然后顺序写入key和value,再写入校验和和过期时间的unix时间戳

datafile写入完成后可以得到新写入项的offset,然后将该key对应的offset与写入的数据项的size写入到内存的索引中,prologic/bitcask索引使用了artAdaptive Radix Tree(自适应前缀树)作为索引的数据结构,虽然不如hash表查找速度快,但因为是树状结构所以可以支持范围查找。

当datafile写入到一定的大小时会创建一个新的可读可写的datafile,在此之后的新数据会写入到这个新datafile中,老datafile会被设置为只读。因此一个bitcask实例会有多个datafile,所以索引中还必须存储key所在文件的id。

数据结构

image.png

  • path指向bitcask的工作目录,即各种文件的存放目录
  • curr指向当前可读写的datafile,数据都写入到该文件中
  • datafiles 为bitcask持有的所有datafile map,其中key为文件id
  • trie和ttlIndex指向内存中的索引树
  • isMerging标记当前是否在进行Merge

删除/修改key

上面提到bitcask中删除修改数据也是顺序写磁盘,那么写入的是什么样的数据呢?

实际上,bitcask中修改数据与写入数据是同一个api,即都是Put(key, value []byte),所以修改key也是往datafile中追加写一个新entry,不同是会修改索引中key的指向为最新数据项在文件中的位置。

而删除数据其实就是put(key, []byte{})即向datafile写入空字节切片,写完之后会删除索引中的key。

查找key

get(key)时会先从内存的索引树中根据key找到key所在的文件id和offset以及size,然后通过mmap到对应datafile文件中offset处拉取entry,然后根据前12个字节处的key len与value len数据指示解析出key和value,检查下校验和,自此数据检索完成。

Merge过程

由于bitcask中增删改都是追加写文件,不可避免的磁盘占用会越来越多,所以需要在合适的时机执行merge操作,将old entry和deleted entry从磁盘中清理掉。

bitcask Merge的过程如下:

  1. 加写锁,判断当前是否有其他线程在执行merge,如果有则退出,如果没有则标记isMerging为true,解锁继续执行
  2. 加读锁,禁止数据写入,但是可以读
  3. 当前datafile刷盘,然后关闭当前datafile,将当前dafafile创建为只读datafile加到bitcask实例的datafile列表中,再创建一个新的当前可读写datafile,新的当前文件不执行merge
  4. 释放读锁
  5. 在工作目录下创建merge子目录,以merge目录为工作目录创建merge用的bitcask实例:mdb
  6. 遍历当前bitcask实例索引中的所有key,如果k在要merge的datafiles列表中的话则将k/v写入到mdb中,完成后关闭mdb
  7. 加写锁,禁止读写
  8. 关闭当前bitcask实例
  9. 删除当前工作目录中的所有文件
  10. 通过rename将mdb工作目录中的所有文件挪到当前工作目录下
  11. 重新打开实例
  12. isMerging标记为false,释放写锁,此时可进行读写

索引持久化

上文提到索引是存储在内存中的,这样的话进程重启后索引就需要重新构建,如果数据量多的话,可想而知进程启动得多慢。

所以bitcask中会在以下几个时机将内存中的索引持久化到磁盘中:

  1. bitcask实例关闭时
  2. 创建新的datafile之后

索引持久化流程

  1. 在工作目录中创建临时索引文件temp_index
  2. 遍历art索引树将节点的 k/item 写入到文件中
  3. temp_index文件rename为index

索引文件的使用

创建bitcask实例时,会检查工作目录下的索引文件,如果有索引文件,会将索引文件加载到内存中生成art索引树,然后判断索引文件是否是最新的,即索引文件生成后有没有新数据写入,如果不是最新的还需要从最新的datafile中读取数据到索引中。

如果没有索引文件则会遍历所有的datafile,遍历所有数据来构建索引。

总结

可以看到bitcask的实现还是非常简单(lou)的。put(k, v)加了全局锁,锁粒度较粗,并发读写性能应该不是很强。merge的过程要遍历所有的datafile,还要创建新文件,所以对系统的IO压力应该也比较大。

...

阅读全文 »

keynote中插入高亮代码的方法

Category 杂文
Tag 杂文
Posted on
View

直接复制vscode中的代码到keynote中效果惨不忍睹,经过一番搜索,发现了一种效果很好的方法,而且keynote中可编辑

1. 安装highlight

$ brew install highlight

2. 复制要插入的代码

3. 执行以下命令

$ pbpaste | highlight --syntax=go --style=github -k "Fira Code" -K 36 -u "utf-8" -t 4 -O rtf | pbcopy
  • –syntax 指定代码语法格式
  • -u 指定编码,否则中文会乱码
  • –style 指定高亮的样式
  • -K 指定代码的字大小

实际效果

image.png

...

阅读全文 »

brk与mmap

Posted on
View

1. 前言

glibc的malloc函数在申请大于128K的内存时使用mmap分配内存,mmap会从堆区和栈区中间的部分划分内存,而在申请小于128K的内存时使用brk从堆上划分内存。

2. brk/sbrk

brk是linux上一个系统调用,而sbrk是一个C库函数

2.1 brk函数原型

int brk(void *addr);

参数

参数 解释
addr 要调整到的内存地址

返回值

返回增加的大小

2.2 sbrk函数原型

void *sbrk(intptr_t increment);

参数

参数 解释
increment 增加的内存大小

返回值

返回增加之后的program break内存地址

2.3 brk的原理

brk实际是通过改变program break来实现的,这个program break可以理解为“堆顶指针”,意味着程序堆内存使用到了该位置。

image.png

而这种内存的分配方式有个问题,看下下图:

image.png

假设B已经被free了,但是由于上面有一个C对象,所以program break指针不能简单的向下移动来释放内存。那怎么办呢?

实际上free后不能立即归还内存,只是将这块内存标记为空闲,后续再申请内存时可以复用这块内存。并且两块连续的空闲内存可以合并为一块空闲内存,当最高地址空间的空闲内存大于128K时(可以通过M_TRIM_THRESHOLD选项调节),执行内存紧缩。对于上图来说,如果C也被free了,program break就可以指向A的结束地址了,就能释放一部分内存了。

难道这就是传说中的线性内存分配

3. mmap

3.1 mmap函数原型

void *mmap(void *addr, size_t len, int prot, int flags, int fd, off_t offset);

参数

参数 解释
addr 映射的起始地址,通常设置为NULL,由内核来分配
len 指定将文件映射到内存的部分的长度
prot 映射区域的保护方式,通常是下面几个选项的组合
flags 映射区的特性标志位,常用的有以下两个选项
fd 要映射到内存中的文件描述符
offset 文件映射的偏移量,必须是操作系统内存页大小的整数倍

返回值

返回映射区的起始地址

3.2 munmap函数原型

// 解除映射
int munmap(void *start, size_t length);

参数

参数 解释
start mmap返回的映射区的起始地址
length 映射区的大小

返回值

解除成功返回0,失败返回-1

3.3 mmap原理

linxu内核使用vm_area_struct结构来表示一个独立的虚拟内存区域(比如堆、栈、bss段、代码段等),一个进程会有多个vm_area_struct结构体,各个vm_area_struct使用树结构或者链表连接。

vm_area_struct结构包含了该区域的起止地址和其他信息以及一个vm_ops指针,vm_ops指针内部引出所有针对这个区域可用的系统调用函数。

mmap就是创建一个新vm_area_struct结构,并将其与文件磁盘地址做映射。

image.png

mmap申请的内存可以通过munmap释放。

4. 总结

方式 内存碎片 适用场景
brk 多,因为不可释放 申请小内存
mmap 无,因为可以直接释放 申请大内存,如果用来申请小内存的话就会创建非常多的vm_area_struct结构体,不划算

5. 参考资料

...

阅读全文 »