System wide unique nanosecond timestamps

A Unique Identifier can be very useful for tracing. Those ids are even more useful when they contain a high-resolution timestamp. 

Not only do they record the time of an event, but if unique can help trace events as they pass through the system. Such unique timestamps however can be expensive depending on how they are implemented.  

This post explores a lightweight means of producing a unique, monotonically increasing system-wide nano-second resolution timestamp available in our open-source library.

Uses for Unique Identifiers

Unique identifiers can be useful to associate with a piece of information so that information can be referred to later unambiguously. This could be an event, a request, an order id, or a customer id.

They can naturally be used as a primary key in a database or key/value store to retrieve that information later.

One of the challenges of generating these identifiers is avoiding creating duplicates while not having an increasing cost. 

You could record every identifier created in a database, however, this uses O(n) storage as you add more identifiers. 

You could generate a random identifier such as a UUID which is unlikely to repeat, however, this creates large ids that otherwise don't hold any information. e.g. a UUID can look like 
d85686f5-7a53-4682-9177-0b64037af336

This UUID could be stored in 16 bytes however is often stored as an object taking 40 bytes of memory.

Using 256 bits reduces the risk of a repeated identifier, but doubles the memory used.

Timestamps as Unique Identifiers

Using a timestamp has two benefits. You don't need to store much information as the wall clock is the driver. You only need to check two threads that don't have the same time, but if this information is lost on a restart, for example, wall clock time should have progressed enough that you still won't get a duplicate. 

Such identifiers are also easier to read and give additional information which is useful for tracing. A timestamp-based unique identifier can look like 
2021-12-20T23:30:51.8453925

This timestamp could be stored in a LocalDateTime object however can be stored as just 8 bytes as a long, which is the way we typically use it.

MappedUniqueTimeProvider code

This is the abridged version of the MappedUniqueTimeProvider available on GitHub

/**
 * Timestamps are unique across threads/processes on a single machine.
 */
public enum MappedUniqueTimeProvider implements TimeProvider {
    INSTANCE;

    private final Bytes bytes;
    private TimeProvider provider = SystemTimeProvider.INSTANCE;

    MappedUniqueTimeProvider() {
        String user = System.getProperty("user.name", "unknown");
        MappedFile file = MappedFile.mappedFile(OS.TMP + "/.time-stamp." + user + ".dat", OS.pageSize(), 0);
        bytes = file.acquireBytesForWrite(mumtp, 0);
    }

    @Override
    public long currentTimeNanos() throws IllegalStateException {
        long time = provider.currentTimeNanos(), time5 = time >>> 5;
        long time0 = bytes.readVolatileLong(LAST_TIME), timeNanos5 = time0 >>> 5;

        if (time5 > timeNanos5 && bytes.compareAndSwapLong(LAST_TIME, time0, time))
            return time;

        while (true) {
            time0 = bytes.readVolatileLong(LAST_TIME);
            long next = (time0 + 0x20) & ~0x1f;
            if (bytes.compareAndSwapLong(LAST_TIME, time0, next))
                return next;
            Jvm.nanoPause();
        }
    }
}

The following techniques have been used to ensure time stamps’ uniqueness and efficiency

Shared memory

This TimeProvider uses shared memory to ensure a nanosecond resolution time is unique. A memory-mapped file is accessed in a thread-safe way to ensure the timestamps are monotonically increasing. Chronicle Bytes has a library to support thread-safe access to a memory-mapped file. 

A long value in the memory-mapped file is read and attempted to be updated in a loop. The CAS or compare-and-swap operation is atomic and checks the previous value hasn't been changed by another thread. This will only succeed for one thread on the same machine.

Storing a nanosecond timestamp in a long

We use a primitive long to store times stamps for efficiency, this can be harder to work with as a result, however, we have support for printing and parsing a long timestamp called the NanoTimestampLongConverter Our wire format also parses and renders these timestamps as text implicitly making it easier to print, debug and create units tests for.

public class Event extends SelfDescribingMarshallable {
    @LongConversion(NanoTimestampLongConverter.class)
    long time;
}

Event e = new Event();
e.time = CLOCK.currentTimeNanos();
String str = e.toString();
Event e2 = Marshallable.fromString(str);
System.out.println(e2);
Prints
!net.openhft.chronicle.wire.Event {
  time: 2021-12-20T23:30:51.8453925
}

As nano-second timestamps are a high-resolution format, it will only last until the year 2262 as a signed long or 2554 if you assume it's an unsigned long, before the values overflow.

We have used for using extra bits in the timestamp for other purposes, such as storing the host identifier or a source id. For this reason, we also ensure the timestamp is unique to a multiple of 32 ns, allowing us to use the lower 5 bits for other purposes if we wish. If you were implementing this yourself you could drop this requirement.

Performance

Under normal operation, obtaining the unique nanosecond timestamp takes well under 50 ns on modern machines. Under heavy multi-threaded load in benchmarks, it can take a few hundred nanoseconds. However, this assumes the timestamps are discarded, so I consider such a benchmark an unrealistic use case.

The MappedUniqueTimeProvider application can sustain the generation of over 30 million/second and not run ahead of the wall clock due to the mentioned techniques

Restartability

As long as time doesn't go backward, this strategy can lose all states and still ensure uniqueness from the wall clock alone. If wall clock time does go backward by say an hour, the state will ensure there are no duplicates, however, the timestamps won't match the wall clock until the wall clock catches up.

Conclusion

It is possible to have a lightweight, unique identifier generator that holds nanosecond timestamps.

Links

Chronicle Bytes https://github.com/OpenHFT/Chronicle-Bytes

Chronicle Performance Engineers https://www.linkedin.com/groups/12138236/

Chronicle Software https://chronicle.software/

Authors

Peter Lawrey https://www.linkedin.com/in/peterlawrey/

Reviewed by Forough Goudarzi https://www.linkedin.com/in/forough-goudarzi-29946280/