分布式🔒

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

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

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

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

1. 
   
2.   /
   
3.     abc/
   
4.     def0/
   
5.     my/
   
6.       ver/
   
7.         test/
   

复制代码

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

1. test value string 【这就是该节点的数据】
   
2. cZxid = 0x1f
   
3. ctime = Sun Mar 17 00:04:11 UTC 2019
   
4. mZxid = 0x38
   
5. mtime = Sun Mar 17 00:32:06 UTC 2019
   
6. pZxid = 0x36
   
7. cversion = 8
   
8. dataVersion = 2
   
9. aclVersion = 0
   
10. ephemeralOwner = 0x0
    
11. dataLength = 17
    
12. 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了。应该果断中断你的修改。

怎么找个分布式系统跑自己的程序？

Hmoon 发表于 2019-3-18 13:23
怎么找个分布式系统跑自己的程序？

好像这样的文章不少。取决于你想学习哪种分布式系统。我刚刚谷了一下，单机运行hadoop的文章2013发的，到2018年发的都有。资源很丰富的样子。

14417335 发表于 2019-3-18 22:44
好像这样的文章不少。取决于你想学习哪种分布式系统。我刚刚谷了一下，单机运行hadoop的文章2013发的，到 ...

我的单机跑过很多次spark,你的意思是单机模拟distributed system?

面试考Paxos？有点过分了吧
不过如果对Paxos这类分布式一致性协议的工程实现感兴趣的话，推荐这个文章：Paxos Made Live

上了一个学期的distributed system，还是不懂LZ这是在讲啥 :(

已收藏，谢谢啦，考的好细

biomedicineman 发表于 2019-3-19 13:13
上了一个学期的distributed system，还是不懂LZ这是在讲啥 :(

在分布计算中，有很多关于只让一个进程写，只让一个进程做leader，consensus。这种问题必然会用到分布锁。

你们的教材是如何介绍分布锁的应用的？

非常有用，谢谢楼主。

有幸用过zookeeper，当时只觉得它是管理cluster里面的node的，发现内部是类似Linux的那种系统，没想到还能用来实现分布式锁