滑动窗口与流控的算法本质

滑动窗口不只是一道 LeetCode 题型，它是网络协议、流控、限流的通用模式。 本文从抽象模型出发，贯穿 TCP、算法题、反压、限流、RDMA， 试图找到”窗口”这个概念的统一内核。

一、滑动窗口：一个抽象的速率匹配模式

在任何 producer-consumer 系统中，都存在一个核心矛盾：生产速率与消费速率的不匹配。 滑动窗口的本质，就是在不停止生产者的前提下，用一个有界缓冲区来吸收速率差异， 并通过动态调整窗口大小来反馈消费者的处理能力。

抽象地看，滑动窗口模式包含三个要素：

1. 窗口（Window）：一段允许”在途”（in-flight）的数据范围，由左边界和右边界界定。
2. 滑动（Sliding）：随着消费者确认（ACK），窗口左边界右移；随着生产者发送，窗口内的已用空间增长。
3. 流量控制（Flow Control）：消费者通过通告可用窗口大小，限制生产者的发送速率。

用伪代码描述这个模型：

窗口状态:
  left   = 已确认的最大序号 + 1
  right  = left + window_size
  inflight = 已发送但未确认的数据量

不变量:
  inflight <= window_size
  只有当 inflight < window_size 时，生产者才能继续发送

消费者反馈:
  ACK(n)         -> left = n, inflight 减少
  WINDOW_UPDATE  -> window_size 变化, right 随之变化

这个模型的美妙之处在于它的通用性。TCP 的滑动窗口是它的实例，算法题中的双指针是它的简化， 限流器的滑动窗口计数是它的变体，Reactive Streams 的 request(n) 是它的信用形式。

为什么不直接用队列？

队列也能解耦 producer 和 consumer，但队列有两个问题：

• 无界队列：内存爆炸。当 producer 远快于 consumer 时，队列会无限增长。
• 有界队列：阻塞。当队列满时，producer 被迫阻塞等待。

滑动窗口提供了第三条路：不阻塞 producer，但限制其发送量。 Producer 可以持续发送，只要 in-flight 数据量不超过窗口大小。 当窗口耗尽时，producer 暂停；当收到 ACK 后，窗口滑动，producer 恢复。

这在网络环境中尤其重要，因为阻塞意味着 RTT 级别的等待，而滑动窗口允许流水线化发送。

二、TCP 滑动窗口：发送窗口与接收窗口

TCP 的滑动窗口是上述抽象模型最经典的实现。

发送端的四个区域

TCP 发送端维护的序列号空间可以分为四个区域：

|<--- 已确认 --->|<-- 已发送未确认 -->|<-- 可用窗口 -->|<--- 不可用 --->|
                 ^                    ^                ^
              SND.UNA             SND.NXT      SND.UNA+SND.WND

• 已确认（ACKed）：序号 < SND.UNA，数据已被接收端确认。
• 已发送未确认（Sent, Unacknowledged）：SND.UNA <= 序号 < SND.NXT，数据已发送但还没收到 ACK。
• 可用窗口（Usable Window）：SND.NXT <= 序号 < SND.UNA + SND.WND，允许发送但尚未发送。
• 不可用（Not Usable）：序号 >= SND.UNA + SND.WND，超出窗口范围，不允许发送。

其中：

SND.WND = min(cwnd, rwnd)

cwnd 是拥塞窗口（由拥塞控制算法决定），rwnd 是接收端通告的接收窗口。

接收端的窗口通告

接收端在每个 ACK 报文中携带 Window 字段（16 位，最大 65535 字节；配合 Window Scale 选项可扩展到 1 GB）， 告诉发送端”我还能接收多少字节”：

rwnd = RCV.BUFFER_SIZE - (RCV.NXT - 已交付给应用层的位置)

当应用层通过 read() 读走数据后，rwnd 增大；当接收缓冲区积压时，rwnd 减小。

Silly Window Syndrome

当接收端应用层每次只读取少量数据时，会出现一个病态情况：

1. 接收缓冲区几乎满了，rwnd 很小（比如 1 字节）。
2. 接收端发送 Window Update，通告 rwnd = 1。
3. 发送端发送 1 字节数据（加上 40 字节 TCP/IP 头部）。
4. 接收端又只读了 1 字节，再次通告 rwnd = 1。

每个有效载荷只有 1 字节，但头部开销是 40 字节，效率极低。这就是 Silly Window Syndrome。

解决方案（双管齐下）：

Nagle 算法的伪代码：

if (data_to_send >= MSS) {
    send_immediately();
} else if (no_unacked_data) {
    send_immediately();  /* 第一个小包立即发 */
} else {
    buffer_data();       /* 等待 ACK 到来后再发送 */
}

