百万节点数据库扩展之道(1): 传统关系型数据库
本博客在http://doc001.com/同步更新。
本文主要内容翻译自MySQL开发者Ulf Wendel在PHP Submmit 2013上所做的报告「Scaling database to million of nodes」。翻译过程中没有全盘照搬原PPT，按照自己的理解进行了部分改写。水平有限，如有错误和疏漏，欢迎指正。
本文是系列的第一篇，本系列所有文章如下：
- 百万节点数据库扩展之道(1): 传统关系型数据库
前言
今天的数据库世界让人倍感迷惑。回想十年前进行Web开发，可选择的数据库还极为有限。然而现在，除了传统的数据库外，有150+的NoSQL数据库供君选择。这期间究竟发生了什么翻天覆地的变化，使得单节点数据库逐步演变为数百万节点的全球数据库？为了解答这个疑惑，本文将引导读者回顾这些年数据库的那些事儿。
在正文之前，读者应当明白，与传统开发相比，在海量数据库系统上进行应用开发存在一定区别，而开发海量数据库本身则有天壤之别。
数据库的出现
1960年代——黑暗岁月
有谁曾经接触过大型机的日常数据交换？2000年以后呢？
1960年代的数据存储示意图
这个时候的应用数据被存储在磁带上，数据库还未被发明出来。公司在生产环境使用的每一个应用都有自己的数据存储方式。开发者使用十六进制编译器来解读数据，制作报告时需要花费了很多额外的时间从多个应用抽取数据。从这个安全问题频出的年代看，这是怎样天真美好的岁月，应用安全到只有知悉所有实现细节才能保持运行的地步，就算你拿到数据也白搭。(Zz..囧)
1970年代——神迹初显
这个时代的数据存储的目标包括：
- 数据的内在视图(存储细节)和外在视图(外在表现)分离
- 中心式存储
- 数据一致性，高效的数据访问
- 多用户支持，访问控制
1970年代数据库示意图
(关系型)数据库终于被发明了出来，成为解决一个公司内部不同应用的数据共享问题的有效手段。
一个数据库系统必须确保数据一致性，并提供诸如访问控制之类的手段保证多应用、多用户环境下的数据安全。当然，数据的存储效率也极为关键。
使用数据库带来的一个好处就是，用户看到的数据外在视图和内在视图是完全隔离的。用户根本不需要关心数据的存储细节。不管内部的存储方式如何，数据库使用一致的SQL语言提供数据。
基本数据概念
什么是数据？
我们知道数据一致性是一个数据库系统的核心问题，然而，究竟什么是数据？
显然，所有的数据都会有一个类型和一个值域。例如，一个字符串是一组字母的序列，一个数却只包含数字，它们的类型就是不一样的。
不同类型的数据示意图
操作符(operator)与数据结构(data structure)
数据可以分为标量(scalar)数据类型和非标量(non-scalar)数据类型两类。一个标量数据类型只保存唯一的数据项，字符串、整数就是典型的标量数据类型。与之相反，一个非标量数据类型是包含多个数据项的类型，类就是典型的非标量数据类型。
操作符用于操作数据类型，每一个数据类型都有一组适用的操作符集合。例如，类的构造器(constructor)是用于初始化类成员的操作符。
数据结构规定了数据的组织、存储方式。一些数据库系统允许自定义数据结构。一个对象(object)由一个数据结构和定义在其上的一组操作符组成，而POD(plain old data)数据结构就只包含数据结构。
操作符与数据结构示意图
状态(state)
在一个程序中，数据是动态的。数据的状态随时间发生变化，修改操作会导致数据状态变化，通常这些状态遵循一定的规则。
数据状态示意图
数据库的数据模型
数据库的一个数据模型定义了数据库的数据结构、数据的存储方式，和全局操作符。数据库会长期运行，全局操作符实际上规定了可能发生的状态变化。
数据库内部使用数据库模式(schema)描述一个特定数据模型。很少有数据库以无模式的方式存储数据，当然，很多的NoSQL系统的模式非常灵活。
常见数据模型分为四种：
- 关系模型(Relational data model)
- 文档模型(Document model)
- 键值模型(Key-Value model)
- 宽列模型(Wide columnar model)
后三种都属于NoSQL的范畴。接下来将简要介绍这四种模型。
关系型数据库
尽管关系模型的缺点被一些NoSQL所改进，但是除了这些缺点，我们不应该忘记关系模型的优点。至少到现在，关系模型仍然占有统治地位。
NoSQL的革新本质在于数据模型本身，而其它的改进多流于表面，完全可以被关系型数据库借鉴。例如，关系型数据库也可以实现HTTP接口；关系型数据库也可以提供更低层次的访问接口来绕开SQL；关系型数据库也可以简化管理体系；等等。
模式设计
模式设计是关系型数据库应用开发的第一步，包含3个步骤：
- 提炼出需要存储的信息。
- 创建实体-关系(E-R)模型：
- 实体：主题、事情、物体
- 属性：对实体的描述、信息项、规则
- 候选键：能够唯一标识一个实体的属性集合
- 关系：实体间的关联，1:1、1:n、n:m
- 将E-R模型转化为物理数据模型：
- 网络模型、关系模型、分层模型
- 关系模型：表、属性、主键
- 关系模型：应用数据库规范化法则
数据库规范化(database normalization)
数据库规范化的目的是降低数据表的冗余和依赖程度。数据库规范化有很多范式，其中第一范式(first normal form, 1NF)规定：
- 一个关系的所有属性都是不可再分的原子数据项
- 每一个属性只包含唯一的值
该范式禁止创建嵌套的表结构，例如下图中，在一张博客发表表内嵌套一个博客评论列表。嵌套的表结构在NoSQL中比较常见。
嵌套表示意图
为了不破坏1NF，同时满足一些必要的嵌套需求，SQL:99和SQL:2003引入了非原子数据结构。SQL:99增加了ROW和ARRAY，SQL:2003增加了MULTISET。遗憾的是，很多关系型数据库都没有实现这些数据类型。进一步说，如果这些数据类型得到了实现，关系型数据库连接(join)操作将会变得非常高效，键值数据库和文档数据库在这方面的优势也就不那么明显了。
查询
关系型数据库的查询通过SQL语言进行，其理论基础是关系代数。
ACID事务
关系型数据库的事务满足ACID：
- 原子性(atomicity)
- 一个事务的操作要么全做，要么全不做
- 在各种失效情况下也予以保证：掉电、崩溃...
- 一致性(consistency)
- 事务只能导致数据库从一个有效状态转变到另外一个有效状态
- 已定义的规则不会被违反：约束、触发器...
- 隔离性(isolation)
- 并行执行的事务与串行执行的效果等效，不会互相干扰
- 持久性(durability)
- 一旦事务提交，就不可撤销
- 在各种失效情况下也予以保证：掉电、崩溃...
ACID反映了数据库管理系统(database management system，DBMS)设计和开发的目标。DBMS不仅仅保证数据被正确组织(数据模型，模式)，保证数据被轻松访问(关系代数、SQL)，也需要保证多用户环境下的数据安全。
在RDMS事务中，用户的工作要么全做，要么都不做，不存在中间状态。事务不会破坏任何已定义的规则，在完成时保证数据库仍然处于一个已定义的一致状态。事务在被提交前，不会被其它并发的事务妨碍。事务一旦提交，其结果永远不会丢失。
并发控制
假设两个事务同时想修改同一个数据项，需要保证它们的修改不会相互冲突。这个工作由并发控制(concurrency control)算法来完成。
并发控制算法的分类如下图所示：
并发控制算法分类
这张图是从原PPT翻译得到的，对该分类有疑问的请参考其它文献。
并发控制算法可以分为悲观算法和乐观算法两大类。悲观算法在事务开始前就检查冲突数据，提前锁定，使事务访问顺序化。乐观算法将冲突检查推迟到最后进行，如果冲突，则回滚事务。
隔离级别
ANSI/ISO SQL定义了若干隔离级别，隔离级别会影响并发控制算法的效率：
- 可序列化(serializable)
- 最高级别的隔离，在事务期间对冲突数据的读写保持范围锁(range lock)，即冲突事务顺序进行
- 可重复读(repeatable read)
- 没有范围锁，可能存在「幻影读(phantom read)」现象
- 授权读(read committed)
- 可能发生「不可重复读(non-repeatable read)」
- 未授权读(read uncommitted)
- 允许「脏读(dirty read)」
幻象读：一个事务中，两个完全相同的查询语句执行得到不同的「结果集」。在下图的例子中，事务1的第2次查询语句读到了事务2新提交的数据。
幻象读
不可重复读：在一次事务中，「一行数据」获取两遍得到不同的结果。在下图的例子中，事务2提交成功，因此它对id为1的行的修改就对其它事务可见了，与事务1之前已经从这行读到了另外一个「age」的值不同。
不可重复读
脏读：当一个事务允许读取另外一个事务修改但未提交的数据时，就可能发生脏读。在下图的例子中，事务2修改了一行，但是没有提交，事务1读了这个没有提交的数据。现在如果事务2回滚了刚才的修改或者做了另外的修改的话，事务1中查到的数据就是不正确的了
脏读
物理层面
关系型数据库将记录存储在「页(page)」中，每一个页是4~32KB大小的连续内存区域。一个页可以包含一个或多个记录。如果单个页不能存储下一个记录的全部数据，那么将使用额外的溢出页(overflow page)。为了优化访问效率，关系型数据库使用B-tree或其衍生数据结构将页按序存储在磁盘上。如果数据的实际存储顺序与一个索引的顺序一致，那么这个索引是一个聚集索引(clustered index)。例如，InnoDB就使用聚集索引按照主键来组织数据表。聚集索引有助于获得更高的顺序搜索性能。
连接(join)
考虑一个数据表连接操作r⋈s(r、s分别是两个数据表)，常见的执行策略包括：
- 嵌套循环(nested loop)
- 通过两层嵌套循环完成，首先扫描表r，每读到一条记录，就去扫描表s以查找符合要求的记录
- 算法复杂度O(nr*ns)，其中nr和ns分别是表r和表s中的记录数量
- 对索引和连接条件无任何要求
- 块嵌套循环(block nested loop)
- 嵌套循环的一个变种，以块为单位而不是以记录为单位处理关系
- 相比嵌套循环，能够减少从硬盘传输数据的次数，因此，效率有所改进
- 索引嵌套循环(indexed nested loop)
- 如果内层嵌套的被连接表的连接属性上有索引，则可以利用索引来优化符合要求记录的查找
- 归并连接(merge join，又称排序-归并-连接，sort-merge join)
- 对连接的两个表按公共属性排序，利用归并排序算法寻找公共属性相同的符合条件的记录
- 可用于计算自然连接和等值连接
- 散列连接(hash join)
- 将连接的两个表按照公共属性使用相同的hash函数将记录映射到同一空间，再对相同hash值的记录做匹配
- 实际的实现只对一个较小的表建hash查找表，另外一个表直接匹配记录
- 可用于计算自然连接和等值连接
原PPT只提及了nested loop和hash join，这里根据其它材料进行了补充。
关系型数据库架构扩展
尽可能地缓存
缓存是提高数据库性能的一个有效手段。
数据库保存的数据有状态的(stateful)，且为硬状态(hard-state)，保证数据一致性(consistent)；缓存保存的数据无状态(stateless)，且为软状态(soft-state)，不保证数据一致性(inconsisteng)。
一个典型的缓存系统如下图所示：
缓存示意图
软状态维持一段有限的时间，在过期前需要重新刷新，否则自动失效。软状态可能比数据库中的状态滞后。相反，硬状态一直存在，且一定正确。
缓存的无状态特征允许缓存系统简单地通过增加/减少资源来调整规模。
接下来的描述都是以MySQL为例展开的。
MySQL内置缓存
除了外部的缓存系统，MySQL本身也进行了两项重要的改进：
- 内置了查询缓存，该缓存的数据状态与数据库是一致的。
- 通过InnoDB提供了Memcache协议的底层记录访问接口，访问速度比外部的Memcache更快，简化了架构。
MySQL改进示意图
MySQL主从
MySQL对可扩展性的答案是主从复制模式。在该模式中，所有的客户端写请求由唯一的master进行处理。master将操作记录到二进制日志中，该日志被异步发送给slave们，slave们重放操作，完成数据的更新。slave可以处理客户端的读操作，前提是，应用可以容忍极短时间的数据滞后。该模式应该和缓存结合使用。
MySQL主从示意图
在一个读操作为主的环境(如Web应用)中，该模式具备极佳的横向扩展能力，增加新slave的代价可以忽略不计。
在一个写操作为主的环境中，该模式很难横向扩展：
- 只有一个master处理所有的写操作，很容易单节点故障
- 很难读写分离，即使使用PECL/mysqlnd_ms效果也不是很好
- MySQL要努力啊...
更多MySQL演示资料参见slideshare。
架构扩展的目标
每一个MySQL工程师都应该知道架构扩展的目标有这些：
- 可用性(availability)
- 节点失效不会对集群造成影响
- 可伸缩性
- 地理分布
- 能够根据用户和数据的规模伸缩
- 均衡读/写负载
- 分区透明
- 一切内部细节对客户端都是透明的
MySQL架构扩展方案分类
根据欲达到的目标，可对现有的MySQL解决方案进行归类。在这里，按照「事务执行的位置」和「节点同步发生的时间」将解决方案分为四类：
MySQL架构扩展方案
未完待续...
下一部分将介绍NoSQL理论和Amazon Dynamo，参见：
