唯一ID的用途
- 作为业务数据的唯一标识，用该ID来进行分库分表
- 使用绝对自增的ID作为绝对时钟的模拟
业务系统对ID号的要求
概括下来，那业务系统对ID号的要求有哪些呢？
全局唯一性：不能出现重复的ID号，既然是唯一标识，这是最基本的要求。
趋势递增：可以作为排序字段
- 单调递增：保证下一个ID一定大于上一个ID，例如事务版本号、IM增量消息、排序等特殊需求。
- 信息安全（防逆向）：如果ID是连续的，恶意用户的扒取工作就非常容易做了，直接按照顺序下载指定URL即可；如果是订单号就更危险了，竞对可以直接知道我们一天的单量。所以在一些应用场景下，会需要ID无规则、不规则。
- 一般会将该ID用作索引，为性能考虑考虑的话，一般使用64位整数。如果允许用字符串的话，用上面的UUID即可。
- 实际项目中，我们更有可能使用53位整数作为唯一ID（主要考虑是JS等语言或者JSON协议等对int64的支持不好，其限制在于仅支持float)
常见实现方案
借助数据库的主键ID
优点：简单，绝对自增
不足：该方案存在单点故障风险；另外，数据库能支撑的吞吐比较低
优化：考虑多台Master，设置不同的步长
借助Redis的incr
优点：性能好、绝对自增
不足：redis的定位是缓存，数据有丢失的可能。
雪花算法
实现思路：时间戳 + 机器ID + 自增ID（随机，而不要从0开始）
优点：简单、性能好、趋势递增
不足：依赖机器的时钟，如果服务器时钟回拨，会导致重复ID生成。
时钟回拨
可以考虑通过历史时间（当自增ID发生回环时，进行+1）、扩展位（当检测到本次时间相比之前变小，则扩展位++）
解决时钟回拨问题的方法
等待机制：
当检测到时钟回拨时，生成器可以等待时间追上上次生成ID的时间戳，然后再生成新的ID。这种方法简单直接，但可能会导致生成器在等待期间无法生成新的ID。
扩展位：
在ID结构中增加额外的位来处理时钟回拨。例如，可以使用额外的位来记录时钟回拨的次数，从而避免ID重复。
预留时间戳：
在生成ID时，预留一些时间戳范围，用于处理时钟回拨。例如，可以预留一些时间戳范围，当检测到时钟回拨时，使用预留的时间戳生成新的ID。
逻辑时钟：
使用逻辑时钟（如Lamport时钟或Vector时钟）代替物理时钟。逻辑时钟可以保证在分布式系统中事件的顺序，避免时钟回拨问题。
借助Zookeeper
优点：唯一性有保证，上面雪花算法中的机器ID便可以考虑使用该方案来获取。
不足：吞吐量低，仅32位
UUID
本质：去中心的生成方法本身没法保证唯一性。一般降到实际可忽略的重复概率就能用了。分布式系统之所以难，很重要的原因之一是“没有一个全局时钟，难以保证绝对的时序”，要想保证绝对的时序，还是只能使用单点服务，用本地时钟保证“绝对时序”。
Leaf算法
实现思路：号段模式，由数据库先来负责分配号段，再由专门的分发服务来负责自增生成唯一ID
优点：分布式，无单点；性能好
不足：实现略复杂
解决分布式唯一 ID 的一个想法
本方案参考百度 UidGenerator，解决了 workerId 无法复用的问题
使用 Snowflake，利用 MySQL 自增 Id 分配 workerId，并复用 workerId；同时利用时间号段保证时间趋势递增
使用 Snowflake，64bit 的 Id 设计如下：
因此，最多有 2^10 = 1024 个 workerId，分配 WorkerId 的 DB Schema 设计如下：
CREATE TABLE IF NOT EXISTS worker_node_tab
(
id BIGINT NOT NULL AUTO_INCREMENT COMMENT ‘worker id’,
ip CHAR(64) NOT NULL COMMENT ‘host IP’,
port CHAR(64) NOT NULL COMMENT ‘host port’,
last_timestamp TIMESTAMP NOT NULL COMMENT ‘last timestamp’,
duration_step TIMESTAMP NOT NULL COMMENT ‘duration’,
mtime TIMESTAMP NOT NULL COMMENT ‘modified time’,
ctime TIMESTAMP NOT NULL COMMENT ‘created time’,
PRIMARY KEY(id)
) COMMENT=’WorkerID Assigner for UID Generator’,ENGINE = INNODB;
服务启动流程：
往 worker_node_tab 插入自己的 IP&Port 等信息，获取 DB 自增 id，设置 workerId = id % 1024
从 worker_node_tab 获取最大的 last_timestamp(max_last_timestamp)，并设置 timestamp = max_last_timestamp + duration_step
备注：因为百度 UidGenerator workerId 不会重复，因此不用担心 timestamp 重复；我们需要复用 workerId，因此必须要保证 timestamp 是趋势递增的
生成 Id 流程：
sequence += 1
如果 sequence 还没超过 MAX_SEQUENCE(2^12)，则跳到(3)直接生成 Id；如果 sequence 大于等于 MAX_SEQUENCE，则设置 timestamp += 1, sequence = 0，然后跳到(3)生成 Id（timestamp 在本地自增，因此不用担心时间回拨的问题）
生成 Id：Id = timestamp << (10 + 12) | workerId << 12 | sequence
duration_step 可以设置为两天（或更长），每隔一天异步到 DB 申请一个时间号段（即设置 DB last_timestamp += duration_step）；可以做到弱依赖 DB
微信的自增ID生成
给我们的一些启发：
逻辑服务层：负责加载max_seq=>cur_seq，每次分配新的时，cur_seq++;如果超出，则持久化max_seq，从而减少了对store的读写
store层：负责存储每一个用户的max_seq，但是如果每一个用户都存储一个max_seq的话，使用的量有点大，可以考虑一个uid范围内的公用一个max_seqno
store的持久化：NRW策略（W +R > N)
set化部署，号段隔离
如何确保ID不回撤 等价于 如何确保一个号段的请求，总是落到同一个逻辑服务上。
路由表：版本号
第三方仲裁去更新路由表，逻辑服务去访问store层时去
参考：https://www.infoq.cn/article/wechat-serial-number-generator-architecture
