使用AVX2指令集加速推荐系统MMR层余弦相似度计算

发布于
分类 汇编
标签 Go
阅读数

1. 背景

前一段时间公司上线了一套Go实现的推荐系统,上线后发现MMR层虽然只有纯计算但耗时十分离谱,通过pprof定位问题所在之后进行了优化,虽然降低了非常多但是我们认为其中还有优化空间。

image.png

可以看到日常平均耗时126ms,P95 360ms。

MMR层主要耗时集中在了余弦相似度的计算部分,这部分我们使用的gonum库进行计算,其底层在x86平台上利用了SSE指令集进行了加速。

SSE指令集已经非常古老了,xmm寄存器只能存储两个双精度浮点数,每次只能并行进行两个双精度浮点数的计算,而AVX2指令集可以并行计算四个,理论上可以获得两倍的性能提升,因此我们决定自己使用AVX2指令集手写汇编的方式替代掉gonum库。

1.1 余弦相似度算法

余弦相似度的计算公式为

image.png

对应的代码为

import "gonum.org/v1/gonum/floats"

func CosineSimilarity(a, b []float64) float64 {
    dotProduct := floats.Dot(a, b) // 计算a和b的点积
    normA := floats.Norm(a, 2) // 计算向量a的L2范数
    normB := floats.Norm(b, 2) // 计算向量b的L2范数
    return dotProduct / (normA * normB)
}

2. Dot点积计算加速

gonum点积计算Dot的部分汇编代码如下:

TEXT ·DotUnitary(SB), NOSPLIT, $0
    ...
loop_uni:
	// sum += x[i] * y[i] unrolled 4x.
	MOVUPD 0(R8)(SI*8), X0
	MOVUPD 0(R9)(SI*8), X1
	MOVUPD 16(R8)(SI*8), X2
	MOVUPD 16(R9)(SI*8), X3
	MULPD  X1, X0
	MULPD  X3, X2
	ADDPD  X0, X7
	ADDPD  X2, X8

	ADDQ $4, SI   // i += 4
	SUBQ $4, DI   // n -= 4
	JGE  loop_uni // if n >= 0 goto loop_uni

    ...

end_uni:
	ADDPD    X8, X7
	MOVSD    X7, X0
	UNPCKHPD X7, X7
	ADDSD    X0, X7
	MOVSD    X7, sum+48(FP) // Return final sum.
	RET

可以看到其中使用xmm寄存器并行计算两个双精度浮点数,并且还采用了循环展开的优化手段,一个循环中同时进行4个元素的计算。

我们利用AVX2指令集并行计算四个双精度浮点数进行加速

loop_uni:
	// sum += x[i] * y[i] unrolled 8x.
	VMOVUPD 0(R8)(SI*8), Y0 // Y0 = x[i:i+4]
	VMOVUPD 0(R9)(SI*8), Y1 // Y1 = y[i:i+4]
	VMOVUPD 32(R8)(SI*8), Y2 // Y2 = x[i+4:i+8]
	VMOVUPD 32(R9)(SI*8), Y3 // Y3 = x[i+4:i+8]
	VMOVUPD 64(R8)(SI*8), Y4 // Y4 = x[i+8:i+12]
	VMOVUPD 64(R9)(SI*8), Y5 // Y5 = y[i+8:i+12]
	VMOVUPD 96(R8)(SI*8), Y6 // Y6 = x[i+12:i+16]
	VMOVUPD 96(R9)(SI*8), Y7 // Y7 = x[i+12:i+16]
	VFMADD231PD Y0, Y1, Y8 // Y8 = Y0 * Y1 + Y8
	VFMADD231PD Y2, Y3, Y9
	VFMADD231PD Y4, Y5, Y10
	VFMADD231PD Y6, Y7, Y11
	ADDQ $16, SI   // i += 16
	CMPQ DI, SI
	JG  loop_uni // if len(x) > i goto loop_uni

可以看到我们每个循环中同时用到8个ymm寄存器即一次循环计算16个数,而且还用到了VFMADD231PD指令同时进行乘法累积的计算。

最终Benchmark结果:

BenchmarkDot 一个循环中计算8个数
BenchmarkDot-2          14994770                78.85 ns/op
BenchmarkDot16 一个循环中计算16个数
BenchmarkDot16-2        22867993                53.46 ns/op
BenchmarkGonumDot Gonum点积计算
BenchmarkGonumDot-2      8264486               144.4 ns/op

可以看到点积部分我们得到了大约2.7倍的性能提升

3. L2范数计算加速

gonum库中进行L2范数计算的算法并不是常规的a1^2 + a2^2 ... + aN^2这种计算,而是采用了Netlib算法,减少了溢出和下溢,其Go源码如下:

func L2NormUnitary(x []float64) (norm float64) {
	var scale float64
	sumSquares := 1.0
	for _, v := range x {
		if v == 0 {
			continue
		}
		absxi := math.Abs(v)
		if math.IsNaN(absxi) {
			return math.NaN()
		}
		if scale < absxi {
			s := scale / absxi
			sumSquares = 1 + sumSquares*s*s
			scale = absxi
		} else {
			s := absxi / scale
			sumSquares += s * s
		}
	}
	if math.IsInf(scale, 1) {
		return math.Inf(1)
	}
	return scale * math.Sqrt(sumSquares)
}

其汇编代码比较晦涩难懂,但管中窥豹再结合Go源码可以看出来没有用到并行能力,每次循环只计算一个数

TEXT ·L2NormUnitary(SB), NOSPLIT, $0
    ...
loop:
	MOVSD   (X_)(IDX*8), ABSX // absxi = x[i]
	...

我们优化之后的核心代码如下:

