Posted Updated Database / SQL DB6 minutes read (About 859 words)

SQL语法

基本操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
SELECT			<field>, DISTINCT <field>
INTO			<new_tbl> [IN <other_db>]
FROM			<tbl>
WHERE			<field> <OP> <value>/<field>
ORDER BY		<field> [ASC/DESC];

INSERT INTO		<tbl>[<field>]
VALUES			(<value>);

UPDATE			<tbl>
SET				<field> = <value>
WHERE			<field> <OP> <value>/<field>;

DELETE
FROM			<tbl>
WHERE			<field> <OP> <value>/<field>;

数据库、表、索引、视图

创建

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
!-- 创建数据库
CREATE DATABASE <db_name>;

!-- 创建表
CREATE TABLE <tbl>(
	<field>		<dtype>,
	<field>		<dtype>		<CSTRT>,					!-- MSSQL、ORACLE
	<CSTRT>		(<field>,),								!-- MySQL
	CONSTRAINT [<cstrt_name>] <cstrt> (<field>,)		!-- common
)

!-- 创建索引
CREATE INDEX <index_name>
ON <tbl> (<field>);

!-- 创建视图
CREATE VIEW <view_name> AS
<select_expr>;
自增字段
1
2
3
4
5
6
7
8
9
10
!-- MSSQL
<field> <dtype> IDENTITY
!-- MySQL
<field> <dtype> AUTO_INCREMENT
!-- ORACLE：创建自增序列，调用`.nextval`方法获取下个自增值
CREATE SEQUENCE <seq>
MINVALUE <min>
START WITH <value>
INCREMENT BY <step>
CACHE <cache>				!-- 提高性能

丢弃

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
!-- 丢弃索引
!-- MSSQL
DROP INDEX <tbl>.<index_name>;
!-- ORACLE
DROP INDEX <index_name>;
!-- MySQL
ALTER TABLE <tbl>
DROP INDEX <index_name>;

!-- 丢弃表/数据
DROP TABLE <tbl>;
TRUNCATE TABLE <tbl>;

!-- 丢弃数据库
DROP DATABASE <db_name>;

!-- 丢弃视图
DROP VIEW <view>;

修改表

1
2
3
4
5
6
7
8
9
10
11
!-- 添加列
ALTER TABLE <tbl>
ADD <field> <dtype>;

!-- 删除列
ALTER TABLE <tbl>
DROP COLUMN <field>;

!-- 修改类型
ALTER TABLE <tbl>
ALTER COLUMN <field> <dtype>;

关键字

TOP

  • MSSQL：SELECT TOP <num>/<num> PERCENT *
  • MYSQL：LIMIT <num>
  • ORACLE：WHERE ROWNUM <= <num>

Alias

  • AS：指定行、列别名

Join

  • [INNER] JOIN
  • LEFT JOIN
  • RIGHT JOIN
  • FULL JOIN

Union

  • UNION：合并SELECT结果集
    • 要求结果集中列数量、类型必须相同

NULL

  • IS [NOT] NULL：比较是否为NULL值
  • 比较符无法测试NULL值

符号

运算符

  • =：有些方言可以使用==
  • <>：有些方言可以使用!=
  • >
  • <
  • >=
  • <=
  • BETWEEN <value> AND <value>
  • [NOT] IN (<value>)
  • [NOT] LIKE <pattern>
    • %：匹配0个、多个字符
    • _：匹配一个字符
    • [<char>]：字符列中任意字符
    • ^[<char>]/[!<char>]：非字符列中任意字符

逻辑运算

  • AND
  • OR

符号

  • '：SQL中使用单引号包括文本值
    • 大部分方言也支持"双引号

数据类型

MySQL

TEXT类型 描述
CHAR([<size>])
VARCHAR([<size>])
TINYTEXT
LONGTEXT
MEDIUMITEXT
BLOB
MEDIUMBLOB
LONGBLOB
ENUM(<val_list>)
SET
NUMBER类型 描述
TINYINT([<size>])
SMALLINT([<size>])
MEDIUMINT([<size>])
INT([<size>])
BIGINT([<size>])
FLOAT([<size>])
DOUBLE([<size>])
DECIMAL([<size>])
DATE类型 描述
DATE()
DATETIME()
TIMSTAMP()
TIME()
YEAR()

MSSQL

ASCII类型 描述
CHAR([<size>])
VARCHAR([<size>])
TEXT
UNICODE类型 描述
CHAR([<size>])
VARCHAR([<size>])
text
BINARY类型 描述
bit
binary([<n>])
varbinary([<n>])
image
NUMBER类型 描述
TINYINT
SMALLINT
MEDIUMINT
INT
BIGINT
DECIMAL(p, s)
FLOAT([<n>])
REAL
SMALLMONEY
MONEY
DATE类型 描述
DATETIME
DATETIME2
SMALLDATETIME
DATE
TIME
DATETIMEOFFSET
TIMESTAMP

约束

  • 建表时添加约束

    • MSSQL、ORACLE：可直接在字段声明后添加约束
    • MySQL：需独立指定约束

  • 向已有表添加约束

    • 可以添加匿名、具名约束
    • MSSQL、ORACLE：有COLUMN关键字

  • 删除约束

    • MySQL：使用约束关键字指定
    • MSSQL、ORACLE：使用CONSTRAINT关键字指定

NOT NULL

1
<field> <dtype> NOT NULL

DEFAULT

DEFAULT

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
!-- 建表
<field> <dtype> DEFAULT <value>

!-- 已有表添加
!-- MySQL
ALTER TABLE <tbl>
ALTER <field> SET DEFAULT <value>;
!-- MSSQL、ORACLE
ALTER TABLE <tbl>
ALTER COLUMN <field> SET DEFAULT <value>;

!-- 删除
!-- MySQL
ALTER TABLE <tbl>
ALTER <field> DROP DEFAULT;
!-- MSSQL、ORACLE
ALTER TABLE <tbl>
ALTER COLUMN <field> DROP DEFAULT;

UNIQUE

UNIQUE

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
!-- 建表
!-- MySQL、MSSQL、ORACLE
CONSTRAINT [<cstrt_name>] UNIQUE (<field>,)
!-- MySQL
UNIQUE [KEY] [<cstrt_name>] (<field>)
!-- MSSQL、ORACLE
<field> <dtype> UNIQUE

!-- 已有表添加
!-- MySQL、MSSQL、ORACLE
ALTER TABLE <tbl>
ADD UNIQUE(<field>);
ALTER TABLE <tbl>
ADD CONSTRAINT <cstrt_name> UNIQUE(<field>,);

!-- 删除
!-- MySQL
ALTER TABLE <tbl>
DROP INDEX <cstrt_name>;
!-- MSSQL、ORACLE
ALTER TABlE <tbl>
DROP CONSTRAINT <cstrt_name>;

PRIMARY KEY

PRIMARY KEY

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
!-- 建表
!-- MySQL、MSSQL、ORACLE
CONSTRAINT [<cstrt_name>] PRIMARY KEY (<field>,)
!-- MYSQL
PRIMARY KEY (<field>,)
!-- MSSQL、ORACLE
<field> <dtype> PRIMARY KEY


!-- 已有表添加
!-- MySQL、MSSQL、ORACLE
ALTER TABLE <tbl>
ADD PRIMARY KEY (<field>,);
ALTER TABLE <tbl>
ADD CONSTRAINT <cstrt_name> PRIMARY KEY (<field>,);

!-- 删除
!-- MySQL
ALTER TABLE <tbl>
DROP PRIMARY KEY;
!-- MSSQL、ORACLE
ALTER TABLE <tbl>
DROP CONSTRAINT <cstrt_name>;

FOREIGN KEY

FOREIGN KEY

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
!-- 建表
!-- MySQL、MSSQL、ORACLE
CONSTRAINT [<cstrt_name>] FOREIGN KEY (<field>,)
REFERENCES <tbl>(<field>,)
!-- MYSQL
FOREIGN KEY (<field>,)
REFERENCES <tbl>(<field>,)
!-- MSSQL、ORACLE
<field> <dtype> FOREIGN KEY
REFERENCES <tbl>(<field>,)


!-- 已有表添加
!-- MySQL、MSSQL、ORACLE
ALTER TABLE <tbl>
ADD FOREIGN KEY (<field>,)
REFERENCES <tbl>(<field>,);
ALTER TABLE <tbl>
ADD CONSTRAINT <cstrt_name> FOREIGN KEY (<field>,)
REFERENCES <tbl>(<field>);

!-- 删除
!-  MySQL
ALTER TABLE <tbl>
DROP FOREIGN KEY <cstrt_name>;
!-- MSSQL、ORACLE
ALTER TABLE <tbl>
DROP CONSTRAINT <cstrt_name>;

CHECK

CHECK

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
!-- 建表
!-- MySQL、MSSQL、ORACLE
CONSTRAINT [<cstrt_name>] CHECK(<condition>)
!-- MySQL
CHECK (condition)
!-- MSSQL、ORACLE
<field> <dtype> CHECK(<condition>)

!-- 已有表添加
!-- MySQL、MSSQL、ORACLE
ALTER TABLE <tbl>
ADD CHECK (condition);
ALTER TABLE <tbl>
ADD CONSTRAINT <cstrt_name> CHECK (condition);

!-- 删除
!-- MySQL
ALTER TABLE <tbl>
DROP CHECK <cstrt_name>;
!-- MSSQL、ORACLE
ALTER TABLE <tbl>
DROP CONSTRAINT <cstrt_name>;

内建函数

Date

  • MySQL

    • NOW()
    • CURDATE()
    • CURTIME()
    • DATE()
    • EXTRACT()
    • DATE_ADD()
    • DATE_SUB()
    • DATE_DIFF()
    • DATE_FORMAT()

  • MSSQL

    • GETDATE()
    • DATEPART()
    • DATEADD()
    • DATEDIFF()
    • CONVERT()

