Why is it hard to scale a database, in layman’s terms?

Question

Paul King · Accepted Answer

There are four main challenges when scaling a database: search, concurrency, consistency, and speed.
 
Suppose you have a list of 10 names. To find someone, you just go down the list.

But what if there are 1 million names? Now you need a strategy for finding something. A telephone book lists the names in alphabetical order so you can skip around. This is a solution to the search problem.

What if 1 million people are trying to use the telephone book at the same time? This is the problem of concurrency. Everyone could wait in one very long line at City Hall, or you could print 1 million copies of the book -- a strategy called "replication". If you put them in people's homes -- a strategy called "distributed" -- you also get faster access.

What if someone changes their phone number? The strategy of replication created a problem, which is that you now have to change all 1 million phone books. And when are you going to change them, because they are all in use? You could change them one at a time, but this would create a data consistency problem. You could take them all away and issue new ones, but now you have an availability problem while you are doing it.

And what if thousands of people are changing their phone numbers every hour? Now you have a giant traffic jam called "contention for resources" which leads to "race conditions" (unpredictable outcomes) and "deadlocks" (database gridlock).

All of these problems have solutions, but the solutions can get very complex. For example, you can issue addendums to the phone books (called "change logs")  rather than reprinting all of them. But you have to make sure to check the addendums all the time. You can distribute new versions of the phone books with a cut-over date, so that everyone switches at the same time to get greater consistency, but now the phone books are always slightly out of date.
 
Now scale this to billions of names in data centers distributed around the world accessed by millions of users.
 
The basic goal of a database is to maintain the illusion that there is only one copy, only one person changes it at a time, everyone always sees the most current copy, and it is instantly fast. This is impossible to achieve at scale when millions of people are accessing and updating trillions of data elements from all over the world.
 
The task of database design, therefore, is to come as close to this illusion as possible using hundreds of interlocking algorithmic tricks.

Yishan Wong · Answer

Here is an explanation for true laymen, i.e. non-technical people who don't understand databases.

(For people who do, just ignore this and the minor technical errors in the analogy)

There are numerous ways in which "scaling" is hard but first I want to explain why scaling is fundamentally hard - the reason is that "scaling" isn't a single activity. In gross terms, it is basically about making a complex system "greater" - usually bigger or larger, typically having to do so very quickly. The key is that a complex system cannot be made bigger or more productive or more efficient in any one simple way - often the effects of the system interact with each other, so if you just expand one part, the other parts usually fail to function with it correctly and you don't get the desired expansion in capability - you almost always have to do some re-engineering.

An analogy: 
Think of a database as a library. It's where you store books, or collections of books (e.g. all the Harry Potter books). In particular, your web application is a library that stores books and makes them available to people who want to read them. Imagine that this library gets featured on TechCrunch and becomes very popular, and suddenly you have to deal with a bunch of new scaling issues. Let's examine how some of them play out, in simplistic terms:

Example one: Many, many books.
Your library is popular, and is growing. In fact, now you have many more books than you started with, and your current building cannot house them all. For a long time, you just put them on the next shelf in the room. But now you have exceeded the size of your humble library building. What you have to do is buy or lease some adjacent buildings, and put the books in those buildings. You might run into issues doing so, because there are a finite number of buildings near you, or maybe real estate prices are very high and it's just not financially sustainable to lease the very expensive building next door. So you have to think carefully in terms of which buildings to lease, and how to find them so that they are near enough and cost-effective to use for book storage.

The real-world analog here is that databases are often stored on hard drives, and hard drives are of finite space, and you can only pack so many hard drives on a computer (in a data center, on a rack). Data centers are now very, very large in order to contend with this common problem but if you are an extremely voluminous library, you may exceed this constraint, and overflow your data center rack's ability to hold hard drives, or even your entire data center and need a new one (rare). Still, the point is that no matter how much room you start off with, you may exceed it, and you may not be able to linearly keep adding more "units" of room (i.e. shelves in the same building) and you might have to take some sort of step jump, like leasing another building or renting another rack or building another datacenter.

Example two: Finding a book among many, many books.
When your library fit comfortable in one room, all you had to do was line up all the books alphabetically and if someone wanted a book, they just searched through the big room until they found the book. It probably took at most 30 minutes.

Now your library is so big that you've rented several buildings. When someone wants a book, they have to walk through (potentially) several buildings to find the book. Let's say that people simply won't stand for this amount of lag time to find a book (similar to how long it takes to load a webpage). They just want to go to the correct building right away, go to the right floor, go to the right shelf, and grab the book they want. They don't want it to take more than the 30 minutes it used to take.

To do that, you need to create a new reference system, called an index. Libraries in real life actually have this problem, and the solution used to be card catalogs. They look like this:

Young people don't know what these are, because they came in the era before computers. Card catalogs are literally a database, but done using small drawers and little pieces of paper (the cards). Because they're so bulky, we digitized them and put them on computers now, which is why if you are younger than ~25, you've probably never seen one.

What the card catalog (the index) does is create a card for every book, and puts them in drawers, sorted by title, author, subject, etc. Then, if you want to look for a book, you go to the card catalog - which fits inside a single room - look up the card corresponding to the book you want, and the card tells you exactly which building, floor, and shelf the book is on. So you spend 10 minutes at the card catalog, 10 minutes walking over to the right building, and then 5 minutes walking up to the right floor and right shelf, and 5 minutes locating the exact book.

When a library gets too large, it has to implement a card catalog to keep book searching times down to a reasonable time (e.g. 30 minutes), otherwise it will take days to search through several buildings for a book and people won't use the library. This feature is qualitatively different from just leasing more buildings and searching them all - and is an example of how you have to come up with a new solution in order to overcome a scaling issue once you've passed a certain threshold - you're not just getting some more shelves, you have to put together the catalog, you have to print up all the cards (which is hard, because you have to go and list all your books and sort them first by author, then title, then subject, etc, and this is a huge pain because you've already got several buildings full of books), and you have to make a special room for the card catalog in your library near the front door and tell everyone to check the card catalog first.

