diff --git a/src/test/java/com/google/devtools/build/lib/analysis/AspectValueTest.java b/src/test/java/com/google/devtools/build/lib/analysis/AspectValueTest.java
index 4b71f81..b0cf53b 100644
--- a/src/test/java/com/google/devtools/build/lib/analysis/AspectValueTest.java
+++ b/src/test/java/com/google/devtools/build/lib/analysis/AspectValueTest.java
@@ -15,7 +15,6 @@
 
 import com.google.common.collect.ImmutableList;
 import com.google.common.testing.EqualsTester;
-import com.google.devtools.build.lib.actions.ActionLookupValue;
 import com.google.devtools.build.lib.analysis.config.BuildConfiguration;
 import com.google.devtools.build.lib.analysis.util.AnalysisTestCase;
 import com.google.devtools.build.lib.analysis.util.TestAspects;
@@ -220,10 +219,11 @@
   private static SkyKey createKey(
       Label label, BuildConfiguration baseConfiguration, NativeAspectClass aspectClass,
       AspectParameters parameters, BuildConfiguration aspectConfiguration) {
-    return ActionLookupValue.key(AspectValue.createAspectKey(
-                label, baseConfiguration, new AspectDescriptor(aspectClass, parameters),
-        aspectConfiguration
-    ));
+    return AspectValue.createAspectKey(
+        label,
+        baseConfiguration,
+        new AspectDescriptor(aspectClass, parameters),
+        aspectConfiguration);
   }
 
   private static SkyKey createDerivedKey(
@@ -234,11 +234,12 @@
       BuildConfiguration aspectConfiguration2) {
     AspectKey baseKey = AspectValue.createAspectKey(label, baseConfiguration,
         new AspectDescriptor(aspectClass1, parameters1), aspectConfiguration1);
-    return ActionLookupValue.key(AspectValue.createAspectKey(
-        label, baseConfiguration,
-        ImmutableList.of(baseKey), new AspectDescriptor(aspectClass2, parameters2),
-        aspectConfiguration2
-    ));
+    return AspectValue.createAspectKey(
+        label,
+        baseConfiguration,
+        ImmutableList.of(baseKey),
+        new AspectDescriptor(aspectClass2, parameters2),
+        aspectConfiguration2);
   }
 
 }
