1. 背景和特性

传统数据库软件开发中，主键自动生成技术是基本需求。而各个数据库对于该需求也提供了相应的支持，比如 MySQL 的自增键，Oracle 的自增序列等。

当数据分片后，不同数据节点生成全局唯一主键是非常棘手的问题。同一个逻辑表内的不同实际表之间的自增键由于无法互相感知而产生重复主键。

分布式ID的特性如下：

全局唯一性，不能重复
趋势递增：保证写入性能，例如mysql的存储
单调递增：保证下一个ID一定大于上一个 ID，例如事务版本号、IM 增量消息、排序等特殊需求。
信息安全：如果ID是连续的，很容易知道订单量级，或者直接按照顺序下载指定URL即可

2. UUID

UUID 是最简单的分布式 ID 方案
UUID 是通用唯一识别码（Universally Unique Identifier)的缩写，开放软件基金会(OSF)规范定义了包括网卡 MAC 地址、时间戳、名字空间（Namespace）、随机或伪随机数、时序等元素。利用这些元素来生成 UUID。
UUID 是由 128 位二进制组成，一般转换成十六进制，然后用 String 表示 .

优点：本地生成，性能快
缺点：

长度过长 - UUID 太长，16 字节 128 位，通常以 36 长度的字符串表示，很多场景不适用。例如：Mysql 官方明确建议主键越短越好，36 个字符长度的 UUID 不符合要求。
信息不安全 - 基于 MAC 地址生成 UUID 的算法可能会造成 MAC 地址泄露，这个漏洞曾被用于寻找梅丽莎病毒的制作者位置。
无序

3. 利用常见的服务生成

如redis，zk等，

优点：简单、方便
缺点：依赖他们的高可用、运维成本

4. 雪花算法

Twitter（推特）的SnowFlake算法是一种著名的分布式服务器用户ID生成算法。SnowFlake算法所生成的ID是一个64bit的长整型数字，这个64bit被划分成四个部分，其中后面三个部分分别表示时间戳、工作机器ID、序列号。

4.1 原理

SnowFlakeID的四个部分，具体介绍如下：

第一位占用1 bit，其值始终是0，没有实际作用。
时间戳占用41 bit，精确到毫秒。
工作机器id 占用10 bit，最多可以容纳1024个节点。
序列号占用12 bit，最多可以累加到4095。这个值在同一毫秒同一节点上从0开始不断累加

总体来说，在工作节点达到1024顶配的场景下，SnowFlake算法在同一毫秒内最多可以生成多少个全局唯一ID呢？

同一毫秒的ID数量大致为：1024*4096=4194304，总计400多万个ID，
也就是说，在绝大多数并发场景下都是够用的。

上面的bit数分配只是一个官方的推荐，是可以微调的。比方说，如果1024的节点数不够，可以增加3个bit，扩大到8192个节点；再比方说，如果每毫秒生成4096个ID比较多，可以从12 bit减小到使用10 bit，则每毫秒生成1024个ID。这样，单个节点1秒可以生成1024*1000，也就是100多万个ID，数量也是巨大的；剩下的位数为剩余时间，还剩下40 bit的时间戳，比原来少1位，则可以持续32年。

优点：

生成ID时不依赖于数据库，完全在内存生成，高性能和高可用性。
容量大，每秒可生成几百万个ID。
ID呈趋势递增，后续插入数据库的索引树时，性能较高。

缺点：

依赖于系统时钟的一致性，如果某台机器的系统时钟回拨了，有可能造成ID冲突，或者ID乱序。

4.3 改造

4.3.1 基于时间戳

时间戳是从0开始递增的，计算41位bit可以表示多少年？69年

初始时间：idSeed，例如2018-01-01，即生成的Id为（System.currentTimeMillis() - 1577808000000L）
位数：改为50位，那么可以使用35702年

4.3.2 基于机器码

位数：普通业务场景下，5位表示就行。可以表示32台机器
机器Id的唯一性：例如，使用本机Ip（有问题的，见下文分析），一般是不变的机器序号例如：servicename.dy1 这种。

4.3.3 基于序列号

序列号的是在当前时间（精确到毫秒）下，递增的序号。

位数：使用4bit，那么1ms可以生成的数量为16个，那么一秒就是1.6W个，可以满足绝大数的业务场景

4.3.4 增加业务码

使用的场景：作为分库分表的依据、作为业务space隔离

下面以作为分表的例子展开来说明。

位数：使用5bit来表示分为32个库，放在64bit的最后5bit。
分表时，需要将旧数据库的数据导入新的数据库，这样通过Id就直接获可以取到业务code。

通过上面的改造现在的位数分配为：50 + 5 + 4 + 5 = 64位

综上所述，可以满足：35702年的使用，满足1.6w/qps，同时满足增加了业务的信息满足了扩展性。

4.4 问题和解法

机器码重复问题，入上述机器码的生成是：ip后3三位 % 32，以下两种情况会导致机器码相同，那么就可能会导致生成的ID重复。

当Ip漂移
当申请的机器资源加入集群时

解法：能表示机器节点唯一的名称就可以，例如serviceName.dy1，然后通过一个固定函数去转换成数字，方案在机器码部分

分布式ID