Why are Facebook, Digg and Twitter So Hard To Scale?

http://highscalability.com/blog/2009/10/13/why-are-facebook-digg-and-twitter-so-hard-to-scale.html

by yarapavan • 17 years ago

84 49 17 years ago

Retric3• 17 years ago

I spent a few hours mocking up a solution to this type of status updates in code. It seemed fairly obvious so I assumed it was not a real problem. However, if there is any interest I can turn it to some sort of blog post next weekend.

dlsspy• 17 years ago

Sure it's obvious until you have hundreds of millions of nodes that each link to somewhere between 100 and 2,000,000 other nodes that need to be updated when any given node updates (assume around 5,000 nodes are updating every second with a power law kind of distribution).

If you think that's obvious, I think you're significantly beyond all of the people with all of the "hello world" twitter clones out there.

wheels3• 17 years ago

Interestingly, the problem isn't so much in building a scalable store on a single machine that goes up to a certain point -- a billion edges, for example (about what we've tested our DB up to). Distributing the data becomes a really hard problem, however, because the issues of data locality is tricky. Typical map-reduce patterns are only of limited utility since each traversal may imply additional traversals, so you end up having to have "smart" (computing) nodes which may themselves trigger a second tier of map-reduces.

This is quite different from the problems of even large scale web apps where there's essentially a set of data that's pulled from a caching layer and assembled.

Retric3• 17 years ago

It all comes down how well you can slice the process. There is no cheep over the counter solution to these problems but a little custom code can go a long way.

5k node updates per second might sound like a problem, but one core of one machine can easily keep up with that so you can have several copies and several views of the whole network graph. Public vs. private messages can be handled separately and then joined before presentation to the user. You can separate finding which message to display from the message data. You even get to display dirty reads as long as the data is <2 seconds old it's plenty good enough.

Ok, describing the solution based on the above insights takes some time and pictures but does it still sound horrible?

PS: Twitter was forced to morph an architecture built to solve a different problem into a working solution. That takes time and can be fairly difficult. But, starting from scratch it's not that bad.

LiveTheDream• 17 years ago

A blog post would be great. Don't you find it odd though, that the engineers at Digg, Twitter, and Facebook think it is a very difficult problem?

Retric3• 17 years ago

When you grow from zero to 100million users you get to watch as each piece breaks under growing load. Keeping a system running as it just keeps growing is hard.

However, Facebook rolled out a messaging system with little problem. I think the problem is guessing and simulating the load before people start messing with it. While not wasting millions building for load that never shows up.

fizx• 17 years ago

I've wondered for a while about some hybrid push/pull distribution scheme. I have 100 followers, just push. Oprah has 1M, 1% of which are currently active, pull. Sounds complicated, but feasible.

bsaunder2• 17 years ago

But is also has to do with how frequently the information is changed/accessed.

e.g. If Oprah only publishes 3 tweets a day, but her one million followers each check 100 times a day (just to be on the bleeding edge of gossip), it's much less effort to push the change.

On the flip side, if you post status changes several times a day but your followers rarely check (daily/weekly), pull may make more sense.

Although, I suppose that a push inherently requires an update/write, while a pull is generally a read. Seems like this might need to be taken into consideration as well.

siculars• 17 years ago

scaling is hard. this is why, for the non-technical audience... also the post ends with "brave new world." yuck.

bsaunder2• 17 years ago

I think the trade off between push/pull is influenced by the ratio of the 'velocity' of data (how frequently it changes) to its access frequency.

If accessed frequently, but changes less frequently, then push makes sense, if changes frequently, but accessed infrequently, then pull makes sense.

It also seems likely that the same piece of data may have different ratios from different perspectives.

dasil0034• 17 years ago

I think it's laughable to put Twitter and Digg in the same category of scalability as Facebook.

Maybe things have changed since the last time I visited Digg over 2 years ago, but the social networking aspects are not very significant. The vast majority of their hits are practically fully page cacheable.

