大数据学习笔记

一、大数据介绍

1. Big Data

• Data whose scale, diversity, and complexity require new architecture, techniques, algorithms, and analytics to manage it and extract value and hidden knowledge from it

• Large T (dimension of each vector) and large N (number of training samples)

• 特点 3V：
• Scale (Volume): 数据量大
• Complexity (Variety): 种类复杂
• Speed (Velocity): 产生速度很快

二、关系型

1. Table/Relation

结构

• 列：一个属性，有明确的数据类型，并且是原子类型（无嵌套结构）

• 行：一个记录

• 通常是瘦长的

• Schema：类型

• Instance：具体值

• Key：特殊的列，唯一的，主键、外键

SQL

create table student(
	id int NOT NULL,
	name varchar(255),
	class_id int,
	primary key (id),
	foreign key (class_id) references class(id)
	);

insert into Student values (131234, ‘张飞’, 1995/1/1, M, ‘计算机’, 2013, 85);

delete from Student where ID = 131234;

update Student set GPA = 86 where ID = 131234;

• 选择：提取行

• 投影：提取列

• 连接：将两个表根据一个字段进行拼接

• Group by

2. DBMS

系统架构

• Parser：语法解析，语法检查，表名、列名、类型检查

• Query Plan：产生多组计划并估算时间，在其中选择最佳的

• Execution Engine：根据计划，完成相应的运算和操作

• Transaction management：实现ACID、写日志、加锁，保证并行事务的正确性

数据存储

• 使用 Page + Tuple 进行存储

• Page 为系统 Page 大小的整数倍

• Tuple 先存边长字段的偏移量，再在后面存储真正内容

索引

• 树索引相比哈希索引多支持了范围查询

• B^+^ 树

• 主索引决定数据顺序，二级索引存储page id、slot id

• 是否使用索引根据 query optimizer 的评估结果

缓存

• 由于数据访问具有局部性：
• Temporal locality (时间局部性)：同一个数据元素可能会在一段时间内多次被访问
• Spatial locality (空间局部性)：位置相近的数据元素可能会被一起访问

Join 运算的实现

• 遍历：需要读 M~r~ + BM~r~M~s~ 个 page，可以依靠索引进行判断，减少次数

• Hash Join：现根据一张表的 joinkey 建立哈希表，再通过哈希表找到所有匹配
• 当哈希表超过内存大小时，需要根据 joinkey 进行分区

• Sort Merge Join: 先分成排好序的块，再将块进行归并，一般用于已经排好的数据

ACID

• 原子性：要么完全执行，要么完全没执行

• 一致性：执行前后状态都是正确的

• 隔离性：并发事务互不影响

• 持久性：commit以后，结果不消失

事务冲突

• 读脏数据：读了别人改了未提交的

• 更新丢失：重写了别人修改后的数据

• 不可重复读：写了别人已经读的数据

• 解决方案
• 悲观
• 2P 在事务执行前对用到的数据进行加锁，事务结束前再解锁
• 使用循环等待检测避免死锁
• 乐观
• 事务提交前检查是否有冲突
• Snapshot isolation

事务日志

• WAL：在 write 和 commit 前记录意向到 log 中

• 数据存储的 page header 中要保存最新的日志号，避免数据写回磁盘，但缓存中的 log 丢了

• 需要 checkpoint 来减少恢复时间

3. 数据仓库

定义

数据立方

• 多维的数据表示

• 上卷（rollup）：求和

• 下钻（drill down）：展开

• 切片（slice）：选某一维度

• 切块（dice）：选某几个维度

列式存储

• 当大部分情况只涉及某几列

• 会读比较完整的数据

4. 分布式数据库

水平分片

• 根据 key 的哈希结果

• 对于join操作，如果使用的是分区 key，则各自执行

• 如果不是则重新分片，再分发

• 分布式事务也是2 phase
• 第一阶段询问能否执行
• 第二阶段执行，并收集执行结果

三、大数据存储系统

1. 分布式文件系统

CAP

• Consistency

• Availability

• Partition tolerance

NFS

• 用于共享文件

• 保证了操作的无状态以及幂等性

• 使用cache
• 关闭时写回
• 使用缓存前比较GETATTR

AFS

• 设计目标：高可扩展性

• 把被动询问改成主动通知

• 会缓存整个文件而不是数据页，且缓存在硬盘中

GFS/HDFS

• 不再是系统级的文件系统，而是用户态的

• 优化：大块数据的顺序读、并行追加

• 放弃：已有文件的修改

• 分为 Name Node 和 Data Node
• Name Node 存储文件的 metadata
• Data Node 存储文件的数据块

• 数据块
• 定长：64 MB
• 三份，冗余在不同 node 上

• 读取
• 从 Name Node 获取读取的目标
• 直接从 Data Node 上读取

• 写入
• 从 Name Node 获取写入的目标
• 写入到一个 Data Node 上，Data Node 会向后传递数据，都传输完成后再写入磁盘
• 对于并发写一个数据块的操作，单 Data Node 上进行并发控制

2. 键值对存储

Dynamo

• 单个机子底层仍是关系型数据库

• 将 key 进行哈希，根据哈希值分配到一个节点上

