Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

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

highscalability.com

Post reply on HN
Print view View original

11–20 of 52 posts

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

#11

Post by scott_s »

Retric wrote: post #10
dlsspy wrote: post #3

Earlier quoted context omitted.

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.

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 b…

I think you under-estimate the complexity and performance costs of having a massively distributed data structure. Having N nodes perform computations on a graph many times the size of N is easy. Maintaining some form of coherency throughout all N nodes is hard.

The communication costs are significant, and probably similar to N-body simulations.

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

#12

Post by Retric »

LiveTheDream wrote: post #8
Retric wrote: post #2

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.

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?

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.

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

#15

Post by [deleted] »

dasil003 wrote: post #9

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 pa…

[deleted]

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

#16

Post by x3m »

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.

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

#18

Post by gaius »

scott_s wrote: post #11
Retric wrote: post #10

Earlier quoted context omitted.

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 b…

I think you under-estimate the complexity and performance costs of having a massively distributed data structure. Having N nodes perform computations on a graph many times the size of N is easy. Maintaining some form of coherency throughout all N nodes is hard. The communication costs are significant, and probably similar to N-body simulations.

Maintaining some form of coherency throughout all N nodes is hard.

Hence the "eventually consistent" model.

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

#19

Post by scott_s »

gaius wrote: post #18
scott_s wrote: post #11

Earlier quoted context omitted.

I think you under-estimate the complexity and performance costs of having a massively distributed data structure. Having N nodes perform computations on a graph many times the size of N is easy. Maintaining some form of coherency throughout all N nodes is hard. The communication costs are significant, and probably similar to N-body simulations.

Maintaining some form of coherency throughout all N nodes is hard. Hence the "eventually consistent" model.

That's still hard. There's a trade-off between accuracy and performance.

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

#20

Post by jbert »

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?

Post reply on HN