常见数据结构原理

常见数据结构原理:

channel slice map

Channel

数据结构

type hchan struct {
    qcount   uint           // total data in the queue
    dataqsiz uint           // size of the circular queue
    buf      unsafe.Pointer // points to an array of dataqsiz elements
    elemsize uint16
    closed   uint32
    elemtype *_type // element type
    sendx    uint   // send index
    recvx    uint   // receive index
    recvq    waitq  // list of recv waiters
    sendq    waitq  // list of send waiters

    lock mutex
}

hchan：channel 数据结构

• qcount：当前 channel 中存在多少个元素； • dataqsize: 当前 channel 能存放的元素容量； • buf：channel 中用于存放元素的环形缓冲区； • elemsize：channel 元素类型的大小； • closed：标识 channel 是否关闭； • elemtype：channel 元素类型； • sendx：发送元素进入环形缓冲区的 index； • recvx：接收元素所处的环形缓冲区的 index； • recvq：因接收而陷入阻塞的协程队列； • sendq：因发送而陷入阻塞的协程队列；

思考：为啥会有阻塞队列，因为写入 channel 和从 channel 读取数据，会时常阻塞。例如：写入goroutine写入后，没有goroutine读取的话，会阻塞。读取也是一样。

waitq

type waitq struct {
    first *sudog
    last  *sudog
}

waitq：阻塞的协程队列

first：队列头部
last：队列尾部

sudog

type sudog struct {
    g *g

    next *sudog
    prev *sudog
    elem unsafe.Pointer // data element (may point to stack)

    isSelect bool

    c        *hchan
}

sudog：用于包装协程的节点（双链表结构）

• g：goroutine，协程； • next：队列中的下一个节点； • prev：队列中的前一个节点； • elem: 读取/写入 channel 的数据的容器; • isSelect：标识当前协程是否处在 select 多路复用的流程中； • c：标识与当前 sudog 交互的 chan.

异常情况：

对于未初始化的 chan，写入操作会引发死锁；
对于已关闭的 chan，写入操作会引发 panic.
读空 channel，park 挂起，引起死锁；
关闭未初始化过的 channel 会 panic；
重复关闭 channel 会 panic；

锁的作用：

核心作用：channel 内部锁是保障其并发安全的核心，所有对 channel 内部状态（缓冲区、关闭标记、等待队列）的修改都需加锁，避免竞态条件；
核心场景：保护缓冲区操作（有缓冲 channel）、保障发送 - 接收配对（无缓冲 channel）、原子性修改关闭状态、保护元数据读取；

写流程串联：

写时存在阻塞读协程 - 直接写入阻塞读协程

加锁；
从阻塞度协程队列中取出一个 goroutine 的封装对象 sudog；
在 send 方法中，会基于 memmove 方法，直接将元素拷贝交给 sudog 对应的 goroutine；
在 send 方法中会完成解锁动作.

总结：需要知道底层数据结构，环形数组（缓冲区数据） + 锁 + 双链表（阻塞队列）

写时无阻塞读协程但环形缓冲区仍有空间 - 写入环形缓冲区

• 加锁； • 将当前元素添加到环形缓冲区 sendx 对应的位置； • sendx++; • qcount++; • 解锁，返回.

写时无阻塞读协程且环形缓冲区无空间 - 阻塞写协程

• 加锁； • 构造封装当前 goroutine 的 sudog 对象； • 完成指针指向，建立 sudog、goroutine、channel 之间的指向关系； • 把 sudog 添加到当前 channel 的阻塞写协程队列中； • park 当前协程； • 倘若协程从 park 中被唤醒，则回收 sudog（sudog能被唤醒，其对应的元素必然已经被读协程取走）； • 解锁，返回

读操作串联

读时有阻塞的写协程 - 从阻塞写协程中读取

• 加锁； • 从阻塞写协程队列中获取到一个写协程； • 倘若 channel 无缓冲区，则直接读取写协程元素，并唤醒写协程； • 倘若 channel 有缓冲区，则读取缓冲区头部元素，并将写协程元素写入缓冲区尾部后唤醒写写成； • 解锁，返回.

读时无阻塞写协程且缓冲区有元素 - 从环形缓冲区读取

• 加锁； • 获取到 recvx 对应位置的元素； • recvx++ • qcount-- • 解锁，返回

读时无阻塞写协程且缓冲区无元素 - 阻塞读协程

• 加锁； • 构造封装当前 goroutine 的 sudog 对象； • 完成指针指向，建立 sudog、goroutine、channel 之间的指向关系； • 把 sudog 添加到当前 channel 的阻塞读协程队列中； • park 当前协程； • 倘若协程从 park 中被唤醒，则回收 sudog（sudog能被唤醒，其对应的元素必然已经被写入）； • 解锁，返回

Select 多路复用原理

一、select 核心特性（先明确行为）

在讲原理前，先回顾 select 的核心行为，这是理解底层的基础：

