You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@arrow.apache.org by th...@apache.org on 2023/02/07 21:42:36 UTC

[arrow-ballista] 03/03: Tests and fixes

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

thinkharderdev pushed a commit to branch cluster-state-refactor-2
in repository https://gitbox.apache.org/repos/asf/arrow-ballista.git

commit 3767b1799992b7edb8e5c140e3cd6038d146fa28
Author: Dan Harris <da...@thinkharder.dev>
AuthorDate: Tue Feb 7 14:17:07 2023 -0500

    Tests and fixes
---
 ballista/scheduler/src/cluster/kv.rs               | 286 +++++++--
 ballista/scheduler/src/cluster/memory.rs           | 277 ++++++--
 ballista/scheduler/src/cluster/mod.rs              |  55 +-
 ballista/scheduler/src/cluster/test/mod.rs         | 595 +++++++++++++++++
 ballista/scheduler/src/scheduler_server/mod.rs     |   9 +-
 .../src/scheduler_server/query_stage_scheduler.rs  |  17 +-
 ballista/scheduler/src/state/backend/cluster.rs    | 710 ---------------------
 ballista/scheduler/src/state/backend/etcd.rs       | 348 ----------
 ballista/scheduler/src/state/backend/memory.rs     | 411 ------------
 ballista/scheduler/src/state/backend/mod.rs        | 169 -----
 ballista/scheduler/src/state/backend/sled.rs       | 397 ------------
 ballista/scheduler/src/state/backend/utils/mod.rs  |  21 -
 .../scheduler/src/state/backend/utils/oneshot.rs   | 179 ------
 .../src/state/backend/utils/subscriber.rs          | 248 -------
 ballista/scheduler/src/state/execution_graph.rs    | 319 +--------
 ballista/scheduler/src/state/executor_manager.rs   |  22 +-
 ballista/scheduler/src/state/mod.rs                |  45 +-
 ballista/scheduler/src/state/task_manager.rs       |  73 +--
 ballista/scheduler/src/test_utils.rs               | 312 ++++++++-
 19 files changed, 1505 insertions(+), 2988 deletions(-)

diff --git a/ballista/scheduler/src/cluster/kv.rs b/ballista/scheduler/src/cluster/kv.rs
index 25f09ee3..dccbe95b 100644
--- a/ballista/scheduler/src/cluster/kv.rs
+++ b/ballista/scheduler/src/cluster/kv.rs
@@ -30,7 +30,8 @@ use ballista_core::config::BallistaConfig;
 use ballista_core::error::{BallistaError, Result};
 use ballista_core::serde::protobuf::job_status::Status;
 use ballista_core::serde::protobuf::{
-    self, ExecutorHeartbeat, ExecutorTaskSlots, FailedJob, KeyValuePair,
+    self, AvailableTaskSlots, ExecutorHeartbeat, ExecutorTaskSlots, FailedJob,
+    KeyValuePair, PhysicalPlanNode, QueuedJob,
 };
 use ballista_core::serde::scheduler::{ExecutorData, ExecutorMetadata};
 use ballista_core::serde::AsExecutionPlan;
@@ -38,7 +39,9 @@ use ballista_core::serde::BallistaCodec;
 use dashmap::DashMap;
 use datafusion::prelude::SessionContext;
 use datafusion_proto::logical_plan::AsLogicalPlan;
+use datafusion_proto::protobuf::LogicalPlanNode;
 use futures::StreamExt;
+use itertools::Itertools;
 use log::warn;
 use prost::Message;
 use std::collections::{HashMap, HashSet};
@@ -49,8 +52,8 @@ use std::time::{SystemTime, UNIX_EPOCH};
 /// State implementation based on underlying `KeyValueStore`
 pub struct KeyValueState<
     S: KeyValueStore,
-    T: 'static + AsLogicalPlan,
-    U: 'static + AsExecutionPlan,
+    T: 'static + AsLogicalPlan = LogicalPlanNode,
+    U: 'static + AsExecutionPlan = PhysicalPlanNode,
 > {
     /// Underlying `KeyValueStore`
     store: S,
@@ -107,17 +110,25 @@ impl<S: KeyValueStore, T: 'static + AsLogicalPlan, U: 'static + AsExecutionPlan>
                     ))
                 })?;
 
-            let slots_iter = slots.task_slots.iter_mut().filter(|slots| {
-                executors
-                    .as_ref()
-                    .map(|executors| executors.contains(&slots.executor_id))
-                    .unwrap_or(true)
-            });
+            let mut available_slots: Vec<&mut AvailableTaskSlots> = slots
+                .task_slots
+                .iter_mut()
+                .filter_map(|data| {
+                    (data.slots > 0
+                        && executors
+                            .as_ref()
+                            .map(|executors| executors.contains(&data.executor_id))
+                            .unwrap_or(true))
+                    .then_some(data)
+                })
+                .collect();
+
+            available_slots.sort_by(|a, b| Ord::cmp(&b.slots, &a.slots));
 
             let reservations = match distribution {
-                TaskDistribution::Bias => reserve_slots_bias(slots_iter, num_slots),
+                TaskDistribution::Bias => reserve_slots_bias(available_slots, num_slots),
                 TaskDistribution::RoundRobin => {
-                    reserve_slots_round_robin(slots_iter, num_slots)
+                    reserve_slots_round_robin(available_slots, num_slots)
                 }
             };
 
@@ -151,17 +162,25 @@ impl<S: KeyValueStore, T: 'static + AsLogicalPlan, U: 'static + AsExecutionPlan>
                     ))
                 })?;
 
-            let slots_iter = slots.task_slots.iter_mut().filter(|slots| {
-                executors
-                    .as_ref()
-                    .map(|executors| executors.contains(&slots.executor_id))
-                    .unwrap_or(true)
-            });
+            let mut available_slots: Vec<&mut AvailableTaskSlots> = slots
+                .task_slots
+                .iter_mut()
+                .filter_map(|data| {
+                    (data.slots > 0
+                        && executors
+                            .as_ref()
+                            .map(|executors| executors.contains(&data.executor_id))
+                            .unwrap_or(true))
+                    .then_some(data)
+                })
+                .collect();
+
+            available_slots.sort_by(|a, b| Ord::cmp(&b.slots, &a.slots));
 
             let reservations = match distribution {
-                TaskDistribution::Bias => reserve_slots_bias(slots_iter, num_slots),
+                TaskDistribution::Bias => reserve_slots_bias(available_slots, num_slots),
                 TaskDistribution::RoundRobin => {
-                    reserve_slots_round_robin(slots_iter, num_slots)
+                    reserve_slots_round_robin(available_slots, num_slots)
                 }
             };
 
@@ -181,7 +200,7 @@ impl<S: KeyValueStore, T: 'static + AsLogicalPlan, U: 'static + AsExecutionPlan>
         &self,
         reservations: Vec<ExecutorReservation>,
     ) -> Result<()> {
-        let lock = self.store.lock(Keyspace::Slots, "global").await?;
+        let lock = self.store.lock(Keyspace::Slots, "all").await?;
 
         with_lock(lock, async {
             let resources = self.store.get(Keyspace::Slots, "all").await?;
@@ -209,7 +228,9 @@ impl<S: KeyValueStore, T: 'static + AsLogicalPlan, U: 'static + AsExecutionPlan>
                 }
             }
 
-            Ok(())
+            self.store
+                .put(Keyspace::Slots, "all".to_string(), slots.encode_to_vec())
+                .await
         })
         .await
     }
@@ -246,25 +267,80 @@ impl<S: KeyValueStore, T: 'static + AsLogicalPlan, U: 'static + AsExecutionPlan>
         .await?;
 
         if !reserve {
-            let proto: protobuf::ExecutorData = spec.into();
-            self.store
-                .put(Keyspace::Slots, executor_id, proto.encode_to_vec())
-                .await?;
+            let available_slots = AvailableTaskSlots {
+                executor_id,
+                slots: spec.available_task_slots,
+            };
+
+            let lock = self.store.lock(Keyspace::Slots, "all").await?;
+
+            with_lock(lock, async {
+                let current_slots = self.store.get(Keyspace::Slots, "all").await?;
+
+                let mut current_slots: ExecutorTaskSlots =
+                    decode_protobuf(current_slots.as_slice())?;
+
+                if let Some((idx, _)) =
+                    current_slots.task_slots.iter().find_position(|slots| {
+                        slots.executor_id == available_slots.executor_id
+                    })
+                {
+                    current_slots.task_slots[idx] = available_slots;
+                } else {
+                    current_slots.task_slots.push(available_slots);
+                }
+
+                self.store
+                    .put(
+                        Keyspace::Slots,
+                        "all".to_string(),
+                        current_slots.encode_to_vec(),
+                    )
+                    .await
+            })
+            .await?;
+
             Ok(vec![])
         } else {
-            let mut specification = spec;
-            let num_slots = specification.available_task_slots as usize;
+            let num_slots = spec.available_task_slots as usize;
             let mut reservations: Vec<ExecutorReservation> = vec![];
             for _ in 0..num_slots {
                 reservations.push(ExecutorReservation::new_free(executor_id.clone()));
             }
 
-            specification.available_task_slots = 0;
+            let available_slots = AvailableTaskSlots {
+                executor_id,
+                slots: 0,
+            };
+
+            let lock = self.store.lock(Keyspace::Slots, "all").await?;
+
+            with_lock(lock, async {
+                let current_slots = self.store.get(Keyspace::Slots, "all").await?;
+
+                let mut current_slots: ExecutorTaskSlots =
+                    decode_protobuf(current_slots.as_slice())?;
+
+                if let Some((idx, _)) =
+                    current_slots.task_slots.iter().find_position(|slots| {
+                        slots.executor_id == available_slots.executor_id
+                    })
+                {
+                    current_slots.task_slots[idx] = available_slots;
+                } else {
+                    current_slots.task_slots.push(available_slots);
+                }
+
+                self.store
+                    .put(
+                        Keyspace::Slots,
+                        "all".to_string(),
+                        current_slots.encode_to_vec(),
+                    )
+                    .await
+            })
+            .await?;
 
-            let proto: protobuf::ExecutorData = specification.into();
-            self.store
-                .put(Keyspace::Slots, executor_id, proto.encode_to_vec())
-                .await?;
             Ok(reservations)
         }
     }
@@ -383,26 +459,34 @@ impl<S: KeyValueStore, T: 'static + AsLogicalPlan, U: 'static + AsExecutionPlan>
     }
 
     async fn submit_job(&self, job_id: String, graph: &ExecutionGraph) -> Result<()> {
-        let status = graph.status();
-        let encoded_graph =
-            ExecutionGraph::encode_execution_graph(graph.clone(), &self.codec)?;
+        if self.queued_jobs.get(&job_id).is_some() {
+            let status = graph.status();
+            let encoded_graph =
+                ExecutionGraph::encode_execution_graph(graph.clone(), &self.codec)?;
 
-        self.store
-            .apply_txn(vec![
-                (
-                    Operation::Put(status.encode_to_vec()),
-                    Keyspace::JobStatus,
-                    job_id.clone(),
-                ),
-                (
-                    Operation::Put(encoded_graph.encode_to_vec()),
-                    Keyspace::ExecutionGraph,
-                    job_id.clone(),
-                ),
-            ])
-            .await?;
+            self.store
+                .apply_txn(vec![
+                    (
+                        Operation::Put(status.encode_to_vec()),
+                        Keyspace::JobStatus,
+                        job_id.clone(),
+                    ),
+                    (
+                        Operation::Put(encoded_graph.encode_to_vec()),
+                        Keyspace::ExecutionGraph,
+                        job_id.clone(),
+                    ),
+                ])
+                .await?;
 
-        Ok(())
+            self.queued_jobs.remove(&job_id);
+
+            Ok(())
+        } else {
+            Err(BallistaError::Internal(format!(
+                "Failed to submit job {job_id}, job was not in queueud jobs"
+            )))
+        }
     }
 
     async fn get_jobs(&self) -> Result<HashSet<String>> {
@@ -410,11 +494,21 @@ impl<S: KeyValueStore, T: 'static + AsLogicalPlan, U: 'static + AsExecutionPlan>
     }
 
     async fn get_job_status(&self, job_id: &str) -> Result<Option<JobStatus>> {
-        let value = self.store.get(Keyspace::JobStatus, job_id).await?;
+        if let Some((job_name, queued_at)) = self.queued_jobs.get(job_id).as_deref() {
+            Ok(Some(JobStatus {
+                job_id: job_id.to_string(),
+                job_name: job_name.clone(),
+                status: Some(Status::Queued(QueuedJob {
+                    queued_at: *queued_at,
+                })),
+            }))
+        } else {
+            let value = self.store.get(Keyspace::JobStatus, job_id).await?;
 
-        (!value.is_empty())
-            .then(|| decode_protobuf(value.as_slice()))
-            .transpose()
+            (!value.is_empty())
+                .then(|| decode_protobuf(value.as_slice()))
+                .transpose()
+        }
     }
 
     async fn get_execution_graph(&self, job_id: &str) -> Result<Option<ExecutionGraph>> {
@@ -610,3 +704,87 @@ async fn with_lock<Out, F: Future<Output = Out>>(mut lock: Box<dyn Lock>, op: F)
     lock.unlock().await;
     result
 }
+
+#[cfg(test)]
+mod test {
+    use crate::cluster::kv::KeyValueState;
+    use crate::cluster::storage::sled::SledClient;
+    use crate::cluster::test::{
+        test_executor_registration, test_fuzz_reservations, test_job_lifecycle,
+        test_job_planning_failure, test_reservation,
+    };
+    use crate::cluster::TaskDistribution;
+    use crate::test_utils::{
+        test_aggregation_plan, test_join_plan, test_two_aggregations_plan,
+    };
+    use ballista_core::error::Result;
+    use ballista_core::serde::BallistaCodec;
+    use ballista_core::utils::default_session_builder;
+
+    #[cfg(feature = "sled")]
+    fn make_sled_state() -> Result<KeyValueState<SledClient>> {
+        Ok(KeyValueState::new(
+            "",
+            SledClient::try_new_temporary()?,
+            BallistaCodec::default(),
+            default_session_builder,
+        ))
+    }
+
+    #[cfg(feature = "sled")]
+    #[tokio::test]
+    async fn test_sled_executor_reservation() -> Result<()> {
+        test_executor_registration(make_sled_state()?).await
+    }
+
+    #[cfg(feature = "sled")]
+    #[tokio::test]
+    async fn test_sled_reserve() -> Result<()> {
+        test_reservation(make_sled_state()?, TaskDistribution::Bias).await?;
+        test_reservation(make_sled_state()?, TaskDistribution::RoundRobin).await?;
+
+        Ok(())
+    }
+
+    #[cfg(feature = "sled")]
+    #[tokio::test]
+    async fn test_sled_fuzz_reserve() -> Result<()> {
+        test_fuzz_reservations(make_sled_state()?, 10, TaskDistribution::Bias, 10, 10)
+            .await?;
+        test_fuzz_reservations(
+            make_sled_state()?,
+            10,
+            TaskDistribution::RoundRobin,
+            10,
+            10,
+        )
+        .await?;
+
+        Ok(())
+    }
+
+    #[cfg(feature = "sled")]
+    #[tokio::test]
+    async fn test_sled_job_lifecycle() -> Result<()> {
+        test_job_lifecycle(make_sled_state()?, test_aggregation_plan(4).await).await?;
+        test_job_lifecycle(make_sled_state()?, test_two_aggregations_plan(4).await)
+            .await?;
+        test_job_lifecycle(make_sled_state()?, test_join_plan(4).await).await?;
+        Ok(())
+    }
+
+    #[cfg(feature = "sled")]
+    #[tokio::test]
+    async fn test_in_memory_job_planning_failure() -> Result<()> {
+        test_job_planning_failure(make_sled_state()?, test_aggregation_plan(4).await)
+            .await?;
+        test_job_planning_failure(
+            make_sled_state()?,
+            test_two_aggregations_plan(4).await,
+        )
+        .await?;
+        test_job_planning_failure(make_sled_state()?, test_join_plan(4).await).await?;
+
+        Ok(())
+    }
+}
diff --git a/ballista/scheduler/src/cluster/memory.rs b/ballista/scheduler/src/cluster/memory.rs
index 2d59fd9b..b68d7b8e 100644
--- a/ballista/scheduler/src/cluster/memory.rs
+++ b/ballista/scheduler/src/cluster/memory.rs
@@ -25,14 +25,15 @@ use async_trait::async_trait;
 use ballista_core::config::BallistaConfig;
 use ballista_core::error::{BallistaError, Result};
 use ballista_core::serde::protobuf::{
-    executor_status, ExecutorHeartbeat, ExecutorStatus, ExecutorTaskSlots, FailedJob,
+    executor_status, AvailableTaskSlots, ExecutorHeartbeat, ExecutorStatus,
+    ExecutorTaskSlots, FailedJob, QueuedJob,
 };
 use ballista_core::serde::scheduler::{ExecutorData, ExecutorMetadata};
 use dashmap::DashMap;
 use datafusion::prelude::SessionContext;
 
 use crate::cluster::event::ClusterEventSender;
-use crate::scheduler_server::{timestamp_millis, SessionBuilder};
+use crate::scheduler_server::{timestamp_millis, timestamp_secs, SessionBuilder};
 use crate::state::session_manager::{
     create_datafusion_context, update_datafusion_context,
 };
@@ -44,13 +45,14 @@ use std::collections::{HashMap, HashSet};
 use std::ops::DerefMut;
 
 use std::sync::Arc;
