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

[n0099]

原文发表于 https://www.v2ex.com/t/908047

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

和一个外部数据库中的某个表，假设表只有一个字段并且是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友们能够补充更多理论上以及实践中如何处理这类问题的方案

[n0099]

可能会有人抱怨这是 提前优化了未来发生的事 或 将复杂的分布式理论用在这是overkill
但实际上我已经遇到了符合最初那张时序图

中的执行流程的协调问题：

读取已有行是L62~69
已被锁的行是L81
锁新插入行是L86
插入未被锁的行是L87
释放新插入行锁是另一个方法ReleaseAllLocks()： https://github.com/n0099/TiebaMonitor/blob/af625cb481e2e4630f34e4fb3ec9fc7b1a1c9454/crawler/src/Tieba/Crawl/Saver/AuthorRevisionSaver.cs#L97
他出现在 https://github.com/n0099/TiebaMonitor/blob/af625cb481e2e4630f34e4fb3ec9fc7b1a1c9454/crawler/src/Tieba/Crawl/Saver/ReplySaver.cs#L59 被 https://github.com/n0099/TiebaMonitor/blob/af625cb481e2e4630f34e4fb3ec9fc7b1a1c9454/crawler/src/Tieba/Crawl/Facade/BaseCrawlFacade.cs#L72 调用

[n0099]

https://www.v2ex.com/t/908047#r_12562608
codehz 15 小时 14 分钟前 via iPhone
我来捋一捋，这一大段先查询再插入的目的是防止重复的插入？有没有一种可能用 INSERT ON DUPLICATE 来解决呢？直接忽略重复插入的冲突有影响吗

---

https://www.v2ex.com/t/908047#r_12564068
h0099 OP 11 小时 11 分钟前
#2 @codehz 并不需要INSERT INTO ... ON DUPLICATE KEY UPDATE（ PGSQL 又称UPSERT）因为这是仅插入而没有更新或删除（即 CRUD 只有 C ）
也可以直接INSERT IGNORE： https://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就可以知道少了多少行没有被插入（由于 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的DELECT的后台 crontab （或是线程每次INSERT后都尝试DELETE一次）来定期执行删除这类冗余的“重复”行
但这跟UPSERT/INSERT IGNORE类似仍然是缓解问题而不是解决问题
而且DELETE作为事（INSERT）后补救也不可能解决更罕见（线程在同一秒内完成所有任务）的两个线程插入的所有字段都相同（也就是触发 DUPLICATE 错误）的场景

---

https://www.v2ex.com/t/908047#r_12564332
codehz 10 小时 33 分钟前 via iPhone
我记得可以 on duplicate update key=key 这样来忽略 duplicate 而且不修改数据（返回 0 行修改）

---

https://www.v2ex.com/t/908047#r_12564368
h0099 OP 10 小时 29 分钟前
原地 UPDATE 为原值跟 INSERT IGNORE 是类似的
只不过完全静默了 WARN （而 INSERT IGNORE 是将 DUPLICATE ERR 降至 WARN ）

---

https://www.v2ex.com/t/908047#r_12565781
h0099 OP 7 小时 9 分钟前

但不论 UPSERT 还是 IGNORE 都是从数据库层面缓解问题，他不是保证永不发生 DUPLICATE 错误

如果要从数据库层面解决可以尝试

7.SELECT ... FOR UPDATE语法所产生的插入意向排他锁

线程 1 和 2 每次 SELECT 时都通过 WHERE 子句（只取 field=a 的行）缩小了FOR UPDATE所造成的IX 锁的范围（不然没有 WHERE 我怀疑会锁全表，也就是类似于LOCK TABLES ... WRITE）
线程 2 在执行后必须无限期（直到达到innodb_lock_wait_timeout）等待线程 1COMMIT，因为线程 2 想要 SELECT 的行field=a已于此前被线程 1 设置 IX 锁
不难看出此时进程范围的全局锁（进程锁）已经没有存在的必要了，因为他的目的跟 IX 锁是类似的（但他无法目前像 IX 锁那样无限期阻塞任何试图读取进程锁的线程）
实际上 IX 锁同样降低了并行度，因为这跟原文中提出的1.延后线程 2 查询数据库的时机是类似的目的：
都是将任何试图读取某些行（IX 锁是 field=a 的行，1.延后线程 2是所有行，也就是回到了LOCK TABLES）的线程挂起直至正在写入某些行的其他线程COMMIT
也就是说两者都是试图通过serialize最开始读行的过程从而避免后续INSERT时冲突

https://dev.mysql.com/doc/refman/8.0/en/innodb-locking.html#innodb-intention-locks
https://dev.mysql.com/doc/refman/8.0/en/innodb-locking.html#innodb-insert-intention-locks
https://dev.mysql.com/doc/refman/8.0/en/innodb-locking-reads.html
https://stackoverflow.com/questions/21261213/select-for-update-with-insert-into
https://stackoverflow.com/questions/10935850/when-to-use-select-for-update

但人生自古谁无死，不幸地，截止 2022 年 11 月发布的最新版本EFCore 7，我所使用的.NET 企业级 ORM Entity Framework Core中仍未引入任何原生的 IQueryable linq2sql operator 使得其可以被翻译为追加在SELECT末尾的FOR UPDATE： dotnet/efcore#26042 (comment)
目前能用的变通只有额外查询 rawsql 来表示 IX 锁（而不能直接嵌入已有的 linq2sql 中）： https://stackoverflow.com/questions/37984312/how-to-implement-select-for-update-in-ef-core

[n0099]

https://www.v2ex.com/t/908047#r_12587293
daxiguaya 1 天前

1. 图 1 中的"进程锁"清理数据的时机可以调整下,等到没有任何活跃事务的情况下再把它清掉.

2. 图 1 的设计中向"进程锁"插入数据的时机看起来有问题: 如果"线程 1"锁定完后(数据 A)事务处理失败了,那么"线程 2"存在也忽略掉(数据 A). 时机是"线程 1"-"锁新插入行"后,""释放新插入行锁""之前"线程 2"获取"已被锁的行".

PS: 这些是基于单体服务的设计. 我不喜欢用SELECT ... FOR UPDATE,它通常会让我其它功能查询也被无辜的阻塞

---

https://www.v2ex.com/t/908047#r_12589945
h0099 OP 1 天前

1. 那会在有许多线程并行执行事务时造成“饥饿”（ starvation ），因为靠后创建的线程获取不到任何没被锁的行导致其无事可做
2. 如果事务执行失败或者发生其他异常了也会释放锁（ try finally ）。而且为了保险我还加了锁超时，其他线程获取锁时会忽略已经连续锁了 5 分钟的行（数据库不会真卡到 INSERT 一些行都卡上几分钟吧）