diff --git a/src/test/java/com/google/devtools/build/lib/analysis/util/AnalysisTestCase.java b/src/test/java/com/google/devtools/build/lib/analysis/util/AnalysisTestCase.java
index 60fc89a..fdddbee 100644
--- a/src/test/java/com/google/devtools/build/lib/analysis/util/AnalysisTestCase.java
+++ b/src/test/java/com/google/devtools/build/lib/analysis/util/AnalysisTestCase.java
@@ -437,10 +437,12 @@
   protected Artifact getBinArtifact(String packageRelativePath, ConfiguredTarget owner)
       throws InterruptedException {
     Label label = owner.getLabel();
-    return buildView.getArtifactFactory().getDerivedArtifact(
-        label.getPackageFragment().getRelative(packageRelativePath),
-        getTargetConfiguration().getBinDirectory(label.getPackageIdentifier().getRepository()),
-        new ConfiguredTargetKey(owner));
+    return buildView
+        .getArtifactFactory()
+        .getDerivedArtifact(
+            label.getPackageFragment().getRelative(packageRelativePath),
+            getTargetConfiguration().getBinDirectory(label.getPackageIdentifier().getRepository()),
+            ConfiguredTargetKey.of(owner));
   }
 
   protected Set<SkyKey> getSkyframeEvaluatedTargetKeys() {
diff --git a/src/test/java/com/google/devtools/build/lib/analysis/util/BuildViewTestCase.java b/src/test/java/com/google/devtools/build/lib/analysis/util/BuildViewTestCase.java
index 10e012a..457d184 100644
--- a/src/test/java/com/google/devtools/build/lib/analysis/util/BuildViewTestCase.java
+++ b/src/test/java/com/google/devtools/build/lib/analysis/util/BuildViewTestCase.java
@@ -34,7 +34,6 @@
 import com.google.devtools.build.lib.actions.ActionGraph;
 import com.google.devtools.build.lib.actions.ActionInput;
 import com.google.devtools.build.lib.actions.ActionKeyContext;
-import com.google.devtools.build.lib.actions.ActionLookupValue;
 import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.actions.ArtifactOwner;
 import com.google.devtools.build.lib.actions.CommandLineExpansionException;
@@ -1022,11 +1021,10 @@
    * be "foo.o".
    */
   protected Artifact getBinArtifact(String packageRelativePath, String owner) {
-    ConfiguredTargetKey config = makeConfiguredTargetKey(owner);
     return getPackageRelativeDerivedArtifact(
         packageRelativePath,
-        config.getConfiguration().getBinDirectory(RepositoryName.MAIN),
-        config);
+        getConfiguration(owner).getBinDirectory(RepositoryName.MAIN),
+        makeConfiguredTargetKey(owner));
   }
 
   /**
@@ -1036,9 +1034,10 @@
    * be "foo.o".
    */
   protected Artifact getBinArtifact(String packageRelativePath, ConfiguredTarget owner) {
-    return getPackageRelativeDerivedArtifact(packageRelativePath,
+    return getPackageRelativeDerivedArtifact(
+        packageRelativePath,
         owner.getConfiguration().getBinDirectory(RepositoryName.MAIN),
-        new ConfiguredTargetKey(owner));
+        ConfiguredTargetKey.of(owner));
   }
 
   /**
@@ -1074,10 +1073,11 @@
         packageRelativePath,
         owner.getConfiguration().getBinDirectory(RepositoryName.MAIN),
         (AspectValue.AspectKey)
-            ActionLookupValue.key(AspectValue.createAspectKey(
-                owner.getLabel(), owner.getConfiguration(),
-                new AspectDescriptor(creatingAspectFactory, parameters), owner.getConfiguration()
-            ))
+            AspectValue.createAspectKey(
+                    owner.getLabel(),
+                    owner.getConfiguration(),
+                    new AspectDescriptor(creatingAspectFactory, parameters),
+                    owner.getConfiguration())
                 .argument());
   }
 
@@ -1101,8 +1101,9 @@
    * just be "foo.o".
    */
   protected Artifact getGenfilesArtifact(String packageRelativePath, String owner) {
-    ConfiguredTargetKey configKey = makeConfiguredTargetKey(owner);
-    return getGenfilesArtifact(packageRelativePath, configKey, configKey.getConfiguration());
+    BuildConfiguration config = getConfiguration(owner);
+    return getGenfilesArtifact(
+        packageRelativePath, ConfiguredTargetKey.of(makeLabel(owner), config), config);
   }
 
   /**
@@ -1112,8 +1113,8 @@
    * just be "foo.o".
    */
   protected Artifact getGenfilesArtifact(String packageRelativePath, ConfiguredTarget owner) {
-    ConfiguredTargetKey configKey = new ConfiguredTargetKey(owner);
-    return getGenfilesArtifact(packageRelativePath, configKey, configKey.getConfiguration());
+    ConfiguredTargetKey configKey = ConfiguredTargetKey.of(owner);
+    return getGenfilesArtifact(packageRelativePath, configKey, owner.getConfiguration());
   }
 
   /**
@@ -1138,13 +1139,16 @@
       AspectParameters params) {
     return getPackageRelativeDerivedArtifact(
         packageRelativePath,
-        owner.getConfiguration().getGenfilesDirectory(
-            owner.getTarget().getLabel().getPackageIdentifier().getRepository()),
+        owner
+            .getConfiguration()
+            .getGenfilesDirectory(
+                owner.getTarget().getLabel().getPackageIdentifier().getRepository()),
         (AspectValue.AspectKey)
-            ActionLookupValue.key(AspectValue.createAspectKey(
-                owner.getLabel(), owner.getConfiguration(),
-                new AspectDescriptor(creatingAspectFactory, params), owner.getConfiguration()
-            ))
+            AspectValue.createAspectKey(
+                    owner.getLabel(),
+                    owner.getConfiguration(),
+                    new AspectDescriptor(creatingAspectFactory, params),
+                    owner.getConfiguration())
                 .argument());
   }
 
@@ -1202,9 +1206,10 @@
    * @param owner the artifact's owner.
    */
   protected Artifact getSharedArtifact(String rootRelativePath, ConfiguredTarget owner) {
-    return getDerivedArtifact(PathFragment.create(rootRelativePath),
+    return getDerivedArtifact(
+        PathFragment.create(rootRelativePath),
         targetConfig.getBinDirectory(RepositoryName.MAIN),
-        new ConfiguredTargetKey(owner));
+        ConfiguredTargetKey.of(owner));
   }
 
   protected Action getGeneratingActionForLabel(String label) throws Exception {
@@ -1293,7 +1298,7 @@
     }
   }
 
