You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@impala.apache.org by jo...@apache.org on 2023/06/21 05:21:44 UTC

[impala] 01/04: IMPALA-12150: Use protocol version to isolate cluster components

This is an automated email from the ASF dual-hosted git repository.

joemcdonnell pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/impala.git

commit a82830896b590dd7a445f8f7e91f25356a7dd3c2
Author: wzhou-code <wz...@cloudera.com>
AuthorDate: Wed May 10 17:22:34 2023 -0700

    IMPALA-12150: Use protocol version to isolate cluster components
    
    Some Thrift request/response structs in CatalogService were changed to
    add new variables in the middle, which caused cross version
    incompatibility issue for CatalogService.
    
    Impala cluster membership is managed by the statestore. During upgrade
    scenarios where different versions of Impala daemons are upgraded one
    at a time, the upgraded daemons have incompatible message formats.
    Even through protocol versions numbers were already defined for
    Statestore and Catalog Services, they were not used. The Statestore and
    Catalog server did not check the protocol version in the requests, which
    allowed incompatible Impala daemons to join one cluster. This causes
    unexpected query failures during rolling upgrade.
    
    We need a way to detect this and enforce that some rules are followed:
     - Statestore refuses the registration requests from incompatible
       subscribers.
     - Catalog server refuses the requests from incompatible clients.
     - Scheduler assigns tasks to a group of compatible executors.
    
    This patch isolate Impala daemons into separate clusters based on
    protocol versions of Statestore service to prevent incompatible Impala
    daemons from communicating with each other. It covers the Thrift RPC
    communications between catalogd and coordinators, and communication
    between statestore and its subscribers (executor, coordinators,
    catalogd and admissiond). This change should work for future upgrade.
    
    Following changes were made:
     - Bump StatestoreServiceVersion and CatalogServiceVersion to V2 for
       all requests of Statestore and Catalog services.
     - Update the request and response structs in CatalogService to ensure
       each Thrift request struct has protocol version and each Thrift
       response struct has returned status.
     - Update the request and response struct in StatestoreService to
       ensure each Thrift request struct has protocol version and each
       Thrift response struct has returned status.
     - Add subscriber type so that statestore could distinguish different
       types of subscribers.
     - Statestore checks protocol version for registration requests from
       subscribers. It refuses the requests with incompatible version.
     - Catalog server checks protocol version for Catalog service APIs, and
       returns error for requests with incompatible version.
     - Catalog daemon sends its address and the protocol version of Catalog
       service when it registers to statestore, statestore forwards the
       address and the protocol version of Catalog service to all
       subscribers during registration.
     - Add UpdateCatalogd API for StatestoreSubscriber service so that the
       coordinators could receive the address and the protocol version of
       Catalog service from statestore if the coordinators register to
       statestore before catalog daemon.
     - Add GetProtocolVersion API for Statestore service so that the
       subscribers can check the protocol version of statestore before
       calling RegisterSubscriber API.
     - Add starting flag tolerate_statestore_startup_delay. It is off by
       default. When it's enabled, the subscriber is able to tolerate
       the delay of the statestore's availability. The subscriber's
       process will not exit if it cannot register with the specified
       statestore on startup. But instead it enter into Recovery mode,
       it will loop, sleep and retry till it successfully register with
       the statestore. This flag should be enabled during rolling upgrade.
    
    CatalogServiceVersion is defined in CatalogService.thrift. In future,
    if we make non backward version compatible changes in the request or
    response structures for CatalogService APIs, we need to bump the
    protocol version of Catalog service.
    StatestoreServiceVersion is defined in StatestoreService.thrift.
    Similarly if we make non backward version compatible changes in the
    request or response structures for StatestoreService APIs, we need
    to bump the protocol version of Statestore service.
    
    Message formats for KRPC communications between coordinators and
    executors, and between admissiond and coordinators are defined
    in proto files under common/protobuf. If we make non backward version
    compatible changes in these structures, we need to bump the
    protocol version of Statestore service.
    
    Testing:
     - Added end-to-end unit tests.
     - Passed the core tests.
     - Ran manual test to verify old version of executors cannot register
       with new version of statestore, and new version of executors cannot
       register with old version of statestore.
    
    Change-Id: If61506dab38c4d1c50419c1b3f7bc4f9ee3676bc
    Reviewed-on: http://gerrit.cloudera.org:8080/19959
    Reviewed-by: Andrew Sherman <as...@cloudera.com>
    Tested-by: Impala Public Jenkins <im...@cloudera.com>
---
 be/src/catalog/catalog-server.cc                   |  72 ++-
 be/src/catalog/catalog-server.h                    |  16 +-
 be/src/common/global-flags.cc                      |   9 +
 be/src/exec/catalog-op-executor.cc                 |  35 +-
 be/src/rpc/thrift-server-test.cc                   |   3 +
 be/src/runtime/exec-env.cc                         |  71 ++-
 be/src/runtime/exec-env.h                          |  28 ++
 be/src/scheduling/admissiond-env.cc                |   3 +-
 be/src/service/client-request-state.cc             |  14 +-
 be/src/service/impala-server.cc                    |  10 +-
 be/src/service/impala-server.h                     |   4 +
 .../statestore/statestore-service-client-wrapper.h |   8 +
 be/src/statestore/statestore-subscriber-catalog.h  |  61 +++
 .../statestore-subscriber-client-wrapper.h         |   8 +
 be/src/statestore/statestore-subscriber.cc         | 527 ++++++++++++++++-----
 be/src/statestore/statestore-subscriber.h          | 418 ++++++++++------
 be/src/statestore/statestore-test.cc               |   9 +-
 be/src/statestore/statestore.cc                    | 240 +++++++++-
 be/src/statestore/statestore.h                     | 118 ++++-
 common/thrift/CatalogService.thrift                |  31 +-
 common/thrift/StatestoreService.thrift             | 113 ++++-
 common/thrift/generate_error_codes.py              |  10 +-
 common/thrift/metrics.json                         |  68 ++-
 .../impala/catalog/ImpaladTableUsageTracker.java   |   4 +-
 .../catalog_service/test_catalog_service_client.py |   8 +
 tests/custom_cluster/test_custom_statestore.py     | 205 +++++++-
 tests/custom_cluster/test_services_rpc_errors.py   |  11 +
 tests/statestore/test_statestore.py                |   5 +-
 28 files changed, 1748 insertions(+), 361 deletions(-)

