java - 使ULID字典顺序对时间更加敏感

我在一个项目中使用了this ULID example，不仅需要ULID提供的唯一性，还需要其字典分类能力。
但是，我发现，无论我做了多少尝试，我都无法仅对循环中排序的生成的ID进行排序。
例如

class Test{
    public static void main(String[] args) {
            ArrayList<String> ulids = new ArrayList<>();

            for (int i = 0; i < 10; i++) {

                ulids.add(ULID.generate());
            }

            System.out.println("Original:\n..." + ulids);

            Collections.shuffle(ulids);

            System.out.println("Shuffled:\n..." + ulids);

            ulids.sort(new Comparator<String>() {
                @Override
                public int compare(String o1, String o2) {
                    return o1.compareTo(o2);
                }
            });

            System.out.println("Sorted:\n..." + ulids);

        }
}

Sample output:
Original:
...[01edrp4ng81d3mvkp8s7z19znm, 01edrp4ng872nwfj6b9fsxjkkd, 01edrp4ng86v07r6c9sh62ghr7, 01edrp4ng8bpfw3m2q8bynd5st, 01edrp4ng896t1qhsngrz3h251, 01edrp4ng8jne084nsw5saesfe, 01edrp4ng8w8qz9qtgy3958r1v, 01edrp4ng8fdn30qnr2ktddyz4, 01edrp4ng8ekj0vt393tw12x8j, 01edrp4ng80wacxxskgej5d8mm]
Shuffled:
...[01edrp4ng896t1qhsngrz3h251, 01edrp4ng8w8qz9qtgy3958r1v, 01edrp4ng86v07r6c9sh62ghr7, 01edrp4ng8bpfw3m2q8bynd5st, 01edrp4ng8fdn30qnr2ktddyz4, 01edrp4ng80wacxxskgej5d8mm, 01edrp4ng872nwfj6b9fsxjkkd, 01edrp4ng81d3mvkp8s7z19znm, 01edrp4ng8jne084nsw5saesfe, 01edrp4ng8ekj0vt393tw12x8j]
Sorted:
...[01edrp4ng80wacxxskgej5d8mm, 01edrp4ng81d3mvkp8s7z19znm, 01edrp4ng86v07r6c9sh62ghr7, 01edrp4ng872nwfj6b9fsxjkkd, 01edrp4ng896t1qhsngrz3h251, 01edrp4ng8bpfw3m2q8bynd5st, 01edrp4ng8ekj0vt393tw12x8j, 01edrp4ng8fdn30qnr2ktddyz4, 01edrp4ng8jne084nsw5saesfe, 01edrp4ng8w8qz9qtgy3958r1v]

我检查了实现，发现由于时间是生成ULID的核心因素，并且由于所用时间的敏感性是毫秒，即(System.currentTimeMillis())，因此可以通过在id生成循环中引入一些延迟来对它们进行排序。
我引入了大约5毫秒的延迟，并且所有ID都已排序。例如:

class TestWithMsDelay{

   public static void main(String[] args) {
        ArrayList<String> ulids = new ArrayList<>();

        for (int i = 0; i < 10; i++) {
            try {
                Thread.sleep(5L);
                ulids.add(ULID.generate());
            } catch (Exception ex) {
                ex.printStackTrace();
            }
        }

        System.out.println("Original:\n..." + ulids);

        Collections.shuffle(ulids);

        System.out.println("Shuffled:\n..." + ulids);

        ulids.sort(new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                return o1.compareTo(o2);
            }
        });

        System.out.println("Sorted:\n..." + ulids);

    }


}
Sample output:
Original:
...[2rjdme5a5h2ntcd20xq4z487tx, 2rjdme63a23ddsy0km21n6n34a, 2rjdme6pnrenx79zd3jj18est4, 2rjdme70bv45b648p82dbj584n, 2rjdme7d8gx9v9db66ftsxbmqq, 2rjdme7psqdykt24qfymn2e4ba, 2rjdme80as7t1h1rr00m676718, 2rjdme8rztp50bad6ktkhrfhk8, 2rjdme93ngkxkfmf6aegqxer9e, 2rjdme9ea04x22rpx2f3rp5gez]
Shuffled:
...[2rjdme7psqdykt24qfymn2e4ba, 2rjdme6pnrenx79zd3jj18est4, 2rjdme80as7t1h1rr00m676718, 2rjdme63a23ddsy0km21n6n34a, 2rjdme93ngkxkfmf6aegqxer9e, 2rjdme70bv45b648p82dbj584n, 2rjdme9ea04x22rpx2f3rp5gez, 2rjdme8rztp50bad6ktkhrfhk8, 2rjdme7d8gx9v9db66ftsxbmqq, 2rjdme5a5h2ntcd20xq4z487tx]
Sorted:
...[2rjdme5a5h2ntcd20xq4z487tx, 2rjdme63a23ddsy0km21n6n34a, 2rjdme6pnrenx79zd3jj18est4, 2rjdme70bv45b648p82dbj584n, 2rjdme7d8gx9v9db66ftsxbmqq, 2rjdme7psqdykt24qfymn2e4ba, 2rjdme80as7t1h1rr00m676718, 2rjdme8rztp50bad6ktkhrfhk8, 2rjdme93ngkxkfmf6aegqxer9e, 2rjdme9ea04x22rpx2f3rp5gez]

