面试复习提纲

Go

数据结构

Go 本身只有数组、切片、映射、字符串 几种数据结构

数组

数组是基本的顺序表，在初始化时需要声明长度与类型，而后会申请类型长度 × 数据个数的内存空间。
从底层来看，数组是一段定长的内存，借助于下标可以实现指定位置数据的快速访问。
不同长度的数组之间不能互相赋值
为了提升实际效率，小于 4 个的数组会直接在栈上初始化（展开成多行赋值），而多余 4 个的则会在静态存储区初始化后拷贝到栈上

切片

切片功能上实现了可变长度的数组，可以按需自动增长和缩小。在申请切片时，除去长度外，还可以标明容量。容量为为暂未使用的空间，尽管已经分配给该数组，但是在未主动扩容前，只能访问长度部分的内存。
切片将会分配cap长度的内存，并将len长度的内存标为可用。对于这len长度的部分，可以当作数组一样使用。每当新插入数据时，则会从cap获取空间到len中。这样可以避免频繁的申请内存及复制。

插入元素时，如果容量不足以容纳新的元素，就会触发扩容。当切片长度小于 1024 时，每次扩容都会直接翻倍；而超过 1024 时，则会变为 1.25 倍。但如果插入的元素很多，则会根据插入元素的数量进行扩容。

需要注意的是，如果对切片取子切片，实际上是共用的同一段地址，也即如果b = a[2:4]，那么修改a[3]会同时改变b[2]！
下一个需要注意的是，如果a由于append触发扩容后，由于被分配了新的内存，这时再修改a[3]就不会再影响b[2]。
如果分别对b进行append()，并且未触发扩容，那么其会覆盖a的值
也即子切片实际上是原本切片的一个“窗口”，要避免产生这个窗口，可以使用copy(b, a[2:4])

同样，由于切片取子切片会复用内存，如果从一个大切片取出一个小的子切片，那么直到子切片被释放前，大切片都不会被释放，这可能会浪费大量的内存。

具体可见下面代码的输出

package main

import "fmt"

func main() {
	a := make([]int, 5, 7)
	for i := 0; i < len(a); i++ {
		a[i] = i
	}
	// b := make([]int, 2)
	// copy(b, a[2:4])
	b := a[2:4]
	fmt.Println(a, len(a), cap(a)) // [0 1 2 3 4] 5 7
	fmt.Println(b, len(b), cap(b)) // [2 3] 2 5
	a[3] = 33
	fmt.Println(a, len(a), cap(a)) // [0 1 2 33 4] 5 7
	fmt.Println(b, len(b), cap(b)) // [2 33] 2 5
	a = append(a, 99)
	a = append(a, 99)
	b = append(b, 666)
	fmt.Println(a, len(a), cap(a)) // [0 1 2 33 666 99 99] 7 7
	fmt.Println(b, len(b), cap(b)) // [2 33 666] 3 5
	a = append(a, 99)
	a = append(a, 99)
	a[3] = 333
	fmt.Println(a, len(a), cap(a)) // [0 1 2 333 666 99 99 99 99] 9 14
	fmt.Println(b, len(b), cap(b)) // [2 33 666] 3 5
}

映射

映射在别的语言中可能会被称为哈希表、字典。其实现了无序键值对的快速检索，可以根据 key 快速获取 value
在底层，映射使用哈希表 + 链表实现

每一个键值对，将会根据 key 计算哈希值，存储到对应的桶（链表）中，每个桶最多可以存储 8 个键值对（键数组和值数组）。当超过 8 个时，会存储入溢出桶，直至触发扩容。

对于初始化值小于 25 个的映射，将会被展开为多个赋值语句；而对于多于 25 个的初始化数据，则会展开为 key 数组和 value 数组循环赋值。

如果溢出桶过多（溢出桶的出现意味着某个哈希值对应了很多键值对），将会降低查询效率，因此需要通过扩容来降低每个桶的负载。当出现下面两种情况时，发生扩容：

装载因子超过6.5（元素数量 ÷ 桶数量） - 翻倍扩容
溢出桶过多 - 等量扩容

发生溢出桶很多但又未触发装载因子超过6.5原因是大量地插入删除导致数据被集中在溢出桶中，需要将这些桶的数据进行重新整理，避免内存泄漏
而翻倍扩容则是将一个桶的内容分发到两个桶中存储（如原本取哈希前 3 位，扩容后取前 4 位）。

映射的 key 必须是一个不可变对象，也即可以进行可以进行比较、默认使用深拷贝的对象。一方面是为了可以计算哈希值；另一方面是避免了引用类型被修改导致 key 也被连带修改

字符串

字符串的逻辑上等同于数组，结构上和切片很类似，没有cap字段。
考虑到性能、映射等各种问题，字符串是不可变的，尽管可以使用a = a + "abc"来实现修改，但是这实际上返回的是一个全新的字符串。

另外，单纯使用+或者fmt.Sprintf()性能是非常慢的，因为需要大量的内存申请。对于大量数据的拼接，应该使用strings.Builder或bytes.Buffer

在使用range遍历字符串时，返回的是rune而非类似 C/C++ 的 char(byte)。
rune实际上是一个int32类型，对应的是 Unicode。
对于所有非纯英文操作，如涉及中文，应该先转换为[]rune后再处理

package main

import (
    "bytes"
    "fmt"
)

func main() {
    s := "Hello 世界"
    for _, c := range s {
        buf := bytes.NewBuffer([]byte{})
        buf.WriteRune(c)
        fmt.Printf("%T %c %+v %+v\n", c, c, buf.Bytes(), byte(c))
    }
    fmt.Println(len(s), len([]rune(s)))
    fmt.Println([]rune(s))
    fmt.Println([]byte(s))
}

输出为（这里的 19990、30028 是 Unicode 原始字码，非 UTF-8 编码）

int32 H [72] 72
int32 e [101] 101
int32 l [108] 108
int32 l [108] 108
int32 o [111] 111
int32   [32] 32
int32 世 [228 184 150] 22
int32 界 [231 149 140] 76
12 8
[72 101 108 108 111 32 19990 30028]
[72 101 108 108 111 32 228 184 150 231 149 140]

如果需要比较两个[]string是否相等，应该使用reflect.DeepEqual()，而非目前网络上推崇的for循环。

对于切片长度较长，而字符串本身并不长的情况，使用反射可以达到很好的效果。
对于切片长度本身较短，而字符串本身很长的情况，应该使用 for 循环来进行判断。

尽管切片较短时，for 循环占优，但优势并不明显！而反之则有非常明显的优势

零值与空值

整数类（int、int8、uint8、byte……）: 0
浮点数类（float32、float64）: 0.0
布尔型（bool）: false
指针: nil

Go 中，nil 不是一个关键字，下面的代码是可以正确输出的

package main

import "fmt"

func main() {
	nil := 1
	fmt.Println(nil) // 1
}

并且我们理解上的nil本身也是包含很多细节的，其表示 该类型 指针的空值，也即不同类型的指针对应的nil是不一样的，不同类型的nil不能直接比较，但都可以与nil本身比较。但可以借助interface{}来比较两个不同类型的nil

package main

import "fmt"

func main() {
	var a *int = nil
	var b *int8 = nil
	fmt.Printf("%#v %#v %#v %#v\n", a, b, a == nil, b == nil) // (*int)(nil) (*int8)(nil) true true
}

init 函数和 defer

当一个编译好的 Go 程序运行时，首先会构建依赖关系，没有任何依赖的包优先处理，按照 **常量 → 变量 → 各个init() ** 的顺序进行初始化，接着会继续对其他包进行初始化。当所有初始化完成后，执行 main()

同一个文件内，可以包含多个 init()，但 运行顺序不做保证

以下面的代码为例，共包括两个文件

package dep

import "fmt"

var a = func() int {
	fmt.Println("dep 1")
	return 0
}()

func init() {
	fmt.Println("dep 2.1")
}

func init() {
	fmt.Println("dep 2.2")
}

func init() {
	fmt.Println("dep 2.3")
}

package main

import (
	"fmt"

	_ "temp/dep"
)

var a = func() int {
	fmt.Println(1)
	return 0
}()

func init() {
	fmt.Println(2.1)
}

func init() {
	fmt.Println(2.2)
}

func init() {
	fmt.Println(2.3)
}

func main() {
	fmt.Println(3)
}

通常，输出应该是（没有其他因素影响，init()顺序调用）

dep 1
dep 2.1
dep 2.2
dep 2.3
1
2.1
2.2
2.3
3

defer 会在函数退出时运行，当有多个 defer 时，将会逆序调用。

通常 defer 可以用于关闭文件，清理资源

new 和 make

new 只会分配内存，返回的是一个指针。内存的内容会被初始化为全 0（各类型的零值）

map在分配内存后，返回对象的引用；除此之外，map 还可以初始化xslice、map、channel

panic 和 error

Go 没有单独的异常类型，其异常使用panic()抛出，可接受的参数为interface{}

Go 使用错误和异常两种概念，来对应其他语言中的异常(Exception)，前者使用error作为函数的返回值来解决，后者则通过panic()、recover()、defer来实现

格式化打印

占位符	含义	#	# 含义	+	+ 含义
`%v`	输出内容默认格式	`%#v`	输出类型及详细格式	`%+v`	输出内容详细格式（输出结构体字段名）
`%T`	输出类型
`%%`	输出`%`
`%t`	输出布尔类型
`%b`	输出二进制数字	`%#b`	输出十进制数字（带前导 0b）	`%+b`	输出十进制数字（带正负号）
`%d`	输出十进制数字			`%+d`	输出十进制数字（带正负号）
`%o`	输出八进制数字	`%#o`	输出八进制数字（带前导 0）	`%+o`	输出八进制数字（带正负号）
`%x`	输出十六进制数字（或十六进制表示字符串）	`%#x`	输出十六进制数字（带前导 0x）	`%+x`	输出十六进制数字（带正负号）
`%X`	输出大写十六进制数字（或十六进制表示字符串）	`%#X`	输出大写十六进制数字（带前导 0X）	`%+X`	输出大写十六进制数字（带正负号）
`%U`	输出 Unicode 编码（格式为`U+0000`）	`%#U`	输出 Unicode 编码及对应字符（带单引号）
`%e`	按照科学计数法输出数字			`%+e`	按照科学计数法输出（带正负号）
`%E`	按照科学计数法输出数字（大写 e）			`%+e`	按照科学计数法输出（大写 E，带正负号）
`%f`	输出浮点数			`%+f`	输出浮点数（带正负号）
`%g`	根据合适输出`%e`或`%f`			`%+g`	自动选择合适的输出（带正负号）
`%G`	根据合适输出`%E`或`%f`			`%+G`	自动选择合适的输出（带正负号）
`%c`	输出数字对应的 Unicode 字符
`%s`	输出字符串
`%q`	输出字符串（使用引号包裹并转义）	`%#q`	输出字符串（使用反引号包裹，需要转义时，按`%q`输出）	`%+q`	输出 Unicode 编码（格式为`\u0000`）
`%p`	输出的地址指针（前导为 0x）	`%#p`	输出地址指针（不带前导）

内存对齐

与 C 相同，Go 中也存在内存对其的问题，在 32 位系统中，对齐系数为 $4$ （ $32Bytes$ ）；64 位系统中，对齐系数为 $8$ （ $64Bytes$ ）。

需要内存对齐的原因如下:

跨平台: 不是所有的硬件平台都能够访问任意地址上的任意数据。例如：特定的硬件平台只允许在特定地址获取特定类型的数据，否则会导致异常情况
性能: 若访问未对齐的内存，将会导致 CPU 进行两次内存访问，并且要花费额外的时钟周期来处理对齐及运算。而本身就对齐的内存仅需要一次访问就可以完成读取动作，这显然高效很多，是标准的空间换时间做法
原子操作: 在 32 位系统原子操作 64 位数据，必须 8 字节对齐，否则无法处理

结构体的变量会按顺序存入内存，同时内存中的数据以对齐系数划分成行，如果新的结构体超出当前行的剩余空间，则会被存入新的一行中。上一行剩余的空间使用 padding 填充，如果数据结构存在很多变量，不恰当的对齐可能会浪费大量空间

由于 struct{} 占用的空间为零，往往其不需要内存对齐，但当其为最后一个成员变量时，将会占据单独的一行

type demo1 struct {
	a int8
	b int16
	c int32
}

type demo2 struct {
	a int8
	c int32
	b int16
}

func main() {
	fmt.Println(unsafe.Sizeof(demo1{})) // 8
	fmt.Println(unsafe.Sizeof(demo2{})) // 12
}

通道（channel）

channel 是 Goroutine 之间的通信方式。其打通了不同的协程，使他们之间可以非常方便的传输数据

缓冲区

缓冲区可以允许通道内存储缓冲区个数个数据。

如无缓冲的 channel（等价于make(chan T,0)），每当发送方发送一条数据时，发送方将会被阻塞，直到接收方取出数据后才会继续运行

而有缓冲 channel 则允许存储多条数据不阻塞发送方。

可以参考下面的代码，修改通道的缓冲长度，查看被阻塞的主函数

package main

import (
	"fmt"
	"time"
)

func main() {
	fmt.Println(1)
	c := make(chan byte, 1)
	fmt.Println(2)
	go func() {
		for {
			time.Sleep(time.Second * 5)
			select {
			case <-c:
				fmt.Println("recv")
			}
		}
	}()
	c <- 0x1
	fmt.Println(3)
	c <- 0x2
	fmt.Println(4)
}

通道的 panic

关闭一个 nil 通道
关闭一个已关闭的通道
向已关闭的通道发送信息

