如何从理论上避免这类并行任务交错执行时的冲突问题

[h0099]

假设有一个进程，其内部有一个全局的锁和两个（或多个）互相不知道对方存在的异步任务正在运行

和一个外部数据库中的某个表，假设表只有一个字段并且是UNIQUE约束。数据库每SESSION的隔离级别是READ COMMITTED

任务的目的是向表中插入一些行

1. 但会先查询表中已有行（此时有START TRANSACTION），然后排除掉表中已有的
2. 再向进程范围的全局锁声明占用了即将插入的已排除了表中已有行的行
3. 然后向表插入这些行，在COMMIT表明成功插入后
4. 再去进程全局锁释放此前占有的行

因此当存在两个并行执行的这个任务时可能有符合如下 uml 时序图的流程：

线程 1->数据库: 读取已有行
数据库->+线程 1:
进程锁->线程 1: 已被锁的行
线程 1->进程锁: 锁新插入行
    线程 2->数据库: 读取已有行
    数据库->+线程 2:
    进程锁->线程 2: 已被锁的行
    线程 2->进程锁: 锁新插入行
线程 1->-数据库: 插入未被锁的行
线程 1->进程锁: 释放新插入行锁
    线程 2->-数据库: 插入未被锁的行
note right of 数据库: DUPLICATED
    线程 2->进程锁: 释放新插入行锁

利用 https://www.websequencediagrams.com 在线渲染：

DUPLICATED表示线程 2试图插入已经被线程 1插入了的行，因此违反了数据库层的UNIQUE约束

对上图填充实际数据后

线程 1->数据库: 读取已有行\nSTART TRANSACTION\nSELECT * FROM t
数据库->+线程 1: 0 row returned
进程锁->线程 1: 已被锁的行\n0 行
线程 1->进程锁: 锁新插入行\n1 行：a
    线程 2->数据库: 读取已有行\nSTART TRANSACTION\nSELECT * FROM t
    数据库->+线程 2: 0 row returned
线程 1->-数据库: 插入未被锁的行\nINSERT INTO t\nVALUES ('a');\nCOMMIT;
线程 1->进程锁: 释放新插入行锁\n0 行
    进程锁->线程 2: 已被锁的行\n0 行
    线程 2->进程锁: 锁新插入行\n1 行：a
    线程 2->-数据库: 插入未被锁的行\nINSERT INTO t\nVALUES ('a');\nCOMMIT;
note right of 数据库: #1062\nDuplicate entry 'a'
    线程 2->进程锁: 释放新插入行锁\n0 行

可以看出在符合这个时序图的流程中进程锁和数据库层事务都无法阻止这种冲突，因为

1. 线程 2访问数据库表中已有行的时机早于线程 1``COMMIT他的INSERT，所以线程 2无法预见线程 1将在未来插入行a（由于READ COMMITED事务隔离级别）
2. 线程 2访问进程锁的时机又晚于线程 1完成COMMIT和释放进程锁中的行a，所以线程 2也不知道此前线程 1已经插入了行a

提出的解决方法：

1.延后线程 2查询数据库的时机：

如果让线程 1等待线程 2释放了进程锁之后才开始查询表，那么线程 1就可以从表中得知行a此前已经被插入了（但线程 1并不知道这是线程 2插入的）

这实际上就是serializability（linearizability和serializability的区别），即完全放弃了并行度，同一时间只能有一个任务在工作。这也意味着进程锁此时也是完全无用的，因为他的主要目的是让其他线程知道当前有哪些行即将插入表（但还没有COMMIT）

2.延后线程 1释放进程锁的时机：

如果让线程 1等待线程 2查询进程锁之后再去释放锁，那么线程 2就可以知道不应该插入行a

缺点：

• 无法确定进程锁中的行是否已经插入还是即将插入（如果不额外查询表）
• （ 1 和 2 的共同缺点）任务之间相互等待造成了逻辑耦合，即线程 1必须知晓线程 2的存在并等待线程 2开始查询进程锁后线程 1才能释放锁并完成他的任务销毁线程。实际上线程不应该知道其他线程也在同时运行，他们本应只需要与进程范围的全局锁通信
• 实践中并非所有要插入的行都是大概率冲突的，那么会造成大量线程一直在等待自己插入的行被其他线程查询，然后再释放他们，也就是潜在的内存泄露。当然这可以通过增加超时或定长FIFO stack（见下）来缓解

3.数据库事务隔离级别从READ COMMITED降至READ UNCOMMITED

回顾经典之

可见降至READ UNCOMMITED后允许dirty read的发生，也就是对于如下时序：

线程 2可以在线程 1已经向数据库发送了INSERT，但还没发送COMMIT从而提交事务之前就得知行 a已经被插入了

缺点： 对于最初的时序流程

仍然不适用，因为没有任何约束使得线程 2不能在线程 1向数据库发送INSERT之前就查询表，自然也就没有发生dirty read

4.缓存最近插入的行的进程范围全局FIFO stack

线程 1->数据库: 读取已有行\nSTART TRANSACTION\nSELECT * FROM t
数据库->+线程 1: 0 row returned
进程锁->线程 1: 已被锁的行\n0 行
FIFO->线程 1: 最近插入的行\n0 行
线程 1->进程锁: 锁新插入行\n1 行：a
    线程 2->数据库: 读取已有行\nSTART TRANSACTION\nSELECT * FROM t
    数据库->+线程 2: 0 row returned
线程 1->-数据库: 插入未被锁的行\nINSERT INTO t\nVALUES ('a');\nCOMMIT;
线程 1->FIFO: 追加最近插入的行\na
线程 1->进程锁: 释放新插入行锁\n0 行
    进程锁->线程 2: 已被锁的行\n0 行
    FIFO->线程 2: 最近插入的行\n1 行：a
    线程 2->进程锁: 锁新插入行\n1 行：b
    线程 2->-数据库: 插入未被锁的行\nINSERT INTO t\nVALUES ('b');\nCOMMIT;
    线程 2->FIFO: 追加最近插入的行\na
    线程 2->进程锁: 释放新插入行锁\n0 行

如果线程 1保证在释放进程锁的行 a之前先将其 push ，那么线程 2就可以在 pop 时发现行 a已经被插入，尽管这时进程锁中表明行 a没有被锁（即正准备插入但尚未COMMIT）

缺点：

• pop 时只能获得最近一次其他线程所插入的一个行，假如在线程 1push行 a后又有线程 3push 或 pop 了其他行，那么线程 1仍然不知道行 a已经被插入。因此实践中需要使用List等可随机访问的结构来在所有历史中查找已插入的行（这相当于直接去数据库查表）
• 控制 stack 的容量使其不应该比表中所有行还多，也不应该比单次任务所插入的行数还少（而这两个都是运行时变量不可能提前预知），实践中应该能够缓存最近数次或时间上最近数分钟（同样需要根据运行时 tunning ）内完成的任务所插入的行
• 即便容量再大也仍然无法从理论上避免这类冲突（频繁查表也不能）

5.2PC （两阶段提交）或2PL （两阶段锁）以协调任务

6.外部程序控制锁以协调任务，如各类 message queue 或 zookeeper

由于我对分布式 /并行计算理论不甚了解，所以希望 V2EX 的各位 v 友们能够补充更多理论上以及实践中如何处理这类问题的方案

[h0099]

@yangbowen github.com/n0099/TiebaMonitor/issues/32#issuecomment-1401757287

> 其实你只要说这句就够了，其它诸如 intel/arm risc/cisc 指令集之争等在这个问题当中似乎是无关的吧。

是的，但我完全不知道在数据库领域中相近的概念叫什么，于是只好就我了解到这些概念的领域来说。
LL/SC 无疑比 CAS 来得强大。

---

> 请注意本讨论串中的所有`dirty read`（除了上述那一个）都应该查找替换为`phantom read`（以及 typo 之`COMMITTED`少打了一个`T`），因为我最开始看着这图时就写错了：
>
> > 可见降至 READ UNCOMMITED 后允许 dirty read 的发生
>
> 另外请注意尽管`non-repeatable read`和`phantom read`之间看起来很相似（他们的 UML 时序图甚至是完全相同的），但本质完完全全两码事：

然而不论您称呼它 dirty read 还是 phantom read ，我都仍然不知道那都是什么意思。
另外我觉得用时序图考虑并发和同步问题其实不太好，容易被误导的。而且较低的一致性约束下有可能发生根本就不能画成时序图的情形，比方说线程 1 的操作次序在线程 2 看来和在线程 3 看来可以是不一样的。

[h0099]

@yangbowen https://github.com/n0099/TiebaMonitor/issues/32#issuecomment-1401828929

> 而我也大量使用了`.NET`所提供的这类`RMW 同步原语`如

Interlocked 操作应该是封装的处理器提供的指令。x86 的指令本就提供原子性，而且大都可以直接加前缀`LOCK`（例如`ADD [data],eax`变成`LOCK ADD [data],eax`）就提供强内存序保障的原子性。而微软早就把这样的操作封装成了 Interlocked 开头的 API 函数。合理推测 .NET 的这些原语遵循了类似的命名。

