通过在多个节点(计算机)上对多个磁盘上的数据集进行分区，减少从磁盘检索数据所需的时间，主要两种形式
1）跨节点并行
2）一个节点跨磁盘并行
水平分区一数据记录被划分在多个节点上，即每个节点上存储一个数据子集
1）垂直分区:例如r(A,B,C,D)，主键为A，划分为r1(A,B)和r2(A,C,D)
2）默认是水平分区

I/O并行技术(设节点数为n):

轮询方法(Round-robin) :
第i条记录存储到的节点为imod n.
Hash分区:
选择一个或多个属性作为分区属性.
选择取值范围为0…n-1的哈希函数h
设i为哈希函数h应用于记录属性的计算结果，然后将记录存储在节点i
范围分区:
选择分区的属性.
选定分区向量vector [vo,v1 …]
设v是一条记录分区属性的值，那么1≤V1的记录分配到节点i+1; V< Vo的记录分配到节点0;V≥Vn2的记录分配到节点n-1.

五、分片

水平的将大的数据集划分为较小的，易于管理的数据集的过程，数据切成碎片。

每个碎片可以独立地为所负责的数据提供读写的服务
某个查询的数据可能来自两个碎片
数据分片要考虑查询模式以便碎片本身不会称为性能瓶颈

六、复制

多个结点上存储数据集的多个拷贝，称作副本。
相同的数据在不同的结点上存在多个副本，提供了可伸缩性，可用性和容错性

复制实现方法

主从复制
对等复制

主从复制

系统配置是主从配置环境
所有数据写入主节点，持久化后复制到多个从节点。
数据的写(增删改)操作访问主节点的数据，读(查询)操作访问任意节点。
适用于读密集型应用
需要考虑读一致性的问题
主要解决方法有：
1）投票机制:大多数从节点包含相同版本的记录，则声明读操作是一致的
2）实现投票机制需要从节点之间建立可靠、快速的沟通机制

对等复制

节点之间不分主从，每个节点是对等的，每个写操作数据复制到所有对等的节点上。
每个节点都可以处理读请求和写请求。
对等复制容易导致写不一致问题:同时更新多个节点的同一个数据
1）悲观并发策略:基于锁机制
2）乐观并发策略:不用锁，最终一致性
读不一致性问题
投票机制

七、数据分布倾斜（Data-Distribution skew）

一些节点拥有较多记录，而其他节点则拥有的记录数很少。
.数据分布倾斜类型
1）属性-值倾斜
➢一些分区属性值出现在多个记录中
➢分区属性值相同的所有记录最终都在同一个分区中
➢范围分区和hash分区都会出现这个问题.
2）分区倾斜
➢选择不当的范围分区向量可能会将太多记录分配给某些分区，而将太少记录分配给其
3）执行倾斜
➢某些运算符运行的时间比其他运算符长，执行时间的差异可能会导致一些处理器空闲，而其他处理器仍然计算查询的一部分。

处理范围中分区倾斜

创建平衡的分区向量
1）基于分区属性对数据进行排序
2）按照如下顺序扫描数据来构造分区向量
➢每读取1/n的数据之后，下一个记录的分区属性值被添加到分区向量中(n表示分区数量)
3）如果分区属性中存在重复项，则可能导致不平衡.
减少代价
➢分区向量可以使用记录的随机样本创建
➢另外一种方法:采用直方图(histograms) 建立分区向量

八、虚拟结点分区

核心思想:假设虚拟节点的数量是实际节点倍数

虚拟节点映射到真实节点
使用范围分区向量跨虚拟节点划分记录
➢Hash分区也可以用
虚拟节点映射到真实节点
1）轮询:虚拟节点i映射到真实节点(imod n)+1
2）映射表:映射表virtual to_ real map[]记录哪一个虚拟节点在哪一个真实节点上
➢允许通过将虚拟节点从加载较多的节点移动到加载较少的节点来处理倾斜
➢解决了数据倾斜和执行倾斜

九、一致性HASH

1997年由MIT的Karger等人在解决分布式Cache中提出。
场景: 假设有N个Cache, 如何将数据对象映射到N个Cache?
-> Hash (object) % N
如果Cache m坏了，则所有映射到cachem的对象会失效
-> Hash (object) % (N-1)
如果访问负载增加，需要添加cache
->Hash (object) % (N+1)
如果硬件能力增强，希望增加的节点承担更多的负载，普通hash算法难以实现

算法原理

环形空间：共有2^32个bucket空间，首尾相接形成环
数据映射到环形hash空间
使用相同的hash函数将结点(cache/server)映射到hash空间，通常用结点的ip
将数据映射到结点
沿顺时针方向，根据数据对象的key，遇到第一个cache/server就将数据存入其中。
如果某节点server宕机
按顺时针迁移的规则，opject2迁移至object3，其他不变
如果增加新服务器
按顺时针迁移规则，object4被迁移到server4中，其他不变。

引入虚拟结点的一致性hash

节点分布不均匀，出现Skew问题
设虚拟节点个数为4
Server11, Server12, server31, server32数据对象Object到虚拟节点的对应关系Object1→server12;
Object2 > server32
Object3 >server31
Object4 > server11
虚拟节点的hash计算采用对应节点的IP地址;数字后缀的方式
➢例如，Server1 的IP地址为202.168.110.241
Hash (“202.168.110.241#1" )，
Hash (“202.168.110.241#2” )

数据库SQL（十）：水平扩展及数据一致性

文章目录

一、单机的一致性

问题

解决方案

二、计算平台分类

三、集群

四、 I/O并行