diff --git a/quiche/quic/masque/masque_client_session.cc b/quiche/quic/masque/masque_client_session.cc
index b9efaf9..6d3d74e 100644
--- a/quiche/quic/masque/masque_client_session.cc
+++ b/quiche/quic/masque/masque_client_session.cc
@@ -383,6 +383,9 @@
                 << " compressed with stream ID " << connect_udp->stream()->id()
                 << " and got message status "
                 << MessageStatusToString(message_status);
+  QUIC_DVLOG(2) << "Contents of outgoing HTTP Datagram of length "
+                << http_payload.size() << ":" << std::endl
+                << quiche::QuicheTextUtils::HexDump(http_payload);
 }
 
 void MasqueClientSession::CloseConnectUdpStream(
diff --git a/quiche/quic/masque/masque_server_backend.cc b/quiche/quic/masque/masque_server_backend.cc
index 83e461f..ce5ab57 100644
--- a/quiche/quic/masque/masque_server_backend.cc
+++ b/quiche/quic/masque/masque_server_backend.cc
@@ -81,16 +81,23 @@
     }
   }
 
-  auto it = backend_client_states_.find(request_handler->connection_id());
-  if (it == backend_client_states_.end()) {
+  BackendClient* backend_client = nullptr;
+  std::vector<std::unique_ptr<QuicBackendResponse>>* responses = nullptr;
+  for (BackendClientState& state : backend_client_states_) {
+    if (state.backend_client->GetQuicSpdySession() !=
+        request_handler->GetStream()->spdy_session()) {
+      continue;
+    }
+    backend_client = state.backend_client;
+    responses = &state.responses;
+  }
+  if (backend_client == nullptr) {
     QUIC_LOG(ERROR) << "Could not find backend client for "
                     << request_handler->connection_id()
                     << request_headers.DebugString();
     return false;
   }
 
-  BackendClient* backend_client = it->second.backend_client;
-
   std::unique_ptr<QuicBackendResponse> response =
       backend_client->HandleMasqueRequest(request_headers, request_handler);
   if (response == nullptr) {
@@ -105,7 +112,7 @@
                   << request_headers.DebugString();
 
   request_handler->OnResponseBackendComplete(response.get());
-  it->second.responses.emplace_back(std::move(response));
+  responses->emplace_back(std::move(response));
 
   return true;
 }
@@ -143,19 +150,23 @@
   QuicMemoryCacheBackend::CloseBackendResponseStream(request_handler);
 }
 
-void MasqueServerBackend::RegisterBackendClient(QuicConnectionId connection_id,
-                                                BackendClient* backend_client) {
-  QUIC_DLOG(INFO) << "Registering backend client for " << connection_id;
-  QUIC_BUG_IF(quic_bug_12005_1, backend_client_states_.find(connection_id) !=
-                                    backend_client_states_.end())
-      << connection_id << " already in backend clients map";
-  backend_client_states_[connection_id] =
-      BackendClientState{backend_client, {}};
+void MasqueServerBackend::RegisterBackendClient(BackendClient* backend_client) {
+  QUIC_DLOG(INFO) << "Registering backend client for "
+                  << backend_client->GetQuicSpdySession()->connection_id();
+  backend_client_states_.push_back(BackendClientState{backend_client, {}});
 }
 
-void MasqueServerBackend::RemoveBackendClient(QuicConnectionId connection_id) {
-  QUIC_DLOG(INFO) << "Removing backend client for " << connection_id;
-  backend_client_states_.erase(connection_id);
+void MasqueServerBackend::RemoveBackendClient(BackendClient* backend_client) {
+  QUIC_DLOG(INFO) << "Removing backend client for "
+                  << backend_client->GetQuicSpdySession()->connection_id();
+  backend_client_states_.erase(
+      std::remove_if(backend_client_states_.begin(),
+                     backend_client_states_.end(),
+                     [backend_client](BackendClientState& state) {
+                       return state.backend_client->GetQuicSpdySession() ==
+                              backend_client->GetQuicSpdySession();
+                     }),
+      backend_client_states_.end());
 }
 
 QuicIpAddress MasqueServerBackend::GetNextClientIpAddress() {
diff --git a/quiche/quic/masque/masque_server_backend.h b/quiche/quic/masque/masque_server_backend.h
index d097c23..7735f2b 100644
--- a/quiche/quic/masque/masque_server_backend.h
+++ b/quiche/quic/masque/masque_server_backend.h
@@ -14,6 +14,7 @@
 #include "absl/container/flat_hash_map.h"
 #include "absl/strings/string_view.h"
 #include "openssl/curve25519.h"
+#include "quiche/quic/core/http/quic_spdy_session.h"
 #include "quiche/quic/core/quic_connection_id.h"
 #include "quiche/quic/masque/masque_utils.h"
 #include "quiche/quic/platform/api/quic_export.h"
@@ -36,6 +37,7 @@
     virtual std::unique_ptr<QuicBackendResponse> HandleMasqueRequest(
         const quiche::HttpHeaderBlock& request_headers,
         QuicSimpleServerBackend::RequestHandler* request_handler) = 0;
+    virtual QuicSpdySession* GetQuicSpdySession() = 0;
     virtual ~BackendClient() = default;
   };
 
@@ -59,11 +61,10 @@
       QuicSimpleServerBackend::RequestHandler* request_handler) override;
 
   // Register backend client that can handle MASQUE requests.
-  void RegisterBackendClient(QuicConnectionId connection_id,
-                             BackendClient* backend_client);
+  void RegisterBackendClient(BackendClient* backend_client);
 
   // Unregister backend client.
-  void RemoveBackendClient(QuicConnectionId connection_id);
+  void RemoveBackendClient(BackendClient* backend_client);
 
   // Provides a unique client IP address for each CONNECT-IP client.
   QuicIpAddress GetNextClientIpAddress();
@@ -106,9 +107,7 @@
     BackendClient* backend_client;
     std::vector<std::unique_ptr<QuicBackendResponse>> responses;
   };
