使用时间戳的并发控制

​专栏内容：

  • 手写数据库toadb
    本专栏主要介绍如何从零开发，开发的步骤，以及开发过程中的涉及的原理，遇到的问题等，让大家能跟上并且可以一起开发，让每个需要的人成为参与者。
    本专栏会定期更新，对应的代码也会定期更新，每个阶段的代码会打上tag，方便阶段学习。

​开源贡献：

  • toadb开源库

个人主页：我的主页
管理社区：开源数据库
座右铭：天行健，君子以自强不息；地势坤，君子以厚德载物.

文章目录

  • 使用时间戳的并发控制
  • 前言
  • 概述
  • 时间戳介绍
    • 记录时间戳的方法
    • 事务提交的记录
  • 可以解决的问题
    • 过晚的读
    • 过晚的写
    • 脏数据的问题
    • mysql中的表现
  • 基于时间戳调度的规则
    • 调度器选择
    • 读写请求的处理
  • 多版本时间戳
  • 时间戳与封锁
  • 总结
  • 结尾

前言

随着信息技术的飞速发展，数据已经渗透到各个领域，成为现代社会最重要的资产之一。在这个大数据时代，数据库理论在数据管理、存储和处理中发挥着至关重要的作用。然而，很多读者可能对数据库理论感到困惑，不知道如何选择合适的数据库，如何设计有效的数据库结构，以及如何处理和管理大量的数据。因此，本专栏旨在为读者提供一套全面、深入的数据库理论指南，帮助他们更好地理解和应用数据库技术。

数据库理论是研究如何有效地管理、存储和检索数据的学科。在现代信息化社会中，数据量呈指数级增长，如何高效地处理和管理这些数据成为一个重要的问题。同时，随着云计算、物联网、大数据等新兴技术的不断发展，数据库理论的重要性日益凸显。

因此，本专栏的分享希望可以提高大家对数据库理论的认识和理解，对于感兴趣的朋友带来帮助。

概述

在数据库中如何保证并发事务时，数据的一致性，也就是可串行化，会有采用调度器来进行协调各事务中动作的顺序，以衣是否可以执行等。调度器采用的模型主要有几种：

  • 基于封锁的调度模型
  • 基于时间戳的调度模型
  • 基于有效性确认的调度模型

前几篇博文中分享了基于封锁的调度模型，本文主要介绍基于时间戳的调度模型，主要从时间戳的概念，可以保证的行为和存在的问题，调度规则，以及多版本的优化，与封锁模型的联合使用等方面进行介绍。

时间戳介绍

也就是记录上次读和写每个数据库元素的事务时间点，同时每个事务也有一个时间戳，记录它的开始时间点。

当有事务要请求该数据库元素时，比较这两个时间，根据事务的时间戳来调度，来确保串行调度。

记录时间戳的方法

  • 理论上当多个事务开始的时间间隔大于时间最小计数时，使用时间来记录是可以达到目标的，但是往往时间的精度不足以记录多个同时开始的事务。

  • 调度器维护一个计时器。每当一个事务开始时，计数器就加1，而新值成为该事务的时间戳。这种方法与时间无关，但是它们具有时间的特性，单调递增，不会重复，总是保证晚的事务比开始早的事务具有更高的时间戳；

事务提交的记录

当一个事务T读到另一事务U所写的数据，这一行为也是符合串行化规则，但是事务U最后中止了，并没有提交，这样事务T读到的是脏数据，这一问题肯定会导致数据库状态变得不一致，这是任何调度器都要防止的脏读。

除了两个事务和数据库元素上的时间戳外，还需要记录一个事务的提交状态位，当事务没有提交时，调度器也需要阻止其它事务的访问请求。

可以解决的问题

假如事务在开始的那一时刻就立即执行结束，那也就不会发生非可串行化的问题。往往事务中的各个动作都会持续一段时间，这就会过晚读和过晚写的问题发生，而当事务中止时，读取的此事务写的数据，就会发生脏读的情况。

过晚的读

  • 问题描述
    事务执行的时间轴是这样的

如图所示，事务T的读在事务U的写之后，而事务U的开始时间晚于事务T，这就导致事务T读到的数据不一致。

  • 解决方法
    当事务T的进行读请求时，发现当前数据元素上的时间戳晚于自己的事务开始时间戳时，事务T应该是需要中止，它什么都不能做了。

过晚的写

  • 问题描述
    事务执行的时间轴是这样的

如图所示，事务U开始时间晚于事务T，而事务U的读操作早于事务T，本应该事务U可以读到T写入的值，但是T的写入更晚。

  • 解决方法
    事务T因为时间戳晚于数据元素上的时间戳，也就是事务U访问的时间戳，应该中止事务T，让事务U可以读取正确的数据。

脏数据的问题

事务提交标志的设置，就是用来解决这个问题的，先来看两个问题。

  • 问题一
    |事务U | 事务T|
    |:–|:–|
    |begin; ||
    |write(X) | |
    || begin;|
    ||read(X)|
    |abort||
    ||commit;|

  • 问题二
    |事务U | 事务T|
    |:–|:–|
    |begin; ||
    |write(X) | |
    || begin;|
    ||write(X)|
    ||commit;|
    |abort||

对于问题一，因为事务U在事务T之前启动，并写入X，所有事务T读取X是符合上面时间戳的规则，但是当事务U最终中止时，事务T读取的X就是脏数据，是数据库中本不存在的数据；

