电商课题：分布式锁

关键词：
并发控制
防止并发

英文关键词：
Distributed Lock
Distributed Lock Manager

电商目的：
保证整个（分布式）系统内对一个重要事物（订单，账户等）的有效操作线程，同一时间内有且只有一个。比如交易中心有N台服务器，订单中心有M台服务器，如何保证一个订单的同一笔支付处理，一个账户的同一笔充值操作是原子性的。

基于哪些服务实现分布式锁？

memcache
ZooKeeper
Redis
Hazelcast
google Chubby

基于memcache的分布式锁

memcache的所有命令都是原子性的（internally atomic），所以利用它的add命令即可。
郑昀列出一段简单但埋下了问题的伪码：

if (cache.add("lock:{orderid}", currenttimestamp, expiredtime)) {  
  // 已获得锁，继续
  try{do something}catch{...}
  cache.delete("lock.{orderid}")
} else { 
// 或等待锁超时，或重试，或返回
}

上面代码所暴露的常见性问题

1）如持有锁的线程异常退出或宕机，锁并没有释放；
2）设置了key的expire，那么如果有新线程在key过期后拿到了新的锁，原来超时的线程回来时，如果不经判断会误认为那是它持有的锁，会误删锁。

解决思路

1）强制释放
在键值上做文章，存入的是 current UNIX time+lock timeout+1 ，这样其他线程可以通过锁的键值对应的时间戳来判断这种情况是否发生了，如果当前的时间已经大于lock.{orderid}的键值，说明该锁已失效，可以被重新使用。
2）释放自己持有的锁时，先检查是否已超时
持有锁的线程在解锁之前应该再检查一次自己的锁是否已经超时，再去做DELETE操作，因为可能客户端因为某个耗时的操作而挂起，操作完的时候锁因为超时已经被别人获得，这时就不必解锁了。

继续解决

上面的办法会引入新问题：
如果多个线程检测到锁超时，都尝试去释放锁，那么就会出现竞态条件（race condition）。场景是，
1. C0操作超时了，但它还持有着锁，C1和C2读取lock.{orderid}检查时间戳，先后发现超时了。
2. C1 发送delete lock.{orderid}，
3. C1 发送set lock.{orderid} 且成功。
4. C2 发送delete lock.{orderid}，
5. C2 发送set lock.{orderid} 且成功。

这样，C1和C2都认为自己拿到了锁。
如果比较在意这种竞态条件，那么推荐使用基于zookeeper或redis的解决方案。

基于ZooKeeper的分布式锁

这主要得益于ZooKeeper为我们保证了数据的强一致性，即用户只要完全相信每时每刻，zk集群中任意节点（一个zk server）上的相同znode的数据一定是相同的。锁服务可以分为两类，一个是保持独占，另一个是控制时序。所谓保持独占，就是所有试图来获取这个锁的客户端，最终只有一个可以成功获得这把锁。通常的做法是把zk上的一个znode看作是一把锁，通过 create znode的方式来实现。所有客户端都去创建 /distributed_lock 节点，最终成功创建的那个客户端也就拥有了这把锁。

控制时序，就是所有试图获取这个锁的客户端，最终都是会被安排执行，只是有个全局时序。做法和上面基本类似，只是这里 /distributedlock 已经预先存在，客户端在它下面创建临时有序节点（这个可以通过节点的属性控制：CreateMode.EPHEMERALSEQUENTIAL来指定）。zk的父节点（/distributed_lock）维持一份sequence，保证子节点创建的时序性，从而形成了每个客户端的全局时序。

ZooKeeper 里实现分布式锁的基本逻辑：

客户端调用create()方法创建名为“locknode/guid-lock-”的节点，需要注意的是，这里节点的创建类型需要设置为EPHEMERAL_SEQUENTIAL。
客户端调用getChildren(“locknode”)方法来获取所有已经创建的子节点，同时在这个节点上注册上子节点变更通知的Watcher。
客户端获取到所有子节点path之后，如果发现自己在步骤1中创建的节点是所有节点中序号最小的，那么就认为这个客户端获得了锁。
如果在步骤3中发现自己并非是所有子节点中最小的，说明自己还没有获取到锁，就开始等待，直到下次子节点变更通知的时候，再进行子节点的获取，判断是否获取锁。

释放锁的过程相对比较简单，就是删除自己创建的那个子节点即可。

基于Redis的分布式锁

接着前面的竞态条件说，同样的场景下，使用Redis的SETNX（即SET if Not eXists，类似于memcache的add）和GETSET（先写新值，返回旧值，原子性操作，可以用于分辨是不是首次操作）命令便可迎刃而解：

C3发送SETNX lock.{orderid} 想要获得锁，由于C0还持有锁，所以Redis返回给C3一个0，
C3发送GET lock.{orderid} 以检查锁是否超时了，如果没超时，则等待或重试。
反之，如果已超时，C3通过下面的操作来尝试获得锁： GETSET lock.{orderid} <current Unix time + lock timeout + 1>
通过GETSET，C3拿到的时间戳如果仍然是超时的，那就说明，C3如愿以偿拿到锁了。
如果在C3之前，有个叫C4的客户端比C3快一步执行了上面的操作，那么C3拿到的时间戳是个未超时的值，这时，C3没有如期获得锁，需要再次等待或重试。留意一下，尽管C3没拿到锁，但它改写了C4设置的锁的超时值，不过这一点非常微小的误差带来的影响可以忽略不计。

jeffkit的伪码参考：

# get lock
lock = 0  
while lock != 1:  
    timestamp = current Unix time + lock timeout + 1
    lock = SETNX lock.orderid timestamp
    if lock == 1 or (now() > (GET lock.orderid) and now() > (GETSET lock.orderid timestamp)):
        break
    else:
        sleep(10ms)

do_your_job()

# release lock
if now() < GET lock.orderid:  
    DEL lock.orderid