-  absl::flat_hash_map<QuicConnectionId, BackendClientState,
-                      QuicConnectionIdHash>
-      backend_client_states_;
+  std::vector<BackendClientState> backend_client_states_;
   uint8_t connect_ip_next_client_ip_[4];
   struct QUIC_NO_EXPORT ConcealedAuthCredential {
     std::string key_id;
diff --git a/quiche/quic/masque/masque_server_session.cc b/quiche/quic/masque/masque_server_session.cc
index c0b9911..4b815d6 100644
--- a/quiche/quic/masque/masque_server_session.cc
+++ b/quiche/quic/masque/masque_server_session.cc
@@ -163,7 +163,7 @@
   // TODO(b/181606597) Remove this workaround once we use PMTUD.
   connection->SetMaxPacketLength(kDefaultMaxPacketSizeForTunnels);
 
-  masque_server_backend_->RegisterBackendClient(connection_id(), this);
+  masque_server_backend_->RegisterBackendClient(this);
   QUICHE_DCHECK_NE(event_loop_, nullptr);
 
   // We don't currently use `masque_mode_` but will in the future. To silence
@@ -185,7 +185,7 @@
     const QuicConnectionCloseFrame& frame, ConnectionCloseSource source) {
   QuicSimpleServerSession::OnConnectionClosed(frame, source);
   QUIC_DLOG(INFO) << "Closing connection for " << connection_id();
-  masque_server_backend_->RemoveBackendClient(connection_id());
+  masque_server_backend_->RemoveBackendClient(this);
   // Clearing this state will close all sockets.
   connect_udp_server_states_.clear();
 }
@@ -699,6 +699,8 @@
   return response;
 }
 
+QuicSpdySession* MasqueServerSession::GetQuicSpdySession() { return this; }
+
 void MasqueServerSession::OnSocketEvent(QuicEventLoop* /*event_loop*/,
                                         QuicUdpSocketFd fd,
                                         QuicSocketEventMask events) {
diff --git a/quiche/quic/masque/masque_server_session.h b/quiche/quic/masque/masque_server_session.h
index 5f11f2d..5e8dc70 100644
--- a/quiche/quic/masque/masque_server_session.h
+++ b/quiche/quic/masque/masque_server_session.h
@@ -76,6 +76,7 @@
   std::unique_ptr<QuicBackendResponse> HandleMasqueRequest(
       const quiche::HttpHeaderBlock& request_headers,
       QuicSimpleServerBackend::RequestHandler* request_handler) override;
+  QuicSpdySession* GetQuicSpdySession() override;
 
   // From QuicSocketEventListener.
   void OnSocketEvent(QuicEventLoop* event_loop, QuicUdpSocketFd fd,