1 背景介绍

1.1 数据产生的三个阶段

• 运营式系统阶段（被动）
• 用户原创内容阶段（主动）
• 感知式系统阶段（自动）

1.2 数据种类定义

1.3 大数据的定义

大数据是指利用常用软件工具捕获、管理和处理数据所耗时间超过可容忍时间的数据集。

1.4 大数据的4V特性

• Volume 体积： Volume scale of data 数据的体积规模
• Variety 种类： Variety different forms of data 数据的多种不同形式
• Velocity 速度： Velocity analysis of streaming data 流数据的速度分析
• Veracity* 准确性： Veracity uncertainty of data 数据的不准确性

1.5 大数据特征

• Value 价值：价值密度低是大数据的一个典型特征。
• Variety 多样性：能够在不同的数据类型中进行交叉分析是大数据的核心技术之一。
• Velocity 速度：<1s 秒级响应 实时处理的要求是区别大数据应用和传统数据仓库技术、BI技术的关键差别之一。
• Volume 数据量：>1PB PB级数据

1.6 数据处理需求与传统平台硬件扩展能力之间的差距不断扩大

1.7 大数据分析与传统BI分析的区别

分析过程的区别

• 传统BI分析：事务 ---> 关系型数据库 ---批处理--> 数据仓库 ---> 分析
• 大数据分析：非结构化 ---流式--> 集群化数据库 <--- 组织分析

1.8 大数据应用的类型

2 E-R模型

2.1 数据库设计过程

需求分析 <==> 概念数据库设计 <==> 逻辑数据库设计 <==> 物理数据库设计

2.2 E-R模型基本概念

• 实体（Entity）：客观存在可以相互区分的事物（矩形）
• 属性（Attribute）：实体具有的某一特性（椭圆）
• 域（Domain）：属性的取值范围，即值集
• 实体型（Entity Type）：实体名和其属性名集共同构成
• 实体集（Entity Set）：同型实体的集合
• 联系（Relationship）：多个实体之间的相互关联（菱形）
• 联系集（Relationship Set）：同类联系的集合
• 联系的元或度（Degree）：参与联系的实体集的个数
• 码（Key）
  • 超码：能唯一标识实体的属性或属性组
  • 候选码：其任意真子集都不能成为超码的最小超码
  • 主码：从所有候选码中选定的一个用来区别同一实体集中的不同实体的候选码（下划线）
• 参与（Participation）：实体集之间的关联
  • 全部参与：实体集E中的每个实体都参与到联系集R中的至少一个联系，E全部参与R（双线连接）
  • 部分参与：实体集E中只有部分实体参与到联系集R的联系中，E部分参与R
• 存在依赖（Existence Dependency）：实体x的存在依赖于实体y的存在，x存在依赖于y
  • x称为支配实体，y称为从属实体
  • 存在依赖一定全部参与
  • 参照完整性：一个实体集的属性是另一实体集的主码属性
• 角色（Role）：实体在联系中的作用

2.3 属性的类型

• 复合（Composite）属性：可以划分为更小的属性的属性，对应简单属性
• 多值属性：有多于一个取值的属性，对应单值属性（双椭圆）
• 派生（Derived）属性：可以从其他相关的属性或实体派生出来的属性值，对应基属性/存储属性（虚椭圆）

2.4 映射的基数（Mapping Cardinalities）

实体之间联系的数量，即一个实体通过一个联系集能与另一实体集相关联的实体的数目。

• 一对一（1:1），一对多（1:m），多对多（m:n）
• 在E-R图中用箭头或线段表示（箭头表示1，线段表示m）

2.5 键

• 实体主键在E-R图中用下划线表示
• 联系集的键：在联系集中可唯一确定一个联系的属性

参与联系的实体集的主键的联合包含联系集的主键

2.6 弱实体集（Weak Entity Set）

如果一个实体集的所有属性都不足以形成主码的，则称这样的实体集为弱实体集。

2.6.1 分辨符（Discriminator）

弱实体集中用于区别依赖于某个特定强实体集的属性集合，也称作部分码（Partial Key）

2.6.2 弱实体集的主码

由该弱实体集所存在依赖的强实体集的主码和该弱实体集的分辨符组成。

2.6.3 为什么使用弱实体集？

