3 ms·

assuming that local access is cheaper than distribution, wouldn't a merge sort be better?

Jensson 4y ago
I assumed the data is spread out in a set of databases. Reading even just a few terabytes of data into a single server is slow and expensive, and then you'd still need to spend a few days cpu time to sort it locally. And for a bit larger datasets you wont be able to handle it with most computers, I think most large companies has some data sets at about a petabyte, so I don't think assuming that amount of data is unreasonable. I worked with data at about an exabyte, not many has that much data, but it starts to get hard to do it locally at just one millionth that amount. But maybe I'm over estimating how common that is. Another question is how much time it takes. Lets say we have small data, a few gigabytes or so. Sorting that would still take about 10 seconds to a minute, which is annoyingly slow to users. If that data is distributed over many computers that can each read a subset, then the distributed sorting will go much much quicker so you can do a full sort over the entire dataset within a normal 100ms request SLO. But this assumes that the user needs to sort using arbitrary comparisons, otherwise it is of course much better to just pre sort the dataset and serve it that way. And even if you have all data locally, if that data doesn't fit in memory distributed would still help. Network within a server cluster is typically faster than communicating with local persistent storage, so distributed you can read it once and send it to the different workers instead of having to read and write it over and over as you'd have to do if you sorted it locally. So in other words, making a computer read X data from disk takes about the same time as getting that data to a distributed set of computers, since you can send data faster than you read it, and this is the worst case for distributed. Note: This assumes that we can't precompute the sort, meaning the user asks for some ordering they want the items to be sorted in and we have to provide that on the fly. Pre-sorting data once is easy, so I'm not sure why we would discuss that case. Also networking tends to cost a ton more when you run it on others computers like AWS or Azure or Google cloud, then it might not be as viable. Don't they take like 10x more than the cost of networking? But when I worked at Google we got to run distributed jobs juggling a petabyte of data without anyone asking questions, so it can't be that expensive. As long as you didn't make an infinite loop in your distributed program or so nobody cares, and even when a guy did that his job ran for a couple of weeks before people noticed that our compute quota ran out, so I'm pretty sure it can't be expensive. But that amount of networking would probably cost a fortune in Gcloud.

I assumed the data is spread out in a set of databases. Reading even just a few terabytes of data into a single server is slow and expensive, and then you'd still need to spend a few days cpu time to sort it locally. And for a bit larger datasets you wont be able to handle it with most computers, I think most large companies has some data sets at about a petabyte, so I don't think assuming that amount of data is unreasonable. I worked with data at about an exabyte, not many has that much data, but it starts to get hard to do it locally at just one millionth that amount. But maybe I'm over estimating how common that is. Another question is how much time it takes. Lets say we have small data, a few gigabytes or so. Sorting that would still take about 10 seconds to a minute, which is annoyingly slow to users. If that data is distributed over many computers that can each read a subset, then the distributed sorting will go much much quicker so you can do a full sort over the entire dataset within a normal 100ms request SLO. But this assumes that the user needs to sort using arbitrary comparisons, otherwise it is of course much better to just pre sort the dataset and serve it that way. And even if you have all data locally, if that data doesn't fit in memory distributed would still help. Network within a server cluster is typically faster than communicating with local persistent storage, so distributed you can read it once and send it to the different workers instead of having to read and write it over and over as you'd have to do if you sorted it locally. So in other words, making a computer read X data from disk takes about the same time as getting that data to a distributed set of computers, since you can send data faster than you read it, and this is the worst case for distributed. Note: This assumes that we can't precompute the sort, meaning the user asks for some ordering they want the items to be sorted in and we have to provide that on the fly. Pre-sorting data once is easy, so I'm not sure why we would discuss that case. Also networking tends to cost a ton more when you run it on others computers like AWS or Azure or Google cloud, then it might not be as viable. Don't they take like 10x more than the cost of networking? But when I worked at Google we got to run distributed jobs juggling a petabyte of data without anyone asking questions, so it can't be that expensive. As long as you didn't make an infinite loop in your distributed program or so nobody cares, and even when a guy did that his job ran for a couple of weeks before people noticed that our compute quota ran out, so I'm pretty sure it can't be expensive. But that amount of networking would probably cost a fortune in Gcloud.