写点什么

【分布式技术】分布式锁和 ID

作者:L L
  • 2024-03-24
    广东
  • 本文字数:5162 字

    阅读完需:约 17 分钟

【分布式技术】分布式锁和ID

在分布式系统中,需要为每个实体(对象、业务记录等)分配唯一的标识符,以便在不同节点间进行识别和定位。分布式 ID 能够通过特定算法或中心化的分配器来生成全局唯一的标识符,保证系统的正常运行和识别不同实体的能力。

分布式 ID

常见分布式 ID 实现,一般要求具有以下特性:

  • 全局唯一

  • 有序性(趋势递增、单调递增):可以通过时钟同步、分布式锁、MQ、一致性协议等方法来保证

  • 有一定意义(含时间戳),但需要安全(防止被识别规律)

  • ID 生成器高可用:尽量低延迟、高 QPS;紧凑型(存储友好)

方案 1:UUID

UUID 是按照 OSF(开放软件基金会)制定的标准计算,业界有多种方式生成 UUID,一般用到以太网卡地址、当前纳秒级时间(时钟序列)、芯片 ID 码和许多可能的数字。

  • 全局唯一的 IEEE 机器识别号:优先从网卡获得,否则从其他方式获得

  • 实现简单,性能好(本地生成,没有网络消耗)。如果只是考虑唯一性,那么 UUID 基本满足使用要求。


特定场景下,存在以下问题:

  • 无序:不能保证趋势递增;UUID 生成的是字符串(不全是数字),无序字符串,存储和查询性能差

  • 存储不友好:UUID 有 16 字节(128 位)

  • 信息安全问题:基于 MAC 地址生成的 UUID 算法,可能泄露 MAC 地址

  • ID 无业务含义,可读性差


Java版:UUID.randomUUID().toString()36个字符,如a3fce3e1-c495-4893-8845-e4e376dbf5ad


不建议 UUID 做数据库主键:

  • 整体上 UUID 生成的 ID 可以看作是随机,插入时可能会导致 B+树索引的分裂;非递增 ID 作为索引也不利于顺序读

  • MySQL 官方建议主键要尽量越短越好,UUID 有 128 位。

方案 2:数据库自增主键

单机模式:使用数据库的 ID 自增策略,简单易用;数据库生成的 ID 绝对有序。如 MySQL 的 auto_increment。

  • 无法扛高并发场景,存在单点问题

  • ID 无业务含义,但还是可能会有安全问题(数据量等推算)


针对单机性能问题,可以做数据库多主模式。每台机器,基于序列的起始值和步长设置不同的初始值和相同的步长(步长大于节点数)

  • 系统扩容难(要调整步长困难)

  • 数据库压力还是大(每次获取 ID 还是需要读写数据库)

方案 3:基于 Redis 生成

还可以基于 ZK、Mongodb 等中间件生成 Redis 是单线程,天生保证原子性,可以使用 INCR 和 INCRBY 自增原子命令来实现。

  • Redis 是基于内存,读写性能好。不过为了避免数据丢失,需要做持久化。

  • 机器故障,还是可能会生成重复的 ID

  • Redis Cluster:可以部署 Redis Cluster 提高可用性和并发。和 MySQL 一样需要设置不同的增长步数

方案 4:Snowflake 雪花算法

Snowflake 是 Twitter 开源的,目前相对被广泛使用。Snowflake 是一个 64 位的 Long 型整数:1 位标识符+ 41 位时间戳+ 10 位 workerID + 12 位序列号;转换为字符后长度为 18~19。

  • 标识符:一般用正数,固定为 0

  • 时间范围(毫秒级):241/(1000*60*60*24*365)=70 年

  • 工作机器数量:2 的 10 次方=1024,可以灵活设置 dataCenterId 和 machineId

  • 同一毫秒内可以生成不碰撞序列 ID 数:2 的 12 次方=4096。可以灵活增加/减少位数(依赖 workId 的实现)


优点:

  • 独立,性能好:不依赖数据库、redis 等第三方系统,稳定性高,生成 ID 的性能也高

  • 设计灵活:基于雪花算法思想,可以自由调整不同段的比特位,灵活设计合适的 ID 算法


