创建一个锁目录 /lock；
当一个客户端需要获取锁时，在 /lock 下创建临时的且有序的子节点；
客户端获取 /lock 下的子节点列表，判断自己创建的子节点是否为当前子节点列表中序号最小的子节点，如果是则认为获得锁；否则监听自己的前一个子节点，获得子节点的变更通知后重复此步骤直至获得锁；
执行业务代码，完成后，删除对应的子节点。

5. 会话超时

如果一个已经获得锁的会话超时了，因为创建的是临时节点，所以该会话对应的临时节点会被删除，其它会话就可以获得锁了。可以看到，这种实现方式不会出现数据库的唯一索引实现方式释放锁失败的问题。

6. 羊群效应

一个节点未获得锁，只需要监听自己的前一个子节点，这是因为如果监听所有的子节点，那么任意一个子节点状态改变，其它所有子节点都会收到通知（羊群效应，一只羊动起来，其它羊也会一哄而上），而我们只希望它的后一个子节点收到通知。

分布式锁的几种实现方式

常见分布式锁一般有四种实现方式：

数据库锁；
基于ZooKeeper的分布式锁；
Chubby，类似ZooKeeper的分布式组件；
基于Redis的分布式锁。

数据库锁：这种方式很容易被想到，把竞争的资源放到数据库中，利用数据库锁来实现资源竞争，可以参考之前的文章《数据库事务和锁》。例如：（1）悲观锁实现：查询库存商品的sql可以加上 "FOR UPDATE" 以实现排他锁，并且将“查询库存”和“减库存”打包成一个事务 COMMIT，在A用户查询和购买完成之前，B用户的请求都会被阻塞住。（2）乐观锁实现：在库存表中加上版本号字段来控制。或者更简单的实现是，当每次购买完成后发现库存小于零了，回滚事务即可。 zookeeper的分布式锁：实现分布式锁，ZooKeeper是专业的。它类似于一个文件系统，通过多系统竞争文件系统上的文件资源，起到分布式锁的作用。具体的实现方式，请参考之前的文章《zookeeper的开发应用》。 Chubby：Google 公司实现的粗粒度分布式锁服务，有点类似于 ZooKeeper，但也存在很多差异。Chubby 通过 sequencer 机制解决了请求延迟造成的锁失效的问题。 redis的分布式锁：简单来说是通过setnx竞争键的值。

“数据库锁”是竞争表级资源或行级资源，“zookeeper锁”是竞争文件资源，“redis锁”是为了竞争键值资源。它们都是通过竞争程序外的共享资源，来实现分布式锁。

不过在分布式锁的领域，还是zookeeper更专业。redis本质上也是数据库，所有其它两种方案都是“兼职”实现分布式锁的，效果上没有zookeeper好。

性能消耗小：当真的出现并发锁竞争时，数据库或redis的实现基本都是通过阻塞，或不断重试获取锁，有一定的性能消耗。而zookeeper锁是通过注册监听器，当某个程序释放锁是，下一个程序监听到消息再获取锁。锁释放机制完善：如果是redis获取锁的那个客户端bug了或者挂了，那么只能等待超时时间之后才能释放锁；而zk的话，因为创建的是临时znode，只要客户端挂了，znode就没了，此时就自动释放锁。集群的强一致性：众所周知，zookeeper是典型实现了 CP 事务的案例，集群中永远由Leader节点来处理事务请求。而redis其实是实现 AP 事务的，如果master节点故障了，发生主从切换，此时就会有可能出现锁丢失的问题。

分布式锁设计原则

互斥性在任意时刻，只有一个客户端持有锁。
不死锁分布式锁本质上是一个基于租约（Lease）的租借锁，如果客户端获得锁后自身出现异常，锁能够在一段时间后自动释放，资源不会被锁死。
一致性硬件故障或网络异常等外部问题，以及慢查询、自身缺陷等内部因素都可能导致Redis发生高可用切换，replica提升为新的master。此时，如果业务对互斥性的要求非常高，锁需要在切换到新的master后保持原状态。

层次一：使用setnx命令，执行结束之后释放锁

redis.SetNX(ctx, key, "1")
defer redis.del(ctx, key)

