search

n0099 / open-tbm

https://n0099.net/tbm
GNU Affero General Public License v3.0
9 stars 2 forks source link

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

Open n0099 opened 1 year ago

n0099 commented 1 year ago

原文发表于 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

缺点：

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）

缺点：

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

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

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

n0099 commented 1 year ago

可能会有人抱怨这是 提前优化了未来发生的事 或 将复杂的分布式理论用在这是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 commented 1 year ago

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： https://github.com/dotnet/efcore/issues/26042#issuecomment-993534289 目前能用的变通只有额外查询 rawsql 来表示 IX 锁（而不能直接嵌入已有的 linq2sql 中）： https://stackoverflow.com/questions/37984312/how-to-implement-select-for-update-in-ef-core

n0099 commented 1 year ago

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 commented 1 year ago

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 commented 1 year ago

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

  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 commented 1 year ago

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 具有更高的 共识数 ，不可能只用 原子读 、原子写 之类的具有更低 共识数 的操作实现，无论做多少个这样的操作。 那我觉得您的这个场景也是类似的，您需要的是一个原子的 仅当不会冲突才写入 的操作，不可能只用低共识数的 总是读取 总是写入 操作实现。

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

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

n0099 commented 1 year ago

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

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

在图 image 中线程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 commented 1 year ago

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

我的理解是这里需要的行为实际上是一个原子的 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 commented 1 year ago

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

