分布式技术原理与算法解析 01

例如使用redis的 SETEX 命令，使用zookeeper、etcd等。协调者可能成为性能瓶颈，容易引发单点故障。应当使用主备备份。

当访问临界资源时，先向其他所有程序发送一条请求消息，在接收到所有程序返回的同意消息后才可访问临界资源。请求消息包含请求的资源、请求者id、发起时间。

程序123共享资源A，程序1和程序3分别在时刻8和时刻12要访问资源。于是分别在相应时刻向其他程序发送申请请求。

程序2暂时不访问，所以同意1和3的请求。1比3提出的时间更早，于是3同意1的申请，并等待1返回同意

程序1接收到其他所有程序的同意消息后，使用资源A并结束后释放，向请求队列中要使用资源A的程序3发送同意请求，并将其中队列中删除。程序3接收到1返回的同意消息后获得权限，能够访问A

访问一次临界资源要发送 n-1 次请求、接收 n-1 次响应，至少 2*(n-1) 次交互，可能带来“信令风暴”。且一台机器故障整个系统不可用。

通信成本高，可用性低。其适合节点少且变动不频繁的系统，如P2P结构系统。Hadoop的HDFS文件系统就应用了分布式算法。

所有程序组成一个环，令牌按照某个方向在程序间传递。拿到令牌才能访问资源，若不需要则直接传递给下一个。

单个程序有更高的通信效率，一个周期内每个程序都能访问到资源。但是即使系统中只有一个节点需要访问资源，令牌也要在所有节点中反复传递。令牌环算法非常适合通信模式为令牌环方式的分布式系统，如移动自组织网络、无人机通信。

集中式和单点式都存在单点故障问题，在令牌环算法中一个程序故障后，直接将令牌传递给故障程序的下一个，从而解决单点故障问题。但这要求每个程序都能记住环中所有参与者。适用于系统规模较小且每个程序都高频率使用临界资源且时间较短的场景。

两层结构的分布式令牌环算法，将整个网络组织成两层结构，在全局环有一个全局令牌，在局部环上有一个局部令牌。

主节点负责整个分布式集群中节点的协调和管理，保证节点的有序运行和一致性。

简单直接，选取ID最大节点为主节点。初始时所有节点都是普通节点，选举成功后仅当主节点故障或失去联系后才重选主节点。选举中用到3种消息：

此算法假设集群中每个节点均知道其他节点ID，选举过程如下：

MongoDB 的副本集群故障转移就使用了 Bully 算法，其使用节点的最后操作时间戳作为ID。

此算法优点是选举速度快、算法复杂度低、简单易实现。缺点：每个节点要保存全局信息，故额外信息多；任一比当前主节点ID大的新节点加入集群时都可能触发重新选举，如果其因网络原因频繁退出加入集群会导致频繁切主。

3种角色：leader、candidate、follower。选举流出如下：

通过节点ID和数据ID作为参考进行选举，节点ID和数据ID越大表示数据越新，优先成主。3种角色：leader、follower、observer（观察者，无投票权）。节点有4种状态：looking（选举状态，认为集群中没有leader）、leading、following、observing。

投票过程种每个节点都有唯一三元组 (server_id, server_szID, epoch) 分别表示（本节点唯一ID；本节点存放的数据ID，越大则数据越新选举权重越大；当前选取轮数，一般用逻辑时钟表示），用于表示自己的信息。

采取“少数服从多数，ID大的节点优先”，通过 (epoch, vote_id, vote_zxID) 表明投票给哪个节点，二元组表示（轮数；被投票节点id；被投票节点的服务器zxID）。ZAB中先比较 server_szID，再比较 server_id，大的为leader。

以3个节点为例：

ZAB采用广播方式，若有n个节点则信息量为 n*(n-1)。投票时要知道所有节点的节点ID和数据ID，所以需要时间较长。当稳定性较好，加入新节点时会触发选主，但不一定切换。

在分布式系统中运行的事务，由多个本地事务组合而成。实现方法：

简单概括：协调者下发请求事务操作，参与者将操作结果通知协调者，协调者根据所有参与者的反馈结果决定各参与者是要提交操作还是撤销操作。

为了保证不同节点分布式事务一致性，选哟一个协调者管理所有节点。分2个阶段：投票、提交

其满足了ACID但仍有不足：

引入了超时机制和准备阶段，用于解决同步阻塞和数据不一致问题

前者需要锁住资源，且没有解决数据不一致问题。这里将要处理的事务通过消息或日志的方式异步执行，消息或日志可存入本地文件、db、mq，再通过业务规则进行失败重试。这使用基于分布式消息的最终一致性解决方案解决分布式事务问题。

例如电商平台下单支付，通过支付系统支付成功后订单状态修改为支付成功，然后通知厂库发货。三个相互独立系统通过rpc调用。

购物流程如下：

锁是实现多线程同时访问同一共享资源，保证同一时刻只有一个线程可访问共享资源所做的一种标记。分布式锁是指分布式环境下，系统部署在多个机器中，实现分布式互斥的一种机制

例如某电商售卖吹风机，库存2个，但有5个买家。最简单方案就是给吹风机库存数加一个锁，每个用户提交订单后，后台服务器给库存加一个锁，根据订单修改库存。但是这个方法仍存在问题。例如：理想情况下，A买了1个，库存还剩1个，此时应当提示B库存不足，B购买失败。但如果是A和B同时获取到库存还剩2个的数据。A买走1个，B买走2个，库存还剩0或1个。此时总共只有两个吹风机，但卖出去3个。（可以考虑MySQL的 for update 语句）。

创建一张锁表，通过操作该表数据实现分布式锁。要锁住某个资源就增加一条记录，要释放时就删除这条记录。db对共享资源做唯一约束。

缺点：

将数据放入计算机内存，不写入磁盘减少IO。通常使用 Redis 的 setnx(key, value)。

再考虑电商售卖吹风机的场景，假设库存数量充足。A先到达Server2通过setnx获得锁；B和C几乎同时到达Server1和Server3，但因为Server2获得锁，所以只能等待。Server2获得锁后用1s完成订单，删除key以释放锁。Server1获得锁可以访问资源，但是完成操作后发生故障，无法主动释放锁。Server3只能等到已有的key超时，锁自动释放后才能访问资源。

相比与使用数据库，使用缓存优点如下：

缺点是超时机制不是十分靠谱，如果一个进程执行时间较长导致时间超时，从而不正确释放了锁。

zookeeper基于树形结构实现分布式锁，其由4种节点组成：

基于zookeeper的临时顺序节点实现了分布式锁

仍以电商售卖吹风机为例，用户ABC同时提交了购物请求：

图中，只有再A完成购买、C完成查询后，B才可以购买。

zookeeper解决了各种问题，如单点故障、不可重入、死锁等，但由于频繁的删除添加节点，所以性能不如基于缓存实现的分布式锁。

设计分布式锁应该考虑：

“羊群效应”指分布式锁竞争中大量“watcher消息”和“子节点列表获取”操作重复进行，且大多数节点的结果都是自己并不是最小的节点，继续等下一次通知，而不是执行业务逻辑。这会对zookeeper造成去打性能和网络影响。解决方法如下：