分布式唯一 id

• （选答）系统设计题 1）请分析题⽬需求，给出你认为合理的技术⽅案，技术⽅案格式可参考原公司； 2）请充分通过题⽬展现你的设计⽅法，设计理念。对于关键的技术选型，给出适当注解； 需求描述：设计⼀个服务，任何⼈调⽤这个服务，都返回⼀个unique id，不能重复；

需求分析

1. 服务提供唯一 id 的获取, 使用 HTTP 方式提供调用
2. id 应尽可能短, 节省内存
3. 按照时间尽量有序, 利于储存在 MySQL 符合聚簇索引插入排序性能
4. 高可用
5. 高并发
6. 可扩展

依照以上需求分析, 决定使用雪花算法来作为id的生成算法: 使用 64 位整数来储存生成的 id. 具体 64 位使用如下:

1. 空符号位 1bit
2. 时间戳 41bit: 2^41 个数字, 储存时间戳(毫秒级) 储存时间可以使用 80年 +
3. 数据中心ID 5bit: 最大32个数据中心
4. 机器ID 5bit: 单中心最大32个服务
5. 序列号 12bit: 单服务下的序号生成, 最大 2^12 = 4096 位数字

以上设置下, 在单 node 情况下, 每毫秒最多生成 4096 位数字.

保证单节点下的序列号唯一

当服务是单进程时, 每个服务算一个节点. 当服务是多进程时, 要么设置进程锁, 要么对每个进程都算作一个节点. 进程内多线程, 使用线程锁, 保证生成的序列号唯一.

采用方案

使用雪花算法, 最多可设置 1024 个节点提供服务. 通过 DNS + lvs + keepalived + Tenginx 方式提高高并发, 高可用的服务.

问题

1. 单节点同一毫秒下生成的节点数据超过了 4096 个怎么处理?

设置循环, 等待下一毫秒再次获取

1. 如何保证有序?

单机情况下绝对有序.

分布式情况下: 时间戳在id的高位, 所以不同时间下产生的序列号是有序的. 但是对于不同节点在同一时间下产生的序列号, 会按照数据中心和机器ID来排序的.

1. 如何高可用?

多机房+多机器, 对应数据中心ID和机器ID, 使用 lvs 做均衡负载, Nginx 作为单机器的 web 服务器, keepalived 作为 Nginx 健康检查.

• 使用 Tenginx 可以对转发的服务进行健康监测
• lvs: 每个机房一台主机作为 lvs + keepalived 服务器, 请求到达 lvs 上会转发到当前机房的 nginx 上.
• keepalived: 当机房内的 Nginx 不可用时, 将下线这个 Nginx
• Nginx: 请求转发给 id 生成服务

通过 DNS 可以将请求分发到不同机房的 lvs 上. 如果 lvs 故障, 需要更改 DNS 配置.

1. 可扩展

由雪花算法产生的id结构来看, 最多支持 32机房 * 32机器 = 1024 个节点. 一般来说达不到这个量级.

• 单机房可以设置多个 lvs 服务, 多个 lvs 对接多个 Nginx, 机房内设置主路由, 请求从外部过来先到达主路由, 再路由到 lvs, 再转发到 Nginx 上.
• 增加单机房内的 Nginx 服务数量
• Nginx 下增加节点数量
• 增加机房

1. 效果预估

2. 单机 Nginx QPS 一般在 1w ~ 2w 之间.
3. 单线程每毫秒 4095 个id, 每秒为 409w +, 生成几乎不会触发自旋锁.
4. 生成 id 过程只涉及到: 获取毫秒时间, 加锁获取当前毫秒的计数, 几乎没有计算压力.