常见的统一标识符算法(UUID、NUID、Snowflake)

2019-02-28 算法 笔记 #UUID #NUID #Snowflake #Twitter #Leaf
更新日志
2019-03-08 添加美团分布式ID生成系统: Leaf 的相关内容

在日常开发过程中,肯定少不了接触“统一标识符”,一般我们都直接使用各个语言标准库中的实现,例如在Java中可以使用java.util.UUID.randomUUID()来获取。使用UUID的场景各不相同,那该怎么选择统一标识符算法呢?

UUID

通用唯一识别码(英语:Universally Unique Identifier,UUID),是用于计算机体系中以识别信息数目的一个128位标识符,还有相关的术语:全局唯一标识符(GUID)。 根据标准方法生成,不依赖中央机构的注册和分配,UUID具有唯一性,这与其他大多数编号方案不同。重复UUID码概率接近零,可以忽略不计。 - 《通用唯一识别码》 - Wikipedia

UUID共36位(32个字符+4个连接符号),格式为: xxxxxxxx-xxxx-Mxxx-Nxxx-xxxxxxxxxxxx, M表示版本,N表示变体。变体是为了保持向后兼容以及能应对未来的变更,在RFC4122标准中有明确定义了变体的取值和作用:

The following table lists the contents of the variant field, where the letter “x” indicates a “don’t-care” value.

Msb0 Msb1 Msb2 Description
0 x x Reserved, NCS backward compatibility.
1 0 x The variant specified in this document.
1 1 0 Reserved, Microsoft Corporation backward compatibility
1 1 1 Reserved for future definition.

UUID目前一共5个版本,每个版本的实现的方式不同,具体每个版本的定义建议看:《UUID版本》- Wikipedia

使用的最多的应该是版本4,例如在Java中的java.util.UUID.randomUUID()就是一个版本4的实现,在多数情况下我们都直接使用该方法获取UUID。

各版本的特点:

适用场景

通常我们建议使用UUID来标识对象或持久化数据,但以下情况最好不使用UUID:

引用至:《UUID在用户跟踪的妙用》- 江邊望海的笔记

NUID

NUID是CNCF组织下NATS项目的一个UID库(从commit来看,应该是2018-03-17才变更到NATS下面的)。项目主页上介绍很简单“A highly performant unique identifier generator.”,看样子在性能方面是极有信心的。该算法的实现代码极少,包含注释一共才135行。

NUID使用62个字符(0-9a-zA-Z)生成22位的结果,结果分为2部分:

主要逻辑有:

  1. 使用真随机数或者当前时间的纳秒作为伪随机数的随机种子
  2. 前12位使用真随机数
  3. 后10位使用伪随机数(使用对伪随机数 /= base 获取到下一次的伪随机数,然后对数进行取余操作获取具体的字符)

前12位的真随机数:

// Generate a new prefix from crypto/rand.
// This call *can* drain entropy and will be called automatically when we exhaust the sequential range.
// Will panic if it gets an error from rand.Int()
func (n *NUID) RandomizePrefix() {
  var cb [preLen]byte
  cbs := cb[:]
  if nb, err := rand.Read(cbs); nb != preLen || err != nil {
    panic(fmt.Sprintf("nuid: failed generating crypto random number: %v\n", err))
  }
  
  for i := 0; i < preLen; i++ {
    n.pre[i] = digits[int(cbs[i])%base]
  }
}

后10位的伪随机数:

// Generate the next NUID string.
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[:])
}

生成的结果示例: M4bZr7xyO3toV6T6iC7lWB

Benchmark结果:

nuid benchmark

适用场景

Snowflake

Snowflake(雪花算法)是Twitter推出的在分布式环境生成唯一ID的算法。

雪花算法的组成格式如下(1+41+10+12 = 64):

Snowflake

关于雪花算法的文章很多,本文最后贴出了相关文章,我就不再赘述了。以下主要说说雪花算法的特点:

基于以上特点,Snowflake的适用场景很明确:

需要注意的是:由于中间主要的41位是根据系统时钟生成的,如果某机器的系统时钟发生了调整(回拨),那么可能导致生成重复的ID。

Leaf

Leaf是美团开源的分布式UID生成服务,支持两种生成ID的模式:

  1. 号段模式(segment,基于数据库)
  2. 雪花算法模式(Snowflake)

其中,基于Snowflake的实现使用了Zookeeper来尝试避免因系统时钟回拨导致可能生成重复ID的问题,具体逻辑如下图所示:

美团 - Leaf

关于美团Leaf以及其他UID方案的优缺点可以看看《Leaf——美团点评分布式ID生成系统》- 美团技术团队

相关引用

UUID

NUID

Snowflake

Leaf

Go




文章作者:eightpigs
创作时间:2019-02-28
更新时间: 2019-03-08
许可协议:CC by-nc-nd 4.0