【分布式系统设计】：漫谈幂等
引言
因为笔者对分布式系统有着狂热的兴趣，因此开了【分布式系统设计】这一专题，不仅可以分享学习成果，帮助大家面试，根据费曼方法，还能在写文章的过程过发现自己认识的不足。
分布式系统与单机编程有着巨大的区别，一台计算机上的任何错误（硬件错误，kernel panic）可以让计算机直接宕机(single point of failure)，这意味着单机程序没有任何容错性，而这是对可用性有着极高要求的互联网公司们绝对无法容忍的。而在大部分分布式系统中，一台甚至多台机器的宕机以及机器之间的网络中断(network partition, 这个问题将在之后的文章中分析)并不会影响到整个系统的运作。然而，分布式系统中各种各样的错误都有可能发生，围绕着分布式系统的容错性，可用性，以及一致性，许多精妙的设计与算法被提出。这个专题将分析和总结分布式数据库，分布式缓存，分布式计算和分布式事务等话题。作为第一篇文章，本文将介绍幂等(idempotency)这个概念以及其重要性，并且讨论几个实现幂等的方法，让大家对分布式系统有一个初步的认识。
幂等
笔者有过一个真实的经历（听着很像为了写文章编出来的，但是千真万确），之前跟朋友们约好旅行，在网上买机票的过程中，有一个朋友在最后一步也就是VISA支付界面点击付款时被通知付款失败，于是他重新点了一次支付，然后成功了。这个过程听上去很正常，可是当他检查邮箱和自己的银行账户时，发现自己付款了两次，于是开始了漫长的与航空公司扯皮的过程（最后成功退款）。
当时并不明白为什么会出现这种情况，因为如果VISA告诉我支付失败，那么支付一定是失败了，为什么我仍然付款了呢？这就引入了计算机通信的不可靠性了，笔者将支付的几种情况画出来：
支付成功
这种情况展示了在一个小小的分布式系统中（你的电脑和visa的服务器）一次完整且正常的通信，用户提交订单，VISA处理订单并通知用户成功。
订单提交丢失
这种情况展示了提交订单请求在不稳定的网络环境中的丢失，用户并不知道自己的请求丢失了，一直等下去是肯定不行的，所以在分布式系统中，所有的API接口都会设置一个超时机制（timeout）。在此例中，用户点击付款，于是电脑调用VISA的支付接口，但是请求丢失，过了一段时间后调用超时了，客户端返回用户一个超时错误。用户此时也许会重试，但是这种情况下的重试不会出问题，因为订单并没有真正提交。
订单处理失败
这种情况中，VISA支付服务器出错（写数据库失败或者下游服务宕机），于是给用户返回了一个错误。用户也许会重试，但是同样也没有问题，因为订单并没有真正提交。
订单处理成功，但是回复丢失
这是最为棘手的一种情况，订单处理成功，然后服务器给用户电脑的回复丢失了，用户电脑对支付接口的调用将会超时，此时一旦用户重试提交订单并且成功，两次支付将会发生！
幂等(idempotency)正是为了应对这种情况而提出的一种机制。在数学中，幂等意味着函数的多次调用将返回相同结果：f(x)=f(f(x))。在分布式系统中有着相似的意味：接口的多次调用将返回相同的系统状态。简单地举例来说，我们不管几次调用支付接口，银行账户都只应该有一次扣款。
接下来将会介绍幂等的几种实现方法。
实现方法
天然幂等
有很多操作是天然幂等的，比如SQL中的 SELECT, DELETE， 部分 UPDATE语句和精心设计的 INSERT语句。
SELECT作为一个只读操作，每次调用自然不会改变系统状态。
对于 DELETE语句来说，当我们要执行 DELETE FROM some_table WHERE id=1234，第一次执行将会把 id为1234的行删除，而当执行第二次时，因为此行已经被删除，SQL执行不会影响到任何行，所以 DELETE语句也是幂等的。
为什么说只有部分 UPDATE语句是幂等的呢？比方说 UPDATE user_table SET username='Rick'WHERE id=1234语句就是幂等的，因为无论执行多少次，用户1234的用户名都会是Rick。但是对于 UPDATE item_stock_table SET stock=stock-1WHERE id=1234语句就是不幂等的，因为每次执行都会将商品的库存减少1件。
对于 INSERT操作，如果我们对于给要插入的表加入一个unique field, 并且在插入时附上这个field。比方说有一个表叫做 user_table，id在创表时设为唯一，那么 INSERT INTO user_table(id,username)VALUES(1234,"rick")语句在id为1234的用户不存在时会插入成功，而一旦插入成功，第二次重试一定会返回一个 ERR_DUPLICATE错误。
乐观锁
乐观锁指在操作之前，向服务器索要一个版本号，在随后的实际操作请求中附上版本号，如果请求中的版本号与服务器当前版本号一致，那么视为有效操作，当操作成功时，服务器会生成一个新的版本号。因此当客户端重试时，请求会带着旧的版本号，服务器发现版本号不一致时会返回一个错误。
举个例子，就如之前我们说到的支付问题，当用户的电脑发送支付100元的请求前，可以向服务器索要当前账户余额，假如服务器返回了1000元的账户余额，那么这个请求将会附上这个余额，当服务器收到请求时，将执行以下逻辑：
def transaction(request):
if request.balance == account.balance:
account.balance -= request.transaction_amount
return SUCCESS
else
return ERR_INVALID_REQUEST因此，一旦第一次请求成功，第二次请求发生时请求中的余额已经和真实余额不一致，所以会收到一个错误返回。
当然，这只是一个非常简化的例子来帮助大家理解乐观锁，真实的支付系统非常复杂，比如大部分系统使用最终一致性模型（以后笔者会撰文详细分析），支付成功时余额并不会马上减少，而是后台有一个状态机来管理交易的整个life cycle。
全局唯一request id
乐观锁会带来一个问题，那就是要求在获取版本号之后系统状态不能发生任何改变，然而在高并发系统中，系统状态随时可能被其他请求改变，这将导致本请求被其他独立的请求干扰。比方说有一个抢票网站以票的当前存量为版本号，假如用户电脑第一次拿到的存量为100, 而发出抢票请求后系统中的存量因为另外一个用户的抢票请求变成了99，此时因为100对不上99，这个请求就会失败，导致了不相干的请求之间互相干扰。
这时我们回想起在上一幂等方法中提到的 INSERT操作，如果说我们给每个请求附上一个随机生成的 reuqest id，并且在服务器上维护一个存储reuqest id的数据库（reuqest id设为唯一），处理请求前将这个 request id插入数据库，如果说插入成功，说明这个请求还没有被处理过，如果插入失败，意味着此请求已经被处理，系统将返回一个错误回复。具体流程可以由以下伪代码展示：
def transaction(request):
err = database.insert(request.request_id)
if err != Null:
return err
process_request(request)
return SUCCESS总结
在这篇文章中我们分析了幂等的重要性与实现方法。在分布式系统中，因为网络的不稳定性，重试是一个非常频繁的操作，幂等将帮助我们在不稳定的网络中维护一个正确的系统状态。
相信读者已经理解了分布式系统中错误的不可避免性。然而，不要就这么认为分布式系统是不靠谱的，我们仍然有着许许多多巧妙的机制与算法来实现其整体的可靠性。后续文章中笔者将分享更多的分布式原理，来让大家感受到分布式系统的精妙之处。