幂等性设计

幂等性定义

幂等性设计用数学的语言来表达是：f(x) = f(f(x))。在计算机中幂等性指一个操作多次执行的结果与其执行一次的结果相同。

注意：这里强调的是结果，而非响应。

Wiki 上幂等性的定义：https://zh.wikipedia.org/zh-cn/%E5%86%AA%E7%AD%89

在某二元运算下，幂等元素是指被自己重复运算（或对于函数是为复合）的结果等于它自己的元素。例如，乘法下唯一两个幂等实数为0和1。

设计具有幂等性的分布式系统可以有效避免数据不一致和重复处理的问题。非幂等性产生的原因如下：

1. 前端设计不合理，用户主动多次请求；
2. 网络库超时重试机制；
3. 弱一致性分布式系统中，不合理的查询判断。

支付是一个需要强幂等性的典型场景：用户点击支付按钮后，可能因为网页响应慢而重复点击，或者网络问题导致客户端重试。需要避免重复支付。

幂等性 & 并发安全：不是一回事。

同一笔订单不停地提交支付，如果扣了不止一次钱，说明该操作不幂等；有多笔订单同时进行支付，最后扣除的金额不是这么多笔金额的总和，说明该操作有并发安全问题。

这是两个维度的问题，应该分开讨论解决。

生成全局唯一ID

利用全局唯一 ID 及数据库主键唯一特性，可以解决重复提交的问题。相同的 ID 重复插入时，产生 result in duplicate entry for key primary 错误。系统流程图如下：

系统中一般会搭建一个独立的全局 ID 生成服务，生成的 ID 建议具备以下特性：

1. 全局唯一：不能出现重复的ID号；
2. 趋势递增：在 MySQL InnoDB 引擎中使用的是聚集索引，由于多数 RDBMS 使用 B-tree 的数据结构来存储索引数据，在主键的选择上应该尽量使用有序的主键保证写入性能；
3. 单调自增：保证下一个ID一定大于上一个ID，例如事务版本号、IM增量消息、排序等特殊需求。
4. 信息安全：防止被外界猜到生成规律。

UUID

UUID(Universally Unique Identifier)的标准型式包含32个16进制数字，以连字号分为五段，形式为8-4-4-4-12的36个字符，格式：xxxxxxxx-xxxx-Mxxx-Nxxx-xxxxxxxxxxxx（其中 M 代表 UUID 版本，N的一至三个最高有效位表示 UUID 变体）；示例：550e8400-e29b-41d4-a716-446655440000，到目前为止业界一共有5种方式生成 UUID，详情见 IETF 发布的 UUID 规范A Universally Unique IDentifier (UUID) URN Namespace。

看一个 C++ 标准 UUID v4 生成方案：符合RFC 4122 UUID v4标准（版本位固定为'4'，长度为36字符）

std::string GenerateUuid() {
  static std::random_device rd;                    // 1. 硬件随机数生成器
  static std::mt19937 gen(rd());                   // 2. Mersenne Twister 随机数引擎
  static std::uniform_int_distribution<> dis(0, 15); // 3. 均匀分布，范围0-15
  static const char* hex_chars = "0123456789abcdef"; // 4. 十六进制字符表

  std::string uuid = "xxxxxxxx-xxxx-4xxx-yxxx-xxxxxxxxxxxx"; // 5. UUID v4 模板
  for (char& c : uuid) {
    if (c == 'x') {
      c = hex_chars[dis(gen)];                     // 6. 随机替换 'x'
    } else if (c == 'y') {
      c = hex_chars[(dis(gen) & 0x3) | 0x8];      // 7. 特殊处理 'y' 位
    }
  }
  return uuid;
}

优点：性能非常高，本地生成，没有网络消耗；

缺点：

• 不易于存储：UUID太长，16字节128位，通常以36长度的字符串表示，很多场景不适用；
• 信息不安全：基于 MAC 地址生成 UUID 的算法可能会造成 MAC 地址泄露，这个漏洞曾被用于寻找梅丽莎病毒的制作者位置；
• 不适合作为数据库主键：太长；在 InnoDB 引擎下，UUID的无序性可能会引起数据位置频繁变动，严重影响性能。