关闭通道

使用close(c)可以关闭一个通道。
一个已经关闭通道再次关闭，或是向关闭的通道发送数据都会导致 panic。

要避免重复的关闭通道可以使用sync.Once
可以使用程序逻辑来告知发送者停止发送信息，避免触发 panic

Go 内存管理

Go 的对象（struct）可以分配在栈上，Go 会在编译时通过逃逸分析确定数据是否超出当前作用域，如果未超过当前作用域，则会被分配在栈上，而不是堆上，从而减轻 GC 负担¹

页堆

页堆(page heap, mheap): 一组连续的页面被称为 span，当分配 大对象（ $\ge 32KB$ ）或是编译器无法计算大小的数据，使用页堆分配，分配时会加中央锁（同时只能分配一个）。这时最大的内存块，也是进行垃圾回收的地方。

mheap 通过将页归为不同的结构进行管理

mspan: 双向链表，包含页起始地址、大小、页面数量。根据内存页按照大小分为 67 个不同类别，大小从 $8Bytes$ 到 $32KB$ 。每个 mspan 包含两个，一个用于带指针对象，一个用于无指针对象，便于 GC
mcentral: 相同大小的 span 归类在一起，每个 mcentral 包含两个 mspanList
- empty: 双向 span 链表，包括没有空闲对象的 span 或缓存 mcache 中的 span
- non-empty: 有空闲对象的 span 双向链表，当向 mcentral 请求 span 时，从这里获取 span 并移入 empty
arena: 当需要更多内存时，从虚拟内存中以每块 $64MB$ 为单位获取新内存，将会被划分页并映射到 span
mcache: 用于提供给每个 goroutine 的高速缓存，用于存储 小对象（ $\le 32KB$ ），类似于线程堆栈，但属于堆。可以在不加锁的情况下高效分配小内存

栈

每个 goroutine 有一个栈存储静态数据，包括函数栈帧、静态结构、原生类型值、指针

分配过程

Go 中根据对象大小来决定如何分配

微对象（ $size \lt 16Bytes$ ）: 从 mcache 的微小分配器分配
小对象（ $16Bytes \le size \le 32KB]$ ）: 分配在 mcache 对应的 mspan，如果不足将从 mheap 分配新的 mspan
大对象（ $size \ge 32KB$ ）: 直接分配在 mheap 上，如果 mheap 不足，则从操作系统分配新的页

Go 垃圾回收

Go 的垃圾回收机制为 带三色标记的标记清除²，其包含两个阶段：

标记: 从根对象开始查找所有存活的对象
清除: 遍历所有对象，将未被标记的对象回收

常规的标记清除策略，要求程序暂停，因此通过三色抽象，来实现更复杂的流程。

三色标记算法的对象包含三种颜色：

白色: 潜在的垃圾，可能会被回收
黑色: 活跃的对象，根对象可达或未引用外部指针
灰色: 活跃的对象，存在指向对象兑现的指针

通过不确定的白色对象，来实现垃圾回收的同时执行用户程序

三色标记法的流程如下：

暂停用户程序
将根对象标记为灰色，其他对象标记为白色
继续用户程序
从灰色集选择一个灰色对象，将灰色对象标记为黑色
将黑色对象指向的所有子对象标记为灰色
重复 4，直到灰色集为空

但如果在标记阶段中，一个对象被使用，建立了 A 对象到 B 对象的引用。如果 A 对象已经被标记为黑色，那么 B 对象可能会保留白色，并被错误释放。这种情况称为悬挂指针，属于非常严重的错误。

要解决该问题，需要使用屏障技术，确保 CPU 执行的顺序性。要保证并发、增量标记正确性，需要达成下面两种三色不变性中的一种：

强三色不变性: 黑色对象不会指向白色对象
弱三色不变性: 黑色对象指向的白色对象必须:source包含一条从灰色经由多个白色的可达路径

Go 使用了两种写屏障技术，在写操作时，执行相应的逻辑。

插入写屏障: Dijkstra 在 1978 年提出，当需要执行*slot = ptr时，首先会通过shade(ptr)尝试将新的对象改为灰色。该方案保证了强三色不变性，但是并未清除原本的老对象，这些需要释放的内存需要等到下一个循环才会被回收
删除写屏障: Yuasa 在 1990 年提出，当需要执行*slot = ptr时，将会使用shade(slot)将老的对象改为灰色，确保了弱三色不变性

Go 调度器

目前的 Go 调度器主要采用 GMP 模型³⁴

G: Goroutine，Go 协程
M: Thread，线程
P: Processor，处理器（本地调度器）

Go 程序会在启动时，初始化GOMAXPROCS个处理器（默认是 CPU 核心数），每个处理器将负责维护一个 Goroutine 队列。
当有 Goroutine 被创建时，其首先会出现在一个公共队列中，由各个处理器从公共队列获取一部分 Goroutine 加入到自己的本地队列中（这样可以避免频繁地访问公共队列，由于各个处理器属于并发执行，加锁花销很大）。
每个处理器会对应一个用以执行任务的线程，处理器会将当前本地队列第一个 Goroutine 交给线程运行，并在合适实际切换到下一个 Goroutine。
当处理器本地队列为空时，处理器会尝试从公共队列获取 Goroutine，或从其他处理器窃取 Goroutine（工作窃取）
如果由于系统调用线程被阻塞，那么处理器将会重新绑定一个空闲的线程或新建一个线程进行任务。被阻塞的线程在阻塞结束后，将会寻找一个空闲的处理器或插入到等待队列中。

Go IO 模型

Go net 包通过封装 epoll 实现 IO 复用，是传统多线程模型（goroutine）和 IO 复用模型的结合，既有多线程模型的易用性，又拥有 IO 复用的高性能

互斥锁和读写锁

互斥锁(sync.Mutex)是确保一段代码只有一个协程在执行，当一个协程获取锁后，其他协程都将被阻塞

互斥锁有两种状态

正常状态: 所有等待锁的 goroutine 按照 FIFO 顺序等待。唤醒的 goroutine 不会直接拥有锁，而是会和新请求锁的 goroutine 竞争锁的拥有。新请求锁的 goroutine 具有优势：它正在 CPU 上执行，而且可能有好几个，所以刚刚唤醒的 goroutine 有很大可能在锁竞争中失败。在这种情况下，这个被唤醒的 goroutine 会加入到等待队列的前面。如果一个等待的 goroutine 超过 1ms 没有获取锁，那么它将会把锁转变为饥饿模式。
饥饿模式: 锁的所有权将从 unlock 的 goroutine 直接交给交给等待队列中的第一个。新来的 goroutine 将不会尝试去获得锁，即使锁看起来是 unlock 状态, 也不会去尝试自旋操作，而是放在等待队列的尾部；如果一个等待的 goroutine 获取了锁，并且满足一以下其中的任何一个条件：(1)它是队列中的最后一个；(2)它等待的时候小于1ms。它会将锁的状态转换为正常状态。

读写锁(sync.RWMutex): 将读操作和写操作分离，因为单纯的读操作是可以并行处理不产生问题的。在读操作原多于写操作的情况下，施加读写锁可以减少阻塞的发生

协程退出

协程只能由自己控制自己退出，别的协程（包括主线程）都不能控制其他协程退出。因为如果存在一个强制关闭的机制，那么对于资源的处理将会非常复杂，如果 defer 内存在阻塞的代码，甚至会导致整个程序卡死。

算法

排序算法

名称	空间复杂度	平均时间复杂度	最优时间复杂度	最坏时间复杂度	稳定
直接插入排序	$O(1)$	$O(n^2)$	$O(n)$	$O(n^2)$	是
冒泡排序	$O(1)$	$O(n^2)$	$O(n)$	$O(n^2)$	是
简单选择排序	$O(1)$	$O(n^2)$	$O(n^2)$	$O(n^2)$	否
希尔排序	$O(1)$	$O(n^2)$	$O(n)$	$O(n^2)$	否
快速排序	$O(log_2n)$	$O(nlog_2n)$	$O(nlog_2n)$	$O(n^2)$	否
堆排序	$O(1)$	$O(nlog_2n)$	$O(n^2)$	$O(log_2n)$	否
归并排序	$O(n)$	$O(nlog_2n)$	$O(nlog_2n)$	$O(nlog_2n)$	是
基数排序	$O(r)$	$O(d(n+r))$	$O(d(n+r))$	$O(d(n+r))$	是

插入排序: 将数字插入到已排序数组的对应位置
- 内存优化（直接插入排序）: 使用长度为n的数组存储，并使用pos标记已排序（<= pos）和未排序（> pos）区间
- 时间优化: 链表存储
希尔排序: 设置步长gap为长度n除以 2，得到gap组 2 个数的集合，对这些集合进行插入排序；将gap缩小至一半，重复上述过程，直到gap为 1
简单选择排序: 不停的找到未排序部分最小的数放到最前面
堆排序: 将数据插入到一个小顶堆中
冒泡排序: 发现相邻的两个数存在逆序关系时，交换他们的位置

快速排序: 在区间内取中间值，将小于中间值和大于中间值的分别移动到两侧，再对两侧区间继续快速排序

func QuickSort(nums []int) {
    if len(nums) <= 1 {
        return
    }

    var l, r = 0, len(nums) - 1
    mid := (nums[l] + nums[r]) / 2
    for l < r {
        for l < r && nums[l] <= mid {
            // 因为 mid 有可能是最小值，因此应该把相等的分到左侧
            l++ // 从左往右找到第一个大于 mid 的值
        }
        for l < r && nums[r] > mid {
            r-- // 从右往左找到第一个小于等于 mid 的值
        }
        if l < r {
            // 交换两个“位置错误”的数
            nums[l], nums[r] = nums[r], nums[l]
            l++
        }
    }
    QuickSort(nums[:l])
    QuickSort(nums[l:])
}

归并排序: 将区间分为两部分，并对两部分分别进行归并排序，而后将两部分（已排序）合并
基数排序: 按照每一位的顺序放置到不同的桶内，取出即可得到有序的结果
计数排序: 将一个长度为最大值的数组记为false，将存在的数设置为true，遍历得到true的结果
睡眠排序: 对每个数n建立一个休眠 n 秒的线程，休眠结束后输出n

平衡二叉树

深度: 距离叶子的距离
平衡二叉树任意一个节点左右子树深度绝对值不大于 1
但是极端情况下，平衡二叉树可能形状并不那么“平衡”
在修改数据后，平衡二叉树需要通过左旋、右旋来确保新的树仍然平衡（旋转只涉及三个节点）
左旋

      a                    b
    /   \       左旋      /  \   
   x     b      ==>     a    y
       /   \           /  \
      c     y         x    c


      a                   b              
    /   \      右旋      /  \
   b    y      ==>     x     a
  /  \                     /   \
 x    c                   c     y

插入时间复杂度: $O(log_2n)$
查询时间复杂度: $O(log_2n)$
删除时间复杂度: $O(log_2n)$

每次插入操作，都需要递归更新深度，并判断是否需要旋转
每次删除操作，在找到要删除的节点后，需要找到其右孩子的最小值（该节点可能存在右孩子），并将该最小值升级到被删除的位置，同时递归更新路径上所有节点

// Tree 平衡二叉树结构
type Tree struct {
	number int
	count  int
	left   *Tree
	right  *Tree
	depth  int
}

// NewTree 生成一个平衡二叉树
func NewTree() *Tree {
	return nil
}

// NewTreeNode 新建一个二叉树节点
func NewTreeNode(number int) *Tree {
	return &Tree{
		number: number,
		count:  1,
		left:   nil,
		right:  nil,
		depth:  1,
	}
}

// Insert 向树内插入一个数
func (t *Tree) Insert(n int) *Tree {
	if t == nil {
		return NewTreeNode(n)
	}
	if n == t.number {
		// 就是当前值
		t.count++
		t.updateNode()
		return t
	} else if n > t.number {
		// 插到右边
		t.right = t.right.Insert(n)
	} else {
		// 插到左边
		t.left = t.left.Insert(n)
	}
	t.updateNode()
	return t.rotate()
}

// Remove 删除一个指定的元素（个数减一）
func (t *Tree) Remove(n int) (*Tree, error) {
	if t == nil {
		return nil, fmt.Errorf("Can not find number %d in AVL Tree", n)
	}
	if n == t.number {
		t.count--

		if t.count <= 0 {
			if t.left != nil && t.right != nil {
                // 拥有左右孩子，将右孩子的最小值提升
				minLeaf, tmp := t.right.removeLeft()
				minLeaf.left = t.left
				minLeaf.right = tmp
				minLeaf.updateNode()

				return minLeaf.rotate(), nil
			} else if t.left != nil {
                // 只有左孩子，提升左孩子
				return t.left, nil
			} else {
                // 只有右孩子，提升右孩子
				return t.right, nil
			} else {
                // 没有孩子，直接移除
                return nil, nil
            }
		}
		return t, nil
	} else if n > t.number {
		var err error
		t.right, err = t.right.Remove(n)
		t.right.updateNode()
		return t.rotate(), err
	} else {
		var err error
		t.left, err = t.left.Remove(n)
		t.left.updateNode()
		return t.rotate(), err
	}
}

func (t *Tree) removeLeft() (minLeaf *Tree, newRoot *Tree) {
	if t.left == nil {
		minLeaf = t
		newRoot = t.right
		return
	}
	minLeaf, t.left = t.left.removeLeft()
	t.updateNode()
	newRoot = t.rotate()
	return
}