loop:
	VMOVUPD 0(R8)(SI*8), Y0 // Y0 = x[i:i+4]
	VMOVUPD 32(R8)(SI*8), Y1 // Y1 = y[i+4:i+8]
	VMOVUPD 64(R8)(SI*8), Y2 // Y2 = x[i+8:i+12]
	VMOVUPD 96(R8)(SI*8), Y3 // Y3 = x[i+12:i+16]
	VMOVUPD 128(R8)(SI*8), Y4 // Y4 = x[i+16:i+20]
	VMOVUPD 160(R8)(SI*8), Y5 // Y5 = y[i+20:i+24]
	VMOVUPD 192(R8)(SI*8), Y6 // Y6 = x[i+24:i+28]
	VMOVUPD 224(R8)(SI*8), Y7 // Y7 = x[i+28:i+32]
	VFMADD231PD Y0, Y0, Y8 // Y8 = Y0 * Y0 + Y8
	VFMADD231PD Y1, Y1, Y9
	VFMADD231PD Y2, Y2, Y10
	VFMADD231PD Y3, Y3, Y11
	VFMADD231PD Y4, Y4, Y12
	VFMADD231PD Y5, Y5, Y13
	VFMADD231PD Y6, Y6, Y14
	VFMADD231PD Y7, Y7, Y15

	ADDQ $32, SI // i += 32
	CMPQ DI, SI
	JG  loop // if len(x) > i goto loop

我们采用原始的算法计算以利用到并行计算的能力,并且循环展开,一次循环中同时计算32个数,最终Benchmark结果:

BenchmarkAVX2L2Norm
BenchmarkAVX2L2Norm-2          29381442                40.99 ns/op
BenchmarkGonumL2Norm
BenchmarkGonumL2Norm-2           1822386               659.4 ns/op

可以看到得到了大约16倍的性能提升

4. 总结

通过这次优化我们在余弦相似度计算部分最终得到了(144.4 + 659.4 * 2) / (53.46 + 40.99 * 2) = 10.8倍的性能提升,效果还是非常显著的。相较于《记一次SIMD指令优化计算的失败经历》这次失败的初次尝试,本次还是非常成功的,切实感受到了SIMD的威力。

另外在本次优化过程中也涨了不少姿势

AVX-512指令降频问题

AVX-512指令因为并行度更高理论上性能也更高,但AVX-512指令会造成CPU降频,因此业界使用非常慎重,这一点可以参考字节的json解析库sonic的这个issue: https://github.com/bytedance/sonic/issues/319

循环展开优化

在一次循环中做更多的工作,优点有很多:

  • 减少循环控制的开销,循环变量的更新和条件判断次数更少,降低了分支预测失败的可能性
  • 增加指令并行性,更多的指令可以在流水线中并行执行

但一次循环使用过多的寄存器从实际Benchmark看性能确实更好,但是否存在隐患我没有看到相关的资料,希望这方面的专家可以指教一下。

...

阅读全文 »

又一个Rust练手项目-wssh(SSH over Websocket Client)

发布于
分类 Rust
标签 Rust
阅读数

1. wssh

1.1 开发背景

公司内部的发布系统提供一个连接到k8s pod的web终端,可以在网页中连接到k8s pod内。实现原理大概为通过websocket协议代理了k8s pod ssh,然后在前端通过xterm.js+websocket实现了web终端的效果。

但是每次需要进pod内调试点东西都需要打开浏览器进到发布系统里一通点点点才能进入,而发布系统页面加载的又非常慢,所以效率非常低。

因此使用Rust实现了一个命令行工具,可以在本机终端中通过命令连接到k8s pod,实现了类似于ssh client的效果。这样一来不仅简化了我登陆pod的过程,又熟悉了Rust,还输出了篇博客。

项目地址:github.com/Orlion/wssh

1.2 效果

  1. 通过-e test指定为测试环境,执行后会先调用发布系统的应用列表api查询出所有应用,然后在输出中列出所有应用供用户选择 App选择

  2. 选择应用后通过连接到websocket server,websocket server转发到与pod的ssh连接,实现“SSH”到应用的pod的效果 Pod

2. 原理

公司发布系统的现状: 公司发布系统

首先我们的发布系统提供了一个Websocket Server,这个server实际代理了到k8s pod ssh连接。然后在前端通过xterm.js模拟了一个终端,通过websocket连接到server。

wssh替换了前端: 架构

3. 实现细节

3.1 命令行参数解析

wssh命令行参数解析使用了clap这个库

let clap_command = clap::Command::new("wssh")
    .version("0.1.0") // 指定版本号
    .author("Orlion") // 作者
    .about("SSH over Websocket 客户端")
    .arg(  // 添加命令行参数
        clap::Arg::new("env")
            .long("env")
            .short('e')
            .help("环境 test/preview")
            .value_name("ENV")
            .required(true),
    );
let matches = clap_command.get_matches();
// 获取--env参数值
let env = matches.get_one::<String>("env").expect("请输入--env参数");

3.2 发布系统登录

1.1节所述,wssh会调用发布系统的api,发布系统需要先登录才能调用,但是调用登录api比较麻烦,还需要用户输入账号密码,因此wssh使用了github.com/thewh1teagle/rookie 库直接读取发布系统域名下的cookie,免去了输入账号密码的麻烦,非常的简单。

let domains = vec!["jumpserver.domain.com".into()];
let cookies = rookie::chrome(Some(domains)).map_err(|e| { // 使用rookie从chrome获取jumpserver的cookie
    error::from_string(format!("获取jumpserver cookie失败: {}", e.to_string()))
})?;

let mut cookie_map: HashMap<String, Cookie> = HashMap::new();
for cookie in cookies {
    if cookie.name == "sessionid" || cookie.name == "JUMPSERVER_SESS_ID" {
        cookie_map.insert(cookie.name.clone(), cookie);
    }
}

let cookies = cookie_map
    .values()
    .map(|cookie| format!("{}={}", cookie.name, cookie.value))
    .collect::<Vec<String>>()
    .join("; ");
}

3.3 命令行中输出应用列表

在命令行中输出列表供用户选择如果手动输出的话出来的效果是比较差的,因此找到了dialoguer这个库,这个库提供了一个模糊搜索的组件FuzzySelect

let app_index =
    dialoguer::FuzzySelect::with_theme(&dialoguer::theme::ColorfulTheme::default())
        .with_prompt("请选择应用") // 提示信息
        .item("0. 退出") // 为用户提供退出的选项
        .items(&app_selections) // 输出应用列表
        .default(0) // 默认选择退出
        .interact()
        .map_err(|e| error::from_string(format!("选择应用失败: {}", e.to_string())))?;

3.4 通过websocket登陆到pod

首先使用tokio_tungstenite库建立websocket连接。

let uri = format!(
    "wss://jumpserver.domain.com/ssh?ssh_token={}",
    urlencoding::encode(ssh_token),
);
let (socket, response) = tokio_tungstenite::connect_async(uri)
    .await
    .map_err(|e| error::from_string(format!("websocket连接失败: {}", e.to_string())))?;

