几乎所有的业务系统，都会有很多表记录，都有生成一个记录标识的需求，或者直接使用数据自带的自增键，或者自己开发（一般大公司有中间件部门提供组件或服务），作为工程师也是我们要掌握的技能，过往实践中，碰到过不少ID生成场景，如：
- 数据量不大(数据在千万以下)，写入并发未达到数据库上限，建单表，主键使用数据库的auto_increment足矣;
- 业务日志，数据写入海量(每天可能达到百亿级，如果到家的日志平台-守望者，阿里的鹰眼等)，写入并发高，主键适合使用UUID;
- 数据量大(如订单 交易 积分等)，使用了分库分表，ID的生成要求：生成全局唯一，高性能，容灾，可扩展，这里就需要分布式ID；
- 其他：有脱敏性要求的，防竞品收集商家数量 订单数量 交易笔数等商业机密，要求ID散列，如商家ID，订单ID，交易ID 不宜使用数据库的自增键。
分布式ID，顾名思义在分布式环境下生成全局唯一的ID。有twitter提出的Snowflake(雪花)算法，Flicker算法，有在Flicker思想上进一步的数据库+本地缓存算法。
Snowflake
算法
算法理解起来还是比较简单：
- 41 bits: Timestamp(毫秒级)
- 10 bits:机器ID(一般是单元机房ID 5 bits + 机器ID 5 bits)，也说是逻辑分片的l
- 12 bits: 可单机生成12位bit的自增序列
JAVA实现
/**
* Created by 登程 on 2018/1/24.
*/
public class Snowflake {
/**
* 机器ID占用位数
*/
private static final int WORK_ID_BIT_SIZE = 10;
/**
* 机器ID最大数
*/
private static final int WORK_ID_MAX_VAL = -1 ^ (-1 << WORK_ID_BIT_SIZE);
private int workId;
/**
* 序列占用最大位数
*/
private static final int SEQUENCE_BIT_SIZE = 12;
/**
* 序列最大值(4098)
*/
private static final int SEQUENCE_MAX_VAL = -1 ^ (-1 << SEQUENCE_BIT_SIZE);
private int sequence = 0;
private long lastTimestamp = 0L;
/**
* 最小日期1970-01-01
*/
private static final long MIN_TIME = 1288834974657L;
public Snowflake(int workId) {
if (workId > WORK_ID_MAX_VAL || workId < 0) {
throw new IllegalArgumentException("workId参数错误");
}
this.workId = workId;
}
public synchronized long nextId() {
long currentTime = getTimestamp();
if (lastTimestamp > currentTime) {
throw new IllegalArgumentException("time clock is error!");
}
if (currentTime == lastTimestamp) {
this.sequence = (this.sequence + 1) & SEQUENCE_MAX_VAL;
if (sequence > SEQUENCE_MAX_VAL) {
throw new IllegalArgumentException("并发量大，sequence溢出!");
}
} else {
this.sequence = 0;
lastTimestamp = currentTime;
}
return ((lastTimestamp - MIN_TIME) << (WORK_ID_BIT_SIZE+SEQUENCE_BIT_SIZE)) | (this.workId << WORK_ID_BIT_SIZE) | sequence;
}
private long getTimestamp() {
return System.currentTimeMillis();
}
}
测试代码如下
/**
* Created by 登程 on 2018/1/25.
*/
public class TestSnowflake {
private static ExecutorService threadPool = Executors.newFixedThreadPool(200);
private static Snowflake snowflake2 = new Snowflake(11);
private static Snowflake snowflake1 = new Snowflake(10);
public static void main(String[] args) {
for (int i = 0; i < 100000; i++) {
threadPool.execute(new IdGenThread(snowflake2));
threadPool.execute(new IdGenThread(snowflake1));
}
threadPool.shutdown();
while (!threadPool.isTerminated()){
try {
Thread.sleep(100L);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
}
/**
* Created by 登程 on 2018/1/25.
*/
public class IdGenThread implements Runnable {
private Snowflake snowflake;
IdGenThread(Snowflake snowflake) {
this.snowflake = snowflake;
}
@Override
public void run() {
System.out.println(snowflake.nextId());
}
}
优点缺点
优点和缺点都明显
优点
- 生成Long型易操作，有序
- 性能高效(单机支持4098个并发生成ID，对于大部分业务来说足够了)
缺点
- 维护成本：维护机器ID(大公司有统一机器部署服务，单元机房和机器很容易读取到，小公司维护起来较为麻烦，可能需要在每台机器上序号）
- 没有一个全局时钟，难以保证时序
Flicker算法
不同分库设置不同的起始值和步长。Flicker启用了两台数据库服务器来生成ID，通过区分auto_increment的起始值和步长来生成奇偶数的ID。
数据库配置
Sequence Server1:
auto-increment-increment = 2
auto-increment-offset = 1
Sequence Server2:
auto-increment-increment = 2
auto-increment-offset = 2
如何路由到不同的数据库上，做到负载均衡：如果保证自增顺序，可以考虑利用ZK或redis等做分布式锁来保证；不考虑自增顺序，可以考虑RPC类似的负载原理。
- 优势：利用mysql自增id
- 缺点：运维成本比较高，数据扩容时需要重新设置步长;数据库的写压力依然很大，每次生成ID都要访问数据库。
基于数据库更新＋内存分配
在数据库中维护一个ID，获取下一个ID时，会对数据库进行ID=ID+{步长} WHERE ID=XX，如果更新成功，则表示可以拿到{步长} 个ID，在内存中进行分配，单机最多可生产{步长} 个ID，超时或者达到{步长} 个ID后，则继续对数据库进行获取。
在分布式环境下，容灾和扩容是需要考虑，概括起来就是：生成id的数据库可以是多机，其中的一个或者多个数据库挂了，不能影响id获取，保证高可用.
利用多库的id生成方案： 每个数据库只拿自己的那一段id. 如下图,sample_db_1-sample_db_4是用来生成全局唯一id的4个数据库(一般在业务数据库中建立，可保证同生共死)，那么每个数据库对于同一个id有一个起始值，比如步长是1000.
| 数据库 | 取值范围(步长：1000) |
|---|---|
| sample_db_1 | 0 |
| sample_db_2 | 1000 |
| sample_db_3 | 2000 |
| sample_db_4 | 3000 |
应用某台服务器获取ID的时候,随机取到了sample_db_2,那么这台机器会拿到2000-2999这一千个id（初始值是2000，在单机内存中将其视为临界资源保证自增）,当然而这个时候4个数据库上id起始值会变成下图所示：
| 数据库 | 取值范围(步长：1000) |
|---|---|
| sample_db_1 | 0 |
| sample_db_2 | 5000 |
| sample_db_3 | 2000 |
| sample_db_4 | 3000 |
注意到,下次从sample_db_2上取得的id就变成了5000-5999. 这样,完全避免了多机上取id的重复.比如sample_db_2只会取到1000-1999,5000-5999,9000-9999, 13000-13999…sample_db_1,sample_db_3,sample_db_4其他数据库取值范围也一样,这样就不会相互重叠，数据唯一性得到保证。
如果扩容，如将数据库扩展成5个（建议设定初始值，避免重试多次），sample_db_2的取值范围就会是1000-1999，6000-6999，11000-11999...一个小段时间存在2台服务器有生成统一ID的可能，建议重启机器并做重试(有重复异常时，取ID)，这样问题解决。
优势：高可用
缺点：无法保证自增顺序；需要根据合适的写入QPS来判断步长。
