maksim 发布的文章

请求时间过长,用户侧可能已经离开本页面了,服务端还在消耗资源处理,得到的结果没有意义,同时过长时间的服务端处理会占用过多资源,导致并发能力下降,甚至出现不可用事故,一般一个请求是由多个串行或并行的子任务来完成的,每个子任务可能是另外的内部请求,那么当这个请求超时的时候,我们就需要快速返回,释放占用的资源,比如goroutine,文件描述符等。

我们可以利用管道了来决这个问题。

package main

import (
    "fmt"
    "sync"
    "time"
)
package main

import (
    "fmt"
    "time"
)

func job(ch chan<- struct{}) {
    time.Sleep(time.Second * 5)
    ch <- struct{}{}
}

var ch chan struct{}

func main() {
    ch = make(chan struct{}, 1)
    go func() {
        job(ch)
    }()

    select {
    case <-ch:
        fmt.Println("done")
    case <-time.After(time.Second * 3):
        fmt.Println("timeout process exit!")
    }

}

问题定义

很多人在做程序的时候在启动 Goroutine 的时候并没有限制其执行的数量,如果任务只有 100 个,1000 、10000 个 其实都没有问题,但是如果你执行任务非常耗时,而且数量特别大,在不断的开 Goroutine 的时候很有可能就崩溃了。

在服务器上执行任务的时候是需要限制执行数量的,如果超过设置的执行数量就需要进行等待。

现在我们来模拟一下这种情况的出现。

package main

import (
    "fmt"
    "sync"
    "time"
)

func job(i int) {
    time.Sleep(time.Millisecond * 500)
    fmt.Printf("执行完毕,序号 %d \n\n", i)
}

func main() {
    wg := sync.WaitGroup{}
    for i := 0; i < 10000000; i++ {
        wg.Add(1)
        go func(i int) {
            defer wg.Done()
            job(i)
        }(i)
    }
    wg.Wait()
}

在 Job 函数中,我们故意让函数 sleep 500 毫秒,用来模拟耗时操作,我们来执行一下。

...

执行完毕,序号 286128 

执行完毕,序号 20228 

panic: too many concurrent operations on a single file or socket (max 1048575)

goroutine 1432450 [running]:
internal/poll.(*fdMutex).rwlock(0x14000128060, 0x0?)
        /opt/homebrew/Cellar/go/1.18.2/libexec/src/internal/poll/fd_mutex.go:147 +0x13c
internal/poll.(*FD).writeLock(...)
        /opt/homebrew/Cellar/go/1.18.2/libexec/src/internal/poll/fd_mutex.go:239
internal/poll.(*FD).Write(0x14000128060, {0x14131074780, 0x20, 0x30})
        /opt/homebrew/Cellar/go/1.18.2/libexec/src/internal/poll/fd_unix.go:370 +0x48
os.(*File).write(...)
        /opt/homebrew/Cellar/go/1.18.2/libexec/src/os/file_posix.go:48
os.(*File).Write(0x14000126008, {0x14131074780?, 0x20, 0x14070f5f758?})
        /opt/homebrew/Cellar/go/1.18.2/libexec/src/os/file.go:176 +0x64
fmt.Fprintf({0x104434438, 0x14000126008}, {0x1043fe079, 0x1b}, {0x14070f5f758, 0x1, 0x1})
        /opt/homebrew/Cellar/go/1.18.2/libexec/src/fmt/print.go:205 +0x88
fmt.Printf(...)
        /opt/homebrew/Cellar/go/1.18.2/libexec/src/fmt/print.go:213
main.job(0x0?)
        /Users/guozhu/WorkSpace/study-go/go/main.go:11 +0x78
main.main.func1(0x0?)
        /Users/guozhu/WorkSpace/study-go/go/main.go:20 +0x50
created by main.main
        /Users/guozhu/WorkSpace/study-go/go/main.go:18 +0x40

Process finished with the exit code 2

刚开始执行其实是没问题的,但是等执行一会后 Go 就会报错了,panic: too many concurrent operations on a single file or socket (max 1048575)

