elastic_scheduler.py 12.6 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
# Copyright (c) 2017, Daniele Venzano
#
# Licensed 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.

"""
The Elastic scheduler is the implementation of the scheduling algorithm presented in this paper:
https://arxiv.org/abs/1611.09528
"""

from collections import namedtuple
import logging
import threading
import time

26
from zoe_lib.state import Execution, SQLManager, Service
27
from zoe_master.exceptions import ZoeException
28

29
from zoe_master.backends.interface import terminate_execution, get_platform_state, start_elastic, start_essential, update_service_resource_limits
30 31
from zoe_master.scheduler.simulated_platform import SimulatedPlatform
from zoe_master.exceptions import UnsupportedSchedulerPolicyError
32
from zoe_master.stats import NodeStats
33 34 35 36

log = logging.getLogger(__name__)

ExecutionProgress = namedtuple('ExecutionProgress', ['last_time_scheduled', 'progress_sequence'])
37
SELF_TRIGGER_TIMEOUT = 60  # the scheduler will trigger itself periodically in case platform resources have changed outside its control
38 39 40 41 42 43 44 45 46 47


class ZoeElasticScheduler:
    """The Scheduler class for size-based scheduling. Policy can be "FIFO" or "SIZE"."""
    def __init__(self, state: SQLManager, policy):
        if policy != 'FIFO' and policy != 'SIZE':
            raise UnsupportedSchedulerPolicyError
        self.trigger_semaphore = threading.Semaphore(0)
        self.policy = policy
        self.queue = []
48
        self.queue_running = []
49 50 51
        self.additional_exec_state = {}
        self.async_threads = []
        self.loop_quit = False
Daniele Venzano's avatar
Daniele Venzano committed
52
        self.loop_th = threading.Thread(target=self._thread_wrapper, name='scheduler')
53 54
        self.loop_th.start()
        self.state = state
55 56 57 58 59
        for execution in self.state.execution_list(status='running'):
            if execution.all_services_running:
                self.queue_running.append(execution)
            else:
                self.queue.append(execution)
60
                self.additional_exec_state[execution.id] = ExecutionProgress(0, [])
61 62 63 64 65 66 67

    def trigger(self):
        """Trigger a scheduler run."""
        self.trigger_semaphore.release()

    def incoming(self, execution: Execution):
        """
68
        This method adds the execution to the end of the queue and triggers the scheduler.
69 70 71 72 73
        :param execution: The execution
        :return:
        """
        exec_data = ExecutionProgress(0, [])
        self.additional_exec_state[execution.id] = exec_data
74
        self.queue.append(execution)
75 76 77 78 79 80 81 82 83 84 85
        self.trigger()

    def terminate(self, execution: Execution) -> None:
        """
        Inform the master that an execution has been terminated. This can be done asynchronously.
        :param execution: the terminated execution
        :return: None
        """
        def async_termination(e):
            """Actual termination runs in a thread."""
            with e.termination_lock:
86 87 88 89 90
                try:
                    terminate_execution(e)
                except ZoeException as ex:
                    log.error('Error in termination thread: {}'.format(ex))
                    return
91
                self.trigger()
92
            self._adjust_core_limits()
93 94 95 96 97
            log.debug('Execution {} terminated successfully'.format(e.id))

        try:
            self.queue.remove(execution)
        except ValueError:
98 99 100 101
            try:
                self.queue_running.remove(execution)
            except ValueError:
                log.error('Terminating execution {} that is not in any queue'.format(execution.id))
102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119

        try:
            del self.additional_exec_state[execution.id]
        except KeyError:
            pass

        th = threading.Thread(target=async_termination, name='termination_{}'.format(execution.id), args=(execution,))
        th.start()
        self.async_threads.append(th)

    def _cleanup_async_threads(self):
        counter = len(self.async_threads)
        while counter > 0:
            if len(self.async_threads) == 0:
                break
            th = self.async_threads.pop(0)
            th.join(0.1)
            if th.isAlive():  # join failed
120
                # log.debug('Thread {} join failed'.format(th.name))
