「《DDIA》读书笔记」分布式数据系统(上)

三、分布式数据系统

限于单机CPU的计算能力和内存大小,我们会希望将数据库分布在多台机器上

由此我们需要考虑:

  1. 可伸缩性:如果你的数据量、读取负载、写入负载超出单台机器的处理能力,可以将负载分散到多台计算机上。
  2. 容错/可用性:如果你的应用需要在单台机器(或多台机器,网络或整个数据中心)出现故障的情况下仍然能继续工作,则可使用多台机器,以提供冗余。一台故障时,另一台可以接管。
  3. 延迟:如果在世界各地都有用户,你也许会考虑在全球范围部署多个服务器,从而每个用户可以从地理上最近的数据中心获取服务,避免了等待网络数据包穿越半个世界。

共享架构:垂直扩展,扩展单机性能

无共享架构:水平扩展,任意多台的机器

数据分布在多个节点上有两种常见的方式:复制&分区

1. 复制

1.1. 领导者和追随者

复制分为3种:

  1. 同步
  2. 异步
  3. 半同步

图中展示了同步和异步两种复制模式

image-20211222204259801

同步复制的优点是,从库保证有与主库一致的最新数据副本。如果主库突然失效,我们可以确信这些数据仍然能在从库上上找到。缺点是,如果同步从库没有响应(比如它已经崩溃,或者出现网络故障,或其它任何原因),主库就无法处理写入操作。主库必须阻止所有写入,并等待同步副本再次可用。

1.1.1. 主库失效:故障切换

  1. 确认主库失效。有很多事情可能会出错:崩溃,停电,网络问题等等。没有万无一失的方法来检测出现了什么问题,所以大多数系统只是简单使用 超时(Timeout) :节点频繁地相互来回传递消息,并且如果一个节点在一段时间内(例如30秒)没有响应,就认为它挂了(因为计划内维护而故意关闭主库不算)。
  2. 选择一个新的主库。这可以通过选举过程(主库由剩余副本以多数选举产生)来完成,或者可以由之前选定的控制器节点(controller node) 来指定新的主库。主库的最佳人选通常是拥有旧主库最新数据副本的从库(最小化数据损失)。让所有的节点同意一个新的领导者,是一个共识问题。
  3. 重新配置系统以启用新的主库。客户端现在需要将它们的写请求发送给新主库(将在“请求路由”中讨论这个问题)。如果老领导回来,可能仍然认为自己是主库,没有意识到其他副本已经让它下台了。系统需要确保老领导认可新领导,成为一个从库。

1.1.2. 复制日志

  1. 基于语句的复制(我理解就是binlog)
  2. 传输预写式日志(WAL:MySQL的WAL,在Innodb中也就是redo log)对于覆写单个磁盘块的B树,每次修改都会先写入 预写式日志(Write Ahead Log, WAL),以便崩溃后索引可以恢复到一个一致的状态。
  3. 逻辑日志复制(不是很理解)
  4. 基于触发器的复制(不建议使用)

1.1.3. 复制延迟问题

  1. 读己之写:这是一个保证,如果用户重新加载页面,他们总会看到他们自己提交的任何更新。它不会对其他用户的写入做出承诺:其他用户的更新可能稍等才会看到。它保证用户自己的输入已被正确保存。
  2. 单调读:这是一个比 强一致性(strong consistency) 更弱,但比 最终一致性(eventual consistency) 更强的保证。当读取数据时,您可能会看到一个旧值;单调读取仅意味着如果一个用户顺序地进行多次读取,则他们不会看到时间后退,即,如果先前读取到较新的数据,后续读取不会得到更旧的数据。(可以考虑基于UID作哈希)
  3. 一致前缀读:这个保证说:如果一系列写入按某个顺序发生,那么任何人读取这些写入时,也会看见它们以同样的顺序出现。(有因果相关的写入到同一个分区)

1.2. 多主复制

image-20211222211619274

多主复制存在写入冲突,怎么解决?后续的文章会解答

1.3. 无主复制

1.3.1. 节点故障时写入数据库

