分布式ID生成方法

参考资料：
https://www.w3cschool.cn/architectroad/architectroad-distributed-id.html
https://www.jianshu.com/p/14712264341f

题目1：实现一个分布式集群模式下系统生成唯一流水号的算法，要求：
a.流水号不能重复；
b.不能生成一次访问一次数据库；
c.满足高并发性能要求；

方式一、数据库自增序列

这是最常见的一种方式，利用DB来生成全库唯一ID。

优点：
1）使用简单，代码方便，性能可以接受。
2）ID为数字类型，排序方便。

缺点：
1）不同数据库语法和实现不同，数据库迁移或多数据库版本支持时需要处理。
2）在单数据库、读写分离或一主多从场景下，只有一个主库可以生成，有单点故障风险。
3）在性能达不到要求时，难于扩展。
4）当多个系统需要合并或涉及数据迁移时处理复杂。
5）在分库分表时麻烦。

优化方案：
针对主库单点，如果有多个Master，可以设置每个Master库的起始数字不同，步长相同，步长可以是Master的个数。如：Master1 生成的是 1，4，7，10，Master2生成的是2，5，8，11，Master3生成的是 3，6，9，12。这样可以有效生成集群中的唯一ID，也可以大大降低ID生成库操作的负载。

【常见方法二：单点批量ID生成服务】

/只能生成一条/
SELECT REPLACE(UUID(),’-‘,’’) AS id;
/在数据库中找一张数据多的表执行生成多条/
SELECT (REPLACE(UUID(), ‘-‘, ‘’)) id FROM 表名 LIMIT （条数1000）;

【常见方法三：uuid】

优点：
1）使用简单。
2）生成ID性能高，基本不会有性能问题。
3）全球唯一，当数据迁移、数据合并、数据库变更时，可以从容应对。

缺点：
1）数据无序，无法保证趋势递增。
2）UUID使用字符串存储，查询效率较低。
3）存储空间较大，如果是海量数据库，需考虑存储量的问题。
4）传输数据量大。
5）可读性差。

// add()和remove()方法在失败的时候会抛出异常(不推荐)
Queue<UUID> queue = new ConcurrentLinkedQueue<>();
for (int i = 0; i < 100; i++) {
    UUID uuid = UUID.randomUUID();
    queue.offer(uuid);
}
try {
     System.out.println("poll="+queue.poll()); //返回第一个元素，并在队列中删除
} finally {
    if(queue.size() / 1000 == 0.25) {
        for (int i = 0; i < 750; i++) {
            UUID uuid = UUID.randomUUID();
            queue.offer(uuid);
        }
    }
}

【常见方法四：取当前毫秒数】

uuid是一个本地算法，生成性能高，但无法保证趋势递增，且作为字符串ID检索效率低，有没有一种能保证递增的本地算法呢？

取当前毫秒数是一种常见方案：uint64 ID = GenTimeMS();

优点：
（1）本地生成ID，不需要进行远程调用，时延低
（2）生成的ID趋势递增

（3）生成的ID是整数，建立索引后查询效率高

缺点：

（1）如果并发量超过1000，会生成重复的ID

我去，这个缺点要了命了，不能保证ID的唯一性。当然，使用微秒可以降低冲突概率，但每秒最多只能生成1000000个ID，再多的话就一定会冲突了，所以使用微秒并不从根本上解决问题。

【常见方法五：类 Snowflake算法】

Snowflake是twitter开源的分布式ID生成算法，其核心思想是：一个long型的ID，使用其中41bit作为毫秒数，10bit作为机器编号，12bit作为毫秒内序列号。这个算法单机每秒内理论上最多可以生成1000*(2^12)，也就是400W的ID，完全能满足业务的需求。

借鉴snowflake的思想，结合各公司的业务逻辑和并发量，可以实现自己的分布式ID生成算法。

举例，假设某公司ID生成器服务的需求如下：
（1）单机高峰并发量小于1W，预计未来5年单机高峰并发量小于10W
（2）有2个机房，预计未来5年机房数量小于4个
（3）每个机房机器数小于100台
（4）目前有5个业务线有ID生成需求，预计未来业务线数量小于10个
（5）…

分析过程如下：

（1）高位取从2016年1月1日到现在的毫秒数（假设系统ID生成器服务在这个时间之后上线），假设系统至少运行10年，那至少需要10年365天24小时3600秒1000毫秒=320*10^9，差不多预留39bit给毫秒数

（2）每秒的单机高峰并发量小于10W，即平均每毫秒的单机高峰并发量小于100，差不多预留7bit给每毫秒内序列号

（3）5年内机房数小于4个，预留2bit给机房标识

（4）每个机房小于100台机器，预留7bit给每个机房内的服务器标识

（5）业务线小于10个，预留4bit给业务线标识

64bit标识

这样设计的64bit标识，可以保证：
（1）每个业务线、每个机房、每个机器生成的ID都是不同的
（2）同一个机器，每个毫秒内生成的ID都是不同的
（3）同一个机器，同一个毫秒内，以序列号区区分保证生成的ID是不同的

（4）将毫秒数放在最高位，保证生成的ID是趋势递增的

缺点：

（1）由于“没有一个全局时钟”，每台服务器分配的ID是绝对递增的，但从全局看，生成的ID只是趋势递增的（有些服务器的时间早，有些服务器的时间晚）

最后一个容易忽略的问题：

生成的ID，例如message-id/ order-id/ tiezi-id，在数据量大时往往需要分库分表，这些ID经常作为取模分库分表的依据，为了分库分表后数据均匀，ID生成往往有“取模随机性”的需求，所以我们通常把每秒内的序列号放在ID的最末位，保证生成的ID是随机的。

又如果，我们在跨毫秒时，序列号总是归0，会使得序列号为0的ID比较多，导致生成的ID取模后不均匀。解决方法是，序列号不是每次都归0，而是归一个0到9的随机数，这个地方。