121 122 123 124 125 126 127 128 129
                self.async_threads.append(th)
            counter -= 1

    def _refresh_execution_sizes(self):
        for execution in self.queue:  # type: Execution
            exec_data = self.additional_exec_state[execution.id]
            if exec_data.last_time_scheduled == 0:
                progress = 0
            else:
130
                last_progress = (time.time() - exec_data.last_time_scheduled) / ((execution.services_count / execution.running_services_count) * execution.size)
131 132
                exec_data.progress_sequence.append(last_progress)
                progress = sum(exec_data.progress_sequence)
133
            remaining_execution_time = (1 - progress) * execution.size
134 135 136 137 138 139 140 141 142 143 144 145 146 147
            execution.size = remaining_execution_time * execution.services_count

    def _pop_all_with_same_size(self):
        out_list = []
        while len(self.queue) > 0:
            job = self.queue.pop(0)  # type: Execution
            ret = job.termination_lock.acquire(blocking=False)
            if ret and job.status != Execution.TERMINATED_STATUS:
                out_list.append(job)
            else:
                log.debug('While popping, throwing away execution {} that has the termination lock held'.format(job.id))

        return out_list

Daniele Venzano's avatar
Daniele Venzano committed
148 149 150 151 152 153 154 155 156 157
    def _thread_wrapper(self):
        while True:
            try:
                self.loop_start_th()
            except BaseException:  # pylint: disable=broad-except
                log.exception('Unmanaged exception in scheduler loop')
            else:
                log.debug('Scheduler thread terminated')
                break

158 159
    def loop_start_th(self):
        """The Scheduler thread loop."""
160
        auto_trigger = SELF_TRIGGER_TIMEOUT
161
        while True:
Daniele Venzano's avatar
Daniele Venzano committed
162 163 164 165 166
            ret = self.trigger_semaphore.acquire(timeout=1)
            if not ret:  # Semaphore timeout, do some thread cleanup
                self._cleanup_async_threads()
                auto_trigger -= 1
                if auto_trigger == 0:
167
                    auto_trigger = SELF_TRIGGER_TIMEOUT
Daniele Venzano's avatar
Daniele Venzano committed
168 169 170 171
                    self.trigger()
                continue
            if self.loop_quit:
                break
172

Daniele Venzano's avatar
Daniele Venzano committed
173 174 175 176
            if len(self.queue) == 0:
                log.debug("Scheduler loop has been triggered, but the queue is empty")
                continue
            log.debug("Scheduler loop has been triggered")
177

Daniele Venzano's avatar
Daniele Venzano committed
178 179
            while True:  # Inner loop will run until no new executions can be started or the queue is empty
                self._refresh_execution_sizes()
180

Daniele Venzano's avatar
Daniele Venzano committed
181 182
                if self.policy == "SIZE":
                    self.queue.sort(key=lambda execution: execution.size)
183

Daniele Venzano's avatar
Daniele Venzano committed
184 185 186 187 188 189 190 191 192 193
                log.debug('--> Queue dump after sorting')
                for j in self.queue:
                    log.debug(str(j))
                log.debug('--> End dump')

                jobs_to_attempt_scheduling = self._pop_all_with_same_size()
                log.debug('Scheduler inner loop, jobs to attempt scheduling:')
                for job in jobs_to_attempt_scheduling:
                    log.debug("-> {}".format(job))

194
                try:
195
                    platform_state = get_platform_state(self.state)
196 197 198 199 200 201 202
                except ZoeException:
                    log.error('Cannot retrieve platform state, cannot schedule')
                    for job in jobs_to_attempt_scheduling:
                        job.termination_lock.release()
                    self.queue = jobs_to_attempt_scheduling + self.queue
                    break

