1.动机

1.1 大数据的来源和使用

随着计算机的飞速发展，网站产生了大量数据，数据规模远超传统数据库系统能够处理的规模，我们把具有量大，存储速度要求高，数据多样性丰富的特征的数据统称为大数据。

大数据的来源方方面面。比如社交软件，零售业交易数据，物联网设备。

大数据的应用可以帮助分析用户的偏好，精准推送内容、广告、商品等。

目前已经有几个系统用于存储和处理大数据，他们使用集群技术，集群中的机器使用术语节点(node)表示。

1.2 大数据查询

关系型数据库主要通过SQL进行查询，大数据查询受到其非常大的数据量/高速处理的需求驱动，选择余地更大。

构建能够扩展到大数据量/高速处理的数据管理系统需要并行存储和处理数据。构建一个支持SQL及诸如事务那样的其他数据库特性的关系型数据库，并同时通过大量机器上运行来支持非常高的性能，这不是一项简单的任务。这类应用可分为两类。

1.需要非常高的可扩展性的事务处理系统:事务处理系统支持大量短时间运行的查询和更新

如果对支持关系数据库的所有特性的要求放松，那么被设计用于支持事务处理的数据库就很容易扩展到非常多的机器上。许多需要扩展到非常大的数据量/高速处理的事务处理应用可以在没有完整的数据库支持的情况下进行管理。

此类应用的数据访问的主要模式是使用关联的键存储数据，并使用该键检索数据。这样的存储系统称为键值存储系统。在前面的用户配置文件示例中，用户配置文件数据的键可以是用户的标识。有些应用在概念上需要连接，但通过应用程序代码或者视图的形式来实现连接。

例如，在社交网络应用中，当一个用户连接到系统时，系统应该向该用户显示来自其所有朋友的新贴子。如果有关贴子和朋友的数据是以关系形式来维护的，那么这就需要一个连接。反之，假设系统在键值存储中为每个用户维护一个对象，包括他们的朋友的信息以及这些朋友的贴子。应用程序可以通过受限找出用户的朋友集，然后查询每个朋友的数据对象来找到他们的贴子。以这种方式实现连接而不是在数据库中完成连接。另一种选择如下：每当用户u0发布贴子时，对于该用户的每个朋友ui，系统都会向代表ui的数据对象发送一条消息，并且将与该朋友关联的数据用新帖子的摘要进行更新。当用户ui检查更新时，提供朋友贴子摘要视图所需的所有数据可以在一个地方获得，并且可被快速检索。

这两种备选方案之间存在着权衡，比如，第一种备选方案在查询时代价高，第二种方式在存储和写入时代价高。但这两种方法都允许应用在不支持连接的情况下在键值存储系统中执行其任务。

2.需要非常高的扩展性且支持非关系数据的查询处理系统.。此类系统的典型示例是哪些被设计用来对网络服务器和其他应用程序产生的日志进行分析的系统。其他示例包括文档和知识的存储及索引系统，例如那些在网络上支持关键字搜索的系统。

许多此类应用所使用的数据存储在多个文件中。设计用于支持此类应用的系统受限需要能够存储大量的大型文件。其次，它必须能够支持对存储在这些文件中的数据进行查询。由于数据不一定是关系型的，因此为查询此类数据而设计的系统必须支持任意程序代码，而不仅仅支持关系代数或者SQL查询。

大数据应用通常需要处理大量的文本、图像和视频数据。本篇文章我们将介绍当前广泛使用的大数据查询技术，这些技术允许指定复杂的数据处理任务，同时使得任务能容易地并行化。让程序员不必关注这些复杂的低层问题。

2.存储系统

大数据上得应用具有极高的可扩展性要求，现在已经有许多用于大数据存储的系统。这些系统包括。

• 分布式文件系统。他们允许文件跨大量机器存储，同时允许使用传统的文件系统接口访问文件。分布式文件系统用于存储大型文件，还被用作能支持记录存储的系统的存储层。
• 跨多数据库分片。分片是指跨多个系统对记录进行划分的过程；换言之，记录在系统之间划分。分片的一个典型应用案例是跨数据库集合对不同用户对应的记录进行划分。每个数据库都是传统的集中式数据库，可能没有其他数据库的任何信息。客户机软件的工作是跟踪记录是如何划分的，并将每个查询发送给相应的数据库。
• 键值存储系统。它们允许基于键的方式来存储和检索记录。此外可能提供有限的查询工具。但是它们不是成熟的数据库系统，又被称为NoSQL系统，因为此类存储系统通常不支持SQL语言。

