可重复读_DDIA系统设计读笔记（第六七章切分与事务）

1、数据切分

上一章利用数据复制的方式，解决了数据的稳定性问题，同时读写分离提升系统的读写性能，并考虑了全球分布时用户就近访问的场景。 但是当单张表的数据越来越多时，例如达到100G时，其读性能会明显下降。此时，就需要对数据进行切分，将一张臃肿的大表拆分为多个小表，从而提升数据库的操作性能。 数据切分包括两类：垂直切分和水平切分。就像切蛋糕一样，可以竖着切，也可以横着切。

1.1 垂直切分

本质是做归类。包含垂直分库和垂直分表两种。

垂直分库基于系统功能，将某个功能涉及的表放在同一个库中，不同功能的表放在不同的库。但这是比较粗的，垂直分表要更细致一些。当某个表字段较多时，可以新建一张扩展表，将不经常用或字段长度较大的字段拆分出去到扩展表中，从而缩小原表的体积。

优点：

1. 垂直分库：不同业务功能解耦，可各自独立维护

• 垂直切分：MySQL底层是通过数据页存储的，一条记录占用空间过大会导致跨页，造成额外的性能开销。大表拆小表，每行的体积变小了，能避免数据跨页的问题。同时内存中也可以塞入更多的记录行，命中率更高，减少磁盘IO。以上都提升了数据库性能。

缺点：

1. 写负担增加：切分之前，只需在一张表上写入，拆分后，由于每张表只记录部分属性，因此会对多个表进行写入。

2. 本质上没有解决单表数据量过大的问题

1.2 水平切分

数据量的增长主要是数据行的大量增长，只有水平切分能从根本上解决问题。

例如，一张原表A，分成三张子表A1，A2，A3，这三张子表具有与A相同的列，只不过行数为原表的三分之一。这三张表一般分散到三台机器上，从而在整体上具有更多的计算资源，且将来也非常易于扩展。采用水平切分的数据库也称为分片库，三张子表分布在三个分片上。

优点：

• 不存在单库数据量过大、高并发的性能瓶颈，提升系统稳定性和负载能力

• 应用端改造较小，不需要拆分业务模块

缺点：

• 跨分片的事务一致性难以保证：例如用户下单后发生了退款，则退款的订单生成时，需要在原支付单上记上退款金额。如果这两条记录不在一个分片内，事务性很难保证。例如退款订单写入失败，原支付单的写入也必须一同回滚。

• Join问题：例如有user_id和user_name两张表，分片1上user_id对应的user_name值存在分片2的user_name表里，此时在分片1内对两张表进行join是无法得到预期结果的。

1.3. 切分方法

切分包含两次映射，一次是关键字到逻辑分片的映射，一次是逻辑分片到物理节点的映射。下面讨论的是关键字到逻辑分片的映射，集群中逻辑分片到物理节点的映射一般由Zookeeper这种工具来维护。

1. 基于关键字区间划分

例如按照用户名划分，A-G开头的放在第一个分片，H-N的放在第二个分片，以此类推。当然这个范围的划分并不一定是线性的，因为数据本身可能就不是平均的。例如某个区间的分布比较多，可以适当缩小，使得不同分片的数据规模趋于平均。

优点：

• 单表大小可控

• 天然便于水平扩展。后期如果想对整个分片集群扩容时，只需要添加节点即可，无需对其他分片的数据进行迁移

• 天然支持区间查询。使用分片字段进行范围查找时，可快速定位到所在分片

缺点：

• 存在热点问题。例如按时间字段分片，有些分片存储最近时间段内的数据，可能会被频繁的读写，而有些分片存储的历史数据，则很少被查询。

热点问题解决方案：

多个列组成关键字，降低关键字称为热点的概率。或者，如果关键字成为热点，则在关键字开头或结尾增加一个随机数，强制分配到不同分区。但这样需要额外记录哪些关键字进行来特殊处理，否则查询时就会失败。

2. 基于关键字哈希划分

哈希的目的，是将原本并不均匀的数据打散，从而变动均匀，避免出现热点问题，造成资源浪费。例如，对关键字进行取模。