可以解决互斥性的问题，但不能做到不死锁：如果抛出异常了，没有释放锁，导致锁一直无法释放。

层次二：添加过期时间

redis.SetNX(ctx, key, "1", expiration)
defer redis.del(ctx, key)

为了避免锁一直不释放的情况，添加一个过期时间。依旧存在问题：

如果expiration设置得太大，程序中途退出之后，锁迟迟无法释放
如果expiration设置得太小，程序还没执行完，锁就已经释放了

注意，这里不能写成两句话，因为两句话无法保证原子性。在Redis中，只有lua能够保证多条语句的原子性。

setnx(key,..)
expire(key,...)

层次三：释放锁的时候只能释放自己申请的锁

setnx的时候设置的value为全局唯一的ID，可以使用雪花算法、UUID等。
使用lua脚本保证SetNX与Expire的原子性，做到了不死锁。但是如果任务还没有执行完，别的线程获取到了锁，del操作会把别人获得的锁释放掉。所以需要保证释放锁的时候只能释放当前线程自己申请的锁。

redis.SetNX(ctx, key, randomValue, expiration)
defer redis.del(ctx, key, randomValue)

以下为与之配套的lua脚本

if redis.call("get",KEYS[1]) == ARGV[1] then
    return redis.call("del",KEYS[1])
else
    return 0
end

如果redis-v6包已经支持cad（compare and delete），因而lua脚本可以精简为以下代码 redis.cad(ctx, key, randomValue)

只删除当前线程/协程抢到的锁，避免在程序运行过慢锁过期时删除别的线程/协程的锁，能做到一定程度的一致性。

使用lua做到自锁自解。

if redis.call("get",KEYS[1]) == ARGV[1] then
    return redis.call("del",KEYS[1])
else
    return 0
end

当客户端发现在锁的租期内无法完成操作时，就需要延长锁的持有时间，进行续租（renew）。同解锁一样，客户端应该只能续租自己持有的锁。在Redis中可使用如下Lua脚本来实现续租：

if redis.call("get",KEYS[1]) == ARGV[1] then
    return redis.call("expire",KEYS[1], ARGV[2])
else
    return 0
end

func myFunc() (errCode *constant.ErrorCode) {
    errCode := DistributedLock(ctx, key, randomValue, LockTime)
    defer DelDistributedLock(ctx, key, randomValue)
    if errCode != nil {
        return errCode
    }
    // doSomeThing
}

// 注意，以下代码还不能用cas优化，因为公司的redis-v6还不支持oldvalue是nil
func DistributedLock(ctx context.Context, key, value string, expiration time.Duration) (errCode *constant.ErrorCode) {

    ok, err := redis.SetNX(ctx, key, value, expiration)
    if err == nil {
        if !ok {
            return constant.ERR_MISSION_GOT_LOCK
        }
        return nil
    }

    // 应对超时且成功场景，先get一下看看情况
    time.Sleep(DistributedRetryTime)
    v, err := redis.Get(ctx, key)
    if err != nil {
        return constant.ERR_CACHE
    }
  if v == value {
  // 说明超时且成功
      return nil
  } else if v != "" {
    // 说明被别人抢了
    return constant.ERR_MISSION_GOT_LOCK
  }
  
  // 说明锁还没被别人抢，那就再抢一次
  ok, err = redis.SetNX(ctx, key, value, expiration)
  if err != nil {
    return constant.ERR_CACHE
  }
  if !ok {
      return constant.ERR_MISSION_GOT_LOCK
  }
      return nil
  }
  


func DelDistributedLock(ctx context.Context, key, value string) (errCode *constant.ErrorCode) {
	// redis.cad(ctx, key, randomValue)
    v, err := redis.Cad(ctx, key, value)
    if err != nil {
        return constant.ERR_CACHE
    }
	return nil
}

解决超时且成功的问题，写入超时且成功是偶现的、灾难性的经典问题。还存在的问题是： 1）单点问题，单master有问题，如果有主从，那主从复制过程有问题时，也存在问题 2）锁过期然后没完成流程怎么办

层次四：续租保证任务执行过程中一直持有锁