对于交互式应用（如 SSH），Nagle 算法会引入延迟，可以通过 TCP_NODELAY 选项禁用。

三、Go-Back-N 与 Selective Repeat：两种重传策略

滑动窗口协议有两种经典的错误恢复策略。它们在序列号空间利用率和接收端缓冲需求上有本质区别。

Go-Back-N（GBN）

核心规则：接收端只接受按序到达的帧。乱序帧直接丢弃。

发送端窗口大小: N（可同时在途 N 个帧）
接收端窗口大小: 1（只期望下一个按序帧）

序列号空间要求: seq_bits >= log2(N + 1)
  即序列号空间大小 > 窗口大小

优点：接收端实现简单，不需要缓冲乱序帧。

缺点：一个帧丢失，后续所有帧都要重传，即使它们已经正确到达。

Sender:  [0] [1] [2] [3] [4] [5]
              X                    <- 帧 1 丢失
Receiver: 0   -   -   -   -   -   <- 帧 2-5 全部丢弃
Timeout -> 重传: [1] [2] [3] [4] [5]

Selective Repeat（SR）

核心规则：接收端缓冲乱序帧，只请求重传丢失的帧。

发送端窗口大小: N
接收端窗口大小: N（需要缓冲区）

序列号空间要求: seq_bits >= log2(2N)
  即序列号空间大小 >= 2 * 窗口大小

序列号空间为什么要更大？因为发送端和接收端的窗口可能完全不重叠， 如果序列号空间不够大，新旧帧的序列号会混淆。

优点：带宽利用率高，只重传丢失的帧。

缺点：接收端需要更多缓冲区，实现更复杂。

Sender:  [0] [1] [2] [3] [4] [5]
              X                    <- 帧 1 丢失
Receiver: 0   -   2   3   4   5   <- 帧 2-5 缓冲
NAK(1) -> 重传: [1]
Receiver: 0  1  2  3  4  5        <- 帧 1 到达后，按序交付 1-5

TCP 的选择：SACK

TCP 默认行为类似 Go-Back-N（累积确认），但通过 SACK（Selective Acknowledgment）选项 支持 Selective Repeat 的优势：

ACK 报文中的 SACK 块:
  ACK = 4          (累积确认到 3)
  SACK: 6-8, 10-12 (告诉发送端 6-8, 10-12 已收到)
  
发送端只需重传: 4-5, 9

对比总结

四、算法中的滑动窗口：双指针与单调队列

从算法竞赛的角度看，滑动窗口是一类用双指针维护区间性质的技巧。 其核心思想与网络协议完全一致：维护一个满足约束条件的最大/最小区间。

双指针模板

经典的滑动窗口算法模板：

int sliding_window(int *arr, int n, int target) {
    int left = 0, right = 0;
    int window_state = 0;  /* 窗口内的某种聚合状态 */
    int result = 0;

    while (right < n) {
        /* 扩展窗口：加入 arr[right] */
        window_state = update_add(window_state, arr[right]);
        right++;

        /* 收缩窗口：当窗口不满足约束时 */
        while (!is_valid(window_state, target)) {
            window_state = update_remove(window_state, arr[left]);
            left++;
        }

        /* 更新答案 */
        result = max(result, right - left);
    }

    return result;
}

关键性质：left 和 right 都只向右移动，永不回退。因此总时间复杂度为 O(n)， 尽管看起来有两层循环。每个元素最多被加入窗口一次、移出窗口一次。

经典问题

问题 1：无重复字符的最长子串

int length_of_longest_substring(const char *s) {
    int freq[128] = {0};
    int left = 0, max_len = 0;
    int n = strlen(s);

    for (int right = 0; right < n; right++) {
        freq[(unsigned char)s[right]]++;

        while (freq[(unsigned char)s[right]] > 1) {
            freq[(unsigned char)s[left]]--;
            left++;
        }

        int current_len = right - left + 1;
        if (current_len > max_len) {
            max_len = current_len;
        }
    }

    return max_len;
}

问题 2：和大于等于 target 的最短子数组

int min_subarray_len(int target, int *nums, int n) {
    int left = 0;
    int sum = 0;
    int min_len = n + 1;

    for (int right = 0; right < n; right++) {
        sum += nums[right];

        while (sum >= target) {
            int current_len = right - left + 1;
            if (current_len < min_len) {
                min_len = current_len;
            }
            sum -= nums[left];
            left++;
        }
    }

    return min_len <= n ? min_len : 0;
}

与 TCP 的类比

五、单调队列：O(n) 滑动窗口最大值

滑动窗口最大值（LeetCode 239）是一个经典问题， 要求在 O(n) 时间内计算固定大小窗口内的最大值。

问题定义

给定数组 nums 和窗口大小 k，返回每个窗口位置的最大值。