-  private ConfiguredTargetKey makeConfiguredTargetKey(String label) {
+  private BuildConfiguration getConfiguration(String label) {
     BuildConfiguration config;
     try {
       config = getConfiguredTarget(label).getConfiguration();
@@ -1304,7 +1309,11 @@
       //TODO(b/36585204): Clean this up
       throw new RuntimeException(e);
     }
-    return new ConfiguredTargetKey(makeLabel(label), config);
+    return config;
+  }
+
+  private ConfiguredTargetKey makeConfiguredTargetKey(String label) {
+    return ConfiguredTargetKey.of(makeLabel(label), getConfiguration(label));
   }
 
   protected static List<String> actionInputsToPaths(Iterable<? extends ActionInput> actionInputs) {
@@ -1923,7 +1932,7 @@
       root = configuration.getGenfilesDirectory(repository);
     }
     ArtifactOwner owner =
-        new ConfiguredTargetKey(target.getTarget().getLabel(), target.getConfiguration());
+        ConfiguredTargetKey.of(target.getTarget().getLabel(), target.getConfiguration());
 
     RawAttributeMapper attr = RawAttributeMapper.of(associatedRule);
 
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/ActionTemplateExpansionFunctionTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/ActionTemplateExpansionFunctionTest.java
index 3fdb7a0..8e55e34 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/ActionTemplateExpansionFunctionTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/ActionTemplateExpansionFunctionTest.java
@@ -104,8 +104,7 @@
     List<Action> actions = evaluate(spawnActionTemplate);
     assertThat(actions).hasSize(3);
 
-    ArtifactOwner owner = ActionTemplateExpansionValue.createActionTemplateExpansionKey(
-        spawnActionTemplate);
+    ArtifactOwner owner = ActionTemplateExpansionValue.key(spawnActionTemplate);
     int i = 0;
     for (Action action : actions) {
       String childName = "child" + i;
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/ArtifactFunctionTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/ArtifactFunctionTest.java
index 6e321c5..aba2931 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/ArtifactFunctionTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/ArtifactFunctionTest.java
@@ -321,10 +321,10 @@
   }
 
   private void setGeneratingActions() throws InterruptedException {
-    if (evaluator.getExistingValue(OWNER_KEY) == null) {
+    if (evaluator.getExistingValue(ALL_OWNER) == null) {
       differencer.inject(
           ImmutableMap.of(
-              OWNER_KEY,
+              ALL_OWNER,
               new ActionLookupValue(
                   actionKeyContext, ImmutableList.<ActionAnalysisMetadata>copyOf(actions), false)));
     }
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 ff83c4a..375c715 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
@@ -32,7 +32,6 @@
 import com.google.devtools.build.lib.vfs.Path;
 import com.google.devtools.build.lib.vfs.inmemoryfs.InMemoryFileSystem;
 import com.google.devtools.build.skyframe.InMemoryMemoizingEvaluator;
-import com.google.devtools.build.skyframe.LegacySkyKey;
 import com.google.devtools.build.skyframe.MemoizingEvaluator;
 import com.google.devtools.build.skyframe.RecordingDifferencer;
 import com.google.devtools.build.skyframe.SequencedRecordingDifferencer;
@@ -51,7 +50,6 @@
 
 abstract class ArtifactFunctionTestCase {
   static final ActionLookupKey ALL_OWNER = new SingletonActionLookupKey();
-  static final SkyKey OWNER_KEY = LegacySkyKey.create(SkyFunctions.ACTION_LOOKUP, ALL_OWNER);
 
   protected Set<ActionAnalysisMetadata> actions;
   protected boolean fastDigest = false;
@@ -158,13 +156,8 @@
 
   private static class SingletonActionLookupKey extends ActionLookupKey {
     @Override
-    protected SkyKey getSkyKeyInternal() {
-      return OWNER_KEY;
-    }
-
-    @Override
-    protected SkyFunctionName getType() {
-      throw new UnsupportedOperationException();
+    public SkyFunctionName functionName() {
+      return SkyFunctions.CONFIGURED_TARGET;
     }
   }
 
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/FilesystemValueCheckerTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/FilesystemValueCheckerTest.java
index eb2d141..8c77934 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/FilesystemValueCheckerTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/FilesystemValueCheckerTest.java
@@ -23,7 +23,6 @@
 import com.google.common.collect.ImmutableSet;
 import com.google.common.util.concurrent.Runnables;
 import com.google.devtools.build.lib.actions.Action;
-import com.google.devtools.build.lib.actions.ActionLookupValue;
 import com.google.devtools.build.lib.actions.ActionLookupValue.ActionLookupKey;
 import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.actions.Artifact.SpecialArtifact;
@@ -360,13 +359,12 @@
     FileSystemUtils.writeContentAsLatin1(out2.getPath(), "fizzlepop");
 
     SkyKey actionLookupKey =
-        ActionLookupValue.key(
-            new ActionLookupKey() {
-              @Override
-              protected SkyFunctionName getType() {
-                return SkyFunctionName.FOR_TESTING;
-              }
-            });
+        new ActionLookupKey() {
+          @Override
+          public SkyFunctionName functionName() {
+            return SkyFunctionName.FOR_TESTING;
+          }
+        };
     SkyKey actionKey1 = ActionExecutionValue.key(actionLookupKey, 0);
     SkyKey actionKey2 = ActionExecutionValue.key(actionLookupKey, 1);
     differencer.inject(
@@ -440,13 +438,12 @@
     FileSystemUtils.createDirectoryAndParents(last.getPath());
 
     SkyKey actionLookupKey =
-        ActionLookupValue.key(
-            new ActionLookupKey() {
-              @Override
-              protected SkyFunctionName getType() {
-                return SkyFunctionName.FOR_TESTING;
-              }
-            });
+        new ActionLookupKey() {
+          @Override
+          public SkyFunctionName functionName() {
+            return SkyFunctionName.FOR_TESTING;
+          }
+        };
     SkyKey actionKey1 = ActionExecutionValue.key(actionLookupKey, 0);
     SkyKey actionKey2 = ActionExecutionValue.key(actionLookupKey, 1);
     SkyKey actionKeyEmpty = ActionExecutionValue.key(actionLookupKey, 2);
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/SkyframeAwareActionTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/SkyframeAwareActionTest.java
index 015b1f3..e497ab7 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/SkyframeAwareActionTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/SkyframeAwareActionTest.java
@@ -389,7 +389,7 @@
         null);
 
     // Sanity check that our invalidation receiver is working correctly. We'll rely on it again.
-    SkyKey actionKey = ActionExecutionValue.key(OWNER_KEY, 0);
+    SkyKey actionKey = ActionExecutionValue.key(ACTION_LOOKUP_KEY, 0);
     TrackingEvaluationProgressReceiver.EvaluatedEntry evaluatedAction =
         progressReceiver.getEvalutedEntry(actionKey);
     assertThat(evaluatedAction).isNotNull();
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 a6b2483..8e569fc 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
@@ -81,7 +81,6 @@
 import com.google.devtools.build.skyframe.EvaluationProgressReceiver;
 import com.google.devtools.build.skyframe.EvaluationResult;
 import com.google.devtools.build.skyframe.InMemoryMemoizingEvaluator;
-import com.google.devtools.build.skyframe.LegacySkyKey;
 import com.google.devtools.build.skyframe.RecordingDifferencer;
 import com.google.devtools.build.skyframe.SequencedRecordingDifferencer;
 import com.google.devtools.build.skyframe.SequentialBuildDriver;
@@ -109,10 +108,8 @@
  * The common code that's shared between various builder tests.
  */
 public abstract class TimestampBuilderTestCase extends FoundationTestCase {
-  protected static final ActionLookupValue.ActionLookupKey ALL_OWNER =
+  protected static final ActionLookupValue.ActionLookupKey ACTION_LOOKUP_KEY =
       new SingletonActionLookupKey();
-  protected static final SkyKey OWNER_KEY =
-      LegacySkyKey.create(SkyFunctions.ACTION_LOOKUP, ALL_OWNER);
   protected static final Predicate<Action> ALWAYS_EXECUTE_FILTER = Predicates.alwaysTrue();
   protected static final String CYCLE_MSG = "Yarrrr, there be a cycle up in here";
 
@@ -238,10 +235,10 @@
 
     return new Builder() {
       private void setGeneratingActions() {
-        if (evaluator.getExistingValue(OWNER_KEY) == null) {
+        if (evaluator.getExistingValue(ACTION_LOOKUP_KEY) == null) {
           differencer.inject(
               ImmutableMap.of(
-                  OWNER_KEY,
+                  ACTION_LOOKUP_KEY,
                   new ActionLookupValue(actionKeyContext, ImmutableList.copyOf(actions), false)));
         }
       }
@@ -342,7 +339,10 @@
     PathFragment execPath = PathFragment.create("out").getRelative(name);
     Path path = execRoot.getRelative(execPath);
     return new Artifact(
-        path, Root.asDerivedRoot(execRoot, execRoot.getRelative("out")), execPath, ALL_OWNER);
+        path,
+        Root.asDerivedRoot(execRoot, execRoot.getRelative("out")),
+        execPath,
+        ACTION_LOOKUP_KEY);
   }
 
   /**
@@ -497,13 +497,8 @@
 
   private static class SingletonActionLookupKey extends ActionLookupValue.ActionLookupKey {
     @Override
-    protected SkyKey getSkyKeyInternal() {
-      return OWNER_KEY;
-    }
-
-    @Override
-    protected SkyFunctionName getType() {
-      throw new UnsupportedOperationException();
+    public SkyFunctionName functionName() {
+      return SkyFunctions.CONFIGURED_TARGET;
     }
   }
 
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/TreeArtifactBuildTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/TreeArtifactBuildTest.java
index e0bb1f7..3846003 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/TreeArtifactBuildTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/TreeArtifactBuildTest.java
@@ -1182,7 +1182,10 @@
     PathFragment execPath = PathFragment.create("out").getRelative(name);
     Path path = execRoot.getRelative(execPath);
     return new SpecialArtifact(
-        path, Root.asDerivedRoot(execRoot, execRoot.getRelative("out")), execPath, ALL_OWNER,
+        path,
+        Root.asDerivedRoot(execRoot, execRoot.getRelative("out")),
+        execPath,
+        ACTION_LOOKUP_KEY,
         SpecialArtifactType.TREE);
   }
 
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/TreeArtifactMetadataTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/TreeArtifactMetadataTest.java
index 3e156be..0f346d6 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/TreeArtifactMetadataTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/TreeArtifactMetadataTest.java
@@ -224,10 +224,10 @@
   }
 
   private void setGeneratingActions() throws InterruptedException {
-    if (evaluator.getExistingValue(OWNER_KEY) == null) {
+    if (evaluator.getExistingValue(ALL_OWNER) == null) {
       differencer.inject(
           ImmutableMap.of(
-              OWNER_KEY,
+              ALL_OWNER,
               new ActionLookupValue(
                   actionKeyContext, ImmutableList.<ActionAnalysisMetadata>copyOf(actions), false)));
     }