---

> 事实核查：截止 2023 年 1 月，我仍然无法直接在生产环境中删除进程锁，因为我观察到在删除后仍然会造成这种`race condition`并且无法得到合理解释

听上去有点有趣，希望能搞明白是为什么就好了。我是觉得你这里理应是不需要多一个进程锁的。

---

> 然而 so 人早已道明真相： https://stackoverflow.com/questions/1171749/what-does-a-transaction-around-a-single-statement-do
>
> > 这可能归因于“迷信”编程，或者它可能表明对数据库事务性质的根本误解。一种更仁慈的解释是，这只是过度应用一致性的结果，这是不恰当的，这是爱默生委婉语的另一个例子：
> > 愚蠢的一致性是小脑袋的妖精，
> > 受到小政治家、哲学家和神学家的崇拜
>
> 我的评价是：疑似当代 https://en.wikipedia.org/wiki/Cargo_cult https://en.wikipedia.org/wiki/Cargo_cult_programming https://stevemcconnell.com/articles/cargo-cult-software-engineering/

比起说是过度应用一致性，我看不如说是不理解一致性。`START TRANSACTION`和`COMMIT`并不是只要加了就没有一致性方面问题的魔法，需要正确理解和运用。
话说比起说是`小政治家、哲学家和神学家`的崇拜，我倒感觉像是伊欧那样的程序员会有的崇拜（（

---

> 然而更现实的问题是乐观并发控制是用于协调`SELECT+UPDATE`而不是`SELECT+INSERT`的，而我这里又只有`INSERT`没有`UPDATE`，所以加了`ROW_VERSION`和对应的程序中乐观并发控制业务逻辑也无济于事

是的，它是乐观的。然后这个问题的话……我知道了，它通过`SELECT`只能把乐观的条件放在某个行上，但是不可能放在`满足某种条件的行现在还不存在`这件事上，是不是？
想要的行为是数据库在满足对应条件的行被`INSERT`时打破这一乐观锁，但既然这样的行现在还不存在，就没法把这个条件绑定在哪个行上面，对不对？
那样的话，也许一个可行的办法是：首先`INSERT`“空的”行（除了标识符 /主键那样的东西以外不包含有意义的数据，只有 dummy 值），失败也行。换言之哪个线程抢到了这个`INSERT`的机会根本无所谓。然后在`将空行 UPDATE 为有意义的行`这个操作上做乐观锁。

---

> 这就是阁下之后所提到的 https://en.wikipedia.org/wiki/ABA_problem 而乐观并发控制本质上也是为了解决这个

不这不是。ABA 问题，顾名思义，就是说 CAS 的时候读到的值跟之前读到的值是一样的，所以 CAS 会成功，但其实这个值已经被其它线程修改过又改回来了，不应该让这个 CAS 成功。如果这里的正确行为只依赖于被 CAS 的这个值本身的话这是不成问题的，成问题的情况是虽然这个共享变量本身是一样的但因为修改过所以已经不能当作仍然满足条件了。最典型的就是它是个指针，被修改过又改回来了，但它指向的东西已经不一样了，这种变化却不能被这个指针变量上的 CAS 捕获。
ABA 问题比这个单调递增计数器的问题困难得多。

---

