Research Tips

6.NULL: The Missing Semester of Your CS Education

6.NULL: The Missing Semester of Your CS Education 原课程总结 几个简单的命令： 文件导航：Windows 和 unix-like system 之间存在一定的区别 cd/cp/mv/rm/mkdir/ls 使用重定向过程中需要注意权限问题： $ sudo find -L /sys/class/backlight -maxdepth 2 -name '*brightness*' /sys/class/backlight/thinkpad_screen/brightness $ cd /sys/class/backlight/thinkpad_screen $ sudo echo 3 > brightness An error occurred while redirecting file 'brightness' open: Permission denied echo 等程序并不知道 | 的存在，它们只知道从自己的输入输出流中进行读写。

https://blog.shunzi.tech/post/6.NULL/

生产力工具

Text Editor / IDE

• Vim

• vscode - remote ssh
• nmap / ncat / git-bash proxy
• server: runing sshd daemon
• strong password or use ssh key to login
• frp
• frp-server
• VPN / Reverse Proxy

Terminal

• xshell / git-bash / windows terminal / mac iTerm…

• zsh / bash / sh / fish

• tmux / screen

• keyboard shortcuts:
The Best Keyboard Shortcuts for Bash (aka the Linux and macOS Terminal)
Bash is the default command-line shell on most Linux distributions, from Ubuntu and Debian to Red Hat and Fedora. Bash is also the default shell included with macOS, and you can install a Linux-based bash environment on Windows 10. The bash shell features a wide variety of keyboard shortcuts you can use.

https://www.howtogeek.com/howto/ubuntu/keyboard-shortcuts-for-bash-command-shell-for-ubuntu-debian-suse-redhat-linux-etc/

CLI & Shell

• Package mananger:
• apt, dpkg (ubuntu, Debian) - .deb
• brew (macOS)
• dnf (fedora) - .rpm
• yum (centos) - .rpm

• Install from source
• README/INSTALL doc
• configure / make install

• Communication: Pipe & Redirect
• Pipe: |
• Redirect: >>, >, <

• Commands: ag, awk, sed
• -help
• man [command]
• https://command-not-found.com/
• TLDR https://tldr.sh/
• Common commands recorded by ourselves
• https://github.com/zjs1224522500/BlogIssue/issues/17

Example1 - 计算平均吞吐

• step1. 构造对应的吞吐量数据 run_exp.sh

• step2. 计算平均吞吐 run_dummy.sh

Example2 - 计算尾延迟分布

• step1. 构造对应的延迟记录文件 req_time

• step2. 分析对应的延迟

CMake

• including Makefile.

• cmake / make
• CMake 最终实现的是帮助编译成 Makefile
• https://github.com/richardchien/modern-cmake-by-example

Modern CMake

个人认为也可以包含在 6.NULL 系列的 CMake 教程 CMake 最终实现的是帮助编译成 Makefile 本文参考了上述链接，重点是 B站 IPADS 的新人培训教程，对 Makefile 和 CMake 进行了讲解，然后个人再做一些补充。 了解 Makefile 最基本的格式 targets：规则的目标，可以是 Object File（一般称它为中间文件），也可以是可执行文件，还可以是一个标签； prerequisites：是我们的依赖文件，要生成 targets 需要的文件或者是目标。可以是多个，也可以是没有； command：make 需要执行的命令（任意的 shell 命令）。可以有多条命令，每一条命令占一行。 注意：我们的目标和依赖文件之间要使用冒号分隔开，命令的开始一定要使用Tab键。 name: dependencies commands # or targets : prerequisites commands # or targets : prerequisites; command command #include int main(int argc, const char *argv[]) { std::cout answer; if (answer == expected_answer) { std::cout << "Correct!"

https://blog.shunzi.tech/post/6.NULL-1-ModernCMake/

Git

• Version Control System

• Gitlab/Gitee/Github/BitBucket
• https://ipads.se.sjtu.edu.cn/zh/slides/tutorial-2021/Tutorial03_Git.pdf

• Collaboration
• Issue / Pull Request

科研数据管理

文献数据

• 管理软件：Zotero / EndNote / Mendeley / … / even File System

• 数据同步：软件自带 / OneDrive / 坚果云 / 阿里云盘

• 文献下载：学校数据库（IEEE/ACM/…）, dblp, Google Scholar, 知网（毕业论文）

dblp: computer science bibliography

see FAQ for more information Update May 7, 2017: Please note that we had to disable the phrase search operator (.)

https://dblp.org/

文献阅读笔记

• 笔记软件：Notion, 印象笔记, 飞书文档，有道云笔记
• 大道至简：markdown + sync

• 知识分享平台：Blog, Zhihu, 简书, CSDN

论文写作

• Latex
• vscode + Latex Workshop + texlive
• Overleaf
• TexStudio
• …

• Figures
• Excel / Origin / GNUPlot / Python+matplotlib
• Visio / ProcessOn / draw.io / Lucid Chart

论文/技术分享

阅读流程

• 旨在解决一个什么样的问题？
• 如果是自己设计，大概会有个什么样的思路（在不看本文的设计之前）

• 以前的解决思路有什么缺陷？Related Work 的相关讨论（包括实验部分的对比方案的讨论）
• 可能也会是本文设计的动机点

• 本文方案的动机点是什么？
• 方案动机中也可能有一些新的发现，而以前的研究没有关注

• 本文方案的核心思想和贡献？
• 几句话简单概括，整体的架构图、流程图

• 本文带来的理论上的和实际性能上的提升？
• 除非需要考究实验细节，或者复现实验，不用阅读过多的实验细节
• 但是需要明确实验是否能验证本文的结论
• 观察实验对比结果看看是否有可能有新的发现
• 绝大部分方案都是做 Trade-Off

