UUID的压缩

  1. 云栖社区>
  2. 博客>
  3. 正文

UUID的压缩

长风呼啸 2018-11-03 08:21:09 浏览1744
展开阅读全文

概述

UUID,通用唯一识别码(Universally Unique Identifier)。
UUID的目的是让分布式系统中的所有元素都能有唯一的辨识信息,而不需要透过中央控制端来做辨识信息的指定。
UUID的标准型式包含32个16进制数字,以连字号分为五段,形式为8-4-4-4-12的32个字符。
示例:

550e8400-e29b-41d4-a716-446655440000

——以上内容摘自百度百科

实现

UUID有很多实现版本,以下是JDK的一个实现:

    private static class Holder {
        static final SecureRandom numberGenerator = new SecureRandom();
    }

    public static UUID randomUUID() {
        SecureRandom ng = Holder.numberGenerator;

        byte[] randomBytes = new byte[16];
        ng.nextBytes(randomBytes);
        randomBytes[6]  &= 0x0f;  /* clear version        */
        randomBytes[6]  |= 0x40;  /* set to version 4     */
        randomBytes[8]  &= 0x3f;  /* clear variant        */
        randomBytes[8]  |= 0x80;  /* set to IETF variant  */
        return new UUID(randomBytes);
    }

用SecureRandom生成的16字节(128bit)随机数,用掩码打上版本和IETF标识。
实际有效随机位122位。关于冲突概率,可以参考笔者另一片文章,漫谈散列函数

特征

UUID的优点很明显:“分布式”、“唯一”。
这些优点使得UUID被广泛使用,尤其是分布式环境下。

然而其缺点也很明显:无序,长度较长。
这些缺点也极大地限制了其应用范围,比如数据表的主键,通常大家都不会用UUID。

但还是有不少地方用到UUID的:
有时候想给一个对象分配一个标识,但是该对象不好提取唯一特征,然后该环境下又不好统一分配,
这时候很自然就想到UUID了,UUID不需要以对象特征为参数,也不用担心重复(不是说不会重复,只是不用担心,就像不用担心天上掉下陨石砸到自己一样-_-)。

压缩

但是看着这个36个字节长度的UUID,总不自觉地会想有没有优化的余地。
16字节的信息,用16进制显示,有32个字符,加上分隔符,有36字节。
事实上,如果用base64编码这16个字节,可以压缩到22字节。

    public static byte[] hex2Bytes(String hex) {
        if (hex == null || hex.isEmpty()) {
            return new byte[0];
        }
        byte[] bytes = hex.getBytes();
        int n = bytes.length >> 1;
        byte[] buf = new byte[n];
        for (int i = 0; i < n; i++) {
            int index = i << 1;
            buf[i] = (byte) ((byte2Int(bytes[index]) << 4) | byte2Int(bytes[index + 1]));
        }
        return buf;
    }

    private static int byte2Int(byte b) {
        return (b <= '9') ? b - '0' : b - 'a' + 10;
    }

    public static String compressUUID(String uuid){
        String hex = uuid.replace("-", "");
        byte[] bytes = FormatUtils.hex2Bytes(hex);
        return new String(Base64.encode(bytes, Base64.URL_SAFE | Base64.NO_PADDING | Base64.NO_WRAP));
    }

UUID压缩前后:

d44979db-5c64-40f1-b47e-e7f41c4be9e7

3dkJ2-z92fr9DuD9rNvp4A

36字节相对22字节,节约接近40%的长度,对于存储和传输而言,都是较大的提升;
虽然从可读性来说,UUID的可读性更好。
在权衡可读性和性能的时候,笔者通常的想法是,如果阅读和书写比较频繁,选择可读性较好的,如果不怎么需要阅读,选择对机器友好的。
尤其是对于数据库存储这种情况,由于存在规模效应,显然压缩的版本更具性价比。

优化

如果需要压缩版本的UUID,调用JDK的UUID生成字符串,再处理成压缩版的UUID,显然“绕圈子”了。
我们可以仿照JDK的写法直接生成:

    public static String randomUUID() {
        byte[] bytes = new byte[15];
        Holder.numberGenerator.nextBytes(bytes);
        return Base64.encodeToString(bytes, Base64.URL_SAFE | Base64.NO_WRAP);
    }

15字节的随机数,120bit, 和JDK的randomUUID效用上是差不多,然后15是3的倍数,base64编码时不需要PADDING;
生成20字节的字符串(15 / 3 * 4), 相对UUID的36字节,节约近一半的空间。

其他

base64编码有一个逼死强迫症的特点:除了常规字符[A-Za-z0-9]之外,需要另外两个字符才能凑够64个字符。
于是,我们看到base64分化了两个版本,分别以 ['+', '/'] 和 ['-', '_'] 作为补充字符的两个版本。
其中,后者是URL_SAFE的版本,前者编码后可能会包含'/', 而'/'是URL的分隔符。
但无论哪个版本,对于URL而言,有非常规字符确实确实不是很“美观”。
于是,有人想出了base62编码。
base62编码,通常用来给long编码还好,用来编码任意字节数组的话,效率很低。
不过对于long来说,base62编码长度为11字节,而十六进制编码也只是16个字节,而且十六进制可读性更好。

简书的文章ID,十六进制,12字节(48bit)。

12字节的长度,可读性OK;48bit,取值范围有两百多万亿,够用。总的来说,是比较均衡的方案。
我很好奇是怎么构造的:
随机数?可能性不大。
自增序列?不太像。通常纯自增序列的ID长度不固定,如QQ号。

如果让我来写,有可能会混合多个因子来构造ID。
例如Twitter的Snowflake,混合了时间戳,机器ID和序列号。

计算机从16位寄存器,到32位,再到64位,就不往上涨了;
在当前的体系下,对于数据库存储而言,64bit的ID是最适合的。

总结

  • 尽量用整型的ID;
  • 如果要用UUID,尽量用压缩的版本;
  • MD5也是128bit, 作为字符串传输和存储时,base64编码要优于16进制。

网友评论

登录后评论
0/500
评论
长风呼啸
+ 关注