huizhou | 萝卜

2024-11-16 14:58:29

最近想要系统的学习一下基础设施方面的知识，所以准备搭建一个学习环境，我没有多余的机器使用，只有一个MacBook Pro 2021 ，所以选择在笔记本上使用 Docker 搭建一套环境，目前看来第一步还是顺利的。

安装 GitLab

Mac 的M1芯片使用的是ARM架构，所以我们去寻找 ARM架构的镜像， 我是用的是yrzr/gitlab-ce-arm64v8:latest

首先需要创建 gitlab-ce 的三个工作目录 etc、 log、 opt ，不然会报错 。
将volumes里面的配置修改成你的工作目录就可以了。这里暴露了两个端口9922、9980 因为是在本地使用，所以就没开放https的443 端口，后面也不准备使用https。
docker-compose.yaml

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

version: "3.8"
services:
  gitlab-ce:
    image: yrzr/gitlab-ce-arm64v8:latest
    container_name: gitlab-ce
    privileged: true
    restart: always
    ports:
      - "9922:22"
      - "9980:9980"
    volumes:
      - /Users/hxzhouh/tools/gitlab/etc:/etc/gitlab:z
      - /Users/hxzhouh/tools/gitlab/log:/var/log/gitlab:z
      - /Users/hxzhouh/tools/gitlab/opt:/var/opt/gitlab:z
    deploy:
      resources:
        limits:
          memory: 4096M
    tty: true
    stdin_open: true

这里需要注意的是，我们对外暴露的端口是9980，因为我们后面会配置 gitlab 的http 端口运行在9980 而不是 默认的80 ，这样做，是为了避免这个问题：
https://stackoverflow.com/questions/66961517/gitlab-http-clone-url-is-wrong-port-8022-missing

等待docker 被拉起来，然后进入gitlab-ce 里面修改 配置 /etc/gitlab/gitlab.rb

1
2

docker exec -it gitlab-ce /bin/bash
vi /etc/gitlab/gitlab.rb

在最后添加三行，保存退出。

1
2
3

external_url 'http://127.0.0.1:9980'
gitlab_rails['gitlab_ssh_host'] = '127.0.0.1'
gitlab_rails['gitlab_shell_ssh_port'] = 9922

然后修改默认密码

1
2
3
4

gitlab-rails console -e production
user = User.where(id: 1).first
user.password = 'AIl+mVN(:bk\#5%c'
user.save!

最后在执行reload 操作，然后重启

1
2

gitlab-ctl reconfigure
gitlab-ctl restart

稍等片刻。
然后 浏览器输入127.0.0.1:9980 就可以打开gitlab-ce了，默认的root 账号密码就是我们刚刚修改的密码。

添加ssh

跟使用GitHub一样，我们先创建一个ssh 密钥对， 然后将公钥添加到 GitLab里面。在本地 ~/.ssh/config 里面添加配置

1
2
3
4
5
6

Host 127.0.0.1
HostName 127.0.0.1
Port 9922
IdentityFile ~/.ssh/ssh
PreferredAuthentications publickey
User root

测试一下

1
2

➜  .ssh ssh -T [email protected]
Welcome to GitLab, @root!    

ssh 是没有问题的。

尝试新建一个项目

创建成功，在本地将代码拉下来。

1

git clone ssh://[email protected]:9922/root/hello-world.git

ssh 推送也是没有问题的

1
2
3

➜  hello-world git:(main) git push origin --force
To ssh://127.0.0.1:9922/root/hello-world.git
   b4dd724..e45f213  main -> main

Gitlab Runners 配置

在setting -> CI/CD -> Runners 点击 …,然后 根据 ‘Show runner installation and registration instructions’ 文档 安装 runners

我这里输入的命令是：

1
2
3
4
5

sudo curl --output /usr/local/bin/gitlab-runner https://gitlab-runner-downloads.s3.amazonaws.com/latest/binaries/gitlab-runner-darwin-arm64
sudo chmod +x /usr/local/bin/gitlab-runner
gitlab-runner install
gitlab-runner start
gitlab-runner register --url http://127.0.0.1:9980 --registration-token GR13489416KQ-jitR3JhfMgr8f-9G

有几个关键点需要注意

1. Enter tags for the runner (comma-separated):
   1. GitLab是用 tag来管理runner 的，最好是一个runner做一件事情，用tag 标记，写.gitlab.ci.yml 的时候需要指定tags
2. Enter an executor
   1. executor 有很多种，我这里为了演示，选择了shell

更多关于GitLab Runner 的 的介绍可以参考官网的文章，这里就不做展开。
安装好了就可以在 http://127.0.0.1:9980/admin/runners 看到效果了

