Distributed locks

分布式🔒
ZooKeeper版本（欢迎Redis版本或其它版本）。当然又是浅谈版。

题目来源于一道🐶🐶面试题。题干好像很简单就是实现分布式锁。这里虽然很大程度上依赖ZooKeeper但是把ZooKepper的行为转化为你在面试里需要实现的功能，应该会是个更加完整的答案。

ZooKeeper是分布式计算的一个重要组成部分，high availability, 解决分布式metadata的管理。得益于，并和🐶🐶的Chubby有很多类似点。

在ZooKeeper里数据以类似文件目录结构的N-ary树来存储。每个存储数据的节点叫做ZNode。节点可以存储数据（不适宜太长的数据）。每个ZNode可以又children ZNode。（除了Ephemerals cannot have children）。举个例子

[Bash shell] 纯文本查看 复制代码

?

/   abc/   def0/   my/     ver/       test/

比如/my/ver/test 的数据有这些：

[Bash shell] 纯文本查看 复制代码

?

test value string 【这就是该节点的数据】 cZxid = 0x1f ctime = Sun Mar 17 00:04:11 UTC 2019 mZxid = 0x38 mtime = Sun Mar 17 00:32:06 UTC 2019 pZxid = 0x36 cversion = 8 dataVersion = 2 aclVersion = 0 ephemeralOwner = 0x0 dataLength = 17 numChildren = 0

在ZooKeeper里，有三种nodes的属性：

• persistent
• sequential
• euphemeral （和persistent互斥）临时节点。连线后有个sessionid。掉线超过给定时间后ZooKeeper就会删除所有跟该sessionid的临时节点。再次连接进来如果原sessionid已经过期则会有新的sessionid。

这三种属性通过combination又会产生下面的组合：

• persistent
• sequential & persistent
• sequential & euphemeral
• euphemeral

每个Znode上可以加watch，当节点发生变化的时候，a watch event is one-time trigger, sent to the client that set the watch, which occurs when the data for which the watch was set changes

ZooKeeper有很多官方推荐的Recipes。其中之一便是分布式锁。我的学习只要来源于 https://zookeeper.apache.org/doc ... ml#sc_recipes_Locks

• Call create( ) with a pathname of "_locknode_/lock-" and the sequence and ephemeral flags set.
• Call getChildren( ) on the lock node without setting the watch flag (this is important to avoid the herd effect).
• If the pathname created in step 1 has the lowest sequence number suffix, the client has the lock and the client exits the protocol.
• The client calls exists( ) with the watch flag set on the path in the lock directory with the next lowest sequence number 【注一。这是坑爹的描述】
• if exists( ) returns false, go to step 2. Otherwise, wait for a notification for the pathname from the previous step before going to step 2.

注一，坑爹的部分在于lowest sequence number是对全局lowest sequence number来说，还是对于自家The client的sequence number来说。应为后者。如果你理解为前者（后来查阅了官方代码才搞清楚），那么就会陷入herd effect的陷阱。
我们按照上面的顺序走一遍。前提条件是/locknode这个ZNode已经产生了。
一、locknode下面没有任何子Znode。那么ZooKeeeper产生/locknode/lock-0000000000，这个0000000000是ZooKeeper自动产生的严格升序。并且告诉你。你记住了你的号是0
二、getChildren就只得到一个孩子：/locknode/lock-0000000000
三、你的号是0，且最小的孩子是0，所以你拥有lock，你不用排队，走了。这时lock-0000000000仍然在那里。

另外一个人来排队了。
一、locknode下面有1个Znode，且最大的号是0。那么ZooKeeeper产生/locknode/lock-0000000001，这个0000000001是ZooKeeper自动产生的严格升序。并且告诉你。你记住了你的号是1
二、getChildren就得到两个孩子：/locknode/lock-0000000000 和 /locknode/lock-0000000001
三、你的号是1，且当前lock是0，你还在队伍里
四、你知道你前面那个人的号是0。你决定，如果0有什么变化请通知我。五、如果你前面的人走了、或者前面的人掉线时间过长，你会得到ZooKeeper的call，告诉你你watch的发生了变化，你回到并执行第二点。不出意外的话你会得到lock。

什么叫herd effect？如果每个没有得到lock的client都去关注（watch）队伍的头部是不是变化了，那么除了等待队伍里的第一名排队者以外，其他人都是在做重复的无用功。所以更好的设计就是该recipe里写的，每个人只关心你前面的那位是不是有变化。要么你前面的人掉线或者网络坏、不排队走了、这样你就关心更前面的那位，要么是你前面的人拿到lock而且用完了release了，走了，这样你就拿到了lock。
另外一个改进的地方是，即便你认为你拿到了锁。由于网络的延迟或其它G1GC等原因，还有个mid-air collision的问题。可以考虑用ZNode 的 cversion （在上面的例子里 /my/ver/test 的 cversion=8)。任何它（直接）下面的节点变化都会导致这个cversion 数值增加。可以使用这个值来检测是否出现mid-air collision。如果ZooKeeper认为你已经掉线并且踢掉了你的lock。下一个人已经先于你进行了修改，并且留下它的cversion的记录。那么你后拿着更小的cversion去修改就应该能够发现你已经out了。应该果断中断你的修改。
在分布计算中，有很多关于只让一个进程写，只让一个进程做leader，consensus。这种问题必然会用到分布锁。

你们的教材是如何介绍分布锁的应用的？
https://mp.weixin.qq.com/s/pnPxgljnohU746TTVzUt3g
3Mysql分布式锁

mysqlLock.lcok内部是一个sql,为了达到可重入锁的效果那么我们应该先进行查询，如果有值，那么需要比较node_info是否一致，这里的node_info可以用机器IP和线程名字来表示，如果一致那么就加可重入锁count的值，如果不一致那么就返回false。如果没有值那么直接插入一条数据