• 避免数据冗余、以及因此带来的数据的不一致性
• 反映了一个实体对其他实体依赖的逻辑结构
• 弱实体集可以随它们的强实体集的删除而自动删除
• 弱实体集可以物理地随它们的强实体集存储

2.6.4 弱实体集在E-R图中的表示

• 弱实体集：双边框矩形
• 标识性联系：双边框菱形
• 联系集双线连接弱实体集（全部参与），箭头指向强实体集（一对多联系）
• 弱实体集的分辨符：下划虚线

2.7 扩展E-R特性

• 特殊化（Specialization）：根据实体集中子集的差异特性对实体集进行分组（ISA倒三角）
• 一般化（概括）（Generalization）：根据实体集共有的性质，合成一个较高层的实体集（逆特殊化）
• 属性继承（Attribute Inheritance）：高层实体集的属性被低层实体集自动继承
  • 层次结构（Hierarchy）：实体集作为低层实体只能参与到一个ISA联系中
  • 格结构（Lattice）：低层实体集可以参与到多个ISA联系中
• 聚集（Aggregation）：实体集与联系集之间的联系，以及联系集之间的联系，解决E-R模型不能表达联系间的联系、或联系集与实体集间的联系的问题

2.8 设计E-R图的过程

1. 确定实体类型
2. 确定联系类型
3. 连接实体类型和联系类型，组合E-R图
4. 确定实体类型和联系类型的属性
5. 确定实体类型的码

2.9 E-R模型向关系模式的转换

• 实体 → 关系
• 属性 → 关系的属性
• 复合属性 → 将每个组合属性作为复合属性所在实体的属性
• 多值数型 → 新的关系 + 所在实体的码
• 一对多联系 → 将单方参与实体的码作为多方参与实体的属性
• 多对多联系 → 将联系定义为新的关系，属性为参与双方的码
• 一对一联系 → 若联系一方全部参与，则将联系另一方的码作为全部参与一方的属性
• 弱实体集 → 所对应的关系的码与弱实体集本身的分辨符加上所依赖的强实体集的码
• 概括 → 高层实体集和低层实体集分别转为表，低层实体集所对应的关系包括高层实体集的码
• 聚集 → 实体集A和B与他们的联系集R被看成实体集C，C与另一实体集D构成联系S，则S所对应的关系的码由R和D的码构成

3 数据库应用设计和优化基础

3.1 优化

• 不访问不必要的数据
  • B*Tree/hash等索引方法 定位必要的数据
  • Column Store（列存储？）/分表方式 分开存储数据
• 合理利用硬件提高访问效率
  • 缓存：消除对数据的重复访问
  • 批处理：减少交互的次数（网络、磁盘）
  • 新硬件：降低后端的延时，提高效率
• 提高系统吞吐量
  • 细化工作单元，减少串行操作
  • 优化硬件配置，提高整体TCO和硬件利用率
  • 合理拆分（水平、垂直拆分），提高系统整体吞吐能力

3.2 响应时间 vs 吞吐量

性能：衡量完成特定任务的速度或速率
响应时间：衡量系统与用户交互时多久能够收到响应
吞吐量：衡量系统在单位时间里可以完成的任务量
*响应时间 = 服务时间 + 队列时间
经典响应时间曲线：
Arrival Rate = 1.55 trx/s
Service Time = 2 ms/trx
Queue Time = 1ms/trx
Response Time = 3ms/trx

3.3 磁盘性能估计

3.3.1 访问时间

• 从发出请求到数据开始传输之间的时间
• 寻道时间（Seek Time）
  • 磁盘臂定位时间，即磁盘臂移动到正确的磁道所需的时间
  • 与移动距离成正比，平均寻道时间是最坏时间的 1/3（4-10 ms）
• 旋转等待时间（Rotational latency）
  • 寻道结束后，等待被存取的扇区出现在读写头下面的时间
  • 平均旋转等待时间是磁盘旋转一周时间的 1/2（2-5 ms）

3.3.2 数据传输率

• 从磁盘获得数据或向磁盘存储数据的速率（4-8 MB/s）

3.3.3 平均故障时间

• 预期系统无故障连续运行的时间
• （30,000-800,000 小时，即 3.4-91 年）

3.4 磁盘块存取的优化

