孙荣辛|大数据穿针引线进阶必看——Google经典大数据知识

  • 2022 年 11 月 8 日
  • 筆記

大数据技术的发展是一个非常典型的技术工程的发展过程,荣辛通过对于谷歌经典论文的盘点,希望可以帮助工程师们看到技术的探索、选择过程,以及最终历史告诉我们什么是正确的选择。

何为大数据

 

“大数据”这个名字流行起来到现在,差不多已经有十年时间了。在这十年里,不同的人都按照自己的需要给大数据编出了自己的解释。有些解释很具体,来自于一线写 Java 代码的工程师,说用 Hadoop 处理数据就是大数据;有些解释很高大上,来自于市场上靠发明大词儿为生的演说家,说我们能采集和处理全量的数据就是大数据,如果只能采集到部分数据,或者处理的时候要对数据进行采样,那就不是大数据。

在笔者看来,其实“大数据”技术的核心理念是非常清晰的,基本上可以被三个核心技术理念概括。

  • 服务器规模:能够伸缩到一千台服务器以上的分布式数据处理集群的技术。

  • 服务器架构:这个上千个节点的集群,是采用廉价的 PC 架构搭建起来的。

  • 编程模式:“把数据中心当作是一台计算机”(Datacenter as a Computer)。

 

触发问题 大数据技术 传统数据处理技术 解决的问题
服务器规模 千台服务器以上 几十台服务器 可行性
服务器架构 普通x86服务器,普通硬盘 专用硬件,如大型机、小型机 性价比
编程模型 Datacenter as a Computer 使用方自己处理分布式和容错问题 复杂性

 

大型集群让处理海量数据变得“可能”;基于开放的 PC 架构,让处理海量数据变得“便宜”;而优秀的封装和抽象,则是让处理海量数据变得“容易”。这也是现在谁都能用上大数据技术的基础。可以说,这三个核心技术理念,真正引爆了整个“大数据”技术,让整个技术生态异常繁荣。

笔者认为,Google 能成为散播大数据火种的人,是有着历史的必然性的:作为一个搜索引擎,Google 在数据层面,面临着比任何一个互联网公司都更大的挑战。无论是 Amazon 这样的电商公司,还是 Yahoo 这样的门户网站,都只需要存储自己网站相关的数据。而 Google,则是需要抓取所有网站的网页数据并存下来。而且光存下来还不够,早在 1999 年,两个创始人就发表了 PageRank 的论文,也就是说,Google 不只是简单地根据网页里面的关键字来排序搜索结果,而是要通过网页之间的反向链接关系,进行很多轮的迭代计算,才能最终确认排序。而不断增长的搜索请求量,让 Google 还需要有响应迅速的在线服务。

三驾马车和基础设施

 

面对存储、计算和在线服务这三个需求,Google 就在 2003、2004 以及 2006 年,分别抛出了三篇重磅论文。也就是我们常说的“大数据”的三驾马车:GFSMapReduce 和 Bigtable

GFS 的论文发表于 2003 年,它主要是解决了数据的存储问题。作为一个上千节点的分布式文件系统,Google 可以把所有需要的数据都能很容易地存储下来。GFS它运行于廉价的普通硬件上,并提供容错功能,和以往的文件系统的不同,系统中部件错误不再被当作异常,而是将其作为常见的情况加以处理。其的新颖之处并不在于它采用了多么令人惊讶的新技术,而在于它采用廉价的商用计算机集群构建分布式文件系统,在降低成本的同时经受了实际应用的考验。

然后,光存下来还不够,我们还要基于这些数据进行各种计算。这个时候,就轮到 2004 年发表的 MapReduce 出场了。通过借鉴 Lisp,Google 利用简单的 Map 和 Reduce 两个函数,对于海量数据计算做了一次抽象,这就让“处理”数据的人,不再需要深入掌握分布式系统的开发了。而且他们推出的 PageRank 算法,也可以通过多轮的 MapReduce 的迭代来实现。MapReduce 解决了处理数据的问题,可以对数据进行各种计算。

