1. 应用场景和需求

在互联网应用开发中，海量数据需要分布式存储，不论是用分库分表还是nosql存储，数据查询和计算时经常会需要唯一ID。

单纯的生成全局ID并不是什么难题，但是生成的ID通常要满足分片的一些要求¹：

• 不能有单点故障。
• 以时间为序，或者ID里包含时间。这样一是可以少一个索引，二是冷热数据容易分离。
• 可以控制ShardingId。比如某一个用户的文章要放在同一个分片内，这样查询效率高，修改也容易。
• 不要太长，最好64bit。使用long比较好操作。

2. 常见解决方案汇总

2.1 GUID

GUID生成的是长度为32的16进制格式的字符串，加上4个分隔符号，长度是36个字符。如果回退为byte数组共16个byte元素，即GUID是一个128bit长的数字，一般用16进制表示。

算法的核心思想是结合机器的网卡、当地时间、一个随即数来生成GUID。

从理论上讲，如果一台机器每秒产生10000000个GUID，则可以保证（概率意义上）3240年不重复

优点：

• 本地生成ID，不需要进行远程调用，时延低

• 扩展性好，基本可以认为没有性能上限

缺点：

• 无法保证趋势递增

• GUID过长，往往用字符串表示，作为主键建立索引查询效率低，常见优化方案为“转化为两个uint64整数存储”或者“折半存储”（折半后不能保证唯一性）

2.2 基于数据库自增自动的集群方案

关系型数据库的表字段都提供了自增类型，比如mysql的auto_increment，可以利用这个特性来实现生成ID功能。Flicker在解决全局ID生成方案里就采用了MySQL自增长ID的机制（auto_increment + replace into + MyISAM）。

先在mysql里创建表，定义一个 id bigint(20) unsigned NOT NULL auto_increment 字段 ，insert一条记录，使用SELECT LAST_INSERT_ID();就能取到新ID。这只是在单台数据库上实现。

从高可用角度考虑，为避免单点故障，Flicker启用了两台数据库服务器来生成ID，通过区分auto_increment的起始值和步长来生成奇偶数的ID。最后，在客户端只需要通过轮询方式取ID就可以了。

优点：

• 充分借助数据库的自增ID机制，提供高可靠性，生成的ID有序。

缺点：

• 占用两个独立的数据库实例，有些浪费资源，成本较高。

2.3 基于redis的分布式ID生成器

这个方案类似twitter的snowflake算法，不过是把取时间和毫秒内的增长ID的计算放在了redis中。

redis的EVAL，EVALSHA命令用来运行lua脚本。利用redis的lua脚本执行功能，在每个节点上通过lua脚本生成唯一ID。

利用lua脚本，返回的是一个四元组（second秒, microSecond毫秒, partition分片id, seq毫秒内的自增id），其中redis的TIME命令，可以取得redis服务器上的秒数和微秒数，逻辑分片ID是预置好的，毫秒内的自增id可以用INCR获取。

客户端处理这个四元组，生成64位int类型的ID。

比如GTM时间 Fri Mar 13 10:00:00 CST 2015 ，它的距1970年的毫秒数是 1426212000000，假定分片ID是53，自增长序列是4，则生成的ID是：

((second * 1000 + microSecond / 1000) << (12 + 10)) + (shardId << 10) + seq;

5981966696448054276 = 1426212000000 << 22 + 53 << 10 + 41

2.4 twitter的snowflake算法

twitter在把存储系统从MySQL迁移到Cassandra的过程中由于Cassandra没有顺序ID生成机制，于是自己开发了一套全局唯一ID生成服务：Snowflake。 为了满足Twitter每秒上万条消息的请求，每条消息都必须分配一条唯一的id，这些id还需要一些大致的顺序（方便客户端排序），并且在分布式系统中不同机器产生的id必须不同。 代码参考²。

最高位是符号位，始终为0。接下来依次是：41位的时间序列（精确到毫秒，41位的长度可以使用69年）；10位的机器标识（10位的长度最多支持部署1024个节点）；12位的计数顺序号（12位的计数顺序号支持每个节点每毫秒产生4096个ID序号）。

优点：

• 高性能，低延迟；
• 独立的应用；按时间有序。

缺点：

• 需要独立的开发和部署。

3. snowflake算法详解

3.1 一个golang实现

下面是一个golang实现的snowflake算法³的核心实现。

// Generate creates and returns a unique snowflake ID
func (n *Node) Generate() ID {

	//加锁
	n.Lock()

	//获取当前毫秒
	now := time.Now().UnixNano() / 1000000

	if n.time == now {
		//毫秒内自增
		n.step = (n.step + 1) & stepMask

		//溢出
		if n.step == 0 {
			//时间增长
			for now <= n.time {
				now = time.Now().UnixNano() / 1000000
			}
		}
	} else {
		//新时间，自增bit块初始为0
		n.step = 0
	}

	n.time = now

	//拼接生成int64 ID
	/*
		Epoch等于2006-03-21:20:50:14 GMT
		var Epoch int64 = 1288834974657
	*/
	r := ID((now-Epoch)<<timeShift |
		(n.node << nodeShift) |
		(n.step),
	)

	n.Unlock()
	return r
}

3.2 snowflake算法变种

3.2.1 工作机器id

严格意义上来说这个bit段的使用可以是进程级，机器级的话你可以使用MAC地址来唯一标示工作机器，工作进程级可以使用IP+Path来区分工作进程。 如果工作机器比较少，可以使用配置文件来设置这个id是一个不错的选择，如果机器过多可以从数据库auto_increment字段中读取id。

3.2.2 自定义bit块

可以根据需要增加bit块，各部分的位数可以根据需要增加。 比如：如果不需要部署1024台机器那么多，所以可以减少机器码；如果做成一个公司通用服务，要考虑接入多种业务后，产生的ID不冲突，需要增加业务码进行区分，同时为了保证服务能支持接入一定数量的业务，需要为业务码保留足够位数。

3.3 注意事项

• 自增码在多线程环境中，需要加锁，避免同一毫秒内产生冲突

• 多台机器上部署时，要保证机器的时间一致（需要用到NTP保证系统时间精确）

参考文献：