Monotonically strictly increasing clock source

[CMCDragonkai]

I'm just wondering, did you find a monotonic strict increasing clock source for the timestamp generation? Otherwise there's a small change at high resolution scenarios where the time will be the same, we could get an equal time and then the ids are not strictly ordered. Compare with: https://github.com/boundary/flake And with reference to: http://learnyousomeerlang.com/time

On a single machine it should be possible with just a counter though, but then you need to keep state of the old counter somewhere. If the OS could provide this counter, it would be much easier.

[alizain]

You're completely correct, at high resolution scenarios, there is a chance of non-strict ordering. I think for this library, a state variable will be the most appropriate for ensuring monotonicity. Is this something you'd like to add?

[phillbaker]

@alizain I think I have a related question: in the case where we do have strictly ordered items (say a batch of items to be processed), an increasing counter for that batch would provide ordering. What would you think about making the first 16 bit uint an optional random or counter? In that case the layout might look like:

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                      32_bit_uint_time_high                                |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|     16_bit_uint_time_low      | 16_bit_uint_random or 16_bit_uint_counter |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                       32_bit_uint_random                                  |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                       32_bit_uint_random                                  |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

[CMCDragonkai]

In PHP, you need one of 2 extensions, the one that gives you the posix monotonic clock, or the one that gives you windows monotonic clock.

[alizain]

Monotonically increasing ULIDs have been spec'ed and implemented, so I'm closing this. Let me know if there are any issues!

[CMCDragonkai]

How did you decide to implement it? With a private counter variable? I guess that's more portable than relying on the OS monotonic clocks.

Also how can we propagate this functionality to all the other implementations?

[alizain]

Yes, I used a private counter variable, ended up being pretty straightforward.

I've spec'ed out the way it achieves monotonic. If there are no flaws, than ideally, other implementations would simply follow that spec. I think for specific languages, it would be best to create issues in that project, where you require this feature.

[alizain]

@CMCDragonkai and @phillbaker, to illustrate the implementation, I've copied over some code from the README.md

import { createMonotonic } from 'ulid'

const ulid = createMonotonic()

ulid(150000) // 000XAL6S41ACTAV9WEVGEMMVRQ
ulid(150000) // 000XAL6S41ACTAV9WEVGEMMVRR
ulid(150000) // 000XAL6S41ACTAV9WEVGEMMVRS
ulid(150000) // 000XAL6S41ACTAV9WEVGEMMVRT
ulid(150000) // 000XAL6S41ACTAV9WEVGEMMVRV
ulid(150000) // 000XAL6S41ACTAV9WEVGEMMVRW
ulid(150000) // 000XAL6S41ACTAV9WEVGEMMVRX
ulid(150000) // 000XAL6S41ACTAV9WEVGEMMVRY
ulid(150000) // 000XAL6S41ACTAV9WEVGEMMVRZ
ulid(150000) // 000XAL6S41ACTAV9WEVGEMMVS0
ulid(150000) // 000XAL6S41ACTAV9WEVGEMMVS1
ulid(150000) // 000XAL6S41ACTAV9WEVGEMMVS2

As you can see, the same time component is being passed into the generator. To preserve ordering, it increments the least significant bit in the random component (with carrying for overflows).