这样,无论是 GFS 存储数据,还是 MapReduce 处理数据,系统的吞吐量都没有问题了,因为所有的数据都是顺序读写。但是这两个,其实都没有办法解决好数据的高性能随机读写问题。

因此,面对这个问题,2006 年发表的 Bigtable 就站上了历史舞台了。它是直接使用 GFS 作为底层存储,来做好集群的分片调度,以及利用 MemTable + SSTable 的底层存储格式,来解决大集群、机械硬盘下的高性能的随机读写问题。

 

 

到这里,GFSMapReduce 和 Bigtable 这三驾马车的论文,就完成了“存储”、“计算”、“实时服务”这三个核心架构的设计。不过这三篇论文其实还依赖了两个基础设施。

  • 保障数据一致性的分布式锁。对于这个问题,Google 在发表 Bigtable 的同一年,就发表了实现了 Paxos 算法的 Chubby 锁服务的论文。

  • 数据怎么序列化以及分布式系统之间怎么通信。Google 在前面的论文里都没有提到这一点,但是Facebook 在 2007 年发表的 Thrift 的相关论文解决了相关问题。

实际上,Bigtable 的开源实现 HBase,就用了 Thrift 作为和外部多语言进行通信的协议。Twitter 也开源了 elephant-bird,使得 Hadoop 上的 MapReduce 可以方便地使用 Thrift 来进行数据的序列化。

 

 

 

OLAP 和 OLTP 数据库

 

可以说,Google这三驾马车是为整个业界带来了大数据的火种,但是整个大数据领域的进化才刚刚开始。

首先 MapReduce,作为一个“计算”引擎,在有着更大计算需求的背景下(OLAP),其开始朝着以下方式进化。

  1. 编程模型MapReduce 的编程模型还是需要工程师去写程序的,所以它进化的方向就是通过一门 DSL,进一步降低写 MapReduce 的门槛。在这个领域的第一阶段最终胜出的,是 Facebook 在 2009 年发表的 Hive。Hive 通过一门基本上和 SQL 差不多的 HQL,大大降低了数据处理的门槛,从而成为了大数据数据仓库的事实标准;

  2. 执行引擎。Hive 虽然披上了一个 SQL 的皮,但是它的底层仍然是一个个的 MapReduce 的任务,所以延时很高,没法当成一个交互式系统来给数据分析师使用。于是 Google 又在 2010 年,发表了 Dremel 这个交互式查询引擎的论文,采用数据列存储 + 并行数据库的方式。这样一来,Dremel 不仅有了一个 SQL 的皮,还进一步把 MapReduce 这个执行引擎给替换掉了。

  3. 多轮迭代问题:在 MapReduce 这个模型里,一个 MapReduce 就要读写一次硬盘,这对硬盘是无比大的负担。2010年的Spark论文,通过把数据放在内存而不是硬盘里,大大提升了分布式数据计算性能。

     

围绕 MapReduce,整个技术圈都在不断优化和迭代计算性能,HiveDremel 和 Spark 分别从“更容易写程序”,“查询响应更快”,“更快的单轮和多轮迭代”的角度,完成了对 MapReduce 的彻底进化。

作为一个“在线服务”的数据库,Bigtable 的进化是这样的:

  1. 事务问题和 Schema 问题:Google 先是在 2011 年发表了 Megastore 的论文,在 Bigtable 之上,实现了类 SQL 的接口,提供了 Schema,以及简单的跨行事务。如果说 Bigtable 为了伸缩性,放弃了关系型数据库的种种特性。那么 Megastore 就是开始在 Bigtable 上逐步弥补关系型数据库的特性。

  2. 异地多活和跨数据中心问题:Google 在 2012 年发表的 Spanner,能够做到“全局一致性”。这样,就算是基本解决了这两个问题,第一次让我们有一个“全球数据库”。

 

 

 

