diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/ArtifactFunctionTestCase.java b/src/test/java/com/google/devtools/build/lib/skyframe/ArtifactFunctionTestCase.java
index 2f75f40..1a93420 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/ArtifactFunctionTestCase.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/ArtifactFunctionTestCase.java
@@ -49,7 +49,7 @@
 import java.util.concurrent.atomic.AtomicReference;
 
 abstract class ArtifactFunctionTestCase {
-  protected static final SkyKey OWNER_KEY = new SkyKey(SkyFunctions.ACTION_LOOKUP, "OWNER");
+  protected static final SkyKey OWNER_KEY = SkyKey.create(SkyFunctions.ACTION_LOOKUP, "OWNER");
   protected static final ActionLookupKey ALL_OWNER = new SingletonActionLookupKey();
 
   protected Predicate<PathFragment> allowedMissingInputsPredicate = Predicates.alwaysFalse();
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/TimestampBuilderTestCase.java b/src/test/java/com/google/devtools/build/lib/skyframe/TimestampBuilderTestCase.java
index 2218684..9ddfcb5 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/TimestampBuilderTestCase.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/TimestampBuilderTestCase.java
@@ -88,7 +88,7 @@
  */
 public abstract class TimestampBuilderTestCase extends FoundationTestCase {
 
-  private static final SkyKey OWNER_KEY = new SkyKey(SkyFunctions.ACTION_LOOKUP, "OWNER");
+  private static final SkyKey OWNER_KEY = SkyKey.create(SkyFunctions.ACTION_LOOKUP, "OWNER");
   protected static final ActionLookupValue.ActionLookupKey ALL_OWNER =
       new SingletonActionLookupKey();
   protected static final Predicate<Action> ALWAYS_EXECUTE_FILTER = Predicates.alwaysTrue();
diff --git a/src/test/java/com/google/devtools/build/skyframe/CyclesReporterTest.java b/src/test/java/com/google/devtools/build/skyframe/CyclesReporterTest.java
index 8179d13..ab17456 100644
--- a/src/test/java/com/google/devtools/build/skyframe/CyclesReporterTest.java
+++ b/src/test/java/com/google/devtools/build/skyframe/CyclesReporterTest.java
@@ -29,7 +29,7 @@
 @RunWith(JUnit4.class)
 public class CyclesReporterTest {
 
-  private static final SkyKey DUMMY_KEY = new SkyKey(SkyFunctionName.create("func"), "key");
+  private static final SkyKey DUMMY_KEY = SkyKey.create(SkyFunctionName.create("func"), "key");
 
   @Test
   public void nullEventHandler() {
diff --git a/src/test/java/com/google/devtools/build/skyframe/ErrorInfoTest.java b/src/test/java/com/google/devtools/build/skyframe/ErrorInfoTest.java
index 3e15000..4b04614 100644
--- a/src/test/java/com/google/devtools/build/skyframe/ErrorInfoTest.java
+++ b/src/test/java/com/google/devtools/build/skyframe/ErrorInfoTest.java
@@ -49,7 +49,7 @@
 
   private void runTestFromException(boolean isDirectlyTransient, boolean isTransitivelyTransient) {
     Exception exception = new IOException("ehhhhh");
-    SkyKey causeOfException = new SkyKey(SkyFunctionName.create("CAUSE"), 1234);
+    SkyKey causeOfException = SkyKey.create(SkyFunctionName.create("CAUSE"), 1234);
     DummySkyFunctionException dummyException =
         new DummySkyFunctionException(exception, isDirectlyTransient, /*isCatastrophic=*/ false);
 
@@ -87,9 +87,10 @@
 
   @Test
   public void testFromCycle() {
-    CycleInfo cycle = new CycleInfo(
-        ImmutableList.of(new SkyKey(SkyFunctionName.create("PATH"), 1234)),
-        ImmutableList.of(new SkyKey(SkyFunctionName.create("CYCLE"), 4321)));
+    CycleInfo cycle =
+        new CycleInfo(
+            ImmutableList.of(SkyKey.create(SkyFunctionName.create("PATH"), 1234)),
+            ImmutableList.of(SkyKey.create(SkyFunctionName.create("CYCLE"), 4321)));
 
     ErrorInfo errorInfo = ErrorInfo.fromCycle(cycle);
 
@@ -102,13 +103,14 @@
 
   @Test
   public void testFromChildErrors() {
-    CycleInfo cycle = new CycleInfo(
-        ImmutableList.of(new SkyKey(SkyFunctionName.create("PATH"), 1234)),
-        ImmutableList.of(new SkyKey(SkyFunctionName.create("CYCLE"), 4321)));
+    CycleInfo cycle =
+        new CycleInfo(
+            ImmutableList.of(SkyKey.create(SkyFunctionName.create("PATH"), 1234)),
+            ImmutableList.of(SkyKey.create(SkyFunctionName.create("CYCLE"), 4321)));
     ErrorInfo cycleErrorInfo = ErrorInfo.fromCycle(cycle);
 
     Exception exception1 = new IOException("ehhhhh");
-    SkyKey causeOfException1 = new SkyKey(SkyFunctionName.create("CAUSE1"), 1234);
+    SkyKey causeOfException1 = SkyKey.create(SkyFunctionName.create("CAUSE1"), 1234);
     DummySkyFunctionException dummyException1 =
         new DummySkyFunctionException(exception1, /*isTransient=*/ true, /*isCatastrophic=*/ false);
     ErrorInfo exceptionErrorInfo1 = ErrorInfo.fromException(
@@ -117,14 +119,14 @@
 
     // N.B this ErrorInfo will be catastrophic.
     Exception exception2 = new IOException("blahhhhh");
-    SkyKey causeOfException2 = new SkyKey(SkyFunctionName.create("CAUSE2"), 5678);
+    SkyKey causeOfException2 = SkyKey.create(SkyFunctionName.create("CAUSE2"), 5678);
     DummySkyFunctionException dummyException2 =
         new DummySkyFunctionException(exception2, /*isTransient=*/ false, /*isCatastrophic=*/ true);
     ErrorInfo exceptionErrorInfo2 = ErrorInfo.fromException(
         new ReifiedSkyFunctionException(dummyException2, causeOfException2),
         /*isTransitivelyTransient=*/ false);
 
-    SkyKey currentKey = new SkyKey(SkyFunctionName.create("CURRENT"), 9876);
+    SkyKey currentKey = SkyKey.create(SkyFunctionName.create("CURRENT"), 9876);
 
     ErrorInfo errorInfo = ErrorInfo.fromChildErrors(
         currentKey, ImmutableList.of(cycleErrorInfo, exceptionErrorInfo1, exceptionErrorInfo2));
diff --git a/src/test/java/com/google/devtools/build/skyframe/GraphConcurrencyTest.java b/src/test/java/com/google/devtools/build/skyframe/GraphConcurrencyTest.java
index 68e3046..c10277f 100644
--- a/src/test/java/com/google/devtools/build/skyframe/GraphConcurrencyTest.java
+++ b/src/test/java/com/google/devtools/build/skyframe/GraphConcurrencyTest.java
@@ -72,7 +72,7 @@
   }
 
   protected SkyKey key(String name) {
-    return new SkyKey(SKY_FUNCTION_NAME, name);
+    return SkyKey.create(SKY_FUNCTION_NAME, name);
   }
 
   @Test
diff --git a/src/test/java/com/google/devtools/build/skyframe/GraphTester.java b/src/test/java/com/google/devtools/build/skyframe/GraphTester.java
index 70dbe80..76759af 100644
--- a/src/test/java/com/google/devtools/build/skyframe/GraphTester.java
+++ b/src/test/java/com/google/devtools/build/skyframe/GraphTester.java
@@ -157,7 +157,7 @@
   }
 
   public static SkyKey skyKey(String key) {
-    return new SkyKey(NODE_TYPE, key);
+    return SkyKey.create(NODE_TYPE, key);
   }
 
   /**
@@ -260,7 +260,7 @@
   public static SkyKey[] toSkyKeys(String... names) {
     SkyKey[] result = new SkyKey[names.length];
     for (int i = 0; i < names.length; i++) {
-      result[i] = new SkyKey(GraphTester.NODE_TYPE, names[i]);
+      result[i] = SkyKey.create(GraphTester.NODE_TYPE, names[i]);
     }
     return result;
   }
diff --git a/src/test/java/com/google/devtools/build/skyframe/InMemoryNodeEntryTest.java b/src/test/java/com/google/devtools/build/skyframe/InMemoryNodeEntryTest.java
index 1298c48..4170c54 100644
--- a/src/test/java/com/google/devtools/build/skyframe/InMemoryNodeEntryTest.java
+++ b/src/test/java/com/google/devtools/build/skyframe/InMemoryNodeEntryTest.java
@@ -54,7 +54,7 @@
       NestedSetBuilder.<TaggedEvents>emptySet(Order.STABLE_ORDER);
 
   private static SkyKey key(String name) {
-    return new SkyKey(NODE_TYPE, name);
+    return SkyKey.create(NODE_TYPE, name);
   }
 
   @Test
diff --git a/src/test/java/com/google/devtools/build/skyframe/MemoizingEvaluatorTest.java b/src/test/java/com/google/devtools/build/skyframe/MemoizingEvaluatorTest.java
index 2fcd1a9..27ca052 100644
--- a/src/test/java/com/google/devtools/build/skyframe/MemoizingEvaluatorTest.java
+++ b/src/test/java/com/google/devtools/build/skyframe/MemoizingEvaluatorTest.java
@@ -145,7 +145,7 @@
   }
 
   protected static SkyKey toSkyKey(String name) {
-    return new SkyKey(NODE_TYPE, name);
+    return SkyKey.create(NODE_TYPE, name);
   }
 
   @Test
diff --git a/src/test/java/com/google/devtools/build/skyframe/ParallelEvaluatorTest.java b/src/test/java/com/google/devtools/build/skyframe/ParallelEvaluatorTest.java
index 172efd5..41d9cdc 100644
--- a/src/test/java/com/google/devtools/build/skyframe/ParallelEvaluatorTest.java
+++ b/src/test/java/com/google/devtools/build/skyframe/ParallelEvaluatorTest.java
@@ -1434,7 +1434,7 @@
     class ParentFunction implements SkyFunction {
       @Override
       public SkyValue compute(SkyKey skyKey, Environment env) {
-        SkyValue dep = env.getValue(new SkyKey(childType, "billy the kid"));
+        SkyValue dep = env.getValue(SkyKey.create(childType, "billy the kid"));
         if (dep == null) {
           return null;
         }
@@ -1451,7 +1451,7 @@
         skyFunctions, false);
 
     try {
-      evaluator.eval(ImmutableList.of(new SkyKey(parentType, "octodad")));
+      evaluator.eval(ImmutableList.of(SkyKey.create(parentType, "octodad")));
       fail();
     } catch (RuntimeException e) {
       assertEquals("I WANT A PONY!!!", e.getCause().getMessage());
diff --git a/src/test/java/com/google/devtools/build/skyframe/ReverseDepsUtilImplTest.java b/src/test/java/com/google/devtools/build/skyframe/ReverseDepsUtilImplTest.java
index 4c2d9c6f..7c5e476 100644
--- a/src/test/java/com/google/devtools/build/skyframe/ReverseDepsUtilImplTest.java
+++ b/src/test/java/com/google/devtools/build/skyframe/ReverseDepsUtilImplTest.java
@@ -99,13 +99,14 @@
     for (int numRemovals = 0; numRemovals <= numElements; numRemovals++) {
       Example example = new Example();
       for (int j = 0; j < numElements; j++) {
-        REVERSE_DEPS_UTIL.addReverseDeps(example, Collections.singleton(new SkyKey(NODE_TYPE, j)));
+        REVERSE_DEPS_UTIL.addReverseDeps(
+            example, Collections.singleton(SkyKey.create(NODE_TYPE, j)));
       }
       // Not a big test but at least check that it does not blow up.
       assertThat(REVERSE_DEPS_UTIL.toString(example)).isNotEmpty();
       assertThat(REVERSE_DEPS_UTIL.getReverseDeps(example)).hasSize(numElements);
       for (int i = 0; i < numRemovals; i++) {
-        REVERSE_DEPS_UTIL.removeReverseDep(example, new SkyKey(NODE_TYPE, i));
+        REVERSE_DEPS_UTIL.removeReverseDep(example, SkyKey.create(NODE_TYPE, i));
       }
       assertThat(REVERSE_DEPS_UTIL.getReverseDeps(example)).hasSize(numElements - numRemovals);
       assertThat(example.dataToConsolidate).isNull();
@@ -119,12 +120,12 @@
       Example example = new Example();
       List<SkyKey> toAdd = new ArrayList<>();
       for (int j = 0; j < numElements; j++) {
-        toAdd.add(new SkyKey(NODE_TYPE, j));
+        toAdd.add(SkyKey.create(NODE_TYPE, j));
       }
       REVERSE_DEPS_UTIL.addReverseDeps(example, toAdd);
       assertThat(REVERSE_DEPS_UTIL.getReverseDeps(example)).hasSize(numElements);
       for (int i = 0; i < numRemovals; i++) {
-        REVERSE_DEPS_UTIL.removeReverseDep(example, new SkyKey(NODE_TYPE, i));
+        REVERSE_DEPS_UTIL.removeReverseDep(example, SkyKey.create(NODE_TYPE, i));
       }
       assertThat(REVERSE_DEPS_UTIL.getReverseDeps(example)).hasSize(numElements - numRemovals);
       assertThat(example.dataToConsolidate).isNull();
@@ -135,10 +136,10 @@
   public void testDuplicateCheckOnGetReverseDeps() {
     Example example = new Example();
     for (int i = 0; i < numElements; i++) {
-      REVERSE_DEPS_UTIL.addReverseDeps(example, Collections.singleton(new SkyKey(NODE_TYPE, i)));
+      REVERSE_DEPS_UTIL.addReverseDeps(example, Collections.singleton(SkyKey.create(NODE_TYPE, i)));
     }
     // Should only fail when we call getReverseDeps().
-    REVERSE_DEPS_UTIL.addReverseDeps(example, Collections.singleton(new SkyKey(NODE_TYPE, 0)));
+    REVERSE_DEPS_UTIL.addReverseDeps(example, Collections.singleton(SkyKey.create(NODE_TYPE, 0)));
     try {
       REVERSE_DEPS_UTIL.getReverseDeps(example);
       assertThat(numElements).isEqualTo(0);
@@ -149,7 +150,7 @@
   @Test
   public void doubleAddThenRemove() {
     Example example = new Example();
-    SkyKey key = new SkyKey(NODE_TYPE, 0);
+    SkyKey key = SkyKey.create(NODE_TYPE, 0);
     REVERSE_DEPS_UTIL.addReverseDeps(example, Collections.singleton(key));
     // Should only fail when we call getReverseDeps().
     REVERSE_DEPS_UTIL.addReverseDeps(example, Collections.singleton(key));
@@ -164,8 +165,8 @@
   @Test
   public void doubleAddThenRemoveCheckedOnSize() {
     Example example = new Example();
-    SkyKey fixedKey = new SkyKey(NODE_TYPE, 0);
-    SkyKey key = new SkyKey(NODE_TYPE, 1);
+    SkyKey fixedKey = SkyKey.create(NODE_TYPE, 0);
+    SkyKey key = SkyKey.create(NODE_TYPE, 1);
     REVERSE_DEPS_UTIL.addReverseDeps(example, ImmutableList.of(fixedKey, key));
     // Should only fail when we reach the limit.
     REVERSE_DEPS_UTIL.addReverseDeps(example, Collections.singleton(key));
@@ -181,8 +182,8 @@
   @Test
   public void addRemoveAdd() {
     Example example = new Example();
-    SkyKey fixedKey = new SkyKey(NODE_TYPE, 0);
-    SkyKey key = new SkyKey(NODE_TYPE, 1);
+    SkyKey fixedKey = SkyKey.create(NODE_TYPE, 0);
+    SkyKey key = SkyKey.create(NODE_TYPE, 1);
     REVERSE_DEPS_UTIL.addReverseDeps(example, ImmutableList.of(fixedKey, key));
     REVERSE_DEPS_UTIL.removeReverseDep(example, key);
     REVERSE_DEPS_UTIL.addReverseDeps(example, Collections.singleton(key));
@@ -193,12 +194,12 @@
   public void testMaybeCheck() {
     Example example = new Example();
     for (int i = 0; i < numElements; i++) {
-      REVERSE_DEPS_UTIL.addReverseDeps(example, Collections.singleton(new SkyKey(NODE_TYPE, i)));
+      REVERSE_DEPS_UTIL.addReverseDeps(example, Collections.singleton(SkyKey.create(NODE_TYPE, i)));
       // This should always succeed, since the next element is still not present.
-      REVERSE_DEPS_UTIL.maybeCheckReverseDepNotPresent(example, new SkyKey(NODE_TYPE, i + 1));
+      REVERSE_DEPS_UTIL.maybeCheckReverseDepNotPresent(example, SkyKey.create(NODE_TYPE, i + 1));
     }
     try {
-      REVERSE_DEPS_UTIL.maybeCheckReverseDepNotPresent(example, new SkyKey(NODE_TYPE, 0));
+      REVERSE_DEPS_UTIL.maybeCheckReverseDepNotPresent(example, SkyKey.create(NODE_TYPE, 0));
       // Should only fail if empty or above the checking threshold.
       assertThat(numElements == 0 || numElements >= ReverseDepsUtilImpl.MAYBE_CHECK_THRESHOLD)
           .isTrue();
diff --git a/src/test/java/com/google/devtools/build/skyframe/SkyKeyTest.java b/src/test/java/com/google/devtools/build/skyframe/SkyKeyTest.java
index 8f7b247..0e22db3 100644
--- a/src/test/java/com/google/devtools/build/skyframe/SkyKeyTest.java
+++ b/src/test/java/com/google/devtools/build/skyframe/SkyKeyTest.java
@@ -36,7 +36,7 @@
     assertThat(hashCodeSpy.getNumberOfTimesHashCodeCalled()).isEqualTo(0);
 
     // When a SkyKey is constructed with that HashCodeSpy as its argument,
-    SkyKey originalKey = new SkyKey(SkyFunctionName.create("TEMP"), hashCodeSpy);
+    SkyKey originalKey = SkyKey.create(SkyFunctionName.create("TEMP"), hashCodeSpy);
 
     // Then the HashCodeSpy reports that its hashcode method was called once.
     assertThat(hashCodeSpy.getNumberOfTimesHashCodeCalled()).isEqualTo(1);