• 并行和分布式数据库。它们提供传统的数据库接口，但是跨多台机器存储数据，并且跨多台机器并行执行查询处理。

2.1 分布式文件系统

分布式文件系统(distritubuted file system,DFS)跨大量机器存储文件，同时为客户机提供单一的文件系统视图。与任何文件系统类似，它是一个由文件名和目录构成的系统，客户机不需要关注文件存储在哪里，这种分布式文件系统可以存储大量的数据，并支持非常大量的并发客户机。此类系统非常适合存储非结构化数据，如网页、网络服务器日志、图像等，这些非结构化数据被存储为大型文件。

DFS的一个里程碑系统是Google的GFS，基于GFS体系结构的Hadoop文件系统现在也得到了广泛的应用。

分布式系统可以将文件分块，跨机器划分存储。

此外，每个文件库跨多台(通常是三台)机器进行复制，这样机器就不会因为故障导致文件无法访问。

下图显示了Hadoop文件系统的体系结构。HDFS的核心是一台运行在被称为名字节点(NameNode)的机器上的服务器，存储HDFS中数据块的机器被称为数据节点(DataNode)

所有的系统请求都被发送到NameNode。

对于文件读取请求，HDFS服务器将返回文件中块的块标识列表以及包含在每个块的标识列表，然后从存储该块副本的其中一台机器中提取出每个块。

对于文件写入请求，HDFS服务器创建新的块标识，将每个块标识分配给多台(通常为三台)机器，并将块标识和机器分配返回给客户机。然后客户机将块标识和块数据发送给存储数据的指定机器。

可以通过HDFS文件系统API的程序来访问这些文件，这些API在诸如Java，Python等语言中都是可用的。

HDFS分布式文件系统也可以连接到机器的本地文件系统，这样就可以像访问存储在本地的文件那样访问HDFS中的文件。这需要向本地文件系统提供名字节点机器的地址和HDFS服务器侦听请求的端口。本地文件系统根据文件路径识别哪些文件访问是针对HDFS中的文件的，并向HDFS服务器发送相应的请求。

2.2 分片

单一数据库无法满足海量数据的存储、处理。如果已经采用了集中式数据库构建应用，需要扩展来处理更多用户，一种常用方式是跨多个数据库划分数据，并将用户的子集分配给每个数据库，这被称为分片(sharding)。

划分通常在一个或者多个属性上完成，这些属性被称为划分属性、划分键或分片键。用户被账户标识通常用作划分键。划分可以通过定义每个数据库处理的键的范围来完成，例如，1~10000划分给数据库A，10001~20000划分给数据库B。这种划分称为范围划分。还可以通过哈希函数进行哈希划分。

当在应用程序代码中进行分片时，应用程序必须跟踪哪个键存储在哪个数据库上，并且必须将查询路由到相应的数据库。无法用简单的方式来处理从多个数据库读取或者更新数据的查询，因为不可能提交跨所有数据库的单个查询。应用程序需要从多个数据库中读取数据并计算最终的查询结果。跨数据库更新会导致更多问题。除此之外，如果一个数据库过载，则必须将该数据库中的部分数据卸载到其他数据库…后续文章我们将讨论这些问题

2.3 键值存储系统

许多网络应用需要存储非常大量(数十亿或者极端情况下数万亿)但相对较小(几千字节到几兆字节)的记录。

理想情况下，应该使用大规模并行的关系数据库来存储此类数据，但是，构建可以跨大量机器并行运行同时支持诸如外码约束和事务那样的标准数据库特征的关系数据库系统并不容易。

键值存储系统提供了一种解决方案。

并行键值存储跨多台机器来存储划分键，并把更新和查找处理路由到正确的机器，它们还支持复制，确保数据的一致性。此外，它们还提供了在需要时向系统添加更多的机器的能力，并且确保负载在系统中的机器自动均衡。因此，当前并行键值存储相比分片得到了更广泛的应用。

