https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=8704965
Evolution of the Unix System Architecture: An Exploratory Case Study。其中有对于 FreeBSD 从 1970 年（Research PDP7）到现在的架构的演进过程的简单介绍，可以帮助理解一些现在看来不合理的设计是在什么样的背景下做出的决定。现代的操作系统已经过于复杂而让人经常不知道从哪里入手开始了解，这类从最早的原型开始逐渐介绍演变过程的可能是更好的了解操作系统构成的资料。
Evolution of the Unix System Architecture: An Exploratory Case Study。其中有对于 FreeBSD 从 1970 年（Research PDP7）到现在的架构的演进过程的简单介绍，可以帮助理解一些现在看来不合理的设计是在什么样的背景下做出的决定。现代的操作系统已经过于复杂而让人经常不知道从哪里入手开始了解，这类从最早的原型开始逐渐介绍演变过程的可能是更好的了解操作系统构成的资料。
https://dl.acm.org/doi/10.1145/3465480.3467835
Thinking in events: from databases to distributed collaboration software。Event sourcing 架构的综述，着重介绍了需要对事件持久化的场景。在理想情况下任何后端的状态能依靠对外部事件的重放来重现，把 source of truth 从数据库转变为事件记录，数据库只是系统状态的一个 snapshot。
Thinking in events: from databases to distributed collaboration software。Event sourcing 架构的综述，着重介绍了需要对事件持久化的场景。在理想情况下任何后端的状态能依靠对外部事件的重放来重现，把 source of truth 从数据库转变为事件记录，数据库只是系统状态的一个 snapshot。
https://www.usenix.org/conference/nsdi21/presentation/ghigoff
BMC: Accelerating Memcached using Safe In-kernel Caching and Pre-stack Processing。架构上的改进虽然成立，做法本身有点 ad-hoc，非常强的依赖于 UDP 本身足够简单且无状态，memcached 业务场景大量零散查询，才能在网络栈处理请求之前增加一层 kv cache 提前返回一部分查询结果，eBPF 是否能拓展到更复杂的情况也存疑。比较有意思的是和 kernel-bypass (Userspace Network Stack) 的对比，即使 eBPF 有不小的性能惩罚，现阶段缺少 Userspace Interrupt 的 kernel-bypass 的 polling 开销也远大于 eBPF。
BMC: Accelerating Memcached using Safe In-kernel Caching and Pre-stack Processing。架构上的改进虽然成立，做法本身有点 ad-hoc，非常强的依赖于 UDP 本身足够简单且无状态，memcached 业务场景大量零散查询，才能在网络栈处理请求之前增加一层 kv cache 提前返回一部分查询结果，eBPF 是否能拓展到更复杂的情况也存疑。比较有意思的是和 kernel-bypass (Userspace Network Stack) 的对比，即使 eBPF 有不小的性能惩罚，现阶段缺少 Userspace Interrupt 的 kernel-bypass 的 polling 开销也远大于 eBPF。
https://doi.org/10.1145/3243176.3243195
Biased Reference Counting: Minimizing Atomic Operations in Garbage Collection。RC 操作在测试的swift 客户端场景中平均占 42% 的运行时间，RC 的 atomic 操作平均占 25% 的时间。观察到大多数对象很少跨线程，所以将 RC 的计数器区分出 owner 线程（不需要 atomic）和公共线程，最终减少了客户端 22.5% 的平均执行时间。感觉如果 CPU 能提供专门的 RC 指令然后分发给加速器而不在当前的指令流水线处理，能解决 atomic 对性能影响的大多数情况，这类 RC 场景并不需求非常严格的内存释放的实时性。
Biased Reference Counting: Minimizing Atomic Operations in Garbage Collection。RC 操作在测试的swift 客户端场景中平均占 42% 的运行时间，RC 的 atomic 操作平均占 25% 的时间。观察到大多数对象很少跨线程，所以将 RC 的计数器区分出 owner 线程（不需要 atomic）和公共线程，最终减少了客户端 22.5% 的平均执行时间。感觉如果 CPU 能提供专门的 RC 指令然后分发给加速器而不在当前的指令流水线处理，能解决 atomic 对性能影响的大多数情况，这类 RC 场景并不需求非常严格的内存释放的实时性。
https://lwn.net/ml/linux-kernel/20210913200132.3396598-1-sohil.mehta@intel.com/
Intel 在 CPU 中加入了 User Interrupts 的扩展，让进程具有不经过内核的 IPC 能力。当前版本的实现还比较受限，除了只能用于用户进程到用户进程的中断，Linux 也没有提供完全的控制调度的能力，可能只有 Snap 这种场景可以享受到延迟大幅下降的收益。不过这至少是实现能和内核空间同等性能的用户空间驱动的第一步，也有避免 hypercall 来解决硬件 / 部分虚拟化 I/O 性能的潜力。
Intel 在 CPU 中加入了 User Interrupts 的扩展，让进程具有不经过内核的 IPC 能力。当前版本的实现还比较受限，除了只能用于用户进程到用户进程的中断，Linux 也没有提供完全的控制调度的能力，可能只有 Snap 这种场景可以享受到延迟大幅下降的收益。不过这至少是实现能和内核空间同等性能的用户空间驱动的第一步，也有避免 hypercall 来解决硬件 / 部分虚拟化 I/O 性能的潜力。
https://www.usenix.org/conference/nsdi21/presentation/yang-juncheng
面向 TTL 设计的 in-memory key-value cache。常见的纯内存 kv 是依赖较为通用的基于 object 大小的内存分配策略的（类似 tcmalloc / jemalloc 的优化方式）；Segcache 将 TTL 作为 cache 的核心设计，围绕 TTL 来设计内存分配策略，把 segment 变成了类似于 Region-based memory management 的方式。
面向 TTL 设计的 in-memory key-value cache。常见的纯内存 kv 是依赖较为通用的基于 object 大小的内存分配策略的（类似 tcmalloc / jemalloc 的优化方式）；Segcache 将 TTL 作为 cache 的核心设计，围绕 TTL 来设计内存分配策略，把 segment 变成了类似于 Region-based memory management 的方式。
https://arxiv.org/abs/2107.01250
Linear Probing Revisited: Tombstones Mark the Death of Primary Clustering。Knuth 1963 年对于 linear-probing hash table 插入操作的复杂度分析指出在 load factor 是 1 - 1/x 的情况下，插入操作的复杂度期望是 Θ(x^2)。本文的不同在于指出如果只有插入操作，是不可能维持 load factor 在 1 - 1/x 或以下的，进一步的考虑常见作为工程实现 trick 的墓碑机制（删除时简单替换被删除的值为墓碑），由于插入在遇到墓碑时就可以停止，一个将 load factor 维持在 1 - 1/x 以下的操作序列中的插入的均摊复杂度会低于 Θ(x^2)。进一步的优化可以在定期重建时均匀的随机插入一些墓碑，让查找和删除均摊插入的开销，最终达到所有操作的期望复杂度都是 Θ(x)。
It turns out that both of these weaknesses can be removed if we simply use a larger rebuild window size R. Intuitively, the larger the R, the more time there is for tombstones to accumulate and the better the insertions perform. On the other hand, tombstone accumulation is precisely the reason that R is classically set to be small, since it breaks the classical analysis and potentially tanks the performance of queries.
这个结果不会显著影响 hash table 的工程实践，更多的是指出已经广泛使用的 linear-probing hash table 并没有过去理论分析中预想的慢。
Linear Probing Revisited: Tombstones Mark the Death of Primary Clustering。Knuth 1963 年对于 linear-probing hash table 插入操作的复杂度分析指出在 load factor 是 1 - 1/x 的情况下，插入操作的复杂度期望是 Θ(x^2)。本文的不同在于指出如果只有插入操作，是不可能维持 load factor 在 1 - 1/x 或以下的，进一步的考虑常见作为工程实现 trick 的墓碑机制（删除时简单替换被删除的值为墓碑），由于插入在遇到墓碑时就可以停止，一个将 load factor 维持在 1 - 1/x 以下的操作序列中的插入的均摊复杂度会低于 Θ(x^2)。进一步的优化可以在定期重建时均匀的随机插入一些墓碑，让查找和删除均摊插入的开销，最终达到所有操作的期望复杂度都是 Θ(x)。
It turns out that both of these weaknesses can be removed if we simply use a larger rebuild window size R. Intuitively, the larger the R, the more time there is for tombstones to accumulate and the better the insertions perform. On the other hand, tombstone accumulation is precisely the reason that R is classically set to be small, since it breaks the classical analysis and potentially tanks the performance of queries.
这个结果不会显著影响 hash table 的工程实践，更多的是指出已经广泛使用的 linear-probing hash table 并没有过去理论分析中预想的慢。
https://datatracker.ietf.org/doc/html/draft-iab-protocol-maintenance
The Harmful Consequences of the Robustness Principle。Robustness Principle 是 HTML 和很多早期互联网协议的设计原则：
Be strict when sending and tolerant when receiving. Implementations must follow specifications precisely when sending to the network, and tolerate faulty input from the network. When in doubt, discard faulty input silently, without returning an error message unless this is required by the specification.
Robustness Principle 基于了一个假设的场景：It is not possible to affect change in a system the size of the Internet，而这和当前互联网协议的维护状况已经不符合了。为了解决 Robustness Principle 导致的事实标准凌驾于协议文档的问题的一个例子：https://web.dev/interop-2022/
The Harmful Consequences of the Robustness Principle。Robustness Principle 是 HTML 和很多早期互联网协议的设计原则：
Be strict when sending and tolerant when receiving. Implementations must follow specifications precisely when sending to the network, and tolerate faulty input from the network. When in doubt, discard faulty input silently, without returning an error message unless this is required by the specification.
Robustness Principle 基于了一个假设的场景：It is not possible to affect change in a system the size of the Internet，而这和当前互联网协议的维护状况已经不符合了。为了解决 Robustness Principle 导致的事实标准凌驾于协议文档的问题的一个例子：https://web.dev/interop-2022/
https://doi.org/10.14778/3485450.3485454
DBOS: a DBMS-oriented operating system。基于 DBMS 实现的分布式操作系统，比较性能的角度比较有意思，分布式操作系统并不应该以 Linux 作为一个性能比较的对象，而是应该和 Linux + k8s 类似的组合来比较性能。微内核 + 分布式操作系统可能不可能在单机上达到和宏内核类似的性能，但是从整个集群来说实际上减少了抽象层次，就算是带了个 DBMS 这么重的抽象也能达到不错的性能。
DBOS: a DBMS-oriented operating system。基于 DBMS 实现的分布式操作系统，比较性能的角度比较有意思，分布式操作系统并不应该以 Linux 作为一个性能比较的对象，而是应该和 Linux + k8s 类似的组合来比较性能。微内核 + 分布式操作系统可能不可能在单机上达到和宏内核类似的性能，但是从整个集群来说实际上减少了抽象层次，就算是带了个 DBMS 这么重的抽象也能达到不错的性能。
https://www.usenix.org/conference/usenixsecurity21/presentation/kirzner
An Analysis of Speculative Type Confusion Vulnerabilities in the Wild。Spectre v1 类的攻击对现代 CPU（和 Meltdown 不同，不局限于特定的 CPU 架构）在想要保持性能的情况下几乎是无法彻底解决的，这篇对利用的机制提供了一个比较全面的综述。
An Analysis of Speculative Type Confusion Vulnerabilities in the Wild。Spectre v1 类的攻击对现代 CPU（和 Meltdown 不同，不局限于特定的 CPU 架构）在想要保持性能的情况下几乎是无法彻底解决的，这篇对利用的机制提供了一个比较全面的综述。
https://eprint.iacr.org/2021/1022
Zero-Knowledge Middleboxes。利用零知识证明让合作的客户端能向中间人证明端到端加密的流量符合特定的 policy（如只允许部分协议 / DNS deny list）而中间人无法得知任何具体内容。对于部分中间人如 ISP 可以解决法律义务，对于公司 IT 来说可以在允许端到端加密的情况下保证网络策略，相对于现在只能阻断如 DoH 来强制触发降级到完全不加密的协议或者立法禁止所有端到端加密是一种大家都能接受的折中手段。作者希望 TLS 的后续协议迭代把便于零知识证明作为协议设计的一部分。
Zero-Knowledge Middleboxes。利用零知识证明让合作的客户端能向中间人证明端到端加密的流量符合特定的 policy（如只允许部分协议 / DNS deny list）而中间人无法得知任何具体内容。对于部分中间人如 ISP 可以解决法律义务，对于公司 IT 来说可以在允许端到端加密的情况下保证网络策略，相对于现在只能阻断如 DoH 来强制触发降级到完全不加密的协议或者立法禁止所有端到端加密是一种大家都能接受的折中手段。作者希望 TLS 的后续协议迭代把便于零知识证明作为协议设计的一部分。
Read It Never
http://erlang.org/download/armstrong_thesis_2003.pdf At the highest level of abstraction an architecture is “a way of thinking about the world.” 对 erlang 语言本身不是特别有兴趣的可以跳着看下 2，5，10 章和 APPENDIX B。 一些内容的 TL;DR 版本： 1. A component is considered faulty once…
https://keunwoo.com/notes/rebooting/
On rebooting: the unreasonable effectiveness of turning computers off and on again。为什么电脑重启一下就能解决各种问题，是个很好的 fault-handling 的例子。fault-handling 不是某个语言的错误处理方式，是一类将非预期的系统状态转化为可预期的程序逻辑来限制 ill-formed 状态扩散的方式。
On rebooting: the unreasonable effectiveness of turning computers off and on again。为什么电脑重启一下就能解决各种问题，是个很好的 fault-handling 的例子。fault-handling 不是某个语言的错误处理方式，是一类将非预期的系统状态转化为可预期的程序逻辑来限制 ill-formed 状态扩散的方式。
https://www.ietf.org/id/draft-dekater-panrg-scion-overview-02.html
SCION (Scalability, Control, and Isolation On Next-generation networks)，次世代 BGP。略读了一下：
- AS 带证书，可以给子 AS 签子证书，每个 AS 都可以配置自己独立的 root of trust CA。
- 每个 AS 给的不再是下一跳，而是 path-segment construction beacons (PCBs)，可以认为是一段路径。路径（PCB）上的每个 AS 都会对这个 PCB 签名，每个 AS 可以独立的配置允许的转发路径规则。
- 发送端可以组合最多 3 个 PCB 来决定发送路径，类似于 source routing，但是同时又能验证 PCB 符合 root of trust 以及各个 AS 都接受这个 PCB。
实现：https://github.com/scionproto/scion
但是建议看 https://www.scionlab.org/
SCION (Scalability, Control, and Isolation On Next-generation networks)，次世代 BGP。略读了一下：
- AS 带证书，可以给子 AS 签子证书，每个 AS 都可以配置自己独立的 root of trust CA。
- 每个 AS 给的不再是下一跳，而是 path-segment construction beacons (PCBs)，可以认为是一段路径。路径（PCB）上的每个 AS 都会对这个 PCB 签名，每个 AS 可以独立的配置允许的转发路径规则。
- 发送端可以组合最多 3 个 PCB 来决定发送路径，类似于 source routing，但是同时又能验证 PCB 符合 root of trust 以及各个 AS 都接受这个 PCB。
实现：https://github.com/scionproto/scion
但是建议看 https://www.scionlab.org/
Read It Never
https://www.ietf.org/id/draft-dekater-panrg-scion-overview-02.html SCION (Scalability, Control, and Isolation On Next-generation networks)，次世代 BGP。略读了一下： - AS 带证书，可以给子 AS 签子证书，每个 AS 都可以配置自己独立的 root of trust CA。 - 每个 AS 给的不再是下一跳，而是 path-segment construction…
在生产环境使用 SCION 的是 Swiss National Bank, 今年新的 The Complete Guide to SCION (https://doi.org/10.1007/978-3-031-05288-0) 相对 2017 年的 SCION: A Secure Internet Architecture 有一些设计更新和更详细的细节。
Read It Never
https://doi.org/10.1145/2901318.2901326 Linux 内核调度的 casestudy，比较全面的介绍了现代 Linux 内核调度的方法，同时几个调度的 bug 也对于在现代硬件下调度系统的复杂度有比较好的展现。
https://lwn.net/SubscriberLink/909611/447c4722188eb46b/
一个简略的关于 Intel 大小核调度是怎么实现的介绍，其他关于现代操作系统调度的复杂程度可以参见上面这篇 "The Linux scheduler: a decade of wasted cores"。
“And you have to realize that there are not very many things that have aged as well as the scheduler. Which is just another proof that scheduling is easy.” - Linus Torvalds, 2001
一个简略的关于 Intel 大小核调度是怎么实现的介绍，其他关于现代操作系统调度的复杂程度可以参见上面这篇 "The Linux scheduler: a decade of wasted cores"。
“And you have to realize that there are not very many things that have aged as well as the scheduler. Which is just another proof that scheduling is easy.” - Linus Torvalds, 2001
https://gvisor.dev/blog/2022/10/24/buffer-pooling/
How we Eliminated 99% of gVisor Networking Memory Allocations with Enhanced Buffer Pooling。在 GC 语言里手动管理内存提高了 gVisor 网络协议栈 30+% 的吞吐（笑）。当然不止简单的手动管理内存（引用计数），还对 buffer 分页，实现了 copy on write，新 buffer 的实现可以看：https://github.com/google/gvisor/tree/master/pkg/bufferv2 。并且 GC 语言本身依然保证了内存安全性。
How we Eliminated 99% of gVisor Networking Memory Allocations with Enhanced Buffer Pooling。在 GC 语言里手动管理内存提高了 gVisor 网络协议栈 30+% 的吞吐（笑）。当然不止简单的手动管理内存（引用计数），还对 buffer 分页，实现了 copy on write，新 buffer 的实现可以看：https://github.com/google/gvisor/tree/master/pkg/bufferv2 。并且 GC 语言本身依然保证了内存安全性。
http://www.melconway.com/Home/Committees_Paper.html
How Do Committees Invent? 相对于论证更多的是对现实系统架构的观察得出的假说："Any organization that designs a system (defined more broadly here than just information systems) will inevitably produce a design whose structure is a copy of the organization's communication structure."
或者使用原文的另一个说法，一个组织设计的系统与组织本身是同构的。
How Do Committees Invent? 相对于论证更多的是对现实系统架构的观察得出的假说："Any organization that designs a system (defined more broadly here than just information systems) will inevitably produce a design whose structure is a copy of the organization's communication structure."
或者使用原文的另一个说法，一个组织设计的系统与组织本身是同构的。
https://netflixtechblog.com/2721924a2822
Seeing through hardware counters: a journey to threefold performance increase。这是我第一次看到在生产上（Netflix）因为字段没有 padding 导致的巨大性能差异的分析，是标准的不同核心互相不停的 invalidate L1 cache 的场景。
Seeing through hardware counters: a journey to threefold performance increase。这是我第一次看到在生产上（Netflix）因为字段没有 padding 导致的巨大性能差异的分析，是标准的不同核心互相不停的 invalidate L1 cache 的场景。
https://doi.org/10.1145/3292500.3330651
MOBIUS: Towards the Next Generation of Query-Ad Matching in Baidu’s Sponsored Search。百度新的广告推荐系统，主要由两部分变化：
- 在排序层加入了一个额外的相关性模型保证相关性超过阈值
- 可能由于排序层大幅增加了计算量，在匹配层额外考虑了点击率来达到候选集减小的情况下保证召回率
其实我本来看图把三层揉在一起了以为是他们做了一套 e2e 的方案，结果那个图的意思是打破了原来各层的单目标优化，而且相关性还是得靠卡阈值。论文的很大一部分重点在于如何训练出一个有效的相关性模型。
题外话，这个三层架构（或者两层，召回和排序，百度内部架构把排序额外拆成了粗排和精排两层）是很多推荐系统通病的来源。这个架构有一个隐含假设：用户只会点击相关的东西，所以点击率 / 播放时长预估本身保证了相关性，但是这个假设对于高于全局平均优化目标的条目会失效（比如 YouTube 有一段时间给所有人都推荐某钢琴视频）。这个推荐结果在排序系统逻辑上是成立的：如果给所有人都推荐这个视频，所有人对这个视频的平均播放时长是高于用户的平均播放时长的（因为 YouTube 的单目标优化是优化播放时长），那么给所有人都推荐这个视频符合全局的优化目标。这个现象的出现是因为 1、排序层缺少相关性的目标 2、这类单目标优化很难学到负权重。百度这个模型解决了怎么学到负相关性和怎么以相关性作为优化目标，就是最后卡个阈值就发论文了还是有点太 it works 了（
MOBIUS: Towards the Next Generation of Query-Ad Matching in Baidu’s Sponsored Search。百度新的广告推荐系统，主要由两部分变化：
- 在排序层加入了一个额外的相关性模型保证相关性超过阈值
- 可能由于排序层大幅增加了计算量，在匹配层额外考虑了点击率来达到候选集减小的情况下保证召回率
其实我本来看图把三层揉在一起了以为是他们做了一套 e2e 的方案，结果那个图的意思是打破了原来各层的单目标优化，而且相关性还是得靠卡阈值。论文的很大一部分重点在于如何训练出一个有效的相关性模型。
题外话，这个三层架构（或者两层，召回和排序，百度内部架构把排序额外拆成了粗排和精排两层）是很多推荐系统通病的来源。这个架构有一个隐含假设：用户只会点击相关的东西，所以点击率 / 播放时长预估本身保证了相关性，但是这个假设对于高于全局平均优化目标的条目会失效（比如 YouTube 有一段时间给所有人都推荐某钢琴视频）。这个推荐结果在排序系统逻辑上是成立的：如果给所有人都推荐这个视频，所有人对这个视频的平均播放时长是高于用户的平均播放时长的（因为 YouTube 的单目标优化是优化播放时长），那么给所有人都推荐这个视频符合全局的优化目标。这个现象的出现是因为 1、排序层缺少相关性的目标 2、这类单目标优化很难学到负权重。百度这个模型解决了怎么学到负相关性和怎么以相关性作为优化目标，就是最后卡个阈值就发论文了还是有点太 it works 了（
https://engineering.fb.com/2022/06/08/core-data/cache-invalidation/
Cache made consistent: Meta’s cache invalidation solution。有点标题党，meta 并不是解决了 cache invalidation 的问题，而是把解决这个这个问题的角度从正确性问题转换成了可用性问题。要解决可用性问题，首先要做的是定义出问题的可观察指标。meta 建立了一套对于缓存一致性的监控系统，把问题从 “保证系统逻辑是正确的” 转变成了 “尽可能提高 cache 一致性指标”，对这个问题来说是个挺新颖的角度。
For any anomaly in a stateful service, it is an anomaly only if clients can observe it one way or the other. Otherwise, we argue that it doesn’t matter at all.
Cache made consistent: Meta’s cache invalidation solution。有点标题党，meta 并不是解决了 cache invalidation 的问题，而是把解决这个这个问题的角度从正确性问题转换成了可用性问题。要解决可用性问题，首先要做的是定义出问题的可观察指标。meta 建立了一套对于缓存一致性的监控系统，把问题从 “保证系统逻辑是正确的” 转变成了 “尽可能提高 cache 一致性指标”，对这个问题来说是个挺新颖的角度。
For any anomaly in a stateful service, it is an anomaly only if clients can observe it one way or the other. Otherwise, we argue that it doesn’t matter at all.
https://www.sigarch.org/fast-memcpy-a-system-design/
Fast memcpy, A System Design。优化目标是 CPU 的每个 cycle 移动 16 bytes，从 CPU 的角度来考虑达到这个目标 CPU 需要提供什么样的能力。也可以看 ClickHouse 的 memcpy 实现（的注释）：https://github.com/ClickHouse/ClickHouse/blob/master/base/glibc-compatibility/memcpy/memcpy.h
大体上分成三个阶段：
- Small Size: 复制的长度小于一次 load 的宽度（16 bytes）
- Medium Size: 复制的长度小于完整的一轮循环展开（如果循环展开 8 次，就是 128 bytes）
- Large Size: 在对齐的内存上循环展开复制
Fast memcpy, A System Design。优化目标是 CPU 的每个 cycle 移动 16 bytes，从 CPU 的角度来考虑达到这个目标 CPU 需要提供什么样的能力。也可以看 ClickHouse 的 memcpy 实现（的注释）：https://github.com/ClickHouse/ClickHouse/blob/master/base/glibc-compatibility/memcpy/memcpy.h
大体上分成三个阶段：
- Small Size: 复制的长度小于一次 load 的宽度（16 bytes）
- Medium Size: 复制的长度小于完整的一轮循环展开（如果循环展开 8 次，就是 128 bytes）
- Large Size: 在对齐的内存上循环展开复制