这些是基于单体服务的设计

哪怕再怎么分布式（实际上同一个进程里的多线程也已经是分布式了所以才会有这些并行竞争问题），不论是无主还是有主的分布式网络，最终都得往一个单点（接受 INSERT 写操作的单主数据库网络）上竞争资源（插入什么行），那这就需要协调来避免竟态（同时插入导致表里存了重复行，但这会被数据库本身的 UNIQUE 约束给拦截所以导致各个线程收到 duplicate entry 错误，但我又不希望某个线程只是因为插入的一大批行中有一些已经存在了就导致整个事务回滚），除非能让分布式数据库也变成多主网络（ apache hadoop 那样），那每个任务节点就可以只向固定的数据库节点 INSERT （但仍然需要在接受 INSERT 写操作的所有数据库节点之间不断同步数据从而保证不会有相同 key 但 value 却不同的记录，也就是保证数据一致性）

我不喜欢用SELECT ... FOR UPDATE,它通常会让我其它功能查询也被无辜的阻塞

根据 https://dev.mysql.com/doc/refman/8.0/en/innodb-locking.html#innodb-intention-locks 的那张表格
事务 A 中的SELECT ... FOR UPDATE所产生的 IX 锁（有意排他锁）的确会导致事务 B 的普通的SELECT所产生的 S 锁（非有意共享锁）被挂起并一直等待 IX 锁释放（直到innodb_lock_wait_timeout）
但这表格也暗示了事务 A 的 IX 锁不会导致另一个事务 C 的SELECT ... FOR SHARE所产生的 IS 锁被挂起（Compatible），尽管我也不知道这会在哪个事务隔离级别下成立（可能是READ COMMITTED），但阁下的确可以亲自试试看

[n0099]

https://www.v2ex.com/t/908047#r_12595620
daxiguaya 2 天前

1. 我对于"进程锁"所要处理的问题有不一样的看法. 我认为"进程锁"应当能解决你提出的"幻读"的问题,它存的是真正写入的数据. 你担心"无事可做",只能说目前只能保证不会重复插入导致整个事务回滚,这个应该更重要? 关于"饥饿"的问题,如果真的是瓶颈的话,可以提早去识别"垃圾数据": 非当前所有活跃"写事务"需要的数据都是"垃圾数据"

2. 就算有各种释放锁、忽略的机制我认为还是有漏洞(还是上面说的那个时机),关键点在于向"进程锁"写入数据在提交之前. 确实加了些机制容错,但在 "线程 1"向"进程锁"插入数据->处理失败"进程锁"数据 的中间会有"线程 2"读取"进程锁". 如果有理解不对的地方可以直接忽略掉.

PS: SELECT ... FOR UPDATE这个问题我保留观点,还要考虑间隔锁、表锁之类的问题,除非死锁的时候我会去 DEBUG 数据库的锁状态,其它情况我想操这个心 :)

---

https://www.v2ex.com/t/908047#r_12596633
h0099 OP 2 天前

我认为"进程锁"应当能解决你提出的"幻读"的问题

我遇到的不是幻读而是“滞后”读，您可以从图 1 中看出来线程 2 读取进程锁时线程 1 已经释放了线程 1 此前插入并锁的行 a ，而线程 2 此前从数据库中读时还不存在行 a ，所以导致线程 2 从两处取得（时机上一个太早一个太晚）的事实都是不存在行 a

它存的是真正写入的数据

准确地说进程锁缓存着的行在数据库中有 3 种状态：即将 INSERT （还没 COMMIT ），已经 INSERT （ COMMIT 了，只有这个状态下是真正写入的数据），INSERT 失败（ ROLLBACK 了）

只能说目前只能保证不会重复插入导致整个事务回滚,这个应该更重要?

是

提早去识别"垃圾数据": 非当前所有活跃"写事务"需要的数据都是"垃圾数据"

的确可以提前不去生成已经被进程锁占据着的行的数据

在 "线程 1"向"进程锁"插入数据->处理失败"进程锁"数据 的中间会有"线程 2"读取"进程锁"

所以阁下的意思还是建议使用您最初提出的"进程锁"清理数据的时机可以调整下,等到没有任何活跃事务的情况下再把它清掉.
但问题并不在线程 2 在线程 1 还占据着进程锁中的行 a 时去读取进程锁中的行 a ，因为进程锁的目的不就是让线程 2 （或更多后续任务）知道现在行 a 被线程 1 占据着吗？

还要考虑间隔锁、表锁之类的问题

根据 https://dev.mysql.com/doc/refman/8.0/en/innodb-locking.html#innodb-gap-locks

对于使用唯一索引锁定行以搜索唯一行的语句，不需要间隙锁定。（这不包括搜索条件只包括多列唯一索引的某些列的情况；在这种情况下，确实会发生间隙锁定。）例如，如果该 id 列具有唯一索引，则以下语句仅使用一个索引记录锁定 id 值为 100 的行，其他会话是否在前面的间隙中插入行并不重要：
SELECT * FROM child WHERE id = 100;
如果 id 未索引或具有非唯一索引，则该语句会锁定前面的间隙。

而这里的 a 所在的字段是具有 UNIQUE 约束的并且 SELECT 的 WHERE 子句使用=而不是< > BETWEEN 等 range operator ，所以只有 row lock 而没有 gap lock

这里还值得注意的是，不同事务可以在间隙上持有冲突锁。例如，事务 A 可以在一个间隙上持有一个共享间隙锁（间隙 S 锁），而事务 B 在同一间隙上持有一个独占间隙锁（间隙 X 锁）。允许冲突间隙锁的原因是，如果从索引中清除记录，则必须合并不同事务在记录上持有的间隙锁。
间隙锁 InnoDB 是“纯粹抑制性的”，这意味着它们的唯一目的是防止其他事务插入间隙。间隙锁可以共存。一个事务获取的间隙锁不会阻止另一个事务在同一间隙上获取间隙锁。共享和排他间隙锁之间没有区别。它们彼此不冲突，并且它们执行相同的功能。

这应该暗示了SELECT ... WHERE uniq > 1 FOR SHARE（ gap IS ）可以与SELECT ... WHERE uniq > 1 FOR UPDATE（ gap IX ）同时执行

可以明确禁用间隙锁定。如果您将事务隔离级别更改为 READ COMMITTED ，则会发生这种情况。在这种情况下，间隙锁定在搜索和索引扫描中被禁用，并且仅用于外键约束检查和重复键检查。
使用隔离级别 READ COMMITTED 还有其他影响 。在 MySQL 评估 WHERE 条件后，释放不匹配行的记录锁。对于 UPDATE 语句，InnoDB 进行“半一致”读取，这样它将最新提交的版本返回给 MySQL ，以便 MySQL 可以确定该行是否匹配 UPDATE 的 WHERE 条件

