持续更新中... at 2024.01.09半夜
写了一部分概述，尝试在里面多塞一些私货，希望除了应试以外大家也能有所实质性的收获。
¶ 应试
¶ 往年题目
¶ 概述
NoSQL，即Not Only SQL，意为“不仅仅是SQL”，是一项全新的数据库技术，它打破了传统关系型数据库的思维定式，不再使用关系型数据库的表结构，而是使用键值对的方式存储数据，这种方式可以更好地适应大数据的存储和访问需求。
很多朋友对 Redis 是比较熟悉的，习惯于称它为一种“缓存”，但是 Redis 本身并不是缓存，它就是一种 NoSQL 数据库，属于 NoSQL 中的“键值对数据库”（Key-Value Database）。只不过，由于他在实现上将数据存储在内存中，所以在实际应用中，我们通常会将 Redis 用作缓存。那么在“键值对数据库”这分类下，自然不只有 Redis，还有很多其他的数据库，比如 Memcached、LevelDB、RocksDB、Berkeley DB 等等。
另一种比较有意思的数据库就是图数据库，例如 Neo4j，它是一种基于图论的数据库，它的数据结构是图而不是表，它的查询语言也不是 SQL，而是 Cypher。图数据库的应用场景主要是在社交网络、推荐系统、生物信息学等领域。
看的出来，与我们熟悉的 MySQL、Oracle 等关系型数据库相比，NoSQL 数据库显然要多样一些，它们的数据结构、查询语言、应用场景都不尽相同，但是它们都有一个共同的特点，就是不使用 SQL 语言，这也是 NoSQL 的由来。
总的来讲，NoSQL 数据库有四种主要的类型：
- 键值对数据库（Key-Value Database）：常用来做缓存，例如 Redis、Memcached 等，通过键来查找值，键和值都是字符串类型，没有固定的结构，也没有关系型数据库中的表、行、列的概念。
- 文档型数据库（Document Database）：常用来存储 JSON、XML 等格式的文档，例如 MongoDB、CouchDB 等，文档型数据库的查询语言和关系型数据库的 SQL 语言类似，但是文档型数据库不支持 JOIN 操作。
- 列存储数据库（Column Database）：常用于各类分析，例如 HBase、Cassandra 等，它们的数据结构是一系列的列，而不是关系型数据库中的行。
- 图数据库（Graph Database）：常用于社交网络、推荐系统、生物信息学等领域，例如 Neo4j、OrientDB 等，它们的数据结构是图，而不是表，它的查询语言也不是 SQL，而是 Cypher。
¶ 数据库历史
¶ NoSQL与SQL
关系数据库的优势：
-
保持数据的一致性（事务处理）
-
最小冗余
-
成熟的技术
-
复杂查询如JOIN
但是关系型数据库也有一些缺陷，这些缺陷很容易在应用规模增长时显现出来：
-
大量数据的写入处理
-
表结构变更及建立索引
-
字段不固定的应用
-
对简单查询需要快速返回结果的处理
相比之下，NoSQL就有易于数据的分散、提升性能和增大规模、模式灵活和扩展性好的一系列特点。
¶ NoSQL分类
¶ 数据一致性理论
¶ CAP理论
CAP理论：一个分布式系统不可能满足一致性，可用性和分区容错性这三个需求，最多只能同时满足两个。
- C，Consistency（一致性）：在分布式系统完成某写操作后任何读操作，都应该获取到该写操作写入的那个最新的值。相当于要求分布式系统中的各节点时时刻刻保持数据的一致性。
- A，Availability（可用性）：一直可以正常的做读写操作。简单而言就是客户端一直可以正常访问并得到系统的正常响应。用户角度来看就是不会出现系统操作失败或者访问超时等问题。
- P，Tolerance of network Partition（分区容错性）：指的分布式系统中的某个节点或者网络出现了故障的时候，整个系统仍然能对外提供满足一致性和可用性的服务，也就是说部分故障不影响整体使用。
一般来说，跨区域的系统，无法舍弃P性质，那么就只能在数据一致性和可用性上做一个艰难选择。NoSQL 运动的主题其实是创造各种可用性优先、数据一致性其次的方案；而传统数据库坚守ACID特性，做的是相反的事情。
CAP 无法三者兼得，三种潜在的组合方式特点是：
- CA: 优先保证一致性和可用性，放弃分区容错。 这也意味着放弃系统的扩展性，系统不再是分布式的，有违设计的初衷。
结局是关系型数据库。
- CP: 优先保证一致性和分区容错性，放弃可用性。在数据一致性要求比较高的场合（譬如:Zookeeper，Hbase）是比较常见的做法，一旦发生网络故障或者消息丢失，就会牺牲用户体验，等恢复之后用户才逐渐能访问。
结局是分布式数据库。
- AP: 优先保证可用性和分区容错性，放弃一致性。放弃一致性不是说一致性就不保证了，而是逐渐的变得一致。
解决是保证最终一致性的系统，例如 BASE。
¶ 数据一致性
数据的一致性大致可以分为三类，强一致性、弱一致性和最终一致性：
- 强一致性，也叫即时一致性。假如A先写入了一个值到存储系统，存储系统保证后续A，B，C的读取操作都将返回最新值。单副本数据容易保证强一致性，多副本数据需要使用分布式事务协议。
- 弱一致性。假如A先写入了一个值到存储系统，存储系统不能保证后续A，B，C的读取操作能读取到最新值。不一致性窗口指的就是A写入后A、B、C读到最新数据的时间。
- 最终一致性是弱一致性的一种特例。假如A首先
write了一个值到存储系统，存储系统保证如果在A，B，C后续读取之前没有其它写操作更新同样的值的话，最终所有的读取操作都会读取到A写入的最新值；此种情况下，如果没有失败发生的话，“不一致性窗口”的大小依赖于以下的几个因素：交互延迟，系统的负载，以及复制技术中replica的个数（这个可以理解为master/salve模式中，slave的个数）。最终一致性方面最出名的系统可以说是 DNS 系统，当更新一个域名的IP以后，根据配置策略以及缓存控制策略的不同，最终所有的客户都会看到最新的值。当然，这个过程中，可能会有一些客户端看到旧值，这个时间窗口的大小，取决于DNS服务器的配置，以及客户端的缓存策略。
除此以外，还有Causal consistency（因果一致性）、Read-your-writes consistency（读自写一致性）、Session consistency（会话一致性）和Monotonic read/write consistency（单调读/写一致性）等很多情况存在。
¶ BASE与ACID
BASE的含义：
- Basically Availble：基本可用：基本可用是指分布式系统在出现不可预知故障的时候，允许损失部分可用性。
- Soft-state：软状态/柔性事务：允许系统中的数据存在中间状态，并认为该中间状态的存在不会影响系统的整体可用性，即允许系统在不同节点的数据副本之间进行数据同步的过程存在延时。
- Eventual Consistency：最终一致性：最终一致性强调的是系统中所有的数据副本，在经过一段时间的同步后，最终能够达到一个一致的状态。因此，最终一致性的本质是需要系统保证最终数据能够达到一致，而不需要实时保证系统数据的强一致性。
| BASE | ACID |
|---|---|
| 弱一致性 | 强一致性 |
| 可用性优先 | 隔离性 |
| 乐观方法 | 采用悲观、保守方法 |
¶ 数据一致性实现技术
¶ NWR模型
其中：
- N: 复制的节点数量，即副本数。
- R: 成功读操作的最小节点数。
- W: 成功写操作的最小节点数。
只需 W + R > N，就可以保证强一致性，因为读取数据的节点和被同步写入的节点是有重叠的，此时读(写)延迟由最慢的R(W)副本决定。
如果 R + W > N，那么分布式系统就会提供强一致性的保证，因为读取数据的节点和被同步写入的节点有重叠；如果 R + W ≤ N，这时读取和写入操作是不重叠的，系统只能保证最终一致性，而副本达到一致的时间则依赖于系统异步更新的实现方式。
几种特殊情况：
- W = 1， R = N ，对写操作要求高性能高可用。
- R = 1 ， W = N ，对读操作要求高性能高可用，比如类似cache之类业务。
- W = Q, R = Q where Q = N / 2 + 1 一般应用适用，读写性能之间取得平衡，如N=3 ， W=2 ， R=2。
¶ 两阶段提交协议
两阶段提交协议是很常见的解决分布式事务的方式，可以保证分布式事务中，要么所有参与的进程都提交事务成功，要么都取消事务，这样做可以在分布式环境中保持 ACID 中的原子性 A。
在两阶段提交协议中，包含了两种角色：
- 参与者：实际处理事务的机器。
- 协调者：其中一台单独的处理分布式事务的机器。
该算法分为两个阶段：
- 投票阶段：在请求阶段，协调者将通知事务参与者准备提交或取消事务，然后进入表决过程。在表决过程中，参与者将告知协调者自己的决策：同意（事务参与者本地作业执行成功）或取消（本地作业执行故障）。
- 提交阶段：协调者将基于第一个阶段的投票结果进行决策：提交或取消。当且仅当所有的参与者同意提交事务协调者才通知所有的参与者提交事务，否则协调者将通知所有的参与者取消事务。
两阶段提交协议的优点是实现足够简单，但是存在同步阻塞、单点故障和数据不一致的问题：
- 同步阻塞：执行过程中，所有参与节点都是事务阻塞型的。当参与者占有公共资源时，其他第三方节点访问公共资源不得不处于阻塞状态。
- 单点故障：由于协调者的重要性，一旦协调者发生故障。参与者会一直阻塞下去。尤其在第二阶段，协调者发生故障，那么所有的参与者还都处于锁定事务资源的状态中，而无法继续完成事务操作。
如果是协调者挂掉，可以重新选举一个协调者，但是无法解决因为协调者宕机导致的参与者处于阻塞状态的问题。
- 数据不一致：在二阶段提交的阶段二中，当协调者向参与者发送
commit请求之后，发生了局部网络异常或者在发送commit请求过程中协调者发生了故障，这回导致只有一部分参与者接受到了commit请求。而在这部分参与者接到commit请求之后就会执行commit操作。但是其他部分未接到commit请求的机器则无法执行事务提交。于是整个分布式系统便出现了数据不一致性的现象。 - 二阶段无法解决的问题：协调者在发出
commit消息之后宕机，而唯一接收到这条消息的参与者同时也宕机了。那么即使协调者通过选举协议产生了新的协调者，这条事务的状态也是不确定的，没人知道事务是否被已经提交。
¶ 文档型数据库
¶ 文档型数据库介绍
**文档（Document）**是文档数据库中的主要概念。文档数据库可存放并获取文档，其格式可以是XML、JSON、BSON等。数据库中的文档彼此相似，但结构不必完全相同，不像关系型数据库那样，表格中每行数据的模式都要相同，并且向文档中新增属性时，既无需预先定义，也不用修改已有文档内容。
文档型数据库和关系型数据库在一些概念上可以对应起来：
| Oracle | MongoDB |
|---|---|
| 数据库实例（Instance） | MongoDB实例（Instance） |
| 模式（Schema） | 数据库（Database） |
| 表格（Table） | 集合（Collection） |
| 行（Row） | 文档（Document） |
| 伪列（rowid） | _id |
| JOIN | DBRef |
文档型数据库具有可操作指定的一致性强度、单文档级别的事务、可扩展性强等特点，适用于大量的数据存储和查询，但是不适合于复杂的事务处理。
例如，文档型数据库可以用来进行事件记录、网站分析等场景，但不适合复杂事务、多表关联查询等场景。
¶ MongoDB
MongoDB 是由C++语言编写的，是一个基于分布式文件存储的开源数据库系统。MongoDB 将数据存储为一个文档，数据结构由键值(key value)对组成，类似于 JSON 对象（称为 BSON），字段值可以包含其他文档，数组及文档数组。
MongoDB 没有提供对连接操作的支持，这就要求用户将所有相关的数据存储在一个文档里，避免在外部使用连接。
¶ 数据模型
MongoDB 中使用 _id 作为一行的唯一标识，其类型是一个 ObjectID()。MongoDB 又一个比较丰富的类型系统，如下图所示：
MongoDB 有一种比较特殊的集合类型：固定集合，指的是事先创建，并且大小固定的集合。假设一个集合设置了固定大小为100，再添加一条文档的时候，会把最前面的文档剔除，永远只保留100条数据。固定集合有着这样的特性：
- 固定集合很像环形队列，如果空间不足，最早的文档就会被删除，为新的文档腾出空间。
- 固定集合适用于任何想要自动淘汰过期属性的场景，比如日志文件，聊天记录，通话信息记录等只需保留最近某段时间内的应用场景。
¶ 访问与操作
¶ 管理命令
¶ 实现机制
一个运行着的 MongoDB 数据库就可以看成是一个 MongoDB Server；Server 由实例和数据库组成，在一般的情况下一个 MongoDB Server 机器上包含一个实例和多个与之对应的数据库；MongoDB 中一系列物理文件(数据文件，日志文件等)的集合或与之对应的逻辑结构(集合，文档等)被称为数据库。
在 MongoDB 内部，每个数据库都包含一个.ns 文件和一些数据文件，而且这些数据文件会随着数据量的增加而变得越来越多。
如果系统中有一个叫做
foo的数据库，那么构成foo这个数据库的文件就会由foo.ns，foo.0，foo.1，foo.2等等组成。
MongoDB 内部有预分配空间的机制，每个预分配的文件都用 0 进行填充，由于有了这个机制，MongoDB 始终保持额外的空间和空余的数据文件，从而有效避免了由于数据暴增而带来的磁盘压力过大的问题。由于集合中数据量的增加，数据文件每新分配一次，它的大小都会是上一个数据文件大小的 2 倍，每个数据文件最大 2G。这样的机制有利于防止较小的数据库浪费过多的磁盘空间，同时又能保证较大的数据库有相应的预留空间使用。
数据库的每个集合都对应一个命名空间，每个索引也有对应的命名空间。这些命名空间的元数据都集中在 *.ns 文件中，如下图所示：
图中可以看到，每个命名空间可以包含多个不同的盘区，这些盘区并不是连续的。与数据文件的增长相同，每一个命名空间对应的盘区大小的也是随着分配的次数不断增长的。这样做的目的是为了平衡命名空间浪费的空间与保持某一个命名空间中数据的连续性。
上图中还有一个需要注意的命名空间：$freelist，这个命名空间用于记录不再使用的盘区(被删除的 Collection 或索引)。 每当命名空间需要分配新的盘区的时候，都会先查看 $freelist 是否有大小合适的盘区可以使用，这样就回收空闲的磁盘空间。
¶ 列存储数据库
¶ 列存储数据库介绍
如果翻转数据，列式存储与关系存储将会非常相似：
- 列式数据库，以列相关存储架构进行数据存储的数据库，主要适合于批量数据处理和即时查询。
- 行式数据库，数据以行相关的存储体系架构进行空间分配，主要适合于大批量的数据处理，常用于联机事务型数据处理。
¶ HBase
¶ HBase简介
HBase（Hadoop Database）是一个高可靠性、高性能、面向列、可伸缩的分布式存储系统，利用HBase技术可在廉价PC Server上搭建起大规模结构化存储集群。
HBase是Google BigTable的开源实现，模仿并提供了基于Google文件系统的BigTable数据库的所有功能。
HBase主要依靠横向扩展，通过不断增加廉价的商用服务器，来增加计算和存储能力；仅能通过主键(row key)和主键的range来检索数据，仅支持单行事务(可通过Hive支持来实现多表连接等复杂操作)；主要用来存储非结构化和半结构化的松散数据。HBase的目标是处理非常庞大的表，可以用普通的计算机处理超过10亿行数据，并且有数百万列元素组成的数据表。
Base中表的特点：
- 大：一个表可以有上亿行，上百万列。
- 面向列：面向列(族)的存储和权限控制，列(族)独立检索。
- 稀疏：对于为空(null)的列，并不占用存储空间，因此表可以设计的非常稀疏。
HBase与以前的关系数据库存在很大的区别，它是按照BigTable开发的，是一个稀疏的、分布的、持续多维度的排序映射数组，作为基于列模式的映射数据库，它只能表示很简单的键-数据的映射关系，它大大简化了传统的关系数据库。二者的区别有：
- 数据类型：HBase只有简单的字符串类型，所有类型都由用户自己处理，它只保存字符串；关系数据库有丰富的类型选择和存储方式。
- 数据操作：HBase操作只有很简单的插入、查询、删除、清空等，表和表之间是分离的，没有复杂的表和表之间的关系，所以也不能也没有必要实现表和表之间的关联等操作；传统的关系数据通常有各种各样的函数、连接操作。
- 存储模式：HBase是基于列存储的，每个列族都有几个文件保存，不同列族的文件是分离的；传统的关系数据库是基于表格结构和行模式保存的。
- 数据维护：HBase的更新正确来说应该不叫更新，而且一个主键或者列对应的新的版本，而它旧有的版本仍然会保留，所以它实际上是插入了新的数据；传统关系数据库里面是替换修改。
- 可伸缩性：HBase和BigTable这类分布式数据库就是直接为了这个目的开发出来的，能够轻易的增加或者减少（在硬件错误的时候）硬件数量，而且对错误的兼容性比较高；传统的关系数据库通常需要增加中间层才能实现类似的功能。
¶ HBase数据模型
HBase的索引是行关键字、列关键字和时间戳，每个值是一个不解释的字符数组，数据都是字符串，没有类型。用户在表格中存储数据，每一行都有一个可排序的主键和任意多的列，由于是稀疏存储的，同一张表里面的每一行数据都可以有截然不同的列。
列名字的格式是<family>:<label>，都是由字符串组成，每一张表有一个family集合，这个集合是固定不变的，相当于表的结构，只能通过改变表结构来改变，但是label值相对于每一行来说都是可以改变的。HBase把同一个family里面的数据存储在同一个目录底下，而HBase的写操作是锁行的，每一行都是一个原子元素，都可以加锁。
所有数据库的更新都有一个时间戳标记，每个更新都是一个新的版本，而HBase会保留一定数量的版本，这个值是可以设定的。
HBase数据模型中三个重要概念：
- 行键（Row Key）：HBase表的主键，表中的记录按照行键排序。行键是用来检索记录的主键。
- 时间戳（Timestamp）：每次数据操作对应的时间戳，可看作是数据的版本号，不同版本通过时间戳来进行索引。
- 列族（Column Family）：表在水平方向有一个或者多个列族组成，一个列族中可以由任意多个列组成，即列族支持动态扩展，无需预先定义列的数量以及类型，所有列均以二进制格式存储，用户需要自行进行类型转换。
虽然从概念视图来看，HBase中的每个表格是由很多行组成的，但是，在物理存储上面，它是按照列来保存的。概念视图中空白的列实际不会被存储，当请求这些空白的单元格的时候，会返回null值；如果在查询的时候不提供时间戳，那么会返回距离现在最近的那一个版本的数据（因为在存储的时候，数据会按照时间戳排序）。
¶ HBase访问与操作
¶ HBase实现机制
HBase在设计上是一个典型的 Master - Slave 架构，传统模式下是不支持高可用的（因为 Master 节点可能会挂掉）。HBase 的主要功能组件有三个：
- 库函数。
- 一个 HMaster 服务器。
- 多个 HRegion 服务器。
HRegion 服务器可以根据工作负载的变化，从一个簇中动态地增加或删除，主服务器 HMaster 负责把 Hregion 分配到 HRegion 服务器，进行 HRegion 服务器的负载均衡。每个 HRegion 服务器管理一个 HRegion 集合，通常在每个 HRegion 服务器上，会放置10到1000个 Hregion，HRegion 服务器处理针对那些已经加载的 HRegion 而提出的读写请求，并且会对过大的 HRegion 进行划分。
客户端直接从HRegion服务器上读取数据，并不依赖于主服务器HMaster来获得HRegion的位置信息，所以在实际应用中，主服务器负载很小。
一个HBase中存储了许多表，每个表都是一个HRegion集合，每个 HRegion 包含了位于某个域区间内的所有数据。表中的所有行都按照行键的字典序排列，表在行的方向上分割为多个HRegion。
HRegion会按照大小进行分割，每个表一开始只有一个HRegion，随着数据不断插入表，HRegion不断增大，当增大到一个阀值的时候，HRegion就会等分成两个新的HRegion。不同的HRegion会被HMaster分配给相应的HRegionServer进行管理。
HRegion 虽然是分布式存储的最小单元，但并不是底层存储的最小单元。事实上，HRegion 由一个或者多个 HStore 组成，每个 HStore 保存一个列族；每个HStrore 又由一个 memStore 和0至多个 HStoreFile 组成。HStoreFile 以HFile格式保存在HDFS上。
用户写入的数据首先会放入HMemStore，当HMemStore满了以后 flashcatch成一个HStoreFile。当storeFile数量增长到一定阈值后，系统会进行合并（minor major compaction），合并过程会进行版本的合并和删除工作，形成更大的storeFile（优化一般主要针对major合并）。
进一步来看，HBase使用三层类似B+树的结构来保存HRegion位置信息：
- Zookeeper文件：它记录了
-ROOT-表的位置信息，即root region的位置信息。 -ROOT-表：只包含一个root region，记录了.META.表中的region信息。通过root region，我们就可以访问.META.表的数据。.META.表：记录了用户表的HRegion信息，.META.表可以有多个HRegion，保存了HBase中所有数据表的HRegion位置信息。
HBase存储系统架构：
在上图中可以看到，HBase 本身是运行在 Hadoop 上的。Hadoop 提供了分布式存储和计算能力，其存储部分是由一个NameNode 和若干 DataNode 组成的：
- NameNode作为主服务器，管理文件系统的命名空间和客户端对文件的访问操作。
- 集群中的DataNode管理存储的数据。
- HDFS 允许用户以文件的形式存储数据。
- 从内部来看，文件被分成若干个数据块，而且这若干个数据块存放在一组DataNode上。
在 HDFS 中，存在两种文件类型：
- HFile：HBase中KeyValue数据的存储格式，HFile是Hadoop的二进制格式文件，实际上HStoreFile就是对HFile做了轻量级包装，即HStoreFile底层就是HFile。
- HLogFile：HBase中WAL（Write Ahead Log）的存储格式，物理上是Hadoop的顺序文件。
HFile 是用于实际数据存储的文件，他包括六部分：
- Data Block：保存表中的数据，这部分可以被压缩。
- Meta Block（可选的）：保存用户自定义的 key/value 对，可被压缩。
- File Info：HFile的元信息，不被压缩，用户可在这部分添加自己的元信息。
- Data Block Index：Data Block的索引。
- Meta Block Index（可选的）：Meta Block的索引。
- Trailer：读取 HFile 时会首先读取 Trailer，Trailer 保存了每个段的起始位置（Magic Number用来做安全check），然后，DataBlockIndex 会被读取到内存中，这样当检索某个 key 时，不需要扫描整个 HFile，只需从内存中找到 key 所在的 block，通过一次磁盘io将整个block读取到内存中，再找到需要的key。
HFile 里面的每个 Key/Value 对（Data Block）就是一个简单的 byte 数组。但是这个数组里面包含了很多项，并且有固定的结构，最开始是两个固定长度的数值，分别表示 Key 的长度（Key Length）和 Value 的长度（Value Length），紧接着是 Key，开始是固定长度的数值，表示 RowKey 的长度，紧接着是RowKey，然后是固定长度的数值，表示 Family 的长度，然后是 Family，接着是Qualifier，然后是两个固定长度的数值，表示 Time Stamp 和 Key Type（Put/Delete）；Value 部分没有这么复杂的结构，就是纯粹的二进制数据了。
HLog（WAL，Write Ahead Log），类似Mysql中的binlog，用来做灾难恢复，HLog记录数据的所有变更，一旦数据修改，就可以从HLog中进行恢复。
每个HRegionServer维护一个HLog，而不是每个HRegion一个，这样不同HRegion(来自不同表)的日志会混在一起，这样做的目的是，不断追加单个文件相对于同时写多个文件而言，可以减少磁盘寻址次数，因此，可以提高对表的写性能。
这种设计带来的麻烦是，如果一台HRegionServer下线，为了恢复其上的HRegion，需要将HRegionServer上的HLog进行拆分，然后分发到其它HRegionServer上进行恢复。
HLog文件就是一个普通的Hadoop顺序文件（Sequence File），顺序文件的Key是HLogKey对象，HLogKey中记录了写入数据的归属信息，除了表和HRegion名字外，同时还包括顺序号和时间戳；Value是HBase的Key/Value对象，即对应HFile中的Key/Value。结构如下图所示：
¶ Cassandra
¶ MapReduce
MapReduce是Google公司的核心计算模型，它将复杂的运行于大规模集群上的并行计算过程高度地抽象到两个函数：Map和Reduce。适合用MapReduce来处理的数据集(或任务)，需要满足一个基本要求: 待处理的数据集可以分解成许多小的数据集，而且每一个小数据集都可以完全并行地进行处理。
MapReduce极大地方便了编程人员在不会分布式并行编程的情况下，将自己的程序运行在分布式系统上。
Map-Reduce框架和分布式文件系统是运行在一组相同的节点上的，即计算节点和存储节点通常在一起。这种配置允许框架在那些已经存好数据的节点上高效地调度任务，这可以使整个集群的网络带宽被非常高效地利用。
Map-Reduce框架由单独一个master JobTracker和每个集群节点一个slave TaskTracker共同组成。master负责调度构成一个作业的所有任务，这些任务分布在不同的slave上，master监控它们的执行，重新执行已经失败的任务；slave仅负责执行由master指派的任务。
MapReduce模型的核心就是map和reduce两个函数，如下图所示：
下图说明了用MapReduce来处理大数据集的过程，就是将大数据集分解为成百上千的小数据集，每个(或若干个)数据集分别由集群中的一个结点(一般就是一台普通的计算机)进行处理并生成中间结果，然后这些中间结果又由大量的结点进行合并，形成最终结果：
- MapReduce的输入一般来自HDFS中的文件，这些文件分布存储在集群内的节点上。运行一个MapReduce程序会在集群的许多节点甚至所有节点上运行mapping任务，任意的mapper都可以处理任意的输入文件。
- 当mapping阶段完成后，这阶段所生成的中间键值对数据必须在节点间进行交换，把具有相同键的数值发送到同一个reducer。Reduce任务在集群内的分布节点同mappers的一样。这是MapReduce中唯一的任务节点间的通信过程。
- 所有数据传送都是由Hadoop MapReduce平台自身去做的，是通过关联到数值上的不同键来隐式引导的。这是Hadoop MapReduce的可靠性的基础元素。如果集群中的节点失效了，任务必须可以被重新启动。
一般而言，Hadoop的一个简单的MapReduce任务执行流程如下：
- JobTracker负责分布式环境中实现客户端创建任务并提交。
- InputFormat模块负责做Map前的预处理。
- 将RecordReader处理后的结果作为Map的输入，然后Map执行定义的Map逻辑，输出处理后的(key,value)对到临时中间文件。
- Shuffle&Partitioner：在MapReduce流程中，为了让reduce可以并行处理map结果，必须对map的输出进行一定的排序和分割，然后再交给对应的reduce。这个将map输出进行进一步整理并交给reduce的过程，就称为shuffle。Partitioner是选择配置，主要作用是在多个Reduce的情况下，指定Map的结果由某一个Reduce处理，每一个Reduce都会有单独的输出文件。
- Reduce执行具体的业务逻辑，即处理数据以得到结果的业务，并且将处理结果输出给OutputFormat。
- OutputFormat的作用是，验证输出目录是否已经存在和输出结果类型是否符合Config中配置类型，若成立则输出Reduce汇总后的结果。
在 MapReduce 模型的工作过程中，Shuffle 是一个至关重要的阶段。
Shuffle：将Map输出进行进一步整理并交给reduce的过程。
Shuffle过程是MapReduce工作流程的核心，也被称为奇迹发生的地方。要想理解MapReduce，Shuffle是必须要了解的。Shuffle过程包含在map和reduce两端中，描述着数据从map task输出到reduce task输入的这段过程。
在map端的shuffle过程是对map的结果进行划分（partition）、排序（sort）和spill（溢写），然后将属于同一个划分的输出合并在一起，并写到磁盘上，同时按照不同的划分将结果发送给对应的reduce（map输出的划分与reduce的对应关系由JobTracker确定）。Reduce端又会将各个map送来的属于同一个划分的输出进行合并（merge），然后对merge的结果进行排序，最后交给reduce处理。
¶ 键值对数据库
¶ 键值对数据库介绍
键值数据库是一种非关系数据库，它使用简单的键值方法来存储数据。键值数据库将数据存储为键值对集合，其中键作为唯一标识符，键和值都可以是从简单对象到复杂复合对象的任何内容。
键值数据库是高度可分区的，并且允许以其他类型的数据库无法实现的规模进行水平扩展。
典型应用是涉及频繁读写、拥有简单数据模型的应用内容缓存，比如会话、配置文件、参数、购物车等存储配置和用户数据信息的移动应用。
其优点是扩展性好、灵活性好、大量写操作时性能高，缺点是无法存储结构化信息、条件查询效率较低。
¶ Redis
¶ Redis 简介
Redis是一个开源的使用ANSI C语言编写、支持网络、可基于内存亦可持久化的日志型、Key-Value数据库。
Redis是一个很快的数据库，也支持比较多的数据类型，比如String、list、set和zset，支持各种原子操作，不够用的操作也可以使用 Lua 脚本扩充。
Redis的另一个特点是支持主从同步，可以从主服务器向任意数量的从服务器同步。
¶ Redis数据模型
Redis 的 Key 都为字符串类型，Value 有五种基本类型：
| 类型 | 存储的值 | 读写能力 |
|---|---|---|
| STRING | 可以是字符串、整数或者浮点数 | 对整个字符串或者字符串的其中一部分执行操作；对整数和浮点数执行自增（increment）或者自减（decrement）操作 |
| LIST | 一个链表，链表上的每个节点都包含了一个字符串 | 从链表的两端推入或者弹出元素；根据偏移量对链表进行修剪（trim）；读取单个或者多个元素；根据值查找或者移除元素 |
| SET | 包含字符串的无序收集器（unordered collection），并且被包含的每个字符串都是独一无二、各不相同的 | 添加、获取、移除单个元素；检查一个元素是否存在于集合中；计算交集、并集、差集；从集合里面随机获取元素 |
| HASH | 包含键值对的无序散列表 | 添加、获取、移除单个键值对；获取所有键值对 |
| ZSET | 字符串成员（member）与浮点数分值（score）之间的有序映射，元素的排列顺序由分值的大小决定 | 添加、获取、删除单个元素；根据分值范围（range）或者成员来获取元素 |
在 Redis 中字符串（STRING）是二进制安全的，这意味着它们没有任何特殊终端字符来确定长度，所以可以存储任何长度为 512 兆的字符串。
**列表（LIST）**是简单的字符串列表，通过插入顺序排序。一个列表结构可以有序地存储多个字符串，和表示字符串时使用的方法一样，可以添加一个元素到 Redis 列表的头部或尾部。列表的最大长度为个元素（4294967295，每个列表的元素超过四十亿）。
集合（SET）可以存储多个字符串。通过使用散列表来保证自己存储的每个字符串都是各不相同的，散列表只有键，但没有与键相关联的值。集合的最大长度为个元素（4294967295，每个列表的元素超过四十亿）。
集合除了基本的添加操作和移除操作之外，还支持很多其他操作。比如
SINTER、SUNION、SDIFF这3个命令就可以分别执行常见的交集计算、并集计算和差集计算。
**散列（HASH）**可以存储多个键值对之间的映射。散列存储的值既可以是字符串又可以是数字值，并且用户同样可以对散列存储的数字值执行自增操作或者自减操作。
**有序集合（ZSET）**是Redis里比较有特色的一种数据结构，有序集合和散列一样，都用于存储键值对。有序集合的键被称为成员（member），每个成员都是独一无二的；值则被称为分值（score），分值必须为浮点数。有序集合是Redis里面唯一一个既可以根据成员访问元素（这一点和散列一样），又可以根据分值以及分值的排列顺序来访问元素的结构。
¶ 其他Redis命令
HyperLogLog 是用来做基数统计的一种数据结构。HyperLogLog 的优点是在输入元素的数量或者体积非常非常大时，计算基数所需的空间总是固定的、并且是很小的，每个 HyperLogLog 键只需要花费 12 KB 内存，就可以计算接近 个不同元素的基数。因为 HyperLogLog 只会根据输入元素来计算基数，而不会储存输入元素本身，所以HyperLogLog 不能像集合那样，返回输入的各个元素。
Redis事务允许一组命令在单一步骤中执行，在一个事务中的所有命令作为单个独立的操作顺序执行；Redis事务是原子的，原子意味着要么所有的命令都执行，要么都不执行。
分区是将数据分割成多个 Redis 实例，每个实例将只包含键子集。分区技术允许更大的数据库，使用多台计算机的内存总和；可以按比例在多内核和多个计算机计算，以及网络带宽向多台计算机和网络适配器。
Redis支持备份/持久化，SAVE命令用于创建当前 Redis 数据库的备份，执行后会创建.rdb文件保存当前快照。
Redis的持久化技术是八股的重要内容，课程上介绍的是 RDB 持久化。
Redis 数据库可以配置安全保护的，所以任何客户端在连接执行命令时需要进行身份验证。
¶ DynamoDB
¶ 图数据库
¶ Neo4j
Neo4j 是一个高性能的 NoSQL 图形数据库，使用图（graph）相关的概念来描述数据模型，把数据保存为图中的节点以及节点之间的关系。
Neo4j 中两个最基本的概念是节点和边，节点表示实体，边则表示实体之间的关系。节点和边都可以有自己的属性。不同实体通过各种不同的关系关联起来，形成复杂的对象图。