对单个 file/socket 的并发操作个数超过了系统上限,这个报错是 fmt.Printf 函数引起的,fmt.Printf 将格式化后的字符串打印到屏幕,即标准输出。在 linux 系统中,标准输出也可以视为文件,内核(kernel)利用文件描述符(file descriptor)来访问文件,标准输出的文件描述符为 1,错误输出文件描述符为 2,标准输入的文件描述符为 0,简而言之就是内存耗尽了。

那如果我们将 fmt.Printf 这行代码去掉呢?那程序很可能会因为内存不足而崩溃。这一点更好理解,每个协程至少需要消耗 2KB 的空间,那么假设计算机的内存是 2GB,那么至多允许 2GB/2KB = 1M 个协程同时存在。那如果协程中还存在着其他需要分配内存的操作,那么允许并发执行的协程将会数量级地减少。

利用 Channel 限制 Goroutine 数量

make(chan struct{}, 3) 创建缓冲区大小为 3 的 channel,在没有被接收的情况下,至多发送 3 个消息则被阻塞。

利用这样特性,我们会可以在开启 Goroutine 调用 <- struct{}{},若缓存区满了则会被阻塞。当协程任务执行结束,在调用 <- ch 释放缓冲区,这样就可以限制 Goroutine 的数量了。

package main

import (
    "fmt"
    "sync"
    "time"
)

func job(i int) {
    time.Sleep(time.Millisecond * 500)
    fmt.Printf("执行完毕,序号 %d \n\n", i)
}

var pool chan struct{}

func main() {
    pool = make(chan struct{}, 1000)

    wg := sync.WaitGroup{}

    for i := 0; i < 10000000; i++ {
        pool <- struct{}{}
        wg.Add(1)
        go func(i int) {
            defer wg.Done()
            defer func() {
                <-pool
            }()
            job(i)
        }(i)
    }
    wg.Wait()
}

哈夫曼树

哈夫曼编码,又称为霍夫曼编码,它是现代压缩算法的基础,假设要把字符串【ABBBCCCCCCCCDDDDDDEE】转换成二进制编码进行传输,想到的第一种做法可以把他转换成 ASCII 编码(65~69,1000001~1000101),例如我们现在要传输 ABBB。

ABBB

1000001100001010000101000010

但是有点冗长,如果希望编码更短呢?

可以先约定一下五个字母对对应的二进制。

A  -> 0
B  -> 1
C  -> 10
D  -> 11
E  -> 100

我们依旧传输 ABBB

0111

但是现在有一个问题,我们如何去解释这个二进制呢?因为有的字符是 1 位有的是 2 位有的是三位的。这个二进制中指有 A 是 0 开头的,所以二进制的第一位是 0 我们可以直接解析成 A,但是后面的几位就很难搞了。

按照我们的规则 111 可以被解析为:

  • BD
  • DB
  • BBB

导致这个问题的根本原因是我们的一个字母的编码可以是后一个编码的前缀,所以我们就需要进行约定,每一个编码都不能是后一位的前缀。所以我们先规定,所有字母都用三位:

ABCDE
000001010011100

一共二十个字母,转换成 60 个二进制位.

如果使用哈夫曼编码,可以压缩至 41 个二进制位,约为原来长度的 68.3%。相当于压缩了30%。

哈夫曼树

先计算出每个字母的出现频率(权值,这里直接用出现次数),【ABBBCCCCCCCCDDDDDDEE】。

ABCDE
13862

利用这些权值,构建一颗哈夫曼树(又称为霍夫曼树、最优二叉树)。

如何构建一颗哈夫曼树呢?假设有 n 个权值。

  1. 以权值作为根节点构建 n 颗二叉树,组成森林
  2. 在森林中选出 2 个根节点最小的树合并,作为一颗新树的左右子树,且新树的根节点为其左右子树根节点之和。
  3. 从森林中删除刚刚选取的 2 颗树,并将新树加入森林
  4. 重复 2、3步骤,直到森林只剩一棵树为止,该树即为哈夫曼树。

根据规则,我们来构建哈夫曼树,构建过程如下图

2023-04-12T07:18:31.png

构建哈夫曼编码