NULL

  • MSSQL

    • ISNULL(<field>, <replacement>)

  • ORACLE

    • NVL(<field>, <repalcement>)

  • MySQL

    • IFNULL(<field>, <replacement>)
    • COALESCE(<field>, <replacement>)

Aggregate聚集函数

Scalar

Posted Updated Database / Hadoop11 minutes read (About 1679 words)

Hive

Hive简介

Hive是Hadoop平台上的数据仓库，面向结构化数据分析

  • 将结构化数据文件映射为一张数据库表

  • 提供完整的SQL查询功能，所用语言称为HiveQL

    • Hive将HiveQL转换为MapReduce作业，在hadoop平台运行
    • Hive相当于一个在hadoop平台上的SQL Shell
    • 方便用户使用HiveQL快速实现简单数据分析、统计，而不必 开发专用MapReduce程序，学习成本低

  • 相较于传统关系数据库，Hive具有如下特点

    ||Hive|传统关系型数据库| |———|———|———-| |数据存储|HDFS分布式文件系统|服务器本地文件系统| |查询处理|MapReduce计算模型|自行设计的查询处理模型| |应用场景|海量数据分析处理|高性能查询，实时性好| |数据更新|不支持对具体数据行修改，只能覆盖、追加|支持| |事务处理|不支持|支持| |索引支持|不支持，一般需要对数据进行全部扫描|支持，多种索引| |扩展能力|基于Hadoop平台，存储、计算强大的扩展能力|扩展性较差| |数据加载|Writing Time Schema：数据加载时无需进行模式检查，在读取数据时对数据以一定模式进行解释|Reading Time Schema：要求数据必须符合数据库表结构|

Hive服务端组件

Driver

负责将用户的编写的HiveQL查询语句进行解析、编译、优化、生成 执行计划，然后调用底层MapReduce计算模型执行，包括

  • Compiler：编译器
  • Optimizer：优化器
  • Executor：执行器

MetaStore

元信息管理器，对Hive正确运行举足轻重

  • MetaStore实际上就是Thrift服务

    • MetaStore客户端（hive、spark shell等）和服务端通过 thrift协议进行通信
    • 客户端通过连接metastore服务，实现对元数据的存取
    • 通过Thrift获取元数据，屏蔽了访问MetaStore Database 所需的驱动、url、用户名、密码等细节

  • 负责存储元数据在关系型数据库（称为MetaStore Database）

    • 元数据包括Hive创建的database、table等元信息
    • 支持的关系型数据库
      • Derby：Apache旗下Java数据库
      • MySQL

  • MetaStore服务可以独立运行，可以让多个客户端同时连接、 甚至安装到远程服务器集群，保持Hive运行的健壮性

Embedded Metastore Server(Database Derby)

内嵌模式：使用内嵌的Derby数据库存储元数据

  • 不需要额外起Metastore服务
  • 一次只能一个客户端连接，使用做实验，不适合生产环境
  • Derby默认会在调用hive命令所在目录的metastore_db文件中 持久化元数据

embeded_metastore_database

Local Metastore Server

本地元存储

  • 采用外部数据库，支持

    • MySQL
    • Postgres
    • Orcale
    • MSSQL

  • 数据库独立于hive部署，hive服务使用JDBC访问元数据，多个 服务可以同时进行

  • 本地元存储不需要单独起metastore服务，用的是跟hive在同一 进程metastore服务

local_metastore_server

Remote Metastore Server

远程元存储

  • 类似于本地元存储，只是需要单独启动metastore服务，和hive 运行在不同的进程（甚至主机）中

  • 需要在每个客户端配置文件配置连接到该metastore服务

    • hive通过thrift访问metastore

  • 此模式可以控制到数据库的连接

remote_metastore_server

hiveserver2

基于的Thrift RPC实现

  • 远程客户端可以通过hiveserver2执行对hive的查询并返回结果

    • 支持多客户端并发、身份验证

  • 可以使用JDBC、ODBC、Thrift连接hiveserver2（Thrift Server 特性）

  • hiveserver2也能访问元数据，不依赖于metastore服务

Hive客户端组件

CLI

Command Line Interface

  • 允许用户交互式的使用Hive

THrift Client/beeline

基于Thrift的JDBC Client

  • 包括JDBC/ODBC驱动程序

WEB GUI

允许用户通过WEB GUI图形界面访问Hive

  • 需要首先启动Hive Web Interface服务

Hive查询处理

过程

  1. 用户提交HQL至Driver
  2. Driver把查询交给Compiler，Compiler使用MetaStore中元信息 检查、编译
  3. 查询经过Optimizer优化交由Executor Engine执行，转换为 MapReduce作业后调用MapReduce执行
  4. MapReduce存取HDFS，对数据进行处理，查询结果返回Driver

数据类型

  • 基础数据类型

    • Integer
    • Float
    • Double
    • String

  • 复杂数据类型：通过嵌套表达复杂类型

    • Map
    • List
    • Struct

  • 还允许用户自定以类型、函数扩展系统

数据存储模型

使用传统数据库：Table、Row、Column、Partition等概念，易于 理解

Database

相当于关系型数据库中的Namespace

  • 将不同用户数据隔离到不同的数据库、模式中

Table

表格

  • 逻辑上由存储的数据、描述数据格式的相关元数据组成

    • 表格数据存放在分布式文件系统（HDFS）中
    • 元数据存储在MetaStore服务指定关系型数据库中

  • 创建表格、加载数据之前，表格在HDFS中就是一个目录， 表格分为两种类型

    • 托管表：数据文件存放在Hive数据仓库中，即HDFS中的一个 目录，是Hive数据文件默认存放路径
    • 外部表：数据文件可以存放在其他文件系统中

Partition

根据“分区列”的值，对表格数据进行粗略划分的极值

  • 存储上：是Hive中表格主目录的子目录，名字即为定义的分区列 名字

  • 逻辑上：分区不是表中的实际字段，是虚拟列

    • 根据虚拟列（可能包含多个实际字段）划分、存储表格数据
    • 同一虚拟列中字段通常应该经常一起被查询，这样在需要 存取部分数据字段时，可以只扫描部分表

Bucket

Table、Partition都是目录级别的数据拆分，指定Bucket的表格， 数据文件将按照规律拆分成多个文件

  • 每个桶就是table、partition目录中的文件

  • 一般使用Hash函数实现数据分桶，创建表时，需要指定桶数量、 分桶操作依据的列

  • 用户执行Sample查询时，Hive可以使用分桶信息，有效的Prune Data，如：对每个目录下单个桶文件进行查询

Posted Updated Database23 minutes read (About 3403 words)

物理查询优化

查询代价估算

代价模型

代价估计模型：基于CPU代价、IO代价

  • $P$：计划访问的页面数
  • $CPUTimePerPage$：读取每个页面的时间花费
  • $T$：访问的元组数，索引扫描应包括索引读取花费
    • 反映CPU代价，因为访问页面上的元组需要解析元组结构， 消耗CPU
  • $W$：selectivity，选择率/权重因子，表明IO、CPU的相关性

Selectivity

选择率：在关系R中，满足条件A <cond_op> a的元组数R和 所有元组数N的比值

  • 在CBO中占有重要地位
  • 其精确程度直接影响最优计划的选择

估计方法

  • Non-Parametric Method：非参方法，使用ad-hoc数据结构、 直方图维护属性值分布

  • Parametric Method：参数方法，使用预先估计的分布函数 逼近真实分布

  • Curve Fitting：曲线拟合法，使用多项式函数、最小标准差 逼近属性值分布

  • Sampling：抽样法，从数据库中抽取部分元组，针对样本进行 查询，收集统计数据

    • 需要足够多样本被测试才能达到足够精度

  • 综合法

单表扫描算法

索引

两表联接算法

todo

Nested Loop

嵌套循环联接算法：扫描外表，读取记录根据join字段上的 索引去内表中查询

  • 适合场景
    • 外表记录较少（<1w）
    • 内表已经创建索引、性能较好
    • inner、left outer、left semi、left antisemi join

嵌套循环联接算法

  • 搜索时扫描整个表、索引
1
2
3
4
for each row R1 in the outer table:
	for each row R2 in the inner table:
		if R1 join with R2:
			return (R1, R2)
  • 外部循环逐行消耗外部输入表，当其数据量很大时可以并行扫描 内表
  • 内表被外表驱动：内部循环为每个外部行执行，在内表中搜索 匹配行

基于块嵌套循环联接算法

  • 每次IO申请以“块”为单位尽量读入多个页面
  • 改进获取元组的方式
1
2
3
4
5
6
7
8
9
10
for each chunk c1 of t1
	if c1 not in memory:
		read chunk c1 to memory
	for each row r1 in chunk c1:
		for each chunk c2 of t2:
			if c2 not in memory:
				read chunk c2 into memory
			for each row r2 in c2:
				if r1 join with r2:
					return(R1, R2)
  • 内存循环最后一个块使用后作为下次循环循环使用的第一个块 可以节省一次IO

索引嵌套循环联接算法

  • 索引嵌套循环连结：在内表中搜索时使用索引，可以加快联接 速度
  • 临时索引嵌套循环连结：为查询临时生成索引作为查询计划的 一部分，查询完成后立刻将索引破坏

(Sort)Merge Join

排序归并联接算法

  • 适合场景
    • 联接字段已经排序，如B+树索引
    • inner、left outer、left semi、left anti semi、 right outer、right semi、right anti semi join、union
    • 等值、非等值联接，除!=/<>

算法

  • 确保两个关联表都是按照关联字段进行排序

    • 若关联字段已经有排序一致的可用索引，可以利用索引直接 进行merge join操作
    • 否则先对关联字段进行排序，表过大无法一次载入内存时 需要分块载入

  • 从每个表分别取记录开始匹配（升序）

    • 若符合关联条件，放入结果集
    • 否则丢关联字段较小记录，取对应表中下条记录继续 匹配，直到整个循环结束
    • 对于多对join，通常需要使用临时表进行操作

      todo

