Designing a single-threaded, asynchronous, and highly concurrent engine

I got this question while interviewing for the MTS (Member of Technical Staff) position at a reputed startup. They asked me to write the theoretical architecture implementation of a single-threaded, asynchronous, and highly concurrent engine.

Below is the explanation and procedure that I followed.

Flow of code

First of all, we need to understand the flow of execution of the code and the intermediate steps involved in it.

There will be three steps involved majorly:

1. The source code will be first broken into tokens and parsed into an AST with the help of a syntax parser. The code will now be in the form of an Abstract Syntax Tree.

2. After that, this AST will go to the interpreter for compilation. It will get converted into bytecode for further processing.

3. The bytecode generated above will be sent to the main thread for execution and executed inside the call stack.

Single-threaded Concurrency model

Since our motive here is to make the engine single-threaded, we will have only one thread for the execution of the tasks. We won't be able to run multiple tasks parallelly. If any CPU-intensive task is there, it will block the execution of further tasks causing the system to collapse or hang. So we need to keep the architecture such that it becomes non-blocking.

The concurrency model shown in the figure above has three significant components.

1. Call Stack

   The frames of the function calls form a stack. At the start of the program, Global Execution Context is created. After that, according to the function calls, a new frame is created to execute it. Being a stack, it supports LIFO (Last in, first out).

2. Memory Heap

   Inside the memory heap, memory is allocated to the objects and variables present inside the code. The memory is allocated randomly to every object in a heap.

3. Task Queue

   The primary purpose of the task queue is to queue the tasks while the call stack executes the previous ones. Since it is a queue, the operations performed here will be FIFO (First in, first out).

But now the question arises, how does the task queue be able to queue the tasks beforehand?

Asynchronous operations

To make the engine asynchronous, we can use an event loop. It helps us in making the engine asynchronous. We will also use the OS kernel and OS as well as web APIs. These are also very helpful in making the system asynchronous.

Components of the asynchronous model

1. Event Loop

   The primary work of the event loop is to monitor the call stack continuously and push a task from the task queue to the call stack when it gets empty.

2. OS Kernel & APIs

   We can use the OS Kernel for offloading the main thread from Input/Output operations, making the system asynchronous.

Engine model and execution process

Since we have outlined the architecture, we will try to understand the implementation and execution of the above model.

At the start of the code, a global execution context will be created in the call stack. Then the memory will be allocated to the objects and variables inside the memory heap. Then the code execution will start line by line.

Now, to make the system non-blocking, we will use the OS Kernel and APIs, e.g., Web APIs like setTimeOut(), localeStorage() And file read and write with the help of OS Kernel. When these types of tasks are inside the code, the main thread will send them to the OS environment, and the control will go to the following line of code. Since the control moves ahead instead of waiting for these operations to complete, these tasks will be queued in the task queue on completion from the OS environment.

Here the work of the event loop starts. An event loop is a process in which the call stack searches for the pending tasks in the task queue when nothing is to be executed inside the call stack. The event loop starts functioning only when all the frames inside the call stack are popped out. The task that was pushed inside the queue first will be pushed to the call stack first until all the queued tasks are executed.

This way, all the code will be executed, and all the tasks will be handled concurrently without blocking the main thread. This system takes help from the OS Kernel and APIs for handling I/O operations, allowing it to execute all the tasks on a single thread concurrently and asynchronously without blocking the thread.

Garbage collection and freeing up the memory

After the execution of the code, the memory from the heap needs to be freed up. Otherwise, it may cause system storage issues and slow it down. For this purpose, we need to use a garbage collector (GC). After doing some research, I thought of including the Mark and Sweep garbage collection algorithm for the implementation of the Garbage Collector of this engine. This algorithm works on the concept of 'an object is unreachable'. It points out the root object of the whole code - for example, the Global or Window object in our web browsers. After getting the root objects, it will search all the objects reachable from the root object, then all the objects reachable from those objects, and so on. After pointing out all the reachable objects, it sweeps all the unreachable objects.

Further optimization techniques

We also need to focus on some optimization techniques to make our engine more optimal and fast.

1. Inlining

   At the start, we can inline all the source code, saving a lot of time that might be wasted in parsing the blank lines.

2. Inline caching

   We can use the inline caching method to cache the simultaneous calls of the same function with the same arguments. It will cache those results, and the next time the same call happens, it won't need to execute the code instead, it will directly provide the output.

Outro

So it was all about the high-level architecture of a single-threaded, asynchronous, and highly concurrent engine. If you want to learn more of it, you can check out the links in the references section below.

Also, if you like my content, you can support me with a 👍 and catch me on Twitter and LinkedIn. If you also like to host your repositories on GitHub, like me, you can find me there also GitHub.

Feedbacks are most welcome.

References

https://developer.mozilla.org/en-US/docs/Web/JavaScript/EventLoop

https://v8.dev/

https://developer.mozilla.org/en-US/docs/Web/JavaScript/Memory_Management#garbage_collection