{"id":{"repo_id":"cambridge","oai_identifier":"oai:www.repository.cam.ac.uk:1810/376471"},"canonical_url":"https://search.dev.ndltd.org/etd/cambridge/oai:www.repository.cam.ac.uk:1810/376471","repository":{"repo_id":"cambridge","name":"Cambridge University","base_url":"https://api.repository.cam.ac.uk/server/oai/request"},"display":{"title":"Scheduling for Reduced Tail Task Latencies in Highly Utilised Datacenters","abstract":"Modern datacenters have become the backbone for running diverse workloads that increasingly comprise data-parallel computational jobs. Due to the ease of use and diversity of resources they host there has been a rise in the demand for datacenters leading to high volumes of traffic. Datacenters execute thousands of jobs by scheduling billions of tasks every day. To meet these demands, datacenter providers operate their clusters at levels of high utilisation. We show that under such conditions existing scheduling designs impose 3x larger wait times on tail tasks, that is, tasks that finish the last among tasks of jobs. This leads to large tail task completion times and consequently, elevated job completion times. In this dissertation, we propose a new decentralised scheduling model, Murmuration, that uses multiple communicating scheduler instances to ensure tasks are scheduled in a manner that reduces their total wait times. It achieves this by scheduling all tasks of a job such that their start times are as close together as possible, thereby ensuring small tail task completion times and better average job completion times. Our evaluation of Murmuration using publicly available workloads on a real-world cluster shows a median job completion time that is 15 --- 25% less than that of the default Kubernetes scheduler under both bursty and normal request arrival rates, reducing the median completion times by a fourth. We show that Murmuration scales to incoming workloads by scheduling more than a million tasks in a matter of minutes and exhibits a near-constant scheduling time for tasks even in very large scheduler deployments. We further enhance the design of Murmuration by incorporating queue re-ordering techniques for both scheduling jobs and executing tasks. Simulations show that with shortest remaining job first policy Murmuration outperforms other schedulers with a median job completion time that is 100x better than that of the current schedulers when evaluated on two industry workloads. Murmuration is also capable of handling scheduler failures with a performance impact of a mere 0.17% increase in job completion times at the 99th percentile. Moreover, increasing the number of scheduler instances in Murmuration improves its performance by reducing the total wait times of jobs assigned to the new schedulers.","abstract_html":"Modern datacenters have become the backbone for running diverse workloads that increasingly comprise data-parallel computational jobs. Due to the ease of use and diversity of resources they host there has been a rise in the demand for datacenters leading to high volumes of traffic. Datacenters execute thousands of jobs by scheduling billions of tasks every day. To meet these demands, datacenter providers operate their clusters at levels of high utilisation. We show that under such conditions existing scheduling designs impose 3x larger wait times on tail tasks, that is, tasks that finish the last among tasks of jobs. This leads to large tail task completion times and consequently, elevated job completion times. In this dissertation, we propose a new decentralised scheduling model, Murmuration, that uses multiple communicating scheduler instances to ensure tasks are scheduled in a manner that reduces their total wait times. It achieves this by scheduling all tasks of a job such that their start times are as close together as possible, thereby ensuring small tail task completion times and better average job completion times. Our evaluation of Murmuration using publicly available workloads on a real-world cluster shows a median job completion time that is 15 --- 25% less than that of the default Kubernetes scheduler under both bursty and normal request arrival rates, reducing the median completion times by a fourth. We show that Murmuration scales to incoming workloads by scheduling more than a million tasks in a matter of minutes and exhibits a near-constant scheduling time for tasks even in very large scheduler deployments. We further enhance the design of Murmuration by incorporating queue re-ordering techniques for both scheduling jobs and executing tasks. Simulations show that with shortest remaining job first policy Murmuration outperforms other schedulers with a median job completion time that is 100x better than that of the current schedulers when evaluated on two industry workloads. Murmuration is also capable of handling scheduler failures with a performance impact of a mere 0.17% increase in job completion times at the 99th percentile. Moreover, increasing the number of scheduler instances in Murmuration improves its performance by reducing the total wait times of jobs assigned to the new schedulers.","abstract_has_math":false,"creators":["Vijaya Kumar, Smita"],"institution":"University of Cambridge","degree_name":"Doctor of Philosophy (PhD)","degree_level":"Doctoral","degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":["Kalyvianaki, Evangelia"],"committee_chairs":[],"committee_members":[],"year":2024,"date_issued":"2024-01-31","date_published":"2024-01-31","updated_at":"2026-07-22T22:24:13Z","subjects":["datacenters","highly utilised","job scheduling","tail task latency"],"languages":["eng"],"rights":[],"rights_urls":["https://apollo8-f-pro.lib.cam.ac.uk/bitstreams/6474e4f7-10a9-40d0-a449-4c99b7c6c080/download","https://www.rioxx.net/licenses/all-rights-reserved/"],"identifier_entries":[]},"links":{"outbound_url":"https://doi.org/10.17863/CAM.113695","outbound_label":"DOI","outbound_source":"dc:identifier.doi"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Kalyvianaki, Evangelia"]},{"key":"dc:creator","label":"Author","values":["Vijaya Kumar, Smita"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.issued","label":"Date","values":["2024-01-31"]},{"key":"dc:publisher.institution","label":"Dc Publisher Institution","values":["University of Cambridge"]},{"key":"dc:relation.isreferencedby.uri","label":"Dc Relation Isreferencedby URI","values":["https://www.repository.cam.ac.uk/handle/1810/376471"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]},{"key":"dc:type.qualificationlevel","label":"Dc Type Qualificationlevel","values":["Doctoral"]},{"key":"dc:type.qualificationname","label":"Dc Type Qualificationname","values":["Doctor of Philosophy (PhD)"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["datacenters","highly utilised","job scheduling","tail task latency"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["https://apollo8-f-pro.lib.cam.ac.uk/bitstreams/6474e4f7-10a9-40d0-a449-4c99b7c6c080/download","https://www.rioxx.net/licenses/all-rights-reserved/"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.doi","label":"DOI","values":["https://doi.org/10.17863/CAM.113695"]},{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://apollo8-f-pro.lib.cam.ac.uk/bitstreams/a7543b7e-fbfc-4ae3-aeb0-23880ac5d089/download"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["Modern datacenters have become the backbone for running diverse workloads that increasingly comprise data-parallel computational jobs. Due to the ease of use and diversity of resources they host there has been a rise in the demand for datacenters leading to high volumes of traffic. Datacenters execute thousands of jobs by scheduling billions of tasks every day. To meet these demands, datacenter providers operate their clusters at levels of high utilisation. We show that under such conditions existing scheduling designs impose 3x larger wait times on tail tasks, that is, tasks that finish the last among tasks of jobs. This leads to large tail task completion times and consequently, elevated job completion times. In this dissertation, we propose a new decentralised scheduling model, Murmuration, that uses multiple communicating scheduler instances to ensure tasks are scheduled in a manner that reduces their total wait times. It achieves this by scheduling all tasks of a job such that their start times are as close together as possible, thereby ensuring small tail task completion times and better average job completion times. Our evaluation of Murmuration using publicly available workloads on a real-world cluster shows a median job completion time that is 15 --- 25% less than that of the default Kubernetes scheduler under both bursty and normal request arrival rates, reducing the median completion times by a fourth. We show that Murmuration scales to incoming workloads by scheduling more than a million tasks in a matter of minutes and exhibits a near-constant scheduling time for tasks even in very large scheduler deployments. We further enhance the design of Murmuration by incorporating queue re-ordering techniques for both scheduling jobs and executing tasks. Simulations show that with shortest remaining job first policy Murmuration outperforms other schedulers with a median job completion time that is 100x better than that of the current schedulers when evaluated on two industry workloads. Murmuration is also capable of handling scheduler failures with a performance impact of a mere 0.17% increase in job completion times at the 99th percentile. Moreover, increasing the number of scheduler instances in Murmuration improves its performance by reducing the total wait times of jobs assigned to the new schedulers."]},{"key":"dc:format.checksum.md5","label":"Dc Format Checksum Md5","values":["b6075522f1fcb713b7de7d8b3e5f647b","87eda9de84448d1f82354d60eee3eb5f"]},{"key":"dc:title","label":"Title","values":["Scheduling for Reduced Tail Task Latencies in Highly Utilised Datacenters"]}]}],"canonical_facts":{"dc:contributor.advisor":["Kalyvianaki, Evangelia"],"dc:creator":["Vijaya Kumar, Smita"],"dc:date.issued":["2024-01-31"],"dc:description.abstract":["Modern datacenters have become the backbone for running diverse workloads that increasingly comprise data-parallel computational jobs. Due to the ease of use and diversity of resources they host there has been a rise in the demand for datacenters leading to high volumes of traffic. Datacenters execute thousands of jobs by scheduling billions of tasks every day. To meet these demands, datacenter providers operate their clusters at levels of high utilisation. We show that under such conditions existing scheduling designs impose 3x larger wait times on tail tasks, that is, tasks that finish the last among tasks of jobs. This leads to large tail task completion times and consequently, elevated job completion times. In this dissertation, we propose a new decentralised scheduling model, Murmuration, that uses multiple communicating scheduler instances to ensure tasks are scheduled in a manner that reduces their total wait times. It achieves this by scheduling all tasks of a job such that their start times are as close together as possible, thereby ensuring small tail task completion times and better average job completion times. Our evaluation of Murmuration using publicly available workloads on a real-world cluster shows a median job completion time that is 15 --- 25% less than that of the default Kubernetes scheduler under both bursty and normal request arrival rates, reducing the median completion times by a fourth. We show that Murmuration scales to incoming workloads by scheduling more than a million tasks in a matter of minutes and exhibits a near-constant scheduling time for tasks even in very large scheduler deployments. We further enhance the design of Murmuration by incorporating queue re-ordering techniques for both scheduling jobs and executing tasks. Simulations show that with shortest remaining job first policy Murmuration outperforms other schedulers with a median job completion time that is 100x better than that of the current schedulers when evaluated on two industry workloads. Murmuration is also capable of handling scheduler failures with a performance impact of a mere 0.17% increase in job completion times at the 99th percentile. Moreover, increasing the number of scheduler instances in Murmuration improves its performance by reducing the total wait times of jobs assigned to the new schedulers."],"dc:format.checksum.md5":["b6075522f1fcb713b7de7d8b3e5f647b","87eda9de84448d1f82354d60eee3eb5f"],"dc:identifier.doi":["https://doi.org/10.17863/CAM.113695"],"dc:identifier.uri":["https://apollo8-f-pro.lib.cam.ac.uk/bitstreams/a7543b7e-fbfc-4ae3-aeb0-23880ac5d089/download"],"dc:language":["eng"],"dc:publisher.institution":["University of Cambridge"],"dc:relation.isreferencedby.uri":["https://www.repository.cam.ac.uk/handle/1810/376471"],"dc:rights":["https://apollo8-f-pro.lib.cam.ac.uk/bitstreams/6474e4f7-10a9-40d0-a449-4c99b7c6c080/download","https://www.rioxx.net/licenses/all-rights-reserved/"],"dc:subject":["datacenters","highly utilised","job scheduling","tail task latency"],"dc:title":["Scheduling for Reduced Tail Task Latencies in Highly Utilised Datacenters"],"dc:type":["Thesis"],"dc:type.qualificationlevel":["Doctoral"],"dc:type.qualificationname":["Doctor of Philosophy (PhD)"]},"updated_at":"2026-07-22T22:24:13Z"}