> 然而将单个值上升到集合层面就麻烦的多（什么 pythonic ）
> 我能想出来的是线程 1 读取后就改一下`ROW_VERSION`，也就是说`ROW_VERSION`跟踪的不再是这行被改动了几次而是被读了几次
> 但这实际上就意味着又回到了`并行度=1`的[serializability]( https://en.wikipedia.org/wiki/Serializability)，因为这时只有强迫同时只有一个线程在读写才能保证每个线程的`ROW_VERSION`都是他想要的（即`COMMIT`时也没被其他事务由于`SELECT`而改变）

读取的时候当然不应该修改`ROW_VERSION`吧。这个版本记号显然应该跟踪写入而不是读取。
顺带一提，跨线程共享内存的同步问题里也有`ROW_VERSION`的类似做法，也就是使用两倍宽度的 CAS ，存放一个指针+一个版本记号。然后会碰到另一种问题，就是版本记号可能会回卷。

---

> 然而 testandset 同样是一种 atomic 操作，他的名字就已经暗示了他是把两个常见的原本是独立的原子操作给封装成又一个原子操作

当然了。但组成它的两个操作本身只有 共识数 1 ，而 test-and-set 具有 共识数 2 ——如果您只有两个线程的话，让它们彼此等待对方就好啦。

---

> 事实核查：截止 2023 年 1 月，仍然没有 RDBMS 实现了杨博文阁下所提出的这种全新的具有颠覆性的基于 changeset 的事务隔离机制

我不相信。况且您都能说出 changeset 这个词，怎么想这东西都应该早已出现在 RDBMS 领域当中了吧。
还是说，RDBMS 实在是不希望迫使它们的调用者在没有出错的情况下被迫`ROLLBACK`，而且可能反复地？
而 Intel TSX 指令集 的做法是只是试一试能不能用这种机制无锁地完成，只要发生任何冲突、中断或者其它原因就让所有冲突方 transaction abort ，此时调用者需要回退到更可靠（性能差一点）的实现，例如全局互斥锁。也因此当他们想要禁用这个指令集的时候就直接让所有事务总是立即失败就行啦。

---

> 您在写`贴吧辅助工具皇帝鸡血神` @bakasnow 最爱的易语言？

显然我在写伪代码。而且我显然不喜欢这样写代码，只不过在照顾某位依赖机器翻译的人罢了。

---

> 为什么这里会有 ABA

很简单：某个线程写入了这个指针，然后把不再被用到的旧指针释放了。然后某个线程又做了一遍这个过程。但之前被释放了的指针可能又被分配到，于是此期间一直没有读过这个变量的另一个线程 compare 到了跟它之前读到的相同的指针，但这个相同的指针指向的值其实已经不一样了。所以 ABA 。
而在 GC 环境下不用显式释放这个指针，GC 引擎只会在真的没有别的线程在引用这个指针了之后才会释放它（上面看到一样的指针以为数据也没变的那个线程，也保持着对它的一个引用，从而也会避免它被 GC ），所以就没有这个问题。

> 什么整数？

跟`ROW_VERSION`基本上是一个功能只是叫法可能不一样的一个整数。

---

> 我还在做生信，而且做的比以前大了很多。我没有去找过 lys ，这边事情比较多，基本上都在做研究

您好。原来您就是他们先前说的 西兔 。久仰大名。

[h0099]

@n0099 https://github.com/n0099/TiebaMonitor/issues/32#issuecomment-1403181038

https://github.com/n0099/TiebaMonitor/issues/32#issuecomment-1401757287
> 是的，但我完全不知道在数据库领域中相近的概念叫什么，于是只好就我了解到这些概念的领域来说。

而`四叶头子 CS 硕士 PLT 理论中级高手仏皇 irol 阁下`对此早有预言： https://t.me/s/n0099official/1777

---
> LL/SC 无疑比 CAS 来得强大。

enwiki 进一步澄清：
> 如果发生任何更新，存储条件保证失败，即使加载链接读取的值已经恢复。因此，LL/SC 对比读取后跟[比较和交换]( https://en.wikipedia.org/wiki/Compare-and-swap)(CAS) 更强，如果旧值已恢复，后者将不会检测更新（请参阅[ABA 问题]( https://en.wikipedia.org/wiki/ABA_problem)）。

因此 LLSC 主要是为了解决 CAS 可能遇到的 ABA 问题
然而截止 2023 年 1 月，即便是早已被彻底禁用了的 intel tsx 指令集中也没有 arm 中的[ldarx]( https://www.ibm.com/docs/en/xl-c-aix/13.1.0?topic=functions-lqarx-ldarx-lwarx-lharx-lbarx)

---
> 请注意本讨论串中的所有`dirty read`（除了上述那一个）都应该查找替换为`phantom read`（以及 typo 之`COMMITTED`少打了一个`T`），因为我最开始看着这图时就写错了：
>
> > 可见降至 READ UNCOMMITED 后允许 dirty read 的发生
>
> 另外请注意尽管`non-repeatable read`和`phantom read`之间看起来很相似（他们的 UML 时序图甚至是完全相同的），但本质完完全全两码事： [stackoverflow.com/questions/11043712/what-is-the-difference-between-non-repeatable-read-and-phantom-read]( https://stackoverflow.com/questions/11043712/what-is-the-difference-between-non-repeatable-read-and-phantom-read)

反转了不是所有的`dirty read`都要查找替换为`phantom read`，而是应该替换为`non-repeatable read`
具体而言有

- https://github.com/n0099/TiebaMonitor/issues/32#issue-1527862957
> 可见降至 READ UNCOMMITED 后允许 dirty read 的发生，也就是对于如下时序：
>
> 没有任何约束使得线程 2 不能在线程 1 向数据库发送 INSERT 之前就查询表，自然也就没有发生 dirty read

中的措辞`dirty read`是正确的

- https://github.com/n0099/TiebaMonitor/issues/32#issuecomment-1401199725
> 请注意即便 COMMIT 了也不代表其他并行事务就能知道您已经 COMMIT 了 INSERT 了行 a （也就是 dirty read ），因为在防止 dirty read 的事务隔离级别（ REPEATABLE READ 及以上，如 SERIALIZED ）
>
> 如果阁下的 INSERT 生效是指让其他事务看得见所 INSERT 的行（ dirty read ），那么必须等到 COMMIT 之后才有可能发生 dirty read ，因此此处的所有 SESSION 的事务隔离级别都是 READ COMMITTED 而不是最弱的 READ UNCOMMITTED
>
> 我没有说把事务隔离级别从 REPEATABLE READ 降低到 READ COMMITTED 就一定会发生 dirty read

需要替换为`non-repeatable read`

---
> 然而不论您称呼它 dirty read 还是 phantom read ，我都仍然不知道那都是什么意思。

`dirty read`就是当前事务中的`SELECT`读到其他*尚未*COMMIT 的事务中此前做出的`UPDATE/INSERT`，也就是`READ UNCOMMITTED`（跟事务隔离级别同名但不是指隔离级别），所以防止`dirty read`的隔离级别叫`READ COMMITTED`
`non-repeatable read`就是当前事务中的`SELECT`读到其他*已经*COMMIT 的事务中此前做出的`UPDATE/INSERT`，也就是`READ COMMITTED`（只能读到其他已经 COMMIT 事务中做出的所有变化，排除了尚未 COMMIT 事务的），所以防止`non-repeatable read`的隔离级别叫`REPEATABLE READ`
`phantom read`在`REPEATABLE READ`事务隔离级别的基础之上额外避免了读到其他事务`INSERT`的行（当前事务此前没有读到过的）
例如一个`REPEATABLE READ`隔离级别的事务中执行两次`SELECT COUNT(*) FROM table`，而另一个事务在这两次执行之间`INSERT`了一行，那么两次 count 结果就是不同的，而在防止`phantom read`的隔离级别`SERIALIZED`中就会保证相同

---
> 另外我觉得用时序图考虑并发和同步问题其实不太好，容易被误导的。

那也没有更好的办法表达并行事件之间的关联了

---
> 而且较低的一致性约束下有可能发生根本就不能画成时序图的情形，比方说线程 1 的操作次序在线程 2 看来和在线程 3 看来可以是不一样的。

阁下是指在现代多核 cpu 中由于每个 core 都有着自己的 L1cache 所以跑在不同 core 上的指令有可能在读取同一个地址上不同的 L1cache 值（也就是 desync ）吗？我的建议是滥用`volatile`

[h0099]

@n0099 https://github.com/n0099/TiebaMonitor/issues/32#issuecomment-1403243840

github.com/n0099/TiebaMonitor/issues/32#issuecomment-1401828929

> Interlocked 操作应该是封装的处理器提供的指令。x86 的指令本就提供原子性，而且大都可以直接加前缀 LOCK （例如 ADD [data],eax 变成 LOCK ADD [data],eax ）就提供强内存序保障的原子性。而微软早就把这样的操作封装成了 Interlocked 开头的 API 函数。合理推测 .NET 的这些原语遵循了类似的命名。

xp 时有有`Interlock*()`的 win32api 了：learn.microsoft.com/en-us/windows/win32/api/winnt/nf-winnt-interlockedcompareexchange
.NET CLR 不过就是直接 P/Invoke 过去调`kernel32.dll`而已，linux 可能是调 syscall 甚至直接生成 asm
interlock 的命名词源可能是 en.wikipedia.org/wiki/Interlock

---
> 听上去有点有趣，希望能搞明白是为什么就好了。我是觉得你这里理应是不需要多一个进程锁的。

我也认为引入`SELECT ... FOR UPDATE`所在数据库层产生的`IX 锁`后其已经代替了进程锁的职责那就应该删除有关代码减少复杂度
然而在现代后端中台微服务娱乐圈带架构师们眼中看来反而不应该像 90s 的企业级 COBOL 程序员那样写上千行的 PL/SQL 以依赖于数据库层而不是后端程序的逻辑：www.v2ex.com/t/909780#r_12600576
所以他们更喜欢在程序中实现进程锁，或是引入各种 mq zookeeper 那样专门负责协调任何并行任务的消息 middleware 来重新实现数据库层的锁，并将这称为从数据库层解耦出了业务逻辑还避免了 vendor lock （尽管大型系统中本就极难更换 RDBMS ）

---
> 比起说是过度应用一致性，我看不如说是不理解一致性。START TRANSACTION 和 COMMIT 并不是只要加了就没有一致性方面问题的魔法，需要正确理解和运用。

本来把多个 SQL 语句套进一个事务里就只是为了让他们变成一个原子操作，使得这些语句所造成的影响（`INSERT/UPDATE`造成写）要么都执行成功（`COMMIT`），要么都执行失败（`ROLLBACK`），所以保证了数据一致性
而这的所谓原子很明显不保证在并行事务时不会有任何`race condition`，只有事务隔离级别才能用来控制允许哪些类型的`race condition`发生
数据一致性也只是保证不会发生在一个事务中两个`INSERT`语句只有一个所产生影响实际生效了而另一个却消失了（比如 duplicated 错误导致另一个`INSERT`被`ROLLBACK`），事务在此同样不能保证在并行事务时不会发生两个事务都`SELECT+INSERT`了相同的行（也就是本帖最初的问题）
RDBMS 厂商们为了实现 ANSI SQL 4 大事务隔离级别都不约而同的选择了主要基于阻塞等待锁的实现而不是主要基于无锁数据结构所封装的 cpu 指令集提供的无锁原子操作

---
> 话说比起说是小政治家、哲学家和神学家的崇拜，我倒感觉像是伊欧那样的程序员会有的崇拜（（

与此同时截止 2023 年 1 月，`四叶沙其马里 1 群皇帝日冕开发者`伊欧神仍在步`奥利金德 rust 研究潮`高强度 star 相关 repo：

---
> 是的，它是乐观的。然后这个问题的话……我知道了，它通过 SELECT 只能把乐观的条件放在某个行上，但是不可能放在满足某种条件的行现在还不存在这件事上，是不是？

一个朴素的`SELECT`不可能产生这种约束，所以有`FOR UPDATE`后缀所产生的`IX 锁`（以及`FOR SHARE`产生`IS 锁`），而产生`X 锁`很明显是会造成其他事务阻塞的
因此 EFCore 开发者 MSFT 员工将其归类为悲观并发控制：github.com/dotnet/efcore/issues/26042

---
> 想要的行为是数据库在满足对应条件的行被 INSERT 时打破这一乐观锁，但既然这样的行现在还不存在，就没法把这个条件绑定在哪个行上面，对不对？

因为乐观并发控制依赖于一个已有的`ROW_VERSION`值，如果行根本不存在那您只能定义个 NULL 来表示

---
> 那样的话，也许一个可行的办法是：首先 INSERT“空的”行（除了标识符 /主键那样的东西以外不包含有意义的数据，只有 dummy 值），失败也行。换言之哪个线程抢到了这个 INSERT 的机会根本无所谓。

这就是`INSERT IGNORE`

---
> 然后在将空行 UPDATE 为有意义的行这个操作上做乐观锁。

然而乐观并发控制本就依赖于观察`UPDATE`所返回的`affected rows`是 0 还是 1 来得知是否有其他事务已经修改了`ROW_VERSION`
那也同样可以观察`INSERT IGNORE`所返回的`affected rows`是 0 还是 1

所以 www.v2ex.com/t/908047#r_12564068 的 @codehz 早已道明：
> 我来捋一捋，这一大段先查询再插入的目的是防止重复的插入？有没有一种可能用 INSERT ON DUPLICATE 来解决呢？直接忽略重复插入的冲突有影响吗

他所说的`INSERT INTO ... ON DUPLICATE KEY UPDATE`实际上就是数据库层的 CAS 原子操作：
dev.mysql.com/doc/refman/8.0/en/insert-on-duplicate.html
stackoverflow.com/questions/45652775/thread-safety-of-insert-on-duplicate-key-update
stackoverflow.com/questions/27544540/how-exactly-is-insert-on-duplicate-key-update-atomic

> 并不需要`INSERT INTO ... ON DUPLICATE KEY UPDATE`（ PGSQL 又称`UPSERT`）因为这是仅插入而没有更新或删除（即 CRUD 只有 C ） 也可以直接`INSERT IGNORE`： [dev.mysql.com/doc/refman/8.0/en/insert.html]( dev.mysql.com/doc/refman/8.0/en/insert.html)
>
> > If you use the IGNORE modifier, ignorable errors that occur while executing the INSERT statement are ignored. For example, without IGNORE, a row that duplicates an existing UNIQUE index or PRIMARY KEY value in the table causes a duplicate-key error and the statement is aborted. With IGNORE, the row is discarded and no error occurs. Ignored errors generate warnings instead.
>
> 然后在每次`INSERT`后[`SELECT ROW_COUNT`]( dev.mysql.com/doc/refman/8.0/en/information-functions.html#function_row-count)就可以知道少了多少行没有被插入（由于 DUPLICATE 或其他错误）（但只有行的数量，而非精确的对应关系，如果需要知道具体少插入了哪些行仍然需要`SELECT`之前插入的行范围）
>
> 但不论 UPSERT 还是 IGNORE 都是从数据库层面缓解问题，他不是保证永不发生 DUPLICATE 错误，而是保证发生 DUPLICATE 错误后您的程序也能跑（因为一个改成了 UPDATE ，一个将 ERR 降级到 WARN ）

然而又有新的问题：
> 而我更需要避免的是这种类似 DUPLICATE 造成了数据冗余，但又完全符合数据库层的 UNIQUE 约束的问题：
> 
> 可以看到两个线程都插入了“完全一致”的行，除了 time 字段值分别是 1674453494 和 1674453492 （因此两者 INSERT 时都不会触发 DUPLICATE 错误） 而这是因为右侧线程在左侧线程于`12:39:54.874436`时间`COMMIT`之前就已经`SELECT`了，所以右侧不知道左侧即将`INSERT` time 为 1674453492 的“重复”行
> 对此问题我当然可以选择写一个基于[window function]( learnsql.com/blog/sql-window-functions-cheat-sheet/)的`DELECT`的后台 crontab （或是线程每次`INSERT`后都尝试`DELETE`一次）来定期执行删除这类冗余的“重复”行 但这跟`UPSERT/INSERT IGNORE`类似仍然是缓解问题而不是解决问题 而且`DELETE`作为事（`INSERT`）后补救也不可能解决更罕见（线程在同一秒内完成所有任务）的两个线程插入的所有字段都相同（也就是触发 DUPLICATE 错误）的场景

---
> 不这不是。ABA 问题，顾名思义，就是说 CAS 的时候读到的值跟之前读到的值是一样的，所以 CAS 会成功，但其实这个值已经被其它线程修改过又改回来了，不应该让这个 CAS 成功。如果这里的正确行为只依赖于被 CAS 的这个值本身的话这是不成问题的，成问题的情况是虽然这个共享变量本身是一样的但因为修改过所以已经不能当作仍然满足条件了。最典型的就是它是个指针，被修改过又改回来了，但它指向的东西已经不一样了，这种变化却不能被这个指针变量上的 CAS 捕获。

en.wikipedia.org/wiki/Compare-and-swap#ABA_problem 进一步指出：
> 有可能在读取旧值和尝试 CAS 之间，某些其他处理器或线程两次或多次更改内存位置，以便它获取与旧值匹配的位模式。如果这个看起来与旧值一模一样的新位模式具有不同的含义，就会出现问题：例如，它可能是回收地址或包装版本计数器。

---
> ABA 问题比这个单调递增计数器的问题困难得多。

> 跟 ROW_VERSION 基本上是一个功能只是叫法可能不一样的一个整数。

> 顺带一提，跨线程共享内存的同步问题里也有 ROW_VERSION 的类似做法，也就是使用两倍宽度的 CAS ，存放一个指针+一个版本记号。

然而 DCAS 中的额外自增就类似乐观并发控制中使用的自增`ROW_VERSION`：
> 对此的一般解决方案是使用双倍长度的 CAS (DCAS)。例如，在 32 位系统上，可以使用 64 位 CAS 。下半场用于举行柜台。操作的比较部分将指针和计数器的先前读取值与当前指针和计数器进行比较。如果它们匹配，则交换发生——新值被写入——但新值有一个递增的计数器。这意味着如果发生 ABA ，虽然指针值相同，但计数器极不可能相同

---
> 然后会碰到另一种问题，就是版本记号可能会回卷。

回顾经典之 logrotate：
> 对于 32 位值，必须发生 2^32 的倍数操作，导致计数器 wrap 并且在那一刻，指针值也必须偶然相同

en.wikipedia.org/wiki/ABA_problem#Tagged_state_reference：
> 如果“tag”字段回绕，针对 ABA 的保证将不再有效。然而，据观察，在当前现有的 CPU 上，并使用 60 位标签，只要程序生命周期（即不重新启动程序）被限制为 10 年，就不可能进行回绕；此外，有人认为，出于实际目的，通常有 40-48 位的标签就足以保证不会回绕。由于现代 CPU （特别是所有现代 x64 CPU ）倾向于支持 128 位 CAS 操作，这可以提供针对 ABA 的可靠保证。

---
> 很简单：某个线程写入了这个指针，然后把不再被用到的旧指针释放了。然后某个线程又做了一遍这个过程。但之前被释放了的指针可能又被分配到，于是此期间一直没有读过这个变量的另一个线程 compare 到了跟它之前读到的相同的指针，但这个相同的指针指向的值其实已经不一样了。所以 ABA 。

en.wikipedia.org/wiki/ABA_problem 指出：
> 如果一个项目从列表中移除，删除，然后分配一个新项目并将其添加到列表中，由于[MRU]( en.wikipedia.org/wiki/Cache_replacement_policies#Most_recently_used_(MRU))内存分配，分配的对象与删除的对象位于同一位置是很常见的。因此，指向新项的指针通常等于指向旧项的指针，从而导致 ABA 问题。

---
> 而在 GC 环境下不用显式释放这个指针，GC 引擎只会在真的没有别的线程在引用这个指针了之后才会释放它（上面看到一样的指针以为数据也没变的那个线程，也保持着对它的一个引用，从而也会避免它被 GC ），所以就没有这个问题。

enwiki 同时声称：
> 另一种方法是推迟回收已删除的数据元素。延迟回收的一种方法是在具有[自动垃圾收集器]( en.wikipedia.org/wiki/Garbage_collection_(computer_science))的环境中运行算法；然而，这里的一个问题是，如果 GC 不是无锁的，那么整个系统就不是无锁的，即使数据结构本身是无锁的。

---
> 读取的时候当然不应该修改 ROW_VERSION 吧。这个版本记号显然应该跟踪写入而不是读取。

真这样做最现实的问题这些行基本上就没法被其他事务读取了（如果自增`ROW_VERSION`是在数据库层静默执行（如通过`TRIGGER`）实现的而不是执行 SQL 的程序主动`SELECT+UPDATE`，除非是后者那么程序可以在只读不写的事务中省略`UPDATE SET ROW_VERSION += 1`来避免惊扰其他并行的后续事务使其以为乐观并发控制的资源竞争失败了（也就是 CAS 中同样存在的`false-positive`））

---
> 当然了。但组成它的两个操作本身只有 共识数 1 ，而 test-and-set 具有 共识数 2 ——如果您只有两个线程的话，让它们彼此等待对方就好啦。

经典 mutex 阻塞锁
然而我无法理解 en.wikipedia.org/wiki/Consensus_(computer_science)#Consensus_number 表格中为什么声称 CAS 等原子操作的共识数是 $\infty$ 所以他们可以用于包裹任何操作

---
> 我不相信。况且您都能说出 changeset 这个词，怎么想这东西都应该早已出现在 RDBMS 领域当中了吧。

RDBMS 中的 changeset 是 MVCC 中的`SNAPSHOT`，主要用于实现`REPEATABLE READ`中禁止`non-repeatable read`的需求
github.com/n0099/TiebaMonitor/issues/32#issuecomment-1401625868 早已道明：
> > 虽然`TRANSACTION`中的不同语句可以间隔任意久的时间，但数据库引擎对于开着的`TRANSACTION`肯定是要保持某些状态记录的
>
> 也就是 mysql 默认事务隔离级别`REPEATABLE READ`下需要对每个事务每个`SELECT`所读到的每一行都做缓存（被称作 SNAPSHOT ）[dev.mysql.com/doc/refman/8.0/en/innodb-consistent-read.html]( dev.mysql.com/doc/refman/8.0/en/innodb-consistent-read.html) 这也是其他使用 MVCC 的 RDBMS 实现 ANSI SQL 中要求的 4 个事务隔离级别之`REPEATABLE READ`的常规做法 http://mbukowicz.github.io/databases/2020/05/01/snapshot-isolation-in-postgresql.html www.postgresql.org/docs/current/transaction-iso.html

企业级 orm 如 EFCore 中的 changeset 是 changetracking 的结果集：learn.microsoft.com/en-us/ef/core/change-tracking/
tbm.Crawler 中的 changeset 是基于 EFCore changetracking 的输出对每次爪巴后对一些表的影响的集合：
github.com/n0099/TiebaMonitor/blob/2f84a4ab96c07e0e1d7055d945ce9bcae9085a90/crawler/src/Tieba/Crawl/Saver/SaverChangeSet.cs#L11
github.com/n0099/TiebaMonitor/blob/2f84a4ab96c07e0e1d7055d945ce9bcae9085a90/crawler/src/Tieba/Crawl/Saver/BaseSaver.cs#L29

---
> 还是说，RDBMS 实在是不希望迫使它们的调用者在没有出错的情况下被迫 ROLLBACK ，而且可能反复地？

真这样做可能会违反`ANSI SQL`，当然从历史上看是先有 DB2 后有标准，而在 RDBMS 厂商们最初引入事务这个包裹复数 SQL 的概念时可能就业已设计为了`COMMIT`几乎不会失败：
> github.com/n0099/TiebaMonitor/issues/32#issuecomment-1401433577
>
> > 但不太能理解的是为什么它一定要让其它事务阻塞等待，而不是先返回不可靠的`SELECT`结果，如果有冲突的话再让`COMMIT`失败，整个事务被`ROLLBACK`，而且`截至 COMMIT 成功之前调用者必须把 SELECT 结果视为不可靠的，不能当真`呢？
>
> github.com/n0099/TiebaMonitor/issues/32#issuecomment-1401199725 早已做出循环论证：
>
> > 因为 COMMIT 本就极少会产生错误（ stackoverflow.com/questions/3960189/can-a-commit-statement-in-sql-ever-fail-how ）

而从现在的分布式网络角度来看更容易遇到的是不知道`COMMIT`是否成功了（比如 node 卡死了无法响应，或是网络故障导致响应丢包），也就是一个介于确定性的二值`成功 /失败`之间的状态

---
> 而 Intel TSX 指令集 的做法是只是试一试能不能用这种机制无锁地完成，只要发生任何冲突、中断或者其它原因就让所有冲突方 transaction abort ，此时调用者需要回退到更可靠（性能差一点）的实现，例如全局互斥锁。也因此当他们想要禁用这个指令集的时候就直接让所有事务总是立即失败就行啦。

这就像在使用乐观并发控制时要判断`INSERT/UPDATE`所返回的`affected rows`是 0 还是 1 ，而在封装了此类操作的 orm 如[EFCore]( learn.microsoft.com/en-us/ef/core/saving/concurrency)中会直接给您 throw 一个比通用的数据库服务端异常更具体的[`DbUpdateConcurrencyException`]( learn.microsoft.com/en-us/dotnet/api/microsoft.entityframeworkcore.dbupdateconcurrencyexception)异常

---
> 显然我在写伪代码。而且我显然不喜欢这样写代码

然而我也看不懂中文编程之 github.com/wenyan-lang/wenyan/issues/617

> 只不过在照顾某位依赖机器翻译的人罢了。

不开机翻我也慢慢读懂（ 30\~100words/min ），而开机翻更快（ 500\~700 字 /分钟）也方便大段引用复制粘贴

[h0099]

@yangbowen https://github.com/n0099/TiebaMonitor/issues/32#issuecomment-1403425152

> 然而截止 2023 年 1 月，即便是早已被彻底禁用了的 intel tsx 指令集中也没有 arm 中的[ldarx]( www.ibm.com/docs/en/xl-c-aix/13.1.0?topic=functions-lqarx-ldarx-lwarx-lharx-lbarx)

所以 ldarx 就是 LL/SC 的 intrinsic 咯。
TSX 指令集的话很容易实现 LL/SC 的效果的：事务中相当于所有的读都是 LL ，所有的写都是 SC 。因为仅当事务成功提交的情况下写才会生效（能被看到副作用，而不是透明地被状态回滚）。事务要么成功提交——此时事务中所有的读都没有别的地方在写，并且所有的写生效；要么失败——此时所有的写都不生效。
写起来大概是这样的感觉：
```cpp
std::mutex g_mtx;
std::map<int, int> g_map;
if (_xbegin() == 0xFFFF) {
// proceed to transactional access to global data
g_map.insert(3, 4);
_xend();
} else {
// fallback to mutex
std::unique_lock lock(g_mtx);
g_map.insert(3, 4);
}
```
里面的所有读写都会被追踪事务性。然后 _xend 的时候，如果没有冲突的话写入会生效，相当于成功的 LL/SC ；反之如果失败的话处理器会把所有状态回滚到 _xbegin 的地方，然后 _xbegin 会返回一个表示失败的返回值。（是的，if 里已经执行过的代码变成就像没发生一样）
总之，可以把 TSX 理解为加强版但是更容易失败的 LL/SC 。
和你们数据库这边的事务原理是差不多的嘛，除了因为是 CPU 实现的所以它可以把调用者已经执行过的代码给时间倒流成根本没有发生过。

---

> `dirty read`就是当前事务中的`SELECT`读到其他_尚未_COMMIT 的事务中此前做出的`UPDATE/INSERT`，也就是`READ UNCOMMITTED`（跟事务隔离级别同名但不是指隔离级别），所以防止`dirty read`的隔离级别叫`READ COMMITTED`

就是当前事务读到**尚未**提交的事务中已经做出的`UPDATE/INSERT`。咦那如果删除行的话也会因为`dirty read`而已经就看不见那个行了吗？
另外，读到尚未提交的事务中已经做出的修改，那么……
- 即便如此，当前（读取）事务也能成功提交吗？
- 如果能的话，即便写入的事务还没提交，当前事务也能成功提交吗？
- 如果能的话，也就是说甚至于写入的事务可能后来又`ROLLBACK`了，但`dirty read`的事务却成功提交了？
- 如果都能的话，那确实挺 dirty 的。可以想见如果不注意的话能够发生一些麻烦的错误。
- 反过来说，假如它像乐观锁那样，能读到但是这种情况下会被`ROLLBACK`，那其实倒是不难避免数据不一致。

> `non-repeatable read`就是当前事务中的`SELECT`读到其他_已经_COMMIT 的事务中此前做出的`UPDATE/INSERT`，也就是`READ COMMITTED`（只能读到其他已经 COMMIT 事务中做出的所有变化，排除了尚未 COMMIT 事务的），所以防止`non-repeatable read`的隔离级别叫`REPEATABLE READ`

**已经**`COMMIT`的事务当然要被读到的吧，否则岂不是`COMMIT`了个寂寞。也许一万年前某个早已提交的事务插入了某一行，那您总不能说要`REPEATABLE READ`的话您到现在都还看不见那一行。
比起这个，我想顾名思义来说，应该是说当前事务**开始之后**其它事务的**已经提交的**写入被当前事务中的读取看到，所以当前事务中对同一数据的两次读取可能看到的状态是不一致的，而且这种不一致并不来自于当前事务中的写入。所以说“读取是不可重复的”，所以对事务的原子性有一定的违背吧？
为了避免这种违背原子性和隔离的情形，大概就需要为每个事务维护一个状态 snapshot （实现上可以不用拷贝整个状态，但上层表现上看起来就像开始事务之后进入了一个跟其它事务独立的平行空间一样）。

> `phantom read`在`REPEATABLE READ`事务隔离级别的基础之上额外避免了读到其他事务`INSERT`的行（当前事务此前没有读到过的）
> 例如一个`REPEATABLE READ`隔离级别的事务中执行两次`SELECT COUNT(*) FROM table`，而另一个事务在这两次执行之间`INSERT`了一行，那么两次 count 结果就是不同的，而在防止`phantom read`的隔离级别`SERIALIZED`中就会保证相同

也就是跟 non-repeatable read 差不多，但是针对插入行而不是修改行。
即便如此，即便在最高的隔离级别`SERIALIZED`当中，如果两个事务各自执行了一次`SELECT COUNT(*) FROM table`（都读到了一开始的`COUNT`），然后各自`INSERT`了一行，而且在`INSERT`的行的某一列记录了`INSERT`时的`COUNT`。那么，是否仍然可以这两个事务全部成功提交，而且得到了两个这个记录相同（都是“两边都没有`INSERT`之前的`COUNT`”）的行？
显然如果所有访问全都带全局互斥锁的话这种情形是不可能的。但在没有互斥锁但有最高隔离级别的事务的情况下呢？

[h0099]

@yangbowen https://github.com/n0099/TiebaMonitor/issues/32#issuecomment-1403539880

> 那也没有更好的办法表达并行事件之间的关联了

比画时序图要严密但是不直观的，是描述操作之间的 [happens-before]( https://en.cppreference.com/w/cpp/atomic/memory_order#Formal_description) 约束吧。A happens-before B 就是说 B 能看到 A 的副作用。happens-before 具有传递性。
这样的话虽然不太直观，但是不会像时序图只描述了可能发生的时序的一种，而是能够只依赖于确实被约束的时序关系。

---

> 阁下是指在现代多核 cpu 中由于每个 core 都有着自己的 L1cache 所以跑在不同 core 上的指令有可能在读取同一个地址上不同的 L1cache 值（也就是 desync ）吗？我的建议是滥用`volatile`

这是不对的。实际上`volatile`并没有这个意思，也不是用来解决这种情况的。
“跨线程共享变量使用`volatile`避免不同步问题”是一个被广泛地重复的错误的说法。请不要继续重复这个错误了。
MSVC 让`volatile`写具有[release 语义]( https://en.cppreference.com/w/cpp/atomic/memory_order#Release-Acquire_ordering)，`volatile`读具有[acquire 语义]( https://en.cppreference.com/w/cpp/atomic/memory_order#Release-Acquire_ordering)。但这是非标准的扩展，而且 acquire 读 release 写也不足以解决所有线程间同步问题。

---

> xp 时有有`Interlock*()`的 win32api 了： https://learn.microsoft.com/en-us/windows/win32/api/winnt/nf-winnt-interlockedcompareexchange
> .NET CLR 不过就是直接 P/Invoke 过去调`kernel32.dll`而已，linux 可能是调 syscall 甚至直接生成 asm

我觉得应该不会实现成 P/Invoke 或者 syscall 了对应的系统 API 。这些 Interlocked 操作是很轻量的，基本上是单个原生指令的封装。实现成 P/Invoke 甚至 syscall 的话就太慢了。理应是直接产生对应的汇编指令的。
就像它不会把两个 int32 的加法实现成 P/Invoke 某个 API ，即便假如真的有这样的 API 。

---

> 然而又有新的问题：
>
> > 而我更需要避免的是这种类似 DUPLICATE 造成了数据冗余，但又完全符合数据库层的 UNIQUE 约束的问题：
> > 
> > 可以看到两个线程都插入了“完全一致”的行，除了 time 字段值分别是 1674453494 和 1674453492 （因此两者 INSERT 时都不会触发 DUPLICATE 错误） 而这是因为右侧线程在左侧线程于`12:39:54.874436`时间`COMMIT`之前就已经`SELECT`了，所以右侧不知道左侧即将`INSERT` time 为 1674453492 的“重复”行
> > 对此问题我当然可以选择写一个基于[window function]( https://learnsql.com/blog/sql-window-functions-cheat-sheet/)的`DELECT`的后台 crontab （或是线程每次`INSERT`后都尝试`DELETE`一次）来定期执行删除这类冗余的“重复”行 但这跟`UPSERT/INSERT IGNORE`类似仍然是缓解问题而不是解决问题 而且`DELETE`作为事（`INSERT`）后补救也不可能解决更罕见（线程在同一秒内完成所有任务）的两个线程插入的所有字段都相同（也就是触发 DUPLICATE 错误）的场景

……原来是这样啊。我有点明白了。
那这完全不是`INSERT ON DUPLICATE`的问题啊，而是，实际上无法用`UNIQUE`约束来正确描述您想要的约束：时间戳不一定相等，但不可以有时间戳连续且消息相同的行（消息相同的两行之间必须间隔有时间戳介于其间且消息与其不同的行）。
那这还挺难办的，因为`UNIQUE`约束看上去只考虑相等，并没有“其它不相等的行的某一列的范围”那种上下文信息。

这个部分之前没看明白，现在才明白了。那我觉得如果你不想那么“补救”的话，那这个问题可以分成以下几个部分：
- 你需要的约束是什么？就`消息相同的两行之间必须间隔有时间戳介于其间且消息不同的行`这种约束而言，它是“如果**存在**这样（时间戳介于其间且消息不同）的行的话那么满足约束”，显然它不可能用`UNIQUE`这种“如果**不存在**这样（对应列相同）的行的话那么满足约束”的约束实现。
- 有没有办法让数据库引擎明白而且能够检查这样的约束？还是说只有做`SELECT`然后由调用者根据`SELECT`结果才能进行这一约束的检查？
- 如果能的话，能不能让数据库引擎根据这一约束检查决定要不要让`INSERT`成功？而且，原子地——其它事务的`INSERT`可能破坏这一约束，所以约束检查和`INSERT`必须原子地发生。
- 如果不能的话，能不能让数据库引擎保证：要么`影响这一约束的那部分 SELECT 结果在 SELECT 到 INSERT 成功期间没有变化`，要么`INSERT 不发生效果，或者说没有任何其它事务能够既看到这个 INSERT 的效果又成功提交`

[h0099]

@yangbowen https://github.com/n0099/TiebaMonitor/issues/32#issuecomment-1404405047

> TSX 指令集的话很容易实现 LL/SC 的效果的：事务中相当于所有的读都是 LL ，所有的写都是 SC 。因为仅当事务成功提交的情况下写才会生效（能被看到副作用，而不是透明地被状态回滚）。事务要么成功提交——此时事务中所有的读都没有别的地方在写，并且所有的写生效；要么失败——此时所有的写都不生效。

类比数据库的事务隔离级别的话，应该是相当于最高的`SERIALIZED`吧？不会看到其它核心尚未成功提交的写，所以不 dirty read ；也不会看到其它核心在本事务进行期间成功提交的写（这种情况下对方的事务和本事务都会失败，不会成功提交），所以也不 non-repeatable-read 。但其实并不真的保证这些提交了或没提交的写一定不会被读到，而是说也许暂时读到了，但一定会事务失败，处理器会把架构状态回滚，程序无法基于“读到了但又被回滚了”的读取而影响行为。总之就是个乐观锁的`SERIALIZED`吧。

[h0099]

@yangbowen https://github.com/n0099/TiebaMonitor/issues/32#issuecomment-1404461843

> RDBMS 厂商们为了实现 ANSI SQL 4 大事务隔离级别都不约而同的选择了主要基于阻塞等待锁的实现而不是主要基于无锁数据结构所封装的 cpu 指令集提供的无锁原子操作

这跟数据库引擎的实现里面有没有采用 CPU 指令集提供的无锁原子操作其实关系不大。这更多是关于它的接口采取怎样的设计的问题。单个 SQL 语句发生在远远超过单个 CPU 指令的时间跨度上。（显然需要执行十万甚至九万个指令来 parse 并执行您的一个 SQL 语句）
引擎内部基于阻塞等待锁 /自旋锁还是基于无锁数据结构，跟用户的 SQL 事务跟其他用户的 SQL 事务之间是通过锁还是无锁来解决竞态问题，并不需要有对应关系。

---

> 经典 mutex 阻塞锁
> 然而我无法理解 https://en.wikipedia.org/wiki/Consensus_(computer_science)#Consensus_number 表格中为什么声称 CAS 等原子操作的共识数是 ∞ 所以他们可以用于包裹任何操作

建议阅读该词条引用 [Wait-Free Synchronization]( https://cs.brown.edu/~mph/Herlihy91/p124-herlihy.pdf) 。
特别地，其中说到：

> The basic idea is the following: each object has an associated _consensus number_, which is the maximum number of processes for which the object can solve a simple consensus problem. In a system of _n_ or more concurrent processes, we show that it is impossible to construct a wait-free implementation of an object with consensus number _n_ from an object with a lower consensus number.

[h0099]

@n0099 https://github.com/n0099/TiebaMonitor/issues/32#issuecomment-1404661123

https://github.com/n0099/TiebaMonitor/issues/32#issuecomment-1403425152

> 里面的所有读写都会被追踪事务性。然后 _xend 的时候，如果没有冲突的话写入会生效，相当于成功的 LL/SC ；反之如果失败的话处理器会把所有状态回滚到 _xbegin 的地方，然后 _xbegin 会返回一个表示失败的返回值。（是的，if 里已经执行过的代码变成就像没发生一样）

然而如果此时其他并行线程读取了`g_map`并得知`key=3`的存在，cpu 能回滚那个线程此前的读取使其又忘记了`key=3`的存在吗？

> 和你们数据库这边的事务原理是差不多的嘛

然而数据库事务的`COMMIT`无法失败

> 除了因为是 CPU 实现的所以它可以把调用者已经执行过的代码给时间倒流成根本没有发生过。

数据库事务的`ROLLBACK`也会导致该事务中所有做出的`INSERT/UPDATE/DELETE`对表造成的影响都被回退
或者说在`COMMIT`之前这些影响都只存在于 mysql [undo log]( https://dev.mysql.com/doc/refman/8.0/en/innodb-undo-logs.html)和[change buffer]( https://dev.mysql.com/doc/refman/8.0/en/innodb-parameters.html#sysvar_innodb_change_buffering)中
然而这同样无法回退某个`READ UNCOMMITTED`事务隔离级别的事务此前已经获得的读取结果，因为客户端已经知道了

---
> 就是当前事务读到**尚未**提交的事务中已经做出的`UPDATE/INSERT`。咦那如果删除行的话也会因为`dirty read`而已经就看不见那个行了吗？

否
https://dev.mysql.com/doc/refman/8.0/en/innodb-transaction-isolation-levels.html 进一步指出：

> - 使用 READ COMMITTED 还有额外的效果：
> 对于[UPDATE]( https://dev.mysql.com/doc/refman/8.0/en/update.html)or [DELETE]( https://dev.mysql.com/doc/refman/8.0/en/delete.html)语句，InnoDB 只对它更新或删除的行持有锁。WHERE 在 MySQL 评估条件后，释放不匹配行的记录锁 。这大大降低了死锁的可能性，但它们仍然会发生。
> - READ UNCOMMITTED
> [SELECT]( https://dev.mysql.com/doc/refman/8.0/en/select.html) statements are performed in a nonlocking fashion, but a possible earlier version of a row might be used. Thus, using this isolation level, such reads are not consistent. This is also called a [dirty read]( https://dev.mysql.com/doc/refman/8.0/en/glossary.html#glos_dirty_read). Otherwise, this isolation level works like [READ COMMITTED]( https://dev.mysql.com/doc/refman/8.0/en/innodb-transaction-isolation-levels.html#isolevel_read-committed).

实际上`INSERT`也不属于`dirty read`的范围：
https://stackoverflow.com/questions/54063118/read-committed-vs-read-uncommited-if-both-transaction-do-not-rollback

> 您的示例与 Isolation Levels. 这是因为它们影响 readers 行为，而不是 writers ，而在您的示例中只有 writers.
> 您应该参考这篇 BOL 文章：[Understanding Isolation Levels]( https://learn.microsoft.com/en-us/sql/connect/jdbc/understanding-isolation-levels?view=sql-server-2017) 说
> > 选择事务隔离级别不会影响为保护数据修改而获取的锁。无论为该事务设置的隔离级别如何，事务始终会对其修改的任何数据获取独占锁并持有该锁直到事务完成。对于 读取操作，事务隔离级别主要定义保护级别免受其他事务所做修改的影响。

---
> 另外，读到尚未提交的事务中已经做出的修改，那么……
>
> * 即便如此，当前（读取）事务也能成功提交吗？

在数据库事务中`COMMIT`几乎不会失败，所以讨论是否成功是无意义的，除非语境是在分布式数据库网络中

https://github.com/n0099/TiebaMonitor/issues/32#issuecomment-1403243840
> > 还是说，RDBMS 实在是不希望迫使它们的调用者在没有出错的情况下被迫 ROLLBACK ，而且可能反复地？
>
> 真这样做可能会违反`ANSI SQL`，当然从历史上看是先有 DB2 后有标准，而在 RDBMS 厂商们最初引入事务这个包裹复数 SQL 的概念时可能就业已设计为了`COMMIT`几乎不会失败：
>
> > [#32 (comment)]( https://github.com/n0099/TiebaMonitor/issues/32#issuecomment-1401433577)
> > > 但不太能理解的是为什么它一定要让其它事务阻塞等待，而不是先返回不可靠的`SELECT`结果，如果有冲突的话再让`COMMIT`失败，整个事务被`ROLLBACK`，而且`截至 COMMIT 成功之前调用者必须把 SELECT 结果视为不可靠的，不能当真`呢？
> >
> >
> > [#32 (comment)]( https://github.com/n0099/TiebaMonitor/issues/32#issuecomment-1401199725) 早已做出循环论证：
> > > 因为 COMMIT 本就极少会产生错误（ [stackoverflow.com/questions/3960189/can-a-commit-statement-in-sql-ever-fail-how]( https://stackoverflow.com/questions/3960189/can-a-commit-statement-in-sql-ever-fail-how) ）
>
> 而从现在的分布式网络角度来看更容易遇到的是不知道`COMMIT`是否成功了（比如 node 卡死了无法响应，或是网络故障导致响应丢包），也就是一个介于确定性的二值`成功 /失败`之间的状态

---
> * 如果能的话，即便写入的事务还没提交，当前事务也能成功提交吗？

是

---
> * 如果能的话，也就是说甚至于写入的事务可能后来又`ROLLBACK`了，但`dirty read`的事务却成功提交了？

是
所以在`READ UNCOMMITTED`和`REPEATABLE READ`事务隔离级别下不要使用朴素的`SELECT+INSERT/UPDATE`模式如
```sql
SELECT a, b FROM t; -- (1, 2)
UPDATE t SET b = 2+1 WHERE a = 1
```
因为您想要`UPDATE`使得`b=b+1=3`，然而在您`SELECT`到的 b 值可能是来自另一个尚未提交事务中的
```sql
UPDATE t SET b = 2 WHERE a = 1
```
所造成的影响，如果另一个事务最终`ROLLBACK`了那么`2+1`就是错误的

---
> 反过来说，假如它像乐观锁那样，能读到但是这种情况下会被 ROLLBACK ，那其实倒是不难避免数据不一致。

但您可以在此使用乐观并发控制的思维改成
```sql
UPDATE t SET b = 2+1 WHERE a = 1 AND b = 2
```
这样在另一个事务`ROLLBACK`后这个`UPDATE`所返回的`affected rows`是 0 也就是避免了写入错误的`2+1`

https://dev.mysql.com/doc/refman/8.0/en/innodb-transaction-isolation-levels.html 也详细说明了为什么会这样（尽管这段来自对`READ COMMITTED`的陈述但其同样适用于`READ UNCOMMITTED`）：
> 对于[UPDATE]( https://dev.mysql.com/doc/refman/8.0/en/update.html)语句，如果一行已经被锁定，则 InnoDB 执行“半一致”读取，将最新提交的版本返回给 MySQL ，以便 MySQL 判断该行是否符合 WHERE 条件 [UPDATE]( https://dev.mysql.com/doc/refman/8.0/en/update.html)。如果该行匹配（必须更新），MySQL 将再次读取该行，这次 InnoDB 要么锁定它，要么等待锁定它。

---
> 如果都能的话，那确实挺 dirty 的。可以想见如果不注意的话能够发生一些麻烦的错误。

所以实践中很少有人用`READ UNCOMMITTED`事务隔离级别，ANSI SQL 中要求实现主要是为了留一个`escape hatch`作为 DBA 对频繁死锁无计可施时的`last resort`
然而在 PGSQL 中直接实现的更加严格也就是完全禁止`dirty read`：
https://www.postgresql.org/docs/current/transaction-iso.html
> 在 PostgreSQL 中，您可以请求四种标准事务隔离级别中的任何一种，但在内部只实现了三种不同的隔离级别，即 PostgreSQL 的 Read Uncommitted 模式的行为类似于 Read Committed 。这是因为这是将标准隔离级别映射到 PostgreSQL 的多版本并发控制体系结构的唯一明智方法。
> 该表还显示 PostgreSQL 的可重复读实现不允许幻读。这在 SQL 标准下是可以接受的，因为该标准规定了在某些隔离级别下哪些异常不能发生；更高的保证是可以接受的。可用隔离级别的行为在以下小节中详细说明。

以及在各种非传统的 DBMS 如列存储数据库（如 yandex 的 clickhouse ）中根本没有实现事务（主要是为了性能以及实现这些过于复杂），也就是说一切`SELECT`都是`READ UNCOMMITTED`

---
> **已经**`COMMIT`的事务当然要被读到的吧，否则岂不是`COMMIT`了个寂寞。也许一万年前某个早已提交的事务插入了某一行，那您总不能说要`REPEATABLE READ`的话您到现在都还看不见那一行。

然而在`REPEATABLE READ`事务隔离级别下，如果事务 A 在两万年前就业已`SELECT`了某行并一直卡着不`COMMIT/ROLLBACK`，而随后在一万年前时另一个事务 B 对该行做了[DML]( https://dev.mysql.com/doc/refman/8.0/en/glossary.html#glos_dml)并`COMMIT`，那事务 A 仍然不知道事务 B 做了什么

https://dev.mysql.com/doc/refman/8.0/en/innodb-consistent-read.html 进一步指出：
> 假设您在默认 [REPEATABLE READ]( https://dev.mysql.com/doc/refman/8.0/en/innodb-transaction-isolation-levels.html#isolevel_repeatable-read)隔离级别下运行。当您发出一致读取（即普通 [SELECT]( https://dev.mysql.com/doc/refman/8.0/en/select.html)语句）时，InnoDB 为您的事务提供一个时间点，您的查询将根据该时间点查看数据库。如果另一个事务删除一行并在您的时间点分配后提交，您不会看到该行已被删除。插入和更新的处理方式类似。

但又指出`REPEATABLE READ`只是对于 reads 也就是`SELECT`生效，对`INSERT/UPDATE`中由 WHERE 子句所产生的 reads 无效
> 数据库状态的快照适用 [SELECT]( https://dev.mysql.com/doc/refman/8.0/en/select.html)于事务中的语句，不一定适用于 [DML]( https://dev.mysql.com/doc/refman/8.0/en/glossary.html#glos_dml)语句。如果您插入或修改某些行然后提交该事务， 则从另一个并发 REPEATABLE READ 事务发出的[DELETE]( https://dev.mysql.com/doc/refman/8.0/en/delete.html)or[UPDATE]( https://dev.mysql.com/doc/refman/8.0/en/update.html)语句 可能会影响那些刚刚提交的行，即使会话无法查询它们。如果一个事务确实更新或删除了由另一个事务提交的行，那么这些更改对当前事务是可见的。

这也就解释了上文中的
> 在`READ UNCOMMITTED`和`REPEATABLE READ`事务隔离级别下不要使用朴素的`SELECT+INSERT/UPDATE`模式

[h0099]

@n0099 https://github.com/n0099/TiebaMonitor/issues/32#issuecomment-1404661123

> 所以对事务的原子性有一定的违背吧？ 为了避免这种违背原子性和隔离的情形

事务的所谓`atomic`只是说 要么所有语句都成功 要么都失败
因此单个事务中复数个 DML 所造成的影响 要么都会生效 要么都不生效

https://github.com/n0099/TiebaMonitor/issues/32#issuecomment-1403243840
> 本来把多个 SQL 语句套进一个事务里就只是为了让他们变成一个原子操作，使得这些语句所造成的影响（`INSERT/UPDATE`造成写）要么都执行成功（`COMMIT`），要么都执行失败（`ROLLBACK`），所以保证了数据一致性
> 而这的所谓原子很明显不保证在并行事务时不会有任何`race condition`，只有事务隔离级别才能用来控制允许哪些类型的`race condition`发生

---
> 大概就需要为每个事务维护一个状态 snapshot （实现上可以不用拷贝整个状态

mysql innodb 中对 MVCC 的实现是[undo log]( https://dev.mysql.com/doc/refman/8.0/en/innodb-undo-logs.html)：
https://dev.mysql.com/doc/refman/8.0/en/glossary.html#glos_consistent_read
> - 一致性读取
> 一种读取操作，它使用 快照信息根据时间点呈现查询结果，而不管同时运行的其他事务执行的更改。如果查询到的数据已经被另一个事务更改，则根据 undo log 的内容重建原始数据。这种技术通过强制事务等待其他事务完成来 避免一些可能会降低并发性的锁定问题。
> 使用 REPEATABLE READ 隔离级别，快照基于执行第一次读取操作的时间。使用 READ COMMITTED 隔离级别，快照将重置为每个一致读取操作的时间。
> 一致读取是默认模式，在该模式下 InnoDB 处理处于 READ COMMITTED 和 REPEATABLE READ 隔离级别的 SELECT 语句。因为一致读取不会在它访问的表上设置任何锁，所以其他会话可以在对表执行一致读取时自由修改这些表。

因此`REPEATABLE READ`或者说 mysql 所谓的[`Consistent Nonlocking Reads`]( https://dev.mysql.com/doc/refman/8.0/en/innodb-consistent-read.html)就像是一种无锁数据结构

---
> 也就是跟 non-repeatable read 差不多，但是针对插入行而不是修改行

`INSERT/UPDATE/DELETE`3 大 DML 都属于`phantom read`的控制范围，只是我举的例子是`COUNT(*)`所以必须得是`INSERT/UPDATE`才会影响前后`COUNT(*)`的结果
而 so 人 https://stackoverflow.com/questions/11043712/what-is-the-difference-between-non-repeatable-read-and-phantom-read/11044968#11044968 举的例子就更准确：
> 幻读：查询中的所有行前后都具有相同的值，但正在选择不同的行（因为 B 删除或插入了一些）。示例：select sum(x) from table;如果行已添加或删除，即使没有更新受影响的行本身，也会返回不同的结果。

---
> 在最高的隔离级别`SERIALIZED`当中，如果两个事务各自执行了一次`SELECT COUNT(*) FROM table`（都读到了一开始的`COUNT`），然后各自`INSERT`了一行，而且在`INSERT`的行的某一列记录了`INSERT`时的`COUNT`。

这得看两个事务 A 和 B 分别执行`SELECT`和`INSERT`之间的时序：
事务隔离级别|时序|事件
-|-|-
所有|B 在 A 执行`SELECT+INSERT+COMMIT`后`SELECT`|B**会**看到 A 多`INSERT`的一行
`READ UNCOMMITTED`|B 在 A 执行`SELECT+INSERT`（ A 尚未 COMMIT ）后`SELECT`|B**会**看到 A 多`INSERT`的一行
`READ COMMITTED`|B 在 A 执行`SELECT+INSERT`（ A 尚未 COMMIT ）后`SELECT`|B**不会**看到 A 多`INSERT`的一行
`READ COMMITTED`|B 在 A 执行`SELECT+INSERT+COMMIT`后`SELECT`|B**会**看到 A 多`INSERT`的一行
`REPEATABLE READ`|B 在 A 执行`SELECT`后`SELECT`，然后 A 执行`INSERT+COMMIT`|B 的`SELECT`（仅限`SELECT`，因为上文提及通过`UPDATE/INSERT`的 WHERE 子句造成的 read 会绕过`SNAPSHOT`）<br>**永远不会**看到 A 多`INSERT`的一行即便 A 已 COMMIT
`SERIALIZED`|B 在 A 执行完`SELECT`后`SELECT`时阻塞等待 A 执行`INSERT+COMMIT`|B**会**看到 A 多`INSERT`的一行<br>但这并不是`phantom read`因为 B 此前根本没有读到那一行（ B 一直在等待 A`COMMIT`）

---
> 那么，是否仍然可以这两个事务全部成功提交

`COMMIT`几乎不会失败

---
> 而且得到了两个这个记录相同（都是“两边都没有`INSERT`之前的`COUNT`”）的行？

无法，因为事务 B 会阻塞等待 A 的`COMMIT`生效因为 A 的`SELECT COUNT(*) ... FOR SHARE`给这表加了`IS 锁`

---
> 显然如果所有访问全都带全局互斥锁的话这种情形是不可能的。但在没有互斥锁但有最高隔离级别的事务的情况下呢？

https://dev.mysql.com/doc/refman/8.0/en/innodb-transaction-isolation-levels.html 早已指出`SERIALIZABLE`的本质就是给所有`SELECT`末尾追加`FOR SHARE`：
> - SERIALIZABLE
> This level is like [REPEATABLE READ]( https://dev.mysql.com/doc/refman/8.0/en/innodb-transaction-isolation-levels.html#isolevel_repeatable-read), but InnoDB implicitly converts all plain [SELECT]( https://dev.mysql.com/doc/refman/8.0/en/select.html) statements to [SELECT ... FOR SHARE]( https://dev.mysql.com/doc/refman/8.0/en/select.html) if [autocommit]( https://dev.mysql.com/doc/refman/8.0/en/server-system-variables.html#sysvar_autocommit) is disabled

而`FOR SHARE`就是给行加`IS 锁`： https://dev.mysql.com/doc/refman/8.0/en/innodb-locking-reads.html
> 在读取的任何行上设置共享模式锁。其他会话可以读取这些行，但在您的事务提交之前不能修改它们。如果这些行中的任何一行被另一个尚未提交的事务更改，您的查询将等待该事务结束，然后使用最新的值。

https://dev.mysql.com/doc/refman/8.0/en/innodb-locking.html#innodb-shared-exclusive-locks 进一步指出：
> InnoDB supports multiple granularity locking which permits coexistence of row locks and table locks. For example, a statement such as [LOCK TABLES ... WRITE]( https://dev.mysql.com/doc/refman/8.0/en/lock-tables.html) takes an exclusive lock (an X lock) on the specified table. To make locking at multiple granularity levels practical, InnoDB uses [intention locks]( https://dev.mysql.com/doc/refman/8.0/en/glossary.html#glos_intention_lock). Intention locks are table-level locks that indicate which type of lock (shared or exclusive) a transaction requires later for a row in a table. There are two types of intention locks:
> - An [intention shared lock]( https://dev.mysql.com/doc/refman/8.0/en/glossary.html#glos_intention_shared_lock) (IS) indicates that a transaction intends to set a shared lock on individual rows in a table.
> - An [intention exclusive lock]( https://dev.mysql.com/doc/refman/8.0/en/glossary.html#glos_intention_exclusive_lock) (IX) indicates that a transaction intends to set an exclusive lock on individual rows in a table.
> For example, [SELECT ... FOR SHARE]( https://dev.mysql.com/doc/refman/8.0/en/select.html) sets an IS lock, and [SELECT ... FOR UPDATE]( https://dev.mysql.com/doc/refman/8.0/en/select.html) sets an IX lock.
> The intention locking protocol is as follows:
> - Before a transaction can acquire a shared lock on a row in a table, it must first acquire an IS lock or stronger on the table.
> - Before a transaction can acquire an exclusive lock on a row in a table, it must first acquire an IX lock on the table.

[alexfarm]

大神，能麻烦移步看下我的问题吗，https://cn.v2ex.com/t/1008054

[h0099]

本帖后续 https://github.com/n0099/open-tbm/issues/32#issuecomment-1404661123
其他话题 https://z.n0099.net/#narrow/stream/37-parallel