Database Sharding Explained

All kinds of servers – database servers, web servers, even servers for online games – have a limit on how many simultaneous connections they can accept and how much data they can process. When a server reaches the limit of its capacity, it will appear to slow down or become unresponsive to any applications that are using it. In extreme cases, the server can completely collapse under the strain – requiring the attention of a system administrator before it can be fixed. Downtime (the duration of time in which servers are unavailable) costs US businesses millions of dollars each year.

Various solutions have evolved to combat this. For beginners this means that there is a lot of terminology to become familiar with, and it’s not always easy to see the differences between all of the techniques. In this post, I’m going to introduce you to database sharding in NoSQL systems, and to some of the other common techniques you’ll encounter.

Scaling Up vs. Scaling Out

There are two strategies for increasing how much work a database can do: scaling up and scaling out.

Scaling up (also known as vertical scaling) refers to upgrading a server – adding more memory, a faster processor, or larger storage devices. These can all help increase the amount of traffic a server can support, and the amount of data it can process in a reasonable period of time.

Scaling out (or horizontal scaling) involves adding more servers to the task. This is more complicated to do, but can provide much larger increases in capacity. The additional servers can either act as backup devices – coming online when the main server fails, so that the application can continue – or the work and network traffic can be shared between all of the servers.

Many NoSQL databases have been built with horizontal scaling in mind. However, that doesn’t mean that there is never a place for vertical scaling.

There aren’t really any important techniques for using a scaled-up system. It does what it did before, but (hopefully) better and faster.

When more servers are added to the network, the group of machines assigned to particular task is often called a cluster. There are few common techniques used when you have multiple machines.

	Vertical Scaling	Horizontal Scaling
Hardware costs	Can be very expensive. Top-of-the-line components are pricey.	Servers can be less-powerful. When you need more capacity, add a new, cheap, server.
Software costs	No additional charges.	License fees for another operating system and database software.
Space	No additional space used.	More servers = more space required in the data center.
Power consumption	Very little additional power used.	More servers = more power used.
Ease of implementation	Very easy.	Can be complicated, requiring well-trained personnel.
Capacity increases	Even the best components still have a limit.	Although there are some limiting factors, you can usually keep adding servers.

Database Mirroring and Replication

Database mirroring is one of the techniques traditionally used with database servers; usually as part of a disaster-recovery plan and not to improve the day-to-day performance of the system.

It involves storing a complete copy of the database on a different server. Should the primary server fail, the backup machine can come online and pick up where the primary left off. This reduces downtime from being how long it takes for an engineer/administrator to get the server back online, to the minutes or seconds it takes for the system to detect a failure and activate the backup machine.

The process for keeping the database synchronized is replication.

Load Balancing

Load balancing is used in conjunction with other techniques to reduce the strain on individual servers by spreading the load across multiple machines. It works by continually monitoring how busy each server in a cluster is, and rerouting network traffic to the machines that are doing less work. It does not deal with the issues surrounding how all of the databases are synchronized.

Traditionally, load balancing was done at a hardware level using specialized network routers, or software running on dedicated machines on the network. In MMORPG design, for example, clients often talk to the game through bespoke proxy server software that can route their message to a machine which has enough capacity to deal with the action.

Table Partitioning and Sharding

In modern applications, the simple problem with database mirroring and replication is that tables are so big – often with billions of rows. Unless the contents of the table itself are divided up across multiple servers, the machine is going to struggle to process it.

Vertical partitioning does not help. This is putting tables their own server – so the entire database is spread across a cluster – but again, when you have over a billion rows in the table, it may still be too large for one server to cope with.

Sharding, also known as horizontal partitioning, reduces the burden on individual database servers by spreading the rows of tables across multiple machines. Each server contains the table structure, but only a small subset of the total data that is contained in it. As each instance of the database is only dealing with part of the data, they do not become bogged down or suffer from indices that are too large to be useful.

The usual approach to sharding is for the database designer to write a sharding function – a small routine that uses information in a row to decide on which server it should be stored. For example, a sharding function might look at a key/value pair that contains a country name and put all rows from the USA on one server, and all rows from Europe on another.

As most NoSQL databases have been built with a scale-out mentality, sharding usually works very well and most of them have support for it. Setup time is usually minimal.

Table partitioning is not, however, a guarantee that the data will be safe and always accessible. Database mirroring and load balancing are still extremely useful for ensuring that data is available even if servers fail. Many NoSQL systems also have features for mirroring and replication, in addition to sharding. So if you need a highly-available, scalable, and high-performing database system then those are the ones to look at.