再聊 UUID，来自实战的剖析（分时图战法实战剖析电子书）

这文章是因为过去使用大量的 UUID，但 UUID 有个致命的缺点是，它实在太长了，128 bits 用 Hex 表示法，至少要 32 个字元，如果再加上分隔符号，就要 36 个字元，把这放在面向使用者者的页面上，应该不会有人会记得住吧！但 UUID 就真的只能这么长吗？其实是可以再短一点的。没想到在《UUID的作用？》之后，有机会再来聊聊怎么缩短 UUID 吧。

刚刚才说到目前的表示法是 Hex (十六进制)，也就是讲 128 bits 每 4 bits 为一组，然后用 0 到 F，分别表示 0 (0000) 到 15 (1111)，这也就是为什么长度会是 32 个字元 (128 / 4)，所以想要更短，最简单的做法是 5 bits 为一组用 32 个字母来表示，或是用 6 bits 为一组用 64 个字母来表示，这时长度也就可以缩短到 26 (ceil(128 / 5)) 字元或 22 (ceil(128 / 6)) 字元了。用 7 bits 一组也不是不行，只是找到易读的 128 个字母就是件困难的事了。

这次文章的范例和往常用 Java 不同，是用 Kotlin，但我还是尽量让程式码简单一点。首先，我们先替既有的 Java 类别 UUID 加上一个 extension method [关于 extension 我个人比较喜欢 Swift 的写法]，能给定一组字母，然后用这组字母来编码 UUID。

fun UUID.shortId(characters: String): String {
  return ""
}

由于刚刚提到，是用几个 bits 为一组 (事实上这非强制性，只是在解释上比较方便)，因此我们先检查给定的字母数量是否为 2 的次方，于是第一个版本就出来了，还没有功能，单纯检查输入是否合法，另外 Kotlin 支援预设参数，我顺便加上由 0 到 9，大小写的英文字母及两个特殊符号的字母组合。

private const val defaultCharacters: String = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ_-"

private fun Double.isInteger(): Boolean {
  return this.isFinite() && this.compareTo(ceil(this)) == 0
}

fun UUID.shortId(characters: String = defaultCharacters): String {
  val exponent = log2(characters.length.toDouble());
  if (!exponent.isInteger()) {
    throw IllegalArgumentException("must have 2 ^ n characters")
  }
  return ""
}

然后写个测试，验证一下是否真的会抛出例外：

@Test
fun testIllegalCharacters() {
  val uuid = randomUUID()
  assertThrows<IllegalArgumentException> {
    uuid.shortId("0123456789")
  }
}

接着，我们是希望变短，而不是变长，因此字母不该小于 2 ^ 4 个，因此再加上一个指数不得小于 4 的限制：

fun UUID.shortId(characters: String = defaultCharacters): String {
  val exponent = log2(characters.length.toDouble());
  if (!exponent.isInteger()) {
    throw IllegalArgumentException("must have 2 ^ n characters")
  }
  if (exponent <= 4) {
    throw IllegalArgumentException("less than 16 characters")
  }
  return ""
}

然后再补上一个测试案例：

@Test
fun testInsufficientCharacters() {
  val uuid = randomUUID()
  assertThrows<IllegalArgumentException> {
    uuid.shortId("0123456789abcde")
  }
}

到这边，我个人是觉得这些检查佔据太多行数，抽象层级和接下来要专注的内容不同，所以直接将验证的逻辑抽成一个函式，这时主函式就清爽多了。如果要再增加对参数检查的逻辑 (例如，不可有重复的字母)，也是写在刚抽出去的函式中，增加可读性。

fun UUID.shortId(characters: String = defaultCharacters): String {
  val exponent = assertCharactersSize(characters)
  return ""
}

private fun assertCharactersSize(characters: String): Int {
  val exponent = log2(characters.length.toDouble());
  if (!exponent.isInteger()) {
    throw IllegalArgumentException("must have 2 ^ n characters")
  }
  if (exponent < 4) {
    throw IllegalArgumentException("less than 16 characters")
  }
  return exponent.toInt()
}

有一点二进制基础的大概都知道将 10 进制的数字转换成 2 进制，就是一直除以 2 取余数 (或是用位元运算往右 shift 取被 shift 的那个 bit)，同理，假设是 5 bits 一组，那就是取 32 的余数 (或是往右 shift 5 bits)。