image-20211222212434421

1.3.2. 读修复和反熵

上图的订正过程就是读修复,在读时会新值写入到旧值副本中

反熵:对账系统

1.3.3. 读写的法定人数

更一般地说,如果有n个副本,每个写入必须由w节点确认才能被认为是成功的,并且我们必须至少为每个读取查询r个节点。 (在我们的例子中,$n = 3,w = 2,r = 2$)。只要$w + r> n$,我们期望在读取时获得最新的值,因为r个读取中至少有一个节点是最新的。遵循这些r值,w值的读写称为法定人数(quorum)vii的读和写【44】。你可以认为,r和w是有效读写所需的最低票数。

image-20211222213009650

w+r>n的局限性在于:法定人数不一定必须是大多数,只是读写使用的节点交集至少需要包括一个节点。

允许通过参数w和r来调整读取陈旧值的概率,但把它们当成绝对的保证是不明智的。

1.3.4. 宽松的法定人数与数据回传

后者被认为是一个宽松的法定人数(sloppy quorum)【37】:写和读仍然需要w和r成功的响应,但这些响应可能来自不在指定的n个“主”节点中的其它节点。比方说,如果你把自己锁在房子外面,你可能会敲开邻居的门,问你是否可以暂时呆在沙发上。

一旦网络中断得到解决,代表另一个节点临时接受的一个节点的任何写入都被发送到适当的“主”节点。这就是所谓的数据回传(暗示移交)。 (一旦你再次找到你的房子的钥匙,你的邻居礼貌地要求你离开沙发回家。)

2. 数据分区

分区的目标是在多台机器上均匀分布数据和查询负载,避免出现热点(负载不成比例的节点)。

image-20211225175040414

2.1. key-value数据的分区

如果分区是不均匀,则会出现某些分区节点比其他分区承担更多的数据量或查询负载,我们称之为倾斜。数据倾斜会导致分区效率下降很多。在极端的情况下,所有的负载可能集中在一个分区上,这意味着10个节点9个空闲,系统的瓶颈在最繁忙的那个节点上。这种负载严重不成比例的分区即成为系统热点(hot spot)。

2.1.1. 基于关键字区间分区

一种分区的方法是为每个分区指定一块连续的键范围(从最小值到最大值),如纸质百科全书的卷(图6-2)。

image-20211225180037087但该方法如果按时间戳去进行区间的划分,还是会造成热点问题。

2.1.2. 基于关键字哈希值分区

image-20211225180327241

通过关键字哈希进行分区,我们会丧失良好的区间查询特性

如果想学习关于常见中间件的哈希一致性负载均衡,可以看一下另一篇关于分布式缓存的文章【我想自己做一个】分布式缓存GoCache

Cassandra采取了折衷的策略【11, 12, 13】。 Cassandra中的表可以使用由多个列组成的复合主键来声明。键中只有第一列会作为散列的依据,而其他列则被用作Casssandra的SSTables中排序数据的连接索引。尽管查询无法在复合主键的第一列中按范围扫表,但如果第一列已经指定了固定值,则可以对该键的其他列执行有效的范围扫描。

组合索引方法为一对多关系提供了一个优雅的数据模型。

2.2. 分区与二级索引

二级索引通常并不能唯一地标识记录,而是用来加速特定值的查询:查找用户123的所有操作,查找包含词语hogwash的所有文章,查找所有颜色为红色的车辆等等。

2.2.1. 基于文档分区的二级索引

image-20211225181556271

2.2.2. 基于词条的二级索引分区

image-20211225181626901

关键词分区的全局索引优于文档分区索引的地方点是它可以使读取更有效率:不需要分散/收集所有分区,客户端只需要向包含关键词的分区发出请求。全局索引的缺点在于写入速度较慢且较为复杂,因为写入单个文档现在可能会影响索引的多个分区(文档中的每个关键词可能位于不同的分区或者不同的节点上) 。

所以基于词条的二级索引更新需要分布式事务的支持,但又不是所有的数据库都支持分布式事务。

2.3. 分区再平衡