以 left 为 0,right 为 1,可以得出 5 个字母对应的哈夫曼编 码

ABCDE
11101100101111

【ABBBCCCCCCCCDDDDDDEE】 的哈夫曼编码是:

11101101101100000000001010101010101111

现在还有一个问题,这个哈夫曼编码传递过去对方能解析吗,我们之前说要对齐编码长度,方便解析,可是在这里长度是不一样的。

哈夫曼的编码有一个特点,那就是的编码都不是其他编码的前缀,结合这一特点,我们就可以注意解析二进制了例如步骤如下:

  1. 我们先读去第一个 1 这样就可以将 C 排除了
  2. 继续读取,数据变成了 11,这样就把 D 给排除了
  3. 继续读取,数据变成了 111 这样就剩下了两个选择,A,E
  4. 继续读取,数据编程了 1110 这样就确定了是 A

以此类推就可以解码出所有的字符了。

在哈夫曼中出现次数最多的字符,编码是最短的,在上面的字符串中,C 出现的次数最多,所以它的编码就是 0,出现的最少的字符,编码就是最长的,这样一来,哈夫曼编码出现的二进制天然就是最短的,这样一来就构成了任何一个编码都不是另外编码的前缀。

总结

  • n 个权值构建出来的哈夫曼树拥有 n 个子叶子节点
  • 每个哈夫曼编码都不是另一个哈夫曼编码的前缀,说白了路径的长短,就是编码的长短,再结合上每个字符其实都是在叶子节点上,这就不可能是其他叶子节点的前缀,因为如果是前缀,需要满足两个节点的关系为父子节点才可以。
  • 哈夫曼是带全路径长度最短的树,权值较大的节点离根节点较近
  • 带权路径长度:书中所有的叶子结点的权值乘上其道根节点的路径长度。与最终的哈夫曼编码总长度成正比关系

B+树是 B 树的变体,常用于数据库和操作系统的文件系统中,MySQL 数据库的索引就是基于 B+树的实现的,其大致结构如下:

B+ tree

  • B+ Tree 的特点

    • 分为内部节点(非叶子)、叶子结点 2 种节点

      • 内部节点只存储 key,不存储具体数据
      • 叶子节点存储 key 和具体的数据。
    • 所有的叶子节点形成一条有序链表
    • m 阶 B+Tree 树非根节点的元素数量 x :⌈m /2⌉ ≤ x < m

为什么要设计成这样呢?

硬盘的分类

市面上常见的硬盘有:机械硬盘(Hard Disk Drive, HDD),固态硬盘(Solid State Drive,SSD)

硬盘

在这里,我们主要介绍机械硬盘

盘片(platter)、盘面(side)、读写磁头(head)

磁盘剖面图

机器硬盘的剖面图大概就长这个样子。

  • 硬盘一般由多个盘片组成
  • 每个盘片包含包含两个盘面,两面都可以放数据
  • 每个盘面有 1 个对应的读写磁头
  • 盘面、磁头由上到下从 0 开始编号

磁道(track)、扇区(sector)

扇区和磁道

  • 盘面中一圈圈灰色圆环为一条条的磁道
  • 磁道由外到内从 0 开始编码
  • 每个磁道上的一个弧段叫做一个扇区
  • 扇区就是磁盘的最小读写单位
  • 一个扇区的大小通常是 512 字节,也有 4096 字节的

早期磁盘的扇区细节

  • 每条磁道的扇区数是相同,所以外圈扇区的面积会比内圈扇区大
  • 为了更好的读取数据,它们会存放相同的字节数,所以外圈扇区的记录密度要比去内圈小,会浪费大量的空间。
  • 硬盘的存储容量 = 磁头书 盘面磁道数 磁道扇区数 * 扇区字节数

柱面(cylinder)

柱面

想通编号的磁道形成了一个圆柱,成为柱面,磁盘的柱面数与一个盘里面的磁道数是相等得分。

