大数据必读文献

推荐人：张俊林

小编推荐：本文献是张俊林在写作《大数据日知录》时的整理的大数据必读文献，小编基本翻完了这本书，作者用心整理了大数据相关的算法和架构，并很好的把握了各个技术点的难易程度，是了解大数据技术全貌的较深科普类著作。而本文献则是大家学习进阶各个技术的重要参考。中国有句古话“师傅领进门，修行在个人”。读这本书只是进门，读这篇博文提供的参考文献并付诸实践则是每个技术人员的修行。

作者注：每章后参考文献是本书作者从大量文献中筛出的有较大理论创新的论文列表，或者有较大发展潜力及影响力的开源系统列表，完成本书所参阅文献量数倍于所列出者，之所以这样，目的在于汰劣余优，节省读者时间，在时间充裕情况下建议读者对每章后参考文献都能深入了解，为满足时间不足者之需，本着精中选优之原则，本附录列出了解大数据技术必读文献，并附上作者简评。一家之言，姑妄观之。

一致性

[1] L. Lamport. Paxos Made Simple. ACM SIGACT News (Distributed Computing Column),2001, 32(4): 51-58.

点评：Lamport因其对分布式理论做出的杰出贡献获得了2013年度图灵奖。在过去十年里，Paxos基本成为了分布式领域内一致性协议的代名词。Google的粗粒度锁服务Chubby的设计开发者Burrows曾经说过：“所有一致性协议本质上要么是Paxos要么是其变体”，Paxos是几乎所有相关课程必讲内容以及很多其它一致性协议的起点，Paxos的重要性由此可见一斑。另一方面，Paxos也以难以理解闻名，这篇论文是Lamport为了清晰解释Paxos基本原理而写的，相对直观易懂。

[2] D. Ongaro and J. Ousterhout. In Search of an Understandable Consensus Algorithm.Tech Report. 2013.

点评: 与Paxos协议不同，在达到类似的一致性功能前提下，Raft一致性协议的最主要目标有两个：首先是可理解性，在做技术决策和选型的时候，在达到相似功能前提下，首先以易于理解作为选型标准；其次是实现实际系统的确定性，Raft追求每个技术细节的清晰界定与描述，以此达到实现具体系统时的明确性。本论文介绍了Raft的内在运作机理细节，其清晰易理解的特性确实令人印象深刻。

Key-Value数据库

[1] G. DeCandia, D. Hastorun, M. Jampani, G. Kakulapati, A. Lakshman, A. Pilchin, S. Sivasubramanian, P. Vosshall, and W. Vogels. Dynamo: amazon's highly available key-value store. Proceedings of ACM symposium on Operating systems principles, 2007,pp: 205-220.

点评：Dynamo是最为经典的基于P2P的大规模分布式KV数据库，对于后续类似大数据存取系统的研发有具大影响力，诸如Cassandra、Riak、Voldemort等系统大量借鉴其设计思路。这篇论文是了解大数据存储系统必须熟读的文献，在其中引入了一致性哈希数据分片策略、反熵协议、Merkle树、向量时钟、Quorum-based一致性协议等诸多技术，尽管这些技术大多数在Dynamo之前即有，但是很少系统能够集如此众多经典技术于一炉并锻造出基于此的实用系统。基于P2P的大规模存储架构管理复杂性要远高于Master-Slave架构，对于其实用性尽管有争议，但是从技术角度，这篇论文有很多值得借鉴学习之处。

文档数据库

[1]Mongodb. http://www.mongodb.org/

点评：Mongodb目前是形形色色的所有NoSQL数据库中市场占有率最高的，这说明其使用场景的广泛性和其极高的受欢迎程度，熟悉了解其使用方法有助于很多情形下解决实际工作中的问题。

内存KV数据库

[1] J. Ousterhout et al. The Case for RAMClouds: Scalable High-Performance Storage Entirely in DRAM. ACM Special Interest Group on Operating Systems,, 2009.

