Wednesday, April 22, 2020

Thesis Proposal - Lightweight Preemptable Functions

Sol Boucher presented his thesis proposal today via Zoom.  It was well attended and I think many of us are already looking forward to his defense.

Lightweight Preemptable Functions (LPF)
Function calls require some knowledge of the cost for a program to know whether it can invoke it or not in other time critical execution.

In the current space of multitasking, three approaches will be first reviewed: futures, threads, and processes.  Futures rely on the runtime to provide asynchronous execution, but preemption requires yield points, and not all execution can support these points, nor can it be clear what this future will do.  With threads, execution is fairly independent, but minimal information is provided toward scheduling and cancellation is hard.  Processes provide good support for cancellation, except that on fork(), only one thread is required to be carried over in the new process.  The other threads are canceled, which can result in inconsistent state.

The thesis proposal is: Introducing a novel abstraction for preemption at the granularity of a synchronous function call, which includes a timeout.

launch(function, timeout, argument) returning a continuation.  If the timeout elapses, the continuation is returned, but it is then the choice of the caller for whether to resume it or cancel.  This LPF executes within the same thread context as the caller, thereby reducing overhead.  However, to resume the LPF, it will need a new stack.  To support the timeout, it relies on a timer signal that can occur every ~5 microseconds.  Launch / resume have overhead comparable to this, significantly better than fork or pthread_create.  However, cancel is extremely expensive.

LPFs also have an issue with calling functions that are non-reentrant, similar to the rules governing signal handlers.  To address this, the runtime provides selective relinking to capture what the LPF is calling via the global offset table (GOT).  Some GOT entries point to dynamic libraries, other entries are initially pointing to the dynamic linker.  This runtime support also needs to intercept thread local variables.  This interception support imposes about 10ns of  overhead, which is little above the cost of function calls themselves.

Microservice approaches have significant latency, often tends to hundreds of microseconds.  Primarily the requirement to create a sufficient container, often via processes or virtualization.  If the microservice was instead written safely and using LPFs, then the latency could be reduced toward the hardware bound as measured by communicating between VMs or committing transactions.

Cancellation cleanup is difficult in languages, such as C, that require explicit cleanup.  In other languages, adding a new exception path for timeout and cancellation could then invoke the necessary destructors.  Nonetheless, this can be expensive (perhaps single milliseconds).

Other possible future work:
Another cancellation step is the cost of unloading the mirrored library, so could the runtime instead track the changes made and then determine whether to roll back or discard.
Is it possible to reduce the overhead of the preemption signals or improving their granularity.

No comments: