diff --git a/src/test/java/com/google/devtools/build/skyframe/BUILD b/src/test/java/com/google/devtools/build/skyframe/BUILD
index f213c16..712dc50 100644
--- a/src/test/java/com/google/devtools/build/skyframe/BUILD
+++ b/src/test/java/com/google/devtools/build/skyframe/BUILD
@@ -31,6 +31,7 @@
         "//src/main/java/com/google/devtools/build/lib:util",
         "//src/main/java/com/google/devtools/build/lib/collect",
         "//src/main/java/com/google/devtools/build/lib/concurrent",
+        "//src/main/java/com/google/devtools/build/lib/skyframe/serialization/autocodec",
         "//src/main/java/com/google/devtools/build/skyframe",
         "//src/main/java/com/google/devtools/build/skyframe:skyframe-objects",
         "//src/test/java/com/google/devtools/build/lib:testutil",
@@ -52,7 +53,6 @@
         ":testutil",
         "//src/main/java/com/google/devtools/build/lib:events",
         "//src/main/java/com/google/devtools/build/lib:util",
-        "//src/main/java/com/google/devtools/build/lib/collect",
         "//src/main/java/com/google/devtools/build/lib/collect/nestedset",
         "//src/main/java/com/google/devtools/build/lib/concurrent",
         "//src/main/java/com/google/devtools/build/skyframe",
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 06dd49b..7cac95f 100644
--- a/src/test/java/com/google/devtools/build/skyframe/CyclesReporterTest.java
+++ b/src/test/java/com/google/devtools/build/skyframe/CyclesReporterTest.java
@@ -27,8 +27,7 @@
 @RunWith(JUnit4.class)
 public class CyclesReporterTest {
 
-  private static final SkyKey DUMMY_KEY =
-      LegacySkyKey.create(SkyFunctionName.create("func"), "key");
+  private static final SkyKey DUMMY_KEY = () -> SkyFunctionName.create("func");
 
   @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 a003914..9c9d00e 100644
--- a/src/test/java/com/google/devtools/build/skyframe/ErrorInfoTest.java
+++ b/src/test/java/com/google/devtools/build/skyframe/ErrorInfoTest.java
@@ -47,7 +47,7 @@
 
   private void runTestFromException(boolean isDirectlyTransient, boolean isTransitivelyTransient) {
     Exception exception = new IOException("ehhhhh");
-    SkyKey causeOfException = LegacySkyKey.create(SkyFunctionName.create("CAUSE"), 1234);
+    SkyKey causeOfException = GraphTester.toSkyKey("CAUSE, 1234");
     DummySkyFunctionException dummyException =
         new DummySkyFunctionException(exception, isDirectlyTransient, /*isCatastrophic=*/ false);
 
@@ -89,8 +89,8 @@
   public void testFromCycle() {
     CycleInfo cycle =
         new CycleInfo(
-            ImmutableList.of(LegacySkyKey.create(SkyFunctionName.create("PATH"), 1234)),
-            ImmutableList.of(LegacySkyKey.create(SkyFunctionName.create("CYCLE"), 4321)));
+            ImmutableList.of(GraphTester.toSkyKey("PATH, 1234")),
+            ImmutableList.of(GraphTester.toSkyKey("CYCLE, 4321")));
 
     ErrorInfo errorInfo = ErrorInfo.fromCycle(cycle);
 
@@ -105,12 +105,12 @@
   public void testFromChildErrors() {
     CycleInfo cycle =
         new CycleInfo(
-            ImmutableList.of(LegacySkyKey.create(SkyFunctionName.create("PATH"), 1234)),
-            ImmutableList.of(LegacySkyKey.create(SkyFunctionName.create("CYCLE"), 4321)));
+            ImmutableList.of(GraphTester.toSkyKey("PATH, 1234")),
+            ImmutableList.of(GraphTester.toSkyKey("CYCLE, 4321")));
     ErrorInfo cycleErrorInfo = ErrorInfo.fromCycle(cycle);
 
     Exception exception1 = new IOException("ehhhhh");
-    SkyKey causeOfException1 = LegacySkyKey.create(SkyFunctionName.create("CAUSE1"), 1234);
+    SkyKey causeOfException1 = GraphTester.toSkyKey("CAUSE1, 1234");
     DummySkyFunctionException dummyException1 =
         new DummySkyFunctionException(exception1, /*isTransient=*/ true, /*isCatastrophic=*/ false);
     ErrorInfo exceptionErrorInfo1 = ErrorInfo.fromException(
@@ -119,14 +119,14 @@
 
     // N.B this ErrorInfo will be catastrophic.
     Exception exception2 = new IOException("blahhhhh");
-    SkyKey causeOfException2 = LegacySkyKey.create(SkyFunctionName.create("CAUSE2"), 5678);
+    SkyKey causeOfException2 = GraphTester.toSkyKey("CAUSE2, 5678");
     DummySkyFunctionException dummyException2 =
         new DummySkyFunctionException(exception2, /*isTransient=*/ false, /*isCatastrophic=*/ true);
     ErrorInfo exceptionErrorInfo2 = ErrorInfo.fromException(
         new ReifiedSkyFunctionException(dummyException2, causeOfException2),
         /*isTransitivelyTransient=*/ false);
 
-    SkyKey currentKey = LegacySkyKey.create(SkyFunctionName.create("CURRENT"), 9876);
+    SkyKey currentKey = GraphTester.toSkyKey("CURRENT, 9876");
 
     ErrorInfo errorInfo = ErrorInfo.fromChildErrors(
         currentKey, ImmutableList.of(cycleErrorInfo, exceptionErrorInfo1, exceptionErrorInfo2));
@@ -184,4 +184,3 @@
     }
   }
 }
