Archive for March, 2008

Progress on MySQL Proxy Partitioning

Saturday, March 29th, 2008

As posted here I started to think about possible ways to implement database sharding/partitioning.

I finally found the time to start prototyping a MySQL Proxy based solution that would allow you to analyze and rewrite queries to direct them to different databases. So this would going to be a nearly 100% transparent solution (some queries are impossible to support due to the nature of having multiple tables in different locations).

How does it work?
The main goal is to split up mysql tables and optionally put each of the resulting partitions on different mysql servers.

For now I concentrate on splitting up big tables into smaller ones within the same database. Distribution of these tables (i.e. partitions) over multiple databases would be the final goal and a lot more challenging task (think of transactions).

The work to be done would be divided into these 4 steps:

1. Analyze the query to find out which tables are involved and what the parition key would be (i.e. the value of the partition column or a hint - more on that later).
1.a. Validate the query and reject queries that cannot be analyzed (missing partition key etc.)

2. Determine the partition table / database. This could be done by a simple lookup, a hashing function or anything else.

3. Rewrite the query and replace the table names with the partition table names.

4. Execute the query on the correct database server and return the result back to the client.

An example:

Say this is the table you want to split up:

CREATE TABLE books (
    id INTEGER NOT NULL,
    name VARCHAR(100) NOT NULL,
    author INTEGER NOT NULL,
   
    PRIMARY KEY(id)
);

The partition tables for table books are named books_even and books_odd all with the same layout as books. The partition column is author so this value determines the partition table to be used. In this example we put all books of authors with an even id into books_even and the “odd ones” (meaning the “not even” ones not the strange ones ;) ) into books_odd.

Say the following query is sent to the proxy:

SELECT * FROM books WHERE author = 3;

The proxy would do the following:

1. Analyze the query and find that table books is used and that it is a partitioned table. We have defined that author is our partition column so “3” is our partition key. Both will be passed to the next part:

2. Lookup the partition table for books and partition key “3” => books_odd.

3. Rewrite the query to:

SELECT * FROM books_odd WHERE author = 3;

4. Execute it and send the result to the client.

What is the status right now?
After getting warm with LUA and setting up a (unit) test environment, which was an easy task since MySQL Proxy already comes with a handy solution for that, I started to implement the query analyzer (step 1) and rewriter (step 3). Both utilize the tokenizer provided by the proxy and don’t rely on regular expressions because it would be to be too error prone in my opinion.

There is already a lot of code and tests ready and it turns out to work as intended. But still there is a lot of work and head ache ahead. My next goal is to run the test suite of one of our major products with about 2,000 database bound tests against the partitioner to see how this works out.

The analyzer is already able to parse various types of queries like:

SELECT * FROM books WHERE author = 3;
SELECT * FROM books AS b, prices WHERE b.author = 3;
INSERT INTO books (id, author) VALUES (1, 3);
DELETE FROM books WHERE author = 3;
UPDATE books SET name = ‘new’ AND author = 3;

# Hinting works like this
/* partitionKey(books) = ‘books_odd’ */ SELECT * FROM books;
/* skipPartition() */ SELECT ‘do not analyze me!’;

… and a lot more like queries including comments or joins or invalid queries (i.e. no partition key provided).

The rewriter is able to rewrite all of the queries above.

Actually, I think a good deal of the queries of the application I intended to test with would correctly be analyzed and rewritten right now. But there is still a lot of work to do on this side to handle more complex queries including subselects, functions etc.

What’s next?
As said above the next goal is to run the test suites of our applications utilizing the partitioner. Once this is point is reached I will post the prototype here.

Up to now all of this looks like it could really work for us so I hope there is going to be more than a prototype but we will have to see.

Posted in hscale, mysql | 6 Comments »

MySQL Partitioning on Application Side

Wednesday, March 26th, 2008

After following the scale up path (i.e. buy bigger boxes) for a while now, we definitely need to scale out as things start to become “unhandy” and simply HUGE. (See small things are better)

We are running an OLTP application with about 200 million transaction per month. Currently we have some very large tables with more than 1,5 billion rows and the total database size is about 600 GB - all InnoDB.

What we want to implement is application based sharding, i.e. splitting up the big tables and distribute them among many smaller servers. Furthermore we need to implement some sort of archiving mechanism since the db size is growing very fast. Putting old data into compressed myisam tables seems to be a good solution here.

So, how to implement this?

These solutions come into mind immediately:

  1. Using MySQL Cluster (this is not really application wise sharding but I mention it for completeness)
  2. Using MySQL Proxy with transparent query rewriting and load balancing
  3. Implement it into a JDBC driver
  4. Implement it into the application data access layer (DAOs)

Each solution comes with a list of pros and cons.

MySQL Cluster
Using the cluster would bring scalability right away but as we do not have any experience with this and had a lot of issues with the other storage engines (first crashes with MyISAM, then crashes with InnoDB, both being unsolved for a while even though the MySQL Enterprise Support did a great job!) I feel quite reluctant switching to a new storage engine. The hardware requirements would be too high too, so I don’t think that this could be the best solution.

Application Based Sharding
For all the other 3 types of partitioning I would use the following mechanism and meta tables.
Say this is a table I would like to split (Please note that this is just an example with some added redundancy (productCategory) to ease partitioning by product category.):

