Lab Checkpoint 3: the TCP sender

2 Checkpoint 3: The TCP Sender

​ Lab3 将实现 TCP 中的 TCPSender，其需要完成的功能有：

• 跟踪 Receiver 的 TCPReceiverMessage 信息（acknos 和 window sizes），通过将 ByteStream 的数据以 TCP Segments 的格式不断发送，尽可能地填满 window， 直到 window 满了或者 ByteStream 中没有任何东西可以发送。
• 跟踪那些已发送但还没有被接收的 segments， 通常将这些数据被称为 “outstanding” segments。
• 若是这些 segments 在足够长的时间后没有没接收， 则重传这些 segments 数据。

​ 这些功能实现了 “automatic repeat request (ARQ)” 机制，TCPSender 的任务就是确保 TCPReceiver 能收到每个字节至少一次。

Lab Checkpoint 2: the TCP receiver

​ Lab2 将实现 TCP 协议的 TCPReceiver，通过 receive() 函数从 peer 端接收数据， 经过 Reassembler 处理写入 ByteStream 缓存， 应用层就可以通过 TCPSocket 读取数据。

​ 在接收 peer 端数据的同时， TCPReceiver 通过 send() 函数承担着告知 peer 一些重要信息的职责， 这些信息包括这两个部分：

• Acknowledgment: first_unassembled_index 又称 **ackno**， 是 TCPReceiver 从 peer 发送端希望收到的 第一个字节的索引号。
• Flow Control: **window size**， 是 ByteStream 可以写入的剩余空间， 限制了 TCPSender 发送数据的 index 的实际范围。 通过这个 window， TCPReceiver 能够 对输入的数据流量进行控制， 限制发送端的数据直到接收端准备好继续接收。

通常将 ackno 称作 window 的索引左边界 （Smallest Index）， 将 ackno + window size 称作 window 的索引右边界 （Largest Index）

Lab Checkpoint 1: stitching substrings into a byte stream

0. Overview

​ 由于底层网络是以 “best effort” 的形式在进行数据报 (datagram) 的传输，意味着在数据包传输的过程中，很可能会发生丢失、 重复、乱序或者被替换的现象，因此需要 TCP 为数据包提供可靠的底层逻辑。Lab1 的实验需要完成 ByteStream 外部的 StreamReassembler 部分。

Lab Checkpoint 0: networking warmup

1. Set up GNU/Linux on your computer

CS144 的任务需要 GNU/Linux 操作系统和一个支持 C++ 2020 标准的 C++ 编译器（非常激进 … ）

我的运行环境：ubuntu-22.04.3 with g++ 13.2.0

PJ——索引调优

1、任务要求

• 阅读材料：J. M. Hellerstein, J. F. Naughton, A. Pfeffer. Generalized Search Trees for Database Systems. In VLDB 1995.

• 背景描述：GiST 的意思是通用的搜索树（Generalized Search Tree），它是一种平衡树结构的访问方法，在系统中作为一个基本模版，可以使用它实现任意索引模式。B-trees、R-trees和许多其它的索引模式都可以用 GiST 实现。

• 作业要求：

  1. 阅读材料的简要阅读报告 (pdf)

  2. 索引实践报告（二选一）

     1. 对PG代码中的Gist使用性能进行分析，并形成报告 (pdf)
        • PG支持快速造数据，数据量建议百万条及以上
        • 主要为 Gist，B-trees，R-trees，RD-trees之间的性能比较分析，参考「参考材料2」
     2. 用PG中的Gist实现一类索引，并形成报告 (pdf, source codes)
        • 可选索引：B+trees，Hash，倒排索引
        • 实现规范参见「参考材料3」
        • 源码组织类似「参考材料4」即可，包含测试和README

  3. README，标明小组人员及分工表

  • 以上所有文件压缩在一个zip文件内，文件名「姓名1_学号1，姓名2 _学号2….zip」
  • 推荐使用PostgreSQL 14.x Linux

• 参考材料

  1. PostgreSQL: Documentation: 14: F.7. btree_gist
  2. PostgreSQL索引(5) – GiST – PostgreSQL数据库内核探究 (mengqingzhong.com)
  3. PostgreSQL: Documentation: 14: 65.3. Extensibility
  4. jinyyu/tlsh_gist (github.com)

• 附加说明

  • 小组/个人作业，每组提交一份文件，每组成员得分相同

  • 四个作业之一，取已做作业中的最高分作为作业得分

  • 本次作业结束后可换组