snowflake 算法

snowflake 是 Twitter 开源的分布式自增 ID 算法。特点是：按时间有序、生成的结果小、生成效率高。

• 第 1 位占用 1bit，其值始终是 0，可看做是符号位不使用。
• 第 2 位开始的 41 位是时间戳，41-bit 位可表示 2^41 个数，每个数代表毫秒，那么雪花算法可用的时间年限是(1L<<41)/(1000L360024*365)=69 年的时间。
• 中间的 10-bit 位可表示机器数，即 2^10 = 1024 台机器，但是一般情况下不会部署这么多台机器。如果对 IDC（互联网数据中心）有需求，还可以将 10-bit 分 5-bit 给 IDC，分 5-bit 给工作机器。这样就可以表示 32 个 IDC，每个 IDC 下可以有 32 台机器，具体的划分可以根据自身需求定义。
• 最后 12-bit 位是自增序列，可表示 2^12 = 4096 个数。

这样的划分之后相当于：在一毫秒一个数据中心的一台机器上可产生 4096 个有序的不重复的 ID，理论上 snowflake 方案的 QPS 约为409.6w/s。但是 IDC 和机器数肯定不止一个，所以毫秒内能生成的有序 ID 能力是翻倍的。

优点：

• 毫秒数在高位，自增序列在低位，整个ID趋势递增；
• 不依赖数据库等第三方系统，以服务的方式部署，稳定性更高；
• 支持根据自身业务特性灵活分配 bit 位。

缺点：强依赖机器时钟，如果机器上时钟回拨，会导致发号重复或者服务会处于不可用状态。

应用实例：Mongdb objectID，通过“时间+机器码+pid+inc”共12个字节，以4+3+2+3的方式最终标识成一个24长度的十六进制字符。

数据库生成

以 MySQL 为例，利用给字段设置auto_increment_increment和auto_increment_offset来保证 ID 自增。

优点：非常简单，利用现有数据库系统的功能实现；ID 号单调自增，可以实现一些对ID有特殊要求的业务。

缺点：强依赖 DB，DB 异常时整个系统不可用（可配置主从复制，但是数据一致性在特殊情况下难以保证）；ID 发号性能瓶颈为单台 MySQL 的读写性能。

解决 MySQL 导致的性能瓶颈：

参考 Flickr 团队的一种主键生成策略：Ticket Servers: Distributed Unique Primary Keys on the Cheap。分别设置两台机器对应的参数，TicketServer1 从1开始发号， TicketServer2 从2开始发号，两台机器每次发号之后都递增2。

假设部署 N 台机器，步长需设置为 N，每台的初始值依次为0,1,2,…,N-1. 这种架构有以下几个缺点：

1. 系统水平扩展困难：定义好了步长和机器台数之后，添加机器时需要手动重新配置多台机器的初始值和步长以重新分配 segment；随着机器数量增加，重新配置过程变得复杂且容易出错。
2. ID只能趋势递增，不能单调递增；
3. 数据库压力大：每次获取 ID 都得读写一次数据库，只能靠堆机器来提高性能。

Leaf-segment 方案

1. 原方案每次获取 ID 读写一次数据库，数据库压力大；改为利用 proxy server 批量获取，每次获取一个 segment 号段的值；
2. 各个业务的不同发号需求用 biz_tag 字段来区分：每个 biz-tag 的 ID 获取相互隔离，互不影响；如果需要对数据库扩容，只需要对 biz_tag 分库分表。

数据库表设计：

+-------------+--------------+------+-----+-------------------+-----------------------------+
| Field       | Type         | Null | Key | Default           | Extra                       |
+-------------+--------------+------+-----+-------------------+-----------------------------+
| biz_tag     | varchar(128) | NO   | PRI |                   |                             |
| max_id      | bigint(20)   | NO   |     | 1                 |                             |
| step        | int(11)      | NO   |     | NULL              |                             |
| desc        | varchar(256) | YES  |     | NULL              |                             |
| update_time | timestamp    | NO   |     | CURRENT_TIMESTAMP | on update CURRENT_TIMESTAMP |
+-------------+--------------+------+-----+-------------------+-----------------------------+