随着时间的推移,数据库可能总会出现某些变化:

  1. 查询吞吐量增加,所以您想要添加更多的CPU来处理负载。
  2. 数据集大小增加,所以您想添加更多的磁盘和RAM来存储它。
  3. 机器出现故障,其他机器需要接管故障机器的责任。

所有这些更改都需要数据和请求从一个节点移动到另一个节点。 将负载从集群中的一个节点向另一个节点移动的过程称为再平衡(rebalancing)。

无论使用哪种分区方案,再平衡通常都要满足一些最低要求:

  1. 再平衡之后,负载(数据存储,读取和写入请求)应该在集群中的节点之间公平地共享。
  2. 再平衡发生时,数据库应该继续接受读取和写入。
  3. 节点之间只移动必须的数据,以便快速再平衡,并减少网络和磁盘I/O负载。

2.3.1. 固定数量的分区

  1. 创建远超实际节点的分区数,然后为每个节点分配多个分区。
  2. 新增节点,该新节点可以从每个现有节点上匀走几个分区,直到分区再次平衡。分区在节点之间迁移,但分区总数量仍然不变,也不会改变关键词到分区的映射关系。这里唯一要调整的是分区与节点的对应关系。

image-20211225183650083

2.3.2. 动态分区

对于使用键范围分区的数据库(请参阅“根据键的范围分区”),具有固定边界的固定数量的分区将非常不便:如果出现边界错误,则可能会导致一个分区中的所有数据或者其他分区中的所有数据为空。手动重新配置分区边界将非常繁琐。

出于这个原因,按键的范围进行分区的数据库(如HBase和RethinkDB)会动态创建分区。当分区增长到超过配置的大小时(在HBase上,默认值是10GB),会被分成两个分区,每个分区约占一半的数据【26】。与之相反,如果大量数据被删除并且分区缩小到某个阈值以下,则可以将其与相邻分区合并。

动态分区的一个优点是分区数量适应总数据量。如果只有少量的数据,少量的分区就足够了,所以开销很小;如果有大量的数据,每个分区的大小被限制在一个可配置的最大值【23】。

2.3.3. 按节点比例分区

通过动态分区,分区的数量与数据集的大小成正比,因为拆分和合并过程将每个分区的大小保持在固定的最小值和最大值之间。另一方面,对于固定数量的分区,每个分区的大小与数据集的大小成正比。在这两种情况下,分区的数量都与节点的数量无关

Cassandra和Ketama使用的第三种方法是使分区数与节点数成正比——换句话说,每个节点具有固定数量的分区【23,27,28】。在这种情况下,每个分区的大小与数据集大小成比例地增长,而节点数量保持不变,但是当增加节点数时,分区将再次变小。由于较大的数据量通常需要较大数量的节点进行存储,因此这种方法也使每个分区的大小较为稳定。

2.4. 请求路由

现在我们已经将数据集分割到多个机器上运行的多个节点上。但是仍然存在一个悬而未决的问题:当客户想要发出请求时,如何知道要连接哪个节点?随着分区重新平衡,分区对节点的分配也发生变化。

  1. 允许客户联系任何节点(例如,通过循环策略的负载均衡(Round-Robin Load Balancer))。如果该节点恰巧拥有请求的分区,则它可以直接处理该请求;否则,它将请求转发到适当的节点,接收回复并传递给客户端。
  2. 首先将所有来自客户端的请求发送到路由层,它决定了应该处理请求的节点,并相应地转发。此路由层本身不处理任何请求;它仅负责分区的负载均衡。
  3. 要求客户端知道分区和节点的分配。在这种情况下,客户端可以直接连接到适当的节点,而不需要任何中介。

image-20211225205918746

3. 事务

这篇内容的主逻辑就是针对特定的问题给出相对通用的解决方案。

事务是应用程序将多个读写操作组合成一个逻辑单元的一种方式。

和事务打交道时间长了,你可能会觉得它显而易见。但我们不应将其视为理所当然。事务不是天然存在的;它们是为了简化应用编程模型而创建的。通过使用事务,应用程序可以自由地忽略某些潜在的错误情况和并发问题,因为数据库会替应用处理好这些。(我们称之为安全保证(safety guarantees))。