输入: nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3
输出: [3, 3, 5, 5, 6, 7]

单调递减队列

关键洞察：如果 nums[i] >= nums[j] 且 i > j，那么在 i 存在于窗口中的时间内， j 永远不可能成为最大值。因此 j 可以安全地从候选集中移除。

维护一个双端队列（deque），存储元素的下标，保证队列中的元素值单调递减。

#include <stdio.h>
#include <stdlib.h>

void max_sliding_window(int *nums, int n, int k, int *result) {
    int *deque = (int *)malloc(n * sizeof(int));
    int front = 0, back = -1;

    for (int i = 0; i < n; i++) {
        /* 移除超出窗口范围的队头元素 */
        while (front <= back && deque[front] <= i - k) {
            front++;
        }

        /* 移除所有小于当前元素的队尾元素（维护单调递减） */
        while (front <= back && nums[deque[back]] <= nums[i]) {
            back--;
        }

        /* 当前元素入队 */
        deque[++back] = i;

        /* 窗口形成后，记录结果 */
        if (i >= k - 1) {
            result[i - k + 1] = nums[deque[front]];
        }
    }

    free(deque);
}

正确性证明

引理：在任意时刻，deque 中的元素下标严格递增，对应的值严格递减。

证明（归纳法）：

基础情况：空队列，性质平凡成立。

归纳步骤：假设处理 nums[i-1] 后队列满足单调性。处理 nums[i] 时：

1. 所有值 <= nums[i] 的队尾元素被弹出。设弹出后队尾元素为 deque[back]， 则 nums[deque[back]] > nums[i]（否则它也会被弹出）。
2. i 被插入队尾。由于 i > deque[back]（下标递增）且 nums[i] < nums[deque[back]]（值递减）， 单调性得以维持。

定理：队头元素始终是当前窗口的最大值。

证明：

1. 队头元素在窗口范围内（超出范围的已被移除）。
2. 设窗口内最大值为 nums[m]。如果 m 不在队列中，说明存在某个 j > m 使得 nums[j] >= nums[m]，m 被弹出。但这意味着 nums[j] >= nums[m]， 与 nums[m] 是最大值矛盾。因此 m 一定在队列中。
3. 由于队列单调递减，最大值一定在队头。

复杂度分析

• 时间复杂度：O(n)。每个元素最多入队一次、出队一次，总操作 2n 次。
• 空间复杂度：O(k)。队列中最多 k 个元素。

摊还分析：虽然内层 while 循环在最坏情况下可能处理多个元素， 但每个元素在其生命周期内只被插入和删除各一次。 因此总操作次数不超过 2n，平均每次操作 O(1)。

六、反压机制：Reactive Streams、gRPC、Kafka

反压（Backpressure）是滑动窗口思想在更高层级系统中的体现。 核心问题不变：当下游处理不过来时，如何让上游放慢速度？

Reactive Streams 的 request(n) 模型

Reactive Streams 规范定义了四个接口：

public interface Publisher<T> {
    void subscribe(Subscriber<? super T> s);
}

public interface Subscriber<T> {
    void onSubscribe(Subscription s);
    void onNext(T t);
    void onError(Throwable t);
    void onComplete();
}

public interface Subscription {
    void request(long n);  /* 关键：消费者请求 n 个元素 */
    void cancel();
}

request(n) 就是信用机制：消费者告诉生产者”我能处理 n 个元素”， 这等价于 TCP 接收端通告 rwnd。

Subscriber                Publisher
    |--- request(10) ------->|     "我的窗口大小是 10"
    |<--- onNext(item1) -----|
    |<--- onNext(item2) -----|
    |<--- ... (共 10 个) -----|
    |--- request(5) -------->|     "窗口又开了 5"
    |<--- onNext(item11) ----|
    |<--- ... --------------- |

这是一种纯粹的信用制（credit-based）流控，与 TCP 的窗口通告在本质上同构。

gRPC 流控

gRPC 底层使用 HTTP/2，继承了 HTTP/2 的流级别和连接级别双层流控：

连接级别 flow control window (默认 65535 字节)
  |
  +-- Stream 1 flow control window (默认 65535 字节)
  +-- Stream 2 flow control window
  +-- Stream 3 flow control window

发送端发送 DATA 帧时，同时消耗连接级别和流级别的窗口。 接收端通过 WINDOW_UPDATE 帧补充窗口：

WINDOW_UPDATE (stream_id=0, increment=32768)   <- 连接级别
WINDOW_UPDATE (stream_id=5, increment=16384)   <- 流级别

gRPC 的 Go 实现（grpc-go）中，默认的 BDP（Bandwidth Delay Product）估算器 会根据 RTT 和吞吐量动态调整窗口大小：