磁盘块

  • 磁盘块,在 Windows 叫做簇(cluster),在 linux 中叫做块(block)
  • 相邻的 2^n 个扇区组合在一起,形成一个磁盘块
  • 操作系统对磁盘进行管理时,以磁盘块作为最小读写单位,一般来说一个磁盘块是 4096 字节(4kb,由 8 个连续的 512 字节扇区组成)

注意:

  • 磁盘块是操作系统中的一个虚拟概念
  • 扇区是磁盘上真实存在的物理区域

操作系统读取硬盘数据的过程

  1. 操作系统将 LBA(Logical Block Address,逻辑块地址) 传送给磁盘驱动器并启动那个读取命令,比如类似设备号 4、磁头号4、磁道号 8、扇区号 6、扇区计数 8 这样的信息。
  2. 磁盘驱动器会根据 LBA 将磁头移动到正确的磁道,盘片开始旋转,将目标扇区旋转到磁盘下
  3. 磁盘控制器将扇区数据等信息传送到一个处于磁盘界面的缓冲区
  4. 磁盘驱动器向操作系统发出“数据就绪”信号
  5. 操作系统从磁盘界面的缓冲区读取数据

    1. 既可以按照一个字节一个字节的方式读取
    2. 也可以启动 DMA(Direct Memory Access,直接内存读取)命令获取

磁盘完成 IO 操作的时间

  • 主要由寻道时间、旋转延迟时间、数据传输时间 3 个部分构成

    • 寻道时间 (seek):将读写磁头移动至正确的磁道上所需的时间,这部分时间代价最高
    • 旋转延迟时间(rotation):磁盘旋转将目标扇区移动到读写磁头下方所需的时间,取决于磁盘转速
    • 数据传输时间(transfer):完成数据传输所需要的时间,取决于接口的数据传输率,通常远小于前两部分消耗时间的
  • 决定时间长短的大部分因素是和硬件相关的,但所需移动的磁道数是可以通过操作系统来进行控制的。

    • 减少所需移动的磁道数是减少整个磁盘读写时间的有效办法
    • 合理安排磁头的移动以减少寻道时间就是磁盘调度算法的目的所在

MySQL 的索引底层为何使用 B+Tree

  • 为了减小 IO 操作数量,一般把一个节点的大小设计成最小读写单位的大小
  • MySQL 的存储引擎 InnoDB 的最小读取单位是 16K
  • 对比 B Tree 和 B+ Tree 的优势:

    • 每个几点存储 key 数量更多,树的高度更低
    • 所有的具体数据都存在叶子节点上,所以每次查询都要查到叶子节点,查询速度比较稳定
    • 所有的叶子节点构成一个有序链表,做区间查询更方便

B-Tree

B 树是一种平衡的多路搜索树,用于文件系统、数据库的实现。

3 阶 B-Tree

4 阶 B-Tree

5 阶 B-Tree

仔细观察 B 树有什么眼前一亮的特点?

  • 一个节点可以存储超过 2 个元素、可以拥有超过 2 个子节点
  • 拥有二叉搜索树的一些性质,我们拿 3 阶 B 树举例,root 节点左侧都是比 18 小的,右侧都是比 48 大的,而中间的节点是在他们两者之间的。
  • 平衡,每个节点所有的子树高度都是一致的。
  • 比较矮

m 阶 B-tree 的性质(m ≥ 2)

  • 假设一个节点存储的元素个数为
  • 根节点: 1 ≤ x ≤ m - 1 :
  • 非根节点:⌈m /2⌉ - 1 ≤ x ≤ m -1
  • 如果有子节点,子节点的个数 y = x + 1

如果我们是 3 阶段 Btree:

  • 根节点:1 ≤ x ≤ 2
  • 非根节点 2≤ y ≤3

因此可以成为(2,3)树、2-3 树。

B 树 VS 二叉搜索树

  • B-Tree 和 二叉搜索树,在逻辑上是等价的

二叉搜索树

3 阶 B-Tree