点评：RAMCloud是非常有影响力的内存KV数据库，其整体架构比较简洁，内存保留一份数据将备份数据存储在外存的策略能较好地在成本和性能间获得平衡，不过其高可用性设计方案存在较大缺陷。相对而言，Membase是设计较为完善的内存KV数据库，可惜其技术资料较少。

[2] Redis. http://redis.io/

点评：作为工业界最广泛使用的内存KV数据库，Redis因其极高的单机读写效率以及能支持灵活复杂的键值数据结构而广受欢迎。但是考虑到分布式架构设计，比如数据分片及高可用方案，Redis不仅在此方面进展缓慢，同时其设计方案显得乏善可陈，甚至可以说不甚优雅，这也许跟作者更关注并保证系统的读写效率有关。

分布式文件系统

[1] S. Ghemawat, H. Gobioff and S.T. Leung. The Google File System. 19th ACM Symposium on Operating Systems Principles,2003.

点评： GFS是Google公司为了能够存储以百亿计的海量网页信息而专门开发的文件系统。在Google的整个大数据存储与处理技术框架中，GFS是其它相关技术的基石，因为GFS提供了海量非结构化信息的存储平台，并提供了数据的冗余备份、成千台服务器的自动负载均衡以及失效服务器检测等各种完备的分布式存储功能。同时GFS对于后来的大数据技术发展潮流有极为巨大的影响和推动作用，仿制GFS和Mapreduce的Hadoop获得广泛流行应该说是引发大数据技术大爆发的源头之一。

[2] D. Beaver, S. Kumar, H.C. Li, J. Sobel and P. Vajgel. Finding a Needle in Haystack: Facebook’s  Photo Storage. The 7th USENIX Symposium on Operating Systems Design and Implementation,2010.

点评：Haystack是Facebook公司设计开发的一种“对象存储系统”，这里的“对象”主要指用户上传的图片数据。大型商业互联网公司对于类似于Haystack这种“对象存储系统”有很大的需求，这里的“对象”往往指满足一定性质的媒体类型，类似于图片数据的存储有其自身特点，典型的特征是：一次写入，多次读取，从不更改，很少删除。很多其他类型的数据也有此种特点，比如邮件附件、视频文件以及音频文件等等，一般将这种数据称为“Blob数据”，对应的存储可以称为“Blob存储系统”。因为其特点是读多改少，所以在设计这种存储系统的时候，保证读取效率是需要重点考虑的要素。目前国内的淘宝和腾讯等大型互联网公司也独立开发了类似的存储系统，其实现思路应该与Haystack系统差异不大。

Erasure Code

[1] J. S.  Plank. A Tutorial on Reed-Solomon Coding for Fault-Tolerance in RAID-like Systems, Technical Report,1996.

点评：为了增加存储系统的可靠性和数据的可用性，经常使用数据备份来达到这一点，工业界通常的做法是对数据做三备份。但是数据备份带来的缺点是明显增加存储成本。纠删码可以缓解这种情况，通过增加部分数据冗余而非多备份来获得数据的可靠存储，目前很多实际的大数据存储系统都采取了多备份和纠删码相结合的技术方案，热点数据仍然采取多备份，长尾冷门数据采取纠删码。Reed-Solomon编码是最常用的纠删码，比如Google的GFS第二代系统Colossus以及Facebook的HDFS-RAID都是采用RS编码，本论文非常通俗易懂地介绍了RS编码的原理和实现机制。

[2] M. Sathiamoorthy  etc. XORing Elephants: Novel Erasure Codes for Big Data . In 39th International Conference on Very Large Data Bases (VLDB), 2013.

点评：在分布式数据存储应用环境下，RS编码有其固有缺陷：在恢复少量毁损数据块时，需要大量的网络传输来获得所有其它数据块，很容易导致网络带宽阻塞。LRC的提出就是为了解决这一难题，LRC能够在可靠性与RS码大致相同的情况下，减少恢复损毁数据所需的数据块数量，也就缓解了网络传输过多的问题。本论文就是Facebook的研发人员提出的一个典型的LRC编码，除此外，微软的AWS云存储系统也采取了类似的思路。