本质上说,MapReduce 的迭代是在不断优化OLAP类型的数据处理性能,而Bigtable的进化,则是在保障伸缩性的前提下,获得了更多的关系型数据库的能力

实时数据处理的抽象进化

 

从 MapReduce 到 Dremel,我们查询数据的响应时间就大大缩短了。但是计算的数据仍然是固定的、预先确定的数据,这样系统往往有着大到数小时、小到几分钟的数据延时。所以,为了解决好这个问题,流式数据处理就走上了舞台。

首先是 Yahoo 在 2010 年发表了 S4 的论文并将其开源。而几乎是在同一时间,Twitter 工程师南森·马茨(Nathan Marz)以一己之力开源了 Storm,并且在很长一段时间成为了工业界的事实标准。和 GFS 一样,Storm 还支持“至少一次”(At-Least-Once)的数据处理。另外,基于 Storm 和 MapReduce,南森更是提出了 Lambda 架构,它可以称之为是第一个 流批协同 的大数据处理架构。

接着在 2011 年,Kafka的论文也发表了。最早的 Kafka 其实只是一个“消息队列”,但是由于 Kafka 里发送的消息可以做到“正好一次”(Exactly-Once),所以大家就动起了在上面直接解决 Storm 解决不好的消息重复问题的念头。于是,Kafka 逐步进化出了 Kafka Streams 这样的实时数据处理方案。而后在 2014 年,Kafka 的作者 Jay Krepson 提出了 Kappa 架构,这个可以被称之为第一代“流批一体”的大数据处理架构。

在大数据的流式处理领域似乎没有 Google 什么事儿,但是在 2015 年,Google 发表的 Dataflow 的模型,可以说是对于流式数据处理模型做出了最好的总结和抽象。一直到现在,Dataflow 就成为了真正的“流批一体”的大数据处理架构。而后来开源的 Flink 和 Apache Beam,则是完全按照 Dataflow 的模型实现的了。

 

 

 

一致性与调度

 

到了现在,随着“大数据领域”本身的高速发展,数据中心里面的服务器越来越多,我们对于数据一致性的要求也越来越高。为了解决一致性问题,我们就有了基于 Paxos 协议的分布式锁。但是 Paxos 协议的性能很差,于是有了进一步的 Multi-Paxos 协议。可惜的是Paxos 协议并不容易理解,于是就有了 Raft 这个更容易理解的算法的出现。Kubernetes 依赖的 etcd 就是用 Raft 协议实现的。

也正是因为数据中心里面的服务器越来越多,我们会发现原有的系统部署方式越来越浪费。当我们有数百乃至数千台服务器的时候,浪费的硬件和电力成本就成为不能承受之重了。于是,尽可能用满硬件资源成为了刚需。由此一来,我们对于整个分布式系统的视角,也从虚拟机转向了容器,这也是 Kubernetes 这个系统的由来。其从更加全面的角度来进行资源管理和调度系统。

争论与分歧

 

到此为止,笔者为大家简单地介绍了大数据技术的论文演进的脉络。但是整个技术的发展也并不是一个直线上升的状态:

  • 有争论,比如 MapReduce 的论文发表之后,数据库领域知名的科学家大卫·德维特(David DeWitt)就发表过一篇论文“MapReduce:A major step backwards”,抨击 MapReduce 相比于并行数据库是一种倒退

  • 有妥协,比如,Bigtable 不支持跨行事务也不支持 SQL,就是一个明证。直到 5 年后发表的 Megastore,他们才开始着手解决这两个问题;

  • 更有不成功的尝试,典型的就是 Sawzall 和 Pig,Google 在发表 MapReduce 论文之前,就发表了 Sawzall 这个用来撰写 MapReduce 任务的 DSL,Yahoo 也很早就完成了对应的开源实现 Apache Pig。但是 10 年后的今天,我们的主流选择是用 SQL 或者 DataFrame,Pig 的用户已经不多了,而 Sawzall 也没有再听 Google 提起过。

     

    所以可以说,大数据技术的发展是一个非常典型的技术工程的发展过程,跟随这个脉络,我们可以看到工程师们对于技术的探索、选择过程,以及最终历史告诉我们什么是正确的选择。

     

