From aa00a19ee2fec7fa130cbd5828aad59574641415 Mon Sep 17 00:00:00 2001 From: Tristan Van Berkom Date: Sat, 13 Oct 2018 20:25:48 +0900 Subject: doc: Adding new architecture document about how the scheduler works. --- doc/source/arch_scheduler.rst | 132 ++++ doc/source/image-sources/arch-scheduler-job.odg | Bin 0 -> 15465 bytes .../image-sources/arch-scheduler-queue-ports.odg | Bin 0 -> 16179 bytes doc/source/image-sources/arch-scheduler-queues.odg | Bin 0 -> 15591 bytes doc/source/image-sources/arch-scheduler-run.odg | Bin 0 -> 14172 bytes doc/source/images/arch-scheduler-job.svg | 750 +++++++++++++++++++++ doc/source/images/arch-scheduler-queue-ports.svg | 318 +++++++++ doc/source/images/arch-scheduler-queues.svg | 488 ++++++++++++++ doc/source/images/arch-scheduler-run.svg | 437 ++++++++++++ doc/source/main_architecture.rst | 1 + 10 files changed, 2126 insertions(+) create mode 100644 doc/source/arch_scheduler.rst create mode 100644 doc/source/image-sources/arch-scheduler-job.odg create mode 100644 doc/source/image-sources/arch-scheduler-queue-ports.odg create mode 100644 doc/source/image-sources/arch-scheduler-queues.odg create mode 100644 doc/source/image-sources/arch-scheduler-run.odg create mode 100644 doc/source/images/arch-scheduler-job.svg create mode 100644 doc/source/images/arch-scheduler-queue-ports.svg create mode 100644 doc/source/images/arch-scheduler-queues.svg create mode 100644 doc/source/images/arch-scheduler-run.svg diff --git a/doc/source/arch_scheduler.rst b/doc/source/arch_scheduler.rst new file mode 100644 index 000000000..bc1a3efcd --- /dev/null +++ b/doc/source/arch_scheduler.rst @@ -0,0 +1,132 @@ + + +Scheduler +========= +The *Scheduler* is what is responsible for running the main event loop and +dispatching *Jobs* to complete tasks on behalf of *Queues*. + + +Jobs +~~~~ +The basic functionality of spawning tasks is implemented by the base Job +class, which is derived in a few ways but for now we'll only talk about the +ElementJob type since that is the most centric. + +The Job class has the following responsibilities: + +* Spawning the given job as a subprocess. + +* Offering an abstract method for subclasses to handle the outcome of + a job when it completes. + +* Forcefully terminating it's subprocess. + +* Suspending and resuming it's subprocess. + +* Declaring the types of resources it will require, and which resources + it will require exclusively. + + +Below is a rough outline of the interactions between the main process +and job specific child process: + +.. image:: images/arch-scheduler-job.svg + :align: center + + +Resources +~~~~~~~~~ +To understand how we manage load balancing in the scheduler it is important +to understand *resources*. + +For the scheduler, *resources* are domains which a Job can request which represent +physical resources, such as the CPU or some network bandwidth, or the local +artifact cache. + +This is used by the Scheduler when consuming Jobs from Queues and deciding +how many jobs can be run at a given time. + + +Queues +~~~~~~ +The various Queue implementations in the Scheduler can be combined such that +parallelism is maximized. For example one can *Track* and *Build* inside the +same session, in this way one does not need to wait for a tracking session to +complete in order to start building. + +The input elements to the scheduler are expected to be sorted in depth first +order whenever the order is important, again allowing maximum parallelism +at build time. + +.. image:: images/arch-scheduler-queues.svg + :align: center + +The Queue implementations are: + +* **Track** + + The tracking queue must always come first if it is used in the given session. + This is because the Source *"ref"*, and consequently the cache key of any elements + which have been requested for tracking, cannot be known until tracking is complete. + +* **Pull** + + The pull queue tries to obtain a built artifact from a remote artifact server, + it should be placed in advance of the fetch queue if used, since we can safely + avoid fetching if fetching is not imerative, and we already have a cached + artifact. + +* **Fetch** + + The fetch queue attempts to download source code to build the given element, + this activity is sometimes skipped if the artifact is already present, or + if the exact source code is already present. + +* **Build** + + The build queue attempts to build the element if it's artifact is not locally + present. + +* **Push** + + The push queue attempts to push the resulting artifact to a remote artifact + server. + + +Queue internals +~~~~~~~~~~~~~~~ +Internally, the queue has an input queue and an output queue. + +.. image:: images/arch-scheduler-queue-ports.svg + :align: center + +When elements are on the input queue they get queried for their *QueueStatus* +in order to determine which elements should be processed or moved from the input +queue to the output queue. When elements are on the output queue, they are ready +to be consumed by the scheduler and moved on to the next queue; however each +queue holds on to the result status of every element which passed through for later +reference and reports to the user. + + +Scheduler +~~~~~~~~~ +The scheduler itself has the main responsibility of popping off jobs from +the existing queues it was given, and running the jobs as long as elements +remain to be processed. + +A huge simplification of this can be visualized as follows: + +.. image:: images/arch-scheduler-run.svg + :align: center + +This is implemented by iterating over the Queues given to the scheduler +and processing any *"Ready"* elements so long as there are sufficient resource +tokens available for the ready elements to run, and by moving the *"Done"* +elements onto the subsequent queues in the list of queues. + +.. note:: + + When looking for *"Ready"* elements in the queues, we iterate over the + queue list in *reverse order*. This is important to allow elements to + get as far as they can in the queue list as fast as possible, and helps + to prevent resource starvation. diff --git a/doc/source/image-sources/arch-scheduler-job.odg b/doc/source/image-sources/arch-scheduler-job.odg new file mode 100644 index 000000000..0171ad553 Binary files /dev/null and b/doc/source/image-sources/arch-scheduler-job.odg differ diff --git a/doc/source/image-sources/arch-scheduler-queue-ports.odg b/doc/source/image-sources/arch-scheduler-queue-ports.odg new file mode 100644 index 000000000..1a13ed316 Binary files /dev/null and b/doc/source/image-sources/arch-scheduler-queue-ports.odg differ diff --git a/doc/source/image-sources/arch-scheduler-queues.odg b/doc/source/image-sources/arch-scheduler-queues.odg new file mode 100644 index 000000000..792890edf Binary files /dev/null and b/doc/source/image-sources/arch-scheduler-queues.odg differ diff --git a/doc/source/image-sources/arch-scheduler-run.odg b/doc/source/image-sources/arch-scheduler-run.odg new file mode 100644 index 000000000..4a596e413 Binary files /dev/null and b/doc/source/image-sources/arch-scheduler-run.odg differ diff --git a/doc/source/images/arch-scheduler-job.svg b/doc/source/images/arch-scheduler-job.svg new file mode 100644 index 000000000..9a50135d8 --- /dev/null +++ b/doc/source/images/arch-scheduler-job.svg @@ -0,0 +1,750 @@ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + Setup signal handlers + + + + + + + + + + + + + Block signals + + + + + + + + + + + + + fork() + + + + + + + + + + + + + Unblock signals + + + + + + + + + + + + + + + + + + + + + + + + + + + Main BuildStream Process + + + + + + Job Process + + + + + + + + + + + + + Initialize subprocess logging redirection + + + + + + + + + + + + + + + + + + + + Unblock selected signals (ready) + + + + + + + + + + + + + + + + + + + + Run the job payload + + + + + + + + + + + + + + + + + + + + Log messages + + + + + + + + + + + + + + + + + + + Start New Job + + + + + + + + + + + + Receive IPC Messages + + + + + + + + + + + + + Report job result and any other state + + + + + + + + + + + + + Collect results on job instance + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + Collect exit status + + + + + + + + + + + + + Exit with symbolic exit status + + + + + + + + + + + + Interruptible Job Harness + + + + + + + + + + + + + Inform the job owner that a job completed, hand over the result + + + + + + + + + + + + + + + + + + + + + + + + + + Job ControlSuspend (SIGTSTP)Resume (SIGCONT)Terminate (SIGTERM)Kill (SIGKILL) + + + + + + + + + + + + + Job Exited + + + + + + + + + + + + + This process is a fork() of the main process without execve().This means it has access to the main process data model at the time of the fork(), any modifications made after this point are copy-on-write, and any side effects of the job need to be manually propagated back to the main process through the IPC. + + + + + + + \ No newline at end of file diff --git a/doc/source/images/arch-scheduler-queue-ports.svg b/doc/source/images/arch-scheduler-queue-ports.svg new file mode 100644 index 000000000..2466551bf --- /dev/null +++ b/doc/source/images/arch-scheduler-queue-ports.svg @@ -0,0 +1,318 @@ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + Processed + + + + + + + + + + + + + Failed + + + + + + + + + + + + + Skipped + + + + + + + + + + + + + + + + + + + Ready + + + + + + + + + + + + + Skip + + + + + + Queue implementations report a “QueueStatus” for all of the elements which are in the input queue at all times.Skip elements go directly to the output queue without processing, and the scheduler only ever processes the Ready elements. + + + + + + + + + + + + + Wait + + + + + + + + + + + + + Elements In + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + Element Processing + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + After elements are either processed or skipped, they move to the Queue’s output queue where the scheduler can pick them up and and move them along to the next Queue.Elements which have passed through a Queue are also kept in status lists for bookkeeping purposes. + + + + + + Input Queue + + + + + + Output Queue + + + + + + + \ No newline at end of file diff --git a/doc/source/images/arch-scheduler-queues.svg b/doc/source/images/arch-scheduler-queues.svg new file mode 100644 index 000000000..8732b9fc4 --- /dev/null +++ b/doc/source/images/arch-scheduler-queues.svg @@ -0,0 +1,488 @@ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + Element + + + + + + + + + + + + + Element + + + + + + + + + + + + + Element + + + + + + + + + + + + + Element + + + + + + Pull + + + + + + + + + + + + + + + + + + + + Element + + + + + + + + + + + + + Element + + + + + + + + + + + + + Element + + + + + + + + + + + + + Element + + + + + + Fetch + + + + + + + + + + + + + + + + + + + + Element + + + + + + + + + + + + + Element + + + + + + + + + + + + + Element + + + + + + + + + + + + + Element + + + + + + Build + + + + + + + + + + + + + + + + + + + + Element + + + + + + + + + + + + + Element + + + + + + + + + + + + + Element + + + + + + + + + + + + + Element + + + + + + Track + + + + + + + + + + + + + + + + + + + + Element + + + + + + + + + + + + + Element + + + + + + + + + + + + + Element + + + + + + + + + + + + + Element + + + + + + Push + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + Elements In + + + + + + + + + + + + + + + + + + + + Elements Out + + + + + + + + + + + + + + \ No newline at end of file diff --git a/doc/source/images/arch-scheduler-run.svg b/doc/source/images/arch-scheduler-run.svg new file mode 100644 index 000000000..e031aa57e --- /dev/null +++ b/doc/source/images/arch-scheduler-run.svg @@ -0,0 +1,437 @@ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + Scheduler.run() + + + + + + + + + + + + + Wait + + + + + + Run Event Loop + + + + + + + + + + + + + Job Done + + + + + + + + ReadyElementsRemain + + + + + + + + + + + + + QueueJobs + + + + + + + + + + + + + + + + + + + + Yes + + + + + + + + + + + + + + + + + + + + Return + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + No + + + + + + + \ No newline at end of file diff --git a/doc/source/main_architecture.rst b/doc/source/main_architecture.rst index 6e284f31e..7c13e41d6 100644 --- a/doc/source/main_architecture.rst +++ b/doc/source/main_architecture.rst @@ -12,3 +12,4 @@ This section provides details on the overall BuildStream architecture. arch_program_flow arch_data_model arch_dependency_model + arch_scheduler -- cgit v1.2.1