这可能也就是我在生产中只要使用 mysql 默认的REPEATABLE READ隔离级别就会疯狂死锁的原因

除非死锁的时候我会去 DEBUG 数据库的锁状态,其它情况我想操这个心 :)

建议无脑降低事务隔离级别至READ COMMITTED

[yangbowen]

可以看出在符合这个时序图的流程中进程锁和数据库层事务都无法阻止这种冲突，因为
1. 线程2访问数据库表中已有行的时机早于 线程1COMMIT ``他的INSERT，所以`线程2`无法预见`线程1`将在未来插入行`a`（由于`READ COMMITED`事务隔离级别）
2. `线程2`访问进程锁的时机又晚于`线程1`完成`COMMIT`和释放进程锁中的行`a`，所以`线程2`也不知道此前`线程1`已经插入了行`a`

蛮怪的。我不懂数据库但是，既然线程2在START TRANSACTION之后的读SELECT * FROM t，由于线程1的写的成功COMMIT，其读取值已不再正确，那么线程2的COMMIT不该失败吗？否则它岂不是TRANSACTION了个寂寞？
如果TRANSACTION的存在并没有让事务中的这两个语句产生什么关系，换言之COMMIT只是让INSERT生效的话。那么既然您的两个（或更多个）线程，在INSERT和COMMIT之间并没有与全局锁或者其它线程有任何交互，那么从开始INSERT到COMMIT起作用的这段时间对于该线程以外是没有看得见的效果的。INSERT立即生效，跟INSERT然后立即COMMIT然后生效，从外面看起来是一样的。所以，这和您不用TRANSACTION应当没有任何差别。

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

这应该也是不对的吧？允许dirty read的发生，应该并不是说保证它会发生？

[yangbowen]

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

我的理解是这里需要的行为实际上是一个原子的 RMW操作 ——如何插入这一行是依赖于 相同的行是否已被插入 这个要读取到的条件的。这个读操作+插入操作整体上必须是原子的/事务的。
比较常见的一种做法是提供 CAS 原子操作：如果满足[条件]那么[写入]否则[失败] 。另一种做法是提供 LL/SC ：如果先前读取的[几个位置]没有被写入那么[写入]否则[失败]。 x86 提供前者，而 ARM 提供后者，而不只是提供原子的读、写。以 CAS 为例，使用者可以采取如下方案：

临时值 = 读(全局值);
临时值2 = 计算(临时值);
while (!CAS(全局值, 临时值, 临时值2)) {
   临时值 = 读(全局值);
   临时值2 = 计算(临时值);
}

其中CAS是原子的

CAS(data, expected, desired) {
   if (data == expected) {
      data = desired;
      return true;
   } else {
      return false;
   }
}

实际上维基百科关于上面说的RMW操作的 词条 也已指出， CAS 、 LL/SC 具有更高的 共识数 ，不可能只用 原子读 、原子写 之类的具有更低 共识数 的操作实现，无论做多少个这样的操作。
那我觉得您的这个场景也是类似的，您需要的是一个原子的 仅当不会冲突才写入 的操作，不可能只用低共识数的 总是读取 总是写入 操作实现。

---

关于这个方案再多说几点。

• 它不会发生死锁。不论 CAS 是否成功发生，它都立即返回而不作等待。它根本不阻塞，所以也不存在死锁。
• 它也不会发生活锁。如果某个线程的 CAS 失败，那是因为其它线程在它读取和 CAS 的间隙当中做了写入。虽然此线程需要在循环中重新 CAS 一遍，但导致其失败的线程一定成功完成了写入。所以总是有进展发生，不存在活锁。
• CPU 提供的这种指令通常宽度有限——只能对一定宽度的数据做这个原子操作，不能将这种原子性扩展到更大的数据结构当中。这种宽度限制不能被简单地克服，无法只用较窄的原子 CAS 实现更宽的原子 CAS 。 x86 最长提供到机器字长两倍宽度的 CAS ，即 32 位下的 CMPXCHG8B 指令和 64 位下的 CMPXCHG16B 指令。如何用宽度受限的原子 CAS 操作实现更复杂的无锁数据结构是一个被广泛研究的问题。但对数据库这类更重量级的软件实现（而且可以接受高得多的操作延迟）而言，理应不受如此紧凑的限制。
• 上面用伪代码表示的这个方案只涉及了总是要写入只是写入多少需要根据读取值决定的简单情况。对这个做一定的调整也不难类似地实现例如只对当前全局值的一部分情况要做写入，否则需要等待其它线程对全局值做更多修改之类的情形。或者说这个while可以兼具自旋锁的功能。同时根据需要还可以在循环体内加入 sleep 或者阻塞的语句。这些情况下，上述关于它不会死锁也不会活锁的表述不再适用。

总之，这是一个很通用的原理。我猜对于数据库的分布式访问来说应该也是有原理相当的构造的。只是发生在更长的延时、更大的数据、更复杂的数据结构。

[n0099]

#32 (comment)

既然线程2在START TRANSACTION之后的读SELECT * FROM t，由于线程1的写的成功COMMIT，其读取值已不再正确，那么线程2的COMMIT不该失败吗？否则它岂不是TRANSACTION了个寂寞？

在图

中线程2是在线程1执行INSERT和COMMIT之前就SELECT了的，因此线程2认为行a不存在，而线程2如果不INSERT行a而是直接COMMIT那么什么错误都不会发生
因为COMMIT本就极少会产生错误（ https://stackoverflow.com/questions/3960189/can-a-commit-statement-in-sql-ever-fail-how ），所以所有图中的DUPLICATE错误都是在执行INSERT时就发生的而不是COMMIT（图中画在一起了所以容易误导）

SQL中的TRANSACTION只是用来封装多个SQL使其成为原子操作的，就像CAS

如果TRANSACTION的存在并没有让事务中的这两个语句产生什么关系，换言之COMMIT只是让INSERT生效的话。

COMMIT让INSERT生效只不过是二次确认了写入行a或b这个操作所以数据库会把这个行真的写入硬盘

实际上对于mysql innodb而言COMMIT写入后还有一大堆内存缓冲区如redolog doublewrite，只有等到这些内存缓存的buffer page也被fsync到硬盘上了才是真的数据落地
然而有些硬盘驱动会欺骗系统以让fsync syscall立即返回但实际上数据还在硬盘的缓存里并没有实际写入持久存储：
https://www.percona.com/blog/2018/02/08/fsync-performance-storage-devices/
https://dev.mysql.com/doc/refman/8.0/en/innodb-parameters.html#sysvar_innodb_flush_log_at_trx_commit

许多操作系统和一些磁盘硬件会欺骗刷新到磁盘的操作。他们可能会告诉 mysqld刷新已经发生，即使它没有发生。在这种情况下，即使使用推荐的设置也无法保证事务的持久性，在最坏的情况下，断电可能会损坏 InnoDB数据。在 SCSI 磁盘控制器或磁盘本身中使用电池供电的磁盘缓存可以加快文件刷新速度，并使操作更安全。您还可以尝试禁用硬件缓存中的磁盘写入缓存。

但这一切对数据库用户而言都是无关的（抽象隔离），用户只需要知道COMMIT了就是不可撤销地写入数据库了
请注意即便COMMIT了也不代表其他并行事务就能知道您已经COMMIT了INSERT了行a（也就是dirty read），因为在防止dirty read的事务隔离级别（REPEATABLE READ及以上，如SERIALIZED）中其他事务有可能不知道您INSERT了的（因为其他事务先前SELECT过所以产生了SNAPSHOT，从而保证REPEATABLE READ）

那么既然您的两个（或更多个）线程，在INSERT和COMMIT之间并没有与全局锁或者其它线程有任何交互

实际运行时环境的线程比这的2个更多，并且在COMMIT之前会有许多个INSERT被执行，所以会有更多交互，我画的图是试图简化模型

那么从开始INSERT到COMMIT起作用的这段时间对于该线程以外是没有看得见的效果的。INSERT立即生效，跟INSERT然后立即COMMIT然后生效，从外面看起来是一样的。所以，这和您不用TRANSACTION应当没有任何差别。

如果阁下的INSERT生效是指让其他事务看得见所INSERT的行（dirty read），那么必须等到COMMIT之后才有可能发生dirty read，因此此处的所有SESSION的事务隔离级别都是READ COMMITTED而不是最弱的READ UNCOMMITTED
对于mysql，如果线程2INSERT行a时数据库层发现这违反了UNIQUE约束（因为线程1已经这么做了），那么在此时就会返回错误并静默地ROLLBACK事务而不是等到COMMIT时再这么做
使用事务包裹SELECT和INSERT的目的是为了让他们进入同一个原子操作中（就像CAS），因为实际上在COMMIT之前会有许多个INSERT被执行所以需要避免在INSERT重复行时由于mysql返回错误而只INSERT了一半的行

这应该也是不对的吧？允许dirty read的发生，应该并不是说保证它会发生？

我没有说把事务隔离级别从REPEATABLE READ降低到READ COMMITTED就一定会发生dirty read，如果您只有一个线程在这对着一个SESSION执行SQL（也就是并行度=1），那么什么race condition都不会发生

[n0099]

#32 (comment)

我的理解是这里需要的行为实际上是一个原子的 RMW操作 ——如何插入这一行是依赖于 相同的行是否已被插入 这个要读取到的条件的。这个读操作+插入操作整体上必须是原子的/事务的。

是，所以阁下也看到了我后来需要给SELECT加上FOR UPDATE从而实现每个线程通过SELECT就能锁住他们准备INSERT的行a或b，mysql称其为IX锁： https://dev.mysql.com/doc/refman/8.0/en/innodb-locking.html#innodb-intention-locks

那我觉得您的这个场景也是类似的，您需要的是一个原子的 仅当不会冲突才写入 的操作，不可能只用低共识数的 总是读取 总是写入 操作实现。

而仅靠一个与mysqld进程毫无关系的进程范围全局锁是不可能保证 SELECT/INSERT和对进程锁的写 会被包裹进同一个原子操作的

CAS 、 LL/SC 具有更高的 共识数 ，不可能只用 原子读 、原子写 之类的具有更低 共识数 的操作实现，无论做多少个这样的操作。

所以我们的四叶头子CS硕士PLT理论中级高手仏皇irol阁下 @kokoro-aya 再一次从计算机科学理论研究的角度为我们提前证明了这一点，而无需亲自下凡接触mysqld

• 它不会发生死锁。不论 CAS 是否成功发生，它都立即返回而不作等待。它根本不阻塞，所以也不存在死锁。

而对于SQL的TRANSACTION而言不可能要求用户一次性就能把他想封装成原子操作的所有语句都发送过来让数据库处理
也就是说用户发送的语句是一条条分开的（每条语句之间可以间隔无限久时间），而不是在单次通信中就发送（实际上如果用户提前就知道我到底要发送多少条语句，那TRANSACTION所带来的原子性的意义就被削弱了，只剩下事务中任意语句失败时整个事务都会ROLLBACK以保证数据一致性这个用途）

START TRANSACTION;
SELECT ...;
INSERT ...;
COMMIT;

那么此时如果某个语句显式声明了锁，如SELECT ... FOR UPDATE产生了IX锁（有意排他锁）
或由于当前事务隔离级别（如SERIALIZED）导致语句隐式声明了锁
那么有上锁就必定会有并行事务一直阻塞等待解锁，直到 https://serverfault.com/questions/241823/setting-a-time-limit-for-a-transaction-in-mysql-innodb

• 它也不会发生活锁。如果某个线程的 CAS 失败，那是因为其它线程在它读取和 CAS 的间隙当中做了写入。虽然此线程需要在循环中重新 CAS 一遍，但导致其失败的线程一定成功完成了写入。所以总是有进展发生，不存在活锁。

而对于这种传统的阻塞锁设计而言只要复数个线程请求同一资源的频率足够高就很容易导致livelock，结果哪个线程都没有真的INSERT，enwiki条目也进一步指出livelock是starvation的特例：Livelock is a special case of resource starvation; the general definition only states that a specific process is not progressing.

• CPU 提供的这种指令通常宽度有限——只能对一定宽度的数据做这个原子操作，不能将这种原子性扩展到更大的数据结构当中。这种宽度限制不能被简单地克服，无法只用较窄的原子 CAS 实现更宽的原子 CAS 。 x86 最长提供到机器字长两倍宽度的 CAS ，即 32 位下的 CMPXCHG8B 指令和 64 位下的 CMPXCHG16B 指令。

无法只用较窄的原子 CAS 实现更宽的原子 CAS 我的理解是同样是因为阁下此前提及的共识数，比如用两个32位CAS操作来试图封装一个64位资源成原子性的会导致其共识数不同，如 https://en.wikipedia.org/wiki/Consensus_(computer_science)#Consensus_number 的表格中指出：

Consensus number	Objects
$2n-2$	n-register assignment

如何用宽度受限的原子 CAS 操作实现更复杂的无锁数据结构是一个被广泛研究的问题。但对数据库这类更重量级的软件实现（而且可以接受高得多的操作延迟）而言，理应不受如此紧凑的限制。

所以传统数据库厂商无法把CPU指令集层面提供的同步原语进一步封装嵌入RDBMS设计中通过抽象隔离暴露给用户来用

• 上面用伪代码表示的这个方案只涉及了总是要写入只是写入多少需要根据读取值决定的简单情况。对这个做一定的调整也不难类似地实现例如只对当前全局值的一部分情况要做写入，否则需要等待其它线程对全局值做更多修改之类的情形。或者说这个while可以兼具自旋锁的功能。同时根据需要还可以在循环体内加入 sleep 或者阻塞的语句。这些情况下，上述关于它不会死锁也不会活锁的表述不再适用。

只要引入了对desync（当要写入的值已经被改了就说明发送了同步失效，也就是违反了 https://en.wikipedia.org/wiki/Linearizability ）的资源进行等待（不论上锁还是解锁）都会重新回到阻塞锁模型中所以dead/livelock的幽灵又回来了

总之，这是一个很通用的原理。我猜对于数据库的分布式访问来说应该也是有原理相当的构造的。只是发生在更长的延时、更大的数据、更复杂的数据结构。

传统老牌RDBMS中基本没有什么无锁数据结构，毕竟其内部结构实现过于复杂恶俗使得他们无从下手改造成无锁的，这也是为什么v2ex的 @daxiguaya 于 https://www.v2ex.com/t/908047#r_12595620 指出

还要考虑间隔锁、表锁之类的问题,除非死锁的时候我会去 DEBUG 数据库的锁状态,其它情况我想操这个心 :)

[n0099]

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

• https://learn.microsoft.com/en-us/dotnet/api/system.threading.interlocked
  https://github.com/n0099/TiebaMonitor/blob/5f6abb0ac8581d09903cdb9da667d7b99b8427dd/crawler/src/Worker/ArchiveCrawlWorker.cs#L86
  https://github.com/n0099/TiebaMonitor/blob/5f6abb0ac8581d09903cdb9da667d7b99b8427dd/crawler/src/Worker/ArchiveCrawlWorker.cs#L67
  https://github.com/n0099/TiebaMonitor/blob/2f84a4ab96c07e0e1d7055d945ce9bcae9085a90/crawler/src/Tieba/ClientRequesterTcs.cs#L26
  https://github.com/n0099/TiebaMonitor/blob/2f84a4ab96c07e0e1d7055d945ce9bcae9085a90/crawler/src/Tieba/ClientRequesterTcs.cs#L69
• https://learn.microsoft.com/en-us/dotnet/api/system.collections.concurrent.concurrentdictionary-2
  https://github.com/n0099/TiebaMonitor/search?q=concurrent

然而很明显.NET对system.collections.concurrent下的类的内部实现并不一定是完全采用基于RMW同步原语的无锁操作设计的：
https://devblogs.microsoft.com/pfxteam/faq-are-all-of-the-new-concurrent-collections-lock-free/

（此答案基于 .NET Framework 4。 由于以下详细信息是未记录的实施细节，因此它们可能会在未来的版本中更改。）
否。新的 System.Collections.Concurrent 命名空间中的所有集合在某种程度上都采用了无锁技术以实现一般性能优势，但在某些情况下使用传统锁。
ConcurrentBag 有时需要锁定，但对于某些并发场景（例如，许多线程以相同的速率进行生产和消费），它是一个非常有效的集合。
ConcurrentDictionary<TKey,TValue> 在向字典中添加或更新数据时使用细粒度锁定，但它对于读取操作是完全无锁的。 这样针对以字典读取为最频繁操作的场景进行了优化。

https://www.red-gate.com/simple-talk/blogs/inside-the-concurrent-collections-concurrentdictionary/ 进一步指出：

那么，如果你要实现一个线程安全的字典，你会怎么做？天真的实现是简单地在所有访问字典的方法周围加一个锁。这可行，但不允许太多并发。
幸运的是，使用的分桶Dictionary允许对此进行简单但有效的改进——每个桶一个锁。这允许修改不同存储桶的不同线程并行进行。任何对存储桶内容进行更改的线程都会锁定该存储桶，确保这些更改是线程安全的。将每个桶映射到锁的方法是GetBucketAndLockNo方法：

private void GetBucketAndLockNo(
        int hashcode, out int bucketNo, out int lockNo, int bucketCount) {
        
    // the bucket number is the hashcode (without the initial sign bit)
    // modulo the number of buckets
    bucketNo = (hashcode & 0x7fffffff) % bucketCount;
	  
    // and the lock number is the bucket number modulo the number of locks
    lockNo = bucketNo % m_locks.Length;
}

但是，这确实需要对存储桶的实现方式进行一些更改。非并发使用的单个后备数组中的“隐式”链表Dictionary在不同的桶之间增加了依赖性，因为每个桶都使用相同的后备数组。相反，ConcurrentDictionary在每个桶上使用严格的链表：

这确保每个桶都与所有其他桶完全分开；从桶中添加或删除项目独立于对其他桶的任何更改。

所以就有了基于NonBlockingHashMap这个无锁数据结构（众所周知dict本质hashmap+bucket array）实现的ConcurrentDictionary： https://github.com/VSadov/NonBlocking

进一步的我在奥利金德数理逻辑带手子当代图灵可计算性理论中级高手dc神 @dylech30th 的指导下也意识到了接连使用复数个原子操作不代表这个操作集合也是原子性的（从共识数理论可得），所以我在 https://github.com/n0099/TiebaMonitor/blob/c414ca3429ceb1cd4a7607c10fb79cb608b7cd2d/crawler/src/Tieba/Crawl/CrawlerLocks.cs#L44 中还是需要无脑lock整个ConcurrentDictionary类实例使得对其的复数个原子操作都被包裹进一个原子操作中（就像SQL TRANSACTION），这实际上使得在这里使用ConcurrentDictionary没啥意义了，因为其内部的每个原子操作又带来了不必要（整个dict业已被锁所以并行度=1）的无锁/有锁.NET实现开销

[n0099]

TL;DR: 我在mysql中使用TRANSACTION封装两个 SELECT ... FOR UPDATE所产生的IX锁 和 INSERT 语句使其成为原子操作实现了类似于ConcurrentDictionary.GetOrAdd的同步原语（您可以将具有UNIQUE约束的二维表视作一个Dict<uniqueKey,fieldsTuple>数据结构）

#32 (comment)

