⛵️帆船书#17&18 | 并行数据库

数据库系统体系结构

[1] 集中式数据库系统完全运行在单台计算机上, 随着个人计算机和局域网的发展, 数据库前端功能不断移向客户机, 后端由服务器系统提供
客户-服务器接口协议推动了客户-服务器数据库系统发展

[2] 事务服务器在提供数据库服务方面使用大大超过数据服务器

• 事务服务器有多个进程, 可能运行在多个处理器上, 所有进程访问公共数据(数据库缓冲区), 系统将这些数据存放在共享内存中
  处理查询的进程, 执行(锁和日志管理以及检查点等)任务的系统进程
• 数据服务器提供未加工的数据, 通过把数据和锁告诉缓存在客户端, 努力使客户端和服务器通信最小化——并行数据库使用类似的优化

[3] 并行数据库系统由(通过高速互联网络连接在一起的)多台处理器和多张硬盘构成
加速比衡量通过增加并行性可以得到的对单个事务的处理速度的增长
扩展比衡量通过增加并行性可以得到的处理大量事务的能力
得到理想加速比和扩展比的障碍:

• 干扰: 由于并行系统执行进程经常要访问共享资源, 新进程与原有进程竞争共享资源(系统总线、共享硬盘、锁)会发生干扰, 同时影响加速比和扩展比
• 偏斜: 单个任务分解为多个并行步骤, 规模分配方式可能是偏斜的
• 启动代价: 可能掩盖实际的处理时间, 降低加速比

[4] 并行数据库体系结构

• 共享内存: 共享公共的主存和磁盘
• 共享磁盘: 共享公共磁盘, 有独立的主存
• 无共享: 不共享磁盘和主存
• 层次: 不共享磁盘和主存, 但是每个结点内部共享内存或共享磁盘

[5] 分布式数据库系统是部分独立的一组数据库系统, 共享一个公共模式, 协调地处理访问非本地数据的事务
系统之间通过通信网络相互通信

[6] 局域网连接分布在小的地理范围内的结点, 比如连接单个建筑或几个相邻的建筑
广域网连接分布在打的地理范围内的结点——Internet

[7] 存储区域网是一种特殊形式的局域网, 是为大型存储设备和多台计算机之间提供快速互联而设计的

I/O并行

[1] 数据访问: 扫描; 点查询; 范围查询

[2] 把关系划分到多张可用磁盘中, 使检索速度更快

划分	方法	适用
轮转	对关系任意顺序扫描, 每张磁盘有大致相同数目元组	适合对每个查询顺序读整个关系的应用, 不适用于点查询和范围查询
散列	将给定关系一个或多个属性指定为划分属性, 基于划分属性进行散列	适用于基于划分属性的点查询和顺序扫描整个关系的查询, 但是不适用于基于非划分属性 的点查询和范围查询
范围	给每张磁盘分配有连续属性值范围的元组	适用于基于划分属性的点查询和范围查询 执行偏斜: 如果查询范围内有许多元组, 会导致磁盘I/O瓶颈——对于这样的查询可以使用散列分布和轮转法

[3] 常用散列划分和范围划分
小型关系最好放在单张磁盘; 大型关系倾向于放到所有可用磁盘
关系有m张磁盘块, 系统有n张磁盘, 则应该分配min{m, n}张磁盘

[1] 偏斜的表现形式:

• 属性值偏斜: 某些值出现在许多元组的划分属性中, 划分属性上取相同值的所有元组落入统一分区
• 划分偏斜: 即使不存在属性值偏斜, 划分也出现了负载不均衡

[2] 随着并行度增大, 由于偏斜导致加速比的损失也增大

[3] 减少偏斜的技术

• 平衡划分向量: 首先关系按照划分属性排序, 然后用排序顺序扫描, 每读过1/n, 将下一元组的划分属性值加入划分向量——缺点: 初始排序的额外I/O开销
• 使用直方图: 直接构造平衡的范围划分函数, 直方图可以存储在系统目录中
• 虚处理器划分: 针对范围划分, 首先将元组和操作映射到虚处理器, 然后将虚处理器一次映射回事雞的处理器(通过轮转法划分实现)
  思想: 即使由于偏斜使得一个范围内有比其他范围更多的元组, 这些元组也将划分到多个虚处理器范围上, 轮转法将虚处理器分配到实际的处理器, 就将额外的工作分布到多个实际的处理器中

查询间并行

[1] 用处: 扩展事务处理系统, 并发地运行不同查询, 提高吞吐量
单个事务的响应时间不会比事务以隔离方式运行时更快

[2] 共享内存: 无需修改, 类似串行机器中分时并发的事务

[3] 共享磁盘: 需要互相传送封锁和日志等消息
当一个处理器访问或更新数据时, 数据库系统必须保证该处理器在它的缓冲池中拥有该数据等最新版本——高速缓存一致性

1. 事务对一个页面读写之前, 先用相应共享或排他模式封锁页面, 获得锁后从共享磁盘读取该页面最新版本
2. 事务释放页面排他锁之前, 将页面刷新到共享磁盘
   如果最新版本在某个处理器缓冲池, 事务可以从缓冲池获得页面, 避免对磁盘重复读写

