MySQL Cluster and real-time requirements

This blog gives some background to the decisions made when designing the
storage engine NDB Cluster used in MySQL Cluster around how to support
real-time requirements (or as I sometime refer to it, predictable response
time requirements).

Requirement analysis

When analysing the requirements for NDB Cluster based on its usage in telecom
databases two things were important. The first requirement is that we need to
be able to respond to queries within a few milliseconds (today even down to
tens of microseconds). The second requirement is that we need to do this while
at the same time supporting a mix of simple traffic queries combined with a
number of more complex queries running at the same time.

The first requirement was the main requirement that led to NDB Cluster using a
main memory storage model with durability on disk using a REDO log and
various checkpoints. Today we also support storing non-indexed columns on
disk in combination with columns stored in main memory.

Potential solutions

The second requirement was a bit harder to handle. To solve the second requirement
in an extremely large environment with many CPUs can be done by allowing the
traffic queries and management queries to run on different CPUs. This model will
however not work at all in a confined environment with only 1-2 CPUs and it will
even be hard to put to work in a large environment since the usage of the
management queries will come and go quickly.

The next potential solution is to simply leave the problem to the OS. Modern OSs

of today use a time-sharing model. However each time quanta is fairly long
compared to our requirement of responding within parts of a millisecond.
So this model won't work very well either.

Yet another possibility would be to use a real-time operating system, but this would
marginalise the product too much.

Most DBMS today use the OS to handle the requirements on reponse times. So as an
example if one uses MySQL/InnoDB and send various queries to the MySQL Server,
some traffic queries and some management queries, MySQL will use different threads
for each query. MySQL will deliver good throughput even in the context of very
varying workloads since the OS will use time-sharing to fairly split the CPU usage
amongst the various threads. However it will not be able to handle response time
requirements of parts of a millisecond with a mixed load of simple and complex
queries.

AXE VM

So when designing NDB Cluster we wanted to avoid this problem. NDB was designed
within Ericsson. In Ericsson a real-time telecom switch had been developed in the
70s, the AXE. The AXE is still in popular use today and new versions of it are still
developed. AXE had a solution to this problem which was built around a message
passing machine.

I spent a good deal of the 90s developing a virtual machine for AXE called AXE VM
that later turned into a real product called APZ VM (APZ is the name of the CPU
subsystem in the AXE). This virtual machine was able to execute on any machine.
The AXE VM used a model where execution was handled as execution of signals. A
signal is simply a message, this message contains an address label, it contains
a signal number and it contains data of various sizes. A signal is executed inside
a block, a block is a module that is self-contained, it owns all its data and
the only manner to get to the data in the block is through sending a signal to the
block.

So effectively the AXE VM implemented a real-time operating system inside a normal
operating system such as Windows, Linux, Solaris or Mac OS X.

The AXE VM also had a lot of handling of the language used in AXE called PLEX. This
is no longer present in NDB. But NDB still is implemented using signals and blocks.
The blocks are implemented in C++ and in AXE VM it was possible to have such
blocks, they were called simulated blocks. In NDB all blocks are nowadays simulated
blocks.

How does NDB solve the real-time problem

So how does this model enable response times of down to parts of a millisecond even
in a highly loaded system. First of all it is important to state that NDB does
handle this. We have very demanding customers both in the telecom, networking and
in financial sectors and lately also in the storage world that expects to run
complex transactions involving tens of different key lookups and scan queries and
that expects these transactions to complete within a few milliseconds even at
90-95% load in the system.

As an example in the financial sector missing the deadline might mean that you miss
the opportunity to buy or sell some stock equity in real-time trading. In the telecom
sector your telephone call setup and other telco services depends on immediate
response to complex transactions.

At the same time these systems also need to ensure that they can analyse the data
in real-time, these queries obviously have less demanding response time
requirements, but they are not allowed to impact the response time of the traffic queries.

The virtual machine model implements this by using a design technique where each
signal is only allowed to execute for a few microseconds. A typical key lookup
query in modern CPUs takes less than two microseconds to execute. Scanning a table
is divided up into scanning a few rows at a time where each such scan takes less
than ten microseconds. All other maintenance work to handle restarts, node failures,
aborts, creating new tables and so forth is similarly implemented with the same
requirements on signal execution.

