java - 如何将UUID转换为小于40位的数字？

Question

我需要将 UUID(例如 ffffffff-ffff-ffff-ffff-ffffffffffff)转换为数字尽可能少的数字。这些 UUID 是由 com.fasterxml.uuid.impl.TimeBasedGenerator.java 生成的.

package com.fasterxml.uuid.impl;

import java.util.UUID;

import com.fasterxml.uuid.*;

/**
 * Implementation of UUID generator that uses time/location based generation
 * method (variant 1).
 *<p>
 * As all JUG provided implementations, this generator is fully thread-safe.
 * Additionally it can also be made externally synchronized with other
 * instances (even ones running on other JVMs); to do this,
 * use {@link com.fasterxml.uuid.ext.FileBasedTimestampSynchronizer}
 * (or equivalent).
 *
 * @since 3.0
 */
public class TimeBasedGenerator extends NoArgGenerator
{
    /*
    /**********************************************************************
    /* Configuration
    /**********************************************************************
     */

    protected final EthernetAddress _ethernetAddress;

    /**
     * Object used for synchronizing access to timestamps, to guarantee
     * that timestamps produced by this generator are unique and monotonically increasings.
     * Some implementations offer even stronger guarantees, for example that
     * same guarantee holds between instances running on different JVMs (or
     * with native code).
     */
    protected final UUIDTimer _timer;

    /**
     * Base values for the second long (last 8 bytes) of UUID to construct
     */
    protected final long _uuidL2;
    
    /*
    /**********************************************************************
    /* Construction
    /**********************************************************************
     */

    /**
     * @param ethAddr Hardware address (802.1) to use for generating
     *   spatially unique part of UUID. If system has more than one NIC,
     */
    
    public TimeBasedGenerator(EthernetAddress ethAddr, UUIDTimer timer)
    {
        byte[] uuidBytes = new byte[16];
        if (ethAddr == null) {
            ethAddr = EthernetAddress.constructMulticastAddress();
        }
        // initialize baseline with MAC address info
        _ethernetAddress = ethAddr;
        _ethernetAddress.toByteArray(uuidBytes, 10);
        // and add clock sequence
        int clockSeq = timer.getClockSequence();
        uuidBytes[UUIDUtil.BYTE_OFFSET_CLOCK_SEQUENCE] = (byte) (clockSeq >> 8);
        uuidBytes[UUIDUtil.BYTE_OFFSET_CLOCK_SEQUENCE+1] = (byte) clockSeq;
        long l2 = UUIDUtil.gatherLong(uuidBytes, 8);
        _uuidL2 = UUIDUtil.initUUIDSecondLong(l2);
        _timer = timer;
    }
    
    /*
    /**********************************************************************
    /* Access to config
    /**********************************************************************
     */

    @Override
    public UUIDType getType() { return UUIDType.TIME_BASED; }

    public EthernetAddress getEthernetAddress() { return _ethernetAddress; }
    
    /*
    /**********************************************************************
    /* UUID generation
    /**********************************************************************
     */
    
    /* As timer is not synchronized (nor _uuidBytes), need to sync; but most
     * importantly, synchronize on timer which may also be shared between
     * multiple instances
     */
    @Override
    public UUID generate()
    {
        final long rawTimestamp = _timer.getTimestamp();
        // Time field components are kind of shuffled, need to slice:
        int clockHi = (int) (rawTimestamp >>> 32);
        int clockLo = (int) rawTimestamp;
        // and dice
        int midhi = (clockHi << 16) | (clockHi >>> 16);
        // need to squeeze in type (4 MSBs in byte 6, clock hi)
        midhi &= ~0xF000; // remove high nibble of 6th byte
        midhi |= 0x1000; // type 1
        long midhiL = (long) midhi;
        midhiL = ((midhiL << 32) >>> 32); // to get rid of sign extension
        // and reconstruct
        long l1 = (((long) clockLo) << 32) | midhiL;
        // last detail: must force 2 MSB to be '10'
        return new UUID(l1, _uuidL2);
    }
}

我预计每天至少会在特定机器上生成 1200 万个 UUID。我假设 TimeBasedGenerator 将在程序启动时启动一次，因此将具有恒定的网络地址和恒定的随机生成器种子时间(下面代码中的值 now ) .