diff --git a/be/src/catalog/catalog-server.cc b/be/src/catalog/catalog-server.cc
index cb31bc0d2..2da354573 100644
--- a/be/src/catalog/catalog-server.cc
+++ b/be/src/catalog/catalog-server.cc
@@ -176,7 +176,10 @@ class CatalogServiceThriftIf : public CatalogServiceIf {
   // Executes a TDdlExecRequest and returns details on the result of the operation.
   void ExecDdl(TDdlExecResponse& resp, const TDdlExecRequest& req) override {
     VLOG_RPC << "ExecDdl(): request=" << ThriftDebugString(req);
-    Status status = catalog_server_->catalog()->ExecDdl(req, &resp);
+    Status status = CheckProtocolVersion(req.protocol_version);
+    if (status.ok()) {
+      status = catalog_server_->catalog()->ExecDdl(req, &resp);
+    }
     if (!status.ok()) LOG(ERROR) << status.GetDetail();
     TStatus thrift_status;
     status.ToThrift(&thrift_status);
@@ -189,7 +192,10 @@ class CatalogServiceThriftIf : public CatalogServiceIf {
       override {
     VLOG_RPC << "ResetMetadata(): request=" << ThriftDebugString(req);
     DebugActionNoFail(FLAGS_debug_actions, "RESET_METADATA_DELAY");
-    Status status = catalog_server_->catalog()->ResetMetadata(req, &resp);
+    Status status = CheckProtocolVersion(req.protocol_version);
+    if (status.ok()) {
+      status = catalog_server_->catalog()->ResetMetadata(req, &resp);
+    }
     if (!status.ok()) LOG(ERROR) << status.GetDetail();
     TStatus thrift_status;
     status.ToThrift(&thrift_status);
@@ -202,7 +208,10 @@ class CatalogServiceThriftIf : public CatalogServiceIf {
   void UpdateCatalog(TUpdateCatalogResponse& resp, const TUpdateCatalogRequest& req)
       override {
     VLOG_RPC << "UpdateCatalog(): request=" << ThriftDebugString(req);
-    Status status = catalog_server_->catalog()->UpdateCatalog(req, &resp);
+    Status status = CheckProtocolVersion(req.protocol_version);
+    if (status.ok()) {
+      status = catalog_server_->catalog()->UpdateCatalog(req, &resp);
+    }
     if (!status.ok()) LOG(ERROR) << status.GetDetail();
     TStatus thrift_status;
     status.ToThrift(&thrift_status);
@@ -215,7 +224,10 @@ class CatalogServiceThriftIf : public CatalogServiceIf {
   void GetFunctions(TGetFunctionsResponse& resp, const TGetFunctionsRequest& req)
       override {
     VLOG_RPC << "GetFunctions(): request=" << ThriftDebugString(req);
-    Status status = catalog_server_->catalog()->GetFunctions(req, &resp);
+    Status status = CheckProtocolVersion(req.protocol_version);
+    if (status.ok()) {
+      status = catalog_server_->catalog()->GetFunctions(req, &resp);
+    }
     if (!status.ok()) LOG(ERROR) << status.GetDetail();
     TStatus thrift_status;
     status.ToThrift(&thrift_status);
@@ -227,9 +239,15 @@ class CatalogServiceThriftIf : public CatalogServiceIf {
   void GetCatalogObject(TGetCatalogObjectResponse& resp,
       const TGetCatalogObjectRequest& req) override {
     VLOG_RPC << "GetCatalogObject(): request=" << ThriftDebugString(req);
-    Status status = catalog_server_->catalog()->GetCatalogObject(req.object_desc,
-        &resp.catalog_object);
+    Status status = CheckProtocolVersion(req.protocol_version);
+    if (status.ok()) {
+      status = catalog_server_->catalog()->GetCatalogObject(
+          req.object_desc, &resp.catalog_object);
+    }
     if (!status.ok()) LOG(ERROR) << status.GetDetail();
+    TStatus thrift_status;
+    status.ToThrift(&thrift_status);
+    resp.__set_status(thrift_status);
     VLOG_RPC << "GetCatalogObject(): response=" << ThriftDebugStringNoThrow(resp);
   }
 
@@ -243,7 +261,10 @@ class CatalogServiceThriftIf : public CatalogServiceIf {
     // so a heavy query workload against a table undergoing a slow refresh doesn't
     // end up taking down the catalog by creating thousands of threads.
     VLOG_RPC << "GetPartialCatalogObject(): request=" << ThriftDebugString(req);
-    Status status = catalog_server_->catalog()->GetPartialCatalogObject(req, &resp);
+    Status status = CheckProtocolVersion(req.protocol_version);
+    if (status.ok()) {
+      status = catalog_server_->catalog()->GetPartialCatalogObject(req, &resp);
+    }
     if (!status.ok()) LOG(ERROR) << status.GetDetail();
     TStatus thrift_status;
     status.ToThrift(&thrift_status);
@@ -254,7 +275,10 @@ class CatalogServiceThriftIf : public CatalogServiceIf {
   void GetPartitionStats(TGetPartitionStatsResponse& resp,
       const TGetPartitionStatsRequest& req) override {
     VLOG_RPC << "GetPartitionStats(): request=" << ThriftDebugString(req);
-    Status status = catalog_server_->catalog()->GetPartitionStats(req, &resp);
+    Status status = CheckProtocolVersion(req.protocol_version);
+    if (status.ok()) {
+      status = catalog_server_->catalog()->GetPartitionStats(req, &resp);
+    }
     if (!status.ok()) LOG(ERROR) << status.GetDetail();
     TStatus thrift_status;
     status.ToThrift(&thrift_status);
@@ -268,7 +292,10 @@ class CatalogServiceThriftIf : public CatalogServiceIf {
   void PrioritizeLoad(TPrioritizeLoadResponse& resp, const TPrioritizeLoadRequest& req)
       override {
     VLOG_RPC << "PrioritizeLoad(): request=" << ThriftDebugString(req);
-    Status status = catalog_server_->catalog()->PrioritizeLoad(req);
+    Status status = CheckProtocolVersion(req.protocol_version);
+    if (status.ok()) {
+      status = catalog_server_->catalog()->PrioritizeLoad(req);
+    }
     if (!status.ok()) LOG(ERROR) << status.GetDetail();
     TStatus thrift_status;
     status.ToThrift(&thrift_status);
@@ -279,16 +306,33 @@ class CatalogServiceThriftIf : public CatalogServiceIf {
   void UpdateTableUsage(TUpdateTableUsageResponse& resp,
       const TUpdateTableUsageRequest& req) override {
     VLOG_RPC << "UpdateTableUsage(): request=" << ThriftDebugString(req);
-    Status status = catalog_server_->catalog()->UpdateTableUsage(req);
+    Status status = CheckProtocolVersion(req.protocol_version);
+    if (status.ok()) {
+      status = catalog_server_->catalog()->UpdateTableUsage(req);
+    }
     if (!status.ok()) LOG(WARNING) << status.GetDetail();
+    TStatus thrift_status;
+    status.ToThrift(&thrift_status);
+    resp.__set_status(thrift_status);
+    VLOG_RPC << "UpdateTableUsage(): response.status=" << resp.status;
   }
 
  private:
   CatalogServer* catalog_server_;
+
+  Status CheckProtocolVersion(CatalogServiceVersion::type client_version) {
+    Status status = Status::OK();
+    if (client_version < catalog_server_->GetProtocolVersion()) {
+      status = Status(TErrorCode::CATALOG_INCOMPATIBLE_PROTOCOL, client_version + 1,
+          catalog_server_->GetProtocolVersion() + 1);
+    }
+    return status;
+  }
 };
 
 CatalogServer::CatalogServer(MetricGroup* metrics)
-  : thrift_iface_(new CatalogServiceThriftIf(this)),
+  : protocol_version_(CatalogServiceVersion::V2),
+    thrift_iface_(new CatalogServiceThriftIf(this)),
     thrift_serializer_(FLAGS_compact_catalog_topic), metrics_(metrics),
     topic_updates_ready_(false), last_sent_catalog_version_(0L),
     catalog_objects_max_version_(0L) {
@@ -319,9 +363,10 @@ Status CatalogServer::Start() {
   RETURN_IF_ERROR(Thread::Create("catalog-server", "catalog-metrics-refresh-thread",
       &CatalogServer::RefreshMetrics, this, &catalog_metrics_refresh_thread_));
 
-  statestore_subscriber_.reset(new StatestoreSubscriber(
+  statestore_subscriber_.reset(new StatestoreSubscriberCatalog(
      Substitute("catalog-server@$0", TNetworkAddressToString(server_address)),
-     subscriber_address, statestore_address, metrics_));
+     subscriber_address, statestore_address, metrics_, protocol_version_,
+     server_address));
 
   StatestoreSubscriber::UpdateCallback cb =
       bind<void>(mem_fn(&CatalogServer::UpdateCatalogTopicCallback), this, _1, _2);
@@ -337,6 +382,7 @@ Status CatalogServer::Start() {
     status.AddDetail("CatalogService failed to start");
     return status;
   }
+
   RETURN_IF_ERROR(statestore_subscriber_->Start());
 
   // Notify the thread to start for the first time.
diff --git a/be/src/catalog/catalog-server.h b/be/src/catalog/catalog-server.h
index 605b41bc0..9abe9f8d6 100644
--- a/be/src/catalog/catalog-server.h
+++ b/be/src/catalog/catalog-server.h
@@ -23,15 +23,15 @@
 #include <boost/shared_ptr.hpp>
 #include <boost/unordered_set.hpp>
 
+#include "catalog/catalog.h"
 #include "gen-cpp/CatalogService.h"
 #include "gen-cpp/Frontend_types.h"
 #include "gen-cpp/Types_types.h"
-#include "catalog/catalog.h"
 #include "kudu/util/web_callback_registry.h"
-#include "statestore/statestore-subscriber.h"
+#include "rapidjson/rapidjson.h"
+#include "statestore/statestore-subscriber-catalog.h"
 #include "util/condition-variable.h"
 #include "util/metrics-fwd.h"
-#include "rapidjson/rapidjson.h"
 
 using kudu::HttpStatusCode;
 
@@ -87,7 +87,15 @@ class CatalogServer {
   /// service has started.
   void MarkServiceAsStarted();
 
+  // Returns the protocol version of catalog service.
+  CatalogServiceVersion::type GetProtocolVersion() const {
+    return protocol_version_;
+  }
+
  private:
+  /// Protocol version of the Catalog Service.
+  CatalogServiceVersion::type protocol_version_;
+
   /// Indicates whether the catalog service is ready.
   std::atomic_bool service_started_{false};
 
@@ -96,7 +104,7 @@ class CatalogServer {
   ThriftSerializer thrift_serializer_;
   MetricGroup* metrics_;
   boost::scoped_ptr<Catalog> catalog_;
-  boost::scoped_ptr<StatestoreSubscriber> statestore_subscriber_;
+  boost::scoped_ptr<StatestoreSubscriberCatalog> statestore_subscriber_;
 
   /// Metric that tracks the amount of time taken preparing a catalog update.
   StatsMetric<double>* topic_processing_time_metric_;
diff --git a/be/src/common/global-flags.cc b/be/src/common/global-flags.cc
index d54cb4612..822617e4c 100644
--- a/be/src/common/global-flags.cc
+++ b/be/src/common/global-flags.cc
@@ -169,6 +169,9 @@ DEFINE_int32(stress_catalog_startup_delay_ms, 0, "A stress option that injects e
     "catalogd opens ports or accepts connections. Delay <= 0 injects no delay.");
 DEFINE_int32(stress_disk_read_delay_ms, 0, "A stress option that injects extra delay"
     " in milliseconds when the I/O manager is reading from disk.");
+DEFINE_int32(stress_statestore_startup_delay_ms, 0, "A stress option that injects extra "
+    "delay in milliseconds during the startup of statestore. The delay is before the "
+    "statestored opens ports or accepts connections. Delay <= 0 injects no delay.");
 #endif
 
 DEFINE_string(debug_actions, "", "For testing only. Uses the same format as the debug "
@@ -375,6 +378,12 @@ DEFINE_bool(pull_table_types_and_comments, false,
     "catalogd-only flag. Required if users want GET_TABLES requests return correct table "
     "types or comments.");
 
+DEFINE_bool(tolerate_statestore_startup_delay, false, "If set to true, the subscriber "
+    "is able to tolerate the delay of the statestore's availability. The subscriber's "
+    "process will not exit if it cannot register with the specified statestore on "
+    "startup. But instead it enters into Recovery mode, it will loop, sleep and retry "
+    "till it successfully registers with the statestore.");
+
 // TGeospatialLibrary's values are mapped here as constants
 static const string geo_lib_none = "NONE";
 static const string geo_lib_hive_esri = "HIVE_ESRI";
diff --git a/be/src/exec/catalog-op-executor.cc b/be/src/exec/catalog-op-executor.cc
index c6c245428..2078716d0 100644
--- a/be/src/exec/catalog-op-executor.cc
+++ b/be/src/exec/catalog-op-executor.cc
@@ -47,8 +47,6 @@ using namespace apache::hive::service::cli::thrift;
 using namespace apache::thrift;
 
 DECLARE_bool(use_local_catalog);
-DECLARE_int32(catalog_service_port);
-DECLARE_string(catalog_service_host);
 DECLARE_string(debug_actions);
 
 DECLARE_int32(catalog_client_connection_num_retries);
@@ -96,8 +94,6 @@ Status CatalogOpExecutor::Exec(const TCatalogOpRequest& request) {
   DCHECK(profile_ != NULL);
   RuntimeProfile::Counter* exec_timer = ADD_TIMER(profile_, "CatalogOpExecTimer");
   SCOPED_TIMER(exec_timer);
-  const TNetworkAddress& address =
-      MakeNetworkAddress(FLAGS_catalog_service_host, FLAGS_catalog_service_port);
   RETURN_IF_ERROR(status);
   switch (request.op_type) {
     case TCatalogOpType::DDL: {
@@ -107,7 +103,8 @@ Status CatalogOpExecutor::Exec(const TCatalogOpRequest& request) {
       exec_response_.reset(new TDdlExecResponse());
       int attempt = 0; // Used for debug action only.
       CatalogServiceConnection::RpcStatus rpc_status =
-          CatalogServiceConnection::DoRpcWithRetry(env_->catalogd_client_cache(), address,
+          CatalogServiceConnection::DoRpcWithRetry(env_->catalogd_client_cache(),
+              *ExecEnv::GetInstance()->GetCatalogdAddress().get(),
               &CatalogServiceClientWrapper::ExecDdl, request.ddl_params,
               FLAGS_catalog_client_connection_num_retries,
               FLAGS_catalog_client_rpc_retry_interval_ms,
@@ -130,7 +127,8 @@ Status CatalogOpExecutor::Exec(const TCatalogOpRequest& request) {
       TResetMetadataResponse response;
       int attempt = 0; // Used for debug action only.
       CatalogServiceConnection::RpcStatus rpc_status =
-          CatalogServiceConnection::DoRpcWithRetry(env_->catalogd_client_cache(), address,
+          CatalogServiceConnection::DoRpcWithRetry(env_->catalogd_client_cache(),
+              *ExecEnv::GetInstance()->GetCatalogdAddress().get(),
               &CatalogServiceClientWrapper::ResetMetadata, request.reset_metadata_params,
               FLAGS_catalog_client_connection_num_retries,
               FLAGS_catalog_client_rpc_retry_interval_ms,
@@ -344,15 +342,14 @@ void CatalogOpExecutor::SetColumnStats(const TTableSchema& col_stats_schema,
 
 Status CatalogOpExecutor::GetCatalogObject(const TCatalogObject& object_desc,
     TCatalogObject* result) {
-  const TNetworkAddress& address =
-      MakeNetworkAddress(FLAGS_catalog_service_host, FLAGS_catalog_service_port);
   TGetCatalogObjectRequest request;
   request.__set_object_desc(object_desc);
 
   TGetCatalogObjectResponse response;
   int attempt = 0; // Used for debug action only.
   CatalogServiceConnection::RpcStatus rpc_status =
-      CatalogServiceConnection::DoRpcWithRetry(env_->catalogd_client_cache(), address,
+      CatalogServiceConnection::DoRpcWithRetry(env_->catalogd_client_cache(),
+          *ExecEnv::GetInstance()->GetCatalogdAddress().get(),
           &CatalogServiceClientWrapper::GetCatalogObject, request,
           FLAGS_catalog_client_connection_num_retries,
           FLAGS_catalog_client_rpc_retry_interval_ms,
@@ -366,14 +363,13 @@ Status CatalogOpExecutor::GetPartialCatalogObject(
     const TGetPartialCatalogObjectRequest& req,
     TGetPartialCatalogObjectResponse* resp) {
   DCHECK(FLAGS_use_local_catalog || TestInfo::is_test());
-  const TNetworkAddress& address =
-      MakeNetworkAddress(FLAGS_catalog_service_host, FLAGS_catalog_service_port);
   if (FLAGS_inject_latency_before_catalog_fetch_ms > 0) {
     SleepForMs(FLAGS_inject_latency_before_catalog_fetch_ms);
   }
   int attempt = 0; // Used for debug action only.
   CatalogServiceConnection::RpcStatus rpc_status =
-      CatalogServiceConnection::DoRpcWithRetry(env_->catalogd_client_cache(), address,
+      CatalogServiceConnection::DoRpcWithRetry(env_->catalogd_client_cache(),
+          *ExecEnv::GetInstance()->GetCatalogdAddress().get(),
           &CatalogServiceClientWrapper::GetPartialCatalogObject, req,
           FLAGS_catalog_client_connection_num_retries,
           FLAGS_catalog_client_rpc_retry_interval_ms,
@@ -388,11 +384,10 @@ Status CatalogOpExecutor::GetPartialCatalogObject(
 
 Status CatalogOpExecutor::PrioritizeLoad(const TPrioritizeLoadRequest& req,
     TPrioritizeLoadResponse* result) {
-  const TNetworkAddress& address =
-      MakeNetworkAddress(FLAGS_catalog_service_host, FLAGS_catalog_service_port);
   int attempt = 0; // Used for debug action only.
   CatalogServiceConnection::RpcStatus rpc_status =
-      CatalogServiceConnection::DoRpcWithRetry(env_->catalogd_client_cache(), address,
+      CatalogServiceConnection::DoRpcWithRetry(env_->catalogd_client_cache(),
+          *ExecEnv::GetInstance()->GetCatalogdAddress().get(),
           &CatalogServiceClientWrapper::PrioritizeLoad, req,
           FLAGS_catalog_client_connection_num_retries,
           FLAGS_catalog_client_rpc_retry_interval_ms,
@@ -403,11 +398,10 @@ Status CatalogOpExecutor::PrioritizeLoad(const TPrioritizeLoadRequest& req,
 
 Status CatalogOpExecutor::GetPartitionStats(
     const TGetPartitionStatsRequest& req, TGetPartitionStatsResponse* result) {
-  const TNetworkAddress& address =
-      MakeNetworkAddress(FLAGS_catalog_service_host, FLAGS_catalog_service_port);
   int attempt = 0; // Used for debug action only.
   CatalogServiceConnection::RpcStatus rpc_status =
-      CatalogServiceConnection::DoRpcWithRetry(env_->catalogd_client_cache(), address,
+      CatalogServiceConnection::DoRpcWithRetry(env_->catalogd_client_cache(),
+          *ExecEnv::GetInstance()->GetCatalogdAddress().get(),
           &CatalogServiceClientWrapper::GetPartitionStats, req,
           FLAGS_catalog_client_connection_num_retries,
           FLAGS_catalog_client_rpc_retry_interval_ms,
@@ -418,11 +412,10 @@ Status CatalogOpExecutor::GetPartitionStats(
 
 Status CatalogOpExecutor::UpdateTableUsage(const TUpdateTableUsageRequest& req,
   TUpdateTableUsageResponse* resp) {
-  const TNetworkAddress& address =
-      MakeNetworkAddress(FLAGS_catalog_service_host, FLAGS_catalog_service_port);
   int attempt = 0; // Used for debug action only.
   CatalogServiceConnection::RpcStatus rpc_status =
-      CatalogServiceConnection::DoRpcWithRetry(env_->catalogd_client_cache(), address,
+      CatalogServiceConnection::DoRpcWithRetry(env_->catalogd_client_cache(),
+          *ExecEnv::GetInstance()->GetCatalogdAddress().get(),
           &CatalogServiceClientWrapper::UpdateTableUsage, req,
           FLAGS_catalog_client_connection_num_retries,
           FLAGS_catalog_client_rpc_retry_interval_ms,
diff --git a/be/src/rpc/thrift-server-test.cc b/be/src/rpc/thrift-server-test.cc
index 50edea47e..b9f82ec0c 100644
--- a/be/src/rpc/thrift-server-test.cc
+++ b/be/src/rpc/thrift-server-test.cc
@@ -81,6 +81,9 @@ class DummyStatestoreService : public StatestoreServiceIf {
   virtual void RegisterSubscriber(TRegisterSubscriberResponse& response,
       const TRegisterSubscriberRequest& request) {
   }
+  virtual void GetProtocolVersion(TGetProtocolVersionResponse& response,
+      const TGetProtocolVersionRequest& request) {
+  }
 };
 
 std::shared_ptr<TProcessor> MakeProcessor() {
diff --git a/be/src/runtime/exec-env.cc b/be/src/runtime/exec-env.cc
index c796c1337..087a8ef80 100644
--- a/be/src/runtime/exec-env.cc
+++ b/be/src/runtime/exec-env.cc
@@ -139,6 +139,8 @@ DECLARE_int32(webserver_port);
 DECLARE_int64(tcmalloc_max_total_thread_cache_bytes);
 DECLARE_string(admission_service_host);
 DECLARE_int32(admission_service_port);
+DECLARE_string(catalog_service_host);
+DECLARE_int32(catalog_service_port);
 
 DECLARE_string(ssl_client_ca_certificate);
 
@@ -245,15 +247,33 @@ ExecEnv::ExecEnv(int krpc_port, int subscriber_port, int webserver_port,
   TNetworkAddress statestore_address =
       MakeNetworkAddress(statestore_host, statestore_port);
 
+  catalogd_address_ = std::make_shared<const TNetworkAddress>(
+      MakeNetworkAddress(FLAGS_catalog_service_host, FLAGS_catalog_service_port));
+
+  TStatestoreSubscriberType::type subscriber_type = TStatestoreSubscriberType::UNKNOWN;
+  if (FLAGS_is_coordinator) {
+    subscriber_type = FLAGS_is_executor ? TStatestoreSubscriberType::COORDINATOR_EXECUTOR
+                                        : TStatestoreSubscriberType::COORDINATOR;
+  } else if (FLAGS_is_executor) {
+    subscriber_type = TStatestoreSubscriberType::EXECUTOR;
+  }
   // Set StatestoreSubscriber::subscriber_id as hostname + krpc_port.
   statestore_subscriber_.reset(new StatestoreSubscriber(
       Substitute("impalad@$0:$1", FLAGS_hostname, FLAGS_krpc_port), subscriber_address,
-      statestore_address, metrics_.get()));
+      statestore_address, metrics_.get(), subscriber_type));
 
   if (FLAGS_is_coordinator) {
     hdfs_op_thread_pool_.reset(
         CreateHdfsOpThreadPool("hdfs-worker-pool", FLAGS_num_hdfs_worker_threads, 1024));
+
+    StatestoreSubscriber::UpdateCatalogdCallback update_catalogd_cb =
+        bind<void>(mem_fn(&ExecEnv::UpdateCatalogd), this, _1);
+    statestore_subscriber_->AddUpdateCatalogdTopic(update_catalogd_cb);
   }
+  StatestoreSubscriber::CompleteRegistrationCallback complete_registration_cb =
+      bind<void>(mem_fn(&ExecEnv::SetStatestoreRegistrationCompleted), this);
+  statestore_subscriber_->AddCompleteRegistrationTopic(complete_registration_cb);
+
   if (FLAGS_is_coordinator && !AdmissionServiceEnabled()) {
     // We only need a Scheduler if we're performing admission control locally, i.e. if
     // this is a coordinator and there isn't an admissiond.
@@ -494,11 +514,18 @@ Status ExecEnv::StartStatestoreSubscriberService() {
 
   // Must happen after all topic registrations / callbacks are done
   if (statestore_subscriber_.get() != nullptr) {
-    Status status = statestore_subscriber_->Start();
+    bool has_registered_catalogd = false;
+    TCatalogRegistration catalogd_registration;
+    Status status =
+        statestore_subscriber_->Start(&has_registered_catalogd, &catalogd_registration);
     if (!status.ok()) {
       status.AddDetail("Statestore subscriber did not start up.");
       return status;
     }
+    if (statestore_subscriber_->IsRegistered()) SetStatestoreRegistrationCompleted();
+    if (has_registered_catalogd && FLAGS_is_coordinator) {
+      UpdateCatalogd(catalogd_registration);
+    }
   }
 
   return Status::OK();
@@ -640,4 +667,44 @@ Status ExecEnv::GetAdmissionServiceAddress(
   return Status::OK();
 }
 
+void ExecEnv::UpdateCatalogd(const TCatalogRegistration& catalogd_registration) {
+  if (catalogd_registration.address.hostname.empty()
+      || catalogd_registration.address.port == 0) {
+    return;
+  }
+  if (catalogd_registration.protocol
+      != statestore_subscriber_->GetCatalogProtocolVersion()) {
+    // This should not happen now. Since we bump up catalog and statestore service
+    // versions at same time, coordinators must have same protocol versions as catalogd
+    // if they can join one cluster. But in future, it may happen if the two protocol
+    // versions are not updated at same time for some reason.
+    // Note that Impalad coordinators must wait for their local replica of the catalog to
+    // be initialized from the statestore prior to opening up client ports. If the
+    // coordinator has incompatible protocol version from catalogd, it should not open
+    // client ports.
+    LOG(INFO) << "Protocol version of Catalog service does not match the protocol "
+              << "version of registered catalogd: "
+              << statestore_subscriber_->GetCatalogProtocolVersion()
+              << " vs. " << catalogd_registration.protocol;
+  }
+  std::lock_guard<std::mutex> l(catalogd_address_lock_);
+  DCHECK(catalogd_address_.get() != nullptr);
+  bool is_matching = (catalogd_registration.address.port == catalogd_address_->port
+      && catalogd_registration.address.hostname == catalogd_address_->hostname);
+  if (!is_matching) {
+    LOG(INFO) << "The address of Catalog service is changed from "
+              << TNetworkAddressToString(*catalogd_address_.get())
+              << " to " << TNetworkAddressToString(catalogd_registration.address);
+    catalogd_address_ =
+        std::make_shared<const TNetworkAddress>(catalogd_registration.address);
+  }
+}
+
+std::shared_ptr<const TNetworkAddress> ExecEnv::GetCatalogdAddress() const {
+  std::lock_guard<std::mutex> l(catalogd_address_lock_);
+  DCHECK(catalogd_address_.get() != nullptr);
+  std::shared_ptr<const TNetworkAddress> address = catalogd_address_;
+  return address;
+}
+
 } // namespace impala
diff --git a/be/src/runtime/exec-env.h b/be/src/runtime/exec-env.h
index f15e674b3..57e373b9a 100644
--- a/be/src/runtime/exec-env.h
+++ b/be/src/runtime/exec-env.h
@@ -25,6 +25,7 @@
 #include <kudu/client/client.h>
 
 // NOTE: try not to add more headers here: exec-env.h is included in many many files.
+#include "common/atomic.h"
 #include "common/global-types.h"
 #include "common/status.h"
 #include "runtime/client-cache-types.h"
@@ -70,6 +71,7 @@ class ThreadResourceMgr;
 class TmpFileMgr;
 class Webserver;
 class CodeGenCache;
+class TCatalogRegistration;
 
 namespace io {
   class DiskIoMgr;
@@ -192,6 +194,23 @@ class ExecEnv {
   /// Returns true if the admission control service is enabled.
   bool AdmissionServiceEnabled() const;
 
+  /// Returns true if the registration with statestore is completed.
+  bool IsStatestoreRegistrationCompleted() const {
+    return statestore_registration_completed_.Load() != 0;
+  }
+
+  /// Set the flag when the registration with statestore is completed.
+  void SetStatestoreRegistrationCompleted() {
+    statestore_registration_completed_.CompareAndSwap(0, 1);
+  }
+
+  /// Callback function for receiving notification of updating catalogd.
+  /// This function is called after catalogd is registered to statestore.
+  void UpdateCatalogd(const TCatalogRegistration& catalogd_registration);
+
+  /// Return the current address of Catalog service.
+  std::shared_ptr<const TNetworkAddress> GetCatalogdAddress() const;
+
  private:
   // Used to uniquely identify this impalad.
   BackendIdPB backend_id_;
@@ -296,6 +315,15 @@ class ExecEnv {
   /// this backend. Queries take up multiple slots only when mt_dop > 1.
   int64_t admission_slots_;
 
+  /// Flag that indicate if the registration with statestore is completed.
+  AtomicInt32 statestore_registration_completed_{0};
+
+  /// Current address of Catalog service
+  std::shared_ptr<const TNetworkAddress> catalogd_address_;
+
+  /// Protects catalogd_address_.
+  mutable std::mutex catalogd_address_lock_;
+
   /// Initialize ExecEnv based on Hadoop config from frontend.
   Status InitHadoopConfig();
 
diff --git a/be/src/scheduling/admissiond-env.cc b/be/src/scheduling/admissiond-env.cc
index 27fbf8f99..a7b226049 100644
--- a/be/src/scheduling/admissiond-env.cc
+++ b/be/src/scheduling/admissiond-env.cc
@@ -60,7 +60,8 @@ AdmissiondEnv::AdmissiondEnv()
       MakeNetworkAddress(FLAGS_state_store_host, FLAGS_state_store_port);
   statestore_subscriber_.reset(new StatestoreSubscriber(
       Substitute("admissiond@$0", TNetworkAddressToString(admission_service_addr)),
-      subscriber_address, statestore_address, metrics));
+      subscriber_address, statestore_address, metrics,
+      TStatestoreSubscriberType::ADMISSIOND));
 
   scheduler_.reset(new Scheduler(metrics, request_pool_service()));
   cluster_membership_mgr_.reset(new ClusterMembershipMgr(
diff --git a/be/src/service/client-request-state.cc b/be/src/service/client-request-state.cc
index 7bb4338ef..0e3ab995f 100644
--- a/be/src/service/client-request-state.cc
+++ b/be/src/service/client-request-state.cc
@@ -82,8 +82,6 @@ using namespace strings;
 DECLARE_bool(abort_on_failed_audit_event);
 DECLARE_bool(abort_on_failed_lineage_event);
 DECLARE_int32(krpc_port);
-DECLARE_int32(catalog_service_port);
-DECLARE_string(catalog_service_host);
 DECLARE_int64(max_result_cache_size);
 DECLARE_bool(use_local_catalog);
 
@@ -828,10 +826,8 @@ void ClientRequestState::ExecLoadDataRequestImpl(bool exec_in_worker_thread) {
   catalog_update.db_name = exec_request_->load_data_request.table_name.db_name;
   catalog_update.is_overwrite = exec_request_->load_data_request.overwrite;
 
-  const TNetworkAddress& address =
-      MakeNetworkAddress(FLAGS_catalog_service_host, FLAGS_catalog_service_port);
-  CatalogServiceConnection client(
-      ExecEnv::GetInstance()->catalogd_client_cache(), address, &status);
+  CatalogServiceConnection client(ExecEnv::GetInstance()->catalogd_client_cache(),
+      *ExecEnv::GetInstance()->GetCatalogdAddress().get(), &status);
   {
     lock_guard<mutex> l(lock_);
     RETURN_VOID_IF_ERROR(UpdateQueryStatus(status));
@@ -1572,10 +1568,8 @@ Status ClientRequestState::UpdateCatalog() {
       }
 
       Status cnxn_status;
-      const TNetworkAddress& address =
-          MakeNetworkAddress(FLAGS_catalog_service_host, FLAGS_catalog_service_port);
-      CatalogServiceConnection client(
-          ExecEnv::GetInstance()->catalogd_client_cache(), address, &cnxn_status);
+      CatalogServiceConnection client(ExecEnv::GetInstance()->catalogd_client_cache(),
+          *ExecEnv::GetInstance()->GetCatalogdAddress().get(), &cnxn_status);
       RETURN_IF_ERROR(cnxn_status);
 
       VLOG_QUERY << "Executing FinalizeDml() using CatalogService";
diff --git a/be/src/service/impala-server.cc b/be/src/service/impala-server.cc
index 78421f6e7..432a9659a 100644
--- a/be/src/service/impala-server.cc
+++ b/be/src/service/impala-server.cc
@@ -634,7 +634,7 @@ bool ImpalaServer::IsCoordinator() { return is_coordinator_; }
 
 bool ImpalaServer::IsExecutor() { return is_executor_; }
 
-bool ImpalaServer::IsHealthy() { return services_started_.load(); }
+bool ImpalaServer::IsHealthy() { return AreServicesReady(); }
 
 int ImpalaServer::GetBeeswaxPort() {
   DCHECK(beeswax_server_ != nullptr);
@@ -2306,7 +2306,7 @@ void ImpalaServer::CancelQueriesOnFailedBackends(
 }
 
 std::shared_ptr<const BackendDescriptorPB> ImpalaServer::GetLocalBackendDescriptor() {
-  if (!services_started_.load()) return nullptr;
+  if (!AreServicesReady()) return nullptr;
 
   lock_guard<mutex> l(local_backend_descriptor_lock_);
   // Check if the current backend descriptor needs to be initialized.
@@ -2329,7 +2329,7 @@ std::shared_ptr<const BackendDescriptorPB> ImpalaServer::GetLocalBackendDescript
 }
 
 void ImpalaServer::BuildLocalBackendDescriptorInternal(BackendDescriptorPB* be_desc) {
-  DCHECK(services_started_.load());
+  DCHECK(AreServicesReady());
   bool is_quiescing = shutting_down_.Load() != 0;
 
   *be_desc->mutable_backend_id() = exec_env_->backend_id();
@@ -3166,6 +3166,10 @@ void ImpalaServer::Join() {
   }
 }
 
+bool ImpalaServer::AreServicesReady() const {
+  return services_started_.load() && exec_env_->IsStatestoreRegistrationCompleted();
+}
+
 Status ImpalaServer::CheckClientRequestSession(
     SessionState* session, const std::string& client_request_effective_user,
     const TUniqueId& query_id) {
diff --git a/be/src/service/impala-server.h b/be/src/service/impala-server.h
index 64ccc5c10..7afbc430f 100644
--- a/be/src/service/impala-server.h
+++ b/be/src/service/impala-server.h
@@ -483,6 +483,10 @@ class ImpalaServer : public ImpalaServiceIf,
   void CancelQueriesOnFailedBackends(
       const std::unordered_set<BackendIdPB>& current_membership);
 
+  /// Returns true if all services required for the server have been started and the
+  /// registration with statestore is completed.
+  bool AreServicesReady() const;
+
   /// Start the shutdown process. Return an error if it could not be started. Otherwise,
   /// if it was successfully started by this or a previous call, return OK along with
   /// information about the pending shutdown in 'shutdown_status'. 'relative_deadline_s'
diff --git a/be/src/statestore/statestore-service-client-wrapper.h b/be/src/statestore/statestore-service-client-wrapper.h
index 2c77cbc25..e085929c4 100644
--- a/be/src/statestore/statestore-service-client-wrapper.h
+++ b/be/src/statestore/statestore-service-client-wrapper.h
@@ -48,6 +48,14 @@ class StatestoreServiceClientWrapper : public StatestoreServiceClient {
     recv_RegisterSubscriber(_return);
   }
 
+  void GetProtocolVersion(TGetProtocolVersionResponse& _return,
+      const TGetProtocolVersionRequest& params, bool* send_done) {
+    DCHECK(!*send_done);
+    send_GetProtocolVersion(params);
+    *send_done = true;
+    recv_GetProtocolVersion(_return);
+  }
+
 #pragma clang diagnostic pop
 };
 
diff --git a/be/src/statestore/statestore-subscriber-catalog.h b/be/src/statestore/statestore-subscriber-catalog.h
new file mode 100644
index 000000000..759db297d
--- /dev/null
+++ b/be/src/statestore/statestore-subscriber-catalog.h
@@ -0,0 +1,61 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements.  See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership.  The ASF licenses this file
+// to you 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.
+
+#pragma once
+
+#include "statestore/statestore-subscriber.h"
+
+namespace impala {
+
+/// Statestore subscriber for Catalog service.
+/// Catalog-specific parameters for statestore registration.
+/// We will add more parameters when supporting CatalogD HA.
+class StatestoreSubscriberCatalog : public StatestoreSubscriber {
+ public:
+  /// Only constructor.
+  ///   subscriber_id - should be unique across the cluster, identifies this subscriber
+  ///   heartbeat_address - the local address on which the heartbeat service which
+  ///                       communicates with the statestore should be started.
+  ///   statestore_address - the address of the statestore to register with
+  ///   catalogd_address - address of catalog service.
+  ///   catalog_protocol_version - protocol version of Catalog service.
+  StatestoreSubscriberCatalog(const std::string& subscriber_id,
+      const TNetworkAddress& heartbeat_address,
+      const TNetworkAddress& statestore_address,
+      MetricGroup* metrics,
+      CatalogServiceVersion::type catalog_protocol_version,
+      const TNetworkAddress& catalogd_address)
+    : StatestoreSubscriber(subscriber_id, heartbeat_address, statestore_address, metrics,
+        TStatestoreSubscriberType::CATALOGD) {
+    catalogd_registration_.__set_protocol(catalog_protocol_version);
+    catalogd_registration_.__set_address(catalogd_address);
+  }
+
+  virtual ~StatestoreSubscriberCatalog() {}
+
+  /// Set Register Request
+  virtual Status SetRegisterRequest(TRegisterSubscriberRequest* request) {
+    request->__set_catalogd_registration(catalogd_registration_);
+    return StatestoreSubscriber::SetRegisterRequest(request);
+  }
+
+ private:
+  /// Additional registration info for catalog daemon.
+  TCatalogRegistration catalogd_registration_;
+};
+
+}
diff --git a/be/src/statestore/statestore-subscriber-client-wrapper.h b/be/src/statestore/statestore-subscriber-client-wrapper.h
index b5f66be40..0360243a0 100644
--- a/be/src/statestore/statestore-subscriber-client-wrapper.h
+++ b/be/src/statestore/statestore-subscriber-client-wrapper.h
@@ -56,6 +56,14 @@ class StatestoreSubscriberClientWrapper : public StatestoreSubscriberClient {
      recv_UpdateState(_return);
    }
 
+   void UpdateCatalogd(TUpdateCatalogdResponse& _return,
+       const TUpdateCatalogdRequest& params, bool* send_done) {
+     DCHECK(!*send_done);
+     send_UpdateCatalogd(params);
+     *send_done = true;
+     recv_UpdateCatalogd(_return);
+   }
+
 #pragma clang diagnostic pop
 };
 
diff --git a/be/src/statestore/statestore-subscriber.cc b/be/src/statestore/statestore-subscriber.cc
index ea787fc04..048a62a47 100644
--- a/be/src/statestore/statestore-subscriber.cc
+++ b/be/src/statestore/statestore-subscriber.cc
@@ -69,6 +69,7 @@ DEFINE_int64_hidden(statestore_subscriber_recovery_grace_period_ms, 30000L, "Per
 DEFINE_int32(statestore_client_rpc_timeout_ms, 300000, "(Advanced) The underlying "
     "TSocket send/recv timeout in milliseconds for a catalog client RPC.");
 
+DECLARE_bool(tolerate_statestore_startup_delay);
 DECLARE_string(debug_actions);
 DECLARE_string(ssl_client_ca_certificate);
 DECLARE_string(ssl_server_certificate);
@@ -100,73 +101,243 @@ class StatestoreSubscriberThriftIf : public StatestoreSubscriberIf {
  public:
   StatestoreSubscriberThriftIf(StatestoreSubscriber* subscriber)
       : subscriber_(subscriber) { DCHECK(subscriber != NULL); }
+
   virtual void UpdateState(TUpdateStateResponse& response,
                            const TUpdateStateRequest& params) {
-    TUniqueId registration_id;
-    if (params.__isset.registration_id) {
-      registration_id = params.registration_id;
-    }
+    Status status = CheckProtocolVersion(params.protocol_version);
+    if (status.ok()) {
+      TUniqueId registration_id, statestore_id;
+      if (params.__isset.registration_id) {
+        registration_id = params.registration_id;
+      }
+      if (params.__isset.statestore_id) {
+        statestore_id = params.statestore_id;
+      }
 
-    subscriber_->UpdateState(params.topic_deltas, registration_id,
-        &response.topic_updates, &response.skipped).ToThrift(&response.status);
-    // Make sure Thrift thinks the field is set.
-    response.__set_skipped(response.skipped);
+      subscriber_
+          ->UpdateState(params.topic_deltas, registration_id, statestore_id,
+              &response.topic_updates, &response.skipped)
+          .ToThrift(&response.status);
+      // Make sure Thrift thinks the field is set.
+      response.__set_skipped(response.skipped);
+    }
+    TStatus thrift_status;
+    status.ToThrift(&thrift_status);
+    response.__set_status(thrift_status);
   }
 
   virtual void Heartbeat(THeartbeatResponse& response, const THeartbeatRequest& request) {
-    subscriber_->Heartbeat(request.registration_id);
+    Status status = CheckProtocolVersion(request.protocol_version);
+    if (status.ok()) {
+      TUniqueId registration_id, statestore_id;
+      if (request.__isset.registration_id) {
+        registration_id = request.registration_id;
+      }
+      if (request.__isset.statestore_id) {
+        statestore_id = request.statestore_id;
+      }
+      subscriber_->Heartbeat(registration_id, statestore_id);
+    }
+    TStatus thrift_status;
+    status.ToThrift(&thrift_status);
+    response.__set_status(thrift_status);
+  }
+
+  virtual void UpdateCatalogd(TUpdateCatalogdResponse& response,
+      const TUpdateCatalogdRequest& request) {
+    Status status = CheckProtocolVersion(request.protocol_version);
+    if (status.ok()) {
+      subscriber_->UpdateCatalogd(request.catalogd_registration,
+          request.registration_id, request.statestore_id, request.sequence);
+    }
+    TStatus thrift_status;
+    status.ToThrift(&thrift_status);
+    response.__set_status(thrift_status);
   }
 
  private:
   StatestoreSubscriber* subscriber_;
+
+  Status CheckProtocolVersion(StatestoreServiceVersion::type statestore_version) {
+    Status status = Status::OK();
+    if (statestore_version < subscriber_->GetProtocolVersion()) {
+      status = Status(TErrorCode::STATESTORE_INCOMPATIBLE_PROTOCOL, subscriber_->id(),
+          subscriber_->GetProtocolVersion() + 1, statestore_version + 1);
+    }
+    return status;
+  }
 };
 
 StatestoreSubscriber::StatestoreSubscriber(const string& subscriber_id,
     const TNetworkAddress& heartbeat_address, const TNetworkAddress& statestore_address,
-    MetricGroup* metrics)
+    MetricGroup* metrics, TStatestoreSubscriberType::type subscriber_type)
   : subscriber_id_(subscriber_id),
-    statestore_address_(statestore_address),
+    protocol_version_(StatestoreServiceVersion::V2),
+    catalog_protocol_version_(CatalogServiceVersion::V2),
+    heartbeat_address_(heartbeat_address),
+    subscriber_type_(subscriber_type),
     thrift_iface_(new StatestoreSubscriberThriftIf(this)),
-    failure_detector_(
-        new TimeoutFailureDetector(seconds(FLAGS_statestore_subscriber_timeout_seconds),
-            seconds(FLAGS_statestore_subscriber_timeout_seconds / 2))),
     client_cache_(new StatestoreClientCache(1, 0, FLAGS_statestore_client_rpc_timeout_ms,
         FLAGS_statestore_client_rpc_timeout_ms, "",
         !FLAGS_ssl_client_ca_certificate.empty())),
-    metrics_(metrics->GetOrCreateChildGroup("statestore-subscriber")),
-    heartbeat_address_(heartbeat_address),
+    metrics_(metrics->GetOrCreateChildGroup("statestore-subscriber")) {
+  statestore_ = new StatestoreStub(this, statestore_address, metrics);
+  client_cache_->InitMetrics(metrics, "statestore-subscriber.statestore");
+}
+
+Status StatestoreSubscriber::AddTopic(const Statestore::TopicId& topic_id,
+    bool is_transient, bool populate_min_subscriber_topic_version,
+    string filter_prefix, const UpdateCallback& callback) {
+  return statestore_->AddTopic(topic_id, is_transient,
+      populate_min_subscriber_topic_version, filter_prefix, callback);
+}
+
+void StatestoreSubscriber::AddUpdateCatalogdTopic(
+    const UpdateCatalogdCallback& callback) {
+  statestore_->AddUpdateCatalogdTopic(callback);
+}
+
+void StatestoreSubscriber::AddCompleteRegistrationTopic(
+    const CompleteRegistrationCallback& callback) {
+  statestore_->AddCompleteRegistrationTopic(callback);
+}
+
+bool StatestoreSubscriber::IsInPostRecoveryGracePeriod() const {
+  return statestore_->IsInPostRecoveryGracePeriod();
+}
+
+bool StatestoreSubscriber::IsRegistered() const {
+  return statestore_->IsRegistered();
+}
+
+Status StatestoreSubscriber::Start(bool* has_registered_catalogd,
+    TCatalogRegistration* registered_catalogd_registration) {
+  // Backend must be started before registration
+  std::shared_ptr<TProcessor> processor(
+      new StatestoreSubscriberProcessor(thrift_iface_));
+  std::shared_ptr<TProcessorEventHandler> event_handler(
+      new RpcEventHandler("statestore-subscriber", metrics_));
+  processor->setEventHandler(event_handler);
+
+  ThriftServerBuilder builder(
+      "StatestoreSubscriber", processor, heartbeat_address_.port);
+  if (IsInternalTlsConfigured()) {
+    SSLProtocol ssl_version;
+    RETURN_IF_ERROR(
+        SSLProtoVersions::StringToProtocol(FLAGS_ssl_minimum_version, &ssl_version));
+    LOG(INFO) << "Enabling SSL for Statestore subscriber";
+    builder.ssl(FLAGS_ssl_server_certificate, FLAGS_ssl_private_key)
+        .pem_password_cmd(FLAGS_ssl_private_key_password_cmd)
+        .ssl_version(ssl_version)
+        .cipher_list(FLAGS_ssl_cipher_list);
+  }
+
+  ThriftServer* server;
+  RETURN_IF_ERROR(builder.Build(&server));
+  heartbeat_server_.reset(server);
+  RETURN_IF_ERROR(heartbeat_server_->Start());
+
+  // Specify the port which the heartbeat server is listening on.
+  heartbeat_address_.port = heartbeat_server_->port();
+
+  return statestore_->Start(has_registered_catalogd, registered_catalogd_registration);
+}
+
+/// Set Register Request
+Status StatestoreSubscriber::SetRegisterRequest(
+    TRegisterSubscriberRequest* request) {
+  // Resolve the heartbeat address if necessary. Don't re-register with statestore
+  // if the heartbeat address cannot be resolved.
+  TNetworkAddress heartbeat_address = heartbeat_address_;
+  if (FLAGS_statestore_subscriber_use_resolved_address) {
+    IpAddr ip_address;
+    RETURN_IF_ERROR(HostnameToIpAddr(heartbeat_address.hostname, &ip_address));
+    heartbeat_address.hostname = ip_address;
+    LOG(INFO) << Substitute(
+        "Registering with statestore with resolved address $0", ip_address);
+  }
+  request->__set_subscriber_location(heartbeat_address);
+  request->__set_subscriber_id(subscriber_id_);
+  request->__set_subscriber_type(subscriber_type_);
+  request->__set_subscribe_catalogd_change(statestore_->IsSubscribedCatalogdChange());
+  return Status::OK();
+}
+
+void StatestoreSubscriber::Heartbeat(
+    const RegistrationId& registration_id, const TUniqueId& statestore_id) {
+  // It's possible the heartbeat is received for previous registration.
+  if (statestore_->IsMatchingStatestoreId(statestore_id)) {
+    statestore_->Heartbeat(registration_id);
+  }
+}
+
+void StatestoreSubscriber::UpdateCatalogd(
+    const TCatalogRegistration& catalogd_registration,
+    const RegistrationId& registration_id,
+    const TUniqueId& statestore_id, int64 sequence) {
+  if (statestore_->IsMatchingStatestoreId(statestore_id)) {
+    statestore_->UpdateCatalogd(catalogd_registration, registration_id, sequence);
+  }
+}
+
+Status StatestoreSubscriber::UpdateState(const TopicDeltaMap& incoming_topic_deltas,
+    const RegistrationId& registration_id, const TUniqueId& statestore_id,
+    vector<TTopicDelta>* subscriber_topic_updates, bool* skipped) {
+  if (statestore_->IsMatchingStatestoreId(statestore_id)) {
+    return statestore_->UpdateState(
+        incoming_topic_deltas, registration_id, subscriber_topic_updates, skipped);
+  }
+  return Status::OK();
+}
+
+StatestoreSubscriber::StatestoreStub::StatestoreStub(StatestoreSubscriber* subscriber,
+    const TNetworkAddress& statestore_address, MetricGroup* metrics)
+  : subscriber_(subscriber),
+    statestore_address_(statestore_address),
+    failure_detector_(
+        new TimeoutFailureDetector(seconds(FLAGS_statestore_subscriber_timeout_seconds),
+            seconds(FLAGS_statestore_subscriber_timeout_seconds / 2))),
     is_registered_(false) {
-  connected_to_statestore_metric_ =
-      metrics_->AddProperty("statestore-subscriber.connected", false);
-  connection_failure_metric_ =
-    metrics_->AddCounter("statestore-subscriber.num-connection-failures", 0);
+  std::string metrics_name_prefix = "";
+  metrics_ = metrics->GetOrCreateChildGroup(
+      metrics_name_prefix + "statestore-subscriber");
+  connected_to_statestore_metric_ = metrics_->AddProperty(
+      "statestore-subscriber.connected", false);
+  connection_failure_metric_ = metrics_->AddCounter(
+      "statestore-subscriber.num-connection-failures", 0);
   last_recovery_duration_metric_ = metrics_->AddDoubleGauge(
       "statestore-subscriber.last-recovery-duration", 0.0);
   last_recovery_time_metric_ = metrics_->AddProperty<string>(
       "statestore-subscriber.last-recovery-time", "N/A");
-  topic_update_interval_metric_ = StatsMetric<double>::CreateAndRegister(metrics_,
-      "statestore-subscriber.topic-update-interval-time");
-  topic_update_duration_metric_ = StatsMetric<double>::CreateAndRegister(metrics_,
-      "statestore-subscriber.topic-update-duration");
-  heartbeat_interval_metric_ = StatsMetric<double>::CreateAndRegister(metrics_,
-      "statestore-subscriber.heartbeat-interval-time");
-  registration_id_metric_ = metrics->AddProperty<string>(
+  topic_update_interval_metric_ = StatsMetric<double>::CreateAndRegister(
+      metrics_, "statestore-subscriber.topic-update-interval-time");
+  topic_update_duration_metric_ = StatsMetric<double>::CreateAndRegister(
+      metrics_, "statestore-subscriber.topic-update-duration");
+  heartbeat_interval_metric_ = StatsMetric<double>::CreateAndRegister(
+      metrics_, "statestore-subscriber.heartbeat-interval-time");
+  registration_id_metric_ = metrics_->AddProperty<string>(
       "statestore-subscriber.registration-id", "N/A");
-  client_cache_->InitMetrics(metrics, "statestore-subscriber.statestore");
+  statestore_id_metric_ = metrics_->AddProperty<string>(
+      "statestore-subscriber.statestore-id", "N/A");
+  update_catalogd_metric_ = metrics_->AddCounter(
+      "statestore-subscriber.num-update-catalogd", 0);
+  re_registr_attempt_metric_ = metrics_->AddCounter(
+      "statestore-subscriber.num-re-register-attempt", 0);
 }
 
-Status StatestoreSubscriber::AddTopic(const Statestore::TopicId& topic_id,
-    bool is_transient, bool populate_min_subscriber_topic_version,
-    string filter_prefix, const UpdateCallback& callback) {
+Status StatestoreSubscriber::StatestoreStub::AddTopic(
+    const Statestore::TopicId& topic_id, bool is_transient,
+    bool populate_min_subscriber_topic_version, string filter_prefix,
+    const UpdateCallback& callback) {
   lock_guard<shared_mutex> exclusive_lock(lock_);
   if (is_registered_) return Status("Subscriber already started, can't add new topic");
   TopicRegistration& registration = topic_registrations_[topic_id];
   registration.callbacks.push_back(callback);
   if (registration.processing_time_metric == nullptr) {
-    registration.processing_time_metric = StatsMetric<double>::CreateAndRegister(metrics_,
-        CALLBACK_METRIC_PATTERN, topic_id);
-    registration.update_interval_metric = StatsMetric<double>::CreateAndRegister(metrics_,
-        UPDATE_INTERVAL_METRIC_PATTERN, topic_id);
+    registration.processing_time_metric = StatsMetric<double>::CreateAndRegister(
+        metrics_, CALLBACK_METRIC_PATTERN, topic_id);
+    registration.update_interval_metric = StatsMetric<double>::CreateAndRegister(
+        metrics_, UPDATE_INTERVAL_METRIC_PATTERN, topic_id);
     registration.update_interval_timer.Start();
   }
   registration.is_transient = is_transient;
@@ -176,8 +347,51 @@ Status StatestoreSubscriber::AddTopic(const Statestore::TopicId& topic_id,
   return Status::OK();
 }
 
-Status StatestoreSubscriber::Register() {
-  Status client_status;
+void StatestoreSubscriber::StatestoreStub::AddUpdateCatalogdTopic(
+    const UpdateCatalogdCallback& callback) {
+  update_catalogd_callbacks_.push_back(callback);
+}
+
+void StatestoreSubscriber::StatestoreStub::AddCompleteRegistrationTopic(
+    const CompleteRegistrationCallback& callback) {
+  complete_registration_callbacks_.push_back(callback);
+}
+
+Status StatestoreSubscriber::StatestoreStub::Register(bool* has_registered_catalogd,
+    TCatalogRegistration* registered_catalogd_registration) {
+  // Check protocol version of the statestore first.
+  TGetProtocolVersionRequest get_protocol_request;
+  TGetProtocolVersionResponse get_protocol_response;
+  get_protocol_request.__set_protocol_version(subscriber_->GetProtocolVersion());
+  int attempt = 0; // Used for debug action only.
+  StatestoreServiceConn::RpcStatus rpc_status =
+      StatestoreServiceConn::DoRpcWithRetry(subscriber_->client_cache_.get(),
+          statestore_address_,
+          &StatestoreServiceClientWrapper::GetProtocolVersion,
+          get_protocol_request,
+          FLAGS_statestore_subscriber_cnxn_attempts,
+          FLAGS_statestore_subscriber_cnxn_retry_interval_ms,
+          [&attempt]() {
+            return attempt++ == 0 ?
+                DebugAction(FLAGS_debug_actions, "GET_PROTOCOL_VERSION_FIRST_ATTEMPT") :
+                Status::OK();
+          },
+          &get_protocol_response);
+  RETURN_IF_ERROR(rpc_status.status);
+  Status status = Status(get_protocol_response.status);
+  if (status.ok()) {
+    connected_to_statestore_metric_->SetValue(true);
+    if (get_protocol_response.protocol_version < subscriber_->GetProtocolVersion()) {
+      // Return error for incompatible statestore.
+      return Status(TErrorCode::STATESTORE_INCOMPATIBLE_PROTOCOL, subscriber_->id(),
+          subscriber_->GetProtocolVersion() + 1,
+          get_protocol_response.protocol_version + 1);
+    }
+  } else {
+    return status;
+  }
+
+  // Register subscriber
   TRegisterSubscriberRequest request;
   for (const auto& registration : topic_registrations_) {
     TTopicRegistration thrift_topic;
@@ -189,13 +403,14 @@ Status StatestoreSubscriber::Register() {
     request.topic_registrations.push_back(thrift_topic);
   }
 
-  request.subscriber_location = heartbeat_address_;
-  request.subscriber_id = subscriber_id_;
+  RETURN_IF_ERROR(subscriber_->SetRegisterRequest(&request));
   TRegisterSubscriberResponse response;
-  int attempt = 0; // Used for debug action only.
-  StatestoreServiceConn::RpcStatus rpc_status =
-      StatestoreServiceConn::DoRpcWithRetry(client_cache_.get(), statestore_address_,
-          &StatestoreServiceClientWrapper::RegisterSubscriber, request,
+  attempt = 0; // Used for debug action only.
+  rpc_status =
+      StatestoreServiceConn::DoRpcWithRetry(subscriber_->client_cache_.get(),
+          statestore_address_,
+          &StatestoreServiceClientWrapper::RegisterSubscriber,
+          request,
           FLAGS_statestore_subscriber_cnxn_attempts,
           FLAGS_statestore_subscriber_cnxn_retry_interval_ms,
           [&attempt]() {
@@ -205,94 +420,104 @@ Status StatestoreSubscriber::Register() {
           },
           &response);
   RETURN_IF_ERROR(rpc_status.status);
-  Status status = Status(response.status);
+  status = Status(response.status);
   if (status.ok()) {
     connected_to_statestore_metric_->SetValue(true);
     last_registration_ms_.Store(MonotonicMillis());
   }
-  if (response.__isset.registration_id) {
-    lock_guard<mutex> l(registration_id_lock_);
-    registration_id_ = response.registration_id;
-    const string& registration_string = PrintId(registration_id_);
-    registration_id_metric_->SetValue(registration_string);
-    VLOG(1) << "Subscriber registration ID: " << registration_string;
-  } else {
-    VLOG(1) << "No subscriber registration ID received from statestore";
+  {
+    lock_guard<mutex> l(id_lock_);
+    if (response.__isset.protocol_version) {
+      protocol_version_ = response.protocol_version;
+      VLOG(1) << "Statestore protocol version: " << protocol_version_;
+    } else {
+      VLOG(1) << "No service_version received from statestore";
+      protocol_version_ = StatestoreServiceVersion::V1;
+    }
+    if (response.__isset.registration_id) {
+      registration_id_ = response.registration_id;
+      const string& registration_string = PrintId(registration_id_);
+      registration_id_metric_->SetValue(registration_string);
+      VLOG(1) << "Subscriber registration ID: " << registration_string;
+    } else {
+      VLOG(1) << "No subscriber registration ID received from statestore";
+    }
+    if (response.__isset.statestore_id) {
+      statestore_id_ = response.statestore_id;
+      const string& statestore_id_string = PrintId(statestore_id_);
+      statestore_id_metric_->SetValue(statestore_id_string);
+      VLOG(1) << "Statestore ID: " << statestore_id_string;
+    } else {
+      VLOG(1) << "No statestore ID received from statestore";
+    }
+    if (status.ok() && response.__isset.catalogd_registration) {
+      VLOG(1) << "Registered catalogd address: "
+              << TNetworkAddressToString(response.catalogd_registration.address);
+      if (has_registered_catalogd != nullptr) *has_registered_catalogd = true;
+      if (registered_catalogd_registration != nullptr) {
+        *registered_catalogd_registration = response.catalogd_registration;
+      }
+    }
   }
   heartbeat_interval_timer_.Start();
   return status;
 }
 
-Status StatestoreSubscriber::Start() {
+Status StatestoreSubscriber::StatestoreStub::Start(bool* has_registered_catalogd,
+    TCatalogRegistration* registered_catalogd_registration) {
   Status status;
   {
     // Take the lock to ensure that, if a topic-update is received during registration
-    // (perhaps because Register() has succeeded, but we haven't finished setting up state
-    // on the client side), UpdateState() will reject the message.
+    // (perhaps because Register() has succeeded, but we haven't finished setting up
+    // state on the client side), UpdateState() will reject the message.
     lock_guard<shared_mutex> exclusive_lock(lock_);
     LOG(INFO) << "Starting statestore subscriber";
-
-    // Backend must be started before registration
-    std::shared_ptr<TProcessor> processor(
-        new StatestoreSubscriberProcessor(thrift_iface_));
-    std::shared_ptr<TProcessorEventHandler> event_handler(
-        new RpcEventHandler("statestore-subscriber", metrics_));
-    processor->setEventHandler(event_handler);
-
-    ThriftServerBuilder builder(
-        "StatestoreSubscriber", processor, heartbeat_address_.port);
-    if (IsInternalTlsConfigured()) {
-      SSLProtocol ssl_version;
-      RETURN_IF_ERROR(
-          SSLProtoVersions::StringToProtocol(FLAGS_ssl_minimum_version, &ssl_version));
-      LOG(INFO) << "Enabling SSL for Statestore subscriber";
-      builder.ssl(FLAGS_ssl_server_certificate, FLAGS_ssl_private_key)
-          .pem_password_cmd(FLAGS_ssl_private_key_password_cmd)
-          .ssl_version(ssl_version)
-          .cipher_list(FLAGS_ssl_cipher_list);
-    }
-
-    ThriftServer* server;
-    RETURN_IF_ERROR(builder.Build(&server));
-    heartbeat_server_.reset(server);
-    RETURN_IF_ERROR(heartbeat_server_->Start());
-
-    // Resolve the heartbeat address if necessary. Also specify the port which
-    // the heartbeat server is listening on.
-    if (FLAGS_statestore_subscriber_use_resolved_address) {
-      IpAddr ip_address;
-      RETURN_IF_ERROR(HostnameToIpAddr(heartbeat_address_.hostname, &ip_address));
-      heartbeat_address_.hostname = ip_address;
-      LOG(INFO) << Substitute("Registering with statestore with resolved address $0",
-          ip_address);
+    // Inject failure before registering to statestore.
+    status = DebugAction(FLAGS_debug_actions, "REGISTER_STATESTORE_ON_STARTUP");
+    if (status.ok()) {
+      status = Register(has_registered_catalogd, registered_catalogd_registration);
     }
-    heartbeat_address_.port = heartbeat_server_->port();
-
-    LOG(INFO) << "Registering with statestore";
-    status = Register();
     if (status.ok()) {
       is_registered_ = true;
-      LOG(INFO) << "statestore registration successful";
+      LOG(INFO) << "statestore registration successful on startup";
     } else {
-      LOG(INFO) << "statestore registration unsuccessful: " << status.GetDetail();
+      LOG(INFO) << "statestore registration unsuccessful on startup: "
+                << status.GetDetail();
+      if (FLAGS_tolerate_statestore_startup_delay) {
+        LOG(INFO) << "Tolerate the delay of the statestore's availability on startup";
+        status = Status::OK();
+      }
     }
   }
 
-  // Registration is finished at this point, so it's fine to release the lock.
-  RETURN_IF_ERROR(Thread::Create("statestore-subscriber", "recovery-mode-thread",
-      &StatestoreSubscriber::RecoveryModeChecker, this, &recovery_mode_thread_));
-
+  if (status.ok()) {
+    // Registration is finished at this point, so it's fine to release the lock.
+    status = Thread::Create("statestore-subscriber", "recovery-mode-thread",
+        &StatestoreSubscriber::StatestoreStub::RecoveryModeChecker, this,
+        &recovery_mode_thread_);
+  }
   return status;
 }
 
-void StatestoreSubscriber::RecoveryModeChecker() {
-  failure_detector_->UpdateHeartbeat(STATESTORE_ID, true);
+void StatestoreSubscriber::StatestoreStub::RecoveryModeChecker() {
+  // Define a local variable is_registered since we need to hold lock when accessing
+  // class member variable is_registered_.
+  bool is_registered;
+  {
+    lock_guard<shared_mutex> exclusive_lock(lock_);
+    is_registered = is_registered_;
+  }
+  if (is_registered) {
+    failure_detector_->UpdateHeartbeat(STATESTORE_ID, true);
+  }
 
   // Every few seconds, wake up and check if the failure detector has determined
   // that the statestore has failed from our perspective. If so, enter recovery
   // mode and try to reconnect, followed by reregistering all subscriptions.
   while (true) {
-    if (failure_detector_->GetPeerState(STATESTORE_ID) == FailureDetector::FAILED) {
+    FailureDetector::PeerState state = failure_detector_->GetPeerState(STATESTORE_ID);
+    if (state == FailureDetector::FAILED
+        || (state == FailureDetector::UNKNOWN && !is_registered)) {
       // When entering recovery mode, the class-wide lock_ is taken to
       // ensure mutual exclusion with any operations in flight.
       lock_guard<shared_mutex> exclusive_lock(lock_);
@@ -300,19 +525,36 @@ void StatestoreSubscriber::RecoveryModeChecker() {
       recovery_timer.Start();
       connected_to_statestore_metric_->SetValue(false);
       connection_failure_metric_->Increment(1);
-      LOG(INFO) << subscriber_id_
+      LOG(INFO) << subscriber_->subscriber_id_
                 << ": Connection with statestore lost, entering recovery mode";
       uint32_t attempt_count = 1;
+      bool has_registered_catalogd = false;
+      TCatalogRegistration registered_catalogd_registration;
       while (true) {
         LOG(INFO) << "Trying to re-register with statestore, attempt: "
                   << attempt_count++;
-        Status status = Register();
+        re_registr_attempt_metric_->Increment(1);
+        Status status =
+            Register(&has_registered_catalogd, &registered_catalogd_registration);
         if (status.ok()) {
-          // Make sure to update failure detector so that we don't immediately fail on the
-          // next loop while we're waiting for heartbeat messages to resume.
+          if (!is_registered_) {
+            is_registered_ = true;
+            is_registered = true;
+            for (const CompleteRegistrationCallback& callback
+                : complete_registration_callbacks_) {
+              callback();
+            }
+          }
+          // Make sure to update failure detector so that we don't immediately fail on
+          // the next loop while we're waiting for heartbeat messages to resume.
           failure_detector_->UpdateHeartbeat(STATESTORE_ID, true);
           LOG(INFO) << "Reconnected to statestore. Exiting recovery mode";
 
+          if (has_registered_catalogd) {
+            for (const UpdateCatalogdCallback& callback : update_catalogd_callbacks_) {
+              callback(registered_catalogd_registration);
+            }
+          }
           // Break out of enclosing while (true) to top of outer-scope loop.
           break;
         } else {
@@ -338,23 +580,43 @@ void StatestoreSubscriber::RecoveryModeChecker() {
   }
 }
 
-Status StatestoreSubscriber::CheckRegistrationId(const RegistrationId& registration_id) {
-  {
-    lock_guard<mutex> r(registration_id_lock_);
-    // If this subscriber has just started, the registration_id_ may not have been set
-    // despite the statestore starting to send updates. The 'unset' RegistrationId is 0:0,
-    // so we can differentiate between a) an early message from an eager statestore, and
-    // b) a message that's targeted to a previous registration.
-    if (registration_id_ != TUniqueId() && registration_id != registration_id_) {
-      return Status(Substitute("Unexpected registration ID: $0, was expecting $1",
-          PrintId(registration_id), PrintId(registration_id_)));
-    }
+Status StatestoreSubscriber::StatestoreStub::CheckRegistrationId(
+    const RegistrationId& registration_id) {
+  lock_guard<mutex> r(id_lock_);
+  // If this subscriber has just started, the registration_id_ may not have been set
+  // despite the statestore starting to send updates. The 'unset' RegistrationId is 0:0,
+  // so we can differentiate between a) an early message from an eager statestore, and
+  // b) a message that's targeted to a previous registration.
+  if (registration_id_ != TUniqueId() && registration_id != registration_id_) {
+    return Status(Substitute("Unexpected registration ID: $0, was expecting $1",
+        PrintId(registration_id), PrintId(registration_id_)));
   }
+  return Status::OK();
+}
 
+Status StatestoreSubscriber::StatestoreStub::CheckRegistrationIdAndUpdateCatalogdSeq(
+    const RegistrationId& registration_id, int64 sequence){
+  lock_guard<mutex> r(id_lock_);
+  if (registration_id_ != TUniqueId() &&
+      (registration_id != registration_id_ || sequence <= last_update_catalogd_seq_)) {
+    return Status(Substitute("Unexpected registration ID: $0, was expecting $1 "
+        "or unexpected sequence number: $2, was expecting greater than $3",
+            PrintId(registration_id), PrintId(registration_id_), sequence,
+            last_update_catalogd_seq_));
+  }
+  last_update_catalogd_seq_ = sequence;
   return Status::OK();
 }
 
-void StatestoreSubscriber::Heartbeat(const RegistrationId& registration_id) {
+
+bool StatestoreSubscriber::StatestoreStub::IsMatchingStatestoreId(
+    const TUniqueId statestore_id) {
+  lock_guard<mutex> r(id_lock_);
+  return statestore_id == statestore_id_;
+}
+
+void StatestoreSubscriber::StatestoreStub::Heartbeat(
+    const RegistrationId& registration_id) {
   const Status& status = CheckRegistrationId(registration_id);
   if (status.ok()) {
     heartbeat_interval_metric_->Update(
@@ -365,9 +627,22 @@ void StatestoreSubscriber::Heartbeat(const RegistrationId& registration_id) {
   }
 }
 
-Status StatestoreSubscriber::UpdateState(const TopicDeltaMap& incoming_topic_deltas,
-    const RegistrationId& registration_id, vector<TTopicDelta>* subscriber_topic_updates,
-    bool* skipped) {
+void StatestoreSubscriber::StatestoreStub::UpdateCatalogd(
+    const TCatalogRegistration& catalogd_registration,
+    const RegistrationId& registration_id, int64 sequence) {
+  update_catalogd_metric_->Increment(1);
+  const Status& status =
+      CheckRegistrationIdAndUpdateCatalogdSeq(registration_id, sequence);
+  if (status.ok()) {
+    for (const UpdateCatalogdCallback& callback : update_catalogd_callbacks_) {
+      callback(catalogd_registration);
+    }
+  }
+}
+
+Status StatestoreSubscriber::StatestoreStub::UpdateState(
+    const TopicDeltaMap& incoming_topic_deltas, const RegistrationId& registration_id,
+    vector<TTopicDelta>* subscriber_topic_updates, bool* skipped) {
   RETURN_IF_ERROR(CheckRegistrationId(registration_id));
 
   // Put the updates into ascending order of topic name to match the lock acquisition
@@ -488,15 +763,21 @@ Status StatestoreSubscriber::UpdateState(const TopicDeltaMap& incoming_topic_del
     registration.update_interval_timer.Reset();
   }
   sw.Stop();
-  topic_update_duration_metric_->Update(sw.ElapsedTime() / (1000.0 * 1000.0 * 1000.0));
+  topic_update_duration_metric_->Update(
+      sw.ElapsedTime() / (1000.0 * 1000.0 * 1000.0));
   return Status::OK();
 }
 
-bool StatestoreSubscriber::IsInPostRecoveryGracePeriod() const {
+bool StatestoreSubscriber::StatestoreStub::IsInPostRecoveryGracePeriod() const {
   bool has_failed_before = connection_failure_metric_->GetValue() > 0;
   bool in_grace_period = MilliSecondsSinceLastRegistration()
       < FLAGS_statestore_subscriber_recovery_grace_period_ms;
   return has_failed_before && in_grace_period;
 }
 
+bool StatestoreSubscriber::StatestoreStub::IsRegistered() {
+  lock_guard<shared_mutex> exclusive_lock(lock_);
+  return is_registered_;
+}
+
 }
diff --git a/be/src/statestore/statestore-subscriber.h b/be/src/statestore/statestore-subscriber.h
index ddfaf7525..6e65359ea 100644
--- a/be/src/statestore/statestore-subscriber.h
+++ b/be/src/statestore/statestore-subscriber.h
@@ -25,6 +25,7 @@
 #include <boost/thread/shared_mutex.hpp>
 
 #include "gen-cpp/StatestoreService.h"
+#include "gen-cpp/StatestoreService_types.h"
 #include "gen-cpp/StatestoreSubscriber.h"
 #include "rpc/thrift-client.h"
 #include "rpc/thrift-util.h"
@@ -68,15 +69,18 @@ class StatestoreSubscriber {
  public:
   /// Only constructor.
   ///   subscriber_id - should be unique across the cluster, identifies this subscriber
-  //
+  ///
   ///   heartbeat_address - the local address on which the heartbeat service which
   ///                       communicates with the statestore should be started.
-  //
   ///   statestore_address - the address of the statestore to register with
+  ///   subscriber_type - subscriber type
   StatestoreSubscriber(const std::string& subscriber_id,
       const TNetworkAddress& heartbeat_address,
       const TNetworkAddress& statestore_address,
-      MetricGroup* metrics);
+      MetricGroup* metrics,
+      TStatestoreSubscriberType::type subscriber_type);
+
+  virtual ~StatestoreSubscriber() {}
 
   /// A TopicDeltaMap is passed to each callback. See UpdateCallback for more details.
   typedef std::map<Statestore::TopicId, TTopicDelta> TopicDeltaMap;
@@ -102,40 +106,79 @@ class StatestoreSubscriber {
                                 std::vector<TTopicDelta>* topic_updates)> UpdateCallback;
 
   /// Adds a topic to the set of topics that updates will be received
-  /// for. When a topic update is received, the supplied UpdateCallback
-  /// will be invoked. Therefore clients should ensure that it is safe
-  /// to invoke callback for the entire lifetime of the subscriber; in
-  /// particular this means that the subscriber should be torn-down
-  /// before any objects that own callbacks.
-  //
-  /// Must be called before Start(), in which case it will return
-  /// Status::OK. Otherwise an error will be returned.
+  /// for.
   Status AddTopic(const Statestore::TopicId& topic_id, bool is_transient,
       bool populate_min_subscriber_topic_version, std::string filter_prefix,
       const UpdateCallback& callback);
 
+  /// UpdateCatalogdCallback is invoked every time that a notification of updating
+  /// catalogd is received from the statestore.
+  typedef boost::function<void (const TCatalogRegistration& catalogd_registration)>
+      UpdateCatalogdCallback;
+
+  /// Adds a callback for notification of updating catalogd.
+  void AddUpdateCatalogdTopic(const UpdateCatalogdCallback& callback);
+
+  /// CompleteRegistrationCallback is invoked when the registration with the statestore
+  /// is completed.
+  typedef boost::function<void ()>CompleteRegistrationCallback;
+
+  /// Adds a callback for registration completion.
+  void AddCompleteRegistrationTopic(const CompleteRegistrationCallback& callback);
+
   /// Registers this subscriber with the statestore, and starts the
   /// heartbeat service, as well as a thread to check for failure and
   /// initiate recovery mode.
-  //
+  /// has_registered_catalogd - return true if the catalogd is successfully registered
+  ///                           to statestore.
+  /// registered_catalogd_registration - return the address and protocol of the
+  ///                                    registered catalogd.
+  ///
   /// Returns OK unless some error occurred, like a failure to connect.
-  Status Start();
+  virtual Status Start(bool* has_registered_catalogd = nullptr,
+      TCatalogRegistration* registered_catalogd_registration = nullptr);
+
+  /// Set Register Request
+  virtual Status SetRegisterRequest(TRegisterSubscriberRequest* request);
 
   /// Return the port that the subscriber is listening on.
   int heartbeat_port() const { return heartbeat_address_.port; }
 
   const std::string& id() const { return subscriber_id_; }
 
+  StatestoreServiceVersion::type GetProtocolVersion() const {
+    return protocol_version_;
+  }
+
+  CatalogServiceVersion::type GetCatalogProtocolVersion() const {
+    return catalog_protocol_version_;
+  }
+
   /// Returns true if the statestore has recovered and the configurable post-recovery
   /// grace period has not yet elapsed.
   bool IsInPostRecoveryGracePeriod() const;
 
+  /// Returns true if the registration with statestore is completed.
+  bool IsRegistered() const;
+
  private:
   /// Unique, but opaque, identifier for this subscriber.
   const std::string subscriber_id_;
 
-  /// Address of the statestore
-  TNetworkAddress statestore_address_;
+  /// Protocol version of the statestore service for this subscriber.
+  StatestoreServiceVersion::type protocol_version_;
+
+  /// Protocol version of the catalog service for this subscriber.
+  CatalogServiceVersion::type catalog_protocol_version_;
+
+  /// Address that the heartbeat service should be started on. Initialised in constructor,
+  /// updated in Start() with the actual port if the wildcard port 0 was specified.
+  /// If FLAGS_statestore_subscriber_use_resolved_address is true, this address needs to
+  /// be resolved before calling Register() every time.
+  TNetworkAddress heartbeat_address_;
+
+  /// Subscriber type
+  TStatestoreSubscriberType::type subscriber_type_;
 
   /// Implementation of the heartbeat thrift interface, which proxies
   /// calls onto this object.
@@ -144,12 +187,6 @@ class StatestoreSubscriber {
   /// Container for the heartbeat server.
   std::shared_ptr<ThriftServer> heartbeat_server_;
 
-  /// Failure detector that tracks heartbeat messages from the statestore.
-  boost::scoped_ptr<impala::TimeoutFailureDetector> failure_detector_;
-
-  /// Thread in which RecoveryModeChecker runs.
-  std::unique_ptr<Thread> recovery_mode_thread_;
-
   /// statestore client cache - only one client is ever used. Initialized in constructor.
   /// The StatestoreClientCache is created with num_retries = 1 and wait_ms = 0.
   /// Connections are still retried, but the retry mechanism is driven by DoRpcWithRetry.
@@ -160,69 +197,6 @@ class StatestoreSubscriber {
   /// MetricGroup instance that all metrics are registered in. Not owned by this class.
   MetricGroup* metrics_;
 
-  /// Metric to indicate if we are successfully registered with the statestore
-  BooleanProperty* connected_to_statestore_metric_;
-
-  /// Metric to count the total number of connection failures to the statestore
-  IntCounter* connection_failure_metric_;
-
-  /// Amount of time last spent in recovery mode
-  DoubleGauge* last_recovery_duration_metric_;
-
-  /// When the last recovery happened.
-  StringProperty* last_recovery_time_metric_;
-
-  /// Accumulated statistics on the frequency of topic-update messages, including samples
-  /// from all topics.
-  StatsMetric<double>* topic_update_interval_metric_;
-
-  /// Accumulated statistics on the time taken to process each topic-update message from
-  /// the statestore (that is, to call all callbacks)
-  StatsMetric<double>* topic_update_duration_metric_;
-
-  /// Accumulated statistics on the frequency of heartbeat messages
-  StatsMetric<double>* heartbeat_interval_metric_;
-
-  /// Tracks the time between heartbeat messages. Only updated by Heartbeat(), which
-  /// should not run concurrently with itself. Use a ConcurrentStopWatch because the
-  /// watch is started in one thread, but read in another.
-  ConcurrentStopWatch heartbeat_interval_timer_;
-
-  /// Current registration ID, in string form.
-  StringProperty* registration_id_metric_;
-
-  /// Object-wide lock that protects the below members. Must be held exclusively when
-  /// modifying the members, except when modifying TopicRegistrations - see
-  /// TopicRegistration::update_lock for details of locking there. Held in shared mode
-  /// when processing topic updates to prevent concurrent updates to other state. Most
-  /// private methods must be called holding this lock; this is noted in the method
-  /// comments.
-  boost::shared_mutex lock_;
-
-  /// Address that the heartbeat service should be started on. Initialised in constructor,
-  /// updated in Start() with the actual port if the wildcard port 0 was specified.
-  /// If FLAGS_statestore_subscriber_use_resolved_address is true, this is set to the
-  /// resolved IP address in Start().
-  TNetworkAddress heartbeat_address_;
-
-  /// Set to true after Register(...) is successful, after which no
-  /// more topics may be subscribed to.
-  bool is_registered_;
-
-  /// Protects registration_id_. Must be taken after lock_ if both are to be taken
-  /// together.
-  std::mutex registration_id_lock_;
-
-  /// Set during Register(), this is the unique ID of the current registration with the
-  /// statestore. If this subscriber must recover, or disconnects and then reconnects, the
-  /// registration_id_ will change after Register() is called again. This allows the
-  /// subscriber to reject communication from the statestore that pertains to a previous
-  /// registration.
-  RegistrationId registration_id_;
-
-  /// Monotonic timestamp of the last successful registration.
-  AtomicInt64 last_registration_ms_{0};
-
   struct TopicRegistration {
     /// Held when processing a topic update. 'StatestoreSubscriber::lock_' must be held in
     /// shared mode before acquiring this lock. If taking multiple update locks, they must
@@ -259,63 +233,235 @@ class StatestoreSubscriber {
     std::vector<UpdateCallback> callbacks;
   };
 
-  /// One entry for every topic subscribed to. 'lock_' must be held exclusively to add or
-  /// remove entries from the map or held as a shared lock to lookup entries in the map.
-  /// Modifications to the contents of each TopicRegistration is protected by
-  /// TopicRegistration::update_lock.
-  boost::unordered_map<Statestore::TopicId, TopicRegistration> topic_registrations_;
+  /// The subscriber-side representation of an individual statestore instance, which
+  /// tracks variety of bookkeeping information.
+  class StatestoreStub {
+   public:
+    StatestoreStub(StatestoreSubscriber* subscriber,
+        const TNetworkAddress& statestore_address, MetricGroup* metrics);
+
+    /// Returns OK unless some error occurred, like a failure to connect.
+    Status Start(bool* has_registered_catalogd,
+        TCatalogRegistration* registered_catalogd_registration);
+
+    /// Adds a topic to the set of topics that updates will be received
+    /// for. When a topic update is received, the supplied UpdateCallback
+    /// will be invoked. Therefore clients should ensure that it is safe
+    /// to invoke callback for the entire lifetime of the subscriber; in
+    /// particular this means that the subscriber should be torn-down
+    /// before any objects that own callbacks.
+    ///
+    /// Must be called before Start(), in which case it will return
+    /// Status::OK. Otherwise an error will be returned.
+    Status AddTopic(const Statestore::TopicId& topic_id, bool is_transient,
+        bool populate_min_subscriber_topic_version, std::string filter_prefix,
+        const UpdateCallback& callback);
+
+    /// Adds a callback for notification of updating catalogd.
+    void AddUpdateCatalogdTopic(const UpdateCatalogdCallback& callback);
+
+    /// Adds a callback for registration completion.
+    void AddCompleteRegistrationTopic(const CompleteRegistrationCallback& callback);
+
+    /// Called when the statestore sends a topic update. Each registered callback is
+    /// called in turn with the given map of incoming_topic_deltas from the statestore.
+    /// Each TTopicDelta sent from the statestore to the subscriber will contain the
+    /// topic name, a list of additions to the topic, a list of deletions from the topic,
+    /// and the version range the update covers. A from_version of 0 indicates a non-
+    /// delta update. In response, any updates to the topic by the subscriber are
+    /// aggregated in subscriber_topic_updates and returned to the statestore. Each
+    /// update is a TTopicDelta that contains a list of additions to the topic and a list
+    /// of deletions from the topic. Additionally, if a subscriber has received an
+    /// unexpected delta update version range, they can request a new delta update by
+    /// setting the "from_version" field of the TTopicDelta response. The next statestore
+    /// update will be based off the version the subscriber responds with. If the
+    /// subscriber is in recovery mode, this method returns immediately.
+    ///
+    /// Returns an error if some error was encountered (e.g. the supplied registration ID
+    /// was unexpected), and OK otherwise. The output parameter 'skipped' is set to true
+    /// if the subscriber chose not to process this topic-update (if, for example, a
+    /// concurrent update was being processed, or if the subscriber currently believes it
+    /// is recovering). Doing so indicates that no topics were updated during this call.
+    Status UpdateState(const TopicDeltaMap& incoming_topic_deltas,
+        const RegistrationId& registration_id,
+        std::vector<TTopicDelta>* subscriber_topic_updates, bool* skipped);
+
+    /// Called when the statestore sends a heartbeat message. Updates the failure
+    /// detector.
+    void Heartbeat(const RegistrationId& registration_id);
+
+    /// Called when the catalogd has been updated.
+    void UpdateCatalogd(const TCatalogRegistration& catalogd_registration,
+        const RegistrationId& registration_id, int64 sequence);
+
+    /// Run in a separate thread. In a loop, check failure_detector_ to see if the
+    /// statestore is still sending heartbeat messages. If not, enter 'recovery mode'
+    /// where a reconnection is repeatedly attempted. Once reconnected, all existing
+    /// subscriptions and services are reregistered and normal operation resumes.
+    ///
+    /// During recovery mode, any public methods that are started will block on lock_,
+    /// which is only released when recovery finishes. In practice, all registrations are
+    /// made early in the life of an impalad before the statestore could be detected as
+    /// failed.
+    [[noreturn]] void RecoveryModeChecker();
+
+    /// Creates a client of the remote statestore and sends a list of
+    /// topics to register for. Returns OK unless there is some problem
+    /// connecting, or the statestore reports an error.
+    Status Register(bool* has_registered_catalogd,
+        TCatalogRegistration* registered_catalogd_registration);
+
+    /// Returns OK if registration_id == registration_id_, or if registration_id_ is not
+    /// yet set, an error otherwise. Used to confirm that RPCs from the statestore are
+    /// intended for the current registration epoch.
+    Status CheckRegistrationId(const RegistrationId& registration_id);
+
+    // Returns OK if registration_id == registration_id_ and
+    // sequence == last_update_catalogd_seq_.
+    Status CheckRegistrationIdAndUpdateCatalogdSeq(const RegistrationId& registration_id,
+        int64 sequence);
+
+    /// Check if the given statestore ID is matching with the statestore ID of this
+    /// statestore.
+    bool IsMatchingStatestoreId(const TUniqueId statestore_id);
+
+    int64_t MilliSecondsSinceLastRegistration() const {
+      return MonotonicMillis() - last_registration_ms_.Load();
+    }
+
+    bool IsInPostRecoveryGracePeriod() const;
+
+    /// Check if the subscriber is interesting to receive the notification of catalogd
+    /// change.
+    bool IsSubscribedCatalogdChange() { return !update_catalogd_callbacks_.empty(); }
+
+    /// Returns true if the registration with statestore is completed.
+    bool IsRegistered();
+
+   private:
+    /// Pointer to parent StatestoreSubscriber object
+    StatestoreSubscriber* subscriber_;
+
+    /// Address of the statestore
+    TNetworkAddress statestore_address_;
+
+    /// Object-wide lock that protects the below members. Must be held exclusively when
+    /// modifying the members, except when modifying TopicRegistrations - see
+    /// TopicRegistration::update_lock for details of locking there. Held in shared mode
+    /// when processing topic updates to prevent concurrent updates to other state. Most
+    /// private methods must be called holding this lock; this is noted in the method
+    /// comments.
+    boost::shared_mutex lock_;
+
+    /// Failure detector that tracks heartbeat messages from the statestore.
+    boost::scoped_ptr<impala::TimeoutFailureDetector> failure_detector_;
+
+    /// Thread in which RecoveryModeChecker runs.
+    std::unique_ptr<Thread> recovery_mode_thread_;
+
+    /// MetricGroup instance that all metrics are registered in. Not owned by this class.
+    MetricGroup* metrics_;
+
+    /// Metric to indicate if we are successfully registered with the statestore
+    BooleanProperty* connected_to_statestore_metric_;
+
+    /// Metric to count the total number of connection failures to the statestore
+    IntCounter* connection_failure_metric_;
+
+    /// Amount of time last spent in recovery mode
+    DoubleGauge* last_recovery_duration_metric_;
+
+    /// When the last recovery happened.
+    StringProperty* last_recovery_time_metric_;
+
+    /// Accumulated statistics on the frequency of topic-update messages, including
+    /// samples from all topics.
+    StatsMetric<double>* topic_update_interval_metric_;
+
+    /// Accumulated statistics on the time taken to process each topic-update message
+    /// from the statestore (that is, to call all callbacks)
+    StatsMetric<double>* topic_update_duration_metric_;
+
+    /// Accumulated statistics on the frequency of heartbeat messages
+    StatsMetric<double>* heartbeat_interval_metric_;
 
-  /// Subscriber thrift implementation, needs to access UpdateState
-  friend class StatestoreSubscriberThriftIf;
+    /// Current registration ID, in string form.
+    StringProperty* registration_id_metric_;
 
-  /// Called when the statestore sends a topic update. Each registered callback is called
-  /// in turn with the given map of incoming_topic_deltas from the statestore. Each
-  /// TTopicDelta sent from the statestore to the subscriber will contain the topic name, a
-  /// list of additions to the topic, a list of deletions from the topic, and the version
-  /// range the update covers. A from_version of 0 indicates a non-delta update.  In
-  /// response, any updates to the topic by the subscriber are aggregated in
-  /// subscriber_topic_updates and returned to the statestore. Each update is a TTopicDelta
-  /// that contains a list of additions to the topic and a list of deletions from the
-  /// topic. Additionally, if a subscriber has received an unexpected delta update version
-  /// range, they can request a new delta update by setting the "from_version" field of the
-  /// TTopicDelta response. The next statestore update will be based off the version the
-  /// subscriber responds with.  If the subscriber is in recovery mode, this method returns
-  /// immediately.
-  //
-  /// Returns an error if some error was encountered (e.g. the supplied registration ID was
-  /// unexpected), and OK otherwise. The output parameter 'skipped' is set to true if the
-  /// subscriber chose not to process this topic-update (if, for example, a concurrent
-  /// update was being processed, or if the subscriber currently believes it is
-  /// recovering). Doing so indicates that no topics were updated during this call.
+    /// Current statestore ID, in string form.
+    StringProperty* statestore_id_metric_;
+
+    /// Metric to count the total number of UpdateCatalogd RPCs received by subscriber.
+    IntCounter* update_catalogd_metric_;
+
+    /// Metric to count the total number of re-registration attempt.
+    IntCounter* re_registr_attempt_metric_;
+
+    /// Tracks the time between heartbeat messages. Only updated by Heartbeat(), which
+    /// should not run concurrently with itself. Use a ConcurrentStopWatch because the
+    /// watch is started in one thread, but read in another.
+    ConcurrentStopWatch heartbeat_interval_timer_;
+
+    /// One entry for every topic subscribed to. 'lock_' must be held exclusively to add
+    /// or remove entries from the map or held as a shared lock to lookup entries in the
+    /// map. Modifications to the contents of each TopicRegistration is protected by
+    /// TopicRegistration::update_lock.
+    boost::unordered_map<Statestore::TopicId, TopicRegistration> topic_registrations_;
+
+    /// Callback functions to handle the notification of updating catalogD.
+    std::vector<UpdateCatalogdCallback> update_catalogd_callbacks_;
+
+    /// Callback functions for registration completion.
+    std::vector<CompleteRegistrationCallback> complete_registration_callbacks_;
+
+    /// Set to true after Register(...) is successful, after which no
+    /// more topics may be subscribed to.
+    bool is_registered_;
+
+    /// Protects registration_id_, protocol_version_ and statestore_id_. Must be taken
+    /// after lock_ if both are to be taken together.
+    std::mutex id_lock_;
+
+    /// Set during Register(), this is the unique ID of the current registration with the
+    /// statestore. If this subscriber must recover, or disconnects and then reconnects,
+    /// the registration_id_ will change after Register() is called again. This allows
+    /// the subscriber to reject communication from the statestore that pertains to a
+    /// previous registration.
+    RegistrationId registration_id_;
+
+    /// Protocol version of the statestore, which is returned in the registration response
+    /// from the statestore.
+    StatestoreServiceVersion::type protocol_version_;
+
+    /// Instance ID of the statestore, which is returned in the registration response
+    /// from the statestore.
+    TUniqueId statestore_id_;
+
+    // Last sequence number for notification of changing active CatalogD.
+    int64 last_update_catalogd_seq_ = 0;
+
+    /// Monotonic timestamp of the last successful registration.
+    AtomicInt64 last_registration_ms_{0};
+  };
+
+  // statestore instances
+  StatestoreStub* statestore_ = nullptr;
+
+  /// Called when the statestore sends a topic update.
   Status UpdateState(const TopicDeltaMap& incoming_topic_deltas,
-      const RegistrationId& registration_id,
+      const RegistrationId& registration_id, const TUniqueId& statestore_id,
       std::vector<TTopicDelta>* subscriber_topic_updates, bool* skipped);
 
-  /// Called when the statestore sends a heartbeat message. Updates the failure detector.
-  void Heartbeat(const RegistrationId& registration_id);
+  /// Called when the statestore sends a heartbeat message.
+  void Heartbeat(const RegistrationId& registration_id,
+      const TUniqueId& statestore_id);
 
-  /// Run in a separate thread. In a loop, check failure_detector_ to see if the statestore
-  /// is still sending heartbeat messages. If not, enter 'recovery mode' where a
-  /// reconnection is repeatedly attempted. Once reconnected, all existing subscriptions
-  /// and services are reregistered and normal operation resumes.
-  //
-  /// During recovery mode, any public methods that are started will block on lock_, which
-  /// is only released when recovery finishes. In practice, all registrations are made
-  /// early in the life of an impalad before the statestore could be detected as failed.
-  [[noreturn]] void RecoveryModeChecker();
-
-  /// Creates a client of the remote statestore and sends a list of
-  /// topics to register for. Returns OK unless there is some problem
-  /// connecting, or the statestore reports an error.
-  Status Register();
-
-  /// Returns OK if registration_id == registration_id_, or if registration_id_ is not yet
-  /// set, an error otherwise. Used to confirm that RPCs from the statestore are intended
-  /// for the current registration epoch.
-  Status CheckRegistrationId(const RegistrationId& registration_id);
-
-  int64_t MilliSecondsSinceLastRegistration() const {
-    return MonotonicMillis() - last_registration_ms_.Load();
-  }
+  /// Called when the catalogd has been updated.
+  void UpdateCatalogd(const TCatalogRegistration& catalogd_registration,
+      const RegistrationId& registration_id, const TUniqueId& statestore_id,
+      int64 sequence);
+
+  /// Subscriber thrift implementation, needs to access UpdateState
+  friend class StatestoreSubscriberThriftIf;
 };
 }
diff --git a/be/src/statestore/statestore-test.cc b/be/src/statestore/statestore-test.cc
index 4d1bac900..beed00df6 100644
--- a/be/src/statestore/statestore-test.cc
+++ b/be/src/statestore/statestore-test.cc
@@ -57,13 +57,15 @@ TEST(StatestoreTest, SmokeTest) {
 
   StatestoreSubscriber* sub_will_start = perm_objects->Add(
       new StatestoreSubscriber("sub1", MakeNetworkAddress("localhost", 0),
-          MakeNetworkAddress("localhost", statestore->port()), new MetricGroup("")));
+          MakeNetworkAddress("localhost", statestore->port()),
+          new MetricGroup(""), TStatestoreSubscriberType::COORDINATOR_EXECUTOR));
   ASSERT_OK(sub_will_start->Start());
 
   // Confirm that a subscriber trying to use an in-use port will fail to start.
   StatestoreSubscriber* sub_will_not_start = perm_objects->Add(new StatestoreSubscriber(
       "sub3", MakeNetworkAddress("localhost", sub_will_start->heartbeat_port()),
-      MakeNetworkAddress("localhost", statestore->port()), new MetricGroup("")));
+      MakeNetworkAddress("localhost", statestore->port()),
+      new MetricGroup(""), TStatestoreSubscriberType::COORDINATOR_EXECUTOR));
   ASSERT_FALSE(sub_will_not_start->Start().ok());
 
   statestore->ShutdownForTesting();
@@ -91,7 +93,8 @@ void SslSmokeTestHelper(const string& server_ca_certificate,
 
   StatestoreSubscriber* sub = perm_objects->Add(
       new StatestoreSubscriber("smoke_sub", MakeNetworkAddress("localhost", 0),
-          MakeNetworkAddress("localhost", statestore->port()), new MetricGroup("")));
+          MakeNetworkAddress("localhost", statestore->port()),
+          new MetricGroup(""), TStatestoreSubscriberType::COORDINATOR_EXECUTOR));
   Status sub_status = sub->Start();
   ASSERT_EQ(sub_should_start, sub_status.ok());
 
diff --git a/be/src/statestore/statestore.cc b/be/src/statestore/statestore.cc
index bf2e800a0..840c2d630 100644
--- a/be/src/statestore/statestore.cc
+++ b/be/src/statestore/statestore.cc
@@ -23,6 +23,7 @@
 
 #include <boost/lexical_cast.hpp>
 #include <thrift/Thrift.h>
+#include <thrift/protocol/TProtocolException.h>
 #include <gutil/strings/substitute.h>
 #include <gutil/strings/util.h>
 
@@ -106,12 +107,20 @@ DEFINE_int32(statestore_update_tcp_timeout_seconds, 300, "(Advanced) The time af
     "badly hung machines that are not able to respond to the update RPC in short "
     "order.");
 
+DEFINE_int32(statestore_update_catalogd_tcp_timeout_seconds, 3, "(Advanced) The "
+    "time after which a UpdateCatalogd RPC to a subscriber will timeout. This setting "
+    "protects against badly hung machines that are not able to respond to the "
+    "UpdateCatalogd RPC in short order");
+
 DECLARE_string(debug_actions);
 DECLARE_string(ssl_server_certificate);
 DECLARE_string(ssl_private_key);
 DECLARE_string(ssl_private_key_password_cmd);
 DECLARE_string(ssl_cipher_list);
 DECLARE_string(ssl_minimum_version);
+#ifndef NDEBUG
+DECLARE_int32(stress_statestore_startup_delay_ms);
+#endif
 
 // Metric keys
 // TODO: Replace 'backend' with 'subscriber' when we can coordinate a change with CM
@@ -124,6 +133,7 @@ const string STATESTORE_UPDATE_DURATION = "statestore.topic-update-durations";
 const string STATESTORE_PRIORITY_UPDATE_DURATION =
     "statestore.priority-topic-update-durations";
 const string STATESTORE_HEARTBEAT_DURATION = "statestore.heartbeat-durations";
+const string STATESTORE_UPDATE_CATALOGD_NUM = "statestore.num-update-catalogd";
 
 // Initial version for each Topic registered by a Subscriber. Generally, the Topic will
 // have a Version that is the MAX() of all entries in the Topic, but this initial
@@ -140,6 +150,28 @@ const char* Statestore::IMPALA_REQUEST_QUEUE_TOPIC = "impala-request-queue";
 
 typedef ClientConnection<StatestoreSubscriberClientWrapper> StatestoreSubscriberConn;
 
+namespace impala {
+
+std::string SubscriberTypeToString(TStatestoreSubscriberType::type t) {
+  switch (t) {
+    case TStatestoreSubscriberType::ADMISSIOND:
+      return "ADMISSIOND";
+    case TStatestoreSubscriberType::CATALOGD:
+      return "CATALOGD";
+    case TStatestoreSubscriberType::COORDINATOR:
+      return "COORDINATOR";
+    case TStatestoreSubscriberType::EXECUTOR:
+      return "EXECUTOR";
+    case TStatestoreSubscriberType::COORDINATOR_EXECUTOR:
+      return "COORDINATOR AND EXECUTOR";
+    case TStatestoreSubscriberType::UNKNOWN:
+    default:
+      return "UNKNOWN";
+  };
+}
+
+}
+
 class StatestoreThriftIf : public StatestoreServiceIf {
  public:
   StatestoreThriftIf(Statestore* statestore)
@@ -149,12 +181,63 @@ class StatestoreThriftIf : public StatestoreServiceIf {
 
   virtual void RegisterSubscriber(TRegisterSubscriberResponse& response,
       const TRegisterSubscriberRequest& params) {
+    if (FLAGS_debug_actions == "START_STATESTORE_IN_PROTOCOL_V1"
+        && strncmp(params.subscriber_id.c_str(), "python-test-client", 18) == 0
+        && params.protocol_version > StatestoreServiceVersion::V1) {
+      // Simulate the behaviour of old statestore to throw exception for new version
+      // of subscribers.
+      throw apache::thrift::protocol::TProtocolException(
+          apache::thrift::protocol::TProtocolException::INVALID_DATA, "Invalid data");
+    }
+    if (params.protocol_version < statestore_->GetProtocolVersion()) {
+      // Refuse old version of subscribers
+      response.__set_protocol_version(statestore_->GetProtocolVersion());
+      response.__set_statestore_id(statestore_->GetStateStoreId());
+      Status status = Status(TErrorCode::STATESTORE_INCOMPATIBLE_PROTOCOL,
+          params.subscriber_id, params.protocol_version + 1,
+          statestore_->GetProtocolVersion() + 1);
+      status.ToThrift(&response.status);
+      return;
+    }
+    TStatestoreSubscriberType::type subscriber_type = TStatestoreSubscriberType::UNKNOWN;
+    if (params.__isset.subscriber_type) {
+      subscriber_type = params.subscriber_type;
+    }
+    bool subscribe_catalogd_change = false;
+    if (params.__isset.subscribe_catalogd_change) {
+      subscribe_catalogd_change = params.subscribe_catalogd_change;
+    }
+    TCatalogRegistration catalogd_registration;
+    if (params.__isset.catalogd_registration) {
+      catalogd_registration = params.catalogd_registration;
+    }
+
     RegistrationId registration_id;
+    bool has_registered_catalogd;
+    TCatalogRegistration registered_catalogd_registration;
     Status status = statestore_->RegisterSubscriber(params.subscriber_id,
-        params.subscriber_location, params.topic_registrations, &registration_id);
+        params.subscriber_location, params.topic_registrations, subscriber_type,
+        subscribe_catalogd_change, catalogd_registration, &registration_id,
+        &has_registered_catalogd, &registered_catalogd_registration);
     status.ToThrift(&response.status);
     response.__set_registration_id(registration_id);
+    response.__set_statestore_id(statestore_->GetStateStoreId());
+    response.__set_protocol_version(statestore_->GetProtocolVersion());
+    if (has_registered_catalogd) {
+      response.__set_catalogd_registration(registered_catalogd_registration);
+    }
+  }
+
+  virtual void GetProtocolVersion(TGetProtocolVersionResponse& response,
+      const TGetProtocolVersionRequest& params) {
+    LOG(INFO) << "Subscriber protocol version: " << params.protocol_version;
+    response.__set_protocol_version(statestore_->GetProtocolVersion());
+    response.__set_statestore_id(statestore_->GetStateStoreId());
+    Status status = Status::OK();
+    status.ToThrift(&response.status);
+    return;
   }
+
  private:
   Statestore* statestore_;
 };
@@ -318,10 +401,16 @@ void Statestore::Topic::ToJson(Document* document, Value* topic_json) {
 
 Statestore::Subscriber::Subscriber(const SubscriberId& subscriber_id,
     const RegistrationId& registration_id, const TNetworkAddress& network_address,
-    const vector<TTopicRegistration>& subscribed_topics)
+    const vector<TTopicRegistration>& subscribed_topics,
+    TStatestoreSubscriberType::type subscriber_type, bool subscribe_catalogd_change)
   : subscriber_id_(subscriber_id),
     registration_id_(registration_id),
-    network_address_(network_address) {
+    network_address_(network_address),
+    subscriber_type_(subscriber_type),
+    subscribe_catalogd_change_(subscribe_catalogd_change) {
+  LOG(INFO) << "Subscriber '" << subscriber_id_
+            << "' with type " << SubscriberTypeToString(subscriber_type_)
+            << " registered (registration id: " << PrintId(registration_id_) << ")";
   RefreshLastHeartbeatTimestamp();
   for (const TTopicRegistration& topic : subscribed_topics) {
     GetTopicsMapForId(topic.topic_name)
@@ -406,7 +495,8 @@ void Statestore::Subscriber::RefreshLastHeartbeatTimestamp() {
 }
 
 Statestore::Statestore(MetricGroup* metrics)
-  : subscriber_topic_update_threadpool_("statestore-update",
+  : protocol_version_(StatestoreServiceVersion::V2),
+    subscriber_topic_update_threadpool_("statestore-update",
         "subscriber-update-worker",
         FLAGS_statestore_num_update_threads,
         FLAGS_statestore_max_subscribers,
@@ -432,10 +522,15 @@ Statestore::Statestore(MetricGroup* metrics)
         FLAGS_statestore_heartbeat_tcp_timeout_seconds * 1000,
         FLAGS_statestore_heartbeat_tcp_timeout_seconds * 1000, "",
         IsInternalTlsConfigured())),
+    update_catalogd_client_cache_(new StatestoreSubscriberClientCache(1, 0,
+        FLAGS_statestore_update_catalogd_tcp_timeout_seconds * 1000,
+        FLAGS_statestore_update_catalogd_tcp_timeout_seconds * 1000, "",
+        IsInternalTlsConfigured())),
     thrift_iface_(new StatestoreThriftIf(this)),
     failure_detector_(new MissedHeartbeatFailureDetector(
         FLAGS_statestore_max_missed_heartbeats,
         FLAGS_statestore_max_missed_heartbeats / 2)) {
+  UUIDToTUniqueId(boost::uuids::random_generator()(), &statestore_id_);
   DCHECK(metrics != NULL);
   metrics_ = metrics;
   num_subscribers_metric_ = metrics->AddGauge(STATESTORE_LIVE_SUBSCRIBERS, 0);
@@ -451,9 +546,12 @@ Statestore::Statestore(MetricGroup* metrics)
       metrics, STATESTORE_PRIORITY_UPDATE_DURATION);
   heartbeat_duration_metric_ =
       StatsMetric<double>::CreateAndRegister(metrics, STATESTORE_HEARTBEAT_DURATION);
+  update_catalogd_metric_ = metrics->AddCounter(STATESTORE_UPDATE_CATALOGD_NUM, 0);
 
   update_state_client_cache_->InitMetrics(metrics, "subscriber-update-state");
   heartbeat_client_cache_->InitMetrics(metrics, "subscriber-heartbeat");
+  update_catalogd_client_cache_->InitMetrics(
+      metrics, "subscriber-update-catalogd");
 }
 
 Statestore::~Statestore() {
@@ -461,6 +559,13 @@ Statestore::~Statestore() {
 }
 
 Status Statestore::Init(int32_t state_store_port) {
+#ifndef NDEBUG
+  if (FLAGS_stress_statestore_startup_delay_ms > 0) {
+    LOG(INFO) << "Stress statestore startup delay: "
+              << FLAGS_stress_statestore_startup_delay_ms << " ms";
+    SleepForMs(FLAGS_stress_statestore_startup_delay_ms);
+  }
+#endif
   std::shared_ptr<TProcessor> processor(new StatestoreServiceProcessor(thrift_iface()));
   std::shared_ptr<TProcessorEventHandler> event_handler(
       new RpcEventHandler("statestore", metrics_));
@@ -486,6 +591,8 @@ Status Statestore::Init(int32_t state_store_port) {
   RETURN_IF_ERROR(subscriber_heartbeat_threadpool_.Init());
   RETURN_IF_ERROR(Thread::Create("statestore-heartbeat", "heartbeat-monitoring-thread",
       &Statestore::MonitorSubscriberHeartbeat, this, &heartbeat_monitoring_thread_));
+  RETURN_IF_ERROR(Thread::Create("statestore-update-catalogd", "update-catalogd-thread",
+      &Statestore::MonitorUpdateCatalogd, this, &update_catalogd_thread_));
   service_started_ = true;
 
   return Status::OK();
@@ -604,8 +711,16 @@ Status Statestore::OfferUpdate(const ScheduledSubscriberUpdate& update,
 Status Statestore::RegisterSubscriber(const SubscriberId& subscriber_id,
     const TNetworkAddress& location,
     const vector<TTopicRegistration>& topic_registrations,
-    RegistrationId* registration_id) {
-  if (subscriber_id.empty()) return Status("Subscriber ID cannot be empty string");
+    TStatestoreSubscriberType::type subscriber_type,
+    bool subscribe_catalogd_change,
+    const TCatalogRegistration& catalogd_registration,
+    RegistrationId* registration_id,
+    bool* has_registered_catalogd,
+    TCatalogRegistration* registered_catalogd_registration) {
+  bool is_catalogd = subscriber_type == TStatestoreSubscriberType::CATALOGD;
+  if (subscriber_id.empty()) {
+    return Status("Subscriber ID cannot be empty string");
+  }
 
   // Create any new topics first, so that when the subscriber is first sent a topic update
   // by the worker threads its topics are guaranteed to exist.
@@ -630,14 +745,32 @@ Status Statestore::RegisterSubscriber(const SubscriberId& subscriber_id,
   LOG(INFO) << "Registering: " << subscriber_id;
   {
     lock_guard<mutex> l(subscribers_lock_);
+    UUIDToTUniqueId(subscriber_uuid_generator_(), registration_id);
     SubscriberMap::iterator subscriber_it = subscribers_.find(subscriber_id);
     if (subscriber_it != subscribers_.end()) {
-      UnregisterSubscriber(subscriber_it->second.get());
+      shared_ptr<Subscriber> subscriber = subscriber_it->second;
+      UnregisterSubscriber(subscriber.get());
+      // Check if the subscriber's network addresses are matching.
+      if (subscriber->network_address().hostname != location.hostname
+          || subscriber->network_address().port != location.port) {
+        LOG(INFO) << "Subscriber " << subscriber_id
+                  << " re-register with different address, old address: "
+                  << TNetworkAddressToString(subscriber->network_address())
+                  << " , new address: " << TNetworkAddressToString(location);
+      }
     }
 
-    UUIDToTUniqueId(subscriber_uuid_generator_(), registration_id);
-    shared_ptr<Subscriber> current_registration(
-        new Subscriber(subscriber_id, *registration_id, location, topic_registrations));
+    if (is_catalogd) {
+      if (catalog_manager_.RegisterCatalogd(subscriber_id, *registration_id,
+              catalogd_registration)) {
+        LOG(INFO) << "CatalogD: " << subscriber_id << " is registered.";
+        update_catalod_cv_.NotifyAll();
+      }
+    }
+
+    shared_ptr<Subscriber> current_registration(new Subscriber(
+        subscriber_id, *registration_id, location, topic_registrations,
+        subscriber_type, subscribe_catalogd_change));
     subscribers_.emplace(subscriber_id, current_registration);
     failure_detector_->UpdateHeartbeat(subscriber_id, true);
     num_subscribers_metric_->SetValue(subscribers_.size());
@@ -648,13 +781,36 @@ Status Statestore::RegisterSubscriber(const SubscriberId& subscriber_id,
     RETURN_IF_ERROR(OfferUpdate(update, &subscriber_topic_update_threadpool_));
     RETURN_IF_ERROR(OfferUpdate(update, &subscriber_priority_topic_update_threadpool_));
     RETURN_IF_ERROR(OfferUpdate(update, &subscriber_heartbeat_threadpool_));
+    *registered_catalogd_registration =
+        catalog_manager_.GetCatalogRegistration(has_registered_catalogd);
   }
 
-  LOG(INFO) << "Subscriber '" << subscriber_id << "' registered (registration id: "
-            << PrintId(*registration_id) << ")";
   return Status::OK();
 }
 
+bool Statestore::CatalogManager::RegisterCatalogd(const SubscriberId& subscriber_id,
+    const RegistrationId& registration_id,
+    const TCatalogRegistration& catalogd_registration) {
+  lock_guard<mutex> l(catalog_mgr_lock_);
+  is_registered_ = true;
+  catalogd_subscriber_id_ = subscriber_id;
+  catalogd_registration_id_ = registration_id;
+  catalogd_registration_ = catalogd_registration;
+  return true;
+}
+
+const TCatalogRegistration& Statestore::CatalogManager::GetCatalogRegistration(
+    bool* is_registered) {
+  lock_guard<mutex> l(catalog_mgr_lock_);
+  *is_registered = is_registered_;
+  return catalogd_registration_;
+}
+
+int64 Statestore::CatalogManager::GetSendingSequence() {
+  lock_guard<mutex> l(catalog_mgr_lock_);
+  return ++sending_sequence_;
+}
+
 bool Statestore::FindSubscriber(const SubscriberId& subscriber_id,
     const RegistrationId& registration_id, shared_ptr<Subscriber>* subscriber) {
   DCHECK(subscriber != nullptr);
@@ -685,6 +841,7 @@ Status Statestore::SendTopicUpdate(Subscriber* subscriber, UpdateKind update_kin
   // Set the expected registration ID, so that the subscriber can reject this update if
   // they have moved on to a new registration instance.
   update_state_request.__set_registration_id(subscriber->registration_id());
+  update_state_request.__set_statestore_id(statestore_id_);
 
   // Second: try and send it
   Status status;
@@ -877,6 +1034,7 @@ Status Statestore::SendHeartbeat(Subscriber* subscriber) {
   THeartbeatRequest request;
   THeartbeatResponse response;
   request.__set_registration_id(subscriber->registration_id());
+  request.__set_statestore_id(statestore_id_);
   RETURN_IF_ERROR(
       client.DoRpc(&StatestoreSubscriberClientWrapper::Heartbeat, request, &response));
 
@@ -1042,6 +1200,63 @@ void Statestore::DoSubscriberUpdate(UpdateKind update_kind, int thread_id,
   }
 }
 
+[[noreturn]] void Statestore::MonitorUpdateCatalogd() {
+  // Wait for notification. If catalogd is registered, send notification to all
+  // coordinators
+  while (1) {
+    {
+      unique_lock<mutex> l(*catalog_manager_.GetLock());
+      update_catalod_cv_.Wait(l);
+    }
+    SendUpdateCatalogdNotification();
+  }
+}
+
+void Statestore::SendUpdateCatalogdNotification() {
+  bool has_registered_catalogd;
+  TCatalogRegistration catalogd_registration =
+      catalog_manager_.GetCatalogRegistration(&has_registered_catalogd);
+  DCHECK(has_registered_catalogd);
+  if (!has_registered_catalogd) return;
+
+  vector<std::shared_ptr<Subscriber>> receivers;
+  {
+    lock_guard<mutex> l(subscribers_lock_);
+    for (const auto& subscriber : subscribers_) {
+      if (subscriber.second->IsSubscribedCatalogdChange()) {
+        receivers.push_back(subscriber.second);
+      }
+    }
+  }
+  for (const auto& subscriber : receivers) {
+    Status status;
+    StatestoreSubscriberConn client(update_catalogd_client_cache_.get(),
+        subscriber->network_address(), &status);
+    if (status.ok()) {
+      TUpdateCatalogdRequest request;
+      TUpdateCatalogdResponse response;
+      request.__set_registration_id(subscriber->registration_id());
+      request.__set_statestore_id(statestore_id_);
+      request.__set_sequence(catalog_manager_.GetSendingSequence());
+      request.__set_catalogd_registration(catalogd_registration);
+      status = client.DoRpc(
+          &StatestoreSubscriberClientWrapper::UpdateCatalogd, request, &response);
+      if (!status.ok()) {
+        if (status.code() == TErrorCode::RPC_RECV_TIMEOUT) {
+          // Add details to status to make it more useful, while preserving the stack
+          status.AddDetail(Substitute(
+              "Subscriber $0 timed-out during update catalogd RPC. Timeout is $1s.",
+                  subscriber->id(),
+                  FLAGS_statestore_update_catalogd_tcp_timeout_seconds));
+        }
+        LOG(ERROR) << "Couldn't send UpdateCatalogd RPC,  " << status.GetDetail();
+      } else {
+        update_catalogd_metric_->Increment(1);
+      }
+    }
+  }
+}
+
 void Statestore::UnregisterSubscriber(Subscriber* subscriber) {
   SubscriberMap::const_iterator it = subscribers_.find(subscriber->id());
   if (it == subscribers_.end() ||
@@ -1053,6 +1268,7 @@ void Statestore::UnregisterSubscriber(Subscriber* subscriber) {
   // Close all active clients so that the next attempt to use them causes a Reopen()
   update_state_client_cache_->CloseConnections(subscriber->network_address());
   heartbeat_client_cache_->CloseConnections(subscriber->network_address());
+  update_catalogd_client_cache_->CloseConnections(subscriber->network_address());
 
   // Prevent the failure detector from growing without bound
   failure_detector_->EvictPeer(subscriber->id());
diff --git a/be/src/statestore/statestore.h b/be/src/statestore/statestore.h
index 1b43e111a..2a21fa6a6 100644
--- a/be/src/statestore/statestore.h
+++ b/be/src/statestore/statestore.h
@@ -32,6 +32,7 @@
 #include "common/atomic.h"
 #include "common/status.h"
 #include "gen-cpp/StatestoreService.h"
+#include "gen-cpp/StatestoreService_types.h"
 #include "gen-cpp/StatestoreSubscriber.h"
 #include "gen-cpp/Types_types.h"
 #include "rpc/thrift-client.h"
@@ -39,6 +40,7 @@
 #include "statestore/failure-detector.h"
 #include "statestore/statestore-subscriber-client-wrapper.h"
 #include "util/aligned-new.h"
+#include "util/condition-variable.h"
 #include "util/metrics-fwd.h"
 #include "util/thread-pool.h"
 #include "util/webserver.h"
@@ -52,6 +54,8 @@ class Status;
 typedef ClientCache<StatestoreSubscriberClientWrapper> StatestoreSubscriberClientCache;
 typedef TUniqueId RegistrationId;
 
+std::string SubscriberTypeToString(TStatestoreSubscriberType::type t);
+
 /// The Statestore is a soft-state key-value store that maintains a set of Topics, which
 /// are maps from string keys to byte array values.
 ///
@@ -104,6 +108,13 @@ typedef TUniqueId RegistrationId;
 /// These empty updates are important so that subscribers can keep track of the current
 /// version number and report back their progress in receiving the topic contents.
 ///
+/// The Statestore is the central manager of the cluster. Subscribers join in the cluster
+/// through registration. To avoid incompatibility issues between the different components
+/// in the cluster, statestore uses protocol version to isolate cluster components, and
+/// only accepts the registration requests from the subscribers with compatible protocol
+/// versions. This ensure all of components in a cluster could communicate with compatible
+/// APIs and message format in the wire.
+///
 /// +================+
 /// | Implementation |
 /// +================+
@@ -153,7 +164,12 @@ class Statestore : public CacheLineAligned {
   Status RegisterSubscriber(const SubscriberId& subscriber_id,
       const TNetworkAddress& location,
       const std::vector<TTopicRegistration>& topic_registrations,
-      RegistrationId* registration_id) WARN_UNUSED_RESULT;
+      TStatestoreSubscriberType::type subscriber_type,
+      bool subscribe_catalogd_change,
+      const TCatalogRegistration& catalogd_registration,
+      RegistrationId* registration_id,
+      bool* has_registered_catalogd,
+      TCatalogRegistration* registered_catalogd_registration);
 
   /// Registers webpages for the input webserver. If metrics_only is set then only
   /// '/healthz' page is registered.
@@ -187,6 +203,12 @@ class Statestore : public CacheLineAligned {
   /// after it stops responding to heartbeats.
   static int64_t FailedExecutorDetectionTimeMs();
 
+  const TUniqueId& GetStateStoreId() const { return statestore_id_; }
+
+  StatestoreServiceVersion::type GetProtocolVersion() const {
+    return protocol_version_;
+  }
+
  private:
   /// A TopicEntry is a single entry in a topic, and logically is a <string, byte string>
   /// pair.
@@ -358,7 +380,9 @@ class Statestore : public CacheLineAligned {
    public:
     Subscriber(const SubscriberId& subscriber_id, const RegistrationId& registration_id,
         const TNetworkAddress& network_address,
-        const std::vector<TTopicRegistration>& subscribed_topics);
+        const std::vector<TTopicRegistration>& subscribed_topics,
+        TStatestoreSubscriberType::type subscriber_type,
+        bool subscribe_catalogd_change);
 
     /// Information about a subscriber's subscription to a specific topic.
     struct TopicSubscription {
@@ -454,6 +478,16 @@ class Statestore : public CacheLineAligned {
     /// Refresh the subscriber's last heartbeat timestamp to the current monotonic time.
     void RefreshLastHeartbeatTimestamp();
 
+    /// Check if the subscriber is Catalog daemon.
+    bool IsCatalogd() const {
+      return subscriber_type_ == TStatestoreSubscriberType::CATALOGD;
+    }
+
+    /// Check if the subscriber wants to receive the notification of catalogd change.
+    bool IsSubscribedCatalogdChange() const {
+      return subscribe_catalogd_change_;
+    }
+
    private:
     /// Unique human-readable identifier for this subscriber, set by the subscriber itself
     /// on a Register call.
@@ -468,6 +502,12 @@ class Statestore : public CacheLineAligned {
     /// The location of the subscriber service that this subscriber runs.
     const TNetworkAddress network_address_;
 
+    /// Subscriber type
+    TStatestoreSubscriberType::type subscriber_type_;
+
+    /// Indicate if the subscriber subscribe to the notification of updating catalogd.
+    bool subscribe_catalogd_change_;
+
     /// Maps of topic subscriptions to current TopicSubscription, with separate maps for
     /// priority and non-priority topics. The state describes whether updates on the
     /// topic are 'transient' (i.e., to be deleted upon subscriber failure) or not
@@ -489,6 +529,54 @@ class Statestore : public CacheLineAligned {
     bool unregistered_ = false;
   };
 
+  /// CatalogManager:
+  ///   Tracks variety of bookkeeping information for Catalog daemon.
+  class CatalogManager {
+   public:
+    CatalogManager()
+      : is_registered_(false),
+        sending_sequence_(0) {}
+
+    /// Register one catalogd.
+    bool RegisterCatalogd(const SubscriberId& subscriber_id,
+        const RegistrationId& registration_id,
+        const TCatalogRegistration& catalogd_registration);
+
+    /// Return the protocol version of catalog service and address of catalogd.
+    const TCatalogRegistration& GetCatalogRegistration(bool* is_registered);
+
+    /// Return the mutex lock.
+    std::mutex* GetLock() { return &catalog_mgr_lock_; }
+
+    /// Get sending sequence number.
+    int64 GetSendingSequence();
+
+   private:
+    /// Protect all member variable.
+    std::mutex catalog_mgr_lock_;
+
+    /// Indicate if the catalogd has been registered.
+    bool is_registered_;
+
+    /// subscriber_id of the registered catalogd.
+    SubscriberId catalogd_subscriber_id_;
+
+    /// RegistrationId of the registered catalogd.
+    RegistrationId catalogd_registration_id_;
+
+    /// Additional registration info for catalog daemon.
+    TCatalogRegistration catalogd_registration_;
+
+    /// Sending sequence number.
+    int64 sending_sequence_;
+  };
+
+  /// Unique identifier for this statestore instance.
+  TUniqueId statestore_id_;
+
+  /// Protocol version of the statestore.
+  StatestoreServiceVersion::type protocol_version_;
+
   /// Protects access to subscribers_ and subscriber_uuid_generator_. See the class
   /// comment for the lock acquisition order.
   std::mutex subscribers_lock_;
@@ -501,10 +589,15 @@ class Statestore : public CacheLineAligned {
   /// Subscribers are held in shared_ptrs so that RegisterSubscriber() may overwrite their
   /// entry in this map while UpdateSubscriber() tries to update an existing registration
   /// without risk of use-after-free.
-  typedef boost::unordered_map<SubscriberId, std::shared_ptr<Subscriber>>
-    SubscriberMap;
+  typedef boost::unordered_map<SubscriberId, std::shared_ptr<Subscriber>> SubscriberMap;
   SubscriberMap subscribers_;
 
+  /// CatalogD Manager
+  CatalogManager catalog_manager_;
+
+  /// Condition variable for sending the notifications of updating catalogd.
+  ConditionVariable update_catalod_cv_;
+
   /// Used to generated unique IDs for each new registration.
   boost::uuids::random_generator subscriber_uuid_generator_;
 
@@ -568,6 +661,9 @@ class Statestore : public CacheLineAligned {
   /// Thread that monitors the heartbeats of all subscribers.
   std::unique_ptr<Thread> heartbeat_monitoring_thread_;
 
+  /// Thread to send notification of updating catalogd.
+  std::unique_ptr<Thread> update_catalogd_thread_;
+
   /// Indicates whether the statestore has been initialized and the service is ready.
   std::atomic_bool service_started_{false};
 
@@ -581,6 +677,11 @@ class Statestore : public CacheLineAligned {
   /// of time.
   boost::scoped_ptr<StatestoreSubscriberClientCache> heartbeat_client_cache_;
 
+  /// Cache of subscriber clients used for UpdateCatalogd() RPCs. Only one client per
+  /// subscriber should be used, but the cache helps with the client lifecycle on
+  /// failure.
+  boost::scoped_ptr<StatestoreSubscriberClientCache> update_catalogd_client_cache_;
+
   /// Container for the internal statestore service.
   boost::scoped_ptr<ThriftServer> thrift_server_;
 
@@ -617,6 +718,9 @@ class Statestore : public CacheLineAligned {
   /// Same as above, but for SendHeartbeat() RPCs.
   StatsMetric<double>* heartbeat_duration_metric_;
 
+  /// Metric to count the total number of UpdateCatalogd RPCs sent by statestore.
+  IntCounter* update_catalogd_metric_;
+
   /// Utility method to add an update to the given thread pool, and to fail if the thread
   /// pool is already at capacity. Assumes that subscribers_lock_ is held by the caller.
   Status OfferUpdate(const ScheduledSubscriberUpdate& update,
@@ -726,6 +830,12 @@ class Statestore : public CacheLineAligned {
   /// id.
   [[noreturn]] void MonitorSubscriberHeartbeat();
 
+  /// Monitors the notification of updating catalogd.
+  [[noreturn]] void MonitorUpdateCatalogd();
+
+  /// Send notification of updating catalogd to the coordinators.
+  void SendUpdateCatalogdNotification();
+
   /// Raw callback to indicate whether the service is ready.
   void HealthzHandler(const Webserver::WebRequest& req, std::stringstream* data,
       HttpStatusCode* response);
diff --git a/common/thrift/CatalogService.thrift b/common/thrift/CatalogService.thrift
index ceb244227..57c4b0a2b 100644
--- a/common/thrift/CatalogService.thrift
+++ b/common/thrift/CatalogService.thrift
@@ -29,7 +29,12 @@ include "SqlConstraints.thrift"
 // CatalogServer service API and related structs.
 
 enum CatalogServiceVersion {
-  V1
+  V1 = 0
+  // There is back version incompatibility for Thrift structure since some entries were
+  // added in the middle of Thrift structure, like IMPALA-11350. We need to increase
+  // the service version for Catalog so that CatalogServer will refuse the requests
+  // from the incompatible clients.
+  V2 = 1
 }
 
 // Prefix used on statestore topic entry keys to indicate that the entry
@@ -100,7 +105,7 @@ struct TDdlQueryOptions {
 
 // Request for executing a DDL operation (CREATE, ALTER, DROP).
 struct TDdlExecRequest {
-  1: required CatalogServiceVersion protocol_version = CatalogServiceVersion.V1
+  1: required CatalogServiceVersion protocol_version = CatalogServiceVersion.V2
 
   // Common header included in all CatalogService requests.
   2: optional TCatalogServiceRequestHeader header
@@ -235,7 +240,7 @@ struct TUpdatedPartition {
 // after DML operations.
 // TODO: Rename this struct to something more descriptive.
 struct TUpdateCatalogRequest {
-  1: required CatalogServiceVersion protocol_version = CatalogServiceVersion.V1
+  1: required CatalogServiceVersion protocol_version = CatalogServiceVersion.V2
 
   // True if SYNC_DDL is set in query options.
   2: required bool sync_ddl
@@ -276,7 +281,7 @@ struct TUpdateCatalogResponse {
 
 // Parameters of REFRESH/INVALIDATE METADATA commands
 struct TResetMetadataRequest {
-  1: required CatalogServiceVersion protocol_version = CatalogServiceVersion.V1
+  1: required CatalogServiceVersion protocol_version = CatalogServiceVersion.V2
 
   // Common header included in all CatalogService requests.
   2: optional TCatalogServiceRequestHeader header
@@ -316,7 +321,7 @@ struct TResetMetadataResponse {
 
 // Request to GetFunctions()
 struct TGetFunctionsRequest {
-  1: required CatalogServiceVersion protocol_version = CatalogServiceVersion.V1
+  1: required CatalogServiceVersion protocol_version = CatalogServiceVersion.V2
 
   // Common header included in all CatalogService requests.
   3: optional TCatalogServiceRequestHeader header
@@ -553,7 +558,7 @@ struct TPartialDbInfo {
 
 // RPC request for GetPartialCatalogObject.
 struct TGetPartialCatalogObjectRequest {
-  1: required CatalogServiceVersion protocol_version = CatalogServiceVersion.V1
+  1: required CatalogServiceVersion protocol_version = CatalogServiceVersion.V2
 
   // A catalog object descriptor: a TCatalogObject with the object name and type fields
   // set. This may be a TABLE, DB, CATALOG, or FUNCTION. The selectors below can
@@ -600,7 +605,7 @@ struct TGetPartialCatalogObjectResponse {
 // Request the complete metadata for a given catalog object. May trigger a metadata load
 // if the object is not already in the catalog cache.
 struct TGetCatalogObjectRequest {
-  1: required CatalogServiceVersion protocol_version = CatalogServiceVersion.V1
+  1: required CatalogServiceVersion protocol_version = CatalogServiceVersion.V2
 
   // Common header included in all CatalogService requests.
   3: optional TCatalogServiceRequestHeader header
@@ -612,12 +617,14 @@ struct TGetCatalogObjectRequest {
 
 // Response from TGetCatalogObjectRequest
 struct TGetCatalogObjectResponse {
-  1: required CatalogObjects.TCatalogObject catalog_object
+  1: required Status.TStatus status;
+
+  2: required CatalogObjects.TCatalogObject catalog_object
 }
 
 // Request the partition statistics for the specified table.
 struct TGetPartitionStatsRequest {
-  1: required CatalogServiceVersion protocol_version = CatalogServiceVersion.V1
+  1: required CatalogServiceVersion protocol_version = CatalogServiceVersion.V2
   2: required CatalogObjects.TTableName table_name
   // if the table is transactional then this field represents the client's view
   // of the table snapshot view in terms of ValidWriteIdList.
@@ -645,7 +652,7 @@ struct TGetPartitionStatsResponse {
 // catalog objects. Currently only used for controlling the priority of loading
 // tables/views since Db/Function metadata is loaded on startup.
 struct TPrioritizeLoadRequest {
-  1: required CatalogServiceVersion protocol_version = CatalogServiceVersion.V1
+  1: required CatalogServiceVersion protocol_version = CatalogServiceVersion.V2
 
   // Common header included in all CatalogService requests.
   2: optional TCatalogServiceRequestHeader header
@@ -667,7 +674,9 @@ struct TTableUsage {
 }
 
 struct TUpdateTableUsageRequest {
-  1: required list<TTableUsage> usages
+  1: required CatalogServiceVersion protocol_version = CatalogServiceVersion.V2
+
+  2: required list<TTableUsage> usages
 }
 
 struct TUpdateTableUsageResponse {
diff --git a/common/thrift/StatestoreService.thrift b/common/thrift/StatestoreService.thrift
index 71eb57902..62e9f5b04 100644
--- a/common/thrift/StatestoreService.thrift
+++ b/common/thrift/StatestoreService.thrift
@@ -20,9 +20,14 @@ namespace java org.apache.impala.thrift
 
 include "Status.thrift"
 include "Types.thrift"
+include "CatalogService.thrift"
 
 enum StatestoreServiceVersion {
    V1 = 0
+   // There is back version incompatibility. We need to increase the service version
+   // for Statestore so that Statestore will refuse the registration requests from
+   // the incompatible subscribers.
+   V2 = 1
 }
 
 // Description of a single entry in a list of heavy memory usage queries
@@ -179,9 +184,29 @@ struct TTopicRegistration {
   4: optional string filter_prefix
 }
 
+// Define the type for statestore subscriber
+enum TStatestoreSubscriberType {
+  UNKNOWN = 0
+  ADMISSIOND = 1
+  CATALOGD = 2
+  COORDINATOR = 3
+  EXECUTOR = 4
+  COORDINATOR_EXECUTOR = 5
+}
+
+// Additional registration info for catalog daemon.
+struct TCatalogRegistration {
+  // Protocol version of Catalog service.
+  1: required CatalogService.CatalogServiceVersion protocol;
+
+  // Address of catalogd.
+  2: required Types.TNetworkAddress address;
+}
+
 struct TRegisterSubscriberRequest {
+  // Protocol version of the subscriber
   1: required StatestoreServiceVersion protocol_version =
-      StatestoreServiceVersion.V1
+      StatestoreServiceVersion.V2
 
   // Unique, human-readable identifier for this subscriber
   2: required string subscriber_id;
@@ -191,6 +216,18 @@ struct TRegisterSubscriberRequest {
 
   // List of topics to subscribe to
   4: required list<TTopicRegistration> topic_registrations;
+
+  // Subscribe type
+  5: optional TStatestoreSubscriberType subscriber_type;
+
+  // Indicate if the subscriber wishes to be notified of changes to the catalogd.
+  // When it's set as true, statestore will send UpdateCatalogd RPC to the subscriber
+  // once there is catalogd change. Currently it as true for coordinators. In future,
+  // it will be set as true for catalogd when supporting Catalog HA.
+  6: optional bool subscribe_catalogd_change;
+
+  // Set iff this subscriber is catalogd.
+  7: optional TCatalogRegistration catalogd_registration;
 }
 
 struct TRegisterSubscriberResponse {
@@ -200,23 +237,58 @@ struct TRegisterSubscriberResponse {
   // Unique identifier for this registration. Changes with every call to
   // RegisterSubscriber().
   2: optional Types.TUniqueId registration_id;
+
+  // Protocol version of the statestore
+  3: optional StatestoreServiceVersion protocol_version;
+
+  // Unique identifier for the statestore instance. It could be changed for a new
+  // call RegisterSubscriber() if the statestore instance has been restarted since
+  // last registration.
+  4: optional Types.TUniqueId statestore_id;
+
+  // Catalog registration info.
+  5: optional TCatalogRegistration catalogd_registration;
+}
+
+struct TGetProtocolVersionRequest {
+  // Protocol version of the subscriber
+  1: required StatestoreServiceVersion protocol_version =
+      StatestoreServiceVersion.V2
+}
+
+struct TGetProtocolVersionResponse {
+  // whether the call was executed correctly at the application level
+  1: required Status.TStatus status;
+
+  // Protocol version of the statestore
+  2: required StatestoreServiceVersion protocol_version;
+
+  // Unique identifier for the statestore instance.
+  3: optional Types.TUniqueId statestore_id;
 }
 
 service StatestoreService {
   // Register a single subscriber. Note that after a subscriber is registered, no new
   // topics may be added.
   TRegisterSubscriberResponse RegisterSubscriber(1: TRegisterSubscriberRequest params);
+
+  // Get protocol version of the statestore
+  TGetProtocolVersionResponse GetProtocolVersion(1: TGetProtocolVersionRequest params);
 }
 
 struct TUpdateStateRequest {
+  // Protocol version of the statestore
   1: required StatestoreServiceVersion protocol_version =
-      StatestoreServiceVersion.V1
+      StatestoreServiceVersion.V2
 
   // Map from topic name to a list of changes for that topic.
   2: required map<string, TTopicDelta> topic_deltas;
 
   // Registration ID for the last known registration from this subscriber.
   3: optional Types.TUniqueId registration_id;
+
+  // Unique identifier for the statestore instance.
+  4: optional Types.TUniqueId statestore_id;
 }
 
 struct TUpdateStateResponse {
@@ -233,11 +305,43 @@ struct TUpdateStateResponse {
 }
 
 struct THeartbeatRequest {
-  1: optional Types.TUniqueId registration_id;
+  // Protocol version of the statestore
+  1: optional StatestoreServiceVersion protocol_version =
+      StatestoreServiceVersion.V2
+
+  // registration_id of the receiver
+  2: optional Types.TUniqueId registration_id;
+
+  // Unique identifier for the statestore instance.
+  3: optional Types.TUniqueId statestore_id;
 }
 
 struct THeartbeatResponse {
+  // Whether the call was executed correctly at the application level
+  1: required Status.TStatus status;
+}
+
+struct TUpdateCatalogdRequest {
+  // Protocol version of the statestore
+  1: required StatestoreServiceVersion protocol_version =
+      StatestoreServiceVersion.V2
+
+  // registration_id of the receiver
+  2: required Types.TUniqueId registration_id;
+
+  // Unique identifier for the statestore instance.
+  3: required Types.TUniqueId statestore_id;
 
+  // Monotonously increasing number
+  4: required i64 sequence;
+
+  // Catalog registration info.
+  5: required TCatalogRegistration catalogd_registration;
+}
+
+struct TUpdateCatalogdResponse {
+  // Whether the call was executed correctly at the application level
+  1: required Status.TStatus status;
 }
 
 service StatestoreSubscriber {
@@ -255,4 +359,7 @@ service StatestoreSubscriber {
 
   // Called when the statestore sends a heartbeat.
   THeartbeatResponse Heartbeat(1: THeartbeatRequest params);
+
+  // Called when active catalogd has been updated.
+  TUpdateCatalogdResponse UpdateCatalogd(1: TUpdateCatalogdRequest params);
 }
diff --git a/common/thrift/generate_error_codes.py b/common/thrift/generate_error_codes.py
index e1091bd16..5ece600a6 100755
--- a/common/thrift/generate_error_codes.py
+++ b/common/thrift/generate_error_codes.py
@@ -479,7 +479,15 @@ error_codes = (
 
   ("PARQUET_ROWS_SKIPPING", 155, "Couldn't skip rows in column '$0' in file '$1'."),
 
-  ("QUERY_OPTION_PARSE_FAILED", 156, "Failed to parse query option '$0': $1")
+  ("QUERY_OPTION_PARSE_FAILED", 156, "Failed to parse query option '$0': $1"),
+
+  ("CATALOG_INCOMPATIBLE_PROTOCOL", 157,
+   "Client has incompatible protocol version V$0 conflicting with catalogd's version "
+   "V$1"),
+
+  ("STATESTORE_INCOMPATIBLE_PROTOCOL", 158,
+   "Subscriber '$0' has incompatible protocol version V$1 conflicting with statestored's "
+   "version V$2")
 )
 
 import sys
diff --git a/common/thrift/metrics.json b/common/thrift/metrics.json
index c24d49e7d..7e650343c 100644
--- a/common/thrift/metrics.json
+++ b/common/thrift/metrics.json
@@ -1729,6 +1729,41 @@
     "kind": "PROPERTY",
     "key": "statestore-subscriber.registration-id"
   },
+  {
+    "description": "The most recent statestore ID for this subscriber with the statestore. Set to 'N/A' if no registration has been completed",
+    "contexts": [
+      "ADMISSIOND",
+      "CATALOGSERVER",
+      "IMPALAD"
+    ],
+    "label": "Statestore Id",
+    "units": "NONE",
+    "kind": "PROPERTY",
+    "key": "statestore-subscriber.statestore-id"
+  },
+  {
+    "description": "The number of RPCs received for updating catalogd.",
+    "contexts": [
+      "CATALOGSERVER",
+      "IMPALAD"
+    ],
+    "label": "Number of UpdateCatalogd RPCs",
+    "units": "UNIT",
+    "kind": "COUNTER",
+    "key": "statestore-subscriber.num-update-catalogd"
+  },
+  {
+    "description": "The number of Re-Registration Attempt.",
+    "contexts": [
+      "ADMISSIOND",
+      "CATALOGSERVER",
+      "IMPALAD"
+    ],
+    "label": "Number of Re-Registration Attempt",
+    "units": "UNIT",
+    "kind": "COUNTER",
+    "key": "statestore-subscriber.num-re-register-attempt"
+  },
   {
     "description": "The number of active StateStore subscriber clients in this Impala Daemon's client cache. These clients are for communication from this role to the StateStore.",
     "contexts": [
@@ -1805,6 +1840,16 @@
     "kind": "STATS",
     "key": "statestore.heartbeat-durations"
   },
+  {
+    "description": "The number of RPCs sent for updating catalogd.",
+    "contexts": [
+      "STATESTORE"
+    ],
+    "label": "Number of UpdateCatalogd RPCs",
+    "units": "UNIT",
+    "kind": "COUNTER",
+    "key": "statestore.num-update-catalogd"
+  },
   {
     "description": "The number of registered Statestore subscribers.",
     "contexts": [
@@ -1925,6 +1970,26 @@
     "kind": "GAUGE",
     "key": "subscriber-update-state.client-cache.total-clients"
   },
+  {
+    "description": "The number of clients in use by the Statestore update catalogd client cache.",
+    "contexts": [
+      "STATESTORE"
+    ],
+    "label": "Subscriber Update Catalogd Client Cache Clients In Use",
+    "units": "NONE",
+    "kind": "GAUGE",
+    "key": "subscriber-update-catalogd.client-cache.clients-in-use"
+  },
+  {
+    "description": "The total number of clients in the Statestore update catalogd client cache.",
+    "contexts": [
+      "STATESTORE"
+    ],
+    "label": "Subscriber Update Catalogd Client Cache Total Clients",
+    "units": "NONE",
+    "kind": "GAUGE",
+    "key": "subscriber-update-catalogd.client-cache.total-clients"
+  },
   {
     "description": "Number of bytes used by the application. This will not typically match the memory use reported by the OS, because it does not include TCMalloc overhead or memory fragmentation.",
     "contexts": [
@@ -3060,7 +3125,8 @@
     "units": "NONE",
     "kind": "COUNTER",
     "key": "cluster-membership.group-set.executor-groups.total-healthy.$0"
-  },{
+  },
+  {
     "description": "Total number of backends in the executor group set $0 registered with the statestore",
     "contexts": [
       "IMPALAD"
diff --git a/fe/src/main/java/org/apache/impala/catalog/ImpaladTableUsageTracker.java b/fe/src/main/java/org/apache/impala/catalog/ImpaladTableUsageTracker.java
index 5db822b16..cac1600b9 100644
--- a/fe/src/main/java/org/apache/impala/catalog/ImpaladTableUsageTracker.java
+++ b/fe/src/main/java/org/apache/impala/catalog/ImpaladTableUsageTracker.java
@@ -101,8 +101,8 @@ public class ImpaladTableUsageTracker {
         TUpdateTableUsageRequest reqToSend;
         synchronized (this) {
           if (unreportedUsages.isEmpty()) continue;
-          reqToSend =
-              new TUpdateTableUsageRequest(new ArrayList<>(unreportedUsages.values()));
+          reqToSend = new TUpdateTableUsageRequest();
+          reqToSend.setUsages(new ArrayList<>(unreportedUsages.values()));
           unreportedUsages.clear();
         }
         byte[] byteResp =
diff --git a/tests/catalog_service/test_catalog_service_client.py b/tests/catalog_service/test_catalog_service_client.py
index 8d89d9a19..5e4c97d0d 100644
--- a/tests/catalog_service/test_catalog_service_client.py
+++ b/tests/catalog_service/test_catalog_service_client.py
@@ -129,3 +129,11 @@ class TestCatalogServiceClient(ImpalaTestSuite):
     LOG.debug(response)
     assert response.status.status_code == TErrorCode.GENERAL
     assert 'Database name must be set' in str(response.status)
+
+    # Negative test with incompatible protocol version
+    request = TGetFunctionsRequest()
+    request.db_name = unique_database
+    request.protocol_version = CatalogService.CatalogServiceVersion.V1
+    response = catalog_client.GetFunctions(request)
+    LOG.debug(response)
+    assert response.status.status_code == TErrorCode.CATALOG_INCOMPATIBLE_PROTOCOL
diff --git a/tests/custom_cluster/test_custom_statestore.py b/tests/custom_cluster/test_custom_statestore.py
index 4a5db8149..15d63ec84 100644
--- a/tests/custom_cluster/test_custom_statestore.py
+++ b/tests/custom_cluster/test_custom_statestore.py
@@ -29,7 +29,10 @@ import uuid
 import socket
 
 from tests.common.custom_cluster_test_suite import CustomClusterTestSuite
+from tests.common.environ import build_flavor_timeout
+from tests.common.skip import SkipIfBuildType
 from tests.common.impala_test_suite import ImpalaTestSuite
+from time import sleep
 
 from Types.ttypes import TNetworkAddress
 from thrift.protocol import TBinaryProtocol
@@ -37,10 +40,12 @@ from thrift.transport import TSocket, TTransport
 
 import StatestoreService.StatestoreSubscriber as Subscriber
 import StatestoreService.StatestoreService as Statestore
+import CatalogService.CatalogService as Catalog
 from ErrorCodes.ttypes import TErrorCode
 
 LOG = logging.getLogger('custom_statestore_test')
 STATESTORE_SERVICE_PORT = 24000
+CATALOG_SERVICE_PORT = 26000
 
 # A simple wrapper class to launch a cluster where we can tune various
 # startup parameters of the statestored to test correct boundary-value
@@ -58,18 +63,48 @@ class TestCustomStatestore(CustomClusterTestSuite):
   def get_workload(self):
     return 'functional-query'
 
-  def __register_subscriber(self):
+  def __get_protocol_version(self):
+    request = Subscriber.TGetProtocolVersionRequest(
+        protocol_version=Subscriber.StatestoreServiceVersion.V2)
+    client_transport = TTransport.TBufferedTransport(
+        TSocket.TSocket('localhost', STATESTORE_SERVICE_PORT))
+    trans_protocol = TBinaryProtocol.TBinaryProtocol(client_transport)
+    client = Statestore.Client(trans_protocol)
+    client_transport.open()
+    try:
+      return client.GetProtocolVersion(request)
+    except Exception as e:
+      # For statestore with StatestoreServiceVersion.V1, 'GetProtocolVersion' is not
+      # supported. Exception "Invalid method name: 'GetProtocolVersion'" is thrown
+      # by Thrift client.
+      assert False, str(e)
+
+  def __register_subscriber(self, ss_protocol=Subscriber.StatestoreServiceVersion.V2,
+                            in_v2_format=True, expect_exception=False):
     subscriber_id = "python-test-client-%s" % uuid.uuid4()
     topics = []
-    request = Subscriber.TRegisterSubscriberRequest(topic_registrations=topics,
-      subscriber_location=TNetworkAddress("localhost", self.port),
-      subscriber_id=subscriber_id)
-    client_transport = \
-      TTransport.TBufferedTransport(TSocket.TSocket('localhost', STATESTORE_SERVICE_PORT))
-    protocol = TBinaryProtocol.TBinaryProtocol(client_transport)
-    client = Statestore.Client(protocol)
+    if (ss_protocol == Subscriber.StatestoreServiceVersion.V1 and not in_v2_format):
+      request = Subscriber.TRegisterSubscriberRequest(topic_registrations=topics,
+          protocol_version=ss_protocol,
+          subscriber_location=TNetworkAddress("localhost", self.port),
+          subscriber_id=subscriber_id)
+    else:
+      request = Subscriber.TRegisterSubscriberRequest(topic_registrations=topics,
+          protocol_version=ss_protocol,
+          subscriber_location=TNetworkAddress("localhost", self.port),
+          subscriber_type=Subscriber.TStatestoreSubscriberType.COORDINATOR_EXECUTOR,
+          subscriber_id=subscriber_id)
+    client_transport = TTransport.TBufferedTransport(
+        TSocket.TSocket('localhost', STATESTORE_SERVICE_PORT))
+    trans_protocol = TBinaryProtocol.TBinaryProtocol(client_transport)
+    client = Statestore.Client(trans_protocol)
     client_transport.open()
-    return client.RegisterSubscriber(request)
+    try:
+      response = client.RegisterSubscriber(request)
+      assert not expect_exception
+      return response
+    except Exception as e:
+      assert expect_exception, str(e)
 
   @CustomClusterTestSuite.with_args(statestored_args="-statestore_max_subscribers=3")
   def test_statestore_max_subscribers(self):
@@ -102,3 +137,155 @@ class TestCustomStatestore(CustomClusterTestSuite):
         "Registering with statestore with resolved address")
     self.assert_catalogd_log_contains("INFO",
         "Registering with statestore with resolved address")
+
+  @pytest.mark.execute_serially
+  def test_statestore_compatible_subscriber(self):
+    # Get protocol version of statestore.
+    response = self.__get_protocol_version()
+    assert response.status.status_code == TErrorCode.OK
+    assert response.protocol_version == Subscriber.StatestoreServiceVersion.V2
+
+    # Register compatible subscriber.
+    response = self.__register_subscriber()
+    # Verify response of normal registration for compatible subscriber.
+    assert response.status.status_code == TErrorCode.OK
+    assert response.protocol_version == Subscriber.StatestoreServiceVersion.V2
+    assert response.catalogd_registration.protocol == Catalog.CatalogServiceVersion.V2
+    assert response.catalogd_registration.address.port == CATALOG_SERVICE_PORT
+
+  @pytest.mark.execute_serially
+  @CustomClusterTestSuite.with_args(
+      statestored_args="--debug_actions=START_STATESTORE_IN_PROTOCOL_V1")
+  def test_statestore_incompatible_statestore(self):
+    """Test that the old statestored refuses the registration request from new
+    incompatible subscriber."""
+    self.__register_subscriber(ss_protocol=Subscriber.StatestoreServiceVersion.V2,
+        in_v2_format=True, expect_exception=True)
+
+  @pytest.mark.execute_serially
+  def test_statestore_incompatible_subscriber(self):
+    """Test that the new statestored refuses the registration request from old
+    incompatible subscriber."""
+    response = self.__register_subscriber(
+        ss_protocol=Subscriber.StatestoreServiceVersion.V1,
+        in_v2_format=True, expect_exception=False)
+    assert response.status.status_code == TErrorCode.STATESTORE_INCOMPATIBLE_PROTOCOL
+
+    self.__register_subscriber(ss_protocol=Subscriber.StatestoreServiceVersion.V1,
+        in_v2_format=False, expect_exception=True)
+
+  def test_subscriber_fail_on_startup_register_failure(self):
+    """The impalads are not expected to be able to tolerate the failure of registration
+    on startup without starting flags FLAGS_tolerate_statestore_startup_delay set as
+    true."""
+    try:
+      self._start_impala_cluster(
+          ["--impalad_args=--debug_actions=REGISTER_STATESTORE_ON_STARTUP:FAIL@1.0"])
+      assert False, "cluster startup should have failed"
+    except Exception:
+      self._stop_impala_cluster()
+
+  @CustomClusterTestSuite.with_args(
+    impalad_args="--debug_actions=REGISTER_STATESTORE_ON_STARTUP:FAIL@1.0 "
+                 "--tolerate_statestore_startup_delay=true")
+  def test_subscriber_tolerate_startup_register_failure(self):
+    """The impalads are expected to be able to tolerate the failure of registration
+    on startup with starting flags FLAGS_tolerate_statestore_startup_delay set as
+    true.
+    During rolling upgrade, registration failures could be caused by incompatible
+    protocols between subscribers and statestore. For example, executors or coordinators
+    are upgraded before statestore."""
+    self.execute_query("select count(*) from functional.alltypes")
+
+    # Verify that impalad entered recovery mode and tried to re-register with statestore.
+    re_register_attempt = self.cluster.impalads[0].service.get_metric_value(
+        "statestore-subscriber.num-re-register-attempt")
+    assert re_register_attempt > 0
+
+
+class TestStatestoreStartupDelay(CustomClusterTestSuite):
+  """This test injects a real delay in statestored startup. The impalads and catalogd are
+  expected to be able to tolerate this delay with FLAGS_tolerate_statestore_startup_delay
+  set as true. This is not testing anything beyond successful startup."""
+
+  @classmethod
+  def get_workload(self):
+    return 'functional-query'
+
+  @classmethod
+  def setup_class(cls):
+    if cls.exploration_strategy() != 'exhaustive':
+      pytest.skip('Statestore startup delay tests only run in exhaustive')
+    super(TestStatestoreStartupDelay, cls).setup_class()
+
+  @SkipIfBuildType.not_dev_build
+  @CustomClusterTestSuite.with_args(
+    impalad_args="--tolerate_statestore_startup_delay=true",
+    catalogd_args="--tolerate_statestore_startup_delay=true",
+    statestored_args="--stress_statestore_startup_delay_ms=60000")
+  def test_subscriber_tolerate_startup_delay(self):
+    """The impalads and catalogd are expected to be able to tolerate the delay of
+    statestored startup with starting flags FLAGS_tolerate_statestore_startup_delay
+    set as true."""
+    # The actual test here is successful startup, and we assume nothing about the
+    # functionality of the impalads before the coordinator and catalogd finish
+    # starting up.
+    self.execute_query("select count(*) from functional.alltypes")
+
+    # Verify that impalad and catalogd entered recovery mode and tried to re-register
+    # with statestore.
+    re_register_attempt = self.cluster.impalads[0].service.get_metric_value(
+        "statestore-subscriber.num-re-register-attempt")
+    assert re_register_attempt > 0
+    re_register_attempt = self.cluster.catalogd.service.get_metric_value(
+        "statestore-subscriber.num-re-register-attempt")
+    assert re_register_attempt > 0
+
+  @SkipIfBuildType.not_dev_build
+  def test_subscriber_fail_on_startup_delay(self):
+    """The impalads and catalogd are not expected to be able to tolerate the delay of
+    statestored startup without starting flags FLAGS_tolerate_statestore_startup_delay
+    set as true."""
+    try:
+      self._start_impala_cluster(
+          ["--state_store_args=--stress_statestore_startup_delay_ms=60000"])
+      assert False, "cluster startup should have failed"
+    except Exception:
+      self._stop_impala_cluster()
+
+  def test_subscriber_tolerate_restart_catalog(self):
+    """Restart catalogd and verify update-catalogd RPCs are sent by statestore
+    """
+    statestore_service = self.cluster.statestored.service
+    start_sent_rpc_count = statestore_service.get_metric_value(
+        "statestore.num-update-catalogd")
+    impalad_service = self.cluster.impalads[0].service
+    start_recv_rpc_count = impalad_service.get_metric_value(
+        "statestore-subscriber.num-update-catalogd")
+
+    # Restart catalog daemon.
+    self.cluster.catalogd.restart()
+    wait_time_s = build_flavor_timeout(15, slow_build_timeout=30)
+    sleep(wait_time_s)
+    # Verify update-catalogd RPCs are sent to coordinators from statestore.
+    end_sent_rpc_count = statestore_service.get_metric_value(
+        "statestore.num-update-catalogd")
+    assert end_sent_rpc_count > start_sent_rpc_count
+    end_recv_rpc_count = impalad_service.get_metric_value(
+        "statestore-subscriber.num-update-catalogd")
+    assert end_recv_rpc_count > start_recv_rpc_count
+
+  @SkipIfBuildType.not_dev_build
+  @CustomClusterTestSuite.with_args(
+    catalogd_args="--stress_catalog_startup_delay_ms=60000")
+  def test_subscriber_tolerate_catalogd_startup_delay(self):
+    """The impalads are expected to be able to tolerate the delay of catalog startup.
+    """
+    # The actual test here is successful startup, and we assume nothing about the
+    # functionality of the impalads before catalogd finish starting up.
+    self.execute_query("select count(*) from functional.alltypes")
+
+    # Verify that impalad received notification of updating catalogd.
+    recv_rpc_count = self.cluster.impalads[0].service.get_metric_value(
+        "statestore-subscriber.num-update-catalogd")
+    assert recv_rpc_count > 0
diff --git a/tests/custom_cluster/test_services_rpc_errors.py b/tests/custom_cluster/test_services_rpc_errors.py
index 3efcb393b..be9a8f029 100644
--- a/tests/custom_cluster/test_services_rpc_errors.py
+++ b/tests/custom_cluster/test_services_rpc_errors.py
@@ -44,6 +44,17 @@ class TestStatestoreRpcErrors(CustomClusterTestSuite):
     result = self.execute_query("select count(*) from functional_parquet.alltypes")
     assert result.success, str(result)
 
+  @pytest.mark.execute_serially
+  @CustomClusterTestSuite.with_args(
+      " --debug_actions=GET_PROTOCOL_VERSION_FIRST_ATTEMPT:FAIL@1.0")
+  def test_get_protocol_version_rpc_error(self, vector):
+    self.assert_impalad_log_contains("INFO",
+        "Injected RPC error.*Debug Action: GET_PROTOCOL_VERSION_FIRST_ATTEMPT")
+
+    # Ensure cluster has started up by running a query.
+    result = self.execute_query("select count(*) from functional_parquet.alltypes")
+    assert result.success, str(result)
+
 
 class TestCatalogRpcErrors(CustomClusterTestSuite):
   """Tests for catalog RPC handling."""
diff --git a/tests/statestore/test_statestore.py b/tests/statestore/test_statestore.py
index ba7605ae4..94d7f60f1 100644
--- a/tests/statestore/test_statestore.py
+++ b/tests/statestore/test_statestore.py
@@ -205,7 +205,7 @@ class StatestoreSubscriber(object):
     self.heartbeat_event.acquire()
     try:
       self.heartbeat_count += 1
-      response = Subscriber.THeartbeatResponse()
+      response = Subscriber.THeartbeatResponse(status=STATUS_OK)
       if self.heartbeat_cb is not None and self.exception is None:
         try:
           response = self.heartbeat_cb(self, args)
@@ -280,6 +280,7 @@ class StatestoreSubscriber(object):
     request = Subscriber.TRegisterSubscriberRequest(
       topic_registrations=topics,
       subscriber_location=TNetworkAddress("localhost", self.port),
+      subscriber_type=Subscriber.TStatestoreSubscriberType.COORDINATOR_EXECUTOR,
       subscriber_id=self.subscriber_id)
     response = self.client.RegisterSubscriber(request)
     if response.status.status_code == TErrorCode.OK:
@@ -549,7 +550,7 @@ class TestStatestore():
       # Delay every second heartbeat.
       if (heartbeat_count[0] % 2 == 1):
         time.sleep(4)
-      return Subscriber.THeartbeatResponse()
+      return Subscriber.THeartbeatResponse(status=STATUS_OK)
 
     with StatestoreSubscriber(heartbeat_cb=heartbeat_cb) as sub:
       topic_name = "test_intermittent_hung_heartbeats"