So what this means is that a typical traffic transaction is normally handled by one
key lookup or a short scan query and then the response is sent back to the API node.
A transaction consists of a number of such interactions normally on the order of
tens of such queries. This means that each interaction needs to complete within
100-200 microseconds in order to handle response times of a few millseconds
for the transaction.

NDB can handle this response time requirement even when 20-30 messages are
queued up before the message given that each message will only take on the order
of 1-2 microseconds to execute. So most of the time is still spent in the transporter
layer sending the message and receiving the message.

A complex query will execute in this model by being split into many small signal
executions. Each time a signal is completed it will put itself back into the queue
of signals and wait for its next turn.

So traffic queries will always have the ability to meet strict requirements on
response time. Another nice thing with this model is that it will adapt to
varying workloads within a few microseconds. So if there is currently no traffic
queries to execute, then the complex query will get the CPU to itself since the
next signal will execute immediately after being put on the queue.

Handling memory allocation

One more important factor in ensuring that NDB can always operate in an optimal

manner and deliver the expected throughput is that we control memory. All the

memory is allocated at startup, this means that we cannot get into a situation where

we oversubscribe the main memory of the machine. NDB even have a number of

config parameters to ensure that the memory used by NDB data nodes is never

paged out.

Locking of CPUs

One more manner of ensuring that NDB always operates in an optimal manner is to

control the placement of threads onto different CPUs.

Behaviour of NDB at high load

There is one more very important aspect of this model. As load increases two
things happens. First we execute more and more signals every time we have
received a set of signals. This means that the overhead to collect each
signal decreases. Second executing larger and larger sets of signals means
that we send larger and larger packets. This means that the cost per packet
decreases. Thus actually NDB data nodes executes more and more efficiently
as load increases. This is a very important characteristic that avoids many
overload problems.

Building a mixed environment for traffic and management queries

Finally the separation of Data Server and Query Server functionality makes it
possible to use different Query Server for traffic queries to the ones used
for complex queries. So in the MySQL Cluster model this means that you can
use a set of MySQL Servers in the cluster to handle short real-time queries.
You can use a different set of MySQL Servers to handle complex queries.
Thus MySQL Cluster can handle real-time requirements in a proper configuration
of the cluster even when operating using SQL queries.

Conclusion

The interface to the Data Server is as you can now see implemented on top of
signals, the most common ones are TCKEYREQ that implements all types of
key lookups using the primary key and SCAN_TABREQ that implements all types
of scan queries (also including join queries that have been pushed down to
data nodes). There is a protocol to carry these signals that currently uses
TCP/IP sockets but have historically also been carried by SCI, Infiniband
and shared memory transporters.

So the separation of Data Server and Query Server functionality might mean
that MySQL Cluster have slightly longer minimum response time compared to
a local storage engine in MySQL, but MySQL Cluster will continue to deliver
low and predictable response times even using varying workloads and even
when executing at very high loads.

One experiment that was done when developing pushdown join functionality
showed that the performance of those pushed down joins was the same
when executing in an otherwise idle cluster as when executing in a cluster
that performed 50.000 update queries per second.

NDB has been designed such that with some work of configuring it properly
it can be extremely reliable in delivering predictable response times. At the
same time we're working hard to make it easier and easier to configure also
when you don't want to control every bell and whistle. One step in this direction
is the introduction of the ability to read also from backup replicas and the
adaptive control of which threads that help out in sending.

Separation of Query Server and Data Server

In MySQL we have separated the Query Server and the Data Server
functionality. The Query Server is what takes care of handling the
SQL queries and maps those to lower layers call into the Data Server.
The API to the Data Server in MySQL is the storage engine API.

Almost all DBMS have a similar separation between Data Server and Query
Server.

When I performed my research work, that later led to development of
NDB Cluster, that is now MySQL Cluster, an important part of the
research was to handle the separation of the Data Server and
the Query Server.

As part of my research we looked deeply into the next generation mobile
networks and their use of network databases. From these studies it was
obvious that the traffic part of the applications almost always made very
simple queries, mostly key lookups and in some cases slightly more complex
queries were used.

At the same time there is also management applications in the telecom
network, these applications will often use more complex queries and will
almost always use some sort of standard access method such as SQL.

Normally the traffic queries have strict requirements on response times
whereas the management applications have much less strict requirements
on response times.

So it was clear that there was a need for both a fast path to the data
as well as standard APIs used for more complex queries and for data
provisioning.

