Add time based UUIDs

[GaelTadh]

See #5941.

Using SecureRandom as a UUID generator is slow and doesn't allow us
to take adavantage of some lucene optimizations around ids with common
prefixes. This commit will allow us to use a
timestamp64bit-macAddr-counter UUID. Since the macAddr may be shared
among several nodes running on the same hardware we use an xor of the
macaddr with a SecureRandom number generated on startup.

[kimchy]

can we add a unit test that verifies the shared prefix behavior of this new UUID?

[kimchy]

should we catch Throwable here to be safe? Also, maybe do a simple debug log it so we can see why it fails if we really want to?

[kimchy]

LAST_TIMESTAMP handling is not thread safe, but at the end, an 8 bytes incremental sequence number with salted mac address should protect from time shifts and restarts. I wonder if we can remove it completely? Need to think about this.

Also, now we are moving to 22 byte UID, compared to previously having 16 byte UID, potentially, the sequence number can be smaller, but then, we might need to make sure we generate / make it incremental within the same timestamp as the seq generation scope is smaller which entails synchronization.

[kimchy]

also, the mac address code is flaky, its not only on OSX that we can potentially fail, but also on systems that are virtualized, ... . Check https://github.com/cowtowncoder/java-uuid-generator/blob/3.0/src/main/java/com/fasterxml/uuid/EthernetAddress.java for inspiration.

[s1monw]

a couple of things:

• I think this should be it's own class that can be a singleton. We should have a TimeBasedUUID.java and RandomBasedUUID.java that way we can put in the right impl on initialisation time and don't need the if here.
• if we have dedicated impls then we can simply use member variables rather than static variable.s
• we should use a PaddedAtomicLong for the timestamp and update in a CAS loop like:

do {
  long last = lastTimestamp.get();
  if (lastTimeStamp.compareAndSet(last, timestamp) {
    break;
  } 
} while(last < timestamp);

• I wonder if 32bit sequence IDs are enough?
• do we really need the ByteBuffer instance of can we maybe just use a simple copy method for the bytes, the long should be simple as well just a static method with 4 shifts?

[GaelTadh]

I've pushed some new changes including the unit tests. @s1monw I can remove the ByteBuffer stuff if we really want to and add our own. I'm pulling things into a singleton now.

[s1monw]

I think we are missing the time is going backwards checks here? Essentially we should:

• check the current timestamp and if it goes backwards add one
• try update the timestamp
  • if success step out
  • else read the current timestamp again and retry

[mikemccand]

I think these members can be final?

[pickypg]

This happens regardless in the next if-statement since address remains null.

[mikemccand]

Thanks @pickypg, I started from @GaelTadh patch and then folded in
most of your & my feedback into a new branch here:

mikemccand@e5e21b7

The one thing I didn't do is move the singleton to UUIDGenerator
interface; I think Strings.* APIs is good place to expose access to
these different generators?

I removed the PaddedAtomicLong: I think it's overkill here, and a
distraction.

I left the CAS loop to ensure lastTimestamp grows monotonically, but
tried to simplify it.

I removed APIs to parse out the time-based UUID: it's supposed to be
opaque to callers.

I broke out SecureRandomHolder as its own package private class.

I dropped sequence number from 8 bytes to 3, and now increment the
timestamp when the bottom two bytes are 0, to deal with a biggish
clock slip backwards while JVM is up. I also randomized the sequence
id on init for best effort protection of backwards clock-slip while
JVM is down.

[pickypg]

@mikemccand LGTM