3.1. 深入理解事务

ACID:原子性(Atomicity)、一致性(Consistency)、隔离性(Isolation)、持久性(Durability)

3.1.1. 原子性

ACID原子性的定义特征是:能够在错误时中止事务,丢弃该事务进行的所有写入变更的能力。

3.1.2. 一致性

ACID一致性的概念是,对数据的一组特定约束必须始终成立。即不变量(invariants)。例如,在会计系统中,所有账户整体上必须借贷相抵。如果一个事务开始于一个满足这些不变量的有效数据库,且在事务处理期间的任何写入操作都保持这种有效性,那么可以确定,不变量总是满足的。

但是,一致性的这种概念取决于应用程序对不变量的理解,应用程序负责正确定义它的事务,并保持一致性。这并不是数据库可以保证的事情:如果你写入违反不变量的脏数据,数据库也无法阻止你。

原子性,隔离性和持久性是数据库的属性,而一致性(在ACID意义上)是应用程序的属性。

3.1.3. 隔离性

ACID意义上的隔离性意味着,同时执行的事务是相互隔离的:它们不能相互冒犯。传统的数据库教科书将隔离性形式化为可串行化(Serializability),这意味着每个事务可以假装它是唯一在整个数据库上运行的事务。数据库确保当多个事务被提交时,结果与它们串行运行(一个接一个)是一样的,尽管实际上它们可能是并发运行的。

3.1.4. 持久性

持久性 是一个承诺,即一旦事务成功完成,即使发生硬件故障或数据库崩溃,写入的任何数据也不会丢失。

3.2. 弱隔离级别

3.2.1. 读已提交的保证

最基本的事务隔离级别是读已提交(Read Committed),它提供了两个保证:

  1. 从数据库读时,只能看到已提交的数据(没有脏读(dirty reads))
  2. 写入数据库时,只会覆盖已经写入的数据(没有脏写(dirty writes)未提交的更新可能会在另一个事务出现)

image-20220102212557489

image-20220102210924303

脏写在MySQL的RUC,RC、RR隔离级别下都不会发生,因为在Alice事务update完之后,Bob事务再update会被阻塞,直到Alice事务提交。

3.2.2. 实现读已提交

那么如何实现读已提交呢?或者说通过什么方法避免脏读和脏写?

脏写——行锁

脏读——记录旧的版本值

数据库通过使用行锁(row-level lock) 来防止脏写:当事务想要修改特定对象(行或文档)时,它必须首先获得该对象的锁。然后必须持有该锁直到事务被提交或中止。一次只有一个事务可持有任何给定对象的锁;如果另一个事务要写入同一个对象,则必须等到第一个事务提交或中止后,才能获取该锁并继续。这种锁定是读已提交模式(或更强的隔离级别)的数据库自动完成的。

大多数数据库会使用图7-4的方式防止脏读:对于写入的每个对象,数据库都会记住旧的已提交值,和由当前持有写入锁的事务设置的新值。当事务正在进行时,任何其他读取对象的事务都会拿到旧值。 只有当新值提交后,事务才会切换到读取新值。

3.2.3. 快照级别隔离&可重复读

读已提交可能可以满足大部分的事务需求了,但还是会存在一定的问题,比如下图的这个问题:
image-20220102221333939

这个问题被称为不可重复读或读取偏差,大多数情况下是可以接受的,但在某些情况下又是不能接受的,比如数据的备份,在备份的过程中会频繁查询数据,如果这个时候接受了已提交的修改的数据(新数据),备份的数据可能会包含一部分旧,一部分新,从这样的备份中恢复数据,数据的准确性是无法保证的。

那么如何解决这个问题呢?使用MVCC

与读取提交的隔离类似,快照隔离的实现通常使用写锁来防止脏写(请参阅“读已提交”),这意味着进行写入的事务会阻止另一个事务修改同一个对象。但是读取不需要任何锁定。从性能的角度来看,快照隔离的一个关键原则是:读不阻塞写,写不阻塞读。