优点：

• 数据分片相对比较均匀，不容易出现热点和并发访问的瓶颈

缺点：

• 后期分片集群扩容时，需要迁移旧的数据(使用一致性hash算法能较好的避免这个问题)

• 查询时必须先计算好数据所在的分片，否则数据库只能每个分片依次扫描。自然，也就更不支持区间查询。

一个折中方案是：由多个列组成复合主键，复合主键只有第一部分可以用于哈希分区，而其他列则用作组合索引来对分片内数据进行排序。当进行区间查询时，如果为第一列指定好固定值，可以对其他列执行高效的区间查询。

1.4 切分的弊端

1. 事务一致性问题 提交事务时需要协调多个节点，推后了提交事务的时间点，延长了事务的执行时间。导致事务在访问共享资源时发生冲突或死锁的概率增高。随着数据库节点的增多，这种趋势会越来越严重，从而成为系统在数据库层面上水平扩展的枷锁。 对于那些性能要求很高，但对一致性要求不高的系统，往往不苛求系统的实时一致性，只要在允许的时间段内达到最终一致性即可，可采用事务补偿的方式。与事务在执行中发生错误后立即回滚的方式不同，事务补偿是一种事后检查补救的措施，一些常见的实现方法有：对数据进行比对检查，基于日志进行对比，定期同标准数据来源进行同步等等。事务补偿还要结合业务系统来考虑。 2. 跨库Join 切分之后，数据可能分布在不同的节点上，此时join会比较麻烦，最好的解决方式是避免join。 1. 建立配置表或冗余字段，资源利用率降低 系统中所有模块都可能依赖的一些表，为了避免跨库join查询，可以将这类表在每个数据库中都保存一份。这些数据通常很少会进行修改，所以也不担心一致性的问题。 冗余字段是指，对于需要join才能拿到的数据，在写入时就一并写入。如记录user_id的表，写入user_id时，将user_name也一并写入。 2. 应用层多次查询自行组装，应用层逻辑复杂 在系统层面，分两次查询，第一次查询的结果集中找出关联数据id，然后根据id发起第二次请求得到关联数据。最后将获得到的数据进行字段拼装。 3. 维护局部关联，维护成本高 将可能需要关联的数据，维护在一个分片上，避免跨分片。 3. 跨库分页、聚合数据 跨节点多库进行查询时，会出现limit分页、order by排序等问题。分页需要按照指定字段进行排序，当排序字段就是分片字段时，通过分片规则就比较容易定位到指定的分片；当排序字段非分片字段时，就变得比较复杂了。需要先在不同的分片节点中将数据进行排序并返回，然后将不同分片返回的结果集进行汇总和再次排序，最终返回给用户。 在使用Max、Min、Sum、Count之类的函数进行计算的时候，也需要先在每个分片上执行相应的函数，然后将各个分片的结果集进行汇总和再次计算，最终将结果返回 4. 全局主键ID要避重复 由于数据分布在不用的分片上，因此某个分区数据库自生成的ID无法保证全局唯一。一般的做法是，建立一个全局主键id表，所有的id先利用该表自增生成。 但这又存在单点故障问题，为此，可以用多台机器来交替生成。例如，由两个数据库服务器生成ID，设置不同的auto_increment值。第一台id的起始值为1，每次步长增长2，另一台的id起始值为2，每次步长增长也是2。结果第一台生成的ID都是奇数(1, 3, 5, 7 ...)，第二台生成的ID都是偶数(2, 4, 6, 8 ...)。 同时，发号器一次可以批量生成多个id号缓存起来，用完了基于数据库再生成一批，降低数据库压力。

1.5 小结

2、事务

2.1 ACID

客户端在同一事务中包含多个写操作时，数据库所提供的保证

原子性(A)：这一系列写操作保证要么全部成功，要么全部失败。不存在部分成功部分失败的情况。

一致性(C)：如转账时，一定是一个人账户余额减少，一个人账户余额增加。这个性质更多的应由应用层来保证，其实不属于数据库性质