我们有可能会遇到我们的机器节点挂了，那么这个锁就不会得到释放，我们可以启动一个定时任务，通过计算一般我们处理任务的一般的时间，比如是5ms，那么我们可以稍微扩大一点，当这个锁超过20ms没有被释放我们就可以认定是节点挂了然后将其直接释放。

• 适用场景: Mysql分布式锁一般适用于资源不存在数据库，如果数据库存在比如订单，那么可以直接对这条数据加行锁，不需要我们上面多的繁琐的步骤，比如一个订单，那么我们可以用select * from order_table where id = 'xxx' for update进行加行锁，那么其他的事务就不能对其进行修改。
• 优点:理解起来简单，不需要维护额外的第三方中间件(比如Redis,Zk)。
• 缺点:虽然容易理解但是实现起来较为繁琐，需要自己考虑锁超时，加事务等等。性能局限于数据库，一般对比缓存来说性能较低。对于高并发的场景并不是很适合。

前面我们介绍的都是悲观锁，这里想额外提一下乐观锁，在我们实际项目中也是经常实现乐观锁，因为我们加行锁的性能消耗比较大，通常我们会对于一些竞争不是那么激烈，但是其又需要保证我们并发的顺序执行使用乐观锁进行处理，我们可以对我们的表加一个版本号字段，那么我们查询出来一个版本号之后，update或者delete的时候需要依赖我们查询出来的版本号，判断当前数据库和查询出来的版本号是否相等，如果相等那么就可以执行，如果不等那么就不能执行。这样的一个策略很像我们的CAS(Compare And Swap),比较并交换是一个原子操作。这样我们就能避免加select * for update行锁的开销。

Zk的数据节点和文件目录类似，所以我们可以用此特性实现分布式锁。我们以某个资源为目录，然后这个目录下面的节点就是我们需要获取锁的客户端，未获取到锁的客户端注册需要注册Watcher到上一个客户端，可以用下图表示。

Zookeeper不需要配置锁超时，由于我们设置节点是临时节点，我们的每个机器维护着一个ZK的session，通过这个session，ZK可以判断机器是否宕机。如果我们的机器挂掉的话，那么这个临时节点对应的就会被删除，所以我们不需要关心锁超时。

• 优点:ZK可以不需要关心锁超时时间，实现起来有现成的第三方包，比较方便，并且支持读写锁，ZK获取锁会按照加锁的顺序，所以其是公平锁。对于高可用利用ZK集群进行保证。
• 缺点:ZK需要额外维护，增加维护成本，性能和Mysql相差不大，依然比较差。并且需要开发人员了解ZK是什么。

熟悉Redis的同学那么肯定对setNx(set if not exist)方法不陌生，如果不存在则更新，其可以很好的用来实现我们的分布式锁。对于某个资源加锁我们只需要

setNx resourceName value

这里有个问题，加锁了之后如果机器宕机那么这个锁就不会得到释放所以会加入过期时间，加入过期时间需要和setNx同一个原子操作，在Redis2.8之前我们需要使用Lua脚本达到我们的目的，但是redis2.8之后redis支持nx和ex操作是同一原子操作。

set resourceName value ex 5 nx






Javaer都知道Jedis，Jedis是Redis的Java实现的客户端，其API提供了比较全面的Redis命令的支持。Redission也是Redis的客户端，相比于Jedis功能简单。Jedis简单使用阻塞的I/O和redis交互，Redission通过Netty支持非阻塞I/O。Jedis最新版本2.9.0是2016年的快3年了没有更新，而Redission最新版本是2018.10月更新。








CheckSequencer()：调用Chubby的API检查此时这个序列号是否有效。


访问资源服务器检查，判断当前资源服务器最新的序列号和我们的序列号的大小。


lock-delay:为了防止我们校验的逻辑入侵我们的资源服务器，其提供了一种方法当客户端失联的时候，并不会立即释放锁，而是在一定的时间内(默认1min)阻止其他客户端拿去这个锁，那么也就是给予了一定的buffer等待STW恢复，而我们的GC的STW时间如果比1min还长那么你应该检查你的程序，而不是怀疑你的分布式锁了。

http://redis.io/topics/distlock
- Why not just use Zookeeper?

Safety and Liveness guarantees

1. Safety property: Mutual exclusion. At any given moment, only one client can hold a lock.
2. Liveness property A: Deadlock free. Eventually it is always possible to acquire a lock, even if the client that locked a resource crashed or gets partitioned.
3. Liveness property B: Fault tolerance. As long as the majority of Redis nodes are up, clients are able to acquire and release locks.

Why failover-based implementations are not enough

The simplest way to use Redis to lock a resource is to create a key in an instance. The key is usually created with a limited time to live, using the Redis expires feature, so that eventually it will get released (property 2 in our list). When the client needs to release the resource, it deletes the key.

Superficially this works well, but there is a problem: this is a single point of failure in our architecture. What happens if the Redis master goes down? Well, let’s add a slave! And use it if the master is unavailable. This is unfortunately not viable. By doing so we can’t implement our safety property of mutual exclusion, because Redis replication is asynchronous.

There is an obvious race condition with this model:

1. Client A acquires the lock in the master.
2. The master crashes before the write to the key is transmitted to the slave.
3. The slave gets promoted to master.
4. Client B acquires the lock to the same resource A already holds a lock for. SAFETY VIOLATION!

Correct implementation with a single instance

http://www.cnblogs.com/it-cen/p/4440745.html

http://www.oschina.net/translate/redis-distlock

http://wh0426.iteye.com/blog/2212025