NOC-NOC 面向性能最优的分布式事务 (sigmod 24) 论文阅读
NOC-NOC：面向性能最优的分布式事务（sigmod 24）
1 摘要
以前的分布式事务性能最优的工作都致力于研究优化事务的读操作，但忽略了影响写整体性能的关键因素–写操作，本文通过优化写操作进一步提高分布式事务的性能；
提出了一个新的设计目标：NOC-NOC
利用 双视图 + 版本向量技术 实现了两个满足这一设计目标的新事务算法
2 介绍
只读事务优化文章：
SNOW 不可能定理：只读事务优化的4个属性无法同时满足，只能同时满足其中3个：
- S 严格可串行化 strict serializability，要求事务之间按开始时间严格有序，不存在内部操作的并发执行，比如查询余额一定在转账之后；
- N 操作非阻塞 Non-Blocking Operation，要求读操作能立刻被响应，不会因为等待其他节点或锁占用而延迟；
- O 每个读操作仅有单个回复 One Response Per Read，要求读操作只读一个版本；
- W 允许同时存在冲突写事务 Write Transactions that Conflict，要求允许对同一个数据项更改的写事务在并发进行‘
满足 N+O 的算法：延迟最低的只读事务算法
满足 S+W 的算法：功能最强的只读事务算法，因为其简化了上层应用的开发
NOCS 定理：只读事务的最优性能为：在一致性视图的情况下，同时满足 NOC 三个属性：
- N 非阻塞 non-blocking
- O 单轮通信 one round communication
- C 常量元数据 constant amount of data，需要满足跨分区数据的一致性读的视图
元数据用于计算只读事务所需的一致性视图，比如事务ID，时间戳；
作者进行的实验：
LORA 和 RA-NOC 在事务数量小的情况下，或写比例小的情况下，延迟较低，吞吐量较高；
但是当事务数量增加并且写事务增多时，整体的延迟在变大，吞吐量在降低；
由于 NOC 仅优化了只读事务，在写事务占比较多时，锁竞争会导致整体的吞吐量降低；
左右两幅图都是既有只读事务，又有写的事务；
近几年提出的几个隔离级别：
RC：读已提交
RA：读原子性：在RC的基础上，避免了断裂读取异常 fractured reads
关于断裂读取异常：read committed 可能会导致下面的情景
| T1 | T2 |
|---|---|
| begin ( x = 1, y = 1 ) | begin ( x = 1, y = 1 ) |
| read x = 1 | |
| write x = 2 | |
| write y = 3 | |
| commit | |
| read y = 3 | |
| commit |
RA：T2 要么对 T1 所有更新操作感知，要么都不感知，这里之前读了 x = 1，那么后面对 y 的读取只能是1；
RA+：在RA隔离级别的基础上，同时能够保证 read your writes
read your write （Session Guarantees for Weakly Consistent Replicated Data 94）
没有 read your write 的情景：通常出现在弱一致性系统中
一个用户改了个新的密码，在重新登录的过程中，由于密码副本是分布式存储，有一个副本异步更新的较慢，用户输入新更改的密码去登录，结果查询到的是那个未来得及更新的副本，导致收到密码无效。而 read your write 能够保证客户端在登录过程中始终读取最新的密码
TCC：事务之间执行能够保证因果一致性
能在并发情况下，满足下面两个事务的顺序关系，即先执行T1，后执行T2
T1：用户A浏览了商品X并将其添加到购物车
T2：用户B查看了用户A的购物车，并在此基础上给用户A推荐了相关商品Y
TCCv：TCC基础上使其收敛
NOC-NOC标准：
只读事务需要满足前面三个原则（第一个NOC）
并且由SNOW定理证明的，在存在冲突写事务的情况下，只读事务算法只能满足 N+O+W
本文在SNOW基础上，写事务算法如果满足写的 NOC，能够最大化提升系统性能；
定理3.1 在SI隔离级别下，没有事务算法能够同时满足 NOC-NOC 这6个准则
定理3.2 RC隔离级别下，没有事务算法能够同时满足 NOC-NOC 这6个准则 + 全局可见性
图3是在RC隔离级别下，T2读取到的数据应该是一样的，都是最开始的数据；
在满足NOC-NOC + 全局可见性下，T2会读到T1未提交的数据，违背了RC；
否则，如果T2读到的是原始数据，在T1先开始T2后开始的情况下，在a中T2读不到T1更新的数据，也违背了NOC-NOC里的 $$O_R$$
本文设计了两个算法，分别在 RA+ 和 TCCv 隔离级别下满足 NOC-NOC 6个准则的算法
RA-NOC2 算法
LSV：局部安全视图
GSV：全局安全视图
疑问：（GPT）
1、事务算法指的是？并发控制算法
2、RA会出现不可重复读吗？会，仅比RC多个避免 fracture read
3、它们跟2PL，OCC有什么联系和区别？
RAMP-family 和 Eiger-family 算法主要用于分布式环境下的事务处理，以解决分区数据一致性和可靠性的问题；（数据分布在不同的分区）
而2PL 和 OCC 算法通常用于单机或分布式环境下的本地事务处理，以解决并发控制和一致性问题；
4、如何理解TCCv的收敛？
RAMP算法提出的背景：
传统的隔离级别是针对单节点环境下的异常定义的，而分布式数据库会出现新的异常
主要原因在于多个节点上同一个事务的更新可能不是原子可见的
受网络等影响，某些节点未完成更新，使得同一个读操作读分布在不同副本上的数据时，读取的版本不一致；
RAMP算法保证了多节点上读取结果的一致性；