CREATE TABLE orders (
    orderId BIGINT(20) NOT NULL,

    productCategory VARCHAR(50) NOT NULL,
    productId BIGINT(20) NOT NULL,
    date DATETIME NOT NULL,

    PRIMARY KEY (orderId)
);

The column productCategory would be the partition key since there are only about 20 to 100 product categories used and the data is spread almost evenly. The real scenario would be different but this is a close and easy to grasp match.

The partition meta data table could look like this:

CREATE TABLE partition (
    sourceTable VARCHAR(255) NOT NULL, # would be "orders" in our example
    partitionKey VARCHAR(255) NOT NULL, # would be the value of "productCategory"
    dbHost VARCHAR(100) NOT NULL,
    dbPort VARCHAR(100) NOT NULL, 
    dbName VARCHAR(100) NOT NULL,
    dbUser VARCHAR(100) NOT NULL,
    dbPass VARCHAR(100) NOT NULL,
    dbTable VARCHAR(100) NOT NULL,

    PRIMARY KEY (sourceTable, partitionKey)
);

This way I could assign a different database connection to each product category or a set of categories. Furthermore we can have multiple tables of the same “type” within one database because the table name is configured, too (dbTable). So we could have the tables order_books, orders_hardware, orders_cds on server A and orders_dvds, orders_shirts on server B.

Limitations
This type of partitioning forces all queries to include a partition key (i.e. a productCategory) and IN clauses on the partition key are not possible or at least very hard to implement. Furthermore a full table scan (i.e. selecting rows based on the orderId column) requires to scan all tables. (This could be optimized if you have a correlation between orderId and productCategory in some way which is the case in our scenario - more on that later.).

MySQL Proxy and JDBC Driver
Yesterday I played a bit with the MySQL Proxy and yes it is hell of an awesome thing! I did some sort of query rewriting and load balancing which was easy at first hand.
The approach for both, MySQL Proxy and JDBC driver, would be the same: Rewrite the queries coming from the application by analyzing them and by using hints put into the SQL by the application (where analyzing does not help).

Assume the following query is issued to look up all orders of a product category:

SELECT * FROM orders WHERE productCategory=‘Books’;

After analyzing the query it is clear that we have to lookup the database configuration for the category ‘Books’, so we could rewrite that query (and send it to a different database connection if needed) like this:

SELECT * FROM orders_books WHERE productCategory=‘Books’;

We could even strip off the WHERE clause if there are only books stored in the table “orders_books”.

That was easy. What about more complex queries like (Attention: Bad database design ahead! It is just an example ;)):

SELECT
    orders.*,
    books.*
FROM
    orders,
    books
WHERE
    orders.productName = books.name

We know that the partition key has to be ‘Books’. But how can our query analyzer know that? It can’t. So there might be queries that are valid but cannot be analyzed. One way is to add a where condition AND orders.productCategory = 'Books', but that might not always be possible or wanted.
Another option would be to add hints like this:

SELECT
    orders.*,
    books.*
FROM
    orders /* HINT: productCategory=’Books’ */,
    books
WHERE
    orders.productName = books.name

I think implementing it as a MySQL Proxy LUA script or a JDBC driver would not make a big difference on the approach. I would prefer MySQL Proxy a lot though.

The pros of this approach are very clear:

  1. It is a transparent solution. Only a few parts of the application need to be changed in best case.
  2. It could be easily released as open source since it is not bound to any type of application - a huge plus IMHO!
  3. It keeps the application code simple.

The cons:

  1. Implementation is very challenging. Analyzing the queries would be the toughest part.
  2. Harder to test against the application since it is a runtime dependency. Would have to come up with a good integration test scenario.
  3. Performance could be an issue since the queries need to be parsed.
  4. Application would need to be changed anyway since we cannot issue some sorts of queries anymore. This could be small or a huge impact depending on the application.

Application Data Access Layer (DAO)
This would be the most straightforward way of implementing partitioning. Since we have total control over our application we could adopt the mechanism in any way to meet our needs. The basic concept would be to use a PartitionFactory like this:

public interface PartitionFactory {
 
    public Connection getConnection(String sourceTable, String partitionKey);
 
    public String getTable(String sourceTable, String partitionKey);
}

Within this solution we have to know which partition to use beforehand. Thus every DAO method has to know where to go. This could be done by adding the partition key to every method or rewriting methods to first find out which partition to use.
The path to this solution is clear and very straightforward, I think.

The pros:

  1. Easy to implement since we know what the application wants and does.
  2. Fast. No need to rewrite queries.
  3. Easier to grasp for (database) developers since they see the dependencies right in the code.

The cons:

  1. Proprietary solution unless embedded into other frameworks like Spring, Hibernate or iBatis.
  2. Might blowup the application code making it harder to understand.
  3. A lot of the application needs to be changed.

Summary
We are still in the process of evaluating every solution. Right now I would love to go for the MySQL Proxy solution be it just for its aesthetic image ;) We need to do a bit more prototyping to see if this would really be a good solution.

Any comment, discussion or hint is highly appreciated!

More to follow soon…

Posted in hscale, java, mysql | 14 Comments »