大数据技术盘点

 

相比于某一门计算机课程、某一门编程语言或者某一个开源框架,“大数据”涉及到的知识点多而繁杂。所以这里,笔者就整理了一份知识地图,好让读者可以对论文中提到的知识点有迹可循。

 

 

分布式系统

 

所有的大数据系统都是分布式系统。我们需要大数据系统,就是因为普通的单机已经无法满足我们期望的性能了。那么作为一个分布式的数据系统,它就需要满足三个特性:可靠性可扩展性可维护性

  • 可靠性:如果只记录一份数据,那么当硬件故障的时候就会遇到丢数据的问题,所以我们需要对数据做复制。而数据复制之后,以哪一份数据为准,又给我们带来了主从架构、多主架构以及无主架构的选择。在最常见的主从架构里,根据复制过程,可以有同步复制和异步复制之分。同步复制的节点可以作为高可用切换的 Backup Master,而异步复制的节点只适合作为只读的 Shadow Master。

  • 可扩展性:在“大数据”的场景下,单个节点存不下所有数据,于是就有了数据分区。常见的分区方式有两种,第一种是通过区间进行分片,典型的代表就是 Bigtable,第二种是通过哈希进行分区,在大型分布式系统中常用的是一致性 Hash,典型的代表是 Cassandra。

  • 可维护性。我们需要考虑容错,在硬件出现故障的时候系统仍然能够运作。我们还需要考虑恢复,也就是当系统出现故障的时候,仍能快速恢复到可以使用的状态。而为了确保我们不会因为部分网络的中断导致作出错误的判断,我们就需要利用共识算法,来确保系统中能够对哪个节点正在正常服务作出判断。这也就引出了 CAP 这个所谓的“不可能三角”。

    分布式系统的核心问题就是 CAP 这个不可能三角,我们需要在一致性、可用性和分区容错性之间做权衡和选择。因此,我们选择的主从架构、复制策略、分片策略,以及容错和恢复方案,都是根据我们实际的应用场景下对于 CAP 进行的权衡和选择。

 

存储引擎

 

上万台的分布式集群,最终还是要落到每一台单个服务器上完成数据的读写。那么在存储引擎上,关键的技术点主要包括三个部分。

  • 事务。在传统的数据库领域,我们有 ACID 这样的事务特性即原子性(Atomic)、一致性(Consistency)、隔离性(Isolation)以及持久性(Durability)。而在大数据领域,很多时候因为分布式的存在,事务常常会退化到 BASE 的模型,即表基本可用(Basically Available)、软状态(Soft State)以及最终一致性(Eventually Consistent)。不过无论是 ACID 还是 BASE,在单机上,我们都会使用预写日志(WAL)、快照(Snapshot)和检查点(Checkpoints)以及写时复制(Copy-on-Write)这些技术,来保障数据在单个节点的写入是原子的。而只要写入的数据记录是在单个分片上,我们就可以保障数据写入的事务性,所以我们很容易可以做到单行事务,或者是进一步的实体组(Entity Group)层面的事务。

  • 写入和存储。这个既要考虑到计算机硬件的特性,比如数据的顺序读写比随机读写快,在内存上读写比硬盘上快;也要考虑到我们在算法和数据结构中的时空复杂度,比如 Hash 表的时间复杂度是 O(1),B+ 树的时间复杂度是 O(logN)。这样,通过结合硬件性能、数据结构和算法特性,我们会看到分布式数据库最常使用的,其实是基于 LSM 树(Log-Structured Merge Tree)的 MemTable+SSTable 的解决方案。

  • 数据的序列化。出于存储空间和兼容性的考虑,我们会选用 Thrift 这样的二进制序列化方案。而为了在分析数据的时候尽量减少硬盘吞吐量,我们则要研究 Parquet 或者 ORCFile 这样的列存储格式。然后,为了在 CPU、网络和硬盘的使用上取得平衡,我们又会选择 Snappy 或者 LZO 这样的快速压缩算法。

 

