订阅业界RSS CSDN首页> 业界

PayPal高级工程总监:读完这100篇论文 就能成大数据高手

发表于2015-07-07 09:25| 次阅读| 来源LinkeDin| 0 条评论| 作者Anil Madan

摘要:PayPal高级工程总监Anil Madan写了篇大数据的文章,近日CSDN对此进行了翻译。一共有100篇大数据的论文,涵盖大数据技术栈,全部读懂你将会是大数据的顶级高手。

数据存储层

宽泛地讲,据对一致性(consistency)要求的强弱不同,分布式数据存储策略,可分为ACID和BASE两大阵营。ACID是指数据库事务具有的四个特性:原子性(Atomicity)、一致性(Consistency)、隔离性(Isolation)、持久性(Durability)。ACID中的一致性要求比较强,事务执行的结果必须是使数据库从一个一致性状态变到另一个一致性状态。而BASE对一致性要求较弱,它的三个特征分别是:基本可用(Basically Available), 软状态/柔性事务(Soft-state,即状态可以有一段时间的不同步), 最终一致性(Eventual consistency)。BASE还进一步细分基于键值的,基于文档的和基于列和图形的 – 细分的依据取决于底层架构和所支持的数据结构(注:BASE完全不同于ACID模型,它以牺牲强一致性,获得基本可用性和柔性可靠性,并要求达到最终一致性)。

在数据存储层,还有很多类似的系统和某些系统的变种,这里,我仅仅列出较为出名的几个。如漏掉某些重要系统,还请谅解。

BASE

键值存储(Key Value Stores)

Dynamo29】– 这是由亚马逊工程师们设计的基于键值的高可用的分布式存储系统(注:Dynamo放弃了数据建模的能力,所有的数据对象采用最简单的Key-value模型存储,可简单地将Dynamo理解为一个巨大的Map。Dynamo是牺牲了部分一致性,来换取整个系统的高可用性)。

Cassandra30】 – 这是由Facebook工程师设计的一个离散的分布式结构化存储系统,受亚马逊的Dynamo启发,Cassandra采用的是面向多维的键值或面向列的数据存储格式(注:Cassandra可用来管理分布在大量廉价服务器上的巨量结构化数据,并同时提供没有单点故障的高可用服务)。

Voldemort31】 –这又是一个受亚马逊的Dynamo启发的分布式存储作品,由全球最大的职业社交网站LinkedIn的工程师们开发而成(注:Voldemort,这个在《哈利·波特》中常被译作“伏地魔”的开源数据库,支撑起了LinkedIn的多种数据分析平台)。

面向列的存储(Column Oriented Stores)

BigTable32】 –这是一篇非常经典的学术论文,阐述了面向列的分布式的数据存储方案,由谷歌荣誉出品。(注:Bigtable是一个基于Google文件系统的分布式数据存储系统,是为谷歌打拼天下的“三驾马车”之一,另外两驾马车分别是分布式锁服务系统Chubby和下文将提到的MapReduce)。

HBase33】 –目前还没有有关Hbase的定义性论文,这里的文献提供了一个有关HBase技术的概述性文档(注:Hbase是一个分布式的、面向列的开源数据库。其设计理念源自谷歌的 BigTable,用Java语言编写而成。文献【33】是一个有关Hbase的幻灯片文档)。

Hypertable34】-文献是一个有关“Hypertable”的技术白皮书,对该数据存储结构做了较为详细的介绍(注:Hypertable也是一个开源、高性能、可伸缩的数据库,它采用与Google的Bigtable类似的模型)。

面向文档的存储(Document Oriented Stores)

CouchDB35】– 这是一款面向文档的、开源数据存储管理系统(注:文献【35】是一本Apache CouchDB的400多页的官方文档)。

MongoDB36】 –是目前非常流行的一种非关系型(NoSQL)数据库(注:文献【36】是一个有关MongoDB的白皮书,对MongoDB结构做了很不错的介绍)。

面向图(Graph)的存储

Neo4j37】 –文献是Ian Robinson等撰写的图书《Graph Databases(图数据库)》(注:Neo4j是一款目前最为流行的高性能NoSQL 图数据库,它使用图来描述数据模型,把数据保存为图中的节点以及节点之间的关系。这是最流行的图数据库)。

Titan38】 –文献是有关Titan的在线文档(Titan是一款Apache许可证框架下的分布式的开源图数据库,特别为存储和处理大规模图而做了大量优化)。

ACID

我注意到,现在很多开源社区正在悄悄发生变化,它们开始“亦步亦趋”地跟随谷歌的脚步。这也难怪,谷歌太牛,跟牛人混,近牛者牛 —— 下面4篇文献,有3篇来自于谷歌的“神来之笔”,他们解决了全球分布一致的数据存储问题。

Megastore39】 –这是一个构建于BigTable之上的、高可用的分布式存储系统,文献为有关Megastore的技术白皮书(注:Megastore在被谷歌使用了数年之后,相关技术信息才在2001年公布。CSDN网站亦有文献【39】的中文解读:Google Megastore分布式存储技术全揭秘)。

