返回 登录
0

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

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

基础与算法

关系数据库

经典的系统设计

列式数据库

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

数据并行计算

  • 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回顾文章,解释了“‘三中取二’的表述是错误的,过度简化了各个属性之间的矛盾关系。”

杂项

扩展阅读

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

  • 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数据库研究生课程阅读列表,比本列表更全面
评论