分布式基本概念 - 分布式 | 啵啵的黄金屋 = 新的启程 = 勤能补拙

# 分布式

# 分布式缓存

# 一致性哈希算法

# 布隆算法

布隆算法是为了解决缓存穿透问题而设置的布隆过滤器原理

1. 将全部数据库当中的 ID 值进行 hash 函数计算，结果范围为 [0,m] 之间

2. 将结果存入一个长度为 m 的二进制当中

存入方案

假设 ID=1 的一个数据通过 hash 计算的结果为 2
那么长度为 m 的二进制数据为 0010......
假设再存入一个数据 ID=10，通过 hsah 计算结果为 4
那么长度为 m 的二进制数据为 0010100......
如果计算结果重复，那么当前位置的值不变

原则：

如果客户端发送过来数据 ID 计算结果的二进制位为 1，表示存在，但是实际结果不一定存在
如果客户端发来数据 ID 计算结果在二进制上为 0，表示不存在，那么实际结果一定不存在

降低错误率：

1. 可以增大二进制长度，降低 hash 碰撞概率

2. 增加多个 hash 函数，多个函数计算结果分别标志 1，由多个标志的 1 决定一个 ID 是否存在

代码实现：

	package main

	import "fmt"

	var bitmap []byte

	func main() {
	s := "test"
	Blood(8, s, 8)
	fmt.Println(bitmap)
	}

	func Blood(n int, key string, prime int) {
	bitmap = make([]byte, n)
	bitmap[hash(key, prime)] = 1
	}
	func hash(key string, prime int) int {
	var ha int = len(key)
	for i := 0; i < len(key); i++ {
	ha = ha + int(key[i])
	}
	return ha % prime
	}

# 分布式锁

分布式锁实现三种方式：

基于数据库实现分布式锁；
基于缓存（Redis 等）实现分布式锁；
基于 Zookeeper 实现分布式锁；

分布式锁应该具备哪些条件

1、在分布式系统环境下，一个方法在同一时间只能被一个机器的一个线程执行；
2、高可用的获取锁与释放锁；
3、高性能的获取锁与释放锁；
4、具备可重入特性；
5、具备锁失效机制，防止死锁；
6、具备非阻塞锁特性，即没有获取到锁将直接返回获取锁失败。

为了防止单机情况下，某一台 redis 宕机，采用 Redlock 分布式锁

# Redlock 实现

在 Redis 的分布式环境中，我们假设有 N 个 Redis master。这些节点完全互相独立，不存在主从复制或者其他集群协调机制。我们确保将在 N 个实例上使用与在 Redis 单实例下相同方法获取和释放锁。现在我们假设有 5 个 Redis master 节点，同时我们需要在 5 台服务器上面运行这些 Redis 实例，这样保证他们不会同时都宕掉。

为了取到锁，客户端应该执行以下操作:

获取当前 Unix 时间，以毫秒为单位。
依次尝试从 5 个实例，使用相同的 key 和具有唯一性的 value（例如 UUID）获取锁。当向 Redis 请求获取锁时，客户端应该设置一个网络连接和响应超时时间，这个超时时间应该小于锁的失效时间。例如你的锁自动失效时间为 10 秒，则超时时间应该在 5-50 毫秒之间。这样可以避免服务器端 Redis 已经挂掉的情况下，客户端还在死死地等待响应结果。如果服务器端没有在规定时间内响应，客户端应该尽快尝试去另外一个 Redis 实例请求获取锁。
客户端使用当前时间减去开始获取锁时间（步骤 1 记录的时间）就得到获取锁使用的时间。当且仅当从大多数（N/2+1，这里是 3 个节点）的 Redis 节点都取到锁，并且使用的时间小于锁失效时间时，锁才算获取成功。
如果取到了锁，key 的真正有效时间等于有效时间减去获取锁所使用的时间（步骤 3 计算的结果）。
如果因为某些原因，获取锁失败（没有在至少 N/2+1 个 Redis 实例取到锁或者取锁时间已经超过了有效时间），客户端应该在所有的 Redis 实例上进行解锁（即便某些 Redis 实例根本就没有加锁成功，防止某些节点获取到锁但是客户端没有得到响应而导致接下来的一段时间不能被重新获取锁）。