Spanner40】–这是由谷歌研发的、可扩展的、全球分布式的、同步复制数据库,支持SQL查询访问。(注:Spanner的“老爹”是Big Table,可以说,没有“大表”这个爹,就不可能有这个强有力的“扳手” 儿子。它是第一个把数据分布在全球范围内的系统,并且支持外部一致性的分布式事务)。

MESA41】–亦是由谷歌研发的、跨地域复制(geo-replicated)、高可用的、可容错的、可扩展的近实时数据仓库系统(注:在2014年的VLDB 大会上,谷歌公布了他们的分析型数据仓库系统MESA,该系统主要用于存储Google互联网广告业务相关的关键衡量数据。文献【41】是VLDB的会议论文)。

CockroachDB42】–该系统是由Google前工程师Spencer Kimball领导开发的Spanner 的开源版本(注:这个项目的绰号是“螳螂(Cockroach)”,其寓意是“活得长久”,因为蟑螂是地球上生命力最强的生物之一,即使被砍下头颅,依然还能存活好几天!文献【42】是代码托管网站GitHub上对Cockroach的说明性文档)。

资源管理器层(Resource Managers)

第一代Hadoop的生态系统,其资源管理是以整体单一的调度器起家的,其代表作品为YARN。而当前的调度器则是朝着分层调度的方向演进(Mesos则是这个方向的代表作),这种分层的调度方式,可以管理不同类型的计算工作负载,从而可获取更高的资源利用率和调度效率。

YARN43】– 这是新一代的MapReduce计算框架,简称MRv2,它是在第一代MapReduce的基础上演变而来的(注:MRv2的设计初衷是,为了解决第一代Hadoop系统扩展性差、不支持多计算框架等问题。对国内用户而言,原文献下载链接可能会产生404错误,这里提供一个新文献:由2011年剥离自雅虎的Hadoop初创公司Hortonworks给出的官方文献43】new,阅读该文献也可对YARN有较为深入的理解。CSDN亦有对YARN详细解读的文章:更快、更强——解析Hadoop新一代MapReduce框架Yarn)。

Mesos44】–这是一个开源的计算框架,可对多集群中的资源做弹性管理(注:Mesos诞生于UC Berkeley的一个研究项目,现为Apache旗下的一个开源项目,它是一个全局资源调度器。目前Twitter、 Apple等国外大公司正在使用Mesos管理集群资源,国内用户有豆瓣等。文献【44】是加州大学伯克利分校的研究人员发表于著名会议NSDI上的学术论文)。

这些计算框架和调度器之间是松散耦合的,调度器的主要功能就是基于一定的调度策略和调度配置,完成作业调度,以达到工作负载均衡,使有限的资源有较高的利用率。

调度器(Schedulers)

作业调度器,通常以插件的方式加载于计算框架之上,常见的作业调度器有4种:

计算能力调度器45】Capacity Scheduler)-该文献是一个关于计算能力调度器的指南式文档,介绍了计算能力调度器的不同特性。

公平调度器46】(FairShare Scheduler) -该文献是Hadoop的公平调度器设计文档,介绍了公平调度的各项特征(注:公平调度是一种赋予作业资源的方法,它提供了一个基于任务数的负载均衡机制,其目的是让所有的作业随着时间的推移,都能平均的获取等同的共享资源)。

延迟调度47】(Delayed Scheduling) –该文献是加州大学伯克利分校的一份技术报告,报告介绍了公平调度器的延迟调度策略。

公平与能力调度器48】(Fair & Capacity schedulers )–该文献是一篇关于云环境下的Hadoop调度器的综述性论文。

协调器(Coordination)

在分布式数据系统中,协调器主要用于协调服务和进行状态管理。

