全局唯一ID设计方案

全局唯一ID设计方案在分布式系统中，经常需要使用全局唯一ID查找对应的数据。产生这种ID需要保证系统全局唯一，而且要高性能以及占用相对较少的空间。

全局唯一ID在数据库中一般会被设成主键，这样为了保证数据插入时索引的快速建立，还需要保持一个有序的趋势。

这样全局唯一ID就需要保证这两个需求：
全局唯一
趋势有序
全局ID产生的几种方式

数据库自增
当服务使用的数据库只有单库单表时，可以利用数据库的auto_increment来生成全局唯一递增ID.

优势：
简单，无需程序任何附加操作
保持定长的增量
在单表中能保持唯一性

劣势：
高并发下性能不佳，主键产生的性能上限是数据库服务器单机的上限。
水平扩展困难，在分布式数据库环境下，无法保证唯一性。

UUID
一般的语言中会自带UUID的实现，比如Java中UUID方式UUID.randomUUID().toString()，可以通过服务程序本地产生，ID的生成不依赖数据库的实现。

优势：
本地生成ID，不需要进行远程调用。
全局唯一不重复。
水平扩展能力非常好。

劣势：
ID有128 bits,占用的空间较大，需要存成字符串类型，索引效率极低。
生成的ID中没有带Timestamp，无法保证趋势递增

Twitter Snowflake

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

根据snowflake算法的思想，我们可以根据自己的业务场景，产生自己的全局唯一ID。因为Java中long类型的长度是64bits，所以我们设计的ID需要控制在64bits。

产生唯一ID的Java代码：有修改

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

Java代码

package com.pandy.framework.core.id;

import java.security.SecureRandom;