最后，在 刚才创建的工程中，添加一个 .gitlab-ci.yml 测试一下。

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

stages:  
  - build  
build_job:  
  stage: build  
  tags:  
    - golang-local-shell  
  script:  
    - go build -o myapp  
  only:  
    - main  
    - tags  
  artifacts:  
    paths:  
      - myapp

将代码推送到gitlab，很快就能编译完了 http://127.0.0.1:9980/root/hello-world/-/pipelines

然后在 http://127.0.0.1:9980/root/hello-world/-/artifacts 可以找到 构建的产物。

至此，在本地搭建GitLab环境已经弄好，下一篇文章，在折腾在本地搭建k8s 集群，然后从GitLab自动打包成docker镜像推送到 k8s 集群，完成一个CI/CD的完整流水线。

2024-10-19 12:03:18

对于无锁编程来讲，无锁只是一个表象，编程者设法组织 data+processing，重点在于如何消除 dataracing。而消除 dataracing 而言，传统的并发编程逻辑是采用关键区、排他性锁、读写锁等方式来保护 data 不会因为 processing 而导致错误读或错误写，那么对于无锁编程来说，则是通过消除 data 的共享性，或者消除并发操作 data 等方式来解决问题。
所以最典型的无锁编程技法包含两个技巧：

1. structure
2. bumper loop
   其他的方法都是相似思路的具体衍生。

这里的“其他的方法”，是指完全不使用锁定或 CAS 的算法设计方案。本文中讨论的是如何设计数据结构及其处理器（算法）来防止加锁，甚至于连 CAS 也去除。

至于在共享的data上强行消除竞争读写问题的其他无锁方案，例如RingBuffer之类的工具类库，则是完全依赖于具体的 data 实体并在具体的 CPU 上进行设计，基本上是一种很受限的方法，不具备高层次抽象层面的通用性。尽管其具体的设计思路有迹可循，但却不是最佳的选择：一个优秀的 RingBuffer，它的致命之处就在于在单核心的CPU上，或者单颗 vCPU 的 vHost 上可能是无法降级工作的，或者即使能工作也是低效的或者高消费的。所以本文讨论的是更通用的，在任何高级语言（无论其线程、协程支持度如何）于任何 Targets 上都可以通行的无锁编程技法。

Structure copy

Structure copy是一种经典的无锁编程技巧。它的核心思想在于将易变数据交给一个 structure 管理，通常可能起名为 Entry，然后在这个 structure 上展开数据处理过程。如此，由于数据处理过程只会操作其所关联到的 structure，因此这一组数据本身就是非共享的，也就不需要考虑 dataracing 的潜在可能性的。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

type Worker struct {
  closed int32 // avoid duplicated release rsrc in Close()
  entries []*Entry
}

type Entry struct {
  Count int
  Data []any
}

func (w *Worker) New(data ...any) *Entry {
  e:=&Entry{Data:data}
  w.entries = append(w.entries, e)
  return e
}

func (e *Entry) Run() {
  // processing e.data
}

假设初始化数据 data []any 被提供给 Worker，基于此产生一个 Entry，然后通过 Entry.Run 来处理初始化数据，产生结果，那么上面的示例代码就避免了数据包（Count，Data）的共享问题，因为这个数据包是排他性独立的。

有时候我们的数据包很难拆解，此时可以以衍生技法来实现拆解。具体的思路是设法进行分治。即数据包可以按照推进程度重新设计为 step1，step2，等等，每一步骤中的小数据包的计算结果依次提交给下一步骤。又或者数据包可以拆解为若干个小计项目，最后将多个小计结果合并计算（Map-Reduce?）。

无论采取哪种拆解思路，总的思路不变，即单个 processing 所操作的 data 是排他性独立的一个副本，从而从根本上去除共享加锁解锁的需求。

问题

问题在于太多的小块内存（Entry struct）可能是不好的。一方面它可能带来额外的内存消耗（如果正在处理一个巨大的链表、数组之类，你不太可能总是制造它们的副本），另一方面，太多频繁的小块内存的分发和析构也会产生难以接受的开销。有时候，强制这样的小块内存在栈上分配（如果语言或者编译器支持）是解决后一问题的良药。不过更多的情况下、或许这的确就是不可行的。
当然，带有 GC 的语言这方面的压力会小一点。 其次，使用一个sync.Pool也可以减轻小内存频繁分配的压力。

应用

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

type Logger struct {  
    handler Handler // for structured logging  
}
type Handler interface {  
	 Handle(context.Context, Record) error
}

func (l *Logger) Debug(msg string, args ...any) {  
    l.log(context.Background(), LevelDebug, msg, args...)  
}