final long now = 1644575806478L;

final TimeBasedGenerator sut = new TimeBasedGenerator(EthernetAddress.fromInterface(),
  new UUIDTimer(new Random(now), null));

如何将 UUID 转换为数字

a) 少于 40 位和

b) 重复的 UUID 最早每 6 个月出现一次？

尝试 1 失败

将 UUID 转换为数字的最简单方法如下所示:

import java.math.BigInteger;
import java.util.function.Function;

public class OldUUIDConverter implements Function<String, BigInteger> {
    @Override
    public BigInteger apply(final String uuid) {
        final String uuidWithoutDashes = uuid.replaceAll("-", "");
        return new BigInteger(uuidWithoutDashes, 16);
    }
}

对于最大可能的 UUID (ffffffff-ffff-ffff-ffff-ffffffffffff)，它会生成数字

340282366920938463463374607431768211455
^         ^         ^         ^         ^

因为我们直接转换UUID，所以如果UUID生成器不会太频繁地产生重复的UUID，则不会重复。

满足上述要求的标准b)。但标准 a)——转换后的数字的长度——却不是。

尝试 2 失败

有人建议只取UUID的前8位数字。这样就满足了标准a)。

但是，UUID 的前 8 位数字重复得太频繁。

我写了一个简单的测试程序:

import com.fasterxml.uuid.EthernetAddress;
import com.fasterxml.uuid.UUIDTimer;
import com.fasterxml.uuid.impl.TimeBasedGenerator;
import org.junit.Test;

import java.io.IOException;
import java.util.HashSet;
import java.util.Random;
import java.util.Set;

public class UUIDShortenerTest {
    @Test
    public void test() throws IOException {
        final Set<String> first8DigitsAsLong = new HashSet<>(73000000);

        final long now = 1644575806478L;

        final TimeBasedGenerator sut = new TimeBasedGenerator(EthernetAddress.fromInterface(), new UUIDTimer(new Random(now), null));

        for (int i=0; i < Integer.MAX_VALUE; i++) {
            final String curUuid = sut.generate().toString();
            final String first8Digits = curUuid.substring(0, 8);
            if ((i % 1000000L) == 0) {
                System.out.println(String.format("Counter: %d", i));
            }
            if (!first8DigitsAsLong.add(first8Digits)) {
                System.out.println("Duplicate!");
                System.out.println(i);
                break;
            }
        }
    }
}

我运行了10次。每次我记下 UUID 代数，然后重复前 8 位数字。

结果如下:

1. 重复 74499376 UUID 生成后找到的前 8 位数字。
2. 44259478
3. 45365652
4. 45031094
5. 45445463
6. 46250299
7. 45403800
8. 44658612
9. 46098250
10. 43748051

假设我生成 7500 万个 UUID 后，前 8 位数字重复。

如果我每天生成 1200 万个 UUID，这意味着第一个前 8 位数重复的 UUID 将在 62-63 天(75000000/1200000=62.5 天)后生成。

这 62.5 天(大约两个月)低于 UUID 重复之前 6 个月的要求。

我所知道的选项

我可以采取多种措施来解决该问题。

其中之一是增加我使用的第一位数字的数量，直到 UUID 重复的频率达到所需的水平。也就是说，我可以尝试使用前 9 位数字而不是 8 位，看看它是否足够好。如果没有，我可以使用前 10 位数字等。

另一种方法是使用失败的尝试 #1 中的代码，并将结果数字340282366920938463463374607431768211455编码到具有更大基础的数字系统中。

假设我使用数字 0-9、拉丁小写和大写字母以及 14 个特殊字符。结果每个数字可以有 10+26+26+14=76 个数字。我假设以 76 为基数的系统中的上述数字将比十进制或十六进制系统中的相同数字短。

还有其他更好的选择(例如具有足够多样性的哈希函数)吗？

Answer 1

这是生日问题。理论上，只要生成两个 UUID 就可以发生 UUID 冲突，但是有方便的 probability tables 。您正在尝试生成 12*10^6*30*6 ~= 2*10^9 id。您愿意冒多大的风险？