-
diff --git a/src/test/java/com/google/devtools/build/skyframe/GraphTest.java b/src/test/java/com/google/devtools/build/skyframe/GraphTest.java
index a864f48..378f58c 100644
--- a/src/test/java/com/google/devtools/build/skyframe/GraphTest.java
+++ b/src/test/java/com/google/devtools/build/skyframe/GraphTest.java
@@ -41,8 +41,6 @@
 
 /** Base class for sanity tests on {@link EvaluableGraph} implementations. */
 public abstract class GraphTest {
-
-  private static final SkyFunctionName SKY_FUNCTION_NAME = SkyFunctionName.FOR_TESTING;
   protected ProcessableGraph graph;
   protected TestRunnableWrapper wrapper;
   private final Version startingVersion = getStartingVersion();
@@ -71,7 +69,7 @@
   }
 
   protected SkyKey key(String name) {
-    return LegacySkyKey.create(SKY_FUNCTION_NAME, name);
+    return GraphTester.toSkyKey(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 657dd00..a30af1c 100644
--- a/src/test/java/com/google/devtools/build/skyframe/GraphTester.java
+++ b/src/test/java/com/google/devtools/build/skyframe/GraphTester.java
@@ -19,9 +19,12 @@
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.ImmutableSet;
+import com.google.common.collect.Interner;
 import com.google.common.collect.Iterables;
+import com.google.devtools.build.lib.concurrent.BlazeInterners;
 import com.google.devtools.build.lib.events.Event;
 import com.google.devtools.build.lib.events.ExtendedEventHandler.Postable;
+import com.google.devtools.build.lib.skyframe.serialization.autocodec.AutoCodec;
 import com.google.devtools.build.lib.util.Pair;
 import com.google.devtools.build.skyframe.SkyFunction.Environment;
 import com.google.devtools.build.skyframe.SkyFunctionException.Transience;
@@ -161,7 +164,7 @@
   }
 
   public static SkyKey skyKey(String key) {
-    return LegacySkyKey.create(NODE_TYPE, key);
+    return Key.create(key);
   }
 
   /** A value in the testing graph that is constructed in the tester. */
@@ -276,8 +279,8 @@
 
   public static ImmutableList<SkyKey> toSkyKeys(String... names) {
     ImmutableList.Builder<SkyKey> result = ImmutableList.builder();
-    for (int i = 0; i < names.length; i++) {
-      result.add(LegacySkyKey.create(GraphTester.NODE_TYPE, names[i]));
+    for (String element : names) {
+      result.add(Key.create(element));
     }
     return result.build();
   }
@@ -400,4 +403,24 @@
       }
     };
   }