不难看出此时进程范围的全局锁（进程锁）已经没有存在的必要了，因为他的目的跟 IX 锁是类似的（但他无法目前像 IX 锁那样无限期阻塞任何试图读取进程锁的线程）

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

[yangbowen]

并且在COMMIT之前会有许多个INSERT被执行

其实你只要说这句就够了，其它诸如持久化等在这个问题当中似乎是无关的吧。
对于多个写操作，TRANSACTION保证了它们整体的原子性——同时的或将来的其它会话要么看到所有这些写入，要么全都不看到。是吧？
这完全能够理解，不理解的部分是TRANSACTION对事务内的读取（SELECT）如何起作用。如果读取同样被包含在这种原子性当中，那您开头所说的进程全局锁理应是多余的；反之，在只有一个写入语句的简化情况下TRANSACTION的存在似乎并没有任何作用的样子。
或者这么说：如果将SELECT移到START TRANSACTION之前（事务外），行为上是否会有任何可以依赖的差别呢？

---

如果阁下的INSERT生效是指让其他事务看得见所INSERT的行（dirty read），那么必须等到COMMIT之后才有可能发生dirty read，因此此处的所有SESSION的事务隔离级别都是READ COMMITTED而不是最弱的READ UNCOMMITTED

生效的意思当然就是说能够被读取看到。COMMIT之前的INSERT不会被看到效果。但，在只需要一个INSERT的简化例子当中，彻底把TRANSACTION删掉，让INSERT立即生效（比起INSERT之后该线程紧接着执行COMMIT让INSERT生效，并没有在这之间和全局锁发生任何交互），跟开头的例子有什么差别呢？这是我所没能理解的。

对于mysql，如果线程2INSERT行a时数据库层发现这违反了UNIQUE约束（因为线程1已经这么做了），那么在此时就会返回错误并静默地ROLLBACK事务而不是等到COMMIT时再这么做

不难理解当INSERT由于违反约束而失败时整个事务失败并被ROLLBACK。但假如INSERT并没有（数据库的）错误，却是调用者基于先前SELECT到的，而现在已经被修改掉的数据，所作出的呢？是否有这样的事务隔离级别，从而在这种情况下也会ROLLBACK整个事务？
举个例子，假设自行实现某种自增计数器，而且并没有在数据库中设置相应的约束。线程1读取了计数器的当前值，根据当前值递增后写入递增后的值，这些操作被放在一个事务当中。线程2也做同样的事，但是刚好在线程1的两个操作之间完成了线程2的所有操作。于是，线程1准备写入的值跟线程2是一样的。
像这样的情况下就算这个写入操作是合法的，不违反数据库的约束，也理应让线程1的事务回滚而非成功提交。广泛一点来说，线程1的事务的 读取集 （事务中读过哪些数据——准备写入的东西可能是调用者根据这些数据推算出的）跟线程2的事务的 写入集 （事务中写入了哪些数据）有重合，这样的情况下很可能不应该让两个事务都成功提交。写入的数据可能依赖于先前的读取，而且调用者（在得知事务成功提交后）的后续操作可能依赖于确实是在读取到的这样的数据的基础上发生了这样的写入。

---

而仅靠一个与mysqld进程毫无关系的进程范围全局锁是不可能保证 SELECT/INSERT和对进程锁的写 会被包裹进同一个原子操作的

实际上是可能的，只不过大概不是你要的效果。那就是所有需要原子操作的地方获取全局锁。意味着不论这些原子操作访问了什么，都无法并行。
事实上，包括 C++ 标准库在内的一些库，对于根本没有什么硬件原子操作支持的平台，就可以这样实现原子操作。但截至目前我并未知悉有这样的平台（多处理器，但没有硬件原子操作支持）。
实现 自旋锁 或者 互斥体 并不需要 CAS ，只需要比它弱得多的 test-and-set ——将某个 bit 置为 1 并返回置位前的值，就够了：

获取锁() {
   do {
      临时值 = test_and_set(全局位);
   } while (临时值 == 0);
}
释放锁() {
   clear(全局位);
}

显然用 CAS 或者 LL/SC 很容易实现 test-and-set ，反过来则不行。

---

除了这种完全舍弃并行的做法以外，既然这个事务性是跟 读取集 写入集 相关联的，那么我当然认为这种事务约束理应由数据库而不是调用者实现。

---

无法只用较窄的原子 CAS 实现更宽的原子 CAS 我的理解是同样是因为阁下此前提及的共识数，比如用两个32位CAS操作来试图封装一个64位资源成原子性的会导致其共识数不同，如 https://en.wikipedia.org/wiki/Consensus_(computer_science)#Consensus_number 的表格中指出：

我想这并不是一回事。共识数跟操作的宽度并没有必然关系吧。
另外其实也不是不可以，比方说在 GC 环境下可以这么做：

指针 全局值;
读对象() {
   指针 临时值 = 原子读取(全局值);
   return 解引用(临时值);
}
CAS对象(对象 expected, 对象 desired) {
   指针 临时值 = 原子读取(全局值);
   if (对象相等(解引用(临时值), expected)) {
      指针 临时值2 = new 对象(desired);
      return 原子CAS(全局值, 临时值, 临时值2);
   } else {
      return false;
   }
}

也就是说不修改对象，而是每次都创建新的对象，然后对指针做 CAS 。在 GC 环境下是可行的，在非 GC 环境下则会面临释放时机的问题，还有 ABA问题 。
这个对象可以是任意大的数据结构，比方说可以是一整个 dict 数据结构，只不过为了修改一个值拷贝整个数据结构很容易让它完全丧失性能优势，还不如直接全局加锁。
总之这里只是说不能简单地组合多个窄 CAS 来代替一个宽 CAS 。事实上，之所以处理器通常提供到两倍机器字长的 CAS ，一个主要原因是上述（无锁数据结构）方案，再加上一个额外的整数跟这个指针一同被 CAS ，就需要两倍机器字长的 CAS 。

[yangbowen]

而对于SQL的TRANSACTION而言不可能要求用户一次性就能把他想封装成原子操作的所有语句都发送过来让数据库处理 也就是说用户发送的语句是一条条分开的（每条语句之间可以间隔无限久时间），而不是在单次通信中就发送（实际上如果用户提前就知道我到底要发送多少条语句，那TRANSACTION所带来的原子性的意义就被削弱了，只剩下事务中任意语句失败时整个事务都会ROLLBACK以保证数据一致性这个用途）

这很合理。但是……

START TRANSACTION;
SELECT ...;
INSERT ...;
COMMIT;