列式数据库

[1] F. Chang, J. Dean, S. Ghemawat, W. C. Hsieh, D. A. Wallach, M. Burrows, T. Chandra, A. Fikes, and R. E. Gruber. Bigtable: A distributed storage system for structured data. ACM Transaction on Computing System, 2008,26(2):1-26.

点评：BigTable是一种针对海量结构化或者半结构化数据的存储模型，在Google的云存储体系中处于核心地位，起到了承上启下的作用。GFS是一个分布式海量文件管理系统，对于数据格式没有任何假定，而BigTable以GFS为基础，建立了数据的结构化解释，对于很多实际应用来说，数据都是有一定格式的，在应用开发者看来，BigTable建立的数据模型与应用更贴近。MegaStore存储模型、Percolator计算模型都是建立在BigTable之上的存储和计算模型。从此可看出，BigTable在其中的地位之重要。

[2]Cassandra. http://cassandra.apache.org/

点评：Cassandra在数据模型方面采取了类似Bigtable的方案，而在底层架构则采取了P2P模式，同时大量吸取了Dynamo系统中的设计方案，比如DHT结构、Merkle Tree结合Gossip协议实现数据副本一致性、反熵协议实现P2P集群管理等，另外还采纳了增量故障检测机制（Accrual Failure Detectors）等。如果结合Bigtable、Dynamo等论文来分析Cassandra的源码实现，对于深入理解很多经典的分布式设计方案有很大帮助作用。

[3] C. J. Corbett, J. Dean etc. Spanner: Google's Globally-Distributed Database. 10th USENIX Symposium on Operating Systems Design and Implementation , 2012.

点评： Spanner是Google开发的可全球范围部署的具有极强可扩展性的列式数据库系统。其可以将千亿规模的数据自动部署到世界范围数百个数据中心中的百万台服务器中，通过细粒度的数据备份机制极大增强了数据的可用性以及地理分布上的数据局部性，Spanner具备数据中心级别的容灾能力，即使整个数据中心完全遭到破坏也可以保证数据的可用性。除此外，Spanner还具备接近于传统数据库关系模型的半结构化数据模型定义、类SQL查询语言以及完善的事务支持等特性。应该说Spanner使得NoSQL数据库的处理能力达到了史无前例的高度。

数据通道

[1] Databus: LinkedIn's Change Data Capture Pipeline. SOCC 2012.

http://www.slideshare.net/ShirshankaDas/databus-socc-2012

点评：数据总线的作用就是能够形成数据变化通知通道，当集中存储的数据源（往往是关系数据库）的数据发生变化时，能尽快通知对数据变化敏感的相关应用或者系统构件，使得它们尽快捕获这种数据变化。Linkedin的Databus是一个典型且相对完善的数据总线系统，其提供了近实时性捕获数据变化、数据回溯能力以及主题订阅能力。

协调系统

[1] M. Burrows. The chubby lock service for loosely-coupled distributed systems. In OSDI '06: Proceedings of the 7th symposium on Operating systems design and implementation, 2006,pp: 335-350.

点评：Chubby作为粗粒度锁服务，在Google的GFS、Bigtable等各种超大规模存储系统中都起到了关键的系统协调作用，其也是引发Zookeeper等著名开源协调系统的重要因素，尽管两者在设计思路上还是有较大区别。

[2] P. Hunt, M. Konar, F. P. Junqueira and B. Reed.  ZooKeeper: Wait-free coordination for Internet-scale systems. In USENIX Annual Technical Conference,2011.

点评：Zookeeper作为最著名的开源协调系统，已经在各种应用和大数据系统中获得了非常广泛的使用。其有很多应用的成功设计案例及丰富的相关文档，当设计分布式系统时，如果有领导者选举、配置管理、组成员管理、锁机制等协调功能时，可以优先考虑使用Zookeeper来作为协调系统实现方案。