为了实现快照隔离,数据库使用了我们看到的用于防止图7-4中的脏读的机制的一般化。数据库必须可能保留一个对象的几个不同的提交版本,因为各种正在进行的事务可能需要看到数据库在不同的时间点的状态。因为它同时维护着单个对象的多个版本,所以这种技术被称为多版本并发控制(MVCC, multi-version concurrency control)。

如果一个数据库只需要提供读已提交的隔离级别,而不提供快照隔离,那么保留一个对象的两个版本就足够了:提交的版本和被覆盖但尚未提交的版本。支持快照隔离的存储引擎通常也使用MVCC来实现读已提交隔离级别。一种典型的方法是读已提交为每个查询使用单独的快照,而快照隔离对整个事务使用相同的快照

下面来看一下关于PostorgeSQL的MVCC实现快照隔离

当一个事务开始时,它被赋予一个唯一的,永远增长vii的事务ID(txid)。每当事务向数据库写入任何内容时,它所写入的数据都会被标记上写入者的事务ID。

表中的每一行都有一个 created_by 字段,其中包含将该行插入到表中的的事务ID。此外,每行都有一个 deleted_by 字段,最初是空的。如果某个事务删除了一行,那么该行实际上并未从数据库中删除,而是通过将 deleted_by 字段设置为请求删除的事务的ID来标记为删除。在稍后的时间,当确定没有事务可以再访问已删除的数据时,数据库中的垃圾收集过程会将所有带有删除标记的行移除,并释放其空间。

UPDATE 操作在内部翻译为 DELETE 和 INSERT 。例如,在图7-7中,事务13 从账户2 中扣除100美元,将余额从500美元改为400美元。实际上包含两条账户2 的记录:余额为 $500 的行被标记为被事务13删除,余额为 $400 的行由事务13创建。

image-20220102224245245

3.2.4. 索引和快照隔离

两种方式:

  1. 修改原来的B树,过滤掉不需要的事务id
  2. 每次写入事务,都追加一颗B树

3.2.5. 防止丢更新

到目前为止已经讨论的读已提交和快照隔离级别,主要保证了只读事务在并发写入时可以看到什么。却忽略了两个事务并发写入的问题——我们只讨论了脏写,一种特定类型的写-写冲突是可能出现的。

之前讨论的都是读-写问题,现在开始要写-写问题。

丢失更新:如果应用从数据库中读取一些值,修改它并写回修改的值(读取-修改-写入序列),则可能会发生丢失更新的问题。如果两个事务同时执行,则其中一个的修改可能会丢失,因为第二个写入的内容并没有包括第一个事务的修改

例子:在复杂值中进行本地修改,例如,将元素添加到JSON文档中的一个列表(需要解析文档,进行更改并写回修改的文档)

解决方案:

  1. 原子写

许多数据库提供了原子更新操作,从而消除了在应用程序代码中执行读取-修改-写入序列的需要。如果你的代码可以用这些操作来表达,那这通常是最好的解决方案。例如,下面的指令在大多数关系数据库中是并发安全的:

UPDATE counters SET value = value + 1 WHERE key = 'foo';

类似地,像MongoDB这样的文档数据库提供了对JSON文档的一部分进行本地修改的原子操作,Redis提供了修改数据结构(如优先级队列)的原子操作。

原子操作通常通过在读取对象时,获取其上的排它锁来实现。

  1. 显式锁定,精髓在于FOR UPDATE,告诉对数据库查询返回的所有行加锁
BEGIN TRANSACTION;
SELECT * FROM figures
WHERE name = 'robot' AND game_id = 222
FOR UPDATE;

-- 加锁了
UPDATE figures SET position = 'c4' WHERE id = 1234;
COMMIT;
  1. 自动检查丢失更新

原子操作和锁是通过强制读取-修改-写入序列按顺序发生,来防止丢失更新的方法。另一种方法是允许它们并行执行,如果事务管理器检测到丢失更新,则中止事务并强制它们重试其读取-修改-写入序列。

  1. CAS