+use tracing::debug;
 
 #[derive(Default)]
 pub struct InMemoryClusterState {
     /// Current available task slots for each executor
     task_slots: Mutex<ExecutorTaskSlots>,
     /// Current executors
-    executors: DashMap<String, (ExecutorMetadata, ExecutorData)>,
+    executors: DashMap<String, ExecutorMetadata>,
     /// Last heartbeat received for each executor
     heartbeats: DashMap<String, ExecutorHeartbeat>,
     /// Broadcast channel sender for heartbeats, If `None` there are not
@@ -68,17 +70,25 @@ impl ClusterState for InMemoryClusterState {
     ) -> Result<Vec<ExecutorReservation>> {
         let mut guard = self.task_slots.lock();
 
-        let slots_iter = guard.task_slots.iter_mut().filter(|slots| {
-            executors
-                .as_ref()
-                .map(|executors| executors.contains(&slots.executor_id))
-                .unwrap_or(true)
-        });
+        let mut available_slots: Vec<&mut AvailableTaskSlots> = guard
+            .task_slots
+            .iter_mut()
+            .filter_map(|data| {
+                (data.slots > 0
+                    && executors
+                        .as_ref()
+                        .map(|executors| executors.contains(&data.executor_id))
+                        .unwrap_or(true))
+                .then_some(data)
+            })
+            .collect();
+
+        available_slots.sort_by(|a, b| Ord::cmp(&b.slots, &a.slots));
 
         let reservations = match distribution {
-            TaskDistribution::Bias => reserve_slots_bias(slots_iter, num_slots),
+            TaskDistribution::Bias => reserve_slots_bias(available_slots, num_slots),
             TaskDistribution::RoundRobin => {
-                reserve_slots_round_robin(slots_iter, num_slots)
+                reserve_slots_round_robin(available_slots, num_slots)
             }
         };
 
@@ -95,17 +105,25 @@ impl ClusterState for InMemoryClusterState {
 
         let rollback = guard.clone();
 
-        let slots_iter = guard.task_slots.iter_mut().filter(|slots| {
-            executors
-                .as_ref()
-                .map(|executors| executors.contains(&slots.executor_id))
-                .unwrap_or(true)
-        });
+        let mut available_slots: Vec<&mut AvailableTaskSlots> = guard
+            .task_slots
+            .iter_mut()
+            .filter_map(|data| {
+                (data.slots > 0
+                    && executors
+                        .as_ref()
+                        .map(|executors| executors.contains(&data.executor_id))
+                        .unwrap_or(true))
+                .then_some(data)
+            })
+            .collect();
+
+        available_slots.sort_by(|a, b| Ord::cmp(&b.slots, &a.slots));
 
         let reservations = match distribution {
-            TaskDistribution::Bias => reserve_slots_bias(slots_iter, num_slots),
+            TaskDistribution::Bias => reserve_slots_bias(available_slots, num_slots),
             TaskDistribution::RoundRobin => {
-                reserve_slots_round_robin(slots_iter, num_slots)
+                reserve_slots_round_robin(available_slots, num_slots)
             }
         };
 
@@ -149,13 +167,24 @@ impl ClusterState for InMemoryClusterState {
     ) -> Result<Vec<ExecutorReservation>> {
         let heartbeat = ExecutorHeartbeat {
             executor_id: metadata.id.clone(),
-            timestamp: timestamp_millis(),
+            timestamp: timestamp_secs(),
             metrics: vec![],
             status: Some(ExecutorStatus {
                 status: Some(executor_status::Status::Active(String::default())),
             }),
         };
 
+        let mut guard = self.task_slots.lock();
+
+        // Check to see if we already have task slots for executor. If so, remove them.
+        if let Some((idx, _)) = guard
+            .task_slots
+            .iter()
+            .find_position(|slots| slots.executor_id == metadata.id)
+        {
+            guard.task_slots.swap_remove(idx);
+        }
+
         if reserve {
             let slots = std::mem::take(&mut spec.available_task_slots) as usize;
 
@@ -164,13 +193,23 @@ impl ClusterState for InMemoryClusterState {
                 .map(|_| ExecutorReservation::new_free(metadata.id.clone()))
                 .collect();
 
-            self.executors.insert(metadata.id.clone(), (metadata, spec));
+            self.executors.insert(metadata.id.clone(), metadata.clone());
+
+            guard.task_slots.push(AvailableTaskSlots {
+                executor_id: metadata.id,
+                slots: 0,
+            });
 
             self.heartbeat_sender.send(&heartbeat);
 
             Ok(reservations)
         } else {
-            self.executors.insert(metadata.id.clone(), (metadata, spec));
+            self.executors.insert(metadata.id.clone(), metadata.clone());
+
+            guard.task_slots.push(AvailableTaskSlots {
+                executor_id: metadata.id,
+                slots: spec.available_task_slots,
+            });
 
             self.heartbeat_sender.send(&heartbeat);
 
@@ -179,21 +218,14 @@ impl ClusterState for InMemoryClusterState {
     }
 
     async fn save_executor_metadata(&self, metadata: ExecutorMetadata) -> Result<()> {
-        if let Some(pair) = self.executors.get_mut(&metadata.id).as_deref_mut() {
-            pair.0 = metadata;
-        } else {
-            warn!(
-                "Failed to update executor metadata, executor with ID {} not found",
-                metadata.id
-            );
-        }
+        self.executors.insert(metadata.id.clone(), metadata);
         Ok(())
     }
 
     async fn get_executor_metadata(&self, executor_id: &str) -> Result<ExecutorMetadata> {
         self.executors
             .get(executor_id)
-            .map(|pair| pair.value().0.clone())
+            .map(|pair| pair.value().clone())
             .ok_or_else(|| {
                 BallistaError::Internal(format!(
                     "Not executor with ID {executor_id} found"
@@ -227,8 +259,20 @@ impl ClusterState for InMemoryClusterState {
             }
         }
 
-        self.executors.remove(executor_id);
-        self.heartbeats.remove(executor_id);
+        if let Some(heartbeat) = self.heartbeats.get_mut(executor_id).as_deref_mut() {
+            let new_heartbeat = ExecutorHeartbeat {
+                executor_id: executor_id.to_string(),
+                timestamp: timestamp_secs(),
+                metrics: vec![],
+                status: Some(ExecutorStatus {
+                    status: Some(executor_status::Status::Dead(String::default())),
+                }),
+            };
+
+            *heartbeat = new_heartbeat;
+
+            self.heartbeat_sender.send(heartbeat);
+        }
 
         Ok(())
     }
@@ -254,6 +298,8 @@ pub struct InMemoryJobState {
     completed_jobs: DashMap<String, (JobStatus, Option<ExecutionGraph>)>,
     /// In-memory store of queued jobs. Map from Job ID -> (Job Name, queued_at timestamp)
     queued_jobs: DashMap<String, (String, u64)>,
+    /// In-memory store of running job statuses. Map from Job ID -> JobStatus
+    running_jobs: DashMap<String, JobStatus>,
     /// Active ballista sessions
     sessions: DashMap<String, Arc<SessionContext>>,
     /// `SessionBuilder` for building DataFusion `SessionContext` from `BallistaConfig`
@@ -268,6 +314,7 @@ impl InMemoryJobState {
             scheduler: scheduler.into(),
             completed_jobs: Default::default(),
             queued_jobs: Default::default(),
+            running_jobs: Default::default(),
             sessions: Default::default(),
             session_builder,
             job_event_sender: ClusterEventSender::new(100),
@@ -277,27 +324,52 @@ impl InMemoryJobState {
 
 #[async_trait]
 impl JobState for InMemoryJobState {
-    async fn submit_job(&self, job_id: String, _graph: &ExecutionGraph) -> Result<()> {
-        self.job_event_sender.send(&JobStateEvent::JobAcquired {
-            job_id,
-            owner: self.scheduler.clone(),
-        });
+    async fn submit_job(&self, job_id: String, graph: &ExecutionGraph) -> Result<()> {
+        if self.queued_jobs.get(&job_id).is_some() {
+            self.running_jobs.insert(job_id.clone(), graph.status());
+            self.queued_jobs.remove(&job_id);
 
-        Ok(())
+            self.job_event_sender.send(&JobStateEvent::JobAcquired {
+                job_id,
+                owner: self.scheduler.clone(),
+            });
+
+            Ok(())
+        } else {
+            Err(BallistaError::Internal(format!(
+                "Failed to submit job {job_id}, not found in queued jobs"
+            )))
+        }
     }
 
     async fn get_job_status(&self, job_id: &str) -> Result<Option<JobStatus>> {
-        Ok(self
-            .completed_jobs
-            .get(job_id)
-            .map(|pair| pair.value().0.clone()))
+        if let Some((job_name, queued_at)) = self.queued_jobs.get(job_id).as_deref() {
+            return Ok(Some(JobStatus {
+                job_id: job_id.to_string(),
+                job_name: job_name.clone(),
+                status: Some(Status::Queued(QueuedJob {
+                    queued_at: *queued_at,
+                })),
+            }));
+        }
+
+        if let Some(status) = self.running_jobs.get(job_id).as_deref().cloned() {
+            return Ok(Some(status));
+        }
+
+        if let Some((status, _)) = self.completed_jobs.get(job_id).as_deref() {
+            return Ok(Some(status.clone()));
+        }
+
+        Ok(None)
     }
 
     async fn get_execution_graph(&self, job_id: &str) -> Result<Option<ExecutionGraph>> {
         Ok(self
             .completed_jobs
             .get(job_id)
-            .and_then(|pair| pair.value().1.clone()))
+            .as_deref()
+            .and_then(|(_, graph)| graph.clone()))
     }
 
     async fn try_acquire_job(&self, _job_id: &str) -> Result<Option<ExecutionGraph>> {
@@ -309,6 +381,8 @@ impl JobState for InMemoryJobState {
     async fn save_job(&self, job_id: &str, graph: &ExecutionGraph) -> Result<()> {
         let status = graph.status();
 
+        debug!("saving state for job {job_id} with status {:?}", status);
+
         // If job is either successful or failed, save to completed jobs
         if matches!(
             status.status,
@@ -316,6 +390,14 @@ impl JobState for InMemoryJobState {
         ) {
             self.completed_jobs
                 .insert(job_id.to_string(), (status, Some(graph.clone())));
+            self.running_jobs.remove(job_id);
+        } else if let Some(old_status) =
+            self.running_jobs.insert(job_id.to_string(), graph.status())
+        {
+            self.job_event_sender.send(&JobStateEvent::JobUpdated {
+                job_id: job_id.to_string(),
+                status: old_status,
+            })
         }
 
         Ok(())
@@ -389,17 +471,16 @@ impl JobState for InMemoryJobState {
     }
 
     async fn fail_unscheduled_job(&self, job_id: &str, reason: String) -> Result<()> {
-        if let Some(pair) = self.queued_jobs.get(job_id) {
-            let (job_name, queued_at) = pair.value();
+        if let Some((job_id, (job_name, queued_at))) = self.queued_jobs.remove(job_id) {
             self.completed_jobs.insert(
-                job_id.to_string(),
+                job_id.clone(),
                 (
                     JobStatus {
-                        job_id: job_id.to_string(),
-                        job_name: job_name.clone(),
+                        job_id,
+                        job_name,
                         status: Some(Status::Failed(FailedJob {
                             error: reason,
-                            queued_at: *queued_at,
+                            queued_at,
                             started_at: 0,
                             ended_at: timestamp_millis(),
                         })),
@@ -416,3 +497,99 @@ impl JobState for InMemoryJobState {
         }
     }
 }
+
+#[cfg(test)]
+mod test {
+    use crate::cluster::memory::{InMemoryClusterState, InMemoryJobState};
+    use crate::cluster::test::{
+        test_executor_registration, test_fuzz_reservations, test_job_lifecycle,
+        test_job_planning_failure, test_reservation,
+    };
+    use crate::cluster::TaskDistribution;
+    use crate::test_utils::{
+        test_aggregation_plan, test_join_plan, test_two_aggregations_plan,
+    };
+    use ballista_core::error::Result;
+    use ballista_core::utils::default_session_builder;
+
+    #[tokio::test]
+    async fn test_in_memory_registration() -> Result<()> {
+        test_executor_registration(InMemoryClusterState::default()).await
+    }
+
+    #[tokio::test]
+    async fn test_in_memory_reserve() -> Result<()> {
+        test_reservation(InMemoryClusterState::default(), TaskDistribution::Bias).await?;
+        test_reservation(
+            InMemoryClusterState::default(),
+            TaskDistribution::RoundRobin,
+        )
+        .await?;
+
+        Ok(())
+    }
+
+    #[tokio::test]
+    async fn test_in_memory_fuzz_reserve() -> Result<()> {
+        test_fuzz_reservations(
+            InMemoryClusterState::default(),
+            10,
+            TaskDistribution::Bias,
+            10,
+            10,
+        )
+        .await?;
+        test_fuzz_reservations(
+            InMemoryClusterState::default(),
+            10,
+            TaskDistribution::RoundRobin,
+            10,
+            10,
+        )
+        .await?;
+
+        Ok(())
+    }
+
+    #[tokio::test]
+    async fn test_in_memory_job_lifecycle() -> Result<()> {
+        test_job_lifecycle(
+            InMemoryJobState::new("", default_session_builder),
+            test_aggregation_plan(4).await,
+        )
+        .await?;
+        test_job_lifecycle(
+            InMemoryJobState::new("", default_session_builder),
+            test_two_aggregations_plan(4).await,
+        )
+        .await?;
+        test_job_lifecycle(
+            InMemoryJobState::new("", default_session_builder),
+            test_join_plan(4).await,
+        )
+        .await?;
+
+        Ok(())
+    }
+
+    #[tokio::test]
+    async fn test_in_memory_job_planning_failure() -> Result<()> {
+        test_job_planning_failure(
+            InMemoryJobState::new("", default_session_builder),
+            test_aggregation_plan(4).await,
+        )
+        .await?;
+        test_job_planning_failure(
+            InMemoryJobState::new("", default_session_builder),
+            test_two_aggregations_plan(4).await,
+        )
+        .await?;
+        test_job_planning_failure(
+            InMemoryJobState::new("", default_session_builder),
+            test_join_plan(4).await,
+        )
+        .await?;
+
+        Ok(())
+    }
+}
diff --git a/ballista/scheduler/src/cluster/mod.rs b/ballista/scheduler/src/cluster/mod.rs
index f23fa070..b443d204 100644
--- a/ballista/scheduler/src/cluster/mod.rs
+++ b/ballista/scheduler/src/cluster/mod.rs
@@ -20,6 +20,9 @@ pub mod kv;
 pub mod memory;
 pub mod storage;
 
+#[cfg(test)]
+pub mod test;
+
 use crate::cluster::kv::KeyValueState;
 use crate::cluster::memory::{InMemoryClusterState, InMemoryJobState};
 use crate::cluster::storage::etcd::EtcdClient;
@@ -203,7 +206,7 @@ pub enum TaskDistribution {
 
 /// A trait that contains the necessary method to maintain a globally consistent view of cluster resources
 #[tonic::async_trait]
-pub trait ClusterState: Send + Sync {
+pub trait ClusterState: Send + Sync + 'static {
     /// Reserve up to `num_slots` executor task slots. If not enough task slots are available, reserve
     /// as many as possible.
     ///
@@ -264,7 +267,8 @@ pub trait ClusterState: Send + Sync {
     async fn executor_heartbeats(&self) -> Result<HashMap<String, ExecutorHeartbeat>>;
 }
 
-#[derive(Debug, Clone)]
+/// Events related to the state of jobs. Implementations may or may not support all event types.
+#[derive(Debug, Clone, PartialEq)]
 pub enum JobStateEvent {
     /// Event when a job status has been updated
     JobUpdated {
@@ -372,14 +376,16 @@ pub trait JobState: Send + Sync {
     ) -> Result<Arc<SessionContext>>;
 }
 
-pub(crate) fn reserve_slots_bias<'a, I: Iterator<Item = &'a mut AvailableTaskSlots>>(
-    mut slots: I,
+pub(crate) fn reserve_slots_bias(
+    mut slots: Vec<&mut AvailableTaskSlots>,
     mut n: u32,
 ) -> Vec<ExecutorReservation> {
     let mut reservations = Vec::with_capacity(n as usize);
 
+    let mut iter = slots.iter_mut();
+
     while n > 0 {
-        if let Some(executor) = slots.next() {
+        if let Some(executor) = iter.next() {
             let take = executor.slots.min(n);
             for _ in 0..take {
                 reservations
@@ -396,24 +402,37 @@ pub(crate) fn reserve_slots_bias<'a, I: Iterator<Item = &'a mut AvailableTaskSlo
     reservations
 }
 
-pub(crate) fn reserve_slots_round_robin<
-    'a,
-    I: Iterator<Item = &'a mut AvailableTaskSlots>,
->(
-    mut slots: I,
+pub(crate) fn reserve_slots_round_robin(
+    mut slots: Vec<&mut AvailableTaskSlots>,
     mut n: u32,
 ) -> Vec<ExecutorReservation> {
     let mut reservations = Vec::with_capacity(n as usize);
 
-    while n > 0 {
-        if let Some(executor) = slots.next() {
-            if executor.slots > 0 {
-                reservations
-                    .push(ExecutorReservation::new_free(executor.executor_id.clone()));
-                executor.slots -= 1;
-                n -= 1;
+    let mut last_updated_idx = 0usize;
+
+    loop {
+        let n_before = n;
+        for (idx, data) in slots.iter_mut().enumerate() {
+            if n == 0 {
+                break;
             }
-        } else {
+
+            // Since the vector is sorted in descending order,
+            // if finding one executor has not enough slots, the following will have not enough, either
+            if data.slots == 0 {
+                break;
+            }
+
+            reservations.push(ExecutorReservation::new_free(data.executor_id.clone()));
+            data.slots -= 1;
+            n -= 1;
+
+            if idx >= last_updated_idx {
+                last_updated_idx = idx + 1;
+            }
+        }
+
+        if n_before == n {
             break;
         }
     }
diff --git a/ballista/scheduler/src/cluster/test/mod.rs b/ballista/scheduler/src/cluster/test/mod.rs
new file mode 100644
index 00000000..5ff6a978
--- /dev/null
+++ b/ballista/scheduler/src/cluster/test/mod.rs
@@ -0,0 +1,595 @@
+// 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.
+
+use crate::cluster::{ClusterState, JobState, JobStateEvent, TaskDistribution};
+use crate::scheduler_server::timestamp_millis;
+use crate::state::execution_graph::ExecutionGraph;
+use crate::state::executor_manager::ExecutorReservation;
+use crate::test_utils::{await_condition, mock_completed_task, mock_executor};
+use ballista_core::error::{BallistaError, Result};
+use ballista_core::serde::protobuf::job_status::Status;
+use ballista_core::serde::protobuf::{executor_status, ExecutorHeartbeat, JobStatus};
+use ballista_core::serde::scheduler::{
+    ExecutorData, ExecutorMetadata, ExecutorSpecification,
+};
+use dashmap::DashMap;
+use futures::StreamExt;
+use itertools::Itertools;
+use std::collections::HashSet;
+use std::sync::Arc;
+use std::time::Duration;
+use tokio::sync::RwLock;
+
+pub struct ClusterStateTest<S: ClusterState> {
+    state: Arc<S>,
+    received_heartbeats: Arc<DashMap<String, ExecutorHeartbeat>>,
+    reservations: Vec<ExecutorReservation>,
+    total_task_slots: u32,
+}
+
+impl<S: ClusterState> ClusterStateTest<S> {
+    pub async fn new(state: S) -> Result<Self> {
+        let received_heartbeats = Arc::new(DashMap::new());
+
+        let mut heartbeat_stream = state.executor_heartbeat_stream().await?;
+        let received_heartbeat_clone = received_heartbeats.clone();
+
+        tokio::spawn(async move {
+            while let Some(heartbeat) = heartbeat_stream.next().await {
+                received_heartbeat_clone.insert(heartbeat.executor_id.clone(), heartbeat);
+            }
+        });
+
+        Ok(Self {
+            state: Arc::new(state),
+            received_heartbeats,
+            reservations: vec![],
+            total_task_slots: 0,
+        })
+    }
+
+    pub async fn register_executor(
+        mut self,
+        executor_id: &str,
+        task_slots: u32,
+    ) -> Result<Self> {
+        self.state
+            .register_executor(
+                ExecutorMetadata {
+                    id: executor_id.to_string(),
+                    host: executor_id.to_string(),
+                    port: 0,
+                    grpc_port: 0,
+                    specification: ExecutorSpecification { task_slots },
+                },
+                ExecutorData {
+                    executor_id: executor_id.to_string(),
+                    total_task_slots: task_slots,
+                    available_task_slots: task_slots,
+                },
+                false,
+            )
+            .await?;
+
+        self.total_task_slots += task_slots;
+
+        Ok(self)
+    }
+
+    pub async fn remove_executor(self, executor_id: &str) -> Result<Self> {
+        self.state.remove_executor(executor_id).await?;
+
+        Ok(self)
+    }
+
+    pub async fn assert_live_executor(
+        self,
+        executor_id: &str,
+        task_slots: u32,
+    ) -> Result<Self> {
+        let executor = self.state.get_executor_metadata(executor_id).await;
+        assert!(
+            executor.is_ok(),
+            "Metadata for executor {} not found in state",
+            executor_id
+        );
+        assert_eq!(
+            executor.unwrap().specification.task_slots,
+            task_slots,
+            "Unexpected number of task slots for executor"
+        );
+
+        // Heratbeat stream is async so wait up to 500ms for it to show up
+        await_condition(Duration::from_millis(50), 10, || {
+            let found_heartbeat =
+                self.received_heartbeats.get(executor_id).map(|heartbeat| {
+                    matches!(
+                        heartbeat.status,
+                        Some(ballista_core::serde::generated::ballista::ExecutorStatus {
+                            status: Some(executor_status::Status::Active(_))
+                        })
+                    )
+                });
+
+            futures::future::ready(Ok(found_heartbeat.unwrap_or_default()))
+        })
+        .await?;
+
+        Ok(self)
+    }
+
+    pub async fn assert_dead_executor(self, executor_id: &str) -> Result<Self> {
+        // Heratbeat stream is async so wait up to 500ms for it to show up
+        await_condition(Duration::from_millis(50), 10, || {
+            let found_heartbeat =
+                self.received_heartbeats.get(executor_id).map(|heartbeat| {
+                    matches!(
+                        heartbeat.status,
+                        Some(ballista_core::serde::generated::ballista::ExecutorStatus {
+                            status: Some(executor_status::Status::Dead(_))
+                        })
+                    )
+                });
+
+            futures::future::ready(Ok(found_heartbeat.unwrap_or_default()))
+        })
+        .await?;
+
+        Ok(self)
+    }
+
+    pub async fn try_reserve_slots(
+        mut self,
+        num_slots: u32,
+        distribution: TaskDistribution,
+        filter: Option<Vec<String>>,
+        exact: bool,
+    ) -> Result<Self> {
+        let filter = filter.map(|f| f.into_iter().collect::<HashSet<String>>());
+        let reservations = if exact {
+            self.state
+                .reserve_slots_exact(num_slots, distribution, filter)
+                .await?
+        } else {
+            self.state
+                .reserve_slots(num_slots, distribution, filter)
+                .await?
+        };
+
+        self.reservations.extend(reservations);
+
+        Ok(self)
+    }
+
+    pub async fn cancel_reservations(mut self, num_slots: usize) -> Result<Self> {
+        if self.reservations.len() < num_slots {
+            return Err(BallistaError::General(format!(
+                "Not enough reservations to cancel, expected {} but found {}",
+                num_slots,
+                self.reservations.len()
+            )));
+        }
+
+        let to_keep = self.reservations.split_off(num_slots);
+
+        self.state
+            .cancel_reservations(std::mem::take(&mut self.reservations))
+            .await?;
+
+        self.reservations = to_keep;
+
+        Ok(self)
+    }
+
+    pub fn assert_open_reservations(self, n: usize) -> Self {
+        assert_eq!(
+            self.reservations.len(),
+            n,
+            "Expectedt {n} open reservations but found {}",
+            self.reservations.len()
+        );
+        self
+    }
+
+    pub fn assert_open_reservations_with<F: Fn(&ExecutorReservation) -> bool>(
+        self,
+        n: usize,
+        predicate: F,
+    ) -> Self {
+        assert_eq!(
+            self.reservations.len(),
+            n,
+            "Expectedt {n} open reservations but found {}",
+            self.reservations.len()
+        );
+
+        for res in &self.reservations {
+            assert!(predicate(res), "Predicate failed on reservation {:?}", res);
+        }
+        self
+    }
+
+    pub async fn fuzz_reservation(
+        mut self,
+        concurrency: usize,
+        distribution: TaskDistribution,
+    ) -> Result<()> {
+        let (sender, mut receiver) = tokio::sync::mpsc::channel(1_000);
+
+        let total_slots = self.total_task_slots;
+        for _ in 0..concurrency {
+            let state = self.state.clone();
+            let sender_clone = sender.clone();
+            tokio::spawn(async move {
+                let mut open_reservations = vec![];
+                for i in 0..10 {
+                    if i % 2 == 0 {
+                        let to_reserve = rand::random::<u32>() % total_slots;
+
+                        let reservations = state
+                            .reserve_slots(to_reserve, distribution, None)
+                            .await
+                            .unwrap();
+
+                        sender_clone
+                            .send(FuzzEvent::Reserved(reservations.clone()))
+                            .await
+                            .unwrap();
+
+                        open_reservations = reservations;
+                    } else {
+                        state
+                            .cancel_reservations(open_reservations.clone())
+                            .await
+                            .unwrap();
+                        sender_clone
+                            .send(FuzzEvent::Cancelled(std::mem::take(
+                                &mut open_reservations,
+                            )))
+                            .await
+                            .unwrap();
+                    }
+                }
+            });
+        }
+
+        drop(sender);
+
+        while let Some(event) = receiver.recv().await {
+            match event {
+                FuzzEvent::Reserved(reservations) => {
+                    self.reservations.extend(reservations);
+                    assert!(
+                        self.reservations.len() <= total_slots as usize,
+                        "More than total number of slots was reserved"
+                    );
+                }
+                FuzzEvent::Cancelled(reservations) => {
+                    for res in reservations {
+                        let idx = self
+                            .reservations
+                            .iter()
+                            .find_position(|r| r.executor_id == res.executor_id);
+                        assert!(idx.is_some(), "Received invalid cancellation, not existing reservation for executor ID {}", res.executor_id);
+
+                        self.reservations.swap_remove(idx.unwrap().0);
+                    }
+                }
+            }
+        }
+
+        Ok(())
+    }
+}
+
+#[derive(Debug, Clone)]
+enum FuzzEvent {
+    Reserved(Vec<ExecutorReservation>),
+    Cancelled(Vec<ExecutorReservation>),
+}
+
+pub async fn test_fuzz_reservations<S: ClusterState>(
+    state: S,
+    concurrency: usize,
+    distribution: TaskDistribution,
+    num_executors: usize,
+    task_slots_per_executor: usize,
+) -> Result<()> {
+    let mut test = ClusterStateTest::new(state).await?;
+
+    for idx in 0..num_executors {
+        test = test
+            .register_executor(idx.to_string().as_str(), task_slots_per_executor as u32)
+            .await?;
+    }
+
+    test.fuzz_reservation(concurrency, distribution).await
+}
+
+pub async fn test_executor_registration<S: ClusterState>(state: S) -> Result<()> {
+    let test = ClusterStateTest::new(state).await?;
+
+    test.register_executor("1", 10)
+        .await?
+        .register_executor("2", 10)
+        .await?
+        .register_executor("3", 10)
+        .await?
+        .assert_live_executor("1", 10)
+        .await?
+        .assert_live_executor("2", 10)
+        .await?
+        .assert_live_executor("3", 10)
+        .await?
+        .remove_executor("1")
+        .await?
+        .assert_dead_executor("1")
+        .await?
+        .remove_executor("2")
+        .await?
+        .assert_dead_executor("2")
+        .await?
+        .remove_executor("3")
+        .await?
+        .assert_dead_executor("3")
+        .await?;
+
+    Ok(())
+}
+
+pub async fn test_reservation<S: ClusterState>(
+    state: S,
+    distribution: TaskDistribution,
+) -> Result<()> {
+    let test = ClusterStateTest::new(state).await?;
+
+    test.register_executor("1", 10)
+        .await?
+        .register_executor("2", 10)
+        .await?
+        .register_executor("3", 10)
+        .await?
+        .try_reserve_slots(10, distribution, None, false)
+        .await?
+        .assert_open_reservations(10)
+        .cancel_reservations(10)
+        .await?
+        .try_reserve_slots(30, distribution, None, false)
+        .await?
+        .assert_open_reservations(30)
+        .cancel_reservations(15)
+        .await?
+        .assert_open_reservations(15)
+        .try_reserve_slots(30, distribution, None, false)
+        .await?
+        .assert_open_reservations(30)
+        .cancel_reservations(30)
+        .await?
+        .assert_open_reservations(0)
+        .try_reserve_slots(50, distribution, None, false)
+        .await?
+        .assert_open_reservations(30)
+        .cancel_reservations(30)
+        .await?
+        .try_reserve_slots(20, distribution, Some(vec!["1".to_string()]), false)
+        .await?
+        .assert_open_reservations_with(10, |res| res.executor_id == "1")
+        .cancel_reservations(10)
+        .await?
+        .try_reserve_slots(
+            20,
+            distribution,
+            Some(vec!["2".to_string(), "3".to_string()]),
+            false,
+        )
+        .await?
+        .assert_open_reservations_with(20, |res| {
+            res.executor_id == "2" || res.executor_id == "3"
+        });
+
+    Ok(())
+}
+
+pub struct JobStateTest<S: JobState> {
+    state: Arc<S>,
+    events: Arc<RwLock<Vec<JobStateEvent>>>,
+}
+
+impl<S: JobState> JobStateTest<S> {
+    pub async fn new(state: S) -> Result<Self> {
+        let events = Arc::new(RwLock::new(vec![]));
+
+        let mut event_stream = state.job_state_events().await?;
+        let events_clone = events.clone();
+        tokio::spawn(async move {
+            while let Some(event) = event_stream.next().await {
+                let mut guard = events_clone.write().await;
+
+                guard.push(event);
+            }
+        });
+
+        Ok(Self {
+            state: Arc::new(state),
+            events,
+        })
+    }
+
+    pub async fn queue_job(self, job_id: &str) -> Result<Self> {
+        self.state
+            .accept_job(job_id, "", timestamp_millis())
+            .await?;
+        Ok(self)
+    }
+
+    pub async fn fail_planning(self, job_id: &str) -> Result<Self> {
+        self.state
+            .fail_unscheduled_job(job_id, "failed planning".to_string())
+            .await?;
+        Ok(self)
+    }
+
+    pub async fn assert_queued(self, job_id: &str) -> Result<Self> {
+        let status = self.state.get_job_status(job_id).await?;
+
+        assert!(status.is_some(), "Queued job {} not found", job_id);
+
+        let status = status.unwrap();
+        assert!(
+            matches!(&status, JobStatus {
+            job_id: status_job_id, status: Some(Status::Queued(_)), ..
+        } if status_job_id.as_str() == job_id),
+            "Expected queued status but found {:?}",
+            status
+        );
+
+        Ok(self)
+    }
+
+    pub async fn submit_job(self, graph: &ExecutionGraph) -> Result<Self> {
+        self.state
+            .submit_job(graph.job_id().to_string(), graph)
+            .await?;
+        Ok(self)
+    }
+
+    pub async fn assert_job_running(self, job_id: &str) -> Result<Self> {
+        let status = self.state.get_job_status(job_id).await?;
+
+        assert!(status.is_some(), "Job status not found for {}", job_id);
+
+        let status = status.unwrap();
+        assert!(
+            matches!(&status, JobStatus {
+            job_id: status_job_id, status: Some(Status::Running(_)), ..
+        } if status_job_id.as_str() == job_id),
+            "Expected running status but found {:?}",
+            status
+        );
+
+        Ok(self)
+    }
+
+    pub async fn update_job(self, graph: &ExecutionGraph) -> Result<Self> {
+        self.state.save_job(graph.job_id(), graph).await?;
+        Ok(self)
+    }
+
+    pub async fn assert_job_failed(self, job_id: &str) -> Result<Self> {
+        let status = self.state.get_job_status(job_id).await?;
+
+        assert!(status.is_some(), "Job status not found for {}", job_id);
+
+        let status = status.unwrap();
+        assert!(
+            matches!(&status, JobStatus {
+            job_id: status_job_id, status: Some(Status::Failed(_)), ..
+        } if status_job_id.as_str() == job_id),
+            "Expected failed status but found {:?}",
+            status
+        );
+
+        Ok(self)
+    }
+
+    pub async fn assert_job_successful(self, job_id: &str) -> Result<Self> {
+        let status = self.state.get_job_status(job_id).await?;
+
+        assert!(status.is_some(), "Job status not found for {}", job_id);
+        let status = status.unwrap();
+        assert!(
+            matches!(&status, JobStatus {
+            job_id: status_job_id, status: Some(Status::Successful(_)), ..
+        } if status_job_id.as_str() == job_id),
+            "Expected success status but found {:?}",
+            status
+        );
+
+        Ok(self)
+    }
+
+    pub async fn assert_event(self, event: JobStateEvent) -> Result<Self> {
+        let events = self.events.clone();
+        let found = await_condition(Duration::from_millis(50), 10, || async {
+            let guard = events.read().await;
+
+            Ok(guard.iter().any(|ev| ev == &event))
+        })
+        .await?;
+
+        assert!(found, "Expected event {:?}", event);
+
+        Ok(self)
+    }
+}
+
+pub async fn test_job_lifecycle<S: JobState>(
+    state: S,
+    mut graph: ExecutionGraph,
+) -> Result<()> {
+    let test = JobStateTest::new(state).await?;
+
+    let job_id = graph.job_id().to_string();
+
+    let test = test
+        .queue_job(&job_id)
+        .await?
+        .assert_queued(&job_id)
+        .await?
+        .submit_job(&graph)
+        .await?
+        .assert_job_running(&job_id)
+        .await?;
+
+    drain_tasks(&mut graph)?;
+    graph.succeed_job()?;
+
+    test.update_job(&graph)
+        .await?
+        .assert_job_successful(&job_id)
+        .await?;
+
+    Ok(())
+}
+
+pub async fn test_job_planning_failure<S: JobState>(
+    state: S,
+    graph: ExecutionGraph,
+) -> Result<()> {
+    let test = JobStateTest::new(state).await?;
+
+    let job_id = graph.job_id().to_string();
+
+    test.queue_job(&job_id)
+        .await?
+        .fail_planning(&job_id)
+        .await?
+        .assert_job_failed(&job_id)
+        .await?;
+
+    Ok(())
+}
+
+fn drain_tasks(graph: &mut ExecutionGraph) -> Result<()> {
+    let executor = mock_executor("executor-id1".to_string());
+    while let Some(task) = graph.pop_next_task(&executor.id)? {
+        let task_status = mock_completed_task(task, &executor.id);
+        graph.update_task_status(&executor, vec![task_status], 1, 1)?;
+    }
+
+    Ok(())
+}
diff --git a/ballista/scheduler/src/scheduler_server/mod.rs b/ballista/scheduler/src/scheduler_server/mod.rs
index 155e2725..225a32f3 100644
--- a/ballista/scheduler/src/scheduler_server/mod.rs
+++ b/ballista/scheduler/src/scheduler_server/mod.rs
@@ -361,6 +361,13 @@ mod test {
 
         let job_id = "job";
 
+        // Enqueue job
+        scheduler
+            .state
+            .task_manager
+            .queue_job(job_id, "", timestamp_millis())
+            .await?;
+
         // Submit job
         scheduler
             .state
@@ -373,7 +380,6 @@ mod test {
             .state
             .task_manager
             .get_active_execution_graph(job_id)
-            .await
         {
             let task = {
                 let mut graph = graph.write().await;
@@ -427,7 +433,6 @@ mod test {
             .state
             .task_manager
             .get_active_execution_graph(job_id)
-            .await
             .expect("Fail to find graph in the cache");
 
         let final_graph = final_graph.read().await;
diff --git a/ballista/scheduler/src/scheduler_server/query_stage_scheduler.rs b/ballista/scheduler/src/scheduler_server/query_stage_scheduler.rs
index 29f3d2d7..21683325 100644
--- a/ballista/scheduler/src/scheduler_server/query_stage_scheduler.rs
+++ b/ballista/scheduler/src/scheduler_server/query_stage_scheduler.rs
@@ -100,6 +100,11 @@ impl<T: 'static + AsLogicalPlan, U: 'static + AsExecutionPlan>
             } => {
                 info!("Job {} queued with name {:?}", job_id, job_name);
 
+                self.state
+                    .task_manager
+                    .queue_job(&job_id, &job_name, queued_at)
+                    .await?;
+
                 let state = self.state.clone();
                 tokio::spawn(async move {
                     let event = if let Err(e) = state
@@ -234,6 +239,11 @@ impl<T: 'static + AsLogicalPlan, U: 'static + AsExecutionPlan>
                     .await?;
             }
             QueryStageSchedulerEvent::TaskUpdating(executor_id, tasks_status) => {
+                debug!(
+                    "processing task status updates from {executor_id}: {:?}",
+                    tasks_status
+                );
+
                 let num_status = tasks_status.len();
                 match self
                     .state
@@ -324,9 +334,14 @@ mod tests {
     use datafusion::test_util::scan_empty_with_partitions;
     use std::sync::Arc;
     use std::time::Duration;
+    use tracing_subscriber::EnvFilter;
 
     #[tokio::test]
     async fn test_pending_task_metric() -> Result<()> {
+        tracing_subscriber::fmt()
+            .with_env_filter(EnvFilter::from_default_env())
+            .init();
+
         let plan = test_plan(10);
 
         let metrics_collector = Arc::new(TestMetricsCollector::default());
@@ -368,7 +383,7 @@ mod tests {
         test.tick().await?;
 
         // Job should be finished now
-        let _ = test.await_completion("job-1").await?;
+        let _ = test.await_completion_timeout("job-1", 5_000).await?;
 
         Ok(())
     }
diff --git a/ballista/scheduler/src/state/backend/cluster.rs b/ballista/scheduler/src/state/backend/cluster.rs
deleted file mode 100644
index 2370c492..00000000
--- a/ballista/scheduler/src/state/backend/cluster.rs
+++ /dev/null
@@ -1,710 +0,0 @@
-// 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.
-
-use crate::state::backend::{
-    Keyspace, Operation, StateBackendClient, TaskDistribution, WatchEvent,
-};
-use crate::state::executor_manager::ExecutorReservation;
-use crate::state::{decode_into, decode_protobuf, encode_protobuf, with_lock};
-use ballista_core::error;
-use ballista_core::error::BallistaError;
-use ballista_core::serde::protobuf;
-use ballista_core::serde::protobuf::{
-    executor_status, ExecutorHeartbeat, ExecutorStatus,
-};
-use ballista_core::serde::scheduler::{ExecutorData, ExecutorMetadata};
-use futures::{Stream, StreamExt};
-use log::{debug, info};
-use std::collections::{HashMap, HashSet};
-use std::pin::Pin;
-use std::sync::Arc;
-use std::time::{Duration, Instant, SystemTime, UNIX_EPOCH};
-
-pub type ExecutorHeartbeatStream = Pin<Box<dyn Stream<Item = ExecutorHeartbeat> + Send>>;
-
-/// A trait that contains the necessary method to maintain a globally consistent view of cluster resources
-#[tonic::async_trait]
-pub trait ClusterState: Send + Sync {
-    /// Reserve up to `num_slots` executor task slots. If not enough task slots are available, reserve
-    /// as many as possible.
-    ///
-    /// If `executors` is provided, only reserve slots of the specified executor IDs
-    async fn reserve_slots(
-        &self,
-        num_slots: u32,
-        distribution: TaskDistribution,
-        executors: Option<HashSet<String>>,
-    ) -> error::Result<Vec<ExecutorReservation>>;
-
-    /// Reserve exactly `num_slots` executor task slots. If not enough task slots are available,
-    /// returns an empty vec
-    ///
-    /// If `executors` is provided, only reserve slots of the specified executor IDs
-    async fn reserve_slots_exact(
-        &self,
-        num_slots: u32,
-        distribution: TaskDistribution,
-        executors: Option<HashSet<String>>,
-    ) -> error::Result<Vec<ExecutorReservation>>;
-
-    /// Cancel the specified reservations. This will make reserved executor slots available to other
-    /// tasks.
-    /// This operations should be atomic. Either all reservations are cancelled or none are
-    async fn cancel_reservations(
-        &self,
-        reservations: Vec<ExecutorReservation>,
-    ) -> error::Result<()>;
-
-    /// Register a new executor in the cluster. If `reserve` is true, then the executors task slots
-    /// will be reserved and returned in the response and none of the new executors task slots will be
-    /// available to other tasks.
-    async fn register_executor(
-        &self,
-        metadata: ExecutorMetadata,
-        spec: ExecutorData,
-        reserve: bool,
-    ) -> error::Result<Vec<ExecutorReservation>>;
-
-    /// Save the executor metadata. This will overwrite existing metadata for the executor ID
-    async fn save_executor_metadata(
-        &self,
-        metadata: ExecutorMetadata,
-    ) -> error::Result<()>;
-
-    /// Get executor metadata for the provided executor ID. Returns an error if the executor does not exist
-    async fn get_executor_metadata(
-        &self,
-        executor_id: &str,
-    ) -> error::Result<ExecutorMetadata>;
-
-    /// Save the executor heartbeat
-    async fn save_executor_heartbeat(
-        &self,
-        heartbeat: ExecutorHeartbeat,
-    ) -> error::Result<()>;
-
-    /// Remove the executor from the cluster
-    async fn remove_executor(&self, executor_id: &str) -> error::Result<()>;
-
-    /// Return the stream of executor heartbeats observed by all schedulers in the cluster.
-    /// This can be aggregated to provide an eventually consistent view of all executors within the cluster
-    async fn executor_heartbeat_stream(&self) -> error::Result<ExecutorHeartbeatStream>;
-
-    /// Return a map of the last seen heartbeat for all active executors
-    async fn executor_heartbeats(
-        &self,
-    ) -> error::Result<HashMap<String, ExecutorHeartbeat>>;
-}
-
-/// Default implementation of `ClusterState` that can use the key-value interface defined in
-/// `StateBackendClient
-pub struct DefaultClusterState {
-    kv_store: Arc<dyn StateBackendClient>,
-}
-
-impl DefaultClusterState {
-    pub fn new(kv_store: Arc<dyn StateBackendClient>) -> Self {
-        Self { kv_store }
-    }
-}
-
-#[tonic::async_trait]
-impl ClusterState for DefaultClusterState {
-    async fn reserve_slots(
-        &self,
-        num_slots: u32,
-        distribution: TaskDistribution,
-        executors: Option<HashSet<String>>,
-    ) -> error::Result<Vec<ExecutorReservation>> {
-        let lock = self.kv_store.lock(Keyspace::Slots, "global").await?;
-
-        with_lock(lock, async {
-            debug!("Attempting to reserve {} executor slots", num_slots);
-            let start = Instant::now();
-
-            let executors = match executors {
-                Some(executors) => executors,
-                None => {
-                    let heartbeats = self.executor_heartbeats().await?;
-
-                    get_alive_executors(60, heartbeats)?
-                }
-            };
-
-            let (reservations, txn_ops) = match distribution {
-                TaskDistribution::Bias => {
-                    reserve_slots_bias(self.kv_store.as_ref(), num_slots, executors)
-                        .await?
-                }
-                TaskDistribution::RoundRobin => {
-                    reserve_slots_round_robin(
-                        self.kv_store.as_ref(),
-                        num_slots,
-                        executors,
-                    )
-                    .await?
-                }
-            };
-
-            self.kv_store.apply_txn(txn_ops).await?;
-
-            let elapsed = start.elapsed();
-            info!(
-                "Reserved {} executor slots in {:?}",
-                reservations.len(),
-                elapsed
-            );
-
-            Ok(reservations)
-        })
-        .await
-    }
-
-    async fn reserve_slots_exact(
-        &self,
-        num_slots: u32,
-        distribution: TaskDistribution,
-        executors: Option<HashSet<String>>,
-    ) -> error::Result<Vec<ExecutorReservation>> {
-        let lock = self.kv_store.lock(Keyspace::Slots, "global").await?;
-
-        with_lock(lock, async {
-            debug!("Attempting to reserve {} executor slots", num_slots);
-            let start = Instant::now();
-
-            let executors = match executors {
-                Some(executors) => executors,
-                None => {
-                    let heartbeats = self.executor_heartbeats().await?;
-
-                    get_alive_executors(60, heartbeats)?
-                }
-            };
-
-            let (reservations, txn_ops) = match distribution {
-                TaskDistribution::Bias => {
-                    reserve_slots_bias(self.kv_store.as_ref(), num_slots, executors)
-                        .await?
-                }
-                TaskDistribution::RoundRobin => {
-                    reserve_slots_round_robin(
-                        self.kv_store.as_ref(),
-                        num_slots,
-                        executors,
-                    )
-                    .await?
-                }
-            };
-
-            let elapsed = start.elapsed();
-            if reservations.len() as u32 == num_slots {
-                self.kv_store.apply_txn(txn_ops).await?;
-
-                info!(
-                    "Reserved {} executor slots in {:?}",
-                    reservations.len(),
-                    elapsed
-                );
-
-                Ok(reservations)
-            } else {
-                info!(
-                    "Failed to reserve exactly {} executor slots in {:?}",
-                    reservations.len(),
-                    elapsed
-                );
-
-                Ok(vec![])
-            }
-        })
-        .await
-    }
-
-    async fn cancel_reservations(
-        &self,
-        reservations: Vec<ExecutorReservation>,
-    ) -> error::Result<()> {
-        let lock = self.kv_store.lock(Keyspace::Slots, "global").await?;
-
-        with_lock(lock, async {
-            let num_reservations = reservations.len();
-            debug!("Cancelling {} reservations", num_reservations);
-            let start = Instant::now();
-
-            let mut executor_slots: HashMap<String, ExecutorData> = HashMap::new();
-
-            for reservation in reservations {
-                let executor_id = &reservation.executor_id;
-                if let Some(data) = executor_slots.get_mut(executor_id) {
-                    data.available_task_slots += 1;
-                } else {
-                    let value = self.kv_store.get(Keyspace::Slots, executor_id).await?;
-                    let mut data =
-                        decode_into::<protobuf::ExecutorData, ExecutorData>(&value)?;
-                    data.available_task_slots += 1;
-                    executor_slots.insert(executor_id.clone(), data);
-                }
-            }
-
-            let txn_ops: Vec<(Operation, Keyspace, String)> = executor_slots
-                .into_iter()
-                .map(|(executor_id, data)| {
-                    let proto: protobuf::ExecutorData = data.into();
-                    let new_data = encode_protobuf(&proto)?;
-                    Ok((Operation::Put(new_data), Keyspace::Slots, executor_id))
-                })
-                .collect::<error::Result<Vec<_>>>()?;
-
-            self.kv_store.apply_txn(txn_ops).await?;
-
-            let elapsed = start.elapsed();
-            info!(
-                "Cancelled {} reservations in {:?}",
-                num_reservations, elapsed
-            );
-
-            Ok(())
-        })
-        .await
-    }
-
-    async fn register_executor(
-        &self,
-        metadata: ExecutorMetadata,
-        spec: ExecutorData,
-        reserve: bool,
-    ) -> error::Result<Vec<ExecutorReservation>> {
-        let executor_id = metadata.id.clone();
-
-        let current_ts = SystemTime::now()
-            .duration_since(UNIX_EPOCH)
-            .map_err(|e| {
-                BallistaError::Internal(format!(
-                    "Error getting current timestamp: {:?}",
-                    e
-                ))
-            })?
-            .as_secs();
-
-        //TODO this should be in a transaction
-        // Now that we know we can connect, save the metadata and slots
-        self.save_executor_metadata(metadata).await?;
-        self.save_executor_heartbeat(ExecutorHeartbeat {
-            executor_id: executor_id.clone(),
-            timestamp: current_ts,
-            metrics: vec![],
-            status: Some(ExecutorStatus {
-                status: Some(executor_status::Status::Active("".to_string())),
-            }),
-        })
-        .await?;
-
-        if !reserve {
-            let proto: protobuf::ExecutorData = spec.into();
-            let value = encode_protobuf(&proto)?;
-            self.kv_store
-                .put(Keyspace::Slots, executor_id, value)
-                .await?;
-            Ok(vec![])
-        } else {
-            let mut specification = spec;
-            let num_slots = specification.available_task_slots as usize;
-            let mut reservations: Vec<ExecutorReservation> = vec![];
-            for _ in 0..num_slots {
-                reservations.push(ExecutorReservation::new_free(executor_id.clone()));
-            }
-
-            specification.available_task_slots = 0;
-
-            let proto: protobuf::ExecutorData = specification.into();
-            let value = encode_protobuf(&proto)?;
-            self.kv_store
-                .put(Keyspace::Slots, executor_id, value)
-                .await?;
-            Ok(reservations)
-        }
-    }
-
-    async fn save_executor_metadata(
-        &self,
-        metadata: ExecutorMetadata,
-    ) -> error::Result<()> {
-        let executor_id = metadata.id.clone();
-        let proto: protobuf::ExecutorMetadata = metadata.into();
-        let value = encode_protobuf(&proto)?;
-
-        self.kv_store
-            .put(Keyspace::Executors, executor_id, value)
-            .await
-    }
-
-    async fn get_executor_metadata(
-        &self,
-        executor_id: &str,
-    ) -> error::Result<ExecutorMetadata> {
-        let value = self.kv_store.get(Keyspace::Executors, executor_id).await?;
-
-        let decoded =
-            decode_into::<protobuf::ExecutorMetadata, ExecutorMetadata>(&value)?;
-        Ok(decoded)
-    }
-
-    async fn save_executor_heartbeat(
-        &self,
-        heartbeat: ExecutorHeartbeat,
-    ) -> error::Result<()> {
-        let executor_id = heartbeat.executor_id.clone();
-        let value = encode_protobuf(&heartbeat)?;
-        self.kv_store
-            .put(Keyspace::Heartbeats, executor_id, value)
-            .await
-    }
-
-    async fn remove_executor(&self, executor_id: &str) -> error::Result<()> {
-        let current_ts = SystemTime::now()
-            .duration_since(UNIX_EPOCH)
-            .map_err(|e| {
-                BallistaError::Internal(format!(
-                    "Error getting current timestamp: {:?}",
-                    e
-                ))
-            })?
-            .as_secs();
-
-        let value = encode_protobuf(&ExecutorHeartbeat {
-            executor_id: executor_id.to_owned(),
-            timestamp: current_ts,
-            metrics: vec![],
-            status: Some(ExecutorStatus {
-                status: Some(executor_status::Status::Dead("".to_string())),
-            }),
-        })?;
-        self.kv_store
-            .put(Keyspace::Heartbeats, executor_id.to_owned(), value)
-            .await?;
-
-        // TODO Check the Executor reservation logic for push-based scheduling
-
-        Ok(())
-    }
-
-    async fn executor_heartbeat_stream(&self) -> error::Result<ExecutorHeartbeatStream> {
-        let events = self
-            .kv_store
-            .watch(Keyspace::Heartbeats, String::default())
-            .await?;
-
-        Ok(events
-            .filter_map(|event| {
-                futures::future::ready(match event {
-                    WatchEvent::Put(_, value) => {
-                        if let Ok(heartbeat) =
-                            decode_protobuf::<ExecutorHeartbeat>(&value)
-                        {
-                            Some(heartbeat)
-                        } else {
-                            None
-                        }
-                    }
-                    WatchEvent::Delete(_) => None,
-                })
-            })
-            .boxed())
-    }
-
-    async fn executor_heartbeats(
-        &self,
-    ) -> error::Result<HashMap<String, ExecutorHeartbeat>> {
-        let heartbeats = self.kv_store.scan(Keyspace::Heartbeats, None).await?;
-
-        let mut heartbeat_map = HashMap::with_capacity(heartbeats.len());
-
-        for (_, value) in heartbeats {
-            let data: ExecutorHeartbeat = decode_protobuf(&value)?;
-            if let Some(ExecutorStatus {
-                status: Some(executor_status::Status::Active(_)),
-            }) = &data.status
-            {
-                heartbeat_map.insert(data.executor_id.clone(), data);
-            }
-        }
-
-        Ok(heartbeat_map)
-    }
-}
-
-/// Return the set of executor IDs which have heartbeated within `last_seen_threshold` seconds
-fn get_alive_executors(
-    last_seen_threshold: u64,
-    heartbeats: HashMap<String, ExecutorHeartbeat>,
-) -> error::Result<HashSet<String>> {
-    let now_epoch_ts = SystemTime::now()
-        .duration_since(UNIX_EPOCH)
-        .expect("Time went backwards");
-
-    let last_seen_threshold = now_epoch_ts
-        .checked_sub(Duration::from_secs(last_seen_threshold))
-        .ok_or_else(|| {
-            BallistaError::Internal(format!(
-                "Error getting alive executors, invalid last_seen_threshold of {}",
-                last_seen_threshold
-            ))
-        })?
-        .as_secs();
-
-    Ok(heartbeats
-        .iter()
-        .filter_map(|(exec, heartbeat)| {
-            (heartbeat.timestamp > last_seen_threshold).then(|| exec.clone())
-        })
-        .collect())
-}
-
-/// It will get ExecutorReservation from one executor as many as possible.
-/// By this way, it can reduce the chance of decoding and encoding ExecutorData.
-/// However, it may make the whole cluster unbalanced,
-/// which means some executors may be very busy while other executors may be idle.
-async fn reserve_slots_bias(
-    state: &dyn StateBackendClient,
-    mut n: u32,
-    executors: HashSet<String>,
-) -> error::Result<(Vec<ExecutorReservation>, Vec<(Operation, Keyspace, String)>)> {
-    let mut reservations: Vec<ExecutorReservation> = vec![];
-    let mut txn_ops: Vec<(Operation, Keyspace, String)> = vec![];
-
-    for executor_id in executors {
-        if n == 0 {
-            break;
-        }
-
-        let value = state.get(Keyspace::Slots, &executor_id).await?;
-        let mut data = decode_into::<protobuf::ExecutorData, ExecutorData>(&value)?;
-        let take = std::cmp::min(data.available_task_slots, n);
-
-        for _ in 0..take {
-            reservations.push(ExecutorReservation::new_free(executor_id.clone()));
-            data.available_task_slots -= 1;
-            n -= 1;
-        }
-
-        let proto: protobuf::ExecutorData = data.into();
-        let new_data = encode_protobuf(&proto)?;
-        txn_ops.push((Operation::Put(new_data), Keyspace::Slots, executor_id));
-    }
-
-    Ok((reservations, txn_ops))
-}
-
-/// Create ExecutorReservation in a round robin way to evenly assign tasks to executors
-async fn reserve_slots_round_robin(
-    state: &dyn StateBackendClient,
-    mut n: u32,
-    executors: HashSet<String>,
-) -> error::Result<(Vec<ExecutorReservation>, Vec<(Operation, Keyspace, String)>)> {
-    let mut reservations: Vec<ExecutorReservation> = vec![];
-    let mut txn_ops: Vec<(Operation, Keyspace, String)> = vec![];
-
-    let all_executor_data = state
-        .scan(Keyspace::Slots, None)
-        .await?
-        .into_iter()
-        .map(|(_, data)| decode_into::<protobuf::ExecutorData, ExecutorData>(&data))
-        .collect::<error::Result<Vec<ExecutorData>>>()?;
-
-    let mut available_executor_data: Vec<ExecutorData> = all_executor_data
-        .into_iter()
-        .filter_map(|data| {
-            (data.available_task_slots > 0 && executors.contains(&data.executor_id))
-                .then_some(data)
-        })
-        .collect();
-    available_executor_data
-        .sort_by(|a, b| Ord::cmp(&b.available_task_slots, &a.available_task_slots));
-
-    // Exclusive
-    let mut last_updated_idx = 0usize;
-    loop {
-        let n_before = n;
-        for (idx, data) in available_executor_data.iter_mut().enumerate() {
-            if n == 0 {
-                break;
-            }
-
-            // Since the vector is sorted in descending order,
-            // if finding one executor has not enough slots, the following will have not enough, either
-            if data.available_task_slots == 0 {
-                break;
-            }
-
-            reservations.push(ExecutorReservation::new_free(data.executor_id.clone()));
-            data.available_task_slots -= 1;
-            n -= 1;
-
-            if idx >= last_updated_idx {
-                last_updated_idx = idx + 1;
-            }
-        }
-
-        if n_before == n {
-            break;
-        }
-    }
-
-    for (idx, data) in available_executor_data.into_iter().enumerate() {
-        if idx >= last_updated_idx {
-            break;
-        }
-        let executor_id = data.executor_id.clone();
-        let proto: protobuf::ExecutorData = data.into();
-        let new_data = encode_protobuf(&proto)?;
-        txn_ops.push((Operation::Put(new_data), Keyspace::Slots, executor_id));
-    }
-
-    Ok((reservations, txn_ops))
-}
-
-#[cfg(test)]
-mod tests {
-    use crate::state::backend::cluster::{ClusterState, DefaultClusterState};
-    use crate::state::backend::sled::SledClient;
-
-    use ballista_core::error::Result;
-    use ballista_core::serde::protobuf::{
-        executor_status, ExecutorHeartbeat, ExecutorStatus,
-    };
-
-    use futures::StreamExt;
-
-    use std::sync::Arc;
-
-    #[tokio::test]
-    async fn test_heartbeat_stream() -> Result<()> {
-        let sled = Arc::new(SledClient::try_new_temporary()?);
-
-        let cluster_state: Arc<dyn ClusterState> =
-            Arc::new(DefaultClusterState::new(sled));
-
-        for i in 0..10 {
-            let mut heartbeat_stream = cluster_state.executor_heartbeat_stream().await?;
-
-            cluster_state
-                .save_executor_heartbeat(ExecutorHeartbeat {
-                    executor_id: i.to_string(),
-                    timestamp: 0,
-                    metrics: vec![],
-                    status: Some(ExecutorStatus {
-                        status: Some(executor_status::Status::Active(String::default())),
-                    }),
-                })
-                .await?;
-
-            let received = if let Some(event) = heartbeat_stream.next().await {
-                event.executor_id == i.to_string()
-            } else {
-                false
-            };
-
-            assert!(received, "Did not receive heartbeat for executor {}", i);
-        }
-
-        Ok(())
-    }
-
-    #[tokio::test]
-    async fn test_heartbeats() -> Result<()> {
-        let sled = Arc::new(SledClient::try_new_temporary()?);
-
-        let cluster_state: Arc<dyn ClusterState> =
-            Arc::new(DefaultClusterState::new(sled));
-
-        // Add 10 executor heartbeats
-        for i in 0..10 {
-            cluster_state
-                .save_executor_heartbeat(ExecutorHeartbeat {
-                    executor_id: i.to_string(),
-                    timestamp: i as u64,
-                    metrics: vec![],
-                    status: Some(ExecutorStatus {
-                        status: Some(executor_status::Status::Active(String::default())),
-                    }),
-                })
-                .await?;
-        }
-
-        let heartbeats = cluster_state.executor_heartbeats().await?;
-
-        // Check that all 10 are present in the global view
-        for i in 0..10 {
-            let id = i.to_string();
-            if let Some(hb) = heartbeats.get(&id) {
-                assert_eq!(
-                    hb.executor_id,
-                    i.to_string(),
-                    "Expected heartbeat in map for {}",
-                    i
-                );
-                assert_eq!(
-                    hb.timestamp, i,
-                    "Expected timestamp to be correct for {}",
-                    i
-                );
-            } else {
-                panic!("Expected heartbeat for executor {}", i);
-            }
-        }
-
-        // Send new heartbeat with updated timestamp
-        cluster_state
-            .save_executor_heartbeat(ExecutorHeartbeat {
-                executor_id: "0".to_string(),
-                timestamp: 100,
-                metrics: vec![],
-                status: Some(ExecutorStatus {
-                    status: Some(executor_status::Status::Active(String::default())),
-                }),
-            })
-            .await?;
-
-        let heartbeats = cluster_state.executor_heartbeats().await?;
-
-        if let Some(hb) = heartbeats.get("0") {
-            assert_eq!(hb.executor_id, "0", "Expected heartbeat in map for 0");
-            assert_eq!(hb.timestamp, 100, "Expected timestamp to be updated for 0");
-        }
-
-        for i in 1..10 {
-            let id = i.to_string();
-            if let Some(hb) = heartbeats.get(&id) {
-                assert_eq!(
-                    hb.executor_id,
-                    i.to_string(),
-                    "Expected heartbeat in map for {}",
-                    i
-                );
-                assert_eq!(
-                    hb.timestamp, i,
-                    "Expected timestamp to be correct for {}",
-                    i
-                );
-            } else {
-                panic!("Expected heartbeat for executor {}", i);
-            }
-        }
-
-        Ok(())
-    }
-}
diff --git a/ballista/scheduler/src/state/backend/etcd.rs b/ballista/scheduler/src/state/backend/etcd.rs
deleted file mode 100644
index 5fc83aaa..00000000
--- a/ballista/scheduler/src/state/backend/etcd.rs
+++ /dev/null
@@ -1,348 +0,0 @@
-// 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.
-
-//! Etcd config backend.
-
-use std::collections::HashSet;
-
-use std::task::Poll;
-
-use ballista_core::error::{ballista_error, Result};
-use std::time::Instant;
-
-use etcd_client::{
-    GetOptions, LockOptions, LockResponse, Txn, TxnOp, WatchOptions, WatchStream, Watcher,
-};
-use futures::{Stream, StreamExt};
-use log::{debug, error, warn};
-
-use crate::state::backend::{
-    Keyspace, Lock, Operation, StateBackendClient, Watch, WatchEvent,
-};
-
-/// A [`StateBackendClient`] implementation that uses etcd to save cluster state.
-#[derive(Clone)]
-pub struct EtcdClient {
-    namespace: String,
-    etcd: etcd_client::Client,
-}
-
-impl EtcdClient {
-    pub fn new(namespace: String, etcd: etcd_client::Client) -> Self {
-        Self { namespace, etcd }
-    }
-}
-
-#[tonic::async_trait]
-impl StateBackendClient for EtcdClient {
-    async fn get(&self, keyspace: Keyspace, key: &str) -> Result<Vec<u8>> {
-        let key = format!("/{}/{:?}/{}", self.namespace, keyspace, key);
-
-        Ok(self
-            .etcd
-            .clone()
-            .get(key, None)
-            .await
-            .map_err(|e| ballista_error(&format!("etcd error {:?}", e)))?
-            .kvs()
-            .get(0)
-            .map(|kv| kv.value().to_owned())
-            .unwrap_or_default())
-    }
-
-    async fn get_from_prefix(
-        &self,
-        keyspace: Keyspace,
-        prefix: &str,
-    ) -> Result<Vec<(String, Vec<u8>)>> {
-        let prefix = format!("/{}/{:?}/{}", self.namespace, keyspace, prefix);
-
-        Ok(self
-            .etcd
-            .clone()
-            .get(prefix, Some(GetOptions::new().with_prefix()))
-            .await
-            .map_err(|e| ballista_error(&format!("etcd error {:?}", e)))?
-            .kvs()
-            .iter()
-            .map(|kv| (kv.key_str().unwrap().to_owned(), kv.value().to_owned()))
-            .collect())
-    }
-
-    async fn scan(
-        &self,
-        keyspace: Keyspace,
-        limit: Option<usize>,
-    ) -> Result<Vec<(String, Vec<u8>)>> {
-        let prefix = format!("/{}/{:?}/", self.namespace, keyspace);
-
-        let options = if let Some(limit) = limit {
-            GetOptions::new().with_prefix().with_limit(limit as i64)
-        } else {
-            GetOptions::new().with_prefix()
-        };
-
-        Ok(self
-            .etcd
-            .clone()
-            .get(prefix, Some(options))
-            .await
-            .map_err(|e| ballista_error(&format!("etcd error {:?}", e)))?
-            .kvs()
-            .iter()
-            .map(|kv| (kv.key_str().unwrap().to_owned(), kv.value().to_owned()))
-            .collect())
-    }
-
-    async fn scan_keys(&self, keyspace: Keyspace) -> Result<HashSet<String>> {
-        let prefix = format!("/{}/{:?}/", self.namespace, keyspace);
-
-        let options = GetOptions::new().with_prefix().with_keys_only();
-
-        Ok(self
-            .etcd
-            .clone()
-            .get(prefix.clone(), Some(options))
-            .await
-            .map_err(|e| ballista_error(&format!("etcd error {:?}", e)))?
-            .kvs()
-            .iter()
-            .map(|kv| {
-                kv.key_str()
-                    .unwrap()
-                    .strip_prefix(&prefix)
-                    .unwrap()
-                    .to_owned()
-            })
-            .collect())
-    }
-
-    async fn put(&self, keyspace: Keyspace, key: String, value: Vec<u8>) -> Result<()> {
-        let key = format!("/{}/{:?}/{}", self.namespace, keyspace, key);
-
-        let mut etcd = self.etcd.clone();
-        etcd.put(key, value.clone(), None)
-            .await
-            .map_err(|e| {
-                warn!("etcd put failed: {}", e);
-                ballista_error(&format!("etcd put failed: {}", e))
-            })
-            .map(|_| ())
-    }
-
-    /// Apply multiple operations in a single transaction.
-    async fn apply_txn(&self, ops: Vec<(Operation, Keyspace, String)>) -> Result<()> {
-        let mut etcd = self.etcd.clone();
-
-        let txn_ops: Vec<TxnOp> = ops
-            .into_iter()
-            .map(|(operation, ks, key)| {
-                let key = format!("/{}/{:?}/{}", self.namespace, ks, key);
-                match operation {
-                    Operation::Put(value) => TxnOp::put(key, value, None),
-                    Operation::Delete => TxnOp::delete(key, None),
-                }
-            })
-            .collect();
-
-        etcd.txn(Txn::new().and_then(txn_ops))
-            .await
-            .map_err(|e| {
-                error!("etcd operation failed: {}", e);
-                ballista_error(&format!("etcd operation failed: {}", e))
-            })
-            .map(|_| ())
-    }
-
-    async fn mv(
-        &self,
-        from_keyspace: Keyspace,
-        to_keyspace: Keyspace,
-        key: &str,
-    ) -> Result<()> {
-        let mut etcd = self.etcd.clone();
-        let from_key = format!("/{}/{:?}/{}", self.namespace, from_keyspace, key);
-        let to_key = format!("/{}/{:?}/{}", self.namespace, to_keyspace, key);
-
-        let current_value = etcd
-            .get(from_key.as_str(), None)
-            .await
-            .map_err(|e| ballista_error(&format!("etcd error {:?}", e)))?
-            .kvs()
-            .get(0)
-            .map(|kv| kv.value().to_owned());
-
-        if let Some(value) = current_value {
-            let txn = Txn::new().and_then(vec![
-                TxnOp::delete(from_key.as_str(), None),
-                TxnOp::put(to_key.as_str(), value, None),
-            ]);
-            etcd.txn(txn).await.map_err(|e| {
-                error!("etcd put failed: {}", e);
-                ballista_error("etcd move failed")
-            })?;
-        } else {
-            warn!("Cannot move value at {}, does not exist", from_key);
-        }
-
-        Ok(())
-    }
-
-    async fn lock(&self, keyspace: Keyspace, key: &str) -> Result<Box<dyn Lock>> {
-        let start = Instant::now();
-        let mut etcd = self.etcd.clone();
-
-        let lock_id = format!("/{}/mutex/{:?}/{}", self.namespace, keyspace, key);
-
-        // Create a lease which expires after 30 seconds. We then associate this lease with the lock
-        // acquired below. This protects against a scheduler dying unexpectedly while holding locks
-        // on shared resources. In that case, those locks would expire once the lease expires.
-        // TODO This is not great to do for every lock. We should have a single lease per scheduler instance
-        let lease_id = etcd
-            .lease_client()
-            .grant(30, None)
-            .await
-            .map_err(|e| {
-                warn!("etcd lease failed: {}", e);
-                ballista_error("etcd lease failed")
-            })?
-            .id();
-
-        let lock_options = LockOptions::new().with_lease(lease_id);
-
-        let lock = etcd
-            .lock(lock_id.as_str(), Some(lock_options))
-            .await
-            .map_err(|e| {
-                warn!("etcd lock failed: {}", e);
-                ballista_error("etcd lock failed")
-            })?;
-
-        let elapsed = start.elapsed();
-        debug!("Acquired lock {} in {:?}", lock_id, elapsed);
-        Ok(Box::new(EtcdLockGuard { etcd, lock }))
-    }
-
-    async fn watch(&self, keyspace: Keyspace, prefix: String) -> Result<Box<dyn Watch>> {
-        let prefix = format!("/{}/{:?}/{}", self.namespace, keyspace, prefix);
-
-        let mut etcd = self.etcd.clone();
-        let options = WatchOptions::new().with_prefix();
-        let (watcher, stream) = etcd.watch(prefix, Some(options)).await.map_err(|e| {
-            warn!("etcd watch failed: {}", e);
-            ballista_error("etcd watch failed")
-        })?;
-        Ok(Box::new(EtcdWatch {
-            watcher,
-            stream,
-            buffered_events: Vec::new(),
-        }))
-    }
-
-    async fn delete(&self, keyspace: Keyspace, key: &str) -> Result<()> {
-        let key = format!("/{}/{:?}/{}", self.namespace, keyspace, key);
-
-        let mut etcd = self.etcd.clone();
-
-        etcd.delete(key, None).await.map_err(|e| {
-            warn!("etcd delete failed: {:?}", e);
-            ballista_error("etcd delete failed")
-        })?;
-
-        Ok(())
-    }
-}
-
-struct EtcdWatch {
-    watcher: Watcher,
-    stream: WatchStream,
-    buffered_events: Vec<WatchEvent>,
-}
-
-#[tonic::async_trait]
-impl Watch for EtcdWatch {
-    async fn cancel(&mut self) -> Result<()> {
-        self.watcher.cancel().await.map_err(|e| {
-            warn!("etcd watch cancel failed: {}", e);
-            ballista_error("etcd watch cancel failed")
-        })
-    }
-}
-
-impl Stream for EtcdWatch {
-    type Item = WatchEvent;
-
-    fn poll_next(
-        self: std::pin::Pin<&mut Self>,
-        cx: &mut std::task::Context<'_>,
-    ) -> Poll<Option<Self::Item>> {
-        let self_mut = self.get_mut();
-        if let Some(event) = self_mut.buffered_events.pop() {
-            Poll::Ready(Some(event))
-        } else {
-            loop {
-                match self_mut.stream.poll_next_unpin(cx) {
-                    Poll::Ready(Some(Err(e))) => {
-                        warn!("Error when watching etcd prefix: {}", e);
-                        continue;
-                    }
-                    Poll::Ready(Some(Ok(v))) => {
-                        self_mut.buffered_events.extend(v.events().iter().map(|ev| {
-                            match ev.event_type() {
-                                etcd_client::EventType::Put => {
-                                    let kv = ev.kv().unwrap();
-                                    WatchEvent::Put(
-                                        kv.key_str().unwrap().to_string(),
-                                        kv.value().to_owned(),
-                                    )
-                                }
-                                etcd_client::EventType::Delete => {
-                                    let kv = ev.kv().unwrap();
-                                    WatchEvent::Delete(kv.key_str().unwrap().to_string())
-                                }
-                            }
-                        }));
-                        if let Some(event) = self_mut.buffered_events.pop() {
-                            return Poll::Ready(Some(event));
-                        } else {
-                            continue;
-                        }
-                    }
-                    Poll::Ready(None) => return Poll::Ready(None),
-                    Poll::Pending => return Poll::Pending,
-                }
-            }
-        }
-    }
-
-    fn size_hint(&self) -> (usize, Option<usize>) {
-        self.stream.size_hint()
-    }
-}
-
-struct EtcdLockGuard {
-    etcd: etcd_client::Client,
-    lock: LockResponse,
-}
-
-// Cannot use Drop because we need this to be async
-#[tonic::async_trait]
-impl Lock for EtcdLockGuard {
-    async fn unlock(&mut self) {
-        self.etcd.unlock(self.lock.key()).await.unwrap();
-    }
-}
diff --git a/ballista/scheduler/src/state/backend/memory.rs b/ballista/scheduler/src/state/backend/memory.rs
deleted file mode 100644
index 6cbedb84..00000000
--- a/ballista/scheduler/src/state/backend/memory.rs
+++ /dev/null
@@ -1,411 +0,0 @@
-// 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.
-
-use crate::state::backend::utils::subscriber::{Subscriber, Subscribers};
-use crate::state::backend::{
-    Keyspace, Lock, Operation, StateBackendClient, Watch, WatchEvent,
-};
-use ballista_core::error::Result;
-use dashmap::DashMap;
-use futures::{FutureExt, Stream};
-use log::warn;
-use std::collections::{BTreeMap, HashSet};
-use std::sync::Arc;
-use tokio::sync::Mutex;
-
-type KeySpaceState = BTreeMap<String, Vec<u8>>;
-type KeyLock = Arc<Mutex<()>>;
-
-/// A [`StateBackendClient`] implementation that uses in memory map to save cluster state.
-#[derive(Clone, Default)]
-pub struct MemoryBackendClient {
-    /// The key is the KeySpace. For every KeySpace, there will be a tree map which is better for prefix filtering
-    states: DashMap<String, KeySpaceState>,
-    /// The key is the full key formatted like "/KeySpace/key". It's a flatted map
-    locks: DashMap<String, KeyLock>,
-    subscribers: Arc<Subscribers>,
-}
-
-impl MemoryBackendClient {
-    pub fn new() -> Self {
-        Self::default()
-    }
-
-    fn get_space_key(keyspace: &Keyspace) -> String {
-        format!("/{:?}", keyspace)
-    }
-
-    fn get_flat_key(keyspace: &Keyspace, key: &str) -> String {
-        format!("/{:?}/{}", keyspace, key)
-    }
-}
-
-#[tonic::async_trait]
-impl StateBackendClient for MemoryBackendClient {
-    async fn get(&self, keyspace: Keyspace, key: &str) -> Result<Vec<u8>> {
-        let space_key = Self::get_space_key(&keyspace);
-        Ok(self
-            .states
-            .get(&space_key)
-            .map(|space_state| space_state.value().get(key).cloned().unwrap_or_default())
-            .unwrap_or_default())
-    }
-
-    async fn get_from_prefix(
-        &self,
-        keyspace: Keyspace,
-        prefix: &str,
-    ) -> Result<Vec<(String, Vec<u8>)>> {
-        let space_key = Self::get_space_key(&keyspace);
-        Ok(self
-            .states
-            .get(&space_key)
-            .map(|space_state| {
-                space_state
-                    .value()
-                    .range(prefix.to_owned()..)
-                    .take_while(|(k, _)| k.starts_with(prefix))
-                    .map(|e| (format!("{}/{}", space_key, e.0), e.1.clone()))
-                    .collect()
-            })
-            .unwrap_or_default())
-    }
-
-    async fn scan(
-        &self,
-        keyspace: Keyspace,
-        limit: Option<usize>,
-    ) -> Result<Vec<(String, Vec<u8>)>> {
-        let space_key = Self::get_space_key(&keyspace);
-        Ok(self
-            .states
-            .get(&space_key)
-            .map(|space_state| {
-                if let Some(limit) = limit {
-                    space_state
-                        .value()
-                        .iter()
-                        .take(limit)
-                        .map(|e| (format!("{}/{}", space_key, e.0), e.1.clone()))
-                        .collect::<Vec<(String, Vec<u8>)>>()
-                } else {
-                    space_state
-                        .value()
-                        .iter()
-                        .map(|e| (format!("{}/{}", space_key, e.0), e.1.clone()))
-                        .collect::<Vec<(String, Vec<u8>)>>()
-                }
-            })
-            .unwrap_or_default())
-    }
-
-    async fn scan_keys(&self, keyspace: Keyspace) -> Result<HashSet<String>> {
-        let space_key = Self::get_space_key(&keyspace);
-        Ok(self
-            .states
-            .get(&space_key)
-            .map(|space_state| {
-                space_state
-                    .value()
-                    .iter()
-                    .map(|e| format!("{}/{}", space_key, e.0))
-                    .collect::<HashSet<String>>()
-            })
-            .unwrap_or_default())
-    }
-
-    async fn put(&self, keyspace: Keyspace, key: String, value: Vec<u8>) -> Result<()> {
-        let space_key = Self::get_space_key(&keyspace);
-        if !self.states.contains_key(&space_key) {
-            self.states.insert(space_key.clone(), BTreeMap::default());
-        }
-        self.states
-            .get_mut(&space_key)
-            .unwrap()
-            .value_mut()
-            .insert(key.clone(), value.clone());
-
-        // Notify subscribers
-        let full_key = format!("{}/{}", space_key, key);
-        if let Some(res) = self.subscribers.reserve(&full_key) {
-            let event = WatchEvent::Put(full_key, value);
-            res.complete(&event);
-        }
-
-        Ok(())
-    }
-
-    /// Currently the locks should be acquired before invoking this method.
-    /// Later need to be refined by acquiring all of the related locks inside this method
-    async fn apply_txn(&self, ops: Vec<(Operation, Keyspace, String)>) -> Result<()> {
-        for (op, keyspace, key) in ops.into_iter() {
-            match op {
-                Operation::Delete => {
-                    self.delete(keyspace, &key).await?;
-                }
-                Operation::Put(value) => {
-                    self.put(keyspace, key, value).await?;
-                }
-            };
-        }
-
-        Ok(())
-    }
-
-    /// Currently it's not used. Later will refine the caller side by leveraging this method
-    async fn mv(
-        &self,
-        from_keyspace: Keyspace,
-        to_keyspace: Keyspace,
-        key: &str,
-    ) -> Result<()> {
-        let from_space_key = Self::get_space_key(&from_keyspace);
-
-        let ops = if let Some(from_space_state) = self.states.get(&from_space_key) {
-            if let Some(state) = from_space_state.value().get(key) {
-                Some(vec![
-                    (Operation::Delete, from_keyspace, key.to_owned()),
-                    (Operation::Put(state.clone()), to_keyspace, key.to_owned()),
-                ])
-            } else {
-                // TODO should this return an error?
-                warn!(
-                    "Cannot move value at {}/{}, does not exist",
-                    from_space_key, key
-                );
-                None
-            }
-        } else {
-            // TODO should this return an error?
-            warn!(
-                "Cannot move value at {}/{}, does not exist",
-                from_space_key, key
-            );
-            None
-        };
-
-        if let Some(ops) = ops {
-            self.apply_txn(ops).await?;
-        }
-
-        Ok(())
-    }
-
-    async fn lock(&self, keyspace: Keyspace, key: &str) -> Result<Box<dyn Lock>> {
-        let flat_key = Self::get_flat_key(&keyspace, key);
-        let lock = self
-            .locks
-            .entry(flat_key)
-            .or_insert_with(|| Arc::new(Mutex::new(())));
-        Ok(Box::new(lock.value().clone().lock_owned().await))
-    }
-
-    async fn watch(&self, keyspace: Keyspace, prefix: String) -> Result<Box<dyn Watch>> {
-        let prefix = format!("/{:?}/{}", keyspace, prefix);
-
-        Ok(Box::new(MemoryWatch {
-            subscriber: self.subscribers.register(prefix.as_bytes()),
-        }))
-    }
-
-    async fn delete(&self, keyspace: Keyspace, key: &str) -> Result<()> {
-        let space_key = Self::get_space_key(&keyspace);
-        if let Some(mut space_state) = self.states.get_mut(&space_key) {
-            if space_state.value_mut().remove(key).is_some() {
-                // Notify subscribers
-                let full_key = format!("{}/{}", space_key, key);
-                if let Some(res) = self.subscribers.reserve(&full_key) {
-                    let event = WatchEvent::Delete(full_key);
-                    res.complete(&event);
-                }
-            }
-        }
-
-        Ok(())
-    }
-}
-
-struct MemoryWatch {
-    subscriber: Subscriber,
-}
-
-#[tonic::async_trait]
-impl Watch for MemoryWatch {
-    async fn cancel(&mut self) -> Result<()> {
-        Ok(())
-    }
-}
-
-impl Stream for MemoryWatch {
-    type Item = WatchEvent;
-
-    fn poll_next(
-        self: std::pin::Pin<&mut Self>,
-        cx: &mut std::task::Context<'_>,
-    ) -> std::task::Poll<Option<Self::Item>> {
-        self.get_mut().subscriber.poll_unpin(cx)
-    }
-
-    fn size_hint(&self) -> (usize, Option<usize>) {
-        self.subscriber.size_hint()
-    }
-}
-
-#[cfg(test)]
-mod tests {
-    use super::{StateBackendClient, Watch, WatchEvent};
-
-    use crate::state::backend::memory::MemoryBackendClient;
-    use crate::state::backend::{Keyspace, Operation};
-    use crate::state::with_locks;
-    use futures::StreamExt;
-    use std::result::Result;
-
-    #[tokio::test]
-    async fn put_read() -> Result<(), Box<dyn std::error::Error>> {
-        let client = MemoryBackendClient::new();
-        let key = "key";
-        let value = "value".as_bytes();
-        client
-            .put(Keyspace::Slots, key.to_owned(), value.to_vec())
-            .await?;
-        assert_eq!(client.get(Keyspace::Slots, key).await?, value);
-        Ok(())
-    }
-
-    #[tokio::test]
-    async fn put_move() -> Result<(), Box<dyn std::error::Error>> {
-        let client = MemoryBackendClient::new();
-        let key = "key";
-        let value = "value".as_bytes();
-        client
-            .put(Keyspace::ActiveJobs, key.to_owned(), value.to_vec())
-            .await?;
-        client
-            .mv(Keyspace::ActiveJobs, Keyspace::FailedJobs, key)
-            .await?;
-        assert_eq!(client.get(Keyspace::FailedJobs, key).await?, value);
-        Ok(())
-    }
-
-    #[tokio::test]
-    async fn multiple_operation() -> Result<(), Box<dyn std::error::Error>> {
-        let client = MemoryBackendClient::new();
-        let key = "key".to_string();
-        let value = "value".as_bytes().to_vec();
-        let locks = client
-            .acquire_locks(vec![(Keyspace::ActiveJobs, ""), (Keyspace::Slots, "")])
-            .await?;
-
-        let _r: ballista_core::error::Result<()> = with_locks(locks, async {
-            let txn_ops = vec![
-                (Operation::Put(value.clone()), Keyspace::Slots, key.clone()),
-                (
-                    Operation::Put(value.clone()),
-                    Keyspace::ActiveJobs,
-                    key.clone(),
-                ),
-            ];
-            client.apply_txn(txn_ops).await?;
-            Ok(())
-        })
-        .await;
-
-        assert_eq!(client.get(Keyspace::Slots, key.as_str()).await?, value);
-        assert_eq!(client.get(Keyspace::ActiveJobs, key.as_str()).await?, value);
-        Ok(())
-    }
-
-    #[tokio::test]
-    async fn read_empty() -> Result<(), Box<dyn std::error::Error>> {
-        let client = MemoryBackendClient::new();
-        let key = "key";
-        let empty: &[u8] = &[];
-        assert_eq!(client.get(Keyspace::Slots, key).await?, empty);
-        Ok(())
-    }
-
-    #[tokio::test]
-    async fn read_prefix() -> Result<(), Box<dyn std::error::Error>> {
-        let client = MemoryBackendClient::new();
-        let key = "key";
-        let value = "value".as_bytes();
-        client
-            .put(Keyspace::Slots, format!("{}/1", key), value.to_vec())
-            .await?;
-        client
-            .put(Keyspace::Slots, format!("{}/2", key), value.to_vec())
-            .await?;
-        assert_eq!(
-            client.get_from_prefix(Keyspace::Slots, key).await?,
-            vec![
-                ("/Slots/key/1".to_owned(), value.to_vec()),
-                ("/Slots/key/2".to_owned(), value.to_vec())
-            ]
-        );
-        Ok(())
-    }
-
-    #[tokio::test]
-    async fn read_watch() -> Result<(), Box<dyn std::error::Error>> {
-        let client = MemoryBackendClient::new();
-        let key = "key";
-        let value = "value".as_bytes();
-        let mut watch_keyspace: Box<dyn Watch> =
-            client.watch(Keyspace::Slots, "".to_owned()).await?;
-        let mut watch_key: Box<dyn Watch> =
-            client.watch(Keyspace::Slots, key.to_owned()).await?;
-        client
-            .put(Keyspace::Slots, key.to_owned(), value.to_vec())
-            .await?;
-        assert_eq!(
-            watch_keyspace.next().await,
-            Some(WatchEvent::Put(
-                format!("/{:?}/{}", Keyspace::Slots, key.to_owned()),
-                value.to_owned()
-            ))
-        );
-        assert_eq!(
-            watch_key.next().await,
-            Some(WatchEvent::Put(
-                format!("/{:?}/{}", Keyspace::Slots, key.to_owned()),
-                value.to_owned()
-            ))
-        );
-        let value2 = "value2".as_bytes();
-        client
-            .put(Keyspace::Slots, key.to_owned(), value2.to_vec())
-            .await?;
-        assert_eq!(
-            watch_keyspace.next().await,
-            Some(WatchEvent::Put(
-                format!("/{:?}/{}", Keyspace::Slots, key.to_owned()),
-                value2.to_owned()
-            ))
-        );
-        assert_eq!(
-            watch_key.next().await,
-            Some(WatchEvent::Put(
-                format!("/{:?}/{}", Keyspace::Slots, key.to_owned()),
-                value2.to_owned()
-            ))
-        );
-        watch_keyspace.cancel().await?;
-        watch_key.cancel().await?;
-        Ok(())
-    }
-}
diff --git a/ballista/scheduler/src/state/backend/mod.rs b/ballista/scheduler/src/state/backend/mod.rs
deleted file mode 100644
index 5c859937..00000000
--- a/ballista/scheduler/src/state/backend/mod.rs
+++ /dev/null
@@ -1,169 +0,0 @@
-// 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.
-
-use ballista_core::error::Result;
-use clap::ArgEnum;
-use futures::{future, Stream};
-use std::collections::HashSet;
-use std::fmt;
-use tokio::sync::OwnedMutexGuard;
-
-pub mod cluster;
-#[cfg(feature = "etcd")]
-pub mod etcd;
-pub mod memory;
-#[cfg(feature = "sled")]
-pub mod sled;
-mod utils;
-
-// an enum used to configure the backend
-// needs to be visible to code generated by configure_me
-#[derive(Debug, Clone, ArgEnum, serde::Deserialize, PartialEq, Eq)]
-pub enum StateBackend {
-    Etcd,
-    Memory,
-    Sled,
-}
-
-impl std::str::FromStr for StateBackend {
-    type Err = String;
-
-    fn from_str(s: &str) -> std::result::Result<Self, Self::Err> {
-        ArgEnum::from_str(s, true)
-    }
-}
-
-impl parse_arg::ParseArgFromStr for StateBackend {
-    fn describe_type<W: fmt::Write>(mut writer: W) -> fmt::Result {
-        write!(writer, "The configuration backend for the scheduler")
-    }
-}
-
-#[derive(Debug, Clone, Eq, PartialEq, Hash)]
-pub enum Keyspace {
-    Executors,
-    ActiveJobs,
-    CompletedJobs,
-    FailedJobs,
-    Slots,
-    Sessions,
-    Heartbeats,
-}
-
-#[derive(Debug, Eq, PartialEq, Hash)]
-pub enum Operation {
-    Put(Vec<u8>),
-    Delete,
-}
-
-/// A trait that contains the necessary methods to save and retrieve the state and configuration of a cluster.
-#[tonic::async_trait]
-pub trait StateBackendClient: Send + Sync {
-    /// Retrieve the data associated with a specific key in a given keyspace.
-    ///
-    /// An empty vec is returned if the key does not exist.
-    async fn get(&self, keyspace: Keyspace, key: &str) -> Result<Vec<u8>>;
-
-    /// Retrieve all key/value pairs in given keyspace matching a given key prefix.
-    async fn get_from_prefix(
-        &self,
-        keyspace: Keyspace,
-        prefix: &str,
-    ) -> Result<Vec<(String, Vec<u8>)>>;
-
-    /// Retrieve all key/value pairs in a given keyspace. If a limit is specified, will return at
-    /// most `limit` key-value pairs.
-    async fn scan(
-        &self,
-        keyspace: Keyspace,
-        limit: Option<usize>,
-    ) -> Result<Vec<(String, Vec<u8>)>>;
-
-    /// Retrieve all keys from a given keyspace (without their values). The implementations
-    /// should handle stripping any prefixes it may add.
-    async fn scan_keys(&self, keyspace: Keyspace) -> Result<HashSet<String>>;
-
-    /// Saves the value into the provided key, overriding any previous data that might have been associated to that key.
-    async fn put(&self, keyspace: Keyspace, key: String, value: Vec<u8>) -> Result<()>;
-
-    /// Bundle multiple operation in a single transaction. Either all values should be saved, or all should fail.
-    /// It can support multiple types of operations and keyspaces. If the count of the unique keyspace is more than one,
-    /// more than one locks has to be acquired.
-    async fn apply_txn(&self, ops: Vec<(Operation, Keyspace, String)>) -> Result<()>;
-    /// Acquire mutex with specified IDs.
-    async fn acquire_locks(
-        &self,
-        mut ids: Vec<(Keyspace, &str)>,
-    ) -> Result<Vec<Box<dyn Lock>>> {
-        // We always acquire locks in a specific order to avoid deadlocks.
-        ids.sort_by_key(|n| format!("/{:?}/{}", n.0, n.1));
-        future::try_join_all(ids.into_iter().map(|(ks, key)| self.lock(ks, key))).await
-    }
-
-    /// Atomically move the given key from one keyspace to another
-    async fn mv(
-        &self,
-        from_keyspace: Keyspace,
-        to_keyspace: Keyspace,
-        key: &str,
-    ) -> Result<()>;
-
-    /// Acquire mutex with specified ID.
-    async fn lock(&self, keyspace: Keyspace, key: &str) -> Result<Box<dyn Lock>>;
-
-    /// Watch all events that happen on a specific prefix.
-    async fn watch(&self, keyspace: Keyspace, prefix: String) -> Result<Box<dyn Watch>>;
-
-    /// Permanently delete a key from state
-    async fn delete(&self, keyspace: Keyspace, key: &str) -> Result<()>;
-}
-
-/// Method of distributing tasks to available executor slots
-#[derive(Debug, Clone, Copy)]
-pub enum TaskDistribution {
-    /// Eagerly assign tasks to executor slots. This will assign as many task slots per executor
-    /// as are currently available
-    Bias,
-    /// Distributed tasks evenely across executors. This will try and iterate through available executors
-    /// and assign one task to each executor until all tasks are assigned.
-    RoundRobin,
-}
-
-/// A Watch is a cancelable stream of put or delete events in the [StateBackendClient]
-#[tonic::async_trait]
-pub trait Watch: Stream<Item = WatchEvent> + Send + Unpin {
-    async fn cancel(&mut self) -> Result<()>;
-}
-
-#[derive(Clone, Debug, Eq, PartialEq)]
-pub enum WatchEvent {
-    /// Contains the inserted or updated key and the new value
-    Put(String, Vec<u8>),
-
-    /// Contains the deleted key
-    Delete(String),
-}
-
-#[tonic::async_trait]
-pub trait Lock: Send + Sync {
-    async fn unlock(&mut self);
-}
-
-#[tonic::async_trait]
-impl<T: Send + Sync> Lock for OwnedMutexGuard<T> {
-    async fn unlock(&mut self) {}
-}
diff --git a/ballista/scheduler/src/state/backend/sled.rs b/ballista/scheduler/src/state/backend/sled.rs
deleted file mode 100644
index e42da4ca..00000000
--- a/ballista/scheduler/src/state/backend/sled.rs
+++ /dev/null
@@ -1,397 +0,0 @@
-// 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.
-
-use std::collections::{HashMap, HashSet};
-use std::{sync::Arc, task::Poll};
-
-use ballista_core::error::{ballista_error, BallistaError, Result};
-
-use futures::{FutureExt, Stream};
-use log::warn;
-use sled_package as sled;
-use tokio::sync::Mutex;
-
-use crate::state::backend::{
-    Keyspace, Lock, Operation, StateBackendClient, Watch, WatchEvent,
-};
-
-/// A [`StateBackendClient`] implementation that uses file-based storage to save cluster state.
-#[derive(Clone)]
-pub struct SledClient {
-    db: sled::Db,
-    locks: Arc<Mutex<HashMap<String, Arc<Mutex<()>>>>>,
-}
-
-impl SledClient {
-    /// Creates a SledClient that saves data to the specified file.
-    pub fn try_new<P: AsRef<std::path::Path>>(path: P) -> Result<Self> {
-        Ok(Self {
-            db: sled::open(path).map_err(sled_to_ballista_error)?,
-            locks: Arc::new(Mutex::new(HashMap::new())),
-        })
-    }
-
-    /// Creates a SledClient that saves data to a temp file.
-    pub fn try_new_temporary() -> Result<Self> {
-        Ok(Self {
-            db: sled::Config::new()
-                .temporary(true)
-                .open()
-                .map_err(sled_to_ballista_error)?,
-            locks: Arc::new(Mutex::new(HashMap::new())),
-        })
-    }
-}
-
-fn sled_to_ballista_error(e: sled::Error) -> BallistaError {
-    match e {
-        sled::Error::Io(io) => BallistaError::IoError(io),
-        _ => BallistaError::General(format!("{}", e)),
-    }
-}
-
-#[tonic::async_trait]
-impl StateBackendClient for SledClient {
-    async fn get(&self, keyspace: Keyspace, key: &str) -> Result<Vec<u8>> {
-        let key = format!("/{:?}/{}", keyspace, key);
-        Ok(self
-            .db
-            .get(key)
-            .map_err(|e| ballista_error(&format!("sled error {:?}", e)))?
-            .map(|v| v.to_vec())
-            .unwrap_or_default())
-    }
-
-    async fn get_from_prefix(
-        &self,
-        keyspace: Keyspace,
-        prefix: &str,
-    ) -> Result<Vec<(String, Vec<u8>)>> {
-        let prefix = format!("/{:?}/{}", keyspace, prefix);
-        Ok(self
-            .db
-            .scan_prefix(prefix)
-            .map(|v| {
-                v.map(|(key, value)| {
-                    (
-                        std::str::from_utf8(&key).unwrap().to_owned(),
-                        value.to_vec(),
-                    )
-                })
-            })
-            .collect::<std::result::Result<Vec<_>, _>>()
-            .map_err(|e| ballista_error(&format!("sled error {:?}", e)))?)
-    }
-
-    async fn scan(
-        &self,
-        keyspace: Keyspace,
-        limit: Option<usize>,
-    ) -> Result<Vec<(String, Vec<u8>)>> {
-        let prefix = format!("/{:?}/", keyspace);
-        if let Some(limit) = limit {
-            Ok(self
-                .db
-                .scan_prefix(prefix)
-                .take(limit)
-                .map(|v| {
-                    v.map(|(key, value)| {
-                        (
-                            std::str::from_utf8(&key).unwrap().to_owned(),
-                            value.to_vec(),
-                        )
-                    })
-                })
-                .collect::<std::result::Result<Vec<_>, _>>()
-                .map_err(|e| ballista_error(&format!("sled error {:?}", e)))?)
-        } else {
-            Ok(self
-                .db
-                .scan_prefix(prefix)
-                .map(|v| {
-                    v.map(|(key, value)| {
-                        (
-                            std::str::from_utf8(&key).unwrap().to_owned(),
-                            value.to_vec(),
-                        )
-                    })
-                })
-                .collect::<std::result::Result<Vec<_>, _>>()
-                .map_err(|e| ballista_error(&format!("sled error {:?}", e)))?)
-        }
-    }
-
-    async fn scan_keys(&self, keyspace: Keyspace) -> Result<HashSet<String>> {
-        let prefix = format!("/{:?}/", keyspace);
-        Ok(self
-            .db
-            .scan_prefix(prefix.clone())
-            .map(|v| {
-                v.map(|(key, _value)| {
-                    std::str::from_utf8(&key)
-                        .unwrap()
-                        .strip_prefix(&prefix)
-                        .unwrap()
-                        .to_owned()
-                })
-            })
-            .collect::<std::result::Result<HashSet<_>, _>>()
-            .map_err(|e| ballista_error(&format!("sled error {:?}", e)))?)
-    }
-
-    async fn put(&self, keyspace: Keyspace, key: String, value: Vec<u8>) -> Result<()> {
-        let key = format!("/{:?}/{}", keyspace, key);
-        self.db
-            .insert(key, value)
-            .map_err(|e| {
-                warn!("sled insert failed: {}", e);
-                ballista_error("sled insert failed")
-            })
-            .map(|_| ())
-    }
-
-    async fn apply_txn(&self, ops: Vec<(Operation, Keyspace, String)>) -> Result<()> {
-        let mut batch = sled::Batch::default();
-
-        for (op, keyspace, key_str) in ops {
-            let key = format!("/{:?}/{}", &keyspace, key_str);
-            match op {
-                Operation::Put(value) => batch.insert(key.as_str(), value),
-                Operation::Delete => batch.remove(key.as_str()),
-            }
-        }
-
-        self.db.apply_batch(batch).map_err(|e| {
-            warn!("sled transaction insert failed: {}", e);
-            ballista_error("sled operations failed")
-        })
-    }
-
-    async fn mv(
-        &self,
-        from_keyspace: Keyspace,
-        to_keyspace: Keyspace,
-        key: &str,
-    ) -> Result<()> {
-        let from_key = format!("/{:?}/{}", from_keyspace, key);
-        let to_key = format!("/{:?}/{}", to_keyspace, key);
-
-        let current_value = self
-            .db
-            .get(from_key.as_str())
-            .map_err(|e| ballista_error(&format!("sled error {:?}", e)))?
-            .map(|v| v.to_vec());
-
-        if let Some(value) = current_value {
-            let mut batch = sled::Batch::default();
-
-            batch.remove(from_key.as_str());
-            batch.insert(to_key.as_str(), value);
-
-            self.db.apply_batch(batch).map_err(|e| {
-                warn!("sled transaction insert failed: {}", e);
-                ballista_error("sled insert failed")
-            })
-        } else {
-            // TODO should this return an error?
-            warn!("Cannot move value at {}, does not exist", from_key);
-            Ok(())
-        }
-    }
-
-    async fn lock(&self, keyspace: Keyspace, key: &str) -> Result<Box<dyn Lock>> {
-        let mut mlock = self.locks.lock().await;
-        let lock_key = format!("/{:?}/{}", keyspace, key);
-        if let Some(lock) = mlock.get(&lock_key) {
-            Ok(Box::new(lock.clone().lock_owned().await))
-        } else {
-            let new_lock = Arc::new(Mutex::new(()));
-            mlock.insert(lock_key, new_lock.clone());
-            Ok(Box::new(new_lock.lock_owned().await))
-        }
-    }
-
-    async fn watch(&self, keyspace: Keyspace, prefix: String) -> Result<Box<dyn Watch>> {
-        let prefix = format!("/{:?}/{}", keyspace, prefix);
-
-        Ok(Box::new(SledWatch {
-            subscriber: self.db.watch_prefix(prefix),
-        }))
-    }
-
-    async fn delete(&self, keyspace: Keyspace, key: &str) -> Result<()> {
-        let key = format!("/{:?}/{}", keyspace, key);
-        self.db.remove(key).map_err(|e| {
-            warn!("sled delete failed: {:?}", e);
-            ballista_error("sled delete failed")
-        })?;
-        Ok(())
-    }
-}
-
-struct SledWatch {
-    subscriber: sled::Subscriber,
-}
-
-#[tonic::async_trait]
-impl Watch for SledWatch {
-    async fn cancel(&mut self) -> Result<()> {
-        Ok(())
-    }
-}
-
-impl Stream for SledWatch {
-    type Item = WatchEvent;
-
-    fn poll_next(
-        self: std::pin::Pin<&mut Self>,
-        cx: &mut std::task::Context<'_>,
-    ) -> std::task::Poll<Option<Self::Item>> {
-        match self.get_mut().subscriber.poll_unpin(cx) {
-            Poll::Pending => Poll::Pending,
-            Poll::Ready(None) => Poll::Ready(None),
-            Poll::Ready(Some(sled::Event::Insert { key, value })) => {
-                let key = std::str::from_utf8(&key).unwrap().to_owned();
-                Poll::Ready(Some(WatchEvent::Put(key, value.to_vec())))
-            }
-            Poll::Ready(Some(sled::Event::Remove { key })) => {
-                let key = std::str::from_utf8(&key).unwrap().to_owned();
-                Poll::Ready(Some(WatchEvent::Delete(key)))
-            }
-        }
-    }
-
-    fn size_hint(&self) -> (usize, Option<usize>) {
-        self.subscriber.size_hint()
-    }
-}
-
-#[cfg(test)]
-mod tests {
-    use super::{SledClient, StateBackendClient, Watch, WatchEvent};
-
-    use crate::state::backend::{Keyspace, Operation};
-    use crate::state::with_locks;
-    use futures::StreamExt;
-    use std::result::Result;
-
-    fn create_instance() -> Result<SledClient, Box<dyn std::error::Error>> {
-        Ok(SledClient::try_new_temporary()?)
-    }
-
-    #[tokio::test]
-    async fn put_read() -> Result<(), Box<dyn std::error::Error>> {
-        let client = create_instance()?;
-        let key = "key";
-        let value = "value".as_bytes();
-        client
-            .put(Keyspace::Slots, key.to_owned(), value.to_vec())
-            .await?;
-        assert_eq!(client.get(Keyspace::Slots, key).await?, value);
-        Ok(())
-    }
-
-    #[tokio::test]
-    async fn multiple_operation() -> Result<(), Box<dyn std::error::Error>> {
-        let client = create_instance()?;
-        let key = "key".to_string();
-        let value = "value".as_bytes().to_vec();
-        let locks = client
-            .acquire_locks(vec![(Keyspace::ActiveJobs, ""), (Keyspace::Slots, "")])
-            .await?;
-
-        let _r: ballista_core::error::Result<()> = with_locks(locks, async {
-            let txn_ops = vec![
-                (Operation::Put(value.clone()), Keyspace::Slots, key.clone()),
-                (
-                    Operation::Put(value.clone()),
-                    Keyspace::ActiveJobs,
-                    key.clone(),
-                ),
-            ];
-            client.apply_txn(txn_ops).await?;
-            Ok(())
-        })
-        .await;
-
-        assert_eq!(client.get(Keyspace::Slots, key.as_str()).await?, value);
-        assert_eq!(client.get(Keyspace::ActiveJobs, key.as_str()).await?, value);
-        Ok(())
-    }
-
-    #[tokio::test]
-    async fn read_empty() -> Result<(), Box<dyn std::error::Error>> {
-        let client = create_instance()?;
-        let key = "key";
-        let empty: &[u8] = &[];
-        assert_eq!(client.get(Keyspace::Slots, key).await?, empty);
-        Ok(())
-    }
-
-    #[tokio::test]
-    async fn read_prefix() -> Result<(), Box<dyn std::error::Error>> {
-        let client = create_instance()?;
-        let key = "key";
-        let value = "value".as_bytes();
-        client
-            .put(Keyspace::Slots, format!("{}/1", key), value.to_vec())
-            .await?;
-        client
-            .put(Keyspace::Slots, format!("{}/2", key), value.to_vec())
-            .await?;
-        assert_eq!(
-            client.get_from_prefix(Keyspace::Slots, key).await?,
-            vec![
-                ("/Slots/key/1".to_owned(), value.to_vec()),
-                ("/Slots/key/2".to_owned(), value.to_vec())
-            ]
-        );
-        Ok(())
-    }
-
-    #[tokio::test]
-    async fn read_watch() -> Result<(), Box<dyn std::error::Error>> {
-        let client = create_instance()?;
-        let key = "key";
-        let value = "value".as_bytes();
-        let mut watch: Box<dyn Watch> =
-            client.watch(Keyspace::Slots, key.to_owned()).await?;
-        client
-            .put(Keyspace::Slots, key.to_owned(), value.to_vec())
-            .await?;
-        assert_eq!(
-            watch.next().await,
-            Some(WatchEvent::Put(
-                format!("/{:?}/{}", Keyspace::Slots, key.to_owned()),
-                value.to_owned()
-            ))
-        );
-        let value2 = "value2".as_bytes();
-        client
-            .put(Keyspace::Slots, key.to_owned(), value2.to_vec())
-            .await?;
-        assert_eq!(
-            watch.next().await,
-            Some(WatchEvent::Put(
-                format!("/{:?}/{}", Keyspace::Slots, key.to_owned()),
-                value2.to_owned()
-            ))
-        );
-        watch.cancel().await?;
-        Ok(())
-    }
-}
diff --git a/ballista/scheduler/src/state/backend/utils/mod.rs b/ballista/scheduler/src/state/backend/utils/mod.rs
deleted file mode 100644
index de95dd6e..00000000
--- a/ballista/scheduler/src/state/backend/utils/mod.rs
+++ /dev/null
@@ -1,21 +0,0 @@
-// 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.
-
-#[allow(dead_code)]
-mod oneshot;
-#[allow(dead_code)]
-pub(crate) mod subscriber;
diff --git a/ballista/scheduler/src/state/backend/utils/oneshot.rs b/ballista/scheduler/src/state/backend/utils/oneshot.rs
deleted file mode 100644
index a0d14699..00000000
--- a/ballista/scheduler/src/state/backend/utils/oneshot.rs
+++ /dev/null
@@ -1,179 +0,0 @@
-// 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.
-
-//! It's mainly a modified version of sled::oneshot
-
-use std::{
-    future::Future,
-    pin::Pin,
-    sync::Arc,
-    task::{Context, Poll, Waker},
-    time::{Duration, Instant},
-};
-
-use parking_lot::{Condvar, Mutex};
-
-#[derive(Debug)]
-struct OneShotState<T> {
-    filled: bool,
-    fused: bool,
-    item: Option<T>,
-    waker: Option<Waker>,
-}
-
-impl<T> Default for OneShotState<T> {
-    fn default() -> OneShotState<T> {
-        OneShotState {
-            filled: false,
-            fused: false,
-            item: None,
-            waker: None,
-        }
-    }
-}
-
-/// A Future value which may or may not be filled
-#[derive(Debug)]
-pub struct OneShot<T> {
-    mu: Arc<Mutex<OneShotState<T>>>,
-    cv: Arc<Condvar>,
-}
-
-/// The completer side of the Future
-pub struct OneShotFiller<T> {
-    mu: Arc<Mutex<OneShotState<T>>>,
-    cv: Arc<Condvar>,
-}
-
-impl<T> OneShot<T> {
-    /// Create a new `OneShotFiller` and the `OneShot`
-    /// that will be filled by its completion.
-    pub fn pair() -> (OneShotFiller<T>, Self) {
-        let mu = Arc::new(Mutex::new(OneShotState::default()));
-        let cv = Arc::new(Condvar::new());
-        let future = Self {
-            mu: mu.clone(),
-            cv: cv.clone(),
-        };
-        let filler = OneShotFiller { mu, cv };
-
-        (filler, future)
-    }
-
-    /// Block on the `OneShot`'s completion
-    /// or dropping of the `OneShotFiller`
-    pub fn wait(self) -> Option<T> {
-        let mut inner = self.mu.lock();
-        while !inner.filled {
-            self.cv.wait(&mut inner);
-        }
-        inner.item.take()
-    }
-
-    /// Block on the `OneShot`'s completion
-    /// or dropping of the `OneShotFiller`,
-    /// returning an error if not filled
-    /// before a given timeout or if the
-    /// system shuts down before then.
-    ///
-    /// Upon a successful receive, the
-    /// oneshot should be dropped, as it
-    /// will never yield that value again.
-    pub fn wait_timeout(
-        &mut self,
-        mut timeout: Duration,
-    ) -> Result<T, std::sync::mpsc::RecvTimeoutError> {
-        let mut inner = self.mu.lock();
-        while !inner.filled {
-            let start = Instant::now();
-            let res = self.cv.wait_for(&mut inner, timeout);
-            if res.timed_out() {
-                return Err(std::sync::mpsc::RecvTimeoutError::Disconnected);
-            }
-            timeout = if let Some(timeout) = timeout.checked_sub(start.elapsed()) {
-                timeout
-            } else {
-                Duration::from_nanos(0)
-            };
-        }
-        if let Some(item) = inner.item.take() {
-            Ok(item)
-        } else {
-            Err(std::sync::mpsc::RecvTimeoutError::Disconnected)
-        }
-    }
-}
-
-impl<T> Future for OneShot<T> {
-    type Output = Option<T>;
-
-    fn poll(self: Pin<&mut Self>, cx: &mut Context<'_>) -> Poll<Self::Output> {
-        let mut state = self.mu.lock();
-        if state.fused {
-            return Poll::Pending;
-        }
-        if state.filled {
-            state.fused = true;
-            Poll::Ready(state.item.take())
-        } else {
-            state.waker = Some(cx.waker().clone());
-            Poll::Pending
-        }
-    }
-}
-
-impl<T> OneShotFiller<T> {
-    /// Complete the `OneShot`
-    pub fn fill(self, inner: T) {
-        let mut state = self.mu.lock();
-
-        if let Some(waker) = state.waker.take() {
-            waker.wake();
-        }
-
-        state.filled = true;
-        state.item = Some(inner);
-
-        // having held the mutex makes this linearized
-        // with the notify below.
-        drop(state);
-
-        let _notified = self.cv.notify_all();
-    }
-}
-
-impl<T> Drop for OneShotFiller<T> {
-    fn drop(&mut self) {
-        let mut state = self.mu.lock();
-
-        if state.filled {
-            return;
-        }
-
-        if let Some(waker) = state.waker.take() {
-            waker.wake();
-        }
-
-        state.filled = true;
-
-        // having held the mutex makes this linearized
-        // with the notify below.
-        drop(state);
-
-        let _notified = self.cv.notify_all();
-    }
-}
diff --git a/ballista/scheduler/src/state/backend/utils/subscriber.rs b/ballista/scheduler/src/state/backend/utils/subscriber.rs
deleted file mode 100644
index dd74b664..00000000
--- a/ballista/scheduler/src/state/backend/utils/subscriber.rs
+++ /dev/null
@@ -1,248 +0,0 @@
-// 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.
-
-//! It's mainly a modified version of sled::subscriber
-
-use crate::state::backend::utils::oneshot::{OneShot, OneShotFiller};
-use crate::state::backend::WatchEvent;
-
-use parking_lot::RwLock;
-use std::collections::{BTreeMap, HashMap};
-use std::future::Future;
-use std::pin::Pin;
-use std::sync::atomic::Ordering::Relaxed;
-use std::sync::atomic::{AtomicBool, AtomicUsize};
-use std::sync::mpsc::{sync_channel, Receiver, SyncSender, TryRecvError};
-use std::sync::Arc;
-use std::task::{Context, Poll, Waker};
-use std::time::{Duration, Instant};
-
-static ID_GEN: AtomicUsize = AtomicUsize::new(0);
-
-type Senders = HashMap<usize, (Option<Waker>, SyncSender<OneShot<Option<WatchEvent>>>)>;
-
-/// Aynchronous, non-blocking subscriber:
-///
-/// `Subscription` implements `Future<Output=Option<Event>>`.
-///
-/// `while let Some(event) = (&mut subscriber).await { /* use it */ }`
-pub struct Subscriber {
-    id: usize,
-    rx: Receiver<OneShot<Option<WatchEvent>>>,
-    existing: Option<OneShot<Option<WatchEvent>>>,
-    home: Arc<RwLock<Senders>>,
-}
-
-impl Drop for Subscriber {
-    fn drop(&mut self) {
-        let mut w_senders = self.home.write();
-        w_senders.remove(&self.id);
-    }
-}
-
-impl Subscriber {
-    /// Attempts to wait for a value on this `Subscriber`, returning
-    /// an error if no event arrives within the provided `Duration`
-    /// or if the backing `Db` shuts down.
-    pub fn next_timeout(
-        &mut self,
-        mut timeout: Duration,
-    ) -> std::result::Result<WatchEvent, std::sync::mpsc::RecvTimeoutError> {
-        loop {
-            let start = Instant::now();
-            let mut future_rx = if let Some(future_rx) = self.existing.take() {
-                future_rx
-            } else {
-                self.rx.recv_timeout(timeout)?
-            };
-            timeout = if let Some(timeout) = timeout.checked_sub(start.elapsed()) {
-                timeout
-            } else {
-                Duration::from_nanos(0)
-            };
-
-            let start = Instant::now();
-            match future_rx.wait_timeout(timeout) {
-                Ok(Some(event)) => return Ok(event),
-                Ok(None) => (),
-                Err(timeout_error) => {
-                    self.existing = Some(future_rx);
-                    return Err(timeout_error);
-                }
-            }
-            timeout = if let Some(timeout) = timeout.checked_sub(start.elapsed()) {
-                timeout
-            } else {
-                Duration::from_nanos(0)
-            };
-        }
-    }
-}
-
-impl Future for Subscriber {
-    type Output = Option<WatchEvent>;
-
-    fn poll(mut self: Pin<&mut Self>, cx: &mut Context<'_>) -> Poll<Self::Output> {
-        loop {
-            let mut future_rx = if let Some(future_rx) = self.existing.take() {
-                future_rx
-            } else {
-                match self.rx.try_recv() {
-                    Ok(future_rx) => future_rx,
-                    Err(TryRecvError::Empty) => break,
-                    Err(TryRecvError::Disconnected) => return Poll::Ready(None),
-                }
-            };
-
-            match Future::poll(Pin::new(&mut future_rx), cx) {
-                Poll::Ready(Some(event)) => return Poll::Ready(event),
-                Poll::Ready(None) => continue,
-                Poll::Pending => {
-                    self.existing = Some(future_rx);
-                    return Poll::Pending;
-                }
-            }
-        }
-        let mut home = self.home.write();
-        let entry = home.get_mut(&self.id).unwrap();
-        entry.0 = Some(cx.waker().clone());
-        Poll::Pending
-    }
-}
-
-impl Iterator for Subscriber {
-    type Item = WatchEvent;
-
-    fn next(&mut self) -> Option<WatchEvent> {
-        loop {
-            let future_rx = self.rx.recv().ok()?;
-            match future_rx.wait() {
-                Some(Some(event)) => return Some(event),
-                Some(None) => return None,
-                None => continue,
-            }
-        }
-    }
-}
-
-#[derive(Debug, Default)]
-pub(crate) struct Subscribers {
-    watched: RwLock<BTreeMap<Vec<u8>, Arc<RwLock<Senders>>>>,
-    ever_used: AtomicBool,
-}
-
-impl Drop for Subscribers {
-    fn drop(&mut self) {
-        let watched = self.watched.read();
-
-        for senders in watched.values() {
-            let senders = std::mem::take(&mut *senders.write());
-            for (_, (waker, sender)) in senders {
-                drop(sender);
-                if let Some(waker) = waker {
-                    waker.wake();
-                }
-            }
-        }
-    }
-}
-
-impl Subscribers {
-    pub(crate) fn register(&self, prefix: &[u8]) -> Subscriber {
-        self.ever_used.store(true, Relaxed);
-        let r_mu = {
-            let r_mu = self.watched.read();
-            if r_mu.contains_key(prefix) {
-                r_mu
-            } else {
-                drop(r_mu);
-                let mut w_mu = self.watched.write();
-                if !w_mu.contains_key(prefix) {
-                    let old = w_mu.insert(
-                        prefix.to_vec(),
-                        Arc::new(RwLock::new(HashMap::default())),
-                    );
-                    assert!(old.is_none());
-                }
-                drop(w_mu);
-                self.watched.read()
-            }
-        };
-
-        let (tx, rx) = sync_channel(1024);
-
-        let arc_senders = &r_mu[prefix];
-        let mut w_senders = arc_senders.write();
-
-        let id = ID_GEN.fetch_add(1, Relaxed);
-
-        w_senders.insert(id, (None, tx));
-
-        Subscriber {
-            id,
-            rx,
-            existing: None,
-            home: arc_senders.clone(),
-        }
-    }
-
-    pub(crate) fn reserve<R: AsRef<[u8]>>(&self, key: R) -> Option<ReservedBroadcast> {
-        if !self.ever_used.load(Relaxed) {
-            return None;
-        }
-
-        let r_mu = self.watched.read();
-        let prefixes = r_mu.iter().filter(|(k, _)| key.as_ref().starts_with(k));
-
-        let mut subscribers = vec![];
-
-        for (_, subs_rwl) in prefixes {
-            let subs = subs_rwl.read();
-
-            for (_id, (waker, sender)) in subs.iter() {
-                let (tx, rx) = OneShot::pair();
-                if sender.send(rx).is_err() {
-                    continue;
-                }
-                subscribers.push((waker.clone(), tx));
-            }
-        }
-
-        if subscribers.is_empty() {
-            None
-        } else {
-            Some(ReservedBroadcast { subscribers })
-        }
-    }
-}
-
-pub(crate) struct ReservedBroadcast {
-    subscribers: Vec<(Option<Waker>, OneShotFiller<Option<WatchEvent>>)>,
-}
-
-impl ReservedBroadcast {
-    pub fn complete(self, event: &WatchEvent) {
-        let iter = self.subscribers.into_iter();
-
-        for (waker, tx) in iter {
-            tx.fill(Some(event.clone()));
-            if let Some(waker) = waker {
-                waker.wake();
-            }
-        }
-    }
-}
diff --git a/ballista/scheduler/src/state/execution_graph.rs b/ballista/scheduler/src/state/execution_graph.rs
index dbd29226..e60d138e 100644
--- a/ballista/scheduler/src/state/execution_graph.rs
+++ b/ballista/scheduler/src/state/execution_graph.rs
@@ -35,7 +35,7 @@ use ballista_core::execution_plans::{ShuffleWriterExec, UnresolvedShuffleExec};
 use ballista_core::serde::protobuf::failed_task::FailedReason;
 use ballista_core::serde::protobuf::job_status::Status;
 use ballista_core::serde::protobuf::{
-    self, execution_graph_stage::StageType, FailedTask, JobStatus, QueuedJob, ResultLost,
+    self, execution_graph_stage::StageType, FailedTask, JobStatus, ResultLost,
     RunningJob, SuccessfulJob, TaskStatus,
 };
 use ballista_core::serde::protobuf::{job_status, FailedJob, ShuffleWritePartition};
@@ -158,6 +158,8 @@ impl ExecutionGraph {
         let builder = ExecutionStageBuilder::new();
         let stages = builder.build(shuffle_stages)?;
 
+        let started_at = timestamp_millis();
+
         Ok(Self {
             scheduler_id: Some(scheduler_id.to_string()),
             job_id: job_id.to_string(),
@@ -166,10 +168,14 @@ impl ExecutionGraph {
             status: JobStatus {
                 job_id: job_id.to_string(),
                 job_name: job_name.to_string(),
-                status: Some(job_status::Status::Queued(QueuedJob { queued_at })),
+                status: Some(Status::Running(RunningJob {
+                    queued_at,
+                    started_at,
+                    scheduler: scheduler_id.to_string(),
+                })),
             },
             queued_at,
-            start_time: timestamp_millis(),
+            start_time: started_at,
             end_time: 0,
             stages,
             output_partitions,
@@ -1223,7 +1229,7 @@ impl ExecutionGraph {
         self.status = JobStatus {
             job_id: self.job_id.clone(),
             job_name: self.job_name.clone(),
-            status: Some(job_status::Status::Failed(FailedJob {
+            status: Some(Status::Failed(FailedJob {
                 error,
                 queued_at: self.queued_at,
                 started_at: self.start_time,
@@ -1271,18 +1277,6 @@ impl ExecutionGraph {
         self.failed_stage_attempts.remove(&stage_id);
     }
 
-    pub(crate) fn disown(&mut self) {
-        self.scheduler_id = None;
-
-        if let JobStatus {
-            status: Some(Status::Running(RunningJob { scheduler, .. })),
-            ..
-        } = &mut self.status
-        {
-            std::mem::take(scheduler);
-        }
-    }
-
     pub(crate) async fn decode_execution_graph<
         T: 'static + AsLogicalPlan,
         U: 'static + AsExecutionPlan,
@@ -1621,24 +1615,20 @@ fn partition_to_location(
 #[cfg(test)]
 mod test {
     use std::collections::HashSet;
-    use std::sync::Arc;
-
-    use datafusion::arrow::datatypes::{DataType, Field, Schema};
-    use datafusion::logical_expr::JoinType;
-    use datafusion::logical_expr::{col, count, sum, Expr};
-    use datafusion::physical_plan::display::DisplayableExecutionPlan;
-    use datafusion::prelude::{SessionConfig, SessionContext};
-    use datafusion::test_util::scan_empty;
 
     use crate::scheduler_server::event::QueryStageSchedulerEvent;
     use ballista_core::error::Result;
     use ballista_core::serde::protobuf::{
-        self, failed_task, job_status, task_status, ExecutionError, FailedTask,
-        FetchPartitionError, IoError, JobStatus, TaskKilled, TaskStatus,
+        self, failed_task, job_status, ExecutionError, FailedTask, FetchPartitionError,
+        IoError, JobStatus, TaskKilled,
     };
-    use ballista_core::serde::scheduler::{ExecutorMetadata, ExecutorSpecification};
 
-    use crate::state::execution_graph::{ExecutionGraph, TaskDescription};
+    use crate::state::execution_graph::ExecutionGraph;
+    use crate::test_utils::{
+        mock_completed_task, mock_executor, mock_failed_task, test_aggregation_plan,
+        test_coalesce_plan, test_join_plan, test_two_aggregations_plan,
+        test_union_all_plan, test_union_plan,
+    };
 
     #[tokio::test]
     async fn test_drain_tasks() -> Result<()> {
@@ -1911,18 +1901,6 @@ mod test {
             4,
         )?;
 
-        // TODO the JobStatus is not 'Running' here, no place to mark it to 'Running' in current code base.
-        assert!(
-            matches!(
-                agg_graph.status,
-                JobStatus {
-                    status: Some(job_status::Status::Queued(_)),
-                    ..
-                }
-            ),
-            "Expected job status to be running"
-        );
-
         assert_eq!(agg_graph.available_tasks(), 2);
         drain_tasks(&mut agg_graph)?;
         assert_eq!(agg_graph.available_tasks(), 0);
@@ -2794,265 +2772,4 @@ mod test {
 
         Ok(())
     }
-
-    async fn test_aggregation_plan(partition: usize) -> ExecutionGraph {
-        let config = SessionConfig::new().with_target_partitions(partition);
-        let ctx = Arc::new(SessionContext::with_config(config));
-
-        let schema = Schema::new(vec![
-            Field::new("id", DataType::Utf8, false),
-            Field::new("gmv", DataType::UInt64, false),
-        ]);
-
-        let logical_plan = scan_empty(None, &schema, Some(vec![0, 1]))
-            .unwrap()
-            .aggregate(vec![col("id")], vec![sum(col("gmv"))])
-            .unwrap()
-            .build()
-            .unwrap();
-
-        let optimized_plan = ctx.optimize(&logical_plan).unwrap();
-
-        let plan = ctx.create_physical_plan(&optimized_plan).await.unwrap();
-
-        println!("{}", DisplayableExecutionPlan::new(plan.as_ref()).indent());
-
-        ExecutionGraph::new("localhost:50050", "job", "", "session", plan, 0).unwrap()
-    }
-
-    async fn test_two_aggregations_plan(partition: usize) -> ExecutionGraph {
-        let config = SessionConfig::new().with_target_partitions(partition);
-        let ctx = Arc::new(SessionContext::with_config(config));
-
-        let schema = Schema::new(vec![
-            Field::new("id", DataType::Utf8, false),
-            Field::new("name", DataType::Utf8, false),
-            Field::new("gmv", DataType::UInt64, false),
-        ]);
-
-        let logical_plan = scan_empty(None, &schema, Some(vec![0, 1, 2]))
-            .unwrap()
-            .aggregate(vec![col("id"), col("name")], vec![sum(col("gmv"))])
-            .unwrap()
-            .aggregate(vec![col("id")], vec![count(col("id"))])
-            .unwrap()
-            .build()
-            .unwrap();
-
-        let optimized_plan = ctx.optimize(&logical_plan).unwrap();
-
-        let plan = ctx.create_physical_plan(&optimized_plan).await.unwrap();
-
-        println!("{}", DisplayableExecutionPlan::new(plan.as_ref()).indent());
-
-        ExecutionGraph::new("localhost:50050", "job", "", "session", plan, 0).unwrap()
-    }
-
-    async fn test_coalesce_plan(partition: usize) -> ExecutionGraph {
-        let config = SessionConfig::new().with_target_partitions(partition);
-        let ctx = Arc::new(SessionContext::with_config(config));
-
-        let schema = Schema::new(vec![
-            Field::new("id", DataType::Utf8, false),
-            Field::new("gmv", DataType::UInt64, false),
-        ]);
-
-        let logical_plan = scan_empty(None, &schema, Some(vec![0, 1]))
-            .unwrap()
-            .limit(0, Some(1))
-            .unwrap()
-            .build()
-            .unwrap();
-
-        let optimized_plan = ctx.optimize(&logical_plan).unwrap();
-
-        let plan = ctx.create_physical_plan(&optimized_plan).await.unwrap();
-
-        ExecutionGraph::new("localhost:50050", "job", "", "session", plan, 0).unwrap()
-    }
-
-    async fn test_join_plan(partition: usize) -> ExecutionGraph {
-        let config = SessionConfig::new().with_target_partitions(partition);
-        let ctx = Arc::new(SessionContext::with_config(config));
-
-        let schema = Schema::new(vec![
-            Field::new("id", DataType::Utf8, false),
-            Field::new("gmv", DataType::UInt64, false),
-        ]);
-
-        let left_plan = scan_empty(Some("left"), &schema, None).unwrap();
-
-        let right_plan = scan_empty(Some("right"), &schema, None)
-            .unwrap()
-            .build()
-            .unwrap();
-
-        let sort_expr = Expr::Sort {
-            expr: Box::new(col("id")),
-            asc: false,
-            nulls_first: false,
-        };
-
-        let logical_plan = left_plan
-            .join(&right_plan, JoinType::Inner, (vec!["id"], vec!["id"]), None)
-            .unwrap()
-            .aggregate(vec![col("id")], vec![sum(col("gmv"))])
-            .unwrap()
-            .sort(vec![sort_expr])
-            .unwrap()
-            .build()
-            .unwrap();
-
-        let optimized_plan = ctx.optimize(&logical_plan).unwrap();
-
-        let plan = ctx.create_physical_plan(&optimized_plan).await.unwrap();
-
-        println!("{}", DisplayableExecutionPlan::new(plan.as_ref()).indent());
-
-        let graph = ExecutionGraph::new("localhost:50050", "job", "", "session", plan, 0)
-            .unwrap();
-
-        println!("{:?}", graph);
-
-        graph
-    }
-
-    async fn test_union_all_plan(partition: usize) -> ExecutionGraph {
-        let config = SessionConfig::new().with_target_partitions(partition);
-        let ctx = Arc::new(SessionContext::with_config(config));
-
-        let logical_plan = ctx
-            .sql("SELECT 1 as NUMBER union all SELECT 1 as NUMBER;")
-            .await
-            .unwrap()
-            .to_logical_plan()
-            .unwrap();
-
-        let optimized_plan = ctx.optimize(&logical_plan).unwrap();
-
-        let plan = ctx.create_physical_plan(&optimized_plan).await.unwrap();
-
-        println!("{}", DisplayableExecutionPlan::new(plan.as_ref()).indent());
-
-        let graph = ExecutionGraph::new("localhost:50050", "job", "", "session", plan, 0)
-            .unwrap();
-
-        println!("{:?}", graph);
-
-        graph
-    }
-
-    async fn test_union_plan(partition: usize) -> ExecutionGraph {
-        let config = SessionConfig::new().with_target_partitions(partition);
-        let ctx = Arc::new(SessionContext::with_config(config));
-
-        let logical_plan = ctx
-            .sql("SELECT 1 as NUMBER union SELECT 1 as NUMBER;")
-            .await
-            .unwrap()
-            .to_logical_plan()
-            .unwrap();
-
-        let optimized_plan = ctx.optimize(&logical_plan).unwrap();
-
-        let plan = ctx.create_physical_plan(&optimized_plan).await.unwrap();
-
-        println!("{}", DisplayableExecutionPlan::new(plan.as_ref()).indent());
-
-        let graph = ExecutionGraph::new("localhost:50050", "job", "", "session", plan, 0)
-            .unwrap();
-
-        println!("{:?}", graph);
-
-        graph
-    }
-
-    fn mock_executor(executor_id: String) -> ExecutorMetadata {
-        ExecutorMetadata {
-            id: executor_id,
-            host: "localhost2".to_string(),
-            port: 8080,
-            grpc_port: 9090,
-            specification: ExecutorSpecification { task_slots: 1 },
-        }
-    }
-
-    fn mock_completed_task(task: TaskDescription, executor_id: &str) -> TaskStatus {
-        let mut partitions: Vec<protobuf::ShuffleWritePartition> = vec![];
-
-        let num_partitions = task
-            .output_partitioning
-            .map(|p| p.partition_count())
-            .unwrap_or(1);
-
-        for partition_id in 0..num_partitions {
-            partitions.push(protobuf::ShuffleWritePartition {
-                partition_id: partition_id as u64,
-                path: format!(
-                    "/{}/{}/{}",
-                    task.partition.job_id,
-                    task.partition.stage_id,
-                    task.partition.partition_id
-                ),
-                num_batches: 1,
-                num_rows: 1,
-                num_bytes: 1,
-            })
-        }
-
-        // Complete the task
-        protobuf::TaskStatus {
-            task_id: task.task_id as u32,
-            job_id: task.partition.job_id.clone(),
-            stage_id: task.partition.stage_id as u32,
-            stage_attempt_num: task.stage_attempt_num as u32,
-            partition_id: task.partition.partition_id as u32,
-            launch_time: 0,
-            start_exec_time: 0,
-            end_exec_time: 0,
-            metrics: vec![],
-            status: Some(task_status::Status::Successful(protobuf::SuccessfulTask {
-                executor_id: executor_id.to_owned(),
-                partitions,
-            })),
-        }
-    }
-
-    fn mock_failed_task(task: TaskDescription, failed_task: FailedTask) -> TaskStatus {
-        let mut partitions: Vec<protobuf::ShuffleWritePartition> = vec![];
-
-        let num_partitions = task
-            .output_partitioning
-            .map(|p| p.partition_count())
-            .unwrap_or(1);
-
-        for partition_id in 0..num_partitions {
-            partitions.push(protobuf::ShuffleWritePartition {
-                partition_id: partition_id as u64,
-                path: format!(
-                    "/{}/{}/{}",
-                    task.partition.job_id,
-                    task.partition.stage_id,
-                    task.partition.partition_id
-                ),
-                num_batches: 1,
-                num_rows: 1,
-                num_bytes: 1,
-            })
-        }
-
-        // Fail the task
-        protobuf::TaskStatus {
-            task_id: task.task_id as u32,
-            job_id: task.partition.job_id.clone(),
-            stage_id: task.partition.stage_id as u32,
-            stage_attempt_num: task.stage_attempt_num as u32,
-            partition_id: task.partition.partition_id as u32,
-            launch_time: 0,
-            start_exec_time: 0,
-            end_exec_time: 0,
-            metrics: vec![],
-            status: Some(task_status::Status::Failed(failed_task)),
-        }
-    }
 }
diff --git a/ballista/scheduler/src/state/executor_manager.rs b/ballista/scheduler/src/state/executor_manager.rs
index 9155c015..b7a6b875 100644
--- a/ballista/scheduler/src/state/executor_manager.rs
+++ b/ballista/scheduler/src/state/executor_manager.rs
@@ -24,6 +24,7 @@ use ballista_core::serde::protobuf;
 
 use crate::cluster::ClusterState;
 use crate::config::SlotsPolicy;
+use crate::scheduler_server::timestamp_secs;
 use crate::state::execution_graph::RunningTaskInfo;
 use ballista_core::serde::protobuf::executor_grpc_client::ExecutorGrpcClient;
 use ballista_core::serde::protobuf::{
@@ -39,6 +40,7 @@ use parking_lot::Mutex;
 use std::collections::{HashMap, HashSet};
 use std::sync::Arc;
 use tonic::transport::Channel;
+use tracing::trace;
 
 type ExecutorClients = Arc<DashMap<String, ExecutorGrpcClient<Channel>>>;
 
@@ -163,7 +165,7 @@ impl ExecutorManager {
         } else {
             let alive_executors = self.get_alive_executors_within_one_minute();
 
-            println!("Alive executors: {:?}", alive_executors);
+            trace!("alive executors: {:?}", alive_executors);
 
             self.cluster_state
                 .reserve_slots(n, self.task_distribution, Some(alive_executors))
@@ -454,21 +456,16 @@ impl ExecutorManager {
         specification: ExecutorData,
         reserve: bool,
     ) -> Result<Vec<ExecutorReservation>> {
-        self.test_scheduler_connectivity(&metadata).await?;
+        debug!(
+            "registering executor {} with {} task slots",
+            metadata.id, specification.total_task_slots
+        );
 
-        let current_ts = SystemTime::now()
-            .duration_since(UNIX_EPOCH)
-            .map_err(|e| {
-                BallistaError::Internal(format!(
-                    "Error getting current timestamp: {:?}",
-                    e
-                ))
-            })?
-            .as_secs();
+        self.test_scheduler_connectivity(&metadata).await?;
 
         let initial_heartbeat = ExecutorHeartbeat {
             executor_id: metadata.id.clone(),
-            timestamp: current_ts,
+            timestamp: timestamp_secs(),
             metrics: vec![],
             status: Some(ExecutorStatus {
                 status: Some(executor_status::Status::Active(String::default())),
@@ -720,6 +717,7 @@ mod test {
 
     async fn test_reserve_partial_inner(slots_policy: SlotsPolicy) -> Result<()> {
         let cluster = test_cluster_context();
+
         let executor_manager =
             ExecutorManager::new(cluster.cluster_state(), slots_policy);
 
diff --git a/ballista/scheduler/src/state/mod.rs b/ballista/scheduler/src/state/mod.rs
index 342dd7aa..3582e487 100644
--- a/ballista/scheduler/src/state/mod.rs
+++ b/ballista/scheduler/src/state/mod.rs
@@ -20,13 +20,11 @@ use datafusion::datasource::source_as_provider;
 use datafusion::logical_expr::PlanVisitor;
 use std::any::type_name;
 use std::collections::HashMap;
-use std::future::Future;
 use std::sync::Arc;
 use std::time::Instant;
 
 use crate::scheduler_server::event::QueryStageSchedulerEvent;
 
-use crate::state::backend::Lock;
 use crate::state::executor_manager::{ExecutorManager, ExecutorReservation};
 use crate::state::session_manager::SessionManager;
 use crate::state::task_manager::{TaskLauncher, TaskManager};
@@ -44,7 +42,6 @@ use datafusion_proto::logical_plan::AsLogicalPlan;
 use log::{debug, error, info};
 use prost::Message;
 
-pub mod backend;
 pub mod execution_graph;
 pub mod execution_graph_dot;
 pub mod executor_manager;
@@ -420,26 +417,6 @@ impl<T: 'static + AsLogicalPlan, U: 'static + AsExecutionPlan> SchedulerState<T,
     }
 }
 
-pub async fn with_lock<Out, F: Future<Output = Out>>(
-    mut lock: Box<dyn Lock>,
-    op: F,
-) -> Out {
-    let result = op.await;
-    lock.unlock().await;
-    result
-}
-/// It takes multiple locks and reverse the order for releasing them to prevent a race condition.
-pub async fn with_locks<Out, F: Future<Output = Out>>(
-    locks: Vec<Box<dyn Lock>>,
-    op: F,
-) -> Out {
-    let result = op.await;
-    for mut lock in locks.into_iter().rev() {
-        lock.unlock().await;
-    }
-    result
-}
-
 #[cfg(test)]
 mod test {
 
@@ -456,6 +433,7 @@ mod test {
 
     use crate::config::SchedulerConfig;
 
+    use crate::scheduler_server::timestamp_millis;
     use crate::test_utils::{test_cluster_context, BlackholeTaskLauncher};
     use datafusion::arrow::datatypes::{DataType, Field, Schema};
     use datafusion::logical_expr::{col, sum};
@@ -519,6 +497,10 @@ mod test {
         let plan = test_graph(session_ctx.clone()).await;
 
         // Create 4 jobs so we have four pending tasks
+        state
+            .task_manager
+            .queue_job("job-1", "", timestamp_millis())
+            .await?;
         state
             .task_manager
             .submit_job(
@@ -529,6 +511,10 @@ mod test {
                 0,
             )
             .await?;
+        state
+            .task_manager
+            .queue_job("job-2", "", timestamp_millis())
+            .await?;
         state
             .task_manager
             .submit_job(
@@ -539,6 +525,10 @@ mod test {
                 0,
             )
             .await?;
+        state
+            .task_manager
+            .queue_job("job-3", "", timestamp_millis())
+            .await?;
         state
             .task_manager
             .submit_job(
@@ -549,6 +539,10 @@ mod test {
                 0,
             )
             .await?;
+        state
+            .task_manager
+            .queue_job("job-4", "", timestamp_millis())
+            .await?;
         state
             .task_manager
             .submit_job(
@@ -603,6 +597,10 @@ mod test {
         let plan = test_graph(session_ctx.clone()).await;
 
         // Create a job
+        state
+            .task_manager
+            .queue_job("job-1", "", timestamp_millis())
+            .await?;
         state
             .task_manager
             .submit_job(
@@ -623,7 +621,6 @@ mod test {
             let plan_graph = state
                 .task_manager
                 .get_active_execution_graph("job-1")
-                .await
                 .unwrap();
             let task_def = plan_graph
                 .write()
diff --git a/ballista/scheduler/src/state/task_manager.rs b/ballista/scheduler/src/state/task_manager.rs
index ebc58c5f..2f464976 100644
--- a/ballista/scheduler/src/state/task_manager.rs
+++ b/ballista/scheduler/src/state/task_manager.rs
@@ -169,6 +169,16 @@ impl<T: 'static + AsLogicalPlan, U: 'static + AsExecutionPlan> TaskManager<T, U>
         }
     }
 
+    /// Enqueue a job for scheduling
+    pub async fn queue_job(
+        &self,
+        job_id: &str,
+        job_name: &str,
+        queued_at: u64,
+    ) -> Result<()> {
+        self.state.accept_job(job_id, job_name, queued_at).await
+    }
+
     /// Generate an ExecutionGraph for the job and save it to the persistent state.
     /// By default, this job will be curated by the scheduler which receives it.
     /// Then we will also save it to the active execution graph
@@ -222,7 +232,13 @@ impl<T: 'static + AsLogicalPlan, U: 'static + AsExecutionPlan> TaskManager<T, U>
     /// Get the status of of a job. First look in the active cache.
     /// If no one found, then in the Active/Completed jobs, and then in Failed jobs
     pub async fn get_job_status(&self, job_id: &str) -> Result<Option<JobStatus>> {
-        self.state.get_job_status(job_id).await
+        if let Some(graph) = self.get_active_execution_graph(job_id) {
+            let guard = graph.read().await;
+
+            Ok(Some(guard.status()))
+        } else {
+            self.state.get_job_status(job_id).await
+        }
     }
 
     /// Get the execution graph of of a job. First look in the active cache.
@@ -231,8 +247,8 @@ impl<T: 'static + AsLogicalPlan, U: 'static + AsExecutionPlan> TaskManager<T, U>
         &self,
         job_id: &str,
     ) -> Result<Option<Arc<ExecutionGraph>>> {
-        if let Some(cached) = self.active_job_cache.get(job_id) {
-            let guard = cached.execution_graph.read().await;
+        if let Some(cached) = self.get_active_execution_graph(job_id) {
+            let guard = cached.read().await;
 
             Ok(Some(Arc::new(guard.deref().clone())))
         } else {
@@ -264,8 +280,10 @@ impl<T: 'static + AsLogicalPlan, U: 'static + AsExecutionPlan> TaskManager<T, U>
             debug!("Updating {} tasks in job {}", num_tasks, job_id);
 
             // let graph = self.get_active_execution_graph(&job_id).await;
-            let job_events = if let Some(cached) = self.active_job_cache.get(&job_id) {
-                let mut graph = cached.execution_graph.write().await;
+            let job_events = if let Some(cached) =
+                self.get_active_execution_graph(&job_id)
+            {
+                let mut graph = cached.write().await;
                 graph.update_task_status(
                     executor,
                     statuses,
@@ -346,7 +364,7 @@ impl<T: 'static + AsLogicalPlan, U: 'static + AsExecutionPlan> TaskManager<T, U>
     pub(crate) async fn succeed_job(&self, job_id: &str) -> Result<()> {
         debug!("Moving job {} from Active to Success", job_id);
 
-        if let Some(graph) = self.remove_active_execution_graph(job_id).await {
+        if let Some(graph) = self.remove_active_execution_graph(job_id) {
             let graph = graph.read().await.clone();
             if graph.is_successful() {
                 self.state.save_job(job_id, &graph).await?;
@@ -376,7 +394,7 @@ impl<T: 'static + AsLogicalPlan, U: 'static + AsExecutionPlan> TaskManager<T, U>
         failure_reason: String,
     ) -> Result<(Vec<RunningTaskInfo>, usize)> {
         let (tasks_to_cancel, pending_tasks) = if let Some(graph) =
-            self.get_active_execution_graph(job_id).await
+            self.get_active_execution_graph(job_id)
         {
             let mut guard = graph.write().await;
 
@@ -416,14 +434,15 @@ impl<T: 'static + AsLogicalPlan, U: 'static + AsExecutionPlan> TaskManager<T, U>
     }
 
     pub async fn update_job(&self, job_id: &str) -> Result<usize> {
-        debug!("Update job {} in Active", job_id);
-        if let Some(graph) = self.get_active_execution_graph(job_id).await {
+        debug!("Update active job {job_id}");
+        if let Some(graph) = self.get_active_execution_graph(job_id) {
             let mut graph = graph.write().await;
 
             let curr_available_tasks = graph.available_tasks();
 
             graph.revive();
-            let graph = graph.clone();
+
+            println!("Saving job with status {:?}", graph.status());
 
             self.state.save_job(job_id, &graph).await?;
 
@@ -461,7 +480,7 @@ impl<T: 'static + AsLogicalPlan, U: 'static + AsExecutionPlan> TaskManager<T, U>
     /// Retrieve the number of available tasks for the given job. The value returned
     /// is strictly a point-in-time snapshot
     pub async fn get_available_task_count(&self, job_id: &str) -> Result<usize> {
-        if let Some(graph) = self.get_active_execution_graph(job_id).await {
+        if let Some(graph) = self.get_active_execution_graph(job_id) {
             let available_tasks = graph.read().await.available_tasks();
             Ok(available_tasks)
         } else {
@@ -620,17 +639,18 @@ impl<T: 'static + AsLogicalPlan, U: 'static + AsExecutionPlan> TaskManager<T, U>
     }
 
     /// Get the `ExecutionGraph` for the given job ID from cache
-    pub(crate) async fn get_active_execution_graph(
+    pub(crate) fn get_active_execution_graph(
         &self,
         job_id: &str,
     ) -> Option<Arc<RwLock<ExecutionGraph>>> {
         self.active_job_cache
             .get(job_id)
-            .map(|value| value.execution_graph.clone())
+            .as_deref()
+            .map(|cached| cached.execution_graph.clone())
     }
 
     /// Remove the `ExecutionGraph` for the given job ID from cache
-    pub(crate) async fn remove_active_execution_graph(
+    pub(crate) fn remove_active_execution_graph(
         &self,
         job_id: &str,
     ) -> Option<Arc<RwLock<ExecutionGraph>>> {
@@ -639,31 +659,6 @@ impl<T: 'static + AsLogicalPlan, U: 'static + AsExecutionPlan> TaskManager<T, U>
             .map(|value| value.1.execution_graph)
     }
 
-    /// Get the `ExecutionGraph` for the given job ID. This will search fist in the `ActiveJobs`
-    /// keyspace and then, if it doesn't find anything, search the `CompletedJobs` keyspace.
-    pub(crate) async fn get_execution_graph(
-        &self,
-        job_id: &str,
-    ) -> Result<ExecutionGraph> {
-        if let Some(active) = self.active_job_cache.get(job_id) {
-            let guard = active.execution_graph.read().await;
-
-            Ok(guard.clone())
-        } else {
-            let graph =
-                self.state
-                    .get_execution_graph(job_id)
-                    .await?
-                    .ok_or_else(|| {
-                        BallistaError::Internal(format!(
-                            "No ExecutionGraph found for job {job_id}"
-                        ))
-                    })?;
-
-            Ok(graph)
-        }
-    }
-
     /// Generate a new random Job ID
     pub fn generate_job_id(&self) -> String {
         let mut rng = thread_rng();
diff --git a/ballista/scheduler/src/test_utils.rs b/ballista/scheduler/src/test_utils.rs
index 36704503..ec3856e4 100644
--- a/ballista/scheduler/src/test_utils.rs
+++ b/ballista/scheduler/src/test_utils.rs
@@ -34,24 +34,27 @@ use crate::state::task_manager::TaskLauncher;
 use ballista_core::config::{BallistaConfig, BALLISTA_DEFAULT_SHUFFLE_PARTITIONS};
 use ballista_core::serde::protobuf::job_status::Status;
 use ballista_core::serde::protobuf::{
-    task_status, JobStatus, MultiTaskDefinition, PhysicalPlanNode, ShuffleWritePartition,
-    SuccessfulTask, TaskId, TaskStatus,
+    task_status, FailedTask, JobStatus, MultiTaskDefinition, PhysicalPlanNode,
+    ShuffleWritePartition, SuccessfulTask, TaskId, TaskStatus,
 };
 use ballista_core::serde::scheduler::{
     ExecutorData, ExecutorMetadata, ExecutorSpecification,
 };
-use ballista_core::serde::BallistaCodec;
+use ballista_core::serde::{protobuf, BallistaCodec};
 use datafusion::arrow::datatypes::{DataType, Field, Schema, SchemaRef};
 use datafusion::common::DataFusionError;
 use datafusion::datasource::{TableProvider, TableType};
 use datafusion::execution::context::{SessionConfig, SessionContext, SessionState};
 use datafusion::logical_expr::{Expr, LogicalPlan};
+use datafusion::physical_plan::display::DisplayableExecutionPlan;
 use datafusion::physical_plan::ExecutionPlan;
-use datafusion::prelude::CsvReadOptions;
+use datafusion::prelude::{col, count, sum, CsvReadOptions, JoinType};
+use datafusion::test_util::scan_empty;
 
 use crate::cluster::BallistaCluster;
 use crate::scheduler_server::event::QueryStageSchedulerEvent;
 
+use crate::state::execution_graph::{ExecutionGraph, TaskDescription};
 use ballista_core::utils::default_session_builder;
 use datafusion_proto::protobuf::LogicalPlanNode;
 use parking_lot::Mutex;
@@ -520,6 +523,46 @@ impl SchedulerTest {
             .await
     }
 
+    pub async fn await_completion_timeout(
+        &self,
+        job_id: &str,
+        timeout_ms: u64,
+    ) -> Result<JobStatus> {
+        let mut time = 0;
+        let final_status: Result<JobStatus> = loop {
+            let status = self
+                .scheduler
+                .state
+                .task_manager
+                .get_job_status(job_id)
+                .await?;
+
+            if let Some(JobStatus {
+                status: Some(inner),
+                ..
+            }) = status.as_ref()
+            {
+                match inner {
+                    Status::Failed(_) | Status::Successful(_) => {
+                        break Ok(status.unwrap())
+                    }
+                    _ => {
+                        if time >= timeout_ms {
+                            break Ok(status.unwrap());
+                        } else {
+                            continue;
+                        }
+                    }
+                }
+            }
+
+            tokio::time::sleep(Duration::from_millis(100)).await;
+            time += 100;
+        };
+
+        final_status
+    }
+
     pub async fn await_completion(&self, job_id: &str) -> Result<JobStatus> {
         let final_status: Result<JobStatus> = loop {
             let status = self
@@ -726,3 +769,264 @@ pub fn assert_failed_event(job_id: &str, collector: &TestMetricsCollector) {
 
     assert!(found, "Expected failed event for job {}", job_id);
 }
+
+pub async fn test_aggregation_plan(partition: usize) -> ExecutionGraph {
+    let config = SessionConfig::new().with_target_partitions(partition);
+    let ctx = Arc::new(SessionContext::with_config(config));
+
+    let schema = Schema::new(vec![
+        Field::new("id", DataType::Utf8, false),
+        Field::new("gmv", DataType::UInt64, false),
+    ]);
+
+    let logical_plan = scan_empty(None, &schema, Some(vec![0, 1]))
+        .unwrap()
+        .aggregate(vec![col("id")], vec![sum(col("gmv"))])
+        .unwrap()
+        .build()
+        .unwrap();
+
+    let optimized_plan = ctx.optimize(&logical_plan).unwrap();
+
+    let plan = ctx.create_physical_plan(&optimized_plan).await.unwrap();
+
+    println!("{}", DisplayableExecutionPlan::new(plan.as_ref()).indent());
+
+    ExecutionGraph::new("localhost:50050", "job", "", "session", plan, 0).unwrap()
+}
+
+pub async fn test_two_aggregations_plan(partition: usize) -> ExecutionGraph {
+    let config = SessionConfig::new().with_target_partitions(partition);
+    let ctx = Arc::new(SessionContext::with_config(config));
+
+    let schema = Schema::new(vec![
+        Field::new("id", DataType::Utf8, false),
+        Field::new("name", DataType::Utf8, false),
+        Field::new("gmv", DataType::UInt64, false),
+    ]);
+
+    let logical_plan = scan_empty(None, &schema, Some(vec![0, 1, 2]))
+        .unwrap()
+        .aggregate(vec![col("id"), col("name")], vec![sum(col("gmv"))])
+        .unwrap()
+        .aggregate(vec![col("id")], vec![count(col("id"))])
+        .unwrap()
+        .build()
+        .unwrap();
+
+    let optimized_plan = ctx.optimize(&logical_plan).unwrap();
+
+    let plan = ctx.create_physical_plan(&optimized_plan).await.unwrap();
+
+    println!("{}", DisplayableExecutionPlan::new(plan.as_ref()).indent());
+
+    ExecutionGraph::new("localhost:50050", "job", "", "session", plan, 0).unwrap()
+}
+
+pub async fn test_coalesce_plan(partition: usize) -> ExecutionGraph {
+    let config = SessionConfig::new().with_target_partitions(partition);
+    let ctx = Arc::new(SessionContext::with_config(config));
+
+    let schema = Schema::new(vec![
+        Field::new("id", DataType::Utf8, false),
+        Field::new("gmv", DataType::UInt64, false),
+    ]);
+
+    let logical_plan = scan_empty(None, &schema, Some(vec![0, 1]))
+        .unwrap()
+        .limit(0, Some(1))
+        .unwrap()
+        .build()
+        .unwrap();
+
+    let optimized_plan = ctx.optimize(&logical_plan).unwrap();
+
+    let plan = ctx.create_physical_plan(&optimized_plan).await.unwrap();
+
+    ExecutionGraph::new("localhost:50050", "job", "", "session", plan, 0).unwrap()
+}
+
+pub async fn test_join_plan(partition: usize) -> ExecutionGraph {
+    let config = SessionConfig::new().with_target_partitions(partition);
+    let ctx = Arc::new(SessionContext::with_config(config));
+
+    let schema = Schema::new(vec![
+        Field::new("id", DataType::Utf8, false),
+        Field::new("gmv", DataType::UInt64, false),
+    ]);
+
+    let left_plan = scan_empty(Some("left"), &schema, None).unwrap();
+
+    let right_plan = scan_empty(Some("right"), &schema, None)
+        .unwrap()
+        .build()
+        .unwrap();
+
+    let sort_expr = Expr::Sort {
+        expr: Box::new(col("id")),
+        asc: false,
+        nulls_first: false,
+    };
+
+    let logical_plan = left_plan
+        .join(&right_plan, JoinType::Inner, (vec!["id"], vec!["id"]), None)
+        .unwrap()
+        .aggregate(vec![col("id")], vec![sum(col("gmv"))])
+        .unwrap()
+        .sort(vec![sort_expr])
+        .unwrap()
+        .build()
+        .unwrap();
+
+    let optimized_plan = ctx.optimize(&logical_plan).unwrap();
+
+    let plan = ctx.create_physical_plan(&optimized_plan).await.unwrap();
+
+    println!("{}", DisplayableExecutionPlan::new(plan.as_ref()).indent());
+
+    let graph =
+        ExecutionGraph::new("localhost:50050", "job", "", "session", plan, 0).unwrap();
+
+    println!("{:?}", graph);
+
+    graph
+}
+
+pub async fn test_union_all_plan(partition: usize) -> ExecutionGraph {
+    let config = SessionConfig::new().with_target_partitions(partition);
+    let ctx = Arc::new(SessionContext::with_config(config));
+
+    let logical_plan = ctx
+        .sql("SELECT 1 as NUMBER union all SELECT 1 as NUMBER;")
+        .await
+        .unwrap()
+        .to_logical_plan()
+        .unwrap();
+
+    let optimized_plan = ctx.optimize(&logical_plan).unwrap();
+
+    let plan = ctx.create_physical_plan(&optimized_plan).await.unwrap();
+
+    println!("{}", DisplayableExecutionPlan::new(plan.as_ref()).indent());
+
+    let graph =
+        ExecutionGraph::new("localhost:50050", "job", "", "session", plan, 0).unwrap();
+
+    println!("{:?}", graph);
+
+    graph
+}
+
+pub async fn test_union_plan(partition: usize) -> ExecutionGraph {
+    let config = SessionConfig::new().with_target_partitions(partition);
+    let ctx = Arc::new(SessionContext::with_config(config));
+
+    let logical_plan = ctx
+        .sql("SELECT 1 as NUMBER union SELECT 1 as NUMBER;")
+        .await
+        .unwrap()
+        .to_logical_plan()
+        .unwrap();
+
+    let optimized_plan = ctx.optimize(&logical_plan).unwrap();
+
+    let plan = ctx.create_physical_plan(&optimized_plan).await.unwrap();
+
+    println!("{}", DisplayableExecutionPlan::new(plan.as_ref()).indent());
+
+    let graph =
+        ExecutionGraph::new("localhost:50050", "job", "", "session", plan, 0).unwrap();
+
+    println!("{:?}", graph);
+
+    graph
+}
+
+pub fn mock_executor(executor_id: String) -> ExecutorMetadata {
+    ExecutorMetadata {
+        id: executor_id,
+        host: "localhost2".to_string(),
+        port: 8080,
+        grpc_port: 9090,
+        specification: ExecutorSpecification { task_slots: 1 },
+    }
+}
+
+pub fn mock_completed_task(task: TaskDescription, executor_id: &str) -> TaskStatus {
+    let mut partitions: Vec<protobuf::ShuffleWritePartition> = vec![];
+
+    let num_partitions = task
+        .output_partitioning
+        .map(|p| p.partition_count())
+        .unwrap_or(1);
+
+    for partition_id in 0..num_partitions {
+        partitions.push(protobuf::ShuffleWritePartition {
+            partition_id: partition_id as u64,
+            path: format!(
+                "/{}/{}/{}",
+                task.partition.job_id,
+                task.partition.stage_id,
+                task.partition.partition_id
+            ),
+            num_batches: 1,
+            num_rows: 1,
+            num_bytes: 1,
+        })
+    }
+
+    // Complete the task
+    protobuf::TaskStatus {
+        task_id: task.task_id as u32,
+        job_id: task.partition.job_id.clone(),
+        stage_id: task.partition.stage_id as u32,
+        stage_attempt_num: task.stage_attempt_num as u32,
+        partition_id: task.partition.partition_id as u32,
+        launch_time: 0,
+        start_exec_time: 0,
+        end_exec_time: 0,
+        metrics: vec![],
+        status: Some(task_status::Status::Successful(protobuf::SuccessfulTask {
+            executor_id: executor_id.to_owned(),
+            partitions,
+        })),
+    }
+}
+
+pub fn mock_failed_task(task: TaskDescription, failed_task: FailedTask) -> TaskStatus {
+    let mut partitions: Vec<protobuf::ShuffleWritePartition> = vec![];
+
+    let num_partitions = task
+        .output_partitioning
+        .map(|p| p.partition_count())
+        .unwrap_or(1);
+
+    for partition_id in 0..num_partitions {
+        partitions.push(protobuf::ShuffleWritePartition {
+            partition_id: partition_id as u64,
+            path: format!(
+                "/{}/{}/{}",
+                task.partition.job_id,
+                task.partition.stage_id,
+                task.partition.partition_id
+            ),
+            num_batches: 1,
+            num_rows: 1,
+            num_bytes: 1,
+        })
+    }
+
+    // Fail the task
+    protobuf::TaskStatus {
+        task_id: task.task_id as u32,
+        job_id: task.partition.job_id.clone(),
+        stage_id: task.partition.stage_id as u32,
+        stage_attempt_num: task.stage_attempt_num as u32,
+        partition_id: task.partition.partition_id as u32,
+        launch_time: 0,
+        start_exec_time: 0,
+        end_exec_time: 0,
+        metrics: vec![],
+        status: Some(task_status::Status::Failed(failed_task)),
+    }
+}