NDBcluster: a true story.

After mentioning it in my last post on the MySQL database, I worked for the last days of the week on building a NDBcluster and trying to get the best from it.
Just to introduce the topic I summarize what are the main characteristics of this engine. When I found NDB for the first time I was looking for a way to store (automatically) IN-MEMORY tables on the hard disk and a way to support LONGTEXT fileds. NDB had both this characteristic and it also offered a clustered approach to databasing, meaning that data were replicated on several machines configured to act as specific kind of nodes of this databased cluster (or clustered database).
I worked on a sandboxed version of the cluster by following this tutorial, with no troubles I installed a two-data-nodes-two-mysql-nodes-one-master-cluster on my laptop, then I started playing with its configuration parameters in order to enanche its performances, that were around 3s to send final results. But parameters to play with are so much that I couldn't find a real way to optimize it, I also found an interesting article but we needed very different performances from the proposed one.
I also tryed to work with a Diskless configuration (meaning that tables were not checkpointed to disk and no logs were written) expecting performances similar to the IN-MEMORY engine, but I couldn't find any enanchements by activating this option.
So, for the moment, NDB is not a solution to our problems and i suggest to direct our interests to a Redis database and to a way to scale our system.
For further information on NDB I suggest to start from MySQL Cluster Overview.

Flare db

Inspired by this post I tried the Flare db

Flare: pros

• Persistent storage (uses TokyoCabinet as storage engine);
• Supports Memcached as communication protocol;
• Easy to do data replication and partitioning (adding slaves is easy and can be done dynamically)

Flare: cons

• It supports only “normal” values, not lists or sets (the append function works only with strings);
• Not much documented;
• Slower than redis: to perform 14600 inserts it took 1.8 s (with PHP lib memcached);

Flare is similar to Redis: both are basic key/value data storage. The main advantage of Flare over Redis is the automatic support to data partitioning, but it could be easily implemented also in Redis. The main disadvantages, that make Redis better suited to Maraja are the performances and the lack of lists support. Testing this database has been interesting also because it uses TokyoCabinet to save data.

Optimizing a slow MySQL database for MapReduce purposes.

The first week is gone, we fixed bugs, wrote some CSS and rebuild the GUI. But now it's time for the serious things and we have to face our worst nightmare: the bottleneck.
Actually, my task is to test how much we can stress our code and the MySQL database in order to beat the Key-value-DB faction.
Just to see from where we are starting, we tryed to save results on the database but we got very low performances, with tens of seconds to save results coming from the client.