可能存在的问题:

  • 依赖机器时钟,如果机器时钟偏移或回拨,会导致重复 ID 生成。可以考虑以下解决方式:

  • 抛异常处理:阻止 ID 生成

  • 重试:比较当前时间和上次生成 ID 的时间,如果小,说明发生了时间回拨,再次生成 ID(无法根治)

  • 关闭服务,摘除节点,告警人工处理

  • 序列号可预测,存在安全隐患

  • 单机单调递增,全局趋势递增(不过一般分布式 ID 只要求趋势递增)

  • 时间理论极限,约 70 年(一般都不会担心这个问题)

业界大厂方案

很多大厂都对雪花算法做出了改进,开源了一些改进方案,如百度 UIDGenerator 和美团 Leaf...Leaf 分别在 MySQL 和 Snowflake 基础上做了优化,实现 Leaf-segment 和 Leaf-snowflake。

Leaf-segment

思路:每次获取一个 ID 区间避免频繁访问数据库,区间段用完再去数据库获取新的号段

  • 核心字段:biz_tag 区分业务,max_ID 表示 biz_tag 目前被分配号段的最大值,step 表示号段长度(设置合理的值)

  • ID 是趋势递增的,扩展灵活,性能较好,可用性较好(比如 ID 生成服务不可用,业务短时间内还是可用)


存在的问题:

  • 依赖 DB,存在业务访问冲突,导致阻塞等待问题

  • ID 号是可预测的,不适用于订单 ID 生成等场景。


改进:采用双 Buffer segment,在当前号段消耗一定数量后,提前检查和准备另一个号段;这样当前号段用完后直接切换使用另一个号段,如此循环。

  • 基于内存存储双 Buffer segment,减少数据库查询和网络依赖,效率更高。有效解决业务访问冲突问题。


存在的问题:号段长度是固定的,长度设置短的话,业务量大还是会触发频繁更新;长度设置过长,不同节点的号段跨度会较大。(动态调整步长)


通常推荐 segment 长度设置为服务高峰期发号 QPS 的 600 倍(10 分钟),这样即使 DB 宕机,Leaf 仍能持续发号 10-20 分钟不受影响。

Leaf-snowflake

基于 snowflake 方案,利用 ZK 的持久化顺序节点动态调整 workerId 的位数。同时会在本地缓存 workerId,避免强依赖 ZK。

ID 生成器高性能设计思路

  • 批量取:每次从生成器拿走一批;可能破坏递增趋势。

  • 提前取:和批量取结合使用,即提前批量取,能够提高业务方的性能,也可能破坏递增趋势。同时也要考虑兜底措施,比如用完了,还没获取到新一批,业务需要等待。

  • 局部存取:可以存储在线程 TLB(thread-local-buffer)里,以后该线程需要 ID 时,直接从 TLB 里面获取,减少全局竞争。


在分布式系统中,由于存在多个节点和并发操作的情况,需要确保在某个时刻只有一个节点或进程能够访问共享资源,以避免数据冲突和不一致的问题。分布式锁是在分布式系统中对共享资源的并发访问进行控制的一种机制。一般来说,一个分布式锁服务,正确性要求越高,性能可能就会越低。

分布式锁

对比进程锁、线程锁常见分布式锁设计实现,需要考虑以下特性:

  • 互斥:不同线程、进程互斥

  • 正确性,避免死锁:例如获取锁的客户端未能释放锁,其他客户端再无法获取该锁。

  • 引入过期时间:会有释放别人的锁、业务未处理完成锁就过期问题

  • 锁唯一性:解决释放别人的锁问题

  • 自动续期:解决业务未处理完成锁就过期问题,使用守护进程检测失效时间进行续租(如 Redisson)

  • 容错:当部分节点宕机时,客户端仍然能够获取锁和释放锁

  • 自动故障转移,比如 etcd、zk

  • 可重入:同一个线程在持有锁的情况下,可以多次获取该锁而不会造成死锁

  • 完善的锁接口:阻塞的和非阻塞的,比如 lock、tryLock

  • 公平:锁唤醒时,按照顺序唤醒


一个严谨的分布式锁模型应该考虑锁租期、锁归属、副本同步、NPC 问题。