Example Three: Many, many people looking for a book all at once
Let's examine the simplest form of this problem: your library is now so popular that tons of people are visiting. Huge crowds, entire mobs of people. This is not as absurd as it sounds - it is one of the most common problems facing web applications that suddenly become very popular.

So you have so many people who want to look for a book that they can't fit through the door. This sounds absurd because it rarely happens in real life, but think about it - a regular door can admit only about one person per second. So if you have 20 people per second who want to enter your library, you end up getting a huge crowd stuck outside your door waiting to pass through it. More people keep coming and the crowd gets bigger and bigger. Eventually it is so huge that more people are waiting outside the library trying to pass through the door than there are who can use your library, so the majority of users attempting to use your library report an experience that is really just waiting outside and never reading a book. Bad word of mouth ensues, and more people hate you than those who have a satisfying book-related experience.

The obvious solution is to cut more doors in the walls. Okay, so you cut another door. Twice as many people can come in now! You cut more doors. Eventually hundreds of doors. Every wall is filled with doors. Hell, you just remove all the walls! Suddenly so many more people can use the library now! Orders of magnitude more!

But soon you run into another problem. It turns out that there is only a limited amount of space available for people to be standing in front of a shelf looking for a particular book. Maybe they can do so quickly - they scan the shelf and find the book they're looking for and get out of the way. But they still occupy that floorspace for a few seconds, and eventually you are so popular that hundreds of people are looking for the same book (or a book that happens to be at the same vertical space as another book that someone is looking for) that they can't all jam into that spot in front of the shelf.

Once again, waiting crowds end up forming in front of the shelves - maybe all of them, maybe just the ones holding the more popular books. There are a few possible solutions here:

If the crowds are clustered around only the most popular books, you just spread them out throughout the library. But then the books are no longer sorted, they are distributed kind of randomly, so now you have to restructure (re-sort) your card catalog so that people can find the book they want at the new location. That's a pain, but not too much - you just have to update the cards for all the popular books.

If the crowds are everyone, i.e. all books are too popular, or you just have too many people, you can try replication. That is, make a copy of your entire library and lease a whole new set of buildings on the other side of town (or the next block), and send half the people to the new building. You can do this a few more times, and make several replicas. One issue you have to contend with here is that in order to keep the copies of your library up to date, you have to make sure all new books get continually copied between the libraries. One way to do this is to call one library the "master" library and new books only come to this library, and every time it happens, you have someone make a copies of those books and dispatch a runner to send them to all the other library copies. The traffic generated by these runners counts against the number of people who can use your library, so you'll have to impose traffic limits on how many people can use one of the libraries and once it gets too high, you create yet another replica instance of your library.

The key idea here is again, that in the beginning in order to scale against the problem of the crowd, you just cut a new door. That doubled your throughput capacity. You could cut yet another door to increase it again. So for awhile you could scale by cutting out new doors in your walls, until you ran out of walls to cut doors in - you removed all the walls. Once you hit that limit and need to scale further (and remember, the number of people coming to your library just keeps on increasing without end), you have to come up with a wholly new solution, like creating multiple copies of your library. Doing so requires a lot of effort - you have to copy all your books, lease whole new sets of buildings, and then figure out a way to manage the incoming traffic so that each library gets a proper fraction of the traffic. All of that is new infrastructure, and you can't do it at the moment you realize you've cut out your last door because during the time it takes to set all that up the total traffic will continue to rise and you'll get hordes of dissatisfied library users crowding up around the library again. So you have to predict based on the rate of traffic increase when the door-cutting solution isn't going to work anymore and start early on the library-replication.

Example Four: Adding many, many new books
Every library has to stay updated, which means that it has to add new books. Let's say your library represents a very active literary field, and there are tons of new books coming out all the time, constantly.

So you have people who buy the new books, make copies of them at the master library, and then distribute the new books to the shelves everywhere. You even have a good enough handle on the traffic that the runners who add the new books create a certain amount of traffic themselves but you've created enough replica libraries so that the ambient traffic levels are low enough that it's not a problem. Great, things look awesome and you decide you can finally take a day off.

