cassandra-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From jmcken...@apache.org
Subject cassandra git commit: Use a CAS loop in UUIDGen instead of a sychronized block to improve performance under contention
Date Mon, 09 May 2016 00:22:46 GMT
Repository: cassandra
Updated Branches:
  refs/heads/trunk c662d876b -> d9083a9c2


Use a CAS loop in UUIDGen instead of a sychronized block to improve performance under contention

patch by Ariel Weisberg; reviewed by Joel Knighton for CASSANDRA-11517


Project: http://git-wip-us.apache.org/repos/asf/cassandra/repo
Commit: http://git-wip-us.apache.org/repos/asf/cassandra/commit/d9083a9c
Tree: http://git-wip-us.apache.org/repos/asf/cassandra/tree/d9083a9c
Diff: http://git-wip-us.apache.org/repos/asf/cassandra/diff/d9083a9c

Branch: refs/heads/trunk
Commit: d9083a9c2946dfc9d82e9784369abc3387c445a7
Parents: c662d87
Author: Ariel Weisberg <ariel.weisberg@datastax.com>
Authored: Wed Apr 6 15:26:37 2016 -0400
Committer: Josh McKenzie <josh.mckenzie@datastax.com>
Committed: Sun May 8 20:22:13 2016 -0400

----------------------------------------------------------------------
 .../org/apache/cassandra/utils/UUIDGen.java     | 37 +++++++++----
 .../org/apache/cassandra/utils/UUIDTests.java   | 57 ++++++++++++++++++++
 2 files changed, 83 insertions(+), 11 deletions(-)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/cassandra/blob/d9083a9c/src/java/org/apache/cassandra/utils/UUIDGen.java
----------------------------------------------------------------------
diff --git a/src/java/org/apache/cassandra/utils/UUIDGen.java b/src/java/org/apache/cassandra/utils/UUIDGen.java
index bb15eae..ac73a47 100644
--- a/src/java/org/apache/cassandra/utils/UUIDGen.java
+++ b/src/java/org/apache/cassandra/utils/UUIDGen.java
@@ -25,10 +25,9 @@ import java.security.SecureRandom;
 import java.util.Collection;
 import java.util.Random;
 import java.util.UUID;
+import java.util.concurrent.atomic.AtomicLong;
 
 import com.google.common.annotations.VisibleForTesting;
-import com.google.common.base.Charsets;
-
 
 /**
  * The goods are here: www.ietf.org/rfc/rfc4122.txt.
@@ -56,7 +55,7 @@ public class UUIDGen
     // placement of this singleton is important.  It needs to be instantiated *AFTER* the
other statics.
     private static final UUIDGen instance = new UUIDGen();
 
-    private long lastNanos;
+    private AtomicLong lastNanos = new AtomicLong();
 
     private UUIDGen()
     {
@@ -260,15 +259,31 @@ public class UUIDGen
 
     // needs to return two different values for the same when.
     // we can generate at most 10k UUIDs per ms.
-    private synchronized long createTimeSafe()
+    private long createTimeSafe()
     {
-        long nanosSince = (System.currentTimeMillis() - START_EPOCH) * 10000;
-        if (nanosSince > lastNanos)
-            lastNanos = nanosSince;
-        else
-            nanosSince = ++lastNanos;
-
-        return createTime(nanosSince);
+        long newLastNanos;
+        while (true)
+        {
+            //Generate a candidate value for new lastNanos
+            newLastNanos = (System.currentTimeMillis() - START_EPOCH) * 10000;
+            long originalLastNanos = lastNanos.get();
+            if (newLastNanos > originalLastNanos)
+            {
+                //Slow path once per millisecond do a CAS
+                if (lastNanos.compareAndSet(originalLastNanos, newLastNanos))
+                {
+                    break;
+                }
+            }
+            else
+            {
+                //Fast path do an atomic increment
+                //Or when falling behind this will move time forward past the clock if necessary
+                newLastNanos = lastNanos.incrementAndGet();
+                break;
+            }
+        }
+        return createTime(newLastNanos);
     }
 
     private long createTimeUnsafe(long when, int nanos)

http://git-wip-us.apache.org/repos/asf/cassandra/blob/d9083a9c/test/unit/org/apache/cassandra/utils/UUIDTests.java
----------------------------------------------------------------------
diff --git a/test/unit/org/apache/cassandra/utils/UUIDTests.java b/test/unit/org/apache/cassandra/utils/UUIDTests.java
index ebe5fd1..0d57c47 100644
--- a/test/unit/org/apache/cassandra/utils/UUIDTests.java
+++ b/test/unit/org/apache/cassandra/utils/UUIDTests.java
@@ -22,12 +22,20 @@ package org.apache.cassandra.utils;
 
 
 import java.nio.ByteBuffer;
+import java.util.Set;
 import java.util.UUID;
+import java.util.concurrent.ExecutorService;
+import java.util.concurrent.Executors;
+import java.util.concurrent.TimeUnit;
+import java.util.concurrent.atomic.AtomicBoolean;
 
 import org.junit.Test;
 
+import com.google.common.collect.Sets;
+
 import org.apache.cassandra.db.marshal.TimeUUIDType;
 import org.apache.cassandra.utils.UUIDGen;
+import org.cliffc.high_scale_lib.NonBlockingHashMap;
 
 
 public class UUIDTests
@@ -88,4 +96,53 @@ public class UUIDTests
         // I'll be damn is the uuid timestamp is more than 10ms after now
         assert now <= tstamp && now >= tstamp - 10 : "now = " + now + ", timestamp
= " + tstamp;
     }
+
+    /*
+     * Don't ignore spurious failures of this test since it is testing concurrent access
+     * and might not fail reliably.
+     */
+    @Test
+    public void verifyConcurrentUUIDGeneration() throws Throwable
+    {
+        long iterations = 250000;
+        int threads = 4;
+        ExecutorService es = Executors.newFixedThreadPool(threads);
+        try
+        {
+            AtomicBoolean failedOrdering = new AtomicBoolean(false);
+            AtomicBoolean failedDuplicate = new AtomicBoolean(false);
+            Set<UUID> generated = Sets.newSetFromMap(new NonBlockingHashMap<>());
+            Runnable task = () -> {
+                long lastTimestamp = 0;
+                long newTimestamp = 0;
+
+                for (long i = 0; i < iterations; i++)
+                {
+                    UUID uuid = UUIDGen.getTimeUUID();
+                    newTimestamp = uuid.timestamp();
+
+                    if (lastTimestamp >= newTimestamp)
+                        failedOrdering.set(true);
+                    if (!generated.add(uuid))
+                        failedDuplicate.set(true);
+
+                    lastTimestamp = newTimestamp;
+                }
+            };
+
+            for (int i = 0; i < threads; i++)
+            {
+                es.execute(task);
+            }
+            es.shutdown();
+            es.awaitTermination(10, TimeUnit.MINUTES);
+
+            assert !failedOrdering.get();
+            assert !failedDuplicate.get();
+        }
+        finally
+        {
+            es.shutdown();
+        }
+    }
 }


Mime
View raw message