开发这部分连接功能时踩了个“坑”,原因是刚开始开发时对Rust的异步特性不熟悉,所以想使用同步多线程的方案,所以开始使用了tungstenite::connect()创建了同步连接,后来在进行两个线程并行读写时遇到了问题,原因是connect返回的对象的read()方法和write()方法接收的是&mut self,因为Rust不允许同时存在两个可变引用,所以并发读写是不可能的。

所以后来换成了tokio_tungstenite::connect_async()函数,这个函数返回的对象提供了split()方法可以将一个连接切分成一个读句柄和一个写句柄,这样就可以并行读写了。

另外查阅文档的过程中也得知了TCP连接可拆分而TLS连接是不可拆分的,所以如果你的websocket server可以通过ws而没有强制wss的话可以使用rs-websocket这个古老的库,这个库的同步连接方法返回的TCP连接是可以拆分的。

3.5 标准输出的调整

要在本地输出远程ssh server输出的内容之前还需要做以下三个调整。

  1. 发送window-change请求 本地终端窗口大小初始化和发生变更时都需要同步ssh server的,以便获得一致的显示效果,如果不发送可能会导致显示内容被截断或者格式不正确,并且vim等命令依赖于准确的终端尺寸来显示界面。
  2. 将标准输出设置为raw模式。在raw模式下,标准输出表现为
    • 没有行缓存,会逐字节输出
    • 不会回显输入,必须由程序写入
    • 输出未规范化(例如,\n 表示“向下一行”,而不是“换行符”)
let mut stdout = std::io::stdout().into_raw_mode()

4. 总结

通过这个项目又加深了对Rust的理解,过程中还首次用到了反人类的生命周期标注🤦🏻‍♀️(虽然后面简化掉了),收获很大,Rust远比看上去简单。

同时越发感慨Go的简易性,Go的协程结合channelselect等组件无疑极大降低了并发编程的难度,如果使用Go来开发这个工具想必难度会相当低。

我的博客即将同步至腾讯云开发者社区,邀请大家一同入驻:https://cloud.tencent.com/developer/support-plan?invite_code=3ac3jhp77t0k8

...

阅读全文 »

磁盘哈希结构-Linear Hashing

发布于
分类 存储
阅读数

1. Linear Hashing

最近在思考一个问题,如果一个存储引擎不需要支持范围查询,那么使用hashtable这样的数据结构是否更合适?恰好看到了lotusdb中使用了一个diskhash的库,从源码看是使用了一种Linear Hashing的哈希表数据结构,由于磁盘与内存的特性不同,因此磁盘哈希结构与常见的内存hashtable不太一样,特意研究了下。

2. 数据结构

image.png

通过primaryFile文件来存储hash桶,每个桶上有slotsPerBucket个槽,每个槽存储一个KV对,桶的数量为2 ^ Level个。当所有槽都用完时,在overflowFile中创建溢出桶,并通过nextOverflow记录新创建的溢出桶在文件中的offset。

初次创建时,会将Level初始化为0,SplitBucketIndex为0,然后创建出primaryFile并初始出一个桶

3. Put

写入过程如下:

  • 计算key的hash,然后hash对桶数量取模计算出key所在的桶
bucketIndex := keyHash & ((1 << t.meta.Level) - 1)
  • 遍历bucketIndex对应的桶以及该桶所有溢出桶上的所有slot,寻找key对应的槽
    • 如果找到则原地更新
    • 如果没有找到说明这是一个新key,则在第一个空槽上插入
    • 如果是新key且没有空槽,这时就需要创建一个溢出桶出来
  • 如果是新增key,需要判断下当前的负载因子是否超过阈值,超过阈值需要进行扩容

3.1 创建溢出桶

一般情况下溢出桶的创建是通过调用File.Truncate()扩容实现的,这里还有个逻辑是在hashtable进行扩容时,有些溢出桶不再使用可以被释放,这些溢出桶会被缓存下来,在创建溢出桶复用这些被释放的溢出桶。

4. 扩容

Linear Hashing的扩容是其核心部分,与内存hashtable常见的扩容策略有所不同,这里重点解释下

4.1 扩容时机

每当新增key之后都会重新计算当前的负载因子,负载因子的计算公式如下

keyRatio := float64(t.NumKeys) / float64(t.NumBuckets*slotsPerBucket) // slotsPerBucket是一个常量

即KV对的数量除以槽的数量。当负载因子超过阈值(默认是0.7)时触发扩容

if keyRatio > t.options.LoadFactor {
	t.split()
}

4.2 扩容过程

Linear Hashing维护一个指针SplitBucketIndex,每次扩容时就拆分这个指针指向的桶。

拆分前会将存储桶的文件扩大一个桶的大小,即增加一个桶。拆分时遍历旧桶所有槽,重新计算槽所在的位置,然后迁移到新桶上。

然后将SplitBucketIndex加1指向下一个桶,加完之后如果溢出了则将SplitBucketIndex归零,这时还要将Level+1,即标识桶数量翻倍。

5. 删除

删除过程比较简单,首先计算key的hash,然后取模计算出所在的桶,遍历桶上所有槽,如果找到槽则将槽置为空,然后写回磁盘

...

阅读全文 »

一个用rust写的类似于Skywalking/CAT的迷你trace PHP扩展

发布于
分类 Rust
标签 Rust
标签 PHP
阅读数

1. 简介

最近在学习rust,恰好看到了skywalking的php扩展采用了rust编写。有用过Skywalking/CAT之类监控系统的同学应该知道,这类系统对我们开发工作帮助非常大,能够非常快的帮我们定位到问题的关键,比如说现在有一个api的请求响应非常慢,那我们就可以从系统提供的web ui中查询这个api请求的链路各个节点的耗时,从而精准的定位慢的关键。

image.png

但是这类系统搭建起来还是比较繁琐的,对于个人开发者或者一些小公司来说成本比较高,因此我在apache/skywalking-php的基础上对其进行精简和部分增强,去掉其上报到skywalking server的部分,将trace log写入到本地文件,在这个本地文件中会记录以下内容:

1. 调用CURL时,记录开始结束时间以及耗时,如果发生错误会将错误信息记录下来

