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 3a4774c..75ad690 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 @@
 
 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 @@
   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 529cb4d..b6619a9 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.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.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 @@
 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 eafa09f..a4b6c9a 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.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 @@
  */
 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 6e21ad5..c2ce139 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 @@
 
 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 @@
       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 6a00a4b..247d0e0 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 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 @@
           "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 @@
     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 efc6c9a..81c27fe 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 @@
     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 a450f6f..3786ddc 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.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 @@
     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 ea6c774..7b33d0b 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 @@
  * 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 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 73d13b8..1349481 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.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 @@
 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 8f4db91..f0b3274 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 @@
   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 @@
         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 20de7df..7c4c798 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 @@
 
 /** 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 214daf5..2efd41b 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.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 9e2f280..9ca228c 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.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 @@
   @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 1ed9592..19c0c1d 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.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 @@
    * 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 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 780d749..675ce81 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 @@
 
     @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 2465258..725d201 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 @@
   /** 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 c313072..39343a2 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 @@
   }
 
   @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 d6fb7b4..8d19cc1 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 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 c21aa6c..f47ab7a 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 @@
     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 3d77021..56988b8 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 @@
 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.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 @@
 
   @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 eb01407..590fce8 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 @@
     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 bb0680d..c729465 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 @@
     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 7374bf3..a0fe84d 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 @@
     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 02f256f..4ed96ec 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 @@
   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 0bdf7ab..c4c784a 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 @@
  */
 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 3aebda0..acef91d 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 @@
  * 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 c76a7ad..2b7c49a 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 @@
 
 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 @@
     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 0314de6..ba19623 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 @@
     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 4e04470..827bb8a 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 @@
 
 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 @@
     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 2f83389..1d92dc2 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.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 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 @@
    * <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 @@
       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 2338368..4a1b830 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 @@
 
     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 6c91565..037fd7c 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 @@
 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 @@
   }
 
   @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 @@
           .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 05ef591..d52a964 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.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 0dcbe30..2bc376e 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 @@
    * 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 @@
     }
 
     @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 a885bef..4de2619 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.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 e46776d..2948e4e 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 @@
 
       // 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 @@
 
   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 @@
                 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 @@
     // 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 @@
               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 7a1a269..8d16da6 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.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 @@
     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 @@
      * <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 @@
     /** 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 @@
         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 8430c28..64c27dc 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.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 0000000..9a5a12f
--- /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 0000000..c83825f
--- /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 7397a7a..d864c02 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 @@
     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;
+    @AutoCodec.VisibleForSerialization
+    @AutoCodec.Instantiator
+    static Key create(
+        RepositoryName repositoryName,
+        RootedPath rootedPath,
+        ImmutableSet<PathFragment> excludedPaths) {
+      return interner.intern(new Key(repositoryName, rootedPath, 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);
-    }
-
-    @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 a09d839..ef4cebc 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 @@
 
 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 @@
     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 ab98da4..61f9eb5 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.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 @@
     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 f861ba7..878f1eb 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 @@
    * 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 @@
   }
 
   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 7af9887..caf3720 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 @@
   }
 
   @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 cf21520..e03d732 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 @@
 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 b435720..20a4dc9 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 @@
       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 @@
                                       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 9c18193..7011784 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 @@
 
 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 @@
     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 c74fe4a..83d909d 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 @@
 
 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 @@
  */
 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 @@
     }
 
     @Override
+    public SkyFunctionName functionName() {
+      return SkyFunctions.WORKSPACE_FILE;
+    }
+
+    @Override
     public boolean equals(Object obj) {
       if (this == obj) {
         return true;
@@ -134,8 +144,13 @@
     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 ea0bd94..b162464 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 @@
 
 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 @@
  * 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 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 1b38713..1a44467 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 @@
                     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 0000000..7c7fe27
--- /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 c33e8ae..bb24dde 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 @@
 SKYFRAME_OBJECT_SRCS = [
     "SkyValue.java",
     "SkyKey.java",
-    "LegacySkyKey.java",
+    "AbstractSkyKey.java",
     "SkyFunctionName.java",
 ]
 
@@ -17,7 +17,6 @@
     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 6d44fbe..babf902 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 @@
  */
 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 311c892..0000000
--- 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 ad952c2..d1348daa 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 @@
    * 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;