New threadpool design

In MySQL 6.0 a threadpool design was implemented based on
libevents and mutexes.

This design unfortunately had a number of deficiences:
1) The performance under high load was constrained due to a global
mutex protecting libevent (see BUG#42288).

2) The design had no flexibility to handle cases where threads were
blocked due to either locking or latches. E.g. a thread held up by a
table lock will be kept in the threadpool as an active thread until
the table lock is released. If all threads are blocked in this state,
it's easy to see that also any query that want to release the table
lock cannot be processed since all threads in the thread pool are
blocked waiting for the table lock (see BUG#34797).

3) The design is intended to support very many connections but
didn't use the most efficient methods to do this on Windows.
libevent uses poll on Windows which isn't a scalable API when
there are thousands of connections.

Also in all of the benchmarking with MySQL it's been clear that
performance of MySQL often drops significantly when there are too
many threads hitting the MySQL Server. We have seen vast
improvements of this the last year and there are some additional
improvements of this in the pipeline for inclusion into the next
MySQL milestone release. However the basic problem is still there,
that too many waiters in the queue can lead to various performance
drop off, one reason for such drop offs can be when mutex waits
starts to timeout in InnoDB.

So actually when we're looking at the threadpool design now, we're
aiming at solving two issues in one. The first is to remove this
scalability dropoff at high thread counts and the second is to
efficiently handle MySQL servers with thousands of connections.
Threadpool also enables us to have more control over on which
CPU threads are scheduled to execute on. We can even dynamically
adapt the CPU usage to optimize for lower power consumption by
the MySQL Server with a clever threadpool design.

We're currently in the phase of experimenting with different
models, however we opted for a design based around usage of epoll
on Linux, eventports on Solaris and kqueue for FreeBSD and
Mac OS X. We will also make a poll-based variant work mostly for
portability reasons although it's scalability won't be so great.
For Windows we're experimenting with some Windows specific
API's such as the IO Completion API.

The code to support thread pooling in MySQL is actually very
small so it's easy to adapt the code for a new experiment.

Last week we found a model that seems to work very fine.
The benchmarks shows that the performance on 1-32 threads is
around 97-103% of one thread per connection performance. When
we go beyond 32 threads the thread pool gains more and more,
it's getting to about 130% at 256 threads and reaches 250%
better performance on 1024 threads. However this model still
have the problem of deadlocks, so there is still some work on
refining this model. The current approach we have is fixing
the deadlock problem but removes about 10-15% of the
performance on lower number of threads. We have however
numerous ideas on how to improve this.

The basic idea with our current approach is to use thread groups,
where each group works indepently of other groups in handling a
set of connections. We're experimenting with the number of
threads per group and also how to handle the situation when the
last thread in the group is getting ready to execute a query.

Compared to maximum performance around 32 threads we reach
about 67% of this performance also on 1024 concurrently active
threads. The drop off 33% is expected since there is some
additional load when we reach an overload situation to ensure
that the proper thread is handling the task. At low number of
threads it's possible to immediately schedule the current worker
thread to work on the query, but in the overload situation there
is some queueing and context switching needed to handle the
situation. However the overhead at overload is constant, so it
doesn't worsen when the number of threads goes to a very high
number.

To handle the problems with blocked threads, we will implement a
new part of the storage engine API and API towards the MySQL
Server where the MySQL Server and the storage engines can
announce that they're planning to go inactive for some reason.
The threadpool will however handle the situation even if a thread
goes to sleep without announcing it, it will simply be more
performant if the announcement comes in those situations.

The new MySQL development model with milestone release is a
vital new injection to the MySQL development leading to the
possibility of making new features available to the MySQL
community users in an efficient manner without endangering the
quality of the MySQL Server. There is a very strict quality model
before approving any new feature into a milestone release.
The 6.0 thread pool design would not meet this strict quality
model. The new design must meet this strict quality model before
being accepted although we have good hopes for this to happen.

Poll set to handle poll, eventports, epoll, kqueue and Windows IO Completion

This blog describes background and implementation of a poll
set to monitor many sockets in one or several receive
threads. The blog is intended as a description but also to
enable some feedback on the design.

I've been spending some time working out all the gory details
of starting and stopping lots of send threads, connection
threads and receive threads over the last few months.

The receive threads will be monitoring a number of socket
connections and as soon as data is available ensure that
the data is received and forwarded to the proper user
thread for execution.

However listening on many sockets is a problem which needs
a scalable solution. Almost every operating system on the
planet has some solution to this problem. The problem is
that they all have different solutions. So I decided to
make a simple interface to those socket monitoring solutions.

First my requirements. I will handle a great number of socket
connections from each thread, I will have the ability to
move socket connections from receive thread to another thread
to dynamically adapt to the usage scenarios. However mostly
the receive thread will wait for events on a set of socket
connections, handle them as they arrive and go back waiting
for more events. On the operating system side I aim at
supporting Linux, OpenSolaris, Mac OS X, FreeBSD and Windows.