# 分布式事务

# CAP 理论

CAP 是一致性，可用性，分区容忍性

一致性：
写操作后的读操作可以读取到最新的数据状态，当数据分布在多个节点上，从任意节点读取到的数据都是最新的状态
可用性
任何事物操作都可以得到响应结果，不会出现响应超时或者响应错误
分区容忍性
因为分布式系统各个节点部署在不同的子网，不可避免的会出现由于网络问题而导致节点之间通信失败，此时仍可进行对外提供服务

在所有分布式事务场景中不会出现同时具备 CAP 三个特性，因为在具备了 P 特性下，C 和 A 无法共存

** 原因：** 因为一致性在进行数据同步的时候会对数据进行锁定而无法获取结果，而可用性是需要在任何时候都可以得到响应结果，所以两个特性是存在矛盾。

# 2PC 提交

2PC 是两阶段提交协议，是将整个事务流程分为两个阶段，准备阶段，提交阶段

准备阶段
事务管理器给每个参与者发送 Prepare 信息，每个数据库参与者在本地执行事务，并写入本地的 Undo/Redo 日志，此时事务没有提交（Undo 日志是用于记录修改前的数据，Redo 日志用于记录修改后的日志）
提交阶段
所有事务操作都是正常操作成功之后，提交阶段才会真正开始执行，如果其中一个发生错误，那么提交就不会进行

两种解决方案：

XA 方案

1. 在准备阶段分支事务执行实际业务操作，但是不提交事务，资源锁定

2. 在提交阶段事务管理器会接受分支事务在准备阶段的执行回复，只要有任意一个分支事务执行失败，事务管理器就会通知所有分支事务执行回滚操作，否则，事务管理器将会通知所有分支事务提交该事务，提交阶段结束，资源释放

缺点：

1. 需要本地数据库支持 XA 协议

2. 资源锁需要等到两个阶段结束才释放，性能较差

seata 方案：

1. 在用户服务的事物管理器向事物协调器申请开启一个全局事务，全局事务创建成功并返回一个全局唯一的 XID

2. 用户服务的分支事务向事物协调器注册分支事务，该分支用户在用户进行操作增加数据逻辑时候（已经提交），并将其纳入 XID 对应的全局事务管辖

3. 用户服务执行分支事务，向用户表插入一条数据

4. 用户分支事务执行完毕

5. 事务管理器向事物协调器发起针对 XID 的全局提交或者回滚

6. 事务协调器调度 XID 下管辖的全部分支事务完成提交或者回滚

Seata 实现 2PC 与传统 2PC 的区别

架构层次方面，传统数据库的分支事务是实际上是在数据库层面，分支事务本身就是数据库自身通过 XA 方案实现，而 Seata 的分支事务则是以包形式的中间件层部署在应用程序这一侧

两阶段提交方面，传统 2PC 是等到两个阶段都完成之后才对锁进行释放，而 Seata 的做法是在第一阶段就将本地事务提交，这样省去了第二阶段持有锁的时间，整体效率变高

# TCC 事务

TCC 要求每个分支事务实现三个操作：预处理 Try，确认 Confirm、撤销 Cancel。

Try 操作做业务检查以及资源预留，Confirm 做业务确认操作，Cancel 实现一个与 Try 相反的操作即回滚操作

事务管理器首先发起所有的分支事务的 try 操作，任何一个分支事务的 try 操作执行失败，事务管理器将会发起所有分支事务的 Cancel 操作，若 try 操作全部成功，事务管理器将会发起所有分支事务的 Confirm 操作，其中 Confirm/Cancel 操作若失败，事务管理器将会进行重试