调度系统

[1] V. K. Vavilapalli etc.  Apache Hadoop YARN: Yet Another Resource Negotiator. ACM Symposium on Cloud Computing, 2013.

点评：YARN是Hadoop2.0的重要组成部分，也被称作MRV2，其全称是“另一个资源协调器”（Yet Another Resource Negotiator），顾名思义，其是一个独立的资源管理系统。MRV2与MRV1相比，最大的改变就是抽象出YARN这个独立资源调度系统。从资源管理系统范型来说，YARN同Mesos一样，是个典型的两级调度器。与Mesos比较，由于Hadoop的广泛流行，再加上YARN代表了Hadoop的未来发展趋势，所以相比而言更活跃，发展前景更乐观。目前已经有很多大数据计算框架已经移植到YARN平台下，比如MR，流式计算系统Storm和Samza，图计算系统Giraph，DAG计算系统Tez等等，相信越来越多计算框架会逐步移植到YARN上，使得YARN成为一个名符其实的支持多种大数据计算框架的基础资源管理平台。

[2] M. Schwarzkopf, A. Konwinski, M. A. Malek and J. Wilkes. Omega: flexible, scalable schedulers for large compute clusters. In Proceedings of the 8th ACM European Conference on Computer Systems,2013,pp: 351–364.

点评：Omega是Google开发的内部集群资源管理与调度系统，在本论文中其提出了一种新型的资源调度方案：状态共享调度器。在这种调度范型中，每个计算框架可以看到整个集群中的所有资源，并采用相互竞争的方式去获取自己所需资源，根据自身特性采取不同的具体资源调度策略，同时系统采用了乐观并发控制手段解决不同框架在资源竞争过程中出现的需求冲突。除此外，本论文还对目前的资源调度系统做了整体分类并对每类的特点做了分析，这对宏观掌握资源调度系统设计策略有很大帮助作用。

消息系统

[1] Apache Kafka. http://kafka.apache.org/documentation.html#design

点评：Kafka是Linkedin开源的pub-sub模式消息系统，尽管最初的设计初衷是Log收集，由于其出色的消息吞吐能力、低延时、高可扩展性、高可用性等诸多能力，目前其使用范围已经大为扩展，甚至可以作为流式计算系统Samza的底层架构。Kafka整体架构设计简洁优雅，也有很多创新点，利用Zookeeper结合文件系统来设计高吞吐、低延迟、高扩展、高可用的消息系统也是独具特色的。除此外，Kafka的设计文档对于如何高效使用磁盘读写以及对操作系统缓存的高效利用的讨论也使人获益匪浅。总而言之，Kafka是掌握大数据系统设计过程中，对很多普适规律如何灵活运用的经典范型之一。

批处理系统

[1] J. Dean and S. Ghemawat. MapReduce: simplified data processing on large clusters. Sixth Symposium on Operating Systems Design and Implementation, 2004.

点评：MapReduce作为当前最典型的大数据批处理计算模型，已经在工业界获得了极为广泛的使用。Google的这篇发表于2004年的论文对整个大数据系统的发展具有至关重要的作用，其与2003年发表的GFS论文是催生Hadoop的直接范型。尽管09年左右以Stone Braker为首的并行数据库领域专家对MR模型提出质疑并引发和Jaffrey Dean等人的技术争论，但是最终的结论是MR和MPP各自有优略且两者有一定互补和相互学习之处。与传统的MPP相比，MR更适合非结构化数据的ETL处理类操作且其可扩展性及容错性明显占优，但是单机处理效率较低。尽管MR提供了简洁的编程接口及完善的容错处理机制，使得大规模并发处理海量数据成为可能，但从发展趋势看，相对复杂的任务转换为MR任务开发效率还是不够高，所以其有逐步被封装到下层的趋势，即在上层系统提供更为简洁方便的应用开发接口，在底层由系统自动转换为大量MR任务，这一点值得关注。