{
	"trace_id": "b89143d7-0fda-43d5-a688-397aef0ee3ef",
	"kind": "CURL",
	"name": "https://error.blog.fanscore.cn/a/57/",
	"payload": {
		"http_code": "0",
		"query": "k1=v1&k2=k2&k3=v3",
		"curl_error": "Could not resolve host: error.blog.fanscore.cn"
	},
	"start_time": "10:19:03.596", // 时间格式%H:%M:%S%.3f
	"end_time": "10:19:03.602",
	"duration_in_micro": 5988 // 耗时
}

{
	"trace_id": "b89143d7-0fda-43d5-a688-397aef0ee3ef",
	"kind": "CURL",
	"name": "https://blog.fanscore.cn/a/57/",
	"payload": {
		"http_code": "200",
		"curl_error": "",
		"query": "k1=v1&k2=k2&k3=v3"
	},
	"start_time": "10:19:03.602",
	"end_time": "10:19:03.969",
	"duration_in_micro": 366647
}

2. 调用PDO函数时,记录开始结束时间以及耗时,如果发生错误会将错误信息记录下来

{
	"trace_id": "b89143d7-0fda-43d5-a688-397aef0ee3ef",
	"kind": "PDO",
	"name": "__construct",
	"payload": {
		"result": "unknown",
		"dsn": "mysql:host=127.0.0.1;dbname=blog;charset=utf8mb4"
	},
	"start_time": "10:19:03.969",
	"end_time": "10:19:03.980",
	"duration_in_micro": 11175
}
{
	"trace_id": "b89143d7-0fda-43d5-a688-397aef0ee3ef",
	"kind": "PDO",
	"name": "query",
	"payload": {
		"statement": "select * from article",
		"result": "object(PDOStatement)"
	},
	"start_time": "10:19:03.980",
	"end_time": "10:19:03.985",
	"duration_in_micro": 5471
}
{
	"trace_id": "b89143d7-0fda-43d5-a688-397aef0ee3ef",
	"kind": "PDO_STATEMENT",
	"name": "fetchAll",
	"payload": {
		"query_string": "select * from article",
		"result": "array(3)"
	},
	"start_time": "10:19:03.985",
	"end_time": "10:19:03.985",
	"duration_in_micro": 25
}

3. 捕获PHP代码中的错误

{
	"trace_id": "b89143d7-0fda-43d5-a688-397aef0ee3ef",
	"kind": "ERROR",
	"name": "E_WARNING: Undefined variable $undefined_value in /Users/orlion/workspace/nginx/www/ptrace/index.php on line 32",
	"payload": {},
	"start_time": "10:19:03.986",
	"end_time": "10:19:03.986",
	"duration_in_micro": 2
}

4. 捕获PHP代码中未捕获的异常

{
	"trace_id": "b89143d7-0fda-43d5-a688-397aef0ee3ef",
	"kind": "EXCEPTION",
	"name": "Exception: test exception in /Users/orlion/workspace/nginx/www/ptrace/index.php on line 34",
	"payload": {
		"trace": "#0 {main}"
	},
	"start_time": "10:19:03.986",
	"end_time": "10:19:03.986",
	"duration_in_micro": 1
}

5. 请求结束后会记录请求开始结束时间、状态码、GET/POST参数

{
	"trace_id": "b89143d7-0fda-43d5-a688-397aef0ee3ef",
	"kind": "URL",
	"name": "/index.php",
	"payload": {
		"$_GET": "{\"a\":\"1\",\"b\":\"2\",\"c\":\"3\"}",
		"$_POST": "[]",
		"method": "GET",
		"status_code": "200"
	},
	"start_time": "10:19:03.595",
	"end_time": "10:19:03.992",
	"duration_in_micro": 397178
}

2. 安装

  1. Requirement

很遗憾,目前只提供mac arm64版本,后续会编译出linux版本,但因为依赖的phper-framework/phper的库不支持windows,因此短期内恐怕不能提供windows版本了。

  1. 进入https://github.com/Orlion/minitrace/releases 下载编译好的扩展二进制文件到本地

  2. 假设第一步将扩展下载到了/tmp/minitrace-v0.1.0-macos-arm64.dylib,编辑php.ini配置文件加入以下配置

[minitrace]
;加载我们的扩展
extension=/tmp/minitrace-v0.1.0-macos-arm64.dylib
;将trace数据输出到/tmp/minitrace.log
minitrace.log_file = /tmp/minitrace.log
  1. 重启fpm

3. 测试使用

编辑以下php文件

<?php

$ch = curl_init();
curl_setopt($ch, CURLOPT_URL, 'https://error.blog.fanscore.cn/a/57/?k1=v1&k2=k2&k3=v3#aaa');
curl_setopt($ch, CURLOPT_RETURNTRANSFER, true);
$response = curl_exec($ch);

$ch = curl_init();
curl_setopt($ch, CURLOPT_URL, 'https://blog.fanscore.cn/a/57/?k1=v1&k2=k2&k3=v3#aaa');
curl_setopt($ch, CURLOPT_RETURNTRANSFER, true);
$response = curl_exec($ch);

$host = '127.0.0.1';
$db   = 'blog';
$user = 'root';
$pass = '123456';
$charset = 'utf8mb4';
$dsn = "mysql:host=$host;dbname=$db;charset=$charset";
$options = [
    PDO::ATTR_ERRMODE            => PDO::ERRMODE_EXCEPTION,
    PDO::ATTR_DEFAULT_FETCH_MODE => PDO::FETCH_ASSOC,
    PDO::ATTR_EMULATE_PREPARES   => false,
];
$pdo = new PDO($dsn, $user, $pass, $options);
$stm = $pdo->query('select * from article');
$rows = $stm->fetchAll();
foreach($rows as $row) {
    print_r($row);
}


var_dump($undefined_value);

throw new Exception('test exception');
?>

然后在浏览器中请求该文件,打开/tmp/minitrace.log就能看到如下输出:

