那些必读的数据库领域论文

之前林仕鼎曾整理过系统架构领域的学习资料，这几天Spark核心团队成员辛湜（Reynold Xin）公开了他整理的一份数据库学习资料列表，Hacker News上引起了不少讨论。其中的评述文字也很有价值，简要编译如下。大家对这个列表如有补充，请评论。

基础与算法

• The Five-Minute Rule Ten Years Later, and Other Computer Storage Rules of Thumb (1997): 此文与十年前的原始论文解释了一个量化公式，用来计算数据页是否应该缓存在内存中。能读到Jim Gray处理一系列相关问题（比如数据页应该多大）的方法，幸何如之。
• Paxos Made Simple (2001): Paxos构成了许多分布式系统的基础。想法很简单，但理解起来却出名的难（可能是因为原始论文的写法太……）。
• AlphaSort: A Cache-Sensitive Parallel External Sort (1995): 缓存友好的排序。
• Patience is a Virtue: Revisiting Merge and Sort on Modern Processors (2014): 实际使用中各种排序算法及其利弊很好的综述。

关系数据库

• Anatomy of a Database System (200x): Joe Hellerstein（伯克利教授，数据库专家）对关系数据库很棒的综述，涉及到各个组件。
• A Relational Model of Data for Large Shared Data Banks (1970): Codd对数据独立性的探讨。尽管最近NoSQL兴起，但我相信这篇论文的一些思想在大规模并行数据系统中越来越重要了。
• ARIES: A Transaction Recovery Method Supporting Fine-Granularity Locking and Partial Rollbacks Using Write-Ahead Logging (1992): 第一个实际可用的算法，支持在故障时并发事务执行而又不丢失数据。此文既有底层细节，又有高层算法的解释，因此很难读。可能还不如先去读一本数据库教材。
• Efficient Locking for Concurrent Operations on B-Trees (1981)和The R*-tree: An Efficient and Robust Access Method for Points and Rectangles (1990): B-Tree是各类数据库的核心数据结构，在随机查找时读放大因子很低。R-tree是B-Tree的扩展，支持多维数据（如地理数据）的查找。
• Improved Query Performance with Variant Indexes (1997): 分析型数据库和OLTP数据库需要不同的利弊权衡方式。这反映在索引数据结构的选择上。此文讨论了许多更适合分析型数据库的索引数据结构。
• On Optimistic Methods for Concurrency Control (1981): 支持并发有悲观和乐观两种方式。此文解释了乐观并发控制。……
• Access Path Selection in a Relational Database Management System (1979): 查询优化的基础。此文解释了传统的成本模型方法，以及选择最佳计划的一个动态规划方法。……
• Eddies: Continuously Adaptive Query Processing (2000): 此文模仿流体力学提出了一系列动态优化查询执行的技术。虽然Eddies还没有商业系统的实际应用，但很启发思路，重要性也在与日俱增。……

经典的系统设计

• A History and Evaluation of System R (1981): IBM的System R和Berkeley的Ingres两个系统都证明了关系数据库是可行的。值得注意的是，30年来关系数据库的内部并没有什么太大变化。
• The Google File System (2003) 和 Bigtable: A Distributed Storage System for Structured Data (2006): Google数据基础设施的两大核心组件。……虽然可能已经被Google更新的技术取代，但其中的思想将历久弥新。
• Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications (2001) 和 Dynamo: Amazon’s Highly Available Key-value Store (2007): Chord诞生于分布式散列表还是学术研究热点的时代。它只做一件事儿，却做到了极致：如何在完全分布式的环境（P2P）中使用一致性散列查找键的位置。Dynamo论文则解释了如何使用Chord构建分布式K-V存储。请注意Dynamo与Chord有一些设计决策上的变化，比如指取表（finger table）是O(N)的而不是O(logN)的，因为Dynamo为Amazon内部使用，对数据中心的节点有更大控制权，而Chord针对的是广域网中的P2P节点。

列式数据库

列式存储和面向列的查询引擎对于分析型负荷即OLAP至关重要，已有15年历史（最早的MonetDB论文发表于1999年），到现在几乎所有商业数据仓库都有列式引擎了。