广泛应用的键值存储包括Bigtable,HBase,Dynamo,MongoDB,Cassandra…

有些键值数据存储将存储中的值看做不可解释的字节序列，而不看其内容。但其他数据存储允许某种形式的结构或模式与每条记录相关联。有些键值存储系统要求所存储的数据遵循特定的数据表示，允许数据存储系统解释被存储的值，并基于所存储的值执行简单查询，这种数据存储被称为文档存储。

文档是一组键值(key-value)对。一个简单的文档例子如下：

{"site":"www.runoob.com", "name":"菜鸟教程"}

MongoDB是一个代表，它接受JSON格式的值。

使用键值存储的一个重要动机是，通过将工作分布在由大量机器组成的集群(cluster)，能够处理非常大量的数据及查询。但是键值存储通常不支持声明式查询(如SQL，因此它也被称为NoSQL系统)，事务，这是为了支持高扩展性而采取的牺牲。

不过缺少上述支持会使应用程序开发变得更加复杂，许多键值存储系统已经发展到提供SQL，事务等了。

下面展示了通过JavaScript的shell接口(在安装配置了MongoDB的系统通过mongo命令打开)访问MongoDB文档存储，作为访问键值存储系统的API的一个实例。

show dbs // Shows available databases
use sampledb // Use database sampledb, creating it if it does not exist 
db.createCollection("student") // Create a collection db.createCollection("instructor")
show collections // Shows all collections in the database
db.student.insert({ "id" : "00128", "name" : "Zhang",
"dept name" : "Comp. Sci.", "tot cred" : 102, "advisors" : ["45565"] })
db.student.insert({ "id" : "12345", "name" : "Shankar",
"dept name" : "Comp. Sci.", "tot cred" : 32, "advisors" : ["45565"] })
db.student.insert({ "id" : "19991", "name" : "Brandt",
"dept name" : "History", "tot cred" : 80, "advisors" : [] })
db.instructor.insert({ "id" : "45565", "name" : "Katz",
"dept name" : "Comp. Sci.", "salary" : 75000,
"advisees" : ["00128","12345"] })
db.student.find() // Fetch all students in JSON format db.student.findOne({"ID": "00128"}) // Find 
one matching student
db.student.remove({"dept name": "Comp. Sci."}) // Delete matching students db.student.drop() // 
Drops the entire collection

看上去还是蛮简单的。MongoDB的一个关键目标是支持扩展到非常大的数据规模和查询/更新负载，因此它支持并行处理，数据分片等。下图是一个MongoDB的分片集群的配置架构。

Bigtable是另一种键值存储，它要求数据值遵循一定的格式。Bigtable不支持完整的关系数据模型，而是为用户提供了简单的数据模型，使客户可以动态控制数据的分布和格式。

在Bigtable中，数据值(记录)可以有多个属性，属性名集合不是预先确定的，并且可以在不同的记录之间变化。因此，属性值的键在概念上由(记录标识，属性名)组成，

就Bigtable而言，每个属性值只是一个字符串。要获取记录的所有属性，可以使用范围查询，或者更加准确的说，使用仅包含记录标识的前缀匹配查询。为了更高效的检索所有属性，存储系统存储按键排序的条目，因此特定记录的所有属性值都聚集在一起。

据作者说，Bigtable是一个稀疏、分布式、持久化存储的多维有序映射表，其数据模型如下

虽然Bigtable本身的记录标识只是一个字符串，但事实上，记录标识本身可以通过映射转变为层次结构的。

比如一个存储通过网络爬虫获得的页面的应用程序可以将如下URL

www.cs.yale.edu/people/silberschatz.html

映射为

edu.yale.cs.www/people/silberschatz.html

反转的原因是为了让同一个域名下的子域名网页能聚集在一起。

下图是一个典型的Bigtable存储结构。

Bigtable不支持Json，但是可以把JSON映射到Bigtable的数据模型上。比如

可以被用标识为"22222"的Bigtable记录来表示，该记录具有多个属性名，如"name.firstname" “children[1].firstname”

此外，单个Bigtable实例可以为多个应用存储数据，每个应用有多个表，只需要简单地将应用名和表名作为记录标识的前缀即可。