func (l *Logger) log(ctx context.Context, level Level, msg string, args ...any) {  
    。。。。
    r := NewRecord(time.Now(), level, msg, pc)  
    。。。。
    _ = l.Handler().Handle(ctx, r)  
}

在 slog 中，每条日志都会被包装成一个NewRecord ，避免了数据竞争。
Entry 模式可以说是到处都有在用，用途也不一定限于为了无锁。然而凡是运用到该模式的地方，自动获得了无锁的收益，这其实是很划算的。

Bumper Loop

Bumper Loop是一种设计模式

Bumper Loop 最经典的例子是Redis, Redis 使用多线程网络模型，但是在事务处理上使用单线程。

它的核心思想是将并行事件强行序列化，然后再一一分发给具体处理程序。于是对于这些具体处理程序来讲，共享数据总是排他性的：因为所有处理程序在同一时间下只会运行一个。如果具体处理程序总是飞快地完成，没有阻塞的忧虑，那么Bumper Loop模式将会是一个非常好的消费模式。

1
2
3
4
5
6
7
8

func (w *Worker) runLoop() {
  for {
    switch{
      case ev:=<-fileWatcherCh:
        onFileChanged(ev)
    }
  }
}

对于低频事件的分发和简化并在此同时去除加锁需求、提升性能来说，循环泵模式是一时之选。在诸如 TCP/IP 服务器的 incoming data 处理上通常Bumper Loop 是最佳选择：

对新进连接请求采取 Entry 模式制作一个独立的处理器 connectionProcessor，该处理器中以循环泵模式接受输入数据，识别输入数据的模式为规约命令，然后分发给具体的规约命令处理器。

问题

Bumper Loop 的问题在于，一个阻塞会破坏整个循环，一个过慢的处理会带来不可知的下一事件的处理延迟，高频率的事件会在分发点上阻塞、堆积，甚至是丢失。尽管 Bumper Loop 似乎很明显地有串行化的效率劣势，但它仍被广泛地用于 TCP/IP server/client 编程中。

Structure Copy 与 Bumper Loop 结合

Bumper Loop 的问题之一是不太适合高频事件场景，一般来说事件频率在80ms以上时才比较好用。这种尺度的隐喻是说单次事件处理平均耗时应该小于 80ms。
在不那么严格的场景中（例如非金融高频交易），有时候可以在耗时的事件处理器中启动一个 gorountine 去异步地慢慢处理，而主体的 bumpper loop 则继续去分发后继事件。这时候异步 go routine 又可以用到 Entry 模式，适当地复制少许状态以便解耦竞态条件。

2024-09-30 11:25:51

2022年，字节跳动给Golang提了issue建议把map的底层实现改成SwissTable的。2023年，dolt写了一篇博客SwissMap: A smaller, faster Golang Hash Table 分享他们 设计了一个基于SwissTable 的 Map ,引起了广泛的关注。目前 Go 核心团队已经开始重新审视 swisstable 设计，在runtime中也添加了部分代码，趁着假期，刚好有时间深入了解一下原理，跟runtime map 相比有什么区别，以及为什么它可能会成为map的标准实现。

This article was first published in the Medium MPP plan. If you are a Medium user, please follow me on Medium. Thank you very much.

本文不会完全解释hashtable或者swisstable的原理。您需要对hashtable 有一定的了解。

哈希表提供了一个key到对应value的映射，通过一个hash函数把key转换成某个“位置“，从这个位置上可以直接拿到我们想要的value，

传统 hashtable

哈希表提供了一个key到对应value的映射，通过一个hash函数把key转换成某个“位置“，从这个位置上可以直接拿到我们想要的value。不过，即使hash函数再完美，把无限的key映射到一个有限大小的内存空间内也还是不可避免得会产生冲突：两个不同的key会被映射到同一个位置。 为了解决这个问题，传统的hashtable有好几个解决方案，最常见的解决冲突的办法有“链表法”和“线性探测法”。

链表法

链表法是最常见的，它的中心思想在于如果key映射到了相同的位置，那么就把这些key和value存在一张链表里。查找的时候先用hash函数计算得到位置，然后再从存放在该位置上的链表里一个个遍历找到key相等的条目。它的结构类似这样：
figure 1: 拉链法实现 hashtable

链表法实现很简单，没那么多边界条件要考虑,插入数据和删除数据很快，插入用链表的头插法，删除只需要移动部分节点的next指针。此外，链表法能采取扩容之外的手段阻止查询性能退化，比如把过长链表转换成搜索树等。链表法的缺点是本身对缓存不够友好，冲突较多的时候缓存命中率较低从而影响性能。不同的slot之间数据在内存里的跨度较大，数据结构整体的空间局部性较差。

线性探测法

