# 自己生成唯一ID
# 1. UUID
UUID（Universally Unique Identifier，通用唯一识别码）是按照开放软件基金会（OSF）制定的标准计算，用到了以太网卡地址、纳秒级时间、芯片 ID 码和许多可能的数字。
UUID 是由一组 32 位数的 16 进制数字所构成，是故 UUID 理论上的总数为1632=2128，约等于 3.4 x 10123。
也就是说若每纳秒产生 1 百万个 UUID，要花 100 亿年才会将所有 UUID 用完。
UUID 通常以连字号分隔的五组来显示，形式为 8-4-4-4-12，总共有 36 个字符（即 32 个英数字母和 4 个连字号）。例如：123e4567-e89b-12d3-a456-426655440000 。
JDK 从 1.5 开始在 java.util 包下提供了一个 UUID 类用来生成 UUID：
UUID uuid = UUID.randomUUID();
String uuidStr1 = uuid.toString();
String uuidStr2 = uuidStr1.replaceAll("-","");
# 2. UUID 的缺点和『好』ID 的标准
为了得到一个全局唯一 ID，很自然地就会想到 UUID 算法。但是，UUID 算法有明显的缺点：
UUID 太长了。16 个字节（128 位），通常以 36 长度的字符串表示，很多场景不适用。
非纯数字。UUID 中会出现 ABCDEF 这些十六进制的字母，因此，在数据库和代码中，自然就不能存储在整型字段或变量中。因此，在数据库中以它作为主键，建立索引的代价比较大，性能有影响。
不安全。UUID 中会包含网卡的 MAC 地址。
从 UUID 的缺点我们也能推导出一个『好』ID 的标准应该有哪些：
最好是由纯数字组成。
越短越好，最好能存进整型变量和数据库的整型字段中。
最好是递增的。即便不是严格递增，至少也应该是趋势递增。
# 3. 用毫秒时间值作 ID
最容易想到、容易实现的满足上述 3 条的数字就是系统的毫秒时间：
public class IdGenerator {
public synchronized long nextId() {
return System.currentTimeMillis();
}
}
但是使用毫秒时间值有 3 个很明显的问题：
- 系统毫秒值以 1970 年 1 月 1 号为起点，你当前获得的第一个 ID 值不是从 1 开始的。有不少 ID 值已经浪费掉了。
- 如果 1 毫秒内调用多次 nextId 方法会获得同样的 ID，即，1 毫秒只能产生一个 ID 值。
- 大多数操作系统（都是非实时操作系统）它们在毫秒级的时间上并不精确。在 10 毫秒级才有准确性。
# 4. 改进一
我们可以让返回的毫秒值不要以计算机公元元年为起点，就能解决第一个问题：
public class IdGenerator {
// private static final long epoch = 1577836800000L;
private static final long epoch = Instant.parse("2020-01-01T00:00:00Z").toEpochMilli();
public synchronized long nextId() {
return System.currentTimeMillis() - epoch;
}
}
上述改进就是以 2020 年 1 月 1 号作为时间毫秒值的起点，这样浪费掉的 ID 就没有那么多了。
# 5. 改进二
对于同毫秒内的 ID 重复问题，我们可以在 ID 的末端留出若干位作为同毫秒内的计数累加值，同毫秒内的调用 nextId() 方法所返回的 ID 值，前一段是毫秒值，是相同的，而后一部分的值则是不同的、累加值。
当然，代价就是毫秒值的上限会降低，因为要『让出』几位出来。
例如，如果空出低 8 位，只『剩下』long 的高 56 位，这个毫秒值用尽大概需要 2284931 年：
(1L << 56) / (1000L * 60 * 60 * 24 * 365) = 2284931
示例：
public class IdGenerator {
/**
* 开始时间截 (2015-01-01)
*/
//private static final long epoch = 1577836800000L;
private static final long epoch = Instant.parse("2020-01-01T00:00:00Z").toEpochMilli();
/**
* 上次生成 ID 的时间截
*/
private long lastTimestamp = -1L;
private long sequence = 0L;
// 所占位数、位移、掩码/极大值
private static final long sequenceBits = 8L;
private static final long sequenceShift = 0L;
private static final long sequenceMask = ~(-1L << sequenceBits);
private static final long timestampBits = 41L;
private static final long timestampLeftShift = sequenceBits;
private static final long timestampMask = ~(-1L << timestampBits);
public synchronized long nextId() {
long timestamp = timeGen();
// 如果当前时间小于上一次 ID 生成的时间戳，说明系统时钟回退过，这个时候应当抛出异常。
// 出现这种原因是因为系统的时间被回拨，或出现闰秒现象。
// 你也可以不抛出异常，而是调用 tilNextMillis 进行等待
if (timestamp < lastTimestamp) {
throw new RuntimeException(
String.format("Clock moved backwards. Refusing to generate id for %d milliseconds", lastTimestamp - timestamp));
}
// 如果是同一时间生成的，则进行毫秒内序列
if (lastTimestamp == timestamp) {
// 相同毫秒内，序列号自增
sequence = (sequence + 1) & sequenceMask;
// 毫秒内序列溢出，即，同一毫秒的序列数已经达到最大
if (sequence == 0) {
// 阻塞到下一个毫秒,获得新的时间戳
timestamp = tilNextMillis(lastTimestamp);
}
}
// 时间戳改变，毫秒内序列重置
else {
sequence = 0L;
}
// 将当前生成的时间戳记录为『上次时间戳』。『下次』生成时间戳时要用到。
lastTimestamp = timestamp;
// 移位并通过或运算拼到一起组成 64 位的 ID
return ((timestamp - epoch) << timestampLeftShift) // 时间戳部分
| sequence; // 序列号部分
}
/**
* 阻塞到下一个毫秒，直到获得新的时间戳
*
* @param lastTimestamp 上次生成ID的时间截
* @return 当前时间戳
*/
protected long tilNextMillis(long lastTimestamp) {
long timestamp = timeGen();
while (timestamp <= lastTimestamp) {
timestamp = timeGen();
}
return timestamp;
}
/**
* 返回以毫秒为单位的当前时间
*
* @return 当前时间(毫秒)
*/
protected long timeGen() {
return System.currentTimeMillis();
}
}
# 6. 改进三（可选改进）
public synchronized long nextId() {
long timestamp = timeGen();
// 如果当前时间小于上一次 ID 生成的时间戳，说明系统时钟回退过，这个时候应当抛出异常。
// 出现这种原因是因为系统的时间被回拨，或出现闰秒现象。
// 你也可以不抛出异常，而是调用 tilNextMillis 进行等待
if (timestamp < lastTimestamp) {
throw new RuntimeException(
String.format("Clock moved backwards. Refusing to generate id for %d milliseconds", lastTimestamp - timestamp));
}
// 如果是同一个 10 mSecs 生成的，则进行毫秒内序列
if (lastTimestamp / 10 == timestamp / 10) {
// 相同毫秒内，序列号自增
sequence = (sequence + 1) & sequenceMask;
// 毫秒内序列溢出，即，同一毫秒的序列数已经达到最大
if (sequence == 0) {
// 阻塞到下一个毫秒,获得新的时间戳
timestamp = tilNext10Millis(lastTimestamp);
}
}
// 时间戳改变，毫秒内序列重置
else {
sequence = 0L;
}
//System.out.println(sequence);
// 将当前生成的时间戳记录为『上次时间戳』。『下次』生成时间戳时要用到。
lastTimestamp = timestamp;
// 移位并通过或运算拼到一起组成 64 位的 ID
return (((timestamp - epoch)/10) << timestampLeftShift) // 时间戳部分
| sequence; // 序列号部分
//return timestamp + ": " + (timestamp - epoch) / 10 + "-" + sequence; // 序列号部分
}
/**
* 阻塞到下一个 10 毫秒，直到获得新的时间戳
*
* @param lastTimestamp 上次生成ID的时间截
* @return 当前时间戳
*/
protected long tilNext10Millis(long lastTimestamp) {
long timestamp = timeGen();
while (timestamp / 10 <= lastTimestamp / 10) {
timestamp = timeGen();
}
return timestamp;
}
/**
* 返回以毫秒为单位的当前时间
* @return 当前时间(毫秒)
*/
protected long timeGen() {
return System.currentTimeMillis();
}
public static void main(String[] args) {
IdGenerator1 idGenerator = new IdGenerator1();
for (int i = 0; i < 10000; i++) {
System.out.println(idGenerator.nextId());
// idGenerator.nextId();
}
}