diff --git a/src/resultstore_streamer.cc b/src/resultstore_streamer.cc
index b23ffbf..097f18b 100644
--- a/src/resultstore_streamer.cc
+++ b/src/resultstore_streamer.cc
@@ -189,6 +189,14 @@
 }
 */
 
+struct ResultStoreStreamer::EdgeData {
+  // mangled string used in UploadRequests
+  std::string action_id;
+
+  // TODO: consider caching the entire UploadRequest proto,
+  // since the majority of fields are reused over the action's lifetime.
+};
+
 ResultStoreStreamer::ResultStoreStreamer(
     const std::vector<std::string>& ninja_command,
     const std::string& config_string, const BuildMetadataMap& metadata,
@@ -268,12 +276,30 @@
 }
 
 // Get an action_id from an Edge.
+// From the proto spec:
+// It can be any string of up to 512 alphanumeric characters [a-zA-Z0-9_-],
+// except for the reserved id '-'.
 static std::string edge_action_id(const Edge* edge) {
   // Use the primary output?
   // assert that there is at least one output node
   return edge->outputs_.front()->path();
 }
 
+const ResultStoreStreamer::EdgeData&
+ResultStoreStreamer::GetEdgeData(const Edge* edge) {
+  // TODO: replace this with try_emplace once C++17 is supported
+  const auto p = edge_data_.emplace(edge, EdgeData{});
+  EdgeData& value = p.first->second;
+  if (p.second) {
+    // newly inserted, so compute new values
+    value.action_id = edge_action_id(edge);
+    // mangle path separator into acceptable characters
+    StringSubstituteCharWithString(&value.action_id, '.', "--");
+    StringSubstituteCharWithString(&value.action_id, '/', "--");
+  }  // else already cached
+  return value;
+}
+
 void ResultStoreStreamer::BuildEdgeStarted(const Edge* edge,
                                           int64_t start_time_millis) {
   if (out_ == nullptr) return;
@@ -283,11 +309,10 @@
 
   rspb::Action* action = req.mutable_action();
 
-  auto* id = action->mutable_id();
-  id->set_invocation_id(invocation_id());
+  auto* id = req.mutable_id();
   id->set_target_id(kDefaultTargetName);
   id->set_configuration_id(kDefaultConfigurationName);
-  const std::string action_id(edge_action_id(edge));  // needs to be url_encoded
+  const std::string& action_id = GetEdgeData(edge).action_id;
   id->set_action_id(action_id);
 
   action->set_name(
@@ -308,6 +333,7 @@
   rspb::StatusAttributes* status_attrs = action->mutable_status_attributes();
   status_attrs->set_status(rspb::Status::BUILDING);
 
+  /* TODO: figure out how to use deps properly.
   // auto* deps = action->mutable_action_dependencies();
   // iterate over edge inputs
   for (const auto* input : edge->inputs_) {
@@ -320,6 +346,7 @@
 
     // dep.set_label(...); // description?
   }
+  */
 
   // auto* properties = action->mutable_properties();
 
@@ -337,7 +364,7 @@
     ExitStatus exit_code, const std::string& output) {
   if (out_ == nullptr) return;
 
-  const std::string action_id(edge_action_id(edge));
+  const std::string& action_id = GetEdgeData(edge).action_id;
 
   {
     // use initial_invocation_ in UploadRequest for batching
@@ -346,8 +373,7 @@
     req.set_upload_operation(rspb::UploadRequest::UploadOperation::UPDATE);
     rspb::Action* action = req.mutable_action();
 
-    auto* id = action->mutable_id();
-    id->set_invocation_id(invocation_id());
+    auto* id = req.mutable_id();
     id->set_target_id(kDefaultTargetName);
     id->set_configuration_id(kDefaultConfigurationName);
     id->set_action_id(action_id);
@@ -373,8 +399,7 @@
     req.set_upload_operation(rspb::UploadRequest::UploadOperation::FINALIZE);
     rspb::Action* action = req.mutable_action();
 
-    auto* id = action->mutable_id();
-    id->set_invocation_id(invocation_id());
+    auto* id = req.mutable_id();
     id->set_target_id(kDefaultTargetName);
     id->set_configuration_id(kDefaultConfigurationName);
     id->set_action_id(action_id);
@@ -410,8 +435,7 @@
 
     rspb::Configuration* configuration = req.mutable_configuration();
 
-    auto* id = configuration->mutable_id();
-    id->set_invocation_id(invocation_id());
+    auto* id = req.mutable_id();
     id->set_configuration_id(kDefaultConfigurationName);
 
     // path-formatted resource name
@@ -446,8 +470,7 @@
 
     rspb::Target* target = req.mutable_target();
 
-    auto* id = target->mutable_id();
-    id->set_invocation_id(invocation_id());
+    auto* id = req.mutable_id();
     id->set_target_id(kDefaultTargetName);
 
     // path-formatted resource name
@@ -483,10 +506,9 @@
 
     rspb::ConfiguredTarget* ctarget = req.mutable_configured_target();
 
-    auto* id = ctarget->mutable_id();
-    id->set_invocation_id(invocation_id());
+    auto* id = req.mutable_id();
     id->set_target_id(kDefaultTargetName);
-    id->set_configuration_id(kDefaultTargetName);
+    id->set_configuration_id(kDefaultConfigurationName);
 
     // path-formatted resource name
     ctarget->set_name(StringFormat(
@@ -532,7 +554,7 @@
     update_mask->add_paths("timing.duration");
 
     rspb::ConfiguredTarget* ctarget = req.mutable_configured_target();
-    auto* id = ctarget->mutable_id();
+    auto* id = req.mutable_id();
     id->set_target_id(kDefaultTargetName);
     id->set_configuration_id(kDefaultConfigurationName);
 
@@ -566,7 +588,7 @@
     update_mask->add_paths("timing.duration");
 
     rspb::Target* target = req.mutable_target();
-    auto* id = target->mutable_id();
+    auto* id = req.mutable_id();
     id->set_target_id(kDefaultTargetName);
 
     millis_to_duration(common_duration,
@@ -597,7 +619,7 @@
     update_mask->add_paths("status_attributes");
 
     rspb::Configuration* config = req.mutable_configuration();
-    auto* id = config->mutable_id();
+    auto* id = req.mutable_id();
     id->set_configuration_id(kDefaultConfigurationName);
 
     config->mutable_status_attributes()->set_status(common_status);
diff --git a/src/resultstore_streamer.h b/src/resultstore_streamer.h
index d63b63a..34bf301 100644
--- a/src/resultstore_streamer.h
+++ b/src/resultstore_streamer.h
@@ -84,6 +84,10 @@
   typedef ::rs::google::devtools::resultstore::v2::UploadRequest UploadRequest;
   void PostRequest(const UploadRequest&);
 
+  struct EdgeData;
+
+  const EdgeData& GetEdgeData(const Edge*);
+
  private:
   /// Original ninja invocation command.
   std::vector<std::string> ninja_command_;
@@ -104,6 +108,9 @@
   // Output stream (should be configured un-buffered)
   // Not owned, so the stream object should outlive this object.
   OutputStream* out_ = nullptr;
+
+  // Cache of edge-associated values, to avoid re-computation.
+  std::map<const Edge*, EdgeData> edge_data_;
 };
 
 #endif // NINJA_RESULTSTORE_STREAMER_H_