Okay, it turns out that all the books in your library are sorted. That is, they're not just randomly put on shelves, they're ordered by author, or title, or whatever. (in the real world, it's the Dewey Decimal System, which is absurd when you learn it as a kid in elementary school but actually makes sense once you understand a bunch of these database issues, oddly enough) In any case, they are sorted because when someone comes up to a shelf and the card catalog told them a book was on that shelf somewhere, they don't have to scan the whole shelf to find the book - everything on the shelf is in order, so you can just kind of skip to the middle of the shelf and look, and then look left and right, and zero in on the book. In any case, all the books have to be lined up in order so that library patrons can do this.

Well, so the books on the shelf are sorted, and the shelves are generally full. Which means that when the runner inserts a new book into the correct position, they have to push a book off the end and onto the next shelf. But that book pushes yet another book on the other end off and onto the next shelf, and so on. Eventually you get to a shelf that has some gaps in it, so you don't have to push a book off. But the whole process is annoying and takes some time and moreover, you don't want other library patrons or runners taking books off the same shelf or adding new ones at the same time! So when you add a book you have to "lock" the whole shelf, and all the other shelves around it, in case you need to push books from one shelf to the next, and books on that shelf to the next, etc.

This locking creates huge traffic problems, because now instead of being able to look for books while standing right next to each other, multiple library patrons have to wait outside a shelf area while a runner is inserting a new book and shifting books to make room for it. If there are a lot of runners, this will be constantly happening, and lots of library patrons will be waiting on a single runner and even worse, sometimes a library runner will be waiting on another library runner. In real life new books don't come out as often, but if you are running a website where people are posting a lot of things all at once, you essentially have runners inserting new books into the library all the time and you'll run into the problems described above.

And, if they don't do it fast enough, i.e. at all the replicas at the same time, some library patrons won't be able to find a book while others can, and they will get mismatching information.

Solving this is left as an exercise to the reader.

Keep in mind again that doing so means you'll have to come up with new instructions for the runners (maybe they batch together several nearby book updates so they can update one shelf with many books at once), maybe new layout arrangements for the library (maybe you space out all the books so that there are gaps between them; what happens when the gaps are filled?) - but once again, the real lesson is that when you only have a couple runners and a couple new books each day it's not a big deal, but once you cross a critical threshold (e.g. horders of runners and waves of new books) you have to start changing up your entire operation and physical layout, and doing so often requires inventive or creative thinking.

----

That's why scaling a database is hard.

It's actually why scaling any complex system (e.g. a web application, which includes database and other servers, all working in coordination) is hard. Think of an entire research university, including labs, classrooms, dorms, where a library and its usage is only one of many interacting components. Massively increase the traffic and usage of one of those components and you have a scaling problem. To overcome it, you usually have to rethink the entire dynamics underlying your system and rearrange your operational protocols (the algorithms in your code) or the layout of your resources. Doing so is always a creative problem-solving endeavor and often the details differ from one large system to another, so while common solutions exist - I've described some simple ones here - you often have to adapt them to your situation: maybe you don't have easily-leasable land for replica libraries. Maybe your books are all encyclopedias so runners can't carry as many of them on each run. Maybe your climate is extra cold so you can't cut as many doors in your library lest the patrons freeze. What works for one operation may not work the same way for another, so every time you end up having to adapt solutions to the job at hand, always requiring a critical eye to examine the problem and ultimately creating a custom-fit solution.

Lastly, all the while that you are doing this, more and more library patrons are pounding on your door and yelling at you because they can't get to the books they want.

Oh, and your library's probably bleeding money buying all those shelves and leasing all those extra buildings too, so how are you going to make money? And all the venture capitalists don't want to fund you because what kind of business model is letting people borrow the books for free? And what do you mean you don't want to put ads inside the books?

Enjoy! :-D

Assistant · Answer

Scaling a database can be challenging for several reasons:
1. Data Size: As the amount of data grows, it can become harder to store and manage everything efficiently. Larger databases may require more powerful hardware and complex configurations.
2. Performance: When more users access a database simultaneously, it can slow down response times. Ensuring fast performance as the number of users increases often requires advanced techniques.
3. Complexity: Databases have relationships between data (like how customers relate to orders). As you scale, maintaining these relationships and ensuring data consistency gets more complicated.
4. Cost: Upgrading hardware or using complex distributed systems can be expensive. Organizations must balance the cost of scaling with their budget.
5. Technical Limitations: Some databases are designed to work in specific ways. For example, relational databases excel in structured data but might struggle with unstructured data or large volumes.
6. Coordination: In larger setups, coordinating data changes across multiple servers can lead to issues like data conflicts or delays, making it harder to keep everything in sync.
In summary, scaling a database involves managing increasing data size, maintaining performance, handling complexity, controlling costs, and addressing technical limitations—all of which can be quite challenging.

Vishwastam Shukla · Answer

Okay, this might be the lamest analogy but I will go ahead anyways.

Scaling databases can be very similar to effectively using wardrobes at home.

Initial/Happy state: 
My wife and I used to make do with 2 wardrobes in our house initially. All our clothes used to fit in those even when the space in wardrobes was shared and our clothes could be present in either one of them. Moving clothes in and out was easy too.

More clothes ( 2-4x scale):
By now, we needed more than two wardrobes. Luckily in our house, we had space to put an additional pair of those. So we happily bought and started stuffing the new wardrobes with our stuff. This is akin to adding one more database for additional data (loosely speaking).

Higher look-up/search time
We started taking more time to find our stuff since now we had 4 different places to look for it. Often times, we would return empty handed from one wardrobe and go looking for our stuff in another one. Hence, higher search times.

Concurrency
Given lack of order, we would also bump into each other at times trying to look for our stuff in the same wardrobe. Imagine 1000s of user transactions in a real database.

Consistency
At times, my wife would go and move a pile of clothes from one place to other. This would upset my ability to recall which stuff lies where. This often lead to me finding a pair of shorts at the place where I was really looking for a formal shirt.

Vertical Partitioning (again, loosely so)
To solve higher search/look up times, my wife and I decided to cleanly partition our clothes. As a result, she ended up with 3 out of 4 wardrobes. Guess what, it was a fair deal for my cloth search queries. I had considerably lesser clothes and hence I took much lesser time to find them by shooting straight for my wardrobe.

Horizontal Partitioning
My wife had, in the meantime, figured out that within her 3 wardrobes, she would further subdivide and arrange clothes in a certain manner. She decided to split them in latest, not so old and old set of clothes. Not the most optimal strategy I thought, but worked for her. Of course, this only works till she she buys more clothes and needs a fourth wardrobe for her latest stuff. You see?

Replication
I love to wear t-shirts but all of them are actually stored in just one wardrobe. Assume I lock that one and lose the key. How do I find another t-shirt to wear? As a safety net for this hypothetical situation, I setup a small closet and store another set of my t-shirts. This is akin to replicating your most crucial data so that you can retrieve it even if one of your databases becomes unavailable.

Now imagine adding even more clothes and may be planning for a few more members in the family. I could go on and on, but I guess you get the drift by now :).

PS - I use caching for my favorite pair of jeans by throwing them on the couch. It super easy to find them out there :)

Nitin Borwankar · Answer

Adding some aspects that don't seem to have received attention in the above answers.

a) It's possible to scale a database to any size at all as long as you don't query it or update it.  You just keep adding disks and you keep adding data.  This is not a facetious statement but is meant to clarify that databases scale or don't scale depending on the kind of queries you run and whether you ever update the data.

b) So it's possible to scale read-only database much easier than a database that is constantly read/written-to/updated hence the issues related to concurrency.

c) Database scaling also depends on how you read the data ie the complexity of the query. if you look up data just by a unique key then this is a much simpler access pattern than if you read data selecting on multiple fields or columns or attributes. e.g. if all you do is look up your SS# in the SS database once a year this is not a hard problem. It is a query that accesses a very small part of the whole database and gets the data relatively quickly with little or no computation involved.

d) On the other hand if you want to query the US Census database by many demographic factors over the whole US population this is a complex query that has to touch the whole database and sort and filter and do many intermediate computations so this is an example of a complex query which is much harder to perform scalably especially if many people are running their own complex queries and other people are changing or entering data.