{"trace_id":"b89143d7-0fda-43d5-a688-397aef0ee3ef","kind":"CURL","name":"https://error.blog.fanscore.cn/a/57/","payload":{"http_code":"0","query":"k1=v1&k2=k2&k3=v3","curl_error":"Could not resolve host: error.blog.fanscore.cn"},"start_time":"10:19:03.596","end_time":"10:19:03.602","duration_in_micro":5988}
{"trace_id":"b89143d7-0fda-43d5-a688-397aef0ee3ef","kind":"CURL","name":"https://blog.fanscore.cn/a/57/","payload":{"http_code":"200","curl_error":"","query":"k1=v1&k2=k2&k3=v3"},"start_time":"10:19:03.602","end_time":"10:19:03.969","duration_in_micro":366647}
{"trace_id":"b89143d7-0fda-43d5-a688-397aef0ee3ef","kind":"PDO","name":"__construct","payload":{"result":"unknown","dsn":"mysql:host=127.0.0.1;dbname=blog;charset=utf8mb4"},"start_time":"10:19:03.969","end_time":"10:19:03.980","duration_in_micro":11175}
{"trace_id":"b89143d7-0fda-43d5-a688-397aef0ee3ef","kind":"PDO","name":"query","payload":{"statement":"select * from article","result":"object(PDOStatement)"},"start_time":"10:19:03.980","end_time":"10:19:03.985","duration_in_micro":5471}
{"trace_id":"b89143d7-0fda-43d5-a688-397aef0ee3ef","kind":"PDO_STATEMENT","name":"fetchAll","payload":{"query_string":"select * from article","result":"array(3)"},"start_time":"10:19:03.985","end_time":"10:19:03.985","duration_in_micro":25}
{"trace_id":"b89143d7-0fda-43d5-a688-397aef0ee3ef","kind":"ERROR","name":"E_WARNING: Undefined variable $undefined_value in /Users/orlion/workspace/nginx/www/ptrace/index.php on line 32","payload":{},"start_time":"10:19:03.986","end_time":"10:19:03.986","duration_in_micro":2}
{"trace_id":"b89143d7-0fda-43d5-a688-397aef0ee3ef","kind":"EXCEPTION","name":"Exception: test exception in /Users/orlion/workspace/nginx/www/ptrace/index.php on line 34","payload":{"trace":"#0 {main}"},"start_time":"10:19:03.986","end_time":"10:19:03.986","duration_in_micro":1}
{"trace_id":"b89143d7-0fda-43d5-a688-397aef0ee3ef","kind":"URL","name":"/index.php","payload":{"$_GET":"{\"a\":\"1\",\"b\":\"2\",\"c\":\"3\"}","$_POST":"[]","method":"GET","status_code":"200"},"start_time":"10:19:03.595","end_time":"10:19:03.992","duration_in_micro":397178}

...

阅读全文 »

rust所有权和借用中的一些case

发布于
分类 Rust
标签 Rust
阅读数

前言

学习rust有一段时间了,也用rust写了两个小项目,过程中发现一些rust教程在所有权和引用这一章节的讲解还是不够丰富,有很多case没有讲到,对所有权和引用的理解不够深入,这就导致实际应用时经常卡在所有权和引用,后面查阅一些资料在社区请教一些大佬后才理解,因此将最近练习过程中遇到的一些所有权和引用方面的问题总结成本文,分享给大家,帮大家踩踩坑。

1. 所有权

let a = 1;
let b = a; // a拷贝给b
println!("{}", a); // 不会报错

a的值被拷贝给了b,a和b被存储在栈上,无需在堆上分配内存

let a = String::from("a");
let b = a;
println!("{}", a); // 会报错,上一行a的所有权转移给了b,a不能再使用了

新手在这里可能会产生疑问?当执行形如let b = a;这样的代码时,到底什么情况下发生拷贝,什么情况下转移所有权呢?问题的答案其实非常简单:

只要a实现了Copy trait,那么就会拷贝,如果没有实现则转移所有权

那么为什么不能拷贝呢?我们可以以String这个类型为例,String是一个复杂类型,由存储在栈上的堆指针、字符串长度、字符串容量组成。

我们假设这里也是拷贝,那么a和b都会持有这个堆指针,当变量离开作用域后,rust会自动清理堆内存,由于a和b都指向了同一位置,那么会释放两次,这就导致了bug。

因此rust这样解决问题:当a赋值给b后,rust认为a不再有效,因此a离开作用域之后不会二次释放,这就是把所有权从a转移到了b。a被赋值给b之后就失效了,因此不能再使用。

如果String实现了Copy trait,拷贝a给b时,把堆指针指向的数据也复制一遍,同时将新的堆指针给b,那么a和b就不会指向同一个位置,就不会二次释放,自然就不会发生二次释放的bug了。

以下类型实现了Copy trait

  • 所有整数类型,比如 u32
  • 布尔类型,bool,它的值是 true 和 false
  • 所有浮点数类型,比如 f64
  • 字符类型,char
  • 元组,当且仅当其包含的类型也都是 Copy 的时候。比如,(i32, i32) 是 Copy 的,但 (i32, String) 就不是
  • 不可变引用 &T,注意: 可变引用 &mut T 是不可以 Copy的(如果Copy相当于两个指针指向一个位置,又会出现上面的二次释放的问题了)

1.1 结构体

结构体所有权问题比较复杂,这里单独拿出来分析。

先看一个简单的

struct User {
    age:
}

let user1 = User {
    age: 100,
};

let user2 = user1;
println!("{:}", user1); // 会报错,因为User没有实现Copy trait,所以user1的所有权转移给了user2
println!("{:}", user1.sign_in_count); // 会报错,user1已经无法使用了

这里要注意,虽然user1分配在栈上,但它没有实现Copy trait,仍然会发生所有权的转移

再看看一个复杂的

struct User {
    username: String,
    age: i128,
}

let user1 = User {
    username: String::from("user1"),
    age: 100,
};

let user2 = User {
    username: user1.username,
    age: user1.age
};

println!("{}", user1.age); // 不会报错,age发生了copy,而非所有权转移,可以继续使用
println!("{}", user1.username); // 会报错,username发生了所有权的转移
println!("{:}", user1); // 会报错

这里需要注意的是结构体内部的字段发生所有权转移后,会导致结构体本身也无法继续使用。但是其内部发生copy的值还是可以继续使用的,也就是user1.age还能继续使用不会报错的原因。

1.2 Option 所有权转移问题

我们先明确一个规则: 只要Option<T>中的T实现了Copy trait,那么Option<T>就实现了Copy trait

let a = Some(String::from("hello world!"));
let b = a.unwrap();
let c = a.unwrap(); // 这里会报错

我们分析下报错的原因,首先看unwrap的源码

pub const fn unwrap(self) -> T {
    match self {
        Some(val) => val,
        None => unwrap_failed(),
    }
}

