系统设计学习（三）限流与零拷贝

七、有哪些常用限流算法？

Leaky Bucket 漏桶

漏桶可理解为是一个限定容量的请求队列。想象有一个桶，有水（指请求或数据）从上面流进来，水从桶下面的一个孔流出来。水流进桶的速度可以是随机的，但是水流出桶的速度是恒定的。 当水流进桶的速度较慢，桶不会被填满，请求就可以被处理。 当水流进桶的速度过快时，桶会逐渐被填满，当水超过桶的容量就会溢出，即被丢弃。

Token Bucket 令牌桶

在令牌桶算法中，系统会以一个固定的速率向桶中添加令牌。当有请求（或数据包）到来时，会从桶中删除一定数量的令牌。如果桶中有足够的令牌，请求就可以立即处理； 如果桶中没有足够的令牌，请求就会被阻塞或丢弃，具体行为取决于具体的实现。 桶有容量限制，如果添加令牌时桶已满，新的令牌就会被丢弃。

Fixed Window 固定窗口

在一个固定的时间窗口内，只允许一定数量的请求。如果在这个时间窗口内的请求已经达到了限制，那么新的请求就会被拒绝，过了当前时间窗口后，会进入下一个时间窗口，并重置窗口内的请求数量，重新计算。

Sliding Window 滑动窗口

在固定窗口限流算法中，如果大量请求在一个时间窗口的边界附近到达，可能会造成瞬时的流量突增。 滑动窗口随着时间的推移，动态统计请求量，避免了在窗口边界附近的流量突增。

九、零拷贝技术

Netty 用到了零拷贝来大幅提升网络吞吐量

正常流程：4次拷贝，4次用户态和内核态之间的切换

1. 应用进程向系统申请读磁盘的数据，这时候程序从用户态切换成内核态。
2. 系统也就是 linux 系统得知要读数据会通知 DMA 模块要读数据，这时 DMA 从磁盘拉取数据写到系统内存中。
3. 系统收到 DMA 拷贝的数据后把数据拷贝到应用内存中，同时把程序从内核态变为用户态。
4. 应用内存拿到从应用内存拿到数据后，会把数据拷贝到系统的 Socket 缓存，然后程序从用户态切换为内核态。
5. 系统再次调用 DMA 模块，DMA 模块把 Socket 缓存的数据拷贝到网卡，从而完成数据的发送，最后程序从内核态切换为用户态。

MMAP + write

buf = mmap(file,length) 
write(socket,buf,length)
  // 所谓的 MMAP， 其实就是系统内存某段空间和用户内存某段空间保持一致，也就是说应用程序能通过访问用户内存访问系统内存
1
2
3

• 应用进程通过接口调用系统接口 MMAP，并且进程从用户态切换为内核态。
• 系统收到 MMAP 的调用后用 DMA 把数据从磁盘拷贝到系统内存，这时是第1次数据拷贝。由于这段数据在系统内存和应用内存是共享的，数据自然就到了应用内存中，这时程序从内核态切换为用户态。
• 程序从应用内存得到数据后，会调用 write 系统接口，这时第2次拷贝开始，具体是把数据拷贝到 Socket 缓存，而且用户态切换为内核态。
• 系统通过 DMA 把数据从 Socket 缓存拷贝到网卡。
• 最后，进程从内核态切换为用户态。

这样做到收益是减少了一次拷贝，但是用户态和内核态仍然是4次切换。

sendfile

1. 应用进程调用系统接口 sendfile，进程从用户态切换完内核态。
2. 系统接收到 sendfile 指令后，通过 DMA 从磁盘把数据拷贝到系统内存。
3. 数据到了系统内存后，CPU 会把数据从系统内存拷贝到 socket 缓存中。
4. 通过 DMA 拷贝到网卡中。
5. 最后，进程从内核态切换为用户态。

零拷贝

1. 应用进程调用系统接口 sendfile，进程从用户态切换完内核态。
2. 系统接收到 sendfile 指令后，通过 DMA 从磁盘把数据拷贝到系统内存。
3. 数据到了系统内存后，CPU 会把文件描述符和数据长度返回到 socket 缓存中（注意这里没有拷贝数据）。
4. 通过 SG-DMA 把数据从系统内存拷贝到网卡中。
5. 最后，进程从内核态切换为用户态。

零拷贝在用户态和内核态之间的切换是2次，拷贝是2次，在内存之间没有拷贝，大大减少了切换次数和拷贝次数,而且全程没有 CPU 参与数据的拷贝。

## SG-DMA
在通常情况下，DMA 操作是在一个连续的内存块上执行的。然而，在实际应用中，所需的数据可能是分散的，即分布在物理内存的多个不同区域。Scatter-Gather DMA 就是为了解决这个问题而设计的：

- 分散（Scatter）：指的是从内存的多个不连续位置读取数据块，并"分散"到连续的硬件缓冲区中，或者相反，将数据从硬件的连续缓冲区写入到内存的分散区域。

- 聚集（Gather）：则是指将来自多个源的数据“聚集”起来，组合成一个大的数据块，以便连续地通过 DMA 传输。

为实现这一过程，操作系统通常会维护一个描述符表或链表，列出所有分散内存区块的地址和大小。DMA 控制器使用这个表来了解每个数据块的位置，并按正确的顺序将它们聚集起来进行传输。

Scatter-Gather DMA 在需要高效处理大量分散数据的场景下非常有用，比如在网络通信、文件系统管理和音视频数据流处理中。它消除了额外的数据拷贝步骤，因为它允许直接在分散的内存区块上操作，从而减少了延迟，提高了吞吐量，并减轻了 CPU 负担。
1
2
3
4
5
6
7
8
9
10