How does facebook keep user friends?

Question

I am wondering how exactly the information that a user with id x is friends with users with identifiers z, y, w is stored in a very large application, for example facebook.

I think of several possibilities

a) Has a table that displays friendships with the identifiers of people participating as foreign keys, as shown here:

Person | isFriendsWith

x ------------------- y

x ------------------ z

x ------------------- w

Which seems to me that it will not scale at all.

b) Enter a field in the users line, which stores the identifiers of your friends in a serialized format, for example, the line # # # # w. I believe that with the right algorithm, parsing and updating this line would be easy.

c) Make a separate table with each user's friends. Will this be too much load on the server?

d) Anything else?

So, if someone knows what facebook is doing and can share the details, it will be clear what is at stake. Also, if someone can share their quick wits, why the things I listed here won't scale well or have other performance issues, I'm interested in hearing this.

thanks

Answer 1

Here are some links. On the first page of links there is a link to the words "mostly complex" that refer to the flickr schema image. I cannot vouch for the correctness of any information in these links:

http://www.makeuseof.com/tag/facebook-work-nuts-bolts-technology-explained/

http://www.theregister.co.uk/2011/07/13/mike_stonebraker_versus_facebook/

http://gigaom.com/cloud/facebook-trapped-in-mysql-fate-worse-than-death/

http://snarfed.org/facebook_data_store_api_thoughts/

The image I mentioned was created by analyzing the business objects in the API that Facebook opened. http://blogs.x2line.com/al/archive/2007/06/02/3124.aspx It was 2007, so it may or may not be representative.