ion model for parallel control ows. To gure out the behavior, we implemented a prototypical data structure for indexing, whose results will be presented and discussed.
While hardware changes in the order of many processor
cores, large amounts of main memory and complex
memory architectures, software must also adopt these changes.
The purpose of increasing the number of processor units is a
linear speedup improvement, which is hard to reach. One
reason therefor is given by parts of a software, that cannot be
parallelized e.g. because of concurrent accesses to the same
shared resource, like shared memory, must be synchronized
[
In this work, we will introduce interesting aspects of the
project \MxKernel: A Bare-Metal Runtime System for
Database Operations in Heterogenous Many-Core Hardware"
which is a joint project of the Embedded System Software
Group and the Databases and Information Systems Group
at TU Dortmund. While common OSs allow the database to
run as an application on top, the MxKernel is a minimal layer
which can be used by both OS and DBMS as an abstraction
layer for the underlying hardware. This software
architecture enables the reuse of data structures and algorithms e.g.
indexes that are used by OSs for le system implementation
[
This paper is organized as follows. In Section 2 we will describe modern hardware in more detail and discuss problematic aspects. More precise information about the concept of the MxKernel will be introduced in Section 3. As a rst data structure using the MxKernel, we built a B-linktree, which is presented and discussed in Section 4, before we summarize in Section 5. Finally, the next steps of the project respecting databases will be outlined in Section 6. 2.
There are several properties of current and future hardware, that we need to follow from the software's view. This Section will discuss some of these characteristics. 2.1
Because it is no longer feasible to increase the clock
frequencies of processing units, more cores are installed on a
chip instead in order to enable more power through
parallelism [
With the ongoing increase of processor units, symmetric
memory architectures stopped scaling with modern
manycore systems [
In terms of distributed memory, parallel computing and
scalability, caches respectively cache coherence are also
signi cant. While caches speed up repeated access to data,
redundant data must be synchronized through complex
cache hierarchies. Since locks that are touched by many cores
are often implemented by using shared memory, cache
coherence quickly results in solutions that are not scalable [
In addition to the growing number of computing units,
we also see an increase in heterogeneous hardware, like
different cores with specialized functions in a single machine
[
The goal of the MxKernel is to improve the performance of manycore systems in regard to the increasing amount of data. In order to achieve this, the MxKernel forms the basis for applications like DBMSs and operating system services as well. Additional small units of work, we call them MxTasks, are used rather than threads for control ow abstraction.
This section will give an overview of the software architecture of the kernel, the MxTasks and how to synchronize them. 3.1
In most cases, operating systems are the basis for applications. The OS manages and abstracts the underlying hardware, which makes it simple to deploy applications on a wide set of di erent hardware. For this purpose, OSs provide interfaces for the hardware and a set of services to applications running on top of it. However, this endeavor also has disadvantages, for example, the OS is the only one who knows much about running applications.
Particularly, DBMSs does need only a few of those
provided services and implements his own ones. This concludes
that \a small e cient operating system with only desired
services" [
the system if the database is to perform well in the presence
of other applications [
In contrast to this, the MxKernel, whose software
architecture is shown in Figure 1, provides a platform for both
OS and DBMS. This makes sense for various reasons. When
the operating system is the base layer for applications, the
hardware will be abstracted to minimize any e ort in regard
to di erent hardware architectures. On the other hand, the
abstraction may become prevalent and applications have
fewer possibilities to control hardware resources precise. While
hardware changed after OSs such as Linux were published,
it has become tedious to adopt these changes. For example,
the entire Linux kernel was temporarily locked by a single
lock to prevent multiple threads passing the kernel in
parallel [
By providing a minimal layer for OSs and other applications like DBMSs, which normally run on top with a need for less abstracting interfaces of the underlying hardware, we promise advantages for both sides. For example, the DBMS could make a better placement of data on the hard disk, improve scheduling of control ows and take more care of NUMA awareness.
Further, there are components that are introduced by
both OSs and DBMSs. Indexing techniques, for example,
are used in databases to e ciently locate tuples. Even le
systems like BeOS [
Threads are a well-known and heavily used method to abstract concurrent control ows. Many OSs, as well as programming languages, implement threads, which also have some disadvantages. When several threads access a data structure at the same time and at least one of them updates the data, the accesses must be atomic or synchronized, e.g. by mutexes or spinlocks. This could impair the scalability of the system because in case of synchronization only a single thread could pass the guarded section.
Another costly aspect is scheduling and the included context switches of threads. Since there are mostly more threads
than processing units on a system, the operating system has
to schedule them periodically. When a thread is
suppressed by the OS for the bene t of another, the context of the
replaced thread has to be saved and the context of the
restored thread has to be recovered. On a Linux based system, a
context switch takes micro- up to milliseconds [
An alternative approach to threads, which represents a
large sequence of instructions, is to split the work into
smaller units, named tasks. Several libraries and operating
systems make use of this concept, e.g. Intel's Threading
Building Blocks [
Also, the MxKernel uses the concept of tasks, namely MxTasks, to manage compute resources. The MxTasks are characterized by a run-to-completion semantic, which means that running tasks will never be suppressed by the kernel. Thus, a task does not need his own stack, instead, all tasks of one core can share the same stack, which minimizes the costs of a context switch between two tasks. Further, the kernel guarantees the execution of a task per core to be atomically, whereas a common thread could be interrupted at any time. As a consequence, all tasks scheduled to the same core are synchronized by de nition and do not need any lock. This makes it easier to synchronize con icting tasks and simpli es the development of lock-free data structures and algorithms.
In regard to modern hardware described in Section 2, we see another bene t that tasks can pro t in contrast to heavyweight threads. Due to the usually longer life and execution time of threads, it is di cult to predict memory accesses and migrate threads to the suitable NUMA region. MxTasks, on the other hand, have a short duration of execution and in this way lesser memory accesses. This allows ner scheduling with respect to local memory requests. 3.3
Nevertheless, the access to one resource from di erent MxTasks has to be synchronized. Otherwise di erent tasks could update one resource on di erent cores at the same time like shown in Figure 2a, which causes unde ned behavior. For this purpose, we present two methods.
Based on the run-to-completion semantic of tasks, we can ensure that all tasks executed on the same CPU core are serialized. By implication, this means when all accesses on one resource are done by tasks assigned to the same core, the resource does not need to be protected by locks or mutual exclusion. Following this, we can synchronize multiple tasks accessing the same resource by scheduling them to the same core without any overhead. This is shown in Figure 2b, where both Resource a and b are mapped to the rst core in the system.
Using the core based synchronization with a xed resource to core mapping may result in an unbalanced load of the system, where some cores may have a lot of work and others not. In order to avoid that balancing problem and to get rid of the static task-to-core-assignment, we implemented a special task for synchronization, called Synchronize-Task. Within a system where concurrent tasks access a shared resource like shown in Figure 2a, every Synchronize-Task represents such a shared resource e.g. a monitor. Every task, that wants to use the shared resource, for example, to print some text on the monitor, needs to enqueue to the waiting list of the Synchronize-Task, shown in Figure 2c. After that, the Synchronize-Task will register itself as ready to run to the MxKernel. By the time the MxKernel executes the Synchronize-Task as a normal MxTask, a set of tasks waiting in the ready list of the Synchronize-Task will be executed directly. To avoid too long execution times, the set of running tasks within a Synchronize-Task will be restricted and the Synchronize-Task will be marked as ready again if not all (sub-) tasks were executed. In this way, the SynchronizeTasks can move around between cores to balance the load and take care of NUMA aware execution. Moreover, when multiple tasks accessing the same data are executed consecutive, their behavior will be more cache-friendly because already cached data could be used for several tasks in a direct way. 4.
The task model introduced in Section 3 di ers from
programming with well-known threads and looks more like an
event-based and asynchronous development. To get started,
we opted for a B-link-tree-based index structure, with which
we have already gained some experience in our group [
B-trees and their variations like B+-trees and B-link-trees
[
As an example for developing with the task model in the context of the MxKernel, we will take a look at the insert operation to store a key-value pair as a record into the Blink-tree. Algorithm 1 shows the pseudo code of a simpli ed insert operation using threads. First, we will nd a leaf in a B-link-tree by traversing through di erent levels of the tree, shown in lines 2 to 7. As we found the correct leaf, we insert the record composed of a key and the corresponding value, represented by lines 8 to 11. In case that the leaf node is full, it is split into two nodes, both lled with half of the key-value pairs and the separator to the new node has to be propagated up to the parent node. Because this is not important for the comparison between the two abstraction models, we neglect this step.
While navigating down to the leaf the record will be stored
in, we need to take a latch on every inner node to prevent
other threads from updating that node. Even for the leaf
node, we have to take a latch during insertion. As a result,
when frequently used nodes, such as the root node, will be
accessed by multiple threads, the latch data structure will
be touched by all of them. The lock contention will be a
big part of the execution time [
The concept of MxTasks and the way they are synchronized with each other gives us the possibility to avoid the lock contention. In opposition to threads, where one thread will traverse through the tree to nd a leaf, multiple tasks are used to process node by node, shown in Algorithm 2. Every insert task will start his work on the root node of the tree. Assuming that the root node is not a leaf, the task will look up for the next child node and create a follow-up task for that node (lines 1-3). On the located child node, this steps will be repeated, until we found a leaf. When the task located the wanted leaf, the key-value pair will be inserted (line 6) and the task is done. Assuming that the node has to be split, an insert task for the pointer to the new node will be spawned at the parent node. Deviating from thread model, where the propagation of the new node would be done bottom-up recursive, the MxKernel uses tasks to propagate the key-pointer pair for the new node up to the parent.
In regard to di erent synchronization techniques described in Section 3.3, the EnqueueTask method (line 3) could have various implementations. When using the core, based synchronization, every node is mapped to a core based on its memory address. Enqueue in this context means to mark the task as ready for the run on the mapped core so that only this core will process all tasks accessing the node. Otherwise, when the Synchronization-Task is used, every node is seen as a shared resource and will be a MxTask which can be processed by the MxKernel. In this way, every node will execute the tasks that are accessing it, to avoid concurrent accesses to one node. 4.2
All measurements are carried out on a machine using the hardware presented in Table 1. While the MxKernel is running directly on the hardware, we used an Ubuntu 17:10 with a Linux Kernel 4:13:0 36 to measure the thread based variant of our benchmark.
As a workload, we insert 5; 000; 000 random generated 32bit key-value pairs into the B-link-tree using a global set of prede ned values, which are \stolen" by threads and tasks. The results of our experiments can be seen in Figure 3. A rst nding is that all measurements show a loss of performance when using more than eight cores. At this point, the 0 2 4 6 8 10 12 14
Linux Threads Cores / Threads
MxTasks (Synchronize-Task) MxTasks (CPU-synchronized) 16
rst processor with eight cores installed is not enough and some tasks and threads are scheduled to the second processor, which is also a separate NUMA region. While the thread benchmark (red) is fastest at four cores and slows down when additional cores are added, all variants of the benchmarks using MxTask gain more throughput until using the ninth core. At the thread variant, we have no in uence on the scheduling of threads and left it to Linux. Therefore, it is possible that two threads on the same core compete for computing time, which may slow down the benchmark.
We also see some di erences in regard to throughput within the two di erent techniques of task synchronization, described in Section 3.3. While synchronization by Synchronize-Task (blue) seems to be slower on the usage of the rst eleven cores, the core based synchronization (green) variant loses more speed when using 12 15 cores. In the end, when using all 16 processing units, their throughput is approximately equivalent.
By pro ling the given benchmark and both techniques for task synchronization we have uncovered problems concerning the task queue data structure, which is used by both Synchronize-Task and the task management of the MxKernel. In order to achieve a wait-free behavior of the queue, an atomic variable is shared between consumer and producer when just one or none item is remaining in the queue. In the case of the synchronize task, where each node is represented by such a task, we get a lot of contention on that shared variable, which slows down the whole application. Unbalanced workloads in which some cores have little work end up behaving the same way. The extra e ort to keep the cache coherent seems to get more expensive when more than one NUMA region is involved which ends in poor performance on two nodes.
Nonetheless, MxTasks seems like a promising approach to make better use of modern hardware than usual threads does. Although we have not made any optimizations regarding the NUMA architecture and do not yet schedule tasks in the best possible way, the MxKernel achieved a higher throughput on the B-link-tree.
In this paper, we presented the MxKernel, which is a baremetal runtime system for Database/Operating System CoDesign. With the project, we focus on modern hardware that is characterized by many cores, complex memory architectures, and heterogeneity. Small units of work are used to abstract control ows rather than threads.
As a rst data structure, we implemented a B-link-tree on top of the MxKernel and MxTasks. Experiments have revealed promising results and have shown that tasks sometimes scale better than threads, even there is still room for optimizations. With the software architecture outlined above, we will obtain a better interface between software and hardware to enable optimization in regard to modern hardware. 6.
As the experiments show, we need to nd a more e cient data structure for task management in order to reduce the contention of shared variables. Considering the intention to create a full runtime environment for databases and operating systems, we must rst solve basic problems such as e cient memory allocation. With MxTasks we have a data structure that is allocated and destroyed at high frequencies, our current usage of a global heap may be a bottleneck for scalability. Similarly, there is still no clarity as to how tasks could be ideally scheduled to available cores. Therefore, we want to model dependencies among MxTasks and their access patterns as metadata, connected directly to the tasks. Also, o ine scheduling may be an opinion.
In regard to databases, more data structures like hash tables have to be implemented in order to further explore the behavior and programming of MxTasks. Furthermore, we will add a transactional interface to the B-link-tree.
This research was supported by the Deutsche Forschungsgemeinschaft, DFG, project number TE 111/2-1.