大数据学习笔记

一、大数据介绍

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

text
1
2
3
4
5
6
7
8
9
10
11
12
13
14
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 运算的实现

  • 遍历：需要读 Mr + BMrMs 个 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 需要预先定义
text
1
2
3
4
5
6
// 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的二进制
text
1
2
3
4
db.student.insert({})

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

4. 图数据

Neo4j

  • 使用自定义结构存储在本地磁盘
  • 使用 Cypher 查询
text
1
2
3
4
5
6
7
8
9
10
11
12
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 来查询
text
1
2
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= NRu

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等文件中读取