启动定时器，在锁过期却没完成流程时续租，只能续租当前线程/协程抢占的锁

// 以下为续租的lua脚本，实现CAS（compare and set）
if redis.call("get",KEYS[1]) == ARGV[1] then
  return redis.call("expire",KEYS[1], ARGV[2])
else
  return 0
end

// 在字节跳动，公司的redis-v6包已经支持cas，因而lua脚本可以精简为以下代码
redis.Cas(ctx, key, value, value)

能保障锁过期的一致性，但是解决不了单点问题同时，可以发散思考一下，如果续租的方法失败怎么办？我们如何解决“为了保证高可用而使用的高可用方法的高可用问题”这种套娃问题？
开源类库Redisson使用了看门狗的方式一定程度上解决了锁续租的问题，Redission执行流程如下：（只要线程一加锁成功，就会启动一个watch dog看门狗，它是一个后台线程，会每隔10秒检查一下（锁续命周期就是设置的超时时间的三分之一），如果线程还持有锁，就会不断的延长锁key的生存时间。因此，Redis就是使用Redisson解决了锁过期释放，业务没执行完问题。当业务执行完，释放锁后，再关闭守护线程。

但是这里，个人建议不要做锁续租，更简洁优雅的方式是延长过期时间，由于我们分布式锁锁住代码块的最大执行时长是可控的（依赖于RPC、DB、中间件等调用都设定超时时间），因而我们可以把超时时间设得大于最大执行时长即可简洁优雅地保障锁过期的一致性

层次五：Redis集群模式下的的分布式锁

如果线程一在Redis的master节点上拿到了锁，但是加锁的key还没同步到slave节点。恰好这时，master节点发生故障，一个slave节点就会升级为master节点。线程二就可以获取同个key的锁啦，这就出现线程A还没执行完，线程B又来执行了，就会有并发安全问题。
Redis的主从同步（replication）是异步进行的，如果向master发送请求修改了数据后master突然出现异常，发生高可用切换，缓冲区的数据可能无法同步到新的master（原replica）上，导致数据不一致。如果丢失的数据跟分布式锁有关，则会导致锁的机制出现问题，从而引起业务异常。针对这个问题介绍两种解法：

使用红锁（RedLock）红锁是Redis作者提出的一致性解决方案。红锁的本质是一个概率问题：如果一个主从架构的Redis在高可用切换期间丢失锁的概率是k，那么相互独立的N个Redis同时丢失锁的概率是多少？如果用红锁来实现分布式锁，那么丢锁的概率是k^N。鉴于Redis极高的稳定性，此时的概率已经完全能满足产品的需求。
- 红锁的问题在于：
  - 加锁和解锁的延迟较大。
  - 难以在集群版或者标准版（主从架构）的Redis实例中实现。
  - 占用的资源过多，为了实现红锁，需要创建多个互不相关的云Redis实例或者自建Redis。
使用WAIT命令。Redis的WAIT命令会阻塞当前客户端，直到这条命令之前的所有写入命令都成功从master同步到指定数量的replica，命令中可以设置单位为毫秒的等待超时时间。客户端在加锁后会等待数据成功同步到replica才继续进行其它操作。执行WAIT命令后如果返回结果是1则表示同步成功，无需担心数据不一致。相比红锁，这种实现方法极大地降低了成本。
- 需要注意的是：
  - WAIT只会阻塞发送它的客户端，不影响其它客户端。
  - WAIT返回正确的值表示设置的锁成功同步到了replica，但如果在正常返回前发生高可用切换，数据还是可能丢失，此时WAIT只能用来提示同步可能失败，无法保证数据不丢失。您可以在WAIT返回异常值后重新加锁或者进行数据校验。
  - 解锁不一定需要使用WAIT，因为锁只要存在就能保持互斥，延迟删除不会导致逻辑问题。

Redis分布式模式下的同步问题

Redis分布式锁在集群模式下实现存在一些局限性，当主从替换时难以保证一致性。

