V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
h0099
V2EX  ›  程序员

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

  •  1
     
  •   h0099 ·
    n0099 · 2023-01-11 02:55:18 +08:00 · 2166 次点击
    这是一个创建于 465 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

    和一个外部数据库中的某个表,假设表只有一个字段并且是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插入的)

    这实际上就是serializabilitylinearizabilityserializability的区别),即完全放弃了并行度,同一时间只能有一个任务在工作。这也意味着进程锁此时也是完全无用的,因为他的主要目的是让其他线程知道当前有哪些行即将插入表(但还没有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 友们能够补充更多理论上以及实践中如何处理这类问题的方案

    32 条回复    2024-01-18 03:08:45 +08:00
    codehz
        2
    codehz  
       2023-01-11 09:28:51 +08:00 via iPhone
    我来捋一捋,这一大段先查询再插入的目的是防止重复的插入?有没有一种可能用 INSERT ON DUPLICATE 来解决呢?直接忽略重复插入的冲突有影响吗
    h0099
        3
    h0099  
    OP
       2023-01-11 13:31:43 +08:00
    #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`]( https://dev.mysql.com/doc/refman/8.0/en/information-functions.html#function_row-count)就可以知道少了多少行没有被插入(由于 DUPLICATE 或其他错误)(但只有行的数量,而非精确的对应关系,如果需要知道具体少插入了哪些行仍然需要`SELECT`之前插入的行范围)

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

    而我更需要避免的是这种类似 DUPLICATE 造成了数据冗余,但又完全符合数据库层的 UNIQUE 约束的问题:

    可以看到两个线程都插入了“完全一致”的行,除了 time 字段值分别是 1674453494 和 1674453492 (因此两者 INSERT 时都不会触发 DUPLICATE 错误)
    而这是因为右侧线程在左侧线程于`12:39:54.874436`时间`COMMIT`之前就已经`SELECT`了,所以右侧不知道左侧即将`INSERT` time 为 1674453492 的“重复”行

    对此问题我当然可以选择写一个基于[window function]( https://learnsql.com/blog/sql-window-functions-cheat-sheet/)的`DELECT`的后台 crontab (或是线程每次`INSERT`后都尝试`DELETE`一次)来定期执行删除这类冗余的“重复”行
    但这跟`UPSERT/INSERT IGNORE`类似仍然是缓解问题而不是解决问题
    而且`DELETE`作为事(`INSERT`)后补救也不可能解决更罕见(线程在同一秒内完成所有任务)的两个线程插入的所有字段都相同(也就是触发 DUPLICATE 错误)的场景
    codehz
        4
    codehz  
       2023-01-11 14:09:44 +08:00 via iPhone
    我记得可以 on duplicate update key=key 这样来忽略 duplicate 而且不修改数据(返回 0 行修改)
    h0099
        5
    h0099  
    OP
       2023-01-11 14:13:30 +08:00
    原地 UPDATE 为原值跟 INSERT IGNORE 是类似的
    只不过完全静默了 WARN (而 INSERT IGNORE 是将 DUPLICATE ERR 降至 WARN )
    h0099
        6
    h0099  
    OP
       2023-01-11 17:34:04 +08:00
    > 但不论 UPSERT 还是 IGNORE 都是从数据库层面缓解问题,他不是保证永不发生 DUPLICATE 错误

    如果要从数据库层面解决可以尝试
    7.`SELECT ... FOR UPDATE`语法所产生的`插入意向排他锁`
    ---

    线程 1 和 2 每次 SELECT 时都通过 WHERE 子句(只取 field=a 的行)缩小了`FOR UPDATE`所造成的[IX 锁]( https://dev.mysql.com/doc/refman/8.0/en/glossary.html#glos_intention_exclusive_lock)的范围(不然没有 WHERE 我怀疑会锁全表,也就是类似于[`LOCK TABLES ... WRITE`]( https://dev.mysql.com/doc/refman/8.0/en/lock-tables.html))
    线程 2 在执行后必须无限期(直到达到[innodb_lock_wait_timeout]( https://dev.mysql.com/doc/refman/8.0/en/innodb-parameters.html#sysvar_innodb_lock_wait_timeout))等待线程 1`COMMIT`,因为线程 2 想要 SELECT 的行`field=a`已于此前被线程 1 设置 IX 锁
    不难看出此时进程范围的全局锁(进程锁)已经没有存在的必要了,因为他的目的跟 IX 锁是类似的(但他无法目前像 IX 锁那样无限期阻塞任何试图读取进程锁的线程)
    实际上 IX 锁同样降低了并行度,因为这跟原文中提出的`1.延后线程 2 查询数据库的时机`是类似的目的:
    都是将任何试图读取某些行(`IX 锁`是 field=a 的行,`1.延后线程 2`是所有行,也就是回到了`LOCK TABLES`)的线程挂起直至正在写入某些行的其他线程`COMMIT`
    也就是说两者都是试图通过[serialize]( https://en.wikipedia.org/wiki/Serializability)最开始读行的过程从而避免后续`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<T> 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
    daxiguaya
        7
    daxiguaya  
       2023-01-17 11:48:23 +08:00
    1. 图 1 中的"进程锁"清理数据的时机可以调整下,等到没有任何活跃事务的情况下再把它清掉.

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

    PS: 这些是基于单体服务的设计. 我不喜欢用`SELECT ... FOR UPDATE`,它通常会让我其它功能查询也被无辜的阻塞
    h0099
        8
    h0099  
    OP
       2023-01-18 00:10:18 +08:00
    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`),但阁下的确可以亲自试试看
    daxiguaya
        9
    daxiguaya  
       2023-01-19 15:16:50 +08:00
    @h0099 1. 我对于"进程锁"所要处理的问题有不一样的看法. 我认为"进程锁"应当能解决你提出的"幻读"的问题,它存的是真正写入的数据. 你担心"无事可做",只能说目前只能保证不会重复插入导致整个事务回滚,这个应该更重要? 关于"饥饿"的问题,如果真的是瓶颈的话,可以提早去识别"垃圾数据": 非当前所有活跃"写事务"需要的数据都是"垃圾数据"

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

    PS: `SELECT ... FOR UPDATE`这个问题我保留观点,还要考虑间隔锁、表锁之类的问题,除非死锁的时候我会去 DEBUG 数据库的锁状态,其它情况我想操这个心 :)
    h0099
        10
    h0099  
    OP
       2023-01-19 21:35:26 +08:00
    > 我认为"进程锁"应当能解决你提出的"幻读"的问题

    我遇到的不是幻读而是“滞后”读,您可以从图 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`
    h0099
        11
    h0099  
    OP
       2023-01-24 09:21:41 +08:00
    https://github.com/n0099/TiebaMonitor/issues/32#issuecomment-1401081050 @yangbowen

    > 可以看出在符合这个时序图的流程中进程锁和数据库层事务都无法阻止这种冲突,因为
    > 1. `线程 2`访问数据库表中已有行的时机早于`` 线程 1``COMMIT ``他的`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`的发生,应该并不是说保证它会发生?
    h0099
        12
    h0099  
    OP
       2023-01-24 09:22:08 +08:00
    @yangbowen https://github.com/n0099/TiebaMonitor/issues/32#issuecomment-1401116944

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

    我的理解是这里需要的行为实际上是一个原子的 [RMW 操作]( https://en.wikipedia.org/wiki/Read%E2%80%93modify%E2%80%93write) ——如何插入这一行是依赖于 相同的行是否已被插入 这个要读取到的条件的。这个读操作+插入操作整体上必须是原子的 /事务的。
    比较常见的一种做法是提供 [CAS]( https://en.wikipedia.org/wiki/Compare-and-swap) 原子操作:如果满足[条件]那么[写入]否则[失败] 。另一种做法是提供 [LL/SC]( https://en.wikipedia.org/wiki/Load-link/store-conditional) :如果先前读取的[几个位置]没有被写入那么[写入]否则[失败]。x86 提供前者,而 ARM 提供后者,而不只是提供原子的读、写。以 CAS 为例,使用者可以采取如下方案:
    ```
    临时值 = 读(全局值);
    临时值 2 = 计算(临时值);
    while (!CAS(全局值, 临时值, 临时值 2)) {
    临时值 = 读(全局值);
    临时值 2 = 计算(临时值);
    }
    ```
    其中`CAS`是原子的
    ```
    CAS(data, expected, desired) {
    if (data == expected) {
    data = desired;
    return true;
    } else {
    return false;
    }
    }
    ```
    实际上维基百科关于上面说的 RMW 操作的 [词条]( https://en.wikipedia.org/wiki/Read%E2%80%93modify%E2%80%93write) 也已指出,CAS 、LL/SC 具有更高的 共识数 ,不可能只用 原子读 、原子写 之类的具有更低 共识数 的操作实现,无论做多少个这样的操作。
    那我觉得您的这个场景也是类似的,您需要的是一个原子的 仅当不会冲突才写入 的操作,不可能只用低共识数的 总是读取 总是写入 操作实现。

    ---

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

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

    总之,这是一个很通用的原理。我猜对于数据库的分布式访问来说应该也是有原理相当的构造的。只是发生在更长的延时、更大的数据、更复杂的数据结构。
    h0099
        13
    h0099  
    OP
       2023-01-24 09:23:11 +08:00
    @n0099 github.com/n0099/TiebaMonitor/issues/32#issuecomment-1401199725

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

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

    在图
    user-images.githubusercontent.com/13030387/214179293-c04a07a2-41cd-4b01-bb01-3852c4a426e3.png
    中`线程 2`是在`线程 1`执行`INSERT`和`COMMIT`之前就`SELECT`了的,因此`线程 2`认为行 a 不存在,而`线程 2`如果不`INSERT`行 a 而是直接`COMMIT`那么什么错误都不会发生
    因为`COMMIT`本就极少会产生错误( 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]( dev.mysql.com/doc/refman/8.0/en/optimizing-innodb-logging.html) [doublewrite]( dev.mysql.com/doc/refman/8.0/en/innodb-doublewrite-buffer.html),只有等到这些内存缓存的 buffer page 也被 fsync 到硬盘上了才是真的数据落地
    然而有些硬盘驱动会欺骗系统以让[fsync syscall]( dev.mysql.com/doc/refman/8.0/en/innodb-parameters.html#sysvar_innodb_flush_method)立即返回但实际上数据还在硬盘的缓存里并没有实际写入持久存储:
    www.percona.com/blog/2018/02/08/fsync-performance-storage-devices/
    dev.mysql.com/doc/refman/8.0/en/innodb-parameters.html#sysvar_innodb_flush_log_at_trx_commit
    > 许多操作系统和一些磁盘硬件会欺骗刷新到磁盘的操作。他们可能会告诉 [mysqld]( dev.mysql.com/doc/refman/8.0/en/mysqld.html)刷新已经发生,即使它没有发生。在这种情况下,即使使用推荐的设置也无法保证事务的持久性,在最坏的情况下,断电可能会损坏 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`都不会发生
    h0099
        14
    h0099  
    OP
       2023-01-24 09:23:54 +08:00
    @n0099 github.com/n0099/TiebaMonitor/issues/32#issuecomment-1401223094

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

    > 我的理解是这里需要的行为实际上是一个原子的 [RMW 操作]( en.wikipedia.org/wiki/Read%E2%80%93modify%E2%80%93write) ——如何插入这一行是依赖于 相同的行是否已被插入 这个要读取到的条件的。这个读操作+插入操作整体上必须是原子的 /事务的。

    是,所以阁下也看到了我后来需要给`SELECT`加上`FOR UPDATE`从而实现每个线程通过`SELECT`就能锁住他们准备`INSERT`的`行 a 或 b`,mysql 称其为`IX 锁`: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`以保证数据一致性这个用途)
    ```sql
    START TRANSACTION;
    SELECT ...;
    INSERT ...;
    COMMIT;
    ```
    那么此时如果某个语句显式声明了锁,如`SELECT ... FOR UPDATE`产生了`IX 锁(有意排他锁)`
    或由于当前事务隔离级别(如`SERIALIZED`)导致语句隐式声明了锁
    那么有上锁就必定会有并行事务一直阻塞等待解锁,直到 serverfault.com/questions/241823/setting-a-time-limit-for-a-transaction-in-mysql-innodb

    > * 它也不会发生[活锁]( en.wikipedia.org/wiki/Deadlock#Livelock)。如果某个线程的 CAS 失败,那是因为其它线程在它读取和 CAS 的间隙当中做了写入。虽然此线程需要在循环中重新 CAS 一遍,但导致其失败的线程一定成功完成了写入。所以总是有进展发生,不存在活锁。

    而对于这种传统的阻塞锁设计而言只要复数个线程请求同一资源的频率足够高就很容易导致`livelock`,结果哪个线程都没有真的`INSERT`,enwiki 条目也进一步指出`livelock`是[starvation]( en.wikipedia.org/wiki/Starvation_(computer_science))的特例:`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 位资源`成原子性的会导致其`共识数`不同,如 en.wikipedia.org/wiki/Consensus_(computer_science)#Consensus_number 的表格中指出:
    Consensus number|Objects
    -|-
    $2n-2$|n-register assignment

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

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

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

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

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

    传统老牌 RDBMS 中基本没有什么无锁数据结构,毕竟其内部结构实现过于复杂恶俗使得他们无从下手改造成无锁的,这也是为什么 V2EX 的 @daxiguayawww.v2ex.com/t/908047#r_12595620 指出
    > 还要考虑间隔锁、表锁之类的问题,除非死锁的时候我会去 DEBUG 数据库的锁状态,其它情况我想操这个心 :)
    h0099
        15
    h0099  
    OP
       2023-01-24 09:24:21 +08:00
    @n0099 https://github.com/n0099/TiebaMonitor/issues/32#issuecomment-1401263844

    而我也大量使用了`.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<T> 有时需要锁定,但对于某些并发场景(例如,许多线程以相同的速率进行生产和消费),它是一个非常有效的集合。
    > ConcurrentDictionary<TKey,TValue> 在向字典中添加或更新数据时使用细粒度锁定,但它对于读取操作是完全无锁的。 这样针对以字典读取为最频繁操作的场景进行了优化。

    https://www.red-gate.com/simple-talk/blogs/inside-the-concurrent-collections-concurrentdictionary/ 进一步指出:
    > 那么,如果你要实现一个线程安全的字典,你会怎么做?天真的实现是简单地在所有访问字典的方法周围加一个锁。这可行,但不允许太多并发。
    > 幸运的是,使用的分桶 Dictionary 允许对此进行简单但有效的改进——每个桶一个锁。这允许修改不同存储桶的不同线程并行进行。任何对存储桶内容进行更改的线程都会锁定该存储桶,确保这些更改是线程安全的。将每个桶映射到锁的方法是 GetBucketAndLockNo 方法:
    ```csharp
    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`实现开销
    h0099
        16
    h0099  
    OP
       2023-01-25 16:20:23 +08:00
    @n0099 https://github.com/n0099/TiebaMonitor/issues/32#issuecomment-1401291684

    TL;DR: 我在 mysql 中使用`TRANSACTION`封装两个 [`SELECT ... FOR UPDATE`]( https://dev.mysql.com/doc/refman/8.0/en/innodb-locking-reads.html)所产生的[`IX 锁`]( https://dev.mysql.com/doc/refman/8.0/en/innodb-locking.html#innodb-intention-locks) 和 `INSERT` 语句使其成为原子操作实现了类似于[`ConcurrentDictionary.GetOrAdd`]( https://learn.microsoft.com/en-us/dotnet/api/system.collections.concurrent.concurrentdictionary-2.getoradd)的同步原语(您可以将具有`UNIQUE`约束的二维表视作一个`Dict<uniqueKey,fieldsTuple>`数据结构)

    https://github.com/n0099/TiebaMonitor/issues/32#issuecomment-1379143131
    > 不难看出此时进程范围的全局锁(进程锁)已经没有存在的必要了,因为他的目的跟 IX 锁是类似的(但他无法目前像 IX 锁那样无限期阻塞任何试图读取进程锁的线程)

    事实核查:截止 2023 年 1 月,我仍然无法直接在生产环境中删除进程锁,因为我观察到在删除后仍然会造成这种`race condition`并且无法得到合理解释
    h0099
        17
    h0099  
    OP
       2023-01-25 16:20:44 +08:00
    @yangbowen https://github.com/n0099/TiebaMonitor/issues/32#issuecomment-1401418933

    > 并且在`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]( https://en.wikipedia.org/wiki/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 。
    h0099
        18
    h0099  
    OP
       2023-01-25 16:20:59 +08:00
    @yangbowen https://github.com/n0099/TiebaMonitor/issues/32#issuecomment-1401433577

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

    这很合理。但是……

    > ```sql
    > 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]( https://en.wikipedia.org/wiki/Transactional_Synchronization_Extensions) 这个指令集就是这么做的,如果发生任何冲突就失败并且让调用者重来。利用现代处理器已有的缓存一致性协议等,处理器确实能够检测到冲突并在这样的情况下撤销已经执行的指令的影响。只不过比较不幸,它大概很难实现得安全,反复地出现安全漏洞(恶意的代码能够让`本来无权读取的内存`对`将要被撤销的状态`产生影响,再通过某些侧信道区别这些`本应撤销的状态差异`,从而作未授权的读取)迫使英特尔禁用该指令集。
    但这种原理应该是首先出现在数据库领域当中,后来才启发了 CPU 设计者设计类似原理的 CPU 指令的。只是我不知道具体哪个数据库的哪种操作允许这样,而不是采用锁和等待。

    > > * 它也不会发生[活锁]( https://en.wikipedia.org/wiki/Deadlock#Livelock)。如果某个线程的 CAS 失败,那是因为其它线程在它读取和 CAS 的间隙当中做了写入。虽然此线程需要在循环中重新 CAS 一遍,但导致其失败的线程一定成功完成了写入。所以总是有进展发生,不存在活锁。
    >
    > 而对于这种传统的阻塞锁设计而言只要复数个线程请求同一资源的频率足够高就很容易导致`livelock`,结果哪个线程都没有真的`INSERT`,enwiki 条目也进一步指出`livelock`是[starvation]( https://en.wikipedia.org/wiki/Starvation_(computer_science))的特例:`Livelock is a special case of resource starvation; the general definition only states that a specific process is not progressing.`

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

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

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

    github.com/n0099/TiebaMonitor/issues/32#issuecomment-1401116944
    > 提供 [CAS]( en.wikipedia.org/wiki/Compare-and-swap) 原子操作:如果满足[条件]那么[写入]否则[失败]

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

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

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

    回顾经典之`3.数据库事务隔离级别从 READ COMMITED 降至 READ UNCOMMITED`节的图
    ![image]( user-images.githubusercontent.com/13030387/214240624-e183eff5-e1d5-4733-99ad-8911c0d5c54f.png)

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

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

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

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

    dev.mysql.com/doc/refman/8.0/en/commit.html 对此早有预言:
    > 默认情况下,MySQL 在 启用[自动提交]( dev.mysql.com/doc/refman/8.0/en/glossary.html#glos_autocommit)模式的情况下运行。这意味着,当不在事务内时,每个语句都是原子的,就好像它被 START TRANSACTIONand 包围一样 COMMIT 。您不能使用 ROLLBACK 来撤销效果;但是,如果在语句执行期间发生错误,则回滚该语句。

    ---
    > 或者这么说:如果将`SELECT`移到`START TRANSACTION`之前(事务外),行为上是否会有任何可以依赖的差别呢?

    移出去会导致单条`SELECT`由于[`AUTO_COMMIT`]( dev.mysql.com/doc/refman/8.0/en/innodb-autocommit-commit-rollback.html)而变成一个只有他一个语句的事务(其隔离级别由于没有显式指定所以会使用 mysql 默认的`REPEATABLE READ`,然而实际上对于单语句事务而言任何隔离级别都是相同的),如果`SELECT`后面没有`FOR UPDATE`那么移出去也是一样的,即便有由于这是单语句事务所以 IX 锁也立即被释放了那还是没有造成差别

    而在 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 人早已道明真相:stackoverflow.com/questions/1171749/what-does-a-transaction-around-a-single-statement-do
    > 这可能归因于“迷信”编程,或者它可能表明对数据库事务性质的根本误解。一种更仁慈的解释是,这只是过度应用一致性的结果,这是不恰当的,这是爱默生委婉语的另一个例子:
    > 愚蠢的一致性是小脑袋的妖精,
    > 受到小政治家、哲学家和神学家的崇拜

    我的评价是:疑似当代 en.wikipedia.org/wiki/Cargo_cult en.wikipedia.org/wiki/Cargo_cult_programming 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`
    建议回顾 www.v2ex.com/t/909762#r_12593822

    > 乐观并发控制是要求每个客户端的后续读写都得依赖于此前查询所获得的的`ROW_VERSION`
    > 比如事务 1`SELECT 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 微软谜语:learn.microsoft.com/en-us/ef/core/saving/concurrency
    > 以及我之前对于类似的场景(但是是 INSERT-only 而不是 UPDATE )使用了数据库层提供的悲观并发控制,毕竟在 SQL 末尾加`FOR UPDATE`可比在 mysql 里用 TRIGGER 模拟单调递增的自增 sql server 的 ROW_VERSION 类型然后在程序业务逻辑里写乐观控制所带来的一大堆 if 简单多了:www.v2ex.com/t/908047

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

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

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

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

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

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

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

    ---
    > 对于根本没有什么硬件原子操作支持的平台,就可以这样实现原子操作。但截至目前我并未知悉有这样的平台(多处理器,但没有硬件原子操作支持)。
    > 实现 自旋锁 或者 互斥体 并不需要 CAS ,只需要比它弱得多的 [test-and-set]( en.wikipedia.org/wiki/Test-and-set)

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

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

    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 环境下可以这么做:
    > ```c
    > 指针 全局值;
    > 读对象() {
    > 指针 临时值 = 原子读取(全局值);
    > 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 。

    什么整数?
    h0099
        20
    h0099  
    OP
       2023-01-25 16:22:21 +08:00
    @n0099 https://github.com/n0099/TiebaMonitor/issues/32#issuecomment-1401625868

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

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

    github.com/n0099/TiebaMonitor/issues/32#issuecomment-1401199725 早已做出循环论证:
    > 因为 COMMIT 本就极少会产生错误( stackoverflow.com/questions/3960189/can-a-commit-statement-in-sql-ever-fail-how

    `如果有冲突的话再让 COMMIT 失败`中的冲突是指`INSERT`还是`SELECT`造成的?`INSERT`时 github.com/n0099/TiebaMonitor/issues/32#issuecomment-1401199725 早已道明:
    > 对于 mysql ,如果`线程 2INSERT 行 a`时数据库层发现这违反了`UNIQUE 约束`(因为`线程 1`已经这么做了),那么在此时就会返回错误并静默地`ROLLBACK`事务而不是等到`COMMIT`时再这么做

    而`SELECT`如何冲突?

    从实用角度讲数据库用户期望的是获取可靠的值,但却拿到了不可靠的值,那用户该如何进行后续的假设?
    并且理论上如果用户要的就是不可靠值那他应该可以通过往`SELECT`追加`FOR SHARE`来做到这一点:
    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 ) dev.mysql.com/doc/refman/8.0/en/innodb-consistent-read.html
    这也是其他使用 MVCC 的 RDBMS 实现 ANSI SQL 中要求的 4 个事务隔离级别之`REPEATABLE READ`的常规做法 http://mbukowicz.github.io/databases/2020/05/01/snapshot-isolation-in-postgresql.html www.postgresql.org/docs/current/transaction-iso.html

    ---
    > 那么它完全可以做成为每个`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 所采用的 en.wikipedia.org/wiki/Multiversion_concurrency_control (然而 mysql innodb 也是 MVCC ,很明显 MVCC 也只是一个抽象概念,而 RDBMS 们滥用他只是为了方便实现`REPEATABLE READ`)

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

    最容易遇到的还是死锁,其次是这种活锁,并且 mysql 无法主动检测出一直有多个事务在争夺同一资源(行集合)并介入其中(比如暂时把资源改成[serializability]( en.wikipedia.org/wiki/Serializability)的以便让事务们缓缓通过),除非阁下愿意像老 DBA 那样 247 高强度盯着 netdata 收集的 metrics 然后手动分析
    ![image]( user-images.githubusercontent.com/13030387/214255699-71e2b4a1-9b2f-47ac-b8d9-97b8d34e1dd9.png)
    h0099
        21
    h0099  
    OP
       2023-01-25 16:23:24 +08:00
    @yangbowen github.com/n0099/TiebaMonitor/issues/32#issuecomment-1401757287

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

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

    ---

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

    然而不论您称呼它 dirty read 还是 phantom read ,我都仍然不知道那都是什么意思。
    另外我觉得用时序图考虑并发和同步问题其实不太好,容易被误导的。而且较低的一致性约束下有可能发生根本就不能画成时序图的情形,比方说线程 1 的操作次序在线程 2 看来和在线程 3 看来可以是不一样的。
    h0099
        22
    h0099  
    OP
       2023-01-25 16:23:40 +08:00
    @yangbowen https://github.com/n0099/TiebaMonitor/issues/32#issuecomment-1401828929

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

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

    ---

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

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

    ---

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

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

    ---

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

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

    ---

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

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

    ---

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

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

    ---

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

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

    ---

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

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

    ---

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

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

    ---

    > 为什么这里会有 ABA

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

    > 什么整数?

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

    ---

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

    您好。原来您就是他们先前说的 西兔 。久仰大名。
    h0099
        23
    h0099  
    OP
       2023-01-26 09:40:17 +08:00
    @n0099 https://github.com/n0099/TiebaMonitor/issues/32#issuecomment-1403181038

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

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

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

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

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

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

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

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

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

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

    需要替换为`non-repeatable read`

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

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

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

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

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

    阁下是指在现代多核 cpu 中由于每个 core 都有着自己的 L1cache 所以跑在不同 core 上的指令有可能在读取同一个地址上不同的 L1cache 值(也就是 desync )吗?我的建议是滥用`volatile`
    h0099
        24
    h0099  
    OP
       2023-01-26 09:41:03 +08:00
    @n0099 https://github.com/n0099/TiebaMonitor/issues/32#issuecomment-1403243840

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

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

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

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

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

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

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

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

    与此同时截止 2023 年 1 月,`四叶沙其马里 1 群皇帝日冕开发者`伊欧神仍在步`奥利金德 rust 研究潮`高强度 star 相关 repo:
    ![image]( user-images.githubusercontent.com/13030387/214503869-fafca63d-3b7a-471e-85a9-0b36c0adacf4.png)

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

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

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

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

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

    这就是`INSERT IGNORE`

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    不开机翻我也慢慢读懂( 30\~100words/min ),而开机翻更快( 500\~700 字 /分钟)也方便大段引用复制粘贴
    h0099
        25
    h0099  
    OP
       2023-01-26 09:41:39 +08:00
    @yangbowen https://github.com/n0099/TiebaMonitor/issues/32#issuecomment-1403425152

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

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

    ---

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

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

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

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

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

    也就是跟 non-repeatable read 差不多,但是针对插入行而不是修改行。
    即便如此,即便在最高的隔离级别`SERIALIZED`当中,如果两个事务各自执行了一次`SELECT COUNT(*) FROM table`(都读到了一开始的`COUNT`),然后各自`INSERT`了一行,而且在`INSERT`的行的某一列记录了`INSERT`时的`COUNT`。那么,是否仍然可以这两个事务全部成功提交,而且得到了两个这个记录相同(都是“两边都没有`INSERT`之前的`COUNT`”)的行?
    显然如果所有访问全都带全局互斥锁的话这种情形是不可能的。但在没有互斥锁但有最高隔离级别的事务的情况下呢?
    h0099
        26
    h0099  
    OP
       2023-01-26 09:42:35 +08:00
    @yangbowen https://github.com/n0099/TiebaMonitor/issues/32#issuecomment-1403539880

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

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

    ---

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

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

    ---

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

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

    ---

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

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

    这个部分之前没看明白,现在才明白了。那我觉得如果你不想那么“补救”的话,那这个问题可以分成以下几个部分:
    - 你需要的约束是什么?就`消息相同的两行之间必须间隔有时间戳介于其间且消息不同的行`这种约束而言,它是“如果**存在**这样(时间戳介于其间且消息不同)的行的话那么满足约束”,显然它不可能用`UNIQUE`这种“如果**不存在**这样(对应列相同)的行的话那么满足约束”的约束实现。
    - 有没有办法让数据库引擎明白而且能够检查这样的约束?还是说只有做`SELECT`然后由调用者根据`SELECT`结果才能进行这一约束的检查?
    - 如果能的话,能不能让数据库引擎根据这一约束检查决定要不要让`INSERT`成功?而且,原子地——其它事务的`INSERT`可能破坏这一约束,所以约束检查和`INSERT`必须原子地发生。
    - 如果不能的话,能不能让数据库引擎保证:要么`影响这一约束的那部分 SELECT 结果在 SELECT 到 INSERT 成功期间没有变化`,要么`INSERT 不发生效果,或者说没有任何其它事务能够既看到这个 INSERT 的效果又成功提交`
    h0099
        27
    h0099  
    OP
       2023-01-26 09:42:50 +08:00
    @yangbowen https://github.com/n0099/TiebaMonitor/issues/32#issuecomment-1404405047

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

    类比数据库的事务隔离级别的话,应该是相当于最高的`SERIALIZED`吧?不会看到其它核心尚未成功提交的写,所以不 dirty read ;也不会看到其它核心在本事务进行期间成功提交的写(这种情况下对方的事务和本事务都会失败,不会成功提交),所以也不 non-repeatable-read 。但其实并不真的保证这些提交了或没提交的写一定不会被读到,而是说也许暂时读到了,但一定会事务失败,处理器会把架构状态回滚,程序无法基于“读到了但又被回滚了”的读取而影响行为。总之就是个乐观锁的`SERIALIZED`吧。
    h0099
        28
    h0099  
    OP
       2023-01-26 13:36:16 +08:00
    @yangbowen https://github.com/n0099/TiebaMonitor/issues/32#issuecomment-1404461843

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

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

    ---

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

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

    > The basic idea is the following: each object has an associated _consensus number_, which is the maximum number of processes for which the object can solve a simple consensus problem. In a system of _n_ or more concurrent processes, we show that it is impossible to construct a wait-free implementation of an object with consensus number _n_ from an object with a lower consensus number.
    h0099
        29
    h0099  
    OP
       2023-01-27 05:52:42 +08:00
    @n0099 https://github.com/n0099/TiebaMonitor/issues/32#issuecomment-1404661123

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

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

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

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

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

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

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

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


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

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

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

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

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

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

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

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



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


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

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

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

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

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

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

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

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

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

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

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

    这也就解释了上文中的
    > 在`READ UNCOMMITTED`和`REPEATABLE READ`事务隔离级别下不要使用朴素的`SELECT+INSERT/UPDATE`模式
    h0099
        30
    h0099  
    OP
       2023-01-29 02:16:10 +08:00
    @n0099 https://github.com/n0099/TiebaMonitor/issues/32#issuecomment-1404661123

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

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

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

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

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

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

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

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

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

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

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

    `COMMIT`几乎不会失败

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

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

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

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

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

    https://dev.mysql.com/doc/refman/8.0/en/innodb-locking.html#innodb-shared-exclusive-locks 进一步指出:
    > InnoDB supports multiple granularity locking which permits coexistence of row locks and table locks. For example, a statement such as [LOCK TABLES ... WRITE]( https://dev.mysql.com/doc/refman/8.0/en/lock-tables.html) takes an exclusive lock (an X lock) on the specified table. To make locking at multiple granularity levels practical, InnoDB uses [intention locks]( https://dev.mysql.com/doc/refman/8.0/en/glossary.html#glos_intention_lock). Intention locks are table-level locks that indicate which type of lock (shared or exclusive) a transaction requires later for a row in a table. There are two types of intention locks:
    > - An [intention shared lock]( https://dev.mysql.com/doc/refman/8.0/en/glossary.html#glos_intention_shared_lock) (IS) indicates that a transaction intends to set a shared lock on individual rows in a table.
    > - An [intention exclusive lock]( https://dev.mysql.com/doc/refman/8.0/en/glossary.html#glos_intention_exclusive_lock) (IX) indicates that a transaction intends to set an exclusive lock on individual rows in a table.
    > For example, [SELECT ... FOR SHARE]( https://dev.mysql.com/doc/refman/8.0/en/select.html) sets an IS lock, and [SELECT ... FOR UPDATE]( https://dev.mysql.com/doc/refman/8.0/en/select.html) sets an IX lock.
    > The intention locking protocol is as follows:
    > - Before a transaction can acquire a shared lock on a row in a table, it must first acquire an IS lock or stronger on the table.
    > - Before a transaction can acquire an exclusive lock on a row in a table, it must first acquire an IX lock on the table.
    alexfarm
        31
    alexfarm  
       93 天前
    大神,能麻烦移步看下我的问题吗,https://cn.v2ex.com/t/1008054
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   903 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 32ms · UTC 21:12 · PVG 05:12 · LAX 14:12 · JFK 17:12
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.