Database sharding and other high scalability features

We encourage users to post events happening in the community to the community events group on https://www.drupal.org.
BogdanN's picture

As information over the Internet becomes more and more revolved around communities and as the need for fast, dynamic content increases, simple caching can't do it anymore. In order to really stand out, a new application logic layer, which would interface with the database abstraction layer and provide tools for easy database sharding would be great. The idea is to be able to split data across several tables, but at the same time keep the caching features and the code intact(meaning that in order to use sharding features, one would only have to plot some rules for the data logic and that's it, no need to redo parts of the code or anything). The idea is inspired by the hibernate sharding feature, and by the ever increasing need for scalability.
Later edit: The nicest thing about sharding is that you can have parts of the data in different databases, spread across multiple servers.

Comments

Tell us more

chx's picture

Most of us have no idea what sharding is. Also, isn't it the database engine's task to provider partitioning?

More about sharding

BogdanN's picture

First of all, sharding isn't partitioning. It's more than that.
I'll try to structure my ideas as diffs between partitioning and sharding.
1. Partitioning practically means splitting a table in smaller parts, according to some rule. This is a database engine's task, therefore database bounded. You've got 2 ways of partitioning data. One is to use merge and create a virtual table, and the other, plain old partitioning. The problem, however, resides not only in the difficult way to implement this and still be able to resolve eventual problems quickly, but also in the limitations in what regards the rules after which the splitting is made. More "bad" data:
- the rules imply one ore more columns to be used. Each of these columns must be part of the primary key or else it won't work.
- there are two types of partitions designed for speed(range and list) and two for easier data maintenance(hash and key). The problem is that range and/or list only have speed gains in a limited area of information types.
2. Sharding means partitioning with any type of rule for content separation. But that's not all to it. The other big advantage is that you can have the table split among different databases on different servers. Let me explain further, by giving an example.
Suppose you have a social network app which is kind of a system where each user can post a number of articles. So, basically, there would be two tables:
- users
- articles
As the database grows larger, the articles table becomes bloated. When talking about several thousands articles, the database server would just freeze. The solution would be a way in which the data could be split not only using one server, but possibly more, and, why not, cheap ones. So, you craft a simple rule, like get the last digit of the user's id (let's call it "x") and all the articles which are written by users with the last digit of the id "x" go in the table articles_x. Thus, you would have 10 articles tables, with articles distributed evenly. Than, move some of the articles tables on a different machine.
Now, the software side. The query's are now re-routed to a new layer (let's call it the shard layer) instead of the database abstraction one. The flow would be something like:
a) issue a "select * from articles where articles.user_id=5436" (in real case scenarios, it would be something like do_query("select","articles",array("user_id" => 5")) or whatever)
b) the shard layer receives the select and gets the last digit of the user id, 6 in this case. It than calls the database abstraction layer with the proper select, which would be "select * from articles_6 where user_id=5436". Just imagine, having to scan a table with 1 million rows instead of 10 millions. That's not all, imagine if 5 of the tables would be on a server, 4 on another and 1 on a cheap, old server. That's cheap, effective scaling!
All the big players started to use it, and I'm talking google, ebay, digg, etc.
More on this can be found here, for example. http://www.datacenterknowledge.com/archives/2007/Apr/27/database_sharding_helps_high-traffic_sites.html
So why this?
Well, I'm a student at Politehnica University in Bucharest, Romania and also a part-time developer-consultant for some large web portals. I needed a way in which to add the ease of use and speed of development of a CMS, with the flexibility of a framework. Drupal seems to do that well, but still lacks some key benefits which are a must when dealing with large-scale projects - seamlessly database sharding integration is one of them.

HSCALE, transparent sharding

markus_petrux's picture

Here's something researching for Transparent Sharding based on MySQL Proxy

http://www.hscale.org

Actually, HSCALE is at version 0.2, too early, yet ...MySQL Proxy, is not in production stage either. But looks promising...

Anyway, this is something to keep an eye into, as it may become a transparent solution for certain scenarios.

PS: where's the difference between partitioning, federation ...and now sharding? :-)

Support for In-Memory DBs

rpfilomeno's picture

I use In-Memory Database for high-performance systems (i really mean high) in my work like Oracle TimesTen. There is a viable opensource alternative that i have tested called MonetDB.

Why would Drupal need such DB? We'll im using Drupal in my work not only for websites but as platform for managing server-to-server communication. Were hitting 2500 transactions/sec at the moment with all the optimization on PHP, apache, and Drupal itself. As we expand this year to 5000/sec MySQL is no longer a viable DB solution for us.

MySQL Cluster?

blender1968's picture

Curious to know why MySQL Cluster (NDB Engine) is not a viable solution for you.

Cheers

NDB is not a realistic

gdd's picture

NDB is not a realistic solution for any Drupal site. It is very badly optimized for highly normalized databases, its best use is for large flat lookup situations. We did a long evaluation of it a while back.

Re: NDB is not a realistic

blender1968's picture

Understood. I was hoping that rpfilomeno would share his experience with MySQL Cluster in comparison to MonetDB.

Cheers

Cluster != Speed

rpfilomeno's picture

I was talking about speed, not High-Availability (HA) that clustering provides. Its like asking why Oracle bought TimesTen DB although Oracle already had a great clustering architecture.

what would change in Drupal

greggles's picture

thanks for all the info on this - can you clarify what would change within Drupal itself to support this? Do you propose writing a contributed module to help with this? Would you provide a patch to core which somehow enables sharding? Would core itself automatically do sharding of some sort?

Also, we've got a half of a master-slave system now (it exists as a patch against Drupal5 but is perhaps not the ideal form and is not committed to core of Drupal6). Can you expand on how this would enhance or replace the concept of master-slave?

--
Open Prediction Markets | Drupal Dashboard

Changes in Drupal

BogdanN's picture

Well, the master-slave system is the most unpleasant method of scaling, I think.
Reasons:
- information redundancy -> the same info sits on each of the slaves
- sync problems (on high loads, the info on the slaves will not be perfectly synchronized at all times)
- the need to setup proxies and large amounts of work on the database side
- on ultra high loads, the master may freeze. A dedicated hardware proxy would do the job, but that's kind of expensive.
The only true advantage is the 99.9999% uptime :). Any of the nodes can drop, and the others take over it's load.
If it's a small database, the information redundancy wouldn't be a problem, but in-memory databases would be much, much faster.
If it's a large database, sharding is the only reasonable way to scale. Think about other advantages:
- the data splitting logic can be as complex as you want it to be: separate "hot" from "cold" pieces of information, easier, more logical caching, etc.
I'm not talking about every web app, but about the large, dynamic ones, where caching itself is just not enough.
Furthermore, I personally sustain the master-master concepts, as they are more appropriate for sharding.
To be honest, I am quite new to Drupal. I've worked for about 4 years with Xaraya, which is an excellent framework and CMS, but it's slowly dying. After researching for a while, I decided Drupal is the best PHP CMS out there. It's fast, reliable and has a vibrant community. I think a patch to the core would be needed, as a module wouldn't have enough insight and access to manipulate the core. The integration of such a feature must be made so that every other module could benefit from it. Not only that, but the native caching system must still work, and more than that, it must benefit from the new data logic.
I am very eager to work with Drupal and add my contributions to the project, so please excuse me if I'm not very Drupal internals savvy, I'm still learning and discovering. From what I've figured so far, the sharding facility would be implemented in a xml file, for example, which would hold the data splitting logic. After that, all the data retrieval and creation would be made automatically by Drupal. The key is to keep all the layers as intact as possible, so that an old implementation of Drupal still benefit from this with a simple core upgrade. In other words, legacy support is a must.
Added thought: I'm thinking that a mapping xml file, in which each table would be mapped to a certain database would be great. For example, articles_0 to articles_4 sit on machine A and articles_5 to articles_9 sit on machine B. The core would know how to issue the db connection based on the query. The advantage? Well, there would be no need for clusters :)

RE: Support for In-Memory DBs

BogdanN's picture

Support for In-Memory Databases is a very good thing also. I'm kind of balanced between in-memory and sharding as tools for scalability. There are however 3 problems with in-memory databases:
1. Don't scale well in what regards the size of the data
2. The risk of data corruption increases
3. In case of failure, loading back the data might be too much of a downtime to spare.
Anyway, I like the idea (though sharding seems more appropriate in what regards large scaling and budget)

Cross-posted to High Performance group

webchick's picture

All of this goes way over my head, but hopefully someone in there can provide better feedback. :D

Other type of DB

rpfilomeno's picture

BTW there is another solution but its not as high-performance as MonetDB. its called P2P DB or Grid Database; it will address a lot of scalability issues with a few trade-off in performance.

Check-out http://wiki.dbgrid.org/index.php, its supports MySQL :D

more info on sharding

Matt V.'s picture

In case anyone is interested in some more background information, here's a write up detailing some pros and cons of sharding.

Is it a good ideea?

BogdanN's picture

After all this talk, is there someone out there who thinks that support for sharding or in-memory databases is a good ideea for a project?

maybe

greggles's picture

It's still not clear to me where in Drupal the changes will need to come. It sounds like they will be in core and I think at this point that we're on the fence about whether or not to take proposals that require changes to core.

I think that people are not very comfortable with sharding data but they are more comfortable with master-slave, so I'm not sure how big of a demand there is for this. I recognize that sharding is a great way to scale big but I'm not sure if it's a great fit for the current and potential Drupal user base.

Even if people like the idea of sharding, I kind of wonder just how much code will need be written (Summer of Code, after all) versus how much of this will just be configuration at the DB level.

Are there any other web applications (or content management systems) that support a system like you propose?

--
Open Prediction Markets | Drupal Dashboard

Support for sharding

BogdanN's picture

Well, there is no other web app that supports sharding out of the box (at least not in PHP). Although I'd love to see it happen, you are right, changes to the core are a delicate issue. I've chosen Drupal because, unlike Joomla, for example, had cleaner code and looked like something fit for a developer, not for someone who just likes shiny stuff out of the box.
I guess I just wanted to combine the joy of creating something ultra high tech with taking part in the Google SoC.
Anyway, I'm going to work on the idea and see what comes of it, then share it with the community, maybe someone will use it.
In the mean time, if this idea doesn't make it to the official list (high chances of that :), I'll just try to work on some other one, if I get elected that is...

I also think that the

phpdude's picture

I also think that the Drupal's database sharding will boost Drupal's scalability.
As you said, I'm affraid it can't be done with just a contributed module. It has to be done with a patch to the core.

For example, the admin can decide on this setup of sharding:

  • users table:
    1. table users-1, DB-1: users 1-10000 (uid)
    2. table users-2, DB-1: users 10001-20000
    3. table users-3, DB-1: users 20001-30000
    4. table users-4, DB-2: users 30001-40000
  • node table:
    1. table node-1, DB-1: users 1-10000 (nid)
    2. table node-2, DB-1: users 10001-20000
    3. table node-3, DB-1: users 20001-30000
    4. table node-4, DB-2: users 30001-40000

If you query user #10281, then Drupal will access the table users-2 in database DB-1

I guess there will be a problem when Drupal needs to join information from different tables in different databases.

new database layer

catch's picture

There's a new database layer patch on it's way into core for D7: http://drupal.org/node/225450

Looks like the only way this could be worked on over the summer would be an extension/modification to that. It's hard to know this week how quickly that patch is going to get in, but I'd be interested to hear how much of what's there would enable sharding and if there's any big barriers to it with the proposed implementation.

I'm also not entirely clear at what level this starts - does it begin with having the user table on one database and the node table on another (or sessions etc.) - or is it specifically splitting the node table into node_1 node_2 node_3 etc.?

Either way this is interesting stuff, and it's good to see it raised. We'd need to know a lot more about specific steps you'd take to get the work done though - probably based on core already having the new PDO and abstraction layer in it.

Triggers

rpfilomeno's picture

Create the master table:

CREATE TABLE mastertable (
id int(5) NOT NULL auto_increment,
owner int(5) default NULL,
data text,
PRIMARY KEY (id)
) ENGINE=MyISAM AUTO_INCREMENT=2 DEFAULT CHARSET=latin1;

Create table1 and table2 the same way.

Then create the trigger on mastertable:

DELIMITER $$

DROP TRIGGER test.shardmanager$$

create trigger test.shardmanager BEFORE INSERT on test.mastertable
for each row BEGIN
IF UNIX_TIMESTAMP()%2 THEN
INSERT INTO table1 (owner,data) VALUES (NEW.owner, NEW.data);
ELSE
INSERT INTO table2 (owner,data) VALUES (NEW.owner,NEW.data);
END IF;
EXCEPTION

END;
$$

DELIMITER ;

You'll have to figure the UPDATE and DELETE part, I feel lazy today ;)

BTW, how do you cancel a trigger from inserting into master table?

Sharding support

BogdanN's picture

These days I need to decide whether I'll use Drupal or Symfony for a large scale web-portal. I guess you can close this proposal :(. It would have been delicate to implement anyway.
If I decide to use Drupal, than I'll post all the improvements I make. If not...
As much as I try, I'm just not sure how Drupal would cope with an environment where every user can choose it's own block layout and theme in terms of a predictive 640 simultaneous users minimum and peaks of up to 2560 (keep in mind that caching tends to null, as the portal would be integrated with a large eLearning system, virtual classrooms, etc.)
Thank you for your time and for making such a great app.

Well I dont know what is out

tjholowaychuk's picture

Well I dont know what is out there for custom block placement modules but it could be as low as a single query per user to retrieve a serialized array of the blocks placement I dont think you should be worried there. As far as scalability as a whole are you planning on using D5 or D6?

vision media
350designs
Print Huge Edmonton Printing Services
Design Inspiration Gallery

Basics first

BartVB's picture

Sharding is a cool concept but IMO it's only applicable for really, really large installs. Flickr or Facebook kind of large. I'm still pretty new with Drupal and haven't had the chance to play with a large scale install of it, but from what I've seen so far there is quite a bit of much lower hanging fruit in the performance department. Sharding is a rather extreme (and pretty complex) solution that's only applicable to a very small handful number of people/companies. IMO optimizing the code that's already here would be something that should be done first.

Re: Basics first

goltiwanisap's picture

maybe, but it's better to implement it on the core so that when your site receiving lots of hits, you can just migrate affected tables or create the succeeding one on the new server.

various tables can be move out of current db. host it in the new one and then re-pointing the new location of that said table on the admin panel.

let say if we're going to display posted messages with size of around 50, we will extract 50 userids from that objects.

and get all the needed user info's from the user tables. sure, you execute 2 queries but then it's a lightweight/simple
queries that any db can handle easily.

Sharding with Drupal will require massive code changes

Etanol's picture

The biggest problem is that sharding does not work well with highly normalized database designs, such as the one Drupal uses. Another thing is that it would make some popular modules unusable - the very first example that pops to mind is views - they would work as long as sharding rules match view rules, which can be impossible to achieve for multiple views at once.

I would love to see a working sharding implementation in Drupal, but the code change would be bigger than between Drupal 4.7 and Drupal 6, and since the feature would be a blessing for less than 0,01% of Drupal users I can't really see it happening.

I've just had an "Archimedes moment" ;-)

Etanol's picture

There are some tables that despite drupal database normalization could be sharded easily - tables created by advanced cache & other similar modules. This would improve scalability significantly.

Im using HSCALE now with

rpfilomeno's picture

Im using HSCALE now with MySQL proxy which allows vertical or horizontal scale depending on how you define the LUA script that re-writes SQL statements and even connections.

useful link for this discussion

PJ-gdo's picture

Here's a link that answers at least a few of the questions above about database sharding:

http://www.codefutures.com/database-sharding/

Transparent database sharding

vzilka's picture

If you'd like to add sharding to your Drupal site, check out http://www.scalebase.com