Daniele Venzano's avatar
Daniele Venzano committed
203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230
                cluster_status_snapshot = SimulatedPlatform(platform_state)
                log.debug(str(cluster_status_snapshot))

                jobs_to_launch = []
                free_resources = cluster_status_snapshot.aggregated_free_memory()

                # Try to find a placement solution using a snapshot of the platform status
                for job in jobs_to_attempt_scheduling:  # type: Execution
                    jobs_to_launch_copy = jobs_to_launch.copy()

                    # remove all elastic services from the previous simulation loop
                    for job_aux in jobs_to_launch:  # type: Execution
                        cluster_status_snapshot.deallocate_elastic(job_aux)

                    job_can_start = False
                    if not job.is_running:
                        job_can_start = cluster_status_snapshot.allocate_essential(job)

                    if job_can_start or job.is_running:
                        jobs_to_launch.append(job)

                    # Try to put back the elastic services
                    for job_aux in jobs_to_launch:
                        cluster_status_snapshot.allocate_elastic(job_aux)

                    current_free_resources = cluster_status_snapshot.aggregated_free_memory()
                    if current_free_resources >= free_resources:
                        jobs_to_launch = jobs_to_launch_copy
231
                        break
Daniele Venzano's avatar
Daniele Venzano committed
232 233
                    free_resources = current_free_resources

234 235
                placements = cluster_status_snapshot.get_service_allocation()
                log.debug('Allocation after simulation: {}'.format(placements))
Daniele Venzano's avatar
Daniele Venzano committed
236 237 238 239

                # We port the results of the simulation into the real cluster
                for job in jobs_to_launch:  # type: Execution
                    if not job.essential_services_running:
240
                        ret = start_essential(job, placements)
Daniele Venzano's avatar
Daniele Venzano committed
241 242 243 244 245 246 247 248
                        if ret == "fatal":
                            jobs_to_attempt_scheduling.remove(job)
                            continue  # trow away the execution
                        elif ret == "requeue":
                            self.queue.insert(0, job)
                            continue
                        elif ret == "ok":
                            job.set_running()
249

Daniele Venzano's avatar
Daniele Venzano committed
250 251
                        assert ret == "ok"

252
                    start_elastic(job, placements)
Daniele Venzano's avatar
Daniele Venzano committed
253 254 255 256 257 258 259

                    if job.all_services_active:
                        log.debug('execution {}: all services are active'.format(job.id))
                        job.termination_lock.release()
                        jobs_to_attempt_scheduling.remove(job)
                        self.queue_running.append(job)

260 261
                self._adjust_core_limits()

Daniele Venzano's avatar
Daniele Venzano committed
262 263 264 265 266 267 268 269 270 271 272 273
                for job in jobs_to_attempt_scheduling:
                    job.termination_lock.release()
                    # self.queue.insert(0, job)

                self.queue = jobs_to_attempt_scheduling + self.queue

                if len(self.queue) == 0:
                    log.debug('empty queue, exiting inner loop')
                    break
                if len(jobs_to_launch) == 0:
                    log.debug('No executions could be started, exiting inner loop')
                    break
274 275 276 277 278 279 280 281 282

    def quit(self):
        """Stop the scheduler thread."""
        self.loop_quit = True
        self.trigger()
        self.loop_th.join()

    def stats(self):
        """Scheduler statistics."""
283 284 285 286 287
        if self.policy == "SIZE":
            queue = sorted(self.queue, key=lambda execution: execution.size)
        else:
            queue = self.queue

288 289
        return {
            'queue_length': len(self.queue),
290
            'running_length': len(self.queue_running),
291 292
            'termination_threads_count': len(self.async_threads),
            'queue': [s.id for s in queue],
293
            'running_queue': [s.id for s in self.queue_running]
294
        }
295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314

    def _adjust_core_limits(self):
        stats = get_platform_state(self.state)
        for node in stats.nodes:  # type: NodeStats
            if len(node.services) == 0:
                continue
            new_core_allocations = {}
            core_sum = 0
            for service in node.services:  # type: Service
                new_core_allocations[service.id] = service.resource_reservation.cores.min
                core_sum += service.resource_reservation.cores.min

            if core_sum < node.cores_total:
                cores_free = node.cores_total - core_sum
                cores_to_add = cores_free / len(node.services)
            else:
                cores_to_add = 0

            for service in node.services:  # type: Service
                update_service_resource_limits(service, cores=new_core_allocations[service.id] + cores_to_add)