Lab Checkpoint 0: networking warmup 直接写了 Markdown 以记录 Networking by hand 的部分， 另外完成了 ByteStream 部分的框架。 而看完 Lab1 的实验要求之后， 感觉需要具体分析并厘清思路， 故而在此做一个详细的记录。
Kiprey 2021 年的 Lab1 的记录给予了我帮助和启发。
该实验通过打印信息进行调试会更有效， 可以自己在
test文件中增加自己的测试样例。
- CS144 Spring 2023 实验仓库 CS144/minnow， 备份为 HangX-Ma/minnow 进行版本回退即可。
- CS144 Spring 2023 Lab1 项目指导书 - Lab Checkpoint 1: stitching substrings into a byte stream
- 具体的项目实现在个人的 Github。
1. 实验说明
CS144 Labs'structure
Lab1 的实验需要完成 ByteStream 外部的 StreamReassembler 部分。 Transmission Control Protocol (TCP) 的传输实现是一种可靠的顺序字节流， 尽管底层网络是以 “best effort” 的形式在进行报文的传输。 这意味着在报文传输的过程中， 数据包中的信息很可能会丢失、 重排、 替换、 或者重复。 这需要 TCP 为数据包提供可靠的底层逻辑。
TCP 的发送端会将字节流分割成短的 segments， 因此这些数据能够契合报文的容量需求。 但正如前述所说， 底层网络可能会使得这些 segments 变得不那么可靠， 因而 StreamReassembler 部分需要实现的， 就是在发送端确保发送的数据是连续的字节流。
2. 要求
StreamReassembler 需要遵循一定的规则。 starter code 中提供了两个公有函数对接口进行了一定的限制。
// Insert a new substring to be reassembled into a ByteStream.
void insert( uint64_t first_index, std::string data,
bool is_last_substring, Writer& output );
// How many bytes are stored in the Reassembler itself?
uint64_t bytes_pending() const;
另外， 根据实验说明， 原则上 Reassembler 需要处理以下几种情况：
- 获取的字节流正好是
ByteStream所需的下一组字节， 需要将这些字节直接用Writer写入到ByteStream的缓存中。 ByteStream很有可能也会存满， 此时若有一部分字节完成Reassembler处理需要传递给ByteStream， 则该部分也需要缓存， 实际上就是该部分也需要占用Reassembler内部的缓存空间， 这个内部的缓存空间就是 unassembled 的部分。- 当收到的字节流能够符合当前的空余空间但在在其更早的字节却不存在的时候 （也就是数据传输产生了空洞， 不连续） 需要将当前收到的字节流在
Reassembler中进行缓存。 Reassembler会丢弃那些超出当前空余空间的字节。 并且， 传入Reassembler中的子列 （substring） 可能会存在重复以及重叠， 或者有一部分已经被存入ByteStream的缓存中， 这些情况都需要考虑并进行处理。
关于存储空间指导书给了下图的提示。
Memory usage limitation of Reassembler and ByteStream
Reassembler 与 ByteStream 的内存上限是之前 Lab0 中规定的 capacity 的大小。 对于 Reassembler 而言， capacity = first_unacceptable_index - first_unpopped_index。 ByteStream 相对于 Reassembler 更为底层， 位于网络收发的端口， 负责实际的收发工作。 所以对于途中的几个 first 开头的索引其具备如下含义：
first_unpopped_index： 已经排序整理且验证正确的部分的起始索引， 这部分（绿色区块）存储在ByteStream的缓存中等待发送。first_unassembled_index： 尚未排序的整理验证的部分， 可称其为子列 （substrings）的起始索引， 这部分（红色区块）存储在Reassembler的内部缓存区域。first_unacceptable_index： 需要被丢弃的部分的起始索引。
3. 实现思路
依据 Memory usage limitation of Reassembler and ByteStream 图中所示的几个 index， 其中最为关键的两个应当是 first_unpopped_index 和 first_unacceptable_index。 框架程序提供的两个方法函数是不够用的， 我们需要定义几个私有变量以便存储关键信息：
unassembled_index_： 表示first_unassembled_index。unassembled_substrings_： 表示 unassembled 部分的缓存集， 为 map 类型， 可以将存储的 first_index 与其对应的 data 进行映射， 并提高查找速度。is_closed_： 表示接受端已收到最后一节 substring， 并且pending_buffer_也已清空， 此时应当终止此次数据的接收。
另外也对框架代码所给的两个函数的变量与功能进行说明：
-
insert
void insert( uint64_t first_index, std::string data, bool is_last_substring, Writer& output );传输 substring 至
ByteStream的主体方法， 包含大部分逻辑实现。first_index： substring 数据的第一个 index， 需要和上述unassembled_index_进行区分。data： 需要进行传输的 substring 数据。is_last_substring： 最后一条 substring 的标志变量。output：ByteStream中实现的Writer类， 将数据写入（push）传输缓存， 这部分信息会被远端的Reader类导出(pop)接收。
-
bytes_pending
uint64_t bytes_pending() const;剩余仍存留在
unassembler缓存部分的数据大小， 该部分和[first_unassembled_index, first_unacceptable_index]区间的available_capability毫无关系， 需要区分。available_capability表示当前能够接收的substring最大的大小。
3.0 符号说明与特殊处理
符号说明
- 重叠部分： 以
=表示子列和存于unassembled_substrings_中或已传入ByteStream中的数据重叠的 index。 - 当前数据： 以
>表示当前数据。 - front数据： 以
F表示与当前数据最邻近的保存在unassembled_substrings_中的那段数据， 这段数据的 first_index 比当前传入数据的 first_index 要小。 - rear数据： 以
R表示与当前数据最邻近的保存在unassembled_substrings_中的那段数据， 这段数据的 first_index 比当前传入数据的 first_index 要大。
特殊情况
对于特殊情况可以跳过后续繁琐的处理逻辑， 加快处理速度。 对于传入的 substring 而言， 有如下几种特殊情况可以跳过处理直接返回：
- 数据重复， 这意味着
first_index + data.size() - 1 < unassembled_index_， 传入的 substring 已经是ByteStream的一部分， 无需重复传输数据。 - 缓存不足，
first_index_ >= unassembled_substrings_ + available_capability， 相当于first_index处于first_unacceptable_index之后的区间， 意味着该 substring 需要被丢弃。 或者available_capability == 0， 此时已经没有空间用于处理。 - 空子列， substring 传入的 data 的大小为零。
3.1 unassembled_index_ >= first_index
这意味着此时传入的 substring 的一部分是已经传入 ByteStream 中的， 或者全都已经传入了 ByteStream。 还有可能有一部分和已经在 unassembled_substrings_ 中缓存的数据重叠， 那么重叠的部分就需要被丢弃。
-
部分重叠
这种情况和有
rear部分的处理会差不多， 所以在代码实现上做了整合， 实时细节在 3.2 节讨论， 唯一有区别的就是在此时需要截断[first_index, unassembled_index_]之间的数据。进行截断后的数据是从
unassembled_index起始的， 需要检查截断后的 data 的长度， 若截断后的 data 的长度超过了 available_capability 那么需要取min(data.size() - overlapped_length, available_capability())。first_index unassembled_index_ v v REPEATED_IN_MAP --------+----------------+-----------+---+------+------ |================|>>>>>>>>>>>|===|RRRRRR| --------+----------------+-----------+---+------+------ ^ first_index + data.size() - 1first_index unassembled_index_ v v REPEATED_IN_MAP --------+----------------+-----------+---+------+------ |================|>>>>>>>>>>>|===|>>>>>>| --------+----------------+-----------+---+------+------ ^ first_index + data.size() - 1 -
全部重叠
这种情况是部分重叠的特殊子集， 已经在特殊情况中处理掉了。
first_index unassembled_index_ v v --------+-------------------+-------------------------- |===================| ... --------+-------------------+-------------------------- ^ first_index + data.size() - 1
3.2 unassembled_index_ < first_index
在 unassembled_substrings_ 中的数据有些是连续的， 有些则不是连续的， 我们在保存数据的时候是以当前要保存的 data 与该 data 的 first_index 值进行映射的。 那么， 最复杂的情况是， 当前的这段数据正好恰在两段已缓存在 unassembled_substrings_ 之间。 这种情况也是需要进行数据截断的， 当前数据可能会超出最大索引值的范围， 这种情况发生在 first_index + data.size() - 1 > unassembled_index_ + cap - 1 的时候。
-
讨论传入数据的 first_index 比保存在
unassembled_substrings_中最邻近的数据的 fisrt_index 小的那部分数据。 可将 index 值较大段的数据称为_rear_index_， 当前数据的 index 仍称作 first_index。 可通过map::lower_bound(first_index)获取大于等于first_index的迭代器。-
没有重叠
则当前的 substring 可以直接保存在
unassembled_substrings_中， 无需做额外的处理， 判断first_index + data.size() - 1 < rear_index即可。first_index rear_index v v ----------------------- +----+-------+-------------------+----------------- |>>>>| |RRRRRRRRRRRRRRRRRRR| ... ----------------------- +----+-------+-------------------+----------------- ^ ^ first_index + data.size() - 1 rear_index + rear_data.size() - 1 -
部分重叠， 与 3.1 节中的情况类似， 需要截断当前的 substring 重复的部分即可， 若截断
rear部分重复的数据， 则还需要重新更新unassemble_substrings_， 效率不高。 需要满足first_index + data.size() - 1 < rear_index + rear_data.size() - 1的条件， 否则就会变成全部重叠的情况。 此时的重叠部分长度就是first_index + data.size() - rear_index。first_index rear_index v v ----------------+-----------+-------+-----------------------+------------- |>>>>>>>>>>>|=======|RRRRRRRRRRRRRRRRRRRRRRR| ... ----------------+-----------+-------+-----------------------+------------- ^ ^ first_index + data.size() - 1 rear_index + rear_data.size() - 1 -
全部重叠 以
rear存在全部重叠为例， 这种情况就直接将rear从unassembled_substrings_中移除即可。需要注意处理完一个最邻近的 substring 后， 可能新的最邻近的 substring 也需要进行处理， 这一般发生在 substring 产生全部重叠的时候， 这能确保当前保存的 substring 的正确性。 更新迭代器时需要更新为
map::lower_bound(rear_index + rear_data.size() - 1)， 才能跨过当前的rear找到next_rear继续进行处理，next_rear也可能还在当前的 data 的覆盖范围。
first_index rear_index v v ----------------+-----------+-------+------------+---+------+------------- |>>>>>>>>>>>|=======|>>>>>>>>>>>>?????>>>>>>| ... ----------------+-----------+-------+------------+---+------+------------- ^ ^ rear_index + rear_data.size() - 1 first_index + data.size() - 1 -
-
讨论当前传入数据与保存在
unassembled_substrings_中 first_index 比当前数据的 first_index 小的最邻近那部分数据的关系。 可将 index 较小段的数据称为 front_index， 当前数据的 index 仍称作first_index。 与rear不同的是， 最多只有一个front数据存在。 若map::lower_bound(first_index)得到的迭代器不是unassembled_substrings_的头部， 说明存在front， 只需要将该位置所在的迭代器向前更新一步即可。 相较从头向后扫描查找与front重叠， 这种办法仅需一次操作即可完成。-
没有重叠
则当前的 substring 可以直接保存在
unassembled_substrings_中， 无需做额外的处理。unassembled_index_ front_index first_index v v v --------+--------------+----+-------+-------------------+----------------- | |FFFF| |>>>>>>>>>>>>>>>>>>>| ... --------+--------------+----+-------+-------------------+----------------- ^ ^ front_index + front_data.size() - 1 first_index + data.size() - 1 -
部分重叠
与 3.1 节中的情况类似， 只需要截断当前的 substring 重复的部分即可， 也可以截断
front重复的部分。unassembled_index_ front_index first_index v v v --------+--------------+------------+---+---------------+----------------- | |FFFFFFFFFFFF|===|>>>>>>>>>>>>>>>| ... --------+--------------+------------+---+---------------+----------------- ^ ^ first_index + data.size() - 1 front_index + front_data.size() - 1 -
全部重叠
此时的处理会和
rear部分有所区别， 调用erase处理 data 时是从前向后， 而rear是从后向前。front_index first_index v v ----------------+-----------+-------+-----------------------+------------- |FFFFFFFFFFF|=======|FFFFFFFFFFFFFFFFFFFFFFF| ... ----------------+-----------+-------+-----------------------+------------- ^ ^ first_index + data.size() - 1 front_index + front_data.size() - 1
-
3.3 补充
最后将数据加入 map 缓存的时候需要特别判断 data.size() > 0， 因为在之前的处理中很可能 data 已经没有实际数据存在了， 这样就不需要将这部分数据放到 map 结构中。 除此之外， 在调用 output.push 的时候需要判断前后的 output.bytes_pushed 的情况， 很可能有一部分数据并没有被传入 ByteStream 的缓存中， 需要我们手动将这部分数据再保存在 map 中， 但不要忘了调用 erase 将之前的 push 不完整的那段数据从 map 中删除。 在遍历 map 查找可以传入 ByteStream 的数据的时候， 一旦发现 unassembled_index 和获取的 sub_index 不一致了， 就可以直接跳出循环， 这意味着数据已经不连续了， 没有必要继续数据传递的进程了。
reassembler_win.cc测试不通过， 可能是迭代器更新不对， 以及lower_bound可能用了upper_bound没找到对应的位置。reassembler_speed_test.cc测试发现读取和写入数据不一致， 可能就是没有考虑 push 时仅有一部分数据被传入了ByteStream而导致数据丢失。
4. 测试结果
cs144@cs144-ubuntu22:~/cs144-sp23/minnow$ cmake --build build --target check1
Test project /home/cs144/cs144-sp23/minnow/build
Start 1: compile with bug-checkers
1/17 Test #1: compile with bug-checkers ........ Passed 4.03 sec
Start 3: byte_stream_basics
2/17 Test #3: byte_stream_basics ............... Passed 0.02 sec
Start 4: byte_stream_capacity
3/17 Test #4: byte_stream_capacity ............. Passed 0.03 sec
Start 5: byte_stream_one_write
4/17 Test #5: byte_stream_one_write ............ Passed 0.03 sec
Start 6: byte_stream_two_writes
5/17 Test #6: byte_stream_two_writes ........... Passed 0.02 sec
Start 7: byte_stream_many_writes
6/17 Test #7: byte_stream_many_writes .......... Passed 0.06 sec
Start 8: byte_stream_stress_test
7/17 Test #8: byte_stream_stress_test .......... Passed 0.03 sec
Start 9: reassembler_single
8/17 Test #9: reassembler_single ............... Passed 0.02 sec
Start 10: reassembler_cap
9/17 Test #10: reassembler_cap .................. Passed 0.02 sec
Start 11: reassembler_seq
10/17 Test #11: reassembler_seq .................. Passed 0.03 sec
Start 12: reassembler_dup
11/17 Test #12: reassembler_dup .................. Passed 0.04 sec
Start 13: reassembler_holes
12/17 Test #13: reassembler_holes ................ Passed 0.02 sec
Start 14: reassembler_overlapping
13/17 Test #14: reassembler_overlapping .......... Passed 0.02 sec
Start 15: reassembler_win
14/17 Test #15: reassembler_win .................. Passed 0.30 sec
Start 16: compile with optimization
15/17 Test #16: compile with optimization ........ Passed 1.57 sec
Start 17: byte_stream_speed_test
ByteStream throughput: 2.26 Gbit/s
16/17 Test #17: byte_stream_speed_test ........... Passed 0.25 sec
Start 18: reassembler_speed_test
Reassembler throughput: 8.10 Gbit/s
17/17 Test #18: reassembler_speed_test ........... Passed 0.36 sec
100% tests passed, 0 tests failed out of 17
Total Test time (real) = 6.87 sec
Built target check1