Replace LegacySkyKey by AbstractSkyKey or custom SkyKeys. AbstractSkyKey doesn't save memory in the 32-bit case, but makes it easier for people to see how many SkyKeys we have.

There's some unnecessary interning in tests, but it was easier to copypasta and doesn't harm anything, I think.

PiperOrigin-RevId: 187694309

70 files changed, 1374 insertions, 576 deletions

diff --git a/src/main/java/com/google/devtools/build/lib/bazel/repository/MavenServerValue.java b/src/main/java/com/google/devtools/build/lib/bazel/repository/MavenServerValue.java
index 3a4774ccc8..75ad690801 100644
--- a/src/main/java/com/google/devtools/build/lib/bazel/repository/MavenServerValue.java
+++ b/src/main/java/com/google/devtools/build/lib/bazel/repository/MavenServerValue.java
@@ -16,9 +16,11 @@ package com.google.devtools.build.lib.bazel.repository;
 
 import com.google.common.base.Objects;
 import com.google.common.base.Preconditions;
+import com.google.common.collect.Interner;
+import com.google.devtools.build.lib.concurrent.BlazeInterners;
 import com.google.devtools.build.lib.util.Fingerprint;
-import com.google.devtools.build.skyframe.LegacySkyKey;
-import com.google.devtools.build.skyframe.SkyKey;
+import com.google.devtools.build.skyframe.AbstractSkyKey;
+import com.google.devtools.build.skyframe.SkyFunctionName;
 import com.google.devtools.build.skyframe.SkyValue;
 import java.util.Arrays;
 import org.apache.maven.settings.Server;