// Min 获取平衡二叉树的最小值
func (t *Tree) Min() (int, error) {
	if t == nil {
		return 0, fmt.Errorf("Can not get the min number in an empty AVL Tree")
	}
	tmp := t
	for tmp.left != nil {
		tmp = tmp.left
	}
	return tmp.number, nil
}

// Max 获取平衡二叉树的最大值
func (t *Tree) Max() (int, error) {
	if t == nil {
		return 0, fmt.Errorf("Can not get the max number in an empty AVL Tree")
	}
	tmp := t
	for tmp.right != nil {
		tmp = tmp.right
	}
	return tmp.number, nil
}

// Depth 获取平衡二叉树节点的深度
func (t *Tree) Depth() int {
	if t == nil {
		return 0
	}
	return t.depth
}

// updateDepth 更新子树深度（左右子树深度必须已更新）
func (t *Tree) updateDepth() {
	if t != nil {
		leftDepth := t.left.Depth()
		rightDepth := t.right.Depth()

		if leftDepth < rightDepth {
			t.depth = rightDepth + 1
		} else {
			t.depth = leftDepth + 1
		}
	}
}

func (t *Tree) updateNode() {
	if t != nil {
		t.updateDepth()
	}
}

// Rotate 尝试旋转树（如果需要）
func (t *Tree) rotate() *Tree {
	if t == nil {
		return t
	}
	leftDepth := t.left.Depth()
	rightDepth := t.right.Depth()

	if leftDepth-rightDepth > 1 {
		// 左子树深度大于右子树深度
		// 右旋
		return t.rotateRight()
	} else if rightDepth-leftDepth > 1 {
		// 左子树深度小于右子树深度
		// 左旋
		return t.rotateLeft()
	}

	return t
}

// RotateRight 平衡二叉树右旋
func (t *Tree) rotateRight() *Tree {
	a := t
	b := a.left
	c := b.right

	a.left = c
	b.right = a

	a.updateNode()
	b.updateNode()

	return b
}

// RotateLeft 平衡二叉树左旋
func (t *Tree) rotateLeft() *Tree {
	a := t
	b := a.right
	c := b.left

	a.right = c
	b.left = a

	a.updateNode()
	b.updateNode()

	return b
}

// Count 获取指定节点存储的数字个数
func (t *Tree) Count() int {
	if t == nil {
		return 0
	}
	return t.count
}

// Number 获取指定节点存储的数字内容
func (t *Tree) Number() int {
	if t == nil {
		return 0
	}
	return t.number
}

// Print 打印二叉树
func (t *Tree) Print() {
	if t != nil {
		fmt.Printf("%d [%d %d] %d\n", t.Number(), t.left.Number(), t.right.Number(), t.Count())
		t.left.Print()
		t.right.Print()
	}
}

B 树、B+ 树

B 树
B 树是多路平衡查找树

$m$ 阶 B 树

每个节点最多有 $m$ 棵子树（ $m-1$ 个关键字）
除根节点外非叶节点最少有 $\lceil \frac{m}{2} \rceil$ 棵子树
所有叶节点在同一层（平衡因子为 $0$ ），且不存储数据（用于查找失败节点）

也即，高度为 $h$ 的 $m$ 阶 B 树，节点至少为 $2\frac{\lceil \frac{m}{2} \rceil ^{h-1} - 1}{\lceil \frac{m}{2} \rceil - 1}$ ，最多为 $\frac{m^h-1}{m - 1}$

B 树是文件的存储结构，在 B 树中检索数据，就是在磁盘上检索数据，而最终的结果则对应一个节点，在内存中读取。因此，B 树的高度决定了磁盘读取次数。

插入: 找到最底层某个可插入的非叶节点，检查是否需要分裂，并向上递归更新
删除：找到数据所在的节点，删除对应的数据，检查是否需要触发合并，并向上递归更新

B+ 树

$m$ 阶 B+ 树

每个节点最多有 $m$ 棵子树
其他节点至少有 $\lceil \frac{m}{2} \rceil$ 个节点
节点子树个数与关键字个数相同

下面是一个 $3$ 阶的 B+ 树，每个节点中的索引为对应孩子中的最大值

                     (8 15)
                /               \
        (2 5 8)                 (11 15)
      /    |     \              /    \
(1 2) -> (3 5) -> (6 8) -> (9 11) -> (13 15)

插入时，从根节点开始比较，直到找到对应的叶节点。插入后检查是否超过限度，并递归更新最值并进行分裂操作。
分裂时只需要将节点一半的内容分到一个新节点

与其他结构相比，B+ 树有如下特点：

中间节点不存储数据本身，只存储一个索引指针，因此在相同的节点大小下，能够存储更多的索引，也即整个树会更低，磁盘 IO 更少
叶子节点的数据相连，因此可以进行范围查询

B 树和 B+ 树的区别

B 树数据存储在所有节点中；B+ 树存储在叶节点中
B 树阶数等于最大子树个数，比最大索引个数大 $1$ ；B+ 树阶数与最大索引数、最大子树个数相等
B+ 树叶子节点的实际存储数据相连接，可以实现范围检索

红黑树

红黑树是满足下列要求的二叉树：

节点为红色或黑色
根节点是黑色
叶子节点是黑色，且不存储数据
红色节点的两个子节点都是黑色
任一节点到其每个叶子的所有路径都有相同数目的黑色节点

红黑树与平衡二叉树是平行概念，思路上类似于 $3$ 阶 B 树，将所有的红色节点合并入其父节点（黑色），即可转换为一棵 2-3 树

所有新插入的节点都应该初始为红色
在插入的检索过程中，需要沿途检查是否存在“一个黑节点有两个红节点孩子”，如果存在则需要将他们变色，为新节点插入做准备

如果新节点的父节点是黑色，那么不需要变色和旋转
如果新插入的节点是根节点，其需要变成黑色
如果新节点的父节点是红色，和父节点的兄弟节点都是红色，那么需要将这两个节点标记为黑色，并把父节点的父节点标记为红色（递归向上进行这一操作）
如果新节点的父节点是红色，父节点的兄弟节点是黑色，则需要进行旋转。

数据库

MySQL

InnoDB vs MyISAM

InnoDB 是支持事务的acid特性的。

支持事务
支持外键。
支持行级锁（只有通过索引进行条件检索才会使用，否则锁全表）
不支持 FULLTEXT 全文索引

MyISAM

MySQL5.5版之前的默认数据库引擎，不支持事务处理
强调性能，每次查询具有原子性,其执行数度比 InnoDB 更快
只支持表级锁，用户在操作 MyISAM 表时，SELECT，UPDATE，DELETE，INSERT语句都会给表自动加锁，如果加锁以后的表满足INSERT并发的情况下，可以在表的尾部插入新的数据。
支持 FULLTEXT 全文索引

各种锁的解释:

表级锁: MySQL 中最基本的表策略，开销最小的策略，并发性低。表级锁通常是在 MySQL 服务器层实现的，所以虽然 InnoDB 实现了行级锁，但是在一些时候， MySQL 数据服务层还是会对 InnoDB 表加上表级锁。
开销小，加锁快；不会出现死锁；锁定粒度大，发生锁冲突的概率最高，并发度最低。
行级锁: 可以最大程度的支持并发处理，同时锁的开销比表级锁要大。目前 InnoDB 和其他的存储引擎中实现了行级锁，行级锁只在存储引擎中进行实现，而 MySQL 服务层并没有实现。
开销大，加锁慢；会出现死锁；锁定粒度最小，发生锁冲突的概率最低，并发度也最高。
行级锁基于索引，如果一条 SQL 语句用不到索引是不会使用行级锁的，会使用表级锁
间隙锁: 符合筛选条件，但没有对应记录的对应的数据叫做“间隙”(GAP)，对这些不存在的数据进行加锁，可以避免幻读

在下面场景中，需要使用表锁

全表更新: 事务需要更新大部分或全部数据，且表又比较大。若使用行锁，会导致事务执行效率低，从而可能造成其他事务长时间锁等待和更多的锁冲突。
多表查询: 事务涉及多个表，比较复杂的关联查询，很可能引起死锁，造成大量事务回滚。这种情况若能一次性锁定事务涉及的表，从而可以避免死锁、减少数据库因事务回滚带来的开销。

索引

主键索引: 特殊的唯一索引，不允许有空值。主键是一种唯一性索引，每个表只能有一个主键，在单表查询中，PRIMARY 主键索引与 UNIQUE 唯一索引的检索效率并没有多大的区别，但在关联查询中，PRIMARY 主键索引的检索速度要高于 UNIQUE 唯一索引。
普通索引: 最基本的索引，没有任何约束限制。
唯一索引: 和普通索引类似，但是具有唯一性约束。
复合索引: 复合索引指多个字段上创建的索引，使用复合索引时遵循最左前缀
全文索引: 全文索引只可以在 VARCHAR 或者 TEXT 类型的列上创建

在检索数据时，首先检索辅助索引获得数据记录主键，然后用主键到主索引中检索获得数据记录

聚簇索引并不是一种单独的索引类型，而是一种数据存储方式

MyISAM 的是非聚簇索引，主索引和辅助索引几乎没有区别，只是主索引中的 key 一定是唯一的。主键索引 B+ 树的节点存储了主键，辅助键索引 B+ 树存储了辅助键。表数据存储在独立的地方。由于索引树是独立的，通过辅助键检索无需访问主键的索引树
InnoDB 使用的是聚簇索引，将主键组织到一棵 B+ 树中，而行数据就储存在叶子节点上，若使用WHERE id=14这样的条件查找主键，则按照 B+ 树的检索算法即可查找到对应的叶节点，之后获得行数据。若对 name 列进行条件搜索，则需要两个步骤。首先在辅助索引 B+ 树中检索 name，到达其叶子节点获取对应的主键。第二步使用主键在主索引 B+ 树中再执行一次 B+ 树检索操作，最终到达叶子节点即可获取整行数据。

索引原则

最适合创建索引的列是出现在WHERE或ON子句中的列，或连接子句中的列而不是出现在SELECT关键字后的列。
对于字符串进行索引，应该制定一个前缀长度，可以节省大量的索引空间。
避免创建过多的索引，索引会额外占用磁盘空间，降低写操作效率。
联合索引最左前缀匹配原则
=和in可以乱序，会被数据库自动优化
尽量选择区分度高的列作为索引。值重复少
索引列不能参与计算，如FROM_UNIXTIME(create_time) = '2014-05-29'就不能使用到索引
LIKE查询，%不能在前
如果关键词or前面的条件中的列有索引，后面的没有，所有列的索引都不会被用到。
列类型是字符串，查询时一定要给值加引号，否则索引失效。

事务和隔离级别

数据库操作应该保证四个特征：

原子性: 所有操作要么全部成功，要么全部失败
一致性: 数据需要从一个正确的状态转到另一个正确的状态（满足约束）
隔离性: 事务的修改在结束前，对其他事务是不可兼得
持久性: 一旦成功提交，那么修改将会被永久存入数据库，即使是系统故障数据也不应该丢失

在并发操作下，数据库查询可能会发生下面的问题：

更新丢失: 两个事务同时修改同一个数据
脏读: 读到了正在修改的数据
不可重复读: 两次读取过程中，数据被修改，从而使得新读入的数据不满足程序逻辑
幻读: 两次读取过程中，插入或删除了数据，从而使得新读入的数据不满足程序逻辑

为解决不同情况下的问题，引入了如下几种隔离级别

第一级别 Read Uncommitted: 事务可以看到其他未提交的事务结果，会导致脏读，且性能并不好
第二级别 Read Committed: 可能会导致不可重复读，在交叉的事务可能会影响结果，大部分数据库的默认级别
第三级别 Repeatable Read: 确保同一事务多个实例并发读取数据结果一致，可能会导致幻读，MySQL 的默认级别
第四级别 Serializable: 通过对事务排序，强制实现不会冲突解决幻读问题（每个读操作都加上共享锁），性能较差

隔离级别	脏读	不可重复读	幻读	Oracle	SQL Server	MySQL
Read Uncommitted	可能	可能	可能	不支持	支持	支持
Read Committed	不可能	可能	可能	支持	支持	支持
Repeatable Read	不可能	不可能	可能	不支持	支持	支持
Serializable	不可能	不可能	不可能	支持	支持	支持

事务日志

事务日志类似于一个临时的修改缓冲区，将操作缓冲起来后再一次性写入数据库

在事务修改时，不将其持久化到数据库中，而是持久化到硬盘上的事务日志中
日志采用追加方式记录，因此写入很快。
事务日志会在后台持久化到硬盘的数据库中
在事务日志持久化到数据库过程中如果数据库崩溃，仍然可以通过事务日志恢复数据

where 和 having

WHERE针对的是被查询表的内容，HAVING针对的是聚合的结果

如下面对年龄进行聚合，WHERE语句必须在GROUP BY前，因此聚合后无法筛选年龄，但可以使用子查询来转换WHERE和HAVING

SELECT `age`, COUNT(`age`) FROM `test`.`people` WHERE `gender`=true
GROUP BY `age`
HAVING `age` = 15

为什么索引使用 B+ 树

（对比 B树、红黑树，like 查询、范围查询）

B+ 树是一种多路的平衡查找树，相对于二叉查找树、AVL、红黑树等二叉树，B+ 树节点可以容纳更多的数据，也拥有更多的子树。对于相同数量的数据，B+ 树会更低，也即查询次数更少。
在磁盘读写时，每一次查询都将是一次磁盘 IO，更低的树拥有更少的磁盘 IO

与 B 树相比，B+ 树节点并不存储实际的数据，因此每一个节点可以节省出更多的空间用于索引，提升 B+ 树的阶数。从而使得 B+ 树相对于 B 树更低。同时，B+ 树的数据集中在叶子节点，且相互连接，可以实现范围查找