One receive thread might be required to listen to socket
connections from many clusters. So there is no real limit
to the number of sockets a receive thread can handle. I
decided however to put a compile time limit in there since
e.g. epoll requires this at create time. This is currently
set to 1024. So if more sockets are needed another receive
thread is needed even if not needed from a performance
point of view.

The implementation aims to cover 5 different implementations.

epoll
-----
epoll interface is a Linux-only interface which uses
epoll_create to create an epoll file descriptor, then
epoll_ctl is used to add/drop file descriptors to the epoll
set. Finally epoll_wait is used to wait on the events to
arrive. Socket connections remain in the epoll set as
long as they are not explicitly removed or closed.

poll
----
Poll is the standard which is there simply to make sure it
works also on older platforms that have none of the other
mechanisms supported. Here there is only one system call,
the poll-call and all the state of the poll set needs to
be taken care of by this implementation.

kqueue
------
kqueue achieves more or less the same thing as epoll, it does
so however with a more complex interface that can support a
lot more things such as polling for completed processes and
i-nodes and so forth. It has a kqueue-method to create the
kqueue file descriptor and then a kevent call which is used
both to add, drop and listen to events on the kqueue socket.
kqueue exists in BSD OS:s such as FreeBSD and Mac OS X.

eventports
----------
eventports is again a very similar implementation to epoll which
has the calls port_create to create the eventport file descriptor.
It has a port_associate call to add a socket to the eventport set.
It has a port_dissociate call to drop a socket from the set.
It has a port_getn call to wait on the events arriving. There is
however a major difference in that after an event arriving in a
port_getn call the socket is removed from the set and has to be
added back. From an implementation point of view this mainly
complicated my design of error handling.

Windows IO Completion
---------------------
I have only skimmed this yet and it differs mainly in being a tad
complex and also in that events from the set can be distributed to
more than one thread. However this feature will not be used in this
design, also I have currently not implemented this yet, I need to
get all the bits together on building on Windows done first.

Implementation
--------------
The implementation is done in C but I still wanted to have
a clear object-oriented interface. To achieve this I
created two header files ic_poll_set.h which declares all
the public parts and ic_poll_set_int.h which defines the
private and the public data structures used. This means that
the internals of the IC_POLL_SET-object is hidden from the
user of this interface.

Here is the public part of the interface (the code is GPL:ed
but it isn't released yet):

Copyright (C) 2008 iClaustron AB, All rights reserved
struct ic_poll_connection
{
int fd;
guint32 index;
void *user_obj;
int ret_code;
};
typedef struct ic_poll_connection IC_POLL_CONNECTION;

struct ic_poll_set;
typedef struct ic_poll_set IC_POLL_SET;
struct ic_poll_operations
{
/*
The poll set implementation isn't multi-thread safe. It's intended to be
used within one thread, the intention is that one can have several
poll sets, but only one per thread. Thus no mutexes are needed to
protect the poll set.

ic_poll_set_add_connection is used to add a socket connection to the
poll set, it requires only the file descriptor and a user object of
any kind. The poll set implementation will ensure that this file
descriptor is checked together with the other file descriptors in
the poll set independent of the implementation in the underlying OS.

ic_poll_set_remove_connection is used to remove the file descriptor
from the poll set.

ic_check_poll_set is the method that goes to check which socket
connections are ready to receive.

ic_get_next_connection is used in a loop where it is called until it
returns NULL after a ic_check_poll_set call, the output from
ic_get_next_connection is prepared already at the time of the
ic_check_poll_set call. ic_get_next_connection will return a
IC_POLL_CONNECTION object. It is possible that ic_check_poll_set
can return without error whereas the IC_POLL_CONNECTION can still
have an error in the ret_code in the object. So it is important to
both check this return code as well as the return code from the
call to ic_check_poll_set (this is due to the implementation using
eventports on Solaris).

ic_free_poll_set is used to free the poll set, it will also if the
implementation so requires close any file descriptor of the poll
set.

ic_is_poll_set_full can be used to check if there is room for more
socket connections in the poll set. The poll set has a limited size
(currently set to 1024) set by a compile time parameter.
*/
int (*ic_poll_set_add_connection) (IC_POLL_SET *poll_set,
int fd,
void *user_obj);
int (*ic_poll_set_remove_connection) (IC_POLL_SET *poll_set,
int fd);
int (*ic_check_poll_set) (IC_POLL_SET *poll_set,
int ms_time);
const IC_POLL_CONNECTION*
(*ic_get_next_connection) (IC_POLL_SET *poll_set);
void (*ic_free_poll_set) (IC_POLL_SET *poll_set);
gboolean (*ic_is_poll_set_full) (IC_POLL_SET *poll_set);
};
typedef struct ic_poll_operations IC_POLL_OPERATIONS;

/* Creates a new poll set */
IC_POLL_SET* ic_create_poll_set();

struct ic_poll_set
{
IC_POLL_OPERATIONS poll_ops;
};