卡内基梅隆的数据库课程-5

课程地址
https://15445.courses.cs.cmu.edu/fall2021/schedule.html

Introduction to Distributed Databases

并行 VS 分布式

并行数据库
每个节点在物理上都比较近
节点之间的通讯是高速LAN
通讯花费比较小
分布式DMBS
节点的物理位置比较远
节点通讯走公网
节点的通讯开销不能忽略

分布式DB

使用单节点介绍的技术，现在来支持分布式环境中的事务和查询执行
优化、查询几乎
并发控制
日志、恢复
分布式的架构指明，哪些共享资源可以被CPU直接访问
这影响了CPU之间的彼此协调，以及他们在数据库的什么地方检查/存储对象

分布式数据库的架构

shared everything
shared memory
CPU通过内部连接访问共享的内存地址
每个CPU都有所有内存数据结构的全局视图
每个处理器上的DBMS实例，知道其他实例
没什么实际的DBMS用这种架构，只有HPC high performace computing 是这种架构
shared disk
每个CPU通过内部连接访问单个逻辑磁盘，每个CPU都有他们自己的私有内存
对于存储层来说，计算层的扩容是独立的
必须在CPU之间发送消息，让他们学习到其他节点的状态
shared nothing
每个DBMS实例都有它自己的CPU、内存、磁盘
节点之间通讯只能通过网络
扩容比较困难、确保一致性比较难、性能和效率比较高

早期的分布式数据库

MUFFIN – UC Berkeley (1979)
SDD-1 – CCA (1979)
System R* – IBM Research (1984)
Gamma – Univ. of Wisconsin (1986)
NonStop SQL – Tandem (1987)

设计问题

应用如何找到数据？
如果再分布式数据中执行查询？
Push query to data.
Pull data to query.
DBMS如何确保正确性？

同质节点 VS 非同质节点

Approach #1: Homogenous Nodes
集群中的每个节点都执行相同的任务集合，尽管数据分区不同
使配置和故障转移更容易
Approach #2: Heterogenous Nodes
节点被分配特殊任务
允许一个物理节点承载专用任务的多个虚拟节点

数据的透明性

用户不需要知道数据的的物理分布，表如何被分区、复制
一个查询可以工作于单个节点的DB，同样也可以运用于分布式DB

数据分区

NoSQL通常叫 sharding
每个节点执行一个查询片段，然后再做合并
naive表分区，每个节点都有全量的数据
水平分区，表的tuple包含不想交的集合
选择按大小、负载、使用平均量划分数据库的列
物理分区，shared nothing；逻辑分区 shared disk
hash分区，range分区

一致性hash，以及Replication Factor

单节点 vs 分布式

单节点的事务只需要访问一个分区
DBMS不需要协调其他节点上的并发事务
分布式事务需要访问一个或多个分区
需要很大的协调开销

事务协调

如果DBMS支持多个操作，以及分布式事务，就必须要一种方式协调他们执行
中心化的方式
去中心化的方式
TP monitor对于DBMS是一个中心化协调的例子
开发于1970-1980年代，提供终端和大型机之间的事务
ATM、航空公司预定
现在的数据库也支持这个功能

分布式并发控制

允许多个事务跨多个节点并发执行
很多单个DBMS的协议需要做修改
实现起来很难
复制、网络通讯开销、节点失败、时钟倾斜

TP Monito

Distributed OLTP Database Systems

OLTP vs OLAP

On-line Transaction Processing (OLTP):
Short-lived read/write txns.
Small footprint.
Repetitive operations
On-line Analytical Processing (OLAP):
Long-running, read-only queries.
Complex joins.
Exploratory queries.

问题

We have not discussed how to ensure that all nodes agree to commit a txn and then to make sure it does commit if we decide that it should.

What happens if a node fails?

What happens if our messages show up late?

What happens if we don’t wait for every node to agree?

重要的假定

假设所有的节点都是良好的，并且都是相同的管理域
如果节点没有失败，那么让其提交事务，最后肯定会提交的
如果不相信分布式DB中的其他节点，需要对事务使用拜占庭容错协议，区块链

原子提交协议

当多个节点完成时，DBMS需要询问多个节点是否可以安全提交
Two-Phase Commit
Three-Phase Commit (not used)
Paxos
Raft
ZAB (Apache Zookeeper)
Viewstamped Replication

2PC

每个节点记录每个阶段的结果，到非易失性存储日志中
What happens if coordinator crashes?
Participants must decide what to do.
What happens if participant crashes?
Coordinator assumes that it responded with an abort if it hasn’t sent an acknowledgement yet