So scalability depends on what queries you want to run and what the background read/write/update processes are while you run your query

e) Finally there is the issue of data normalization ie splitting up your data into logical chunks each chunk called a table.  At the time you write the data you split it up for the sake of efficient storage but when you read it you have to join it all over again.  This join process is very expensive as the tables grow larger and the core of the problem with relational databases is not that "SQL doesn't scale" as the common (but wrong) meme goes.  It is that *joins* don't scale well.
Now when you have to join three or more tables and these tables contain millions of rows as social network databases do, then joins cause relational databases to choke and fall over.

Early Web 2.0 companies like Flickr and Twitter had a particularly bad query pattern which joined multiple tables and then filtered them based on users and followers and this caused major scaling issues that led to the meme "SQL doesn't scale"  but it was the nested join in these applications that caused the bottleneck, not the SQL language which was merely a programmer interface to the data.

The query in question had a common pattern that I call "visibility query" pattern.
In Flickr you had the ability to post a photo so that only certain groups could see it.
So when I logged into my account, before rendering my home page Flickr's database had to compute a complicated query to see all the published photos, to which groups they were published, and then create a union of these and intersect it with the groups that I am a member of and then display those photos to me.
Early Flickr database model  design had these queries all happen at the same time on a single database  with massive contention.

Later Twitter had a very similar anti-pattern with similar contention issues.
When I logged in to Twitter it had to compute who I followed and which out of them were not private tweets and then display my timeline - then keep refreshing it by running the same query for each person logged in.  Ignoring the error of the other bad meme (Rails doesn't scale) this was a problem very similar to the Flickr photo visibility problem except in the context of tweets. Note that Flickr used Php (possibly Perl) and no one concluded that Php doesn't scale or that Perl doesn't scale.  But in the Twitter case while Rails certainly had issues, the join costs of the query over millions of rows, many times a second easily dominated Rails performance issues.

So again databases are easy to scale if you dont want to run any query on the data.  Even moderately sized databases can fall over if your query makes the database run around touching every bit of data every few seconds just to check if something has changed.

Finally databases are hard to scale because real world requirements are hard to fulfill simultaneously satisfying the reads writes updates and deletes for thousands of users who are asking complex question directly or implicitly (via rendering of their home page).

Hope this was simple enough to understand.  The fairly rigorous analysis and explanations have been very competently done by others.

Anonymous · Answer

This is how I explain in non-technical terms why scalability can be hard to managers.  This analogy works in general for explaining scalability, not limited to databases only.

Take a cake recipe:

* 1 cup white sugar
 * 1/2 cup butter
 * 2 eggs
 * 2 teaspoons vanilla extract
 * 1 1/2 cups all-purpose flour
 * 1 3/4 teaspoons baking powder
 * 1/2 cup milk

Suppose you have on hand the following quantities of ingredients:

* 2 cups white sugar
 * 2 cups butter
 * 6 eggs
 * 8 teaspoons vanilla extract
 * 8 cups all-purpose flour
 * 8 teaspoons baking powder
 * 4 cups milk

How many cakes can you make with what you have on hand?

Making a cake is a transaction.  The ingredients on hand represent your computing resources.  The resource requirements per unit of output (per cake) is the resource demand.  And the number of cakes you can make represent your capacity.

In the above case you could make 2 cakes only.  After that you would be out of sugar.  Sugar is the ingredient where the demand / computing resources is the greatest.  Sugar is the limiting factor, also called the bottleneck.

So you go and buy more sugar, say another 8 cups.  How many cakes can you now bake, in total, including the two already baked?  The answer is 3.  Do you see it?  Even though you now have plenty of sugar, you are running out of eggs after 3 cakes.   Eggs are now the bottleneck.

An important observation is there is always a bottleneck.  There is always something that limits further scaling of a recipe.  In computing systems the most common bottlenecks are CPU, RAM, disk and network.  These three resources are the basic ingredients that computer systems require.

But suppose you have access to unlimited ingredients?  What then?   You would still have a bottleneck.  But it might be given names like "number of bakers" or "room in the oven" or "electrical capacity of the kitchen" or "cooling system in the kitchen".

Again, there is always a bottleneck.   There is always some computing resources with a demand that is greater than the others.  Scalability is "easy" when the bottleneck is on a factor that is inexpensive for the customer to upgrade.  With computer systems these would be commodity items like disks or CPU's.  Having a customer scale by adding more disks or CPU's is easy scaling.  Hard scaling is like requiring an electrical upgrade to the kitchen in order to support more ovens.  It is expensive, perhaps prohibitively so.

With a database, scalability in the end is bottlenecked on the coordination needed to maintain database consistency.  Think of a bakery with a single manager who runs the cash register.  Every cake must go past the manager to reach the buyer.  It doesn't matter how many cakes the kitchen can make, if the overall process requires that final quality inspection and handling by a single coordinating party.  Coordination is the bottleneck.  Getting beyond that requires not adding more hardware, but rethinking the process of running a bakery from end-to-end.

Like all analogies this is imperfect.  But l hope it is useful, in layman's terms.

Brian Martin · Answer

Brian's principle of scalability: a properly-scaled database provides the end user with a consistent and satisfying user experience, irrespective of the quantity of data stored in the database.

On scaling for capacity (how many billions of records can the database handle):

Q. Can you transport one child from her school to karate practice at an average speed of 25 mph within a specific time frame in your two-passenger Mazda Miata?

A: Yes.

Q. Can you transport three children from their school to karate practice at an average speed of 25 mph within a specific time frame in your two-passenger Mazda Miata?

A: No. It doesn't scale well. Time to "scale" to the higher-capacity Toyota Prius.

Q. Can you transport six children from their school to karate practice at an average speed of 25 mph within a specific time frame in your Toyota Prius?

A: No. It doesn't scale well. Time to "scale" to a higher-capacity soccer mom van.

Q. Can you transport 20 children from their school to karate practice at an average speed of 25 mph within a specific time frame in your soccer mom van?

A: No. It doesn't scale well. Time to "scale" to a 20-passenger school bus.

Q. Can you transport 200 children from their school to karate practice at an average speed of 25 mph within a specific time frame in your single school bus?

A: No. It doesn't scale well. Time to "scale" to five 40-passenger school buses and multiple bus drivers

Q. Can you transport 2,000 children from their school to karate practice at an average speed of 25 mph within a specific time frame if you deploy fifty 40-passenger school buses?

A: Unlikely, because the fifty 40-passenger school buses that would be needed to transport the 2,000 children at 25 mph within the specific time frame would probably exceed the carrying capacity of the existing roads for that specific block of time.

On scaling for speed/performance (how long does the user wait for a response from the database after hitting the enter key):

Q. Can you transport three children from their school to karate practice at an average speed of 150 mph within a specific time frame in your Toyota Prius?

A: No. It doesn't scale well. Time to "scale" to the faster BMW M5.

Q. Can you transport three children from their school to karate practice at an average speed of 300 mph within a specific time frame in your BMW M5?

A: No. It doesn't scale well. In fact, it's not really possible in any vehicle you can purchase off-the-shelf, so you've reached the limit of performance. That is, of course, unless you are willing to throw an unreasonable amount of money at the problem.

A real world example of scaling in layman's terms -- SABRE, the IBM/American Airlines airline reservation/booking system:

From the Wikipedia entry for SABRE:
http://en.wikipedia.org/wiki/Sabre_%28computer_system%29
In the 1950s, American Airlines was facing a serious challenge in its ability to quickly handle airline reservations in an era that witnessed high growth in passenger volumes in the airline industry. Before the introduction of SABRE, the airline's system for booking flights was entirely manual, having developed from the techniques originally developed at its Little Rock, Arkansas reservations center in the 1920s. In this manual system, a team of eight operators would sort through a rotating file with cards for every flight. When a seat was booked, the operators would place a mark on the side of the card, and knew visually whether it was full. This part of the process was not all that slow, at least when there were not that many planes, but the entire end-to-end task of looking for a flight, reserving a seat and then writing up the ticket could take up to three hours in some cases, and 90 minutes on average. The system also had limited room to scale. It was limited to about eight operators because that was the maximum that could fit around the file, so in order to handle more queries the only solution was to add more layers of hierarchy to filter down requests into batches.

More than 1.7 million people travel via air each day in the US. For an airline to remain viable, that airline needs to maintain a minimum revenue rate per mile flown, which means the airline cannot fly planes that are empty.

Matching available flight capacity across all airlines to the individual travel needs of 1.7 million people per day, in such a way that each person can look up and book a travel reservation in under a minute, and so that airplanes don't fly empty, is a non-trivial database problem that encompasses many of the computer science-related issues such as ACID compliance, parallelism and concurrency control, and deadlock detection and resolution raised by others who have posted answers to this question.

Jacob Minz · Answer

Depending on the kind of data in the database, it may or may not be hard to scale the database. Here's is what I feel could be a definition for the layman:

Data:  Information 
Database: A container/repository/vault for data. 
Querying a Database: Asking a question about the data to the database.
Consistency: Is the information correct at the given time?
Performance: How fast did I get the information?
Availability: Is the database available to me at any time of my choice to answer my queries?
Scaling: Are others (could be as many interrogators as we would like them to be) getting the answers/responses at the same time as me when I was the only person asking the question to the database?

To give an example, consider the following sci-fi scenario:
(1) I am asking the Terminator a question. Only he has access to the sacred book which contains all knowledge. He looks up the book and answers the question. I bring 10 of my friends and all of them start to ask different questions to the guy.  We threaten to send him to the Underworld if he does not answer each of our questions immediately.
(2) The Terminator ensures his survival by cloning 10 of himself, and answering each of my 10 friends immediately. We decide not to terminate him that day.
(3) Now each of my 10 friends bring 10 of their friends, and demand the same quality of service from him. The Terminator finds that just cloning himself does not work anymore. Since they spend time fighting to look up the answer in that single book. The Master Terminator saves the day by creating 10 copies of the sacred book and giving a book to each of his 10 clones.  Depending on the type of queries, he could also equally divide the chapters of the book among the clones, and route my friend to the clone with the answer to his question.. , thereby not wasting money in copying the entire book. But this is what Optimus Prime would have done because his prime love is optimization.
(4) The Terminators may have been happy, but now my 1000 friends get smarter and demand that not all answers are 100% correct, and he update the sacred book by what we think is correct. The Terminators pursuit of happiness ends here.. Because the updating Terminator must ask each of his fellow Terminators to stop answering the questions whose answer got updated (until corrections have been made to their books). More the number of books in existence, the slower is this process, and we start to get really angry.
(5) Here the Terminators must take a decision which may spell life or doom for them. Should they always give a correct answer to my friends, or just give an answer to my friends which had been correct in the past? What happens if one of the Terminator dies trying to make my human friends happy, and it turns out to be too much for him?
(6) The Terminators figure out that the dumb humans may not be able to figure out if the answers are correct or not. So they decide to give slightly incorrect answers, until the time all the sacred books have been updated to contain the correct answers. They just decide that it is better to live and fight next day, rather than to die in the battle.

In summary, it really boils down to what questions we are asking of the Terminators, and there is no one strategy fit all situations case. We really need to understand our data and queries to come up with approaches which scales. The strategies might involve doing trade-offs between consistency (correctness of the answer) and availability (ability of the master Terminator to clone himself at will, so some of my friends don't have to attend the funeral of the dead Terminator Clones) and partition tolerance (ability of the Terminator to create copies of the sacred books).  One dude named Brewer, says we can only pick any two of the three while scaling  a distributed database. That is pretty deep , for even a non-lay-person.

Robert Wagner · Answer

1. Because the database does not know what we are trying to accomplish. Instead it sees commands engineered by humans telling it how to organize, access, and update data. Thus, the database does not have enough information to scale itself and is limited to following instructions we give it.

2. In worst cases, which are all too common, our instructions are written in a procedural language that forces serial, rather than parallel, database operations, causing execution times to increase exponentially (O(n^x)). 
3. Database optimizers are simply not very good. They try to figure out what we want by looking at  statistics gathered during previous accesses. That's as hopeless as  trying to 'optimize' your driving by staring into the rear view mirror. 
4. Even if the database knew what we wanted, its solution would be suboptimal because the database field is full of unsolvable problems, technically called NP-complete problems.

Here is an example of a scaling failure that illustrates all four points. AT&T asked me to fix a weekly batch job that took eight days to run. It had not run to completion in over a year. It ran in a half hour when it was written ten years earlier, when the company (then SBC) had ten million long-distance customers. Over the years, as the customer count grew, the job kept running longer. One programmer improved it by splitting it into ten parallel processes on the client (application) side. A later programmer improved it by splitting each of those into ten, giving one hundred parallel client processes. (Is that all they teach in computer science school?) Four programmers tried and failed. When I got the job, there were 120 million long-distance customers.

I reduced the run time from eight days to 30 minutes, using the same database structure, running on the same Oracle server(s), solely by rewriting the application. Here's how:
 * Scrap multiprocessing on the client side. My job ran as a single client process. Parallelism belongs on the database server side, not the client side. 
 * Scrap PL/SQL in which the job had been written. I rewrote it in straight SQL using large scale set-based operations rather than row-at-a-time forced by PL/SQL. That gave the Oracle optimizer a fighting chance to improve the query strategy and use parallelism on the server side. That illustrates 2. Run time is down to 12 hours.

* Study the execution plans. When the optimizer made bad decisions, hold its hand by breaking queries into smaller steps. That illustrates 3. Run time is down to three hours.

* Employ considerable knowledge of subject matter in the first stage, which was creating a set of 30 thousand customers meeting certain criteria involving sales tax. This is one of the unsolvable problems in 4., technically called a Boolean conjunctive query. For an ideal database to do that on its own, it would need detailed knowledge of tax law, the North American Numbering Plan (NANP), and history of AT&T acquisitions. That information could be written into a high level statement of the problem, as in 1. Run time is down to half an hour.

The scalability failure was caused by bad application programming. It wasn't Oracle's fault.

I think the solution to scalable databases is to scrap SQL and the Procrustean relational model. Replace them with a database that takes as input a description of the problem written in something like XSLT. Let the database design, and have the authority to autonomously redesign, storage structures and replicas.Query and update it with a non-procedural language like XQuery, but make it backward compatible with SQL by mapping to legacy schemas. The database that most closely follows that model is MarkLogic.

Greg Kemnitz · Answer

You have to define what “scale a database” means.

One reason an existing database may have a hard time growing beyond a certain size and still meeting application-side performance requirements is it may have a poor schema. You can have a poor schema in both relational and “NoSQL” environments (ie, you may have not designed your documents to match your searches, etc), but this problem is pretty well-known in relational environments.

In the vast majority of situations, the upper-bound for a relational database is driven by the quality of its schema, the level of parameter tuning done on the db engine, the overall host configuration, and the quality of application-side queries.

If the above are good, you can scale a single-instance database for quite a long time before seeing significant performance degradation. Once you get into the hundreds of millions of records range, you may need to start to worry about partitions. Once you exceed a few terabytes or a few billion records, you may be reaching the upper limit of many single-instance databases (at least unless you buy a ginormous and hugely expensive host to run your instance on and tune the heck out of it).

If you’re going to grow much bigger, you may need to start application-side sharding and have a multi-instance database. If you do your sharding well and are careful to have Shared-nothing architecture [ https://en.wikipedia.org/wiki/Shared-nothing_architecture ] in both your app world and your overall database schema (ie, no “cross-instance” joins), you can have hundreds or even more individual database instances in a giant relational database world.

You’ll probably end up with each shard having multiple instances so you can do nearly-instant cutovers and failovers if you go with an architecture of this kind.

The thing that limits relational databases from having app-unaware horizontal scaling is ACID transactions and relational joins. Doing either across a large node-world is quite difficult, which is why sharding is needed, as each shard is effectively its own independent and isolated database.

As for NoSQL databases, they internalize the sharding (called “partitioning” in NoSQL-land) - and for the most part dispense with ACID transactions across the dataworld as well as joins. As for data integrity, they have a notion of “eventual consistency”, typically governed by a notion of “quorum”, meaning that writes to the database can be specified as being “accepted” by a number of nodes - specified by the quorum number - before the write returns to the application.

This allows them to have a largely shared-nothing dataworld without needing all that much in the way of application-side design (although for best results, partition keys and such must be chosen Very Carefully), and since you don’t have joins, you have to structure your data organization so you don’t need them, which may require more planning and design than a lot of people may think.

This answer is a bit rambling, and I may update it later…

Varun Singh · Answer

There are far too many answers already to this question, and some of them are very good, very detailed answers, so I will keep mine short, more like an elevator pitch for why DB scalability is difficult.

First off, Applications drive databases, not the other way around. A lot of SQL scalability pain is due to the app being un-optimized, not the SQL DB.

#1 - SQL Databases hide a lot of computing complexity within a simple language, and getting deep visibility into that complexity, and the performance issues caused by it, is a hard problem. That one line of SQL which magically fetches users from california from one table, and then fetches their orders for the last quarter from another table, and then sorts it, and then totals the orders up so you can show one column in a report that says (Revenues from California in Q3), might seem magically simple, but there is a lot of hard work that goes into making that work, and not understanding that work leads to poor SQL performance.

#2 - Scaling up is easy but limited and expensive, scaling out requires solving some of the hardest computing challenges in the world. You can only add so much RAM, Flash and cores to that one server before it's not feasible to go beyond anymore. 2 sockets with 6-8 cores with around 128GB of RAM and around a 100K IOPS SSD is the sweet spot today in price:performance:power ratios. Going beyond that, even simple stuff like having a readable secondary replica to offload read queries so the primary can handle more write load, requires dealing with replication and the associated lag, which if not handled right can lead to invalid data being shown at the app layer.

#3 - Scaling out is a very hard data distribution and consistency problem; and you can't even use the scaling out "sharding" technique unless you can actually modify the app to support sharding, or use a transparent sharding solution such as ScaleArc and its competitors. Choosing which data should go to which server out of a cluster of two is easy enough, but going beyond that gets harder and harder very quickly, and especially hard when you have to now migrate data between servers to ensure the load on them stays about equal.

#4 - High availability is a very expensive problem to solve right. You either have to throw in a lot of 'spare' resources to achieve close-to-synchronous replication and instant fail-over, or have to design around failure with a certain tolerance to data loss. This is an added dimension that makes it hard to operate very large SQL clusters.

All that said, after having been in this space for as long as I have, I can tell you one thing the myth that "SQL doesn't scale" is just that, a myth. I've seen enough alternate database vendors put up benchmarks on what their systems can do, and have seen SQL do a lot better with more control, resliency, and an easier app development experience.

Anonymous · Answer

Achieving scalability and elasticity is a huge challenge for relational databases. Relational databases were designed in a period when data could be kept small, neat, and orderly. That’s just not true anymore. Yes, all database vendors say they scale big. They have to in order to survive. But, when you take a closer look and see what’s actually working and what’s not, the fundamental problems with relational databases start to become more clear.

Relational databases are designed to run on a single server in order to maintain the integrity of the table mappings and avoid the problems of distributed computing. With this design, if a system needs to scale, customers must buy bigger, more complex, and more expensive proprietary hardware with more processing power, memory, and storage. Upgrades are also a challenge, as the organization must go through a lengthy acquisition process, and then often take the system offline to actually make the change. This is all happening while the number of users continues to increase, causing more and more strain and increased risk on the under-provisioned resources.

To handle these concerns, relational database vendors have come out with a whole assortment of improvements. Today, the evolution of relational databases allows them to use more complex architectures, relying on a “master-slave” model in which the “slaves” are additional servers that can handle parallel processing and replicated data, or data that is “sharded” (divided and distributed among multiple servers, or hosts) to ease the workload on the master server.

Other enhancements to relational databases such as using shared storage, in-memory processing, better use of replicas, distributed caching, and other new and ‘innovative’ architectures have certainly made relational databases more scalable. Under the covers, however, it is not hard to find a single system and a single point-of-failure (For example, Oracle RAC is a “clustered” relational database that uses a cluster-aware file system, but there is still a shared disk subsystem underneath). Often, the high cost of these systems is prohibitive as well, as setting up a single data warehouse can easily go over a million dollars.

The enhancements to relational databases also come with other big trade-offs as well. For example, when data is distributed across a relational database it is typically based on pre-defined queries in order to maintain performance. In other words, flexibility is sacrificed for performance.

Additionally, relational databases are not designed to scale back down—they are highly inelastic. Once data has been distributed and additional space allocated, it is almost impossible to “undistribute” that data.

Raghavendra Kidiyoor · Answer

On a normal week day in the morning, you can walk into Walmart, pick what you want, and check out in no time. There is plenty of parking available, no shoulder fights in the isles, and hardly any waiting at the checkout counters. On a Black Friday however, things are different. You would probably go at the wee hours in the morning, race to find parking, stand in the long line braving cold, and when the doors open fight everyone else to find what you want and finally, wait for hours at the checkout counter to save those five dollars. It is the same Walmart that you visit every week and that day, although there are additional checkout counters open, you would have a miserable life compared to your normal shopping experience. Databases are like Walmarts -- they can handle certain amount of load under normal circumstances. But when there is a stampede, they can't keep up. For the same reason why Walmart cannot increase its size, inventory, staff, etc. infinitely, databases also cannot get bigger or distributed without challenges.

Jari Tavi · Answer

I have a short, though somewhat technical view:

It's "only" a matter of :

1. integrity of data (ACID) and 
2. serialization  of processing, due #1 (queuing theory+latency issues)

If you don't need  #1, #2 becomes far more easy.

If you want to educate yourself, take a look at Distributed Lock Manager (DLM) and Optimistic Concurrency Control (OCC) to get a better picture of the real life challenges.

One of the challenges is that it is quite hard to mix Non-ACID and ACID requirements with same database engine, thus in many cases "same size does not fit all". Even though MySQL is good in certain tasks, it is more closely on-par with commercial products when embedded with ACID "core" such as InnoDB.

NoSQL is a good approach to many, but not all problems as it has very limited approach to concurrency/integrity without some "neat tricks". Low latency (aka. scalable) generic lock manager to implement ACID is quite a task to implement. On the other hand, having a "lockless" NoSQL and 100% fit to the problem, implementing a very fast and low latency subset of required lock management is not "piece of cake", but just "good engineering".

I know that it's not exactly "layman's" answer, but take the

#1 as "accidents may not happen" thus we have traffic signs and traffic lights. Then take the

#2 as  there are 2-10 lanes for traffic, and when the traffic exceedes the designed limits, there will be queues because of #1. Eh?

#3 Go to Destruction Derby to see what happens if you violate #1 ;-)

Shannon Love · Answer

Scalability is hard to grasp. We don't run into it much in daily life. I got it beaten into me because scalability  is vital to understanding most phenomena in the life sciences.

When talking about information systems, we tend to abstract the systems "on paper" with little lines represent communications and in abstraction, those communications occur instantly. In the real world they don't. It takes a finite amount of time for each transaction/communication. Those real world lags feedback into each other, piling up and causing system the system to slow and potentially jam up all together.

Here' an analogy I often use to explain scalability issues in any kind of information management or other complex systems. It applies to all kinds of informational systems requiring communication between parts e.g. governments, economies, a growing company or a DB. People grasp the analog because we've all had to solve this particular problem.

The task is a common one: deciding where to go to eat lunch. As the number of people in the group grows, the time it takes to decide where to eat and the granularity of the choices decreases.

-) Just you: It takes a few seconds of thought. Hmmm, hamburgers, tex-mex of french bistro? Tex-mex. Done. When you get there you can order any dish.

-) Two people: Now it take a minute or so because you've got to go back and forth. "Where do you want to go?", "I don't really care where do you want to go?" Done. Order anything.

-) 3-5 people: Now your up to 5-10 minutes because each person has to be polled, then conflict negotiated. Takes at least 1 minute per person(N) but usually something like 1.5(N) minutes. Order any dish.

