Sepk

当程序需要读取标准输入时，用户输入的字符串会被显示在终端界面上，在按下回车键之后才能够被程序读取。但是在一些场景下，这种交互逻辑是不合适的，例如需要将用户输入的密码进行隐藏，或者是根据用户已有的输入进行自动补全。这些功能的实现并不依赖于传统的标准输入交互，而是需要定义一套自己的交互逻辑。本文将介绍这种功能背后所用到的一些知识。

IO 控制层

当我们在终端中输入字符串时，字符串明明是被输入到标准输入，那么为什么会显示在标准输出呢？以及为什么程序不能够实时地接收到用户的输入呢？这是其实是因为用户在键盘上的输入并不会被直接写入到程序的标准输入中去，而是需要先经过一个 IO 控制层。IO 控制层中有默认的交互逻辑用于缓存并处理用户的输入。

IO 控制层定义了一套默认的用户输入准则，能够大大减少交互程序的设计复杂度。在交互性程序中，用户的输入并不能够保证一定正确，因此 IO 控制层会先将键盘输入写入到自身的缓冲区，并且将这些字符写入到程序的标准输出上，等到用户按下回车才会将缓冲区中的输入发送给用户程序，这样程序就不需要关心删除用户错误输入的逻辑。当用户按下退格时，IO 控制层会删除掉缓冲区中的相关字符串，并且覆盖标准输出中的信息。在通常的终端中，已经输出的信息是不能够删除的，这其实也是 IO 控制层的默认规则——为了防止用户删除过多的相关消息。但事实上，在命令行终端上，所有的字符都是可以删除的，例如贪吃蛇游戏就是利用相关的功能来实现的。

在另一方面，IO 控制层还需要处理一些控制信号，例如键盘中的 Control-C、Control-Z 信号、方向键等。当 IO 控制层收到键盘上的这些指令时，会生成相应的 Signal 并使用 kill 命令发送给程序。

IO 控制层的相关功能存储在Termios结构体中，当用户不需要 IO 控制层中的某些功能时，可以使用系统调用ioctl()函数来对其进行更改。一些需要实时交互的程序中，例如游戏，可以通过设置Termios中的标准模式标识位来关闭按行缓冲的模式，实时接收用户的输入。在不需要进行输入回显的情景下，例如输入密码，可以设置Termios中的回显为关闭状态，防止输入被打印到标准输出上。

Shell 命令补全

Shell 的命令补全是依赖于 GNU Readline 的，可以将后者理解为 IO 控制层的个性化定制版本。它通过设置 IO 控制层的相关参数，关闭了默认功能，并且自行实现了输入的处理逻辑。在标准的 IO 控制模式中，用户按下 Tab 键意味着输入一个制表符，而在 Shell 语境下，当用户按下 Tab 键时，会根据当前的输入进行命令补全。仔细梳理一下命令补全所需的功能，可以概括为以下几点：实时获取用户输入、缓存用户输入、补全字典、字符串显示以及抹除的功能。前面几条比较容易接触到，自行维护一个输入缓冲区以及前缀树即可，而字符串的显示以及模式则需要用到与屏幕控制码相关的内容。

屏幕控制码是终端中用于控制输出显示的特殊字符串，它可以用于控制屏幕上的光标位置、颜色、显示内容等相关功能。例如将一个光标移动到终端的 y 行 x 列，就可以通过将字符串"\033[y;xH"写入标准输出来实现。Readline 中的补全功能其实是通过读取光标位置、移动光标、打印待补全字符串、恢复光标到最初位置，这一系列操作来完成的，这些操作都是通过屏幕控制码来完成的。

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

void printStringToComplete() {
    // 控制命令：读取光标位置
    printf("\033[6n");
    // 控制命令：从标准输入读取位置
    int y,x;
    scanf("\033[%d;%dR", &y, &x);
    // 控制命令，移动光标
    printf("\033[%d;%dH",y+1,0);
    // 打印字符串
    printf("str to complete");
    // 恢复光标至原位置
    printf("\033[%d;%dH",y,x);
}