@@ -34,9 +36,25 @@ public class MavenServerValue implements SkyValue {
   private final Server server;
   private final byte[] settingsFingerprint;
 
-  public static SkyKey key(String serverName) {
-    Preconditions.checkNotNull(serverName);
-    return LegacySkyKey.create(MavenServerFunction.NAME, serverName);
+  public static Key key(String serverName) {
+    return Key.create(Preconditions.checkNotNull(serverName));
+  }
+
+  static class Key extends AbstractSkyKey<String> {
+    private static final Interner<Key> interner = BlazeInterners.newWeakInterner();
+
+    private Key(String arg) {
+      super(arg);
+    }
+
+    static Key create(String arg) {
+      return interner.intern(new Key(arg));
+    }
+
+    @Override
+    public SkyFunctionName functionName() {
+      return MavenServerFunction.NAME;
+    }
   }
 
   public static MavenServerValue createFromUrl(String url) {
diff --git a/src/main/java/com/google/devtools/build/lib/rules/genquery/GenQuery.java b/src/main/java/com/google/devtools/build/lib/rules/genquery/GenQuery.java
index 529cb4d668..b6619a9ec8 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/genquery/GenQuery.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/genquery/GenQuery.java
@@ -69,8 +69,6 @@ import com.google.devtools.build.lib.query2.output.QueryOptions.OrderOutput;
 import com.google.devtools.build.lib.query2.output.QueryOutputUtils;
 import com.google.devtools.build.lib.runtime.KeepGoingOption;
 import com.google.devtools.build.lib.skyframe.PackageValue;
-import com.google.devtools.build.lib.skyframe.PrecomputedValue.Precomputed;
-import com.google.devtools.build.lib.skyframe.SkyFunctions;
 import com.google.devtools.build.lib.skyframe.TargetPatternValue;
 import com.google.devtools.build.lib.skyframe.TargetPatternValue.TargetPatternKey;
 import com.google.devtools.build.lib.skyframe.TransitiveTargetKey;
@@ -80,7 +78,6 @@ import com.google.devtools.build.lib.util.Fingerprint;
 import com.google.devtools.build.lib.util.Pair;
 import com.google.devtools.build.lib.vfs.Path;
 import com.google.devtools.build.lib.vfs.PathFragment;
-import com.google.devtools.build.skyframe.LegacySkyKey;
 import com.google.devtools.build.skyframe.SkyFunction;
 import com.google.devtools.build.skyframe.SkyKey;
 import com.google.devtools.build.skyframe.ValueOrException;
@@ -103,8 +100,6 @@ import javax.annotation.Nullable;
 public class GenQuery implements RuleConfiguredTargetFactory {
   private static final QueryEnvironmentFactory QUERY_ENVIRONMENT_FACTORY =
       new QueryEnvironmentFactory();
-  public static final Precomputed<ImmutableList<OutputFormatter>> QUERY_OUTPUT_FORMATTERS =
-      new Precomputed<>(LegacySkyKey.create(SkyFunctions.PRECOMPUTED, "query_output_formatters"));
 
   @Override
   @Nullable
diff --git a/src/main/java/com/google/devtools/build/lib/rules/repository/RepositoryDelegatorFunction.java b/src/main/java/com/google/devtools/build/lib/rules/repository/RepositoryDelegatorFunction.java
index eafa09fb5c..a4b6c9a16b 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/repository/RepositoryDelegatorFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/repository/RepositoryDelegatorFunction.java
@@ -26,15 +26,13 @@ import com.google.devtools.build.lib.repository.ExternalPackageUtil;
 import com.google.devtools.build.lib.repository.ExternalRuleNotFoundException;
 import com.google.devtools.build.lib.rules.repository.RepositoryFunction.RepositoryFunctionException;
 import com.google.devtools.build.lib.skyframe.FileValue;
+import com.google.devtools.build.lib.skyframe.PrecomputedValue;
 import com.google.devtools.build.lib.skyframe.PrecomputedValue.Precomputed;
-import com.google.devtools.build.lib.skyframe.SkyFunctions;
 import com.google.devtools.build.lib.util.Fingerprint;
 import com.google.devtools.build.lib.vfs.FileSystemUtils;
 import com.google.devtools.build.lib.vfs.Path;
 import com.google.devtools.build.lib.vfs.PathFragment;
-import com.google.devtools.build.skyframe.LegacySkyKey;
 import com.google.devtools.build.skyframe.SkyFunction;
-import com.google.devtools.build.skyframe.SkyFunction.Environment;
 import com.google.devtools.build.skyframe.SkyFunctionException;
 import com.google.devtools.build.skyframe.SkyFunctionException.Transience;
 import com.google.devtools.build.skyframe.SkyKey;
@@ -56,7 +54,7 @@ import javax.annotation.Nullable;
  */
 public final class RepositoryDelegatorFunction implements SkyFunction {
   public static final Precomputed<Map<RepositoryName, PathFragment>> REPOSITORY_OVERRIDES =
-      new Precomputed<>(LegacySkyKey.create(SkyFunctions.PRECOMPUTED, "repository_overrides"));
+      new Precomputed<>(PrecomputedValue.Key.create("repository_overrides"));
 
   // The marker file version is inject in the rule key digest so the rule key is always different
   // when we decide to update the format.
diff --git a/src/main/java/com/google/devtools/build/lib/rules/repository/RepositoryDirectoryValue.java b/src/main/java/com/google/devtools/build/lib/rules/repository/RepositoryDirectoryValue.java
index 6e21ad5b70..c2ce139864 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/repository/RepositoryDirectoryValue.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/repository/RepositoryDirectoryValue.java
@@ -16,12 +16,15 @@ package com.google.devtools.build.lib.rules.repository;
 
 import com.google.common.base.Objects;
 import com.google.common.base.Preconditions;
+import com.google.common.collect.Interner;
 import com.google.devtools.build.lib.cmdline.RepositoryName;
+import com.google.devtools.build.lib.concurrent.BlazeInterners;
 import com.google.devtools.build.lib.skyframe.DirectoryListingValue;
 import com.google.devtools.build.lib.skyframe.SkyFunctions;
+import com.google.devtools.build.lib.skyframe.serialization.autocodec.AutoCodec;
 import com.google.devtools.build.lib.vfs.Path;
-import com.google.devtools.build.skyframe.LegacySkyKey;
-import com.google.devtools.build.skyframe.SkyKey;
+import com.google.devtools.build.skyframe.AbstractSkyKey;
+import com.google.devtools.build.skyframe.SkyFunctionName;
 import com.google.devtools.build.skyframe.SkyValue;
 import java.util.Arrays;
 import javax.annotation.Nullable;
@@ -124,8 +127,29 @@ public abstract class RepositoryDirectoryValue implements SkyValue {
       new NoRepositoryDirectoryValue();
 
   /** Creates a key from the given repository name. */
-  public static SkyKey key(RepositoryName repository) {
-    return LegacySkyKey.create(SkyFunctions.REPOSITORY_DIRECTORY, repository);
+  public static Key key(RepositoryName repository) {
+    return Key.create(repository);
+  }
+
+  @AutoCodec.VisibleForSerialization
+  @AutoCodec
+  static class Key extends AbstractSkyKey<RepositoryName> {
+    private static final Interner<Key> interner = BlazeInterners.newWeakInterner();
+
+    private Key(RepositoryName arg) {
+      super(arg);
+    }
+
+    @AutoCodec.VisibleForSerialization
+    @AutoCodec.Instantiator
+    static Key create(RepositoryName arg) {
+      return interner.intern(new Key(arg));
+    }
+
+    @Override
+    public SkyFunctionName functionName() {
+      return SkyFunctions.REPOSITORY_DIRECTORY;
+    }
   }
 
   public static Builder builder() {
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/ASTFileLookupValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/ASTFileLookupValue.java
index 6a00a4b78f..247d0e0202 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/ASTFileLookupValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/ASTFileLookupValue.java
@@ -15,10 +15,13 @@
 package com.google.devtools.build.lib.skyframe;
 
 import com.google.common.base.Preconditions;
+import com.google.common.collect.Interner;
 import com.google.devtools.build.lib.cmdline.Label;
+import com.google.devtools.build.lib.concurrent.BlazeInterners;
+import com.google.devtools.build.lib.skyframe.serialization.autocodec.AutoCodec;
 import com.google.devtools.build.lib.syntax.BuildFileAST;
-import com.google.devtools.build.skyframe.LegacySkyKey;
-import com.google.devtools.build.skyframe.SkyKey;
+import com.google.devtools.build.skyframe.AbstractSkyKey;
+import com.google.devtools.build.skyframe.SkyFunctionName;
 import com.google.devtools.build.skyframe.SkyValue;
 
 /**
@@ -30,7 +33,7 @@ public abstract class ASTFileLookupValue implements SkyValue {
   public abstract boolean lookupSuccessful();
   public abstract BuildFileAST getAST();
   public abstract String getErrorMsg();
-  
+
   /** If the file is found, this class encapsulates the parsed AST. */
   private static class ASTLookupWithFile extends ASTFileLookupValue {
     private final BuildFileAST ast;
@@ -56,7 +59,7 @@ public abstract class ASTFileLookupValue implements SkyValue {
           "attempted to retrieve unsuccessful lookup reason for successful lookup");
     }
   }
- 
+
   /** If the file isn't found, this class encapsulates a message with the reason. */
   private static class ASTLookupNoFile extends ASTFileLookupValue {
     private final String errorMsg;
@@ -85,17 +88,38 @@ public abstract class ASTFileLookupValue implements SkyValue {
     return new ASTLookupNoFile(
         String.format("Unable to load package for '%s': %s", fileLabel, reason));
   }
-  
+
   static ASTFileLookupValue forBadFile(Label fileLabel) {
     return new ASTLookupNoFile(
         String.format("Unable to load file '%s': file doesn't exist or isn't a file", fileLabel));
   }
-  
+
   public static ASTFileLookupValue withFile(BuildFileAST ast) {
     return new ASTLookupWithFile(ast);
   }
 
-  public static SkyKey key(Label astFileLabel) {
-    return LegacySkyKey.create(SkyFunctions.AST_FILE_LOOKUP, astFileLabel);
+  public static Key key(Label astFileLabel) {
+    return ASTFileLookupValue.Key.create(astFileLabel);
+  }
+
+  @AutoCodec.VisibleForSerialization
+  @AutoCodec
+  static class Key extends AbstractSkyKey<Label> {
+    private static final Interner<Key> interner = BlazeInterners.newWeakInterner();
+
+    private Key(Label arg) {
+      super(arg);
+    }
+
+    @AutoCodec.VisibleForSerialization
+    @AutoCodec.Instantiator
+    static Key create(Label arg) {
+      return interner.intern(new Key(arg));
+    }
+
+    @Override
+    public SkyFunctionName functionName() {
+      return SkyFunctions.AST_FILE_LOOKUP;
+    }
   }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/ActionEnvironmentFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/ActionEnvironmentFunction.java
index efc6c9a84c..81c27fec48 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/ActionEnvironmentFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/ActionEnvironmentFunction.java
@@ -15,8 +15,12 @@
 package com.google.devtools.build.lib.skyframe;
 
 import com.google.common.collect.ImmutableList;
-import com.google.devtools.build.skyframe.LegacySkyKey;
+import com.google.common.collect.Interner;
+import com.google.devtools.build.lib.concurrent.BlazeInterners;
+import com.google.devtools.build.lib.skyframe.serialization.autocodec.AutoCodec;
+import com.google.devtools.build.skyframe.AbstractSkyKey;
 import com.google.devtools.build.skyframe.SkyFunction;
+import com.google.devtools.build.skyframe.SkyFunctionName;
 import com.google.devtools.build.skyframe.SkyKey;
 import com.google.devtools.build.skyframe.SkyValue;
 import java.util.Collections;
@@ -45,12 +49,33 @@ public final class ActionEnvironmentFunction implements SkyFunction {
     if (actionEnv.containsKey(key) && actionEnv.get(key) != null) {
       return new ClientEnvironmentValue(actionEnv.get(key));
     }
-    return env.getValue(LegacySkyKey.create(SkyFunctions.CLIENT_ENVIRONMENT_VARIABLE, key));
+    return env.getValue(ClientEnvironmentFunction.key(key));
   }
 
   /** @return the SkyKey to invoke this function for the environment variable {@code variable}. */
-  public static SkyKey key(String variable) {
-    return LegacySkyKey.create(SkyFunctions.ACTION_ENVIRONMENT_VARIABLE, variable);
+  public static Key key(String variable) {
+    return Key.create(variable);
+  }
+
+  @AutoCodec.VisibleForSerialization
+  @AutoCodec
+  static class Key extends AbstractSkyKey<String> {
+    private static final Interner<Key> interner = BlazeInterners.newWeakInterner();
+
+    private Key(String arg) {
+      super(arg);
+    }
+
+    @AutoCodec.VisibleForSerialization
+    @AutoCodec.Instantiator
+    static Key create(String arg) {
+      return interner.intern(new Key(arg));
+    }
+
+    @Override
+    public SkyFunctionName functionName() {
+      return SkyFunctions.ACTION_ENVIRONMENT_VARIABLE;
+    }
   }
 
   /**
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/ActionExecutionFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/ActionExecutionFunction.java
index a450f6fc06..3786ddcb4e 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/ActionExecutionFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/ActionExecutionFunction.java
@@ -43,7 +43,6 @@ import com.google.devtools.build.lib.events.Event;
 import com.google.devtools.build.lib.util.Pair;
 import com.google.devtools.build.lib.util.io.TimestampGranularityMonitor;
 import com.google.devtools.build.lib.vfs.PathFragment;
-import com.google.devtools.build.skyframe.LegacySkyKey;
 import com.google.devtools.build.skyframe.SkyFunction;
 import com.google.devtools.build.skyframe.SkyFunctionException;
 import com.google.devtools.build.skyframe.SkyKey;
@@ -88,13 +87,7 @@ public class ActionExecutionFunction implements SkyFunction, CompletionReceiver
     stateMap = Maps.newConcurrentMap();
   }
 
-  private static final Function<String, SkyKey> VAR_TO_SKYKEY =
-      new Function<String, SkyKey>() {
-        @Override
-        public SkyKey apply(String var) {
-          return LegacySkyKey.create(SkyFunctions.CLIENT_ENVIRONMENT_VARIABLE, var);
-        }
-      };
+  private static final Function<String, SkyKey> VAR_TO_SKYKEY = ClientEnvironmentFunction::key;
 
   @Override
   public SkyValue compute(SkyKey skyKey, Environment env) throws ActionExecutionFunctionException,
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/AspectCompletionValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/AspectCompletionValue.java
index ea6c77468c..7b33d0bfe4 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/AspectCompletionValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/AspectCompletionValue.java
@@ -14,11 +14,11 @@
 package com.google.devtools.build.lib.skyframe;
 
 import com.google.auto.value.AutoValue;
-import com.google.common.base.Function;
 import com.google.common.collect.Iterables;
 import com.google.devtools.build.lib.analysis.TopLevelArtifactContext;
 import com.google.devtools.build.lib.skyframe.AspectValue.AspectKey;
-import com.google.devtools.build.skyframe.LegacySkyKey;
+import com.google.devtools.build.lib.skyframe.serialization.autocodec.AutoCodec;
+import com.google.devtools.build.skyframe.SkyFunctionName;
 import com.google.devtools.build.skyframe.SkyKey;
 import com.google.devtools.build.skyframe.SkyValue;
 import java.util.Collection;
@@ -27,32 +27,18 @@ import java.util.Collection;
  * The value of an AspectCompletion. Currently this just stores an Aspect.
  */
 public class AspectCompletionValue implements SkyValue {
-  private final AspectValue aspectValue;
+  @AutoCodec static final AspectCompletionValue INSTANCE = new AspectCompletionValue();
 
-  AspectCompletionValue(AspectValue aspectValue) {
-    this.aspectValue = aspectValue;
-  }
-
-  public AspectValue getAspectValue() {
-    return aspectValue;
-  }
+  private AspectCompletionValue() {}
 
   public static Iterable<SkyKey> keys(
       Collection<AspectValue> targets, final TopLevelArtifactContext ctx) {
     return Iterables.transform(
-        targets,
-        new Function<AspectValue, SkyKey>() {
-          @Override
-          public SkyKey apply(AspectValue aspectValue) {
-            return LegacySkyKey.create(
-                SkyFunctions.ASPECT_COMPLETION,
-                AspectCompletionKey.create(aspectValue.getKey(), ctx));
-          }
-        });
+        targets, aspectValue -> AspectCompletionKey.create(aspectValue.getKey(), ctx));
   }
 
- @AutoValue
- abstract static class AspectCompletionKey {
+  @AutoValue
+  abstract static class AspectCompletionKey implements SkyKey {
     public static AspectCompletionKey create(
         AspectKey aspectKey, TopLevelArtifactContext topLevelArtifactContext) {
       return new AutoValue_AspectCompletionValue_AspectCompletionKey(
@@ -61,5 +47,10 @@ public class AspectCompletionValue implements SkyValue {
 
     public abstract AspectKey aspectKey();
     public abstract TopLevelArtifactContext topLevelArtifactContext();
+
+    @Override
+    public SkyFunctionName functionName() {
+      return SkyFunctions.ASPECT_COMPLETION;
+    }
   }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/BlacklistedPackagePrefixesValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/BlacklistedPackagePrefixesValue.java
index 73d13b8b95..13494812ca 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/BlacklistedPackagePrefixesValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/BlacklistedPackagePrefixesValue.java
@@ -17,7 +17,6 @@ import com.google.common.base.Preconditions;
 import com.google.common.collect.ImmutableSet;
 import com.google.devtools.build.lib.skyframe.serialization.autocodec.AutoCodec;
 import com.google.devtools.build.lib.vfs.PathFragment;
-import com.google.devtools.build.skyframe.LegacySkyKey;
 import com.google.devtools.build.skyframe.SkyKey;
 import com.google.devtools.build.skyframe.SkyValue;
 
@@ -26,8 +25,8 @@ import com.google.devtools.build.skyframe.SkyValue;
 public class BlacklistedPackagePrefixesValue implements SkyValue {
   private final ImmutableSet<PathFragment> patterns;
 
-  private static final SkyKey BLACKLIST_KEY =
-      LegacySkyKey.create(SkyFunctions.BLACKLISTED_PACKAGE_PREFIXES, "");
+  @AutoCodec.VisibleForSerialization @AutoCodec
+  static final SkyKey BLACKLIST_KEY = () -> SkyFunctions.BLACKLISTED_PACKAGE_PREFIXES;
 
   public BlacklistedPackagePrefixesValue(ImmutableSet<PathFragment> patterns) {
     this.patterns = Preconditions.checkNotNull(patterns);
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/ChainUniquenessUtils.java b/src/main/java/com/google/devtools/build/lib/skyframe/ChainUniquenessUtils.java
index 8f4db91db6..f0b3274444 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/ChainUniquenessUtils.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/ChainUniquenessUtils.java
@@ -13,11 +13,7 @@
 // limitations under the License.
 package com.google.devtools.build.lib.skyframe;
 
-import com.google.common.base.Preconditions;
 import com.google.common.collect.ImmutableList;
-import com.google.devtools.build.skyframe.LegacySkyKey;
-import com.google.devtools.build.skyframe.SkyFunctionName;
-import com.google.devtools.build.skyframe.SkyKey;
 
 /**
  * A value for ensuring that an error for a cycle/chain is reported exactly once. This is achieved
@@ -29,15 +25,10 @@ class ChainUniquenessUtils {
   private ChainUniquenessUtils() {}
 
   /**
-   * Create a SkyKey for {@code functionName} with a canonicalized representation of the cycle
-   * specified by {@code chain} as the argument. {@code chain} must be non-empty.
+   * Create a canonicalized representation of the cycle specified by {@code chain}. {@code chain}
+   * must be non-empty.
    */
-  static SkyKey key(SkyFunctionName functionName, ImmutableList<? extends Object> chain) {
-    Preconditions.checkState(!chain.isEmpty());
-    return LegacySkyKey.create(functionName, canonicalize(chain));
-  }
-
-  private static ImmutableList<Object> canonicalize(ImmutableList<? extends Object> cycle) {
+  static <T> ImmutableList<T> canonicalize(ImmutableList<T> cycle) {
     int minPos = 0;
     String minString = cycle.get(0).toString();
     for (int i = 1; i < cycle.size(); i++) {
@@ -48,7 +39,7 @@ class ChainUniquenessUtils {
         minString = candidateString;
       }
     }
-    ImmutableList.Builder<Object> builder = ImmutableList.builder();
+    ImmutableList.Builder<T> builder = ImmutableList.builder();
     for (int i = 0; i < cycle.size(); i++) {
       int pos = (minPos + i) % cycle.size();
       builder.add(cycle.get(pos));
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/ClientEnvironmentFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/ClientEnvironmentFunction.java
index 20de7df60a..7c4c798b4a 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/ClientEnvironmentFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/ClientEnvironmentFunction.java
@@ -14,7 +14,12 @@
 
 package com.google.devtools.build.lib.skyframe;
 
+import com.google.common.collect.Interner;
+import com.google.devtools.build.lib.concurrent.BlazeInterners;
+import com.google.devtools.build.lib.skyframe.serialization.autocodec.AutoCodec;
+import com.google.devtools.build.skyframe.AbstractSkyKey;
 import com.google.devtools.build.skyframe.SkyFunction;
+import com.google.devtools.build.skyframe.SkyFunctionName;
 import com.google.devtools.build.skyframe.SkyKey;
 import com.google.devtools.build.skyframe.SkyValue;
 import java.util.Map;
@@ -23,6 +28,30 @@ import javax.annotation.Nullable;
 
 /** The Skyframe function that generates values for variables of the client environment. */
 public final class ClientEnvironmentFunction implements SkyFunction {
+  public static Key key(String keyString) {
+    return ClientEnvironmentFunction.Key.create(keyString);
+  }
+
+  @AutoCodec.VisibleForSerialization
+  @AutoCodec
+  static class Key extends AbstractSkyKey<String> {
+    private static final Interner<Key> interner = BlazeInterners.newWeakInterner();
+
+    private Key(String arg) {
+      super(arg);
+    }
+
+    @AutoCodec.VisibleForSerialization
+    @AutoCodec.Instantiator
+    static Key create(String arg) {
+      return interner.intern(new Key(arg));
+    }
+
+    @Override
+    public SkyFunctionName functionName() {
+      return SkyFunctions.CLIENT_ENVIRONMENT_VARIABLE;
+    }
+  }
 
   private final AtomicReference<Map<String, String>> clientEnv;
 
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/CollectPackagesUnderDirectoryFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/CollectPackagesUnderDirectoryFunction.java
index 214daf54c1..2efd41b5a0 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/CollectPackagesUnderDirectoryFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/CollectPackagesUnderDirectoryFunction.java
@@ -19,7 +19,6 @@ import com.google.common.collect.Iterables;
 import com.google.devtools.build.lib.analysis.BlazeDirectories;
 import com.google.devtools.build.lib.cmdline.RepositoryName;
 import com.google.devtools.build.lib.packages.NoSuchPackageException;
-import com.google.devtools.build.lib.skyframe.RecursivePkgValue.RecursivePkgKey;
 import com.google.devtools.build.lib.vfs.PathFragment;
 import com.google.devtools.build.lib.vfs.RootedPath;
 import com.google.devtools.build.skyframe.SkyFunction;
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/CollectPackagesUnderDirectoryValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/CollectPackagesUnderDirectoryValue.java
index 9e2f280382..9ca228c3a0 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/CollectPackagesUnderDirectoryValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/CollectPackagesUnderDirectoryValue.java
@@ -17,12 +17,14 @@ import com.google.common.base.MoreObjects;
 import com.google.common.base.Preconditions;
 import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.ImmutableSet;
+import com.google.common.collect.Interner;
 import com.google.devtools.build.lib.cmdline.RepositoryName;
+import com.google.devtools.build.lib.concurrent.BlazeInterners;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe;
-import com.google.devtools.build.lib.skyframe.RecursivePkgValue.RecursivePkgKey;
+import com.google.devtools.build.lib.skyframe.serialization.autocodec.AutoCodec;
 import com.google.devtools.build.lib.vfs.PathFragment;
 import com.google.devtools.build.lib.vfs.RootedPath;
-import com.google.devtools.build.skyframe.LegacySkyKey;
+import com.google.devtools.build.skyframe.SkyFunctionName;
 import com.google.devtools.build.skyframe.SkyKey;
 import com.google.devtools.build.skyframe.SkyValue;
 import java.util.Objects;
@@ -227,10 +229,33 @@ public abstract class CollectPackagesUnderDirectoryValue implements SkyValue {
   @ThreadSafe
   public static SkyKey key(
       RepositoryName repository, RootedPath rootedPath, ImmutableSet<PathFragment> excludedPaths) {
-    return key(new RecursivePkgKey(repository, rootedPath, excludedPaths));
+    return Key.create(repository, rootedPath, excludedPaths);
   }
 
-  static SkyKey key(RecursivePkgKey recursivePkgKey) {
-    return LegacySkyKey.create(SkyFunctions.COLLECT_PACKAGES_UNDER_DIRECTORY, recursivePkgKey);
+  @AutoCodec.VisibleForSerialization
+  @AutoCodec
+  static class Key extends RecursivePkgSkyKey {
+    private static final Interner<Key> interner = BlazeInterners.newWeakInterner();
+
+    private Key(
+        RepositoryName repositoryName,
+        RootedPath rootedPath,
+        ImmutableSet<PathFragment> excludedPaths) {
+      super(repositoryName, rootedPath, excludedPaths);
+    }
+
+    @AutoCodec.VisibleForSerialization
+    @AutoCodec.Instantiator
+    static Key create(
+        RepositoryName repositoryName,
+        RootedPath rootedPath,
+        ImmutableSet<PathFragment> excludedPaths) {
+      return interner.intern(new Key(repositoryName, rootedPath, excludedPaths));
+    }
+
+    @Override
+    public SkyFunctionName functionName() {
+      return SkyFunctions.COLLECT_PACKAGES_UNDER_DIRECTORY;
+    }
   }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/CollectTargetsInPackageValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/CollectTargetsInPackageValue.java
index 1ed9592eb8..19c0c1dbf8 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/CollectTargetsInPackageValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/CollectTargetsInPackageValue.java
@@ -17,10 +17,9 @@ import com.google.auto.value.AutoValue;
 import com.google.devtools.build.lib.cmdline.PackageIdentifier;
 import com.google.devtools.build.lib.pkgcache.FilteringPolicy;
 import com.google.devtools.build.lib.skyframe.serialization.autocodec.AutoCodec;
-import com.google.devtools.build.skyframe.LegacySkyKey;
+import com.google.devtools.build.skyframe.SkyFunctionName;
 import com.google.devtools.build.skyframe.SkyKey;
 import com.google.devtools.build.skyframe.SkyValue;
-import java.io.Serializable;
 
 /** Singleton result of {@link CollectTargetsInPackageFunction}. */
 public class CollectTargetsInPackageValue implements SkyValue {
@@ -33,18 +32,18 @@ public class CollectTargetsInPackageValue implements SkyValue {
    * Creates a key for evaluation of {@link CollectTargetsInPackageFunction}. See that class's
    * comment for what callers should have done beforehand.
    */
-  public static SkyKey key(PackageIdentifier packageId, FilteringPolicy filteringPolicy) {
-    return LegacySkyKey.create(
-        SkyFunctions.COLLECT_TARGETS_IN_PACKAGE,
-        CollectTargetsInPackageKey.create(packageId, filteringPolicy));
+  public static CollectTargetsInPackageKey key(
+      PackageIdentifier packageId, FilteringPolicy filteringPolicy) {
+    return CollectTargetsInPackageKey.create(packageId, filteringPolicy);
   }
 
   /** {@link SkyKey} argument. */
-  @AutoCodec
   @AutoValue
-  public abstract static class CollectTargetsInPackageKey implements Serializable {
+  @AutoCodec
+  public abstract static class CollectTargetsInPackageKey implements SkyKey {
+    @AutoCodec.VisibleForSerialization
     @AutoCodec.Instantiator
-    public static CollectTargetsInPackageKey create(
+    static CollectTargetsInPackageKey create(
         PackageIdentifier packageId, FilteringPolicy filteringPolicy) {
       return new AutoValue_CollectTargetsInPackageValue_CollectTargetsInPackageKey(
           packageId, filteringPolicy);
@@ -53,5 +52,10 @@ public class CollectTargetsInPackageValue implements SkyValue {
     public abstract PackageIdentifier getPackageId();
 
     public abstract FilteringPolicy getFilteringPolicy();
+
+    @Override
+    public SkyFunctionName functionName() {
+      return SkyFunctions.COLLECT_TARGETS_IN_PACKAGE;
+    }
   }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/CompletionFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/CompletionFunction.java
index 780d74924f..675ce81da9 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/CompletionFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/CompletionFunction.java
@@ -261,7 +261,7 @@ public final class CompletionFunction<TValue extends SkyValue, TResult extends S
 
     @Override
     public AspectCompletionValue createResult(AspectValue value) {
-      return new AspectCompletionValue(value);
+      return AspectCompletionValue.INSTANCE;
     }
 
     @Override
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/ContainingPackageLookupValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/ContainingPackageLookupValue.java
index 24652583fb..725d20193a 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/ContainingPackageLookupValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/ContainingPackageLookupValue.java
@@ -14,11 +14,13 @@
 package com.google.devtools.build.lib.skyframe;
 
 import com.google.common.base.Preconditions;
+import com.google.common.collect.Interner;
 import com.google.devtools.build.lib.cmdline.PackageIdentifier;
+import com.google.devtools.build.lib.concurrent.BlazeInterners;
 import com.google.devtools.build.lib.skyframe.serialization.autocodec.AutoCodec;
 import com.google.devtools.build.lib.vfs.Root;
-import com.google.devtools.build.skyframe.LegacySkyKey;
-import com.google.devtools.build.skyframe.SkyKey;
+import com.google.devtools.build.skyframe.AbstractSkyKey;
+import com.google.devtools.build.skyframe.SkyFunctionName;
 import com.google.devtools.build.skyframe.SkyValue;
 
 /**
@@ -39,10 +41,31 @@ public abstract class ContainingPackageLookupValue implements SkyValue {
   /** If there is a containing package, returns its package root */
   public abstract Root getContainingPackageRoot();
 
-  public static SkyKey key(PackageIdentifier id) {
+  public static Key key(PackageIdentifier id) {
     Preconditions.checkArgument(!id.getPackageFragment().isAbsolute(), id);
     Preconditions.checkArgument(!id.getRepository().isDefault(), id);
-    return LegacySkyKey.create(SkyFunctions.CONTAINING_PACKAGE_LOOKUP, id);
+    return Key.create(id);
+  }
+
+  @AutoCodec.VisibleForSerialization
+  @AutoCodec
+  static class Key extends AbstractSkyKey<PackageIdentifier> {
+    private static final Interner<Key> interner = BlazeInterners.newWeakInterner();
+
+    private Key(PackageIdentifier arg) {
+      super(arg);
+    }
+
+    @AutoCodec.VisibleForSerialization
+    @AutoCodec.Instantiator
+    static Key create(PackageIdentifier arg) {
+      return interner.intern(new Key(arg));
+    }
+
+    @Override
+    public SkyFunctionName functionName() {
+      return SkyFunctions.CONTAINING_PACKAGE_LOOKUP;
+    }
   }
 
   public static ContainingPackage withContainingPackage(PackageIdentifier pkgId, Root root) {
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/DirectoryListingStateValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/DirectoryListingStateValue.java
index c3130721d1..39343a2403 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/DirectoryListingStateValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/DirectoryListingStateValue.java
@@ -14,13 +14,16 @@
 package com.google.devtools.build.lib.skyframe;
 
 import com.google.common.base.Preconditions;
+import com.google.common.collect.Interner;
+import com.google.devtools.build.lib.concurrent.BlazeInterners;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe;
+import com.google.devtools.build.lib.skyframe.serialization.autocodec.AutoCodec;
 import com.google.devtools.build.lib.vfs.Dirent;
 import com.google.devtools.build.lib.vfs.Dirent.Type;
 import com.google.devtools.build.lib.vfs.RootedPath;
 import com.google.devtools.build.lib.vfs.Symlinks;
-import com.google.devtools.build.skyframe.LegacySkyKey;
-import com.google.devtools.build.skyframe.SkyKey;
+import com.google.devtools.build.skyframe.AbstractSkyKey;
+import com.google.devtools.build.skyframe.SkyFunctionName;
 import com.google.devtools.build.skyframe.SkyValue;
 import java.io.IOException;
 import java.io.Serializable;
@@ -55,8 +58,29 @@ public final class DirectoryListingStateValue implements SkyValue {
   }
 
   @ThreadSafe
-  public static SkyKey key(RootedPath rootedPath) {
-    return LegacySkyKey.create(SkyFunctions.DIRECTORY_LISTING_STATE, rootedPath);
+  public static Key key(RootedPath rootedPath) {
+    return Key.create(rootedPath);
+  }
+
+  @AutoCodec.VisibleForSerialization
+  @AutoCodec
+  static class Key extends AbstractSkyKey<RootedPath> {
+    private static final Interner<Key> interner = BlazeInterners.newWeakInterner();
+
+    private Key(RootedPath arg) {
+      super(arg);
+    }
+
+    @AutoCodec.VisibleForSerialization
+    @AutoCodec.Instantiator
+    static Key create(RootedPath arg) {
+      return interner.intern(new Key(arg));
+    }
+
+    @Override
+    public SkyFunctionName functionName() {
+      return SkyFunctions.DIRECTORY_LISTING_STATE;
+    }
   }
 
   /**
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/DirectoryListingValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/DirectoryListingValue.java
index d6fb7b484b..8d19cc1739 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/DirectoryListingValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/DirectoryListingValue.java
@@ -13,11 +13,14 @@
 // limitations under the License.
 package com.google.devtools.build.lib.skyframe;
 
+import com.google.common.collect.Interner;
+import com.google.devtools.build.lib.concurrent.BlazeInterners;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe;
+import com.google.devtools.build.lib.skyframe.serialization.autocodec.AutoCodec;
 import com.google.devtools.build.lib.vfs.RootedPath;
-import com.google.devtools.build.skyframe.LegacySkyKey;
-import com.google.devtools.build.skyframe.SkyKey;
+import com.google.devtools.build.skyframe.AbstractSkyKey;
+import com.google.devtools.build.skyframe.SkyFunctionName;
 import com.google.devtools.build.skyframe.SkyValue;
 import java.util.Objects;
 
@@ -49,13 +52,34 @@ public abstract class DirectoryListingValue implements SkyValue {
   public abstract DirectoryListingStateValue getDirectoryListingStateValue();
 
   /**
-   * Returns a {@link SkyKey} for getting the directory entries of the given directory. The
-   * given path is assumed to be an existing directory (e.g. via {@link FileValue#isDirectory} or
-   * from a directory listing on its parent directory).
+   * Returns a {@link Key} for getting the directory entries of the given directory. The given path
+   * is assumed to be an existing directory (e.g. via {@link FileValue#isDirectory} or from a
+   * directory listing on its parent directory).
    */
   @ThreadSafe
-  public static SkyKey key(RootedPath directoryUnderRoot) {
-    return LegacySkyKey.create(SkyFunctions.DIRECTORY_LISTING, directoryUnderRoot);
+  public static Key key(RootedPath directoryUnderRoot) {
+    return Key.create(directoryUnderRoot);
+  }
+
+  @AutoCodec.VisibleForSerialization
+  @AutoCodec
+  static class Key extends AbstractSkyKey<RootedPath> {
+    private static final Interner<Key> interner = BlazeInterners.newWeakInterner();
+
+    private Key(RootedPath arg) {
+      super(arg);
+    }
+
+    @AutoCodec.VisibleForSerialization
+    @AutoCodec.Instantiator
+    static Key create(RootedPath arg) {
+      return interner.intern(new Key(arg));
+    }
+
+    @Override
+    public SkyFunctionName functionName() {
+      return SkyFunctions.DIRECTORY_LISTING;
+    }
   }
 
   static DirectoryListingValue value(RootedPath dirRootedPath, FileValue dirFileValue,
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/ExternalPackageFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/ExternalPackageFunction.java
index c21aa6c95a..f47ab7a7e3 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/ExternalPackageFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/ExternalPackageFunction.java
@@ -14,9 +14,13 @@
 
 package com.google.devtools.build.lib.skyframe;
 
+import com.google.common.collect.Interner;
+import com.google.devtools.build.lib.concurrent.BlazeInterners;
+import com.google.devtools.build.lib.skyframe.serialization.autocodec.AutoCodec;
 import com.google.devtools.build.lib.vfs.RootedPath;
-import com.google.devtools.build.skyframe.LegacySkyKey;
+import com.google.devtools.build.skyframe.AbstractSkyKey;
 import com.google.devtools.build.skyframe.SkyFunction;
+import com.google.devtools.build.skyframe.SkyFunctionName;
 import com.google.devtools.build.skyframe.SkyKey;
 import com.google.devtools.build.skyframe.SkyValue;
 import javax.annotation.Nullable;
@@ -54,10 +58,29 @@ public class ExternalPackageFunction implements SkyFunction {
     return null;
   }
 
-  /**
-   * Returns a SkyKey to find the WORKSPACE file at the given path.
-   */
+  /** Returns a {@link Key} to find the WORKSPACE file at the given path. */
   public static SkyKey key(RootedPath workspacePath) {
-    return LegacySkyKey.create(SkyFunctions.EXTERNAL_PACKAGE, workspacePath);
+    return Key.create(workspacePath);
+  }
+
+  @AutoCodec.VisibleForSerialization
+  @AutoCodec
+  static class Key extends AbstractSkyKey<RootedPath> {
+    private static final Interner<Key> interner = BlazeInterners.newWeakInterner();
+
+    private Key(RootedPath arg) {
+      super(arg);
+    }
+
+    @AutoCodec.VisibleForSerialization
+    @AutoCodec.Instantiator
+    static Key create(RootedPath arg) {
+      return interner.intern(new Key(arg));
+    }
+
+    @Override
+    public SkyFunctionName functionName() {
+      return SkyFunctions.EXTERNAL_PACKAGE;
+    }
   }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/FileStateValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/FileStateValue.java
index 3d77021213..56988b8adb 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/FileStateValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/FileStateValue.java
@@ -16,8 +16,11 @@ package com.google.devtools.build.lib.skyframe;
 import com.google.common.annotations.VisibleForTesting;
 import com.google.common.base.MoreObjects;
 import com.google.common.base.Preconditions;
+import com.google.common.collect.Interner;
 import com.google.devtools.build.lib.actions.FileStateType;
+import com.google.devtools.build.lib.concurrent.BlazeInterners;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe;
+import com.google.devtools.build.lib.skyframe.serialization.autocodec.AutoCodec;
 import com.google.devtools.build.lib.util.io.TimestampGranularityMonitor;
 import com.google.devtools.build.lib.vfs.FileStatus;
 import com.google.devtools.build.lib.vfs.FileStatusWithDigest;
@@ -26,8 +29,8 @@ import com.google.devtools.build.lib.vfs.Path;
 import com.google.devtools.build.lib.vfs.PathFragment;
 import com.google.devtools.build.lib.vfs.RootedPath;
 import com.google.devtools.build.lib.vfs.Symlinks;
-import com.google.devtools.build.skyframe.LegacySkyKey;
-import com.google.devtools.build.skyframe.SkyKey;
+import com.google.devtools.build.skyframe.AbstractSkyKey;
+import com.google.devtools.build.skyframe.SkyFunctionName;
 import com.google.devtools.build.skyframe.SkyValue;
 import java.io.IOException;
 import java.util.Arrays;
@@ -95,8 +98,29 @@ public abstract class FileStateValue implements SkyValue {
 
   @VisibleForTesting
   @ThreadSafe
-  public static SkyKey key(RootedPath rootedPath) {
-    return LegacySkyKey.create(SkyFunctions.FILE_STATE, rootedPath);
+  public static Key key(RootedPath rootedPath) {
+    return Key.create(rootedPath);
+  }
+
+  @AutoCodec.VisibleForSerialization
+  @AutoCodec
+  static class Key extends AbstractSkyKey<RootedPath> {
+    private static final Interner<Key> interner = BlazeInterners.newWeakInterner();
+
+    private Key(RootedPath arg) {
+      super(arg);
+    }
+
+    @AutoCodec.VisibleForSerialization
+    @AutoCodec.Instantiator
+    static Key create(RootedPath arg) {
+      return interner.intern(new Key(arg));
+    }
+
+    @Override
+    public SkyFunctionName functionName() {
+      return SkyFunctions.FILE_STATE;
+    }
   }
 
   public abstract FileStateType getType();
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/FileSymlinkCycleUniquenessFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/FileSymlinkCycleUniquenessFunction.java
index eb01407612..590fce8051 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/FileSymlinkCycleUniquenessFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/FileSymlinkCycleUniquenessFunction.java
@@ -14,11 +14,15 @@
 package com.google.devtools.build.lib.skyframe;
 
 import com.google.common.collect.ImmutableList;
+import com.google.common.collect.Interner;
+import com.google.devtools.build.lib.concurrent.BlazeInterners;
+import com.google.devtools.build.lib.skyframe.serialization.autocodec.AutoCodec;
 import com.google.devtools.build.lib.vfs.RootedPath;
+import com.google.devtools.build.skyframe.AbstractSkyKey;
 import com.google.devtools.build.skyframe.SkyFunction;
+import com.google.devtools.build.skyframe.SkyFunctionName;
 import com.google.devtools.build.skyframe.SkyKey;
 
-
 /**
  * A {@link SkyFunction} that has the side effect of reporting a file symlink cycle. This is
  * achieved by forcing the same key for two logically equivalent cycles
@@ -29,7 +33,28 @@ public class FileSymlinkCycleUniquenessFunction
     extends AbstractChainUniquenessFunction<RootedPath> {
 
   static SkyKey key(ImmutableList<RootedPath> cycle) {
-    return ChainUniquenessUtils.key(SkyFunctions.FILE_SYMLINK_CYCLE_UNIQUENESS, cycle);
+    return Key.create(ChainUniquenessUtils.canonicalize(cycle));
+  }
+
+  @AutoCodec.VisibleForSerialization
+  @AutoCodec
+  static class Key extends AbstractSkyKey<ImmutableList<RootedPath>> {
+    private static final Interner<Key> interner = BlazeInterners.newWeakInterner();
+
+    private Key(ImmutableList<RootedPath> arg) {
+      super(arg);
+    }
+
+    @AutoCodec.VisibleForSerialization
+    @AutoCodec.Instantiator
+    static Key create(ImmutableList<RootedPath> arg) {
+      return interner.intern(new Key(arg));
+    }
+
+    @Override
+    public SkyFunctionName functionName() {
+      return SkyFunctions.FILE_SYMLINK_CYCLE_UNIQUENESS;
+    }
   }
 
   @Override
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/FileSymlinkInfiniteExpansionUniquenessFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/FileSymlinkInfiniteExpansionUniquenessFunction.java
index bb0680d6a1..c729465bc4 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/FileSymlinkInfiniteExpansionUniquenessFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/FileSymlinkInfiniteExpansionUniquenessFunction.java
@@ -14,8 +14,13 @@
 package com.google.devtools.build.lib.skyframe;
 
 import com.google.common.collect.ImmutableList;
+import com.google.common.collect.Interner;
+import com.google.devtools.build.lib.concurrent.BlazeInterners;
+import com.google.devtools.build.lib.skyframe.serialization.autocodec.AutoCodec;
 import com.google.devtools.build.lib.vfs.RootedPath;
+import com.google.devtools.build.skyframe.AbstractSkyKey;
 import com.google.devtools.build.skyframe.SkyFunction;
+import com.google.devtools.build.skyframe.SkyFunctionName;
 import com.google.devtools.build.skyframe.SkyKey;
 
 /**
@@ -28,8 +33,28 @@ public class FileSymlinkInfiniteExpansionUniquenessFunction
     extends AbstractChainUniquenessFunction<RootedPath> {
 
   static SkyKey key(ImmutableList<RootedPath> cycle) {
-    return ChainUniquenessUtils.key(
-        SkyFunctions.FILE_SYMLINK_INFINITE_EXPANSION_UNIQUENESS, cycle);
+    return Key.create(ChainUniquenessUtils.canonicalize(cycle));
+  }
+
+  @AutoCodec.VisibleForSerialization
+  @AutoCodec
+  static class Key extends AbstractSkyKey<ImmutableList<RootedPath>> {
+    private static final Interner<Key> interner = BlazeInterners.newWeakInterner();
+
+    private Key(ImmutableList<RootedPath> arg) {
+      super(arg);
+    }
+
+    @AutoCodec.VisibleForSerialization
+    @AutoCodec.Instantiator
+    static Key create(ImmutableList<RootedPath> arg) {
+      return interner.intern(new Key(arg));
+    }
+
+    @Override
+    public SkyFunctionName functionName() {
+      return SkyFunctions.FILE_SYMLINK_INFINITE_EXPANSION_UNIQUENESS;
+    }
   }
 
   @Override
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/FileValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/FileValue.java
index 7374bf32fe..a0fe84db92 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/FileValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/FileValue.java
@@ -14,13 +14,16 @@
 package com.google.devtools.build.lib.skyframe;
 
 import com.google.common.base.Preconditions;
+import com.google.common.collect.Interner;
 import com.google.devtools.build.lib.actions.FileStateType;
+import com.google.devtools.build.lib.concurrent.BlazeInterners;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe;
+import com.google.devtools.build.lib.skyframe.serialization.autocodec.AutoCodec;
 import com.google.devtools.build.lib.vfs.PathFragment;
 import com.google.devtools.build.lib.vfs.RootedPath;
-import com.google.devtools.build.skyframe.LegacySkyKey;
-import com.google.devtools.build.skyframe.SkyKey;
+import com.google.devtools.build.skyframe.AbstractSkyKey;
+import com.google.devtools.build.skyframe.SkyFunctionName;
 import com.google.devtools.build.skyframe.SkyValue;
 import java.util.Objects;
 import javax.annotation.Nullable;
@@ -112,12 +115,31 @@ public abstract class FileValue implements SkyValue {
     return realFileStateValue().getDigest();
   }
 
-  /**
-   * Returns a key for building a file value for the given root-relative path.
-   */
+  /** Returns a key for building a file value for the given root-relative path. */
   @ThreadSafe
-  public static SkyKey key(RootedPath rootedPath) {
-    return LegacySkyKey.create(SkyFunctions.FILE, rootedPath);
+  public static Key key(RootedPath rootedPath) {
+    return Key.create(rootedPath);
+  }
+
+  @AutoCodec.VisibleForSerialization
+  @AutoCodec
+  static class Key extends AbstractSkyKey<RootedPath> {
+    private static final Interner<Key> interner = BlazeInterners.newWeakInterner();
+
+    private Key(RootedPath arg) {
+      super(arg);
+    }
+
+    @AutoCodec.VisibleForSerialization
+    @AutoCodec.Instantiator
+    static Key create(RootedPath arg) {
+      return interner.intern(new Key(arg));
+    }
+
+    @Override
+    public SkyFunctionName functionName() {
+      return SkyFunctions.FILE;
+    }
   }
 
   /**
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/FilesetEntryFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/FilesetEntryFunction.java
index 02f256f433..4ed96ec337 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/FilesetEntryFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/FilesetEntryFunction.java
@@ -237,10 +237,13 @@ public final class FilesetEntryFunction implements SkyFunction {
   private static RecursiveFilesystemTraversalValue traverse(
       Environment env, String errorInfo, DirectTraversal traversal)
       throws MissingDepException, InterruptedException {
-    SkyKey depKey = RecursiveFilesystemTraversalValue.key(
-        new RecursiveFilesystemTraversalValue.TraversalRequest(traversal.getRoot(),
-            traversal.isGenerated(), traversal.getPackageBoundaryMode(), traversal.isPackage(),
-            errorInfo));
+    RecursiveFilesystemTraversalValue.TraversalRequest depKey =
+        RecursiveFilesystemTraversalValue.TraversalRequest.create(
+            traversal.getRoot(),
+            traversal.isGenerated(),
+            traversal.getPackageBoundaryMode(),
+            traversal.isPackage(),
+            errorInfo);
     RecursiveFilesystemTraversalValue v = (RecursiveFilesystemTraversalValue) env.getValue(depKey);
     if (env.valuesMissing()) {
       throw new MissingDepException();
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/LocalRepositoryLookupValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/LocalRepositoryLookupValue.java
index 0bdf7ab2b6..c4c784a75c 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/LocalRepositoryLookupValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/LocalRepositoryLookupValue.java
@@ -13,11 +13,14 @@
 // limitations under the License.
 package com.google.devtools.build.lib.skyframe;
 
+import com.google.common.collect.Interner;
 import com.google.devtools.build.lib.cmdline.RepositoryName;
+import com.google.devtools.build.lib.concurrent.BlazeInterners;
+import com.google.devtools.build.lib.skyframe.serialization.autocodec.AutoCodec;
 import com.google.devtools.build.lib.vfs.PathFragment;
 import com.google.devtools.build.lib.vfs.RootedPath;
-import com.google.devtools.build.skyframe.LegacySkyKey;
-import com.google.devtools.build.skyframe.SkyKey;
+import com.google.devtools.build.skyframe.AbstractSkyKey;
+import com.google.devtools.build.skyframe.SkyFunctionName;
 import com.google.devtools.build.skyframe.SkyValue;
 
 /**
@@ -28,8 +31,29 @@ import com.google.devtools.build.skyframe.SkyValue;
  */
 public abstract class LocalRepositoryLookupValue implements SkyValue {
 
-  static SkyKey key(RootedPath directory) {
-    return LegacySkyKey.create(SkyFunctions.LOCAL_REPOSITORY_LOOKUP, directory);
+  static Key key(RootedPath directory) {
+    return Key.create(directory);
+  }
+
+  @AutoCodec.VisibleForSerialization
+  @AutoCodec
+  static class Key extends AbstractSkyKey<RootedPath> {
+    private static final Interner<Key> interner = BlazeInterners.newWeakInterner();
+
+    private Key(RootedPath arg) {
+      super(arg);
+    }
+
+    @AutoCodec.VisibleForSerialization
+    @AutoCodec.Instantiator
+    static Key create(RootedPath arg) {
+      return interner.intern(new Key(arg));
+    }
+
+    @Override
+    public SkyFunctionName functionName() {
+      return SkyFunctions.LOCAL_REPOSITORY_LOOKUP;
+    }
   }
 
   private static final LocalRepositoryLookupValue MAIN_REPO_VALUE = new MainRepositoryLookupValue();
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/PackageErrorFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/PackageErrorFunction.java
index 3aebda0b3e..acef91d2df 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/PackageErrorFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/PackageErrorFunction.java
@@ -14,15 +14,19 @@
 package com.google.devtools.build.lib.skyframe;
 
 import com.google.common.base.Preconditions;
+import com.google.common.collect.Interner;
 import com.google.devtools.build.lib.cmdline.PackageIdentifier;
+import com.google.devtools.build.lib.concurrent.BlazeInterners;
 import com.google.devtools.build.lib.packages.BuildFileContainsErrorsException;
 import com.google.devtools.build.lib.packages.BuildFileNotFoundException;
 import com.google.devtools.build.lib.packages.NoSuchPackageException;
 import com.google.devtools.build.lib.packages.Package;
-import com.google.devtools.build.skyframe.LegacySkyKey;
+import com.google.devtools.build.lib.skyframe.serialization.autocodec.AutoCodec;
+import com.google.devtools.build.skyframe.AbstractSkyKey;
 import com.google.devtools.build.skyframe.SkyFunction;
 import com.google.devtools.build.skyframe.SkyFunctionException;
 import com.google.devtools.build.skyframe.SkyFunctionException.Transience;
+import com.google.devtools.build.skyframe.SkyFunctionName;
 import com.google.devtools.build.skyframe.SkyKey;
 import com.google.devtools.build.skyframe.SkyValue;
 import javax.annotation.Nullable;
@@ -38,8 +42,29 @@ import javax.annotation.Nullable;
  * should never return null, since all of its dependencies should already be present.
  */
 public class PackageErrorFunction implements SkyFunction {
-  public static SkyKey key(PackageIdentifier packageIdentifier) {
-    return LegacySkyKey.create(SkyFunctions.PACKAGE_ERROR, packageIdentifier);
+  public static Key key(PackageIdentifier packageIdentifier) {
+    return Key.create(packageIdentifier);
+  }
+
+  @AutoCodec.VisibleForSerialization
+  @AutoCodec
+  static class Key extends AbstractSkyKey<PackageIdentifier> {
+    private static final Interner<Key> interner = BlazeInterners.newWeakInterner();
+
+    private Key(PackageIdentifier arg) {
+      super(arg);
+    }
+
+    @AutoCodec.VisibleForSerialization
+    @AutoCodec.Instantiator
+    static Key create(PackageIdentifier arg) {
+      return interner.intern(new Key(arg));
+    }
+
+    @Override
+    public SkyFunctionName functionName() {
+      return SkyFunctions.PACKAGE_ERROR;
+    }
   }
 
   @Nullable
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/PackageLookupValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/PackageLookupValue.java
index c76a7ad8e1..2b7c49af53 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/PackageLookupValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/PackageLookupValue.java
@@ -15,13 +15,16 @@ package com.google.devtools.build.lib.skyframe;
 
 import com.google.common.base.Objects;
 import com.google.common.base.Preconditions;
+import com.google.common.collect.Interner;
 import com.google.devtools.build.lib.cmdline.PackageIdentifier;
+import com.google.devtools.build.lib.concurrent.BlazeInterners;
 import com.google.devtools.build.lib.packages.BuildFileName;
 import com.google.devtools.build.lib.skyframe.serialization.autocodec.AutoCodec;
 import com.google.devtools.build.lib.vfs.PathFragment;
 import com.google.devtools.build.lib.vfs.Root;
 import com.google.devtools.build.lib.vfs.RootedPath;
-import com.google.devtools.build.skyframe.LegacySkyKey;
+import com.google.devtools.build.skyframe.AbstractSkyKey;
+import com.google.devtools.build.skyframe.SkyFunctionName;
 import com.google.devtools.build.skyframe.SkyKey;
 import com.google.devtools.build.skyframe.SkyValue;
 
@@ -118,9 +121,30 @@ public abstract class PackageLookupValue implements SkyValue {
     return key(PackageIdentifier.createInMainRepo(directory));
   }
 
-  public static SkyKey key(PackageIdentifier pkgIdentifier) {
+  public static Key key(PackageIdentifier pkgIdentifier) {
     Preconditions.checkArgument(!pkgIdentifier.getRepository().isDefault());
-    return LegacySkyKey.create(SkyFunctions.PACKAGE_LOOKUP, pkgIdentifier);
+    return Key.create(pkgIdentifier);
+  }
+
+  @AutoCodec.VisibleForSerialization
+  @AutoCodec
+  static class Key extends AbstractSkyKey<PackageIdentifier> {
+    private static final Interner<Key> interner = BlazeInterners.newWeakInterner();
+
+    private Key(PackageIdentifier arg) {
+      super(arg);
+    }
+
+    @AutoCodec.VisibleForSerialization
+    @AutoCodec.Instantiator
+    static Key create(PackageIdentifier arg) {
+      return interner.intern(new Key(arg));
+    }
+
+    @Override
+    public SkyFunctionName functionName() {
+      return SkyFunctions.PACKAGE_LOOKUP;
+    }
   }
 
   /** Successful lookup value. */
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/PackageValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/PackageValue.java
index 0314de623d..ba1962335b 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/PackageValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/PackageValue.java
@@ -14,14 +14,17 @@
 package com.google.devtools.build.lib.skyframe;
 
 import com.google.common.base.Preconditions;
+import com.google.common.collect.Interner;
 import com.google.devtools.build.lib.cmdline.PackageIdentifier;
+import com.google.devtools.build.lib.concurrent.BlazeInterners;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe;
 import com.google.devtools.build.lib.packages.BuildFileContainsErrorsException;
 import com.google.devtools.build.lib.packages.Package;
 import com.google.devtools.build.lib.skyframe.serialization.autocodec.AutoCodec;
-import com.google.devtools.build.skyframe.LegacySkyKey;
+import com.google.devtools.build.skyframe.AbstractSkyKey;
 import com.google.devtools.build.skyframe.NotComparableSkyValue;
+import com.google.devtools.build.skyframe.SkyFunctionName;
 import com.google.devtools.build.skyframe.SkyKey;
 import java.util.ArrayList;
 import java.util.List;
@@ -52,9 +55,30 @@ public class PackageValue implements NotComparableSkyValue {
     return "<PackageValue name=" + pkg.getName() + ">";
   }
 
-  public static SkyKey key(PackageIdentifier pkgIdentifier) {
+  public static Key key(PackageIdentifier pkgIdentifier) {
     Preconditions.checkArgument(!pkgIdentifier.getRepository().isDefault());
-    return LegacySkyKey.create(SkyFunctions.PACKAGE, pkgIdentifier);
+    return Key.create(pkgIdentifier);
+  }
+
+  @AutoCodec.VisibleForSerialization
+  @AutoCodec
+  static class Key extends AbstractSkyKey<PackageIdentifier> {
+    private static final Interner<Key> interner = BlazeInterners.newWeakInterner();
+
+    private Key(PackageIdentifier arg) {
+      super(arg);
+    }
+
+    @AutoCodec.VisibleForSerialization
+    @AutoCodec.Instantiator
+    static Key create(PackageIdentifier arg) {
+      return interner.intern(new Key(arg));
+    }
+
+    @Override
+    public SkyFunctionName functionName() {
+      return SkyFunctions.PACKAGE;
+    }
   }
 
   public static List<SkyKey> keys(Iterable<PackageIdentifier> pkgIdentifiers) {
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/PostConfiguredTargetValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/PostConfiguredTargetValue.java
index 4e044703cf..827bb8a310 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/PostConfiguredTargetValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/PostConfiguredTargetValue.java
@@ -15,8 +15,12 @@ package com.google.devtools.build.lib.skyframe;
 
 import com.google.common.base.Preconditions;
 import com.google.common.collect.ImmutableList;
+import com.google.common.collect.Interner;
 import com.google.devtools.build.lib.analysis.ConfiguredTarget;
-import com.google.devtools.build.skyframe.LegacySkyKey;
+import com.google.devtools.build.lib.concurrent.BlazeInterners;
+import com.google.devtools.build.lib.skyframe.serialization.autocodec.AutoCodec;
+import com.google.devtools.build.skyframe.AbstractSkyKey;
+import com.google.devtools.build.skyframe.SkyFunctionName;
 import com.google.devtools.build.skyframe.SkyKey;
 import com.google.devtools.build.skyframe.SkyValue;
 
@@ -40,8 +44,29 @@ class PostConfiguredTargetValue implements SkyValue {
     return keys.build();
   }
 
-  public static SkyKey key(ConfiguredTargetKey lac) {
-    return LegacySkyKey.create(SkyFunctions.POST_CONFIGURED_TARGET, lac);
+  public static Key key(ConfiguredTargetKey lac) {
+    return Key.create(lac);
+  }
+
+  @AutoCodec.VisibleForSerialization
+  @AutoCodec
+  static class Key extends AbstractSkyKey<ConfiguredTargetKey> {
+    private static final Interner<Key> interner = BlazeInterners.newWeakInterner();
+
+    private Key(ConfiguredTargetKey arg) {
+      super(arg);
+    }
+
+    @AutoCodec.VisibleForSerialization
+    @AutoCodec.Instantiator
+    static Key create(ConfiguredTargetKey arg) {
+      return interner.intern(new Key(arg));
+    }
+
+    @Override
+    public SkyFunctionName functionName() {
+      return SkyFunctions.POST_CONFIGURED_TARGET;
+    }
   }
 
   public ConfiguredTarget getCt() {
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/PrecomputedValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/PrecomputedValue.java
index 2f8338989d..1d92dc2bca 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/PrecomputedValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/PrecomputedValue.java
@@ -19,17 +19,20 @@ import com.google.common.base.Supplier;
 import com.google.common.base.Suppliers;
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableMap;
+import com.google.common.collect.Interner;
 import com.google.devtools.build.lib.actions.ActionAnalysisMetadata;
 import com.google.devtools.build.lib.analysis.buildinfo.BuildInfoFactory;
 import com.google.devtools.build.lib.analysis.buildinfo.BuildInfoFactory.BuildInfoKey;
+import com.google.devtools.build.lib.concurrent.BlazeInterners;
 import com.google.devtools.build.lib.packages.RuleVisibility;
 import com.google.devtools.build.lib.pkgcache.PathPackageLocator;
 import com.google.devtools.build.lib.skyframe.SkyframeActionExecutor.ConflictException;
 import com.google.devtools.build.lib.skyframe.serialization.autocodec.AutoCodec;
 import com.google.devtools.build.lib.syntax.SkylarkSemantics;
+import com.google.devtools.build.skyframe.AbstractSkyKey;
 import com.google.devtools.build.skyframe.Injectable;
-import com.google.devtools.build.skyframe.LegacySkyKey;
 import com.google.devtools.build.skyframe.SkyFunction;
+import com.google.devtools.build.skyframe.SkyFunctionName;
 import com.google.devtools.build.skyframe.SkyKey;
 import com.google.devtools.build.skyframe.SkyValue;
 import java.util.Map;
@@ -77,31 +80,30 @@ public final class PrecomputedValue implements SkyValue {
   }
 
   public static final Precomputed<String> DEFAULTS_PACKAGE_CONTENTS =
-      new Precomputed<>(LegacySkyKey.create(SkyFunctions.PRECOMPUTED, "default_pkg"));
+      new Precomputed<>(Key.create("default_pkg"));
 
   public static final Precomputed<RuleVisibility> DEFAULT_VISIBILITY =
-      new Precomputed<>(LegacySkyKey.create(SkyFunctions.PRECOMPUTED, "default_visibility"));
+      new Precomputed<>(Key.create("default_visibility"));
 
   public static final Precomputed<SkylarkSemantics> SKYLARK_SEMANTICS =
-      new Precomputed<>(LegacySkyKey.create(SkyFunctions.PRECOMPUTED, "skylark_semantics"));
+      new Precomputed<>(Key.create("skylark_semantics"));
 
-  static final Precomputed<UUID> BUILD_ID =
-      new Precomputed<>(LegacySkyKey.create(SkyFunctions.PRECOMPUTED, "build_id"));
+  static final Precomputed<UUID> BUILD_ID = new Precomputed<>(Key.create("build_id"));
 
   static final Precomputed<Map<String, String>> ACTION_ENV =
-      new Precomputed<>(LegacySkyKey.create(SkyFunctions.PRECOMPUTED, "action_env"));
+      new Precomputed<>(Key.create("action_env"));
 
   static final Precomputed<ImmutableList<ActionAnalysisMetadata>> COVERAGE_REPORT_KEY =
-      new Precomputed<>(LegacySkyKey.create(SkyFunctions.PRECOMPUTED, "coverage_report_actions"));
+      new Precomputed<>(Key.create("coverage_report_actions"));
 
   public static final Precomputed<Map<BuildInfoKey, BuildInfoFactory>> BUILD_INFO_FACTORIES =
-      new Precomputed<>(LegacySkyKey.create(SkyFunctions.PRECOMPUTED, "build_info_factories"));
+      new Precomputed<>(Key.create("build_info_factories"));
 
   static final Precomputed<ImmutableMap<ActionAnalysisMetadata, ConflictException>> BAD_ACTIONS =
-      new Precomputed<>(LegacySkyKey.create(SkyFunctions.PRECOMPUTED, "bad_actions"));
+      new Precomputed<>(Key.create("bad_actions"));
 
   public static final Precomputed<PathPackageLocator> PATH_PACKAGE_LOCATOR =
-      new Precomputed<>(LegacySkyKey.create(SkyFunctions.PRECOMPUTED, "path_package_locator"));
+      new Precomputed<>(Key.create("path_package_locator"));
 
   private final Object value;
 
@@ -146,14 +148,14 @@ public final class PrecomputedValue implements SkyValue {
    * <p>Instances do not have internal state.
    */
   public static final class Precomputed<T> {
-    private final SkyKey key;
+    private final Key key;
 
-    public Precomputed(SkyKey key) {
+    public Precomputed(Key key) {
       this.key = key;
     }
 
     @VisibleForTesting
-    SkyKey getKeyForTesting() {
+    Key getKeyForTesting() {
       return key;
     }
 
@@ -179,4 +181,24 @@ public final class PrecomputedValue implements SkyValue {
       injectable.inject(key, new PrecomputedValue(value));
     }
   }
+
+  /** {@link SkyKey} for {@code PrecomputedValue}. */
+  @AutoCodec
+  public static class Key extends AbstractSkyKey<String> {
+    private static final Interner<Key> interner = BlazeInterners.newWeakInterner();
+
+    private Key(String arg) {
+      super(arg);
+    }
+
+    @AutoCodec.Instantiator
+    public static Key create(String arg) {
+      return interner.intern(new Key(arg));
+    }
+
+    @Override
+    public SkyFunctionName functionName() {
+      return SkyFunctions.PRECOMPUTED;
+    }
+  }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/PrepareDepsOfPatternValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/PrepareDepsOfPatternValue.java
index 23383680be..4a1b83062c 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/PrepareDepsOfPatternValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/PrepareDepsOfPatternValue.java
@@ -14,14 +14,17 @@
 package com.google.devtools.build.lib.skyframe;
 
 import com.google.common.collect.ImmutableList;
+import com.google.common.collect.Interner;
 import com.google.devtools.build.lib.cmdline.TargetParsingException;
 import com.google.devtools.build.lib.cmdline.TargetPattern.Type;
+import com.google.devtools.build.lib.concurrent.BlazeInterners;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe;
 import com.google.devtools.build.lib.pkgcache.FilteringPolicies;
 import com.google.devtools.build.lib.skyframe.TargetPatternValue.TargetPatternKey;
 import com.google.devtools.build.lib.skyframe.TargetPatternValue.TargetPatternSkyKeyOrException;
 import com.google.devtools.build.lib.skyframe.serialization.autocodec.AutoCodec;
-import com.google.devtools.build.skyframe.LegacySkyKey;
+import com.google.devtools.build.skyframe.AbstractSkyKey;
+import com.google.devtools.build.skyframe.SkyFunctionName;
 import com.google.devtools.build.skyframe.SkyKey;
 import com.google.devtools.build.skyframe.SkyValue;
 import java.util.List;
@@ -174,16 +177,36 @@ public class PrepareDepsOfPatternValue implements SkyValue {
 
     private final TargetPatternKey targetPatternKey;
 
-    public PrepareDepsOfPatternSkyKeyValue(TargetPatternKey targetPatternKey) {
+    PrepareDepsOfPatternSkyKeyValue(TargetPatternKey targetPatternKey) {
       this.targetPatternKey = targetPatternKey;
     }
 
-    public SkyKey getSkyKey() {
-      return LegacySkyKey.create(SkyFunctions.PREPARE_DEPS_OF_PATTERN, targetPatternKey);
+    public Key getSkyKey() {
+      return Key.create(targetPatternKey);
     }
 
-    public String getOriginalPattern() {
-      return targetPatternKey.getPattern();
+    @AutoCodec
+    static class Key extends AbstractSkyKey<TargetPatternKey> {
+      private static final Interner<Key> interner = BlazeInterners.newWeakInterner();
+
+      private Key(TargetPatternKey arg) {
+        super(arg);
+      }
+
+      @AutoCodec.VisibleForSerialization
+      @AutoCodec.Instantiator
+      static Key create(TargetPatternKey arg) {
+        return interner.intern(new Key(arg));
+      }
+
+      TargetPatternKey getTargetPatternKey() {
+        return arg;
+      }
+
+      @Override
+      public SkyFunctionName functionName() {
+        return SkyFunctions.PREPARE_DEPS_OF_PATTERN;
+      }
     }
   }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/PrepareDepsOfPatternsValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/PrepareDepsOfPatternsValue.java
index 6c915658f4..037fd7c608 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/PrepareDepsOfPatternsValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/PrepareDepsOfPatternsValue.java
@@ -16,14 +16,15 @@ package com.google.devtools.build.lib.skyframe;
 import com.google.common.base.MoreObjects;
 import com.google.common.base.Preconditions;
 import com.google.common.collect.ImmutableList;
+import com.google.common.collect.Interner;
+import com.google.devtools.build.lib.concurrent.BlazeInterners;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe;
 import com.google.devtools.build.lib.skyframe.TargetPatternValue.TargetPatternKey;
 import com.google.devtools.build.lib.skyframe.serialization.autocodec.AutoCodec;
-import com.google.devtools.build.skyframe.LegacySkyKey;
+import com.google.devtools.build.skyframe.SkyFunctionName;
 import com.google.devtools.build.skyframe.SkyKey;
 import com.google.devtools.build.skyframe.SkyValue;
-import java.io.Serializable;
 import java.util.Objects;
 
 /**
@@ -55,22 +56,32 @@ public final class PrepareDepsOfPatternsValue implements SkyValue {
   }
 
   @ThreadSafe
-  public static SkyKey key(ImmutableList<String> patterns, String offset) {
-    return LegacySkyKey.create(
-        SkyFunctions.PREPARE_DEPS_OF_PATTERNS, new TargetPatternSequence(patterns, offset));
+  public static TargetPatternSequence key(ImmutableList<String> patterns, String offset) {
+    return TargetPatternSequence.create(patterns, offset);
   }
 
   /** The argument value for {@link SkyKey}s of {@link PrepareDepsOfPatternsFunction}. */
   @ThreadSafe
-  public static class TargetPatternSequence implements Serializable {
+  @AutoCodec.VisibleForSerialization
+  @AutoCodec
+  static class TargetPatternSequence implements SkyKey {
+    private static final Interner<TargetPatternSequence> interner =
+        BlazeInterners.newWeakInterner();
+
     private final ImmutableList<String> patterns;
     private final String offset;
 
-    public TargetPatternSequence(ImmutableList<String> patterns, String offset) {
+    private TargetPatternSequence(ImmutableList<String> patterns, String offset) {
       this.patterns = Preconditions.checkNotNull(patterns);
       this.offset = Preconditions.checkNotNull(offset);
     }
 
+    @AutoCodec.VisibleForSerialization
+    @AutoCodec.Instantiator
+    static TargetPatternSequence create(ImmutableList<String> patterns, String offset) {
+      return interner.intern(new TargetPatternSequence(patterns, offset));
+    }
+
     public ImmutableList<String> getPatterns() {
       return patterns;
     }
@@ -103,6 +114,11 @@ public final class PrepareDepsOfPatternsValue implements SkyValue {
           .add("offset", offset)
           .toString();
     }
+
+    @Override
+    public SkyFunctionName functionName() {
+      return SkyFunctions.PREPARE_DEPS_OF_PATTERNS;
+    }
   }
 
   @Override
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/PrepareDepsOfTargetsUnderDirectoryFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/PrepareDepsOfTargetsUnderDirectoryFunction.java
index 05ef591cbf..d52a9640ad 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/PrepareDepsOfTargetsUnderDirectoryFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/PrepareDepsOfTargetsUnderDirectoryFunction.java
@@ -22,7 +22,6 @@ import com.google.devtools.build.lib.cmdline.RepositoryName;
 import com.google.devtools.build.lib.packages.NoSuchPackageException;
 import com.google.devtools.build.lib.pkgcache.FilteringPolicy;
 import com.google.devtools.build.lib.skyframe.PrepareDepsOfTargetsUnderDirectoryValue.PrepareDepsOfTargetsUnderDirectoryKey;
-import com.google.devtools.build.lib.skyframe.RecursivePkgValue.RecursivePkgKey;
 import com.google.devtools.build.lib.vfs.PathFragment;
 import com.google.devtools.build.lib.vfs.RootedPath;
 import com.google.devtools.build.skyframe.SkyFunction;
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/PrepareDepsOfTargetsUnderDirectoryValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/PrepareDepsOfTargetsUnderDirectoryValue.java
index 0dcbe302e5..2bc376ece9 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/PrepareDepsOfTargetsUnderDirectoryValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/PrepareDepsOfTargetsUnderDirectoryValue.java
@@ -13,21 +13,22 @@
 // limitations under the License.
 package com.google.devtools.build.lib.skyframe;
 
+import com.google.common.annotations.VisibleForTesting;
 import com.google.common.base.MoreObjects;
 import com.google.common.base.Preconditions;
 import com.google.common.collect.ImmutableSet;
+import com.google.common.collect.Interner;
 import com.google.devtools.build.lib.cmdline.RepositoryName;
+import com.google.devtools.build.lib.concurrent.BlazeInterners;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe;
 import com.google.devtools.build.lib.pkgcache.FilteringPolicies;
 import com.google.devtools.build.lib.pkgcache.FilteringPolicy;
-import com.google.devtools.build.lib.skyframe.RecursivePkgValue.RecursivePkgKey;
 import com.google.devtools.build.lib.skyframe.serialization.autocodec.AutoCodec;
 import com.google.devtools.build.lib.vfs.PathFragment;
 import com.google.devtools.build.lib.vfs.RootedPath;
-import com.google.devtools.build.skyframe.LegacySkyKey;
+import com.google.devtools.build.skyframe.SkyFunctionName;
 import com.google.devtools.build.skyframe.SkyKey;
 import com.google.devtools.build.skyframe.SkyValue;
-import java.io.Serializable;
 import java.util.Objects;
 
 /**
@@ -61,29 +62,41 @@ public final class PrepareDepsOfTargetsUnderDirectoryValue implements SkyValue {
    * targets.
    */
   @ThreadSafe
-  public static SkyKey key(RepositoryName repository, RootedPath rootedPath,
-      ImmutableSet<PathFragment> excludedPaths, FilteringPolicy filteringPolicy) {
-    return LegacySkyKey.create(
-        SkyFunctions.PREPARE_DEPS_OF_TARGETS_UNDER_DIRECTORY,
-        new PrepareDepsOfTargetsUnderDirectoryKey(
-            new RecursivePkgKey(repository, rootedPath, excludedPaths), filteringPolicy));
+  public static PrepareDepsOfTargetsUnderDirectoryKey key(
+      RepositoryName repository,
+      RootedPath rootedPath,
+      ImmutableSet<PathFragment> excludedPaths,
+      FilteringPolicy filteringPolicy) {
+    return PrepareDepsOfTargetsUnderDirectoryKey.create(
+        new RecursivePkgKey(repository, rootedPath, excludedPaths), filteringPolicy);
   }
 
   /**
    * The argument value for {@link SkyKey}s of {@link PrepareDepsOfTargetsUnderDirectoryFunction}.
    */
+  @VisibleForTesting
   @AutoCodec
-  public static final class PrepareDepsOfTargetsUnderDirectoryKey implements Serializable {
+  public static final class PrepareDepsOfTargetsUnderDirectoryKey implements SkyKey {
+    private static final Interner<PrepareDepsOfTargetsUnderDirectoryKey> interners =
+        BlazeInterners.newWeakInterner();
+
     private final RecursivePkgKey recursivePkgKey;
     private final FilteringPolicy filteringPolicy;
 
-    @AutoCodec.Instantiator
-    public PrepareDepsOfTargetsUnderDirectoryKey(
+    private PrepareDepsOfTargetsUnderDirectoryKey(
         RecursivePkgKey recursivePkgKey, FilteringPolicy filteringPolicy) {
       this.recursivePkgKey = Preconditions.checkNotNull(recursivePkgKey);
       this.filteringPolicy = Preconditions.checkNotNull(filteringPolicy);
     }
 
+    @VisibleForTesting
+    @AutoCodec.Instantiator
+    static PrepareDepsOfTargetsUnderDirectoryKey create(
+        RecursivePkgKey recursivePkgKey, FilteringPolicy filteringPolicy) {
+      return interners.intern(
+          new PrepareDepsOfTargetsUnderDirectoryKey(recursivePkgKey, filteringPolicy));
+    }
+
     public RecursivePkgKey getRecursivePkgKey() {
       return recursivePkgKey;
     }
@@ -93,6 +106,11 @@ public final class PrepareDepsOfTargetsUnderDirectoryValue implements SkyValue {
     }
 
     @Override
+    public SkyFunctionName functionName() {
+      return SkyFunctions.PREPARE_DEPS_OF_TARGETS_UNDER_DIRECTORY;
+    }
+
+    @Override
     public boolean equals(Object o) {
       if (this == o) {
         return true;
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/RecursiveDirectoryTraversalFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/RecursiveDirectoryTraversalFunction.java
index a885befceb..4de261913d 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/RecursiveDirectoryTraversalFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/RecursiveDirectoryTraversalFunction.java
@@ -25,7 +25,6 @@ import com.google.devtools.build.lib.cmdline.RepositoryName;
 import com.google.devtools.build.lib.events.Event;
 import com.google.devtools.build.lib.packages.NoSuchPackageException;
 import com.google.devtools.build.lib.packages.Package;
-import com.google.devtools.build.lib.skyframe.RecursivePkgValue.RecursivePkgKey;
 import com.google.devtools.build.lib.vfs.PathFragment;
 import com.google.devtools.build.lib.vfs.RootedPath;
 import com.google.devtools.build.skyframe.SkyFunction.Environment;
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/RecursiveFilesystemTraversalFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/RecursiveFilesystemTraversalFunction.java
index e46776d94d..2948e4e16d 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/RecursiveFilesystemTraversalFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/RecursiveFilesystemTraversalFunction.java
@@ -177,8 +177,10 @@ public final class RecursiveFilesystemTraversalFunction implements SkyFunction {
 
       // We are free to traverse this directory.
       Collection<SkyKey> dependentKeys = createRecursiveTraversalKeys(env, traversal);
-      return resultForDirectory(traversal, rootInfo,
-          traverseChildren(env, dependentKeys, /*inline=*/traversal.isGenerated));
+      return resultForDirectory(
+          traversal,
+          rootInfo,
+          traverseChildren(env, dependentKeys, /*inline=*/ traversal.isRootGenerated));
     } catch (IOException e) {
       throw new RecursiveFilesystemTraversalFunctionException(
           new FileOperationException("Error while traversing fileset: " + e.getMessage()));
@@ -219,7 +221,7 @@ public final class RecursiveFilesystemTraversalFunction implements SkyFunction {
 
   private static FileInfo lookUpFileInfo(Environment env, TraversalRequest traversal)
       throws MissingDepException, IOException, InterruptedException {
-    if (traversal.isGenerated) {
+    if (traversal.isRootGenerated) {
       byte[] digest = null;
       if (traversal.root.getOutputArtifact() != null) {
         Artifact artifact = traversal.root.getOutputArtifact();
@@ -360,7 +362,7 @@ public final class RecursiveFilesystemTraversalFunction implements SkyFunction {
                 PackageLookupValue.key(traversal.root.asRootedPath().getRootRelativePath()));
 
     if (pkgLookup.packageExists()) {
-      if (traversal.isGenerated) {
+      if (traversal.isRootGenerated) {
         // The traversal's root was a generated directory, but its root-relative path conflicts with
         // an existing package.
         return PkgLookupResult.conflict(traversal, rootInfo);
@@ -394,7 +396,7 @@ public final class RecursiveFilesystemTraversalFunction implements SkyFunction {
     // Use the traversal's path, even if it's a symlink. The contents of the directory, as listed
     // in the result, must be relative to it.
     Iterable<Dirent> dirents;
-    if (traversal.isGenerated) {
+    if (traversal.isRootGenerated) {
       // If we're dealing with an output file, read the directory directly instead of creating
       // filesystem nodes under the output tree.
       List<Dirent> direntsCollection =
@@ -414,7 +416,7 @@ public final class RecursiveFilesystemTraversalFunction implements SkyFunction {
               traversal.root.asRootedPath().getRoot(),
               traversal.root.asRootedPath().getRootRelativePath().getRelative(dirent.getName()));
       TraversalRequest childTraversal = traversal.forChildEntry(childPath);
-      result.add(RecursiveFilesystemTraversalValue.key(childTraversal));
+      result.add(childTraversal);
     }
     return result;
   }
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/RecursiveFilesystemTraversalValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/RecursiveFilesystemTraversalValue.java
index 7a1a269808..8d16da6439 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/RecursiveFilesystemTraversalValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/RecursiveFilesystemTraversalValue.java
@@ -17,17 +17,20 @@ import com.google.common.annotations.VisibleForTesting;
 import com.google.common.base.Objects;
 import com.google.common.base.Optional;
 import com.google.common.base.Preconditions;
+import com.google.common.collect.Interner;
 import com.google.devtools.build.lib.actions.FilesetTraversalParams.DirectTraversalRoot;
 import com.google.devtools.build.lib.actions.FilesetTraversalParams.PackageBoundaryMode;
 import com.google.devtools.build.lib.collect.nestedset.NestedSet;
 import com.google.devtools.build.lib.collect.nestedset.NestedSetBuilder;
 import com.google.devtools.build.lib.collect.nestedset.Order;
+import com.google.devtools.build.lib.concurrent.BlazeInterners;
 import com.google.devtools.build.lib.skyframe.RecursiveFilesystemTraversalFunction.DanglingSymlinkException;
 import com.google.devtools.build.lib.skyframe.RecursiveFilesystemTraversalFunction.FileType;
+import com.google.devtools.build.lib.skyframe.serialization.autocodec.AutoCodec;
 import com.google.devtools.build.lib.vfs.PathFragment;
 import com.google.devtools.build.lib.vfs.Root;
 import com.google.devtools.build.lib.vfs.RootedPath;
-import com.google.devtools.build.skyframe.LegacySkyKey;
+import com.google.devtools.build.skyframe.SkyFunctionName;
 import com.google.devtools.build.skyframe.SkyKey;
 import com.google.devtools.build.skyframe.SkyValue;
 import javax.annotation.Nullable;
@@ -102,12 +105,10 @@ public final class RecursiveFilesystemTraversalValue implements SkyValue {
     return resolvedPaths;
   }
 
-  public static SkyKey key(TraversalRequest traversal) {
-    return LegacySkyKey.create(SkyFunctions.RECURSIVE_FILESYSTEM_TRAVERSAL, traversal);
-  }
-
   /** The parameters of a file or directory traversal. */
-  public static final class TraversalRequest {
+  @AutoCodec
+  public static final class TraversalRequest implements SkyKey {
+    private static final Interner<TraversalRequest> interner = BlazeInterners.newWeakInterner();
 
     /** The path to start the traversal from; may be a file, a directory or a symlink. */
     final DirectTraversalRoot root;
@@ -118,7 +119,7 @@ public final class RecursiveFilesystemTraversalValue implements SkyValue {
      * <p>Such paths and all their subdirectories are assumed not to define packages, so package
      * lookup for them is skipped.
      */
-    final boolean isGenerated;
+    final boolean isRootGenerated;
 
     /** Whether traversal should descend into directories that are roots of subpackages. */
     final PackageBoundaryMode crossPkgBoundaries;
@@ -135,20 +136,36 @@ public final class RecursiveFilesystemTraversalValue implements SkyValue {
     /** Information to be attached to any error messages that may be reported. */
     @Nullable final String errorInfo;
 
-    public TraversalRequest(DirectTraversalRoot root, boolean isRootGenerated,
-        PackageBoundaryMode crossPkgBoundaries, boolean skipTestingForSubpackage,
+    private TraversalRequest(
+        DirectTraversalRoot root,
+        boolean isRootGenerated,
+        PackageBoundaryMode crossPkgBoundaries,
+        boolean skipTestingForSubpackage,
         @Nullable String errorInfo) {
       this.root = root;
-      this.isGenerated = isRootGenerated;
+      this.isRootGenerated = isRootGenerated;
       this.crossPkgBoundaries = crossPkgBoundaries;
       this.skipTestingForSubpackage = skipTestingForSubpackage;
       this.errorInfo = errorInfo;
     }
 
+    @AutoCodec.VisibleForSerialization
+    @AutoCodec.Instantiator
+    static TraversalRequest create(
+        DirectTraversalRoot root,
+        boolean isRootGenerated,
+        PackageBoundaryMode crossPkgBoundaries,
+        boolean skipTestingForSubpackage,
+        @Nullable String errorInfo) {
+      return interner.intern(
+          new TraversalRequest(
+              root, isRootGenerated, crossPkgBoundaries, skipTestingForSubpackage, errorInfo));
+    }
+
     private TraversalRequest duplicate(DirectTraversalRoot newRoot,
         boolean newSkipTestingForSubpackage) {
-      return new TraversalRequest(newRoot, isGenerated, crossPkgBoundaries,
-          newSkipTestingForSubpackage, errorInfo);
+      return create(
+          newRoot, isRootGenerated, crossPkgBoundaries, newSkipTestingForSubpackage, errorInfo);
     }
 
     /** Creates a new request to traverse a child element in the current directory (the root). */
@@ -178,22 +195,28 @@ public final class RecursiveFilesystemTraversalValue implements SkyValue {
         return false;
       }
       TraversalRequest o = (TraversalRequest) obj;
-      return root.equals(o.root) && isGenerated == o.isGenerated
+      return root.equals(o.root)
+          && isRootGenerated == o.isRootGenerated
           && crossPkgBoundaries == o.crossPkgBoundaries
           && skipTestingForSubpackage == o.skipTestingForSubpackage;
     }
 
     @Override
     public int hashCode() {
-      return Objects.hashCode(root, isGenerated, crossPkgBoundaries, skipTestingForSubpackage);
+      return Objects.hashCode(root, isRootGenerated, crossPkgBoundaries, skipTestingForSubpackage);
     }
 
     @Override
     public String toString() {
       return String.format(
           "TraversalParams(root=%s, is_generated=%d, skip_testing_for_subpkg=%d,"
-          + " pkg_boundaries=%s)", root, isGenerated ? 1 : 0,
-          skipTestingForSubpackage ? 1 : 0, crossPkgBoundaries);
+              + " pkg_boundaries=%s)",
+          root, isRootGenerated ? 1 : 0, skipTestingForSubpackage ? 1 : 0, crossPkgBoundaries);
+    }
+
+    @Override
+    public SkyFunctionName functionName() {
+      return SkyFunctions.RECURSIVE_FILESYSTEM_TRAVERSAL;
     }
   }
 
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/RecursivePkgFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/RecursivePkgFunction.java
index 8430c286a5..64c27dc97d 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/RecursivePkgFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/RecursivePkgFunction.java
@@ -20,7 +20,6 @@ import com.google.devtools.build.lib.collect.nestedset.NestedSet;
 import com.google.devtools.build.lib.collect.nestedset.NestedSetBuilder;
 import com.google.devtools.build.lib.collect.nestedset.Order;
 import com.google.devtools.build.lib.packages.NoSuchPackageException;
-import com.google.devtools.build.lib.skyframe.RecursivePkgValue.RecursivePkgKey;
 import com.google.devtools.build.lib.vfs.PathFragment;
 import com.google.devtools.build.lib.vfs.RootedPath;
 import com.google.devtools.build.skyframe.SkyFunction;
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/RecursivePkgKey.java b/src/main/java/com/google/devtools/build/lib/skyframe/RecursivePkgKey.java
new file mode 100644
index 0000000000..9a5a12f1b3
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/RecursivePkgKey.java
@@ -0,0 +1,89 @@
+// Copyright 2018 The Bazel Authors. All rights reserved.
+//
+// Licensed 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 com.google.devtools.build.lib.skyframe;
+
+import com.google.common.base.Preconditions;
+import com.google.common.collect.ImmutableSet;
+import com.google.devtools.build.lib.cmdline.RepositoryName;
+import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe;
+import com.google.devtools.build.lib.skyframe.serialization.autocodec.AutoCodec;
+import com.google.devtools.build.lib.vfs.PathFragment;
+import com.google.devtools.build.lib.vfs.RootedPath;
+import java.util.Objects;
+
+/**
+ * A RecursivePkgKey is a tuple of a {@link RootedPath}, {@code rootedPath}, defining the directory
+ * to recurse beneath in search of packages, and an {@link ImmutableSet} of {@link PathFragment}s,
+ * {@code excludedPaths}, relative to {@code rootedPath.getRoot}, defining the set of subdirectories
+ * strictly beneath {@code rootedPath} to skip.
+ *
+ * <p>Throws {@link IllegalArgumentException} if {@code excludedPaths} contains any paths that are
+ * equal to {@code rootedPath} or that are not beneath {@code rootedPath}.
+ */
+@ThreadSafe
+@AutoCodec
+public class RecursivePkgKey {
+  private final RepositoryName repositoryName;
+  private final RootedPath rootedPath;
+  private final ImmutableSet<PathFragment> excludedPaths;
+
+  public RecursivePkgKey(
+      RepositoryName repositoryName,
+      RootedPath rootedPath,
+      ImmutableSet<PathFragment> excludedPaths) {
+    PathFragment.checkAllPathsAreUnder(excludedPaths, rootedPath.getRootRelativePath());
+    Preconditions.checkState(!repositoryName.isDefault());
+    this.repositoryName = repositoryName;
+    this.rootedPath = Preconditions.checkNotNull(rootedPath);
+    this.excludedPaths = Preconditions.checkNotNull(excludedPaths);
+  }
+
+  public RepositoryName getRepository() {
+    return repositoryName;
+  }
+
+  public RootedPath getRootedPath() {
+    return rootedPath;
+  }
+
+  public ImmutableSet<PathFragment> getExcludedPaths() {
+    return excludedPaths;
+  }
+
+  @Override
+  public String toString() {
+    return "rootedPath=" + rootedPath + ", excludedPaths=<omitted>";
+  }
+
+  @Override
+  public boolean equals(Object o) {
+    if (this == o) {
+      return true;
+    }
+    if (!(o instanceof RecursivePkgKey)) {
+      return false;
+    }
+
+    RecursivePkgKey that = (RecursivePkgKey) o;
+    return excludedPaths.equals(that.excludedPaths)
+        && rootedPath.equals(that.rootedPath)
+        && repositoryName.equals(that.repositoryName);
+  }
+
+  @Override
+  public int hashCode() {
+    return Objects.hash(rootedPath, excludedPaths, repositoryName);
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/RecursivePkgSkyKey.java b/src/main/java/com/google/devtools/build/lib/skyframe/RecursivePkgSkyKey.java
new file mode 100644
index 0000000000..c83825f46d
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/RecursivePkgSkyKey.java
@@ -0,0 +1,49 @@
+// Copyright 2018 The Bazel Authors. All rights reserved.
+//
+// Licensed 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 com.google.devtools.build.lib.skyframe;
+
+import com.google.common.collect.ImmutableSet;
+import com.google.devtools.build.lib.cmdline.RepositoryName;
+import com.google.devtools.build.lib.vfs.PathFragment;
+import com.google.devtools.build.lib.vfs.RootedPath;
+import com.google.devtools.build.skyframe.SkyKey;
+
+/** Common parent class of SkyKeys that wrap a {@link RecursivePkgKey}. */
+abstract class RecursivePkgSkyKey extends RecursivePkgKey implements SkyKey {
+  RecursivePkgSkyKey(
+      RepositoryName repositoryName,
+      RootedPath rootedPath,
+      ImmutableSet<PathFragment> excludedPaths) {
+    super(repositoryName, rootedPath, excludedPaths);
+  }
+
+  @Override
+  public String toString() {
+    return functionName() + " " + super.toString();
+  }
+
+  @Override
+  public boolean equals(Object o) {
+    return super.equals(o)
+        && ((o instanceof RecursivePkgSkyKey))
+        && ((RecursivePkgSkyKey) o).functionName().equals(functionName());
+  }
+
+  /** Don't bother to memoize hashCode because {@link RecursivePkgKey#hashCode} is cheap enough. */
+  @Override
+  public int hashCode() {
+    return 37 * super.hashCode() + functionName().hashCode();
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/RecursivePkgValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/RecursivePkgValue.java
index 7397a7a918..d864c024d3 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/RecursivePkgValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/RecursivePkgValue.java
@@ -13,22 +13,20 @@
 // limitations under the License.
 package com.google.devtools.build.lib.skyframe;
 
-import com.google.common.base.Preconditions;
 import com.google.common.collect.ImmutableSet;
+import com.google.common.collect.Interner;
 import com.google.devtools.build.lib.cmdline.RepositoryName;
 import com.google.devtools.build.lib.collect.nestedset.NestedSet;
 import com.google.devtools.build.lib.collect.nestedset.NestedSetBuilder;
 import com.google.devtools.build.lib.collect.nestedset.Order;
+import com.google.devtools.build.lib.concurrent.BlazeInterners;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe;
 import com.google.devtools.build.lib.skyframe.serialization.autocodec.AutoCodec;
 import com.google.devtools.build.lib.vfs.PathFragment;
 import com.google.devtools.build.lib.vfs.RootedPath;
-import com.google.devtools.build.skyframe.LegacySkyKey;
-import com.google.devtools.build.skyframe.SkyKey;
+import com.google.devtools.build.skyframe.SkyFunctionName;
 import com.google.devtools.build.skyframe.SkyValue;
-import java.io.Serializable;
-import java.util.Objects;
 
 /**
  * This value represents the result of looking up all the packages under a given package path root,
@@ -54,81 +52,43 @@ public class RecursivePkgValue implements SkyValue {
     return new RecursivePkgValue(packages.build());
   }
 
-  /**
-   * Create a transitive package lookup request.
-   */
+  /** Create a transitive package lookup request. */
   @ThreadSafe
-  public static SkyKey key(RepositoryName repositoryName, RootedPath rootedPath,
+  public static Key key(
+      RepositoryName repositoryName,
+      RootedPath rootedPath,
       ImmutableSet<PathFragment> excludedPaths) {
-    return LegacySkyKey.create(
-        SkyFunctions.RECURSIVE_PKG, new RecursivePkgKey(repositoryName, rootedPath, excludedPaths));
+    return Key.create(repositoryName, rootedPath, excludedPaths);
   }
 
   public NestedSet<String> getPackages() {
     return packages;
   }
 
-  /**
-   * A RecursivePkgKey is a tuple of a {@link RootedPath}, {@code rootedPath}, defining the
-   * directory to recurse beneath in search of packages, and an {@link ImmutableSet} of {@link
-   * PathFragment}s, {@code excludedPaths}, relative to {@code rootedPath.getRoot}, defining the set
-   * of subdirectories strictly beneath {@code rootedPath} to skip.
-   *
-   * <p>Throws {@link IllegalArgumentException} if {@code excludedPaths} contains any paths that are
-   * equal to {@code rootedPath} or that are not beneath {@code rootedPath}.
-   */
+  @AutoCodec.VisibleForSerialization
   @AutoCodec
-  @ThreadSafe
-  public static final class RecursivePkgKey implements Serializable {
-    private final RepositoryName repositoryName;
-    private final RootedPath rootedPath;
-    private final ImmutableSet<PathFragment> excludedPaths;
+  static class Key extends RecursivePkgSkyKey {
+    private static final Interner<Key> interner = BlazeInterners.newWeakInterner();
 
-    @AutoCodec.Instantiator
-    public RecursivePkgKey(
+    private Key(
         RepositoryName repositoryName,
         RootedPath rootedPath,
         ImmutableSet<PathFragment> excludedPaths) {
-      PathFragment.checkAllPathsAreUnder(excludedPaths, rootedPath.getRootRelativePath());
-      Preconditions.checkState(!repositoryName.isDefault());
-      this.repositoryName = repositoryName;
-      this.rootedPath = Preconditions.checkNotNull(rootedPath);
-      this.excludedPaths = Preconditions.checkNotNull(excludedPaths);
+      super(repositoryName, rootedPath, excludedPaths);
     }
 
-    public RepositoryName getRepository() {
-      return repositoryName;
-    }
-
-    public RootedPath getRootedPath() {
-      return rootedPath;
-    }
-
-    public ImmutableSet<PathFragment> getExcludedPaths() {
-      return excludedPaths;
-    }
-
-    @Override
-    public String toString() {
-      return "rootedPath=" + rootedPath + ", excludedPaths=<omitted>";
-    }
-
-    @Override
-    public boolean equals(Object o) {
-      if (this == o) {
-        return true;
-      }
-      if (!(o instanceof RecursivePkgKey)) {
-        return false;
-      }
-
-      RecursivePkgKey that = (RecursivePkgKey) o;
-      return excludedPaths.equals(that.excludedPaths) && rootedPath.equals(that.rootedPath);
+    @AutoCodec.VisibleForSerialization
+    @AutoCodec.Instantiator
+    static Key create(
+        RepositoryName repositoryName,
+        RootedPath rootedPath,
+        ImmutableSet<PathFragment> excludedPaths) {
+      return interner.intern(new Key(repositoryName, rootedPath, excludedPaths));
     }
 
     @Override
-    public int hashCode() {
-      return Objects.hash(rootedPath, excludedPaths);
+    public SkyFunctionName functionName() {
+      return SkyFunctions.RECURSIVE_PKG;
     }
   }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/RepositoryValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/RepositoryValue.java
index a09d839654..ef4cebc9ae 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/RepositoryValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/RepositoryValue.java
@@ -16,11 +16,14 @@ package com.google.devtools.build.lib.skyframe;
 
 import com.google.common.base.Objects;
 import com.google.common.base.Preconditions;
+import com.google.common.collect.Interner;
 import com.google.devtools.build.lib.cmdline.RepositoryName;
+import com.google.devtools.build.lib.concurrent.BlazeInterners;
 import com.google.devtools.build.lib.rules.repository.RepositoryDirectoryValue;
+import com.google.devtools.build.lib.skyframe.serialization.autocodec.AutoCodec;
 import com.google.devtools.build.lib.vfs.Path;
-import com.google.devtools.build.skyframe.LegacySkyKey;
-import com.google.devtools.build.skyframe.SkyKey;
+import com.google.devtools.build.skyframe.AbstractSkyKey;
+import com.google.devtools.build.skyframe.SkyFunctionName;
 import com.google.devtools.build.skyframe.SkyValue;
 
 /** A repository's name and directory. */
@@ -121,7 +124,28 @@ public abstract class RepositoryValue implements SkyValue {
     return new NoRepositoryValue(repositoryName);
   }
 
-  public static SkyKey key(RepositoryName repositoryName) {
-    return LegacySkyKey.create(SkyFunctions.REPOSITORY, repositoryName);
+  public static Key key(RepositoryName repositoryName) {
+    return Key.create(repositoryName);
+  }
+
+  @AutoCodec.VisibleForSerialization
+  @AutoCodec
+  static class Key extends AbstractSkyKey<RepositoryName> {
+    private static final Interner<Key> interner = BlazeInterners.newWeakInterner();
+
+    private Key(RepositoryName arg) {
+      super(arg);
+    }
+
+    @AutoCodec.VisibleForSerialization
+    @AutoCodec.Instantiator
+    static Key create(RepositoryName arg) {
+      return interner.intern(new Key(arg));
+    }
+
+    @Override
+    public SkyFunctionName functionName() {
+      return SkyFunctions.REPOSITORY;
+    }
   }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/SequencedSkyframeExecutor.java b/src/main/java/com/google/devtools/build/lib/skyframe/SequencedSkyframeExecutor.java
index ab98da4641..61f9eb5be2 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/SequencedSkyframeExecutor.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/SequencedSkyframeExecutor.java
@@ -91,7 +91,6 @@ import com.google.devtools.build.skyframe.BuildDriver;
 import com.google.devtools.build.skyframe.Differencer;
 import com.google.devtools.build.skyframe.InMemoryMemoizingEvaluator;
 import com.google.devtools.build.skyframe.Injectable;
-import com.google.devtools.build.skyframe.LegacySkyKey;
 import com.google.devtools.build.skyframe.MemoizingEvaluator.EvaluatorSupplier;
 import com.google.devtools.build.skyframe.NodeEntry;
 import com.google.devtools.build.skyframe.RecordingDifferencer;
@@ -364,7 +363,7 @@ public final class SequencedSkyframeExecutor extends SkyframeExecutor {
     envToCheck.addAll(clientEnv.get().keySet());
     previousClientEnvironment = clientEnv.get().keySet();
     for (String env : envToCheck) {
-      SkyKey key = LegacySkyKey.create(SkyFunctions.CLIENT_ENVIRONMENT_VARIABLE, env);
+      SkyKey key = ClientEnvironmentFunction.key(env);
       if (values.containsKey(key)) {
         String value = ((ClientEnvironmentValue) values.get(key)).getValue();
         String newValue = clientEnv.get().get(env);
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/SkylarkImportLookupValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/SkylarkImportLookupValue.java
index f861ba78a6..878f1eba55 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/SkylarkImportLookupValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/SkylarkImportLookupValue.java
@@ -14,13 +14,15 @@
 package com.google.devtools.build.lib.skyframe;
 
 import com.google.common.base.Preconditions;
+import com.google.common.collect.Interner;
 import com.google.devtools.build.lib.cmdline.Label;
+import com.google.devtools.build.lib.concurrent.BlazeInterners;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
+import com.google.devtools.build.lib.skyframe.serialization.autocodec.AutoCodec;
 import com.google.devtools.build.lib.syntax.Environment.Extension;
-import com.google.devtools.build.skyframe.LegacySkyKey;
+import com.google.devtools.build.skyframe.SkyFunctionName;
 import com.google.devtools.build.skyframe.SkyKey;
 import com.google.devtools.build.skyframe.SkyValue;
-import java.io.Serializable;
 import java.util.Objects;
 
 /**
@@ -63,17 +65,33 @@ public class SkylarkImportLookupValue implements SkyValue {
    * loaded from the WORKSPACE file or from a BUILD file.
    */
   @Immutable
-  public static final class SkylarkImportLookupKey implements Serializable {
+  @AutoCodec.VisibleForSerialization
+  @AutoCodec
+  static final class SkylarkImportLookupKey implements SkyKey {
+    private static final Interner<SkylarkImportLookupKey> interner =
+        BlazeInterners.newWeakInterner();
+
     public final Label importLabel;
     public final boolean inWorkspace;
 
-    public SkylarkImportLookupKey(Label importLabel, boolean inWorkspace) {
+    private SkylarkImportLookupKey(Label importLabel, boolean inWorkspace) {
       Preconditions.checkNotNull(importLabel);
       Preconditions.checkArgument(!importLabel.getPackageIdentifier().getRepository().isDefault());
       this.importLabel = importLabel;
       this.inWorkspace = inWorkspace;
     }
 
+    @AutoCodec.VisibleForSerialization
+    @AutoCodec.Instantiator
+    static SkylarkImportLookupKey create(Label importLabel, boolean inWorkspace) {
+      return interner.intern(new SkylarkImportLookupKey(importLabel, inWorkspace));
+    }
+
+    @Override
+    public SkyFunctionName functionName() {
+      return SkyFunctions.SKYLARK_IMPORTS_LOOKUP;
+    }
+
     @Override
     public String toString() {
       return importLabel + (inWorkspace ? " (in workspace)" : "");
@@ -99,8 +117,7 @@ public class SkylarkImportLookupValue implements SkyValue {
   }
 
   static SkyKey key(Label importLabel, boolean inWorkspace) {
-    return LegacySkyKey.create(
-        SkyFunctions.SKYLARK_IMPORTS_LOOKUP, new SkylarkImportLookupKey(importLabel, inWorkspace));
+    return SkylarkImportLookupKey.create(importLabel, inWorkspace);
   }
 
   @Override
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/TargetMarkerValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/TargetMarkerValue.java
index 7af9887252..caf37202c3 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/TargetMarkerValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/TargetMarkerValue.java
@@ -14,12 +14,14 @@
 package com.google.devtools.build.lib.skyframe;
 
 import com.google.common.base.Preconditions;
+import com.google.common.collect.Interner;
 import com.google.devtools.build.lib.cmdline.Label;
+import com.google.devtools.build.lib.concurrent.BlazeInterners;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe;
 import com.google.devtools.build.lib.skyframe.serialization.autocodec.AutoCodec;
-import com.google.devtools.build.skyframe.LegacySkyKey;
-import com.google.devtools.build.skyframe.SkyKey;
+import com.google.devtools.build.skyframe.AbstractSkyKey;
+import com.google.devtools.build.skyframe.SkyFunctionName;
 import com.google.devtools.build.skyframe.SkyValue;
 
 /**
@@ -47,8 +49,29 @@ public final class TargetMarkerValue implements SkyValue {
   }
 
   @ThreadSafe
-  public static SkyKey key(Label label) {
+  public static Key key(Label label) {
     Preconditions.checkArgument(!label.getPackageIdentifier().getRepository().isDefault());
-    return LegacySkyKey.create(SkyFunctions.TARGET_MARKER, label);
+    return Key.create(label);
+  }
+
+  @AutoCodec.VisibleForSerialization
+  @AutoCodec
+  static class Key extends AbstractSkyKey<Label> {
+    private static final Interner<Key> interner = BlazeInterners.newWeakInterner();
+
+    private Key(Label arg) {
+      super(arg);
+    }
+
+    @AutoCodec.VisibleForSerialization
+    @AutoCodec.Instantiator
+    static Key create(Label arg) {
+      return interner.intern(new Key(arg));
+    }
+
+    @Override
+    public SkyFunctionName functionName() {
+      return SkyFunctions.TARGET_MARKER;
+    }
   }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/TargetPatternErrorFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/TargetPatternErrorFunction.java
index cf21520c85..e03d732524 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/TargetPatternErrorFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/TargetPatternErrorFunction.java
@@ -13,11 +13,15 @@
 // limitations under the License.
 package com.google.devtools.build.lib.skyframe;
 
+import com.google.common.collect.Interner;
 import com.google.devtools.build.lib.cmdline.TargetParsingException;
-import com.google.devtools.build.skyframe.LegacySkyKey;
+import com.google.devtools.build.lib.concurrent.BlazeInterners;
+import com.google.devtools.build.lib.skyframe.serialization.autocodec.AutoCodec;
+import com.google.devtools.build.skyframe.AbstractSkyKey;
 import com.google.devtools.build.skyframe.SkyFunction;
 import com.google.devtools.build.skyframe.SkyFunctionException;
 import com.google.devtools.build.skyframe.SkyFunctionException.Transience;
+import com.google.devtools.build.skyframe.SkyFunctionName;
 import com.google.devtools.build.skyframe.SkyKey;
 import com.google.devtools.build.skyframe.SkyValue;
 import javax.annotation.Nullable;
@@ -33,8 +37,29 @@ import javax.annotation.Nullable;
 public class TargetPatternErrorFunction implements SkyFunction {
   // We pass in the error message, which isn't ideal. We could consider reparsing the original
   // pattern instead, but that requires more information.
-  public static SkyKey key(String errorMessage) {
-    return LegacySkyKey.create(SkyFunctions.TARGET_PATTERN_ERROR, errorMessage);
+  public static Key key(String errorMessage) {
+    return Key.create(errorMessage);
+  }
+
+  @AutoCodec.VisibleForSerialization
+  @AutoCodec
+  static class Key extends AbstractSkyKey<String> {
+    private static final Interner<Key> interner = BlazeInterners.newWeakInterner();
+
+    private Key(String arg) {
+      super(arg);
+    }
+
+    @AutoCodec.VisibleForSerialization
+    @AutoCodec.Instantiator
+    static Key create(String arg) {
+      return interner.intern(new Key(arg));
+    }
+
+    @Override
+    public SkyFunctionName functionName() {
+      return SkyFunctions.TARGET_PATTERN_ERROR;
+    }
   }
 
   @Nullable
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/TestCompletionValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/TestCompletionValue.java
index b435720123..20a4dc9e3e 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/TestCompletionValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/TestCompletionValue.java
@@ -14,11 +14,13 @@
 package com.google.devtools.build.lib.skyframe;
 
 import com.google.auto.value.AutoValue;
-import com.google.common.base.Function;
+import com.google.common.collect.Interner;
 import com.google.common.collect.Iterables;
 import com.google.devtools.build.lib.analysis.ConfiguredTarget;
 import com.google.devtools.build.lib.analysis.TopLevelArtifactContext;
-import com.google.devtools.build.skyframe.LegacySkyKey;
+import com.google.devtools.build.lib.concurrent.BlazeInterners;
+import com.google.devtools.build.lib.skyframe.serialization.autocodec.AutoCodec;
+import com.google.devtools.build.skyframe.SkyFunctionName;
 import com.google.devtools.build.skyframe.SkyKey;
 import com.google.devtools.build.skyframe.SkyValue;
 import java.util.Collection;
@@ -36,9 +38,7 @@ public class TestCompletionValue implements SkyValue {
       ConfiguredTargetKey lac,
       final TopLevelArtifactContext topLevelArtifactContext,
       final boolean exclusiveTesting) {
-    return LegacySkyKey.create(
-        SkyFunctions.TEST_COMPLETION,
-        TestCompletionKey.create(lac, topLevelArtifactContext, exclusiveTesting));
+    return TestCompletionKey.create(lac, topLevelArtifactContext, exclusiveTesting);
   }
 
   public static Iterable<SkyKey> keys(Collection<ConfiguredTarget> targets,
@@ -46,31 +46,35 @@ public class TestCompletionValue implements SkyValue {
                                       final boolean exclusiveTesting) {
     return Iterables.transform(
         targets,
-        new Function<ConfiguredTarget, SkyKey>() {
-          @Override
-          public SkyKey apply(ConfiguredTarget ct) {
-            return LegacySkyKey.create(
-                SkyFunctions.TEST_COMPLETION,
-                TestCompletionKey.create(
-                    ConfiguredTargetKey.of(ct), topLevelArtifactContext, exclusiveTesting));
-          }
-        });
+        ct ->
+            TestCompletionKey.create(
+                ConfiguredTargetKey.of(ct), topLevelArtifactContext, exclusiveTesting));
   }
 
+  @AutoCodec
   @AutoValue
-  abstract static class TestCompletionKey {
+  abstract static class TestCompletionKey implements SkyKey {
+    private static final Interner<TestCompletionKey> interner = BlazeInterners.newWeakInterner();
 
-    public static TestCompletionKey create(
+    @AutoCodec.VisibleForSerialization
+    @AutoCodec.Instantiator
+    static TestCompletionKey create(
         ConfiguredTargetKey configuredTargetKey,
         TopLevelArtifactContext topLevelArtifactContext,
         boolean exclusiveTesting) {
-      return new AutoValue_TestCompletionValue_TestCompletionKey(
-          configuredTargetKey, topLevelArtifactContext, exclusiveTesting);
+      return interner.intern(
+          new AutoValue_TestCompletionValue_TestCompletionKey(
+              configuredTargetKey, topLevelArtifactContext, exclusiveTesting));
     }
 
     abstract ConfiguredTargetKey configuredTargetKey();
 
     public abstract TopLevelArtifactContext topLevelArtifactContext();
     public abstract boolean exclusiveTesting();
+
+    @Override
+    public SkyFunctionName functionName() {
+      return SkyFunctions.TEST_COMPLETION;
+    }
   }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/WorkspaceASTValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/WorkspaceASTValue.java
index 9c18193f1f..7011784f7d 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/WorkspaceASTValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/WorkspaceASTValue.java
@@ -15,10 +15,13 @@ package com.google.devtools.build.lib.skyframe;
 
 import com.google.common.base.Preconditions;
 import com.google.common.collect.ImmutableList;
+import com.google.common.collect.Interner;
+import com.google.devtools.build.lib.concurrent.BlazeInterners;
+import com.google.devtools.build.lib.skyframe.serialization.autocodec.AutoCodec;
 import com.google.devtools.build.lib.syntax.BuildFileAST;
 import com.google.devtools.build.lib.vfs.RootedPath;
-import com.google.devtools.build.skyframe.LegacySkyKey;
-import com.google.devtools.build.skyframe.SkyKey;
+import com.google.devtools.build.skyframe.AbstractSkyKey;
+import com.google.devtools.build.skyframe.SkyFunctionName;
 import com.google.devtools.build.skyframe.SkyValue;
 import java.util.List;
 
@@ -56,8 +59,28 @@ public class WorkspaceASTValue implements SkyValue {
     return asts;
   }
 
-  public static SkyKey key(RootedPath path) {
-    return LegacySkyKey.create(SkyFunctions.WORKSPACE_AST, path);
+  public static Key key(RootedPath path) {
+    return Key.create(path);
   }
-}
 
+  @AutoCodec.VisibleForSerialization
+  @AutoCodec
+  static class Key extends AbstractSkyKey<RootedPath> {
+    private static final Interner<Key> interner = BlazeInterners.newWeakInterner();
+
+    private Key(RootedPath arg) {
+      super(arg);
+    }
+
+    @AutoCodec.VisibleForSerialization
+    @AutoCodec.Instantiator
+    static Key create(RootedPath arg) {
+      return interner.intern(new Key(arg));
+    }
+
+    @Override
+    public SkyFunctionName functionName() {
+      return SkyFunctions.WORKSPACE_AST;
+    }
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/WorkspaceFileValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/WorkspaceFileValue.java
index c74fe4a141..83d909deca 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/WorkspaceFileValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/WorkspaceFileValue.java
@@ -16,12 +16,15 @@ package com.google.devtools.build.lib.skyframe;
 
 import com.google.common.base.Preconditions;
 import com.google.common.collect.ImmutableMap;
+import com.google.common.collect.Interner;
+import com.google.devtools.build.lib.concurrent.BlazeInterners;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
 import com.google.devtools.build.lib.packages.BuildFileContainsErrorsException;
 import com.google.devtools.build.lib.packages.Package;
+import com.google.devtools.build.lib.skyframe.serialization.autocodec.AutoCodec;
 import com.google.devtools.build.lib.syntax.Environment.Extension;
 import com.google.devtools.build.lib.vfs.RootedPath;
-import com.google.devtools.build.skyframe.LegacySkyKey;
+import com.google.devtools.build.skyframe.SkyFunctionName;
 import com.google.devtools.build.skyframe.SkyKey;
 import com.google.devtools.build.skyframe.SkyValue;
 import java.util.Map;
@@ -34,24 +37,26 @@ import java.util.Objects;
  */
 public class WorkspaceFileValue implements SkyValue {
 
-  /**
-   * Argument for the SkyKey to request a WorkspaceFileValue.
-   */
+  /** Argument for the SkyKey to request a WorkspaceFileValue. */
   @Immutable
-  public static class WorkspaceFileKey {
+  @AutoCodec
+  public static class WorkspaceFileKey implements SkyKey {
+    private static final Interner<WorkspaceFileKey> interner = BlazeInterners.newWeakInterner();
+
     private final RootedPath path;
     private final int idx;
 
-    /**
-     * Creates a Key for the WorkspaceFileFunction. The path to the workspace file is specified
-     * by {@code path}. This key will ask WorkspaceFileFunction to get the {@code idx+1}-th part of
-     * the workspace file (so idx = 0 represents the first part, idx = 1, the second part, etc...).
-     */
-    public WorkspaceFileKey(RootedPath path, int idx) {
+    private WorkspaceFileKey(RootedPath path, int idx) {
       this.path = path;
       this.idx = idx;
     }
 
+    @AutoCodec.VisibleForSerialization
+    @AutoCodec.Instantiator
+    static WorkspaceFileKey create(RootedPath path, int idx) {
+      return interner.intern(new WorkspaceFileKey(path, idx));
+    }
+
     public RootedPath getPath() {
       return path;
     }
@@ -61,6 +66,11 @@ public class WorkspaceFileValue implements SkyValue {
     }
 
     @Override
+    public SkyFunctionName functionName() {
+      return SkyFunctions.WORKSPACE_FILE;
+    }
+
+    @Override
     public boolean equals(Object obj) {
       if (this == obj) {
         return true;
@@ -134,8 +144,13 @@ public class WorkspaceFileValue implements SkyValue {
     return "<WorkspaceFileValue path=" + path + " idx=" + idx + ">";
   }
 
-  static SkyKey key(RootedPath path, int idx) {
-    return LegacySkyKey.create(SkyFunctions.WORKSPACE_FILE, new WorkspaceFileKey(path, idx));
+  /**
+   * Creates a Key for the WorkspaceFileFunction. The path to the workspace file is specified by
+   * {@code path}. This key will ask WorkspaceFileFunction to get the {@code idx+1}-th part of the
+   * workspace file (so idx = 0 represents the first part, idx = 1, the second part, etc...).
+   */
+  static WorkspaceFileKey key(RootedPath path, int idx) {
+    return WorkspaceFileKey.create(path, idx);
   }
 
   public static SkyKey key(RootedPath path) {
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/WorkspaceNameValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/WorkspaceNameValue.java
index ea0bd94b3a..b16246458b 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/WorkspaceNameValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/WorkspaceNameValue.java
@@ -15,7 +15,6 @@ package com.google.devtools.build.lib.skyframe;
 
 import com.google.common.base.Preconditions;
 import com.google.devtools.build.lib.skyframe.serialization.autocodec.AutoCodec;
-import com.google.devtools.build.skyframe.LegacySkyKey;
 import com.google.devtools.build.skyframe.SkyKey;
 import com.google.devtools.build.skyframe.SkyValue;
 import java.util.Objects;
@@ -29,8 +28,8 @@ import java.util.Objects;
  * the WORKSPACE file.
  */
 public class WorkspaceNameValue implements SkyValue {
-  private static final SkyKey KEY =
-      LegacySkyKey.create(SkyFunctions.WORKSPACE_NAME, DummyArgument.INSTANCE);
+  @AutoCodec @AutoCodec.VisibleForSerialization
+  static final SkyKey KEY = () -> SkyFunctions.WORKSPACE_NAME;
 
   private final String workspaceName;
 
@@ -73,28 +72,4 @@ public class WorkspaceNameValue implements SkyValue {
   public String toString() {
     return String.format("WorkspaceNameValue[name=%s]", workspaceName);
   }
-
-  /** Singleton class used as the {@link SkyKey#argument} for {@link WorkspaceNameValue#key}. */
-  public static final class DummyArgument {
-    static final int HASHCODE = DummyArgument.class.getCanonicalName().hashCode();
-    @AutoCodec public static final DummyArgument INSTANCE = new DummyArgument();
-
-    private DummyArgument() {
-    }
-
-    @Override
-    public boolean equals(Object obj) {
-      return obj instanceof DummyArgument;
-    }
-
-    @Override
-    public int hashCode() {
-      return HASHCODE;
-    }
-
-    @Override
-    public String toString() {
-      return "#";
-    }
-  }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/CodecScanner.java b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/CodecScanner.java
index 1b387134a5..1a44467ba6 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/serialization/CodecScanner.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/serialization/CodecScanner.java
@@ -96,7 +96,8 @@ public class CodecScanner {
                     e);
               }
               try {
-                builder.addConstant(field.get(null));
+                builder.addConstant(
+                    Preconditions.checkNotNull(field.get(null), "%s %s", field, type));
               } catch (IllegalAccessException e) {
                 throw new IllegalStateException(
                     "Could not access field " + field + " for " + type, e);
diff --git a/src/main/java/com/google/devtools/build/skyframe/AbstractSkyKey.java b/src/main/java/com/google/devtools/build/skyframe/AbstractSkyKey.java
new file mode 100644
index 0000000000..7c7fe27029
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/skyframe/AbstractSkyKey.java
@@ -0,0 +1,88 @@
+// Copyright 2018 The Bazel Authors. All rights reserved.
+//
+// Licensed 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 com.google.devtools.build.skyframe;
+
+import com.google.common.base.Preconditions;
+
+/**
+ * For use when the {@link #argument} of the {@link SkyKey} cannot be a {@link SkyKey} itself,
+ * either because it is a type like List or because it is already a different {@link SkyKey}.
+ * Provides convenient boilerplate.
+ */
+public abstract class AbstractSkyKey<T> implements SkyKey {
+  // Visible for serialization.
+  protected final T arg;
+  /**
+   * Cache the hash code for this object. It might be expensive to compute. It is transient because
+   * argument's hash code might not be stable across JVM instances.
+   */
+  private transient int hashCode;
+
+  protected AbstractSkyKey(T arg) {
+    this.arg = Preconditions.checkNotNull(arg);
+  }
+
+  @Override
+  public final int hashCode() {
+    // We use the hash code caching strategy employed by java.lang.String. There are three subtle
+    // things going on here:
+    //
+    // (1) We use a value of 0 to indicate that the hash code hasn't been computed and cached yet.
+    // Yes, this means that if the hash code is really 0 then we will "recompute" it each time. But
+    // this isn't a problem in practice since a hash code of 0 should be rare.
+    //
+    // (2) Since we have no synchronization, multiple threads can race here thinking there are the
+    // first one to compute and cache the hash code.
+    //
+    // (3) Moreover, since 'hashCode' is non-volatile, the cached hash code value written from one
+    // thread may not be visible by another.
+    //
+    // All three of these issues are benign from a correctness perspective; in the end we have no
+    // overhead from synchronization, at the cost of potentially computing the hash code more than
+    // once.
+    int h = hashCode;
+    if (h == 0) {
+      h = computeHashCode();
+      hashCode = h;
+    }
+    return h;
+  }
+
+  @Override
+  public final T argument() {
+    return arg;
+  }
+
+  private int computeHashCode() {
+    return 31 * functionName().hashCode() + arg.hashCode();
+  }
+
+  @Override
+  public final boolean equals(Object obj) {
+    if (this == obj) {
+      return true;
+    }
+    if (obj == null || getClass() != obj.getClass()) {
+      return false;
+    }
+    AbstractSkyKey<?> that = (AbstractSkyKey<?>) obj;
+    return this.functionName().equals(that.functionName()) && this.arg.equals(that.arg);
+  }
+
+  @Override
+  public String toString() {
+    return functionName() + ":" + arg;
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/skyframe/BUILD b/src/main/java/com/google/devtools/build/skyframe/BUILD
index c33e8ae265..bb24dde0c1 100644
--- a/src/main/java/com/google/devtools/build/skyframe/BUILD
+++ b/src/main/java/com/google/devtools/build/skyframe/BUILD
@@ -7,7 +7,7 @@ package(
 SKYFRAME_OBJECT_SRCS = [
     "SkyValue.java",
     "SkyKey.java",
-    "LegacySkyKey.java",
+    "AbstractSkyKey.java",
     "SkyFunctionName.java",
 ]
 
@@ -17,7 +17,6 @@ java_library(
     visibility = ["//visibility:public"],
     deps = [
         "//src/main/java/com/google/devtools/build/lib/collect",
-        "//src/main/java/com/google/devtools/build/lib/concurrent",
         "//third_party:guava",
     ],
 )
diff --git a/src/main/java/com/google/devtools/build/skyframe/ErrorTransienceValue.java b/src/main/java/com/google/devtools/build/skyframe/ErrorTransienceValue.java
index 6d44fbe47c..babf90208c 100644
--- a/src/main/java/com/google/devtools/build/skyframe/ErrorTransienceValue.java
+++ b/src/main/java/com/google/devtools/build/skyframe/ErrorTransienceValue.java
@@ -23,7 +23,7 @@ import java.io.ObjectOutputStream;
  */
 public final class ErrorTransienceValue implements SkyValue {
   public static final SkyFunctionName FUNCTION_NAME = SkyFunctionName.create("ERROR_TRANSIENCE");
-  public static final SkyKey KEY = LegacySkyKey.create(FUNCTION_NAME, "ERROR_TRANSIENCE");
+  @AutoCodec public static final SkyKey KEY = () -> FUNCTION_NAME;
   @AutoCodec public static final ErrorTransienceValue INSTANCE = new ErrorTransienceValue();
 
   private ErrorTransienceValue() {}
diff --git a/src/main/java/com/google/devtools/build/skyframe/LegacySkyKey.java b/src/main/java/com/google/devtools/build/skyframe/LegacySkyKey.java
deleted file mode 100644
index 311c892f20..0000000000
--- a/src/main/java/com/google/devtools/build/skyframe/LegacySkyKey.java
+++ /dev/null
@@ -1,127 +0,0 @@
-// Copyright 2017 The Bazel Authors. All rights reserved.
-//
-// Licensed 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 com.google.devtools.build.skyframe;
-
-import com.google.common.base.Preconditions;
-import com.google.common.collect.Interner;
-import com.google.devtools.build.lib.concurrent.BlazeInterners;
-
-/**
- * Basic implementation of {@link SkyKey}. Potentially non-optimal from a memory perspective, since
- * it uses fields for hash code and {@link #functionName}. The latter should be implemented instead
- * using polymorphism. See {@code ArtifactSkyKey} for an example.
- */
-public class LegacySkyKey implements SkyKey {
-  private static final Interner<SkyKey> SKY_KEY_INTERNER = BlazeInterners.newWeakInterner();
-
-  /**
-   * Creates a {@link SkyKey}. Prefer instead creating custom SkyKeys that are their own arguments,
-   * saving the object wrapper. See {@code ArtifactSkyKey} for an example.
-   */
-  // TODO(janakr): migrate users of this to use custom SkyKey subclasses and delete this.
-  @Deprecated
-  public static SkyKey create(SkyFunctionName functionName, Object argument) {
-    // Intern to save memory.
-    return SKY_KEY_INTERNER.intern(new LegacySkyKey(functionName, argument));
-  }
-
-  private final SkyFunctionName functionName;
-
-  /**
-   * The name of the value.
-   *
-   * <p>This is deliberately an untyped Object so that we can use arbitrary value types (e.g.,
-   * Labels, PathFragments, BuildConfigurations, etc.) as value names without incurring
-   * serialization costs in the in-memory implementation of the graph.
-   */
-  private final Object argument;
-
-  /**
-   * Cache the hash code for this object. It might be expensive to compute. It is transient because
-   * argument's hash code might not be stable across JVM instances.
-   */
-  private transient int hashCode;
-
-  private LegacySkyKey(SkyFunctionName functionName, Object argument) {
-    this.functionName = Preconditions.checkNotNull(functionName);
-    this.argument = Preconditions.checkNotNull(argument);
-    // 'hashCode' is non-volatile and non-final, so this write may in fact *not* be visible to other
-    // threads. But this isn't a concern from a correctness perspective. See the comments in
-    // #hashCode for more details.
-    this.hashCode = computeHashCode();
-  }
-
-  @Override
-  public SkyFunctionName functionName() {
-    return functionName;
-  }
-
-  @Override
-  public Object argument() {
-    return argument;
-  }
-
-  @Override
-  public String toString() {
-    return functionName + ":" + argument;
-  }
-
-  @Override
-  public int hashCode() {
-    // We use the hash code caching strategy employed by java.lang.String. There are three subtle
-    // things going on here:
-    //
-    // (1) We use a value of 0 to indicate that the hash code hasn't been computed and cached yet.
-    // Yes, this means that if the hash code is really 0 then we will "recompute" it each time. But
-    // this isn't a problem in practice since a hash code of 0 should be rare.
-    //
-    // (2) Since we have no synchronization, multiple threads can race here thinking there are the
-    // first one to compute and cache the hash code.
-    //
-    // (3) Moreover, since 'hashCode' is non-volatile, the cached hash code value written from one
-    // thread may not be visible by another.
-    //
-    // All three of these issues are benign from a correctness perspective; in the end we have no
-    // overhead from synchronization, at the cost of potentially computing the hash code more than
-    // once.
-    int h = hashCode;
-    if (h == 0) {
-      h = computeHashCode();
-      hashCode = h;
-    }
-    return h;
-  }
-
-  private int computeHashCode() {
-    return 31 * functionName.hashCode() + argument.hashCode();
-  }
-
-  @Override
-  public boolean equals(Object obj) {
-    if (this == obj) {
-      return true;
-    }
-    if (obj == null) {
-      return false;
-    }
-    if (getClass() != obj.getClass()) {
-      return false;
-    }
-    LegacySkyKey other = (LegacySkyKey) obj;
-    if (hashCode() != other.hashCode()) {
-      return false;
-    }
-    return functionName.equals(other.functionName) && argument.equals(other.argument);
-  }
-}
diff --git a/src/main/java/com/google/devtools/build/skyframe/SimpleCycleDetector.java b/src/main/java/com/google/devtools/build/skyframe/SimpleCycleDetector.java
index ad952c2ef6..d1348daab2 100644
--- a/src/main/java/com/google/devtools/build/skyframe/SimpleCycleDetector.java
+++ b/src/main/java/com/google/devtools/build/skyframe/SimpleCycleDetector.java
@@ -77,8 +77,7 @@ public class SimpleCycleDetector implements CycleDetector {
    * value is popped, we know that all the children are finished. We would use null instead, but
    * ArrayDeque does not permit null elements.
    */
-  private static final SkyKey CHILDREN_FINISHED =
-      LegacySkyKey.create(SkyFunctionName.create("MARKER"), "MARKER");
+  private static final SkyKey CHILDREN_FINISHED = () -> null;
 
   /** The max number of cycles we will report to the user for a given root, to avoid OOMing. */
   private static final int MAX_CYCLES = 20;
diff --git a/src/test/java/com/google/devtools/build/lib/repository/ExternalPackageUtilTest.java b/src/test/java/com/google/devtools/build/lib/repository/ExternalPackageUtilTest.java
index 44808dee10..8d07983cd5 100644
--- a/src/test/java/com/google/devtools/build/lib/repository/ExternalPackageUtilTest.java
+++ b/src/test/java/com/google/devtools/build/lib/repository/ExternalPackageUtilTest.java
@@ -52,9 +52,9 @@ import com.google.devtools.build.lib.skyframe.WorkspaceFileFunction;
 import com.google.devtools.build.lib.syntax.SkylarkSemantics;
 import com.google.devtools.build.lib.util.io.TimestampGranularityMonitor;
 import com.google.devtools.build.lib.vfs.Root;
+import com.google.devtools.build.skyframe.AbstractSkyKey;
 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.MemoizingEvaluator;
 import com.google.devtools.build.skyframe.RecordingDifferencer;
 import com.google.devtools.build.skyframe.SequencedRecordingDifferencer;
@@ -214,8 +214,8 @@ public class ExternalPackageUtilTest extends BuildViewTestCase {
   // HELPER SKYFUNCTIONS
 
   // GetRuleByName.
-  SkyKey getRuleByNameKey(String ruleName) {
-    return LegacySkyKey.create(GET_RULE_BY_NAME_FUNCTION, ruleName);
+  private static SkyKey getRuleByNameKey(String ruleName) {
+    return new Key(ruleName);
   }
 
   EvaluationResult<GetRuleByNameValue> getRuleByName(SkyKey key) throws InterruptedException {
@@ -261,8 +261,8 @@ public class ExternalPackageUtilTest extends BuildViewTestCase {
   }
 
   // GetRegisteredToolchains.
-  SkyKey getRegisteredToolchainsKey() {
-    return LegacySkyKey.create(GET_REGISTERED_TOOLCHAINS_FUNCTION, "singleton");
+  private static SkyKey getRegisteredToolchainsKey() {
+    return () -> GET_REGISTERED_TOOLCHAINS_FUNCTION;
   }
 
   EvaluationResult<GetRegisteredToolchainsValue> getRegisteredToolchains(SkyKey key)
@@ -309,8 +309,8 @@ public class ExternalPackageUtilTest extends BuildViewTestCase {
   }
 
   // GetRegisteredExecutionPlatforms.
-  SkyKey getRegisteredExecutionPlatformsKey() {
-    return LegacySkyKey.create(GET_REGISTERED_EXECUTION_PLATFORMS_FUNCTION, "singleton");
+  private static SkyKey getRegisteredExecutionPlatformsKey() {
+    return () -> GET_REGISTERED_EXECUTION_PLATFORMS_FUNCTION;
   }
 
   EvaluationResult<GetRegisteredExecutionPlatformsValue> getRegisteredExecutionPlatforms(SkyKey key)
@@ -356,4 +356,15 @@ public class ExternalPackageUtilTest extends BuildViewTestCase {
       return null;
     }
   }
+
+  static class Key extends AbstractSkyKey<String> {
+    private Key(String arg) {
+      super(arg);
+    }
+
+    @Override
+    public SkyFunctionName functionName() {
+      return GET_RULE_BY_NAME_FUNCTION;
+    }
+  }
 }
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/ConfigurationsForTargetsTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/ConfigurationsForTargetsTest.java
index e8632b45e4..bc0d3ec083 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/ConfigurationsForTargetsTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/ConfigurationsForTargetsTest.java
@@ -48,8 +48,8 @@ import com.google.devtools.build.lib.skyframe.util.SkyframeExecutorTestUtils;
 import com.google.devtools.build.lib.testutil.Suite;
 import com.google.devtools.build.lib.testutil.TestSpec;
 import com.google.devtools.build.lib.util.OrderedSetMultimap;
+import com.google.devtools.build.skyframe.AbstractSkyKey;
 import com.google.devtools.build.skyframe.EvaluationResult;
-import com.google.devtools.build.skyframe.LegacySkyKey;
 import com.google.devtools.build.skyframe.SkyFunction;
 import com.google.devtools.build.skyframe.SkyFunctionException;
 import com.google.devtools.build.skyframe.SkyFunctionName;
@@ -98,11 +98,20 @@ public class ConfigurationsForTargetsTest extends AnalysisTestCase {
       this.stateProvider = lateBoundStateProvider;
     }
 
-    /**
-     * Returns a {@link SkyKey} for a given <Target, BuildConfiguration> pair.
-     */
-    static SkyKey key(Target target, BuildConfiguration config) {
-      return LegacySkyKey.create(SKYFUNCTION_NAME, new TargetAndConfiguration(target, config));
+    /** Returns a {@link SkyKey} for a given <Target, BuildConfiguration> pair. */
+    private static Key key(Target target, BuildConfiguration config) {
+      return new Key(new TargetAndConfiguration(target, config));
+    }
+
+    private static class Key extends AbstractSkyKey<TargetAndConfiguration> {
+      private Key(TargetAndConfiguration arg) {
+        super(arg);
+      }
+
+      @Override
+      public SkyFunctionName functionName() {
+        return SKYFUNCTION_NAME;
+      }
     }
 
     /**
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/RecursiveFilesystemTraversalFunctionTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/RecursiveFilesystemTraversalFunctionTest.java
index 0da51f8f50..719195dbc5 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/RecursiveFilesystemTraversalFunctionTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/RecursiveFilesystemTraversalFunctionTest.java
@@ -233,14 +233,18 @@ public final class RecursiveFilesystemTraversalFunctionTest extends FoundationTe
   }
 
   private static TraversalRequest fileLikeRoot(Artifact file, PackageBoundaryMode pkgBoundaryMode) {
-    return new TraversalRequest(DirectTraversalRoot.forFileOrDirectory(file),
-        !file.isSourceArtifact(), pkgBoundaryMode, false, null);
+    return TraversalRequest.create(
+        DirectTraversalRoot.forFileOrDirectory(file),
+        !file.isSourceArtifact(),
+        pkgBoundaryMode,
+        false,
+        null);
   }
 
   private static TraversalRequest pkgRoot(
       RootedPath pkgDirectory, PackageBoundaryMode pkgBoundaryMode) {
-    return new TraversalRequest(DirectTraversalRoot.forRootedPath(pkgDirectory), false,
-        pkgBoundaryMode, true, null);
+    return TraversalRequest.create(
+        DirectTraversalRoot.forRootedPath(pkgDirectory), false, pkgBoundaryMode, true, null);
   }
 
   private <T extends SkyValue> EvaluationResult<T> eval(SkyKey key) throws Exception {
@@ -253,14 +257,9 @@ public final class RecursiveFilesystemTraversalFunctionTest extends FoundationTe
 
   private RecursiveFilesystemTraversalValue evalTraversalRequest(TraversalRequest params)
       throws Exception {
-    SkyKey key = rftvSkyKey(params);
-    EvaluationResult<RecursiveFilesystemTraversalValue> result = eval(key);
+    EvaluationResult<RecursiveFilesystemTraversalValue> result = eval(params);
     assertThat(result.hasError()).isFalse();
-    return result.get(key);
-  }
-
-  private static SkyKey rftvSkyKey(TraversalRequest params) {
-    return RecursiveFilesystemTraversalValue.key(params);
+    return result.get(params);
   }
 
   /**
@@ -388,7 +387,7 @@ public final class RecursiveFilesystemTraversalFunctionTest extends FoundationTe
     // Edit the file and verify that the value is rebuilt.
     appendToFile(rootArtifact, "bar");
     RecursiveFilesystemTraversalValue v2 = traverseAndAssertFiles(traversalRoot, expected);
-    assertThat(progressReceiver.invalidations).contains(rftvSkyKey(traversalRoot));
+    assertThat(progressReceiver.invalidations).contains(traversalRoot);
     assertThat(progressReceiver.evaluations).contains(v2);
     assertThat(v2).isNotEqualTo(v1);
     assertTraversalRootHashesAreNotEqual(v1, v2);
@@ -428,7 +427,7 @@ public final class RecursiveFilesystemTraversalFunctionTest extends FoundationTe
     // Edit the target of the symlink and verify that the value is rebuilt.
     appendToFile(linkTargetArtifact, "bar");
     RecursiveFilesystemTraversalValue v2 = traverseAndAssertFiles(traversalRoot, expected);
-    assertThat(progressReceiver.invalidations).contains(rftvSkyKey(traversalRoot));
+    assertThat(progressReceiver.invalidations).contains(traversalRoot);
     assertThat(progressReceiver.evaluations).contains(v2);
     assertThat(v2).isNotEqualTo(v1);
     assertTraversalRootHashesAreNotEqual(v1, v2);
@@ -490,7 +489,7 @@ public final class RecursiveFilesystemTraversalFunctionTest extends FoundationTe
     ResolvedFile expected3 = regularFileForTesting(file3);
     RecursiveFilesystemTraversalValue v2 =
         traverseAndAssertFiles(traversalRoot, expected1, expected2, expected3);
-    assertThat(progressReceiver.invalidations).contains(rftvSkyKey(traversalRoot));
+    assertThat(progressReceiver.invalidations).contains(traversalRoot);
     assertThat(progressReceiver.evaluations).contains(v2);
     // Directories always have the same hash code, but that is fine because their contents are also
     // part of the RecursiveFilesystemTraversalValue, so v1 and v2 are unequal.
@@ -504,7 +503,7 @@ public final class RecursiveFilesystemTraversalFunctionTest extends FoundationTe
       SkyKey toInvalidate = FileStateValue.key(file1);
       appendToFile(file1, toInvalidate, "bar");
       v3 = traverseAndAssertFiles(traversalRoot, expected1, expected2, expected3);
-      assertThat(progressReceiver.invalidations).contains(rftvSkyKey(traversalRoot));
+      assertThat(progressReceiver.invalidations).contains(traversalRoot);
       assertThat(progressReceiver.evaluations).contains(v3);
       assertThat(v3).isNotEqualTo(v2);
       // Directories always have the same hash code, but that is fine because their contents are
@@ -525,7 +524,7 @@ public final class RecursiveFilesystemTraversalFunctionTest extends FoundationTe
         traverseAndAssertFiles(traversalRoot, expected1, expected2, expected3);
     assertThat(v4).isEqualTo(v3);
     assertTraversalRootHashesAreEqual(v3, v4);
-    assertThat(progressReceiver.invalidations).doesNotContain(rftvSkyKey(traversalRoot));
+    assertThat(progressReceiver.invalidations).doesNotContain(traversalRoot);
   }
 
   @Test
@@ -609,7 +608,7 @@ public final class RecursiveFilesystemTraversalFunctionTest extends FoundationTe
     ResolvedFile expected4 = regularFileForTesting(childOf(linkNameArtifact, "file.3"));
     RecursiveFilesystemTraversalValue v2 =
         traverseAndAssertFiles(traversalRoot, expected1, expected2, expected3, expected4);
-    assertThat(progressReceiver.invalidations).contains(rftvSkyKey(traversalRoot));
+    assertThat(progressReceiver.invalidations).contains(traversalRoot);
     assertThat(progressReceiver.evaluations).contains(v2);
     assertThat(v2).isNotEqualTo(v1);
     assertTraversalRootHashesAreNotEqual(v1, v2);
@@ -619,7 +618,7 @@ public final class RecursiveFilesystemTraversalFunctionTest extends FoundationTe
     appendToFile(file1, "bar");
     RecursiveFilesystemTraversalValue v3 =
         traverseAndAssertFiles(traversalRoot, expected1, expected2, expected3, expected4);
-    assertThat(progressReceiver.invalidations).contains(rftvSkyKey(traversalRoot));
+    assertThat(progressReceiver.invalidations).contains(traversalRoot);
     assertThat(progressReceiver.evaluations).contains(v3);
     assertThat(v3).isNotEqualTo(v2);
     assertTraversalRootHashesAreNotEqual(v2, v3);
@@ -633,7 +632,7 @@ public final class RecursiveFilesystemTraversalFunctionTest extends FoundationTe
         traverseAndAssertFiles(traversalRoot, expected1, expected2, expected3, expected4);
     assertThat(v4).isEqualTo(v3);
     assertTraversalRootHashesAreEqual(v3, v4);
-    assertThat(progressReceiver.invalidations).doesNotContain(rftvSkyKey(traversalRoot));
+    assertThat(progressReceiver.invalidations).doesNotContain(traversalRoot);
   }
 
   @Test
@@ -683,7 +682,7 @@ public final class RecursiveFilesystemTraversalFunctionTest extends FoundationTe
         traverseAndAssertFiles(traversalRoot, expected1);
         break;
       case REPORT_ERROR:
-        SkyKey key = rftvSkyKey(traversalRoot);
+        SkyKey key = traversalRoot;
         EvaluationResult<SkyValue> result = eval(key);
         assertThat(result.hasError()).isTrue();
         assertThat(result.getError().getException())
@@ -809,7 +808,7 @@ public final class RecursiveFilesystemTraversalFunctionTest extends FoundationTe
     // Change the digest of the file. See that the value is rebuilt.
     appendToFile(path, "world");
     RecursiveFilesystemTraversalValue v2 = traverseAndAssertFiles(params, expected);
-    assertThat(progressReceiver.invalidations).contains(rftvSkyKey(params));
+    assertThat(progressReceiver.invalidations).contains(params);
     assertThat(v2).isNotEqualTo(v1);
     assertTraversalRootHashesAreNotEqual(v1, v2);
   }
@@ -843,7 +842,7 @@ public final class RecursiveFilesystemTraversalFunctionTest extends FoundationTe
     createFile(rootedPath(derivedArtifact("a/b/c/file.fake")));
     createFile(sourceArtifact("a/b/c/BUILD"));
 
-    SkyKey key = rftvSkyKey(fileLikeRoot(genDir, CROSS));
+    SkyKey key = fileLikeRoot(genDir, CROSS);
     EvaluationResult<SkyValue> result = eval(key);
     assertThat(result.hasError()).isTrue();
     ErrorInfo error = result.getError(key);
@@ -858,7 +857,7 @@ public final class RecursiveFilesystemTraversalFunctionTest extends FoundationTe
     Artifact bazLink = sourceArtifact("foo/baz.sym");
     Path parentDir = scratch.dir("foo");
     bazLink.getPath().createSymbolicLink(parentDir);
-    SkyKey key = rftvSkyKey(pkgRoot(parentOf(rootedPath(bazLink)), DONT_CROSS));
+    SkyKey key = pkgRoot(parentOf(rootedPath(bazLink)), DONT_CROSS);
     EvaluationResult<SkyValue> result = eval(key);
     assertThat(result.hasError()).isTrue();
     ErrorInfo error = result.getError(key);
@@ -876,7 +875,7 @@ public final class RecursiveFilesystemTraversalFunctionTest extends FoundationTe
     barLink.getPath().createSymbolicLink(bazLink.getPath());
     bazLink.getPath().createSymbolicLink(fooLink.getPath());
 
-    SkyKey key = rftvSkyKey(pkgRoot(parentOf(rootedPath(bazLink)), DONT_CROSS));
+    SkyKey key = pkgRoot(parentOf(rootedPath(bazLink)), DONT_CROSS);
     EvaluationResult<SkyValue> result = eval(key);
     assertThat(result.hasError()).isTrue();
     ErrorInfo error = result.getError(key);
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/RecursivePkgKeyTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/RecursivePkgKeyTest.java
index b6bd39494b..158d6e2942 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/RecursivePkgKeyTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/RecursivePkgKeyTest.java
@@ -18,7 +18,6 @@ import static org.junit.Assert.fail;
 import com.google.common.collect.ImmutableSet;
 import com.google.devtools.build.lib.analysis.util.BuildViewTestCase;
 import com.google.devtools.build.lib.cmdline.RepositoryName;
-import com.google.devtools.build.lib.skyframe.RecursivePkgValue.RecursivePkgKey;
 import com.google.devtools.build.lib.vfs.PathFragment;
 import com.google.devtools.build.lib.vfs.Root;
 import com.google.devtools.build.lib.vfs.RootedPath;
diff --git a/src/test/java/com/google/devtools/build/skyframe/BUILD b/src/test/java/com/google/devtools/build/skyframe/BUILD
index f213c16110..712dc503f4 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 @@ java_library(
         "//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 @@ java_test(
         ":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 06dd49b97c..7cac95f273 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 @@ import org.junit.runners.JUnit4;
 @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 a00391481a..9c9d00ee6f 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 @@ public class ErrorInfoTest {
 
   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 class ErrorInfoTest {
   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 class ErrorInfoTest {
   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 @@ public class ErrorInfoTest {
 
     // 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 @@ public class ErrorInfoTest {
     }
   }
 }
-
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 a864f48201..378f58c81e 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 @@ import org.junit.Test;
 
 /** 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 @@ public abstract class GraphTest {
   }
 
   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 657dd00e4a..a30af1c5c0 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.base.Preconditions;
 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 class GraphTester {
   }
 
   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 class GraphTester {
 
   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 @@ public class GraphTester {
       }
     };
   }
+
+  @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 00969da7c4..b16206cd6b 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 @@ import org.junit.runners.JUnit4;
  */
 @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 7521dd3ea6..d2a5bfc6a6 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 @@ public class MemoizingEvaluatorTest {
   }
 
   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 d0d7b9729f..19c78138f4 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.base.Supplier;
 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 @@ import org.junit.runners.JUnit4;
  */
 @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 @@ public class ParallelEvaluatorTest {
 
   @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 @@ public class ParallelEvaluatorTest {
     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 @@ public class ParallelEvaluatorTest {
       @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 @@ public class ParallelEvaluatorTest {
       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 3a603998a8..8d79965842 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 com.google.common.truth.Truth.assertThat;
 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 @@ import org.junit.runners.Parameterized.Parameters;
 /** 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 @@ public class ReverseDepsUtilityTest {
     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 @@ public class ReverseDepsUtilityTest {
       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 class ReverseDepsUtilityTest {
   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 @@ public class ReverseDepsUtilityTest {
   @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 @@ public class ReverseDepsUtilityTest {
   @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 @@ public class ReverseDepsUtilityTest {
   @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 class ReverseDepsUtilityTest {
   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 fc3cb3faa4..d589a7c2d0 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 @@ package com.google.devtools.build.skyframe;
 
 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 @@ public class SkyKeyTest {
     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 @@ public class SkyKeyTest {
       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;
+    }
+  }
 }