select 仅能操作 channel，支持三种 case：
- 接收操作：case val := <-ch: / case <-ch:；
- 发送操作：case ch <- val:；
- 默认分支：default:（无就绪 case 时执行）。
无 default 时，select 会阻塞当前 Goroutine，直到任意一个 case 就绪（channel 可读写）；
有 default 时，若所有 case 都未就绪，直接执行 default，不阻塞；
多个 case 同时就绪时，伪随机选择一个执行（避免某个 case 长期饥饿）；
空 select（无任何 case）会永久阻塞 Goroutine（select {}）；
select 的每个 case 操作都是原子性的（依赖 channel 内部锁保障）。

二、select 底层核心数据结构

Go 编译期会将 select 语句转换为对 runtime 层 selectgo 函数的调用，而每个 select 的 case 会被封装为 scase 结构体，整个 select 对应一个 scase 数组。

// runtime/scase.go 中定义的 select case 结构体
type scase struct {
    kind uint16        // case 类型：0=接收(RCV)、1=发送(SND)、2=默认(DEFAULT)
    ch   *hchan        // 关联的 channel 指针（hchan 是 channel 底层结构体）
    elem unsafe.Pointer // 数据指针：
                        // - 发送 case：指向要发送的值；
                        // - 接收 case：指向存储接收值的地址；
                        // - default：nil
}

// selectgo 函数的入参/出参（简化）
// 返回值：选中的 case 索引（若 <0 表示无就绪 case 且无 default）
func selectgo(cases []scase, ncase int, block bool) (int, bool)

字段	含义
`kind`	标记 case 类型：接收（RCV）、发送（SND）、默认（DEFAULT）
`ch`	指向当前 case 关联的 channel 底层结构体 `hchan`（包含 channel 缓冲区、锁、等待队列等）
`elem`	数据缓冲区指针，用于传递发送 / 接收的数据，避免值拷贝开销

selectgo 执行步骤：

步骤 1：编译期转换

Go 编译器会将代码中的 select 语句转换为：

构建 scase 数组：每个 case 对应一个 scase，default 对应最后一个 scase（kind=DEFAULT）；
调用 selectgo 函数，传入 scase 数组、case 数量、是否阻塞（无 default 则 block=true）；
根据 selectgo 返回的 case 索引，执行对应 case 的逻辑。

步骤 2：运行时 selectgo 执行（核心）

步骤 2.1：锁定所有涉及的 channel（避免死锁）

为了防止多个 Goroutine 同时操作这些 channel 导致死锁，selectgo 会：

收集所有 case 中的非 nil channel；
按 channel 内存地址升序排序（关键！避免不同 Goroutine 按不同顺序加锁导致死锁）；
依次对每个 channel 加锁（调用 hchan.mutex.Lock()）。

步骤 2.2：遍历所有 case，检查是否有就绪的 channel

遍历除 default 外的所有 case，检查对应的 channel 是否 “就绪”（可立即执行发送 / 接收，无需阻塞）：

接收 case（kind=0）：检查 channel 是否有数据（缓冲区非空）或有等待的发送方 → 就绪；
发送 case（kind=1）：检查 channel 是否有空闲缓冲区或有等待的接收方 → 就绪；
记录所有就绪的 case 索引，存入就绪列表。

步骤 2.3：处理就绪 case（核心分支）

有就绪 case：
1. 从就绪列表中伪随机选择一个（用 fastrand() 生成随机数，避免饥饿）；
2. 解锁所有 channel（按加锁逆序解锁）；
3. 执行该 case 的操作（接收 / 发送数据），返回该 case 的索引；
无就绪 case：进入下一步。

步骤 2.4：处理 default 分支

若有 default case（kind=2）：
1. 解锁所有 channel；
2. 返回 default 的索引，执行 default 逻辑；
若无 default：进入阻塞逻辑。

步骤 2.5：阻塞当前 Goroutine（无就绪 + 无 default）

将当前 Goroutine 封装为 sudog 结构体（包含 Goroutine 指针、scase 索引等）；
将 sudog 加入所有涉及 channel 的等待队列：
- 接收 case：加入 channel 的 recvq（接收等待队列）；
- 发送 case：加入 channel 的 sendq（发送等待队列）；
解锁所有 channel；
挂起当前 Goroutine（调用 gopark()），等待被唤醒。

步骤 2.6：被唤醒后重新检查（关键）

当某个 channel 就绪时（比如有数据发送 / 接收），runtime 会唤醒对应的 sudog（即当前 Goroutine），然后：

重新锁定所有 channel（按地址升序）；
检查唤醒当前 Goroutine 的 case 是否真的就绪（避免虚假唤醒）；
若就绪：解锁所有 channel，返回该 case 索引；
若未就绪：重复步骤 2.2~2.5（重新阻塞）。

步骤 3：执行选中的 case 逻辑

selectgo 返回选中的 case 索引后，Go 运行时会执行对应 case 的代码逻辑：