• 在主存储器中对块进行缓冲以减少块的读写次数
• 按柱面组织数据
• 使用多个磁盘
• 磁盘镜像
• 磁盘臂调度——电梯算法
• 利用非易失性RAM作为写缓冲
• 预读和双缓冲
• 日志磁盘

3.5 I/O调度器（Scheduler）

• 目标
  • 减少寻道时间，让旋转一周读取更多扇区
• 任务
  • 1.管理块设备请求队列
  • 2.分配I/O资源给请求
• 做法
  • 合并 + 排序

3.5.1 合并

• 同一或多个相邻扇区的请求 ---合并--> 一次I/O
• 一次I/O对应一条寻址指令
• 减少系统开销和寻址次数

3.5.2 排序

• I/O请求按照扇区增长序列
• Sorted Queue

3.5.3 linus电梯

简单的合并+排序
避免请求饥饿

• 检测到队列中有长时间没有被处理的请求，就暂时中止插入

缺点

• I/O调度器并没有直接处理饥饿请求，没有解决实质问题

3.5.4 ANTICIPATORY(AS)

• 2.6.18 之前默认的I/O调度器
  • 基于预测算法
• 处理完一个请求，不直接处理下一个请求，而是针对上一个请求的进程等待片刻，如果该进程发出一个与当前扇区相同或相邻的请求，则优先处理
• 默认等待6ms
• 如果系统存在大量相邻扇区的请求，性能会很好
  • 当有一个I/O发生时，若又有进程请求I/O操作，则将产生一个默认的6毫秒猜测时间，对下一个进程请求的I/O进行猜测。
  • 这对于随机读写会造成比较大的延时，对数据库应用也很糟糕，而对于Web Server等则会表现得不错。
  • 这个算法可以简单理解为是面向低速磁盘的，猜测时间实际上是为了减少磁头移动的时间。

3.5.5 CFQ(COMPLETELY FAIR QUEUING)

• 2.6.18 之后默认的I/O调度器
  • 每一个提交I/O请求的进程都有一个自己单独的Sorted Queue
• 在一个时间片中，CFQ调度器选择一个进程，处理其I/O队列
• 不是简单的轮询，基于红黑树选择进程（进程优先级）
• 特点是保证各个进程的I/O请求能被均衡处理
• 也有类似AS的等待机制
• 适合多进程同时发出多I/O请求的状况，CFQ对每一个进程维护一个I/O队列，各个进程发来的I/O请求会被CFQ以轮询方式处理，也就是对每一个I/O请求都是公平的。这使得CFQ很适合随机读写的应用（eg: OLTP DB）

3.5.6 DEADLINE

• 带超时的调度算法
  • 除了CFQ本身具有的IO队列之外，DEADLINE额外分别为读IO和写IO提供了FIFO队列。
  • 读FIFO队列的最大等待时间为500ms，写FIFO队列的最大等待时间为5s。
  • 优先级：FIFO(Read) > FIFO(Write) > CFQ
• 3个I/O Queue
  • Read Queue(default timeout: 500ms) FIFO
  • Write Queue(default timeout: 5000ms) FIFO
  • Sorted Queue
• 缺点
  • 当系统存在大量顺序请求时，可能导致请求无法被很好地排序，引发频繁寻道，比较适合随机访问多、时效性高的场景
• 特点
  • 权衡了全局吞吐量和系统延迟
  • 避免写饥饿，当写饥饿次数达到writes_starved，写请求会被立即处理

3.5.7 NOOP(NO OPERATION)

• 最简单的I/O调度策略，本质上就是先来先到服务FIFO，意思就是哪个进程先请求I/O系统就先为哪个服务
• 面向随机访问设备（例如SSD）
• 对于SSD
  • 选择NOOP还是DEADLINE？
  • DEADLINE平衡读写比例

3.5.8 比较

对于数据库应用

• CFQ综合表现最好
• AS表现最差
• DEADLINE在DSS环境表现比CFQ更好一点

3.6 数据访问流程

结合流程图理解

3.7 服务器体系结构

商用服务器大体可以分为三类

• 对称多处理器结构（SMP: Symmetric Multi-Processor）
• 非一致存储访问结构（NUMP: Non-Uniform Memory Access）
• 海量并行处理结构（MPP: Massive Parallel Proccessing）

4 大型数据库系统应用设计方法

……