那么此时如果某个语句显式声明了锁，如SELECT ... FOR UPDATE产生了IX锁（有意排他锁） 或由于当前事务隔离级别（如SERIALIZED）导致语句隐式声明了锁 那么有上锁就必定会有并行事务一直阻塞等待解锁，直到 https://serverfault.com/questions/241823/setting-a-time-limit-for-a-transaction-in-mysql-innodb

但不太能理解的是为什么它一定要让其它事务阻塞等待，而不是先返回不可靠的SELECT结果，如果有冲突的话再让COMMIT失败，整个事务被ROLLBACK，而且截至COMMIT成功之前调用者必须把SELECT结果视为不可靠的，不能当真呢？
虽然TRANSACTION中的不同语句可以间隔任意久的时间，但数据库引擎对于开着的TRANSACTION肯定是要保持某些状态记录的。那么它完全可以做成为每个TRANSACTION记录 读取集 和 写入集 ，仅当从START TRANSACTION到COMMIT之间读取集未曾和其它事务的写入集发生重合时才允许COMMIT成功，否则要求调用者退回START TRANSACTION重来而且先前的SELECT结果必须不作数。
Intel TSX 这个指令集就是这么做的，如果发生任何冲突就失败并且让调用者重来。利用现代处理器已有的缓存一致性协议等，处理器确实能够检测到冲突并在这样的情况下撤销已经执行的指令的影响。只不过比较不幸，它大概很难实现得安全，反复地出现安全漏洞（恶意的代码能够让本来无权读取的内存对将要被撤销的状态产生影响，再通过某些侧信道区别这些本应撤销的状态差异，从而作未授权的读取）迫使英特尔禁用该指令集。
但这种原理应该是首先出现在数据库领域当中，后来才启发了 CPU 设计者设计类似原理的 CPU 指令的。只是我不知道具体哪个数据库的哪种操作允许这样，而不是采用锁和等待。

• 它也不会发生活锁。如果某个线程的 CAS 失败，那是因为其它线程在它读取和 CAS 的间隙当中做了写入。虽然此线程需要在循环中重新 CAS 一遍，但导致其失败的线程一定成功完成了写入。所以总是有进展发生，不存在活锁。

而对于这种传统的阻塞锁设计而言只要复数个线程请求同一资源的频率足够高就很容易导致livelock，结果哪个线程都没有真的INSERT，enwiki条目也进一步指出livelock是starvation的特例：Livelock is a special case of resource starvation; the general definition only states that a specific process is not progressing.

我上面说不发生活锁只是说整个系统一定有进展，但在非常高频率的情况下不保证单个线程一定有进展。相反，确实有可能某个线程反复地 CAS 失败，而且当它重新算好下次要 CAS 的值的时候这个共享的变量又被改掉了，导致这个线程没有进展。
在 CPU 指令的情况当中，线程通常有很多事要做，而 CAS 的单次循环通常很短，可能只是一个递增递减之类的。所以不太会一直在争抢某一个共享变量。得到进展的线程多半可以去做别的不争抢这个变量的工作。但在数据库的情况当中，一个事务的时间跨度长得多，单个或几个线程始终得不到进展是个更现实的问题。

[n0099]

#32 (comment)

其实你只要说这句就够了，其它诸如持久化等在这个问题当中似乎是无关的吧。

#32 (comment)

提供 CAS 原子操作：如果满足[条件]那么[写入]否则[失败]

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

---

对于多个写操作，TRANSACTION保证了它们整体的原子性——同时的或将来的其它会话要么看到所有这些写入，要么全都不看到。是吧？

在READ COMMITTED及以上事务隔离级别中是能保证不发生dirty read的，只有降低到

回顾经典之3.数据库事务隔离级别从READ COMMITED降至READ UNCOMMITED节的图

请注意本讨论串中的所有dirty read（除了上述那一个）都应该查找替换为phantom read（以及typo之COMMITTED少打了一个T），因为我最开始看着这图时就写错了：

可见降至READ UNCOMMITED后允许dirty read的发生

另外请注意尽管non-repeatable read和phantom read之间看起来很相似（他们的UML时序图甚至是完全相同的），但本质完完全全两码事： https://stackoverflow.com/questions/11043712/what-is-the-difference-between-non-repeatable-read-and-phantom-read

---

这完全能够理解，不理解的部分是TRANSACTION对事务内的读取（SELECT）如何起作用。如果读取同样被包含在这种原子性当中，那您开头所说的进程全局锁理应是多余的

SELECT是否对其所读出来的行资源进行锁定是取决于您有没有追加FOR SHARE/UPDATE的，建议复习：
https://dev.mysql.com/doc/refman/8.0/en/innodb-locking.html#innodb-intention-locks
https://dev.mysql.com/doc/refman/8.0/en/innodb-locking.html#innodb-insert-intention-locks
https://dev.mysql.com/doc/refman/8.0/en/innodb-locking-reads.html

---

反之，在只有一个写入语句的简化情况下TRANSACTION的存在似乎并没有任何作用的样子。

https://dev.mysql.com/doc/refman/8.0/en/commit.html 对此早有预言：

默认情况下，MySQL 在 启用自动提交模式的情况下运行。这意味着，当不在事务内时，每个语句都是原子的，就好像它被START TRANSACTIONand包围一样COMMIT。您不能使用ROLLBACK来撤销效果；但是，如果在语句执行期间发生错误，则回滚该语句。

---

或者这么说：如果将SELECT移到START TRANSACTION之前（事务外），行为上是否会有任何可以依赖的差别呢？

移出去会导致单条SELECT由于AUTO_COMMIT而变成一个只有他一个语句的事务（其隔离级别由于没有显式指定所以会使用mysql默认的REPEATABLE READ，然而实际上对于单语句事务而言任何隔离级别都是相同的），如果SELECT后面没有FOR UPDATE那么移出去也是一样的，即便有由于这是单语句事务所以IX锁也立即被释放了那还是没有造成差别

而在 https://stackoverflow.com/questions/1976686/is-there-a-difference-between-a-select-statement-inside-a-transaction-and-one-th/1976701#1976701 的中他所说的

是的，事务内部的人可以看到该事务中其他先前的 Insert/Update/delete 语句所做的更改；事务外的 Select 语句不能。

在SELECT所在的事务的隔离级别是READ UNCOMMITTED时应该是不成立的

然而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/

---

生效的意思当然就是说能够被读取看到。COMMIT之前的INSERT不会被看到效果

这就是READ COMMITTED事务隔离级别

---

但，在只需要一个INSERT的简化例子当中，彻底把TRANSACTION删掉，让INSERT立即生效（比起INSERT之后该线程紧接着执行COMMIT让INSERT生效，并没有在这之间和全局锁发生任何交互），跟开头的例子有什么差别呢？这是我所没能理解的。