[2] M. Isard, S. V. Mihai etc. Dryad: Distributed Data-Parallel Programs from Sequential Building Blocks. ACM SIGOPS in Europe EuroSys, 2007.

点评：Dryad是大数据批处理领域较早明确提出DAG计算范型的系统。在批处理应用环境下，DAG计算模型在表达能力方面明显强于MapReduce模型，后者基本可以被视为前者的一种特例，当然随之也带来了学习和应用成本高的缺点。从这篇论文可以归纳出构建通用DAG计算系统的三层结构：最上层是DAG应用表达层，其重点在于表达便捷性和开发友好性；中间层是DAG执行引擎层，其负责将表达层内容转换映射为分布式任务，并管理控制这些任务运行在最底层的物理集群中。

流式计算

[1]N. Marz. Twitter storm. https://github.com/nathanmarz/storm/wiki,2012

点评: 流式计算是一个越来越受到重视的计算领域，很多应用场景对于大数据处理的计算时效性要求很高，要求计算能够在非常短的时延内完成，这种应用场景就是能够最好发挥流式计算系统威力的场合。目前涌现出不少流式计算系统，比如S4、Storm、Samza、D-Stream 、MUPD8等等，Storm作为其中最具代表性的流式计算系统，无论是从系统完善性还是使用广泛性来说都是非常突出的，非常值得关注。

[2] T.Akidau, A. Balikov, K. Bekir, S. Chernyak, J. Haberman, R. Lax, S. McVeety, D. Mills, P. Nordstrom and S. Whittle. MillWheel: Fault-Tolerant Stream Processing at Internet Scale. In Very Large Database Conference, 2013.

点评：MillWheel作为Google内部使用的流式计算系统，虽然并未开源，但是与Storm一样，其整个系统在处理的低延迟、容错性、可扩展性以及应用表达能力方面在现有各种流式计算系统中都算非常优秀的，这篇论文有助于从系统架构方面了解如何设计一个符合实际应用需求特点的典型流式计算系统。

SQL-On-Hadoop

[1] A. Thusoo, J. S. Sarma, N. Jain, Z. Shao, P. Chakka, N. Zhang, S. Anthony, H. Liu and R. Murthy. Hive - a petabyte scale data warehouse using Hadoop. In International Conference on Data Engineering, 2010, pp: 996-1005.

点评：Hive作为最早的SQL-On-Hadoop系统之一，目前已经获得了广泛使用。尽管其执行引擎采用MR机制导致查询性能较低，且有被其它采用MPP并行数据库思路的系统替代的可能，但是鉴于其对于后续SQL-On-Hadoop系统的影响力，为了深入了解这类系统的发展脉络，其体系结构还是非常值得仔细研究的。

[2] S. Melnik, A. Gubarev, J. J. Long, G. Romer, S. Shivakumar, M. Tolton, and T. Vassilakis. Dremel: interactive analysis of web-scale datasets. Communication of ACM, 2011,54(6):114–123.

点评：Dremel被称为Google的“新三驾马车”之一，其整体设计思路对于目前众多开源SQL-On-Hadoop系统有重大影响，Drill、Impala、Presto等系统整体上借鉴了其设计思路，实践也表明其采用的嵌套数据列式存储、树形服务器架构布局及MPP并行数据库执行引擎是这类系统提升性能的关键因素。

[3]Impala. https://github.com/cloudera/impala

点评：Impala可以看作是Dremel的开源版本，并在其基础上做出了部分创新性改进，从目前可见的评测来看，其也是在各种大小数据集下性能最好的开源SQL-On-Hadoop系统之一，是该类系统中最有发展潜力的系统，其体系架构甚至代码都值得深入了解。

图数据库

[1] G. Malewicz, M.H. Austern, A.J. Bik, J. Dehnert, I. Horn,N. Leiser, and G.Czajkowski,  Pregel: a system for large-scale graph processing. In 2010 SIGMOD Conference,2010.