• 本文可能还存在的问题，未来的解决方向？
• 总结分析本文做的 trade-off 的结论以及没有细节阐述或者解决的问题
• 可以借助文章的引用关系，查看最新的文章关于本方案的问题描述

• 针对上述问题，可能可以去做的方向有哪些？

分享流程

• 核心目的就是向听众阐述上述阅读过程中的几个要点（加粗部分）。

• 但考虑到听众的实际情况，需要在开始分享实际内容之前补充一定的背景知识，”引人入胜“。

举个例子：OSDI’22 ListDB

• 背景：
• 现有的针对于 PM 的索引结构/键值存储的两种形式，以及他们存在的问题
• PM-Only Index：PM 上的索引比 DRAM 上的慢，mfence/clflush 开销比较大
• PM 的硬件特征，如果听众几乎不了解 PM，就有必要解释一下
• 考虑到有不懂的听众，需要大致解释一下 mfence/clflush
• DRAM+PM Hybrid Index/KV-Store：周期性做同步的 Checkpioint 操作开销大（尾延迟高）
• 解释为什么要做 Checkpoint
• 异步增量 Checkpoint 机制：引入 LSM-Tree，本质就是来介绍 LSM 的背景
• LSM 会面对写停顿的问题：为什么会产生写停顿？写停顿带来的影响是什么？
• 所以提出了我们的最终目标：避免写停顿。

• 解决写停顿需要面临的三个挑战，其实也就是在 PM 上实现的 LSM-Tree 存在的三个问题：（每个问题对应了解决方案组成了本文的贡献）
• DRAM 和 PM 之间存在的写延迟的差距：Index-Unified Logging (Convert Logs into SkipLists for Faster Flush)
• 写放大：Zipper Compaction (In-place Merge Sort)
• PM 比 DRAM 对 NUMA 效应更敏感：NUMA-aware Braided SkipList

• 整体架构图：三层结构，其实最好和原本的结构形成一个简单的对比
• 三个关键组成部分，也就是本文贡献点的实施方式

• 设计点一：Fast MemTable Flush with Index-Unified Logging
• 为什么会有这个设计？设计思想的来源？WAL and L0 SkipList 之前的区别其实很小，只在于数据是否有序
• 从而得出结论其实完全可以把 WAL 和 L0 的 SkipList 统一起来
• 那统一起来需要解决些什么问题呢？其实就是消除有序性的差异
• 本质就是在 WAL 的基础上实现 L0 SkipList 的效果，因为 WAL 本身是个同步操作，追加写的，无法保证顺序
• 要想排序，就利用 值无序，指针有序的思想，让其逻辑上有序，所以需要
• 日志上预留指针，提前分配
• 数据刷回过程只刷有序指针，不刷键值对（这样才是真正的复用）
• 刷回过程中不需要调用 持久化指令。为什么呢？（这里就和前面讲为什么需要 clflush 结合起来了）
• 因为数据本身就持久化了，刷回的过程只是刷回的顺序，并不影响数据的正确性
• 将数据从 L0 合并到 L1 的时候确保指针持久化了
• 然后有个流程示例

• 设计点二：Zipper Compaction
• 就地归并排序避免了写放大：因为只有指针更新，所以减小了写放大
• Zipper Compaction 不会阻塞并发读请求
• 因为每个步骤保留了跳表的不变性以保证搜索的正确性
• 跳表的不变性：上层列表是底层的一个有序子集
• Compaction 的具体步骤：
• Scan：从头到尾，构造栈，保存要插入的数据以及对应的位置关系



• Merge：从尾到头。依次弹栈，应用指针的更新操作
• 保留了跳表的不变性，即上层的索引是底层列表的一个有序子集
• 读取操作在这种不变性得到了保证的情况下，依然可以正确执行
• 合并过程中假定了 8 字节指针更新是原子的，为了保证指针更新 failure-atomic，它使用内存 fence 和 cacheline 刷新指令立即持久化每个底层更新



• 因为读操作是从头到尾，且是从 L0 到 L1 的顺序访问 PMTables，而压缩线程则从尾到头合并它们
• 在 Zipper 压缩期间，每个元素都保证是指向至少一个 head（即肯定是能追溯到的）。
• 下图显示了一个原子存储指令序列如何合并两个示例 skiplist。即使并发读线程以下图所示的任何状态访问 PMTables，它也会返回正确的结果。



• Compaction 可能存在的问题：数据新旧版本的合并以及空间的回收
• 因为本方案设计的 Compaction 策略只是指针上的更新，并未实际合并数据，即删除数据
• 原文中的解释说一个 NVM Chunk 中的数据当全部都是旧数据的时候就可以回收该 chunk，那么就可能出现碎片化
• 即部分 chunk 可能因为包含了大量无效数据和少部分有效数据，没有及时回收利用
• 作者说可以设计一个 CoW 的垃圾回收机制来做这件事，但是没做留给了未来的工作

• 设计点三：NUMA-Aware Braided SkipList
• 一个原则：只要保证了跳表上层索引是底层元素的子集，对于跳表的查询就肯定是正确的
• 因为进行了跳表指针合并之后，逻辑上一个跳表变得很大了，而且物理上多个跳表，可能存在于不同的 NUMA 节点上
• 原始的方式访问就很有可能在 NUMA 节点上不断跳跃访问对应的延迟开销很大
• 其实就是构造跳表的过程中，上层指针忽略远程 NUMA 节点中的 SkipList 元素
• 例如，每个元素的上层指针指向同一个NUMA 节点中具有更大键的元素，而不是按照传统的大小关系指向了别的 NUMA 节点
• 与 NUMA-oblivious 传统的 SkipList 相比，Braided SkipList 把远程内存访问次数减少到 1/N，N 是 NUMA 节点的数目

• 测试结果