对于问题二，有趣的事情来了，此时事务T提交后，其实它是基于事务U的，比如X=1，事务U写入后X=2, 事务T写入后X=3，那么提交成功后X=3；而事务U回滚后，好像什么都不需要做，还是事务U回滚为X=1，事务T重新再做一遍呢？

  • 解决方法
    对于问题一的此类问题，请求读操作时，需要看当前数据元素是否已经提交，如果没有提交，需要中止当前请求，或推迟到该数据库元素提交之后再处理。

而对于问题二的此类问题，写操作请求时，也同样需要判断当前数据元素是否已经提交，如果没有提交，需要中止当前请求，或推迟到该数据库元素提交之后再处理。 当然，更晚的写也可以什么都不做，这被称为Thomas写法则，最后事务U中止后，它要回退它的写入和数据库元素上的时间戳，但是事务T的写入被跳过了，同时也提交完成了，此时想恢复事务T的操作已经不可能了。

mysql中的表现

mysql> show variables like 'transaction%';+----------------------------------+-----------------+| Variable_name| Value |+----------------------------------+-----------------+| transaction_alloc_block_size | 8192|| transaction_allow_batching | OFF || transaction_isolation| REPEATABLE-READ || transaction_prealloc_size| 4096|| transaction_read_only| OFF || transaction_write_set_extraction | XXHASH64|+----------------------------------+-----------------+6 rows in set (0.00 sec)mysql> begin;Query OK, 0 rows affected (0.00 sec)mysql> select * from test_concurrent;+------+| i|+------+|5 |+------+1 row in set (0.00 sec)-- 这此时另外启动一个事务，将i修改为6,并提交事务mysql> select * from test_concurrent;+------+| i|+------+|5 |+------+1 row in set (0.00 sec)mysql> update test_concurrent set i = 3 where i = 5;Query OK, 0 rows affected (0.00 sec)Rows matched: 0Changed: 0Warnings: 0mysql> commit;Query OK, 0 rows affected (0.00 sec)mysql> select * from test_concurrent;+------+| i|+------+|6 |+------+1 row in set (0.00 sec)

可以看到mysql中，当前事务可以看到i=5，但确修改不成功，返回0 rows被updated，这就是一个很迷惑的现象。

基于时间戳调度的规则

经过上面问题的分析，现在我们概括基于时间戳调度的规则。

调度器选择

对于来自事务的读写操作请求，调度器有几种选择：

  • 同意该请求
  • 推迟请求
  • 中止请求事务

读写请求的处理

调度器收到读写操作请求，

  1. 收到读操作请求时，检查当前数据库元素上次操作事务的提交状态，
  • 如果已经提交，则再检查时间戳的先后顺序，如果请求事务的时间戳大于当前数据元素的时间戳，则可以同意请求，并将时间戳更新为当前事务；如果事务时间戳小于当前数据元素的时间戳，则需要中止；
  • 如果尚未提交，则请求事务需要推迟；
  1. 当收到写操作请求时，先检查当前事务与数据库元素上的时间戳，
  • 如果请求事务的时间戳大于当前数据元素的时间戳，再检查数据元素上次操作的事务是否提交，如果已经提交，则同意本次写请求；如果未提交，则需要推迟本次请求；
  • 如果事务时间戳小于当前数据元素的时间戳，本次请求事务需要中止；

  1. 当收到事务提交请求时，更新数据元素上的提交状态；同时唤醒等待的事务请求；

  2. 当收到事务T中止请求时，那么回退事务T对应的所有操作数据；等待的事务需要重新发起读或写请求，因为需要检查事务T的写被中止后是否合法。

多版本时间戳

基于时间戳的并发控制调度器，如上面介绍的，会存在读写之间冲突，所以在这个基础上进行了一个重要的演进，就是同时保留数据库元素的多个带不同时间戳的版本，使得读写可以同时进行。

多版本时间戳的流程与上面流程类似：

  1. 当收到写操作请求时WT(X)，如果请求被同意，那么X的一个新版本Xi被创建，它的时间戳为Ti(X);
  2. 此时收到一个读操作请求时RU(X)时，最新版本检查不通过时，查找时间戳小于事务U的版本X；也是就WT(X)执行前的版本，就是当前可读的版本，同意RU(X)在版本X上的读请求；
  3. 数据元素的时间戳与对应的版本有关；
  4. 当然再有事务的写请求来时，还是需要在最后的版本Xi上处理；
  5. 旧版本的清理，当X的某个版本上的时间戳小于任何当前活跃事务的时间戳时，就可以清理掉它了。

多版本时间戳的方式，解决了读写并发时的性能问题。

时间戳与封锁

在大多数只读事务或者并发读写同一元素的情况不频繁时，基于时间戳的调度比较有优势；

而当读写并发比较高，而且对同一数据库元素竞争较大时，封锁调度反而比较优，因为此种情况下基于时间戳的调度，需要进行频繁的回退操作。

在现代商用数据库中，会将事务分为只读事务和读写事务，在只读事务时，只使用时间戳的方式，而只读事务时采用两阶段锁的方式。

总结

基于时间戳的调度模型可以说是一种乐观的模型，它假设没有非可串行化行为发生，并且只有在违例发生时才会进行修正或者中止。与此相反，封锁的调度模型是假设非可串行化行为一定会发生，那么提前进行预防，并且推迟可能发生的事务，但不中止它们，它是一种悲观模型。

这两种模型，如果对于大量只读操作时，乐观型好于悲观型调度器。

结尾

非常感谢大家的支持，在浏览的同时别忘了留下您宝贵的评论，如果觉得值得鼓励，请点赞，收藏，我会更加努力！

作者邮箱：study@senllang.onaliyun.com
如有错误或者疏漏欢迎指出，互相学习。