一、概述
发送者感知的混洗允许在单个区块内混洗交易（the shuffling of transactions），以便尽可能地将来自同一发送者的交易分开。这样做是为了减少在并行执行期间的冲突和重新执行次数。我们的端到端性能基准测试显示，发送者感知的混洗可以将 TPS 提高25%
二、动机
BlockSTM（我们的并行执行框架）的性能在很大程度上取决于输入交易类型 —— 特别是相邻交易之间的依赖关系。如果相邻交易的读写集不是重叠的，BlockSTM 的性能最佳，因为它们之间不会发生冲突，因此乐观执行的交易不需要任何重新执行。基于上述想法，我们引入了一种发送者感知的交易混洗，旨在通过将来自同一发送者的交易至少放置在定义的窗口（window）大小（w）之外，尽可能地减少相邻交易之间的冲突。这是因为来自同一发送者的交易总是冲突的，因为它们倾向于读写到同一组资源（发送者的账户余额和序列号）。
三、规范
我们将 冲突窗口大小 定义为交易可以相互冲突的大小。混洗器在最后 conflict_window_size 个交易中维护一个已添加到区块中的发送方集合。当尝试向区块中选择新交易时，混洗器会尝试找到一个不属于窗口中冲突发送方的交易。如果找到了，它会将找到的第一个非冲突交易添加到区块中；如果没有找到，则会保留顺序，并将剩余区块中的第一个交易添加到区块中。在排序方面，它始终维护以下不变性：
- 同一发送方的所有交易在混洗前后的相对顺序保持不变。
- 如果交易之间不存在冲突，则跨不同发送方的所有交易的相对顺序也将保持不变。换句话说，如果输入区块中每个发送方只有一个交易，则输出顺序将保持不变。
混洗算法的时间复杂度为O(n)，以下是其伪代码。
loop:
if 一个发送方在上一次迭代中离开了滑动窗口，
then: 我们将该发送方的第一个待处理交易添加到区块中
else 当我们有原始交易顺序中要处理的交易时
取一个新的交易，
if 它有冲突，则将其添加到待处理集合中
else 将其添加到区块中
else
从待处理交易中取出第一个交易并将其添加到区块中
四、参考实现
一个实现已经在主代码中完成。它受到链上配置的限制，因此在网络上执行治理提案之前不会生效。
五、风险和缺陷
风险1：系统行为的变化。这改变了围绕交易排序的现有行为 —— 如果有系统隐式依赖于现有的交易排序，则它们将会中断。
六、未来潜力
- 在将来，我们可以扩展这个想法，获取一组交易的读/写集（通过预执行或来自 Move 方面的支持），并使混洗智能到足以将冲突的交易相互分离。
- 这个想法可以进一步扩展为更智能的交易选择进入区块。如果一组交易的读/写集事先已知，我们可以选择非冲突的交易进入区块，以尽可能地使并行执行高效。
七、建议的实施时间表
- 第一阶段（已完成）：代码编写完成，包括单元测试和端到端测试
- 第二阶段（已完成）：在 Previewnet 上进行性能验证
八、建议的部署时间表
- 第一阶段（计划中）：剪切到 v1.4 版本发布
- 第二阶段（计划中）：在 devnet 上进行链上配置更改
- 第三阶段（计划中）：在 testnet 上进行链上配置更改
- 第四阶段（计划中）：通过治理提案在 mainnet 上进行链上配置更改