[4] 无共享: 每个页面有一个本地处理器, 存储在磁盘中
其他处理器想对页面读写时, 将请求发给该页面本地处理器, 而不是直接给页面所在磁盘

查询内并行

[1] 单个查询在多个处理器和磁盘并行执行, 减少运行查询的代价

[2] 操作内并行: 并行执行每个运算, 如排序、选择、投影和连接
操作间并行: 执行一个表达式的多个不同运算
可以互相补充, 并同时应用在一个查询中

操作内并行

因为关系运算面向集合, 所以操作内并行对关系运算(如排序和连接)很自然

[1] 范围划分排序

1. 首先对关系范围划分, 然后对每个分区进行排序
2. 采用范围划分策略对关系中元组重新分布, 使得处于第i个范围的所有元组发送给处理器Pi, 将关系临时存放在磁盘Di
3. 每个处理器在本地对关系中属于自己的分区排序

必须使用好的范围划分向量, 使得每个分区中元组数目大致相同
使用虚处理器划分减少偏斜

[2] 并行的外排归并

1. 每个处理器Pi在本地对磁盘Di中的数据排序
2. 归并: 将每个处理器Pi中排好序的分区使用相同划分向量范围划分到处理器P0…Pm-1中, 用顺序排序发送元组是的每个处理器接收的都是排好序的元组流
3. 每个处理器接收到元组流时归并, 得到一个排好序的归并段
4. 系统将P0…Pm-1中排好序的归并段串接起来得到最终结果

执行偏斜的解决方案: 每个处理器重复地向每个分区发送一个数据块, 即每个处理器发送每个分区第一个数据块, 然后发送每个分区第二个数据块, 让所有处理器可以并行地接受数据

[1] 基于划分的连接(等值连接和自然连接)
两个关系分成几个部分, 而且r中元组仅与s中元组连接
对于范围划分, 两个关系必须采用相同划分向量; 对于散列划分, 两个关系必须使用相同散列函数
可以通过把某些元组放在内存缓冲区, 而不是写到磁盘减少I/O
划分向量应该使|ri|+|si|大致相等

[2] 分片-复制连接(任何连接条件)
两个关系都被划分并且每个划分都被复制到所有处理器
如果两个划分分别为n和m个分区, 那么必须保证至少有m*n个处理器
非对称的分片和复制中, 一个关系被复制, 另一个关系被划分——适用于一个关系很小

[3] 基于划分的并行散列连接
s比r小, 选择较小的关系作为建立散列表的关系

1. 选择散列函数h1, 取得r和s每个元组的连接属性的值, 将元组映射到n个处理器中的一个
   每个处理器Pi读取s中位于Di上的元组, 基于散列函数h1将每个元组发送到适当处理器
2. 目的处理器Pi接收到si, 另一个散列函数h2做进一步划分, 用h2在本地计算散列连接
3. 然后通过h1将较大关系r在n个处理器上重新分布, 目的处理器用h2对它重新划分
4. 每个处理器Pi对r和s本地分区ri和si上执行散列连接算法的创建和探查, 产生散列连接最终结果的一个分区

[4] 并行嵌套循环连接
假设r的每一个分区存在r在连接属性的索引
非对称的分片和复制方法中, 每个处理器Pi对关系s和r第i个分区进行索引嵌套循环连接, 与关系s的元组划分重叠起来做, 减少将s的元组写入磁盘在读出来的代价
s的复制必须与连接同步, 每个处理器Pi的内存缓冲区能有足够的空间存放已经接收到但是尚未用于连接的关系s的元组

操作间并行

[1] 独立并行中: 互不依赖的多个不同操作按并行方式执行
在高度并行的系统中没有太大的用处

[2] 流水线并行中: 处理器计算一个操作结果同时将结果发送给另一个操作, 无需等待整个操作完成
可扩展性不好:

• 只有少量处理器时才有用, 达不到足够的长度来提供较高的并行度
• 对于访问访问所有输入才能输出的关系运算(如集合差运算)不能采用流水线
• 对于一种运算执行代价比其他运算高的多的情况只能获得很小加速比

查询优化和并行系统设计

[1] 查询优化考虑问题

1. 在并行系统中计算运算符树:
   如何对每个运算进行并行化, 为每个运算采用多少个处理器
   在多个处理器上对哪些运算流水线化, 哪些独立执行, 哪些串性执行
2. 确定分配给执行树中每个运算各种类型的资源(处理器、磁盘和内存)

[2] 采用启发式方法减少需要考虑的并行执行计划的数目

1. 仅考虑利用所有处理器, 对每个运算都并行化, 不采用流水线的执行计划
2. 选择最高效的串行执行计划, 然后将该执行计划中的运算并行化 (可以使用交换算子)

[3] 处理器和磁盘发生故障的恢复性: 数据至少复制到两个处理器, 系统追踪失效的处理器, 将工作分配给多个正常运行的处理器

[4] 联机进行: 在系统执行其他事务的同时进行这样的操作
联机索引创建: 进程记住创建索引活跃其间发生的更新, 将变化合并到正在建立的索引中