You are currently browsing the tag archive for the ‘Sharding’ tag.
I like to ride motorbikes. Currently I ride a BMW K1200S – a sports tourer that is both fast and comfortable on the road. Before that I had a five year affair with a BMW R1150GS which took me to all sorts of off-the-beaten-track destinations before we abruptly parted company with me flying through the air in one direction as my bike was smashed in the other direction by criminals in a getaway car.
Most motorbike enthusiasts have, like me, owned a few in their lifetimes and in most cases they are of differing types. A road bike, no matter how much you are prepared to spend, can barely travel faster than walking pace on a good quality dirt road because, apart from the obvious things like tyres and suspension, the geometry is all wrong. The converse is similar – a good dirt bike is frustrating, dull and downright dangerous to ride on a road.
Bikers understand the issues around suitability for purpose and compromise more than most (such as car drivers). Our lottery winning fantasies have a motorbike garage filled, not simply with classics or expense, but with a bike suitable for every purpose and occasion – track, off-road, touring, commuting, cafe racing and every other obvious niche. Some may even want a Harley Davidson for the odd occasion that one would want to ride a machine that leaks more oil than fuel it uses and one would want to travel in a perfectly straight line for 200 yards before it overheats and the rider suffers from renal damage.
But I digress. Harley Davidson hogs, fanbois (or whatever the collective noun is for Harley Davidson fans) can move on. This post has nothing to do with you.
There is nothing in the motorbike world that is analogous to the broad suitability of the SQL RDBMS. SQL spans the most simple and lightweight up to complex, powerful and expensive – with virtually every variation in between covered. It is not just motorbikes, a lot of products out there would want such broad suitability – cars, aeroplanes and buildings. SQL is in a very exclusive club of products that is solves such a broad range of the same problem, and in the case of SQL, that problem is data storage and retrieval. Also SQL seems to solve this problem in a way that the relationships between load, volume, cost, power and expense is fairly linear.
SQL’s greatest remaining strength and almost industry wide ubiquity is that it is the default choice for storing and retrieving data. If you want to store a handful of records, you might as well use a SQL database, not text files. And if you want to store and process huge amounts of transactional data, in virtually all cases, a SQL database is the best choice. So over time, as the demands and complexity of our requirements has grown, SQL has filled the gaps like sand on a windswept beach, and exclusively filled every nook and cranny.
We use SQL for mobile devices, we use SQL for maintaining state on the web, we use SQL for storing rich media, and use it to replicate data around the world. SQL has, as it has been forced to satisfy all manner of requirements, been used, abused, twisted and turned and generally made to work in all scenarios. SQL solutions have denormalization, overly complex and inefficient data models with thousands of entities, and tens of thousands of lines of unmaintainable database code. But still, surprisingly, it keeps on giving as hardware capabilities improve, vendors keep adding features and people keep learning new tricks.
But we are beginning to doubt the knee jerk implementation of SQL for every data storage problem and, at least at the fringes of its capabilities, SQL is being challenged. Whether it be developers moving away from over-use of database programming languages, cloud architects realising that SQL doesn’t scale out very well, or simply CIO’s getting fed up with buying expensive hardware and more expensive licences, the tide is turning against SQL’s dominance.
But this post is not an epitaph for SQL, or another some-or-other-technology is dead post. It is rather an acknowledgement of the role that SQL plays – a deliberate metronomic applause and standing ovation for a technology that is, finally, showing that it is not suitable for every conceivable data storage problem. It is commendable that SQL has taken us this far, but the rate at which we are creating information is exceeding the rate at which we can cheaply add power (processing, memory and I/O performance) to the single database instance.
SQL’s Achilles heel lies in its greatest strength – SQL is big on locking, serial updates and other techniques that allow it to be a bastion for consistent, reliable and accurate data. But that conservative order and robustness comes at a cost and that cost is the need for SQL to run on a single machine. Spread across multiple machines, the locking, checking, index updating and other behind the scenes steps suffer from latency issues and the end result is poor performance. Of course, we can build even better servers with lots of processors and memory or run some sort of grid computer, but then things start getting expensive – ridiculously expensive, as heavy metal vendors build boutique, custom machines that only solve today’s problem.
The scale-out issues with SQL have been known for a while by a small group of people who build really big systems. But recently the problems have moved into more general consciousness by Twitter’s fail-whale, which is largely due to data problems, and the increased interest in the cloud by developers and architects of smaller systems.
The cloud, by design, tries to make use of smaller commodity (virtualized) machines and therefore does not readily support SQL’s need for fairly heavyweight servers. So people looking at the cloud find that although there are promises that their application will port easily, are obviously asking how they bring their database into the cloud and finding a distinct lack of answers. The major database players seem to quietly ignore the cloud and don’t have cloud solutions – you don’t see DB2, Oracle or MySQL for the cloud and the only vendor giving it a go, to their credit (and possibly winning market share), is Microsoft with SQL Server. Even then, SQL Azure (the version of SQL Server that runs on Azure) has limitations, and size limitations that are indirectly related to the size of the virtual machine on which it runs.
Much is being made of approaches to get around the scale out problems of SQL and with SQL Azure in particular, discussions around a sharding approach for data. Some of my colleagues were actively discussing this and it led me to weigh in and make the following observation:
There are only two ways to solve the scale out problems of SQL Databases
1. To provide a model that adds another level of abstraction for data usage (EF, Astoria)
2. To provide a model that adds another level of abstraction for more complicated physical data storage (Madison)
In both cases you lose the “SQLness” of SQL.
It is the “SQLness” that is important here and is the most difficult thing to find the right compromise for. “SQLness” to an application developer may be easy to use database drivers and SQL syntax; to a database developer it may be the database programming language and environment; to a data modeller it may be foreign keys; to a DBA it may be the reliability and recoverability offered by transaction logs. None of the models that have been presented satisfy the perspectives of all stakeholders so it is essentially impossible to scale out SQL by the definition of what everybody thinks a SQL database is.
So the pursuit of the holy grail of a scaled out SQL database is impossible. Even if some really smart engineers and mathematicians are able to crack the problem (by their technically and academically correct definition of what a SQL database is), some DBA or developer in some IT shop somewhere is going to be pulling their hair out thinking that this new SQL doesn’t work the way it is supposed to.
What is needed is a gradual introduction of the alternatives and the education of architects as to what to use SQL for and what not to – within the same solution. Just like you don’t need to store all of your video clips in database blob fields, there are other scenarios where SQL is not the only option. Thinking about how to architect systems that run on smaller hardware, without the safety net of huge database servers, is quite challenging and is an area that we need to continuously discuss, debate and look at in more detail.
The days are the assumption that SQL will do everything for us is over and, like motorcyclists, we need to choose the right technology or else we will fall off.
Database sharding, as a technique for scaling out SQL databases, has started to gain mindshare amongst developers. This has recently has been driven by the interest in SQL Azure, closely followed by disappointment because of the 10GB database size limitation, which in turn is brushed aside by Microsoft who, in a vague way, point to sharding as a solution to the scalability of SQL Azure. SQL Azure is a great product and sharding is an effective (and successful) technique, but before developers that have little experience with building scalable systems are let loose on sharding (or even worse, vendor support for ‘automatic’ sharding), we need to spend some time understanding what the issues are with sharding, the problem that we are trying to solve, and some ways forward to tackle the technical implementation.
The basic principles of sharding are fairly simple. The idea is to partition your data across two or more physical databases so that each database (or node) has a subset of the data. The theory is that in most cases a query or connection only needs to look in one particular shard for data, leaving the other shards free to handle other requests. Sharding is easily explained by a simple single table example. Lets say you have a large customer table that you want to split into two shards. You can create the shards by having all of the customers who’s names start with ‘A’ up to ‘L’ in one database and another for those from ‘M’ to ‘Z’, i.e. a partition key on the first character of the Last Name field. With 13 characters in each shard you would expect to have an even spread of customers across both shards but without data you can’t be sure – maybe there are more customers in the first shard than the second, and maybe you particular region has more in one than the other.
Lets say that you think that it will be better to shard customers by region to get a more even split and you have three shards; one for the US, one for Europe and one for the rest of the world. Although unlikely, you may find that although the number of rows is even that the load across each shard differs. 80% of your business may come from a single region or even if the amount of business is even, that the load will differ across different times of the day as business hours move across the world. The same problem exists across all primary entities that are candidates for sharding. For example, your product catalogue sharding strategy will have similar issues. You can use product codes for an even split, but you may find that top selling products are all in one shard. If you fix that you may find that top selling products are seasonal, so today’s optimal shard will not work at all tomorrow. The problem can be expressed as
The selection of a partition key for sharding is dependant on the number of rows that will be in each shard and the usage profile of the candidate shard over time.
Those are some of the issues just trying to figure out your sharding strategy – and that is the easy part. Sharding seems to have a rule that the application layer is responsible for understanding how the data is split across each shard (where the term ‘partition’ is applied more to the RDBMS only and partitioning is transparent to the application). This creates some problems:
The application needs to maintain an index of partition keys in order to query the correct database when fetching data. This means that there is some additional overhead – database round trips, index caches and some transformation of application queries into the correctly connected database query. While simple for a single table, it is likely that a single object may need to be hydrated from multiple databases and figuring out where to go and fetch each piece of data, dynamically (depending on already fetched pieces of data), can be quite complex.
Any sharding strategy will always be biased towards a particular data traversal path. For example, in a customer biased sharding strategy you may have the related rows in the same shard (such as the related orders for the customer). This works well because the entire customer object and related collections can be hydrated from a single physical database connection, making the ‘My Orders’ page snappy. Unfortunately, although it works for the customer oriented traversal path, the order fulfilment path is hindered by current and open orders being scattered all over the place.
Because the application layer owns the indexes and is responsible for fetching data the database is rendered impotent as a query tool because each individual database knows nothing about the other shards and cannot execute a query accordingly. Even if there was shard index availability in each database, then it would trample all over the domain of the application layers’ domain, causing heaps of trouble. this means that all data access needs to go through the application layer , which create a lot of work to implement an object implementation of all database entities, their variations and query requirements. SQL cannot be used as a query language and neither can ADO, OleDB or ODBC be used – making it impossible to use existing query and reporting tools such as Reporting Services or Excel.
In some cases, sharding may be slower. Queries that need to aggregate or sort across multiple queries will not be able to take advantage of heavy lifting performed in the database. You will land up re-inventing the wheel by developing your own query optimisers in the application layer.
In order to implement sharding successfully we need to deal with the following:
The upfront selection of the best sharding strategy. What entities do we want to shard? What do we want to shard on?
The architecture and implementation of our application layer and data access layer. Do we roll our own? Do we use an existing framework?
The ability to monitor performance and identify problems with the shards in order to change (and re-optimise) our initially chosen sharding strategy over time as the amount of data and usage patterns change over time.
Consideration for other systems that may need to interface with our system, including large monolithic legacy systems and out-of-the-box reporting tools.
So some things to think about if you are considering sharding:
Sharding is no silver bullet and needs to be evaluated architecturally, just like any other major data storage and data access decision.
Sharding of the entire system may not be necessary. Perhaps it is only part of the web front-end that needs performance under high load that needs to be sharded and the backoffice transactional systems don’t need to be sharded at all. So you could build a system that has a small part of the system sharded and migrates data to a more traditional model (or data warehouse even) as needed.
Sharding for scalability is not the only approach for data – perhaps some use could be made of non-SQL storage.
The hand coding of all the application objects may be a lot of work and difficult to maintain. Use can be made of a framework that assists or a code generation tool could be used. However, it has to be feature complete and handle the issues raised in this post.
You will need to take a very careful approach to the requirements in a behavioural or domain driven style. Creating a solution where every entity is sharded, every object is made of shards, and every possible query combination that could be thought up is implemented is going to be a lot of work and result in a brittle unmaintainable system.
You need to look at your database vendors’ support of partitioning. Maybe it will be good enough for your solution and you don’t need to bother with sharding at all.
Sharding, by splitting data across multiple physical databases, looses some (maybe a lot) of the essence of SQL – queries, data consistency, foreign keys, locking. You will need to understand if that loss is worthwhile – maybe you will land up with a data store that is too dumbed down to be useful.
If you are looking at a Microsoft stack specifically, there are some interesting products and technologies that may affect your decisions. These observations are purely my own and are not gleaned from NDA sourced information.
ADO.NET Data Services (Astoria) could be the interface at the application level in front of sharded objects. It replaces the SQL language with a queryable RESTful language.
The Entity Framework is a big deal for Microsoft and will most likely, over time, be the method with which Microsoft delivers sharding solutions. EF is destined to be supported by other Microsoft products, such as SQL Reporting Services, SharePoint and Office, meaning that sharded EF models will be able to be queried with standard tools. Also, Astoria supports EF already, providing a mechanism for querying the data with a non SQL language.
Microsoft is a pretty big database player and has some smart people on the database team. One would expect that they will put effort into the SQL core to better handle partitioning within the SQL model. They already have Madison, which although more read-only and quite closely tuned for specific hardware configurations, offers a compelling parallelised database platform.
The Azure platform has more than just SQL Azure – it also has Azure storage which is a really good storage technology for distributed parallel solutions. It can also be used in conjunction with SQL Azure within an Azure solution, allowing a hybrid approach where SQL Azure and Azure Storage play to their particular strengths.
The SQL azure team has been promising some magic to come out of the Patterns & Practices team – we’ll have to wait and see.
Ayende seems to want to add sharding to nHibernate.
Database sharding has typically been the domain of large websites that have reached the limits of their own, really big, datacentres and have the resources to shard their data. The cloud, with small commodity servers, such as those used with SQL Azure, has raised sharding as a solution for smaller websites but they may not be able to pull off sharding because of a lack of resources and experience. The frameworks aren’t quite there and the tools don’t exist (like an analysis tool for candidate shards based on existing data) – and without those tools it may be a daunting task.
I am disappointed that the SQL Azure team throws out the bone of sharding as the solution to their database size limitation without backing it up with some tools, realistic scenarios and practical advice. Sharding a database requires more than just hand waving and PowerPoint presentations and requires a solid engineering approach to the problem. Perhaps they should talk more to the Azure services team to offer hybrid SQL Azure and Azure Storage architectural patterns that are compelling and architecturally valid. I am particularly concerned when it is offered as a simple solution to small businesses that have to make a huge investment in a technology and and architecture that they are possibly unable to maintain.
Sharding will, however, gain traction and is a viable solution to scaling out databases, SQL Azure and others. I will try and do my bit by communicating some of the issues and solutions – let me know in the comments if there is a demand.