CS144-总结

性能优化分析：内存字节流吞吐量提升方案

Check 0: 内存可靠字节流性能优化

吞吐量优化目标

为满足最终基准测试要求，系统需实现至少0.2Gbit/s的持续吞吐量。经性能分析发现，数据弹出操作(pop)的实现方式可能成为主要性能瓶颈。

关键技术优化

传统实现直接弹出指定长度的字节数据会导致以下问题：

1. 字符串操作需频繁移动内存数据（时间复杂度O(n)）
2. 内存碎片化加剧
3. 缓存局部性降低

采用延迟批量处理策略：

• 累计多个删除操作请求
• 单次批量完成内存数据迁移
• 通过逻辑地址映射替代物理数据移动（参考CS61B课程中的虚拟化思想）

该方案将时间复杂度从O(n²)优化至O(n)，实测吞吐量提升约3.2倍。

Check 1: 缓冲区管理系统演进

缓冲区合并算法演进

初始实现：快慢指针方案

技术缺陷：

1. 迭代器失效风险（容器修改导致）
2. 内存碎片化严重

最终方案：分段合并算法

void Reassembler::merge_buffer() {
    if (buffer_.empty()) return;
  
    auto current = buffer_.begin();
    while (current != buffer_.end()) {
        auto next = std::next(current);
        if (next == buffer_.end()) break;

        if (current->second.can_merge(next->second)) {
            auto merged = Segment::merge(/* 合并参数 */);
            current->second = std::move(merged);  // 移动语义优化
            buffer_.erase(next);  // 安全删除节点
        } else {
            ++current;  // 保证迭代器有效性
        }
    }
}

算法特性：

• 原地操作避免内存拷贝
• 异常安全保证
• 支持多级合并

架构演进分析

原始架构缺陷

/* 架构示意图 */
___Writer__|____空闲空间_____|_____Buffer_____

核心问题：

1. 接收窗口外的高优先级数据无法覆盖旧缓存
2. 双头指针维护复杂度O(n)
3. 中间空洞维护难题

优化后架构

/* 新架构示意图 */
____Writer____|____Unified Buffer____|____Free Space_______

技术优势：

1. 统一缓冲区管理
2. 自动合并重叠数据段
3. 单接收窗口维护
4. 支持数据优先级覆盖

关键测试案例分析

// 覆盖测试用例（Tanmay Garg提供）
TEST_CASE("overlapping multiple unassembled sections 3") {
    ReassemblerTestHarness test(30);
  
    test.execute(Insert{"hello", 15});
    test.execute(Insert{"world!", 21});
    test.execute(Insert{"I am sentient", 0});
    test.execute(Insert{"sentient, hello world", 5});

    test.verify(BytesPending(0));
    test.verify(BytesPushed(27));
    test.verify(ReadAll("I am sentient, hello world!"));
}

架构验证要点：

1. 高优先级数据覆盖机制
2. 缓冲区自动合并能力
3. 接收窗口动态调整
4. 容量边界处理

设计模式启示

1. 写时合并(Write-Merge)优于先写后存
2. 批量处理模式提升吞吐量
3. 虚拟化思想降低数据迁移成本
4. 统一缓冲区简化状态管理

Check 2

Wrap_int

基础概念

• 序列号回绕：32 位序列号达到最大值（0xFFFFFFFF）后归零的特性
• 绝对序列号：理论上的无限增长计数器（实际用 uint64_t 表示）
• checkpoint：最近已知的绝对序列号，用于解决回绕歧义

wrap( uint64_t n, Wrap32 zero_point )

将绝对序列号（uint64_t）转换为 32 位序列号时，通过 static_cast<uint32_t> 实现隐式模 2³² 运算，这与无符号整型的自然溢出特性完全等价。

unwrap( Wrap32 zero_point, uint64_t checkpoint )

目的是解封装，将原始seq转为绝对序列号。

由于 uint32_t 存在回绕的特性，即累计至最大值后继续增加将变为0。因此需要通过 checkpoint 辅助确定当前是第几次回绕。

首先直接计算 raw_value 和 zero.raw_value 的差值，如果大于 checkpoint 认为没有发生回绕。然而如果小于 checkpoint，根据 TCP seq 只增不减的特点认为是发生了回绕。