计算引擎

 

计算的维度实际上也是大数据领域本身进化和迭代最快的一部分。

  • 起初,最原始粗糙的 MapReduce 来进行批数据处理,然后围绕它不断迭代出了让数据处理更快的 Spark 和让数据处理更容易的各种 DSL(比如Hive)。

  • 然后,围绕着实时数据处理,有了“最少一次”的 S4/Storm,并把它和批处理综合到一起,产生了著名的 Lambda 架构。

  • 紧接着有了“以批为流”,通过 Mini-Batch 来进行实时数据处理的 Spark Streaming,以及“流批一体”,能够做到“正好一次”的 Kafka 和 Kappa 结构。

  • 最后,还是 Google 一锤定音,给出了统一的 Dataflow 模型,并伴随着有了 Apache Flink 和 Apache Beam 这两个开源项目。

 

随着 Dataflow 论文的发表,整个大数据的处理引擎逐渐收敛成了一个统一的模型,这是大数据领域发展的一个新的里程碑。

经典文章总结

 

最后,笔者把文中提到的这些论文的前后之间的脉络联系专门做了一张图,放在了下面。如果读者对某一篇论文感到困惑的时候,就可以去翻看它前后对应的论文,找到对应问题的来龙去脉。

 

 

 

同时笔者把在文中提到的论文清单列在了下面,供读者作为一个索引。另外,如果有读者觉得本文的内还不够过瘾,笔者强烈推荐你可以读一下 Big Data: A Survey 这篇综述文章,可以让读者更加深入“大数据”技术的全貌。

 

 

 

有的读者可能担心如何找到和下载这些论文。笔者已经贴心的为大家收集好了全部论文并上传到云盘中,只要点击下方连接,即可获得全套经典论文。

# 百度网盘链接: //pan.baidu.com/share/init?surl=h9eoDbgIYZMeQKb1zDAPOw提取码: 4mei

 

其它相关

izx 问题:

这文章有几个问题,一个关于序列化和服务间通信的问题,protobuf/grpc是事实标准,thrift在grpc出现以后用的人就少了。另外,Bigtable不支持跨行事务按当时的场景也的确不需要,Google在跨行事务上是通过Percolator来解决的。

 

荣辛:高质量的回复,很好的补充!

1. 今日而言,如果新项目选择rpc,grpc绝对是比thrift更合适的选择。但Hadoop和HBase 又在使用thrift 和外部交互,要深入了解这些技术,thrift暂时还没法绕开

2. BigTable不支持跨行事务,但Megastore已经在EntityGroup层面支持,到Spanner已经完全支持了。我的表述目的是在于这个演进的过程

3. Percolator个人感觉在学术和搜索引擎的索引更相关一些,本人水平有限,篇幅有限,就没有讲到。有兴趣的读者欢迎参考

//www.usenix.org/legacy/event/osdi10/tech/full_papers/Peng.pdf

izx:

嗯嗯,我想说的是在Bigtable的年代,Google除了实时索引并没有别的跨行事务的需求,所以就先有了Percolator,其他简单事务都通过Chubby在应用层解决,后来Google业务复杂化之后才有了Megastore,但也更像是过渡方案,目前他们存储层都在往Spanner迁移

荣辛:

所以说”大数据技术的发展是一个非常典型的技术工程的发展过程“,没有完美银弹的方案,只有最合适当下的方案。

 

其它文章

Kubernetes核心技术剖析及在DevOps落地实践

乱谈开源社区、开源项目与企业内部开源(中)

研发效能|DevOps 已死平台工程永存带来的焦虑

如何快速提升团队软件开发成熟度,提升研发效能?

从特拉斯辞职风波到研发效能中的荒唐事

 

感谢点赞、转载
关注我,了解最新研发效能发展动向
欢迎进入「DevOps研发效能群」一起探讨