许多数据存储系统允许存储数据项的多个版本，版本通常由时间戳来标识，但还可以由整数值来标识。一旦创建数据项的新版本，该整数值就递增。例如，Bigtable中，键实际上由三部分构成(记录标识，属性名，时间戳)。

Bigtable可以从Google上作为服务被访问到，其开源版本被Hbase广泛使用。

关于Bigtable的更多内容，可以参考文章：谷歌技术"三宝"之BigTable

2.4 并行数据库

并行数据库(parrallel database)是指在多台机器(统称为集群)上运行的数据库。它被设计用于跨多台机器存储数据，并使用多台机器处理大型查询。

并行数据库包含多个处理器，以提供数据库上的并行工作。旨在通过并行化各种操作（如加载数据、构建索引和评估查询）来提高性能，并行系统通过并行使用多个 CPU 和磁盘来提高处理和 I/O 速度。

让我们逐步讨论并行数据库的工作原理 -

步骤1− 并行处理将大型任务划分为许多较小的任务，并在多个CPU上同时执行较小的任务，从而更快地完成它。

步骤 2− 并行数据库系统背后的驱动力是必须查询 TB 量级的超大型数据库或每秒必须处理大量事务的应用程序的需求。

步骤3− 在并行处理中，许多操作是同时执行的，而不是串行处理，其中计算步骤是按顺序执行的。

下图展示了并行处理与单cpu处理的效率区别。

从程序员的角度看，并行数据库可以像在单台机器上运行的数据库一样使用。

并行数据库的一个问题就是系统的容错性较差，过去人们认为节点故障是个特例，并不经常出现，因此系统只提供事务级别的容错功能，如果在查询过程中节点发生故障，那么整个查询都要从头开始重新执行。

这种重启任务的策略使得并行数据库难以在拥有数以千个节点的集群上处理较长的查询，因为在这类集群中节点的故障经常发生。基于这种分析，并行数据库只适合于资源需求相对固定的应用程序。

在发生故障的情况下重新启动查询不再可行，因为在重新执行查询时很可能再次发生故障。后面我们将介绍MapReduce系统中，开发了避免完全重启的技术，只需要对故障机器上得计算进行重做。然而，这些技术带来了巨大的开销。考虑到跨越成千上万个节点的计算只在一些非常大的应用中才需要，即使在今天，大多数并行的关系数据库系统都以运行在数十至数百台机器上得应用为目标，在故障出现时只需要重新启动查询。

2.5 复制和一致性

复制是保证数据可用性的关键。

复制要求对数据项的任何更新都必须应用于数据项的所有副本，只要包含副本的所有机器都已经启动并相互连接，更新很简单。

然而机器故障确实会发生，这里有两个关键问题

如何确保在多台计算机上更新数据的事务原子执行，如果尽管发生了故障，但是事务更新过的所有数据项都已成功更新，或者所有数据项都已还原回原始值，就称该事务为原子的。

当数据项的某些副本位于发生故障的机器上时，如何对已经被复制的数据项执行更新。这里的一个关键问题是要求一致性。也就是说，一个数据项的所有活跃副本都具有相同的值，并且每次读取都会看到该数据项的最新版本。

后续文章我们将详细探讨解决方案。

分布式系统中，一致性和可用性往往是需要进行权衡的。如果网络故障时，为了保证可用，分区两边的处理可以继续，那就是分区容忍的。（那不就不一致了吗）

可用性：

基本可用是指分布式系统在出现不可预知故障的时候，允许损失部分可用性——但请注意，这绝不等价于系统不可用，以下两个就是“基本可用”的典型例子。

1.响应时间上的损失：正常情况下，一个在线搜索引擎需要0.5秒内返回给用户相应的查询结果，但由于出现异常（比如系统部分机房发生断电或断网故障），查询结果的响应时间增加到了1~2秒。

2.功能上的损失：正常情况下，在一个电子商务网站上进行购物，消费者几乎能够顺利地完成每一笔订单，但是在一些节日大促购物高峰的时候，由于消费者的购物行为激增，为了保护购物系统的稳定性，部分消费者可能会被引导到一个降级页面。

弱状态也称为软状态，和硬状态相对，是指允许系统中的数据存在中间状态，并认为该中间状态的存在不会影响系统的整体可用性，即允许系统在不同节点的数据副本之间进行数据听不的过程存在延时。