From this it was clear that it was desirable to have a clearly defined
Data Server API in a telecom DBMS to handle most of the traffic queries.

Now the next question that came up was the placement of the API. There were
a number of alternatives. One method was to have an API such that the
application can execute direct function calls into the Data Server. A
number of databases uses this approach. The reason for avoiding this
approach is the high availability requirement. If the application gets
a wrong pointer and writes some data out of place, then it can change
the data inside the DBMS. Another problem with this approach is that it
becomes very difficult to manage in a shared nothing architecture since
the application will have to be colocated with its data for the benefits
to be of any value.

So choosing a network-based protocol as the Data Server API was a choice
to ensure the highest level of reliability of the DBMS and its applications.
We have a clear place where we can check the correctness of the API calls
and only through this API can the application change the data in the Data
Server.

Another reason that made it natural to choose a network protocol as API was
that the development of technologies for low-latency and high bandwidth had
started already in the 1990s. The first versions of NDB Cluster actually had
an SCI transporter as its main transporter which ensured that communication
between computers could happen in microseconds. TCP/IP sockets have since
replaced it since also SCI and Infiniband now have support for TCP/IP sockets
that is more or less as fast as direct use of SCI and Infiniband.

One more reason for using a network protocol as API is that it enables us to
build very scalable Data Servers.

To make it easier to program applications we developed the C++ NDB API that
is used to access to the NDB Data Server protocol.

The marriage between MySQL and NDB Cluster was a natural one since NDB Cluster
had mainly focused on the Data Server parts and by connecting to the MySQL
Server we had a natural implementation of the Query Server functionality.

The requirements on extremely fast failover times in telecom DBMSs made it
necessary to implement NDB Cluster as a shared nothing DBMS. So effectively
the Data Server API has support for storing relational tables in a shared
nothing architecture. The methods available in the NDB Data Server API is
methods for key-value access for read and write, scan access using full
table scan and ordered index scans. In 7.2 we also added some functionality
to pushdown join execution into the Data Server API.

To decrease the amount of interaction we also added an interpreter to the
NDB Data Server, this can be used for simple pushdown of filters, it can
be used to perform simple update operations (such as increment a value)
and it can handle LIKE filters.

So what have been the benefits and disadvantages of these architecturial
choices been over the years.

One advantage is that MySQL Cluster can be used for many different things.

One important use case is what it was designed for, there are many good
examples of applications written against any of the direct NDB APIs to
serve telecom applications, financial applications and web applications
while still being able to access the same data through an SQL interface
in the MySQL Server. These applications takes advantages of the
performance advantage that make it possible to scale applications to
as much as hundreds of millions of operations per second.

Another category in poular use with MySQL Cluster is to implement an
LDAP server as the Query Server on top of the NDB Data Server. This would
have been very difficult using a Query Server API since the Query Server
adds a very significant overhead to simple requests.

The latest example of use cases is to use the Data Server to implement
a scalable file system. This has been implemented by HopsFS in replacing
the Name Server in Hadoop HDFS with a set of Name Servers that use a
set of NDB Data Servers to store the actual metadata. Most people that
hear that such an architecture is built on something with MySQL in the
name will immediately think of the overhead in using SQL interface to
implement a file system. But obviously it isn't the SQL interface which
is used, it is implemented directly on top of the Java implementation
of the NDB API, ClusterJ. Personally I also have a hobby project that
I play around every now and then for the last 10 years that will
implement a Linux filesystem on top of NDB Cluster using a new NDB API,
a new NDB management server and using the FUSE API to implement the
file system in userspace.

The final category obviously is the use of MySQL Cluster with the
SQL interface. There are many applications that use this to get to the
high availability of MySQL Cluster but still using the SQL interface.

The disadvantages is obviously that DBMSs that have a more direct
API between the Query Server and the Data Server will get benefits
in that they don't have to go over a network API to access its data.
With NDB Cluster you pay this extra cost to get higher availability,
more flexible access to your data and higher scalability.

We have worked very hard since the inception of NDB Cluster into MySQL
to ensure that the performance of SQL queries is as close as possible
to the colocated Query Server and Data Server APIs. We've gotten very
close and we are working on getting even closer.

At the same time by separating the Data Server and the Query Server we
have made it possible to work on parallelising some queries in an easy
manner. This makes the gap much smaller and for many complex queries
NDB will even outperform local storage engines.