Implement distributed caching for Bazel

This patch implements distributed caching for Bazel using Hazelcast.
Hazelcast is used as a key value store that stores content of files
indexed by the digest of the file. The cache also stores the list of files
for an action. The key in this case is the digest from the key of the action
and the list of files.

In this change I also added the interface for remote execution. The
implementation will be added in a subsequent patch.

This change is only the first in a series of changes related to distributed
caching and remote execution. I plan to revise the APIs and implementation
in subsequent changes.

--
Change-Id: I569285d6149a4e9f8ba2362682c07a9f1e1943b7
Reviewed-on: https://bazel-review.googlesource.com/#/c/2760/
MOS_MIGRATED_REVID=114325038

18 files changed, 1032 insertions, 5 deletions

diff --git a/src/main/java/com/google/devtools/build/lib/BUILD b/src/main/java/com/google/devtools/build/lib/BUILD
index 37ab00cd29..25fab2153e 100644
--- a/src/main/java/com/google/devtools/build/lib/BUILD
+++ b/src/main/java/com/google/devtools/build/lib/BUILD
@@ -26,18 +26,19 @@ java_library(
 filegroup(
     name = "srcs",
     srcs = glob(["**"]) + [
+        "//src/main/java/com/google/devtools/build/docgen:srcs",
+        "//src/main/java/com/google/devtools/build/lib/bazel/dash:srcs",
+        "//src/main/java/com/google/devtools/build/lib/query2:srcs",
+        "//src/main/java/com/google/devtools/build/lib/remote:srcs",
         "//src/main/java/com/google/devtools/build/lib/rules/apple:srcs",
         "//src/main/java/com/google/devtools/build/lib/rules/cpp:srcs",
         "//src/main/java/com/google/devtools/build/lib/rules/genquery:srcs",
         "//src/main/java/com/google/devtools/build/lib/rules/objc:srcs",
-        "//src/main/java/com/google/devtools/common/options:srcs",
-        "//src/main/java/com/google/devtools/build/lib/bazel/dash:srcs",
         "//src/main/java/com/google/devtools/build/lib/sandbox:srcs",
-        "//src/main/java/com/google/devtools/build/skyframe:srcs",
         "//src/main/java/com/google/devtools/build/lib/standalone:srcs",
         "//src/main/java/com/google/devtools/build/lib/worker:srcs",
-        "//src/main/java/com/google/devtools/build/lib/query2:srcs",
-        "//src/main/java/com/google/devtools/build/docgen:srcs",
+        "//src/main/java/com/google/devtools/build/skyframe:srcs",
+        "//src/main/java/com/google/devtools/common/options:srcs",
     ],
     visibility = ["//src/test/shell/bazel:__pkg__"],
 )
@@ -535,6 +536,7 @@ java_library(
         ":vfs",
         "//src/main/java/com/google/devtools/build/lib/actions",
         "//src/main/java/com/google/devtools/build/lib/bazel/dash",
+        "//src/main/java/com/google/devtools/build/lib/remote",
         "//src/main/java/com/google/devtools/build/lib/sandbox",
         "//src/main/java/com/google/devtools/build/lib/standalone",
         "//src/main/java/com/google/devtools/build/lib/worker",
diff --git a/src/main/java/com/google/devtools/build/lib/bazel/BazelMain.java b/src/main/java/com/google/devtools/build/lib/bazel/BazelMain.java
index 2b29f2dc2f..827393296e 100644
--- a/src/main/java/com/google/devtools/build/lib/bazel/BazelMain.java
+++ b/src/main/java/com/google/devtools/build/lib/bazel/BazelMain.java
@@ -46,6 +46,7 @@ public final class BazelMain {
           com.google.devtools.build.lib.bazel.dash.DashModule.class,
           com.google.devtools.build.lib.bazel.rules.BazelRulesModule.class,
           com.google.devtools.build.lib.worker.WorkerModule.class,
+          com.google.devtools.build.lib.remote.RemoteModule.class,
           com.google.devtools.build.lib.standalone.StandaloneModule.class,
           com.google.devtools.build.lib.sandbox.SandboxModule.class,
           com.google.devtools.build.lib.runtime.BuildSummaryStatsModule.class);
diff --git a/src/main/java/com/google/devtools/build/lib/remote/BUILD b/src/main/java/com/google/devtools/build/lib/remote/BUILD
new file mode 100644
index 0000000000..5fc0ec3378
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/remote/BUILD
@@ -0,0 +1,33 @@
+package(
+    default_visibility = ["//src:__subpackages__"],
+)
+
+java_library(
+    name = "remote",
+    srcs = glob(["*.java"]),
+    deps = [
+        "//src/main/java/com/google/devtools/build/lib:build-base",
+        "//src/main/java/com/google/devtools/build/lib:concurrent",
+        "//src/main/java/com/google/devtools/build/lib:events",
+        "//src/main/java/com/google/devtools/build/lib:io",
+        "//src/main/java/com/google/devtools/build/lib:packages-internal",
+        "//src/main/java/com/google/devtools/build/lib:runtime",
+        "//src/main/java/com/google/devtools/build/lib:util",
+        "//src/main/java/com/google/devtools/build/lib:vfs",
+        "//src/main/java/com/google/devtools/build/lib/actions",
+        "//src/main/java/com/google/devtools/build/lib/standalone",
+        "//src/main/java/com/google/devtools/common/options",
+        "//src/main/protobuf:remote_protocol_proto",
+        "//third_party:apache_httpclient",
+        "//third_party:apache_httpcore",
+        "//third_party:gson",
+        "//third_party:guava",
+        "//third_party:hazelcast",
+        "//third_party:protobuf",
+    ],
+)
+
+filegroup(
+    name = "srcs",
+    srcs = glob(["**"]),
+)
diff --git a/src/main/java/com/google/devtools/build/lib/remote/CacheNotFoundException.java b/src/main/java/com/google/devtools/build/lib/remote/CacheNotFoundException.java
new file mode 100644
index 0000000000..0e4e52c1d4
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/remote/CacheNotFoundException.java
@@ -0,0 +1,33 @@
+// Copyright 2016 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.remote;
+
+/**
+ * An exception to indicate the cache is not found because of an expected
+ * problem.
+ */
+final class CacheNotFoundException extends RuntimeException {
+  CacheNotFoundException() {
+    super();
+  }
+
+  CacheNotFoundException(String message) {
+    super(message);
+  }
+
+  CacheNotFoundException(String message, Throwable cause) {
+    super(message, cause);
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/remote/HazelcastCacheFactory.java b/src/main/java/com/google/devtools/build/lib/remote/HazelcastCacheFactory.java
new file mode 100644
index 0000000000..e524770652
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/remote/HazelcastCacheFactory.java
@@ -0,0 +1,48 @@
+// Copyright 2016 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.remote;
+
+import com.hazelcast.client.HazelcastClient;
+import com.hazelcast.client.config.ClientConfig;
+import com.hazelcast.client.config.ClientNetworkConfig;
+import com.hazelcast.core.Hazelcast;
+import com.hazelcast.core.HazelcastInstance;
+
+import java.util.concurrent.ConcurrentMap;
+
+/**
+ * A factory class for providing a {@link ConcurrentMap} object implemented by Hazelcast.
+ * Hazelcast will work as a distributed memory cache.
+ */
+final class HazelcastCacheFactory {
+
+  private static final String CACHE_NAME = "hazelcast-build-cache";
+
+  static ConcurrentMap<String, byte[]> create(RemoteOptions options) {
+    HazelcastInstance instance;
+    if (options.hazelcastNode != null) {
+      // If --hazelast_node is then create a client instance.
+      ClientConfig config = new ClientConfig();
+      ClientNetworkConfig net = config.getNetworkConfig();
+      net.addAddress(options.hazelcastNode.split(","));
+      instance = HazelcastClient.newHazelcastClient(config);
+    } else {
+      // Otherwise create a default instance. This is going to look at
+      // -Dhazelcast.config=some-hazelcast.xml for configuration.
+      instance = Hazelcast.newHazelcastInstance();
+    }
+    return instance.getMap(CACHE_NAME);
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/remote/MemcacheActionCache.java b/src/main/java/com/google/devtools/build/lib/remote/MemcacheActionCache.java
new file mode 100644
index 0000000000..e83ad69987
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/remote/MemcacheActionCache.java
@@ -0,0 +1,169 @@
+// Copyright 2016 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.remote;
+
+import com.google.common.hash.HashCode;
+import com.google.devtools.build.lib.actions.ActionInput;
+import com.google.devtools.build.lib.actions.ActionInputFileCache;
+import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe;
+import com.google.devtools.build.lib.remote.RemoteProtocol.CacheEntry;
+import com.google.devtools.build.lib.remote.RemoteProtocol.FileEntry;
+import com.google.devtools.build.lib.util.Preconditions;
+import com.google.devtools.build.lib.vfs.Path;
+import com.google.protobuf.ByteString;
+
+import java.io.IOException;
+import java.io.InputStream;
+import java.io.OutputStream;
+import java.util.Collection;
+import java.util.concurrent.ConcurrentMap;
+import java.util.concurrent.Semaphore;
+
+/**
+ * A RemoteActionCache implementation that uses memcache as a distributed storage
+ * for files and action output. The memcache is accessed by the {@link ConcurrentMap}
+ * interface.
+ *
+ * The thread satefy is guaranteed by the underlying memcache client.
+ */
+@ThreadSafe
+final class MemcacheActionCache implements RemoteActionCache {
+  private final Path execRoot;
+  private final ConcurrentMap<String, byte[]> cache;
+  private static final int MAX_MEMORY_KBYTES = 512 * 1024;
+  private final Semaphore uploadMemoryAvailable = new Semaphore(MAX_MEMORY_KBYTES, true);
+
+  /**
+   * Construct an action cache using JCache API.
+   */
+  MemcacheActionCache(
+      Path execRoot, RemoteOptions options, ConcurrentMap<String, byte[]> cache) {
+    this.execRoot = execRoot;
+    this.cache = cache;
+  }
+
+  @Override
+  public String putFileIfNotExist(Path file) throws IOException {
+    String contentKey = HashCode.fromBytes(file.getMD5Digest()).toString();
+    if (containsFile(contentKey)) {
+      return contentKey;
+    }
+    putFile(contentKey, file);
+    return contentKey;
+  }
+
+  @Override
+  public String putFileIfNotExist(ActionInputFileCache cache, ActionInput file) throws IOException {
+    // PerActionFileCache already converted this to a lowercase ascii string.. it's not consistent!
+    String contentKey = new String(cache.getDigest(file).toByteArray());
+    if (containsFile(contentKey)) {
+      return contentKey;
+    }
+    putFile(contentKey, execRoot.getRelative(file.getExecPathString()));
+    return contentKey;
+  }
+
+  private void putFile(String key, Path file) throws IOException {
+    int fileSizeKBytes = (int) (file.getFileSize() / 1024);
+    Preconditions.checkArgument(fileSizeKBytes < MAX_MEMORY_KBYTES);
+    try {
+      uploadMemoryAvailable.acquire(fileSizeKBytes);
+      // TODO(alpha): I should put the file content as chunks to avoid reading the entire
+      // file into memory.
+      try (InputStream stream = file.getInputStream()) {
+        cache.put(
+            key,
+            CacheEntry.newBuilder()
+                .setFileContent(ByteString.readFrom(stream))
+                .build()
+                .toByteArray());
+      }
+    } catch (InterruptedException e) {
+      throw new IOException("Failed to put file to memory cache.", e);
+    } finally {
+      uploadMemoryAvailable.release(fileSizeKBytes);
+    }
+  }
+
+  @Override
+  public void writeFile(String key, Path dest, boolean executable)
+      throws IOException, CacheNotFoundException {
+    byte[] data = cache.get(key);
+    if (data == null) {
+      throw new CacheNotFoundException("File content cannot be found with key: " + key);
+    }
+    try (OutputStream stream = dest.getOutputStream()) {
+      CacheEntry.parseFrom(data).getFileContent().writeTo(stream);
+      dest.setExecutable(executable);
+    }
+  }
+
+  private boolean containsFile(String key) {
+    return cache.containsKey(key);
+  }
+
+  @Override
+  public void writeActionOutput(String key, Path execRoot)
+      throws IOException, CacheNotFoundException {
+    byte[] data = cache.get(key);
+    if (data == null) {
+      throw new CacheNotFoundException("Action output cannot be found with key: " + key);
+    }
+    CacheEntry cacheEntry = CacheEntry.parseFrom(data);
+    for (FileEntry file : cacheEntry.getFilesList()) {
+      writeFile(file.getContentKey(), execRoot.getRelative(file.getPath()), file.getExecutable());
+    }
+  }
+
+  @Override
+  public void putActionOutput(String key, Collection<? extends ActionInput> outputs)
+      throws IOException {
+    CacheEntry.Builder actionOutput = CacheEntry.newBuilder();
+    for (ActionInput output : outputs) {
+      Path file = execRoot.getRelative(output.getExecPathString());
+      addToActionOutput(file, output.getExecPathString(), actionOutput);
+    }
+    cache.put(key, actionOutput.build().toByteArray());
+  }
+
+  @Override
+  public void putActionOutput(String key, Path execRoot, Collection<Path> files)
+      throws IOException {
+    CacheEntry.Builder actionOutput = CacheEntry.newBuilder();
+    for (Path file : files) {
+      addToActionOutput(file, file.relativeTo(execRoot).getPathString(), actionOutput);
+    }
+    cache.put(key, actionOutput.build().toByteArray());
+  }
+
+  /**
+   * Add the file to action output cache entry. Put the file to cache if necessary.
+   */
+  private void addToActionOutput(Path file, String execPathString, CacheEntry.Builder actionOutput)
+      throws IOException {
+    if (file.isDirectory()) {
+      // TODO(alpha): Implement this for directory.
+      throw new UnsupportedOperationException("Storing a directory is not yet supported.");
+    }
+    // First put the file content to cache.
+    String contentKey = putFileIfNotExist(file);
+    // Add to protobuf.
+    actionOutput
+        .addFilesBuilder()
+        .setPath(execPathString)
+        .setContentKey(contentKey)
+        .setExecutable(file.isExecutable());
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/remote/README.md b/src/main/java/com/google/devtools/build/lib/remote/README.md
new file mode 100644
index 0000000000..c020564c96
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/remote/README.md
@@ -0,0 +1,15 @@
+How to run a standalone Hazelcast server for testing distributed cache.
+
+* First you need to run a standalone Hazelcast server with JCache API in the
+classpath. This will start Hazelcast with the default configuration.
+
+java -cp third_party/hazelcast/hazelcast-3.5.4.jar \
+    com.hazelcast.core.server.StartServer
+
+* Then you run Bazel pointing to the Hazelcast server.
+
+bazel build --hazelcast_node=127.0.0.1:5701 --spawn_strategy=remote \
+    src/tools/generate_workspace:all
+
+Above command will build generate_workspace with remote spawn strategy that uses
+Hazelcast as the distributed caching backend.
diff --git a/src/main/java/com/google/devtools/build/lib/remote/RemoteActionCache.java b/src/main/java/com/google/devtools/build/lib/remote/RemoteActionCache.java
new file mode 100644
index 0000000000..538a4c987e
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/remote/RemoteActionCache.java
@@ -0,0 +1,71 @@
+// Copyright 2016 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.remote;
+
+import com.google.devtools.build.lib.actions.ActionInput;
+import com.google.devtools.build.lib.actions.ActionInputFileCache;
+import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadCompatible;
+import com.google.devtools.build.lib.vfs.Path;
+
+import java.io.IOException;
+import java.util.Collection;
+
+/**
+ * A cache for storing artifacts (input and output) as well as the output of running an action.
+ */
+@ThreadCompatible
+interface RemoteActionCache {
+  /**
+   * Put the file in cache if it is not already in it. No-op if the file is already stored in
+   * cache.
+   *
+   * @return The key for fetching the file from cache.
+   */
+  String putFileIfNotExist(Path file) throws IOException;
+
+  /**
+   * Same as {@link putFileIfNotExist(Path)} but this methods takes an ActionInput.
+   *
+   * @return The key for fetching the file from cache.
+   */
+  String putFileIfNotExist(ActionInputFileCache cache, ActionInput file) throws IOException;
+
+  /**
+   * Write the file in cache identified by key to the file system. The key must uniquely identify
+   * the content of the file. Throws CacheNotFoundException if the file is not found in cache.
+   */
+  void writeFile(String key, Path dest, boolean executable)
+      throws IOException, CacheNotFoundException;
+
+  /**
+   * Write the action output files identified by the key to the file system. The key must uniquely
+   * identify the action and the content of action inputs.
+   *
+   * @throws CacheNotFoundException if action output is not found in cache.
+   */
+  void writeActionOutput(String key, Path execRoot)
+      throws IOException, CacheNotFoundException;
+
+  /**
+   * Update the cache with the action outputs for the specified key.
+   */
+  void putActionOutput(String key, Collection<? extends ActionInput> outputs)
+      throws IOException;
+
+  /**
+   * Update the cache with the files for the specified key.
+   */
+  void putActionOutput(String key, Path execRoot, Collection<Path> files) throws IOException;
+}
diff --git a/src/main/java/com/google/devtools/build/lib/remote/RemoteActionContextProvider.java b/src/main/java/com/google/devtools/build/lib/remote/RemoteActionContextProvider.java
new file mode 100644
index 0000000000..d3166243f7
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/remote/RemoteActionContextProvider.java
@@ -0,0 +1,55 @@
+// Copyright 2016 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.remote;
+
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableList.Builder;
+import com.google.devtools.build.lib.actions.ActionContextProvider;
+import com.google.devtools.build.lib.actions.Executor.ActionContext;
+import com.google.devtools.build.lib.buildtool.BuildRequest;
+import com.google.devtools.build.lib.exec.ExecutionOptions;
+import com.google.devtools.build.lib.runtime.BlazeRuntime;
+import com.google.devtools.build.lib.runtime.CommandEnvironment;
+
+/**
+ * Provide a remote execution context.
+ */
+final class RemoteActionContextProvider extends ActionContextProvider {
+  private final ImmutableList<ActionContext> strategies;
+
+  RemoteActionContextProvider(
+      CommandEnvironment env,
+      BuildRequest buildRequest,
+      RemoteActionCache actionCache,
+      RemoteWorkExecutor workExecutor) {
+    BlazeRuntime runtime = env.getRuntime();
+    boolean verboseFailures = buildRequest.getOptions(ExecutionOptions.class).verboseFailures;
+    Builder<ActionContext> strategiesBuilder = ImmutableList.builder();
+    strategiesBuilder.add(
+        new RemoteSpawnStrategy(
+            env.getClientEnv(),
+            runtime.getExecRoot(),
+            buildRequest.getOptions(RemoteOptions.class),
+            verboseFailures,
+            actionCache,
+            workExecutor));
+    this.strategies = strategiesBuilder.build();
+  }
+
+  @Override
+  public Iterable<ActionContext> getActionContexts() {
+    return strategies;
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/remote/RemoteModule.java b/src/main/java/com/google/devtools/build/lib/remote/RemoteModule.java
new file mode 100644
index 0000000000..ebc1874362
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/remote/RemoteModule.java
@@ -0,0 +1,81 @@
+// Copyright 2016 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.remote;
+
+import com.google.common.collect.ImmutableList;
+import com.google.common.eventbus.Subscribe;
+import com.google.devtools.build.lib.actions.ActionContextProvider;
+import com.google.devtools.build.lib.buildtool.BuildRequest;
+import com.google.devtools.build.lib.buildtool.buildevent.BuildStartingEvent;
+import com.google.devtools.build.lib.runtime.BlazeModule;
+import com.google.devtools.build.lib.runtime.Command;
+import com.google.devtools.build.lib.runtime.CommandEnvironment;
+import com.google.devtools.common.options.OptionsBase;
+
+/**
+ * RemoteModule provides distributed cache and remote execution for Bazel.
+ */
+public final class RemoteModule extends BlazeModule {
+  private CommandEnvironment env;
+  private BuildRequest buildRequest;
+  private RemoteActionCache actionCache;
+  private RemoteWorkExecutor workExecutor;
+
+  public RemoteModule() {}
+
+  @Override
+  public Iterable<ActionContextProvider> getActionContextProviders() {
+    if (actionCache != null) {
+      return ImmutableList.<ActionContextProvider>of(
+          new RemoteActionContextProvider(env, buildRequest, actionCache, workExecutor));
+    }
+    return ImmutableList.<ActionContextProvider>of();
+  }
+
+  @Override
+  public void beforeCommand(Command command, CommandEnvironment env) {
+    this.env = env;
+    env.getEventBus().register(this);
+  }
+
+  @Override
+  public void afterCommand() {
+    this.env = null;
+    this.buildRequest = null;
+  }
+
+  @Subscribe
+  public void buildStarting(BuildStartingEvent event) {
+    buildRequest = event.getRequest();
+    RemoteOptions options = buildRequest.getOptions(RemoteOptions.class);
+
+    // Don't provide the remote spawn unless at least action cache is initialized.
+    if (actionCache == null && options.hazelcastNode != null) {
+      actionCache =
+          new MemcacheActionCache(
+              this.env.getRuntime().getExecRoot(),
+              options,
+              HazelcastCacheFactory.create(options));
+      // TODO(alpha): Initialize a RemoteWorkExecutor.
+    }
+  }
+
+  @Override
+  public Iterable<Class<? extends OptionsBase>> getCommandOptions(Command command) {
+    return command.builds()
+        ? ImmutableList.<Class<? extends OptionsBase>>of(RemoteOptions.class)
+        : ImmutableList.<Class<? extends OptionsBase>>of();
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/remote/RemoteOptions.java b/src/main/java/com/google/devtools/build/lib/remote/RemoteOptions.java
new file mode 100644
index 0000000000..933b2b1389
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/remote/RemoteOptions.java
@@ -0,0 +1,39 @@
+// Copyright 2016 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.remote;
+
+import com.google.devtools.common.options.Option;
+import com.google.devtools.common.options.OptionsBase;
+
+/**
+ * Options for remote execution and distributed caching.
+ */
+public final class RemoteOptions extends OptionsBase {
+  @Option(
+    name = "hazelcast_node",
+    defaultValue = "null",
+    category = "remote",
+    help = "A comma separated list of hostnames of hazelcast nodes. For client mode only."
+  )
+  public String hazelcastNode;
+
+  @Option(
+    name = "rest_worker_url",
+    defaultValue = "null",
+    category = "remote",
+    help = "URL for the REST worker."
+  )
+  public String restWorkerUrl;
+}
diff --git a/src/main/java/com/google/devtools/build/lib/remote/RemoteSpawnStrategy.java b/src/main/java/com/google/devtools/build/lib/remote/RemoteSpawnStrategy.java
new file mode 100644
index 0000000000..2001f759bb
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/remote/RemoteSpawnStrategy.java
@@ -0,0 +1,262 @@
+// Copyright 2016 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.remote;
+
+import com.google.common.collect.ImmutableMap;
+import com.google.common.hash.Hasher;
+import com.google.common.hash.Hashing;
+import com.google.common.util.concurrent.ListenableFuture;
+import com.google.devtools.build.lib.actions.ActionExecutionContext;
+import com.google.devtools.build.lib.actions.ActionInput;
+import com.google.devtools.build.lib.actions.ActionInputFileCache;
+import com.google.devtools.build.lib.actions.ActionInputHelper;
+import com.google.devtools.build.lib.actions.ActionMetadata;
+import com.google.devtools.build.lib.actions.ExecException;
+import com.google.devtools.build.lib.actions.ExecutionStrategy;
+import com.google.devtools.build.lib.actions.Executor;
+import com.google.devtools.build.lib.actions.Spawn;
+import com.google.devtools.build.lib.actions.SpawnActionContext;
+import com.google.devtools.build.lib.actions.UserExecException;
+import com.google.devtools.build.lib.events.Event;
+import com.google.devtools.build.lib.events.EventHandler;
+import com.google.devtools.build.lib.standalone.StandaloneSpawnStrategy;
+import com.google.devtools.build.lib.util.Preconditions;
+import com.google.devtools.build.lib.util.io.FileOutErr;
+import com.google.devtools.build.lib.vfs.Path;
+
+import java.io.IOException;
+import java.nio.charset.Charset;
+import java.util.Collection;
+import java.util.List;
+import java.util.Map;
+import java.util.concurrent.ExecutionException;
+import java.util.concurrent.TimeUnit;
+import java.util.concurrent.TimeoutException;
+
+/**
+ * Strategy that uses a distributed cache for sharing action input and output files.
+ * Optionally this strategy also support offloading the work to a remote worker.
+ */
+@ExecutionStrategy(
+  name = {"remote"},
+  contextType = SpawnActionContext.class
+)
+final class RemoteSpawnStrategy implements SpawnActionContext {
+  private final Path execRoot;
+  private final StandaloneSpawnStrategy standaloneStrategy;
+  private final RemoteActionCache remoteActionCache;
+  private final RemoteWorkExecutor remoteWorkExecutor;
+
+  RemoteSpawnStrategy(
+      Map<String, String> clientEnv,
+      Path execRoot,
+      RemoteOptions options,
+      boolean verboseFailures,
+      RemoteActionCache actionCache,
+      RemoteWorkExecutor workExecutor) {
+    this.execRoot = execRoot;
+    this.standaloneStrategy = new StandaloneSpawnStrategy(execRoot, verboseFailures);
+    this.remoteActionCache = actionCache;
+    this.remoteWorkExecutor = workExecutor;
+  }
+
+  /**
+   * Executes the given {@code spawn}.
+   */
+  @Override
+  public void exec(Spawn spawn, ActionExecutionContext actionExecutionContext)
+      throws ExecException {
+    if (!spawn.isRemotable()) {
+      standaloneStrategy.exec(spawn, actionExecutionContext);
+      return;
+    }
+
+    Executor executor = actionExecutionContext.getExecutor();
+    ActionMetadata actionMetadata = spawn.getResourceOwner();
+    ActionInputFileCache inputFileCache = actionExecutionContext.getActionInputFileCache();
+    EventHandler eventHandler = executor.getEventHandler();
+
+    // Compute a hash code to uniquely identify the action plus the action inputs.
+    Hasher hasher = Hashing.sha256().newHasher();
+
+    // TODO(alpha): The action key is usually computed using the path to the tool and the
+    // arguments. It does not take into account the content / version of the system tool (e.g. gcc).
+    // Either I put information about the system tools in the hash or assume tools are always
+    // checked in.
+    Preconditions.checkNotNull(actionMetadata.getKey());
+    hasher.putString(actionMetadata.getKey(), Charset.defaultCharset());
+
+    List<ActionInput> inputs =
+        ActionInputHelper.expandArtifacts(
+            spawn.getInputFiles(), actionExecutionContext.getArtifactExpander());
+    for (ActionInput input : inputs) {
+      hasher.putString(input.getExecPathString(), Charset.defaultCharset());
+      try {
+        // TODO(alpha): The digest from ActionInputFileCache is used to detect local file
+        // changes. It might not be sufficient to identify the input file globally in the
+        // remote action cache. Consider upgrading this to a better hash algorithm with
+        // less collision.
+        hasher.putBytes(inputFileCache.getDigest(input).toByteArray());
+      } catch (IOException e) {
+        throw new UserExecException("Failed to get digest for input.", e);
+      }
+    }
+
+    // Save the action output if found in the remote action cache.
+    String actionOutputKey = hasher.hash().toString();
+
+    // Timeout for running the remote spawn.
+    int timeout = 120;
+    String timeoutStr = spawn.getExecutionInfo().get("timeout");
+    if (timeoutStr != null) {
+      try {
+        timeout = Integer.parseInt(timeoutStr);
+      } catch (NumberFormatException e) {
+        throw new UserExecException("could not parse timeout: ", e);
+      }
+    }
+
+    try {
+      // Look up action cache using |actionOutputKey|. Reuse the action output if it is found.
+      if (writeActionOutput(spawn.getMnemonic(), actionOutputKey, eventHandler, true)) {
+        return;
+      }
+
+      FileOutErr outErr = actionExecutionContext.getFileOutErr();
+      if (executeWorkRemotely(
+          inputFileCache,
+          spawn.getMnemonic(),
+          actionOutputKey,
+          spawn.getArguments(),
+          inputs,
+          spawn.getEnvironment(),
+          spawn.getOutputFiles(),
+          timeout,
+          eventHandler,
+          outErr)) {
+        return;
+      }
+
+      // If nothing works then run spawn locally.
+      standaloneStrategy.exec(spawn, actionExecutionContext);
+      if (remoteActionCache != null) {
+        remoteActionCache.putActionOutput(actionOutputKey, spawn.getOutputFiles());
+      }
+    } catch (IOException e) {
+      throw new UserExecException("Unexpected IO error.", e);
+    } catch (UnsupportedOperationException e) {
+      eventHandler.handle(
+          Event.warn(spawn.getMnemonic() + " unsupported operation for action cache (" + e + ")"));
+    }
+  }
+
+  /**
+   * Submit work to execute remotely.
+   *
+   * @return True in case the action succeeded and all expected action outputs are found.
+   */
+  private boolean executeWorkRemotely(
+      ActionInputFileCache actionCache,
+      String mnemonic,
+      String actionOutputKey,
+      List<String> arguments,
+      List<ActionInput> inputs,
+      ImmutableMap<String, String> environment,
+      Collection<? extends ActionInput> outputs,
+      int timeout,
+      EventHandler eventHandler,
+      FileOutErr outErr)
+      throws IOException {
+    if (remoteWorkExecutor == null) {
+      return false;
+    }
+    try {
+      ListenableFuture<RemoteWorkExecutor.Response> future =
+          remoteWorkExecutor.submit(
+              execRoot,
+              actionCache,
+              actionOutputKey,
+              arguments,
+              inputs,
+              environment,
+              outputs,
+              timeout);
+      RemoteWorkExecutor.Response response = future.get(timeout, TimeUnit.SECONDS);
+      if (!response.success()) {
+        String exception = "";
+        if (!response.getException().isEmpty()) {
+          exception = " (" + response.getException() + ")";
+        }
+        eventHandler.handle(
+            Event.warn(
+                mnemonic + " failed to execute work remotely" + exception + ", running locally"));
+        return false;
+      }
+      if (response.getOut() != null) {
+        outErr.printOut(response.getOut());
+      }
+      if (response.getErr() != null) {
+        outErr.printErr(response.getErr());
+      }
+    } catch (ExecutionException e) {
+      eventHandler.handle(
+          Event.warn(mnemonic + " failed to execute work remotely (" + e + "), running locally"));
+      return false;
+    } catch (TimeoutException e) {
+      eventHandler.handle(
+          Event.warn(mnemonic + " timed out executing work remotely (" + e + "), running locally"));
+      return false;
+    } catch (InterruptedException e) {
+      Thread.currentThread().interrupt();
+      eventHandler.handle(Event.warn(mnemonic + " remote work interrupted (" + e + ")"));
+      return false;
+    } catch (WorkTooLargeException e) {
+      eventHandler.handle(Event.warn(mnemonic + " cannot be run remotely (" + e + ")"));
+      return false;
+    }
+    return writeActionOutput(mnemonic, actionOutputKey, eventHandler, false);
+  }
+
+  /**
+   * Saves the action output from cache. Returns true if all action outputs are found.
+   */
+  private boolean writeActionOutput(
+      String mnemonic,
+      String actionOutputKey,
+      EventHandler eventHandler,
+      boolean ignoreCacheNotFound)
+      throws IOException {
+    if (remoteActionCache == null) {
+      return false;
+    }
+    try {
+      remoteActionCache.writeActionOutput(actionOutputKey, execRoot);
+      Event.info(mnemonic + " reuse action outputs from cache");
+      return true;
+    } catch (CacheNotFoundException e) {
+      if (!ignoreCacheNotFound) {
+        eventHandler.handle(
+            Event.warn(mnemonic + " some cache entries cannot be found (" + e + ")"));
+      }
+    }
+    return false;
+  }
+
+  @Override
+  public boolean isRemotable(String mnemonic, boolean remotable) {
+    // Returning true here just helps to estimate the cost of this computation is zero.
+    return remotable;
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/remote/RemoteWorkExecutor.java b/src/main/java/com/google/devtools/build/lib/remote/RemoteWorkExecutor.java
new file mode 100644
index 0000000000..89e12cde55
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/remote/RemoteWorkExecutor.java
@@ -0,0 +1,83 @@
+// Copyright 2016 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.remote;
+
+import com.google.common.collect.ImmutableMap;
+import com.google.common.util.concurrent.ListenableFuture;
+import com.google.devtools.build.lib.actions.ActionInput;
+import com.google.devtools.build.lib.actions.ActionInputFileCache;
+import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadCompatible;
+import com.google.devtools.build.lib.vfs.Path;
+
+import java.io.IOException;
+import java.util.Collection;
+
+/**
+ * Interface for exeucting work remotely.
+ */
+@ThreadCompatible
+interface RemoteWorkExecutor {
+
+  /**
+   * The response of running a remote work.
+   */
+  class Response {
+    private final boolean success;
+    private final String out;
+    private final String err;
+    private final String exception;
+
+    boolean success() {
+      return success;
+    }
+
+    String getOut() {
+      return out;
+    }
+
+    String getErr() {
+      return err;
+    }
+
+    String getException() {
+      return exception;
+    }
+
+    Response(boolean success, String out, String err, String exception) {
+      this.success = success;
+      this.out = out;
+      this.err = err;
+      this.exception = exception;
+    }
+  }
+
+  /**
+   * Submit the work to this work executor.
+   * The output of running this action should be written to {@link RemoteActionCache} indexed
+   * by |actionOutputKey|.
+   *
+   * Returns a future for the response of this work request.
+   */
+  ListenableFuture<Response> submit(
+      Path execRoot,
+      ActionInputFileCache cache,
+      String actionOutputKey,
+      Collection<String> arguments,
+      Collection<ActionInput> inputs,
+      ImmutableMap<String, String> environment,
+      Collection<? extends ActionInput> outputs,
+      int timeout)
+      throws IOException, WorkTooLargeException;
+}
diff --git a/src/main/java/com/google/devtools/build/lib/remote/WorkTooLargeException.java b/src/main/java/com/google/devtools/build/lib/remote/WorkTooLargeException.java
new file mode 100644
index 0000000000..d112ebe199
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/remote/WorkTooLargeException.java
@@ -0,0 +1,32 @@
+// Copyright 2016 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.remote;
+
+/**
+ * An exception that indicates the work is too large to run remotely.
+ */
+final class WorkTooLargeException extends RuntimeException {
+  WorkTooLargeException() {
+    super();
+  }
+
+  WorkTooLargeException(String message) {
+    super(message);
+  }
+
+  WorkTooLargeException(String message, Throwable cause) {
+    super(message, cause);
+  }
+}
diff --git a/src/main/protobuf/BUILD b/src/main/protobuf/BUILD
index 0fb49e5b22..b97fcf1f3c 100644
--- a/src/main/protobuf/BUILD
+++ b/src/main/protobuf/BUILD
@@ -17,6 +17,7 @@ FILES = [
     "xcodegen",
     "worker_protocol",
     "invocation_policy",
+    "remote_protocol",
 ]
 
 [proto_java_library(
diff --git a/src/main/protobuf/remote_protocol.proto b/src/main/protobuf/remote_protocol.proto
new file mode 100644
index 0000000000..a9d476d320
--- /dev/null
+++ b/src/main/protobuf/remote_protocol.proto
@@ -0,0 +1,88 @@
+// Copyright 2015 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.
+
+syntax = "proto3";
+
+package build.remote;
+
+option java_package = "com.google.devtools.build.lib.remote";
+
+// A message for cache entry.
+message CacheEntry {
+  // A list of files stored in this cache entry.
+  repeated FileEntry files = 1;
+
+  // A blob for data that is a chunk of a file.
+  bytes file_content = 2;
+}
+
+// A message for storing a file in cache.
+message FileEntry {
+  // The path in the file system where to read this input artifact from. This is
+  // either a path relative to the execution root (the worker process is
+  // launched with the working directory set to the execution root), or an
+  // absolute path.
+  string path = 1;
+
+  // The cache key to locate the file content. This key is usually generated
+  // from
+  // the content of the file such that different keys means the file content are
+  // different.
+  string content_key = 2;
+
+  // Whether the file is an executable.
+  bool executable = 3;
+
+  // TODO(alpha): For large files we need to break down into chunks to store
+  // in the cache. For that case we need a index for the chunks of the file.
+}
+
+// A message for running a command remotely.
+message RemoteWorkRequest {
+  // The key for writing the output of this work request.
+  string output_key = 1;
+
+  // The arguments for running the command. The command itself is in
+  // arguments[0].
+  repeated string arguments = 2;
+
+  // The list of input files to this work request.
+  repeated FileEntry input_files = 3;
+
+  // A map of environment variables for this command.
+  map<string, string> environment = 4;
+
+  // The list of expected output files to this work request.
+  // The content keys for these entries will be empty since the files don't
+  // exist yet.
+  repeated FileEntry output_files = 5;
+
+  // Timeout for running this command.
+  int32 timeout = 6;
+}
+
+// A message for a work response.
+message RemoteWorkResponse {
+  // True if the work was successful.
+  bool success = 1;
+
+  // String from stdout of running the work.
+  string out = 2;
+
+  // String from stderr of running the work.
+  string err = 3;
+
+  // String for the exception when running this work.
+  string exception = 4;
+}
\ No newline at end of file
diff --git a/third_party/BUILD b/third_party/BUILD
index 09fecf3967..9449cc94f0 100644
--- a/third_party/BUILD
+++ b/third_party/BUILD
@@ -209,6 +209,14 @@ java_import(
 )
 
 java_import(
+    name = "hazelcast",
+    jars = [
+        "hazelcast/hazelcast-3.5.4.jar",
+        "hazelcast/hazelcast-client-3.5.4.jar",
+    ],
+)
+
+java_import(
     name = "error_prone",
     jars = [
         "error_prone/error_prone_core-2.0.9-20160129.jar",
diff --git a/third_party/README.md b/third_party/README.md
index 7e72f70087..b0dd006698 100644
--- a/third_party/README.md
+++ b/third_party/README.md
@@ -260,6 +260,12 @@ a minimal set of extra dependencies.
 * License: MIT license
 
 
+## [hazelcast](http://hazelcast.org/)
+
+* Version: 3.5.4
+* License: Apache License 2.0
+
+
 # Testing
 
 ## [hamcrest](https://code.google.com/p/hamcrest/)