// 伪代码，简化自 grpc-go 的 bdp_estimator.go
func (e *bdpEstimator) calculate() int {
    bdp := e.bandwidth * e.rtt
    return clamp(bdp, minWindow, maxWindow)
}

Kafka Consumer Fetch

Kafka consumer 的 fetch.max.bytes 和 max.partition.fetch.bytes 构成了一种静态窗口：

FetchRequest:
  max_bytes: 52428800        (全局最大抓取量)
  partitions:
    - topic: orders
      partition: 0
      fetch_offset: 12345
      max_bytes: 1048576     (单分区最大抓取量)

消费者通过控制 fetch 频率和每次 fetch 的大小，间接实现了流控。 但这不是动态反压，而是一种预配置的窗口限制。

对比三种反压机制：

七、信用制流控：InfiniBand 与 RDMA

在高性能计算领域，InfiniBand 和 RDMA 网络使用信用制（credit-based）流控， 这是滑动窗口的一种变体。

基本原理

发送端维护信用计数器（credits），每发送一个消息消耗一个信用。 接收端处理完消息后，返还信用给发送端。

初始: sender_credits = receiver_buffer_count = 16

发送消息:
  if (sender_credits > 0) {
      send(msg);
      sender_credits--;
  } else {
      wait();  /* 等待信用返还 */
  }

接收处理:
  msg = recv();
  process(msg);
  send_credit_update(1);  /* 返还 1 个信用 */

与窗口流控的区别

InfiniBand 的链路层流控确保交换机和 HCA（Host Channel Adapter）之间不会丢包， 这是 RDMA 能够提供可靠传输的基础。在数据中心网络中， 类似的信用制流控也被 PFC（Priority Flow Control，IEEE 802.1Qbb）采用。

RDMA 的流控层次

应用层: Verb API (ibv_post_send / ibv_post_recv)
    |
传输层: QP (Queue Pair) 信用制
    |     - Send Queue / Receive Queue
    |     - 接收端必须预先 post receive buffers
    |     - 发送端的信用 = 接收端可用的 receive buffers
    |
链路层: Credit-based Flow Control
    |     - 每个虚拟通道 (VL) 独立的信用
    |     - 发送端在信用耗尽时暂停该 VL
    |
物理层: 信号

在 RDMA 编程中，“接收端没有 post 足够的 receive buffer”是最常见的性能问题之一，本质上就是窗口（信用）配置不当导致的发送端饥饿。

八、基于窗口的限流算法

限流（Rate Limiting）是滑动窗口思想在 API 网关和分布式系统中的应用。

固定窗口计数器

最简单的限流：将时间划分为固定长度的窗口，每个窗口内计数。

#include <time.h>
#include <stdbool.h>

typedef struct {
    int max_requests;
    int window_seconds;
    int current_count;
    time_t window_start;
} fixed_window_limiter_t;

void fixed_window_init(fixed_window_limiter_t *limiter, int max_req, int window_sec) {
    limiter->max_requests = max_req;
    limiter->window_seconds = window_sec;
    limiter->current_count = 0;
    limiter->window_start = time(NULL);
}

bool fixed_window_allow(fixed_window_limiter_t *limiter) {
    time_t now = time(NULL);

    if (now - limiter->window_start >= limiter->window_seconds) {
        limiter->window_start = now;
        limiter->current_count = 0;
    }

    if (limiter->current_count < limiter->max_requests) {
        limiter->current_count++;
        return true;
    }

    return false;
}

缺陷：窗口边界处的突刺问题。如果在窗口末尾和下一个窗口开头各发 N 个请求， 瞬间流量达到 2N，突破了限流目标。

滑动窗口日志

记录每个请求的精确时间戳，检查过去 T 秒内的请求数。

typedef struct {
    int max_requests;
    int window_seconds;
    double *timestamps;     /* 环形缓冲区 */
    int capacity;
    int head;
    int count;
} sliding_log_limiter_t;

bool sliding_log_allow(sliding_log_limiter_t *limiter, double now) {
    /* 移除过期的时间戳 */
    while (limiter->count > 0) {
        double oldest = limiter->timestamps[limiter->head];
        if (now - oldest > limiter->window_seconds) {
            limiter->head = (limiter->head + 1) % limiter->capacity;
            limiter->count--;
        } else {
            break;
        }
    }

    if (limiter->count < limiter->max_requests) {
        int tail = (limiter->head + limiter->count) % limiter->capacity;
        limiter->timestamps[tail] = now;
        limiter->count++;
        return true;
    }

    return false;
}

优点：精确，没有边界突刺。缺点：内存开销大，每个请求都要存时间戳。

滑动窗口计数器