线性探测是另一种常见的哈希表冲突解决方法。它解决冲突的方式于链表法不同，在遇到hash冲突的时候，它会从冲突的位置开始向后一个个查找，直到找到一个空位，或者没找到然后索引回到了冲突发生的位置，这时会进行扩容然后再重新执行上述插入流程。
Figure 2 ：线性探测法添加数据 动画演示

查找也是一样的，首先通过hash函数计算得到元素应该在的位置，然后从这个位置开始一个个比较key是否相等，遇到被删除的元素就跳过，遇到空的slot就停止搜索，这表示元素不在这个哈希表中。所以删除元素的时候，使用的是标记删除。
Figure 3: 线性探测法查找数据演示

线性探测法 的时间复杂度跟链表法差不多，它的优点是对缓存友好，现在可以用数组之类的紧密数据结构实现。同时，它的缺点也很明显：

1. 实现复杂，一个slot有元素、空、被删除这三种状态
2. hash冲突是连锁式的，一处冲突可能会连续影响多处，最终导致插入同样的数据，它扩容的次数会比链表法更多，最终可能会用掉更多的内存。
3. 因为冲突会造成后续插入和删除的连锁反应，所以查找过程退化到O(n)的概率更大，而且没法像链表法那样把有大量冲突的地方转换成搜索树之类的结构。
   因为删除元素麻烦，加上冲突会有连锁影响，所以很多库实现的hashtable都是用的链表法。不过即使有这么多缺点，光缓存友好和内存利用率高在现代计算机上就是非常大的性能优势了，所以像golang和python都会使用线性探测法的近似变种来实现哈希表。

go hashmap 如何存储数据

我们首先来回忆一下 Go Map 是如何存储数据的。
figure 4: go map 示意图

快速总结一下：

• Go map 底层通过哈希函数将 key 映射到多个 bucket中。每个 bucket 具有固定数量的键值对slot，用于存储 key 和对应的 value。
• 每个 bucket 能存储 8个键值对。当冲突发生时（即多个 key 被映射到同一个 bucket），这些 key 和 value 会在同一个 bucket 内存储。
• map 通过哈希函数计算 key 的哈希值，并根据哈希值找到对应的 bucket。
• 如果某个 bucket 被填满（8 个slot已用完），会生成一个 overflow bucket，继续存储新的键值对。
• 查找时数据时，首先计算要查找的 key 的哈希值，然后确定该哈希值映射到的 bucket。Go 会检查每个slot，如果 bucket 中存在overflow bucket，会顺序检查overflow bucket中的 key。

SwissTable，一种高效的 hashtable 实现方式

SwissTable 是一种基于改进的线性探测法的哈希表实现，其核心思想是通过改进哈希表的结构和元数据存储，优化了性能和内存使用。SwissTable 采用了一种新的元数据控制机制，大幅减少了不必要的键比较操作，同时利用 SIMD 指令提升吞吐量。

我们回顾了一下两种常见的哈希表实现，它们要么浪费内存且对缓存不友好；要么发生冲突后会更容易导致查找、插入、删除操作性能下降。这还是在有“完美哈希函数”的情况下，如果你用了个不那么好的哈希函数，那会导致key冲突的概率大大上升，性能问题会更加明显，最坏的情况下性能甚至会不如在数组里进行线性搜索。

业界开始寻找一种既对缓存友好又不会让查找性能退化的太厉害的哈希表算法。大多数人的研究方向是开发更好的哈希函数，在让哈希函数不断接近“完美哈希函数”的品质的同时用各种手段优化计算性能；另外一些人在改进哈希表本身的结构力求在缓存友好、性能和内存用量上找到平衡。swisstable就属于后者。
swisstable的时间复杂度和线性探测法的差不多，空间复杂度介于链表法和线性探测之间。 swisstable的实现有很多，我主要基于dolthub/swiss这个实现进行简要的介绍。

SwissTable 的基本结构

虽然名字变了，实际上swisstable依然是hashtable，而且使用改进的线性探测法来解决hash冲突。 所以大家应该能想象到，swisstable的底层应该也是个类似数组的结构。有了这样大致的模糊印象就可以了，现在我们可以来看看swisstable的结构了:

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

type Map[K comparable, V any] struct {  
    ctrl     []metadata  
    groups   []group[K, V]  
    hash     maphash.Hasher[K]  
    resident uint32   //currently occupied slots in the hash map 
    dead     uint32  //A tombstone indicates a slot that was previously occupied but has been deleted 
    limit    uint32  // This field represents the maximum number of elements that can be added to the hash map before it needs to be resized. It is calculated based on the load factor and the number of groups.
}  
  
