Hi there 👋

限流算法 通常有下面4种： 固定时间窗口(计数器)算法 基本思想是：在固定时间窗口内对请求数进行统计，然后与阈值比较确定是否进行限流，一旦到了时间临界点，就将计数器清零 缺陷： 可能存在在某个时间窗口前90%时间里没有请求，所有的请求都集中在最后10%，这个在该算法中是允许的 滑动时间窗口算法 基本思想是：一个较大的时间窗口内细分成多个小窗口，大窗口按照时间顺序每次向后移动一个小窗口，并保证每次大窗口内的请求总数不超过阈值。 缺陷：滑动窗口是对固定窗口算法的一种改进，但是并没有真正解决固定窗口的临界突发瞬时大流量问题。 漏桶算法 Leaky Bucket 基本思想是：漏桶算法通过一个固定容量的桶，控制进入桶中的请求总数，然后以一定速率从桶中取出请求进行处理，如果桶已经满了，则直接丢弃请求。 缺陷： 漏桶算法因为是先进先出队列，在突发瞬时大流量情况下，会出现大量请求失败情况，不适合抢购，热点事件等场景 适用场景：就像漏斗一样，出口处的速率是恒定的。因此漏桶算法是流量最均衡的限流算法，用于对流量进行整型，保证流量以固定的速率进入系统。 令牌桶算法 基本思想是：令牌桶相当于反向漏桶算法，即以固定速率生成令牌放入固定容量的桶中，每个请求从桶中获取到令牌就允许执行，没有获取到就丢弃。 令牌桶算法弥补了漏桶算法无法应对突发大流量问题，即可以针对突发大流量进行限流。 单机 ratelimit 参考资料 1 里面有上面四种算法的实现，这里仅列举一下固定窗口法和漏桶算法。 固定窗口算法 type FixedWindowRateLimiter struct { threshold int // 阈值 stime time.Time // 开始时间 interval time.Duration // 时间窗口 counter int // 当前计数 lock sync.Mutex } func NewFixedWindowRateLimiter(threshold int, interval time.Duration) *FixedWindowRateLimiter { return &FixedWindowRateLimiter{ threshold: threshold, stime: time.Now(), interval: interval, counter: threshold - 1, // 让其处于下一个时间窗口开始的时间临界点 } } func (l *FixedWindowRateLimiter) Allow() bool { l.lock.Lock() defer l.lock.Unlock() // 判断收到请求数是否达到阈值 if l.counter == l.threshold-1 { now := time.Now() // 达到阈值后，判断是否是请求窗口内 if now.Sub(l.stime) >= l.interval { // 重新计数 l.Reset() return true } // 丢弃多余的请求 return false } else { l.counter++ return true } } func (l *FixedWindowRateLimiter) Reset() { l.counter = 0 l.stime = time.Now() } 漏桶算法 ...

从 cgroup 的介绍中，我们知道了通过设置 /sys/fs/cgroup/ 的值，并且使用 cgroup-tools 启动程序同时指定一个 cgroup，可以达到控制进程使用系统资源的目的。 起因 一个 Go 程序运行在 k8s 环境中，在某一行代码前后设置 start timestamp 和 end timestamp，发现有时候 p99 的 latency 非常高，正常情况下在 1-3 ms，极端情况下有 50-90 ms。百思不得其解，猜测各种可能加查阅资料后，发现应该是没有正确的设置 runtime.GOMAXPROCS。设置为 1 后，极高 latency 的情况明显减少。 为什么 出现这个问题有三个条件，缺一不可： 是 Go 程序，并且采用系统默认 GOMAXPROCS 运行在 k8s 或者 docker 这样的容器环境 宿主机上有多个 CPU 核 GOMAXPROCS 是什么 回忆一下 Go 并发的 GPM 模型： G代表 goroutine，即用户创建的 goroutines P代表逻辑处理器 Logical Processor，默认情况下 P 的数量等于 Host 上 CPU core 的个数， M是操作系统线程。M 必须绑定到一个 P 才能运行。M P 绑定后从队列中找一个 G，你创建的 goroutine 就执行了。M 的个数和 P 的个数不一定一样多（比如休眠的 M）。 而 go 的 runtime GOMAXPROCS 代表的就是 P 的数量，其底层就是 runtime 直接调用 Linux 系统调用 sched_getaffinity() ...

cgroup 比较有趣的地方是它没有提供任何的系统调用接口，所以你不能用 API Call 的方式使用 cgroup，实际上 cgroup 实现了 linux 虚拟文件系统 vfs，所以类似我们熟悉的 btfrs, ext4， 因此可以用类似文件系统的方式进行操作。 比如用 mount 命令看一下 linux 上挂载了哪些设备： # mount -t cgroup /dev/sda2 on / type ext4 (rw,relatime) cgroup on /sys/fs/cgroup/systemd type cgroup (rw,nosuid,nodev,noexec,relatime,xattr,name=systemd) cgroup on /sys/fs/cgroup/net_cls,net_prio type cgroup (rw,nosuid,nodev,noexec,relatime,net_cls,net_prio) cgroup on /sys/fs/cgroup/rdma type cgroup (rw,nosuid,nodev,noexec,relatime,rdma) cgroup2 on /sys/fs/cgroup type cgroup2 (rw,nosuid,nodev,noexec,relatime,nsdelegate,memory_recursiveprot) 可以看到， 第一行是磁盘 sda2 挂载在根目录 /, 它的类型是 ext4 后面几行是 cgroup 挂载在了目录 /sys/fs/cgroup/，类型是 cgroup 如果你的内核比较新的话，将看不到上面那些 cgroup 的行，而是只能看到最后这一行 cgroup2，这是因为新版本的内核使用了 cgroup v2 。 另外类似于 “net_cls”， “rdma” 这些都是 cgroup 子系统的名字，详见本文结尾的附录。 知道了上面这些，那么我们就能用操作文件系统的方式使用 cgroup 了，正好我有两台 linux VM， 一个 Ubuntu Server 22.04，内核 5.15， 默认使用了 cgroup v2 另一个是 Ubuntu Server 20.04, 内核 5.4，使用 cgroup v1 cgroup 和 cgroup2 有很多不一样的地方，具体见参考资料 1。本文所有例子都基于 cgroup v2。 ...

如何存储和表示 B+ 树 前面已经知道，page 是代表 B+ 树被序列化到了磁盘上的结构，一个 page 就是一个 B+ 树节点，通过 mmap 把磁盘上的页映射到内存，然后用 unsafe.Pointer(p) 直接把二进制序列化成 page 结构。也正因为如此，x86 架构上生成的 db 文件是不能在 ARM 架构的机器上打开的。 而 node 结构同样也表示内存中一个 B+ 树的节点，node 与 page 的区别是 node 按需创建的，对于不需要修改的B+树节点，boltdb直接从page中读取数据，当需要修改某个 B+ 树节点时，比如插入删除数据，boltdb 从 page 结构生成成 node 。（此处存疑，我觉得应该是 Cursor 在游走的过程中就会把 page 转化成 node） Bucket.node() 函数中就有如下一段话 func (b *Bucket) node(pgid pgid, parent *node) *node { // Retrieve node if it's already been created. if n := b.nodes[pgid]; n != nil { return n } // Read the page into the node and cache it. n.read(p) b.nodes[pgid] = n } 换句话说，boltdb 不会修改而是只读 mmap 映射的内存，当需要修改时，在内存中另外开辟内存并构造 node 结构，这个新分配的内存属于进程的 heap memory。 ...

主机配置 CPU：i7-9700k CPU 集显：Intel UHD 630 主板：MSI B365M Pro-VDH 黑苹果镜像来源于黑果小兵的 Monterey 12.6，下载链接 , 安装的过程就不赘述了，网上有很多资料。 安装之后最大的问题就是显卡只显示 14 MB 显存，意思就是 MacOS 没有正确的驱动 CPU 的集成显卡，需要改 config.plist 文件。 以上都是安装黑苹果大多数人都会遇到的问题，网上也有很多教程教你把 AAPL,ig-platform-id 的值改成 07009B3E，以及其他的一系列参数等等，但是问题是按照他们的参数设置后，显卡依然无法正常工作。 尝试了很多参数，遇到的问题主要是以下两种 显存依然是 14 MB，但其他正常。但是因为无法驱动导致显示性能所限，无法打开消耗GPU性能的应用，比如 Docker 无法启动，因为 Mac 版的 Docker 初试启动需要开启一个桌面，无法打开。VS Code 也无法使用。 Goland 可以使用。 显存显示正常 1560 MB，但是屏幕的色彩全变了，蓝色显示为橘黄，红色显示为蓝色。 这是困扰我最大的问题，尝试了几天都没有找到解决办法。 最后，通过这个 Youtube 视频介绍的方法 https://www.youtube.com/watch?v=4EU8oT0-Ea8 居然试验成功了！！ 为什么成功了呢？ 我只做了以下几个操作，可能是其中一个，或者全部组合起了作用。 在 ACPI -> Patch 里面添加了 2 项。 NVRAM “7C436110” 那一项的 boot-args 参数里面加了 -cdfon 在 PlatformInfo SMBIOS 里面选择了 iMac19,1 ...

本文主要收集一些例子，以后阅读 Go 汇编时遇到忘记的指令可以查询。 例子 1 package main func main() { l := []int{9, 45, 23, 67, 78} t := 0 for _, v := range l { t += v } println(t) } 截取了一段汇编如下 0x0026 00038 (3.go:4) MOVUPS X15, ""..autotmp_5+40(SP) 0x002c 00044 (3.go:4) MOVUPS X15, ""..autotmp_5+48(SP) 0x0032 00050 (3.go:4) MOVUPS X15, ""..autotmp_5+64(SP) 0x0038 00056 (3.go:4) LEAQ ""..autotmp_5+40(SP), AX 0x003d 00061 (3.go:4) MOVQ AX, ""..autotmp_4+80(SP) 0x0042 00066 (3.go:4) TESTB AL, (AX) 其中 MOVUPS 是 Intel 平台的 SIMD 指令，通过 X15 代表的固定的零寄存器对起始地址为SP + 40 的连续 128 bit （16个字节）进行清零。如果是作用在 slice 结构体上，则是 len 和 cap 为0。 LEAQ 取 SP+40 内存单元的地址，存入 AX 寄存器。 TESTB 把 AL 与 AX 寄存器中的值做逻辑与操作，但不会改变寄存器的值，只是设置相关标志位。这里是用做 nil check，如果加载 AX 失败会触发段错误信号 SIGSEGV，触发 Go Runtime 抛出 Panic。选择 TESTB仅仅是因为指令短小。 接下来就是循环体部分 0x00da 00218 (3.go:8) JMP 220 0x00dc 00220 (3.go:8) MOVQ ""..autotmp_6+32(SP), AX 0x00e1 00225 (3.go:8) CMPQ ""..autotmp_7+24(SP), AX 0x00e6 00230 (3.go:8) JGT 234 0x00e8 00232 (3.go:8) JMP 286 0x00ea 00234 (3.go:8) MOVQ ""..autotmp_6+32(SP), AX 0x00ef 00239 (3.go:8) SHLQ $3, AX 0x00f3 00243 (3.go:8) ADDQ ""..autotmp_3+112(SP), AX 0x00f8 00248 (3.go:8) MOVQ (AX), AX 0x00fb 00251 (3.go:8) MOVQ AX, "".v+8(SP) 0x0100 00256 (3.go:9) MOVQ "".t+16(SP), CX 0x0105 00261 (3.go:9) ADDQ CX, AX 0x0108 00264 (3.go:9) MOVQ AX, "".t+16(SP) 0x010d 00269 (3.go:9) JMP 271 0x010f 00271 (3.go:8) MOVQ ""..autotmp_6+32(SP), AX 0x0114 00276 (3.go:8) INCQ AX 0x0117 00279 (3.go:8) MOVQ AX, ""..autotmp_6+32(SP) 0x011c 00284 (3.go:8) JMP 220 0x011e 00286 (3.go:12) PCDATA $1, $0 0x011e 00286 (3.go:12) NOP CMPQ， 比较 SP+24 和 AX 所存值得大小，实际上，这个操作是把 SP+24 的值减去 AX，得到的值存在另一个寄存器中，供 JGT、JLT 指令使用 JGT ： 有了前面的结果，JGT 只要判断如果值大于 0 ，则跳到 234 行指令。 接下里 234 - 271 行，就是从数组拿出一个元素，赋值给变量 v，然后加上 t 并把结果存在 t 中。 INCQ： 增加数组 index 的值，这个index 存在 AX 中 。 SHLQ 是左移的意思，我没有看懂这里需要左移 3 位的意思？ 例子 2 下面的代码一个用 new，一个直接构建结构体，那么最终生成的代码有区别吗？ ...

本文翻译自 https://github.com/teh-cmc/go-internals/tree/master/chapter1_assembly_primer 先看一个简单的 code // go tool compile -N -l -S once.go // go build -gcflags -S once.go package main //go:noinline func add(a, b int32) (int32, bool) { return a + b, true } func main() { add(10, 32) } 生成汇编 GOOS=linux GOARCH=amd64 go tool compile -S x.go 在我的机器 Ubuntu kernel 5.4.0, Go version go1.18.3 amd64 上出来的结果与原文中还是有些差异的，但为了文章通顺，下面还是用的原文的结果。 0x0000 TEXT "".add(SB), NOSPLIT, $0-16 0x0000 FUNCDATA $0, gclocals·f207267fbf96a0178e8758c6e3e0ce28(SB) 0x0000 FUNCDATA $1, gclocals·33cdeccccebe80329f1fdbee7f5874cb(SB) 0x0000 MOVL "".b+12(SP), AX 0x0004 MOVL "".a+8(SP), CX 0x0008 ADDL CX, AX 0x000a MOVL AX, "".~r2+16(SP) 0x000e MOVB $1, "".~r3+20(SP) 0x0013 RET 0x0000 TEXT "".main(SB), $24-0 ;; ...omitted stack-split prologue... 0x000f SUBQ $24, SP 0x0013 MOVQ BP, 16(SP) 0x0018 LEAQ 16(SP), BP 0x001d FUNCDATA $0, gclocals·33cdeccccebe80329f1fdbee7f5874cb(SB) 0x001d FUNCDATA $1, gclocals·33cdeccccebe80329f1fdbee7f5874cb(SB) 0x001d MOVQ $137438953482, AX 0x0027 MOVQ AX, (SP) 0x002b PCDATA $0, $0 0x002b CALL "".add(SB) 0x0030 MOVQ 16(SP), BP 0x0035 ADDQ $24, SP 0x0039 RET ;; ...omitted stack-split epilogue... Add 函数 0x0000 TEXT "".add(SB), NOSPLIT, $0-16 0x0000 : 表示当前指令相对于函数的偏移量 TEXT “”.add : 定义函数，在链接阶段会被链接器替换为 main.add (SB): SB 是 static base pointer，代表程序地址空间的起始地址。"".add(SB) 代表 add 在程序地址空间的一个固定 offset。比如像下面这样 $ objdump -j .text -t binary | grep 'main.add' 000000000044d980 g F .text 000000000000000f main.add FP 和 SB 的作用可以参见 《Go 语言汇编 一》 ...

寄存器 学过 X86 汇编的同学都知道汇编有AX，BX等寄存器，除此之外，Go 还添加了 PC、FP、SP、SB四个伪寄存器。如下图所示，其中第二列为 GO 添加的4 个伪寄存器，第三列为 X86 寄存器。 看到这里，尘封已久的汇编语言知识需要拿出来复习一下。 FLAGS 是状态寄存器。 IP 是指令寄存器。 AX、BX、CX、DX、SI、DI、BP、SP 是通用寄存器。在X86-64中又增加了八个以R8-R15 方式命名的通用寄存器。 另外 GO 的 4 个伪寄存器作用如下： FP: Frame pointer：伪FP寄存器对应函数的栈帧指针，一般用来访问函数的参数和返回值；golang语言中，函数的参数和返回值，函数中的局部变量，函数中调用子函数的参数和返回值都是存储在栈中的，我们把这一段栈内存称为栈帧（frame），伪FP寄存器对应栈帧的底部，但是伪FP只包括函数的参数和返回值这部分内存，其他部分由伪SP寄存器表示；注意golang中函数的返回值也是通过栈帧返回的，这也是golang函数可以有多个返回值的原因； PC: Program counter：指令计数器，用于分支和跳转，它是汇编的IP寄存器的别名； SB: Static base pointer：一般用于声明函数或者全局变量，对应代码区（text）内存段底部； SP: Stack pointer：指向当前栈帧的局部变量的开始位置，一般用来引用函数的局部变量，这里需要注意汇编中也有一个SP寄存器，它们的区别是：1.伪SP寄存器指向栈帧（不包括函数参数和返回值部分）的底部，真SP寄存器对应栈的顶部；所以伪SP寄存器一般用于寻址函数局部变量，真SP寄存器一般用于调用子函数时，寻址子函数的参数和返回值（后面会有具体示例演示）；2.当需要区分伪寄存器和真寄存器的时候只需要记住一点：伪寄存器一般需要一个标识符和偏移量为前缀，如果没有标识符前缀则是真寄存器。比如(SP)、+8(SP)没有标识符前缀为真SP寄存器，而a(SP)、b+8(SP)有标识符为前缀表示伪寄存器； Symbols 符号 有些符号比如 R1、LR 是不同架构预定义的寄存器。除此之外，还有 GO 定义的 4 个伪寄存器。 FP: Frame pointer: arguments and locals. PC: Program counter: jumps and branches. SB: Static base pointer: global symbols. SP: Stack pointer: the highest address within the local stack frame. 所有用户定义的符号都可以写成 FP 或者 SB + offset 的形式。 ...

ByteGraph ByteGraph 是字节跳动开发的一个分布式图数据库。之前只是听说过图数据库，但并没有用过，因此在阅读的过程中难免对一些概念理解的不够深入。 为什么字节要开发图数据库呢？因为字节的产品都是社交App，因此用户，短视频，专注，点赞，粉丝所有的这些构成了一个巨大的图。 为什么现有的数据库无法满足呢？ 关系型数据库和文档型数据库显然不适合这样的应用场景，比如要获取两个用户之间的关系，即图中两个节点之间的路径，这个路径可以是关注，可以是都点赞了某个视频，关系型数据库无法满足性能需求。其他的图数据库有的是单机，有的是单 master，都不满足要求，因此需要造轮子。 字节的 Workload 分成了 3 种，比我平时听说的多了一种 OLTP，在线处理，比如一个用户发布了新文章，那么 (user,article),(user,tag), (article,tag) 这三条边就要被插入数据库。 OLAP，在线分析数据，一次需要查询大量数据做分析，比如做风险管理分析。 OLSP，这个第一次听说，Online Serving Processing。比如一个用户点赞了某个视频，那么后台需要实时计算他的喜好，然后推荐类似的视频。 整体架构如下所示： BGE, ByteGraph Execution Engine 负责执行 SQL 语句。 BGS, A cache layer in ByteGraph，负责存储相关。 底层的 KV Stroage 可以选用 RocksDB 或者 TerarkDB。 BGE 使用了 Gremlin 作为解析 query language 的解析器，这是一个专门用于图查询的工具。用户输入的查询语句经过 Gremlin 生成 execution plan 然后传给 BGE。 既然是查询引起，那么就涉及到分布式事务，BGE也是用了 2PC。 上图可以直观的显示 ByteGraph 数据库中所存的数据，可见 KV store 是比较适合存这类数据的，因此 BG 的最底层是 KV store。 ...

这期水一篇文章。 网上有很多人流传 Jeff Dean 的这个 Latency numbers，我看过很多遍但总是记不住，干脆把它抄下来算了。 L1 cache reference ......................... 0.5 ns Branch mispredict ............................ 5 ns L2 cache reference ........................... 7 ns Mutex lock/unlock ........................... 25 ns Main memory reference ...................... 100 ns Compress 1K bytes with Zippy ............. 3,000 ns = 3 µs Send 2K bytes over 1 Gbps network ....... 20,000 ns = 20 µs SSD random read ........................ 150,000 ns = 150 µs Read 1 MB sequentially from memory ..... 250,000 ns = 250 µs Round trip within same datacenter ...... 500,000 ns = 0.5 ms Read 1 MB sequentially from SSD* ..... 1,000,000 ns = 1 ms Disk seek ........................... 10,000,000 ns = 10 ms Read 1 MB sequentially from disk .... 20,000,000 ns = 20 ms Send packet CA->Netherlands->CA .... 150,000,000 ns = 150 ms 如果对上面的纳秒、毫秒还没有很直观的概念的话，有人给出了下面这样一个有意思的对比： ...