• C-Store: A Column-oriented DBMS (2005) 和 The Vertica Analytic Database: C-Store 7 Years Later (2012): C-Store是新英格兰地区多所大学（指MIT、布朗、马萨诸塞州大等）的专家们很有影响的学术研究。Vertica是其商业化版本。
• Column-Stores vs. Row-Stores: How Different Are They Really? (2012): 讨论列式存储和查询引擎的重要性。
• Dremel: Interactive Analysis of Web-Scale Datasets (2010): Google令人惊叹的论文。……将列式存储应用于复杂的嵌套数据结构。论文对嵌套数据结构的支持谈得很多，对查询执行的细节涉及较少。有好几个开源项目声称自己在构建Dremel的开源版。但Dremel系统通过大规模并行和列式存储实现低延迟，因此在Google之外这种模型未必有用，因为很少有公司能搞得起几千个节点来做即时查询。

数据并行计算

• MapReduce: Simplified Data Processing on Large Clusters (2004): MapReduce既是一种编程模型（借鉴自函数式编程中的古老概念），也是Google用于分布式数据密集计算的系统。这个编程模型如此简单而又功能强大，能够满足广泛的编程需求。系统加上模型，是容错而且可扩展的。说现在有一半学术界的人在研究的问题都受到MapReduce的极大影响，应该并不为过。
• Resilient Distributed Datasets: A Fault-Tolerant Abstraction for In-Memory Cluster Computing (2012): 伯克利Spark集群技术项目背后的学术论文。Spark公开了RDD这种分布式内存抽象，是跨一个集群内存分布的不可变记录集合。RDD可以转换为使用MapReduce式的计算。RDD抽象对有强时间局部性的负荷（比如查询处理和迭代机器学习）效率可以提高几个数量级。Spark是一个很好的例子，说明了将MapReduce编程模型与执行引擎分离的重要性。
• Shark: SQL and Rich Analytics at Scale (2013): 描述了Shark系统，构建在Spark上的SQL引擎。这篇论文更重要的是讨论了为什么之前的SQL on Hadoop/MapReduce查询引擎都这么慢。
• Spanner (2012): Spanner是“可扩展、多版本、全球分布和同步复制的数据库”。其中关键是TrueTime API，那个在多个节点之间无需通信而为事件定序。有人猜测TrueTime API与向量钟类似，但每个节点必须存储较少数据。不幸的是，虽然Google说要发表关于TrueTime的论文，但现在还没看到。
• Dryad: Distributed Data-Parallel Programs from Sequential Building Blocks (2007): Dryad是微软开发的编程模型，支持大规模数据流编程。“MapReduce与Dryad的差异在于，Dryad应用可以指定任意的通信DAG，而不是非要用map/distribute/sort/reduce操作序列。”

趋势（云计算，仓库规模计算和新硬件）

• A View of Cloud Computing (2010): 关于云计算的权威论文。从技术角度讨论了云计算（主要指资源的弹性而不是面向消费者的“云”）的经济意义和阻碍因素。这些阻碍因素将影响云中系统的设计决策。
• The Datacenter as a Computer: An Introduction to the Design of Warehouse-Scale Machines: Google的Luiz André Barroso和Urs Hölzle解释了仓库规模技术中数据中心软硬件的基础知识。还有配套的视频（注：HighScalability有相应文章）讨论了在大规模并行系统中减少长尾延迟（long-tail latency）的重要性。其他的关键思想还包括资源的解聚（disaggregation）。GFS/HDFS这样的技术已经用高速网络带宽解聚了硬盘，但是DRAM还没有看到这种趋势，因为那需要低延迟联网。
• CAP Twelve Years Later: How the "Rules" Have Changed (2012): Eric Brewer提出的CAP定理指出，任何联网的共享数据系统都只能在一致性、可用性和分区容忍性三个属性中保证其中两个。许多NoSQL存储都用此为自己牺牲一致性的设计决策来辩解。此文是Eric Brewer回顾文章，解释了“‘三中取二’的表述是错误的，过度简化了各个属性之间的矛盾关系。”

杂项

• Reflections on Trusting Trust (1984): 1984年Ken Thompson的图灵奖演讲，描述了黑盒后门问题，指出了信任不是绝对的。

扩展阅读

许多学校都有针对研究生的数据库阅读列表

• Berkeley: http://www.eecs.berkeley.edu/GradAffairs/CS/Prelims/db.html
• Brown: http://www.cs.brown.edu/courses/cs227/papers.html
• Stanford: http://infolab.stanford.edu/db_pages/infoqual.html
• Wisconsin: http://www.cs.wisc.edu/sites/default/files/db.reading.pdf
• Joseph Hellerstein的Berkeley数据库研究生课程阅读列表，比本列表更全面