Hash Join

哈希联接：利用Hash Match联接

  • HJ处理代价非常高，是服务器内存、CPU头号杀手，需要对数据 进行分区时，还会造成大量异步磁盘I/O，避免大数据的HJ， 尽量转化为高效的SMJ、NLJ

    • 表结构设计：冗余字段
    • 索引调整设计
    • SQL优化
    • 冗余表：静态表存储统计结果

  • 类似任何hash算法，内存小、数据偏斜严重时，散列冲突会比较 严重，此时应该考虑使用NIJ

  • 适合场景

    • 两表数据量相差非常大
    • 对CPU消耗明显，需要CPU资源充足
    • 只适合（不）等值查询

In-Memory Hash Join

db_hash_join

build阶段

以操作涉及字段为hash key构造hash表

  • 从构造输入表中取记录，使用hash函数生成hash值

  • hash值对应hash表中的buckets，若一个hash值对应多个桶， 则使用链表将联接桶

  • 构造输入表处理完毕之后，其中记录都被桶关联

  • build表构建的hash表需要频繁访问，最好能全部加载在内存中 ，因此尽量选择小表，避免使用GHJ
probe阶段

  • 从探测输入中取记录，使用同样hash函数生成hash值

  • 根据hash值，在构造阶段构造的hash表中搜索对应桶

  • 为避免冲突，bucket可能会联接到其他bucket，探测操作 会搜索整个冲突链上的buckets查找匹配记录
具体操作

以下操作内部实现其实都是hash join，只是对应算符不同而已

  • join操作

    • 使用join字段计算hash值
    • 使用顶端输入构造hash表，底端输入进行探测
    • 按照联接类型规定的模式输出（不）匹配项
    • 若多个联接使用相同的联接列，这些操作将分组为一个 哈希组

  • grouby操作、unique操作

    • 使用groupby字段、所有select字段计算hash值
    • 使用输入构造hash表，删除重复项、计算聚合表达式
    • 扫描hash表输出所有项

  • union操作、需要去除重复记录操作

    • 所有select字段计算hash值
    • 第一个输入构建hash表，删除重复项
    • 第二个输入进行探测
      • 若第二个输入没有重复项，直接返回没有匹配的项， 扫描hash表返回所有项
      • 若第二个输入有重复项，则应该需要继续构建hash表， 最后统一输出整个hash表

Grace Hash Join

grace hash join：磁盘分块HJ

  • 将两表按照相同hash函数分配至不同分片中

    • 在磁盘上为各分片、表建立相应文件
    • 对表输入计算哈希值，根据哈希值写入分片、表对应文件

  • 再对不同分片进行普通in-memory hash join

    • 若分片依然不能全部加载至内存，可以继续使用 grace hash join
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
grace_hash_join(t1, t2):
	// Grace Hash Join实现
	// 输入：待join表t1、t2
	for row in t1:
		hash_val = hash_func(row)
		N = hash_val % PART_COUNT
		write row to file t1_N

	for row in t2:
		hash_val = hash_func(row)
		N = hash_val % PART_COUNT
		write row to file t2_N

	for i in range(0, PART_COUNT):
		join(t1_i, t2_i)

  • 分片数量PART_COUNT决定磁盘IO效率

    • 分片数量过小：无法起到分治效果，分片仍然需要进行 grace hash join，降低效率
    • 分片数量过大：磁盘是块设备，每次刷盘刷一定数量块才 高效，频繁刷盘不经济
    • 即分片数量在保证刷盘经济的情况下，越大越好，这需要 优化器根据表统计信息确定

  • 特点

    • 有磁盘I/O代价，会降低效率
    • 适合参与join表非常大，无法同时载入内存中

Hybrid Hash Join

hybrid hash join：GHJ基础上结合IMHJ的改进

  • 对build表分片过程中，尽量多把完整分片保留在内存中
  • 对probe表分片时，对应分片可以直接进行probe操作
  • hybrid hash join有时也被直接视为grace hash join， 不做区分

比较

  • 资源消耗

    • HJ：CPU计算、内存（磁盘）中创建临时hash表
    • SMJ：磁盘I/O（扫描表、索引）
    • NLJ：磁盘I/O

  • 性能

    • 通常情况：HJ > NPJ <> SMJ

      • 全表扫描比索引范围扫描再进行表访问更可取时，SMJ 优于NPJ？？？
      • 而表特别小、特别大时，全表扫描优于索引范围扫描

    • 但若关联字段已排序，SMJ性能最优

  • 首条搜索结果

    • NPJ能快速返回首条搜索结果
    • HJ、SMJ返回首条结果较慢

多表联接算法

多表联接算法：找到最优连接顺序（执行路径）

  • 表联接顺序对于查询结果没有影响，但是对资源消耗、性能影响 巨大

  • 随着需要联接表数目增加，可能的联接排列非常多，基本不能 对所有可能穷举分析

    • left-deep tree/linear (processing)tree：$n!$
    • bushy tree：$\frac {2(n-1)!} {(n-1)!}$ （包括left-deep tree、right-deep tree）

    left_deep_tree_bushy_tree

  • 事实上查询优化器不会穷尽搜索所有可能联接排列，而是使用 启发式算法进行搜索

Dynamic Programming

动态规划算法：依次求解各数量表最优联接顺序，直到求出最终结果

  1. 构造第一层关系：每个关系的最优路径就是关系的最优单表扫描 方式

  2. 迭代依次构造之后n-1层关系联接最优解

    • 左深联接树方式：将第k-1层每个关系同第1层关系联接
    • 紧密树联接方式：将第m(m > 2)层每个关系同第k-m层关系 联接

    left_deep_tree_bushy_tree

Heuristic Algorithm

Greedy Algorithm

贪心算法：认为每次连接表的连接方式都是最优的，即从未联接表中 选择使得下次联接代价最小者

  • 多表排序一般为

    • 常量表最前
    • 其他表按可访问元组数量升序排序

  • 贪心算法得到的联接方式都是最优的

    • 则每次联接主要求解要联接表对象的最佳访问方式
    • 即每次代价估计的重点在于单表扫描的代价

  • 求解结束后，局部最优查询计划生成

    • 得到左深树
    • 最初始表位于最左下端叶子节点处

System R

System R：对动态规划算法的改进

  • 保留子树查询最优、次优查询计划，用于上层查询计划生成， 使得查询计划整体较优

Genetic Algorithm

遗传算法：模拟自然界生物进化过程，采用人工进化的方式对目标 空间进行搜索

  • 本质是高效、并行、全局搜索方法
  • 能在搜索过程中自动获取、积累有关搜索空间的知识，并自适应 的控制搜索过程以求的最佳解

思想

  • 将问题域中可能解看作是染色体，将其编码为符号串的形式
  • 对染色体群体反复进行基于遗传学的操作：选择、交叉、变异
  • 根据预定目标适应度函数对每个个体进行评价，不断得到更优 群体，从中全局并行搜索得到优化群体中最优个体

实体

  • population：群体，GA的遗传搜索空间
  • individual：个体，搜索空间中可能解
  • chromosome：染色体，个体特征代表
    • 由若干段基因组成
    • GA中基本操作对象
  • gene：基因
    • 染色体片段
  • fitness：适应度，个体对环境的适应程度

基本操作

  • selection：选择，根据个体适应度在群体中按照一定概率 选择个体作为父本

    • 适应度大个体被选择概率高
    • 体现了适者生存、优胜劣汰的进化规则

  • crossover：交叉，将父本个体按照一定概率随机交换基因 形成新个体

  • mutate：变异，按照一定概率随机改变某个体基因值

涉及问题

  • 串编码方式

    • 把问题的各种参数用二进串进行编码构成子串
    • 把子串拼接成染色体
      • 串长度、编码方式对算法收敛影响极大

  • 适应度/对象函数确定

    • 一般可以把问题模型函数作为对象函数

  • GA超参设置

    • 群体大小$n$：过小难以求出最优解，过大难收敛，一般取 $n = 30 ~ 160$
    • 交叉概率$P_c$：太小难以前向搜索，太大容易破坏高适应 值结构，一般取$P_c = 0.25 ~ 0.75$
    • 变异概率$P_m$：太小难以产生新结构，太大则变为单纯 随机搜索，一般取$P_m = 0.01 ~ 0.2$

算法

  1. 随机初始化种群
  2. 估初始种群：为种群每个个体计算适应值、排序
  3. 若没有达到预定演化数，则继续，否则结束算法
  4. 选择父体
    • 杂交：得到新个体
    • 变异：对新个体变异
  5. 计算新个体适应值，把适应值排名插入种群，淘汰最后个体
  6. 重复3
Posted Updated Database / SQL DB17 minutes read (About 2484 words)

Postgre SQL笔记

安装

  • 交互式客户端：postgresql
  • 服务器：postgres-server
  • 额外功能：postgresql-contrib
  • 开发工具：postgresql-devel

OpenSuSe

1
2
$ sudo zypper in postgresql postgresql-server \
	postgresql-contrib postgresql-devel

CentOS

1
2
$ sudo yum install postgresql postgresql-server \
	postgresql-contrib postgresql-devel

其他版本

  • 从中选择合适版本下载：Postgres Yum repositories

    1
    $ wget https://download.postgresql.org/pub/repos/yum/9.6/redhat/rhel-7-x86_64/pgdg-centos96-9.6-3.noarch.rpm

  • 安装下载的RPM（依赖EPEL repo）

    1
    $ sudo yum install pgdg-centos96-9.6-3.noarch.rpm

  • 更新Yum、安装指定PG版本

    1
    2
    $ sudo yum update
    $ sudo yum install postgresql96-sever postgresql96-contrib
  • 安装的PG带有版本后缀，初始化、启动时注意