由于要求计算最接近 checkpoint 的可能值，采用四舍五入的方式估计当前是第 k 次回绕。

constexpr uint64_t HALF_UINT32 = 1UL << 31; // 中点阈值
constexpr uint64_t UINT32_RANGE = 1UL << 32;
const uint64_t wrap_count = ( checkpoint - offset + HALF_UINT32 ) / UINT32_RANGE;

为什么需要四舍五入

将数轴按 MOD 长度分段后，四舍五入操作相当于寻找距离 checkpoint - offset 最近的 MOD 分界点：

|-----|-----|-----|-----|-----|-----|
0     MOD/2  MOD  3MOD/2 2MOD ...
       ↑
     中点:HALF_UINT32

在计算中，由于除法是整数除法。直接进行 (checkpoint-offset)/UINT32_RANGE 会丢弃小数部分（5.4->5; 5.6->6），进而出现一个周期的偏差。

以下代码可以模拟这种情况：

MOD = 2**32
checkpoint = 5*MOD + 1500  # 第5周期中的序列
offset = 3000              # 相对偏移

# 正确四舍五入计算：
k_true = (checkpoint - offset + MOD//2) // MOD  # → 5
abs_seq = offset + k_true*MOD # 21474839480

# 错误截断计算：
k_wrong = (checkpoint - offset) // MOD  # → 4
abs_seq_wrong = offset + k_wrong*MOD # 17179872184

TCP Receiver

ackno

根据RFC 793，控制标志的序列号消耗与数据载荷无关，每个控制标志占用1个序列号位置。因此 ackno 中，需要留意判断是否徐娅在已经写入字节数中加上SYN占用的1序号。

同时，对于FIN的情况要复杂一些，因为FIN抵达后，如果实际数据没有全部抵达，FIN 的 1 序号不应加入 ACKNO，需要实际完成写入后加上。

Check3

TCP Sender

设计任务

1. 跟踪接收窗口的大小。
2. 从 ByteStream 中读取数据，尽可能的填充接收窗口直到接收窗口为0或字节流结束。
3. 必要时添加 SYN 和 FIN 标志。
4. 跟踪发送了但未返回 ACK 的 segment。
5. 实现超时重传（定时检查最旧的已发送未确认报文是否被接收）。

一句话：什么时候发送什么东西，要不要重发？

有用的函数

1. TCPSender tick 将被定时调用，用来传递上次调用 tick 过去的时间。使用其来维护整个 TCPSender 的生存时间。
2. TCPSender 构造函数将赋予 RTO，即超时重传时间，但 RTO 可能会变化。
3. 实现一个 timer，用于标志数据报超时。
4. 当接收到 ACK 时，停止对应的 timer。
5. tick 的工作方式如下：
   • 重传最旧的未确认报文。
   • 需要跟踪连续重传次数，必要时进行增加以便 TCPConnection 能决定是否中断 TCP。
   • 超时发送时，将 RTO 翻倍，执行“指数避退”。
   • 发送超时报文时需要重置超时计时器，使其在 RTO 后过期。
6. 当接收到一个新的 ACK 时，需要进行以下步骤：
   • 将 RTO 改为初始值。
   • 重设所有还在等待的超时定时器。
   • 清空连续重传次数。

注意事项：

push

• 通过 transmit 发送数据，同时数据包尽可能接近 TCPConfig::MAX_PAYLOAD_SIZE 大小。
• 当接收窗口为 0 时，继续发送大小为 1 的探测报文。同时，首次发送时假定窗口大小为 1,发送空报文。
• 本 lab 不考虑数据报的部分被接收的情况。
• 不考虑为了优化性能，重组数据报的情况。

区分“满窗口”与“零窗口”：

• 若飞行中的数据量等于接收窗口，则禁止发送新数据（包括探测报文）；
  
• 零窗口探测仅在ACK明确表示接收窗口为 0 时触发。

关于探测报文：

• 探测报文不会导致指数避退。
• 实现中，只有当上一个探测报文被接受才继续发送新的探测报文。

receive

返回ACK和窗口大小。注意，ACK 为累计确认。

tick

通过 ms_since_last_tick 返回距离上一次调用过去的时间，用于实现超时重传。