以上的代码就可以实现在当前输入的下一行打印出一行字符串并且返回到原始的输入位置。由于这段代码的处理速度非常快，因此在用户眼中是一个整体的过程。除了 Shell 中的命令补全，vim 中的相关操作同样也是使用这种技术路线来实现的。

终端与 Shell

命令行终端与 Shell 是两个经常容易混淆的概念，但实际上两者的位置是不同的。Shell 的软件位置其实是位于命令行终端的上层，或者说后端。命令行终端的职责更加偏向于处理 IO 设备的各种输入，通过 IO 控制层（或 Shell 自定义的处理逻辑）将其转换为操作系统中的可读语言（各种命令符号），然后将处理后的信息输入到 Shell 程序的标准输入中。而 Shell 的职责则是读取经过处理的输入，按照既定的逻辑调用操作系统的各种接口，最终实现相关的功能。

事实上，终端不止有命令行终端一种，物理终端同样也是终端的一种。在 IO 控制层中，有一些命令是用于调节输入的波特率等参数的，这些参数只适用于物理终端。终端的意义在于“输入的转换”，而在命令行终端中，这一职责其实被淡化了，因此也就容易与其他概念进行混淆。

出于学习 Golang 和 Redis 的目的，我自己尝试着写了一个开源项目 MemTable，依照 Redis 的架构和思路来实现一个内存 KV 存储服务。在基本上完成这个项目中，通过性能测试我发现了项目中的一些不足之处，在此记录。

内存用量统计与接口性能

Redis 中有一个重要的特性是利用 LRU 与 LFU 算法进行键值对的淘汰，这对数据库模块提出了两个要求：所有的键值对必须具有淘汰字段、所有的键值对必须能够统计内存用量。在设计这一功能的时候，我直接使用了 interface 来定义数据库中存储的 Value，这听上去是非常简洁的，只需要在每一个 structure 当中都实现一个内存统计的接口即可。但是这却带来了比较严重的性能问题——在加入该功能后，数据库的 QPS 下降了约 2%左右，而当发生键值对淘汰时，QPS 约下降了 7%左右。这一问题来源于 go 接口的语言特性，参考博客文章探索 Go 中接口的性能。

该文章中提到，不对接口进行断言，直接调用接口中声明的函数时，会导致内存逃逸以及内联失效。最终的结果就是这种调用方式的时间开销大约在几纳秒的量级，是一个较大的开销。以下测试代码来自上文中的博客文章。

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

import (
    "testing"
)

type D interface {
    Append(D)
}

type Strings []string

func (s Strings) Append(d D) {}

func BenchmarkInterface(b *testing.B) {
    s := D(Strings{})
    for i := 0 ; i < b.N ; i += 1 {
        s.Append(Strings{""})
    }
}

func BenchmarkConcrete(b *testing.B) {
    s := Strings{} // only difference is that I'm not casting it to the generic interface
    for i := 0 ; i < b.N ; i += 1 {
        s.Append(Strings{""})
    }
}

func BenchmarkInterfaceTypeAssert(b *testing.B) {
    s := D(Strings{})
    for i := 0 ; i < b.N ; i += 1 {
        s.(Strings).Append(Strings{""})
    }
}

最终的测试结果如下：

1
2
3
4
5
6
7
8
9
10
11

goos: darwin
goarch: amd64
pkg: github.com/tangrc99/MemTable/utils
cpu: Intel(R) Core(TM) i5-7267U CPU @ 3.10GHz
BenchmarkInterface
BenchmarkInterface-4             	453919813	         2.607 ns/op
BenchmarkConcrete
BenchmarkConcrete-4              	1000000000	         0.2945 ns/op
BenchmarkInterfaceTypeAssert
BenchmarkInterfaceTypeAssert-4   	1000000000	         0.2950 ns/op
PASS

