src/java/org/apache/cassandra/utils/TimeUUID.java - cassandra - Git at Google

 /*
  * Licensed to the Apache Software Foundation (ASF) under one
  * or more contributor license agreements.  See the NOTICE file
  * distributed with this work for additional information
  * regarding copyright ownership.  The ASF licenses this file
  * to you under the Apache License, Version 2.0 (the
  * "License"); you may not use this file except in compliance
  * with the License.  You may obtain a copy of the License at
  *
  *     http://www.apache.org/licenses/LICENSE-2.0
  *
  * Unless required by applicable law or agreed to in writing, software
  * distributed under the License is distributed on an "AS IS" BASIS,
  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  * See the License for the specific language governing permissions and
  * limitations under the License.
  */

 package org.apache.cassandra.utils;

 import java.io.DataInput;
 import java.io.DataOutput;
 import java.io.IOException;
 import java.io.Serializable;
 import java.net.InetAddress;
 import java.net.NetworkInterface;
 import java.net.SocketException;
 import java.nio.ByteBuffer;
 import java.security.SecureRandom;
 import java.util.Collection;
 import java.util.Collections;
 import java.util.Enumeration;
 import java.util.HashSet;
 import java.util.List;
 import java.util.Random;
 import java.util.Set;
 import java.util.UUID;
 import java.util.concurrent.TimeUnit;
 import java.util.concurrent.atomic.AtomicLong;
 import java.util.function.Function;
 import java.util.stream.Collectors;

 import com.google.common.hash.Hasher;
 import com.google.common.hash.Hashing;

 import org.apache.cassandra.config.DatabaseDescriptor;
 import org.apache.cassandra.db.marshal.ValueAccessor;
 import org.apache.cassandra.io.IVersionedSerializer;
 import org.apache.cassandra.io.util.DataInputPlus;
 import org.apache.cassandra.io.util.DataOutputPlus;
 import org.apache.cassandra.locator.InetAddressAndPort;
 import org.apache.cassandra.serializers.MarshalException;
 import org.apache.cassandra.serializers.TypeSerializer;

 import static java.util.concurrent.TimeUnit.MICROSECONDS;
 import static org.apache.cassandra.config.CassandraRelevantProperties.CASSANDRA_UNSAFE_TIME_UUID_NODE;
 import static org.apache.cassandra.config.CassandraRelevantProperties.DETERMINISM_UNSAFE_UUID_NODE;
 import static org.apache.cassandra.utils.ByteBufferUtil.EMPTY_BYTE_BUFFER;
 import static org.apache.cassandra.utils.Clock.Global.currentTimeMillis;
 import static org.apache.cassandra.utils.Shared.Recursive.INTERFACES;

 @Shared(inner = INTERFACES)
 public class TimeUUID implements Serializable, Comparable<TimeUUID>
 {
     public static final long serialVersionUID = 1L;

     // A grand day! millis at 00:00:00.000 15 Oct 1582.
     public static final long UUID_EPOCH_UNIX_MILLIS = -12219292800000L;
     protected static final long TIMESTAMP_UUID_VERSION_IN_MSB = 0x1000L;
     protected static final long UUID_VERSION_BITS_IN_MSB = 0xf000L;

     /*
      * The min and max possible lsb for a UUID.
      * Note that his is not 0 and all 1's because Cassandra TimeUUIDType
      * compares the lsb parts as a signed byte array comparison. So the min
      * value is 8 times -128 and the max is 8 times +127.
      *
      * Note that we ignore the uuid variant (namely, MIN_CLOCK_SEQ_AND_NODE
      * have variant 2 as it should, but MAX_CLOCK_SEQ_AND_NODE have variant 0).
      * I don't think that has any practical consequence and is more robust in
      * case someone provides a UUID with a broken variant.
      */
     private static final long MIN_CLOCK_SEQ_AND_NODE = 0x8080808080808080L;
     private static final long MAX_CLOCK_SEQ_AND_NODE = 0x7f7f7f7f7f7f7f7fL;

     public static final long TIMEUUID_SIZE = ObjectSizes.measureDeep(new TimeUUID(10, 10));

     final long uuidTimestamp, lsb;

     public TimeUUID(long uuidTimestamp, long lsb)
     {
         // we don't validate that this is a true TIMEUUID to avoid problems with historical mixing of UUID with TimeUUID
         this.uuidTimestamp = uuidTimestamp;
         this.lsb = lsb;
     }

     public static TimeUUID atUnixMicrosWithLsb(long unixMicros, long uniqueLsb)
     {
         return new TimeUUID(unixMicrosToRawTimestamp(unixMicros), uniqueLsb);
     }

     public static UUID atUnixMicrosWithLsbAsUUID(long unixMicros, long uniqueLsb)
     {
         return new UUID(rawTimestampToMsb(unixMicrosToRawTimestamp(unixMicros)), uniqueLsb);
     }

     /**
      * Returns the smaller possible type 1 UUID having the provided timestamp.
      *
      * <b>Warning:</b> this method should only be used for querying as this
      * doesn't at all guarantee the uniqueness of the resulting UUID.
      */
     public static TimeUUID minAtUnixMillis(long unixMillis)
     {
         return new TimeUUID(unixMillisToRawTimestamp(unixMillis, 0), MIN_CLOCK_SEQ_AND_NODE);
     }

     /**
      * Returns the biggest possible type 1 UUID having the provided timestamp.
      *
      * <b>Warning:</b> this method should only be used for querying as this
      * doesn't at all guarantee the uniqueness of the resulting UUID.
      */
     public static TimeUUID maxAtUnixMillis(long unixMillis)
     {
         return new TimeUUID(unixMillisToRawTimestamp(unixMillis + 1, 0) - 1, MAX_CLOCK_SEQ_AND_NODE);
     }

     public static TimeUUID fromString(String uuidString)
     {
         return fromUuid(UUID.fromString(uuidString));
     }

     public static TimeUUID fromUuid(UUID uuid)
     {
         return fromBytes(uuid.getMostSignificantBits(), uuid.getLeastSignificantBits());
     }

     public static TimeUUID fromBytes(long msb, long lsb)
     {
         return new TimeUUID(msbToRawTimestamp(msb), lsb);
     }

     public static TimeUUID deserialize(ByteBuffer buffer)
     {
         return fromBytes(buffer.getLong(buffer.position()), buffer.getLong(buffer.position() + 8));
     }

     public static TimeUUID deserialize(DataInput in) throws IOException
     {
         long msb = in.readLong();
         long lsb = in.readLong();
         return fromBytes(msb, lsb);
     }

     public void serialize(DataOutput out) throws IOException
     {
         out.writeLong(msb());
         out.writeLong(lsb());
     }

     public ByteBuffer toBytes()
     {
         return ByteBuffer.wrap(toBytes(msb(), lsb()));
     }

     public static byte[] toBytes(long msb, long lsb)
     {
         byte[] uuidBytes = new byte[16];

         for (int i = 0; i < 8; i++)
             uuidBytes[i] = (byte) (msb >>> 8 * (7 - i));

         for (int i = 8; i < 16; i++)
             uuidBytes[i] = (byte) (lsb >>> 8 * (15 - i));

         return uuidBytes;
     }

     public static long sizeInBytes()
     {
         return 16;
     }

     public UUID asUUID()
     {
         return new UUID(rawTimestampToMsb(uuidTimestamp), lsb);
     }

     /**
      * The Cassandra internal micros-resolution timestamp of the TimeUUID, as of unix epoch
      */
     public long unix(TimeUnit units)
     {
         return units.convert(unixMicros(), MICROSECONDS);
     }

     /**
      * The Cassandra internal micros-resolution timestamp of the TimeUUID, as of unix epoch
      */
     public long unixMicros()
     {
         return rawTimestampToUnixMicros(uuidTimestamp);
     }

     /**
      * The UUID-format timestamp, i.e. 10x micros-resolution, as of UUIDGen.UUID_EPOCH_UNIX_MILLIS
      * The tenths of a microsecond are used to store a flag value.
      */
     public long uuidTimestamp()
     {
         return uuidTimestamp & 0x0FFFFFFFFFFFFFFFL;
     }

     public long msb()
     {
         return rawTimestampToMsb(uuidTimestamp);
     }

     public long lsb()
     {
         return lsb;
     }

     public static long rawTimestampToUnixMicros(long rawTimestamp)
     {
         return (rawTimestamp / 10) + UUID_EPOCH_UNIX_MILLIS * 1000;
     }

     public static long unixMillisToRawTimestamp(long unixMillis, long tenthsOfAMicro)
     {
         return unixMillis * 10000 - (UUID_EPOCH_UNIX_MILLIS * 10000) + tenthsOfAMicro;
     }

     public static long unixMicrosToRawTimestamp(long unixMicros)
     {
         return unixMicros * 10 - (UUID_EPOCH_UNIX_MILLIS * 10000);
     }

     public static long msbToRawTimestamp(long msb)
     {
         assert (UUID_VERSION_BITS_IN_MSB & msb) == TIMESTAMP_UUID_VERSION_IN_MSB;
         msb &= ~TIMESTAMP_UUID_VERSION_IN_MSB;
         return   (msb &     0xFFFFL) << 48
                | (msb & 0xFFFF0000L) << 16
                | (msb >>> 32);
     }

     public static long rawTimestampToMsb(long rawTimestamp)
     {
         return TIMESTAMP_UUID_VERSION_IN_MSB
                | (rawTimestamp >>> 48)
                | ((rawTimestamp & 0xFFFF00000000L) >>> 16)
                | (rawTimestamp << 32);
     }

     @Override
     public int hashCode()
     {
         return (int) ((uuidTimestamp ^ (uuidTimestamp >> 32) * 31) + (lsb ^ (lsb >> 32)));
     }

     @Override
     public boolean equals(Object that)
     {
         return    (that instanceof UUID && equals((UUID) that))
                || (that instanceof TimeUUID && equals((TimeUUID) that));
     }

     public boolean equals(TimeUUID that)
     {
         return that != null && uuidTimestamp == that.uuidTimestamp && lsb == that.lsb;
     }

     public boolean equals(UUID that)
     {
         return that != null && uuidTimestamp == that.timestamp() && lsb == that.getLeastSignificantBits();
     }

     @Override
     public String toString()
     {
         return asUUID().toString();
     }

     public static String toString(TimeUUID ballot)
     {
         return ballot == null ? "null" : ballot.uuidTimestamp() + ":" + ballot;
     }

     public static String toString(TimeUUID ballot, String kind)
     {
         return ballot == null ? "null" : String.format("%s(%d:%s)", kind, ballot.uuidTimestamp(), ballot);
     }

     @Override
     public int compareTo(TimeUUID that)
     {
         return this.uuidTimestamp != that.uuidTimestamp
                ? Long.compare(this.uuidTimestamp, that.uuidTimestamp)
                : Long.compare(this.lsb, that.lsb);
     }

     protected static abstract class AbstractSerializer<T extends TimeUUID> extends TypeSerializer<T>
     {
         public <V> void validate(V value, ValueAccessor<V> accessor) throws MarshalException
         {
             if (accessor.isEmpty(value))
                 return;

             if (accessor.size(value) != 16)
                 throw new MarshalException(String.format("UUID should be 16 or 0 bytes (%d)", accessor.size(value)));

             if ((accessor.getByte(value, 6) & 0xf0) != 0x10)
                 throw new MarshalException(String.format("Invalid version for TimeUUID type: 0x%s", Integer.toHexString((accessor.getByte(value, 0) >> 4) & 0xf)));
         }

         public String toString(T value)
         {
             return value == null ? "" : value.toString();
         }

         public ByteBuffer serialize(T value)
         {
             if (value == null)
                 return EMPTY_BYTE_BUFFER;
             ByteBuffer buffer = ByteBuffer.allocate(16);
             buffer.putLong(value.msb());
             buffer.putLong(value.lsb());
             buffer.flip();
             return buffer;
         }
     }

     public static class Serializer extends AbstractSerializer<TimeUUID> implements IVersionedSerializer<TimeUUID>
     {
         public static final Serializer instance = new Serializer();

         public <V> TimeUUID deserialize(V value, ValueAccessor<V> accessor)
         {
             return accessor.isEmpty(value) ? null : accessor.toTimeUUID(value);
         }

         public Class<TimeUUID> getType()
         {
             return TimeUUID.class;
         }

         @Override
         public void serialize(TimeUUID t, DataOutputPlus out, int version) throws IOException
         {
             t.serialize(out);
         }

         @Override
         public TimeUUID deserialize(DataInputPlus in, int version) throws IOException
         {
             return TimeUUID.deserialize(in);
         }

         @Override
         public long serializedSize(TimeUUID t, int version)
         {
             return 16;
         }
     }

     public static class Generator
     {
         private static final long clockSeqAndNode = makeClockSeqAndNode();

         private static final AtomicLong lastMicros = new AtomicLong();

         public static TimeUUID nextTimeUUID()
         {
             return atUnixMicrosWithLsb(nextUnixMicros(), clockSeqAndNode);
         }

         public static UUID nextTimeAsUUID()
         {
             return atUnixMicrosWithLsbAsUUID(nextUnixMicros(), clockSeqAndNode);
         }

         public static TimeUUID atUnixMillis(long unixMillis)
         {
             return atUnixMillis(unixMillis, 0);
         }

         public static TimeUUID atUnixMillis(long unixMillis, long tenthsOfAMicro)
         {
             return new TimeUUID(unixMillisToRawTimestamp(unixMillis, tenthsOfAMicro), clockSeqAndNode);
         }

         public static byte[] atUnixMillisAsBytes(long unixMillis)
         {
             return atUnixMillisAsBytes(unixMillis, 0);
         }

         public static byte[] atUnixMillisAsBytes(long unixMillis, long tenthsOfAMicro)
         {
             return toBytes(rawTimestampToMsb(unixMillisToRawTimestamp(unixMillis, tenthsOfAMicro)), clockSeqAndNode);
         }

         public static byte[] nextTimeUUIDAsBytes()
         {
             return toBytes(rawTimestampToMsb(unixMicrosToRawTimestamp(nextUnixMicros())), clockSeqAndNode);
         }

         // needs to return two different values for the same when.
         // we can generate at most 10k UUIDs per ms.
         private static long nextUnixMicros()
         {
             long newLastMicros;
             while (true)
             {
                 //Generate a candidate value for new lastNanos
                 newLastMicros = currentTimeMillis() * 1000;
                 long originalLastNanos = lastMicros.get();
                 if (newLastMicros > originalLastNanos)
                 {
                     //Slow path once per millisecond do a CAS
                     if (lastMicros.compareAndSet(originalLastNanos, newLastMicros))
                     {
                         break;
                     }
                 }
                 else
                 {
                     //Fast path do an atomic increment
                     //Or when falling behind this will move time forward past the clock if necessary
                     newLastMicros = lastMicros.incrementAndGet();
                     break;
                 }
             }
             return newLastMicros;
         }

         private static long makeClockSeqAndNode()
         {
             if (DETERMINISM_UNSAFE_UUID_NODE.getBoolean())
                 return FBUtilities.getBroadcastAddressAndPort().addressBytes[3];

             if (CASSANDRA_UNSAFE_TIME_UUID_NODE.isPresent())
                 return CASSANDRA_UNSAFE_TIME_UUID_NODE.getLong()
                        ^ FBUtilities.getBroadcastAddressAndPort().addressBytes[3]
                        ^ (FBUtilities.getBroadcastAddressAndPort().addressBytes[2] << 8);

             long clock = new SecureRandom().nextLong();

             long lsb = 0;
             lsb |= 0x8000000000000000L;                 // variant (2 bits)
             lsb |= (clock & 0x0000000000003FFFL) << 48; // clock sequence (14 bits)
             lsb |= makeNode();                          // 6 bytes
             return lsb;
         }

         private static long makeNode()
         {
             /*
              * We don't have access to the MAC address but need to generate a node part
              * that identify this host as uniquely as possible.
              * The spec says that one option is to take as many source that identify
              * this node as possible and hash them together. That's what we do here by
              * gathering all the ip of this host.
              * Note that FBUtilities.getJustBroadcastAddress() should be enough to uniquely
              * identify the node *in the cluster* but it triggers DatabaseDescriptor
              * instanciation and the UUID generator is used in Stress for instance,
              * where we don't want to require the yaml.
              */
             Collection<InetAddressAndPort> localAddresses = getAllLocalAddresses();
             if (localAddresses.isEmpty())
                 throw new RuntimeException("Cannot generate the node component of the UUID because cannot retrieve any IP addresses.");

             // ideally, we'd use the MAC address, but java doesn't expose that.
             byte[] hash = hash(localAddresses);
             long node = 0;
             for (int i = 0; i < Math.min(6, hash.length); i++)
                 node |= (0x00000000000000ff & (long)hash[i]) << (5-i)*8;
             assert (0xff00000000000000L & node) == 0;

             // Since we don't use the mac address, the spec says that multicast
             // bit (least significant bit of the first octet of the node ID) must be 1.
             return node | 0x0000010000000000L;
         }

         private static byte[] hash(Collection<InetAddressAndPort> data)
         {
             // Identify the host.
             Hasher hasher = Hashing.md5().newHasher();
             for(InetAddressAndPort addr : data)
             {
                 hasher.putBytes(addr.addressBytes);
                 hasher.putInt(addr.getPort());
             }

             // Identify the process on the load: we use both the PID and class loader hash.
             long pid = NativeLibrary.getProcessID();
             if (pid < 0)
                 pid = new Random(currentTimeMillis()).nextLong();
             updateWithLong(hasher, pid);

             ClassLoader loader = UUIDGen.class.getClassLoader();
             int loaderId = loader != null ? System.identityHashCode(loader) : 0;
             updateWithInt(hasher, loaderId);

             return hasher.hash().asBytes();
         }

         private static void updateWithInt(Hasher hasher, int val)
         {
             hasher.putByte((byte) ((val >>> 24) & 0xFF));
             hasher.putByte((byte) ((val >>> 16) & 0xFF));
             hasher.putByte((byte) ((val >>>  8) & 0xFF));
             hasher.putByte((byte) ((val >>> 0) & 0xFF));
         }

         public static void updateWithLong(Hasher hasher, long val)
         {
             hasher.putByte((byte) ((val >>> 56) & 0xFF));
             hasher.putByte((byte) ((val >>> 48) & 0xFF));
             hasher.putByte((byte) ((val >>> 40) & 0xFF));
             hasher.putByte((byte) ((val >>> 32) & 0xFF));
             hasher.putByte((byte) ((val >>> 24) & 0xFF));
             hasher.putByte((byte) ((val >>> 16) & 0xFF));
             hasher.putByte((byte) ((val >>>  8) & 0xFF));
             hasher.putByte((byte)  ((val >>> 0) & 0xFF));
         }

         /**
          * Helper function used exclusively by UUIDGen to create
          **/
         public static Collection<InetAddressAndPort> getAllLocalAddresses()
         {
             Set<InetAddressAndPort> localAddresses = new HashSet<>();
             try
             {
                 Enumeration<NetworkInterface> nets = NetworkInterface.getNetworkInterfaces();
                 if (nets != null)
                 {
                     while (nets.hasMoreElements())
                     {
                         Function<InetAddress, InetAddressAndPort> converter =
                         address -> InetAddressAndPort.getByAddressOverrideDefaults(address, 0);
                         List<InetAddressAndPort> addresses =
                         Collections.list(nets.nextElement().getInetAddresses()).stream().map(converter).collect(Collectors.toList());
                         localAddresses.addAll(addresses);
                     }
                 }
             }
             catch (SocketException e)
             {
                 throw new AssertionError(e);
             }
             if (DatabaseDescriptor.isDaemonInitialized())
             {
                 localAddresses.add(FBUtilities.getBroadcastAddressAndPort());
                 localAddresses.add(FBUtilities.getBroadcastNativeAddressAndPort());
                 localAddresses.add(FBUtilities.getLocalAddressAndPort());
             }
             return localAddresses;
         }
     }
 }

 // ---Copied from UUIDGen
 // for the curious, here is how I generated START_EPOCH
 //        Calendar c = Calendar.getInstance(TimeZone.getTimeZone("GMT-0"));
 //        c.set(Calendar.YEAR, 1582);
 //        c.set(Calendar.MONTH, Calendar.OCTOBER);
 //        c.set(Calendar.DAY_OF_MONTH, 15);
 //        c.set(Calendar.HOUR_OF_DAY, 0);
 //        c.set(Calendar.MINUTE, 0);
 //        c.set(Calendar.SECOND, 0);
 //        c.set(Calendar.MILLISECOND, 0);
 //        long START_EPOCH = c.getTimeInMillis();
	/*
	* Licensed to the Apache Software Foundation (ASF) under one
	* or more contributor license agreements. See the NOTICE file
	* distributed with this work for additional information
	* regarding copyright ownership. The ASF licenses this file
	* to you under the Apache License, Version 2.0 (the
	* "License"); you may not use this file except in compliance
	* with the License. You may obtain a copy of the License at
	*
	* http://www.apache.org/licenses/LICENSE-2.0
	*
	* Unless required by applicable law or agreed to in writing, software
	* distributed under the License is distributed on an "AS IS" BASIS,
	* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
	* See the License for the specific language governing permissions and
	* limitations under the License.
	*/

	package org.apache.cassandra.utils;

	import java.io.DataInput;
	import java.io.DataOutput;
	import java.io.IOException;
	import java.io.Serializable;
	import java.net.InetAddress;
	import java.net.NetworkInterface;
	import java.net.SocketException;
	import java.nio.ByteBuffer;
	import java.security.SecureRandom;
	import java.util.Collection;
	import java.util.Collections;
	import java.util.Enumeration;
	import java.util.HashSet;
	import java.util.List;
	import java.util.Random;
	import java.util.Set;
	import java.util.UUID;
	import java.util.concurrent.TimeUnit;
	import java.util.concurrent.atomic.AtomicLong;
	import java.util.function.Function;
	import java.util.stream.Collectors;

	import com.google.common.hash.Hasher;
	import com.google.common.hash.Hashing;

	import org.apache.cassandra.config.DatabaseDescriptor;
	import org.apache.cassandra.db.marshal.ValueAccessor;
	import org.apache.cassandra.io.IVersionedSerializer;
	import org.apache.cassandra.io.util.DataInputPlus;
	import org.apache.cassandra.io.util.DataOutputPlus;
	import org.apache.cassandra.locator.InetAddressAndPort;
	import org.apache.cassandra.serializers.MarshalException;
	import org.apache.cassandra.serializers.TypeSerializer;

	import static java.util.concurrent.TimeUnit.MICROSECONDS;
	import static org.apache.cassandra.config.CassandraRelevantProperties.CASSANDRA_UNSAFE_TIME_UUID_NODE;
	import static org.apache.cassandra.config.CassandraRelevantProperties.DETERMINISM_UNSAFE_UUID_NODE;
	import static org.apache.cassandra.utils.ByteBufferUtil.EMPTY_BYTE_BUFFER;
	import static org.apache.cassandra.utils.Clock.Global.currentTimeMillis;
	import static org.apache.cassandra.utils.Shared.Recursive.INTERFACES;

	@Shared(inner = INTERFACES)
	public class TimeUUID implements Serializable, Comparable<TimeUUID>
	{
	public static final long serialVersionUID = 1L;

	// A grand day! millis at 00:00:00.000 15 Oct 1582.
	public static final long UUID_EPOCH_UNIX_MILLIS = -12219292800000L;
	protected static final long TIMESTAMP_UUID_VERSION_IN_MSB = 0x1000L;
	protected static final long UUID_VERSION_BITS_IN_MSB = 0xf000L;

	/*
	* The min and max possible lsb for a UUID.
	* Note that his is not 0 and all 1's because Cassandra TimeUUIDType
	* compares the lsb parts as a signed byte array comparison. So the min
	* value is 8 times -128 and the max is 8 times +127.
	*
	* Note that we ignore the uuid variant (namely, MIN_CLOCK_SEQ_AND_NODE
	* have variant 2 as it should, but MAX_CLOCK_SEQ_AND_NODE have variant 0).
	* I don't think that has any practical consequence and is more robust in
	* case someone provides a UUID with a broken variant.
	*/
	private static final long MIN_CLOCK_SEQ_AND_NODE = 0x8080808080808080L;
	private static final long MAX_CLOCK_SEQ_AND_NODE = 0x7f7f7f7f7f7f7f7fL;

	public static final long TIMEUUID_SIZE = ObjectSizes.measureDeep(new TimeUUID(10, 10));

	final long uuidTimestamp, lsb;

	public TimeUUID(long uuidTimestamp, long lsb)
	{
	// we don't validate that this is a true TIMEUUID to avoid problems with historical mixing of UUID with TimeUUID
	this.uuidTimestamp = uuidTimestamp;
	this.lsb = lsb;
	}

	public static TimeUUID atUnixMicrosWithLsb(long unixMicros, long uniqueLsb)
	{
	return new TimeUUID(unixMicrosToRawTimestamp(unixMicros), uniqueLsb);
	}

	public static UUID atUnixMicrosWithLsbAsUUID(long unixMicros, long uniqueLsb)
	{
	return new UUID(rawTimestampToMsb(unixMicrosToRawTimestamp(unixMicros)), uniqueLsb);
	}

	/**
	* Returns the smaller possible type 1 UUID having the provided timestamp.
	*
	* <b>Warning:</b> this method should only be used for querying as this
	* doesn't at all guarantee the uniqueness of the resulting UUID.
	*/
	public static TimeUUID minAtUnixMillis(long unixMillis)
	{
	return new TimeUUID(unixMillisToRawTimestamp(unixMillis, 0), MIN_CLOCK_SEQ_AND_NODE);
	}

	/**
	* Returns the biggest possible type 1 UUID having the provided timestamp.
	*
	* <b>Warning:</b> this method should only be used for querying as this
	* doesn't at all guarantee the uniqueness of the resulting UUID.
	*/
	public static TimeUUID maxAtUnixMillis(long unixMillis)
	{
	return new TimeUUID(unixMillisToRawTimestamp(unixMillis + 1, 0) - 1, MAX_CLOCK_SEQ_AND_NODE);
	}

	public static TimeUUID fromString(String uuidString)
	{
	return fromUuid(UUID.fromString(uuidString));
	}

	public static TimeUUID fromUuid(UUID uuid)
	{
	return fromBytes(uuid.getMostSignificantBits(), uuid.getLeastSignificantBits());
	}

	public static TimeUUID fromBytes(long msb, long lsb)
	{
	return new TimeUUID(msbToRawTimestamp(msb), lsb);
	}

	public static TimeUUID deserialize(ByteBuffer buffer)
	{
	return fromBytes(buffer.getLong(buffer.position()), buffer.getLong(buffer.position() + 8));
	}

	public static TimeUUID deserialize(DataInput in) throws IOException
	{
	long msb = in.readLong();
	long lsb = in.readLong();
	return fromBytes(msb, lsb);
	}

	public void serialize(DataOutput out) throws IOException
	{
	out.writeLong(msb());
	out.writeLong(lsb());
	}

	public ByteBuffer toBytes()
	{
	return ByteBuffer.wrap(toBytes(msb(), lsb()));
	}

	public static byte[] toBytes(long msb, long lsb)
	{
	byte[] uuidBytes = new byte[16];

	for (int i = 0; i < 8; i++)
	uuidBytes[i] = (byte) (msb >>> 8 * (7 - i));

	for (int i = 8; i < 16; i++)
	uuidBytes[i] = (byte) (lsb >>> 8 * (15 - i));

	return uuidBytes;
	}

	public static long sizeInBytes()
	{
	return 16;
	}

	public UUID asUUID()
	{
	return new UUID(rawTimestampToMsb(uuidTimestamp), lsb);
	}

	/**
	* The Cassandra internal micros-resolution timestamp of the TimeUUID, as of unix epoch
	*/
	public long unix(TimeUnit units)
	{
	return units.convert(unixMicros(), MICROSECONDS);
	}

	/**
	* The Cassandra internal micros-resolution timestamp of the TimeUUID, as of unix epoch
	*/
	public long unixMicros()
	{
	return rawTimestampToUnixMicros(uuidTimestamp);
	}

	/**
	* The UUID-format timestamp, i.e. 10x micros-resolution, as of UUIDGen.UUID_EPOCH_UNIX_MILLIS
	* The tenths of a microsecond are used to store a flag value.
	*/
	public long uuidTimestamp()
	{
	return uuidTimestamp & 0x0FFFFFFFFFFFFFFFL;
	}

	public long msb()
	{
	return rawTimestampToMsb(uuidTimestamp);
	}

	public long lsb()
	{
	return lsb;
	}

	public static long rawTimestampToUnixMicros(long rawTimestamp)
	{
	return (rawTimestamp / 10) + UUID_EPOCH_UNIX_MILLIS * 1000;
	}

	public static long unixMillisToRawTimestamp(long unixMillis, long tenthsOfAMicro)
	{
	return unixMillis * 10000 - (UUID_EPOCH_UNIX_MILLIS * 10000) + tenthsOfAMicro;
	}

	public static long unixMicrosToRawTimestamp(long unixMicros)
	{
	return unixMicros * 10 - (UUID_EPOCH_UNIX_MILLIS * 10000);
	}

	public static long msbToRawTimestamp(long msb)
	{
	assert (UUID_VERSION_BITS_IN_MSB & msb) == TIMESTAMP_UUID_VERSION_IN_MSB;
	msb &= ~TIMESTAMP_UUID_VERSION_IN_MSB;
	return (msb & 0xFFFFL) << 48
	\| (msb & 0xFFFF0000L) << 16
	\| (msb >>> 32);
	}

	public static long rawTimestampToMsb(long rawTimestamp)
	{
	return TIMESTAMP_UUID_VERSION_IN_MSB
	\| (rawTimestamp >>> 48)
	\| ((rawTimestamp & 0xFFFF00000000L) >>> 16)
	\| (rawTimestamp << 32);
	}

	@Override
	public int hashCode()
	{
	return (int) ((uuidTimestamp ^ (uuidTimestamp >> 32) * 31) + (lsb ^ (lsb >> 32)));
	}

	@Override
	public boolean equals(Object that)
	{
	return (that instanceof UUID && equals((UUID) that))
	\|\| (that instanceof TimeUUID && equals((TimeUUID) that));
	}

	public boolean equals(TimeUUID that)
	{
	return that != null && uuidTimestamp == that.uuidTimestamp && lsb == that.lsb;
	}

	public boolean equals(UUID that)
	{
	return that != null && uuidTimestamp == that.timestamp() && lsb == that.getLeastSignificantBits();
	}

	@Override
	public String toString()
	{
	return asUUID().toString();
	}

	public static String toString(TimeUUID ballot)
	{
	return ballot == null ? "null" : ballot.uuidTimestamp() + ":" + ballot;
	}

	public static String toString(TimeUUID ballot, String kind)
	{
	return ballot == null ? "null" : String.format("%s(%d:%s)", kind, ballot.uuidTimestamp(), ballot);
	}

	@Override
	public int compareTo(TimeUUID that)
	{
	return this.uuidTimestamp != that.uuidTimestamp
	? Long.compare(this.uuidTimestamp, that.uuidTimestamp)
	: Long.compare(this.lsb, that.lsb);
	}

	protected static abstract class AbstractSerializer<T extends TimeUUID> extends TypeSerializer<T>
	{
	public <V> void validate(V value, ValueAccessor<V> accessor) throws MarshalException
	{
	if (accessor.isEmpty(value))
	return;

	if (accessor.size(value) != 16)
	throw new MarshalException(String.format("UUID should be 16 or 0 bytes (%d)", accessor.size(value)));

	if ((accessor.getByte(value, 6) & 0xf0) != 0x10)
	throw new MarshalException(String.format("Invalid version for TimeUUID type: 0x%s", Integer.toHexString((accessor.getByte(value, 0) >> 4) & 0xf)));
	}

	public String toString(T value)
	{
	return value == null ? "" : value.toString();
	}

	public ByteBuffer serialize(T value)
	{
	if (value == null)
	return EMPTY_BYTE_BUFFER;
	ByteBuffer buffer = ByteBuffer.allocate(16);
	buffer.putLong(value.msb());
	buffer.putLong(value.lsb());
	buffer.flip();
	return buffer;
	}
	}

	public static class Serializer extends AbstractSerializer<TimeUUID> implements IVersionedSerializer<TimeUUID>
	{
	public static final Serializer instance = new Serializer();

	public <V> TimeUUID deserialize(V value, ValueAccessor<V> accessor)
	{
	return accessor.isEmpty(value) ? null : accessor.toTimeUUID(value);
	}

	public Class<TimeUUID> getType()
	{
	return TimeUUID.class;
	}

	@Override
	public void serialize(TimeUUID t, DataOutputPlus out, int version) throws IOException
	{
	t.serialize(out);
	}

	@Override
	public TimeUUID deserialize(DataInputPlus in, int version) throws IOException
	{
	return TimeUUID.deserialize(in);
	}

	@Override
	public long serializedSize(TimeUUID t, int version)
	{
	return 16;
	}
	}

	public static class Generator
	{
	private static final long clockSeqAndNode = makeClockSeqAndNode();

	private static final AtomicLong lastMicros = new AtomicLong();

	public static TimeUUID nextTimeUUID()
	{
	return atUnixMicrosWithLsb(nextUnixMicros(), clockSeqAndNode);
	}

	public static UUID nextTimeAsUUID()
	{
	return atUnixMicrosWithLsbAsUUID(nextUnixMicros(), clockSeqAndNode);
	}

	public static TimeUUID atUnixMillis(long unixMillis)
	{
	return atUnixMillis(unixMillis, 0);
	}

	public static TimeUUID atUnixMillis(long unixMillis, long tenthsOfAMicro)
	{
	return new TimeUUID(unixMillisToRawTimestamp(unixMillis, tenthsOfAMicro), clockSeqAndNode);
	}

	public static byte[] atUnixMillisAsBytes(long unixMillis)
	{
	return atUnixMillisAsBytes(unixMillis, 0);
	}

	public static byte[] atUnixMillisAsBytes(long unixMillis, long tenthsOfAMicro)
	{
	return toBytes(rawTimestampToMsb(unixMillisToRawTimestamp(unixMillis, tenthsOfAMicro)), clockSeqAndNode);
	}

	public static byte[] nextTimeUUIDAsBytes()
	{
	return toBytes(rawTimestampToMsb(unixMicrosToRawTimestamp(nextUnixMicros())), clockSeqAndNode);
	}

	// needs to return two different values for the same when.
	// we can generate at most 10k UUIDs per ms.
	private static long nextUnixMicros()
	{
	long newLastMicros;
	while (true)
	{
	//Generate a candidate value for new lastNanos
	newLastMicros = currentTimeMillis() * 1000;
	long originalLastNanos = lastMicros.get();
	if (newLastMicros > originalLastNanos)
	{
	//Slow path once per millisecond do a CAS
	if (lastMicros.compareAndSet(originalLastNanos, newLastMicros))
	{
	break;
	}
	}
	else
	{
	//Fast path do an atomic increment
	//Or when falling behind this will move time forward past the clock if necessary
	newLastMicros = lastMicros.incrementAndGet();
	break;
	}
	}
	return newLastMicros;
	}

	private static long makeClockSeqAndNode()
	{
	if (DETERMINISM_UNSAFE_UUID_NODE.getBoolean())
	return FBUtilities.getBroadcastAddressAndPort().addressBytes[3];

	if (CASSANDRA_UNSAFE_TIME_UUID_NODE.isPresent())
	return CASSANDRA_UNSAFE_TIME_UUID_NODE.getLong()
	^ FBUtilities.getBroadcastAddressAndPort().addressBytes[3]
	^ (FBUtilities.getBroadcastAddressAndPort().addressBytes[2] << 8);

	long clock = new SecureRandom().nextLong();

	long lsb = 0;
	lsb \|= 0x8000000000000000L; // variant (2 bits)
	lsb \|= (clock & 0x0000000000003FFFL) << 48; // clock sequence (14 bits)
	lsb \|= makeNode(); // 6 bytes
	return lsb;
	}

	private static long makeNode()
	{
	/*
	* We don't have access to the MAC address but need to generate a node part
	* that identify this host as uniquely as possible.
	* The spec says that one option is to take as many source that identify
	* this node as possible and hash them together. That's what we do here by
	* gathering all the ip of this host.
	* Note that FBUtilities.getJustBroadcastAddress() should be enough to uniquely
	* identify the node in the cluster but it triggers DatabaseDescriptor
	* instanciation and the UUID generator is used in Stress for instance,
	* where we don't want to require the yaml.
	*/
	Collection<InetAddressAndPort> localAddresses = getAllLocalAddresses();
	if (localAddresses.isEmpty())
	throw new RuntimeException("Cannot generate the node component of the UUID because cannot retrieve any IP addresses.");

	// ideally, we'd use the MAC address, but java doesn't expose that.
	byte[] hash = hash(localAddresses);
	long node = 0;
	for (int i = 0; i < Math.min(6, hash.length); i++)
	node \|= (0x00000000000000ff & (long)hash[i]) << (5-i)*8;
	assert (0xff00000000000000L & node) == 0;

	// Since we don't use the mac address, the spec says that multicast
	// bit (least significant bit of the first octet of the node ID) must be 1.
	return node \| 0x0000010000000000L;
	}

	private static byte[] hash(Collection<InetAddressAndPort> data)
	{
	// Identify the host.
	Hasher hasher = Hashing.md5().newHasher();
	for(InetAddressAndPort addr : data)
	{
	hasher.putBytes(addr.addressBytes);
	hasher.putInt(addr.getPort());
	}

	// Identify the process on the load: we use both the PID and class loader hash.
	long pid = NativeLibrary.getProcessID();
	if (pid < 0)
	pid = new Random(currentTimeMillis()).nextLong();
	updateWithLong(hasher, pid);

	ClassLoader loader = UUIDGen.class.getClassLoader();
	int loaderId = loader != null ? System.identityHashCode(loader) : 0;
	updateWithInt(hasher, loaderId);

	return hasher.hash().asBytes();
	}

	private static void updateWithInt(Hasher hasher, int val)
	{
	hasher.putByte((byte) ((val >>> 24) & 0xFF));
	hasher.putByte((byte) ((val >>> 16) & 0xFF));
	hasher.putByte((byte) ((val >>> 8) & 0xFF));
	hasher.putByte((byte) ((val >>> 0) & 0xFF));
	}

	public static void updateWithLong(Hasher hasher, long val)
	{
	hasher.putByte((byte) ((val >>> 56) & 0xFF));
	hasher.putByte((byte) ((val >>> 48) & 0xFF));
	hasher.putByte((byte) ((val >>> 40) & 0xFF));
	hasher.putByte((byte) ((val >>> 32) & 0xFF));
	hasher.putByte((byte) ((val >>> 24) & 0xFF));
	hasher.putByte((byte) ((val >>> 16) & 0xFF));
	hasher.putByte((byte) ((val >>> 8) & 0xFF));
	hasher.putByte((byte) ((val >>> 0) & 0xFF));
	}

	/**
	* Helper function used exclusively by UUIDGen to create
	**/
	public static Collection<InetAddressAndPort> getAllLocalAddresses()
	{
	Set<InetAddressAndPort> localAddresses = new HashSet<>();
	try
	{
	Enumeration<NetworkInterface> nets = NetworkInterface.getNetworkInterfaces();
	if (nets != null)
	{
	while (nets.hasMoreElements())
	{
	Function<InetAddress, InetAddressAndPort> converter =
	address -> InetAddressAndPort.getByAddressOverrideDefaults(address, 0);
	List<InetAddressAndPort> addresses =
	Collections.list(nets.nextElement().getInetAddresses()).stream().map(converter).collect(Collectors.toList());
	localAddresses.addAll(addresses);
	}
	}
	}
	catch (SocketException e)
	{
	throw new AssertionError(e);
	}
	if (DatabaseDescriptor.isDaemonInitialized())
	{
	localAddresses.add(FBUtilities.getBroadcastAddressAndPort());
	localAddresses.add(FBUtilities.getBroadcastNativeAddressAndPort());
	localAddresses.add(FBUtilities.getLocalAddressAndPort());
	}
	return localAddresses;
	}
	}
	}

	// ---Copied from UUIDGen
	// for the curious, here is how I generated START_EPOCH
	// Calendar c = Calendar.getInstance(TimeZone.getTimeZone("GMT-0"));
	// c.set(Calendar.YEAR, 1582);
	// c.set(Calendar.MONTH, Calendar.OCTOBER);
	// c.set(Calendar.DAY_OF_MONTH, 15);
	// c.set(Calendar.HOUR_OF_DAY, 0);
	// c.set(Calendar.MINUTE, 0);
	// c.set(Calendar.SECOND, 0);
	// c.set(Calendar.MILLISECOND, 0);
	// long START_EPOCH = c.getTimeInMillis();