隔离性(I)：并发进行多个事务时不应该互相干扰。例如某个事务多次写入，另一个事务观察到的应该是其全部完成或者一个都没完成的结果，而不应该看到中间的部分结果。

持久性(C)：一旦提交成功，即使存在硬件故障或数据库崩溃，事务写入的任何数据都不会丢失。这是一个理想化的属性保证。

这四个性质中，最重要的是AI，即原子性和隔离性。

2.2 隔离

如果两个事务操作的是不同的数据，则可以安全的并发执行。只有当某个事务修改数据而另外一个事务同时要读取该数据，或者两个事务同时修改相同数据时，才会出现并发问题。出现并发，才需要考虑隔离。

隔离级别的选取主要需要考虑解决如下问题：

1. 脏读：某个事务只完成部分数据的写入，但事务尚未提交，此时另外一个事务可以看到未提交数据

2. 脏写：两个事务同时尝试更新相同的对象，如果先前的写入只是尚未提交的事务的一部分，且后面事务的写入会覆盖较早的写入

3. 不可重复读：同一个事务内，两次相同的查询，查询的结果行具有不同的值

4. 幻读：同一个事务内，两次相同的查询，查询出不同的结果行

5. 更新丢失：对于读取-修改-写入模式的事务，多个事务并发执行时会造成写入不符合预期

6. 写倾斜：两个事务各自更新不同的对象，对象之间存在约束关系，更新后对象之间的约束关系被打破

这里暂时列出，具体含义会在下面的例子中解释。

一般的隔离级别分为四种：未提交读，提交读，可重复读，串行化。其隔离性依次增加，并发性能依次降低。

1. 未提交读：read uncommitted

原本A事务想读50的余额，在读的过程中因为B的修改，造成读到了中间结果120，该现象称为脏读。

同样，事务B中修改为120尚未提交，此时事务A将余额更新为60，造成脏写。

2. 提交读(RC：read commit)

定义：

读数据库时，只能看到已经成功提交的数据(防止“脏读”)

写数据库时，只会覆盖已经成功提交的数据(防止“脏写”)

用途：

应用最广，可以解决脏读脏写问题，但是不能消除不可重复读和幻读

实现：

通过行锁来防止脏写。当事务想修改某个对象时，必须先获得该对象的锁，并一直持有直到事务结束。因此，在某个时刻，只有一个事务可以拿到该对象的锁。

如何防止脏读？一个思路是读取时也必须拿到锁才能读，即读锁。但运行时间较长的写事务，会阻塞大量的只读事务。因此，对每个待更新的对象，数据库都会维护其旧值和当前持有锁的事务将要设置的新值两个版本。在事务提交之前，所有其他的读操作都读取旧值；仅当写事务提交之后，才会切换到读取新值。

局限：

存在幻读、不可重复读。

下图中两个事务同时进行。事务1中有三次查询，第二次查询相比第一次增加了一行，这种现象为幻读。第三次查询相比第二次，结果行没有改变，但id=2的值由200变为300，这种现象即不可重复读。

3. 可重复读(RR：repeatable read)

定义：

事务读到的数据行的值，在事务期间不会因为其他事务的修改而改变。可重复读对长时间运行的数据备份和数据分析非常有用。

可重复读一般基于快照来实现，因此又有快照隔离的说法。下图是另一个可重复读的例子，事务读的结果只是不受其他事务的影响，本身事务内的修改还是会反映在读取结果上。

实现：

由于多个正在进行的事务可能会在不同的时间点查看数据库状态，所以数据库保留了对象多个不同的提交版本，并基于版本来控制事务读取时的可见性。该技术称为多版本并发控制(MVCC)

MVCC在读取数据项时，不加锁；在更新数据项时，直到最后要提交时，才会加锁。它更新数据前，会将数据拷贝一份，进行一系列修改，并且拷贝的同时，会记录当前的版本号(时间戳)。当修改完毕，即将提交时，再检查此时的版本号是否与刚才记录的一致，如果不一致，则表明数据项被其他事务修改，当前事务的修改被取消。否则，正式提交修改，并增加版本号。

局限：

可重复读只解决了不可重复读的问题，更新丢失，写偏差，幻读等问题依然存在。

