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.

Read any replica in MySQL Cluster 7.5

MySQL Cluster uses a distributed architecture where we have one primary
replica and one or more backup replicas of all data in the cluster.
In previous versions we have not supported reading from the backup
replicas. The reason for this comes from the transaction algorithm in
the NDB storage engine. When the transaction have committed we have
unlocked the rows in the primary replica, but the locks in the backup
replica is unlocked in the complete phase.

The impact of this is that we could potentially perform an update
of a row and then immediately read it and not see our own write. To
avoid this problem we have avoided to read the backup replica.

If it is important to read the backup replica then we need to ensure
that transactions are not reported back to the user until the complete
phase.

When we decided to support read from backup replicas we considered how
to handle this. One manner would be to simply have a flag in the
updating transactions that signals that we want the response after the
complete phase instead of after the commit phase.

We decided that this approach would be possible, but we opted for a
safer approach where it is a table property that defines if tables
can be used for reading the backup replica or not.

Given that there is a latency cost to wait until the complete phase
is done this feature is not enabled for all tables. In 7.5 we decided
to have the default that read from backup replicas isn't enabled.

There are a number of ways to enable read from backup replicas.

Let's start with the case when you haven't created the table yet.
In this case the first manner to handle it is to create a table
with the read backup flag set. This is done by using a special
flag set in the COMMENT section of the CREATE TABLE statement.
To set the flag we use the following comment:
COMMENT="... NDB_TABLE=READ_BACKUP=1 ... "
We run a parser on the COMMENT section where we look for the
NDB_TABLE keyword and after that we look for an equal sign
followed by a new keyword READ_BACKUP which can be set to 1 or
0. It is also possible set several table properties in one comment
and in this case we add a comma and the next property. So e.g.
COMMENT="NDB_TABLE=READ_BACKUP=1,PARTITION_BALANCE=FOR_RA_BY_NODE"

The above feature is a good approach when you want read from backup
replicas in some tables, but not from all tables. A more likely
approach is to set the new configuration variable ndb-read-backup
in the MySQL Server that ensures that all tables gets created with
the read backup flag set.

So basically it is necessary to decide if you want to focus on
read performance or low latency of updating transactions. Given
that NDB is very often used for high write loads we have kept the
default to not set the read backup flag. But many applications
are read-focused, so in this case it makes sense to set the
config variable ndb_read_backup to 1.

There is one more case where there are already existing tables
that have been upgraded from an earlier MySQL Cluster version.
In this case it is possible to change those tables to set the
read backup flag online.

The syntax to use this for a table called t1 would be:
ALTER TABLE t1 algorithm=inplace, COMMENT="NDB_TABLE=READ_BACKUP=1";
This will run an online change that can happen concurrent with
reading and writing transactions.

Now when equipped with read backup flag set on your tables it is
possible to localize your application. Assume that you have the
following MySQL Cluster setup.

Now we want to ensure that the MySQL Server 1 always uses the NDB
data node 1 and vice versa for reading. If the MySQL Server 1 and
the NDB data node 1 are using the same hostname or ip address we
will automatically detect that they are on the same host. So in
this case we will always prefer to send reads to the same host.
If they are on the same host but uses different ip address then
we can tell the MySQL Server 1 that its closest data node
neighbour is the node id of NDB data node 1. This is done by
setting this node id in the MySQL configuration variable
ndb-data-node-neighbour to this value.

So with this settings we are able to more or less make a read
optimised architecture using the MySQL Cluster.

Many people that uses MySQL/InnoDB that tries out MySQL Cluster
will most likely expect the behaviour provided with the read
backup flag set. So users of MySQL Cluster that comes from the
MySQL world should most likely set the ndb-read-backup flag
to get the expected behaviour.

HopsFS based on MySQL Cluster 7.5 delivers a scalable HDFS

The swedish research institute, SICS, have worked hard for a few years on
developing a scalable and a highly available Hadoop implementation using
MySQL Cluster to store the metadata. In particular they have focused on the
Hadoop file system (HDFS) and the YARN. Using features of MySQL
Cluster 7.5 they were able to achieve linear scaling in number of name
nodes as well as in number of NDB data nodes to the number of nodes
available for the experiment (72 machines). Read the press release from
SICS here

The existing metadata layer of HDFS is based on a single Java server
that acts as name node in HDFS. There are implementations to ensure
that this metadata layer have HA by using a backup name node and to
use ZooKeeper for heartbeats and a number of Journalling nodes to
ensure that logs of changes to metadata are safely changed.

With MySQL Cluster 7.5 all these nodes are replaced by a MySQL Cluster
installation with 2 data nodes (or more NDB  data nodes if needed to scale
higher) to achieve the same availability. This solution scales by using many
HDFS name nodes. Each 2 NDB data nodes scales to supporting around
10 name nodes. SICS made an experiment where they managed to
scale HDFS to using 12 NDB data nodes and 60 name nodes where they
achieved 1.2 millions file operations per second. The workload is based on
real-world data from a company delivering a cloud-based service
based on Hadoop. Most file operations are a combination of a number of
key lookups and a number of scan operations. We have not found any
limiting factor for scaling even more with even more machines
available.

This application uses ClusterJ, ClusterJ is a Java API that access
the MySQL Cluster data nodes directly using a very simple API.

The application uses a lot of scans to get the data, so the
application takes advantage of the improved scalability of scans
as present in 7.5. Given that it is a highly distributed application
a lot of the CPU time is spent in communicating, so the new adaptive
algorithms for sending is ensuring that performance is scaling nicely.