我们只要让二叉搜索树中的 18 和 33合并成为一个节点,之后再让 23 和 30 合并以此类推,就变成了 B-Tree。所以我们只需要将二叉搜索树的某些父子节点合并后就可以将变成一颗 B-Tree。

  • 多代节点合并可以获得一个超级节点。

    • 2 代合并的超级节点,最多拥有 4 个子节点(至少是 4 阶 B—Tree)
    • 3 代合并的超级节点,最多拥有 8 个子节点(至少是 8 阶 B—Tree)
    • n 代合并的超级节点,最多拥有 2^n 个子节点(至少是 2^n 阶 B—Tree)
  • m 阶 B-Tree,最多需要 log2m 代合并

搜索

B-Tree 的搜索和二叉树的搜索类似。

  1. 先从节点内部从小到大开始搜索元素
  2. 如果命中,搜索结束
  3. 如果未命中,再去对应的子节点中搜索元素,重复步骤 1

添加

新添加的元素必定是添加到叶子节点。

我们现在有一个4 阶B 树。

B-tree

现在我们要向这棵树中插入 55

  1. 首先是与 40 进行比较,发现 55 比 44 大,那么向右子树添加
  2. 右子树中找到了 60~88,55 比 66 小,那么就像左子树添加
  3. 最终我们找到了 50 节点,这个时候新添加的元素必须放在叶子节点上,那么就会将 55 添加 50 上。

B-Tree

现在我们继续向B-Tree 中插入数据 95,按照上面的逻辑执行后。

btree

如果这个时候右下角的子树已经达到了 3 个节点,如果我们再向其中插入 98 呢?如果在加入的话节点就出了 4 阶 B-Tree 的子节点数量。

这个时候就需要进行:上溢(overflow)。

上溢(overflow)

现在假设是 5 阶 B-Tree,一个节点最多存储四个元素。如果存储了五个元素那么就开始上溢。

btree

  • 上溢节点的元素个数必然等于 m
  • 假设上溢节点最中间的元素的位置为 k

    • 将 K 位置的元素向上与父节点合并
    • 将[0, k- 1]和 [k+1, m -1] 位置的元素分裂成两个子节点

      • 这两个子节点的元素个数,必然都不会低于最低限制 ⌈m /2⌉ - 1

btree

这个时候,子节点的上溢会导致父节点的上溢,因为父节点此时也已经超过了最大值,所以一次分裂完毕后,依然按照上述方法进行解决,最极端的情况,可能会一直分裂到根节点。

btree

我们回到上节的那个例子。

b-tree

现在插入 98 后。

98

插入 52:

Untitled

52

插入 54

54

删除

删除 - 叶子结点

如果我们需要删除的元素在叶子结点中,那么直接删除即可。

B-tree

删除- 非叶子节点

  1. 先找到前驱或者后继元素,覆盖所需元素的值
  2. 先把前驱后继元素删除

寻找 60 的前驱和后继:

BTree

Btree

  • 非叶子节点的前驱或后继元素,必须在叶子节点中。
  • 所以这里的删除前驱或后继元素,就是最开始提到的情况:删除的元素在叶子节点中。
  • 真正的删除元素都是发生在叶子节点上。

叶子节点被删除一个元素后,元素个数可能低于最低限制。这种现象称为下溢(underflow)。

下溢

  • 下溢节点的元素数量必然等于 ⌈m /2⌉ - 2

Btree

  • 如果下溢节点临近的兄弟节点,有至少 ⌈m /2⌉ 个元素,可以像其接一个元素

    • 将父节点的元素 b 插入到下溢节点的 0 位置(最小位置)
    • 用兄弟节点的元素 a(最大元素)替代父节点的 yuansub
    • 这种操作其实就是:旋转

B-Tree

B-Tree

B-Tree

图是一颗 5 阶 B-Tre,现在要删除 22,:

  • 如果下溢节点临近的兄弟节点,只有 ⌈m /2⌉ -1 哥元素

    • 将父节点的元素 b 挪下来和左右子节点进行合并
    • 合并后的节点元素个数等于 ⌈m /2⌉ + ⌈m /2⌉ - 2,不会好过 m -1。
    • 这个操作可能会导致父节点下溢,依然按照上述方法解决,下溢现象可能会一直往上传播。

B-Tree

上溢和下溢带来的现象

  • 上溢会让 B-Tree 变高
  • 下溢会让 B-Tree 变矮