但 UUID 长达 128 bits，多数语言是没有内建型别可以表达这么长的数，Java 的 long 也才 64 bits (事实上 UUID 内部就是用两个 long 表达)，那怎么把个 long 一起取余数或是 shift 呢？这时候可以靠 BigInteger 了，有个建构子可以从指定的 ByteArray 建立 BigInteger 物件。

因此，接下来就是将 UUID 转成 ByteArray，因此新增一个 toBytes 的extension method，由于 Java 没有正整数的型别，所以 UUID 类别的两个成员 mostSignificantBits 和 leastSignificantBits 都有可能是负数，因此像 BigInteger("${mostSignificantBits}${leastSignificantBits}") 这样的写法是会出错的。这裡采用保守的作法，建立一个 17 bytes 的 buffer，然后依序放入 0、 mostSignificantBits 和 leastSignificantBits，第一个 0 确保整个 17 bytes 被视为正整数处理。

再来就是很单纯地取余数，拿余数查表，将查到的字母接在 buffer 的后面，最后记得将整个字串反转 (因为计算过程是将低位串到高位)。BigInteger 其实支援左移或是右移等运算，速度应该比较快，但不熟位元运算的人阅读起来可能需要花点时间，所以这裡还是用取余数的方式。

private const val defaultCharacters: String = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ_-"

private fun UUID.toBytes(): ByteArray {
  // plus one byte (0) to become positive value
  val buffer = ByteBuffer.allocate((Long.SIZE_BYTES * 2) + 1)
  buffer.put(0)
  buffer.putLong(this.mostSignificantBits)
  buffer.putLong(this.leastSignificantBits)
  return buffer.array()
}

fun UUID.shortId(characters: String = defaultCharacters): String {
  val exponent = assertCharactersSize(characters)
  val lookupTable = characters.toCharArray()
  val base = 2.toDouble().pow(exponent).toInt().toBigInteger()
  val buffer = StringBuffer()
  var number = BigInteger(this.toBytes())
  do {
    val mod = number.mod(base)
    number = number.divide(base)
    buffer.append(lookupTable[mod.toInt()])
  } while (number.signum() != 0)
  return buffer.toString().reversed()
}

写完后当然要写个测试验证一下对不对，既然要测试，就得先找出正确解，所以文章一开始的图片就是解释：怎么从一个 UUID 找出编码后的结果。这裡是每 6 bits 一组，绿色是高位元的 64 bits，紫色则是低位元的 64 bits，会发现有个 a 是由高位元的最小 2 bits 搭配低位元的最高 4 bits 组成的，这也是为什么需要两个 Long 一起运算的原因了，因为除非是 4 bits 或 8 bits 一组，不然无法整除 Long，一定会发生要向另一个 Long 借位的情形发生 [不借位其实也是可行的，只是编码出来的长度会再加 1]。

从测试案例就可以看出来长度明显缩短不少：

1、53e6693a-0aaa-4e94-a116–2a397fc89975 (一般形式)
2、53e6693a-0aaa4e94a1162a397fc89975 (去除分隔符号)
3、1jVCAW2GFeBa4mazB-O9BR (短模式)

@Test
fun testShortIdWithDefaultCharacters() {
  val uuid = fromString("53e6693a-0aaa-4e94-a116-2a397fc89975")
  val shortId = uuid.shortId()
  assertEquals("1jVCAW2GFeBa4mazB-O9BR", shortId)
}

既然能够编码，那是否可以解回来呢？当然也是可以，这裡就替 String 增加一个 fromShortId 的 extension method，一样可以指定字母表，只是程式会检查给定的字母数量是否足以解码 (这裡就偷懒没将验证抽出去成独立的函式了)，后续的逻辑就很简单，依序查字母所在的 index，乘上倍数后加上 index，最后一样要记得处理一下正负数 (line 14) 就完成了。

fun String.fromShortId(characters: String = defaultCharacters): UUID {
  val exponent = assertCharactersSize(characters)
  if (this.length != ceil((Long.SIZE_BITS * 2).toDouble() / exponent).toInt()) {
    throw IllegalArgumentException("the string could not be represented with the characters")
  }
  val base = 2.toDouble().pow(exponent).toInt().toBigInteger()
  var number = BigInteger.valueOf(0)
  this.forEach { char ->
    val index = characters.indexOf(char).toBigInteger()
    number = number.times(base).add(index)
  }
  val bytes = number.toByteArray()
  val length = Long.SIZE_BYTES * 2
  val offset = if (bytes.size > length) (bytes.size - length) else 0
  val buffer = ByteBuffer.wrap(bytes, offset, length)
  return  UUID(buffer.long, buffer.long)
}

