设计数据密集型应用（6-7）：分片、事务
设计数据密集型应用（6-7）：分片、事务
分片
假设我们有一个单机数据库，上面有三张表：用户表、商品表和订单表。
无分片
业务刚起步的时候，数据量很少，这个只有三张表的数据库运行得很好。
垂直分片
随着业务发展，用户数量、商品数量、订单数量都在持续增长，数据库的负载越来越高。我们开始对数据库进行垂直拆分（垂直分片），把这三张表拆到三个数据库，而业务代码改改数据库的配置就好。
再后来，一个数据库也承载不了用户表的数据，需要对用户表进行水平拆分（水平分片）。比如，根据用户 ID 将数据哈希到 n 个数据库。
- 垂直分片对业务是透明的，对于小业务来说比较方便，对大业务来说一般无法满足扩展需求。
- 水平分片理论上可以大规模水平扩展以解决单机性能和容量不足，但可能需要业务介入修改；一些数据库中间件、NoSQL、NewSQL 可以做到水平分片对业务透明，但是一般会有接口能力限制或性能损失。
一般说的分片（sharding/partition）是指水平分片——将一个大的数据集（很多 record、row、document）分成多个小的数据集。一个小的数据集就是一个分片，可以保存到不同的机器上。
简单起见，接下来假设我们是要对一个 key-value 集合进行分片。
范围分片
将整个 key-value 集合根据 key 进行排序，然后划分成一个个有序的分片。比如，key 的集合是 [a, z]。可以划分成三个集合 [a, i)、[i, q)、[q, ∞)。
所有分片拼接起来，数据依然是有序的，可以高效执行 range query。
但是，范围分片有一个缺点：容易出现热点分片——少数分片的访问量大大超过其他分片。
热点分片无法通过水平扩展来解决。比如，如果 key 是单调递增的，那所有插入数据都会集中在最后一个分片。这个分片的数据插入速度会成为插入性能的瓶颈。单调递增的 key 在关系数据库领域是非常常见的。
采用范围分片的时候，一般需要动态调整分片的边界和数量：
- 当一个分片太大的时候，需要将其分裂（split）成两个差不多大的分片。
- 当两个相邻的分片太小的时候，需要将其合并（merge）成一个分片。
哈希分片
为了让数据分布更加均匀，避免出现热点，我们可以对 key 执行一次哈希函数，映射到一个整数，然后根据这个整数进行分片。
比如上面提到的用户表分片的哈希取模。但是哈希取模在增加或减少分片的时候比较麻烦，会打乱所有数据。如果采用哈希取模，一般会避免修改分片数量，比如 Redis Cluster 固定分片为 16384 个。
还有一种比较常见的哈希分片方式是一致性哈希（Consistent Hashing）。
根据 key 的哈希结果进行分片会导致 key 是全局无序的，范围查询效率很低。
比较极端的情况下，如果某一个 key 的请求特别多，同样会造成热点分片。
一些数据库，比如 Cassandra 的 key 可以是一个联合主键（>=2 个字段），哈希分片的时候只有第一个字段参与。假如这个联合主键是 {user_id, update_time}，只通过 user_id 的值进行哈希分片，可以保证 user_id 的数据都在同一个分片下，这样就可以实现某个用户的高效范围查询。
路由
分片之后，无论是哈希分片还是范围分片都需要有一个地方维护一个”路由表“——维护 key/hash -> partition -> ip:port 的映射。
事务
事务是对数据库操作的一种抽象，可以简化应用程序的逻辑。
ACID
事务有四个特性：ACID。
- 原子性（Atomicity）：一个事务中的所有操作，要么全部成功，要么全部失败，不会出现部分成功、部分失败的情况。
- 一致性（Consistency）：在事务开始之前和事务结束以后，数据库的完整性没有被破坏。“完整性”指的是应用程序的一些预设约束——数据的不变性。有的预设约束是由数据库保证的，比如外键约束、唯一索引；有的预设约束需要应用程序自己保证，比如账户的余额必须大于等于 0。
- 隔离性（Isolation）：多个事务并发、交叉执行可能会相互影响。隔离性描述的是多个事务并发执行的表现。事务隔离分为不同级别，常见的有：
- 读未提交（Read Uncommitted）
- 读已提交（Read Committed）
- 可重复读（Repeatable Read）
- 快照隔离（Snapshot Isolation）
- 串行化（Serializable）
- 持久性（Durability）：事务成功结束后，对数据的修改就是永久的，即便系统故障也不会丢失。对单副本的数据库来说，持久性的意思是数据被写入外存，比如 HDD 或 SSD。对多副本的数据库来说，持久性意味着数据以及成功复制到其它节点。
ACID 中，原子性、一致性、持久性都比较明确，不存在太多可以 trade-off 的空间。隔离性存在多种不同的隔离级别，可以在安全性与性能之间进行 trade-off。
隔离性是 ACID 中比较复杂的概念。如果不了解每个隔离级别的特点与不同，很容易写出有 bug 的代码，导致数据的一致性被破坏。
介绍隔离性的文章太多了，这里推荐一篇论文： A Critique of ANSI SQL Isolation Levels。下面介绍一下隔离性，主要参考这篇论文。
事务并发的异常现象
不同的隔离级别在事务并发执行时可能出现不同的异常现象。
脏写（Dirty Write）
脏写是最低级别的异常现象，相当于事务执行的时候没有任何保护。多个未提交的事务可能先后修改同一对象，即修改了其它事务未提交的数据。
假设数据库有两个值 x 和 y，事务需要保证 x + y = 100，x 和 y 的初始值均为 50。
现在有两个事务：
- T1: Set1(x=40), Set1(y=60), C1
- T2: Set2(x=60), Set2(y=40), C2
说明：Set1(x=1) 表示事务 T1 修改 x 为 1；C1 表示事务 T1 提交。下同。
执行序列可能如下：
Set1(x=40)...Set2(x=60)...Set2(y=40)...C2...Set1(y=60)...C1
最终数据库的结果是 x=60, y=60，破坏了数据库的一致性。
脏读（Dirty Read）
脏读和脏写的概念类似，脏写是修改了其它事务未提交的数据，脏读就是读取了其它事务未提交的数据。
继续使用上面脏写的例子，假设有两个事务：
- T1: Get1(x), Get1(y), C1
- T2: Set2(x=60), Set2(y=40), C2
说明：Get1(x) 表示事务 T1 对 x 的读取操作；Get1(x=1) 表示事务 T1 读取到 x 的值为 1。下同。
执行序列可能如下：
Get1(x=50)...Set2(x=60)...Set2(y=40)...Get1(y=40)...C1..C2
最终事务 T1 读取到的结果为 x=50, y=40。
不可重复读（Non-Repeatable Read）
字面上的意思：一个事务重复读取同一条记录，得到的结果不一样。
如果这条记录被并发事务修改，但是未提交就被读出来，此时的不可重复读属于脏读。
如果这条记录被并发事务修改，并且已提交，此时的不可重复读属于读提交（Read Committed）。
假设有两个事务：
- T1: Get1(x), Get1(x) // 读两次 x 的值
- T2: Set2(x=60), Set2(y=40)
执行序列如下：
Get1(x=50)...Set2(x=60)...Set2(y=40)...C2..Get1(x=60)...C1 // 不可重复读（读提交）
Get1(x=50)...Set2(x=60)...Set2(y=40)...Get1(x=60)...C2...C1 // 不可重复读（脏读）
幻读（Phantom）
幻读其实可以认为是不可重复读的特殊情况。只是幻读更加侧重于同一个事务先后两次一样的查询返回的记录数是否一样。
出现幻读的条件是事务需要执行谓词（范围）查询。比如：
- 事务 T1: select * from t where a > 5; select * from t where a > 5;
- 事务 T2: insert into t a = 6;
执行序列如下：
select * from t where a > 5; ... insert into t a = 6; ... select * from t where a > 5;
这种情况下，如果 a = 6 被第二个 select 查询出来，则出现幻读。
丢失更新（Lost Update）
Lost update 其实是因为没做好写写冲突的保护，导致两个并发事务其中一个的更新“丢失”了。
比如下面两个事务：
Get1(x=50)...Get2(x=50)...Set2(x=x+20=70)...C2...Set1(x=x+30=80)...C1
x 的初始值是 50，事务 T1 给 x 加 30，事务 T2 给 x 加 20。理想的结果是 50 + 20 + 30 = 100。但是事务 T1 覆盖了事务 T2 提交的值，导致事务 T2 的更新丢失了。
看起来有点像脏写，不过这里例子中 lost update 覆盖掉的是已经提交的事务的数据。脏写应该算是 lost update 的子集，类似脏读与不可重复读。
读偏斜（Read Skew）
在 Google 搜索 read skew 得到和 read skew 相关的文章并不多，大部分都是和 write skew 相关。有一些文章将 read skew 和 non-repeatable read 归为同一类。
Non-repeatable read 侧重于描述某一个对象在一个事务中重复查询多次，结果是否一致。
Read skew 则侧重于描述多个对象之间的一致性关系。
看下面一个例子，假设事务需要保证 x + y = 100，初始值 x = y = 50。
Get1(x=50)...Set2(x=40)...Set2(y=60)...C2..Get1(y=60)...C1
此时，事务 T1 读取到的 x=50, y = 60，x + y = 110 出现不一致的状态。
其实，在 Set2(y=60) 前面再插入一个 Get1(y=50)，就可以看出来 read skew 其实也是不可重复读。
写偏斜（Write Skew）
Write skew 是指两个事务( T1 与 T2 )并发读取一个数据集(例如包含 V1 与 V2)，然后各自修改数据集中不相交的数据项(例如 T1 修改 V1, T2 修改 V2)，最后并发提交事务。导致 write skew 的根本原因是没有做好读写冲突的保护。
直接看一个例子：假设在某银行有两个账户 V1 与 V2，银行允许 V1 或 V2 透支，只要保证两个账户总和非负，即 V1 + V2 ≥ 0。 两个账户的初值各是 100 元。
启动两个事务：
- T1 从 V1 取出 200 元。
- T2 从 V2 取出 200 元。
执行序列如下：
Get1(V1=100)...Get1(V2=100)...Get2(V1=100)...Get2(V2=100)...Set1(V1=-100)...Set2(V2=-100)...C1...C2
最后两个账户的值都是 -100，破坏了数据的一致性。
隔离级别的关系
最后，用一张图总结一下各种隔离级别和异常现象之间的关系。
