Polyjuice 专为单节点多核设置而设计。它假设所有事务类型都是事先已知的，并且可以作为存储过程运行（请参阅下面的策略表部分）。它不支持 MVCC，因为它是在Silo 框架之上实现的。Polyjuice 代码可在https://github.com/derFischer/Polyjuice获取
Polyjuice 不是在少数已知算法中进行选择，而是通过使用基于进化的强化学习和离线训练来搜索细粒度操作的“策略空间”，以最大化吞吐量。在 TPC-C 和 TPC-E 的不同配置下，Polyjuice 可以实现比现有最佳算法高 15% 至 56% 的吞吐量。
最高并发控制 (CC) 算法
不同的最高并发控制 CC 算法在不同的条件下返回最佳结果。两种极端的 CC 算法：
- 两阶段锁定 (2PL) 等待每个相关事务完成。2PL 在高争用下更好，因为它避免了由于后期中止而浪费的工作。
- 乐观并发控制 (OCC) 不跟踪或等待任何相关事务，而是在最后进行验证。OCC 在争用较少的情况下更好，因为它避免了不必要的开销，
有很多已发布的 最高并发控制CC 算法在处理相关事务的方式方面介于 2PL 和 OCC 之间。例如，IC3、CALLAS RP 和 DRP 使事务等待，直到相关事务完成执行到某个点（通过应用事务工作负载的静态分析来确定）。
- 为了保证发表，每篇 并发控制CC 论文很可能都给出了优于其他论文的评估。
- 所以我想知道这个猜想是否成立：对于每个并发控制CC算法X，都存在一个工作量使得X优于其他并发控制CC算法。
在这种情况下，自然的做法是使用混合 CC 算法，该算法可以混合并匹配不同的 OCC 策略，以便更好地处理给定的工作负载。
Tebaldi 和 Cormcc 等联合 CC 方法可以手动对数据进行分区并在每个分区内使用特定的 CC。但这仍然有些粗粒度。曾经有更细粒度的方法，例如 IC3、CALLAS RP 和 DRP，它们分解每个事务，并在事务工作负载的静态分析的指导下管道化这些部分的执行。
更进一步，我们是否可以使用并发控制 CC 来改变形状以使用任何有助于通过学习此工作负载中的访问模式来最大化吞吐量的策略？
这就是本文所研究的内容。该框架有一个聪明的名字：Polyjuice。
Polyjuice 设计使用这些作为要调整的策略参数。
主要分为三大类。
- 读取控制策略：等待依赖项以及读取哪个版本（已提交或未提交）。
- 写入控制策略：等待依赖关系以及是否使此写入对其他事务的未来读取可见。
- 交易验证政策
- 何时验证：事务可以在执行期间的任何时间验证其访问，而不是仅在提交时验证。早期验证可以更快地中止交易，从而减少浪费的工作。
- 验证方法：基于提交时间戳或基于依赖图
Silo
- Polyjuice 很大程度上建立在 Silo 的基础上。Polyjuice 使用 Silo 的验证/提交算法，并从该算法中得出其正确性。
- 由于 Polyjuice 使用 Silo 的验证/提交检查，因此 Polyjuice 提交的任何事务都是 Silo 会提交的事务。
- 由于Silo 安全，Polyjuice 也应该是安全的。
然后，Polyjuice 专注于提高性能，将正确性转移给 Silo 的验证程序。
Silo 的主要贡献是基于乐观并发控制 ( OCC) 的提交/验证协议，该协议提供可串行性，同时避免对只读记录进行所有共享内存写入。
Polyjuice 是使用 Silo 的代码库用 C++ 实现的，只需将 Silo 的并发控制机制替换为 Polyjuice 的基于策略的算法即可。Polyjuice 还依赖 Silo 基于快照的执行来服务只读事务。我猜 Silo 是一种基于 OCC 的算法。
Polyjuice设计
对于每个数据对象，Polyjuice 存储最新提交的数据以及每个对象的访问列表。访问列表包含所有已变为可见的未提交写入以及读取访问。Polyjuice 使用并发运行的工作线程池：每个工作线程根据学习到的策略表查找要遵循的 CC 细粒度操作/策略来执行事务。
在策略表中，每一列都是对要应用的策略操作的查找。即，有多少个动作维度就有多少个列。
每一行都是系统可能处于的状态集合中的一种状态。也就是说，有多少种状态，策略表中就有多少行。这个状态空间由事务类型（记住，我们事先知道所有事务类型，因为它们是系统中的存储过程）和事务正在执行的访问标识（事务中调用读/写访问的静态代码位置）的卡方积组成。
列/操作空间由四类列/操作组成：等待操作、读取版本、写入可见性、早期验证。后三列是布尔值，而等待操作列包含一个整数，表示多值操作（例如，如何等待依赖事务）。
OSDI21 演示很好地解释了策略表和查找。值得一阅，看看如何通过示例直观地实现这一描述。
该策略表的局限性在于假设每种事务类型都是预先知道的，并且与存储过程一样可用。但我认为，如果允许用户进行其他临时在线事务处理，这种方法也是可行的。当然，这会降低这种方法在性能和吞吐量方面的优势，但由于采用了 Silo 风格的验证检查，其正确性仍然存在。因此，我认为这种方法具有一定的灵活性。
训练
策略表是通过使用进化式强化学习方法对工作量进行离线训练来学习的。学习的第一步是创建初始策略群。然后，我们测试每个策略的吞吐量，选出 8 个策略进入下一轮。然后，我们以 4 种不同的方式对这 8 种策略进行变异，每种策略共有 5 种变异（包括原始策略）。变异的方式包括翻转布尔值、改变区间的整数值等。这种测试和变异重复进行多次迭代。每次迭代都会考虑/测试 8*5=40 个策略，剪枝后得到 8 个最佳策略，然后对其进行变异，在下一次迭代中再次得到 40 个策略进行测试。(事实上，Polyjuice 并没有使用交叉方法来产生最佳策略之间的后代，因为发现这种方法效果并不好）。
这种训练是尽力而为，并不能保证达到最优，因为它可能会陷入局部最优。但在实践中，我们发现这种方法效果很好。Polyjuice 可以在 100 次迭代中学习 309K TPS 策略。训练暂时在一台机器上进行；每次迭代需要 80 秒，因此 100 次迭代需要两个多小时。
评估
对于低竞争工作负载（如在 TPC-C 中使用过多仓库），I/O 成为瓶颈，而 CC 的改进并不能带来吞吐量的增加。因此，评估的重点是在具有 2 个 NUMA 节点的 56 核英特尔机器上进行的中度竞争或重度竞争工作负载。每个 NUMA 节点有 28 个内核（至强 Gold 6238R 2.20GHz）和 188GB 内存。
在 1 个仓库（高度竞争）的情况下，Polyjuice 的性能提高了 45%。使用 8 个仓库（中度竞争）时，Polyjuice 提高了 19%。但在低争用情况下（使用更多数量的仓库），Silo 和 Cormcc 优于 Polyjuice。对于 48 个仓库（每个工人对应一个本地仓库），Polyjuice 比 Silo 稍慢（8%），尽管 Polyjuice 学习的策略与 Silo 相同。这是因为 Polyjuice 需要在每个元组中维护额外的元数据，这会影响缓存的本地性。因此，可以说开头的观点仍然成立：没有一种适用于所有工作负载的最高算法，尽管 Polyjuice 已经接近这一目标。
该论文还展示了对 TPC-E 的评估，以展示 Polyjuice 如何仍然能够管理由于更复杂的基准和更多交易而增加的操作空间。最后，根据真实电子商务网站的轨迹（从 Kaggle 下载）进行评估，以展示 Polyjuice 在不同日期的工作负载变化情况下的表现。对于分析的迹线，Polyjuice 需要重新训练 15 次才能覆盖 196 天的时间。
总结
- 如果您知道自己的工作负载，那么您就不需要 Polyjuice，可以使用最适合您的工作负载的 CC 算法。
- 但工作负载很少为人所知且稳定。
- 如果工作负载变化太快/显着或者任何工作负载都没有模式（几乎是随机的），那么 Polyjuice 就再也没有帮助了。
- 否则，Polyjuice 可以通过推断和使用训练确定的正确细粒度 CC 策略来提高高争用和中争用下的吞吐量。