设想一个最朴素的取款程序：先读出账户余额，减去取款金额，再把新余额写回。当两台 ATM 在同一瞬间为同一个账户执行这段逻辑——都读到了 1000 元、都各自算出 900 元、都写回 900 元——结果是取走了 200 元，账户却只少了 100 元。再设想写回的那一刻服务器恰好断电：扣款记下了一半，钱却没真正划走。
这类"并发"与"崩溃"交织出的错误，正是数据库系统要解决的核心问题：当多件事同时发生、当机器随时可能崩溃，如何确保数据的正确性？
破除误解：数据库不只是"存数据的地方"
普通人通常把数据库理解为一种更高级的 Excel——用于存储和查询数据。这个理解缺少了最重要的部分：数据库的核心价值不在于存储，而在于保证并发访问下的数据正确性。
如果只需要存数据，文件就够了。数据库的独特贡献是：在数千个用户同时读写、服务器随时可能断电崩溃的环境下，保证每一笔操作要么完整成功，要么完全没有发生——不存在"一半完成"的状态。
这个保证，在数据库领域叫做事务（Transaction），它的形式化属性叫 ACID。
历史：从文件到关系型数据库
1960 年代：层次型与网状型数据库
早期数据库（如 IBM IMS，1966）使用树状（层次型）或图状（网状型）结构存储数据，查询需要程序员按照特定路径导航——就像在文件系统里沿着目录路径查找。这种结构与物理存储强耦合，更换存储格式就要重写所有查询代码。
1970 年：关系模型的革命
1970 年 6 月，IBM 研究员埃德加·科德（Edgar F. Codd）发表了论文《大型共享数据库数据的关系模型》（A Relational Model of Data for Large Shared Data Banks）。这篇不到 12 页的论文，彻底改变了数据库的设计方式。
科德的核心思想：把数据表示成关系（Relation），也就是我们熟悉的表（Table）。数据之间的关联不通过指针或路径，而通过值的匹配（外键）表达。查询用数学上的关系代数描述——这为后来的 SQL 奠定了理论基础。
关系模型的优雅之处：数据的逻辑结构与物理存储完全解耦。程序员只需说"我想要什么数据"，不需要说"如何找到它"——这是声明式（declarative）查询的开端。
1974 年：SQL 的诞生
IBM 在科德工作的基础上，开发了 SEQUEL 语言（后改名为 SQL，Structured Query Language）。SQL 是第一个成功的声明式查询语言：
-- 找出所有余额超过 10000 元的活期账户
SELECT account_id, holder_name, balance
FROM accounts
WHERE account_type = 'checking'
AND balance > 10000
ORDER BY balance DESC;
```这段代码描述了"想要什么"，而不是"如何查找"——具体的查询执行计划由数据库引擎的查询优化器决定。
ACID：事务的四个承诺
事务概念的成形有清晰的文献轨迹。1981 年，吉姆·格雷（Jim Gray）在 VLDB 上发表《The Transaction Concept: Virtues and Limitations》，把事务系统化为"要么全做、要么不做"的一致性单元，给出了整个领域沿用至今的词汇。1983 年，特奥·哈尔德（Theo Härder）和安德烈亚斯·罗伊特（Andreas Reuter）在《ACM Computing Surveys》的论文《Principles of Transaction-Oriented Database Recovery》中，把事务的核心保障归纳为 ACID 这四个属性——这个缩写正是他们造的（实际上 IBM IMS 系统早在 1973 年就实现了 ACID 事务，但术语是后来命名的）：
原子性（Atomicity）：事务是不可分割的最小单元。银行转账：从 A 账户扣钱 + 向 B 账户加钱，必须同时成功或同时失败——不能只执行一半。
BEGIN TRANSACTION;
UPDATE accounts SET balance = balance - 100 WHERE id = 'A';
UPDATE accounts SET balance = balance + 100 WHERE id = 'B';
COMMIT; -- 两条语句要么都生效，要么都不生效
```一致性（Consistency）：事务执行前后，数据库必须从一个有效状态转换到另一个有效状态。"有效"由数据库约束定义（如账户余额不能为负、外键必须存在）。
隔离性（Isolation）：并发执行的事务，彼此之间不应相互干扰——每个事务运行时，就像系统中只有它一个事务在运行。这是最难实现的属性，也是性能与正确性之间最大的权衡点。
持久性（Durability）：一旦事务提交，其结果必须永久保存，即使随后发生服务器崩溃、断电。实现方式是预写日志（Write-Ahead Log，WAL）：修改真正写入磁盘之前，先把操作记录到日志文件。
WAL 的工作机制值得拆开看，它是持久性、原子性和性能三者的交汇点：
- 先日志，后数据：任何数据页落盘之前，描述这次修改的日志记录必须先落盘。这样崩溃后总能凭日志重建现场。
- 提交即刷日志：
COMMIT返回成功的那一刻，只需保证日志已顺序追加到磁盘；被修改的数据页可以留在内存里慢慢写。数据库借此把昂贵的随机写换成了便宜的顺序追加——这是 WAL 同时提升持久性和写性能的关键。 - 崩溃恢复 = 重做 + 撤销：重启后重放日志把已提交的修改重做（redo），把没提交完的事务撤销（undo），数据库回到"所有已提交事务生效、所有未完成事务如同从未发生"的状态。
这套恢复框架的成熟形态是 IBM 研究院的 ARIES 算法，由 C. Mohan 等人 1992 年发表于《ACM Transactions on Database Systems》。它的一个著名口号是"repeating history"：恢复时先把数据库重演到崩溃瞬间的原样，再从容撤销未提交的事务。今天 PostgreSQL、MySQL InnoDB、SQL Server 的恢复子系统，本质上都是 ARIES 的变体；SQLite 的 WAL 模式则是同一思想的精简实现（见 SQLite 内核剖析）。
隔离级别：正确性与性能的权衡
完全的隔离性（Serializable，可串行化）意味着并发事务的执行结果等同于某种顺序执行——代价是极低的并发性（因为需要大量锁）。实践中，SQL 标准定义了四个隔离级别：
| 隔离级别 | 脏读 | 不可重复读 | 幻读 | 说明 |
|---|---|---|---|---|
| Read Uncommitted | 可能 | 可能 | 可能 | 最弱，性能最高 |
| Read Committed | 不可能 | 可能 | 可能 | PostgreSQL 默认 |
| Repeatable Read | 不可能 | 不可能 | 可能 | MySQL 默认 |
| Serializable | 不可能 | 不可能 | 不可能 | 最强，性能最低 |
- 脏读：读到其他事务尚未提交的数据（若那个事务回滚，读到的数据就是无效的）
- 不可重复读：同一事务内，两次读同一行，数据不同（因为其他事务在中间提交了修改）
- 幻读：同一事务内，两次相同查询返回了不同数量的行（因为其他事务插入或删除了行）
大多数 Web 应用使用 Read Committed 或 Repeatable Read，接受一定程度的异常，换取更高的并发性。
快照读：MVCC 如何让读不阻塞写
上面那张表隐含着"隔离 = 加锁"的假设，但现代数据库的主流做法是多版本并发控制（MVCC）。它的核心机制是：写不覆盖旧值，而是生成一个新版本。每行数据因此同时存在多个版本，各自携带版本号或时间戳。读事务开始时领到一个"快照"，之后看到的就是那个时刻的一致切面——写者在旁边改得再热闹，读者读的仍是历史版本，读写互不阻塞。
快照不是免费的午餐。旧版本必须保留到没有事务再需要它为止：PostgreSQL 把旧版本留在堆表里形成"死元组"，靠 VACUUM 后台清理；InnoDB 把旧版本存在 undo log 里。一个忘记关闭的长事务会拖住全库的清理进度，这是生产环境里真实的事故来源（现场细节见 PostgreSQL 的 MVCC 实现）。
还有一个更隐蔽的坑：快照隔离不等于可串行化。经典反例是"写偏斜"（write skew）：医院规定至少一名医生在岗，两个医生各自查到"有两人在岗"、各自提交请假，两个事务检查都通过，合起来却无人值班。这类异常靠"各自读到的数据没变"检测不出来。早在 1995 年，Berenson 等人就在 SIGMOD 论文《A Critique of ANSI SQL Isolation Levels》中指出，SQL 标准用三种异常来定义隔离级别的做法根本不完备。
修补方案到 2008 年才出现：Cahill、Röhm 与 Fekete 在 SIGMOD 发表可串行化快照隔离（SSI）——在快照之上检测危险的读写依赖结构，发现可能成环就中止其中一个事务。PostgreSQL 9.1（2011 年）率先落地了 SSI，让 Serializable 级别第一次有了不依赖严格两阶段锁的实用实现。
索引：查询性能的核心
没有索引的数据库，每次查询都要扫描整张表（Full Table Scan）。如果表有 1 亿行，一次 WHERE email = 'user@example.com' 的查询就需要检查 1 亿条记录——秒级延迟，完全不可用。
B+ 树索引（大多数关系数据库的默认索引结构）把查询时间从 $O(n)$ 降低到 。但这个对数的底数不是 2，而是每个节点的扇出——B+ 树一个节点就是磁盘上的一页，能存数百到上千个键：
1 亿行，按扇出 1000 估算：1000³ = 10 亿
树高只有约 3 层，根与上层节点常驻内存
一次点查通常只需 1 次磁盘 I/O，而非扫描 1 亿行
```（若误把它当二叉树算， 层——那正是 B+ 树要避免的结果：每层都是一次磁盘寻道。）
B+ 树特别适合范围查询（WHERE age BETWEEN 20 AND 30）——叶子节点形成链表，范围查询只需找到起点然后顺序遍历。
哈希索引适合精确查询（WHERE id = 12345），查找时间 $O(1)$，但不支持范围查询。
NoSQL：关系模型的挑战者
2000 年代中期，Web 2.0 的爆炸性增长带来了关系数据库难以处理的挑战：用户量从万级到亿级，数据结构频繁变化，需要跨越成百上千台服务器水平扩展。
Google（Bigtable，论文发表于 OSDI 2006）和 Amazon（Dynamo，论文发表于 SOSP 2007）分别发表了影响深远的论文，描述了他们为应对这种规模而设计的非关系型（NoSQL）数据库：
| 类型 | 代表系统 | 适用场景 |
|---|---|---|
| 文档型 | MongoDB、CouchDB | 半结构化数据、JSON 文档 |
| 键值型 | Redis、DynamoDB | 缓存、会话、简单查找 |
| 列族型 | Cassandra、HBase | 时序数据、大规模写入 |
| 图数据库 | Neo4j、Amazon Neptune | 社交网络、推荐系统 |
NoSQL 系统通常选择牺牲部分 ACID 属性（尤其是强一致性），换取更高的可用性和扩展性——这正是 CAP 定理（见后文）描述的权衡。
CAP 定理与分布式一致性
2000 年，埃里克·布鲁尔（Eric Brewer）提出了 CAP 猜想，2002 年吉尔伯特和林奇（Gilbert & Lynch）给出了证明：在一个分布式系统中，一致性（Consistency）、可用性（Availability）、分区容错性（Partition Tolerance）三者最多只能同时满足两个。
- 一致性：所有节点在任何时刻都看到同样的数据
- 可用性：每次请求都能得到响应（不一定是最新数据）
- 分区容错性：网络分区（节点之间网络中断）时，系统仍能运行
互联网环境下，网络分区不可避免，所以 P 必须保留，选择变成 CP 或 AP： - CP（一致优先）：HBase、ZooKeeper——网络分区时拒绝服务，保证数据一致 - AP（可用优先）：Cassandra、DynamoDB——网络分区时继续服务，但数据可能不一致
CAP 定理后来被精化为 PACELC 模型：即使没有分区，也存在延迟（L）与一致性（C）的权衡。
代价与争议
ORM 的双刃剑：对象关系映射（ORM，如 Hibernate、Django ORM）简化了数据库操作，但也遮蔽了 SQL 的运作方式，容易产生隐蔽的性能问题（如 N+1 查询问题：循环中每次迭代都触发一次数据库查询，导致 1000 条记录触发 1001 次查询）。
"NewSQL"的声称：Google Spanner（论文发表于 OSDI 2012）、CockroachDB 等系统宣称同时提供 NoSQL 的水平扩展能力和传统关系数据库的 ACID 事务。Spanner 的关键装置是 TrueTime：数据中心的 GPS 接收机与原子钟给出的是一个带误差界的时间区间而非一个时刻；事务提交时若区间的"最早可能时刻"还没过完，就主动等它过去（commit-wait），用几毫秒的等待换来全球范围的外部一致性。CockroachDB 没有专用硬件，用混合逻辑时钟逼近同一目标。代价同样真实：这些系统的写延迟和运营成本显著更高，跨大洲的事务尤其昂贵。
科德原始论文的误解：科德的关系代数中，NULL 值没有良好定义。SQL 对 NULL 的三值逻辑（TRUE/FALSE/UNKNOWN）是后来引入的，在许多情况下违反直觉。科德本人晚年对 SQL 的很多设计感到不满，认为 SQL 并没有忠实地实现关系模型。
跨域连接
- 并发与并行：隔离性本质上是并发控制：完全串行化等价于给所有事务排一条全序，代价是并发度骤降。多版本并发控制换了个思路——让读者看到一个一致快照而不阻塞写者，把"排队"换成"多留几份历史"。推论是：隔离级别的选择等于选择容忍哪些异常，而不是选择要不要正确。
- 逻辑：空值让查询语言变成三值逻辑，排中律随之失效：一个值等于自身不再恒真，否定式的集合判定碰上空值会返回未知，从而过滤掉全部行。可检验推论：凭二值直觉写出的谓词会静默丢行，而不是报错——这是最难察觉的一类缺陷。
- 集合论：关系代数建立在集合与一阶谓词逻辑上，查询重写就是代数等价变换。但只有当算子真正满足交换、结合、分配律时，谓词下推与连接重排才安全；允许重复行的多重集语义，恰恰破坏了其中一部分等价。推论是：优化器的每一次重写，背后都有一条必须成立的代数恒等式。
- 制度经济学：事务是一份可回滚的契约：双方义务要么同时生效，要么当作从未发生。复式记账把这条约束直接写进账簿结构——借贷必须相等，于是"半完成"在形式上无法表达，错账立刻显形。
- 联邦制：中央与地方失联时，地方是继续自行决策，还是停摆等待授权？这正是网络分区时的两难。可检验推论：把整个数据库永久标成一致优先或可用优先是错的，真正的选择粒度是具体操作——唯一性必须一致，浏览可以读旧。同理，跨节点的原子提交与共识密切相关，却受制于所有参与者能否准备完成。
参考文献
- Codd, E. F. A Relational Model of Data for Large Shared Data Banks. CACM 13(6), 1970.（关系模型原始论文）
- Gray, J. "The Transaction Concept: Virtues and Limitations." Proc. VLDB, 1981.（事务概念的经典表述）
- Härder, T. & Reuter, A. "Principles of Transaction-Oriented Database Recovery." ACM Computing Surveys 15(4), 1983.（ACID 术语的出处）
- Mohan, C., Haderle, D., Lindsay, B., Pirahesh, H. & Schwarz, P. "ARIES: A Transaction Recovery Method Supporting Fine-Granularity Locking and Partial Rollbacks Using Write-Ahead Logging." ACM Transactions on Database Systems 17(1), 1992.（ARIES 恢复算法）
- Berenson, H., Bernstein, P., Gray, J., Melton, J., O'Neil, E. & O'Neil, P. "A Critique of ANSI SQL Isolation Levels." Proc. ACM SIGMOD, 1995.（指出 SQL 隔离级别定义的不完备）
- Cahill, M. J., Röhm, U. & Fekete, A. D. "Serializable Isolation for Snapshot Databases." Proc. ACM SIGMOD, 2008.（SSI，PostgreSQL 9.1 可串行化实现的理论基础）
- Gray, J. & Reuter, A. Transaction Processing: Concepts and Techniques. Morgan Kaufmann, 1992.（事务处理的圣经级著作）
- Hellerstein, J. M. & Stonebraker, M. Readings in Database Systems. 5th ed. MIT Press, 2015.（经典论文合集）
延伸阅读
- Kleppmann, M. Designing Data-Intensive Applications. O'Reilly, 2017.（现代分布式数据系统的最佳入门）