// metadata is the h2 metadata array for a group.  
// find operations first probe the controls bytes  
// to filter candidates before matching keys  
type metadata [groupSize]int8  
  
// group is a group of 16 key-value pairstype group[K comparable, V any] struct {  
    keys   [groupSize]K  
    values [groupSize]V  
}

在swisstable 的实现中，ctrl 是一个 []metadata ，[]metadata 跟 []group[K, V] 数量对应 。每个group有8个slot

hash会被分成两部分：57bits长度的为H1，用于确定从哪个groups开始探测，剩下的7bits叫做H2，刚好放在metadata中， 被用作是当前key的哈希特征值，用于后面的查找和过滤。
swisstable比传统哈希表更快的秘诀就在于这些被叫做ctrl的metadata。控制信息主要是下面这几种：

• slot是否为空: 0b10000000
• slot里的元素是否已经被删除: 0b11111110
• slot里存的键值对的key的哈希特征（H2）0bh2
  对于空、删除这几种特殊状态，对应的值都是特意设置的，目的是为了能够在后面的匹配中使用SIMD指令，获得最高的性能。

查找、插入、删除都是基于这些ctrl的，它们非常小，可以尽量多的被放入CPU的高速缓存，同时又包含了足够的信息以满足哈希表的增删改查。而slot就只用来存数据，ctrl和slot一一对应，控制信息在ctrl里的索引就是对应的数据在slot里的索引，下面以添加数据为例，查找，删除 都差不多。

添加数据

swisstable 添加数据的过程分成几个步骤。

1. 计算哈希值并分割为 h1 和 h2 , 根据 h1 确定开始探测的groups ,
2. 使用 metaMatchH2 检查当前组中的 metadata 是否有匹配的 h2。如果找到匹配的 h2，则进一步检查对应槽位中的键是否与目标键相同。如果相同，则更新值并返回。
3. 如果没有找到匹配的键，使用 metaMatchEmpty 检查当前组中是否有空闲slot。如果有slot，则插入新的键值对，并更新 metadata 和 resident 计数。
4. 如果当前组没有空闲槽位，进行线性探测，检查下一个groups。

 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

func (m *Map[K, V]) Put(key K, value V) {  
    if m.resident >= m.limit {  
       m.rehash(m.nextSize())  
    }  
    hi, lo := splitHash(m.hash.Hash(key))  
    g := probeStart(hi, len(m.groups))  
    for { // inlined find loop  
       matches := metaMatchH2(&m.ctrl[g], lo)  
       for matches != 0 {  
          s := nextMatch(&matches)  
          if key == m.groups[g].keys[s] { // update  
             m.groups[g].keys[s] = key  
             m.groups[g].values[s] = value  
             return  
          }  
       }  
       // |key| is not in group |g|,  
       // stop probing if we see an empty slot       matches = metaMatchEmpty(&m.ctrl[g])  
       if matches != 0 { // insert  
          s := nextMatch(&matches)  
          m.groups[g].keys[s] = key  
          m.groups[g].values[s] = value  
          m.ctrl[g][s] = int8(lo)  
          m.resident++  
          return  
       }  
       g += 1 // linear probing  
       if g >= uint32(len(m.groups)) {  
          g = 0  
       }  
    }  
}
func metaMatchH2(m *metadata, h h2) bitset {  
    // https://graphics.stanford.edu/~seander/bithacks.html##ValueInWord  
    return hasZeroByte(castUint64(m) ^ (loBits * uint64(h)))  
}

func nextMatch(b *bitset) uint32 {  
    s := uint32(bits.TrailingZeros64(uint64(*b)))  
    *b &= ^(1 << s) // clear bit |s|  
    return s >> 3   // div by 8  
}

虽然，步骤很少，但是里面使用了比较复杂的位运算，按照正常的流程，需要把h2 跟所有的 对比，直到找到我们要的目标。swisstable 使用了一个很巧妙的方式来实现这个目标。

• 首先将h2 * 0x0101010101010101 得到一个uint64，这样就能一次性对比 8个 ctrl
• 然后跟meta 做 xor 运行。 如果 h2 存在于 metadata 中。那么对应的bit 就是0b00000000 ， metaMatchH2 的作用，可以用 下面的单元测试理解，
• nextMatch 用于确定 key 在group中的的具体位置。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

