0x00 A Single Queue or Two Queues

TCP/IP stack has two options to implement the backlog queue for a socket in the LISTEN state.

Door #1: A Single Queue

A single queue can contain connections in two different states:

• SYN RECEIVED
• ESTABLISHED

And only connections in ESTABLISHED state can be returned to the application by calling the accept() syscall.

Therefore, the length of this queue is determined by the backlog argument of the listen() syscall.

Door #2: A SYN Queue & An Accept Queue

In this case, connections in state SYN RECEIVED are added to the SYN queue, and later moved to the accept queue when their state changes to ESTABLISHED.

之前写某个东西的副产品，本质上和 https://xuri.me/toml-to-go/ 一样。

解析 Toml 仍然依赖 github.com/BurntSushi/toml 这个库。

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

// Eliminates _ and capitalizes the key. The key needs to be exported.
// e.g hello_world -> HelloWorld
func normalizeStructKey(key string) string {
	str := strings.ReplaceAll(key, "_", " ")
	str = strings.Title(str)
	str = strings.ReplaceAll(str, " ", "")
	return str
}

// Generates golang strcut from a given toml file.
// Result needs re-format.
func translate(data map[string]interface{}) string {
	def := ""
	for key, value := range data {
		key = normalizeStructKey(key)
		vt := reflect.ValueOf(value)
		if vt.Kind() == reflect.Map {
			def += key + " struct {\n" + translate(value.(map[string]interface{})) + "\n}\n"
		} else if vt.Kind() == reflect.Slice {
			s := "[]interface{}"
			if vt.Len() > 0 {
				s = reflect.ValueOf(vt.Index(0).Interface()).Type().String()
			}
			def += key + " []" + s + "\n"
		} else {
			def += key + " " + vt.Type().String() + "\n"
		}
	}

	return def
}

if _, err := toml.DecodeFile(tomlPath, &data); err != nil {
    return err
}
inner := translate(data)

支持结构嵌套。

不过生成的文本大概需要 gofmt 一下才符合格式规范。

之前写了一篇分析 uber 的 automaxprocs 的源码，后面抽个了时间写了一个 C++ 版本的。

其一是为了加深对原库的理解；其二是避免太长时间没写 C++ 手生，以及顺带体验一下 C++ 17 的感觉。

代码在：https://github.com/kingsamchen/Eureka/tree/master/auto-cfs-cores

PS：一开始用 filesystem 的时候发现 libstdc++-8 需要专门连接一个 lstdc++fs，否则会因为符号不在同一个 lib 里直接 coredump。。。

最后折腾了一圈还是直接用了以前自己写的 Path

PPS：std::optional 还挺好用

最近直播内部的 golang 服务都使用了 uber 出品的 automaxprocs 这个库。

据伟大的 @ice 马总说，这个库解决了一个困扰B站整个golang（container）技术栈一年多的问题。

出于好奇这个库到底做了什么 magic，能够解决这个持续了一年多的 pain in the ass，抽了一点时间，稍微翻了一下库的源代码，记录如下。

automaxprocs 解决了什么问题

线上容器里的服务通常都对 CPU 资源做了限制，例如默认的 4C。

但是在容器里通过 lscpu 仍然能看到宿主机的所有 CPU 核心：

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

rchitecture:          x86_64
CPU op-mode(s):        32-bit, 64-bit
Byte Order:            Little Endian
CPU(s):                48
On-line CPU(s) list:   0-47
Thread(s) per core:    2
Core(s) per socket:    12
Socket(s):             2
NUMA node(s):          2
Vendor ID:             GenuineIntel
CPU family:            6
Model:                 79
Model name:            Intel(R) Xeon(R) CPU E5-2650 v4 @ 2.20GHz
Stepping:              1

这就导致 golang 服务默认会拿宿主机的 CPU 核心数来调用 runtime.GOMAXPROCS()，导致 P 数量远远大于可用的 CPU 核心，引起频繁上下文切换，影响高负载情况下的服务性能。