从上面可以看到,调用unwrap时,因为Option<String>没有实现Copy trait,所以a发生了所有权转移,a的所有权转移到了unwrap里,所以第二次调用unwrap时就会报错。

解决办法就是调用as_ref/as_mut或者将Option<String>换成Option<&String>,rust中引用默认实现了Copy trait,所以Opiton<&String>不会发生所有权转移 看下as_ref的源码:

pub const fn as_ref(&self) -> Option<&T> {
    match *self {
        Some(ref x) => Some(x),
        None => None,
    }
}

2. 引用

2.1 可变引用

只能可变的引用一个可变变量

let a = 1;
let b = &mut a; // 会报错,无法可变引用一个不可变变量

同一时刻只能存在一个可变引用

let mut a = 1;
let b = &mut a;
*b = 2;
println!("{}", a); // 会报错,可以将a理解成1的一个引用,因为下一行println!("{}", b);所以b这个可变引用的生命周期还未结束,那么此时如果使用a,则违反了可变引用与不可变引用不能同时存在的规则
println!("{}", b);

2.2 解引用

结构体解引用

let user = String::from("user");
let user_ref = &user;
let _user_1 = *user_ref; // 报错

第三行会报错:

error[E0507]: cannot move out of `*user_ref` which is behind a shared reference
  --> src/main.rs:30:19
   |
30 |     let _user_1 = *user_ref;
   |                   ^^^^^^^^^ move occurs because `*user_ref` has type `String`, which does not implement the `Copy` trait

这个报错看到有解释说不能解引用获取到所有权(String没有实现Copy trait只能将user的所有权转移给_user_1),但是这里将user的所有权转移给_user_1也并不会造成什么错误,所以我猜测是rust编译器限制了不能通过解引用间接转移所有权,只能直接转移。

这里还有个case:let _user_1 = &(*user_ref); 这种写法可以编译通过,猜测是编译器优化直接拷贝的引用,而不是先转移所有权再取引用。

3. 参考资料

...

阅读全文 »

一种应用于特定场景的支持LRU的线程安全的无锁uint32->uint32 cache实现

发布于
分类 存储
标签 Go
阅读数

1. 前言

几年前给公司前台业务一个QPS很高的接口做了一个优化,主要请求来源是当前在线用户,接口核心逻辑就是从codis中根据一个数字查询对应的用户id(小于1亿),这两个数字的映射关系是不变的,可以理解为codis中有一个map[uint32]uint32的映射表,这个映射表只增不改。

因为接口对codis造成压力很大,因此决定在Go内存中将映射关系缓存下来,但由于这个映射表很大所以不能全部缓存中内存。因此结合业务逻辑决定引入了一个支持LRU淘汰策略的uint32 -> uint32的高性能缓存组件。

调研之后发现市面上Go的各种线程安全还支持LRU的缓存都是有锁的,性能可能受限,因此决定根据应用场景自己搞个特殊的缓存组件。

2. 实现原理

首先还是贴一下源码仓库地址: https://github.com/Orlion/intcache

2.1 结构体定义:

type IntCache struct {
	b          uint8
	buckets    [][8]uint64
	lruBuckets []uint32
}

func New(b uint8) *IntCache {
	cap := 1 << b
	return &IntCache{
		b:          b,
		buckets:    make([][8]uint64, cap),
		lruBuckets: make([]uint32, cap),
	}
}

image.png

如上图所示,一个IntCache2^bbucketlruBucket,一个bucket有8个K-V对,一个K-V对使用uint64来存储,前32bit存储key,后32bit存储value。一个lruBucket有8个lru值,采用uint32存储,每4bit存储bucket对应的每个K-V对的lru值。

这里你可能会很奇怪为什么lru要单独存储,不要急,继续往下看,读流程时我会详细解释。

2.2 写流程

func (c *IntCache) Set(key uint32, value uint32) {
        if key == 0 && value == 0 {
		panic("key and value can't be 0")
	}
	bucketi := key & (1<<c.b - 1)
	for i := 0; i < 8; i++ {
		e := atomic.LoadUint64(&c.buckets[bucketi][i])
		if e == 0 {
			atomic.StoreUint64(&c.buckets[bucketi][i], uint64(key)<<32|uint64(value))
			c.updLru(bucketi, i)
			return
		}

		if uint32(e>>32) == key {
			e = uint64(key)<<32 | uint64(value)
			atomic.StoreUint64(&c.buckets[bucketi][i], e)
			c.updLru(bucketi, i)
			return
		}
	}

	// find the min lru
	lrus := atomic.LoadUint32(&c.lruBuckets[bucketi])
	var (
		minLru uint32
		mini   int
	)

	for i := 0; i < 8; i++ {
		lru := lrus | 0b1111<<uint32(i)
		if lru < minLru {
			minLru = lru
			mini = i
		}
	}

	atomic.StoreUint64(&c.buckets[bucketi][mini], uint64(key)<<32|uint64(value))
	c.updLru(bucketi, mini)
}

写入步骤如下:

  1. key对容量取模,计算出key落到哪个桶里,然后遍历桶中8个槽(K-V对)
  2. 如果遍历槽为0,说明这个槽还没有被占用,写入当前槽,并更新lru值为7,其他槽的lru值-1
  3. 如果遍历槽的key等于当前的key,则更新这个槽的值,并更新lru值为7,其他槽的lru值-1
  4. 如果遍历完后没有空槽也没有命中key,则找到lru值最小的,淘汰掉然后写入新key并更新lru值

2.3 读流程

func (c *IntCache) Get(key uint32) (value uint32, exists bool) {
	bucketi := key & (1<<c.b - 1)
	for i := 0; i < 8; i++ {
		e := atomic.LoadUint64(&c.buckets[bucketi][i])
                if e == 0 {
			break
		}
                
		if uint32(e>>32) == key {
			value = uint32(e)
			exists = true
			c.updLru(bucketi, i)
			break
		}
	}

	return
}

读取步骤如下:

  1. key对容量取模,计算出key落到哪个桶里,然后遍历桶中8个槽(K-V对)
  2. 如果遍历到的槽为0,说明后面的槽都是没有数据的,无需继续遍历
  3. 如果遍历到的槽的key等于查询的key,则返回value,并更新lru值

3. 总结

3.1 为什么lru要单独存储

