Representing ballerina concurrency model on top of go routines

[heshanpadmasiri]

Objectives

• Come up with a representation that allows us to represent multiple strands on same thread
• Come up with an API design that allow extern functions to yield the current strand

Non objectives

• Writing our own thread scheduler on top of os threads.

---

Ballerina strands don't directly map to go routines directly. Ballerina strands associate back to a thread where only one strand associated with a given thread can be executed in parallel. Where as with a go routine after you start one they can run in parallel with any other routine

In most cases this subtlety is not distinguishable, given strands are considered to be running on parallel threads (example: dispatching calls to isolated resource functions). But this becomes a problem with start actions. Consider

import ballerina/io;
import ballerina/lang.runtime;

public function main() returns error? {
    int[] vals = [];
    var f1 = start nonIsolatedFunction1(vals);
    var f2 = start nonIsolatedFunction2(vals);
    var f3 = start nonIsolatedFunction3(vals);
    var f4 = start nonIsolatedFunction4(vals);
    var result = wait {f1, f2, f3, f4};
    io:println(result);
    io:println(vals);
}

function nonIsolatedFunction1(int[] arr) {
    arr.push(1);
    runtime:sleep(10);
}

function nonIsolatedFunction2(int[] arr) {
    arr.push(2);
    runtime:sleep(20);
}

function nonIsolatedFunction3(int[] arr) {
    arr.push(3);
    runtime:sleep(30);
}

function nonIsolatedFunction4(int[] arr) {
    arr.push(4);
    runtime:sleep(40);
}

According to the spec https://ballerina.io/spec/lang/master/#section_7.6 each nonIsolatedFunction* runs on it's own strand but in the same thread. This means at a given time only one of main, nonIsolatedFunction* strands should be running at the same time at each yield point (wait, runtime:sleep) we should be able to start/resume other strand.

Also extern functions should be able to yield their strand and hand control to runtime. We need to expose a way to do this in extern.context

[heshanpadmasiri]

Also I couldn't think of valid Ballerina code that can do this but there may be a way to do this. Where you start 2 threads and in each you span multiple strands that needs to run within that thread.

[heshanpadmasiri]

I think the correct abstraction is for threads to be represented with go routines. In most cases each strand has it's own thread. Spec makes no guarantee about the scheduling of such threads.

But within a thread scheduling of strand has to be done by us, according to https://ballerina.io/spec/lang/master/#section_7.2. This require us 3 things

1. Ability to scheduling a computation to be started at a yield point

This is entirely in control of the runtime and don't need to be exposed to extern functions. We need this to implement non isolated start actions. Since start action is not a yield point we can start the computation at start action we need to delay it until we have reached a yield point in the same thread such as join or extern function calling yeild.

2. Abilty to yield a computation

This needs to be exposed to extern functions as well. I feel like ideally it should look something like

func externFn(cx *context, args []BalValues) (BalValue, error) {
    cx.yeild() // If we are going to represent each thread as go routine, thus each strand needs to be implemented as it's own computation in the same go routine
    <- cx.yeild() // if we are representing each strand also as a go routine
}

3. Ability to resume a computation

I think it is necessary to support the fallowing sequence in the same thread

1. parent strand start
2. parent yeild -> child strand starts
3. child strand yeild -> parent strand resume
4. parent yeild -> child strand resume

---

Personally I don't like the idea of representing both threads and strands as go routines. Given as far as go runtime is concerned it can run go routines in parallel this can introduce a foot gun where we can accidently run to strands belonging to the same thread in parallel. Most of the ways I can think of avoid this require us the ability to control 3. For instance if we simply use lock that all strands in a given thread must share we can allow strands to yield but we can give cooperative multitasking as required by the spec. It is entirely possible same thread keep acquiring the lock

At the same time I can see a way to support 3 without modelling strands as go routines that allow 3

[heshanpadmasiri]

Supporting order guarantees in alternate wait

