介绍软件工程领域一些通用的设计方案。
Lease
通过 Lease 可以解决或者缓解下面的一些问题：
- 减少 invalidation 检查的开销
- 减少惊群带来的大量无效计算
例如在选举模型中，在 lease 期间，voter 就不会发起投票驱逐 leader，即使它们暂时联系不上 leader。
Backoff
Cache
Cache miss
Cache miss 往往和随机读有关。
Flyweight Pattern
Amortize
Batching
Pipeline
Locality
抽象和反抽象
Parallel
这个策略包含了数据并行和模型并行。前者分割数据，每一个并行单元处理一部分数据；后者分割代码，每个并行单元处理一部分逻辑。
SIMD
例如，将 uint8_t 聚合成 uint128_t 比较。通常用来加速字符串的匹配。
机器学习中的模型并行
机器学习中的模型，其实也是一部分数据。例如神经网络中，它可能就是表示权值的矩阵。如果这个模型比较大，则它对应的矩阵可以被切分。
注意，这种情况下，子模型之间存在依赖关系，所以需要同步和通信。
Provision
这个思路会尝试预测资源的使用，从而提前分配，以一个较小的预测失误的代价，获取预测成功的大幅性能提升。
Prefetch
包含：
- prefetch 数据
- prefetch 代码，也就是 branch prefiction
Warm-up
Ordering
Partial Ordering
通常面临这样的场景，很多个命令构成了全序关系，但其实它们可以被拆成多组彼此 concurrent 的偏序关系：
- 在 NewSQL 的事务层+共识层的架构中，将
(start_ts, commit_ts)的事务拆到多个共识组中，多个共识组之间可以并发 apply。对于共识组中不相交的事务，可以通过并行 apply 继续提高并发度。 - CPU 中的 superscalar 技术
不相关的指令可以乱序执行。
Pipeline
Pipeline 可以作为一个 first-class 的优化类型了。但是我觉得它也是一个 Ordering 的优化。
Parallel
重放
GC
我们往往在异步线程中预处理一些对象，并最后将它们 link 到主干上，或者从主干上 unlink 对象，并最后 gc 掉。如果这中间发生重启，那么这些对象就会游离在存储中。如何区分被 unlink 但尚未被回收的对象，和刚被创建但还没有被 link 的对象呢？这里的通用思路是在重启后对比主干和存储中的对象，所有不出现在主干中的对象就需要被删掉。然后依赖重放来解决第一种情况。
Trade off
Trade off 的思路是权衡两个方案 A 或者 B，在它们各自的好处和坏处中取得一个妥协。
质量和速度
- 向量搜索中的 ANN
- 机器学习中的量化
- 图像处理中的有损压缩
熵(序)
- 存储系统中，如果追求低熵，那么就会产生资源消耗。例如 LSM 中的写放大是提升系统的 Ordering。
The design space of LSM trees spans everything between a write-optimized log to a read-optimized sorted array.
读和写
读优化和写优化的 trade off 是非常常见的。以 RocksDB 为例，就可以列出：
- Leveled 和 Tiered
延迟和吞吐量
- 攒批的方式能够提升吞吐量，但是可能会增加延迟
锁和非锁
锁意味着串行逻辑，通常用来避免写写冲突。
非锁的方案往往涉及多个版本：
- CAS 的方案本质上是异步完成新版本的构建，再原子替换上去。它并不是避免冲突，而是在冲突时退出。
- MVCC 的方案本质上是让读不会阻塞写，解决读写冲突。
类似的思想出现很多：
- TiDB 中使用乐观锁或者悲观锁处理写写冲突，通过 MVCC 处理读写冲突。
- Masstree 中使用锁解决写写冲突，引入版本号解决读写冲突。
- Snapshot Isolation 中，读不会被写影响。
存储和计算
例如，可以存一部分中间结果，从而减少重新计算的开销。包含：
- 动态规划类算法
对特定访问模式的优化
Eager vs Lazy
COW
C++ 中 COW 字符串最初被用来优化内存使用，以及减少不必要的复制。它也被认为是读多写少场景下的一种优化策略。但是它后续被废弃了，原因是它在多线程中的表现不佳。
转移代价
相比于 trade off，另一种思路是将代价转移。此时，接纳方案 A 和 B 的大部分的好处，承担第三个方案/操作 C 的代价，使得 A + B + C 的开销小于单独的 A 或者 B。
一些算法的例子
LRU cache
它使用了双向链表来支持的插入和删除，以及排序；然后又引入了 hash table 来支持快速的查询。它的操作 C 是去维护两个数据结构。而维护链表和 hash 表的代价要比单独使用一个，然后接受另一个的代价要低很多。