在不提供事务的数据库中,有时会发现一种原子操作:比较并设置(CAS, Compare And Set)(先前在“单对象写入”中提到)。此操作的目的是为了避免丢失更新:只有当前值从上次读取时一直未改变,才允许更新发生。如果当前值与先前读取的值不匹配,则更新不起作用,且必须重试读取-修改-写入序列。

但是,如果数据库允许WHERE子句从旧快照中读取,则此语句可能无法防止丢失更新,因为即使发生了另一个并发写入,WHERE条件也可能为真。在依赖数据库的CAS操作前要检查其是否安全。

复制数据库时需要思考的「防止丢失的更新」

在复制数据库中(请参阅第五章),防止丢失的更新需要考虑另一个维度:由于在多个节点上存在数据副本,并且在不同节点上的数据可能被并发地修改,因此需要采取一些额外的步骤来防止丢失更新。

锁和CAS操作假定只有一个最新的数据副本。但是多主或无主复制的数据库通常允许多个写入并发执行,并异步复制到副本上,因此无法保证只有一个最新数据的副本。所以基于锁或CAS操作的技术不适用于这种情况。 (我们将在“线性一致性”中更详细地讨论这个问题。)

3.2.6. 写倾斜&幻读

前面的章节中,我们看到了脏写和丢失更新,当不同的事务并发地尝试写入相同的对象时,会出现这两种竞争条件。

现在想象一下,Alice和Bob是两位值班医生。两人都感到不适,所以他们都决定请假。不幸的是,他们恰好在同一时间点击按钮班。图7-8说明了接下来的事情。

image-20220102234005940

在两个事务中,应用首先检查是否有两个或以上的医生正在值班;如果是的话,它就假定一名医生可以安全地休班。由于数据库使用快照隔离,两次检查都返回 2 ,所以两个事务都进入下一个阶段。Alice更新自己的记录休班了,而Bob也做了一样的事情。两个事务都成功提交了,现在没有医生值班了。违反了至少有一名医生在值班的要求。

(写入偏差的其他例子)

防止双重开支

允许用户花钱或积分的服务,需要检查用户的支付数额不超过其余额。可以通过在用户的帐户中插入一个试探性的消费项目来实现这一点,列出帐户中的所有项目,并检查总和是否为正值。有了写入偏差,可能会发生两个支出项目同时插入,一起导致余额变为负值,但这两个事务都不会注意到另一个。

可以将写入偏差视为丢失更新问题的一般化。如果两个事务读取相同的对象,然后更新其中一些对象(不同的事务可能更新不同的对象),则可能发生写入偏差。在多个事务更新同一个对象的特殊情况下,就会发生脏写或丢失更新(取决于时序)。

解决方案:

  1. UPDTATE的情况:显式锁定,FOR UPDATE
  2. INSERT的情况:实体化冲突,在数据库中预先插入一条数据,使得查询结果可以加锁
  3. 最终大招:串行化!

一个事务中的写入改变另一个事务的搜索查询的结果,被称为幻读。快照隔离避免了只读查询中幻读,但是在像我们讨论的例子那样的读写事务中,幻读会导致特别棘手的写入偏差情况。

3.3. 串行化

读已提交和快照隔离级别会阻止某些竞争条件,但不会阻止另一些。我们遇到了一些特别棘手的例子,写入偏差和幻读。

基于这样的情况,研究人员给出的解决方案是「串行化」,大多数使用「串行化」的数据库都使用了以下三种技术之一

  1. 串行顺序执行事务
  2. 二阶段锁定(2PL)
  3. 乐观并发控制技术,比如可串行化快照隔离(SSI)

3.3.1. 二阶段锁定

两阶段锁定类似,但是锁的要求更强得多。只要没有写入,就允许多个事务同时读取同一个对象。但对象只要有写入(修改或删除),就需要独占访问(exclusive access) 权限:

  1. 如果事务A读取了一个对象,并且事务B想要写入该对象,那么B必须等到A提交或中止才能继续。 (这确保B不能在A底下意外地改变对象。)
  2. 如果事务A写入了一个对象,并且事务B想要读取该对象,则B必须等到A提交或中止才能继续。 (像图7-1那样读取旧版本的对象在2PL下是不可接受的。)