在高版本的 go 中，接口的性能开销降低了，但是其开销相比于类型转换仍然是比较高的。为了取得比较高的性能，一个更好的做法是定义一个通用 Value 字段，所有的非取值操作都直接从 Value 中完成。

1
2
3
4
5

type Value struct {
	eviction int64 // 驱逐字段
	cost uint64	// 内存开销
	value Value	// 真实 value 字段
}

数据库中哈希表直接存储 Value struct，只有在必要时才拿出 value 值。这样能够避免使用接口的开销，是一个更好的选择。

指针结构与 GC 问题

另外一个比较严峻的问题则是 GC 问题。内存数据库其一个重要优点就是支持灵活多变的数据结构，这些数据结构大量使用了指针，会给 go 的 GC 带来比较严峻的挑战。在数据量较大时，go 仿写的 redis 项目 GC 时间可以达到 0.5s 以上，这是不可以接受的。C/C++ 中的内存释放开销时被均摊的，但是在 go/JAVA 这种 GC 语言上内存释放不会被均摊，而是一个瞬时消耗。提高吞吐量的一个很好的思路就是去均摊每一个开销，这样能够使得服务的响应比提升。

实际上，是有办法去避免 go 的 GC 开销的，那就是使用 mmap 来进行内存分配，并将所有的指针代替为 uintptr 类型。uintptr 中的地址不会被GC 扫描到，并且 GC 不会去主动释放 mmap 分配出的内存，这种做法是绝对安全的。同时，直接计算 mmap 的内存大小，能够更好地去估计当前进程使用的内存量，是一个一举两得的措施。但是这样做会对数据结构的设计有更高的要求。在 go 中避免 GC 的代价实在是太大了，在一些进程内缓存的场景，可以说使用这种方式能够减少调用开销，但是作为 KV 存储服务，显然使用无 GC 语言是一个更好的选择。

网络库与 goroutine 调度

为了实现用户态线程的调度，go 网络库中只可能提供阻塞的网络读写，这就要求一个 goroutine 只能够处理一个 client 的请求。这能够降低复杂应用场景下的开发难度。但是对于 Redis 这种业务简单，客户端数量极多的情况，是不太适合的。首先，Redis 中的请求处理是无阻塞的，所以不存在事务执行中的暂停与切换问题，所以 goroutine 的这种模式对于 Redis 事务处理的帮助的微乎其微的。而在另一方面，这种模式甚至有一定的劣势。由于 Redis 中是单事务线程，即使有 10W 个 goroutine，那么也只有少数能够是活跃的。这就会给 goroutine 调度器造成压力。在 pprof 测试中，MemTable 有 60% ~ 70%的时间花费在寻找可运行 goroutine 上。并且 goroutine 在运行10ms 后会被强制调度出去，这就会导致事务线程被无意义的中断，造成一定的切换开销。

如果将单事务线程切换为多事务线程，那么性能会提升吗？我测试过 github 中的一些类型项目，这些项目是使用多事务线程来构建的，数据库采用读写锁来进行保护。当只读操作很多的时候，这种设计当然会提升性能，但是写操作增多时，这种设计并不能够提升性能，反而会造成一定的性能下降。在 redis-benchmark 中，多事务线程的设计会造成 QPS 下降约 6%。

从功能上进行考虑，使用多线程其实也是不太适合的。例如事务操作、多键值对操作、持久化操作，这些处理起来都是比较棘手的。要实现这些功能，数据库内部是一定需要大量加锁的，这会提升开发的难度，并且内存数据库的性能瓶颈是在网络 IO 上，这种付出与回报其实是不成正比的。

go 的优势

如果只是作为学习的话，使用 go 来仿写 redis 是有自身的优势的。其一在于，Redis 用到的功能比较多，使用 C/C++ 时会用到很多第三方依赖库，这些依赖库的风格可能有很大不同，这会增加开发难度。而 go 基本上提供了所有需要的依赖库。其二在于，使用 goroutine 加 channel 可以很轻松地模拟出多线程解析这一特性，在数据量较小时，性能甚至会高于 Redis。