配置

  • postgres安装完成后，默认创建Linux用户

    • 用户密码为空，要为其设置密码以切换到其
      1
      2
      $ sudo passwd postgres
      $ su - postgres
    • 用户目录默认是/var/lib/pgsql
    • 很多命令可以切换到用户postgres直接执行
  • 初始化数据库簇后，默认创建数据库角色postgres、数据库 postgres

初始化

  • 创建新PostgreSQL数据库簇

    1
    2
    3
    $ sudo postgresql-setup initdb
    	# 或
    $ sudo inidb -D /var/lib/pgsql/data
    • 默认数据库存储路径为/var/lib/pgsql/data

  • 开启PG密码认证：修改host-based authentication设置

    1
    2
    3
    4
    # /var/lib/pgsql/data/pg_hba.conf
    # TYPE		DATABASE	USER	ADDRESS			MEHTOD
    host		all			all		127.0.0.1/32	md5
    host		all			all		::1/128			md5
    • 替换默认ident为md5开启密码认证
    • 修改之后需要重启PG

  • 修改postgres用户密码，以可以通过密码作为postgres连接 数据库

    1
    2
    3
    $ su - postgres
    $ psql -d template1 -c "ALTER USER postgres with password '<passwd>'"
    	# 也可以在数据库prompt中执行

启动数据库

  • 作为服务：start、enablePG

    1
    2
    $ sudo systemctl start postgresql
    $ sudo systemctl enable postgresql

  • 作为普通程序启动：pg_ctl

    1
    2
    $ su - postgres
    $ pg_ctl start -D /var/lib/pgsql/data

Roles

PG使用概念roles处理认证、权限问题

  • 角色相较于区分明显的用户、组概念更加灵活

  • create user和create role几乎完全相同

    • create user：创建角色默认带LOGIN属性
    • create role：创建角色默认不带LOGIN属性

权限

  • SUPERUSER/NOSUPERUSER：数据库超级用户
  • CREATEDB/NOCREATEDB：创建数据库
  • CREATEUSER/NOCREATEUSER
  • CREATEROLE/NOCREATEROLE：创建、删除普通用户角色
  • INHERIT/INHERIT：角色可以继承所属用户组权限
  • LOGIN/NONLOGIN：作连接数据库初始角色名
  • REPLICATION/NOREPLICATION：流复制时用到
  • CONNECTION LIMIT connlimit
  • [ENCRYPTED/UNENCRYPTED]PASSWORD '<passwd>'
  • VALID UNTIL '<timestamp>'
  • IN ROLE <role_name>[, ...]：角色所属用户组
  • IN GROUP <role_name>[, ...]
  • ROLE <role_name>[, ...]
  • ADMIN <role_name>[, ...]
  • USER <role_name>[, ...]
  • SYSID uid

角色赋权

1
2
3
4
5
psql> create role/user <name> [[with] <option> [...]];
	# 创建角色时直接赋权
psql> alter role/user <name> [[with] <option> [...]];
psql> grant connect on database <db_name> to <name>;
	# 修改已创建角色权限

组赋权

  • 把多个角色归为组，通过给组赋权、撤销权限实现权限管理
  • PG中角色赋权是通过inherit方式实现的
1
2
3
4
5
6
7
psql> create role father login createdb createrole;
	# 创建组角色、赋权
psql> create role son1 inherit;
psql> grant father to son1;
	# 创建有`inherit`权限的用户、赋权
psql> create role son2 inherit in role father;
	# 创建用户时直接赋组权

认证方式

Peer Authentication

peer：从内核中获取操作系统中用户名，作为数据库角色名连接

  • 默认连接同名数据库
  • 信任Linux用户身份（认证），不询问密码
    • 即使-W强制输入密码，也不会检查密码正确性
  • 只有local连接支持此方法

Trust Authentication

trust：允许任何数据库角色名的连接

  • 信任任何连接、不询问密码

    • 只应该在操作系统层面上能提供足够保护下情况下使用
      • 文件系统权限：限制对Linux域套接字文件的访问
    • 适合单用户、本地连接

  • 数据库、用户权限限制仍然存在

Ident Authentication

ident：从ident服务器中获取操作系统中用户名，用于连接数据库

  • 仅在TCP/IP连接情况下支持

    • 若被指定给local连接，将使用peer认证

  • 数据库服务器向客户端ident服务器询问“连接数据库的”用户， 据此判断连

    • 此流程依赖于客户端完整性，若客户端机器不可信，则 攻击者可以在113端口执行任何程序返回任何用户名
    • 故此认证方法只适合封闭网络，所以客户端机器都被严格 控制
    • 有些ident服务器开启非标准选项导致返回的加密用户名， 此选项应该关闭
    • 基本每个类Unix操作系统都带有ident服务器，用于监听 113端口TCP
涉及配置
  • map：运行系统、数据库用户名之间映射

Password Authentication

Password认证：基于密码的认证方式

  • password：明文传输密码验证
  • md5：MD5-hashed传输密码o

  • md5可以避免密码嗅探攻击

  • password总应该尽量避免使用

    • 启用db_user_namespace特性时无法使用md5
    • SSL加密连接下password也能安全使用

  • 每个数据库的密码存储在pg_authid系统表中

    • 若用户没有设置密码，则存储的密码为null，密码验证 也总是失败
    • 使用create user、alter role等SQL语句修改密码

GSSAPI Authentication

GSSAPI：定义在RFC 2743中的安全认证产业界标准协议

  • GSSAPI为支持其的系统自动提供认证
    • 认证本身是安全的，但是通过数据库连接的数据默认没有 加密，除非使用SSL
  • PG中GSSAPI需要编译时启用支持

SSPI Authentication

negotiate：windows的安全认证技术

  • PG将尽可能使用Kerberos，并自动回滚为NTLM
  • 仅服务器、客户端均在windows下或GSSAPI可用的情况下才能 工作
  • 使用Kerberos情况下，SSPI、GSSAPI工作方式相同
涉及配置
  • include_realm
  • map
  • krb_realm

Kerberos Authentication

Kerberos：适合公共网络上分布式计算的产业界标准安全认证系统

  • Kerberos提供不加密的语句、数据安全认证，若需要加密则使用 SSL
  • PG支持Kerberos第5版，需要在build时开启Kerberos支持
涉及配置
  • map
  • include_realm
  • krb_realm
  • krb_server_hostname

LDAP Authentication

LDAP：类似password，只是使用LDAP作为密码认证方法

涉及配置
  • ldapserver
  • ldapport
  • ldaptls
  • ldapprefix
  • ldapsuffix
  • ldapbasedn
  • ldapbinddn
  • ldapbindpasswd
  • ldapsearchattribute

RADIUS Authentication

RADIUS：类似password，只是使用RADIUS作为密码认证方法

涉及配置
  • radiusserver
  • radiussecret
  • radiusport
  • radiusidentifier

Certificate Authentication

Certificate：使用SSL客户多证书进行认证

  • 所以只在SSL连接中可用
  • 服务器要求客户端提供有效证书，不会向客户端传递密码prompt
    • cn属性（common name）将回和目标数据库的用户名 比较
    • 可通过名称映射允许cn属性和数据库用户名不同
涉及配置
  • map：允许系统、数据库用户名之间映射

PAM Authentication

PAM：类似password，只是使用 PAM(Pluggable Anthentication Modules)作为密码认证机制

涉及配置
  • parmservice：PAM服务名
    • 默认postgresql

pg_ctl

pg_ctl：用于控制PostgreSQL服务器的工具，此工具基本需要在 postgres用户下才能使用

  • 查看状态：$ pg_ctl status -D /var/lib/pgsql/data

psql

Shell

连接数据库

1
$ psql [-h <host>] [-p <port>] [-U <user_name>] [[-d] <db_name>]
  • -h：缺省为local类型连接本地数据库
    • local、host连接类型对应不同认证方式
    • -h localhost和缺省对应不同hba.conf条目
  • -p：缺省端口5432
  • -U/--user_name=：缺省linux用户名
  • [-d]/--database=：当前linux用户名
  • -W：密码，peer、trust模式下无价值

Shell命令

  • postgres不仅仅提供psql交互环境作为shell命令，还提供可以 直接在shell中运行的数据库命令

    • 当然前提是当前linux登陆用户在数据库中存在、有权限
1
2
3
4
$ createdb <db_name> [-O <user_name>]
	# 创建数据库，设置所有权为`user_name`
$ dropdb <db_name>
	# 删除数据库

元命令

元命令：反斜杠命令，\开头，由psql自己处理

  • \后：跟命令动词、参数，其间使用空白字符分割

  • 冒号:：不在引号中的冒号开头的参数会被当作psql变量

  • 反点号：参数内容被当作命令传给shell， 输出（除去换行符）作为参数值

  • 单引号'：参数包含空白时需用单引号包o，其中包含的参数 的内容会进行类C的替换

    • \n（换行）、\digits（八进制）
    • 包含单引号需要使用反斜杠转义

  • 双引号\”<\code>

    • 遵循SQL语法规则，双引号保护字符不被强制转换为 小写，且允许其中使用空白
    • 双引号内的双引号使用双双引号""转义

帮助

  • \?

    • [<commands>]：元命令帮助
    • <options>：psql命令行选项帮助
    • <variables>：特殊变量帮助

  • \h [<clauses>]：SQL命令语法帮助（*表示全部）

展示信息

  • \du：查看用户权限
  • \c <db_name> <name>：以身份name访问数据库db_name
  • \l[ist]：查看数据库
  • \dt：展示当前数据库中表

变量

  • \set foo bar：设置变量
    • 可以像php设置“变量 变量”：\set :foo bar
  • \unset foo：重置变量

数据库变量