每个bucket占用8*8=64B,正好是一个x86 cpu cacheline的大小,刚好填满一个cacheline,这样遍历bucket上8个槽实际只需要读取第一个槽时访问一次内存,后续访问都会直接从cpu cache中读到(当然前提是没有写请求造成cacheline过期),这样可以充分利用cpu缓存。

如果lru值与bucket存储在一起,那么系统中大量的读请求修改lru值就会造成cacheline过期的可能性就会变大,而如果分开存储,读请求不会造成cacheline过期。

你可能会问频繁的写入也会造成cacheline过期影响性能啊,但是我们这是一个典型的读多写少的系统,而且大量的bucket也降低了cacheline过期的几率。

3.2 缺陷

3.2.1 适用场景有限

由于我这个组件用在了在线用户访问的场景中,我将bucket数量设置为日活人数/8,hash冲突的几率还是比较小的,从监控看缓存命中率还是比较可观的。

但是由于不是严格的LRU,因此其他业务场景可能不适用。

3.2.2 value与lru值的更新不是原子的

因为要提高cpu cache命中率,因此value更新与lru更新是分离的,无法做到原子性,这也是很不严谨的,但是我们这个业务场景中不需要严谨的lru,所以可以忽略。

4. 基准测试

与fastcache对比的基准测试代码

func BenchmarkIntcache(b *testing.B) {
	rand.Seed(1)
	var B uint8 = 21
	m := New(B)
	for i := 0; i < b.N; i++ {
		intcacheBenchmarkFn(m)
	}
}

func BenchmarkFastcache(b *testing.B) {
	rand.Seed(1)
	m := fastcache.New(1 << 21 * (64 + 8))
	for i := 0; i < b.N; i++ {
		fastcacheBenchmarkFn(m)
	}
}

func intcacheBenchmarkFn(m *IntCache) {
	wg := &sync.WaitGroup{}
	for i := 0; i < 1000; i++ {
		wg.Add(1)
		go func() {
			for j := 0; j < 300; j++ {
				key := rand.Uint32()
				m.Set(key, key)
				m.Get(key)
			}
			wg.Done()
		}()
	}
	wg.Wait()
}

func fastcacheBenchmarkFn(m *fastcache.Cache) {
	wg := &sync.WaitGroup{}
	for i := 0; i < 1000; i++ {
		wg.Add(1)
		go func() {
			for j := 0; j < 300; j++ {
				key := rand.Uint32()
				b := make([]byte, 4) // uint64的大小为8字节
				binary.LittleEndian.PutUint32(b, key)
				m.Set(b, b)
				r := make([]byte, 4)
				m.Get(r, b)
			}
			wg.Done()
		}()
	}
	wg.Wait()
}

都是1000个协程并发读写300次,结果:

goos: darwin
goarch: arm64
pkg: github.com/Orlion/intcache
BenchmarkIntcache
BenchmarkIntcache-10                  14          78865301 ns/op
BenchmarkFastcache
BenchmarkFastcache-10                 10         113746746 ns/op
PASS
ok      github.com/Orlion/intcache      9.767s

可以看到我们这个实现要快一点。 image.png

...

阅读全文 »

记一次SIMD指令优化计算的失败经历

发布于
分类 汇编
标签 Go
阅读数

1. 前言

书接上回 《统计一个数字二进制位1的个数》,现在我们已经知道如何快速计算出一个int64数字的二进制位1的个数,那么回到我们最初的需求,我们的目的是快速统计一个bitmap中二进制位1的个数,假设我们使用[]uint64来实现bitmap,那么如果要统计这个bitmap中二进制位1的个数,我们可以遍历每个元素,计算出每个uint64元素二进制位1的个数,最后加起来,代码大概如下:

type Bitmap []uint64

func (bitmap Bitmap) OnesCount() (count int) {
	for _, v := range bitmap {
		count += OnesCount64(v)
	}

	return
}

const m0 = 0x5555555555555555 // 01010101 ...
const m1 = 0x3333333333333333 // 00110011 ...
const m2 = 0x0f0f0f0f0f0f0f0f // 00001111 ...

// 计算出x中二进制位1的个数,该函数上篇文章有详细解释,看不懂可以再回去看下
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)
}

这种实现方式在bitmap元素过多,切片长度过长的情况下,计算十分耗时。那么如何优化这段代码呢?

2. 优化

现代CPU一般都支持SIMD指令,通过SIMD指令可以并行执行多个计算,以加法运算为例,如果我们要计算{A0,A1,A2,A3}四个数与{B0,B1,B2,B3}的和,不使用SIMD指令的话,需要挨个计算A0+B0A1+B1A2+B2A3+B3的和。使用SIMD指令的话,可以将{A0,A1,A2,A3}{A0,A1,A2,A3}四个数加载到xmm(128bit)/ymm(256bit)/zmm(512bit)寄存器中,然后使用一条指令就可以同时计算对应的和。这样理论上可以获得N倍的性能提升。

image.png

我们可以采用SIMD指令将OnesCount64函数并行化,并行计算4个uint64数字的结果,代码实现如下:

在popcnt.go文件中定义SimdPopcntQuad函数

package popcnt

func SimdPopcntQuad(nums [4]uint64) [4]uint64

在popcnt.s文件中我们使用汇编实现SimdPopcntQuad函数

#include "textflag.h"