结合固定窗口和滑动日志的折中方案。用两个相邻窗口的加权计数来近似：

typedef struct {
    int max_requests;
    int window_seconds;
    int prev_count;
    int curr_count;
    time_t curr_window_start;
} sliding_counter_limiter_t;

bool sliding_counter_allow(sliding_counter_limiter_t *limiter) {
    time_t now = time(NULL);
    time_t elapsed = now - limiter->curr_window_start;

    if (elapsed >= limiter->window_seconds) {
        limiter->prev_count = limiter->curr_count;
        limiter->curr_count = 0;
        limiter->curr_window_start = now;
        elapsed = 0;
    }

    /* 加权估算当前滑动窗口内的请求数 */
    double weight = 1.0 - ((double)elapsed / limiter->window_seconds);
    double estimated = limiter->prev_count * weight + limiter->curr_count;

    if (estimated < limiter->max_requests) {
        limiter->curr_count++;
        return true;
    }

    return false;
}

三种方案对比

在实际工程中，滑动窗口计数器是最常用的方案，因为它在精度和开销之间取得了最佳平衡。 Redis 的 ZRANGEBYSCORE 也可以实现滑动日志，但通常用在限流粒度较粗的场景。

九、完整 C 实现：TCP 滑动窗口协议模拟器

以下是一个约 200 行的 C 实现，模拟 TCP 风格的滑动窗口协议， 包含发送端、接收端、丢包模拟和窗口通告。

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#include <time.h>

/* ---------- 配置 ---------- */
#define MAX_SEQ         256
#define MAX_BUFFER      64
#define LOSS_PERCENT    20      /* 模拟 20% 丢包率 */
#define TOTAL_FRAMES    50      /* 总共发送 50 帧 */

/* ---------- 帧结构 ---------- */
typedef enum { DATA, ACK } frame_type_t;

typedef struct {
    frame_type_t type;
    int          seq;           /* DATA 帧的序列号 */
    int          ack;           /* ACK 帧的确认号 */
    int          rwnd;          /* 接收端通告的窗口大小 */
    char         payload[16];
} frame_t;

/* ---------- 发送端 ---------- */
typedef struct {
    int  snd_una;               /* 最早未确认 */
    int  snd_nxt;               /* 下一个要发送 */
    int  snd_wnd;               /* 发送窗口大小 */
    int  cwnd;                  /* 拥塞窗口（简化为固定值） */
    int  total_sent;            /* 已发送总数（非序列号回绕） */
    bool sent[MAX_SEQ];         /* 标记哪些序列号已发送未确认 */
    int  retry_count[MAX_SEQ];  /* 重传计数 */
} sender_t;

/* ---------- 接收端 ---------- */
typedef struct {
    int  rcv_nxt;               /* 期望接收的下一个序列号 */
    int  rcv_wnd;               /* 接收窗口大小 */
    int  buffer_size;           /* 接收缓冲区总大小 */
    int  buffered;              /* 当前缓冲的数据量 */
    bool received[MAX_SEQ];     /* 标记已收到的帧 */
    int  delivered;             /* 已交付应用层的帧数 */
} receiver_t;

/* ---------- 网络层（模拟丢包） ---------- */
static bool network_transmit(void) {
    return (rand() % 100) >= LOSS_PERCENT;
}

/* ---------- 初始化 ---------- */
static void sender_init(sender_t *s) {
    memset(s, 0, sizeof(*s));
    s->cwnd = 8;
    s->snd_wnd = 8;    /* 初始窗口 */
}

static void receiver_init(receiver_t *r) {
    memset(r, 0, sizeof(*r));
    r->buffer_size = 16;
    r->rcv_wnd = r->buffer_size;
}

/* ---------- 发送端：发送数据 ---------- */
static int sender_send(sender_t *s, frame_t *out_frames, int max_frames) {
    int effective_wnd = s->snd_wnd < s->cwnd ? s->snd_wnd : s->cwnd;
    int count = 0;

    while (count < max_frames && s->total_sent < TOTAL_FRAMES) {
        /* 检查窗口是否已满 */
        int inflight = (s->snd_nxt - s->snd_una + MAX_SEQ) % MAX_SEQ;
        if (inflight >= effective_wnd) {
            break;
        }

        int seq = s->snd_nxt % MAX_SEQ;
        out_frames[count].type = DATA;
        out_frames[count].seq  = seq;
        out_frames[count].ack  = -1;
        out_frames[count].rwnd = 0;
        snprintf(out_frames[count].payload, 16, "DATA-%03d", s->total_sent);

        s->sent[seq] = true;
        s->snd_nxt = (s->snd_nxt + 1) % MAX_SEQ;
        s->total_sent++;
        count++;
    }

    return count;
}