-) 5-10: Same problem but now its more like 2N minutes just from the lag in communications.   Order any dish.

-) 10-20: More like an hour because now you have infrastructure issues. "Hmmm, this is a big party, we should call ahead and make sure the restaurant can seat us. You can still get everyone in the same room to communicate but it's going to take a while to poll everyone. Probably order any dish but if everyone orders the same thing, restaurant might run out of ingredients.

-) 20-50: 5-24 hours. Now you can't even get everyone in the same room. Individual diners aren't talking directly to each other.  You've got to break into smaller groups which each appoints a representative to go to a meeting and hash out where to eat. They definitely have to contact the restaurant and make sure they're prepared. Everyone ordering a custom dish is pretty much not an option. Everyone is eating one of three or so dishes.

-) 50-100+: 3-7 days+. Now it's just catering. Elect representatives, representatives have to each take a piece of the problem. Strictly limited ordering options for individuals which must be specified long in advance.

-) 1000+: Now it months or years. You're in the army now. Massive preplanning by  specialist who great a dedicated system that will decide months in advance what will everyone will eat. Individuals get to decide how much ketchup to use on their mystery meat. 
 
Substitute "tables" for "people", "relationships" for "where do you want to eat", "queries" for "restaurant" and you have a descent analogy for most database scaling problems.