内部变量

特殊变量

特殊变量：一些选项设置，在运行时可通过改变变量的值、应用的 表现状态改变其，不推荐改变这些变量的用途

  • AUTOCOMMIT：缺省为on，每个SQL命令完成后自行提交，此时 需要输出BEGIN、START TRANSACTION命令推迟提交
  • DBNAMW：当前所连接数据库
  • ENCODING：客户端字符集编码
  • 详情查询手册

环境变量

  • PGDATA：指定数据库簇（存放数据）目录

    1
    $export PGDATA=/var/lib/pgsql/data
    • 默认/var/lib/pgsql/data
    • -D命令行参数指定
Posted Updated Database / Spark15 minutes read (About 2177 words)

SparkSQL2.4中启用CBO时JoinReorder分析

背景

Spark Join方式

SparkSQL目前支持三种join方式

  • broadcast hash join：将小表广播分发到大表所在的结点上 ，并行在各节点上进行hash join

    • 仅适合内表非常小的场合

  • shuffle hash join：按照join key分区，每个结点独立并行 进行hash join

    • 类似分布式GHJ，不同块位于不同结点

  • sort merge join：按照join key分区，在各节点独立并行SMJ

    • spark当前shuffle算法使用sort-based shuffle算法
    • 理论上shuffle过后各分区数据已经排序完毕，无需再次 sort，效率很高

Join类型

SparkSQL支持的Join类型可以分为以下两类

  • 顺序结果无关Join

    • inner join
    • (full)outer join

  • 顺序结果相关Join

    • left(outer) join
    • right(outer) join
    • left semi join
    • right semi join

考虑到JoinReorder的结果

  • 仅支持连接重排序的连接类型只可能是inner join outer join

  • 而outer join重排序虽然不影响结果，但是处理不方便，所以 联接重排序一般仅限于inner join？？？

    • 有些情况下RBO可以将外联接等价转换为内联接
    • SparkSQL2.4中支持的连接重排序仅限于内连接

Cost-Based Opitimization/Optimizer

CBO：基于成本的优化（器）

  • 根据SQL的执行成本制定、优化查询作业执行计划，生成可能 的执行计划中代价最小的计划

    • 数据表统计数据
      • 基/势
      • 唯一值数量
      • 空值数量
      • 平均、最大长度
    • SQL执行路径I/O
    • 网络资源
    • CPU使用情况

  • 在SparkSQL Hash Join中可以用于

    • 选择正确hash建表方
    • 选择正确join类型：广播hash、全洗牌hash
    • join reorder：调整多路join顺序

  • CBO本身需要耗费一定资源，需要平衡CBO和查询计划优化程度

    • 数据表的数据统计资源耗费
    • 优化查询计划即时资源耗费
  • CBO是相较于Rule-Based Optimization的概念

CBO中的独特概念

  • cardinality：集的势，结果集的行数

    • 表示SQL执行成本值
    • SQL执行返回的结果集包含的行数越多，成本越大

  • selectivity：可选择率，施加指定谓语条件后返回结果集的 记录数占未施加任何谓语条件的原始结果记录数的比率

    • 值越小，说明可选择性越好
    • 值越大，说明可选择性越差，成本值越大

Join Reorder

Join Reorder：基于CBO的多表连接顺序重排

  • 用统计信息预估的基修正join顺序

  • 主要涉及到以下两个方面

    • 查询代价估算
    • 多表连接顺序搜索算法

查询代价估计

代价模型

  • 单个join操作成本

    • carinality：对应CPU成本
    • size：对应IO成本

  • join树的成本是所有中间join成本总和

Filter Selectivity估计

过滤选择率：估计应用谓词表达式过滤的选择率

逻辑运算符

  • AND：左侧过滤条件选择率、右侧过滤条件选择率之积

  • OR：左侧、右侧过滤条件选择率之和，减去其乘积

  • NOT：1减去原始过滤条件选择率

比较运算符

  • =：等于条件

    • 若常数取值在当前列取值范围之外，则过滤选择率为0
    • 否则根据柱状图、均匀分布得到过滤选择率

  • <：小于条件

    • 若常数取值小于当前列最小值，则过滤选择率为0
    • 否则根据柱状图、均匀分数得到过滤选择率

Join Carinality估计

联接基：估计联接操作结果的基

  • inner：其他基估计值可由inner join计算

    • num(A)：join操作前表A的有效记录数
    • distinct(A.k)：表A中列k唯一值数量

  • left-outer：取inner join、左表中基较大者

  • right-outer：取inner join、右表中基较大者

  • full-outer

多表连接顺序搜索算法

SparkSQL2.4中使用动态规划算法对可能联接顺序进行搜索，从中 选择最优的联接顺序作为执行计划

  • 最优子结构：一旦前k个表联接顺序确定，则联接前中间表和 第k+1个表方案和前k个表的联接顺序无关

  • 动态规划表：从单表代价开始，逐层向上计算各层多表联接代价 ，直到求得所有表联接最小代价

  • 减少搜索空间启发式想法：尽可能优先有谓词限制的内连接、 中间表

评价

  • 优势：动态规划算法能够求得整个搜索空间中最优解
  • 缺陷：当联接表数量增加时，算法需要搜索的空间增加的非常快 ，计算最优联接顺序代价很高

PostgreSQL

代价模型

Postgres的查询代价估计模型基于CPU开销、IO开销，另外还增加 了启动代价

动态规划算法

类似SparkSQL2.4多表连接算法（假设联接n个表）

  1. 构造第一层关系：每个关系的最优路径就是关系的最优单表扫描 方式

  2. 迭代依次构造之后n-1层关系联接最优解

    • 左深联接树方式：将第k-1层每个关系同第1层关系联接
    • 紧密树联接方式：将第m(m > 2)层每个关系同第k-m层关系 联接

    left_deep_tree_bushy_tree

遗传算法

遗传算法：模拟自然界生物进化过程，采用人工进化的方式对目标 空间进行搜索

  • 本质是高效、并行、全局搜索方法
  • 能在搜索过程中自动获取、积累有关搜索空间的知识，并自适应 的控制搜索过程以求的最佳解

思想

  • 将问题域中可能解看作是染色体，将其编码为符号串的形式
  • 对染色体群体反复进行基于遗传学的操作：选择、交叉、变异
  • 根据预定目标适应度函数对每个个体进行评价，不断得到更优 群体，从中全局并行搜索得到优化群体中最优个体

MySQL

代价模型

  • 因为多表联接顺序采用贪心算法，多个表已经按照一定规则排序 （可访问元组数量升序排序）
  • 所以MySQL认为，找到每个表的最小花费就是最终联接最小代价

贪心算法

贪心算法：认为每次连接表的连接方式都是最优的，即从未联接表中 选择使得下次联接代价最小者

  • 多表排序一般为

    • 常量表最前
    • 其他表按可访问元组数量升序排序

  • 贪心算法得到的联接方式都是最优的

    • 则每次联接主要求解要联接表对象的最佳访问方式
    • 即每次代价估计的重点在于单表扫描的代价

  • 求解结束后，局部最优查询计划生成

    • 得到左深树
    • 最初始表位于最左下端叶子节点处

优化方案

以下分别从查询代价估计、多表连接顺序搜索算法给出方案

查询代价估计

  • 考虑在现有代价模型上增加网络通信开销

  • 在现有直方图估计选择率基础上，增加选择率估计方法

    • Parametric Method：参数方法，使用预先估计分布函数 逼近真实分布

    • Curve Fitting：曲线拟合法，使用多项式函数、最小 标准差逼近属性值分布

多表连接顺序搜索算法

考虑到动态规划算法随着联接表数量增加时，计算代价过于庞大， 可以考虑引入其他算法优化多表连接顺序

  • 遗传算法
  • 退火算法
  • 贪心算法
  • 遗传算法
  • 退火算法
  • 贪心算法
Posted Updated Database12 minutes read (About 1758 words)

DBMS 查询优化

查询优化技术

查询优化技术：求解给定查询语句的高效执行计划过程

  • 目标：在数据库查询优化引擎生成执行策略的过程中，尽量减小 查询总开销

  • SQL层面上的局部优化，区别于数据库调优的全局优化

  • 广义数据库查询优化

    • 查询重用技术
    • 查询重写规则
    • 查询算法优化技术
    • 并行查询优化技术
    • 分布式查询优化技术

  • 狭义数据库查询优化

    • 查询重写规则：代数/逻辑优化，RBO
    • 查询算法优化技术：非代数/物理优化，CBO

代数/逻辑优化

代数/逻辑优化：依据关系代数的等价变换做逻辑变换

  • 语法级：查询语句层、基于语法进行优化
  • 代数级：使用形式逻辑、关系代数原理进行优化
  • 语义级：根据完整性约束，对查询语句进行语义理解，推知可 优化操作

非代数/物理优化

非代数/物理优化：根据数据读取、表连接方式、排序等技术对查询 进行优化

  • 物理级：物理优化技术，基于代价估计模型，比较得出各执行 方式中代价最小者
    • 查询算法优化：运用基于代价估算的多表连接算法求解最小 花费计算

查询重用技术

查询重用：尽可能利用先前执行的结果，以节约全过程时间、减少 资源消耗

  • 查询结果的重用：分配缓冲块存放SQL语句、最后结果集
  • 查询计划的重用：缓存查询语句执行计划、相应语法树结构
  • 优势：节约CPU、IO消耗
  • 弊端
    • 结果集很大回消耗放大内存资源
    • 同样SQL不同用户获取的结果集可能不完全相同

查询重写规则

查询重写：查询语句的等价转换

  • 基于关系代数，关系代数的等价变换规则为查询重写提供了理论 支持
  • 查询重写后，查询优化器可能生成多个连接路径，可以从候选者 中择优