然而很明显.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在每个桶上使用严格的链表：
> ![image](https://user-images.githubusercontent.com/13030387/214192943-2de2a6ee-195f-4d1f-b302-2ff922eff717.png)
> 这确保每个桶都与所有其他桶完全分开；从桶中添加或删除项目独立于对其他桶的任何更改。

所以就有了基于`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 commented 1 year ago

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

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

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

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

yangbowen commented 1 year ago

并且在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 commented 1 year ago

而对于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 commented 1 year ago

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

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

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

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

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

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

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

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

请注意本讨论串中的所有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 commented 1 year ago

我呃呃，你要不自杀吧

n0099 commented 1 year ago

我呃呃，你要不自杀吧

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

n0099 commented 1 year ago

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

但不太能理解的是为什么它一定要让其它事务阻塞等待，而不是先返回不可靠的SELECT结果，如果有冲突的话再让COMMIT失败，整个事务被ROLLBACK，而且截至COMMIT成功之前调用者必须把SELECT结果视为不可靠的，不能当真呢？

https://github.com/n0099/TiebaMonitor/issues/32#issuecomment-1401199725 早已做出循环论证：

因为COMMIT本就极少会产生错误（ stackoverflow.com/questions/3960189/can-a-commit-statement-in-sql-ever-fail-how ）

如果有冲突的话再让COMMIT失败中的冲突是指INSERT还是SELECT造成的？INSERT时 https://github.com/n0099/TiebaMonitor/issues/32#issuecomment-1401199725 早已道明：

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

而SELECT如何冲突？

从实用角度讲数据库用户期望的是获取可靠的值，但却拿到了不可靠的值，那用户该如何进行后续的假设？ 并且理论上如果用户要的就是不可靠值那他应该可以通过往SELECT追加FOR SHARE来做到这一点： https://github.com/n0099/TiebaMonitor/issues/32#issuecomment-1399331576

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

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

虽然TRANSACTION中的不同语句可以间隔任意久的时间，但数据库引擎对于开着的TRANSACTION肯定是要保持某些状态记录的

也就是mysql默认事务隔离级别REPEATABLE READ下需要对每个事务每个SELECT所读到的每一行都做缓存（被称作SNAPSHOT）https://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 https://www.postgresql.org/docs/current/transaction-iso.html

那么它完全可以做成为每个TRANSACTION记录 读取集 和 写入集 ，仅当从START TRANSACTION到COMMIT之间读取集未曾和其它事务的写入集发生重合时才允许COMMIT成功，否则要求调用者退回START TRANSACTION重来而且先前的SELECT结果必须不作数。

然而问题在于REPEATABLE READ顾名思义只协调了SELECT，他对INSERT``UPDATE顶多有阻塞（如果使用了SELECT ... FOR UPDATE导致IX锁）而不会出于其他事务已经INSERT/UPDATE了本事务此前SELECT的行就拦截两个事务中的某一个（而阁下要的是两个事务都ROLLBACK）

但这种原理应该是首先出现在数据库领域当中，后来才启发了 CPU 设计者设计类似原理的 CPU 指令的。只是我不知道具体哪个数据库的哪种操作允许这样，而不是采用锁和等待

我局的是奥利金德rust头子LG神 @LasmGratel 最爱的pgsql所采用的 https://en.wikipedia.org/wiki/Multiversion_concurrency_control （然而mysql innodb也是MVCC，很明显MVCC也只是一个抽象概念，而RDBMS们滥用他只是为了方便实现REPEATABLE READ）

但在数据库的情况当中，一个事务的时间跨度长得多，单个或几个线程始终得不到进展是个更现实的问题

最容易遇到的还是死锁，其次是这种活锁，并且mysql无法主动检测出一直有多个事务在争夺同一资源（行集合）并介入其中（比如暂时把资源改成serializability的以便让事务们缓缓通过），除非阁下愿意像老DBA那样247高强度盯着netdata收集的metrics然后手动分析 image

n0099 commented 1 year ago

提请四叶信安底层壬上壬上海贵族 FSF EFF 精神会员杨博文阁下 @yangbowen 立即前往v2ex回复四叶头子CS硕士PLT理论中级高手仏皇irol阁下所提出的奇思妙想之如果语言能够提供足够的表达性，是否可以不需要反射和 AOP 的概念？： https://www.v2ex.com/t/910403

Prunoideae commented 1 year ago

我呃呃，你要不自杀吧

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

我还在大做特做生信，只不过之前因为某些互联网混沌言论一转虚无了。在这边之后我除了项目的事情几乎没有和外界有联系，所以几乎一个人都不认识

远离魔怔，最幸福的人，，，

yangbowen commented 1 year ago

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

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

请注意本讨论串中的所有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

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

yangbowen commented 1 year ago

而我也大量使用了.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，因为这时只有强迫同时只有一个线程在读写才能保证每个线程的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，这边事情比较多，基本上都在做研究

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

n0099 commented 1 year ago

我呃呃，你要不自杀吧

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

我还在大做特做生信，只不过之前因为某些互联网混沌言论一转虚无了。在这边之后我除了项目的事情几乎没有和外界有联系，所以几乎一个人都不认识

远离魔怔，最幸福的人，，，

远离邪恶组织四叶重工，做最幸福的人，，，

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

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

他没说他是否业已照会了新创lys神吧，您进了新创无际开发群之后没见到西兔人吗？

yangbowen commented 1 year ago

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

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

他没说他是否业已照会了新创lys神吧，您进了新创无际开发群之后没见到西兔人吗？

没有已知证据表明我有见到。

n0099 commented 1 year ago

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

是的，但我完全不知道在数据库领域中相近的概念叫什么，于是只好就我了解到这些概念的领域来说。

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

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

enwiki进一步澄清：

如果发生任何更新，存储条件保证失败，即使加载链接读取的值已经恢复。因此，LL/SC 对比读取后跟比较和交换(CAS) 更强，如果旧值已恢复，后者将不会检测更新（请参阅ABA 问题）。

因此LLSC主要是为了解决CAS可能遇到的ABA问题 然而截止2023年1月，即便是早已被彻底禁用了的intel tsx指令集中也没有arm中的ldarx

请注意本讨论串中的所有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

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

中的措辞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

n0099 commented 1 year ago

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

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

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 interlock的命名词源可能是 https://en.wikipedia.org/wiki/Interlock

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

我也认为引入SELECT ... FOR UPDATE所在数据库层产生的IX锁后其已经代替了进程锁的职责那就应该删除有关代码减少复杂度 然而在现代后端中台微服务娱乐圈带架构师们眼中看来反而不应该像90s的企业级COBOL程序员那样写上千行的PL/SQL以依赖于数据库层而不是后端程序的逻辑： https://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： image

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

一个朴素的SELECT不可能产生这种约束，所以有FOR UPDATE后缀所产生的IX锁（以及FOR SHARE产生IS锁），而产生X锁很明显是会造成其他事务阻塞的 因此EFCore开发者MSFT员工将其归类为悲观并发控制： https://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

所以 https://www.v2ex.com/t/908047#r_12564068 的 @codehz 早已道明：

我来捋一捋，这一大段先查询再插入的目的是防止重复的插入？有没有一种可能用 INSERT ON DUPLICATE 来解决呢？直接忽略重复插入的冲突有影响吗

他所说的INSERT INTO ... ON DUPLICATE KEY UPDATE实际上就是数据库层的CAS原子操作： https://dev.mysql.com/doc/refman/8.0/en/insert-on-duplicate.html https://stackoverflow.com/questions/45652775/thread-safety-of-insert-on-duplicate-key-update https://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

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 错误）的场景

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

https://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 并且在那一刻，指针值也必须偶然相同

https://en.wikipedia.org/wiki/ABA_problem#Tagged_state_reference ：

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

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

https://en.wikipedia.org/wiki/ABA_problem 指出：

如果一个项目从列表中移除，删除，然后分配一个新项目并将其添加到列表中，由于MRU内存分配，分配的对象与删除的对象位于同一位置是很常见的。因此，指向新项的指针通常等于指向旧项的指针，从而导致 ABA 问题。

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

enwiki同时声称：

另一种方法是推迟回收已删除的数据元素。延迟回收的一种方法是在具有自动垃圾收集器的环境中运行算法；然而，这里的一个问题是，如果 GC 不是无锁的，那么整个系统就不是无锁的，即使数据结构本身是无锁的。

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

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

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

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

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

RDBMS中的changeset是MVCC中的SNAPSHOT，主要用于实现REPEATABLE READ中禁止non-repeatable read的需求 https://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 这也是其他使用MVCC的RDBMS实现ANSI SQL中要求的4个事务隔离级别之REPEATABLE READ的常规做法 http://mbukowicz.github.io/databases/2020/05/01/snapshot-isolation-in-postgresql.html https://www.postgresql.org/docs/current/transaction-iso.html

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

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

真这样做可能会违反ANSI SQL，当然从历史上看是先有DB2后有标准，而在RDBMS厂商们最初引入事务这个包裹复数SQL的概念时可能就业已设计为了COMMIT几乎不会失败：

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

但不太能理解的是为什么它一定要让其它事务阻塞等待，而不是先返回不可靠的SELECT结果，如果有冲突的话再让COMMIT失败，整个事务被ROLLBACK，而且截至COMMIT成功之前调用者必须把SELECT结果视为不可靠的，不能当真呢？

https://github.com/n0099/TiebaMonitor/issues/32#issuecomment-1401199725 早已做出循环论证：

因为COMMIT本就极少会产生错误（ https://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中会直接给您throw一个比通用的数据库服务端异常更具体的DbUpdateConcurrencyException异常

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

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

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

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

yangbowen commented 1 year ago

然而截止2023年1月，即便是早已被彻底禁用了的intel tsx指令集中也没有arm中的ldarx

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

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而已经就看不见那个行了吗？ 另外，读到尚未提交的事务中已经做出的修改，那么……

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

yangbowen commented 1 year ago

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

比画时序图要严密但是不直观的，是描述操作之间的 happens-before 约束吧。 A happens-before B 就是说 B 能看到 A 的副作用。 happens-before 具有传递性。 这样的话虽然不太直观，但是不会像时序图只描述了可能发生的时序的一种，而是能够只依赖于确实被约束的时序关系。

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

这是不对的。实际上volatile并没有这个意思，也不是用来解决这种情况的。 “跨线程共享变量使用volatile避免不同步问题”是一个被广泛地重复的错误的说法。请不要继续重复这个错误了。 MSVC 让volatile写具有release语义，volatile读具有acquire语义。但这是非标准的扩展，而且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的DELECT的后台 crontab （或是线程每次INSERT后都尝试DELETE一次）来定期执行删除这类冗余的“重复”行 但这跟UPSERT/INSERT IGNORE类似仍然是缓解问题而不是解决问题 而且DELETE作为事（INSERT）后补救也不可能解决更罕见（线程在同一秒内完成所有任务）的两个线程插入的所有字段都相同（也就是触发 DUPLICATE 错误）的场景

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

这个部分之前没看明白，现在才明白了。那我觉得如果你不想那么“补救”的话，那这个问题可以分成以下几个部分：

yangbowen commented 1 year ago

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

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

yangbowen commented 1 year ago

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 。 特别地，其中说到：

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.

n0099 commented 1 year ago

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和change buffer中 然而这同样无法回退某个READ UNCOMMITTED事务隔离级别的事务此前已经获得的读取结果，因为客户端已经知道了

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

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

  • 使用READ COMMITTED还有额外的效果： 对于UPDATEor DELETE语句， InnoDB只对它更新或删除的行持有锁。WHERE在 MySQL 评估条件后，释放不匹配行的记录锁 。这大大降低了死锁的可能性，但它们仍然会发生。
  • READ UNCOMMITTED SELECT 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. Otherwise, this isolation level works like 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 说

选择事务隔离级别不会影响为保护数据修改而获取的锁。无论为该事务设置的隔离级别如何，事务始终会对其修改的任何数据获取独占锁并持有该锁直到事务完成。对于 读取操作，事务隔离级别主要定义保护级别免受其他事务所做修改的影响。

另外，读到尚未提交的事务中已经做出的修改，那么……

  • 即便如此，当前（读取）事务也能成功提交吗？

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

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

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

真这样做可能会违反ANSI SQL，当然从历史上看是先有DB2后有标准，而在RDBMS厂商们最初引入事务这个包裹复数SQL的概念时可能就业已设计为了COMMIT几乎不会失败：

#32 (comment)

但不太能理解的是为什么它一定要让其它事务阻塞等待，而不是先返回不可靠的SELECT结果，如果有冲突的话再让COMMIT失败，整个事务被ROLLBACK，而且截至COMMIT成功之前调用者必须把SELECT结果视为不可靠的，不能当真呢？

#32 (comment) 早已做出循环论证：

因为COMMIT本就极少会产生错误（ 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模式如

SELECT a, b FROM t; -- (1, 2)
UPDATE t SET b = 2+1 WHERE a = 1

因为您想要UPDATE使得b=b+1=3，然而在您SELECT到的b值可能是来自另一个尚未提交事务中的

UPDATE t SET b = 2 WHERE a = 1

所造成的影响，如果另一个事务最终ROLLBACK了那么2+1就是错误的

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

但您可以在此使用乐观并发控制的思维改成

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语句，如果一行已经被锁定，则InnoDB 执行“半一致”读取，将最新提交的版本返回给MySQL，以便MySQL判断该行是否符合 WHERE条件 UPDATE。如果该行匹配（必须更新），MySQL 将再次读取该行，这次InnoDB要么锁定它，要么等待锁定它。

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

所以实践中很少有人用READ UNCOMMITTED事务隔离级别，ANSI SQL中要求实现主要是为了留一个escape hatch作为DBA对频繁死锁无计可施时的last resort 然而在PGSQL中直接实现的更加严格也就是完全禁止dirty read： image 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并COMMIT，那事务A仍然不知道事务B做了什么

https://dev.mysql.com/doc/refman/8.0/en/innodb-consistent-read.html 进一步指出：

假设您在默认 REPEATABLE READ隔离级别下运行。当您发出一致读取（即普通 SELECT语句）时， InnoDB为您的事务提供一个时间点，您的查询将根据该时间点查看数据库。如果另一个事务删除一行并在您的时间点分配后提交，您不会看到该行已被删除。插入和更新的处理方式类似。

但又指出REPEATABLE READ只是对于reads也就是SELECT生效，对INSERT/UPDATE中由WHERE子句所产生的reads无效

数据库状态的快照适用 SELECT于事务中的语句，不一定适用于 DML语句。如果您插入或修改某些行然后提交该事务， 则从另一个并发REPEATABLE READ事务发出的DELETEorUPDATE语句 可能会影响那些刚刚提交的行，即使会话无法查询它们。如果一个事务确实更新或删除了由另一个事务提交的行，那么这些更改对当前事务是可见的。

这也就解释了上文中的

在READ UNCOMMITTED和REPEATABLE READ事务隔离级别下不要使用朴素的SELECT+INSERT/UPDATE模式

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

事务的所谓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/glossary.html#glos_consistent_read

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

因此REPEATABLE READ或者说mysql所谓的Consistent Nonlocking Reads就像是一种无锁数据结构

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

INSERT/UPDATE/DELETE3大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）
永远不会看到A多INSERT的一行即便A已COMMIT
SERIALIZED B在A执行完SELECT后SELECT时阻塞等待A执行INSERT+COMMIT B会看到A多INSERT的一行
但这并不是phantom read因为B此前根本没有读到那一行（B一直在等待ACOMMIT）

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

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：

而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 takes an exclusive lock (an X lock) on the specified table. To make locking at multiple granularity levels practical, InnoDB uses intention locks. 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 (IS) indicates that a transaction intends to set a shared lock on individual rows in a table.
  • An 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 sets an IS lock, and SELECT ... FOR UPDATE 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.
n0099 commented 1 year ago

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

A happens-before B 就是说 B 能看到 A 的副作用。 happens-before 具有传递性。

然而从字面上看B发生在A之后不代表B一定知道A发生了 如同在READ COMMITTED隔离级别中事务B无法看到尚未COMMIT的事务A做出的副作用 而在REPEATABLE READ隔离级别中B只要早于A读取了某些行那么B就永远无法看到A（不论A是否COMMIT）对这些行做出的变动

这样的话虽然不太直观，但是不会像时序图只描述了可能发生的时序的一种，而是能够只依赖于确实被约束的时序关系。

您也可以画一大堆四叶头子CS硕士PLT理论中级高手仏皇irol阁下 @kokoro-aya 最痛恨的UML时序图来试图穷举出所有的race condition排列组合

“跨线程共享变量使用volatile避免不同步问题”是一个被广泛地重复的错误的说法。请不要继续重复这个错误了。

事实核查：截止2023年1月，c/cpp/java/c#培训班所批发生产的CRUD业务逻辑中级高手们仍在无脑加volatile来试图解决race condition 我的评价是： https://github.com/n0099/TiebaMonitor/issues/32#issuecomment-1401828929

然而so人早已道明真相： 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并不是只要加了就没有一致性方面问题的魔法，需要正确理解和运用。 话说比起说是小政治家、哲学家和神学家的崇拜，我倒感觉像是伊欧那样的程序员会有的崇拜（（

我觉得应该不会实现成 P/Invoke 或者 syscall 了对应的系统 API 。这些 Interlocked 操作是很轻量的，基本上是单个原生指令的封装。实现成 P/Invoke 甚至 syscall 的话就太慢了。理应是直接产生对应的汇编指令的。

但 https://learn.microsoft.com/en-us/windows/win32/api/winnt/nf-winnt-interlockedcompareexchange 的确是winnt.h中声明实现位于kernel32.dll的一个dllexport函数，可能是为了方便难以/无法inline asm但可以dllimport/ffi的语言用户也可以享用这些cpu指令带来的原子操作

根据 https://stackoverflow.com/questions/11161120/whats-the-point-of-methodimploptions-internalcall https://stackoverflow.com/questions/5110706/how-does-extern-work-in-c 由于 https://referencesource.microsoft.com/#mscorlib/system/threading/interlocked.cs,1e337a3aaaf240e4 的.net fx源码显示 image 因此他们是由运行时所使用的CLR实现（.net fx/mono/.net core等）来实现的，c/cpp所编写的CLR实现直接用inline asm还是去P/Invoke/syscall是他的自由

我横竖睡不着，仔细看了半夜，才从 https://en.wikipedia.org/wiki/Shared_Source_Common_Language_Infrastructure 中看出字来，每叶都写着M$FT！

就像它不会把两个 int32 的加法实现成 P/Invoke 某个 API ，即便假如真的有这样的 API 。

然而如果要求对两个int的读是同一个原子操作那的确有Interlocked.Add，当然我同样不知道他的内部实现是P/Invoke还是啥

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

简化这个表的字段到(time, a)，有以下行：

4, a
4, a
3, a
2, b
1, a

如果UNIQUE约束建立在(time, a)上，那么红色的行会被认为违反约束：

- 4, a
+ 4, a
+ 3, a
+ 2, b
+ 1, a

而如果UNIQUE约束建立在a上：

- 4, a
- 4, a
- 3, a
+ 2, b
- 1, a

然而我想要的是

- 4, a
- 4, a
+ 3, a
+ 2, b
+ 1, a

并没有“其它不相等的行的某一列的范围”那种上下文信息

即便要查询出这种模式都无法只通过window fun： https://github.com/n0099/TiebaMonitor/issues/32#issuecomment-1379143131

对此问题我当然可以选择写一个基于window function的DELECT的后台 crontab

而是需要类似 https://stackoverflow.com/questions/34599599/group-by-adjacent-rows-based-on-two-columns/34599655#34599655 demo: https://www.db-fiddle.com/f/qybbksuqvJYEAfTK1QHzCe/0 image image

如果你不想那么“补救”的话

补救其实是事务执行一段时间后再来定期检测然后回退这些重复行，因此他跟事务毫无关系

但这跟UPSERT/INSERT IGNORE类似仍然是缓解问题而不是解决问题

所以本帖的标题才叫如何从理论上避免，建议立即致电四叶头子CS硕士PLT理论中级高手仏皇irol阁下 @kokoro-aya

  • 你需要的约束是什么？就消息相同的两行之间必须间隔有时间戳介于其间且消息不同的行这种约束而言

是

它是“如果存在这样（时间戳介于其间且消息不同）的行的话那么满足约束”，显然它不可能用UNIQUE这种“如果不存在这样（对应列相同）的行的话那么满足约束”的约束实现。

是

  • 有没有办法让数据库引擎明白而且能够检查这样的约束？

无

还是说只有做SELECT然后由调用者根据SELECT结果才能进行这一约束的检查？

是

  • 如果能的话，能不能让数据库引擎根据这一约束检查决定要不要让INSERT成功？而且，原子地——其它事务的INSERT可能破坏这一约束，所以约束检查和INSERT必须原子地发生。

数据库INDEX constraint（UNIQUE和FOREIGN KEY都必须是建立在索引上的）都是在执行INSERT/UPATE/DELETE3大DML时就会检查的，也就是同步地而不是异步的

并且根据 https://github.com/n0099/TiebaMonitor/issues/32#issuecomment-1404661123

但又指出REPEATABLE READ只是对于reads也就是SELECT生效，对INSERT/UPDATE中由WHERE子句所产生的reads无效

数据库状态的快照适用 SELECT于事务中的语句，不一定适用于 DML语句。如果您插入或修改某些行然后提交该事务， 则从另一个并发REPEATABLE READ事务发出的DELETEorUPDATE语句 可能会影响那些刚刚提交的行，即使会话无法查询它们。如果一个事务确实更新或删除了由另一个事务提交的行，那么这些更改对当前事务是可见的。

这也就解释了上文中的

在READ UNCOMMITTED和REPEATABLE READ事务隔离级别下不要使用朴素的SELECT+INSERT/UPDATE模式

DML甚至会绕过事务隔离级别对普通（无FOR SHARE/UPDATE带来的IS/X锁）的SELECT施加的影响，也就是说相当于始终是READ COMMITTED：

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

您的示例与Isolation Levels. 这是因为它们影响readers行为，而不是writers，而在您的示例中只有writers. 您应该参考这篇 BOL 文章：Understanding Isolation Levels 说

选择事务隔离级别不会影响为保护数据修改而获取的锁。无论为该事务设置的隔离级别如何，事务始终会对其修改的任何数据获取独占锁并持有该锁直到事务完成。对于 读取操作，事务隔离级别主要定义保护级别免受其他事务所做修改的影响。

  • 如果不能的话，能不能让数据库引擎保证：要么影响这一约束的那部分SELECT结果在SELECT到INSERT成功期间没有变化

SELECT ... FOR UPDATE所产生的IX锁可以，因为上锁后其他DML都必须阻塞等待这个占有IX锁的事务COMMIT 回顾经典表格之 https://dev.mysql.com/doc/refman/8.0/en/innodb-locking.html#innodb-intention-locks image

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 takes an exclusive lock (an X lock) on the specified table. To make locking at multiple granularity levels practical, InnoDB uses intention locks. 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 (IS) indicates that a transaction intends to set a shared lock on individual rows in a table.
  • An 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 sets an IS lock, and SELECT ... FOR UPDATE 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.

INSERT不发生效果

什么叫INSERT不发生效果？什么都不做然后返回affected rows=0吗，那就是只能用于忽略UNIQUE约束的INSERT IGNORE： https://github.com/n0099/TiebaMonitor/issues/32#issuecomment-1379143131

然后在每次INSERT后SELECT ROW_COUNT就可以知道少了多少行没有被插入（由于 DUPLICATE 或其他错误）（但只有行的数量，而非精确的对应关系，如果需要知道具体少插入了哪些行仍然需要SELECT之前插入的行范围）

但不论 UPSERT 还是 IGNORE 都是从数据库层面缓解问题，他不是保证永不发生 DUPLICATE 错误，而是保证发生 DUPLICATE 错误后您的程序也能跑（因为一个改成了 UPDATE ，一个将 ERR 降级到 WARN ）

或者说没有任何其它事务能够既看到这个INSERT的效果又成功提交

提交什么？其他事务中的INSERT吗？不能除非违反了UNIQUE约束，然而很明显这个场景并没有违反

n0099 commented 1 year ago

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

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

https://github.com/n0099/TiebaMonitor/issues/32#issuecomment-1404661123 早已提出质疑：

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

n0099 commented 1 year ago

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

这跟数据库引擎的实现里面有没有采用 CPU 指令集提供的无锁原子操作其实关系不大。这更多是关于它的接口采取怎样的设计的问题

是，如同无锁数据结构的内部实现也并不一定非要用cpu提供的这些原子操作指令，他也可以继续用传统的mutex阻塞就像concurrentdict： https://github.com/n0099/TiebaMonitor/issues/32#issuecomment-1401263844

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

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

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在每个桶上使用严格的链表： image 这确保每个桶都与所有其他桶完全分开；从桶中添加或删除项目独立于对其他桶的任何更改。

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

单个 SQL 语句发生在远远超过单个 CPU 指令的时间跨度上。（显然需要执行十万甚至九万个指令来 parse 并执行您的一个 SQL 语句）

回顾经典之新创无际上海贵族HKUST高材生lys神 @DWVoid 曾于去年锐评cpython运行时：一个int加法都要编译为数百条x86汇编来执行

引擎内部基于阻塞等待锁/自旋锁还是基于无锁数据结构，跟用户的 SQL 事务跟其他用户的 SQL 事务之间是通过锁还是无锁来解决竞态问题，并不需要有对应关系。

截止2023年1月，DBA面试题八股文仍在考您mysql中的myisam table lock和innodb record/gap/nextkey lock： https://dev.mysql.com/doc/refman/8.0/en/innodb-locking.html#innodb-insert-intention-locks 其原因正是由于失败的抽象隔离导致数据库用户遇到任何race condition时都必须去接触这些抽象泄露出来的核废料： https://github.com/n0099/TiebaMonitor/issues/32#issuecomment-1401223094

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

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

建议阅读该词条引用 Wait-Free Synchronization 。 特别地，其中说到：

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.

经典阅读理解26页长的于1991年发表于TOPLAS的论文 与此同时我还在研读如何利用四叶头子CS硕士PLT理论中级高手仏皇irol阁下十余年前于仏国国家数字科学与技术研究所所发表的stable diffusion早期论文 https://maverick.inria.fr/Publications/2008/OBWBTS08/diffusion_curves.pdf 中的指导思想赋能对tbm中5.25m张贴吧图片进行高精度ocr的任务： https://www.imagemagick.org/discourse-server/viewtopic.php?p=138987#p138987 image image

而阁下引用的这篇论文pdf也是经典后期ocr然后叠加classifier输出的文本框嵌入pdf实现可选中复制的文本，例如用于google books数据集的 https://github.com/tesseract-ocr/tesseract ： image

kokoro-aya commented 1 year ago

我也有点好奇这个问题该怎么解决。因为这个锁显然是和数据库有关的，或者更宽泛地说，某一个有限的并且具有抢占性质的资源。

一般来说反应式或者异步的advocator会鼓吹异步的无锁开发的优越性，但是显然的，这种语境下的锁和资源锁是两回事。如果涉及到对有限的资源的依赖和随时更新的话，那还是会遇到这个issue里提到的时序问题。

假设在一个DBMS里面可以通过设定事务的等级来解决这个问题，那也顶多只能说是DBMS帮我实现了这个锁（顺便实现了C10K）。

那么如果是一个在自己的容器里面要去实现的资源呢？自己去实现MVCC嘛。

如果是完全用异步的写法的话还会有个问题，因为不允许阻塞进程了，所以不能用Java壬常用的无脑加锁的办法来解决，那就更麻烦了。但是你也不能说比如说我这个组件用了这种写法就强迫别人也异步吧（什么传染性）

yangbowen commented 1 year ago

数据库事务的ROLLBACK也会导致该事务中所有做出的INSERT/UPDATE/DELETE对表造成的影响都被回退 或者说在COMMIT之前这些影响都只存在于mysql undo log和change buffer中 然而这同样无法回退某个READ UNCOMMITTED事务隔离级别的事务此前已经获得的读取结果，因为客户端已经知道了

是。这就是主要的差别，客户端跑在 CPU 里所以 CPU 可以让客户端把已经知道的事情忘掉，而数据库引擎当然办不到。

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

然而 Intel® 64 and IA-32 Architectures Software Developer’s Manual 16.3.6 中早已指出：

However, if an RTM execution aborts, all memory updates from within the RTM region are discarded and never made visible to any other logical processor.

并且我合理怀疑它并不是回滚那个线程此前的读取使其又忘记了key=3的存在，而是这些写入都还在本核心的 L1 当中，根本不会被其它线程看到；而逻辑处理器之间的缓存一致性协议本就需要处理其它逻辑处理器的缓存中含有这个地址，而且已修改未回写的情形。 而您早已道明

也就是mysql默认事务隔离级别REPEATABLE READ下需要对每个事务每个SELECT所读到的每一行都做缓存（被称作SNAPSHOT）https://dev.mysql.com/doc/refman/8.0/en/innodb-consistent-read.html

一样的，这里单个核心独占的 L1 就起到了这个 SNAPSHOT 的作用。如何在这个 SNAPSHOT 跟共享的主存储器之间同步是本来就要处理的问题，事务内存只是扩充了暴露给程序员的接口，让程序员可以更有效地利用处理器早就实现了的机制。

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

但您可以在此使用乐观并发控制的思维改成

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语句，如果一行已经被锁定，则InnoDB 执行“半一致”读取，将最新提交的版本返回给MySQL，以便MySQL判断该行是否符合 WHERE条件 UPDATE。如果该行匹配（必须更新），MySQL 将再次读取该行，这次InnoDB要么锁定它，要么等待锁定它。

这倒是很合理，而且跟 CAS 是一个原理。 而且和 CAS 一样也可能别的客户端反复地写入然后您反复地调整WHERE条件然而再次试图UPDATE时又被改了。 以及，这样的话，有没有 ABA 问题（WHERE的值没变，但含义已经不一样了，而且按照新的含义不能这么写入了）的相当情况呢？

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

想必正好适合

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

然而在REPEATABLE READ事务隔离级别下，如果事务A在两万年前就业已SELECT了某行并一直卡着不COMMIT/ROLLBACK，而随后在一万年前时另一个事务B对该行做了DML并COMMIT，那事务A仍然不知道事务B做了什么

这种情况下如果事务A采取上面说的

UPDATE t SET b = 2+1 WHERE a = 1 AND b = 2

能否因为事务B的修改而导致这一写入affected rows 0呢？ 如果能的话，会在UPDATE之后还是在COMMIT之后看到affected rows 0呢？ 然后您又说

但又指出REPEATABLE READ只是对于reads也就是SELECT生效，对INSERT/UPDATE中由WHERE子句所产生的reads无效

但是

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

既然如此，那么如果：

A事务

SELECT a, b FROM t; -- (1, 2)

B事务

UPDATE t SET b = 5 WHERE a = 1;
COMMIT;

A事务

UPDATE t SET b = 6 WHERE b = 5;
SELECT a, b FROM t; -- (1, 2) or (1, 6) ?

既然REPEATABLE READ对UPDATE的WHERE子句无效，那就是说A事务的UPDATE仍旧会看到已提交的B事务的写入，而且会写入b = 6。这个写入是A事务自己作出的，但又间接依赖于B事务的写入。此时会发生哪种情况？

  1. A事务仍旧读到(1, 2)，尽管自己的成功的写入
  2. A事务读到(1, 6)，尽管间接依赖于在A事务期间的B事务的写入
  3. A事务的写入不起作用，尽管不应受REPEATABLE READ效果的WHERE子句因B事务的写入而被满足。
yangbowen commented 1 year ago

我觉得应该不会实现成 P/Invoke 或者 syscall 了对应的系统 API 。这些 Interlocked 操作是很轻量的，基本上是单个原生指令的封装。实现成 P/Invoke 甚至 syscall 的话就太慢了。理应是直接产生对应的汇编指令的。

但 https://learn.microsoft.com/en-us/windows/win32/api/winnt/nf-winnt-interlockedcompareexchange 的确是winnt.h中声明实现位于kernel32.dll的一个dllexport函数，可能是为了方便难以/无法inline asm但可以dllimport/ffi的语言用户也可以享用这些cpu指令带来的原子操作

虽然winnt.h中确实声明了这个函数，但您给出的链接中也说到

This function is implemented using a compiler intrinsic where possible. For more information, see the WinBase.h header file and _InterlockedCompareExchange.

而且就 MSVC 而言它确实同时也是 compiler intrinsic 。意思是说编译器会直接内联对应的汇编指令，不会真的写一个函数调用，除非您设置编译选项来禁用 compiler intrinsics 。

根据 https://stackoverflow.com/questions/11161120/whats-the-point-of-methodimploptions-internalcall https://stackoverflow.com/questions/5110706/how-does-extern-work-in-c 由于 https://referencesource.microsoft.com/#mscorlib/system/threading/interlocked.cs,1e337a3aaaf240e4 的.net fx源码显示 image 因此他们是由运行时所使用的CLR实现（.net fx/mono/.net core等）来实现的，c/cpp所编写的CLR实现直接用inline asm还是去P/Invoke/syscall是他的自由

我横竖睡不着，仔细看了半夜，才从 https://en.wikipedia.org/wiki/Shared_Source_Common_Language_Infrastructure 中看出字来，每叶都写着M$FT！

是自由，但它既然用了InternalCall那理应是为了让 CLR 实现能直接产生对应的汇编指令吧。 从 CLR 调用原生 API 不仅有函数调用，还会有 managed to unmanaged transition ，开销更大了。而在这里当然是没有必要的。 另外，

就像它不会把两个 int32 的加法实现成 P/Invoke 某个 API ，即便假如真的有这样的 API 。

然而如果要求对两个int的读是同一个原子操作那的确有Interlocked.Add，当然我同样不知道他的内部实现是P/Invoke还是啥

其实不能。您仔细看一下，两个形参只有一个是ref int，而对没有位置没有身份只是个值的value当然没有 原子地 这一说。 事实上， x86 的绝大部分指令都有至多 2 个操作数，其中至多 1 个内存操作数，另一个只能是寄存器。那当然也没有双地址原子操作。

可以进一步想一想。所谓对两个地址的读是同一个原子操作，比起假如对两个地址的读是分开的两个原子操作而言，区别在于且仅在于这样的情况： 对这两个地址的 读 之间 看到了其它线程对这两个地址的这样的 原子写 。该 原子写 具有如此的原子性，以至于该两个地址只有两种可见状态，一是在该 原子写 可见之前，二是在该 原子写 可见之后。然而，如果该 读 不作为一个整体具有原子性，则上述 原子写 可以发生在两个 对单个地址的 原子读 之间，从而该 非原子读 看到了该 原子写 一半可见 的状态；反之，对 两个地址的 原子读 不允许这样让该 原子写 只对一半可见。 然而根本不存在这样对两个地址的原子写，写操作和读操作一样只能对单个地址具有原子性。总之，论证了这样一件事： 双地址原子读 和 双地址原子写 只有同时存在才有意义，只存在一个的情况下和皆不存在是无法区分的。

换一种方式来说就是。您原子地读两个不同地址，可是如果写入者不能够原子地写两个不同的地址，只能够原子地写一个地址的话，那么您并无法区分，您的读不是原子的，跟您的读原子地读到了写入者写了一半的状态。从而您的读的这种原子性没有意义。

yangbowen commented 1 year ago

或者更宽泛地说，某一个有限的并且具有抢占性质的资源。

从我看来这不是一个关于 具有抢占性质的资源 的问题，而是一个关于 所需的原子语义并没有被数据库层实现 的问题。 这个场景当中之所以会需要锁，完完全全就是为了确保消息相同的两行之间必须间隔有时间戳介于其间且消息不同的行这一约束并INSERT行，作为一整个原子操作。它和可能等很久的锁（例如等待用户输入——也有同步写法和异步写法的区分）完全不是一回事。这个场景当中 锁 只是实现这个原子性要求的一种方式。 换句话说，这里的有限并且具有抢占性质的资源，拿到资源之后要做的事是即刻知道的，有限步操作完成之后对资源的使用也就完成了。即便需要等待别人，也是等待别人的即刻知道是什么操作的有限步操作。和反应式通常想避免的锁和等待（等待一些更不确定的事，例如用户输入、网络响应等）并不是一回事。 假如 SQL 语句提供这样一个机制，允许你指定本 issue 所需要的约束的话，那我想这是最理想的解决方案，既避免了和锁相关的死锁、活锁等问题，也避免了乐观锁的情况下每次重试都需要客户端和数据库之间的至少一个 round-trip （大幅减小延迟也会大幅减小 resource starvation 的概率）。 然而不幸的是数据库提供的这个接口似乎并没有那么 flexible 。

如果是完全用异步的写法的话还会有个问题，因为不允许阻塞进程了，所以不能用Java壬常用的无脑加锁的办法来解决

这难道不该反过来说吗？如果某个组件采取同步的阻塞的写法，那这会传染给它的用户，用户想异步也不好异步了，除非为这段代码开一个线程然后在主线程里异步等待它。 相反， 组件异步 用户同步 的情况应是好办得多的：这种情况下用户只需要在边界的地方做一个 阻塞等待结果 的操作就把它转化为同步了。 关于这个的问题上，我认为异步的本质是向用户提供更多信息（更不 黑盒 ）的接口：同步的写法是需要等待了就地阻塞等待，而并没有将是否需要等待和等待的是什么的信息反馈给调用者。得不到这一信息的调用者当然也就无法自定义此处的行为，例如无法同时等待其它事件源。当然了，除非为它开一个线程。与之相反，异步的写法是将我要等待到什么才能继续下一步工作也包含在接口当中，所以是更能自定义的。

n0099 commented 1 year ago

既然如此，那么如果：

A事务

SELECT a, b FROM t; -- (1, 2)

B事务

UPDATE t SET b = 5 WHERE a = 1;
COMMIT;

A事务

UPDATE t SET b = 6 WHERE b = 5;
SELECT a, b FROM t; -- (1, 2) or (1, 6) ?

既然REPEATABLE READ对UPDATE的WHERE子句无效，那就是说A事务的UPDATE仍旧会看到已提交的B事务的写入，而且会写入b = 6。这个写入是A事务自己作出的，但又间接依赖于B事务的写入。此时会发生哪种情况？

  1. A事务仍旧读到(1, 2)，尽管自己的成功的写入
  2. A事务读到(1, 6)，尽管间接依赖于在A事务期间的B事务的写入
  3. A事务的写入不起作用，尽管不应受REPEATABLE READ效果的WHERE子句因B事务的写入而被满足。

是(1,6) image https://stackoverflow.com/questions/59287861/repeatable-read-isolation-level-select-vs-update-where https://dba.stackexchange.com/questions/165259/repeatable-read-which-one-is-correct

https://dev.mysql.com/doc/refman/8.0/en/innodb-consistent-read.html 对此早有预言：

一致性读取 意味着 使用InnoDB多版本控制在某个时间点向查询呈现数据库的快照。查询会看到在该时间点之前提交的事务所做的更改，而没有看到后来或未提交的事务所做的更改。此规则的例外情况是查询会看到同一事务中较早语句所做的更改。此例外导致以下异常：如果您更新表中的某些行，一个 SELECT看到更新行的最新版本，但它也可能看到任何行的旧版本。如果其他会话同时更新同一个表，异常意味着您可能会看到该表处于数据库中从未存在过的状态。

n0099 commented 1 month ago

https://news.ycombinator.com/item?id=41159797 https://news.ycombinator.com/item?id=41159384