func TestMetaMatchH2(t *testing.T) {
	metaData := make([]metadata, 2)
	metaData[0] = [8]int8{0x7f, 0, 0, 0x7f, 0, 0, 0, 0x7f} // Imitate ctrl
	m := &metaData[0]
	h := 0x7f
	metaUint64 := castUint64(m)
	h2Pattern := loBits * uint64(h)
	xorResult := metaUint64 ^ h2Pattern
	fmt.Printf("metaUint64: %b\n", xorResult)
	r := hasZeroByte(xorResult)
	fmt.Printf("r: %b\n", r)
	for r != 0 {  
	    fmt.Println(nextMatch(&r))  
	}
}
----
output
// metaUint64: 00000000 11111110 11111110 11111110 0000000 01111111 01111111 00000000
// r: 10000000 00000000 00000000 00000000 10000000 00000000 00000000 10000000
// 0
// 3
// 7

SwissTable 的优势

看完SwissTable的实现，可以总结为下面几点：

• 对hashtable的操作从slot转移到了ctrl上，ctrl更小更容易被填入CPU的高速缓存，因此比直接在slot上操作更快，即使需要多付出一次从ctrl得到索引后再去查找slot的代价。
• 记录哈希特征值，减少了无意义的key等值比较，这是线性探测法性能下降的主要元凶。
• 对slot的查找和操作是通过ctrl批量进行的，单位时间内吞吐量有显著提升。
• 标志位的值和整个数据结构的内存布局都为SIMD进行了优化，可以充分发挥性能优势。
• 对slot也有优化，比如对太大的数据会压缩存储以提高缓存命中率。
  swisstable 解决了空间局部性问题的基础上，还利用了现代CPU的特性批量操作元素，所以性能会有飞跃般的提升。

最后在我本地macbook m1 （不支持SIMD）上跑benchmark，结果如下，在大map场景下，swisstable 性能有比较明显的提升。
Figure 5: swisstable 官方benchmark

总结

目前go 官方还没有swisstable 的实现， 但是关于它的讨论一直再继续，目前社区也有几种实现。比如concurrent-swiss-map ，swiss 等。
不过实现都不是特别完美，比如在小map 场景下swisstable 的性能甚至比不上 runtime_map 等。但是swisstable 表现出来的潜力已经在其他语言上的表现，说明它值得我们期待。

参考文档

• dolthub https://www.dolthub.com/blog/2023-03-28-swiss-map/
• swisstable 原理 https://abseil.io/about/design/swisstables
• 首次提出swisstable的cppcon演讲：https://www.youtube.com/watch?v=ncHmEUmJZf4
• 针对swisstable算法的一些改进：https://www.youtube.com/watch?v=JZE3_0qvrMg
• 位运算原理: http://graphics.stanford.edu/~seander/bithacks.html##ValueInWord
• hash 函数对比： https://aras-p.info/blog/2016/08/09/More-Hash-Function-Tests/
• 另外一篇位运算原理的文章 https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/

2024-09-25 09:34:59

在软件架构中，限流是一种控制资源使用和保护系统安全的重要机制。它通过限制在一定时间内可以处理的请求数量，来防止系统过载，确保系统在高负载情况下仍能保持稳定运行。
本文的目标是分析和实现几种常见的限流算法，以及分析他们优缺点。最后我们探讨一下真实业务代码中的一些限流设计。

This article was first published in the Medium MPP plan. If you are a Medium user, please follow me on Medium. Thank you very much.

假设我们通过性能测试得出我们的系统最大的负载为10TPS。

流量计数器模式

最简单的做法，我们做一个计时器，每秒最多允许10个请求通过，超过这个数量的流量就拒绝。
Code1 ： windows limit run it

https://gist.github.com/hxzhouh/51020e18622c2e38ebf21cd6a9dc5cc6

但是这个做法是有问题的，假设我们2秒内收到了都收到了10TPS请求，但是是在 0.9s 与 1.1s 收到的，这样虽然每个周期的流量都不超过10 TPS请求的阈值，但是系统确实曾经在1s内发生了超过阈值的20TPS请求。
流量计数器的缺陷根源在于它只是针对时间点进行离散的统计，为了弥补该缺陷，一种名为“滑动时间窗”的限流模式被设计出来，它可以实现平滑的基于时间片段统计。

滑动窗口机制

滑动窗口算法(Sliding Window Algorithm)在计算机科学的很多领域中都有成功的应用，譬如TCP协议的阻塞控制(Congestion Control)使用到滑动窗口算法

滑动窗口算法通过将时间分为多个小的时间段，每个时间段内维护一个独立的计数器。当一个请求到达时，它会被分配到当前时间所在的小时间段，并检查该时间段的计数器是否已达到限制。如果未达到，则允许请求并增加计数；如果已达到，则拒绝请求。随着时间的推移，旧的时间段会淡出窗口，新的时间段会加入。
code2: sliding_windows try it
https://gist.github.com/hxzhouh/c5c79ea4b80ea5a026052471de07107f