TEXT ·SimdPopcntQuad(SB),NOSPLIT,$0-64
    VMOVDQU nums+0(FP), Y0 // Y0 = x,将四个uint64数字加载到Y0寄存器
    MOVQ $0x5555555555555555, AX
    MOVQ AX, X9
    VPBROADCASTQ X9, Y5 // Y5 = m0 // 上面三行代码将4个m0加载到Y5寄存器
    MOVQ $0x3333333333333333, AX
    MOVQ AX, X9
    VPBROADCASTQ X9, Y6 // Y6 = m1 // 上面三行代码将4个m1加载到Y6寄存器
    MOVQ $0x0f0f0f0f0f0f0f0f, AX
    MOVQ AX, X9
    VPBROADCASTQ X9, Y7 // Y7 = m2 // 上面三行代码将4个m2加载到Y7寄存器
    MOVQ $0x7f, AX
    MOVQ AX, X9
    VPBROADCASTQ X9, Y8 // Y8 = m;上面三行代码将4个m3加载到Y8寄存器
    VPSRLQ $1, Y0, Y1 // Y1 = x>>1;Y0寄存器上四个uint64数字并行右移1位
    VPAND Y1, Y5, Y1 // Y1 = x>>1&m0;Y1寄存器上四个uint64数字并行与Y5寄存器上的四个m0并行与,结果存到Y1寄存器
    VPAND Y0, Y5, Y2 // Y2 = x&m0
    VPADDQ Y1, Y2, Y0 // x = x>>1&m0 + x&m0
    VPSRLQ $2, Y0, Y1 // Y1 = x>>2
    VPAND Y1, Y6, Y1 // Y1 = x>>2&m1
    VPAND Y0, Y6, Y2 // Y2 = x&m1
    VPADDQ Y1, Y2, Y0 // x = x>>2&m1 + x&m1
    VPSRLQ $4, Y0, Y1 // Y1 = x>>4
    VPAND Y1, Y7, Y1 // Y1 = x>>4&m2
    VPAND Y0, Y7, Y2 // Y2 = x&m2
    VPADDQ Y1, Y2, Y0 // x = x>>2&m2 + x&m2
    VPSRLQ $8, Y0, Y1 // Y1 = x >> 8
    VPADDQ Y1, Y0, Y0 // x += x >> 8
    VPSRLQ $16, Y0, Y1 // Y1 = x >> 16
    VPADDQ Y1, Y0, Y0 // x += x >> 16
    VPSRLQ $32, Y0, Y1 // Y1 = x >> 32
    VPADDQ Y1, Y0, Y0 // x += x >> 32
    VPAND Y0, Y8, Y0 // x & (1<<7-1)
    VMOVDQU Y0, ret+32(FP) // 将结果加载到内存中返回值的位置
    RET

Benchmark

理论上讲如此优化之后我们应该可以获得四倍的性能提升,所以我们写个基准测试验证下:

// 优化之后的并行计算测试
func BenchmarkSimdPopcntQuad(b *testing.B) {
        // 使用随机数防止编译阶段被编译器预先计算出来
	rand.Seed(time.Now().UnixNano())
	nums := [4]uint64{rand.Uint64(), rand.Uint64(), rand.Uint64(), rand.Uint64()}
	for i := 0; i < b.N; i++ {
		SimdPopcntQuad(nums)
	}
}

// 优化之前的顺序计算测试
func BenchmarkSerial(b *testing.B) {
        // 使用随机数防止编译阶段被编译器预先计算出来
	rand.Seed(time.Now().UnixNano())
	nums := [4]uint64{rand.Uint64(), rand.Uint64(), rand.Uint64(), rand.Uint64()}
	for i := 0; i < b.N; i++ {
		serialPopcntQuad(nums)
	}
}

func serialPopcntQuad(nums [4]uint64) [4]uint64 {
	return [4]uint64{uint64(bits.OnesCount64(nums[0])), uint64(bits.OnesCount64(nums[1])), uint64(bits.OnesCount64(nums[2])), uint64(bits.OnesCount64(nums[3]))}
}

运行后结果如下

# go test -bench=. -v
=== RUN   TestSimdPopcntQuad
--- PASS: TestSimdPopcntQuad (0.00s)
goos: linux
goarch: amd64
pkg: github.com/Orlion/popcnt
cpu: Intel Core Processor (Broadwell, no TSX)
BenchmarkSimdPopcntQuad
BenchmarkSimdPopcntQuad-8        3693530               330.8 ns/op
BenchmarkSerial
BenchmarkSerial-8               539924296                2.232 ns/op
PASS
ok      github.com/Orlion/popcnt        2.993s

可以看到优化后的并行计算比原始的顺序计算慢了150倍😭,失败~

image.png

3. 分析

虽然优化失败了,但是我们还是要分析复盘下其中的原因,从中汲取一些经验,下面我们从两方面来分析下。

3.1 未优化函数为什么快?

首先我们可以看到未优化的函数serialPopcntQuad计算四个数字竟然只花了2ns,根据Numbers Everyone Should Know一文,访存的时间大概是100ns,这就有点离谱了,计算竟然不从内存加载我们的参数?

下面我们写段main函数,使用随机数来调用下serialPopcntQuad函数,然后反汇编看下汇编代码分析下。

func main() {
	rand.Seed(time.Now().UnixNano())
	nums := [4]uint64{rand.Uint64(), rand.Uint64(), rand.Uint64(), rand.Uint64()}
	results := serialPopcntQuad(nums)
	fmt.Println(results)
}

func serialPopcntQuad(nums [4]uint64) [4]uint64 {
	return [4]uint64{uint64(bits.OnesCount64(nums[0])), uint64(bits.OnesCount64(nums[1])), uint64(bits.OnesCount64(nums[2])), uint64(bits.OnesCount64(nums[3]))}
}

编译后反汇编:

image.png

从汇编代码中可以看到在调用bits.OnesCount64之前会判断cpu是否支持popcnt指令,如果支持则使用popcnt指令来计算而不是调用bits.OnesCount64来计算,恰好我机器支持popcnt指令,省略了bits.OnesCount64中的一堆计算,因此计算速度非常快。

3.2 优化后为什么慢?

正如3.1中所提到的,相较于cpu计算,访存的代价是非常高的,大概是100ns,而我们汇编代码中为了使用SIMD指令实现统计算法有大量的访存操作。

受限于本人对汇编掌握程度,上面的汇编代码质量应该是很差的,并不能证明SIMD性能差,可能有性能更高的实现,请各位大佬指点。

而且当前Go汇编在不指定编译参数的情况下只能采用旧函数调用约定,必须采用内存传参,所以导致最终基准测试的结果很差。

4. 收获

这一通瞎折腾虽然最终结果失败,但还是有很多收获的。首先真实的体会到了访存有多慢,所以日后在进行性能优化时就会注意这一点,尽量使代码能命中CPU缓存。

再一个就是之前并没有使用过SIMD指令,也没有接触过这种级别的优化,这次算是入门了。

后端选手,水平有限,各位计算机科学家见笑了。

image.png

5. 参考资料

  1. 玩转SIMD指令编程

...

阅读全文 »

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

发布于
标签 Go
阅读数

最近一个需求需要使用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连接占满端口问题排查与解决

发布于
分类 Golang
标签 Go
阅读数

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原理与使用

发布于
分类 Mysql
标签 Mysql
标签 Go
阅读数

原文地址: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

...

阅读全文 »