/* ---------- 发送端：处理 ACK ---------- */
static void sender_recv_ack(sender_t *s, const frame_t *ack_frame) {
    int ack_num = ack_frame->ack;
    int new_wnd = ack_frame->rwnd;

    /* 累积确认：ack_num 之前的所有帧都已确认 */
    while (s->snd_una != ack_num) {
        s->sent[s->snd_una] = false;
        s->retry_count[s->snd_una] = 0;
        s->snd_una = (s->snd_una + 1) % MAX_SEQ;
    }

    s->snd_wnd = new_wnd;

    if (new_wnd == 0) {
        printf("  [SENDER] Zero window! Will probe later.\n");
    }
}

/* ---------- 接收端：处理数据帧 ---------- */
static bool receiver_recv_data(receiver_t *r, const frame_t *data_frame,
                               frame_t *ack_out) {
    int seq = data_frame->seq;

    if (r->buffered >= r->buffer_size) {
        /* 缓冲区满，丢弃 */
        printf("  [RECEIVER] Buffer full, dropping seq=%d\n", seq);
        ack_out->type = ACK;
        ack_out->ack  = r->rcv_nxt;
        ack_out->rwnd = 0;
        return true;
    }

    if (!r->received[seq]) {
        r->received[seq] = true;
        r->buffered++;
        printf("  [RECEIVER] Buffered seq=%d (%s)\n",
               seq, data_frame->payload);
    }

    /* 推进 rcv_nxt：交付连续的帧给应用层 */
    while (r->received[r->rcv_nxt]) {
        r->received[r->rcv_nxt] = false;
        r->rcv_nxt = (r->rcv_nxt + 1) % MAX_SEQ;
        r->buffered--;
        r->delivered++;
    }

    /* 模拟应用层慢速读取：随机消费一些缓冲 */
    if (rand() % 3 == 0 && r->buffered > 0) {
        int consume = 1 + rand() % 2;
        if (consume > r->buffered) consume = r->buffered;
        r->buffered -= consume;
    }

    r->rcv_wnd = r->buffer_size - r->buffered;

    ack_out->type = ACK;
    ack_out->ack  = r->rcv_nxt;
    ack_out->rwnd = r->rcv_wnd;

    return true;
}

/* ---------- 主循环 ---------- */
int main(void) {
    srand((unsigned)time(NULL));

    sender_t   sender;
    receiver_t receiver;
    sender_init(&sender);
    receiver_init(&receiver);

    frame_t send_buf[MAX_BUFFER];
    frame_t ack_frame;
    int round = 0;

    printf("=== TCP Sliding Window Simulator ===\n");
    printf("Total frames: %d, Loss rate: %d%%, Buffer: %d\n\n",
           TOTAL_FRAMES, LOSS_PERCENT, receiver.buffer_size);

    while (receiver.delivered < TOTAL_FRAMES && round < 200) {
        round++;
        printf("--- Round %d (UNA=%d NXT=%d WND=%d delivered=%d) ---\n",
               round, sender.snd_una, sender.snd_nxt,
               sender.snd_wnd, receiver.delivered);

        /* 发送端发送 */
        int nsent = sender_send(&sender, send_buf, MAX_BUFFER);
        if (nsent == 0 && sender.snd_wnd > 0) {
            /* 可能需要重传：简单的超时重传 */
            printf("  [SENDER] Nothing new to send, triggering retransmit\n");
            int seq = sender.snd_una;
            send_buf[0].type = DATA;
            send_buf[0].seq  = seq;
            snprintf(send_buf[0].payload, 16, "RETR-%03d", seq);
            nsent = 1;
            sender.retry_count[seq]++;
        }

        /* 网络传输（可能丢包） */
        for (int i = 0; i < nsent; i++) {
            if (network_transmit()) {
                printf("  [NET] seq=%d delivered\n", send_buf[i].seq);
                if (receiver_recv_data(&receiver, &send_buf[i], &ack_frame)) {
                    /* ACK 也可能丢失 */
                    if (network_transmit()) {
                        printf("  [NET] ACK=%d rwnd=%d delivered\n",
                               ack_frame.ack, ack_frame.rwnd);
                        sender_recv_ack(&sender, &ack_frame);
                    } else {
                        printf("  [NET] ACK lost!\n");
                    }
                }
            } else {
                printf("  [NET] seq=%d LOST!\n", send_buf[i].seq);
            }
        }

        /* 零窗口探测 */
        if (sender.snd_wnd == 0) {
            printf("  [SENDER] Zero-window probe\n");
            frame_t probe = { .type = DATA, .seq = sender.snd_una };
            snprintf(probe.payload, 16, "PROBE");
            if (network_transmit()) {
                receiver_recv_data(&receiver, &probe, &ack_frame);
                if (network_transmit()) {
                    sender_recv_ack(&sender, &ack_frame);
                }
            }
        }
    }

    printf("\n=== Simulation Complete ===\n");
    printf("Rounds: %d, Delivered: %d/%d\n",
           round, receiver.delivered, TOTAL_FRAMES);

    return 0;
}

