Go Metrics SDK Tag 校验性能优化实践-每日运维

背景

Metrics
SDK 是与字节内场时序数据库 ByteTSD 配套的用户指标打点 SDK，在字节内数十万服务中集成，应用广泛，因此 SDK
的性能优化是个重要和持续性的话题。

用户在使用 SDK API 进行打点时，需要传入指标对应的 Tag：

tags := []m.T{{Name: "foo", Value: "a"}, {Name: "bar", Value: "b"}}
metric.WithTags(tags...).Emit(m.Incr(1))

SDK
内部需要对用户传入的 Tag Value 的合法性进行校验，IsValidTagValue，是 SDK 中对 Tag Value
进行字符合法性校验的 util 函数，在对内部一些用户的业务使用 pprof 拉取 profile 时，发现这两个函数的 CPU 消耗占整个打点
API 过程的10%~20%，由于该函数发生在打点 API 的 hot-path 上，因此有必要对其进行进一步优化。

图片

分析

当前实现

我们先看一下 IsValidTagValue 函数内部的实现方式，是否有可优化的点。当前的实现，对于通过 API 传入的每一个Tag Value，会进行以下操作来判断其合法性：

先判断是否是在 Letter、Number 的范围内，是则直接通过；
存储所有允许的特殊字符白名单，遍历 Tag Value 对比其每个字符是否在白名单内。

var (
   // these runes are valid in tag values
   whiteListRunes = []rune{'_', '-', '.', '%', ':', ' ', '[', ']', ',', '%',
      '/', ':', ';', '', '@', '~'}
)
func IsValidTagValue(s string) bool {
   if len(s) == 0 || len(s) > maxTagLen {
      return false
   }
   for i, r := range s {
      if r  maxValidChar {
         return false
      }
      if unicode.IsLetter(r) || unicode.IsNumber(r) || isRuneInWhiteList(r) {
         continue
      }
      return false
   }
   return true
}

该实现的时间复杂度简单分析如下：

对于由 Letter、Number 这样的合法字符构成的字符串(大部分场景)，其时间复杂度是：

对于全由特殊字符构成的字符串，其时间复杂度是：

整个字符串的时间复杂度将介于

到

之间

问题点

可以看到，从当前实现看，一个主要影响性能的点是白名单列表的循环遍历对比操作，我们需要考虑可能的优化方式来降低这个操作的时间复杂度。

优化

优化一：使用 Lookup Table，空间换时间

Metrics SDK 所有允许的合法的字符，实际上是 ASCII 的一个子集，也就是说其所有可能的字符最多只有128个，因此，我们可以通过空间换时间的方式，将对白名单的 O(n) 遍历操作转换为 O(1) 的查表操作：

提前对这128个字符建立一个包含128个成员的数组，在每一个 offset 上标记对应字符是否合法(合法则标记为1)，这样就建立了一个快速的 lookup table

对于要校验的每一个字符，只要将其转化为数组 offset，直接取数组成员值判断是否为1即可

image.png

table := [128]uint8{...}
// fill flags
for i := 0; i  maxValidChar {
       return false
    }
    if table[char] != 1 {
        return false
    }
}
return true

Benchmark

goos: linux
goarch: amd64
pkg: code.byted.org/gopkg/metrics_core/utils
cpu: Intel(R) Xeon(R) Platinum 8260 CPU @ 2.40GHz
BenchmarkLookupAlgoValid
BenchmarkLookupAlgoValid/baseline
BenchmarkLookupAlgoValid/baseline-8                   2839345               478.9 ns/op
BenchmarkLookupAlgoValid/lookup-arraytable
BenchmarkLookupAlgoValid/lookup-arraytable-8          6673456               167.8 ns/op

可以看到，速度提升60%

优化二：使用 SIMD，提升并行度

基于 Lookup Table 的校验方式，将字符串校验的时间复杂度稳定在了

，但有没有可能进一步减少对字符串每一个字符的遍历次数，比如一次校验16个字符？

我们知道，SIMD 指令是循环展开优化的常用思路，那么这里是否可以引入 SIMD 来进一步提升运算并行度和效率？

答案是肯定的，以 intel x86 架构为例，参考其 Intrinsics Guide，在不同的 SIMD 指令集上提供了多个可以实现在不同大小的 lookup table 中查找数据的指令，这些指令可以作为我们加速方案的基础：

图片

注：可以通过 cat /proc/cpuinfo 命令来查看机器支持的simd指令集

鉴于 vpermi2b 指令的支持目前不是很普遍的原因，我们考虑使用 pshufb 来实现一个 SIMD 版本，但我们的Lookup Table 需要调整下，因为：

虽然我们基于 bitmap 实现的 Lookup Table 是 128 bits，刚好可以填充 128 bits 的寄存器
但 pshufb 是按字节进行 lookup 的，128 bits 的寄存器支持16字节的 lookup

