xUID 三种唯一ID生成

GUID-UUID-NUID

开发项目中可能经常会使用到唯一标识符(Unique Identifier),特别是设计一些并发并行的应用系统,之前在Github上看到了一些生成算法库,在此做些学习记录,以备或需。

UUID


第一种UUID,这个就不用多说了,很多语言标准库里面都提供了生成函数,Go的标准库里面没有,但是万能的开源社区提供了多个项目,用来实现符合RFC4122规范的UUID

我看了两个项目:

前面那个提供了NewV3NewV4NewV5三个版本的UUID生成函数;后面那个提供了五种版本的UUID生成函数以及丰富的检验、序列化/反序列化、编码解码等函数,更有实用价值。关于UUID五种版本规范,可以百度谷歌,这里提供 SegmentFault上一个回答的链接 。源码大致浏览了一下,根据不同版本选择一些参与计算的要素,例如:时间MAC地址名字空间MD5SHA1等,对RFC规范不熟悉,具体算法实现不仔细看了,需要的时候用就可以了。


snowflake


这个算法是Twitter提出来并开源的,具体可以参见:https://github.com/twitter/snowflake/tree/snowflake-2010 。Github上Go语言实现这个算法的项目也很多,我选择这个项目学习了一下:

网上对这个算法的分析文章也很多,贴一篇不错的:理解分布式id生成算法SnowFlake

这个算法生成的ID是一个64位整数,原理是某个时间点(2^41^-1毫秒)、某台主机(1024个节点),按序列号(最大4096个)生成一个数。比如如果用作交易流水号,也就是说一毫秒内某台节点受理并发交易不超过4096笔,就不会有重复的可能,还是很强劲的。

简单贴下实现的部分源码:

const (
	CEpoch         = 1474802888000
	CWorkerIdBits  = 10 // Num of WorkerId Bits
	CSenquenceBits = 12 // Num of Sequence Bits

	CWorkerIdShift  = 12
	CTimeStampShift = 22

	CSequenceMask = 0xfff // equal as getSequenceMask()
	CMaxWorker    = 0x3ff // equal as getMaxWorkerId()
)
// +---------------+----------------+----------------+
// |timestamp(ms)42  | worker id(10) | sequence(12)	 |
// +---------------+----------------+----------------+
// NewId Func: Generate next id
func (iw *IdWorker) NextId() (ts int64, err error) {
	iw.lock.Lock()
	defer iw.lock.Unlock()
	ts = iw.timeGen()
	if ts == iw.lastTimeStamp {
		iw.sequence = (iw.sequence + 1) & CSequenceMask
		if iw.sequence == 0 {
			ts = iw.timeReGen(ts)
		}
	} else {
		iw.sequence = 0
	}

	if ts < iw.lastTimeStamp {
		err = errors.New("Clock moved backwards, Refuse gen id")
		return 0, err
	}
	iw.lastTimeStamp = ts
	ts = (ts-CEpoch)<<CTimeStampShift | iw.workerId<<CWorkerIdShift | iw.sequence
	return ts, nil
}


NUID


最后,看一个我比较喜欢的UID生成算法,它是最近才加入CNCF组织的NATs系列项目中使用到的一种唯一标识符算法库,生成速度极快,重复可能极其低。

这个被命名为NUID的算法生成的是一个22字节的数字大小写字母字符串,因此生成范围可能性是62^22^,生成速度我老Mac笔记本大约是60ns~80ns左右一个。2000万只需一点几秒,真是极速爽啊。

看一下算法规则和源码:

const (
	digits   = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"
	base     = 62
	preLen   = 12
	seqLen   = 10
	maxSeq   = int64(839299365868340224) // base^seqLen == 62^10
	minInc   = int64(33)
	maxInc   = int64(333)
	totalLen = preLen + seqLen
)
func (n *NUID) Next() string {
	// Increment and capture.
	n.seq += n.inc
	if n.seq >= maxSeq {
		n.RandomizePrefix()
		n.resetSequential()
	}
	seq := n.seq

	// Copy prefix
	var b [totalLen]byte
	bs := b[:preLen]
	copy(bs, n.pre)

	// copy in the seq in base36.
	for i, l := len(b), seq; i > preLen; l /= base {
		i -= 1
		b[i] = digits[l%base]
	}
	return string(b[:])
}

算法是12字节随机前缀字符串+10字节序列号字符串,两个字符串都是先由随机数或者随机数+随机递增数产生后,再逐数字位随机读取再转换成数字大小写字母。算法很精炼,可以仔细阅读源码研究。

另外,项目源码中还有生成NUID的测试和性能测试程序,还有唯一性检测程序,可以测试和检验。