目标

  • 将查询转换为等价、效率更高的形式
    • 低效率谓词转换为高效率谓词
    • 消除重复条件
  • 将查询重写为等价、简单、不受表顺序限制的形式，为 物理查询阶段提供更多选择

优化方向

  • 过程性查询转换为描述性查询：视图重写
  • 复杂查询尽可能转换为多表连接查询：嵌套子查询、外连接、 嵌套连接等
  • 低效率谓词转换为高效率谓词：等价谓词重写
  • 利用（不）等式性质简化where、having、on条件

查询算法优化技术

todo

Rule-Based Optimizer

RBO：基于规则的优化器

  • 对AST/LP进行遍历，模式匹配能够满足特定规则的结点，进行 等价转换，得到等价的另一棵树

    • 剪枝：删除一些无用计算
    • 合并：合并多个计算步骤

  • 经验式、启发式的固定transformation，手动设置（硬编码） 在数据库中规则决定SQL执行计划

经典优化规则

  • predicate pushdown：谓词下推

    sql_optimization_predicate_pushdown

  • constant folding：常量累加

    sql_optimization_constant_folding

  • column pruning：列值裁剪

    sql_optimization_column_pruning

  • combine limits：Limits合并

  • inner join只访问单表：降为semi join

特点

  • 操作简单、能快速确定连接方式

  • 规则虽然有效但不敏感

    • 数据分布发生变化时，RBO是不感知的

  • 基于RBO生成的执行计划不能确保是最优的

    • 启发式规则只能排除一些明显不好的存取路径

Cost-Base Optimizer

CBO：基于成本的优化器

  • 根据SQL的执行成本制定、优化查询作业执行计划，生成可能 的执行计划中代价最小的计划

    • 数据表统计数据
      • 基/势
      • 唯一值数量
      • 空值数量
      • 平均、最大长度
    • SQL执行路径I/O
    • 网络资源
    • CPU使用情况

  • 以上执行信息获取方式取决于不同平台、数据库

    • 执行SQL前抽样分析数据
    • 每次执行SQL都会记录统计信息

  • 特殊概念

    • cardinality：集的势，结果集的行数

      • 表示SQL执行成本值
      • SQL执行返回的结果集包含的行数越多，成本越大

    • selectivity：可选择率，施加指定谓语条件后返回 结果集的记录数占未施加任何谓语条件的原始结果集记录数 的比率

      • 值越小，说明可选择性越好
      • 值越大，说明可选择性越差，成本值越大

常见优化规则

  • hash-join
    • 选择正确hash建表方
    • 选择正确join类型：广播hash、全洗牌hash
    • join reorder：调整多路join顺序
      • 尽量减小中间shuffle数据集大小，达到最优输出

特点

  • 对各种可能情况进行量化比较，可以得到花费最小的情况
  • CBO本身需要耗费一定资源，需要平衡CBO和查询计划优化程度
    • 数据表的数据统计资源耗费
    • 优化查询计划即时资源耗费，如果组合情况比较多则花费 判断时间较多

并行查询优化技术

并行数据库系统中查询优化的目标：寻找具有最小响应时间的查询 执行计划

  • 具有最小执行代价的计划不一定具有最快相应时间，需要考虑 把查询工作分解为可以并行运行的子工作

  • 查询能否并行取决于

    • 系统中可用资源
    • CPU数目
    • 运算中特定代数运算符

  • 查询并行可以分为

    • 操作内并行：将同一操作如单表扫描、两表连接、排序操作 等分解为多个独立子操作

    • 操作间并行：一条SQL查询语句分解为多个子操作

分布式查询优化技术

分布式数据库系统：查询策略优化、局部处理优化是查询优化重点

  • 查询策略优化：主要是数据传输策略优化

    • 主要考虑因素：数据的通信开销
    • 主要目标：以减少传输次数、数据量

  • 局部处理优化：传统单结点数据库的查询优化技术

  • 代价估计模型：总代价 = IO代价 + CPU代价 + 通信代价

Posted Updated Database3 minutes read (About 432 words)

Database Parser

Parser综述

Parser：分析器，将SQL语句切分为token，根据一定语义规则解析 成AST

todo

查询计划/树

sql_parser_ast

查询计划：由一系列内部操作符组成，操作符按照一定运算关系构成 查询的一个执行方案

  • 形式上：二叉树

    • 树叶是每个单表对象
    • 两个树叶的父节点是连接操作符连接后的中间结果
    • 每个结点即临时“关系”

  • 查询的基本操作：选择、投影、连接

    • 选择、投影的优化规则适用于select-projection-join 操作和非SPY（SPY+Groupby）操作
    • 连接操作包括两表连接、多表连接

结点类型

  • 单表结点：从物理存储到内存解析称逻辑字段的过程

    • 考虑数据获取方式
      • 直接IO获取
      • 索引获取
      • 通过索引定位数据位置后再经过IO获取相应数据块

  • 两表结点：内存中元组进行连接的过程

    • 完成用户语义的局部逻辑操作，完成用户全部语义需要配合 多表连接顺序的操作
    • 不同连接算法导致连接效率不同
    • 考虑两表
      • 连接方式
      • 代价
      • 连接路径

  • 多表中间结点：多个表按照“最优”顺序连接过程

    • 考虑代价最小的“执行计划”的多表连接顺序

Schema Catalog

元数据信息：表的模式信息

  • 表的基本定义：表名、列名、数据类型
  • 表的数据格式：json、text、parquet、压缩格式
  • 表的物理位置
Posted Updated Database / Hadoop5 minutes read (About 724 words)

Hadoop 计算模型

分布式计算模型

分布式系统，不像一般的数据库、文件系统，无法从上至下、从头 到尾进行求和等操作，需要由分散的节点不断向一个点聚拢计算过程 ，考虑将分布式计算模型可以考虑分为两部分

  • 分布：操作原语
  • 聚合：处理流程

MapReduce

MapReduce计算模型主要描述是分布：操作原语部分， 但是此也包含了聚合：处理流程

操作原语

  • map：映射
    • 以键值对二元组为主要处理对象
    • map过程相互独立、各mapper相互不通信的
    • 所以mapper比较适合可独立计算任务
  • reduce：规约
    • 直接处理map输出，reduce中二元组键位map过程中输出值

处理流程

以hadoop中MapReduce为例

  • 需要把任何计算任务转换为一系列MapReduce作业，然后依次 执行这些作业

  • 计算过程的各个步骤之间，各个作业输出的中间结果需要存盘， 然后才能被下个步骤使用（因为各个步骤之间没有明确流程）

缺陷

操作原语部分

  • 提供原语少：需要用户处理更多逻辑，易用性差

  • 所以抽象层次低：数据处理逻辑隐藏在用户代码中，可读性差

  • 所以其表达能力有限：

    • 复杂数据处理任务，如：机器学习算法、SQL连接查询很难 表示用MapReduce计算默认表达
处理流程部分

  • MapReduce需要通过把中间结果存盘实现同步，I/O延迟高

  • reduce任务需要等待map任务全部完成才能继续，同步Barrier 大

适合场景

  • One Pass Computation：只需要一遍扫描处理的计算任务 MapReduce计算模型非常有效

    • 批数据处理

  • Multi Pass Computation：需要在数据上进行多遍扫描、处理 的计算任务，需要执行多个MapReduce作业计算任务，因为 多副本复制、磁盘存取，其效率不高

DAG

Directed Acyclic Graph：只是表示数据处理流程的有向无环图

  • 顶点：数据处理任务，反映一定的业务逻辑，即如何对数据进行 转换和分析
  • 边：数据在不同的顶点间的传递

应用

  • DAG本身并不涉及如何处理数据，只是对数据数据流程的规划

  • 所以DAG并不能改进MapReduce计算模型中原语部分的缺陷，只能 优化数据处理流程

    • 减少MapReduce作业中间结果存盘，减少磁盘I/O
    • 优化map、reduce任务执行，减少同步Barrier

这也正是Tez所做的事情

RDD

Posted Updated Database / Hadoop12 minutes read (About 1790 words)

HBase

HBase简介

HBase是高可靠、高性能、面向列、可伸缩的分布式数据库系统

  • 利用HBase技术可以在廉价硬件上搭建大规模非结构化数据管理 集群

  • HBase借鉴Google Bigtable技术实现的开源软件

    ||HBase|Bigtable| |——-|——-|——-| |存储系统|HDFS|GFS| |数据处理|Hadoop MapReduce|MapReduce| |协同服务|Zookeeper|Chubby| |RDBMS数据导入|Sqoop|-|

  • HBase访问接口

    • Native Java API：常用、高效的访问方式
    • HBase Shell：HBase命令行工具，适合用于管理HBase
    • Thrift Gateway：利用Thrift序列化技术，支持C++、PHP、 Python多种语言异构系统访问HBase表数据
    • REST Gateway：支持REST风格的Http API访问HBase
    • Pig：支持Pig Latin语言操作HBase中数据
      • 最终被转换为MapReduce Job处理HBase表数据
      • 适合做数据统计
    • Hive：支持用户使用HiveQL访问HBase

  • 可以在HBase系统上运行MapReduce作业，实现数据批处理 hbase_mapreduce

HBase数据结构

hbase_storage_structure

Table

HBase的表格，类似关系型数据库中的表格，但有所不同

特殊Table

HBase中有两张特殊的Table

  • .META.：记录用户表Region信息，自身可以有多个region
  • -ROOT-：记录.META.表Region信息的，自身只能有一个 region

Row Key

行键，Table行主键，Table记录按照此排序

Column、Column Family

  • Table在水平方向由一个或多个列簇组成
  • 一个列簇可以由任意多个Column组成
  • 列簇支持动态扩展，无需预先定义列数量、类型
  • 所有列均义二进制格式存储，用户需要自行进行类型转换

Timestamp

时间戳：每次数据操作对应的时间戳，可视为是数据的版本号