接收 case：将 channel 中的数据写入 elem 指向的地址；
发送 case：将 elem 指向的值写入 channel；
default：执行默认逻辑。

select 核心机制详解

1. 伪随机选择就绪 case（避免饥饿）

当多个 case 同时就绪时，selectgo 不会按顺序选择第一个，而是通过伪随机算法选择。

目的：避免某个 case 长期被优先选中（比如 ch1 一直就绪，若按顺序选会导致 ch2 永远得不到执行），保障公平性。

2. 阻塞与唤醒机制

Goroutine 阻塞在 select 时，核心依赖 sudog 和 channel 等待队列：

sudog：封装了 Goroutine 与 select case 的关联关系，是 runtime 层的 “等待对象”；
等待队列（recvq/sendq）：channel 底层的双向链表，存储所有等待该 channel 的 sudog；
唤醒触发：当 channel 有新的发送 / 接收操作时，runtime 会遍历等待队列，唤醒对应的 sudog（Goroutine），使其重新执行 selectgo。

3. 死锁避免（channel 加锁排序）

selectgo 对 channel 按地址升序加锁是关键设计：

假设 Goroutine A 操作 ch1、ch2，Goroutine B 也操作 ch1、ch2；
若都按地址升序加锁（比如 ch1 地址 (ch2，则先锁 ch1 再锁 ch2），则不会出现 “A 锁 ch1 等 ch2，B 锁 ch2 等 ch1” 的死锁；
若不排序，死锁概率会大幅增加。

特殊场景的实现逻辑

1. 空 select（select ）

selectgo 会直接调用 gopark() 永久挂起 Goroutine，直到程序退出（或被手动唤醒）。

2. 单个 case + 无 default

等价于直接执行 <-ch，selectgo 会直接检查 ch 是否就绪，未就绪则阻塞，无需伪随机选择（只有一个 case）。

3. 多个 case 对应同一个 channel

selectgo 会将两个 case 都视为就绪（若 ch 就绪），然后伪随机选一个执行 —— 这是合法的，但无实际业务意义，仅测试时可能用到。

性能注意事项（避坑核心）

1. 大量 case 会降低性能

selectgo 的时间复杂度是 O (n)（n 为 case 数量），主要消耗在：

遍历所有 case 检查就绪状态；
对所有 channel 加锁 / 解锁；若 case 数量超过 100，性能会明显下降。

优化方案：

拆分 select：将大量 case 拆分为多个小 select；
使用反射 / 第三方库：比如 github.com/eapache/channels 实现高效多路复用；
用工作池模式替代：将 channel 操作分发到多个 Goroutine，避免单个 select 监听过多 channel。

2. 避免在 select 中创建临时 channel

select {
	case <-make(chan int): // 临时 channel，永远阻塞
		// 逻辑
}

临时 channel 无缓冲区、无发送方，会导致 select 永久阻塞，且每次执行都会创建新 channel，增加内存开销。

3. select 阻塞时会释放 CPU

Goroutine 阻塞在 select 时，会调用 gopark() 放弃 CPU 使用权，不会占用 CPU 资源（区别于自旋），这是 Go 高效调度的关键。

Channel​

数据结构​

waitq​

sudog​

异常情况：​

锁的作用：​

写流程串联：​

写时存在阻塞读协程 - 直接写入阻塞读协程​

写时无阻塞读协程但环形缓冲区仍有空间 - 写入环形缓冲区​

写时无阻塞读协程且环形缓冲区无空间 - 阻塞写协程​

读操作串联​

读时有阻塞的写协程 - 从阻塞写协程中读取​

读时无阻塞写协程且缓冲区有元素 - 从环形缓冲区读取​

读时无阻塞写协程且缓冲区无元素 - 阻塞读协程​

Select 多路复用原理​

一、select 核心特性（先明确行为）​

二、select 底层核心数据结构​

selectgo 执行步骤：​

步骤 1：编译期转换​

步骤 2：运行时 selectgo 执行（核心）​

步骤 2.1：锁定所有涉及的 channel（避免死锁）​

步骤 2.2：遍历所有 case，检查是否有就绪的 channel​

步骤 2.3：处理就绪 case（核心分支）​

步骤 2.4：处理 default 分支​

步骤 2.5：阻塞当前 Goroutine（无就绪 + 无 default）​

步骤 2.6：被唤醒后重新检查（关键）​

步骤 3：执行选中的 case 逻辑​

select 核心机制详解​

1. 伪随机选择就绪 case（避免饥饿）​

2. 阻塞与唤醒机制​

3. 死锁避免（channel 加锁排序）​

特殊场景的实现逻辑​

1. 空 select（select ）​

2. 单个 case + 无 default​

3. 多个 case 对应同一个 channel​

性能注意事项（避坑核心）​

1. 大量 case 会降低性能​

优化方案：​

2. 避免在 select 中创建临时 channel​

3. select 阻塞时会释放 CPU​