在redis sentinel集群中，我们具有多台redis，他们之间有着主从的关系，例如一主二从。我们的set命令对应的数据写到主库，然后同步到从库。当我们申请一个锁的时候，对应就是一条命令 setnx mykey myvalue ，在redis sentinel集群中，这条命令先是落到了主库。假设这时主库down了，而这条数据还没来得及同步到从库，sentinel将从库中的一台选举为主库了。这时，我们的新主库中并没有mykey这条数据，若此时另外一个client执行 setnx mykey hisvalue , 也会成功，即也能得到锁。这就意味着，此时有两个client获得了锁。这不是我们希望看到的，虽然这个情况发生的记录很小，只会在主从failover的时候才会发生，大多数情况下、大多数系统都可以容忍，但不是所有的系统都能容忍这种瑕疵。

解决

为了解决故障转移情况下的缺陷，Antirez 发明了 Redlock 算法。使用redlock算法，需要多个redis实例，加锁的时候，它会向多半节点发送 setex mykey myvalue 命令，只要过半节点成功了，那么就算加锁成功了。这和zookeeper的实现方案非常类似，zookeeper集群的leader广播命令时，要求其中必须有过半的follower向leader反馈ACK才生效。

在实际工作中使用的时候，我们可以选择已有的开源实现，python有redlock-py，java 中有 Redisson redlock。

redlock确实解决了上面所说的“不靠谱的情况”。但是，它解决问题的同时，也带来了代价。你需要多个redis实例，你需要引入新的库代码也得调整，性能上也会有损。所以，果然是不存在“完美的解决方案”，我们更需要的是能够根据实际的情况和条件把问题解决了就好。

基于 Redis 多机实现的分布式锁 Redlock

以上几种基于 Redis 单机实现的分布式锁其实都存在一个问题，就是加锁时只作用在一个 Redis 节点上，即使 Redis 通过 Sentinel 保证了高可用，但由于 Redis 的复制是异步的，Master 节点获取到锁后在未完成数据同步的情况下发生故障转移，此时其他客户端上的线程依然可以获取到锁，因此会丧失锁的安全性。整个过程如下：

客户端 A 从 Master 节点获取锁。
Master 节点出现故障，主从复制过程中，锁对应的 key 没有同步到 Slave 节点。
Slave 升级为 Master 节点，但此时的 Master 中没有锁数据。
客户端 B 请求新的 Master 节点，并获取到了对应同一个资源的锁。
出现多个客户端同时持有同一个资源的锁，不满足锁的互斥性。

正因为如此，在 Redis 的分布式环境中，Redis 的作者 antirez 提供了 RedLock 的算法来实现一个分布式锁，该算法大概是这样的：假设有 N（N>=5）个 Redis 节点，这些节点完全互相独立，不存在主从复制或者其他集群协调机制，确保在这 N 个节点上使用与在 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 Lua 脚本）。

释放锁的过程相对比较简单：客户端向所有 Redis 节点发起释放锁的操作，包括加锁失败的节点，也需要执行释放锁的操作，antirez 在算法描述中特别强调这一点，这是为什么呢？原因是可能存在某个节点加锁成功后返回客户端的响应包丢失了，这种情况在异步通信模型中是有可能发生的：客户端向服务器通信是正常的，但反方向却是有问题的。虽然对客户端而言，由于响应超时导致加锁失败，但是对 Redis 节点而言，SET 指令执行成功，意味着加锁成功。因此，释放锁的时候，客户端也应该对当时获取锁失败的那些 Redis 节点同样发起请求。

除此之外，为了避免 Redis 节点发生崩溃重启后造成锁丢失，从而影响锁的安全性，antirez 还提出了延时重启的概念，即一个节点崩溃后不要立即重启，而是等待一段时间后再进行重启，这段时间应该大于锁的有效时间。

关于 Redlock 的更深层次的学习，感兴趣的朋友可以查阅下官方文档，https://redis.io/topics/distlock

基于Redis如何实现可重入锁？

可重入锁的释放如何操作？

面试

锁的粒度

一、分布式锁

数据库的唯一索引

Redis 的 SETNX 指令

Redis 的 RedLock 算法

Zookeeper 的有序节点

1. Zookeeper 抽象模型

2. 节点类型

3. 监听器

4. 分布式锁实现