Paxos49】 –文献【49】是经典论文“The Part-Time Parliament(兼职议会50】” 的简化版。

注:两篇文献的作者均是莱斯利·兰伯特(Leslie Lamport),此君是个传奇人物,科技论文写作常用编辑器LaTex,其中“La”就是来自其姓“Lamport”的前两个字母。Lamport目前是微软研究院首席研究员,2013年,因其在分布式计算理论领域做出的杰出贡献,荣获计算机领域最高奖——图灵奖。

牛人的故事特别多,Lamport亦是这样。就这两篇文献而言,Lamport的奇闻轶事都值得说道说道。光看其经典论文题目The Part-Time Parliament(兼职的议会50】”,或许就让读者“一头雾水”,这是一篇计算机科学领域的论文吗?和读者一样感觉的可能还有期刊编辑。其实,早在1990年时,Lamport就提出Paxos算法,他虚构了一个希腊城邦Paxos及其议会,以此来形象比喻说明该算法的流程。论文投出后,期刊编辑建议Lamport,将论文用更加严谨的数学语言重新进行描述一下。可Lamport则认为,我的幽默,你不懂!拒绝修改。时隔八年之后的 1998年,Paxos算法才被伯乐期刊《ACM Transactions on Computer Systems》发表。由于Paxos算法本身过于复杂,且同行不理解自己的“幽默”, 于是,2001年Lamport就用简易语言撰写这篇文章,重新发表了该论文的简化版49】,即“Paxos made simple(Paxos变得简单)”。简化版的摘要更简单,就一句话:“Paxos算法,用简易英语说明之,很简单”,如果去掉中间的那个无故紧要的定语从句,就是“Paxos算法,很简单”。弄得你都来不及做深思状,摘要就完了。这…,这…,完全颠覆了我们常用的“三段论式(提问题、解问题、给结论)”的论文摘要写法啊。

后来,随着分布式系统的不断发展壮大,Paxos算法开始大显神威。Google的Chubby和Apache的Zookeeper,都是用Paxos作为其理论基础实现的。就这样, Paxos终于登上大雅之堂,它也为Lamport在2013年获得图灵奖,立下汗马功劳。从Lamport发表Paxos算法的小案例,我们可以看出:彪悍的人生,不需要解释。牛逼的论文,就可以任性!

Chubby51】– 该文献的作者是谷歌工程师Mike Burrows。Chubby系统本质上就是前文提到的Paxos的一个实现版本,主要用于谷歌分布式锁服务。(注:原文链接会出现404错误,CSDN网站有Chubby论文的下载链接)。

Zookeeper52】 –这是Apache Hadoop框架下的Chubby开源版本。它不仅仅提供简单地上锁服务,而事实上,它还是一个通用的分布式协调器,其设计灵感来自谷歌的Chubby(注:众所周知,分布式协调服务开发困难很大,分布式系统中的多进程间很容易发生条件竞争和死锁。ZooKeeper的开发动力就是减轻分布式应用开发的困难,使用户不必从零开始构建协调服务)。

计算框架(Computational Frameworks)

运行时计算框架,可为不同种类的计算,提供运行时(runtime)环境。最常用的是运行时计算框架是Spark和Flink。

Spark53】 –因Spark日益普及,加之其具备良好的多计算环境的适用性,它已对传统的Hadoop生态环境,形成了严峻的挑战(注:Spark是一个基于内存计算的开源的集群计算系统,其目的在于,让数据分析更加快速。Spark是由加州大学伯克利分校的AMP实验室采用Scala语言开发而成。Spark的内存计算框架,适合各种迭代算法和交互式数据分析,能够提升大数据处理的实时性和准确性,现已逐渐获得很多企业的支持,如阿里巴巴、百度、网易、英特尔等公司均是其用户)。

Flink54】 –这是一个非常类似于Spark的计算框架,但在迭代式数据处理上,比Spark更给力(注:目前大数据分析引擎Flink,已升级成为Apache顶级项目)。

Spark和Flink都属于基础性的大数据处理引擎。具体的计算框架,大体上,可根据采用的模型及延迟的处理不同,来进行分门别类。

批处理(Batch)

MapReduce55】– 这是谷歌有关MapReduce的最早的学术论文(注:对于国内用户,点击原文献链接可能会产生404错误,CSDN网站有MapReduce论文的下载链接)。

MapReduce综述56】 –这是一篇过时、但依然值得一读的、有关MapReduce计算框架的综述性文章。

迭代式(BSP)

Pregel57】–这又是一篇谷歌出品的大手笔论文,主要描述了大规模图处理方法(注:Pregel是一种面向图算法的分布式编程框架,其采用的是迭代式的计算模型。它被称之为Google后Hadoop时代的新“三驾马车”之一。另外两驾马车分别是:“交互式”大数据分析系统Dremel和网络搜索引擎Caffeine)。

Giraph58】 – 该系统建模于谷歌的Pregel,可视为Pregel的开源版本,它是一个基于 Hadoop架构的、可扩展的分布式迭代图处理系统。

GraphX59】 –这是一个同时采用图并行计算和数据并行的计算框架(注:GraphX最先是加州大学伯克利分校AMPLab实验室的一个分布式图计算框架项目,后来整合到Spark中,成为其中的一个核心组件。GraphX最大的贡献在于,在Spark之上提供一栈式数据解决方案,可方便高效地完成图计算的一整套流水作业)。

Hama60】– 是一个构建Hadoop之上的基于BSP模型的分布式计算引擎(注:

Hama的运行环境需要关联 Zookeeper、HBase、HDFS 组件。Hama中最关键的技术,就是采用了BSP模型(Bulk Synchronous Parallel,即整体同步并行计算模型,又名大同步模型)。BSP模型是哈佛大学的计算机科学家Viliant和牛津大学的BillMcColl在1990年联合提出的,他们希望能像冯·诺伊曼体系结构那样,架起计算机程序语言和体系结构间的桥梁,故又称作桥模型(Bridge Model)。

开源处理系统61】Open source graph processing )-这是滑铁卢大学的研究人员撰写的综述性文献,文献【61】对类Pregel(Pregel-like)的、基于BSP模型的图处理系统进行了实验性的比较。