点评： Pregel是Google提出的遵循BSP模型的大规模分布式图计算平台，专门用来解决网页链接分析、社交数据挖掘等实际应用中涉及到的大规模分布式图计算问题。其是一个消息驱动的、遵循以图节点为中心的编程模型的同步图计算框架，对于很多开源图计算系统比如Giraph、Hama以及后续的改进图计算系统都有非常大的影响。

[2] J.E. Gonzalez, Y. Low, H. Gu, D. Bickson, C. Guestrin,  Powergraph: Dis- tributed graph-parallel computation on natural graphs. In Proceedings of the 10^th USENIX Symposium on Operating Systems Design and Implementation,2012.

点评： PowerGraph是一个非常值得关注的离线挖掘类图计算系统，其无论在图计算的理论分析方面还是实际系统实施方面都达到了相当的高度，实际效果也表明PowerGraph基本上是目前主流图计算系统里效率最高的，同时PowerGraph还是个灵活的图计算架构，既可以模拟同步计算模型也可以模拟异步计算模型。

分布式机器学习

[1] W. Dai, J. Wei, X. Zheng, J. K. Kim, S. Lee, J. Yin, Q. Ho, E. P. Xing.  Petuum: A Framework for Iterative-Convergent Distributed ML.2013, arXiv:1312.7651.

点评： 参数服务器是实现分布式机器学习算法的一种典型架构，目前很多研究集中在这个方向，比如Google能够处理百亿参数规模的深度机器学习框架DistBelief就是此种架构。从本质上讲，可以将参数服务器看作是传统共享内存方式在网络环境下的并行扩展版本。Petuum是CMU提出的通用参数服务器架构，其由众多并发执行的带有参数缓存的客户端和由多台保存全局参数的参数服务器集群构成。对于很多迭代类机器学习算法，利用Petuum既可以保证算法正确性也可以快速地处理海量数据。学习这篇论文有助于对参数服务器的宏观架构设计中面临的问题及较通用的解决方案有较深入全面的了解。

[2] M. Zaharia etc. Resilient Distributed Datasets: A Fault-Tolerant Abstraction for In-Memory Cluster Computing,2011, UCB/EECS-2011-82.

点评： Spark大数据处理协议栈是AMPLab实验室推出的一套与Hadoop2.0功能类似的完善处理各种大数据应用的整体解决方案，其最核心的部分是适合解决迭代式机器学习类问题的DAG批处理系统Spark，在此基础上，逐渐在其上层开发出流式计算系统D-Stream、图计算系统GraphX、机器学习库MLlib以及MLBase等适用于不同场景的子系统，遂形成了一整套大数据处理技术方案。本篇论文即讲解DAG批处理系统Spark的设计思路与原理的论文，Spark针对工作集数据提出了基于内存的分布式存储抽象模型：可恢复分布式数据集（Resilient Distributed Datasets，简称RDD），这样工作集数据可以有选择性地被加载并常驻在内存中，有利于后续迭代计算过程，大大提升迭代类机器学习类问题的处理效率。Spark是集成了RDD模型的DAG批处理系统，它在RDD增加数据复用与系统处理速度的优势基础上，同时还具备传统DAG系统的很强的容错性、数据局部性感知的调度策略以及高可扩展性。虽然Spark具有学习成本高的缺点，但是发展潜力较大，很可能会成为解决迭代式机器学习领域问题的标准工具。

[3] R. Bekkerman ,M. Bilenko and J. Langford . Scaling Up Machine Learning: Parallel and Distributed Approaches. 2012, Cambridge University Press.

点评：这是一本有关分布式机器学习的论文集，集中介绍了基于MPI、GPU、MapReduce、Dyrad等各种不同分布式计算泛型下的诸多常见及前沿机器学习算法的并行版本，对于全面系统了解分布式机器学习架构与算法有很大帮助作用。

Report Story