如下图所示，两个事务进行计数器+1的操作，预期计数器进过两次应由42增加为44，但最后的结果是43。原因在于第二次计数时，读到的仍然是42。对用户来说，明明执行了两次计数，但从结果上看只计数了一次，好像有一次计数操作丢失了。

对于读取-修改-写入模式的事务，多个事务并发执行时会造成写入覆盖或丢失，这种异常称为更新丢失。

有时候，即使两个事务更新不同的数据源，也会出现异常。

例如，医院通常会同时要求几位医生值班，医生可以请假，但至少有一位医生在待命。假设Alice和Bob是两位值班医生，在同一时刻两人同时请假。由于数据库使用快照隔离，两次检查都返回当前值班人数为2 ，所以两个事务都进入下一个阶段。Alice更新自己的记录休假了，Bob亦然。两个事务都成功提交。最后没有医生值班，违反了至少有一名医生在值班的要求。

这种由于不同事务对不同数据对象的并发写入造成的异常，称为写偏差。

同时，对于基于条件查询的事务，其结果会受其他事务写入的影响，即幻读

4. 可串行化

保证即使事务并行执行，最终的结果与挨个执行的结果一样。下面介绍可串行化的三种实现方式，用以解决更新丢失，写偏差，幻读的问题。

1. 串行执行

在单个线程上按顺序一次执行，一次只执行一个事务。其可行基于两点：

• RAM足够便宜：可以将数据直接放在内存，无需从磁盘读写，读取速度快

• 写请求通常非常快，读请求可以基于快照

这两点保证了单线程的时间开销其实并不大，不会因为串行而过度等待，并且所有的锁开销也都被节省下来。当然，瓶颈也很明显，单线程的吞吐量仅限于单个CPU核的吞吐量。即使增加再多机器，性能也无法提升，即串行执行失去了拓展性。

因此，只有在特定约束条件下，真的串行执行事务才是可行的：

• 每个事务都必须小而快，只要有一个缓慢的事务，就会拖慢所有事务处理。

• 仅限于活跃数据集可以放入内存的情况。很少访问的数据可能会被移动到磁盘，但如果需要在单线程执行的事务中访问，系统就会变得非常慢。

• 写入吞吐量必须低到能在单个CPU核上处理，如若不然，事务需要能划分至单个分区，且不需要跨分区协调。

• 跨分区事务是可能的，但是它们的使用程度有很大的限制。

2. 两阶段锁(2PL：2 phase locking)

在解释两阶段锁协议之前，先说说一次性锁协议。

一次性锁协议，事务开始时，即一次性申请所有的锁，之后不会再申请任何锁，如果其中某个锁不可用，则整个申请就不成功，事务就不会执行，在事务尾端，一次性释放所有的锁。一次性锁协议不会产生死锁的问题，但事务的并发度不高。

串行执行，其实就是一次性锁协议的一个实现。

两阶段锁协议，整个事务分为两个阶段，前一个阶段为加锁(扩张段)，后一个阶段为解锁(收缩段)。在加锁阶段，事务只能加锁，也可以操作数据，但不能解锁。在解锁阶段，此过程中事务只能解锁，也可以操作数据，不能再加锁。

两阶段协议的优势在于锁的获取和释放更加精细化。当事务涉及多个数据对象时，可以部分锁定其中的一部分进行数据操作，也可以先释放一部分锁让其他事务得以进行。

例如，一个事务涉及两个个数据对象A，B。如果事务对A，B的操作是顺序进行的，在获取锁阶段可以先获取A的锁，此时即使没有获取到B的锁，也能对A进行数据操作。同理，当获得A，B的锁后，做完了A即可将A释放，而无需等待B做完后再一并释放。

不足的是容易出现死锁，因为加锁阶段没有顺序要求。如两个事务分别申请了A, B锁，接着又申请对方的锁，此时进入死锁状态。

2PL协议中，利用锁来实现可串行化。包括读写锁、谓词锁和间隙锁。

读写锁

读锁又称为共享锁，写锁又称为独占锁。