编译和运行：

gcc -O2 -Wall -o tcp_window tcp_window.c
./tcp_window

运行后可观察到丢包、重传、窗口缩小/恢复、零窗口探测等典型 TCP 行为。

十、真实世界中的窗口机制

TCP 零窗口探测

当接收端通告 rwnd = 0 时，发送端不能发送任何数据。 但如果接收端之后窗口打开了，它发送的 Window Update 可能丢失， 导致死锁：发送端等待窗口打开，接收端等待数据到来。

TCP 用零窗口探测（Zero Window Probe）打破死锁。发送端启动持续定时器（Persist Timer），超时后发送 1 字节探测报文。接收端回复 ACK 携带当前 rwnd。若 rwnd 仍为 0，定时器指数退避重试（最大 60 秒）；若 rwnd > 0，恢复正常发送。探测不受拥塞控制约束。

用 ss 或 tcpdump 可以观察零窗口：

# 观察零窗口情况
ss -tnoi | grep -E 'wscale|rcv_space'

# 抓包观察
tcpdump -i eth0 -nn 'tcp[14:2] = 0' -c 20

HTTP/2 流控

HTTP/2 在 TCP 之上引入了自己的流级别流控，理由是：

1. 多路复用：一个 TCP 连接承载多个流，需要流间的公平性。
2. 优先级：高优先级流不应被低优先级流阻塞。
3. 独立控制：每个流可以独立暂停和恢复。

HTTP/2 流控规则：

初始窗口: 65535 字节（SETTINGS_INITIAL_WINDOW_SIZE）
最大窗口: 2^31 - 1 字节

发送 DATA 帧:
  connection_window -= frame_size
  stream_window     -= frame_size
  两者都必须 >= 0

接收 WINDOW_UPDATE:
  if (stream_id == 0)
      connection_window += increment
  else
      stream_window[stream_id] += increment

HTTP/2 流控的一个微妙问题是：它与 TCP 的流控重叠。 如果 HTTP/2 层限制了发送速率，TCP 的拥塞窗口可能不必要地收缩， 导致窗口恢复时性能不佳。这是 QUIC 取消 TCP 的一个动机。

QUIC 的改进

QUIC 在 UDP 之上实现了自己的可靠传输，其流控设计吸取了 TCP 和 HTTP/2 的教训：

QUIC 流控层次:
  1. 流级别 (MAX_STREAM_DATA 帧)
  2. 连接级别 (MAX_DATA 帧)
  3. 流数量限制 (MAX_STREAMS 帧)

相比 HTTP/2 over TCP:
  - 无队头阻塞：一个流的丢包不影响其他流
  - 无 TCP 与应用层流控的重叠
  - 基于偏移量而非增量，更容易从丢包中恢复

QUIC 的流控帧示例：

MAX_STREAM_DATA (stream_id=4, max_data=131072)
  -> "流 4 最多可以发送到偏移 131072"

MAX_DATA (max_data=1048576)
  -> "整个连接总共最多发送到 1048576 字节"

十一、流控策略基准测试对比

不同流控策略在不同场景下表现差异巨大。以下是在 100 Mbps 链路上，使用 MSS=1460 字节的模拟对比（基于 BDP = Bandwidth * RTT 建模）：

Scenario: LAN, no loss (RTT=10ms, loss=0.0%)
Strategy              Tput(Mbps)      Lat(ms)      Retrans
--------              ---------       ------       -------
Stop-and-Wait                1.2         10.0            0
Go-Back-N (N=8)              9.3         10.0            0
Go-Back-N (N=32)            37.4         10.0            0
Selective Repeat            37.4         10.0            0
Credit-Based               100.0          5.0            0

Scenario: WAN, 5% loss (RTT=100ms, loss=5.0%)
Strategy              Tput(Mbps)      Lat(ms)      Retrans
--------              ---------       ------       -------
Stop-and-Wait                0.1        100.0         3424
Go-Back-N (N=8)              0.0        100.0       274.0k
Go-Back-N (N=32)             0.0        100.0         1.1M
Selective Repeat             3.6        100.0         3424
Credit-Based                97.5         50.0          342

1. Stop-and-Wait 吞吐极低，带宽利用率 = MSS / (带宽 * RTT)。
2. Go-Back-N 无丢包时尚可，但丢包导致批量重传，性能雪崩。
3. Selective Repeat 高丢包场景优势明显，只重传丢失帧。
4. Credit-Based 在数据中心无损网络中几乎跑满带宽。

