分布式ID生成方案（雪花算法与变种）
请介绍分布式系统中的全局唯一ID生成方案。雪花算法（Snowflake）的组成结构是什么？时钟回拨问题如何处理？还有哪些其他方案（UUID、数据库自增、Redis INCR、美团Leaf、百度UidGenerator）？
回答
Yahuda
雪花算法（Snowflake，Twitter开源）：
结构（64位Long型）：
- 1bit：符号位（始终0）
- 41bit：时间戳（毫秒级，可使用69年）
- 10bit：工作节点ID（最多1024个节点）
- 12bit：序列号（同一毫秒4096个ID，支持每毫秒409.6万QPS）
时钟回拨问题：
- 如果系统时间回拨，可能会生成重复ID
- 解决方案：
- 等待时间追上回拨前的时间（暴力等待）
- 记录上次生成时间，若当前时间<上次时间则拒绝生成
- 预留回拨位（变种算法）
- 使用Zookeeper记录上轮最大时间
其他方案：
| 方案 | 优点 | 缺点 |
|---|---|---|
| UUID（36位字符串） | 本地生成，无网络开销 | 无序、太长（影响索引性能）、占空间 |
| 数据库自增ID | 有序、简单 | 单点瓶颈、并发低 |
| Redis INCR | 高性能、有序 | 依赖Redis、无业务含义 |
| 美团Leaf | 支持号段模式+雪花模式 | 需要部署服务 |
| 百度UidGenerator | 基于Snowflake优化 | 需依赖DB注册WorkId |
| 滴滴TinyId | 号段模式，支持多DB | 号段耗尽后需等待 |
推荐：Leaf的号段模式（高性能+低延迟）或雪花算法（无中心化）。