因此，我们需要将 bitmap lookup table 做一次升维，变成一个16*8 bits 的二维 lookup table，做两次递进的行、列 lookup 完成查找，基于该思路，可以实现一次校验16个字符，大大提升并行度。

整体方案

该方案主要参考这篇文章：SIMDized check which bytes are in a set(http://0x80.pl/articles/simd-byte-lookup.html)

构建 bitmap table

对于一个 ASCII 字符，我们用其低 4bits 作为 lookup table 的 row index，用高 3bits 作为 lookup table 的 column index，这样对128个 ASCII 字符建立如下的一个二维 bitmap table：

图片

Lookup 流程

我们先实现一个纯 go 语言版本的基于二维 bitmap lookup table 的方案，以便于理解其中的关键逻辑：

table := [16]uint8{}
// fill flags
for i := 0; i > 4
      table[lowerNibble] |= 1  maxValidChar {
       return false
    }
    lowerNibble := uint8(r) & 0x0f
    upperNibble := uint8(r) >> 4
    if table[lowerNibble]&(1 4;
        if ((table[lower] & (1> 4
                        rcBitTable[lowerNibble] |= 1  maxTagLen {
                return false
        }
        sptr := unsafe.Pointer((*reflect.StringHeader)(unsafe.Pointer(&s)).Data)
        var rt byte
        _is_valid_string(unsafe.Pointer(&rcBitTable), sptr, int32(len(s)), unsafe.Pointer(&smTable), unsafe.Pointer(&hmTable), unsafe.Pointer(&rt))
        return rt != 0
}

Benchmark

先做一个通用的 benchmark，待校验的 string 长度从1 ~ 20不等：

goos: linux
goarch: amd64
pkg: code.byted.org/gopkg/metrics_core/utils
cpu: Intel(R) Xeon(R) Platinum 8260 CPU @ 2.40GHz
BenchmarkLookupAlgoValid
BenchmarkLookupAlgoValid/baseline
BenchmarkLookupAlgoValid/baseline-8                  2574217               510.5 ns/op
BenchmarkLookupAlgoValid/lookup-arraytable
BenchmarkLookupAlgoValid/lookup-arraytable-8         6347204               193.7 ns/op
BenchmarkLookupAlgoValid/lookup-2d-bittable-simd
BenchmarkLookupAlgoValid/lookup-2d-bittable-simd-8   6133671               185.2 ns/op

可以看到，SIMD 版本在平均水平上与 arraytable 相当

由于 SIMD 优势主要体现在长字符串时，因此，我们使用一组长度为20左右的 string，再次 benchmark:

goos: linux
goarch: amd64
pkg: code.byted.org/gopkg/metrics_core/utils
cpu: Intel(R) Xeon(R) Platinum 8260 CPU @ 2.40GHz
BenchmarkLookupAlgoValidLong
BenchmarkLookupAlgoValidLong/baseline
BenchmarkLookupAlgoValidLong/baseline-8                  3523198           356.4 ns/op
BenchmarkLookupAlgoValidLong/lookup-arraytable
BenchmarkLookupAlgoValidLong/lookup-arraytable-8         8434142           153.3 ns/op
BenchmarkLookupAlgoValidLong/lookup-2d-bittable-simd
BenchmarkLookupAlgoValidLong/lookup-2d-bittable-simd-8  13621970            87.29 ns/op

可以看到，在长 string 上 SIMD 版本表现出非常大的优势，相对于 arraytable 版本再次提升50%

结论

通过 lookup table + SIMD 的方式优化，字符校验的整体性能可以提升2~4倍
但由于在 Go 中 plan9 汇编无法内联，因此在待校验的字符串较短时不能体现其优势

Go Metrics SDK Tag 校验性能优化实践

背景

分析

当前实现

问题点

优化

优化一：使用 Lookup Table，空间换时间

Benchmark

优化二：使用 SIMD，提升并行度

整体方案

构建 bitmap table

Lookup 流程

Benchmark

结论

相关文章

发布评论取消回复

向阳逐梦

【Rocky 9】Step by Step 从 CentOS 7.9 升级到 Rocky Linux 9.2

oracle查询V$ARCHIVE_GAP慢的问题解决–转瞻Derek

Oracle 11g RAC集群日常运维命令总结

Go Metrics SDK Tag 校验性能优化实践

背景

分析

当前实现

问题点

优化

优化一：使用 Lookup Table，空间换时间

Benchmark

优化二：使用 SIMD，提升并行度

整体方案

构建 bitmap table

Lookup 流程

Benchmark

结论

相关文章

发布评论 取消回复

向阳逐梦

【Rocky 9】Step by Step 从 CentOS 7.9 升级到 Rocky Linux 9.2

oracle查询V$ARCHIVE_GAP慢的问题解决–转瞻Derek

Oracle 11g RAC集群日常运维命令总结

发布评论取消回复