It also explains why town hall style democracy doesn't scale. Why successful small scale test programs in education/corrections/business etc using hundreds of test subjects don't scale don't scale to millions in real use. It explains why people's economic intuition doesn't scale from managing personal transactions to economies of hundreds of millions and so on.

Alex Pixley · Answer

Some databases scale very easily and others don’t. As with everything else, there are tradeoffs. The tradeoff in this case is ACID [1] compliance. If you need to be sure that all of your data *operations* are valid, that is difficult to do when more than one machine is involved. Ensuring absolute consistency across multiple machines doesn’t generally happen with out-of-the-box database management systems (although it is possible). If, on the other hand, you are okay with your data being ‘eventually consistent’ across multiple machines, that’s much more easily attained. In those cases, you can easily spread your database across many, many servers. But, depending upon which nodes are queried, you may not get the most up-to-date results. If your process can handle ‘reasonably close’, then this can be a good choice for you (it is almost always faster, too). These scalable databases tend to fall into a group commonly called NOSQL. The less scalable databases tend to be relational databases based on SQL. For most use cases, a relational SQL database will be better, and there is a certain amount of overlap as most relational database management systems (e.g. Oracle, SQL Server, PostgreSQL, etc.) have added various functionality such as support for XML, JSON, column store, etc. that were first popularized by NOSQL systems.