滑动窗口算法其实就是把流量计数器算法的时间窗口划分小一点，提供更细致的流量控制，并不能完全解决瞬时大流量。也很难在更细粒度上对流量曲线进行整形，起不到削峰填谷的作用。下面继续介绍两种适用于阻塞式限流的限流模式。

漏桶算法

漏桶算法是通过一个固定容量的队列来模拟桶，以恒定速率从桶中取出请求进行处理，无论请求到达的频率如何，都保证请求以均匀的速度被处理，从而平滑流量并防止流量突增。
Code3: leakBucket try it
https://gist.github.com/hxzhouh/ba78993644ce58958127f64fc0976c55

漏桶算法适用于需要强制执行固定速率处理的场景，如网络流量控制、API请求限制等。通过控制令牌的添加速率，漏桶算法能够有效地避免系统因瞬时流量高峰而过载。漏桶实现起来很容易，难点在于如何确定漏桶的两个参数：桶的大小和水的流出速率。如果桶设置得太大，那服务依然可能遭遇流量过大的冲击，不能完全发挥限流的作用；如果设置得太小，那很可能误杀掉一部分正常的请求。

令牌桶算法

令牌桶算法跟漏桶算法想法，更像现实生活中的排队算法，系统以固定的速率放号，我们首先要取号，然后再进行业务处理。 假设我们要限制系统在X秒内最大请求次数不超过Y，那就每间隔X/Y时间往桶中放一个令牌，当有请求进来时，首先要从桶中取得一个准入的令牌，然后才能进入系统进行处理。如果获取不到令牌就返回请求失败。

Code 4 ：token_limit try it
https://gist.github.com/hxzhouh/0c172824334aeea5ef101bd682fef59e

令牌桶算法适用于需要处理突发流量的场景，如网络通信、API调用等。通过控制令牌的填充速率和桶的容量，令牌桶算法能够有效地平衡流量，防止系统过载，同时 如果系统资源富裕的情况下，允许在短期内处理更多的请求。跟漏桶算法类似，令牌生成的速度，也是需要重点考虑的。

实际业务中的限流算法

分布式限流算法

上面介绍的四个限流算法，状态都是存储在内存中的，我们可以理解为单机限流算法，微服务架构下，它们就最多只能应用于集群最入口处的网关上，对整个服务集群进行流量控制，无法细粒度地管理流量在内部微服务节点中的流转情况。如果我们需要实现一个服务的多个节点之间协同限流，那么我们需要将状态保存在集群中共享，下面是一个使用Redis 实现分布式 令牌桶算法的实现。实际上，我在业务中使用更多的是这种方式。

优先级

服务器资源是宝贵的，再资源紧张的情况下，我们更加希望宝贵的资源用于服务我们的vip客户。因此，我们可以设计一种基于“货币化额度”的分布式限流方案。不同于传统令牌桶算法中的“准入/拒绝”二元判定方式，这里的“货币额度”是一种更灵活的限流方式。用户在访问集群中的服务时，每次都会消耗一定的额度，类似于消耗资源的“货币”，并且可以根据用户的等级分配不同的额度。VIP用户可能拥有更高的额度，普通用户则有一定的额度限制。当额度耗尽后，用户需要重新向“令牌桶”申请额度，才能继续访问。
code 5: quota try it
https://gist.github.com/hxzhouh/dc06a2947f4d436bdce9743d65b6c9e6

结论

本文介绍了几种常见的限流算法，包括流量计数器、滑动窗口、漏桶、令牌桶等，并分析了它们在不同场景下的应用效果。流量计数器算法简单易用，但无法应对瞬时高峰流量，滑动窗口算法在一定程度上弥补了这一缺陷。漏桶算法通过固定速率处理请求，适合需要平滑流量的场景，而令牌桶算法则能够灵活处理突发流量，并允许系统在短时间内接收更多请求。

在实际业务中，尤其是微服务架构下，分布式限流是非常重要的。通过 Redis 等中间件的协同，分布式令牌桶算法能有效管理多个节点的流量。此外，基于优先级的“货币化额度”方案为限流设计提供了更多灵活性，有助于提升 VIP 客户体验。限流机制不仅能够保护系统免受过载，还能提升系统的整体稳定性与性能。

参考文档

[1] 限流设计模式

2024-09-15 10:05:57

背景

JSON是一种轻量级的数据交换格式，Go 语言的 encoding/json 包自诞生以来已有十年之久，它凭借其灵活的特性赢得了开发者的青睐。开发者可以通过结构体标签自定义字段的 JSON 表现形式，也可以让 Go 类型自定义其在 JSON 中的表现形式。然而，随着 Go 语言和 JSON 标准的发展，一些功能上的缺失和性能上的限制逐渐暴露出来。

