聊聊分布式锁
对于程序员来说，锁是一种非常好用的、解决资源共享时的冲突的抽象。
我们平时在写代码的时候会用到各种锁，尤其是用JAVA或C#这种机制比较丰富的语言，一言不合就synchronized或者lock。
关于锁的一些其他话题，比如什么锁资源而不是锁逻辑，什么时候spinlock什么时候mutex，老司机们已经很清楚了，小说君不再赘述。
不过，为了不影响下文阅读，小说君还是要简单介绍下悲观锁和乐观锁的概念。
悲观锁，更倾向于自己的修改会跟别的修改发生冲突，因此需要拿到锁再修改共享资源，就是我们常见的大部分锁。
乐观锁，与悲观锁相反，更倾向于自己的修改不会跟被的修改发生冲突，因此可以在完成操作、修改状态前做下check，如果发现别人在自己修改的过程中修改了，就重新来过。
两种锁的实现方式都很简单，应用情景也很显然，悲观锁更适合写密集的情景；而乐观锁，通常需要借助CAS实现，形成一定程度上比较简单的「无锁」结构，更适合读密集的情景。
接下来聊聊分布式的一些话题。
先谈一下情景。
我们仍然以服务为划分单位，假设有服务A和服务B，以及共享状态C。
某个client由于一些原因，同时向服务A和服务B发送了请求a和请求b。
服务A处理请求a时依赖共享状态C的子集Ca，处理完修改共享状态。
服务B处理请求b时依赖共享状态C的子集Cb，处理完修改共享状态。
如果Ca与Cb有交集，这时共享状态的正确性就没办法保证。确保正确性，是最典型的需要做「同步」的情景。
在做更深入的讨论之前，我们先确定一下讨论范围：
首先，「服务A与服务B同属一个进程/物理机」这种特殊情况的处理方式下文不再讨论，我们接下来只考虑服务A与服务B物理分布式部署的情况。
其次，我们先考虑共享状态由单一实例维护的情况。
与单机的此类问题类似，解决此类问题的比较直观的思路，就是引入分布式环境中的锁。
分布式锁实际上是一种比较笼统的概念，考虑一下，我们平时说到「锁」，会自然而然地想到语言runtime甚至操作系统提供的mutex机制，但是说到「分布式锁」，并没有唯一的、普适的一种解决方案。
分布式锁更多地描述的是一种建模问题的「模型」，分布式环境下，本没有「锁」的概念，我们只不过是借助单机时的锁模型，解决一些比较简单的分布式一致性问题。
用分布式锁建模问题是最简单的方式，理解简单，实现起来更简单。对于更复杂的情况，那就只能去找「分布式事务」，或者更完善的解决分布式一致性的基础设施（比如zookeeper，比如etcd）解决问题了。
实现分布式锁的第一反应，就是照搬一套单机环境最常用的悲观锁。也就是如果要进行修改操作，就需要在读依赖数据的时候就都加上锁，最后写成功的时候释放锁。获得锁所有权期间其他服务的任意读写请求都是非法的。
具体实现往往是借助一些强一致性的数据库设施，比如mysql。游戏圈的服务端比较喜欢这种方案，毕竟游戏服务端也并不需要提供什么可用性保证，节点挂掉往往就没办法fail over了。
把之前的问题抽象一下，换一种描述：
服务A和服务B（下面称为Proposer）处理client的请求a和请求b的时候都依赖资源R。
Proposer接到请求后，都需要先向某个中间人（下面称为Acceptor）请求资源R的互斥访问权Mr，请求成功，才能进行后续处理，否则阻塞。
Proposer处理完请求，修改状态，最后释放Mr。
对于Proposer来说，就是三个API：
Prepare，用来获取互斥访问权，参数是资源名称，返回值表示成功或失败。
Accept，用来修改状态。
Release，用来释放互斥访问权。
但是，如之前所说，分布式不比单机多线程执行环境，没有语言或平台做自动锁释放的保证。获取悲观锁的服务节点不能保证一定会将锁释放掉——拿到锁之后节点挂掉的可能性非常大。
这样，就需要给这种锁实现增加一种超时机制，换句话说，互斥访问权是可抢占的。
有趣的是，如此一来，悲观锁总是会变成乐观锁。因为互斥访问权是可抢占的，所以在Acceptor在接收Accept时总是会检查Proposer的互斥访问权是否还合法，不合法的话Proposer需要重新申请互斥访问权——与文章最开始提到的乐观锁机制类似。
如何实现可抢占的互斥访问权？
跟单机环境的乐观锁实现类似，一种方案是基于时间戳的，一种方案是基于版本号的。
由于我们已经将问题简化为单实例维护共享状态，那两种方案其实没太大区别，无非就是看需求是「先到先得」，还是「后到先得」。
我们先来看一种基于时间戳的，后到先得的方案。
Proposer向Acceptor申请访问权时需要指定epoch（可以理解为一种时间戳），获取到访问权之后，才能修改状态。
Acceptor一旦收到更大的新epoch的申请，马上让旧的访问权失效，给新的epoch访问权。
API修改如下：
Prepare，参数需要额外指定一个epoch。Acceptor处理时不再考虑小于等于记录的prepared_epoch的Proposer。
Accept，参数需要额外指定Proposer的经过Prepare API check的epoch。只有跟记录的prepared_epoch一致时，才会修改状态。
Release不再需要。
说完抽象的内容，接下来小说君介绍下之前实现过的一个基于redis的、非常简陋的锁机制。
出现这个需求情景的两个关键词：非幂等的无状态服务、共享状态。
再详细描述一下：
请求的流程是client发到无状态服务，无状态服务从redis取出client的数据，修改（比如递增），存回。
client连续发了两次有效请求，节点A处理中还没存回，节点B存回了，然后节点A处理完存回，这时相当于节点B的修改失效。
Prepare阶段和Accept阶段都需要Acceptor做一些状态的维护，redis在这方面就特别好用。我们可以借助redis对lua的支持，直接hook住服务对redis的数据读写，比如需要进行互斥访问的时候，读取会额外拿到一个redis分配的lockId，更新数据时会检查lockId。
贴一个简单的同时更新多key的lua脚本例子：
local begin = 1
local i = 1
while KEYS[i] do
local key = KEYS[i]
local lockId = ARGV[i]
if not lockId then
return -1
else
local savedLockId = redis.call('HGET', key, '_lockId')
if savedLockId ~= lockId then
-- todo error
return -2
end
end
i = i + 1
end
local keyPos = 1
while ARGV[i] do
local fieldsNum = ARGV[i]
i = i+1
for j=1,fieldsNum do
local fieldName = ARGV[i]
local fieldValue = ARGV[i+1]
redis.call('HSET', KEYS[keyPos], fieldName, fieldValue)
i = i + 2
end
keyPos = keyPos + 1
end
return 0KEYS表示需要更新的一组key，ARGV表示每个key对应的lockId以及key的field和value。
由单一redis实例维护访问权状态，能应付大多数的业务情景，但是正如之前所说，这只是一个高度简化的问题形式。
如果这唯一的redis实例挂掉，锁状态的正确性会在一段短暂时间内无法保证；即使开了主备，由于redis的replica是异步的，也不能做到绝对的正确性保证。
这类问题其实就是之前的Acceptor-Proposer问题复杂化一下，多Acceptor维护互斥访问权状态。redis官方的解决方案是redlock。多redis实例维护锁状态，client利用时间和随机量请求多数锁。
其实现就跟redis的其他一些机制（比如广为吐槽的key expire）一样，充满了工程中的trick。因此后来kleppmann对此也有批判，相关的文章以及翻译随手搜一下就有，简单来说，其依据就是分布式环境中相比于节点宕机的更小概率事件：集群形成网络分化（network partition），以及不同机器的物理时钟有可能不同步。
不过，用多redis实例维护锁状态来解决数据不一致问题确实也不太合适。如果是需要100%正确性，那就不能用redis这种简单、高性能、但又充满了工程trick的实现，与其自己重新实现一次paxos或者raft，不如简单地借助zookeeper或者etcd来做协调。
下一篇小说君简单介绍下如何借助一些提供分布式一致性的基础设施来构建一套分片的、高可用的数据服务。
服务端系列文章的链接，以及后续的主题（按顺序阅读更佳）：
聊聊分布式锁（本篇）
构建高可用的数据服务（暂定）
聊聊RPC与消息流（暂定）
个人订阅号：gamedev101「说给开发游戏的你」，聊聊服务端，聊聊游戏开发。