SICS have also developed a framework for installing MySQL Cluster in
the cloud (Amazon, Google, OpenStack) or on bare metal. I tried this
out and got the entire HopsFS installed on my laptop by doing a few
clicks on a web page on my desktop and pointing out the address of my
laptop. This uses a combination of Karamel, a number of Chef cookbooks
for MySQL Cluster, and a number of cookbooks for installing HopsFS.
Karamel uses JClouds to start up VMs in a number of different clouds.

MySQL Cluster 7.5 is GA, best cluster release ever

I have been fairly quiet on my blog for some time. We've been very busy
developing new features for MySQL Cluster 7.5 and ensuring that the
quality is improved even further.

We're now very pleased to release a new version of MySQL Cluster.

MySQL Cluster 7.5 contains a number of new things that makes MySQL
Cluster even better.
1) You can declare a table as a READ_BACKUP table. This means that
the updating transactions will receive the commit acknowledge
a little bit later to ensure that we can always use any of the
replicas for reading. We will use the nearest replica for
committed reads, for locking reads we will still use the primary
replica to avoid deadlocks.

For applications that are mostly read-focused one can make it easier
to set this variable by setting the ndb-read-backup config variable
to 1 in the MySQL Server configuration. This means that all tables
created from this server will create tables with the READ_BACKUP
flag set to true.

2) You can declare a table as a FULLY_REPLICATED table. This means
that this table will get as many replica as there are nodes in the
cluster.

Fully replicated tables (global tables) provides a very important way
to scale your applications using MySQL Cluster. Many applications have
small tables that is mainly read, these tables can now fully replicated
and thus be read from any data node in the cluster.

Another potential use of fully replicated tables is to use MySQL Cluster
for read scalability. You can start out with a 2-node cluster where both
nodes are able to read the data. If you then need to scale to 4 nodes
you add 2 more nodes to the cluster, you create one more node group
for the 2 new nodes. Then you can reorganise the tables such that they
are fully replicated on all 4 nodes. You can continue in this manner
all the way until you have 48 nodes. All through this process any
MySQL Server can be used to both read and write the data in the cluster.

If the application is an SQL application it is a good idea to place
the MySQL Server is placed on the same computer as a data node.
So in this manner MySQL Cluster have a very easy manner of scaling up
your application for reads.

A third variant to use fully replicated tables is to place hot-spot rows
that are often read and seldom updated into fully replicated tables.

It is possible to set a config variable ndb-fully-replicated to 1 to
ensure that all tables are created as fully replicated. This should
obviously only be used for read scaling applications.

3) We have made it easier to vary the number of partitions in a table.
Normally we will have 2 partitions per LDM thread per node group. So
this means in a 4 node cluster with 2 node groups that have 4 LDMs per
node, there would be 16 partitions in a normal table.

Now it is possible to decide to have less partitions that are still
linked to the number of node groups in the cluster. So one can define
e.g. to have 1 partition per node group. This means that the command
ALTER TABLE REORGANIZE will add more partitions if node groups have
been added since the table last was altered. It will keep the number
to in this case 1 partition per node group. We support seven different
variants here.

The idea with this is to be able to decrease the number of partitions
for smaller tables while still using the automated partitioning
features of MySQL Cluster.

4) In earlier versions of MySQL Cluster we introduced the possibility to
use special send threads to do all the sending. In 7.5 the send threads
have been redesigned such that they now share the burden of sending with
all the other block threads in the NDB data nodes. The block threads will
assist when they are not very loaded. So the send thread assistance is
adaptive based on the CPU usage in the threads.

In order to develop this feature the NDB data nodes now have a very good
view on how much CPU usage each thread is using. This information is used
for internal algorithms, but it is also available as new NDBINFO tables.

5) Earlier versions of MySQL Cluster had a scaling issue with executing
extremely many scans in parallel. In MySQL Cluster 7.5 we have effectively
removed this limitation. Now it is possible to handle many millions of
scans per second for each table for each data node. So the main limitation
is the CPU available now for processing in general.

6) We have also continued working on improving our testing to ensure that
we always deliver better quality with new releases.

7) We have also worked on improving the scalability of the NDB API to
ensure that we deliver high performance even in situations with hundreds
or even thousands of concurrent threads working against the cluster.

8) Last but not least MySQL Cluster 7.5 is based on MySQL 5.7. So this means
that we get a lot of new optimizer features from the MySQL Server, we get
improved scalability of the MySQL Server parts and a lot more.

My personal favorite among those features is definitely the fully replicated
tables and read backup tables. This opens up a new category of application
optimisations in a scalable system.

My endeavour to build MySQL on Windows

I recently worked a lot on getting my local Windows box to compile Windows.
I got a lot of help from the below link that took me a few steps towards the
solution.
http://www.chriscalender.com/resolving-the-bison-exe-m4-invalid-argument-error-when-building-mysqlmariadbxtradb-on-windows/

I had to save away my bison installation, uninstall it and then also
go into a registry editor and remove the various links to the Start Menu referring to
some help for Bison that had spaces in the registry. Resolving this meant that I could
manually run bison on the files in the mysql tarball and get the desired result. But it
was still not enough, I still had the same error when running a full automatic compile.

So then I found the following link coming to my rescue.
http://venublog.com/2010/02/07/changing-mysql-parser-code-on-windows-build-breaks-due-to-bison/

With the aid of this link I realised that I had to make sure that the correct bison
executable was started. So in order to get this to happen I ensured that C:\GnuWin32
was the very first part in PATH.

With this final touch I was finally able to get my Windows builds of MySQL and
MySQL Cluster to work like a charm. I still don't fully understand why the
second step was necessary, but it worked which is good enough for me :)

Do I understand why Windows supports spaces in file names, no.