MySQL 查询过程

客户端发送 SQL 语句到服务端
服务端检查是否存在缓存，如果存在直接返回
解析 SQL 语句
将解析结果送入预处理器
对查询进行优化
操作对应的存储引擎进行查询
返回结果

Redis

Redis 是一种缓存中间件，属于非关系型数据库（No-only SQL）的一种，数据存储在内存中，用来替代传统型数据库在极大流量下的性能问题⁵

其拥有如下特点:

数据存储在内存中，读写速度非常快
单进程单线程，采用 IO 多路复用实现并发
支持常见的多种数据类型
可以将数据持久化到磁盘中
支持主从复制、哨兵
可用作分布式锁
可作为消息中间件，支持发布订阅

数据类型

Redis 本身包含如下几种数据类型:

String: Redis 的基础类型，一个 key 对应一个 value，value 不仅可以是 string，也可以是数字。string 可以包含任何数据（包括二进制数据），最大可存储 512M
Hash: String 键值对集合，适合用于存储对象
List: 简单的 String 列表，按照插入顺序排序，并且可以左右插入或左右删除，取片段。通过双向链表实现
Set: String 的无序集合，通过哈希表实现
SortedSet: 有序的 String 集合
HyperLog
Geo
Pub/Sub
Redis Module
BloomFilter
RedisSearch
Redis-ML
雪崩: Redis 的数据包含一个过期时间，当到达过期时间时，数据会被销毁。如果短时间内大量的数据在同一时间过期，将会导致所有请求集中到数据库，导致崩溃。通常需要在预定过期时间的基础上，加上一个随机值
穿透: 如果 Redis 和数据库中都不存在某数据，而又不断有用户请求，导致数据库压力过大。可以在接口进行校验，避免无意义的查询。使用布隆过滤器，也可以快速判断 key 是否存在于数据库中
击穿: 如果某一个 key 请求量很大，当 Redis 过期后，所有请求将会由数据库承担，导致数据库崩溃。对于热点数据，，可以设置永不过期，或者对该数据的请求添加互斥锁

淘汰机制

volatile-lru: 从已设置过期时间的 KV 中对最近最少使用的数据进行淘汰
volitile-ttl: 从已设置过期时间的 KV 中对剩余时间短的数据淘汰
volatile-lfu: 从已设置过期时间的 KV 中对访问频率最少的数据进行淘汰
volitile-random: 从已设置过期的 KV 中随机选择数据淘汰
allkeys-lru: 从所有 KV 中队最近最少使用的数据进行淘汰
allkeys-lfu：从所有 KV 中对访问频率最少的数据进行淘汰
allkeys-random: 从所有 KV 中随机选择数据淘汰
noeviction: 不淘汰，如果超过内存限制，则返回错误

持久化

Redis 会周期性将数据写入磁盘，实现可持久化

RDB: 将内存数据存入 dump.rdb 文件，简单的定时备份，但可能丢失数据
AOF: 将所有对 Redis 服务器的操作存到文件，通过重放来恢复数据

主从复制

将单个 Redis 扩展为一个主 Redis 和多个从 Redis 可以分散请求的压力。在大部分情况下，读操作较多，写操作较少。由主节点负责处理写操作，而从节点负责读操作，可以有效提升性能。
为了保证数据一致性，主节点与从节点需要通过主从复制来进行同步

从节点在启动后，连接到主节点，由主节点将所有信息发送给从节点。后续过程中，主节点所有新的改动（写命令）都会被同步到从节点

哨兵

哨兵的的主要功能包括主节点存活检测、主从运行情况检测、自动故障转移、主从切换。
哨兵将会执行下面四种任务:

监控: 不间断检查主服务器和从服务器是否正常运行
通知: 当被检控的服务器出现问题，通过 API 发送通知
自动故障转移: 当主节点不能正常工作时，开始自动故障转移，将一个从节点升级为主节点
配置提供者: 客户端应用初始化连接到哨兵，从哨兵获取主节点信息

为什么 Redis 那么快

Redis 完全基于内存，绝大部分请求是纯粹的内存操作
数据结构简单，对数据的操作也简单
单线程不需要上下文切换及临界资源竞争，不需要考虑锁
通过多路复用的非阻塞 IO 来实现并发

Redis 和 Memcached

Redis 可以将数据持久化到硬盘，而 Memcached 不能
Memcached 只支持简单的 key-value
Redis 构建了自己的底层机制，减少性能消耗
Redis 值最大的达到 1G，而 Memcached 只有 1M

应用

云服务类别

Infrastructure as a service

基础设施服务，服务商提供基础资源，用户自己控制底层

Platform as a service

平台即服务，服务商提供环境，抽象操作系统和硬件细节

Software as a service

软件即服务，服务商提供现成的应用

Docker

如何设计一个第三方登录

目前比较官方使用的第三方登录标准为 OAuth2.0

第三方登录包含如下三方：

服务方
第三方应用
用户

用户拥有服务方的账户，并希望将自己账户的部分权限授予第三方用户。

如果用户直接把自己的账户密码交给第三方应用，显然会造成安全问题，最好的情况是：只给予第三方应用一个 Token，每次第三方应用通过 Token 去服务方请求自己需要的资源。同时用户可以随时声明 Token 失效，或修改该 Token 可访问的数据权限。

同时，为了避免用户同时将一个 Token 授权给多个第三方应用，在设计上必须对不同的第三方进行区分。因此需要预先为每个第三方应用分配 ID 和密钥。

故整个流程如下

第三方应用在服务方注册，获取密钥与 ID
用户希望为第三方应用授权
用户访问第三方应用授权页面，并被跳转至服务方登录页面（携带第三方应用 ID、跳回页面地址及其他有必要的信息）
用户登录成功后，被跳回第三方应用的处理页面（携带一个临时认证码及其他有必要的信息）
第三方应用接收到临时认证码后，使用自己的密钥、临时认证码在服务方获取真正的令牌
第三方应用可以通过令牌获取指定的用户权限，为用户提供服务

包括 QQ、Github 在内的很多第三方登录都是类似的原理。

计算机网络

TCP/IP 四层模型

数据链路层:
- 功能：实现了网络硬件与软件的转换，借助物理地址（MAC）来识别每一个不同的设备。
- 通信范围: 局域网设备间数据通信
网络层:
- 功能: 通过 IP 实现了跨局域网设备的通信，同时尽可能选取最优路径进行数据的传输，重点在于实现设备之间的拓扑连接
- 通信范围: 互联网、广域网
传输层:
- 功能: 通过端口号实现了指定应用间的通信，实现了超时重传等功能
- 通信范围: 某两个具体应用（严格来说，子进程之间可以共享端口）
- TCP: 通过滑动窗口、拥塞控制等方法实现了可靠有连接流式传输（传入的数据可以认为必然会被接收方原封不动地收到）
- UDP: 不可靠无连接流式传输，但相对更快
应用层:
- 功能: 基于上述内容，实现具体业务的实现，如文件传输、即时通信。

TCP 协议

TCP 协议对外提供了如下特点

可靠交付: 数据传输无差错，不丢失，不重复，有序
全双工: 读取数据和写入数据可以同时进行
流式传输: 数据在传输过程中可能会被拆解，需要在应用层进行重新解析
有连接: 通信双端会建立一个持续性的连接进行通信

TCP 头部

TCP 协议包首部共有 20字节，并有 4N 字节的可选字段。

2 字节源端口
2 字节目的端口
4 字节序号字段seq: 记录了当前传输负载第一个字节的序号（ $2^{32} = 4G$ ）
4 字节的确认号ack: 其含义为期望收到的下一个报文的序号
4 位的偏移长度: 标记了首部的长度，最大为 15，意味着首部长度为 60
6 位的保留字段置零
1 位紧急位URG: 报文存在紧急数据，尽快传送
1 位确认位ACK: 声明确认号生效，连接建立后应该永远为 1
1 位推送位PSH: 不需要等待缓冲区满，直接发送
1 位复位位RST: 连接出现差错，需要释放资源重新建立
1 位同步位SYN: 请求连接报文
1 位终止位FIN: 结束连接报文
2 字节窗口字段: 设置允许对方发送的数据量
2 字节校验和
2 字节紧急指针: 声明紧急数据的字节数
任意长度选项字段: 最初只包含最大报文长度
填充字段: 将首部填充为 4 的整数倍

三次握手与四次挥手

三次握手

客户端发起连接，发送报文SYN=1,seq=x
服务端收到请求后如果接收连接，则返回SYN=1,seq=y,ack=x+1
客户端确认收到连接，如果已有数据需要发送则发送seq=x+1,ack=y+1，并携带对应的数据；否则发送seq=x,ack=y+1

前两个数据包携带SYN字段，即使不携带数据，序号也需要加 1
由于第二步服务端就已经分配资源，因此如果有大量握手请求，会导致 SYN 泛洪攻击

四次挥手

某一方希望关闭连接，向对端发送释放报文段FIN=1,ACK=1,seq=u，并停止发送数据
对端接收到后发送确认ACK=1,seq=v,ack=u+1
发起方不再发送数据，对端可能还需要发送数据，TCP 处于半关闭状态
对端也没有需要发送的数据时，发送释放报文段FIN=1,ACK=1,seq=w,ack=u+1
发起方确认ACK=1,seq=u+1,ack=w+1。发送报文 2MSL 后，连接关闭（可能会存在确认报文发送失败，对端请求重传的情况）

与三次握手类似，FIN 即使不携带数据，序号也需要加 1
四次挥手顺序不定，只需要满足响应在对应的请求后即可

序号最大为 4G，但由于序号可以循环重复使用，每个报文实际存活时间有限（180 秒），因此除非带宽达到 180 秒传输 4G 的数据（22 M/s），否则 TCP 本身就可以做到不冲突。同时，TCP 头部的扩充字段可以通过设置时间戳来进一步避免冲突，因此即使超过 22 M/s 仍然可以正常使用 TCP⁶⁷

至于为什么要设计为 3 次和 4 次，要考虑的是如何确认通信建立。
如果将通信简单划分为可以通信和无法通信，那么实际上一个 TCP 连接有四种可能：

A 无法发送给 B，B 无法发送给 A
A 可以发送给 B，B 无法发送给 A
A 无法发送给 B，B 可以发送给 A
A 可以发送给 B，B 可以发送给 A

握手的任务就是让 A、B 双方都确认对方知道了双方都可以通信。

第一次握手，A 不知道对方有没有收到，因此 A 什么都不知道。B 收到了 A 的消息，因此他知道 A->B 是连通的
第二次握手，A 在收到 B 的消息时，知道了 A->B 连通（不然 B 不会返回消息），B->A 也连通（不然自己收不到）。但是 B 由于不知道 A 是否已经收到，因此他只知道 A->B 连通
第三次握手，B 收到 A 的确认，B 知道 B->A 也是连通的。双方都确认通信没有问题

四次挥手类似，需要确认：A 已经关闭，并且 B 也已经关闭

第一次挥手，A 发送关闭请求，B 知道 A 准备关闭
第二次挥手，B 发送确认，A 知道 B 已经知道自己准备关闭，因此 A 停止发送数据（但还要接收，因为 B 还未关闭）
第三次挥手，B 发送关闭请求，A 知道 B 也准备关闭（到这时，双方都已经确认对方准备关闭，因此除去最后的确认外，几乎已经完全关闭）
第四次挥手，A 发送确认，B 知道 A 已经知道自己准备关闭，此时 B 也可以正式关闭

原理上来说，三次握手其实应该和四次挥手一样，为四次握手。但是由于第二次握手不需要传输数据，因此 B 发送给 A 的确认以及 B 请求建立连接两条报文可以合并为一次。而关闭连接时期，由于另一方可能还需要发送数据，因此无法合并。

上面的举例是从结果来解释设计，3 次挥手实有更为具体的原因：避免序号错误（The principle reason for the three-way handshake is to prevent old duplicate connection initiations from causing confusion.）
如果只有两次，那么发送方没有取消建立连接的办法，如果发送方第一次发送后，又接着发起第二次（如发送方已超时），那么可能会导致发送方收到的响应实际上是第一次连接的响应。

一个三次握手后直接四次挥手的会话（数据包包含 IPv4 包，seq 除去前两个握手使用的是相对序号）

$ tcpdump -A -t -ns 0 -X -r a.pcap

