专栏首页CSDN技术头条那些必读的数据库领域论文

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

之前林仕鼎曾整理过系统架构领域的学习资料,这几天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数据库研究生课程阅读列表,比本列表更全面

本文分享自微信公众号 - CSDN技术头条(CSDN_Tech)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2014-09-01

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 解密最接近人脑的智能学习机器 ——深度学习及并行化实现

    训练深层模型是长期以来的难题,近年来以层次化、逐层初始化为代表的一系列方法的提出给训练深层模型带来了希望,并在多个应用领域获得了成功。深层模型的并行化框架和训练...

    CSDN技术头条
  • 那些高级运维工程师,都是怎么给公司省机器的?

    随着项目用户量的快速增长,前期可能由于应用程序设计、数据库设计及架构不当,大多项目会在用户量百万、日志/流水等表过千万、乃至过亿时,出现写入卡顿、查询缓慢、各种...

    CSDN技术头条
  • 五个小技巧告诉你如何保护MySQL数据仓库

    汇总各种来源的数据,可以创建一个中央仓库。通过分析和汇总业务数据报告,数据仓库能够帮助企业做出明智、战略性的决策分析。虽然数据仓库提供了许多便利,但是把这些敏感...

    CSDN技术头条
  • 比较全面的3D数据处理建模等链接收集

    点云PCL博主
  • 干货!MySql DAL中间件总结

    mysql作为互联网公司都会用到的数据库,如果在使用过程中出现性能问题,会采用mysql的横向扩展,使用主从复制来提高读性能,要是解决写入问题,需要进行分库分表...

    小小科
  • 干货!MySql DAL中间件总结

    mysql作为互联网公司都会用到的数据库,如果在使用过程中出现性能问题,会采用mysql的横向扩展,使用主从复制来提高读性能,要是解决写入问题,需要进行分库分表...

    民工哥
  • 使用k3s 恢复数据库(前提有完整的数据库数据文件)

    前几天在部署k3s相关服务时,不小心把操作系统整坏了。导致无法启动,磁盘上还有我的一些重要数据。

    兜兜毛毛
  • es6新特性分享

    1、字符串查找 es5使用是indexOf() 返回字符第一次出现的位置int值 es6新增了3个方法:includes()/startsWith()/endW...

    Java中文社群_老王
  • MySQL数据库——数据库的基本概念及MySQL的安装步骤与基本使用

    数据库,DataBase,简称为DB,数据库就是用于存储和管理数据的仓库,其特点是:

    Winter_world
  • JDBC访问MySQL数据库踩坑

    作为一个 Android 开发者,闲来无事,想着使用 JSP + Servlet 写一些简单的接口,然后通过前端调用接口,后端的数据库使用的是 MySQL。

    IT大飞说

扫码关注云+社区

领取腾讯云代金券