+
+  @AutoCodec.VisibleForSerialization
+  @AutoCodec
+  static class Key extends AbstractSkyKey<String> {
+    private static final Interner<Key> interner = BlazeInterners.newWeakInterner();
+
+    @AutoCodec.VisibleForSerialization
+    Key(String arg) {
+      super(arg);
+    }
+
+    static Key create(String arg) {
+      return interner.intern(new Key(arg));
+    }
+
+    @Override
+    public SkyFunctionName functionName() {
+      return SkyFunctionName.FOR_TESTING;
+    }
+  }
 }
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 00969da..b16206c 100644
--- a/src/test/java/com/google/devtools/build/skyframe/InMemoryNodeEntryTest.java
+++ b/src/test/java/com/google/devtools/build/skyframe/InMemoryNodeEntryTest.java
@@ -43,15 +43,13 @@
  */
 @RunWith(JUnit4.class)
 public class InMemoryNodeEntryTest {
-
-  private static final SkyFunctionName NODE_TYPE = SkyFunctionName.create("Type");
   private static final NestedSet<TaggedEvents> NO_EVENTS =
       NestedSetBuilder.<TaggedEvents>emptySet(Order.STABLE_ORDER);
   private static final NestedSet<Postable> NO_POSTS =
       NestedSetBuilder.<Postable>emptySet(Order.STABLE_ORDER);
 
   private static SkyKey key(String name) {
-    return LegacySkyKey.create(NODE_TYPE, name);
+    return GraphTester.toSkyKey(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 7521dd3..d2a5bfc 100644
--- a/src/test/java/com/google/devtools/build/skyframe/MemoizingEvaluatorTest.java
+++ b/src/test/java/com/google/devtools/build/skyframe/MemoizingEvaluatorTest.java
@@ -142,7 +142,7 @@
   }
 
   private static SkyKey toSkyKey(String name) {
-    return LegacySkyKey.create(NODE_TYPE, name);
+    return GraphTester.toSkyKey(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 d0d7b97..19c7813 100644
--- a/src/test/java/com/google/devtools/build/skyframe/ParallelEvaluatorTest.java
+++ b/src/test/java/com/google/devtools/build/skyframe/ParallelEvaluatorTest.java
@@ -25,11 +25,13 @@
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.ImmutableSet;
+import com.google.common.collect.Interner;
 import com.google.common.collect.Iterables;
 import com.google.common.collect.Lists;
 import com.google.common.collect.Sets;
 import com.google.common.eventbus.EventBus;
 import com.google.common.util.concurrent.Uninterruptibles;
+import com.google.devtools.build.lib.concurrent.BlazeInterners;
 import com.google.devtools.build.lib.events.Event;
 import com.google.devtools.build.lib.events.EventHandler;
 import com.google.devtools.build.lib.events.EventKind;
@@ -65,6 +67,9 @@
  */
 @RunWith(JUnit4.class)
 public class ParallelEvaluatorTest {
+  private static final SkyFunctionName CHILD_TYPE = SkyFunctionName.create("child");
+  private static final SkyFunctionName PARENT_TYPE = SkyFunctionName.create("parent");
+
   protected ProcessableGraph graph;
   protected IntVersion graphVersion = IntVersion.of(0);
   protected GraphTester tester = new GraphTester();
@@ -1548,8 +1553,6 @@
 
   @Test
   public void testFunctionCrashTrace() throws Exception {
-    final SkyFunctionName childType = SkyFunctionName.create("child");
-    final SkyFunctionName parentType = SkyFunctionName.create("parent");
 
     class ChildFunction implements SkyFunction {
       @Override
@@ -1563,7 +1566,7 @@
     class ParentFunction implements SkyFunction {
       @Override
       public SkyValue compute(SkyKey skyKey, Environment env) throws InterruptedException {
-        SkyValue dep = env.getValue(LegacySkyKey.create(childType, "billy the kid"));
+        SkyValue dep = env.getValue(ChildKey.create("billy the kid"));
         if (dep == null) {
           return null;
         }
@@ -1573,13 +1576,14 @@
       @Override public String extractTag(SkyKey skyKey) { return null; }
     }
 
-    ImmutableMap<SkyFunctionName, SkyFunction> skyFunctions = ImmutableMap.of(
-        childType, new ChildFunction(),
-        parentType, new ParentFunction());
+    ImmutableMap<SkyFunctionName, SkyFunction> skyFunctions =
+        ImmutableMap.of(
+            CHILD_TYPE, new ChildFunction(),
+            PARENT_TYPE, new ParentFunction());
     ParallelEvaluator evaluator = makeEvaluator(new InMemoryGraphImpl(), skyFunctions, false);
 
     try {
-      evaluator.eval(ImmutableList.of(LegacySkyKey.create(parentType, "octodad")));
+      evaluator.eval(ImmutableList.of(ParentKey.create("octodad")));
       fail();
     } catch (RuntimeException e) {
       assertThat(e).hasCauseThat().hasMessageThat().isEqualTo("I WANT A PONY!!!");
@@ -2318,4 +2322,38 @@
       throws Exception {
     runUnhandledTransitiveErrors(/*keepGoing=*/true, /*explicitlyPropagateError=*/true);
   }
+
+  private static class ChildKey extends AbstractSkyKey<String> {
+    private static final Interner<ChildKey> interner = BlazeInterners.newWeakInterner();
+
+    private ChildKey(String arg) {
+      super(arg);
+    }
+
+    static ChildKey create(String arg) {
+      return interner.intern(new ChildKey(arg));
+    }
+
+    @Override
+    public SkyFunctionName functionName() {
+      return CHILD_TYPE;
+    }
+  }
+
+  private static class ParentKey extends AbstractSkyKey<String> {
+    private static final Interner<ParentKey> interner = BlazeInterners.newWeakInterner();
+
+    private ParentKey(String arg) {
+      super(arg);
+    }
+
+    private static ParentKey create(String arg) {
+      return interner.intern(new ParentKey(arg));
+    }
+
+    @Override
+    public SkyFunctionName functionName() {
+      return PARENT_TYPE;
+    }
+  }
 }
diff --git a/src/test/java/com/google/devtools/build/skyframe/ReverseDepsUtilityTest.java b/src/test/java/com/google/devtools/build/skyframe/ReverseDepsUtilityTest.java
index 3a60399..8d79965 100644
--- a/src/test/java/com/google/devtools/build/skyframe/ReverseDepsUtilityTest.java
+++ b/src/test/java/com/google/devtools/build/skyframe/ReverseDepsUtilityTest.java
@@ -17,6 +17,8 @@
 import static org.junit.Assert.fail;
 
 import com.google.common.collect.ImmutableList;
+import com.google.common.collect.Interner;
+import com.google.devtools.build.lib.concurrent.BlazeInterners;
 import java.util.ArrayList;
 import java.util.Collections;
 import java.util.List;
@@ -28,8 +30,6 @@
 /** Test for {@code ReverseDepsUtility}. */
 @RunWith(Parameterized.class)
 public class ReverseDepsUtilityTest {
-
-  private static final SkyFunctionName NODE_TYPE = SkyFunctionName.create("Type");
   private final int numElements;
 
   @Parameters(name = "numElements-{0}")
@@ -50,14 +50,13 @@
     for (int numRemovals = 0; numRemovals <= numElements; numRemovals++) {
       InMemoryNodeEntry example = new InMemoryNodeEntry();
       for (int j = 0; j < numElements; j++) {
-        ReverseDepsUtility.addReverseDeps(
-            example, Collections.singleton(LegacySkyKey.create(NODE_TYPE, j)));
+        ReverseDepsUtility.addReverseDeps(example, Collections.singleton(Key.create(j)));
       }
       // Not a big test but at least check that it does not blow up.
       assertThat(ReverseDepsUtility.toString(example)).isNotEmpty();
       assertThat(ReverseDepsUtility.getReverseDeps(example)).hasSize(numElements);
       for (int i = 0; i < numRemovals; i++) {
-        ReverseDepsUtility.removeReverseDep(example, LegacySkyKey.create(NODE_TYPE, i));
+        ReverseDepsUtility.removeReverseDep(example, Key.create(i));
       }
       assertThat(ReverseDepsUtility.getReverseDeps(example)).hasSize(numElements - numRemovals);
       assertThat(example.getReverseDepsDataToConsolidateForReverseDepsUtil()).isNull();
@@ -71,12 +70,12 @@
       InMemoryNodeEntry example = new InMemoryNodeEntry();
       List<SkyKey> toAdd = new ArrayList<>();
       for (int j = 0; j < numElements; j++) {
-        toAdd.add(LegacySkyKey.create(NODE_TYPE, j));
+        toAdd.add(Key.create(j));
       }
       ReverseDepsUtility.addReverseDeps(example, toAdd);
       assertThat(ReverseDepsUtility.getReverseDeps(example)).hasSize(numElements);
       for (int i = 0; i < numRemovals; i++) {
-        ReverseDepsUtility.removeReverseDep(example, LegacySkyKey.create(NODE_TYPE, i));
+        ReverseDepsUtility.removeReverseDep(example, Key.create(i));
       }
       assertThat(ReverseDepsUtility.getReverseDeps(example)).hasSize(numElements - numRemovals);
       assertThat(example.getReverseDepsDataToConsolidateForReverseDepsUtil()).isNull();
@@ -87,12 +86,10 @@
   public void testDuplicateCheckOnGetReverseDeps() {
     InMemoryNodeEntry example = new InMemoryNodeEntry();
     for (int i = 0; i < numElements; i++) {
-      ReverseDepsUtility.addReverseDeps(
-          example, Collections.singleton(LegacySkyKey.create(NODE_TYPE, i)));
+      ReverseDepsUtility.addReverseDeps(example, Collections.singleton(Key.create(i)));
     }
     // Should only fail when we call getReverseDeps().
-    ReverseDepsUtility.addReverseDeps(
-        example, Collections.singleton(LegacySkyKey.create(NODE_TYPE, 0)));
+    ReverseDepsUtility.addReverseDeps(example, Collections.singleton(Key.create(0)));
     try {
       ReverseDepsUtility.getReverseDeps(example);
       assertThat(numElements).isEqualTo(0);
@@ -103,7 +100,7 @@
   @Test
   public void doubleAddThenRemove() {
     InMemoryNodeEntry example = new InMemoryNodeEntry();
-    SkyKey key = LegacySkyKey.create(NODE_TYPE, 0);
+    SkyKey key = Key.create(0);
     ReverseDepsUtility.addReverseDeps(example, Collections.singleton(key));
     // Should only fail when we call getReverseDeps().
     ReverseDepsUtility.addReverseDeps(example, Collections.singleton(key));
@@ -118,8 +115,8 @@
   @Test
   public void doubleAddThenRemoveCheckedOnSize() {
     InMemoryNodeEntry example = new InMemoryNodeEntry();
-    SkyKey fixedKey = LegacySkyKey.create(NODE_TYPE, 0);
-    SkyKey key = LegacySkyKey.create(NODE_TYPE, 1);
+    SkyKey fixedKey = Key.create(0);
+    SkyKey key = Key.create(1);
     ReverseDepsUtility.addReverseDeps(example, ImmutableList.of(fixedKey, key));
     // Should only fail when we reach the limit.
     ReverseDepsUtility.addReverseDeps(example, Collections.singleton(key));
@@ -135,8 +132,8 @@
   @Test
   public void addRemoveAdd() {
     InMemoryNodeEntry example = new InMemoryNodeEntry();
-    SkyKey fixedKey = LegacySkyKey.create(NODE_TYPE, 0);
-    SkyKey key = LegacySkyKey.create(NODE_TYPE, 1);
+    SkyKey fixedKey = Key.create(0);
+    SkyKey key = Key.create(1);
     ReverseDepsUtility.addReverseDeps(example, ImmutableList.of(fixedKey, key));
     ReverseDepsUtility.removeReverseDep(example, key);
     ReverseDepsUtility.addReverseDeps(example, Collections.singleton(key));
@@ -147,18 +144,33 @@
   public void testMaybeCheck() {
     InMemoryNodeEntry example = new InMemoryNodeEntry();
     for (int i = 0; i < numElements; i++) {
-      ReverseDepsUtility.addReverseDeps(
-          example, Collections.singleton(LegacySkyKey.create(NODE_TYPE, i)));
+      ReverseDepsUtility.addReverseDeps(example, Collections.singleton(Key.create(i)));
       // This should always succeed, since the next element is still not present.
-      ReverseDepsUtility.maybeCheckReverseDepNotPresent(
-          example, LegacySkyKey.create(NODE_TYPE, i + 1));
+      ReverseDepsUtility.maybeCheckReverseDepNotPresent(example, Key.create(i + 1));
     }
     try {
-      ReverseDepsUtility.maybeCheckReverseDepNotPresent(example, LegacySkyKey.create(NODE_TYPE, 0));
+      ReverseDepsUtility.maybeCheckReverseDepNotPresent(example, Key.create(0));
       // Should only fail if empty or above the checking threshold.
       assertThat(numElements == 0 || numElements >= ReverseDepsUtility.MAYBE_CHECK_THRESHOLD)
           .isTrue();
     } catch (Exception expected) {
     }
   }
+
+  private static class Key extends AbstractSkyKey<Integer> {
+    private static final Interner<Key> interner = BlazeInterners.newWeakInterner();
+
+    private Key(Integer arg) {
+      super(arg);
+    }
+
+    private static Key create(Integer arg) {
+      return interner.intern(new Key(arg));
+    }
+
+    @Override
+    public SkyFunctionName functionName() {
+      return SkyFunctionName.FOR_TESTING;
+    }
+  }
 }
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 fc3cb3f..d589a7c 100644
--- a/src/test/java/com/google/devtools/build/skyframe/SkyKeyTest.java
+++ b/src/test/java/com/google/devtools/build/skyframe/SkyKeyTest.java
@@ -15,6 +15,8 @@
 
 import static com.google.common.truth.Truth.assertThat;
 
+import com.google.common.collect.Interner;
+import com.google.devtools.build.lib.concurrent.BlazeInterners;
 import com.google.devtools.build.lib.testutil.TestUtils;
 import java.io.Serializable;
 import org.junit.Test;
@@ -34,7 +36,7 @@
     assertThat(hashCodeSpy.getNumberOfTimesHashCodeCalled()).isEqualTo(0);
 
     // When a SkyKey is constructed with that HashCodeSpy as its argument,
-    SkyKey originalKey = LegacySkyKey.create(SkyFunctionName.create("TEMP"), hashCodeSpy);
+    SkyKey originalKey = Key.create(hashCodeSpy);
 
     // Then the HashCodeSpy reports that its hashcode method was called once.
     assertThat(hashCodeSpy.getNumberOfTimesHashCodeCalled()).isEqualTo(1);
@@ -83,4 +85,21 @@
       return 42;
     }
   }
+
+  private static class Key extends AbstractSkyKey<HashCodeSpy> {
+    private static final Interner<Key> interner = BlazeInterners.newWeakInterner();
+
+    private Key(HashCodeSpy arg) {
+      super(arg);
+    }
+
+    private static Key create(HashCodeSpy arg) {
+      return interner.intern(new Key(arg));
+    }
+
+    @Override
+    public SkyFunctionName functionName() {
+      return SkyFunctionName.FOR_TESTING;
+    }
+  }
 }