2020年6月

问题定义

很多人在做程序的时候在启动 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 个子叶子节点
  • 每个哈夫曼编码都不是另一个哈夫曼编码的前缀,说白了路径的长短,就是编码的长短,再结合上每个字符其实都是在叶子节点上,这就不可能是其他叶子节点的前缀,因为如果是前缀,需要满足两个节点的关系为父子节点才可以。
  • 哈夫曼是带全路径长度最短的树,权值较大的节点离根节点较近
  • 带权路径长度:书中所有的叶子结点的权值乘上其道根节点的路径长度。与最终的哈夫曼编码总长度成正比关系