Region

Table记录数不断增加而变大后，逐渐分裂出的多个split

  • 每个region由[startkey, endkey)表示
  • 不同region被Master分配给相应RegionServer进行管理（存储）

HBase系统架构

hbase_structure

Client

  • HBase Client使用HBase RPC机制同HMaster、HRegionServer 进行通信
    • 对于管理类操作，通过RPC机制访问HMaster
    • 对于读写操作，通过RPC机制访问HRegionServer

Zookeeper

  • Zookeeper Quorum中记录-ROOT表的位置

    • 客户端访问数据之前首先访问zookeeper
    • 然访问-ROOT-表
    • 然后访问.META.表
    • 最后根据用户数据位置，访问具体数据

  • Zookeeper Quorum中存储有HMaster地址

  • HRegionServer把自己义Ephemeral方式注册到Zookeeper中， 使得HMaster可以随时感知各个HRegionServer健康状态

  • 引入Zookeeper，避免了HMaster单点失败问题

    • HBase中可以启动多个HMaster
    • 通过Zookeeper的Master Election机制保证总有一个Master 运行

HMaster

HMaster在功能上主要负责Table、Region管理工作

  • 管理用户对Table增、删、查、找操作？？？
  • 管理HRegionServer负载均衡，调整Region分布
  • 在Region分裂后，负责新Region分配
  • 在HRegionServer停机后，负责失效HRegionServer上region迁移

HRegionServer

HRegionServer负责响应用户I/O请求，向HDFS文件系统写数据，是 HBase中最核心的模块

hbase_hregion_server_structure

HRegion

HRegionServer内部管理一系列HRegion对象

  • HRegion对象对应Table中一个Region
  • HRegion由多个HStore组成

HStore

每个HStore对应Table中一个列簇的存储，是HBase存储核心模块

  • 由此可以看出列簇就是一个集中存储单元

    • 因此最好将具备共同IO特性的列放在同一个列簇中，可以 提高IO效率

  • HStore由两部分构成

    • MemStore
    • StoreFile：底层实现是HFile，是对HFile的轻量级包装
MemStore

Sorted memory buffer，用户写入数据首先放入MemStore中，满了 后Flush成一个StoreFile

StoreFile

  • 文件数量增长到一定阈值时会触发Compact合并操作，将多个 StoreFile合并成一个StoreFile

    • 合并过程中会进行版本合并、数据删除
    • 即HBase其实只有增加数据，所有更新、删除操作都是后续 Compact过程中进行的
    • 这使得用户写操作只要进入内存就可以立即返回，保证 HBase IO高性能

  • Compact操作会逐步形成越来越大的StoreFile，超过阈值之后 会触发Split操作

    • 当前Region分裂成2个Region
    • 父Region下线
    • 新分裂出的2个子Region会被HMaster分配到相应的 HRegionServer上，实现负载均衡

HLog

每个HRegionServer中都有一个HLog对象，避免因为分布式系统 中节点宕机导致的MemStore中内存数据丢失

  • HLog是实现WriteAheadLog的类

  • HLog作用

    • 每次用户写入MemStore时，也会写入一份数据至HLog文件中
    • HLog定时删除已持久化到StoreFile中的数据

  • HRegion意外终止后，HMaster会通过zookeeper感知到

    • HMaster首先处理遗留的HLog文件，将其中不同Region的Log 数据进行拆分，分别放到相应Region目录下
    • 然后将失效Region重新分配
    • 领取到Region的HRegionServer在Load Region过程中，会 发现有历史HLog需要处理，会Replay HLog中的数据到 MemStore中，然后flush到StoreFile中，完成数据恢复

HBase存储

HBase中所有数据存储在HDFS中

HFile

HFile是Hadoop二进制格式文件，实现HBase中Key-Value数据存储

  • HFile是不定长的，长度固定的只有：Trailer、FileInfo

hbase_hfile_storage_formation

Trailer

含有指针指向其他数据块起点

FileInfo

记录文件的一些元信息，如

  • AVG_KEY_LEN
  • AVG_VALUE_LEN
  • LAST_KEY
  • COMPARATOR
  • MAX_SEQ_ID_KEY

Data Index

记录每个Data块起始点

Meta Index

记录每个Meta块起始点

Data Block

Data Block是HBase IO基本单元

  • 为了提高效率，HRegionServer中实现了基于LRU的Block Cache 机制

  • Data块大小可以在创建Table时通过参数指定

    • 较大的块有利于顺序Scan
    • 较小的块有利于随机查询

  • Data块除了开头的Magic信息外，就是一个个<key, value> 键值对拼接而成

  • Magic内容就是一些随机数字，防止数据损坏

  • 每个键值对就是简单的byte array，但是包含很多项，且有固定 结构 hbase_hfile_datablock_kv

    • 开头是两个固定长度的数值，分别表示key、value长度
    • 然后是key部分
      • 固定长度数值表示RowKey长度
      • RowKey
      • 固定长度数值表示Column Family的长度
      • Column Family
      • Qualifier
      • 固定长度数值表示：Timestamp、KeyType（Put/Delete）
    • Value部分就是二进制数据

HLogFile

HBase中Write Ahead Log存储格式，本质上是Hadoop Sequence File

  • Sequence File的Key是HLogKey对象，记录了写入数据的归属信息

    • table
    • region
    • squecence number：起始值为0，或最近一次存入文件系统 中的squence number
    • timestamp：写入时间

  • Squence File的Value是KeyValue对象，即对应HFile中KeyValue

e

Posted Updated Database / Hadoop27 minutes read (About 4104 words)

Zookeeper

Zookeeper是一个协调软件服务，用于构建可靠的、分布式群组

  • 提供群组成员维护、领导人选举、工作流协同、分布式系统同步 、命名、配置信息维护等服务

  • 提供广义的分布式数据结构：锁、队列、屏障、锁存器

  • Zookeeper促进户端间的松耦合，提供最终一致的、类似传统 文件系统中文件、目录的Znode视图，提供基本操作，如：创建 、删除、检查Znode是否存在

  • 提供事件驱动模型，客户端能观察到Znode的变化

  • Zookeeper运行多个Zookeeper Ensemble以获得高可用性，每个 服务器上的Ensemble都持有分布式系统内存副本，为客户端读取 请求提供服务

zookeeper_structure

Flume

Flume是分布式日志收集系统，收集日志、事件等数据资源，并集中 存储

Flume组件、结构

  • 旧版本组件、结构 flume_struture_old_version

  • 新版本组件、结构：每个Flume整体称为Agent flume_dataflow

    • 两个版本的组件功能、数据流结构都有区别
    • 但是3大组件基本可以一一对应（功能略有差异）

  • Agent是一组独立的JVM守护进程，从客户端、其他Agent接收 数据、迅速传递给下个目的节点

  • 支持多路径流量、多管道接入流量、多管道接出流量、上下文 路由

Source（Agent）

采集数据，是Flume产生数据流的地方

  • 运行在数据发生器所在的服务器上，接收数据发生器接受数据， 将数据以event格式传递给一个或多个Channel

  • 支持多种数据接收方式

    • Avro Source：支持Avro RPC协议，内置支持
    • Thrift Source：支持Thrift协议
    • Exec Source：支持Unix标准输出
    • JMS Source：从JMS（消息、主题）读取数据
    • Spooling Directory Source：监控指定目录内数据变更
    • Twitter 1% firehose Source：通过API持续下载Twitter 数据
    • Netcat Source：监控端口，将流经端口的每个文本行数据 作为Event输入
    • Sequence Generator Source：序列生成器数据源
    • HTTP Source：基于POST、GET方式数据源，支持JSON、BLOB 格式

  • 收集数据模式

    • Push Source：外部系统主动将数据推送到Flume中，如 RPC、syslog
    • Polling Source：Flume主动从外部系统获取数据，如 text、exec

Channel （Collector）

暂时的存储容器，缓存接收到的event格式的数据，直到被sink消费

  • 在source、sink间起桥梁作用

  • Channel基于事务传递Event，保证数据在收发时的一致性

  • Channel可以和任意数量source、sink连接

  • 主要Channel类型有

    • JDBC channel：数据持久化在数据库中，内置支持Derby
    • File Channel：数据存储在磁盘文件中
    • Memory Channel：数据存储在内存中
    • Spillable Meemory Channel：优先存在内存中，内存队列 满则持久到磁盘中
    • Custom Channel：自定义Channel实现

Sink（Storage Tier）

将从Channel接收数据存储到集中存储器中（HDFS、HBase）

Flume Event

Flume事件是内部数据传输最小基本单元、事务处理基本单位

  • 由一个装载数据的byte array、可选header构成
    • 数据对Flume是不透明的
    • header是容纳键值对字符串的无需集合，键在集合内唯一
    • header可以在上下文路由中使用扩展，如：数据清洗
  • Event将传输数据进行封装

Flume架构特性（旧版）

Reliablity

Flume提供了3种数据可靠性选项

  • End-to-End：使用磁盘日志、接受端Ack的方式，保证Flume接收 数据最终到导致目的地

  • Store on Failure：目的地不可用时，将数据保存在本地硬盘， 但进程如果出问题，可能丢失部分数据（发送后目的地不可用）

  • Best Effort：不做任何QoS保证

Scalability

易扩展性

  • Flume三大组件都是可伸缩的
  • Flume对事件的处理不需要带状态，Scalability容易实现

Avaliablity

高可用性：Flume引入Zookeeper用于保存配置数据

  • Zookeeper本身可以保证配置数据一致性、高可用
  • 在配置数据发生变化时，Zookeeper通知Flume Master节点 Flume Master节点通过gossip协议同步数据

flume_distributed_deployment

Manageablity

易管理性

  • 多个Master，保证可以管理大量节点

Extensibility