• biz_tag 区分业务；
• max_id 表示该 biz_tag 目前所被分配的 ID segment 的最大值；
• step 表示每次分配的 segment 长度（读写数据库的频率从1降低到\(\frac{1}{step}\)）

优点：

• 便于线性扩展（对 biz_tag 分库分表）；
• 容灾性高：Leaf 服务内部有 segment 缓存，即使 DB 宕机，短时间内 Leaf 仍能正常对外提供服务；
• 支持自定义max_id，便于业务从原有 ID 方案迁移。

缺点：

• ID 随机性不足，有安全风险；
• TP999 数据波动大，segment 使用完之后依然会 hang 在更新数据库的I/O上，tg999 数据会出现偶尔的尖刺；
• DB 宕机会造成整个系统不可用。

双 buffer 优化：segment 异步预加载

Leaf 取 segment 的时机：segment 消耗完时进行，阻塞等待直到从 DB 取回 segment。

优化：采用 segment 预加载机制：在当前 segment 消费至某个阈值时，开一个新线程异步将下一个 segment 预加载至内存；这种无阻塞的切换方式消除了获取新 segment 时的系统等待，从而显著降低了 TP999 指标。

Leaf 高可用容灾

在应对“DB可用性”挑战方面，当前部署采用一主两从架构，并实行跨机房部署；主从同步基于半同步复制机制，同时依托 Atlas 数据库中间件（开源版本更名为DBProxy）实现自动的主从切换。

该方案在绝大多数场景下表现稳定，仅在少数异常场景下可能退化为异步模式，极低概率会出现数据不一致情况。如业务要求保证100%数据强一致，可选用基于类 Paxos 算法实现的强一致 MySQL 方案。

在服务部署与容灾层面，Leaf 服务按 IDC 进行分布式部署，内部通过“MThrift RPC”框架实现服务通信。负载均衡策略优先引导流量至同机房内的 Leaf 服务；仅在本机房服务不可用时才会跨机房调用。

Leaf-snowflake

方案背景

Leaf-segment 方案生成趋势递增的 ID，ID 号可计算，不适用于订单ID等生成场景，比如竞对在两天中午12点分别下单，通过订单 ID 号相减能大致计算出公司一天的订单量。

为规避 Leaf-segment 生成可推算 ID 的安全风险，提供了Leaf-snowflake 方案。Leaf-snowflake 方案完全沿用 snowflake 方案的 bit 位设计，即以“1+41+10+12”的方式组装 ID 号。 相比 snowflake，Leaf-snowflake做了2点优化：

1. 使用Zookeeper持久顺序节点的特性自动对snowflake节点配置wokerID，一定程度的提高系统的伸缩性和容错性；
2. 解决时钟回拨会可能导致生成重复的 ID 号的问题。

workerID 分配

Leaf-snowflake按照以下步骤启动：

1. 启动 Leaf-snowflake 服务，连接 Zookeeper，检查在leaf_forever 父节点下自己是否已经注册过（是否有该顺序子节点）；
2. 若已注册：直接取回缓存的 workerID 并启动服务；
3. 若未注册：在该父节点下创建一个持久顺序节点，创建成功后取回顺序号作为本机的workerID号，启动服务。

弱依赖 ZooKeeper：除了每次去顺序节点拿数据以外，本地缓存也 workerID 文件，确保在 ZooKeeper 故障时，服务仍能正常启动与运行，实现对第三方组件的弱依赖，保障高SLA。

时钟回拨处理

Leaf-snowflake 依赖时间，如果机器时钟发生回拨，有可能生成重复 ID 号，需要解决时钟回退问题。

服务启动时首先检查自己是否写过 ZooKeeper leaf_forever 节点：

1. 写过：使用自身系统时间与leaf_forever/${self}节点记录时间做比较：
   • 系统时间<leaf_forever/${self}时间：判定机器时间发生了大步长回拨，服务启动失败并报警；