BDP 与窗口大小的关系

一个关键公式：最优窗口大小 = 带宽 x 延迟乘积（BDP）。

BDP = Bandwidth * RTT

示例:
  100 Mbps, RTT = 10ms  -> BDP = 125 KB
  1 Gbps,   RTT = 100ms -> BDP = 12.5 MB
  10 Gbps,  RTT = 1ms   -> BDP = 1.25 MB

如果窗口 < BDP: 管道未满，带宽浪费
如果窗口 > BDP: 缓冲区积压，延迟增加
如果窗口 = BDP: 最优，管道恰好填满

十二、工程实践：陷阱与经验

常见陷阱表

序列号回绕的正确处理

TCP 使用 32 位序列号，在高速链路上可能在几分钟内回绕。正确的比较方式：

/* 错误：直接比较 */
if (seq_a < seq_b) { ... }  /* 回绕时失败 */

/* 正确：利用有符号差值 */
static inline bool seq_before(uint32_t a, uint32_t b) {
    return (int32_t)(a - b) < 0;
}

static inline bool seq_after(uint32_t a, uint32_t b) {
    return (int32_t)(a - b) > 0;
}

这个技巧利用了补码运算：当 a 和 b 的差值在 2^31 范围内时， 有符号差值能正确反映它们的先后关系。Linux 内核的 before() 和 after() 宏就是这样实现的。

关于窗口大小调优的个人看法

我在实际工作中观察到的几个经验：

第一，不要信默认值。 TCP 的默认窗口大小（65535 字节）在高延迟链路上远远不够。 Linux 的自动调优（tcp_rmem / tcp_wmem）大多数时候工作得很好， 但在容器环境中，宿主机的内核参数经常被忽略。 我见过不止一次，K8s pod 里跑的服务因为 net.core.rmem_max 太小而吞吐低下。

第二，双层流控是万恶之源。 HTTP/2 over TCP 的流控是著名的问题， QUIC 的出现部分是为了解决这个问题。在 gRPC 中， 如果你看到 transport: flow control: need X but window is Y 的日志， 通常意味着 HTTP/2 的流级别窗口耗尽了，而 TCP 层可能还有空间。 解决方案通常是调大 SETTINGS_INITIAL_WINDOW_SIZE。

第三，监控窗口比调优更重要。 与其花时间猜最优窗口大小，不如部署监控：

# 查看 TCP 窗口统计
ss -tnoi | awk '/wscale/ {print}'

# 查看内核自动调优范围
sysctl net.ipv4.tcp_rmem
# 输出: 4096  131072  6291456 (min default max)

# 查看拥塞窗口
ss -tnoi | grep -oP 'cwnd:\K\d+'

当你看到 rwnd 持续为 0 或 cwnd 反复震荡时，再去针对性调优。

第四，滑动窗口的思想比具体实现更重要。 无论是写限流中间件、设计消息队列的消费控制， 还是实现流式 RPC 的反压，核心模式都是一样的： 用一个有界的”在途”容量来解耦生产者和消费者，通过反馈信号动态调整。 理解了这个模式，面对任何具体技术都能快速找到切入点。

性能调优检查清单

在生产环境中排查窗口相关问题时，按以下顺序检查：

1. BDP 计算
   - 确认带宽和 RTT
   - 计算理论最优窗口: BDP = 带宽 * RTT
   - 检查实际窗口是否接近 BDP

2. 接收端
   - rmem_max 是否足够大？ (>= BDP)
   - 应用层读取是否及时？ (避免 rwnd 趋零)
   - 是否启用了 Window Scale？

3. 发送端
   - wmem_max 是否足够大？
   - 是否启用了 SACK？
   - Nagle 与 TCP_NODELAY 的取舍

4. 网络
   - 中间设备是否修改了 Window Scale？
   - 是否存在 TCP offload 问题？
   - MTU 是否最优？ (Jumbo frames in DC)

5. 应用层
   - HTTP/2 初始窗口大小
   - gRPC keepalive 设置
   - 是否存在应用层的无意限流？

总结

滑动窗口是计算机科学中最优雅的抽象之一。它用极简的机制解决了一个普遍的问题： 在异步、不可靠的环境中，如何安全高效地传递数据。

从 TCP 的字节级窗口到 Reactive Streams 的元素级信用， 从 InfiniBand 的无损链路到 API 网关的限流计数器， 滑动窗口的形式千变万化，但内核始终如一： 一个有界的在途容量，一个动态的反馈信号，一个滑动的确认边界。

理解这个模式，你就理解了流控的本质。

上一篇: TCP 拥塞控制 下一篇: 限流算法

相关阅读: - TCP 拥塞控制 - MPMC Channel