地址：https://github.com/kingsamchen/Eureka/tree/master/token-bucket-rate-limit

基于 token bucket 的限流实现相比于简单的“时间窗口计数”，更加“平滑”和稳定，不容易出现两个时间窗口衔接前后的 burst 请求。

并且可以直接用到上传/下载的速率控制上。

对于后端服务，可以用作实例的单机请求控制。

这里不打算详细介绍这个机制算法，具体的 concept/idea 可以看 Wikipedia，只对一些实现细节做一点小小的 hint。

虽然概念上，会以一定的速率 rate 往桶里填充 token，但是实际实现上，直接算出两次访问桶的时间差，然后乘以 rate 就能得到过去这段时间要往桶里填充多少 token 了。

所以这里有一个核心的过程：调整桶在任意时刻 t 时桶里的可用 token 数。

另外，考虑到扩展性，可以引入另外一个填充 token 的周期概念：tick。

即：

• 每个 tick 往桶里填充 N 个 token（quantum）
• 一个物理时间间隔 d（单位可以是秒，分，毫秒 .etc）为一个 tick 周期

这样填充速率就不受限为秒级速率了。

注意：10 tokens per 100ms 和 100 tokens per 1s 是有区别的。前者填充桶的间隔更短，可以减少请求等待的时间间隔。

桶的容量（capacity）如果明显大于填充速率 quantum，那么容量可以用来支持某段时间内的 burst 请求，这可能是期望的也可能不是期望的。

另外一个需要注意的点是，桶的可用 token 数是否必须严格大于0。

如果是，那么对于从桶取走 token 的接口语义需要仔细思考和设计（如果多个请求上下文共用一个桶，那么很可能会出现某个上下文一直拿不到 token 的情况）。

FYI：这个 demo 是基于 CPP 实现的，因为工作中一直在用 golang，为了避免 CPP 生疏，还是有必要经常性的练习。

Windows Terminal 中 git log 显示 UTF-8 编码的中文

这个准确的说其实是 powershell 自己的问题。

打开当前用户对应的 powershell 的 profile 文件，如果没有就创建一个，目录一般位于 C:\Users\<user>\Documents\WindowsPowerShell\Microsoft.PowerShell_profile.ps1

添加：

1

$env:LANG=zh_CN.UTF8

然后重启 powershell 即可。

Filename too long 导致 checkout 失败

原因是 git 默认使用旧版的 Windows API，对于路径的支持最大为 MAX_PATH（多么熟悉的宏）。

解决方法是直接开启 git 对 windows 的长文件名支持，执行

1

git config --global core.longpaths true

本文是对 Jeff Preshing 的 Double Checked Locking Is Fixed in C++ 11 笔记。

0x00 传统实现

因为 synchronization 只需要在实例第一次创建时保证；此后（ instance != nullptr 时）都不需要锁来保证 synchronization。

在第一次判断实例为空和上锁之间存在一个 potential race，因此上锁后需要再一次判断实例是否为空。

这也是 double checked 的来由。

所以一个传统但并不100%正确的 DCLP 实现如下：

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

class Singleton {
public:
    static Singleton* GetInstance()
    {
        if (instance == nullptr) {
            std::lock_guard<std::mutex> lock(mtx);
            if (instance == nullptr) {
                instance = new Singleton();				// <-- key point
            }
        }

        return instance;
    }

private:
    // omit explicit static field initialization.
    static std::mutex mtx;
    static Singleton* instance;
};

这基本是早起 C++ DCLP 的实现架子。

0x01 问题：内存乱序以及为什么锁帮不了忙

语句

1

instance = new Singleton();

在 C++ 中实际上等效于

1
2
3

tmp = operator new(sizeof(Singleton));  // step 1: allocate memory via operator new
new(tmp) Singleton;                     // step 2: placement-new for construction
instance = tmp;                         // step 3: assign addr to instance

注意：其中除了分配内存是固定第一步之外，构造对象和赋值内存地址的生成代码顺序是由编译器自己决定。这里的顺序只是一种可能性。