Try 阶段是做业务检查 (一致性) 及资源预留 ( 隔离 ) ，此阶段仅是一个初步操作，它和后续的 Confifirm 一起才能真正构成一个完整的业务逻辑。
Confifirm 阶段是做确认提交， Try 阶段所有分支事务执行成功后开始执行 Confifirm 。通常情况下，采用 TCC 则认为 Confifirm 阶段是不会出错的。即：只要 Try 成功， Confifirm 一定成功。若 Confifirm 阶段真的出错了，需引入重试机制或人工处理。
Cancel 阶段是在业务执行错误需要回滚的状态下执行分支事务的业务取消，预留资源释放。通常情况下，采用 TCC 则认为 Cancel 阶段也是一定成功的。若 Cancel 阶段真的出错了，需引入重试机制或人工处理。
TM 事务管理器
TM 事务管理器可以实现为独立的服务，也可以让全局事务发起方充当 TM 的角色， TM 独立出来是为了成为公用组件，是为了考虑系统结构和软件复用。

TM 在发起全局事务时生成全局事务记录，全局事务 ID 贯穿整个分布式事务调用链条，用来记录事务上下文，
追踪和记录状态，由于 Confifirm 和 cancel 失败需进行重试，因此需要实现为幂等，幂等性是指同一个操作无论请求
多少次，其结果都相同。

TCC 需要注意三种异常处理分别是空回滚、幂等、悬挂:

空回滚：

在没有调用 TCC 资源 Try 方法的情况下，调用了二阶段的 Cancel 方法，Cancel 方法需要识别出这是一个空回滚，然后直接返回成功。

出现原因是当一个分支事务所在服务宕机或网络异常，分支事务调用记录为失败，这个时候其实是没有执行 Try 阶段，当故障恢复后，分布式事务进行回滚则会调用二阶段的 Cancel 方法，从而形成空回滚。

解决思路是关键就是要识别出这个空回滚。思路很简单就是需要知道一阶段是否执行，如果执行了，那就是正常回滚；如果没执行，那就是空回滚。前面已经说过 TM 在发起全局事务时生成全局事务记录，全局事务 ID 贯穿整个分布式事务调用链条。再额外增加一张分支事务记录表，其中有全局事务 ID 和分支事务 ID ，第一阶段 Try 方法里会插入一条记录，表示一阶段执行了。 Cancel 接口里读取该记录，如果该记录存在，则正常回滚；如果该记录不存在，则是空回滚。

幂等：

通过前面介绍已经了解到，为了保证 TCC 二阶段提交重试机制不会引发数据不一致，要求 TCC 的二阶段 Try、Confifirm 和 Cancel 接口保证幂等，这样不会重复使用或者释放资源。如果幂等控制没有做好，很有可能导致数据不一致等严重问题。

解决思路在上述 “分支事务记录” 中增加执行状态，每次执行前都查询该状态。

悬挂：

悬挂就是对于一个分布式事务，其二阶段 Cancel 接口比 Try 接口先执行。

出现原因是在 RPC 调用分支事务 try 时，先注册分支事务，再执行 RPC 调用，如果此时 RPC 调用的网络发生拥堵，通常 RPC 调用是有超时时间的，RPC 超时以后，TM 就会通知 RM 回滚该分布式事务，可能回滚完成后，RPC 请求才到达参与者真正执行，而一个 Try 方法预留的业务资源，只有该分布式事务才能使用，该分布式事务第一阶段预留的业务资源就再也没有人能够处理了，对于这种情况，我们就称为悬挂，即业务资源预留后没法继续处理。

解决思路是如果二阶段执行完成，那一阶段就不能再继续执行。在执行一阶段事务时判断在该全局事务下，“分支事务记录” 表中是否已经有二阶段事务记录，如果有则不执行 Try。