可开发性：可以基于Java为Flume添加各种新功能

  • 实现Source子类，自定义数据接入方式
  • 实现Sink子类，将数据写入特定目标
  • 实现SinkDecorator子类，对数据进行一定的预处理

适合场景

  • 高效率的从多个网站服务器收集日志信息存储在HDFS上
  • 将从多个服务器获取的数据迅速移交给Hadoop
  • 可以收集社交网络站点事件数据，如：facebook、amazon

Kafka

分布式、分区的、可复制的Message System（提交日志服务）， 得益于特有的设计，Kafka具有高性能、高可扩展的特点

  • 完全分布式系统，易于横向扩展、处理极大规模数据
  • 同时为发布、订阅提供极高吞吐能力
  • 支持多订阅，出现失败状态时，可以自动平衡消费者
  • 将消息持久化到磁盘，保证消息系统可靠性，可用于消息 批量消费应用（ETL系统）、实时应用

Kafka组件

kafka_structure

Topic

话题：特定类型的消息流

  • 话题是消息的分类机制

    • 消息产生器向Kafka发布消息必须指定话题

  • Kafka安照Topic维护接收到的消息

    • 话题被划分为一系列分区
    • Kafka集群为每个Topic维护一个分区日志文件存储消息

消息是字节的Payload（有效载荷）

Producer

生产者：向Kafka发布消息的进程

  • 生产者需要指定消息分配至哪个分区
    • 采用Round-Robin方式方便均衡负载
    • 根据应用的语义要求，设置专用Partition Function进行 消息分区

Broker

代理：AMQP客户端，保存已经发布消息的服务器进程

AMQP：the Advanced Message Queuing Protocal，标准开放 的应用层消息中间件协议。AMQP定义了通过网络发送的字节流 的数据格式，兼容性非常好，任何实现AMQP协议的程序可以和 兼容AMQP协议兼容的其他应用程序交互，容易做到跨语言、 跨平台。

  • 一组代理服务器构成Kafka集群

  • Kafka代理是无状态的，消费者需要自行维护已消费状态信息

    • 因此Kafka无法知晓信息是否已经被消费、应该删除，因此 代理使用简单的、基于时间的Serice Level Agreement应用 于保留策略，消息在代理中超过一定时间自动删除

    • 这种设计允许消费者可以重复消费已消费数据

      • 虽然违反队列常见约定
      • 但是实际应用中很多消费者有这种特征

  • 消息代理将紧密耦合的系统设计解耦，可以对未及时处理的消息 进行缓存

    • 提高了吞吐能力
    • 提供了分区、复制、容错支持

  • Kafka代理通过Zookeeper与其他Kafka代理协同 kafka_with_zookeeper

    • 系统中新增代理或代理故障失效时，Zookeeper通知生产者 、消费者
    • 生产者、消费者据此开始同其他代理协同工作

Consumer

消费者：向Kafka subscribe话题，以处理Kafka消息的进程

  • 消费者可以订阅一个或多个话题，从代理拉取数据，消费已经 发布的消息

  • 消费者获取消息系统一般采用两种模型

    • Queuing：队列模型，一组消费者从一个服务器读取信息， 每个消息仅可被其中一个消费者消费

    • Publish Subscribe：发布订阅模型，消息被广播给所有 消费者

  • Kafka采用一种抽象方法：消费者组Consumer Group提供对上述 两种消息系统模型的支持 kafka_comsumer_group

    • 给每个消费者打上属于某个消费者组的标签（这里组只是 表示同组内消费者只能有一个消费信息）

    • 每个发布到话题的消息分发给消费者组的其中一个消费者

    • 一般情况下每个话题下有多个消费者组，每个组中有多个 消费者实例，以达到扩展处理能力、容错

    • 极端情况：如果所有消费者实例都隶属于同一个消费者组， Kafka工作模式类似于队列模型；所有消费者实例隶属于 不同的消费者组，Kafka工作模式类似于发布-订阅模型

消息分区、存储、分发

分区日志

每个分区是有序的、不可更改、可在末尾不断追加的 消息序列

分区优势

  • 允许Kafka处理超过一台服务器容量的日志规模

  • 分区作为并行处理基本单元，允许Kafka进行并行处理

  • 通过保证每个分区仅仅由一个消费者消费，可以保证同一 分区内消息消费的有序

    • 由于可以设置很多分区，仍然可以保证在不同消费者之间 实现负载均衡
    • 分区内外保证消息有序、数据分区处理对大部分实际应用 已经足够

分区管理

每个分区由单独的（一组）服务器处理，负责该分区数据管理、消息 请求，支持多个副本以支持容错

  • 每个分区中有一台服务器作为leader、若干服务器作为follower

  • 领导者负责分区读、写请求，跟随者以被动的方式领导者数据 进行复制

  • 领导者失败，则追随者之一在Zookeeper协调下成为新领导者

  • 为保证负载均衡，每个服务器担任部分分区领导者、其他分区 追随者

存储布局

Kafka存储布局非常简单

kafka_storage

分区存储

  • 话题每个分区对应一个逻辑日志

  • 每个日志为相同的大小的一组分段文件

  • 生产者发布的消息被代理追加到对应分区最后一个段文件中

  • 发布消息数量达到设定值、经过一段时间后，段文件真正写入 磁盘，然后公开给消费者

Offset

分区中每个消息的Sequential ID Number（Offset），唯一标识 分区中消息，并没有明确的消息ID

  • 偏移量是增量的但不连续，下个消息ID通过在其偏移量加上 消息长度得到

  • 偏移量标识每个消费者目前处理到某分区消息队列的位置， 对分区消息队列处理依赖于其（消息通过日志偏移量公开）

  • 偏移量由消费者控制，所以消费者可以以任何顺序消费消息

    • 可以回推偏移量重复消费消息
    • 设计消费者仅仅查看分区末尾若干消息，不改变消息， 其他消费者可以正常的消费

从消息分区机制、消费者基于偏移量消费机制，可以看出Kafka消息 消费机制不会对集群、其他消费者造成影响

适合场景

  • Messaging：消息传递，作为传递消息队列（ActiveMQ、 RabbitMQ等）替代品，提供高吞吐能力、高容错、低延迟

  • Website Activity Tracking：网站活动跟踪，要求系统必须 快速处理产生消息

  • Metric：度量，把分布式各个应用程序的运营数据集中，进行 汇总统计

  • Streaming Processing：流数据处理

  • Event Sourcing：事件溯源，把应用程序状态变化以时间顺序 存储，需要支持大量数据

  • Commit Log：日志提交，作为分布式系统提交日志的外部存储 服务

Storm

Storm是分布式、高容错的实时流数据处理的开源系统

  • Storm为流数据处理设计，具有很高的容错性
  • Storm保证每个消息只能得到一次完整处理，任务失败时会负责 从消息源重试消息，从而支持可靠的消息处理
  • 可以通过实现Storm通讯协议，提供其他语言支持

Storm架构

storm_structure

  • 主节点的运行Nimbus守护进程

    • 分配代码
    • 布置任务
    • 故障检测

  • 工作节点运行Supervisor守护进程

    • 监听、开始、终止工作进程

  • Nimbus、Supervisor都是无状态的（不负责维护客户端两次调用 之间状态维护）

    • 这使得两者十分健壮
    • 两者之间的协调由Zookeeper完成

  • Storm在ZeorMQ内部传递消息

Nimbus

Supervisor

Worker

Storm编程模型

Stream

数据流：没有边界的tuple序列

  • 这些tuple以分布式的方式，并行的创建、处理

Topology

计算拓扑：实时计算应用程序处理逻辑封装成的Topology对象

  • 相当于Mapreduce作业，但是MapReduce作业最终会结束、而 Topology会一直运行直到被杀死
  • Topology由Spout、Bolt组成

Spout

消息源：消息tuple生产者

  • 消息源可以是可靠的、不可靠的
  • 可靠的消息源可在tuple没有被storm成功处理时，可以重新发送
  • 不可靠的消息源则在发送tuple之后彻底丢弃

Bolt

消息处理者：封装所有的消息处理逻辑

  • Bolt可以做很多事情，包括过滤、聚集
  • Bolt一般数据处理流程
    • 处理一个输入tuple，发送0个、多个tuple
    • 调用ack接口，通知storm子集已经处理过了

Task、Executor

Topology每个Spout、Bolt转换为若干个任务在整个集群里执行

  • 默认情况下，每个Task对应一个线程Executor，线程用于执行 task
  • 同一个Spout/Bolt里的Task共享一个物理线程

Stream Grouping

数据分发策略：定义Spout、Bolt间Tasks的数据分发

  • Shuffle Grouping：洗牌式分组，上游Spout数据流tuples随机 分发到下游Bolt的Task

  • Fields Grouping：按指定字段进行分组

  • All Grouping：Spout数据tuple分发给所有下Bolt

  • Global Grouping：Spout数据tuple分发给最小id的task

  • Non-Grouping：类似shuffle Grouping，把具有Non-Grouping 设置Bolt推到其订阅的上游Spout、Bolt

  • Direct Grouping：tuple生产者决定接收tuple下游bolt中的task

  • Local or Shuffle Grouping：如果目标bolt中由一个或多个 task工作在同一进程中，tuple分配给这些task，否则同洗牌式 分组

  • Partial Key Grouping：类似Fields Grouping，但是在下游 Bolt中做负载均衡，提高资源利用率

消息处理保证

Storm追踪由每个SpoutTuple产生的Tuple树

  • 每个从Spout发出tuple，可能会生成成千上万个tuple

    • 根据血缘关系形成一棵tuple树
    • 当tuple树中所有节点都被成功处理了，才说明tuple被完全 处理

  • 每个Topology都有一个消息超时设置，如果Storm在时间内无法 检验tuple树是否完全执行，该tuple标记为执行失败，之后重发

重发

Categories

Follow

Recents

Advertisement

follow.it

×