• 一个节点的数据，同时还会备份到其后面的两个节点上

• Quorum（N, W, R）
• N 个副本
• 写 >= W 个
• 读 >= R 个
• W + R > N
• 利用了最终一致性，保证了高可用

HBase

• 使用<row key, column family: column key, version, value> 的模式存储

• column family 需要预先定义

// put "mytable", "abc","mycf:a", "789"
Put put = new Put("abc".getBytes());
put.add("mycf".getBytes(), "a".getBytes(), "789".getBytes());
table.put(put);
table.close();

• 下层是 HDFS，所以冗余交个 HDFS 来保证

• 使用 B^+^ 树来找对应的node

• 使用 LSM 树来尽量使用顺序写
• 使用多层结构
• 相邻层之间可以进行归并，每层且都有自己内部的顺序
• 修改和删除也采用写的形成，通过归并实现对旧数据的删除
• 读操作需要遍历，找到的第一个就是，比 B^+^ 树性能差。

Cassandra

• 结合了前两者，多了super column key

• 本地使用文件而不是 HDFS， 通过一致性哈希保证备份冗余

3. 文档数据库

MongoDB

• 采用JSON作为基础数据类型，存储为BSON的二进制

db.student.insert({})

db.student.find({major:""},{name:1, year:1})

4. 图数据

Neo4j

• 使用自定义结构存储在本地磁盘

• 使用 Cypher 查询

CREATE (张飞:Student，{name:“张飞”， major: “计算机”,year: 2013})

CREATE (体系结构:Course，{name:“体系结构”})

CREATE (张飞)‐[:Takecourse,{year:2014, grade:85}]‐>(体系结构)

MATCH (x {name:”张飞”}) RETURN x
找具有name:”张飞”属性的顶点

MATCH (x:Student)‐[:Takecourse]‐>(:Course {name:”体系结构”})
RETURN x
找到所有选修体系结构课程的学生顶点

JanusGraph

• 使用 KV 来存储

• 使用 Gremlin 来查询

g.V().has('name','hercules').out('father').values('name')

三、分布式协调系统

1. Zookeeper

• 2f+1 容忍 f 个

• Data Tree
• 每个顶点是一个Znode

• 所有节点维护相同的 Data Tree

• 一主多从

• 写入
• Request Processor：从机发到主机，主机将请求打包成幂等事务
• Atomic Broadcast：主带领从串行执行操作 ZAB协议
• 主广播写
• 主收到 f 个 ack，就广播 commit
• 当收不到 f 个 ack 时，进入恢复态
• 选择拥有最大 txn id 的节点做主
• Replicated DB：所有节点将改动保存到本地

四、大数据运算系统

1. MapReduce

数据模型：

• Map(ik, iv) => {<mk, mv>}

• Combiner(mk, {mv}) => <mk, mv`>

• Reduce(mk, {mv}) => {<ok, ov>}

处理架构

• JobTracker：用来分配任务

• TaskTracker：用来执行 Map 或 Reduce

2. PageRank

计算公式

若数据精度不够，则两边同乘 N， 设 R'~u~= NR~u~

3. 图计算

GraphLite

• 采用 BSP 模型：分成一个个超步，超步之间进行同步，超步内部使用并行计算

• 基于顶点编程：图计算调用顶点的compute，然后可以接受或发送消息

• 当所有节点处于非活跃状态时结束

GAS 模型

• 由于跨节点之间通信很多，浪费

• 在每个节点上维护顶点的副本，先本地求局部和

4. Hive

特点

• 管理和处理结构化数据

• 融合了 MapReduce 和 SQL

HDFS

• 将数据存储在 HDFS 中

• /user/hive/warehouse/表名/pkey=value/bkey=value

HiveQL

• 类似 SQL

数据模型

• 列可以是复杂的数据类型，比如数组、map、结构体

• 可以使用 SerDe 读取外部数据

• pkey 和 bkey 都是手工指定的，不是表中数据

5. Storm 数据流处理

概念

• 计算会形成一个有向无环图DAG

• 每个顶点代表一种运算
• Spout：仅有输出
• Bolt：有输出和输入

• 上游节点发送给下游
• Shuffle：随机发送
• Fields：根据 tuple 中某个字段的取值

6. Kafka 消息日志

角色

• Producer

• Consumer：主动读

• Broker：用来存储 Producer 的消息，为 Consumer 提供消息读取服务

消息的组织

• Topic：每个 Topic 对应一个 log

• Partition：每个 Topic 可以换分成多个，且内部有序，之间无序

• 发布时需指定 topic 和 partition

7. 内存数据库

Memcached

• 单机

• 数据在内存中以 hash table 的形式

Redis

• 分布式

8. Spark

思路

• MapReduce通过HDFS进行作业间的数据共享，代价高

• 把数据放到内存里

基础数据结构

• RDD Resilient Distributed Data Sets

• 只读

• 通过记录 lineage 来备份

• JavaRDD\<T\> 和 JavaPairRDD<K,V>

RDD 的运算

• Transformation
• 输入输出都是 RDD

• Action
• 输入时 RDD，输出是返回给 driver 的结果

Spark SQL

• DataFrame：在 RDD 上定义了关系

• 可以从json、parquet、jdbc等文件中读取