reading from file a.pcap, link-type EN10MB (Ethernet), snapshot length 262144
IP 127.0.0.1.43402 > 127.0.0.1.6666: Flags [S], seq 916859721, win 65495, options [mss 65495,sackOK,TS val 2545404621 ecr 0,nop,wscale 7], length 0
        0x0000:  4500 003c 7b94 4000 4006 c125 7f00 0001  E..<{.@.@..%....
        0x0010:  7f00 0001 a98a 1a0a 36a6 2b49 0000 0000  ........6.+I....
        0x0020:  a002 ffd7 fe30 0000 0204 ffd7 0402 080a  .....0..........
        0x0030:  97b7 cacd 0000 0000 0103 0307            ............
IP 127.0.0.1.6666 > 127.0.0.1.43402: Flags [S.], seq 3047146258, ack 916859722, win 65483, options [mss 65495,sackOK,TS val 2545404622 ecr 2545404621,nop,wscale 7], length 0
        0x0000:  4500 003c 0000 4000 4006 3cba 7f00 0001  E..<..@.@.<.....
        0x0010:  7f00 0001 1a0a a98a b59f c312 36a6 2b4a  ............6.+J
        0x0020:  a012 ffcb fe30 0000 0204 ffd7 0402 080a  .....0..........
        0x0030:  97b7 cace 97b7 cacd 0103 0307            ............
IP 127.0.0.1.43402 > 127.0.0.1.6666: Flags [.], ack 1, win 512, options [nop,nop,TS val 2545404622 ecr 2545404622], length 0
        0x0000:  4500 0034 7b95 4000 4006 c12c 7f00 0001  E..4{.@.@..,....
        0x0010:  7f00 0001 a98a 1a0a 36a6 2b4a b59f c313  ........6.+J....
        0x0020:  8010 0200 fe28 0000 0101 080a 97b7 cace  .....(..........
        0x0030:  97b7 cace                                ....
IP 127.0.0.1.6666 > 127.0.0.1.43402: Flags [F.], seq 1, ack 1, win 512, options [nop,nop,TS val 2545404622 ecr 2545404622], length 0
        0x0000:  4500 0034 58e5 4000 4006 e3dc 7f00 0001  E..4X.@.@.......
        0x0010:  7f00 0001 1a0a a98a b59f c313 36a6 2b4a  ............6.+J
        0x0020:  8011 0200 fe28 0000 0101 080a 97b7 cace  .....(..........
        0x0030:  97b7 cace                                ....
IP 127.0.0.1.43402 > 127.0.0.1.6666: Flags [.], ack 2, win 512, options [nop,nop,TS val 2545404628 ecr 2545404622], length 0
        0x0000:  4500 0034 7b96 4000 4006 c12b 7f00 0001  E..4{.@.@..+....
        0x0010:  7f00 0001 a98a 1a0a 36a6 2b4a b59f c314  ........6.+J....
        0x0020:  8010 0200 fe28 0000 0101 080a 97b7 cad4  .....(..........
        0x0030:  97b7 cace                                ....
IP 127.0.0.1.43402 > 127.0.0.1.6666: Flags [F.], seq 1, ack 2, win 512, options [nop,nop,TS val 2545405622 ecr 2545404622], length 0
        0x0000:  4500 0034 7b97 4000 4006 c12a 7f00 0001  E..4{.@.@..*....
        0x0010:  7f00 0001 a98a 1a0a 36a6 2b4a b59f c314  ........6.+J....
        0x0020:  8011 0200 fe28 0000 0101 080a 97b7 ceb6  .....(..........
        0x0030:  97b7 cace                                ....
IP 127.0.0.1.6666 > 127.0.0.1.43402: Flags [.], ack 2, win 512, options [nop,nop,TS val 2545405622 ecr 2545405622], length 0
        0x0000:  4500 0034 0000 4000 4006 3cc2 7f00 0001  E..4..@.@.<.....
        0x0010:  7f00 0001 1a0a a98a b59f c314 36a6 2b4b  ............6.+K
        0x0020:  8010 0200 0ba4 0000 0101 080a 97b7 ceb6  ................
        0x0030:  97b7 ceb6

TCP 可靠传输

在传输时，由于网络波动问题，可能会发生数据错误或丢失，而为了解决他们引入的重传则可能会导致重复、失序。要实现可靠传输，需要能够解决上述问题。

TCP 底层的 IP 协议无法保证可靠传输，TCP 使用校验、序号、确认、重传机制实现可靠传输

序号和确认机制保证了传输的顺序，同时可以检测出重传、丢失；
校验可以发现传输错误，要求发送方重传
重传则是错误和丢失的解决方案

TCP 中重传包括两种：

超时重传: 每一个报文段都有一个计时器，如果不能在倒计时结束收到确认，则会重新传输。计时器的时间根据实际情况自适应。
$RTT_S=(1-\alpha) \times RTT_S + \alpha \times RTT, a \in (0,1]$ ，通常 $\alpha=0.125$
$RTT_D=(1-\beta)\times RTT_D + \beta \times |RTT_S-RTT|$ ，通常 $\beta=0.25$
计时器时间 $RTO=(1-\beta)\times RTT_D+4\times RTT_D$
冗余 ACK（快速 ACK）: 在收到比期望序号大的报文时，发送冗余 ACK，指明下一个期待的序号。如果发送方对同一个报文收到 3 个冗余 ACK 时，即可认为该报文丢失，进行快速重传

滑动窗口

由于传输本身存在时延，一问一答式的传输效率极低，更好的办法应该是同时发送很多组数据。
发送方和接收方各维护一个窗口（发送窗口和接收窗口）

发送窗口包含 4 部分

已发送成功的部分: 这部分数据是已经被接收方确认接受过
已发送但未确认的部分: 这部分数据已经发送，但暂时未收到确认
未发送但接收方可处理的部分: 这部分数据还未发送，但仍然在发送窗口范围内，将会继续发送
未发送且接收方不可处理的部分: 这部分数据在窗口外，暂时不需要发送

通过冗余 ACK 机制，可以对已接收到的一组数据同时返回确认

接收窗口包含 3 部分

已确认接收的部分
未接受但可接受的部分
不可接受的部分

当接收窗口接收到超出窗口范围的数据，将会被直接丢掉。而接收到数据，将会被标记为已接收成功。每次确认会将第一个未被确认的报文发送回去

发送窗口和滑动窗口并不是一成不变的，两者近似相等，但是由于网络问题以及机器处理速度，实际上可能会稍有变动。接收窗口通过首部的相应字段告知发送方，而发送窗口将根据对方的接收窗口以及网络拥塞窗口共同确认

当接收窗口为 0 时，表明接收窗口关闭，此时发送方会启动一个定时器，按时发送窗口探测报文，当接收方收到探测报文时，会返回当前的接收窗口大小。
如果不定时确认窗口大小，如果接收窗口发送调整窗口的报文丢失，则会造成死锁。

由于窗口对应的单位为字节，因此如果发送窗口很小，则会发送大量只有几个字节的报文，而 TCP 头部最少都有 20 字节，将会造成大量的浪费，因此往往当接收窗口小于 $min(\text{MSS}, \text{bufferSize}/2)$ 时，就会直接认为是 0

流量控制

TCP 提供基于滑动窗口协议的流量控制，实现了端到端的流量控制

通信过程中，接收方根据自己的接收缓存大小，动态调正发送方发送窗口大小，这被称为接收窗口rwnd

如果滑动窗口设置过小: 产生过多 ACK（累积确认机制本身可以减少 ACK）
如果滑动窗口设置过大: 发送数据过多导致路由拥塞，丢失分组

传输层和数据链路层的流量控制区别在于:

数据链路层解决的是两个相邻节点之间的流量控制，且窗口不能动态变化
传输层解决的是端到端用户之间的流量控制，且窗口可以动态变化

拥塞控制

拥塞控制可以防止数据过多地发送到网络中，避免路由器或连路过载。通信双方本身并不能了解到拥塞的细节，只能根据通信时延的增加来确认发生了拥塞。

发送方根据对当前网络的拥塞程度确定拥塞窗口cwnd
拥塞窗口的单位为最大报文段 MSS，该值如果过小，则网络利用率会较低；过大则会在网络层大量分片

实际的发送窗口取rwnd和cwnd的最小值

拥塞控制是全局性的过程，涉及所有相关主机和路由器
流量控制是端到端的控制，通过抑制发送端的速率来确保接收端有能力全部接收

TCP 的拥塞控制包含四部分:

慢开始: 拥塞窗口初始为 1，每收到一个确认，则加 1（加法增大）；从时间上看，每个单位时间都扩大一倍（指数增加， $2^n$ ）；增加存在上限ssthresh，当达到慢启动门限后，就会使用拥塞避免算法
拥塞避免: 没收到cwnd个 ACK，则加 1（线性增长，每个单位时间加 1）；当出现超时时（发生拥塞），则设置ssthresh=cwnd/2，cwnd=1
快重传: 连续收到 3 个冗余确认，直接重传丢失的包，不等待计时器
快恢复: 在快重传发生后，cwnd=ssthresh=cwnd/2，返回拥塞避免状态

TCP 和 UDP 区别

TCP: 有连接、可靠
UDP: 无连接、不可靠

UDP 协议

UDP 只在 IP 的基础上，进行了简单的封装，其通过校验和来确保能够被收到的数据一定未被修改（但存在压根收不到的可能，且校验可以选择关闭），在网络环境不好的情况下，数据存在丢失的可能性

由于 UDP 无连接，在 Go 中，UDP 和 TCP 通信的代码存在不同。TCP 程序在创建 Listener 后，用过 Accept() 来阻塞程序，等待连接建立，并返回一个会话连接。程序可以在新的 goroutine 中处理会话；而 UDP 只能建立一个 UDPConn，通过 ReadFromUDP() 获取数据以及对端地址，如果要发送数据，则需要写明需要发送给哪一个对端。如果存在连续的通信时，UDP 还需要手动维护会话关系。

HTTP 协议

HTTP 是一个基于 TCP/IP 的应用层协议，规定了服务端与客户端的通信格式，默认使用 80 端口

HTTP 协议是人类友好的协议，使用 ASCII 字符作为数据，通过换行来区分数据，并使用\r\n隔离头部和数据体

一个 HTTP 请求，需要先声明请求的类型（如GET、POST、PUT……）
接下来是要访问的资源路径，原本是指资源相对于wwwroot目录的路径，应该是一个具体的文件。但目前该部分往往被前端或后端路由接管，不在拘泥于格式，根据字符串匹配返回不同的结果
路径后则是 HTTP 的版本号

使用换行符来分割头部的其他信息（如User-Agent）

请求:

GET / HTTP/1.0
User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10_10_5)
Accept: */*

响应与请求类似，但版本号后增加了状态码和对应的解释
状态码可以告知 HTTP 处理的结果
第一行后，也是相应的头部数据，并使用空行分割实际的响应体

响应

HTTP/1.0 200 OK 
Content-Type: text/plain
Content-Length: 137582
Expires: Thu, 05 Dec 1997 16:00:00 GMT
Last-Modified: Wed, 5 August 1996 15:55:28 GMT
Server: Apache 0.84

<html>
  <body>Hello World</body>
</html>

状态码

状态码	解释
100 Continue	已接收到请求头，等待发送请求体
101 Switching Protocols	请求通过 Upgrade 字段声明使用基于 HTTP 的其他协议，服务端可以处理该协议，后续会话使用该协议
200 OK	请求成功
301 Moved Permanently	永久重定向到其他路径
302 Moved Temporarily	临时重定向到其他地址
400 Bad Request	客户端请求有问题
401 Unauthorized	需要进行用户身份认证
403 Forbidden	服务端已理解请求，但拒绝执行
404 Not Found	找不到对应的资源
405 Method Not Allowed	请求方法不被支持
418 I'm a teapot	彩蛋（RFC2324）
423 Locked	资源被锁定
451 Unavailable For Legal Reasons	由于法律原因，无法提供服务
500 Internal Server Error	服务端发生未知错误
501 Not Implemented	服务端不支持请求的功能
502 Bad Gateway	网关错误
503 Service Unavailable	服务端临时过载

请求方法

HTTP 本身已经规定了各种方法所代表的含义：

GET: 请求资源
POST: 发送数据（如通过表单）
PUT: 创建或替换资源
DELETE: 删除资源
HEAD: 只请求头部，不请求响应体
PATCH: 部分修改资源
OPTIONS: 获取资源的支持的通信类型

但由于各个方法实际处理方式完全取决于服务端程序，因此大多情况下并未完全按照规范执行。在大多数 RESTful API 中，为了与数据库增删改查保持一致性，采用下面的含义:

GET: 获取资源
PUT: 新建资源
POST: 修改资源
DELETE: 删除资源

除人为定义的语义外，大部分方法并没有特殊含义，完全取决于服务端实现。但为了兼容浏览器，大多会保持与原有语义类似的含义

前后端数据交互

在前后端交互中，数据的发送往往有三种方式:

直接附加到 URL 中，如/api/user?id=10001&name=OhYee
application/x-www-form-urlencoded: 使用表单形式提交，数据将会被放置在 Body 部分，如username=OhYee&password=12345

multipart/form-data: 使用格式化后的表单提交（通常用于上传文件），如

Content-Type:multipart/form-data; boundary=----WebKitFormBoundaryrGKCBY7qhFd3TrwA

 

------WebKitFormBoundaryrGKCBY7qhFd3TrwA

Content-Disposition: form-data; name="text"

 

title

------WebKitFormBoundaryrGKCBY7qhFd3TrwA

Content-Disposition: form-data; name="file"; filename="chrome.png"

Content-Type: image/png

 

PNG ... content of chrome.png ...

------WebKitFormBoundaryrGKCBY7qhFd3TrwA--
————————————————

application/json: 使用 json 格式传输，如{"name":"OhYee","password":"12345"}
text/xml: 使用 xml 格式传输
text/plain: 纯文本格式传输

需要注意的是，除去第一种外，其他的类型如何解析完全依赖于服务端程序。也即及时使用了text/plain，服务端仍然可以按照 json 解析。但通常为了兼容浏览器，需要按照规范实现。

另外，由于 URL 长度本身存在限制，最少的 IE 只有 2083，而广泛使用的 Chrome 也只有 8182。同时由于 URL 需要编码，会增加长度，同时会在浏览器中留下记录，因此除去分页等对用户有意义的功能，应该考虑是否需要使用其他形式传参

Cookie、LocalStorage

HTTP 是一个无状态的协议，在未升级至 WebSocket 时，只通过一个请求、一个响应进行数据交互。如果有多个用户请求同一个页面，服务端无法识别用户的身份。

因此需要采用某个机制来维持用户状态。如果不需要确保下次访问仍然保留状态，可以将信息存储在内存中，否则就需要将其持久化到硬盘中。而为了保证安全，往往页面并不能随心所欲访问系统磁盘，通常使用被限定开放的 Cookie 和 LocalStorage 进行存储⁸

Cookie 是一个大小在 4KB 的存储空间，可以用于保存登录信息，并且可以在设置失效时间后被浏览器自动清除，Cookie 在发送请求时会被添加到请求头部中，如果存入过多无意义的数据会影响性能
LocalStorage 则是在 HTML5 中新加入的技术，大小达到 5MB，如果不清除将会永久保存
SessionStorage 与 LocalStorage 类似，但其在页面关闭后会被清除

无论是存储在 Cookie 还是存储在 LocalStorage 实际上区别并不大，因为他们都是只有客户端可以访问，并且只允许同域名的脚本访问。唯一的区别只在 Cookie 会被添加到所有请求，且可以设置失效时间

跨域

为了确保安全，通常需要限定请求资源的权限。浏览器认为而不同是不同服务，当前的域名的会话不应该随意去访问其他域名的服务（因为可能会有恶意脚本故意访问钓鱼站点，从而导致 Cookie 泄露）

同一个域名要求协议、域名、端口完全相同，否则称为跨域
跨域请求需要进行相应的设置才会被浏览器允许，否则即使消息请求被正确发送，浏览器也不会进行后续操作。

跨域分为两种情况⁹:

简单跨域: 使用GET、POST、HTTP请求，且格式为text/plain、multipart/form-data、application/x-www-form-urlencoded。这些只需要在服务端允许接收其他域名的请求即可，如Access-Control-Allow-Origin: http://foo.example
预检请求: 除简单跨域外，其他的请求都需要提前发送一个OPTIONS请求，服务器需要返回是否允许该请求，而后才会发送正常的请求数据。因此除去上面的Access-Control-Allow-Origin: http://foo.example外，还需要配置Access-Control-Allow-Headers: Content-Type和"Access-Control-Allow-Methods: POST, GET, OPTIONS, DELETE。并且直接返回OPTIONS请求（有其他数据也不会被浏览器处理）
带身份凭据的请求: 如果需要携带 Cookie，则首先需要在前端的请求进行相应的配置withCredentials=true，而后响应中需要携带Access-Control-Allow-Credentials: true，同时Access-Control-Allow-Origin不能使用*，必须具体到域名。其他则按照前面的要求进行配置

下面是博客中使用的预检处理代码和 Python 中所有情况的代码

// CORS
context.AddHeader("Access-Control-Allow-Origin", "*")
context.AddHeader("Access-Control-Allow-Headers", "*")
context.AddHeader("Access-Control-Allow-Methods", "POST, GET, OPTIONS, DELETE")
if context.Request.Method == "OPTIONS" {
        context.Success()
        return
}

cors_origin = request.headers.get(
    "Origin", "*"
)

if request.method == "OPTIONS":
    return Response(
        "OPTIONS",
        mimetype="text/plain",
        content_type="text/plain",
        headers={
            "Access-Control-Allow-Origin": cors_origin,
            "Access-Control-Allow-Methods": "POST, GET, OPTIONS",
            "Access-Control-Allow-Headers": "access-control-allow-origin",
            "Access-Control-Allow-Credentials": "true",
            "Access-Control-Max-Age": "86400"
        }
    )
else:
    # 正常处理逻辑

    response.headers["Access-Control-Allow-Origin"] = cors_origin
    response.headers["Access-Control-Allow-Credentials"] = "true"
    return response

跨域往往在前后端分离系统中联调中存在，如果可以的话，可以使用 Nginx 反向代理来将前后端统一到一个域名下
当然在前端的服务端也可以做一个请求转发，因为跨域限制只在浏览器中存在

HTTP 复用

由于 HTTP 一问一答形式的浪费，可以使用 Keep-Alive 头部字段来实现复用 TCP 连接。通过配置对应的长度字段或是特定的 chunked 包来确定传输结束，断开连接。在 HTTP 1.1 中，默认使用 Keep-Alive。但在目前的状况下，其可能并不是一个较好的优化，一方面是其将会保留一段时间的连接，而对于简单的请求，可能并不会有后续的连接，浪费了系统资源；另一方面，Keep-Alive 请求仍然需要等待上一个请求处理完成后才能发送下一个。

为了解决上面的问题，HTTP 管线化允许一次发送多个请求，但为了响应的顺序，需要确保服务端的返回同样按照顺序，当一个响应被阻塞时，将会影响后续的响应。

造成上面问题的根本在于 HTTP 是基于文本的协议，需要一个明显的顺序来确保会话逻辑。在 HTTP 2 中，通过基于二进制的流式传输多路复用技术，实现了真正的 HTTP 复用，对于同一个域名，只需要建立一个 TCP 连接。

操作系统

Linux 文件系统

文件存储形式

文件存储在硬盘上，硬盘的最小存储单位是扇区(sector)，每个扇区包含 512 字节。在读取硬盘时，为了提升效率，一次需要读取多个扇区，因此将每次读取的扇区总体称为一个块(block)。文件实际上存储在块中。

为了识别每一个块的功能，记录文件信息，需要使用 inode 存储元数据（文件创建时间、文件大小、文件权限、链接数等）

每一个 inode 都有一个编号，操作系统使用 inode 来识别不同文件（文件名只是为了方便用户识别）。文件夹本身也是一个文件，文件夹存储的数据的就是文件夹内包含的文件。使用df -i可以看到系统 inode 分配情况，使用ls -i可以看到每个文件对应的文件号

对于由于文件夹本身是一个文件，因此写权限决定了能否向文件夹写入文件、读权限决定了能否获取文件夹文件列表、执行权限确定了能否进入文件夹内

如果是mv操作，如果源路径和目的路径在同一个文件系统内，只需要将对应 inode 元信息进行修改即可，不需要真正进行文件的移动

文件系统的第一个块被称作超级块，存储了文件系统的结构信息（每个区域的大小，未被分配的块信息）。超级块后为 inode 表，记录了所有 inode 的信息；最后就是实际的数据区域了。

使用stat可以查看一个文件 inode 信息，下面是一个文件的数据，可以看到其包含了文件

$ stat target
  File: target
  Size: 5               Blocks: 8          IO Block: 4096   regular file
Device: 800h/2048d      Inode: 28584       Links: 1
Access: (0644/-rw-r--r--)  Uid: ( 1000/   ohyee)   Gid: ( 1000/   ohyee)
Access: 2021-03-21 00:46:01.146972300 +0800
Modify: 2021-03-21 00:46:05.266972300 +0800
Change: 2021-03-21 00:46:05.266972300 +0800
 Birth: 2021-03-21 00:46:01.146972300 +0800

文件访问

进程要访问一个文件，需要经历如下步骤:

进程调用库函数向内核发起读文件请求
内核检查进程的文件描述符，定位到文件列表
系统调用read()
检索到文件 inode
根据 inode 找到文件对应的地址
访问文件页缓存树，查找对应的页缓存节点
- 如果命中页缓存，直接返回内容
- 如果页缓存缺失，则产生缺失异常，创建页缓存，并从磁盘地址读取对应内容

文件描述符

文件描述符（File Descriptor, FD）是文件的抽象化概念，形式上是一个非负整数，指向内核为每一个进程所维护的该进程打开文件的记录表。当程序打开或创建文件，内核会向进程返回一个文件描述符

缓存 IO

大多数文件系统的默认 IO 操作都是缓存 IO，操作系统会将 IO 数据缓存在文件系统的页缓存中。数据会从操作系统的内核缓冲区被拷贝入应用程序地址空间中。数据传输需要在用户空间和内核空间进行多次拷贝，消耗相对较大。

软链接和硬链接

使用ln -s可以建立软链接，其类似于 Windows 下的快捷方式，新建的文件内容存储了目标文件的相关信息，当对链接文件进行操作时，会被系统转移至目标文件。但对操作系统而言，这两个文件是不同的文件。删除一个文件不会影响另一个文件（如果目标文件被删除，访问链接文件会提示找不到文件）

使用ln可以建立硬链接，硬链接修改的是 inode 的信息，相当于一个文件拥有两个等价的身份，对于系统而言，两者就是一个文件，占用相同的磁盘空间。链接文件和目标文件是完全等价的，删除一个并不会影响另一个文件，当系统发现一个文件的引用计数为 0 时，才会真正从磁盘将其删除。

这里 target 文件是原始文件，target2 和 target3 分别是建立的硬链接和软链接

$ stat target
  File: target
  Size: 5               Blocks: 8          IO Block: 4096   regular file
Device: 800h/2048d      Inode: 28584       Links: 2
Access: (0644/-rw-r--r--)  Uid: ( 1000/   ohyee)   Gid: ( 1000/   ohyee)
Access: 2021-03-21 00:46:01.146972300 +0800
Modify: 2021-03-21 00:46:05.266972300 +0800
Change: 2021-03-21 00:47:59.646972300 +0800
 Birth: 2021-03-21 00:46:01.146972300 +0800
$ stat target2
  File: target2
  Size: 5               Blocks: 8          IO Block: 4096   regular file
Device: 800h/2048d      Inode: 28584       Links: 2
Access: (0644/-rw-r--r--)  Uid: ( 1000/   ohyee)   Gid: ( 1000/   ohyee)
Access: 2021-03-21 00:46:01.146972300 +0800
Modify: 2021-03-21 00:46:05.266972300 +0800
Change: 2021-03-21 00:47:59.646972300 +0800
 Birth: 2021-03-21 00:46:01.146972300 +0800
$ stat target3
  File: target3 -> target
  Size: 6               Blocks: 0          IO Block: 4096   symbolic link
Device: 800h/2048d      Inode: 59481       Links: 1
Access: (0777/lrwxrwxrwx)  Uid: ( 1000/   ohyee)   Gid: ( 1000/   ohyee)
Access: 2021-03-21 00:48:05.386972300 +0800
Modify: 2021-03-21 00:48:05.386972300 +0800
Change: 2021-03-21 00:48:05.386972300 +0800
 Birth: 2021-03-21 00:48:05.386972300 +0800

内存管理

虚拟内存

以单片机为例，CPU 是直接操作内存的 物理地址 的，而很显然，这时 不安全 的。如果程序 A 在 0x2000 写入一个数据后，有另一个程序 B 也想往这里写入数据，就会覆盖掉程序 A 数据。要隔离开各个程序的内存，可以采用 虚拟地址 来进行内存的分配¹⁰。

对于每一个程序本身，其只需要对一个虚拟内存进行操作，由系统将其映射到对应的物理地址上，来避免冲突。

虚拟地址和物理地址之间的管理，有分段和分页两种方式。

内存分段

内存可以通过分段来实现寻址，在 8086 CPU 中，寄存器为 16 位，而内存总线为 20 位。通过段基址和偏移地址，即可实现通过 16 位寄存器寻址 20 位的内存空间。

同时这种段基址和偏移地址的分段方式，也可以用于保护内存空间。由于程序本身采用偏移地址寻址，因此操作系统只需要对偏移地址范围进行判断即可简单地确保程序不会访问其不该访问的内存。

分段存在如下的问题:

内存碎片: 内存分配给程序时，会分配一个段基址和一个段界限，相当于将 $[\text{段基址}, \text{段基址}+\text{段界限}]$ 范围分配给一个程序，当一个程序结束释放内存后，未使用的内存会被间隔开，难以充分分配；
内存交换效率低: 为了解决内存碎片，需要对内存进行重整，将使用中的内存存入 Swap 区域，而后移回内存，使所有未分配内存集中到一起。但 Swap 交换涉及硬盘读写，易产生性能瓶颈

内存分页

将内存划分为更小的段——页，给一个程序分配多个页，来解决分段产生的问题。在 Linux 下，页大小为 $4KB$ 。与分段类似，分页通过页号和 页内偏移 来实现访问。

内存的整理在分页管理中是通过换出 (Swap Out) 和换入 (Swap In)，实现的，每次会将运行中程序暂时未被使用的内存换出到 Swap，使用时再读回。由于每次只有少数几个页被交换，因此效率相对较高。

虚拟地址和物理地址之间的映射使用页表实现，其存储在 CPU 内存管理单元（MMU）中，当无法找到对应的页时，会触发缺页异常，需要进入系统内核空间分配物理内存，更新进程页表，而后返回用户空间，恢复进程运行。以 32 位系统为例，内存大小为 $4GB$ ，如果一个页大小为 $4KB$ ，需要 100 万个页，每个页表项需要 4 个字节大小来存储，共需要消耗 $4MB$ 内存来存储页表。如果有 100 个进程的话，就需要 $400MB$ 内存来存储页表，消耗大量的资源。

要解决页表的浪费，可以采用 多级页表。将页表（一级页表）分成 $1024$ 个页表（二级页表），每个二级页表包含 $1024$ 个页表项。由于内存分配给程序时，页表是需要映射完整的内存大小的，但是实际上绝大部分程序并不需要使用这么多内存。因此采用多级页表只需要分配真正被映射的页表即可。在 64 位系统中，需要使用四级分页。

由于多级页表增加了内存映射的速度，因此需要将常用的页表存入访问速度更快的硬件，也即位于 CPU 中的 Cache —— TLB（页表缓存）

页拥有以下几种类别

文件页: 内存缓冲，可以随时回收
脏页: 已经修改，但未写入磁盘的数据，只有成功写入后才可释放。写入磁盘有两种途径
- 系统调用fsync
- 系统内核pdflush
匿名页: 应用程序动态分配的堆内存，可能会被访问，不能直接释放
Swap: 不常访问的内存可被写入磁盘，而后释放掉内存，当需要读取时再从磁盘读入

段页式内存管理

先把程序划分成多个有逻辑意义的段，段内划分成页，形成段号—页号—页偏移的三层结构

由于 Intel CPU 的遗留问题，操作系统必须实现段页式内存式管理，而 Linux 将所有的段都映射到整个内存地址，从而“屏蔽”了分段管理。

页面置换算法

如果需要访问的页不在内存中时，需要将其调入内存，当内存无空闲空间时，需要从内存调出暂不使用的页送入 Swap。这种选择算法就是页面置换算法¹¹

最佳置换(OPT): 被淘汰的页面是以后用不实用的或是最长时间不被访问的，这样可以保证最低的缺页率，无法实现，但可以作为理论到评判标准
先进先出(FIFO): 优先淘汰最先进入内存的页面
最久未使用(LRU): 最长未被使用的内存将被淘汰，堆栈类算法，性能好但需要硬件支持且难以实现，消耗较大
时钟(CLOCK): 附加一个位，初始为 1，每次被访问都会重置为 1。每次淘汰为 0 的页面，并将查找过程中所有的的 1 置为 0（下次销毁）

内核态和用户态

应用程序依托于库函数和 Shell 来进行系统调用，通过系统调用来控制内核进行操作¹²。

内核是一种特殊的程序，其控制着计算机的硬件资源，如协调 CPU、分配内存……

用户态 是供应用程序运行的空间，为了使程序可以访问内核管理的资源，需要通过系统调用来调用内核程序

系统调用 是操作系统最小的功能单位，大致有 240~350 个

库函数 是屏蔽底层系统调用细节的模块，将复杂的系统调用封装成简单的函数供应用程序调用，如 glibc

Shell 是包裹内核的外壳，是一种特殊的应用程序，方便用户和内核之间进行对话

从内核态切换到用户态，有三种形式:

系统调用: 本质上是软件中断
异常: 当用户态进程发生异常时，将会切换到内核态处理，如缺页异常
外设中断: 当外设完成请求时，通过中断信号通知 CPU

为什么要划分内核态和用户态

本质上内核态和用户态的划分是为了更好的权限管理，如果将硬件操作权限随意地分配给应用程序，而不做统一的管理，很容易由于应用程序质量导致各种问题。

为什么系统调用消耗很大

系统调用将导致内核态和用户态的切换，而切换需要保存 CPU 上下文信息，相当于对所有资源进行了一次切换，因此消耗相对较大。同时不同的系统调用由于在内核态进行的操作不同，因此消耗的时间也不相同。如果只是单纯的内核态和用户态切换，本身消耗是可以接受的。

中断

中断分为同步中断和异步中断，当一个中断到达时，CPU必须停止正在进行的任务，保留上下文切换到中断处理的程序

同步中断指的是当指令执行时由CPU控制单元产生的，之所以称为同步，是因为只有在一条指令终止执行后CPU才会发出中断。
异步中断是由其他硬件设备依照CPU时钟信号随机产生的。

中断处理的流程如下:

中断请求: 中断请求的发生是随机的，CPU 每条指令的最后一个周期会检查 INTR 引脚
中断响应: 一旦发现存在中断且未被屏蔽，CPU 发送 $\overline{INTR}$ 信号，保护断点，转向中断服务程序
中断返回: 中断服务执行瓦尼，CPU 返回原程序执行位置，继续执行原来的程序

进程与并发

进程、线程和协程

进程是资源分配的最小单位，同一时间内执行的进程不会超过 CPU 核心数目。每个进程都已独一无二的 PID，很多资源（如打开的文件、分配的内存）都无法在不同进程中共享（fork 出的子进程除外）

如果并发执行多个进程，每次切换上下文都需要有非常大的开销（需要重新加载对应进程的内存等资源），因此引入了线程的概念。

线程依赖于进程，是任务执行的最小单元。一个程序可能需要同时执行多个任务，那么每个任务可以被分配给多个线程进行并发执行。线程之间属于统一进程，因此资源可以共享，但如果多个线程同时访问同一个资源可能会导致冲突，因此需要通过加锁避免。
由于线程内部切换只需要修改线程本身的上下文即可，不需要变动整个进程的上下文，因此线程切换开销低于进程。

协程是用户态的轻量级线程，其开销相对于线程更小。线程的切换仍然和系统密不可分，而协程则完全位于程序内部，由程序自己控制，操作系统并不需要关心。因此协程切换开销更加小，用户只需要控制好部分临界资源即可。

进程是资源分配的最小单位，线程是任务执行的最小单位。
进程有自己的独立地址空间，每启动一个进程，系统就会为它分配地址空间，建立数据表来维护代码段、堆栈段和数据段，这种操作非常昂贵。而线程是共享进程中的数据的，使用相同的地址空间，因此 CPU 切换一个线程的花费远比进程要小很多，同时创建一个线程的开销也比进程要小很多。
线程之间的通信更方便，同一进程下的线程共享全局变量、静态变量等数据，而进程之间的通信需要以通信的方式（IPC)进行。不过如何处理好同步与互斥是编写多线程程序的难点。
但是多进程程序更健壮，多线程程序只要有一个线程死掉，整个进程也死掉了，而一个进程死掉并不会对另外一个进程造成影响，因为进程有自己独立的地址空间。

进程和线程在 Linux 底层数据结构相同，主要区别在于线程之间可以共享内存、文件，而进程之间则是隔离的。
而协程与线程相比，线程的切换需要进行 系统调用，协程则不需要。

进程调度

进程调度有如下方法:

先来先去服务
时间片轮转法: 每个进程分配一个时间段，程序在时间片内运行，到达时间后让出 CPU
短作业优先
多级反馈队列调度算法: 进程分为多个优先级，队列内部根据先进先出分配时间段，新进程优先进入高优先级，若一个时间片内未完成则移入次一级队列，直至进入最低优先级队列，进行时间片轮转
优先级调度

进程切换

保存处理机上下文，包括程序计数器和其他寄存器
更新 PCB 信息
将进程 PCB 移入相应队列（就绪、阻塞……）
选择另一个进程执行，并更新 PCB
更新内存管理的数据结构
恢复处理机上下文

僵尸进程

父进程通过 fork() 建立子进程后，如果子进程通过 exit() 结束后，其并未被真正的销毁，而是会在进程表中残留一个状态，待父进程处理。

如果父进程可以使用 wait() 或 waitpid() 来接收并释放子进程；也可以在父进程退出后，由 init 接收子进程并释放。
如果父进程没有退出，而是以一个服务存在，那么子进程将不会被回收，尽管并不占用额外的资源，只是占用一个进程号，但是当数量太多时，仍然可能造成问题。

避免僵尸进程有三个思路:

创建子进程时，使用 singnal(SIGCHLE, SIG_IGN) 告诉系统自己不会再子进程结束后进行处理
创建子进程后，使用 wait() 和 waitpid() 等待子进程结束并释放
创建子进程时，调用两次 fork()，并使得子进程直接退出，从而将孙进程移交给 init 管理

并发和并行

并发: 在操作系统中，某一时间段，几个程序在同一个 CPU 上运行，但在任意一个时间点上，只有一个程序在 CPU 上运行。
并行: 当操作系统有多个 CPU 时，一个 CPU 处理 A 线程，另一个 CPU 处理 B 线程，两个线程互相不抢占 CPU 资源，可以同时进行，这种方式成为并行。

并发是伪装的并行，只是在宏观上看，并发和并行类似，但实际上并发仍然只能执行一个任务

信号量

信号量是一种计数器，每一个需要访问临界区资源的线程需要将信号量减一（P 操作）。
如果信号量已经是 0 了，那么这个线程将会被阻塞直至信号量不为 1。
成功执行 P 操作的线程将获得访问临界区资源的权限。

当临界区资源访问结束，使用 V 操作将信号量加 1（如果有正在被阻塞的线程，则直接将其给对应的线程）

信号量用于线程的同步，可以允许多于一个线程访问临界区资源，同时 P、V 操作未限制由同一个主体触发（执行 P 操作的线程可能不会执行 V 操作，而是由别的线程执行 V）

互斥锁用于线程之间互斥，只能同时对一个线程放行，加锁和释放必须由同一个线程进行

乐观锁与悲观锁

乐观锁：操作数据时认为别人不会修改数据，只有在执行更新时判断是否有其他人在修改数据（判断及更新需要是一个原子操作）
悲观锁：认为别人时时刻刻都可能在修改数据，每次操作都对数据加锁

在数据库中乐观锁形式类似于

UPDATE TABLE SET `value`=2,`version`=`version`+1 WHERE `id`=2021 AND `version`=5

下面分别用 Go 实现了乐观锁和悲观锁以及无脑修改，可以看出前两者都可以保证数据正确，而无脑修改会导致结果不足 10000

package main

import (
	"fmt"
	"sync"
	"sync/atomic"
	"time"
)

func OptimisticLock(memory *int32) {
	for {
		temp := *memory
		res := temp + 1
		if atomic.CompareAndSwapInt32(
			memory,
			temp,
			res,
		) {
			break
		}
	}
}

func PessimisticLock(memory *int32, lock *sync.Mutex) {
	lock.Lock()
	defer lock.Unlock()
	temp := *memory
	*memory = temp + 1
}

func JustDoIt(memory *int32) {
	temp := *memory
	*memory = temp + 1
}

func main() {
	var value1 int32
	var value2 int32
	var value3 int32
	lock := new(sync.Mutex)
	for i := 0; i < 10000; i++ {
		go OptimisticLock(&value1)
		go PessimisticLock(&value2, lock)
		go JustDoIt(&value3)
	}
	time.Sleep(time.Second * 5)
	fmt.Println(value1, value2, value3) // 10000 10000 9828
}

死锁

当并发任务需要访问临界区资源时，往往需要加锁，如果 A 和 B 两个任务分别获取了资源 a 和 b 的锁，同时他们希望获取另一个资源的锁，由于他们都在等待对方释放资源，就会导致死锁问题

导致死锁有 4 个条件:

互斥条件: 一个资源只能被一个线程使用
请求和保持条件: 一个线程因请求资源而被阻塞
不剥夺条件: 线程已获得的资源，在未释放前不能强行剥夺
循环等待条件: 若干线程之间形成一种头尾相接的循环等待关系

要解决死锁，只需要破坏任意一个条件即可。如当我们发现 A 获取 a、b 资源并不是要写入数据，只是希望读取数据，那么针对 a、b 资源，可以使用读写锁而非互斥锁。
如果 A 获取 a 资源后并不需要在下一步就进行操作，可以将 a 的值存入一个临时变量，而后释放锁，等到下次需要操作 a 时再次申请锁

IO 模型

阻塞 IO: 阻塞后不消耗 CPU 资源，每个 IO 需要一个单独的进程、线程
非阻塞 IO: 轮询检查，消耗 CPU 资源
IO 复用: 将 IO 注册到复用器（select、poll、epoll）来监听 IO
信号驱动 IO: 发生 IO 操作后，向内核注册信号处理函数，进程本身不阻塞，当 IO 完成后，进程在信号处理函数处理 IO（回调形式，回调本身是阻塞的）
异步 IO: IO 操作结束（包括拷贝到用户区）后，通知进程，由进程自己进行处理（唯一不阻塞的模型）

IO 复用

select
能监听的资源有限（通常是 1024），采用轮询来遍历文件描述符，资源越多，性能越差
内核/用户空间拷贝需要复制大量的文件句柄，产生大量开销
通过水平方式触发
poll
通过链表保存描述符，没有监控数量的限制，但仍然有大量的拷贝开销，并且轮询遍历，水平触发
epoll
不需要轮询: 采用回调机制处理，只会检查活跃的连接
- 需要拷贝的资源少: 通过申请一个文件系统作为存储，通过mmap减少开销，使用链表维护一个就绪队列，只有就绪队列内的文件需要处理；内核态和用户态共享内存
- 同时支持水平触发和边缘触发

面经

阿里函数计算一面

什么时候开学
介绍下开源项目
WASM
函数式编程
RTMP
Go 操作 Linux 文件
唯一一个简历没有的问题，然而不会

二叉树之字遍历（代码）
LeetCode 103，是上个月的每日一题，不过当时 python 写的，所以一开始还是有点懵（Go 没 queue，性能会不会很差），不过还是硬用 slice 实现了，后面又替换成链表实现的 queue，顺手补了个单例测试（在线的编辑器真垃圾，缩进完全随缘）

// queue.go
   
package tree
   
import "fmt"
   
type LinkedNode struct {
    Value *Node
    Next  *LinkedNode
}
   
type Queue struct {
    head *LinkedNode
    tail *LinkedNode
}
   
func (q *Queue) Push(value *Node) {
    newNode := &LinkedNode{
        Value: value,
    }
    if q.head == nil {
        q.head = newNode
        q.tail = q.head
    } else {
        q.tail.Next = newNode
        q.tail = newNode
    }
}
   
func (q *Queue) Pop() (value *Node, err error) {
    if q.head == nil {
        fmt.Errorf("Empty Queue!")
        return
    }
    value = q.head.Value
    if q.head == q.tail {
        q.tail = nil
    }
    q.head = q.head.Next
    return
}
   
func (q *Queue) Empty() bool {
    return q.head == nil
}
   
// -----------------------------------------------
package tree
   
import "fmt"
   
// Node 二叉树
type Node struct {
    Left  *Node
    Right *Node
    Value string
}
   
// zbfs 之字形层序遍历
func zbfs(root *Node) [][]string {
    if root == nil {
        return [][]string{}
}
   
    // q := make([][]*Node, 2)
    // q[0] = make([]*Node, 0) // 当前层
    // q[1] = make([]*Node, 0) // 下一层
   
    q := make([]*Queue, 2)
    q[0] = new(Queue)
    q[1] = new(Queue)
   
    layer := 0
    res := make([][]string, 0)
    res = append(res, make([]string, 0))
   
    // q[0] = append(q[0], root)
    q[0].Push(root)
   
    // for len(q[0]) > 0 {
    //for len(q[0]) > 0 {
    for !q[0].Empty() {
        for !q[0].Empty() {
            // 取队首
            // t := q[0][0]
            // q[0] = q[0][1:]
            // if t == nil {
            // 	continue
            // }
            t, _ := q[0].Pop()
            if t == nil {
                continue
        }
   
        res[layer] = append(res[layer], t.Value)
   
            if t.Left != nil {
                // q[1] = append(q[1], t.Left)
                q[1].Push(t.Left)
            }
            if t.Right != nil {
                // q[1] = append(q[1], t.Right)
                q[1].Push(t.Right)
            }
        }
        q[0], q[1] = q[1], q[0]
        layer++
        res = append(res, make([]string, 0))
    }
    res = res[:layer]
       
    for idx, l := range res {
        if idx&1 == 1 {
            // 奇数行 逆序
            ll := len(l)
            for i := len(l) - 1; i >= 0; i-- {
                fmt.Printf("%s ", l[i])
                if i < ll/2 {
                    res[idx][i], res[idx][ll-i-1] = res[idx][ll-i-1], res[idx][i]
                }
            }
        } else {
            // 偶数行 顺序
            for i := 0; i < len(l); i++ {
                fmt.Printf("%s ", l[i])
            }
        }
        fmt.Printf("\n")
    }
    return res
}
       
// --------------------------------------------------------------------------
   
// tree_test.go
package tree
   
import (
    "reflect"
    "testing"
)
   
func Test_zbfs(t *testing.T) {
   
    root := &Node{
        Left: &Node{
            Left: &Node{
                Left: &Node{
                    Left:  nil,
                    Right: nil,
                    Value: "h",
                },
                Right: &Node{
                    Left:  nil,
                    Right: nil,
                    Value: "i",
                },
                Value: "d",
            },
            Right: &Node{
                Left: &Node{
                    Left:  nil,
                    Right: nil,
                    Value: "j",
                },
                Right: &Node{
                    Left:  nil,
                    Right: nil,
                    Value: "k",
                },
                Value: "e",
            },
            Value: "b",
        },
        Right: &Node{
            Left: &Node{
                Left: &Node{
                    Left:  nil,
                    Right: nil,
                    Value: "l",
                },
                Right: &Node{
                    Left:  nil,
                    Right: nil,
                    Value: "m",
                },
                Value: "f",
            },
            Right: &Node{
                Left: &Node{
                    Left:  nil,
                    Right: nil,
                    Value: "n",
                },
                Right: &Node{
                    Left:  nil,
                    Right: nil,
                    Value: "o",
                },
                Value: "g",
            },
            Value: "c",
        },
        Value: "a",
    }
   
    type args struct {
        root *Node
    }
    tests := []struct {
        name string
        args args
        want [][]string
    }{
        {
            name: "testcase 1",
            args: args{
                root: root,
            },
            want: [][]string{
                {"a"},
                {"c", "b"},
                {"d", "e", "f", "g"},
                {"o", "n", "m", "l", "k", "j", "i", "h"},
            },
        },
        {
            name: "testcase 2",
            args: args{
                root: nil,
            },
            want: [][]string{},
        },
    }
    for _, tt := range tests {
        t.Run(tt.name, func(t *testing.T) {
            if got := zbfs(tt.args.root); !reflect.DeepEqual(got, tt.want) {
                t.Errorf("got %#v want %#v", got, tt.want)
            }
        })
    }
}

阿里函数计算二面

之前写过的推荐算法细节
讲一个 Debug 的经历
Go 有没有什么印象深刻的坑
并发编程中，生产者消费者模型如何实现（底层原语）
讲一下信号量

算法题: 给一个特殊的数组：除去一个数只出现一次外，别的数都成组出现（每一组相邻），如何在最低时间复杂度内找到这个特殊的数

// 1 3 3 2 2
// 3 3 5 5 1 2 2

package main

import (
    "fmt"
)

// search 查找 arr 数组中 [l, r) 范围内唯一一个不成对出现的数
func search(arr []int, l, r int) (a int) {
    mid := (r-l)/2 + l

    // fmt.Println(l, r, mid)

    if r-l <= 1 || (arr[mid] != arr[mid+1] && arr[mid] != arr[mid-1]) {
        // 当前数就是不成对的数
        return mid
    }

    if mid % 2 == 1 {
        // 左侧有奇数个数
        if arr[mid] == arr[mid-1] {
            // 左侧成组，找右侧
            return search(arr, mid+1, r)
        } else {
            // 左侧不成组，找左侧
            return search(arr, l, mid)
        }
    } else {
        // 左侧有偶数个
        if arr[mid] == arr[mid+1] {
            // 左侧成组，且当前也成组，找右侧
            return search(arr, mid+1, r)
        } else {
            // 当前数所在的组之前不成组，找左侧
            return search(arr, l, mid)
        }
    }
}
   
type testcase struct {
        input  []int
        output int
    }
       
func main() {
    testcases := []testcase{
        {
            input:  []int{1, 3, 3, 2, 2},
            output: 0,
        },
        {
            input:  []int{3, 3, 5, 5, 1, 2, 2},
            output: 4,
        },
        {
            input:  []int{1, 3, 3, 5, 5, 2, 2},
            output: 0,
        },
        {
            input:  []int{1, 1, 3, 4, 4, 5, 5},
            output: 2,
        },
        {
            input:  []int{1, 1, 4, 4, 3, 5, 5},
            output: 4,
        },
        {
            input:  []int{1, 1, 4, 4, 5, 5, 3},
            output: 6,
        },
    }
   
allpass := true
    for _, t := range testcases {
        if got := search(t.input, 0, len(t.input)); got != t.output {
            fmt.Printf("Error at %+v, want %d, got %d\n", t.input, t.output, got)
            allpass = false
        }
    }
    if allpass {
        fmt.Println("All testcases passed")
    }
}

阿里函数计算三面

自我介绍
讲一下博客系统，从头自己写的？
对自己提高最大的项目
难度最大的项目
要实现一个后台程序，如果已经启动过，则不在启动新的（单例运行），应该如何实现？
如何寻找系统中 CPU 消耗最高的程序，并分析原因
分布式系统中，如何给上百万个服务器中的大量程序中，分配全局唯一的 ID
有了解过要投的部门么
实习时间

字节电商一面

为什么用go
简单介绍下自己的项目
tcp建立连接和断开连接
为什么最后一个断开需要2msl
goroutine 实现
线程和协程区别（实现上），各自的优缺点（从原理解释）

mysql：查询各科目前3名

SELECT `c1`.`科目` AS '科目', `c1`.`姓名` AS '姓名', `c1`.`成绩` AS '成绩'
FROM `成绩表` AS `c1`
WHERE 3 > (
    SELECT COUNT(DISTINCT `c2`.`成绩`) 
    FROM `成绩表` AS `c2`
    WHERE `c2`.`成绩` > `c1`.`成绩` AND `c1`.`科目` = `c2`.`科目`
)
ORDER BY `科目`, `成绩` desc;

SELECT `c1`.* FROM `成绩表` AS `c1`
LEFT JOIN `成绩表` AS `c2`
ON `c1`.`成绩` < `c2`.`成绩` AND `c1`.`科目` = `c2`.`科目`
GROUP BY `c1`.`科目`, `c1`.`成绩`, `c1`.`姓名`
HAVING COUNT(`c2`.`成绩`) < 3
ORDER BY `c1`.`科目`, `c1`.`成绩` DESC;

链表反转 (LeetCode 25.K 个一组翻转链表)

package main

import (
    "fmt"
)

type List struct {
    Val     int
    Next     *List
}

func Dubug(head *List) {
    for head != nil {
        fmt.Printf("%d -> ", head.Val)
        head = head.Next
    }
    fmt.Println()
}

func Reverse(head *List, k int) (newHead *List, tail *List)  {
       
    cur := head.Next
    newHead = head
    for i:=1; i<k; i++ {
        if cur == nil {
            break
        }
           
        head.Next = cur.Next
        cur.Next = newHead
        newHead = cur
           
        cur = head.Next
    }
    tail = head
       
       
    // Dubug(newHead)
    return 
}

func ReverseList(head *List, k int) *List {
    cur := head
    var tail *List = nil
    var newHead *List = nil
    for cur != nil {
        nh, nt := Reverse(cur, k)
           
        if newHead == nil {
            // 第一次
            newHead = nh
            tail = nt
        } else {
            tail.Next = nh
            tail = nt
        }
        cur = tail.Next
    }
    return newHead
}

func main() {
    lst := &List{
        Val: 1,
        Next: &List{
            Val: 2,
            Next:&List{
                Val: 3,
                Next: &List{
                    Val: 4,
                    Next:&List{
                        Val: 5,
                        Next: nil,
                    },
                },
            },
        },
    }

       
    lst = ReverseList(lst, 3)
    p := lst
    for p != nil {
        fmt.Println(p.Val)
        p = p.Next
    }
}

字节电商二面

MySQL 分页查询，写查询语句
MySQL 索引原则（最左优先）
MySQL 查询过程
Redis 了解过么（没）
epoll 为什么比 select 和 poll 更高效
水平触发和边缘触发

算法题，二维矩阵求路径上的最大值，并输出路径

package main

import (
    "fmt"
)

func main() {
    m := 4
    n := 5
    mp := [][]int {
        {1,3,7,2,12},
        {3,2,10,30,5},
        {4,9,2,1,2},
        {5,8,5,9,3}, 
    }
       
       
    // -----
       
    dp := make([][]int, m)
    pre := make([][]bool, m)  // 0 上 1 左
   

    for i:=0; i<m; i++ {
        dp[i] = make([]int, n)
        pre[i] = make([]bool, n)
    }
       
    for i:=0;i<m;i++{
        for j:=0;j<n;j++{
            if i==0 && j==0 {
                dp[0][0] = mp[0][0]
                continue
            }
            if i == 0{
                dp[i][j] = dp[i][j-1] + mp[i][j]
                    pre[i][j] = true
            } else if j == 0 {
                dp[i][j] = dp[i-1][j] + mp[i][j]
                    pre[i][j] = false
            } else {
                if dp[i-1][j] > dp[i][j-1] {
                    dp[i][j] = dp[i-1][j] + mp[i][j]
                    pre[i][j] = false
                } else {
                    dp[i][j] = dp[i][j-1] + mp[i][j]
                    pre[i][j] = true
                }
            }
        }
    }
       
    stack := make([]string, n+m-1)
    pos := n+m-2
    tmpI := m-1
    tmpJ := n-1
    for tmpI >= 0 && tmpJ >=0 {
        stack[pos] = fmt.Sprintf("(%d,%d) %d", tmpI, tmpJ, mp[tmpI][tmpJ])
        pos--
   
        if !pre[tmpI][tmpJ] {
            tmpI--
        } else {
            tmpJ--
        }
    }
    stack[0] = "0,0"
       
    fmt.Println(dp[m-1][n-1])
    for i:=0;i<m+n-1; i++ {
        fmt.Println(stack[i])
    }
}

Linux 系统中，有一个接口日志文件，求访问量最大的接口，在哪一个时段访问量最大
文件格式

timestamp,url,……
1010101010,/api/1,xxxx
1010101010110,/api/2,xxxx

api=$(cat log | tr -s " " | cut -d ',' -f 2 | sort | uniq -c | sort -r | tr -s " " | cut -d " " -f 3 | sed '1p' -n)
ts=$(cat log | grep ${api} | tr -s " " | cut -d ',' -f 1 | sort | uniq -c | sort -r | tr -s " " | cut -d " " -f 3 | sed '1p' -n)
echo ${ts} ${api}

字节电商三面

介绍下项目
init()调用顺序
协程调度机制
阻塞 IO 调度

给定程序间调用树中，判断是否存在循环调用

package main

import (
    "fmt"
)

type Call struct {
    name string
    arr []*Call
}

var vis map[string]bool

func dfs(cur *Call) bool {
    if visited, existed:= vis[cur.name]; existed && visited == true {
        return false
    }
       
    vis[cur.name] = true
    defer func () {
        vis[cur.name]= false
    }()
    // fmt.Println(vis)
    if cur.arr != nil {
        for _, child := range cur.arr {
            if !dfs(child) {
                return false
            }
        }
    }
    return true
}

func check(root *Call) bool {
    if root == nil {
        return true
    }
    vis = make(map[string]bool)
    return dfs(root)
}

func main() {
    root := &Call{
        name: "A",
        arr: []*Call {
            &Call {
                name:"B",
                arr: nil,
            },
            &Call {
                name:"C",
                arr: []*Call {
                    &Call {
                        name:"D",
                        arr: nil,
                    },
                    &Call {
                        name:"E",
                        arr: nil,
                    },
                    &Call {
                        name:"A",
                        arr: nil,
                    },
                },
            },
        },
    }
    fmt.Println(check(root));
}

字节电商 HR 面

自我介绍
网易的实习工作
网易的 mentor 会怎么评价优缺点
为什么选择杭州而不是北京
实习出勤安排
如何选择字节和别的公司

面试笔记留档