When optimizing a MySQL database we can do it at three possible levels (maybe they can be considered four, but you'll see that a part on the DB variables configuration is missing):

1. Table level: try to design well structured tables is the most important thing, we need primary keys/indexes in the right place. For this purposes I redisegned the MapResults table so that the primary key is no more an auto_increment integer but the key itself.


2. PHP/QUERY level: trying to use less mysql_query() as possible is one of the best optimization at this level, meaning that is better to have very long queries rather then submit thousands of short one. When we're INSERTing or DELETEing rows from a table there's no problem, we got the right SYNTAX supporting the insertion of multiple values with a single query.Things are much different when we have to UPDATE values, MySQL currently doesn't support the update of multiple keys so we can use four different approaches:
   
   
   
   
   • the worst one is to use multiple mysql_query() with on UPDATE for each key to be updated.
   
   
   • The second one is to use the CASE condition, like this:
   
   UPDATE MapResults
   SET value = case key
   when 'a' then CONCAT(value, ', 1')
   when 'b' then CONCAT(value, ', 2')
   [...]
   END
   
   this approach works, but is very slow, and we don't have so much enhancement in terms of time in using it.
   
   
   • The third one is very similar to the previous (also in terms of performance), but uses other condition statements, here's an example
     UPDATE MapResults SET value =
     IFNULL(ELT(FIELD(key, 'a'),
     CONCAT(value, ', 1') [...]), valuez);
   
   
   • The fourth approach is the fastest, it uses temporary tables and four steps: first of all we create the temporary table, then, we fill this table with all values coming from the client, with a common INSERT. Then, we UPDATE the MapResults table by copying the values from the temporary table directly to it. We finally delete the temporary table (that would be deleted anyway when the connection is closed).
   
   
   Ok, we solved the UPDATE problem, but how to choose when to use UPDATE and when to INSERT values? Unfortunately MySQL doesn't have a INSERT IF NOT EXISTS command, so we have to use a trick in order to not SELECT each key from the table to see if they are present. This is solved by using a RIGHT JOIN: we find the keys present in the temporary table but not in the definitive one, then we do a simple one-query-multiple-values-INSERT in order to fill it.
   
   
3. INDEX/ENGINE level: MySQL uses indexing in order to speed up searches, and the type of indexing available depends a lot on the ENGINE used. Since we are using a temporary table is impossible to use indices so a table scan approach is used especially by the main UPDATE discussed above.
The ENGINE problem could be faced also separately from the INDEX one. In general MyISAM is claimed to be lighter and faster then InnoDB, but this seemed to be not true in our case and finding this article on the web explains things a little.
Anyway performances are not so good and by using InnoDB we don't go under 0.9s to write results. The solution comes from the MEMORY engine, it creates and stores tables in the RAM and things become pretty fast, going rapidly to 0.2s per completed job. Anyway using the MEMORY engine is not a good idea especially for the MapResults table, since is not possible to save results back to the disk (not automatically, indeed) and it doesn't support LONGTEXT, so for this table we have to use InnoDB and keep MEMORY for the temporary table, this slows things a little, the lower bound becomes 0.5s, going up to 1.1s.

So far, our approach is to use a MapResults table with the InnoDB engine and a temporary table with the MEMORY engine. Performances are not so good with this approach, so my advise would be building the queue anyway and using MEMORY engine for all the tables, then have a daemon that synchronizes values between the RAM and the disk.
Another interesting idea would be using the NDB engine wich could be clustered and supports LONGTEXT.

LightCloud

LightCloud is a distributed and horizontal scaleable database in Python: until now it was based only Tokyo Tyrant, but recently it included also support for Redis, since from some benchmarks it performs much faster than Tokyo Tyrant. The reason to use LightCloud on top of Redis is the horizontal scalability made easy: LightCloud manages itself all the nodes of Redis, implementing a hash-ring. With Redis alone, such implementation is to be done by the client. In case Redis will be choosed as the db to save the Map results, LightCloud could make hashing really easy.

Notice: in the next version of Redis (1.0) all the client APIs are going to implement some kind of consistent hashing (today only the Ruby apis implement it).

CouchDB and Redis

Here are some observations from the tests with CouchDB and Redis:

CouchDB: pros

From the main website:

• Document based (JSON);
• RESTful HTTP API for reading and updating (JSON);
• Peer-based distributed system (easy to scale/replicate);
• Easy to set-up/configure;

CouchDB: cons

• Unstable release (next versions could break compatibility);
• Doesn't perform “append” of values under a key, without sending the whole document: we need the “rev” id (easy to get with a query) and all the document previously submitted (see the document api http://wiki.apache.org/couchdb/HTTP_Document_API)
• Performances: in many blogs and reviews, CouchDB results much slower than the other key-value databases: http://00f.net/2009/an-overview-of-modern-sql-free-databases/ , http://jacobian.org/writing/couchdb/.

CouchDB: conclusions

The main pro of CouchDB is the way the documents are accessed: communication is entirely done through JSON with a RESTful HTTP api. This approach could guarantee the consistency of our system (since we are using urls to save results), but this is not enough. The last two cons make CouchDB useless to our needs, since our main target feature is a fast append of a value to a list. CouchDB is more application-oriented, we need only a very fast back-end storage for intermediate results: we wouldn't use CouchDB advanced features like views and map/reduce queries.


Redis: pros

• key/value based, where values can be also LISTS and SETS;
• supports atomic operations such push and pop for lists;
• very high performances (from the website:110000 SETs/second, 81000 GETs/second), from my tests it takes 0.4-0.6 sec to save 14600 keys;
• Supports replication;
• Very easy to deploy and configure;
• Well supported (good documentation, mailing list);
• Easy to shard the keys between different servers through hashing;

Redis: cons

• Everything resides in memory: it saves the database asynchronously on the hard-drive depending on the configuration → a failure may bring data loss;
• Not yet completely stable: even if there is already the release candidate 1.0, I had to workaround some bugs in the PHP api;

Redis: conclusions

Redis looks really promising from our point of view. It performs really well and it's really convenient to store one key and the values in form of a list. Push and pop operations are atomic, so there aren't problems of concurrency if we use many instances of the server. Even if everything resides in memory, the risk of data loss is relatively low since it supports replication between different servers and in our case the data is only a temporary result between the map and reduce phase. It looks like the most promising key/value db.

First week updates (20/07/2009 - 24/07/2009)

Presentation and website structure

We have decided to structure the website with the followin sections:

1. "Home page": it contains a first brief description of Maraja and a link to start the testing;
2. "What's Maraja": it contains a detailed description of what is Maraja and an introduction to MapReduce;
3. "Architecture": it contains a description of the architecture of Maraja and an execution overview;
4. "Blog": we have installed a database-less blog platform to use for the next updates
5. "Project members": the members of the Maraja team.

We've written all the content for the website and created some describing images (for the "Architecture" section").

GUI (console) revision

We rebuild the console by adding new types of possible messages (called "system messages"), a new filtering option which allows to show one message over a certain number of dumps and a few options to stop, restart and process step by step the jobs.

We added also a lite version of the console, with only some numerical informations about computed jobs and elapsed time. The user can sweitch between the lite and the advanced version.

A new important feature we included is a debugging system which sends all the errors and informations of every php page to the javascript console.

Lastly we've made some modification for the browser compatibility: now we are compatible with the last version of Webkit, we should only wait for Safari and Chrome to include it.

Code cleanup & optimization

We commented and cleaned every page from uneuseful comments and we optimized part of the code. We added an header to explain the role of each file and a footer to summarize latest important changes.

During the cleanup we found errors which were hidden (also in the architecture of the database) and corrected them. We changed also the status codes of the jobs and the way in which they are assigned.

Lastly we've activated and tested the aliveness check.

Another brick in the wall

After an hard work on defining in detail the structure of the server, we started writing the code to implement it.
At the moment, we wrote the first part of the server, which includes:

* the index, which builds the page with basic functions and the GUI and sends it to the client;
* the givemeajob pages, both for the slave and the master;
* the pages to answer to the i'm alive (both for slave and master, of course);
* the scripts used to check the aliveness of workers.

We wrote also a php script to create jobs, which takes big text files and splits it into pieces of defined length, trying with a dataset of 1.25GB (the Divina Commedia copied several times) it takes up to 100 seconds to create 1345 jobs of 1MB (or 168 of 8MB).
We tried to put all this together and it works just fine, now we're working on the other pages, but the first demo will come very soon.