golang-uuidv4

源码解读 github.com/satori/go.uuid

从头开始跟踪

u2 := uuid.NewV4()
NewV4 函数调用

// NewV4 returns random generated UUID.
func (g *generator) NewV4() UUID {
u := UUID{}
// 长度为16的 byte数组 -> 16个8bit
g.safeRandom(u[:])
u.SetVersion(V4)
u.SetVariant(VariantRFC4122)
return u
}

随机数填充

func (g *generator) safeRandom(dest []byte) {
    // 随机数充满dest
    if _, err := rand.Read(dest); err != nil {
        panic(err)
    }
}

设置版本号相关 bit

// SetVersion sets version bits.
func (u *UUID) SetVersion(v byte) {
	//0x0f == 0000 1111 截取后面4bits
	// |v << 4 在特定位上置1根据version
	//u[6] == 4bits(version) + 12bits(time_hi)
	u[6] = (u[6] & 0x0f) | (v << 4)
}

设置变体(有多个标准,相当于标准变体标识)

// SetVariant sets variant bits.
func (u *UUID) SetVariant(v byte) {
	switch v {
	case VariantNCS:
		u[8] = (u[8]&(0xff>>1) | (0x00 << 7))
    case VariantRFC4122:
    	// 0xff >>2 == 0011 1111
	    // 0x02 <<6 == 1000 0000
		// 把u[8] 变成 10 + 6bits((bits 8 through 13) of the clock sequence)
		u[8] = (u[8]&(0xff>>2) | (0x02 << 6))
	case VariantMicrosoft:
		u[8] = (u[8]&(0xff>>3) | (0x06 << 5))
	case VariantFuture:
		fallthrough
	default:
		u[8] = (u[8]&(0xff>>3) | (0x07 << 5))
	}
}

uuid 表现结构, 变成 16 进制字符并插入 -

func (u UUID) String() string {
	buf := make([]byte, 36)
	// 这个lib只输出 36长度格式的Canonical uuid
	hex.Encode(buf[0:8], u[0:4])
	buf[8] = '-'
	hex.Encode(buf[9:13], u[4:6])
	buf[13] = '-'
	hex.Encode(buf[14:18], u[6:8])
	buf[18] = '-'
	hex.Encode(buf[19:23], u[8:10])
	buf[23] = '-'
	hex.Encode(buf[24:], u[10:])

	return string(buf)
}

const hextable = "0123456789abcdef"
func Encode(dst, src []byte) int {
	for i, v := range src {
        // 把一个byte 的前4bit 和后4bit分别变成一个16进制字符
		dst[i*2] = hextable[v>>4]
		dst[i*2+1] = hextable[v&0x0f]
	}

	return len(src) * 2
}

总结

v4 版本是基于随机数,然后对对应的版本和变体设置. 并转化为 16 进制字符后的结果. 由于 uuid 是 128bit, 长度比较长,所以使得随机数的碰撞几率不会很高.但依然无法让唯一性完全成立.

其他策略

Setup used by MongoDB[1]:
[ time, machine_id, process_id, counter ]
Twitter Snowflake[2] use something similar to the above.
Cassandra[3] use something like this:
[ time, version, variant, counter, node_id ]

From PingCap:

TiDB 的约束更强一点，需要不重复且单调递增
所以这边是有三个 pd-server 来负责发号，号 = 物理 timestamp + 逻辑时钟
前 48 位是物理时间戳，后 16 位是一个逻辑时钟（就是一个计数器）
每隔 1s 将物理时间通过 raft 复制到所有 pd-server 中
即使 master 挂了，新的 master 被选举出来，也能保证 sleep(1s) 后，一定能分配出更大且没有交集的号

PingCap 的基本思路我觉得刨除 master/slave 的集群外. uuid 生成的主要是
timestamp+counter(逻辑时钟)
首先他们是 DB, 所以肯定希望 timestamp 来做前面部分,有利于排序索引
另外独立的 timestamp 对于集中的生成 uuid 可能无法满足需求,粒度可能太大容易出现重复, +counter 主要就看 counter 是怎么针对并发的请求来做处理的. 比如加锁来避免更细粒度的冲突(没有细问)

参考

https://www.ietf.org/rfc/rfc4122.txt
https://news.ycombinator.com/item?id=10606910
https://golang.org/pkg/crypto/rand/#Read
https://en.wikipedia.org/wiki//dev/random