2. 未写过：判定为新服务节点，直接创建持久节点 leaf_forever/${self}并写入自身系统时间；
3. 综合对比其余 Leaf 节点的系统时间，判断自身系统时间是否准确：取 leaf_temporary 下的所有临时节点的服务IP：Port；通过 RPC 请求得到所有节点的系统时间，计算\(\frac{sum(time)}{nodeSize}\)。
   • 若\(abs(\frac{系统时间-sum(time)}{nodeSize})\) < 阈值：判定当前系统时间准确，正常启动服务，同时写临时节点leaf_temporary/${self} 维持租约；
   • 否则：判定本机系统时间发生大步长偏移，启动失败并报警。
4. 每隔一段时间(3s)上报自身系统时间写入leaf_forever/${self}。

检测并阻止发生大步长回拨的节点启动：运行时，若检测到小步长回拨，则等待至追回时间；若回拨步长过大，则立即抛出异常、告警并中止服务。

//发生了回拨，此刻时间小于上次发号时间
if (timestamp < lastTimestamp) {
 			  
           long offset = lastTimestamp - timestamp;
           if (offset <= 5) {
               try {
               	//时间偏差大小小于5ms，则等待两倍时间
                   wait(offset << 1);//wait
                   timestamp = timeGen();
                   if (timestamp < lastTimestamp) {
                      //还是小于，抛异常并上报
                       throwClockBackwardsEx(timestamp);
                     }    
               } catch (InterruptedException e) {  
                  throw  e;
               }
           } else {
               //throw
               throwClockBackwardsEx(timestamp);
           }
       }
//分配ID 

微信的序列号生成器 seqsvr

seqsvr 是微信的一个高可用、高可靠的序列号生成器，利用生成的序列号，实现终端与后台的数据增量同步机制。seqsvr的架构可以分为两层，即StoreSvr和AllocSvr（存储层和缓存中间层）。

这里不详细展开，概括一下关键的设计思路：

1. 为微信的每份同步数据（如消息）提供一个全局递增的64位序列号：
   • 递增性：对同一用户，每次申请的 sequence 必须大于上一次；
   • 用户独立性：每个用户拥有独立的64位 sequence 空间，避免全局竞争。
2. 预分配中间层（segment 机制）：
   • 设计：在内存中维护当前序列号cur_seq和分配上限max_seq。每次分配只需递增cur_seq，只有当cur_seq触及max_seq时，才持久化更新后的max_seq（步长通常为10000）。
   • 收益：将持久化IO次数从每次分配的~10^7 QPS降低到~10^3 QPS，性能得到巨大提升。
3. 分 segment 共享存储：
   • 设计：将连续的 UID 划分为一个 segment，一个 segment 内的所有用户共享一个max_seq。
   • 收益：大幅减少了需要持久化和加载的max_seq数据量（从32GB降至300+KB），加快了服务重启速度。

HTTP 的幂等性

方法	语义	副作用	是否幂等	示例说明
GET	获取资源	无	是	如获取新闻列表，结果可能不同，但无副作用。
HEAD	获取头信息	无	是	常用于探活或检查资源是否存在。
OPTIONS	获取支持方法	无	是	返回“Allow”头标识支持方法。
DELETE	删除资源	有	是	多次删除同一资源，效果与一次相同。
POST	创建资源	有	否	多次提交会创建多个资源，如重复发帖。
PUT	创建/更新资源	有	是	多次提交同一URI仅产生一次更新或创建。

由于 POST 方法非幂等，在网络重复提交或用户多次点击时易产生重复资源。常见解决方案如下：

Token 机制：前端生成唯一 Token 置于表单隐藏域；后端利用数据库唯一约束校验 Token，重复提交会被拦截。 PRG 模式（即 Post/Redirect/Get）服务端处理成功后返回 302 跳转至结果页；结合禁止浏览器缓存表单页，防止用户回退再次提交。

实现幂等性的系统方案选型

第一个问题，由哪个主体实现幂等性呢？

1. 下游系统提供相应的查询接口，上游系统执行查询操作：如果查到了，表明已经执行；未查到，就走失败流程。
2. 下游系统实现幂等性：查询操作交给下游系统，上游系统只负责重试，由下游系统保证一次和多次的请求结果是一样的。 |