Twitter at least has an interesting scaling problem, but they don't have any features and they move at a glacial pace.

Facebook on the other hand has a graph that almost as nasty as Twitter's (minus the million followers thing), but they have 100 times the features, and they push new code every week.

joe_the_user• 17 years ago

What makes Twitter hard is that it is a semi-real-time communications medium that is no longer particularly web-based - a good portion of Tweets come from phones.

But you're right with Digg, I don't see it having any excuses

ivankirigin• 17 years ago

There are facebook pages with millions of fans. If you fan a page, you'll "subscribe" its updates too. It is similar to asymmetric following.

The internal representation is quite elegant.

jdrock• 17 years ago

FB should be more difficult as well because they aren't just showing streaming information. They're making (supposedly) intelligent decisions on what information to show you. Twitter is just showing you a "dumb" stream.

litewulf2• 17 years ago

At the same time, facebook can simply drop messages on the floor if they're bottlenecked, so they have less strict scaling requirements.

mikeryan2• 17 years ago

Just because Twitter and Digg don't operate at the same scale as Facebook doesn't mean they don't face similar issues.

I actually think having a bunch of large sites tackling similar issues will present a whole bunch of neat new technologies for addressing these sorts of issues in the near future.

dasil0034• 17 years ago

I'm not talking about absolute scale. Facebook is small compared to Google scale, but in my (probably poorly) informed opinion it's not as impressive.

All these sites have scaled to multiple servers, which means they've all had to address some of the hard problems, and no doubt that many of the issues are very similar. However even if Facebook's traffic were half of Twitter's it would still be a much more impressive architecture. They support a full-on integrated development platform for crying out loud. That is orders of magnitude more impressive than Twitter's lightweight API whether they're serving 100 or 100,000 requests per second.

I'm not dissing Twitter either, it's just that what Facebook has going is pretty incredible. Consider that failing to scale is basically what killed Friendster.

rythie• 17 years ago

Actually I've found that people follow twice as many people on Twitter as on Facebook and receive updates a whole load more often. Facebook does benefit from being a older company with a lot more engineers though.

timf• 17 years ago

Facebook also "has about 30,000 servers supporting its operations, hosts 80 billion photos, and serves up more than 600,000 photos to its users every second."

(check out http://www.facebook.com/Engineering?v=wall )

yarapavan• 17 years ago

Facebook handles 30K machines, 300M active users, 20B photos, & 25TB per day of logging data. http://bit.ly/EA3oY

yariv• 17 years ago

We (FB) actually push new code every day.

gaius5• 17 years ago

Because those who ignore the pub-sub research IBM did in the 80s are doomed to re-implement it badly.

slackerIII• 17 years ago

Links or paper titles?

gaius5• 17 years ago

In the case of Twitter, CICS has been around since the 60s!

wheels3• 17 years ago

I'll preface this with the fact that I've not read those papers (but today was thinking through the concept of write hooks in information graphs), but I'd assume from the common formation of the pattern that it's only really set up for one-dimensional publishes.

The problem in large scale information networks, more in the Facebook way than the Twitter way, is that you you potentially trigger a cascading effect in information updates if you go pub-sub. Specifically, applications that do interesting things with social graphs have to go beyond basically doing message passing.

I naturally look at things from a recommendations angle, but if you've got a new edge that enters the graph that may affect other edges that are connected to the end points. Those may in turn affect the edges that are connected to those nodes and so on. You want to avoid something that effectively becomes a breadth first traversal of the graph doing updates since that's well, slow, to put it mildly.

This is why large-scale graph algorithms like PageRank work on constantly regenerating static matrices rather than doing regeneration of the ranks dynamically, but that naturally is problematic when you're working on data sets where the most recent data is the most important and is being generated at very high rates.

jfarmer2• 17 years ago

In some models, sure, but is that true in Facebook's? Does anything go beyond one degree?

I can't think of anything, really. If X and Y becomes friends, X's friends and Y's friends see it in their feed ("inbox"), but nobody else. Same goes for tagging someone in a photo, etc.

x3m• 17 years ago

This is in fact an unsolved problem. Current database systems cannot handle this level of connectivity. Facebook can't do a "push" because of all the features they support. It gets extremely complicated if they push complex data into user's mailbox. And twitter cannot do "pull" so they can avoid putting a cap on the number friends/followers but then that's why they cannot really add any feature.

jbert• 17 years ago

I wonder if there is value to be had in migrating users to increase social graph locality.

The probability of (B fr C) is greater than the mean if (A fr B) and (A fr C). That's useful information.

Off the top of my head, I wonder how an algorithm like:

- I have N shards

- pick the top N most-connected users

- assign them each to a shard

- assign their immediate friends to the same shard

- randomly fill in other users

would work.

Possible refinements:

- if the %age of shared friends between two users in the top N is > X, put both users in the same shard + add the N+1th user at a new shard-seed

- chase more than one level of immediacy from the shard-seed users to fill the shard

- if a shard is full, don't drop to random allocation for 1st- or 2nd- level friends, but instead put them all onto shard+1

The idea here is that for pull or push you win if you need to contact fewer shards. i.e. the queries and updates needn't be per-user but per-shard. i.e. you can query/update for all users on a shard in one sql statement.

If you somehow manage to keep all of ashton's friends on 10 shards instead of 100, then that's a big win, surely?

radu_floricica2• 17 years ago

I've been wondering for a while why we don't see more often systems with a huge amount of RAM and asynchronous persistent updates, with a more, how should I put it, computer science-ish architecture inside. MVC works ok, but does it really mean we _have_ to use it always? Is it so hard to make system with a TeraByte of RAM? Why even use memcache? Why not make a clear decision that stuff like user statuses will never even see the inside of a hard disk and make use of the simplification it brings? Is there a clear reason, or simply it's not fashionable?

thomaspaine• 17 years ago

User statuses should never touch hard disk? What happens when your server restarts and everything you were storing in memory disappears?

spc476• 17 years ago

The greylist daemon I wrote (http://www.x-grey.com/) keeps everything in memory, with a checkpoint (everything gets written out to disk) every hour (the main process forks, and it's the child that does the writing). A similar approach might be applicable here.

It could very well be a RAM based approach might be viable once memristros (http://en.wikipedia.org/wiki/Memristor#Potential_application...) are used for memory.

radu_floricica2• 17 years ago

Exactly how often do servers restart? Your average commodity server - maybe twice a year. For user data it's too much, but for user statuses, I don't think so. And if you save the data in a controlled restart and only consider crashes, with a bit of effort you can probably go down to about once every couple of years or less.

As for the benefit... there was a picture some time back here on HN: http://imgur.com/X1Hi1.gif

cd34• 17 years ago

Based on another article on highscalability, Twitter has one master MySQL server that is used for backups only. If a node crashes, it reloads that status from MySQL. That MySQL server handles 300 tweets per second @ roughly 2400 qps.

They now use Scala/JVM rather than rails for the backend, Rails for the frontend.

http://highscalability.com/scaling-twitter-making-twitter-10...

peterwwillis• 17 years ago

You can't store everything in memory all the time. There simply isn't a computer built which can do that. Horizontal scaling with commodity boxes and layers of cache are the most cheap and effective method of returning a high rate of requests as quickly as possible.

kmavm• 17 years ago

You can buy a machine with a terabyte of RAM. If your check doesn't bounce, IBM, HP, Sun, et al. will deliver it via forklift tomorrow. However, that box will cost much, much more than 16 boxes with 64GB each. Those 16 boxes will also have more CPU, network cards, and aggregate bandwidth to RAM than the terabox. The big honkin' box full of RAM is in most respects an unbalanced system; you can do a lot more with a lot less money if it's acceptable to give up on the single-system image programming model.

tybris• 17 years ago

Pervasive writes?

Why are Facebook, Digg and Twitter So Hard To Scale?

Related Stories