1. 功能缺失：比如，不能指定 time.Time 类型的自定义格式化，不能在序列化时省略特定的 Go 值等。
2. API 缺陷：比如，没有简单的方法来正确地从 io.Reader 中反序列化 JSON。
3. 性能限制：标准json包的性能表现并不尽如人意，特别是在处理大量数据时。
4. 行为缺陷：比如，对 JSON 语法的错误处理不够严格，大小写不敏感的反序列化等。

就像math/v2一样的，Go 官方提出encoding/json/v2 来解决上面的那些问题，本文主要目标是分析enable/json中 关于空值的一些问题。以及它在 encoding/json/v2中是如何被解决的。本文不涉及 encoding/json/v2 中其他的修改

This article was first published in the Medium MPP plan. If you are a Medium user, please follow me on Medium. Thank you very much.

omitempty

在encoding/json包中，有这样关于omitempty的描述:

The “omitempty” option specifies that the field should be omitted from the encoding if the field has an empty value, defined as false, 0, a nil pointer, a nil interface value, and any empty array, slice, map, or string.

但是，这种预定义的”空”值判断逻辑并不能满足所有实际场景的需求。我们来看一个例子：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

  
type Post struct {  
    Id         int64           `json:"id,omitempty"`  
    CreateTime time.Time       `json:"create_time,omitempty"`  
    TagList    []Tag           `json:"tag_list,omitempty"`  
    Name       string          `json:"name,omitempty"`  
    Score      float64         `json:"score,omitempty"`  
    Category   Category        `json:"category,omitempty"`  
    LikePost   map[string]Post `json:"like,omitempty"`  
}  
type Tag struct {  
    ID   string `json:"id"`  
    Name string `json:"name"`  
}  
type Category struct {  
    ID   float64 `json:"id"`  
    Name string  `json:"name"`  
}  
  
func main() {  
    b, _ := json.Marshal(new(Post))  
    fmt.Println(string(b))  
}

输出结果为：

1

{"create_time":"0001-01-01T00:00:00Z","category":{"id":0,"name":""}}

虽然Post 各个字段都添加了omitempty 。但是结果并不像我们预期一样。

1. omitempty 不能处理空 struct ，比如 Post.Category
2. omitempty 处理time.Time 的方式不是 我们理解的UTC =0，也就是1970-01-01 00:00:00 ,而是 0001-01-01T00:00:00Z 。

omitzero标签

在 encoding/json/v2 中，会添加一个新的标签 omitzero，添加了两个功能，来解决上面的两个问题。（目前这个功能还在开发中，不过可以通过go-json-experiment/json提前体验新功能）

1. 更好的time.Time 处理。
2. 支持自定义IsZero函数。
   比如下面下面的代码：

 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

package main  
  
import (  
    "encoding/json"  
    "fmt"    v2_json "github.com/go-json-experiment/json"  
    "math"    "time")  
  
type Post struct {  
    Id         int64           `json:"id,omitempty,omitzero"`  
    CreateTime time.Time       `json:"create_time,omitempty,omitzero"`  
    TagList    []Tag           `json:"tag_list,omitempty"`  
    Name       string          `json:"name,omitempty"`  
    Score      ScoreType       `json:"score,omitempty,omitzero"`  
    Category   Category        `json:"category,omitempty,omitzero"`  
    LikePost   map[string]Post `json:"like,omitempty"`  
}  
type ScoreType float64  
  
func (s ScoreType) IsZero() bool {  
    return s < math.MinInt64  
}  
  
type Tag struct {  
    ID   string `json:"id"`  
    Name string `json:"name"`  
}  
type Category struct {  
    ID   float64 `json:"id"`  
    Name string  `json:"name"`  
}  
  
func main() {  
    v1String, _ := json.Marshal(new(Post))  
    fmt.Println(string(v1String))  
    v2String, _ := v2_json.Marshal(new(Post))  
    fmt.Println(string(v2String))  
}

跟encoding/json 相比 encoding/json/v2 解决了上面提到的问题。

1
2

{"create_time":"0001-01-01T00:00:00Z","category":{"id":0,"name":""}}
{"score":0}

结论

通过引入omitzero标签，Go语言在解决JSON编码中”空”值处理的痛点上迈出了重要一步。这个方案不仅满足了开发者对更灵活的”空”值定义的需求，还保持了与现有系统的兼容性。目前该omitzero的落地时间尚未确定，最早也要等到Go 1.24版本。此外，encoding/xml等也会效仿json包，增加omitzero标签。
encoding/json/v2 还包括 性能等其他方面的更新， 有兴趣的Gopher 可以 提前了解这些改动，本博客也会一直关注这个proposal
Go语言开始走向成熟。