开头的例子里也不是只有一个INSERT啊，任何线程在INSERT前都必须先SELECT以排除已存在的行

---

调用者基于先前SELECT到的，而现在已经被修改掉的数据，所作出的呢？是否有这样的事务隔离级别，从而在这种情况下也会ROLLBACK整个事务？

无，所以需要乐观并发控制，如MSSQL中基于一个单调自增的ROW_VERSION字段来跟踪有无UPDATE
建议回顾 https://www.v2ex.com/t/909762#r_12593822

乐观并发控制是要求每个客户端的后续读写都得依赖于此前查询所获得的的ROW_VERSION
比如事务 1SELECT yi, ver FROM t获得(a,0)
那么事务 1 后续的所有对该行的读写（ SELECT/UPDATE ）都得依赖于ver=0这个此前获得的事实
也就是对于读：事务 1 期望重新SELECT yi, ver FROM t获得的还是(a,0)，这叫做REPEATABLE READ（避免了幻读phantom read），注意 mysql 默认的事务隔离级别就是REPEATABLE READ所以默认是已经保证了在同一事务内不断重新执行SELECT yi, ver FROM t返回的永远都是(a,0)
对于写：事务 1 期望UPDATE t SET 某个其他字段 = 某值 WHERE yi = a AND ver = 0所返回的affected rows是 1 行，而如果不是 1 行而是 0 行就意味着表 t 中已经不存在符合约束WHERE yi = a AND ver = 0的行，也就是说行yi=a已经被其他事务修改了
建议参考以某企业级 orm EFCore 为背景的 MSDN 微软谜语： https://learn.microsoft.com/en-us/ef/core/saving/concurrency
以及我之前对于类似的场景（但是是 INSERT-only 而不是 UPDATE ）使用了数据库层提供的悲观并发控制，毕竟在 SQL 末尾加FOR UPDATE可比在 mysql 里用 TRIGGER 模拟单调递增的自增 sql server 的 ROW_VERSION 类型然后在程序业务逻辑里写乐观控制所带来的一大堆 if 简单多了： https://www.v2ex.com/t/908047

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

---

举个例子，假设自行实现某种自增计数器，而且并没有在数据库中设置相应的约束。线程1读取了计数器的当前值，根据当前值递增后写入递增后的值，这些操作被放在一个事务当中。线程2也做同样的事，但是刚好在线程1的两个操作之间完成了线程2的所有操作。于是，线程1准备写入的值跟线程2是一样的。

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

---

像这样的情况下就算这个写入操作是合法的，不违反数据库的约束，也理应让线程1的事务回滚而非成功提交。广泛一点来说，线程1的事务的 读取集 （事务中读过哪些数据——准备写入的东西可能是调用者根据这些数据推算出的）跟线程2的事务的 写入集 （事务中写入了哪些数据）有重合，这样的情况下很可能不应该让两个事务都成功提交。写入的数据可能依赖于先前的读取，而且调用者（在得知事务成功提交后）的后续操作可能依赖于确实是在读取到的这样的数据的基础上发生了这样的写入。

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

---

实际上是可能的，只不过大概不是你要的效果。那就是所有需要原子操作的地方获取全局锁。意味着不论这些原子操作访问了什么，都无法并行。

然而很明显没人想要四叶头子CS硕士PLT理论中级高手仏皇irol阁下写java遇到并行问题时就无脑套一个大synchronized() {}block来降低并行度=1，这只能作为性能不重要但一致性和事务成功率重要的金融军事等企业级场景

---

对于根本没有什么硬件原子操作支持的平台，就可以这样实现原子操作。但截至目前我并未知悉有这样的平台（多处理器，但没有硬件原子操作支持）。
实现 自旋锁 或者 互斥体 并不需要 CAS ，只需要比它弱得多的 test-and-set

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

---

显然用 CAS 或者 LL/SC 很容易实现 test-and-set ，反过来则不行

https://en.wikipedia.org/wiki/Consensus_(computer_science)#Consensus_number 的表格中也进一步指出：

Consensus number	Objects
$1$	atomic read/write registers, mutex
$\infty$	compare-and-swap, load-link/store-conditional,[40] memory-to-memory move and swap, queue with peek operation, fetch&cons, sticky byte

根据层次结构，即使在2进程系统中，读/写寄存器也无法解决一致性问题。栈、队列等数据结构只能解决两个进程之间的共识问题。然而，一些并发对象是通用的（在表中用$\infty$)，这意味着它们可以解决任意数量的进程之间的共识，并且可以通过操作序列模拟任何其他对象

---

除了这种完全舍弃并行的做法以外，既然这个事务性是跟 读取集 写入集 相关联的，那么我当然认为这种事务约束理应由数据库而不是调用者实现。

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

---

另外其实也不是不可以，比方说在 GC 环境下可以这么做：

指针 全局值;
读对象() {
   指针 临时值 = 原子读取(全局值);
   return 解引用(临时值);
}
CAS对象(对象 expected, 对象 desired) {
   指针 临时值 = 原子读取(全局值);
   if (对象相等(解引用(临时值), expected)) {
      指针 临时值2 = new 对象(desired);
      return 原子CAS(全局值, 临时值, 临时值2);
   } else {
      return false;
   }
}

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

---

也就是说不修改对象，而是每次都创建新的对象，然后对指针做 CAS

那阁下实际上是在对机器字长32/64位的指针做CAS，而CPU指令集当然会提供能对机器字长长的数据进行CAS的指令

在 GC 环境下是可行的，在非 GC 环境下则会面临释放时机的问题，还有 ABA问题 。

为什么这里会有ABA

这个对象可以是任意大的数据结构，比方说可以是一整个 dict 数据结构，只不过为了修改一个值拷贝整个数据结构很容易让它完全丧失性能优势，还不如直接全局加锁。

疑似新创无际rust人生信壬西兔人迺逸夫 @Prunoideae 的内存安全性和ios的跨app share文件必须完整复制粘贴

总之这里只是说不能简单地组合多个窄 CAS 来代替一个宽 CAS 。事实上，之所以处理器通常提供到两倍机器字长的 CAS ，一个主要原因是上述（无锁数据结构）方案，再加上一个额外的整数跟这个指针一同被 CAS ，就需要两倍机器字长的 CAS 。

什么整数？

[Prunoideae]

我呃呃，你要不自杀吧

[n0099]

我呃呃，你要不自杀吧

西兔人您来辣
前年阁下从新创无际主群开始大退群后我还以为您虚元了
最近看阁下去了HKUST深造（不做生信了？）
想必您已经见过上海贵族新创lys神 @DWVoid 了吧