在2PL中,写入不仅会阻塞其他写入,也会阻塞读,反之亦然。快照隔离使得读不阻塞写,写也不阻塞读,这是2PL和快照隔离之间的关键区别。另一方面,因为2PL提供了可串行化的性质,它可以防止早先讨论的所有竞争条件,包括丢失更新和写入偏差。

如何使用2PL实现串行化隔离级别?

读与写的阻塞是通过为数据库中每个对象添加锁来实现的。锁可以处于共享模式(shared mode) 或独占模式(exclusive mode)。锁使用如下:

  • 若事务要读取对象,则须先以共享模式获取锁。允许多个事务同时持有共享锁。但如果另一个事务已经在对象上持有排它锁,则这些事务必须等待。

  • 若事务要写入一个对象,它必须首先以独占模式获取该锁。没有其他事务可以同时持有锁(无论是共享模式还是独占模式),所以如果对象上存在任何锁,该事务必须等待。

  • 如果事务先读取再写入对象,则它可能会将其共享锁升级为独占锁。升级锁的工作与直接获得排他锁相同。

  • 事务获得锁之后,必须继续持有锁直到事务结束(提交或中止)。这就是“两阶段”这个名字的来源:第一阶段(当事务正在执行时)获取锁,第二阶段(在事务结束时)释放所有的锁。

虽然2PL可以实现串行化隔离级别,但性能不佳,相当一部分时间用来抢占和释放锁,而且锁的频繁的使用可能引起死锁,使得事务不得不中止并重试。

3.3.2. 谓词锁

在前面的讨论中我们并没有解决幻读的问题,这里提出了一种锁——谓词锁。

谓词锁甚至适用于数据库中尚不存在,但将来可能会添加的对象(幻象)。如果两阶段锁定包含谓词锁,则数据库将阻止所有形式的写入偏差和其他竞争条件,因此其隔离实现了可串行化。

3.3.3. 索引区间锁

不幸的是谓词锁性能不佳:如果活跃事务持有很多锁,检查匹配的锁会非常耗时。因此,大多数使用2PL的数据库实际上实现了索引范围锁(也称为间隙锁(next-key locking)),这是一个简化的近似版谓词锁。

通过使谓词匹配到一个更大的集合来简化谓词锁是安全的。例如,如果你有在中午和下午1点之间预订123号房间的谓词锁,则锁定123号房间的所有时间段,或者锁定12:00~13:00时间段的所有房间(不只是123号房间)是一个安全的近似,因为任何满足原始谓词的写入也一定会满足这种更松散的近似。

索引范围锁并不像谓词锁那样精确(它们可能会锁定更大范围的对象,而不是维持可串行化所必需的范围),但是由于它们的开销较低,所以是一个很好的折衷。

3.3.4. SSI

顾名思义,SSI基于快照隔离——也就是说,事务中的所有读取都是来自数据库的一致性快照(请参阅“快照隔离和可重复读取”)。与早期的乐观并发控制技术相比这是主要的区别。在快照隔离的基础上,SSI添加了一种算法来检测写入之间的串行化冲突,并确定要中止哪些事务。

数据库如何知道查询结果是否可能已经改变?有两种情况需要考虑:

  1. 检测对旧MVCC对象版本的读取(读之前存在未提交的写入)
  2. 检测影响先前读取的写入(读之后发生写入)

image-20220103135641061

为什么要选择在事务43提交时再中止呢?不能提前嘛?

不能,因为我们也不知道食物43是否只是只读事务。

image-20220103141313747

事务43和事务42会相互通知对方先前的读已经过期。虽然事务43的修改的确影响到了事务42,但事务43当时并未提交(修改未生效),而事务42首先尝试提交,所以可以成功;随后当事务43试图提交时,来自42的冲突写已经提交生效,事务43不得不中止。

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×