分布式锁整体对比

  • 数据库:实现简单、易于理解;但对数据库压力大。生产几乎不使用。

  • Redis:易于理解;自行实现需要考虑各种情况,存在可靠性问题。适合高并发场景,对于数据敏感的业务场景,要做兜底方案

  • Redisson:提供各种锁的方法,开发友好,支持阻塞

  • Zookeeper:支持阻塞;实现逻辑较复杂;适用于高可靠,而并发量不是太高的场景

  • ZK 客户端 Curator:提供锁的方法;强一致,对性能有一定影响

  • Etcd:安全和可靠性上有保证;一般不会单独引入 etcd 实现分布式锁,这样会使得系统架构较复杂


按实现方式,以上方案可以归为 2 类:

  • 自璇:客户端未获得锁时,进入一个循环,不断尝试获锁,直到成功或者超时。比如基于数据库和基于 redis 的实现

  • watch 监听:客户端监听某个 key,锁可用时通知客户端。比如基于 ZK 和 etcd 的实现


无论是基于 Redis、Zookeeper 还是 Etcd,分布式锁不是 100%安全,还是有产生并发冲突的可能性。不建议自己实现分布式锁,可以选择 Redisson 或 Curator,使用较方便。

基于数据库的分布式锁

所有锁请求者需要连接同一个数据库

  • 悲观锁:利用唯一索引约束,比如创建一个表,表中包含方法名等字段,并在方法名字段上创建唯一索引,想要执行某个方法,就使用这个方法名向表中插入一条记录,成功插入则获取锁,删除对应的行就是锁释放。

  • 乐观锁:加 version 字段,利用 CAS 实现,可能导致大量的 update 失败。


会出现的问题:

  • 非阻塞,锁获取失败没有排队机制

  • 不可重入,可以通过使用记录线程标识解决

  • 死锁,可以设置超时时间、定时任务检查

  • 高并发下数据库读写是非常缓慢,数据库存在单点故障

  • 不适合在实际的生产环境使用

基于 Redis 的分布式锁

Redis 单实例

最简单的分布式锁:setnx 加锁,del 解锁setnx: set if not exists,是原子操作


但在高并发下,会存在各种问题:

  • 死锁:进程挂了,没及时释放锁,导致锁永远不释放

  • 给锁设置过期时间,setnx + expire,这不是原子操作,还是可能会导致死锁;改为原子操作,比如:SET myKey myValue NX PX 3000

  • 使用 getset,思想如下setnx失败 lockVal = get(myKey)culVal = getset(myKey, newVal) culVal == lockVal ? 获取锁成功:获取锁失败

  • 锁提前过期,业务还没执行完成:使用守护进程检测失效时间进行自动续期

  • Redisson 提供锁续期、可重入等实现

  • 锁被别人释放了:加锁需要具有唯一性

  • 获取锁的值,和自己锁的值判断,相同才能删除(get、判断、del 需要保持原子性,可以使用 lua 脚本)


一个较严谨的流程如下

  • 加锁:SET  lockKey $uniqueID EX $expireTime NX

  • 访问共享资源,处理业务:没执行完之前,开启守护线程,定期给锁续期

  • 释放锁:Lua 脚本,先 GET 判断锁是否属于自己,再 DEL 释放锁


Redis 实现分布式锁可重入:需要借助 Redis 的 Lua 脚本语言和计数器计数,保证同一线程可重入锁的原子性和正确性。

Redis Cluster

主从架构场景下,会出现重复加锁问题:锁先加在一个 master 节点上,再异步同步到 slave 节点。master 挂了会选择 slave 为 master,此时若同步没有完成,就会出现重复加锁问题。ZK 是 CP 的,不存在这样的问题。


Redis 的作者提出一种解决方案,就是 Redlock,基于多个 Master Redis 节点的一种实现。这个方案有 2 个前提:

  • 只部署主库,不需要部署从库和哨兵实例

  • 主库要部署多个,官方推荐至少 5 个实例,这会导致加锁时间变长