According to the spec https://ballerina.io/spec/lang/master/#alternate-wait-action, for error case "As soon as one of the wait operations completes normally with a non-error value v, the alternate-wait-action completes normally with result v. If all of the wait operations complete normally with an error, then it completes normally with result e, where e is the result of the last wait operation to complete." This is non trivial when all the futures has been completed by the time we get the alternate wait. For this to work according to spec each future should be able to tell the order in which it was completed relative to the other future.

[heshanpadmasiri]

I think there are 2 obvious ways to implement this

1. Each future has a monotonically increasing counter.
2. Each future has a monotonically increasing time stamp.

Both are very similar and have to draw back of both these counters going to overflow first one at maximum u64 and second one when unix time overflow.

First has the limitation that every completion of a future needs to be synchronised. Where as second while not locking in the user space has the limitation that monotonic time is not guranteed to be increasing. So we can have 2 futures with the same completion time. Also it may be internally locking to give monotonic guranteess in some hardware but I assume it uses the hardware clocks in systems that matter which implement this locking in hardware level

[heshanpadmasiri]

Looking at the generated assembly https://godbolt.org/z/c3vEEG8qn, I think an atomic i64 is better

[warunalakshitha]

The old Java-based compiler used two different approaches for handling strands.

Approach 01: Ballerina Strand Scheduler

1. A strand behaved like a green (application-level) thread and was not mapped directly to a Java thread.
2. We had the concept of strand groups, where all strands belonging to the same group always executed on the same Java thread.
3. Isolated execution was always assigned to the same global strand group.
4. Worker interaction and the wait mechanism were implemented using queues and locks.
5. Java threads acted like OS threads, and execution was managed by a configurable thread pool.
6. Strand yielding and resuming were implemented by generating switch cases based on the idea behind Duff's Device (https://en.wikipedia.org/wiki/Duff%27s_device). This allowed execution to resume from a specific case number.
7. However, this significantly increased the size of the generated code because every function call required a separate case. As a result, we frequently encountered "method too large" errors for larger functions.
8. Configuring and managing the thread pool also introduced additional overhead.

Approach 02: Mapping Strands to Java Threads (Java 21 Support)

1. Each Ballerina strand was mapped directly to a Java virtual thread.
2. A Ballerina future was mapped to a compatible Java Future.
3. Worker interactions and wait all/wait any semantics were mapped to corresponding Java synchronization mechanisms.
4. For isolated execution, all execution went through a global lock.

We need to ensure that isolated execution does not become serialized unnecessarily. These kind of cases should work

import ballerina/io;
import ballerina/lang.runtime;

public function main() returns error? {
    int[] vals = [];
    var f2 = start nonIsolatedFunction2(vals);
    var f1 = start nonIsolatedFunction1(vals);
    var result = wait f1 | f2;
    io:println(result);
}

function nonIsolatedFunction1(int[] arr) {
    arr.push(1);
    runtime:sleep(10);
}

function nonIsolatedFunction2(int[] arr) {
    arr.push(2);
    runtime:sleep(20);
}

output [1]

Strand scheduling does not always need to follow the same approacesh as jBallerina. Since we are building an interpreter, we have much more control over execution.

[heshanpadmasiri]

I also wonder if fallowing should produce an error

import ballerina/io;

function number(int value) returns int {
    return value;
}

public function main() {
    future<int> before = start number(1);
    future<int> consumed = start number(2);

    int|error first = wait consumed;

    var alternate = wait before | consumed;
}

AFAIK spec only gives completion order guarantees when all the alternate waits as error. So there is no requirement for us to check if consumed is ready if before is also ready with a non error value.

For example this is always an error

import ballerina/io;

function number(int value) returns int|error {
    if value == 1 {
      return error("2");
    }
    return value;
}

public function main() {
    future<int|error> before = start number(1);
    future<int|error> consumed = start number(2);

    int|error first = wait consumed;
    io:println(first);

    var alternate = wait before | consumed;
    io:println(alternate);
}

[heshanpadmasiri]

Implemented in #427