Of course. But there are solid examples from web1.0 and before that did more than twitter, and scaled to more users.
Twitter is pretty simple in terms of functionality.
climbing Mt Everest/K2 has been done many times already, but it's still hard; and not something taken lightly
I just don't like gloating on someone else's mistakes and failures (essentially kicking someone who's already on the ground), especially when I'll probably have my own set of spectacular f-ups to deal with related to my own startup
Uh... yes it is. All scaling problems are database problems. ALL of them. They can be solved by different strategies such as caching, distributed design, etc. But at the end of the day the problem is always that you cant get to the data fast enough. That is a database problem.
Yes, I am defining database as "anything that stores data" It does not have to be SQL for me to consider it a database problem. And in fact my solution is well above the sql level.
You suggest storing all users physical addresses in memory across multiple machines. You also advocate "shard splitting" a la B-tree indexes which split when the node's population reaches 2n. OK, so when a split occurs, how do you maintain that massive table in memory. Do you lock it? Do you examine your existing queue of requests (which may soon point to the wrong node)? How do you handle new queue requests during "shard split maintenance"?
Calling these "database problems" is waving your hands. Why not just call them "computer problems"?
Well ok. I dont have to call them database problems, but I object to someone saying they are not database problems. I agree it is a bit of semantics and I would not have brought it up if he hadnt. Although I have to say I consider this work (and the good questions you ask) to be in the database domain.
Regarding when shard split how you maintain the table, the easy answer is Terracotta. It is amazing for this and handles all that kind of stuff totally in the background. If you didnt have terracotta it would be a harder problem indeed. It handles locking and all of that magic for you. I highly recommend it. Regarding how you handle queue requests while the split is going on, what happens is that while the split is happening, the original shard continues to respond, but all new updates are sent to the old shard and the new one that is being created in the split, so during a split there is addition messaging going on. Once its done, the original shards range of users is cut back, but actually it is still storing all the old data. At that point you can delete the data that has been moved to the new shard - though this is not necessary.
I dont understand. I am saying that Terracotta, which is an open source product, handles the in memory table and synching stuff I was talking about and that you asked about. Its like you dont have to write a C compiler and you dont need to write linux because someone has done the heavy lifting for us. So as far as that specific issue my point was just that the solution is available in an excellent well tested product that lots of folks are using. By the way, I am actually working on exactly these sets of issues -- not to say there are not bigger minds than mine working on high velocity apps, but it is what I spend most of my time on.
When you talk about such an app it's a good idea to have some basic numbers in mind like .5 second average time to respond to an incoming message and 5seconds worst case. (Picked from thin air but I tend to stick with 1x average 3-10x worst case.)
Now as you scale to 50 or so servers they will start to fail with some regularity and you can't reboot and or rebuild in five seconds so we need to have redundant systems ready. Splitting a shard probably takes longer than five seconds so you need to be proactive about such things. So we need an active rebalancing between shard so they can quickly pass around their load and fast failover incase things fail. These are DB problems but they are only problems because they system need to keep responding quickly as parts of the DB fail.
But this is still DB centric how do you load balance incoming and outgoing requests? (Routing each existing user to the same system every time and letting each system lock data when they want to change their password etc.) How do we recover from data corruption? How do we notice an outgoing or incoming mail server is down? You also have n^2 number of connections between systems as you grow can we keep that many sockets open? (More of an issue is we are segregating the network.) Etc.
PS: These are not hard problems by themselves but they are linked. And there are a lot more where they came from.
Most scaling problems are database problems. Not all.
For example, I load tested my last rails app (load testing is my background-I have consulted for major pharma, tax, and other companies) and on a wimpy inherited server, processor maxed out first for the rails processes. I popped in a second CPU, then was able to get to the point where we could support 200 concurrent users, which was all we needed at the time.
I have seen limitations on bandwidth, firewall problems, load balancer misconfiguration, poorly written queries, memory usage,processor usage, thread deadlocks, and licensing limits (max database connections on a trial license) all be bottlenecks. At the larger scale, yes, database is more often the problem, but it's not clear twitter should be using a database in the way they are, anyway. Your statement goes too far.
Yeah, certainly at the small scale there can be a myriad of reasons why a system doesn't perform. At a large scale its hard to imagine real world scenarios where storage has not been the bottleneck. Regarding whether twitter should be using a database, unless they dont want to store there data they need a "database". Does that mean sql? No. It just means storage. As paul Graham has demonstrated a file system can be a great database. But it still a database.
Think about a MMO with 100 users in 1 room, the number of relationstips in that room is (n-1)^2. Add 100 more users walking around and you now need to send 4x as many location updates. You will quickly run out of bandwidth long before storing that much information is a problem.
Now consider a voting system you have 1,000 items and 1,000 users and you want to show how much people like them like each item? How well does that work when there are 100,000 users and 100,000 items?
Its fascinating funny how you are so smart you can't even deign to share your wisdom on this. If I am wrong, tell me where. Given that I have spent the last several years studying/developing distributed databases if I just don't know what I am doing I'd certainly like someone as smart as you to tell me.
I don't use Twitter, but as I understand it, it's a massively many-to-many messaging service, where it's not unusual to follow hundreds of people's tweets and have thousands of people follow yours. Can you imagine the performance if every message required hundreds of disk writes as the "received" copies get spread across a hundred shards?
Actually, this is the beauty of the design: All of the writes happen in parallel. So there if you write to 2000 recipients, but all of the writes happen in parallel you have no bottleneck. And any time a given machine's load gets too heavy, you do a shard split. You really dont care how much writing you do as long as on every machine you write to is not being hit too hard. So if a given server has lets say 10,000 users on it. And each one of those users receives 10 updates an hour. Then it would mean handling, lets say 100,000 writes in an hour, or 27 writes a second. If this was the threshold for this machine (which would be low) you then split the shard so that it then is only handling 13 or 14 writes per second.
So, it's scalable, but the total number of writes/sec necessary is O(messages sent/sec * average number of recipients per message). I could see this working as long as the average number of recipients per message remains constant as the service grows, though it's still a lot of hardware. How much funding does Twitter have again?
If the average number of recipients grows along with the number of users, then there's a problem, because average number of messages should be growing linearly with userbase, so the total hardware required is quadratic. No way that would work out economically...
There is nothing quadratic here. Your are able to scale linearly with the number of messages received in the system. There is a fixed cost per message received which is exactly what you want. By the way, this is exactly how the internet mail system works and it is why it is so scalable.
It's NumOfMessages, not NumOfUsers, and Messages = Messages/User * Users. Then the question is whether Messages/User and Recipients/Message remain constant as NumOfUsers goes up. If both do, then your total cost is linear with the number of users, which is what you want. But if either of them is linear in the number of users, then the total number of messages becomes quadratic in the number of users: a linear factor from growth in userbase, and a linear factor factor from increased usage by each user. Most likely there's a logarithmic correlation (Recipients/Message goes up as more people are on the service, but not by as much as total users), which is still generally fine for scalability concerns.
E-mail's actually a really great example. It worked great as long as it was used for person-to-person communication, which held both the number of messages/user and the number of recipients/message constant. Then spammers found out that the more people who had e-mail, the more they could send to at once, and sent recipients/message through the roof. In 1997/98, there were actually a number of articles about how the e-mail architecture was in serious trouble, and unless some way could be found to limit spam, it would collapse within a couple years. Of course, they dealt with it through spam filters and blacklists on the server, so now e-mail works fine.
Twitter's problem is that both Messages/User and Recipients/Message average significantly higher than e-mail, and yet the resources they have available are significantly lower than the full resources of the Internet. So even if they don't have an architectural scalability problem, they could very well have an economics problem.
I don't understand your correction, but my lack of understanding is really immaterial. I actually agree that twitter has a problem with economics if they cant sell anything. Whether it is worth solving the scalability problem is a good question. Certainly if they keep growing with no revenue, at some point it is definitely an economic problem. Indeed I posted a while ago about the community taking over twitter as a distributed public service (like email). I do think that there is an upper limit to the amount of messages the average user will send.
"Given that I have spent the last several years studying/developing distributed databases..."
That doesn't make your opinion of what's wrong with Twitter any more valid than the crap TC keeps printing unless you happen to also have lots of internal details of the Twitter architecture.
true, but it makes me curious what brilliance someone bring to the table when they have nothing specific to say other than you are wrong. Also given that much of what I am talking about is running code, I at least know that it solves a major class of problems. If it doesnt apply to twitter it should be pretty easy to explain why.
To do the writes requires a lookup. To do a read requires a lookup. That's how sharding works. If not a lookup, then a hash.
This doesn't even get into the complexity of scaling your model from 1,000 or 10,000 users where your brute-force methods seem like they will work and applying it to 10,000,000 users where your model will die a horrible death, kinda like Twitter is today.
uhh... yes it requires a lookup. There is no problem with that since the lookup is not centralized but local. How... read about terracotta. No I dont work for the company just use their open source product.
Hank, your design is so high level as to be almost useless to anyone who'd actually benefit from a proposed design. It's not clear what issues you feel Twitter has, or how exactly this architecture would solve them. Usually your blog posts are more cooked than this one. I'm a regular reader, and at first I honestly thought your post was satirical.
As I read your design, one of the biggest problems is that to build up the infrastructure I think (and infer based of my experience with designing these kinds of systems) you are describing is that it's a massive engineering effort in and of itself. You basically end up rewriting a realtime-optimized BigTable or HBase, and that's much to much to expect of Twitter's small engineering team.
People seem to forget that scalability is a tradeoff, like any other aspect of a service. You devote an amount of resources to the problem that makes sense to your business. Despite twitter's downtimes, people don't seem to be leaving the service, despite several competitors. The service is down, but it isn't down so much that it's unusable.
For a site that's grown at such a rapid pace and has such a small engineering team, I think Twitter's scaling plan is probably very reasonable. They're growing their capacity at a rate they can afford, and a rate that they know will retain most of their userbase.
Well perhaps its a matter of staring at something so long it becomes simple. But I really don't think what I am suggesting is that hard. The main thing that requires some thought is shard splitting. That is not a big piece of code, but it does admittedly take some thought to get right. Aside from that everything else is provided out of the box by someone else like amazon web services or terracotta. I am not sure how I could have been more precise without source code.
It is certainly reasonable to suggest that Twitter is good enough as it is because people still use it, though the grumbling in the market suggests that that may not be something they can bank on forever.
One thing you don't address: where do messages go while a resource is self-splitting? How much redundancy do you build in to prevent this from being a problem? How much backlog do you expect to handle?
And have you checked latency serving out of EC2? Our experience is that the connections are fairly fast but the latency establishing the connection is significant, especially from the west coast where twitter is based.
I addressed this in another answer here but happy to do it again. The way shard splitting works is that the initial shard keeps working while the new shard is being built. During this time, all messages to the old shard are written to the old shard and the new shard, so, unless I don't understand your question I dont see there being a backlog.
Regarding EC2, latency isnt really an issue because Twitter is far from real-time. That said, haven't really noticed any problems with EC2 connection latency, but we are not live yet so I would defer to you on that.
With all due respect andrew why dont you share your technical analysis of what exactly I am saying that is wrong here. Btw, have you ever actually worked on any database scaling problems? Just checking.
I have. I have managed systems that handle millions of clicks a day in databases and billions of dynamic (PHP) pageviews on a daily basis.
I am currently managing a system that serves over 100,000 DNS queries per second, each of which is dynamically evaluated as to how we respond to it. And each of which is logged, amounting to over 7,000,000,000 log lines a day, all which get processed, parsed and in many cases handed over to a database store. Yep, we're dealing with BILLIONS of rows of MySQL per day.
I'm now curious as to why you switched from zeitgeist to molotovs. The yuppie hordes at Zeitgeist are extreme but it is so hard to move back indoors...
I considered this, but given that the messages are small and the primary issue is scaling not storage this, it does not seem to me is a good solution. The entirety of everything ever written on twitter is probably not big enough to worry about storage size. The issue is performance. By the way, this architecture is essentially how email works. All your inbound messages are stored in one place separate from outbound messages from the sender. This allows for infinite horizontal scaling.
Why would you say that? It's not like the Ruby code is handling that many messages. Even Rails sites don't use ruby for their concurrency and messaging. They push down to a database or to another concurrency level like ActiveMQ. Above them lives another piece of code or hardware to do load balancing.
This isn't even about Ruby, it's about the Rails architecture.
The suggested plan seems reasonable. Yes, if you denormalise users inbound and outbound messages then you store the data twice. Yes, shards give almost limitless scalability. However, could it be that during peak load, the number of messages to be written plus indexes to be maintained exceeds the total available disk seek operations?
Your intuition is excellent. These are all valid techniques to alleviate disk seek limitations. They are likely to be successful. Unfortunately, they're expensive options.
You can partially overcome disk seek limitations by performing database batch inserts. So, rather than inserting messages indiviually and updating indexes for each message, you insert 100 messages and perform less disk seeks updating the indexes for each batch. Unfortunately, it can be hard to reliably merge data into suitable batches.
The economics of downtime is a very important consideration. I read that three minutes of downtime reduces the value of a website by 1%. However, that may be a figure bandied by vendors of high-availability equipment. It is also generally acknowledged that high-availability is achieved through strict processes and sheer redundancy of hardware. Therefore, it gets exponentially more expensive to minimise downtime.
So, you've got two non-linear curves, cost and benefit. If you've got an exceptional team, a great architecture and good finances then getting 99.999% uptime should be easy. Of course, this assumes that you don't have unforeseen circumstances, glaring omissions in redundancy - or exponential growth and utilisation without a revenue stream.
Even with generous financing, exponential growth can be deadly. A small but sustained increment in load can be enough to cause a backlog in requests that never recovers. If you're growing fast then it can occur anywhere in your system at any time. I've been a DBA for a renderfarm with thousands of cores and this situation is stressing.
We've also had this situation while working on search. Thankfully, it occurred on a smaller scale and most thankfully it occurred before launch. We had two database servers, two app servers, no redundancy, on unreliable hardware. We didn't make much headway with efficiency improvements because long tests were likely to encounter hardware failure. It was demoralising.
This slowed the development and testing of a database failover feature in the database wrapper. Now this has been implemented, progress is much better. A test that previously took three hours now takes five minutes and we've had much more time to migrate to reliable hardware and introduce redundancy. We've also got a setup which can be used to test resilience to real modes of failure.
My guess is that Twitter's downtime is due to overload, not hardware failures. Thus a scalable system (even one with a high slope) reduces the overload/downtime problem to "buy more servers -- now!" instead of the "analyze bottleneck, rewrite code" loop that it sounds like Twitter is in now.
This is true. Though I can say that if one were building twitter and you didnt either have a design like the one I suggested, or a design with some kind of distributed caching then you are going to have exactly the kinds of scaling problems they have had. In other words if you use tradition techniques for something like twitter you are screwed. However you are absolutely right that (as I said in my piece) they may already, for example have thought of all of this and either implemented or dismissed it because they have a better design, and I have no way of knowing.
This isn't true. You don't need a distributed sharded setup in order to scale. (You probably do if you are limiting yourself to MySQL) I built financial applications way back in the day that had a lot more reads and writes than twitter, and we just used ONE gigantic, super expensive database server.
Hank, good article, and good defense of your article here on HN. Regarding the knee-jerk negative responses you've received here, I can only say that you are a more patient man than I. Best of luck with your current project.
60 comments
[ 3.2 ms ] story [ 143 ms ] threadI just don't like gloating on someone else's mistakes and failures (essentially kicking someone who's already on the ground), especially when I'll probably have my own set of spectacular f-ups to deal with related to my own startup
1) It's not just a DB problem.
So not all scaling problems are database problems.
This is an argument in semantics.
You suggest storing all users physical addresses in memory across multiple machines. You also advocate "shard splitting" a la B-tree indexes which split when the node's population reaches 2n. OK, so when a split occurs, how do you maintain that massive table in memory. Do you lock it? Do you examine your existing queue of requests (which may soon point to the wrong node)? How do you handle new queue requests during "shard split maintenance"?
Calling these "database problems" is waving your hands. Why not just call them "computer problems"?
Regarding when shard split how you maintain the table, the easy answer is Terracotta. It is amazing for this and handles all that kind of stuff totally in the background. If you didnt have terracotta it would be a harder problem indeed. It handles locking and all of that magic for you. I highly recommend it. Regarding how you handle queue requests while the split is going on, what happens is that while the split is happening, the original shard continues to respond, but all new updates are sent to the old shard and the new one that is being created in the split, so during a split there is addition messaging going on. Once its done, the original shards range of users is cut back, but actually it is still storing all the old data. At that point you can delete the data that has been moved to the new shard - though this is not necessary.
Right. Just because we didn't write it doesn't mean it's magic.
There is still a lot of work to be done. It can get very complicated for high velocity apps. And it takes time.
So you're right. Bigger minds than the two of us are probably struggling with this (and lots of other stuff) as we write.
Now as you scale to 50 or so servers they will start to fail with some regularity and you can't reboot and or rebuild in five seconds so we need to have redundant systems ready. Splitting a shard probably takes longer than five seconds so you need to be proactive about such things. So we need an active rebalancing between shard so they can quickly pass around their load and fast failover incase things fail. These are DB problems but they are only problems because they system need to keep responding quickly as parts of the DB fail.
But this is still DB centric how do you load balance incoming and outgoing requests? (Routing each existing user to the same system every time and letting each system lock data when they want to change their password etc.) How do we recover from data corruption? How do we notice an outgoing or incoming mail server is down? You also have n^2 number of connections between systems as you grow can we keep that many sockets open? (More of an issue is we are segregating the network.) Etc.
PS: These are not hard problems by themselves but they are linked. And there are a lot more where they came from.
For example, I load tested my last rails app (load testing is my background-I have consulted for major pharma, tax, and other companies) and on a wimpy inherited server, processor maxed out first for the rails processes. I popped in a second CPU, then was able to get to the point where we could support 200 concurrent users, which was all we needed at the time.
I have seen limitations on bandwidth, firewall problems, load balancer misconfiguration, poorly written queries, memory usage,processor usage, thread deadlocks, and licensing limits (max database connections on a trial license) all be bottlenecks. At the larger scale, yes, database is more often the problem, but it's not clear twitter should be using a database in the way they are, anyway. Your statement goes too far.
Now consider a voting system you have 1,000 items and 1,000 users and you want to show how much people like them like each item? How well does that work when there are 100,000 users and 100,000 items?
If the average number of recipients grows along with the number of users, then there's a problem, because average number of messages should be growing linearly with userbase, so the total hardware required is quadratic. No way that would work out economically...
Basically you end up with this equation
cost = ((NumOfUsers * avgMsgsRevceivedPerUser)/maxWritesPerCPU) * costOfCPU
There is nothing quadratic here. Your are able to scale linearly with the number of messages received in the system. There is a fixed cost per message received which is exactly what you want. By the way, this is exactly how the internet mail system works and it is why it is so scalable.
E-mail's actually a really great example. It worked great as long as it was used for person-to-person communication, which held both the number of messages/user and the number of recipients/message constant. Then spammers found out that the more people who had e-mail, the more they could send to at once, and sent recipients/message through the roof. In 1997/98, there were actually a number of articles about how the e-mail architecture was in serious trouble, and unless some way could be found to limit spam, it would collapse within a couple years. Of course, they dealt with it through spam filters and blacklists on the server, so now e-mail works fine.
Twitter's problem is that both Messages/User and Recipients/Message average significantly higher than e-mail, and yet the resources they have available are significantly lower than the full resources of the Internet. So even if they don't have an architectural scalability problem, they could very well have an economics problem.
That doesn't make your opinion of what's wrong with Twitter any more valid than the crap TC keeps printing unless you happen to also have lots of internal details of the Twitter architecture.
This doesn't even get into the complexity of scaling your model from 1,000 or 10,000 users where your brute-force methods seem like they will work and applying it to 10,000,000 users where your model will die a horrible death, kinda like Twitter is today.
As I read your design, one of the biggest problems is that to build up the infrastructure I think (and infer based of my experience with designing these kinds of systems) you are describing is that it's a massive engineering effort in and of itself. You basically end up rewriting a realtime-optimized BigTable or HBase, and that's much to much to expect of Twitter's small engineering team.
People seem to forget that scalability is a tradeoff, like any other aspect of a service. You devote an amount of resources to the problem that makes sense to your business. Despite twitter's downtimes, people don't seem to be leaving the service, despite several competitors. The service is down, but it isn't down so much that it's unusable.
For a site that's grown at such a rapid pace and has such a small engineering team, I think Twitter's scaling plan is probably very reasonable. They're growing their capacity at a rate they can afford, and a rate that they know will retain most of their userbase.
It is certainly reasonable to suggest that Twitter is good enough as it is because people still use it, though the grumbling in the market suggests that that may not be something they can bank on forever.
And have you checked latency serving out of EC2? Our experience is that the connections are fairly fast but the latency establishing the connection is significant, especially from the west coast where twitter is based.
Regarding EC2, latency isnt really an issue because Twitter is far from real-time. That said, haven't really noticed any problems with EC2 connection latency, but we are not live yet so I would defer to you on that.
I am currently managing a system that serves over 100,000 DNS queries per second, each of which is dynamically evaluated as to how we respond to it. And each of which is logged, amounting to over 7,000,000,000 log lines a day, all which get processed, parsed and in many cases handed over to a database store. Yep, we're dealing with BILLIONS of rows of MySQL per day.
Hey thanks for OpenDNS by the way, I'm a long time user, and I love it.
Better safe the messages in a central store by id and only write the ids to the different pages.
http://news.ycombinator.com/item?id=188080
also you forgot about messaging queues.
This isn't even about Ruby, it's about the Rails architecture.
Your intuition is excellent. These are all valid techniques to alleviate disk seek limitations. They are likely to be successful. Unfortunately, they're expensive options.
You can partially overcome disk seek limitations by performing database batch inserts. So, rather than inserting messages indiviually and updating indexes for each message, you insert 100 messages and perform less disk seeks updating the indexes for each batch. Unfortunately, it can be hard to reliably merge data into suitable batches.
So, you've got two non-linear curves, cost and benefit. If you've got an exceptional team, a great architecture and good finances then getting 99.999% uptime should be easy. Of course, this assumes that you don't have unforeseen circumstances, glaring omissions in redundancy - or exponential growth and utilisation without a revenue stream.
Even with generous financing, exponential growth can be deadly. A small but sustained increment in load can be enough to cause a backlog in requests that never recovers. If you're growing fast then it can occur anywhere in your system at any time. I've been a DBA for a renderfarm with thousands of cores and this situation is stressing.
We've also had this situation while working on search. Thankfully, it occurred on a smaller scale and most thankfully it occurred before launch. We had two database servers, two app servers, no redundancy, on unreliable hardware. We didn't make much headway with efficiency improvements because long tests were likely to encounter hardware failure. It was demoralising.
This slowed the development and testing of a database failover feature in the database wrapper. Now this has been implemented, progress is much better. A test that previously took three hours now takes five minutes and we've had much more time to migrate to reliable hardware and introduce redundancy. We've also got a setup which can be used to test resilience to real modes of failure.
Why? They are proposals to solve a problem that has not yet been defined.
Fact is, you don't know what the problem is.
So proposing a database solution to what could just as easily be a memory management or throughput problem is premature.