Database Sharding

Sharding is an essential concept. The term database sharding has been around for years, and there are lots of different definitions.

What is Sharding?

Sharding is the core concept for partitioning and building a truly scalable database infrastructure. The term sharding has been around for a long time, but it became popularized by Google around 2006 with their Bigtable paper. It is certain that scaling data and compute-intensive task existed well before the introduction of Bigtable, but the idea of distributing data widely in a single cohesive infrastructure was not nearly as well known up to that point.

The term sharding is derived from the idea of a shard: a piece or fragment of broken glass or something similar. When you break something brittle, it will end up in many shard.

Sharding, is the ultimate answer to database slowdown

I convered the primary reasons for degraded database performance. As a database grows, it inevitably gets slower and not on a nice linear path, but often in a rapid exponential curve. THe most common reason for the performance degradation curve is database indexes. If you recall, as an index grows in size, depth, and complexity, it invariably slows down. When you have many indexes, this problem is exacerbated, and performance degradation occurs even faster. Virtually every type of DBMS today relies on indexing as a key tool for maintaining acceptable read performance, so regardless of the type of DBMS you have, you are bound to run into this problem.

The Laws of Databases

As a preface to why sharding is the key weapon in accomplishing the goal of a Database, I have develop three simple laws of databases, which directly relate to sharding:

Law 1 : Small databases are fast.
Law 2 : Big database are slow
Law 3 : Keep your databases small.

The Laws of Databases

The moral of the story is, if you can keep your databases small you will have great performance. So how do you do that? With a horizontal scaling approach called sharding.

Let’s look at the typical life cycle of a database, and what you as a database architect or developer must do to deal with it. Here is typical cycle of database performance degradation:

You start a new project, with a nbrand new (and empty) database.
Everything runs fine, and your database is really fast. Your team is happy, new features are rolling out, and all looks good.
You put the database in production, and it grows.
At a certain point you start to see performance degradation.
You start investigating, find out what is slow, and work out some fix for it.
You run the application for a while longer, and your database grows even larger (and likely at an even faster pace).
Now you run into more performance issues (most likely worse than the first time around). Your users and managers start complaining. Maybe it is so bad that people have trouble even accessing the application.
You again dig in, find out why, make some fixes — sometimes againts huge production pressure and then finally you have something that works acceptably again.
And the cycle continues again …………………
……. until you can no longer optimize a single monolithic database.

Give that you have probably reached (or exceeded) the limt of what your single DBMS engine can do, at this point horizontal scaling is your only viable option. If you are running an “always-on” 24X7 application, now you have to really scramble to put a new databases in place.

This cycle is all too comon, and it’s very painful way to go. It a reactive — constantly trying to respond to database performance problems — rather than being proactive and planning an database scaling strategy from beginning.

If you follow the simple laws given above, then you can plan on keeping your database small and fast from beginning, with horizontal scaling using many small database instances. It is simple and easy to design and maintain excellent performance with a relatively small database. Then you don’t end up in the painful cycel of reactive database performance optimization.

What is the ideal size for a single database instance in a sharded, horizontally scalable?

This, of course, varies widely with particular application and use case, but a good rule of thumb is to size each database instance according to the last time your single monolithic database performed well. Keep your instances around that size, and you will be able to grow and scale as needed without grow.

In looking for a good definition for sharding, I found this one on Wikipedia:

Source: http://en.wikipedia.org/wiki/Shard_(database_architecture) (original article footnotes to references omitted)

Horizontal partitioning is a database design principle whereby rows of a database table are held separately, rather than being split into columns. Each partition forms part of a shard, which may in turn be located on a separate database server or physical location.

An example of horizontal partitioning

There are numerous advantages to this partitioning approach. Since the tables are divided and distributed across multiple servers, the total number of rows in each table in each database is reduced. This reduces index size, which generally improves search performance. A database shard can be placed on separate hardware, and multiple shards can be placed on multiple machines. This enables a distribution of the database over a large number of machines, which means that database performance can be spread out over multiple machines, greatly improving performance.

In practice, sharding is far more complex. Although it has been done for a long time by hand-coding. There is a desire to support sharding automatically, both in terms of adding code support for it, and for identifying candidates to be sharded separately. Consistent hashing is one form of automatic sharding to spread to large loads across multiple smaller services and servers.

Where distributed computing is used to separate load between multiple servers (either for performance or reliability reasons), a shard approach may also be useful.