Redlock 加锁流程:

  • Client 先获取「当前时间戳 T1」

  • Client 依次向「全部节点」发起加锁请求

  • 每个请求会设置超时时间(毫秒级,要远小于锁的有效时间)

  • 如果某一个实例加锁失败,就立即向下一个 Redis 实例请求加锁

  • 如果 Client 从大多数 Redis 实例加锁成功

  • 再次获取「当前时间戳 T2」

  • 如果 T2 - T1 < 锁的过期时间(加锁的总耗时要小于锁的过期时间),认为客户端加锁成功,去操作共享资源

  • 否则认为加锁失败,Client 向「全部节点」发起释放锁请求


RedLock 方案也存在以下情况导致重复加锁:

  • 持久化:机器故障未能及时落盘

  • 时钟跳跃:某个节点发生时钟跳跃,导致加上的锁没有到达实际的超时时间,被误以为超时而释放了

基于 ZK 的分布式锁

Zookeeper 是一个分布式协调系统,被广泛应用于分布式系统的注册中心、配置管理、命名服务、分布式锁、集群管理等场景。ZK 采用 CP 工作模式,注重强一致性,当集群数据不一致时,可能会导致集群不可用。


加锁过程:

  • Client1 客户端尝试创建一个临时 znode 节点,比如/lock,创建成功,相当于拿到锁

  • 其它的客户端会创建失败,获取锁失败(因为 znode 已存在)

  • 等待、监听/lock 节点

  • Client1 完成共享资源访问后,删掉 znode,锁就释放了

  • 其他客户端继续尝试获取锁操作,重复以上步骤


以上方案存在羊群/惊群效应问题,当 Client1 释放锁时,ZK 通过 watch 机制通知所有监听的客户端,但是只有一个客户端能获取到锁。

  • 解决方式:当获取锁失败时,只对前一个节点添加监听器。这样获取锁的客户端释放锁后,只需要通知后一个节点。


ZK 分布式锁的优点:

  • 不需要考虑过期时间,通过临时节点实现

  • Client 拿到锁之后,只要和 ZK 的连接不断,就会一直持有锁。如果 Client 崩溃,ZK 会自动删除对应的临时节点,保证锁释放;使用起来比较方便

  • 每个客户端都与 ZK 维护一个 session,这个 session 依赖定期的心跳来维持

  • watch 机制:加锁失败,可以设置监听事件,等待锁释放


缺点:

  • 不适合高并发场景(性能整体可能不如 Redis)

  • ZK 在创建锁和释放锁的过程,都要动态创建、销毁临时节点

  • 写操作只能通过 Leader 节点执行,再同步到所有 Follower 节点上

  • 锁被误释放:客户端长时间不向 ZK 发送心跳(如 GC STW 过长),ZK 认为客户端崩溃,删除临时节点,锁被释放(客户端认为自己还持有锁)

  • ZK 有多种重试策略,检测不到客户端的心跳,多次重试之后,才会删除临时节点

基于 Etcd 的分布式锁

etcd 是一个 Go 语言实现的可靠的 kv 存储系统,可以用来实现配置中心、服务注册发现、分布式锁等功能。


加锁过程:

  • Client1 创建一个 lease 租约,设置过期时间

  • Client1 携带这个租约,创建/lock 节点

  • 创建成功,则 Client1 拿锁成功

  • Client2 以同样方式创建节点,节点已存在,拿锁失败

  • Client1 操作共享资源

  • Client1 定时给这个租约「续期」,保持自己一直持有锁

  • Client1 删除/lock 节点,释放锁


etcd 实现分布式锁的原理有点类似 ZK,也能避免“惊群效应”问题,但 etcd 使用 Lease 租约机制来实现锁自动释放和续约能力。通过集群模式实现服务的高可用。


参考资料:

https://mp.weixin.qq.com/s/O8o31rRBVL1DwK-JfmurRw

https://mp.weixin.qq.com/s/JzCHpIOiFVmBoAko58ZuGw


下期预告:《分布式技术》分布式事务



发布于: 刚刚阅读数: 5
用户头像

L L

关注

未来不足惧过往不须泣,只有时间才最懂人心 2023-09-12 加入

Java技术栈/办公效能、学习思维、生活旅行分享。致力成为“写作中攻城狮高手,攻城狮中写作高手”。 欢迎关注公众号:过去那点事儿

评论

发布
暂无评论
【分布式技术】分布式锁和ID_分布式技术_L L_InfoQ写作社区