• 若事务要读取对象，则须先获得该对象的读锁。如果该对象已经有写锁，则必须等待写锁释放。获取读锁后，其他事务依然可以获取该对象的读锁，但是无法获取写锁。即允许读读并发，不允许读写并发。

• 若事务要写入对象，则须先获得该对象的写锁。如果该对象上有任何锁(读锁或者写锁)，则必须等待该对象所有锁释放。获取写锁后，其他事务无法再从该对象上获取任何锁。

• 同一个事务内，锁可以升级和降级。在加锁阶段，读锁可以升级为写锁，在解锁阶段，写锁可以降级为读锁。

谓词锁

读写锁实现了对某一行的串行控制。但有时候事务内的读取是范围性的，这时候的控制需要谓词锁。

谓词锁是针对符合条件的所有行进行共享/独占控制，即共享谓词锁，独占谓词锁。

• 如果事务A想要读取匹配某些条件的对象，它必须获取查询条件上的共享谓词锁。如果另一个事务B持有任何满足这一查询条件对象的排它锁，那么A必须等到B释放它的锁之后才允许进行查询。

• 如果事务A想要插入，更新或删除任何对象，则必须首先检查旧值或新值是否与任何现有的谓词锁匹配。如果事务B持有匹配的谓词锁，那么A必须等到B已经提交或中止后才能继续。

间隙锁

如果事务持有很多锁，检查匹配的锁会非常耗时。因此，可以通过使谓词匹配到一个更大的集合来简化谓词锁。例如，如果有一个在12:00~13:00之间预订A房间的谓词锁，则锁定A号房间的所有时间段，或者锁定12:00~13:00时间段的所有房间是一个安全的近似，因为任何满足原始谓词的写入也一定会满足这种更松散的近似。

这样做的好处是，原本要比对某个房间是否为A且预定时间在12:00~13:00之间这两个条件，现在只需比对其中一个即可。如果这些字段上有索引，比对过程将更为快速。

3. 序列化快照隔离(SSI：serializable snapshot isolation)

两阶段锁是一种悲观并发控制机制：如果有可能出错(如数据对象被其他事务持有锁)，最好等到情况安全后再做任何事情。

而串行执行可以认为悲观到了极致：在事务持续期间，每个事务对整个数据库(或数据库的一个分区)具有排它锁。作为对悲观的补偿，必须让每笔事务执行得非常快，从而只需要短时间持有“锁”。

相比之下，序列化快照隔离是一种乐观并发控制技术。乐观意味着，即使存在潜在的危险也不阻止事务，而是继续执行，希望一切都会好起来。当一个事务想要提交时，数据库检查是否有什么不好的事情发生(即隔离是否被违反)：如果是的话，事务将被中止，并且必须重试。

如果存在很多争用(很多事务试图访问相同的对象)，则乐观控制表现不佳，因为这会导致很大一部分事务需要中止。如果系统已经接近最大吞吐量，来自重试事务的额外负载可能会使性能变差。但如果有足够的备用容量，并且事务之间的争用不是太高，乐观的并发控制技术往往比悲观的要好。

写偏差的出现原因在于，后续的写入基于此前从快照中读取的数据作为前提，但该数据之后受其他事务的影响，导致前提不再成立。由于没有锁的限制，造成这种情况有两种原因：

1. 读之前存在未提交的写入

2. 读之后发生写入

这两种情况，刚好是RR隔离级别下，MVCC所忽略的。

对于情况1，可以在提交时确认之前未提交的写入是否提交，如果已经提交，则中止事务。

对于情况2，对于写入事务，在写入前查询最近曾读取受影响数据的其他事务，然后通过这些事务，它们此前所读取的数据已经改变。

4. 性能比较

与两阶段锁定相比，可序列化快照隔离的最大优点是一个事务不需要阻塞等待另一个事务所持有的锁。非常适合读多写少的场景。

与串行执行相比，可序列化快照隔离并不局限于单个CPU核的吞吐量。

SSI的重要指标是中止率，长时间读取和写入数据的事务很可能会发生冲突并中止，这个重试开销会很大。因此SSI要求同时读写的事务尽量短(只读长事务可能没问题)

2.3 小结