/**

* Created by pandy on 16-6-27.

* <p/>

* 项目名称: workspace * 功能说明:

* snowflake是twitter开源的分布式ID生成算法，其核心思想是：

* 产生一个long型的ID，使用其中41bit作为毫秒数，10bit作为机器编号，12bit作为毫秒内序列号。

* 这个算法单机每秒内理论上最多可以生成1000*(2^12)个，也就是大约400W的ID，完全能满足业务的需求。

* 根据snowflake算法的思想，我们可以根据自己的业务场景，产生自己的全局唯一ID。

* 因为Java中long类型的长度是64bits，所以我们设计的ID需要控制在64bits。

* 比如我们设计的ID包含以下信息：

* 创建者: Pandy,

* 邮箱: panyongzheng@163.com, 1453261799@qq.com

* 版权:

* 官网:

* 创建日期: 16-6-27.

* 创建时间: 下午10:59.

* 修改历史:

* -----------------------------------------------

/**

* 创建的时候： workerId 可以用于标记表的序号(表少于1024个表的情况下)，

* 或者模块的序号(表大于1024个表的情况下，按照表属于的模块来定义这个序号)，

* 避免重复ID出现

* 自定义 ID 生成器 ID 生成规则: ID长达 64 bits

public class CustomUUID {

// 基准时间

private long twepoch = 1288834974657L; // Thu, 04 Nov 2010 01:42:54 GMT

// 区域标志位数

private final static long regionIdBits = 3L;

// 机器标识位数

private final static long workerIdBits = 10L;

// 序列号识位数

private final static long sequenceBits = 10L;

// 区域标志ID最大值

private final static long maxRegionId = -1L ^ (-1L << regionIdBits);

// 机器ID最大值

private final static long maxWorkerId = -1L ^ (-1L << workerIdBits);

// 序列号ID最大值

private final static long sequenceMask = -1L ^ (-1L << sequenceBits);

// 机器ID偏左移10位

private final static long workerIdShift = sequenceBits;

// 业务ID偏左移20位

private final static long regionIdShift = sequenceBits + workerIdBits;

// 时间毫秒左移23位

private final static long timestampLeftShift = sequenceBits + workerIdBits + regionIdBits;

private static long lastTimestamp = -1L;

private long sequence = 0L;

private final long workerId;

private final long regionId;

//workerId>=0 && workerId<1024

//regionId>=0 && regionId<8

public CustomUUID(long workerId, long regionId) {

// 如果超出范围就抛出异常

if (workerId > maxWorkerId || workerId < 0) {

throw new IllegalArgumentException("worker Id can't be greater than %d or less than 0");

}

if (regionId > maxRegionId || regionId < 0) {

throw new IllegalArgumentException(

"datacenter Id can't be greater than %d or less than 0");

}

this.workerId = workerId;

this.regionId = regionId;

System.out.println("区域标志ID最大值=" + maxRegionId + ", 机器ID最大值=" + maxWorkerId + ", 序列号ID最大值=" + sequenceMask);

}

public CustomUUID(long workerId) {

// 如果超出范围就抛出异常

if (workerId > maxWorkerId || workerId < 0) {

throw new IllegalArgumentException("worker Id can't be greater than %d or less than 0");

}

this.workerId = workerId;

this.regionId = 0;

System.out.println("区域标志ID最大值=" + maxRegionId + ", 机器ID最大值=" + maxWorkerId + ", 序列号ID最大值=" + sequenceMask);

}

public long generate() {

return this.nextId(false, 0);

}

/**

* 实际产生代码的

* @param isPadding

* @param busId

* @return

private synchronized long nextId(boolean isPadding, long busId) {

long timestamp = timeGen();

long paddingnum = regionId;

if (isPadding) {

paddingnum = busId;

}

if (timestamp < lastTimestamp) {

try {

throw new Exception("Clock moved backwards. Refusing to generate id for "

+ (lastTimestamp - timestamp) + " milliseconds");

} catch (Exception e) {

e.printStackTrace();

}

// 如果上次生成时间和当前时间相同,在同一毫秒内

if (lastTimestamp == timestamp) {

// sequence自增，因为sequence只有10bit，所以和sequenceMask相与一下，去掉高位

sequence = (sequence + 1) & sequenceMask;

// 判断是否溢出,也就是每毫秒内超过1024，当为1024时，与sequenceMask相与，sequence就等于0

if (sequence == 0) {

// 自旋等待到下一毫秒

timestamp = tailNextMillis(lastTimestamp);

}

} else {

// 如果和上次生成时间不同,重置sequence，就是下一毫秒开始，sequence计数重新从0开始累加,

// 为了保证尾数随机性更大一些,最后一位设置一个随机数

sequence = new SecureRandom().nextInt(10);

}

lastTimestamp = timestamp;

return ((timestamp - twepoch) << timestampLeftShift) | (paddingnum << regionIdShift)

| (workerId << workerIdShift) | sequence;

}

// 防止产生的时间比之前的时间还要小（由于NTP回拨等问题）,保持增量的趋势.

private long tailNextMillis(final long lastTimestamp) {

long timestamp = this.timeGen();

while (timestamp <= lastTimestamp) {

timestamp = this.timeGen();

}

return timestamp;

}

// 获取当前的时间戳

protected long timeGen() {

return System.currentTimeMillis();

}

public static void main(String args[]) {

CustomUUID uuid1 = new CustomUUID(1l, 0);

CustomUUID uuid2 = new CustomUUID(2l, 0);

for (int i = 0; i < 100; i++) {

System.out.println(uuid1.nextId(false, 0));

System.out.println(uuid2.nextId(false, 0) + "-");

}

使用自定义的这种方法需要注意的几点：

为了保持增长的趋势，要避免有些服务器的时间早，有些服务器的时间晚，需要控制好所有服务器的时间，而且要避免NTP时间服务器回拨服务器的时间。
在跨毫秒时，序列号总是归0，会使得序列号为0的ID比较多，导致生成的ID取模后不均匀，所以序列号不是每次都归0，而是归一个0到9的随机数。
使用这个CustomUUID类，最好在一个系统中能保持单例模式运行。
原文地址：http://www.androidchina.net/4744.html

不静之心

全局唯一ID设计方案

发表评论取消回复

访问信息

功能

近期评论

不静之心

全局唯一ID设计方案

发表评论 取消回复

访问信息

功能

近期评论

发表评论取消回复