ID是身份标识，你所涉及的每类业务都会有一个，身份证， 手机号， QQ号。那么问题来了，如何设计一个算法，能快速生成ID又能有效地避免冲突。
往小了说，在存储领域每一行数据都会有一个ID，关系型数据库有 auto increment， 非关系型数据库，如mongodb有自己的objectID 算法。
对于各种ID我们可以简化为2类：
1.去中心化，统一长度，规则占坑类， mongodb属于这一类， guid 属于这类类。
2.中心化，ID自增，auto increment属于这一类。
mongodb id
mongodb的ID规则
| 长度(byte) | 含义 |
|---|---|
| 4 | unix epoch到当前的秒数 |
| 3 | 机器标识 |
| 2 | 进程标识 |
| 3 | 扩展计数 |
机器标识可以防止不同机器出现相同ID， 进程标识则可以在同一台机器上防止出现冲突。
对于这种设计， 我想说 good! 无论是单机还是分布式都可以很有效地解决冲突的问题。
即使同一时刻有很多请求，不同机器也不会产生相同的ID，达到了去中心化的ID生成能力。
类似的设计还有twitter snowflake:
| 长度(bit) | 含义 |
|---|---|
| 41 | unix epoch到当前的毫秒数 |
| 10 | 节点ID |
| 12 | sequence |
也做到了不同节点去重，不同时间有序，只是把节点ID的制定交给了使用者。
mysql auto seq
相信大部分研发同学都使用过mysql，auto increment可以有效地解决ID生成。
CREATE TABLE animals (
id MEDIUMINT NOT NULL AUTO_INCREMENT,
name CHAR(30) NOT NULL,
PRIMARY KEY (id)
);id会从1开始自增，所以单台Server的情况下是不会有冲突的可能的。
这样的设计一度非常常见于各种前端技术，用过LAMP技术栈的同学应该记得，目前仍被mysql, redis等广泛使用。
引申
第一种方案是于空间时间相关的，类似于身份证
把坑给你空好，生成机制设计好，生成ID就变成了按机制生成数字填坑， 只要时间不停摆，人口不会短时间内爆增，这个ID就很难重复。
等于把冲突保障交给了系统。
第二种方案与时空无关，只要生成器还在，就可以一直生产数据，冲突由生成器保障。
问题抛出
系统不可靠
以mongodb为例
| 长度(byte) | 含义 | 依赖 | |
|---|---|---|---|
| 4 | unix | epoch到当前的秒数 | 系统时间 |
| 3 | 机器标识 | ||
| 2 | 进程标识 | ||
| 3 | 扩展计数 |
如果因为操作不当，人为把机器的当前时间修改成过去某个时间，其新生成ID的时间部分就有可能冲突。
举例来说，某一年的公历出现了润8月（不可能出现），则8月出生的小朋友就要身份证重号了，现终于知道为什么身份证不使用农历了吧，哟呵呵。
自增的瓶颈
自增形式的生成器很可能成为瓶颈，争对单点的问题业界已经有一些方案，比如分片自增
有3个节点 p1, p2, p3, 生成的ID规则：
p1: 1,4,7,10,13,16,19,22
p2: 2,5,8,11,14,17,20,23
p3:3,6,9,12,15,18,21,24
既使节点A崩溃了，只要有一个节点还在，系统就能工作。
但是不太好扩展，如果一开始只分配了3台机器，后面系统达到瓶颈了添加机器，就比较麻烦了。
ID的意义
在分布式系统中，ID往往有很多意义，比如散列，如何精确地的把按ID的查询散列到某台机器上去，因此在一些场景下ID需要包含机器信息，第一类去中心化ID生成器很好的解决了此类问题。
另外，有时候需要从ID知道系统的数据规模，自增的ID能较好的解决此类问题。
从安全角度上看，不同场景下ID应该有不同的表述，避免被外部猜测。比如微信号在第三方服务中是不能被直接使用的，而是一个64字节不具备查询意义的open id。
能不能有一个ID机器既能满足散列，又能反映数据规模呢，我想是可以的。
本来只想分享一下现行的生成规则，作为文章的附加，我简单设计了一个有效的ID生成器。
分布式ID的设计
设计方向
快速生成，不冲突。
既使系统时间被重置，也不会冲突。
能从最新的ID拿到当前的数据规模。
支持不同场景不同表述。
结构设计
| 长度(byte) | 含义 | 意义 |
|---|---|---|
| 4 | unix epoch到当前的秒数 | 去中心化 |
| 3 | 机器标识 | |
| 2 | 进程标识 | |
| 3 | 扩展计数 | |
| 8 | 统一分配全局ID | 中心化 |
设计思想
设计上将中心化与去中心化结合，对外展示去中心化的ID， 对内展示全部，对统计展示中心化ID。
分配架构
全局ID统一分配器设计
作为中心化的瓶颈，必须由机器保障其功能可靠。
各个节点从全局ID分配器批量获取ID作为预分配资源，当节点剩余预留ID低于阈值时再次申请。
节点分配设计
void Pot::onRequest(long& conID, long& reqID){
uint64_t id = cache.incr(); //预留ID自增
if(id <= 0){ //预留ID不够
cache.distribute([this, &conID, &reqID](uint64_t id, uint32_t err){ //请求后端申请全局分配预留片，并设置好回调
this->response(conID, reqID, id);
}); //向全局请求分本书
return;
}
if(cache.shouldDistribute()){ //检查预留池是否达到申请阈值
cache.distribute(); //向后端申请全局分配预留片
}
response(conID, reqID, id); //返回
}全局分配器工作原理
工作原理也是一样简单
void Distribute::onRequest(long& conID, long& reqID){
uint64_t minID, maxID, err;
uint32_t flag = db.pre(minID, maxID, err); //预分配ID片
if(flag <= 0){ //是否出错
response(conID, reqID, err); //返回
return;
}
response(conID, reqID, minID, maxID); //返回ID片
}
崩溃处理机制
单节点崩溃，其他节点仍能崩溃，这个比较简单。
全局分配器的崩溃处理需要在设计上保障，可以同时并存几个全局生成器，且并不缓存当前最大分配ID，该值由数据库来存储。
全局分配的请求是个低频处理器。
假设工作节点数为N， 系统每秒处理并发为Concurrent, 全局分配器的请求频次F，每次分配ID片长度为P, 全局分配器个数为M，则有下列公式：
F=Concurrent/(NPM)
假设每秒并发数为100万 （1秒产生100万个ID，1秒新增100万个用户，实际不可能），有5个工作节点，全局分配器个数为4， 每次申请ID片为10000。
F=1000,000 / (5 100004) ＝5.
100万每秒的分配也只有每秒几次的请求，而且P的值可以灵活修改，假设P＝100,000(每片10万个ID），则每秒1个请求都没有了。
这种情况下对全局分配的安全只需要对数据主从热备就行了。
理论退化
将上面的规则重新审视一下：
| 字段 | 长度(byte) | 备注 | |
|---|---|---|---|
| time | 4 | unix epoch到当前的秒数 | 去中心化 |
| machine | 3 | 机器标识 | |
| process | 2 | 进程标识 | |
| count | 3 | 扩展计数 | |
| center id | 8 | 统一分配全局ID | 中心化 |
如果只有前4个，去掉center 只退化成了mongodb的去中心化ID生成器。
如果去掉前四项，保留center id,则退化成了具备分布式功能的中心化ID生成器。
在一些简单的业务里，可以只需要在这2者中选一个就可以满足分布式业务的处理。