1. ACID - Wikipedia [ https://en.wikipedia.org/wiki/ACID ]

Donovan Kliegg · Answer

Thermo-dynamics.

Computation involves the movement, persistance and substitution of information.  These activities of computation are done in many different ways, but lets just call all of it energy.  If you had infinite amounts of energy you could create a database that scales to any load.  The universe, however, does not permit the use of infinite amounts of energy so the work of computation has to be performed with low energy.

The information itself is immutable, it never gets destroyed, but the universe if constantly shuffling the information.   To fight the constant shuffling, we use machines to gather and aggregate information in bits.  Bits are very useful in the fight against the shuffling because you can gather up an island of information and pretend that an amount of information above a certain level is a "one" and below is a "zero".  As long as you keep refreshing the piles of information, you can keep the ones and zeros around despite the universes constant grinding on the pile.

The piles of information can be made in a lot of ways.  In integrated circuts, it can be the charge pushed into a cluster of atoms.  On flash, its the trapping of electrons in a nanoscale box. On hard drives its the magnetic charge on a thin layer of iron.  All these things have one thing in common, the faster the computation that can be performed with the bits, the more energy it takes to maintain it.  Much of the innovation around computational hardware is reducing the ratios of speed to energy, but there does seem to be that "fast" bits take more energy than "slow" bits.

How does this apply to database scalability?

The speed of bits are never as fast as we need.  To make up for the lack of speed, the information we need gets summarized, duplicated, and spatially organized to improve efficiency.  It's a trick to get around the lack of infinite energy.  By duplicating a lot of limited energy you can do the computational work in parallel.  These tricks to operate in parallel can get quite complex and that is why its is "hard to scale a database".

Andrew Kuan · Answer

The problem with scaling databases lies in the difficulty in handling writes rather than reads. Imagine, for a moment, that you have a database that doesn't change very often but has to handle a million reads in an hour. You could make ten copies of this database (assuming you can easily apply the occasional change after the fact) to ten different servers, each of which now only has to handle one hundred thousand reads in an hour. If the number of reads doubles, you just double the number of servers.
 
Writes, on the other hand, can't be so easily scaled. Let's return to our ten-server example. Imagine that the number of writes is now a million per hour. Every one of those servers has to handle one million writes in order to be up-to-date. While increasing the number of servers enables you to reduce the read load on any one individual server, if you write data to any one of the servers, it needs to be written to all of them -- increasing the number of servers has no effect on the write load each has to sustain. There's no way to scale up a database with heavy writes without inspecting the structure of the database itself.

Anonymous · Answer

The saying “SQL doesn’t scale” was never true or relevant.

There is no technology of any type that scales if you employ it in dumb ways.

People have said “SQL doesn’t scale” because they use it in dumb ways and expect it to handle whatever load or scale of work they throw at it.

* They don’t analyze queries, or create indexes needed for their queries.
 * They don’t provision server capacity needed for the scale of their data.
 * They let data grow and grow without archiving some of it.
 * They let users run unoptimized custom reporting queries.

Christopher Smith · Answer

There seems like a simpler explanation: it's the transactions stupid.

Databases are intrinsically about presenting a single unified source of truth about a massive amount of state. While there is room for cheating (and rules for how much one can), their interface is really designed around the notion of all mutations of the state to be processed serially, which means even you mutate the data in a millisecond (which is exceptionally fast considering databases are required to persist a transaction prior to completion), we're talking 1000 updates per second MAX.

Now, a good database engine will do its darndest to processes as many transactions in parallel as possible to maximize scalability, but that doesn't help that dependancies intrinsically exist between them, particularly since application logic itself tends to manipulate the database very serially.