当然，也是要写个测试验证一下解码对不对：

@Test
fun testShortIdWithDefaultCharacters() {
  val uuid = fromString("53e6693a-0aaa-4e94-a116-2a397fc89975")
  val shortId = uuid.shortId()
  assertEquals("1jVCAW2GFeBa4mazB-O9BR", shortId)
  assertEquals(uuid, shortId.fromShortId())
}

最后再加上个测试案例，不是用预设的字母表，这裡使用的是 0 到 9，以及大小的 A 到 Z，排除掉容易跟 1 搞混的 I，以及和 0 搞混的 O 和 Q 后共 32 个字母，从测试案例就可以看出，有缩短但幅度就没那么明显了。

fbcf8ca0-a0b7–4e8c-8a05-f0be7c72f022 (一般形式)
fbcf8ca0a0b74e8c8a05f0be7c72f022 (去除分隔符号)
7USX6A185P9T68L1FGPSX75V12 (base 32)

@Test
fun testShortIdWith32Characters() {
  val characters = "0123456789ABCDEFGHJKLMNPRSTUVWXY"
  val uuid = fromString("fbcf8ca0-a0b7-4e8c-8a05-f0be7c72f022")
  val shortId = uuid.shortId(characters)
  assertEquals("7USX6A185P9T68L1FGPSX75V12", shortId)
  assertEquals(uuid, shortId.fromShortId(characters))
}

好啦，有人会说，这不就是 Base64 和 Base 32 吗？是也不是，因为我写的演算法跟标准不太一样，只是用这种编码方式来呈现 UUID 是较少见的 [维基百科：在 Java 持久化系统 Hibernate 中，就采用了 Base64 来将一个较长的唯一识别码 (一般为128-bit的 UUID) 编码为一个字串，用作 HTTP 表单和 HTTP GET URL 中的参数]，原因为何我就不清楚了。

顺手写了个简单的程式测一下两者的效能差距，由于单独一个 toString() 或是 shortId() 的执行时间很短，所以程式是每十万次为单位量测时间，大家有兴趣可以跑跑看。

import java.lang.System.currentTimeMillis
import java.util.*

fun main() {
  val times = 21
  val size = 100_000

  println("index, toString(), shortId()")
  repeat(times) { index ->
    val uuids = (1..size).map { UUID.randomUUID() }
    val toStringStarted = currentTimeMillis()
    uuids.forEach { uuid -> uuid.toString() }
    val shortIdStarted = currentTimeMillis()
    uuids.forEach { uuid -> uuid.shortId() }
    val finished = currentTimeMillis()
    println("${index}, ${shortIdStarted - toStringStarted}, ${finished - shortIdStarted}")
  }
}

我想从图表就看的出来，虽然程式还有优化的可能 (把除法改成位元运算)，但那个差距是相当明显 (单位是 ms)。

后记，说真的，即便将长度从 36 个字元缩短到本文中的 22 或 26 个字元，仍然是一个很长的 ID，一般来说，人的短期记忆力有所谓七加减二的说法，也就是能记住五至九个字元的片段，太长就记不住了，用 UUID 或是较短的其他 ID 产生器，这就得有些取捨了。

以五个字元来说，数字加上英文字母大小写，最多就 62 的五次方种组合，也就是 916,132,832 个组合，又或是不分大小写并排除易混淆字母只用 32 个字元，也就是 32 的五次方共 33,554,432 个组合，碰撞机率还是有的，可搭配资料库纪录已配发的 ID，或加上 namespace 来避免重复。

当长度增加到九个字元，这时 62 的九次方 (13,537,086,546,263,552) 或是 32 的九次方 (35,184,372,088,832)，这时碰撞的机率非常的低，也就是说一次的 Random.nextLong() 加上指定的编码就能产生指定长度的 ID，算是相当快速 (UUID 需要两次的 random) 且方便的，果不其然，可以在 GitHub 的专案看到相似的概念：

short-unique-id - npmGitDownloads

题外话，这次的 short UUID 其实在GitHub 也能找到类似的专案：

文中的范例我放在 GitHub 上，想优化或修改可以去下载。

GitHub - dbi1463/short-uuid

GitHub 的版本跟本文有点不一样，算法没变，主要是用了 Kotlin 的 companion object 稍微改写一下。