这对我的工作来说还不够好...我不想等待任何时间来生成ulids(即使它是10us-100us)，人为延迟的概念使我非常困扰，大声笑。
因此，我修改了ULID.java并将时间源从System.currentTimeMillis()更改为System.nanoTime()令我惊讶的是，我不再需要任何时间延迟就可以对输出ULID进行排序。
我觉得在某处一定有障碍。因为Java Spec警告System.nanoTime()不一定比System.currentTimeMillis()更准确
例如在Javadoc中的System.nanoTime()，它说:
此方法提供纳秒级精度，但不一定提供纳秒级分辨率(即值更改的频率)-除了分辨率至少与currentTimeMillis()一样好以外，不做任何保证。
另外，System.nanoTime()的Javadoc似乎表明它与纪元无关(System.currentTimeMillis()也是)
我相信这可能会导致在ULID.java中使用System.nanoTime()而不是在使用时造成不良行为(随着时间的流逝而影响可排序性，并可能影响唯一性)System.currentTimeMillis() 问题

我的担心合法吗

如果(1.)是正确的，该如何做才能在不破坏其优势的情况下将ULID的时间敏感性提高到1毫秒以上？

最佳答案

ULID有两个部分:时间部分和随机部分。
时间部分是自1970年以来的毫秒数。
随机组件在两种情况下会更新:

当毫秒更改时，将生成一个新的随机值；

当毫秒相同时，随机值增加1。

您在此处显示的实现不执行第二步。
也许您可以包括一些这样的代码(仅作为示例):

if (timestamp == previousTimestamp) {
    randomComponent++;
} else {
    randomComponent = RANDOM.nextLong();
}

我发现的另一个问题是它使用Math.random()而不是java.security.SecureRandom。为了解决这个问题，这是一个建议:

import java.security.SecureRandom;
private static final RANDOM = new SecureRandom();

最后，不建议使用System.nanoTime()，因为它会返回自任意时间点以来的纳秒数。这不是主板上实时时钟(RTC)返回的白天时间。此功能用于测量代码中两点之间的经过时间，可能用于基准测试。例:

long startNanos = System.nanoTime();

// do some expensive tasks here

long endNanos = System.nanoTime();

long elapsedNanos = endNanos - startNanos;

如果愿意，可以检查库ulid-creator。也许可以帮上忙。例:

// Generate a ULID as UUID
UUID ulid = UlidCreator.getUlid();

// Or generate a ULID as String (Crockford's base32)
String ulid = UlidCreator.getUlidString();

项目页面:https://github.com/f4b6a3/ulid-creator
编辑
抱歉。我没有意识到这些问题。
我的担心合法吗
是的，你的赖特。
如果(1.)为真，如何在不破坏ULID优势的情况下将ULID的时间敏感性提高到1毫秒以上，该怎么办？
您可以提高ULID分辨率，但是它不符合ULID Spec(顺便说一句，它不是RFC-4122之类的正式标准)。生成的UUID类似于Jimmy Wilson创建的COMB GUID。两者的主要思想是相同的。
您可以为时间戳组件保留更多位，但是会花费一些位。例如，如果将时间部分从48位增加到64位，它将在2262年左右滚动，但是随机部分将从1208925819614629174706176(2 ^ 80)减少到18446744073709551616(2 ^ 64)。如果成本影响ULID的优势，则取决于您的项目。
我刚刚为纳秒分辨率的ULID实现了一个生成器。巧合的是，几天前我正在研究它。使用System.currentTimeMillis()方法，它实际上具有毫秒精度。在两个后续调用之间使用System.nanoTime()方法模拟了纳秒级的重新溶解。
如果您仍打算使用纳秒级的ULID，请随时进行测试:

package your.package.name;

import java.security.SecureRandom;
import java.time.Instant;
import java.util.UUID;

/**
 * Utility class that creates a COMB GUID with nanoseconds resolution.
 *
 * It borrows the main idea from ULID and COMB generators: a concatenation of
 * time and random bytes. It is composed of 64 bits for time and 64 for random
 * bits.
 *
 * A Nano COMB has two components:
 *
 * 1. Time camponent (64 bits): nanoseconds since 1970
 *
 * 2. Random component (64 bits): a value generated by a secure random
 * generator.
 *
 * Maximum time component year is ~2262 A.D. (2^63/10^9/60/60/24/365.25 + 1970)
 *
 * @author: Fabio Lima 2020
 */
public final class NanoCombCreator {

    private long prevTime = 0;
    private long prevNano = 0;

    private static final long ONE_MILLION_NANOSECONDS = 1_000_000L;

    private static final SecureRandom SECURE_RANDOM = new SecureRandom();

    /**
     * Returns a time component in nanoseconds.
     *
     * It uses `System.currentTimeMillis()` to get the system time in milliseconds
     * accuracy. The nanoseconds resolution is simulated by calling
     * `System.nanoTime()` between subsequent calls within the same millisecond.
     * It's not precise, but it provides some monotonicity to the values generates.
     *
     * @return the current time in nanoseconds
     */
    private synchronized long getTimeComponent() {

        final long time = System.currentTimeMillis();
        final long nano = System.nanoTime();
        final long elapsed; // nanoseconds since last call

        if (time == prevTime) {
            elapsed = (nano - prevNano);
            if (elapsed > ONE_MILLION_NANOSECONDS) {
                try {
                    // make the clock to catch up
                    Thread.sleep(1);
                } catch (InterruptedException e) {
                    System.err.println("something went wrong...");
                }
            }
        } else {
            prevTime = time;
            prevNano = nano;
            elapsed = 0;
        }

        return (time * ONE_MILLION_NANOSECONDS) + elapsed;
    }

    /**
     * Returns the random component using a secure random generator.
     *
     * @return a random value.
     */
    private synchronized long getRandomComponent() {
        return SECURE_RANDOM.nextLong();
    }

    /**
     * Returns a Nano COMB.
     *
     * A Nano COMB is inspired on ULID and COMB generators.
     *
     * It is composed of 64 bits for time and 64 for random bits.
     *
     * @return a UUID
     */
    public synchronized UUID create() {

        final long timeBits = getTimeComponent();
        final long randomBits = getRandomComponent();

        return new UUID(timeBits, randomBits);
    }

    /**
     * Test method that generates many Nano COMBs in a loop.
     *
     * @param args
     */
    public static void main(String[] args) {

        NanoCombCreator creator = new NanoCombCreator();

        for (int i = 0; i < 100; i++) {
            // Generate a Nano COMB
            UUID uuid = creator.create();

            // Extract the milliseconds and nanoseconds
            long milliseconds = uuid.getMostSignificantBits() / ONE_MILLION_NANOSECONDS;
            long nanoseconds = uuid.getMostSignificantBits() & ONE_MILLION_NANOSECONDS;

            // Instantiate an instant using the milliseconds and nanoseconds
            Instant time = Instant.ofEpochMilli(milliseconds).plusNanos(nanoseconds);

            // Print the UUID and the time it was generated (UTC)
            System.out.println("UUID: '" + uuid + "', time: " + time);
        }
    }
}

OUTPUT:

UUID: '16240ee8-3865-1503-d1fb-b4e85f991c6b', time: 2020-07-22T11:15:58.537327680Z
UUID: '16240ee8-3865-f90a-ca19-3ec529750ef7', time: 2020-07-22T11:15:58.537344064Z
UUID: '16240ee8-3866-dd7c-f32f-7acaebcf7766', time: 2020-07-22T11:15:58.537409664Z
UUID: '16240ee8-3868-0a99-3ead-b114e1d61520', time: 2020-07-22T11:15:58.537524800Z
UUID: '16240ee8-3868-efc8-937d-599c72de71a6', time: 2020-07-22T11:15:58.537541248Z
UUID: '16240ee8-386a-3643-6a5e-e3b5e3b03c71', time: 2020-07-22T11:15:58.537655936Z
UUID: '16240ee8-386b-132f-7016-057ab30a2920', time: 2020-07-22T11:15:58.537721408Z
UUID: '16240ee8-386b-f929-d5b0-f70b68aea3d9', time: 2020-07-22T11:15:58.537737280Z