第二个问题，具体实现方案包括哪些呢？

数据库防重：利用唯一索引

数据表设计两个字段：source、reqNo，source表示调用方，seqNo表示调用方发送过来的序列号。source和reqNo设置为组合唯一索引。

核心逻辑：

try {
    dao.insert(entity);    
    // do business
} catch (DuplicateKeyException e) {
    dao.select(param);
    // 幂等返回
}

利用数据库唯一索引来避免重复记录，需要注意以下几个问题：

1. 主从延迟导致误判：在读写分离架构中，INSERT 操作主库后，若 SELECT 查询从库，可能因主从同步延迟而查不到刚插入的数据，导致重复请求被误放行。
   • 方案：将 INSERT 与后续的 SELECT 查询置于同一数据库事务中，确保读写均发生在主库。
2. 数据库容灾与扩容导致约束失效：
   • 故障切换：在跨地域容灾场景下，一次 INSERT 在A地主库成功后，若发生故障切换（Failover），相同的第二次 INSERT 请求可能被路由到B地新主库并再次成功执行。
   • 数据库扩容：分库规则变更可能导致两次相同的 INSERT 请求被路由到不同的数据库分片，使单个分片内的唯一索引失效。
   此类问题通常需要基础设施层支持（如支付宝的分布式数据平台通过数据复制技术保障全局一致性），技术复杂度较高。

token 令牌机制

核心思想是：每次操作都生成一个唯一的 token 凭证，服务器通过该凭证确保同样的操作不会被执行多次。

具体分为两个阶段：

1. 获取 token：客户端会先发送一个请求去获取 token，服务端生成一个全局唯一的 ID 作为 token 保存在 Redis 中，同时把这个 ID 返回给客户端；
2. 后端校验 token：客户端第二次调用业务请求时，在 header 中携带 token，服务端校验这个 token：
   • 校验成功：执行业务，并删除 Redis 中的 token；
   • 校验失败：重复操作，直接返回指定的结果给客户端。

服务端伪代码：

// SETNX keyName value: 如果key存在,则返回0，如果不存在，则返回1

// step1. 申请token
String token = generateUniqueToken();

// step2. 校验token是否存在
if(redis.setNx(token, 1) == 1){
  // do business
} else {
 // 幂等逻辑
}

分布式锁

通过 Redis 的SETNX命令实现接口的幂等性。

SETNX key value：当且仅当 key 不存在时，将 ke y的值设为 value；若给定的key已经存在，则SETNX不做任何动作。设置成功时返回1，否则返回0。

具体流程步骤：客户端先请求服务端，拿到一个代表这次请求业务的唯一字段；将该字段以SETNX的方式存入 Redis 中（设置相应的超时时间）； * 设置成功：第一次请求，执行后续业务逻辑； * 设置失败：已执行当前请求，直接返回。

幂等下的 ABA 问题

幂等操作：

update order set price = 100 where id = 1;

非幂等操作：

update order set price = price+1 where id = 1;

举个栗子： 1. 用户下单一个 100 块钱的商品，在支付前与商家沟通这打个 9 折； 2. 商家操作出错，将价格改成了 8 折，之后发现改错，修改成 9 折，对于订单系统这两次都修改成功了； 3. 由于网络出错，第一次修改通知产生了重试或者其他逻辑，覆盖了后面 90 元的推送； 4. 最终用户支付的价格，是错误的 80 元。

以上 ABA 问题可以使用乐观锁解决：在数据中加一个版本号，版本号不一致则产生异常处理。

参考

弹力设计篇之“幂等性设计”

消息幂等：如何保证消息不被重复消费？

幂等性实现

API 设计 — 如何设计稳定可预测的 API (谈幂等性)？

Leaf——美团点评分布式ID生成系统

微信序列号生成器架构设计及演变

Twitter snowflake

Designing robust and predictable APIs with idempotency

幂等设计

系统架构：分布式幂等适用场景及解决方案

分布式系统互斥性与幂等性问题的分析与解决