For reference, here is a brief definition of consistent hashing, mentioned in the sharding definition above:

Consistent hashing is a special kind of hashing such that when a hash table is resized and consistent hashing is used, only K/n keys need to be remapped on average, where K is the number of keys, and n is the number of slots. In contrast, in most traditional hash tables, a change in the number of array slots causes nearly all keys to be remapped.

The advantages of consistent hashing with sharding is that it reduces the number of rows (or object) affected as a new physical shard servers are added or removed.

Source: http://en.wikipedia.org/wiki/Consistent_hashing

The wikipedia definition is quite extensive and covers the ide of sharding very thoroughly. Here is a much simple definition that I frequently use. Take a big monolithic database, break it into smaller databases by row or object based on a shard key, and host each sharded database on its own server. The shard key is used as the source for determining where a particular row resides, typically using a hash algorithm based on the value of the shard key.

Breaking a big monolithic database into smaller databases

When this is done correctly, a database can easily scale to big proportions, supporting linear performance improvement as nodes are added to the shard cluster. To obtain linear scalability requires the use of a shared-nothing architecture, in which each shard database instance can perform tasks on its own, without a dependency on other shards for its processing.

If you look carefully at any distributed database, especially those that claim linear scalability, you will see that sharding is used in one way or another.

There are many ways to approach sharding, and the two most importante of these next: black-box sharding and relational sharding.

Black-Box Sharding

There are many ways to approach sharding, and I’ll cover the two most important of these next: black-box sharding and relational sharding.

The most common sharding technique in existence is black-box sharding, meaning that the shard distribution logic is controlled internally by the toolkit or product, and not exposed to the application.

A common method of implementing black-box sharding is to distribute each row (or object) using only the Primary Key(i.e., the unique identifier for a particular data item in a database). The distribution is done via a hash algorithm — which can be as rudimentary as a simple modulus algorithm — or with more advanced methods such as consistent hashing(defined earlier in this chapter).

This method of sharding is highly useful and effective for NoSQL or key-value stores, where any type of object being stored is exclusively defined by the application, and is not inspected by the database engine itself.

Black-box sharding for a key-value store

In the figure, you can see that sharding for a key-value paradigm is relatively simple:

Hash the key
Use the hash to either read or write the value

Because the data value is opaque to the database engine, this is by far the easiest sharding method that exists. It works for simple use cases, the developer and application code are strictly and exclusively responsible for managing all data relationships.

The main characteristics of the black-box sharding approach are as follows:

It is fully automatic and does not require knowledge of the sharding scheme from the developer or architect.
The developer has less control over the sharding strategy with most platforms.
Efficiently organizing data using the black-box approach can be challenging. It requires a careful analysis of your application requirements and a detailed understanding of how the particular black-box implementation functions.
Working with related data, such as maintaining and retrieving lists of child data elements, is left in the hands of the developer to work out the best approach.

Relational Sharding

The alternative approach is what I have termed the relational sharding method. This method is ideally suited to a database cluster using an RDBMS engine, but the techniques can be used with other types of engines, as well.

With relational sharding, the application or database architect defines the sharding schema along the natural data relationships in the data model. The advantage is that related data is co-located in the same physical server, allowing more application queries to be resolved with a single invocation to a given shard server.

Example of a relational sharding model for a game application

To define the relational sharding scheme, an appropriate shard key must be selected. In this case, the playerID is common between the two tables, and in fact defines the relationship between Player and Player Game. By selecting playerID as the key, each shard will always contain the related Player Game data for each Player.

Now obtaining a list of Player Game data elements for a given Player is simple, and can be done from a single invocation to one shard server. Further, because the Player Game data is stored in its own table, there is no need to access all related data each time you read or write Player or Player Game information; you can easily access each independently for a wider variety of purposes. Thus it can be both efficient and flexible.

If you like to use joins in your database code, note that most common joins are easily supported with relational sharding, given that all related data is guaranteed to be stored on the same shard server. Thus you can take advantage of many of the natural capabilities of your DBMS engine when using the relational sharding technique.

Relational sharding can be summed up as follows:

The application or database architect is responsible for defining the sharding strategy, typically along natural relational lines. This technique is not as automatic as black-box sharding, but there are other flexibility and performance tradeoffs, as described earlier.
It is typically used with RDBMS engines, but the technique can be applied to other types of DBMS engines as well.
This method offers flexible access to data, particularly when lists of related data, or joins, are required.