Facebook数据库devise?

我一直想知道Facebook如何devise好朋友关系。

我认为用户表是这样的:

user_email PK user_id PK password 

我用桌面上的用户数据(性别,年龄等通过用户电子邮件连接,我会假设)。

它如何将所有的朋友连接到这个用户?

像这样的东西?

 user_id friend_id_1 friend_id_2 friend_id_3 friend_id_N 

可能不会。 由于用户数量未知并将扩大。

保留一个拥有UserID和朋友的UserID的朋友表(我们将其称为FriendID)。 两列都是外键返回到用户表。

一些有用的例子:

 Table Name: User Columns: UserID PK EmailAddress Password Gender DOB Location TableName: Friends Columns: UserID PK FK FriendID PK FK (This table features a composite primary key made up of the two foreign keys, both pointing back to the user table. One ID will point to the logged in user, the other ID will point to the individual friend of that user) 

用法示例:

 Table User -------------- UserID EmailAddress Password Gender DOB Location ------------------------------------------------------ 1 bob@bob.com bobbie M 1/1/2009 New York City 2 jon@jon.com jonathan M 2/2/2008 Los Angeles 3 joe@joe.com joseph M 1/2/2007 Pittsburgh Table Friends --------------- UserID FriendID ---------------- 1 2 1 3 2 3 

这将表明,鲍勃是乔恩和乔的朋友,乔恩也是乔的朋友。 在这个例子中,我们假定友谊总是两种方式,所以你不需要(2,1)或(3,2)这样的表中的一行,因为它们已经在另一个方向上表示了。 例如,友谊或其他关系不是明确的两种方式,你也需要有这些行来表示双向关系。

看看下面的数据库模式, 由Anatoly Lubarsky逆向工程 :

Facebook架构

我最好的select是他们创build了一个图表结构 。 节点是用户,“友谊”是边缘。

保留一个用户表,保留另一个表的边缘。 然后你可以保存边缘的数据,比如“他们成为朋友的日子”和“批准的状态”等。

TL; DR:

他们使用堆栈体系结构和高速cachinggraphics来创build堆栈的MySQL底部。

长答案:

我自己做了一些研究,因为我很好奇他们如何处理他们的大量数据,并快速search。 我看到有人抱怨定制社交networking脚本在用户群增长时变得缓慢。 在我用一万个用户和两百五十万个朋友连接做了一些基准testing后,甚至没有试图去讨论组权限,喜欢和墙贴等问题,结果很快就certificate了这种方法是有缺陷的。 所以我花了一些时间在网上search如何做得更好,并遇到这个官方的Facebook文章:

  • TAO:Facebook的社交图分布式数据存储
  • 陶:图的力量 。

真的build议你在继续阅读之前观看上面第一个链接的介绍。 这可能是FB如何在幕后find最好的解释。

video和文章告诉你一些事情:

  • 他们在堆栈的最底层使用MySQL
  • SQL DB 之上是包含至less两级caching的TAO层,并使用图来描述连接。
  • 我找不到他们实际用于caching图表的软件/数据库

让我们来看看这个,朋友关系是左上angular:

在这里输入图像描述

那么这是一个图表。 :)它没有告诉你如何在SQL中build立它,有几种方法可以做到这一点,但是这个网站有很多不同的方法。 注意:考虑关系数据库是这样的:它被认为是存储规范化的数据,而不是graphics结构。 所以它不会像专门的graphics数据库一样好。

另外考虑一下,你必须做更复杂的查询,而不仅仅是朋友的朋友,例如当你想过滤你和你朋友的朋友喜欢的给定坐标周围的所有位置。 图表是这里的完美解决scheme。

我不能告诉你如何构build它,以便它performance良好,但显然需要一些反复试验和基准testing。

这是我朋友的朋友朋友们的调查令人失望的testing:

DB架构:

 CREATE TABLE IF NOT EXISTS `friends` ( `id` int(11) NOT NULL, `user_id` int(11) NOT NULL, `friend_id` int(11) NOT NULL ) ENGINE=InnoDB AUTO_INCREMENT=2 DEFAULT CHARSET=utf8; 

朋友之友查询:

 ( select friend_id from friends where user_id = 1 ) union ( select distinct ff.friend_id from friends f join friends ff on ff.user_id = f.friend_id where f.user_id = 1 ) 

我真的build议你创build一些样本数据,至less有10K条用户logging,每个用户logging至less有250条朋友连接,然后运行这个查询。 在我的机器上(i7 4770k,SSD,16GB内存),结果是〜0.18 。 也许它可以被优化,我不是一个数据库天才(build议是受欢迎的)。 但是, 如果这个线性增长,那么对于只有10万用户,已经是1.8秒,对于100万用户来说,已经是18秒。

对于大约10万用户来说,这听起来还是可以的,但是考虑到你刚刚find了朋友的朋友,并没有做任何更复杂的查询,比如“ 只显示来自朋友的朋友的post,如果允许或不允许,看到他们中的一些+做一个子查询来检查我是否喜欢他们中的任何一个 “。 你想让数据库做检查,如果你喜欢已经或没有的post,或者你将不得不在代码。 还要考虑到这不是你运行的唯一的查询,而且你在同一时间在一个或多或less的受欢迎的站点上有更多的活跃用户。

我想我的答案回答了Facebook如何devise他们的朋友关系的问题,但是我很抱歉,我不能告诉你如何以一种快速的方式来实现它。 实现一个社交networking很容易,但要确保它的performance不错 – 恕我直言。

我已经开始尝试使用OrientDB来进行graphics查询,并将我的边缘映射到底层的SQL DB。 如果我完成了,我会写一篇关于它的文章。

这很可能是多对多的关系:

FriendList(表格)

 user_id -> users.user_id friend_id -> users.user_id friendVisibilityLevel 

编辑

用户表可能没有user_email作为PK,尽pipe可能是一个唯一的键。

用户(表)

 user_id PK user_email password 

看一下这些描述LinkedIn和Digg如何构build的文章:

还有“大数据:来自Facebook数据团队的观点”可能会有帮助:

http://developer.yahoo.net/blogs/theater/archives/2008/01/nextyahoonet_big_data_viewpoints_from_the_fac.html

另外,这篇文章讨论了非关系数据库以及它们如何被一些公司使用:

http://www.readwriteweb.com/archives/is_the_relational_database_doomed.php

您将看到,这些公司正在处理数据仓库,分区数据库,数据caching以及其他更高层次的概念,而我们大多数人从未处理过这些问题。 或者至less,也许我们不知道我们做的。

前两篇文章中有很多链接应该给你更多的见解。

更新10/20/2014

穆拉特Demirbas写了一个总结

  • TAO:Facebook的社交图分布式数据存储(ATC'13)
  • F4:Facebook的BLOB存储系统(OSDI'14)

http://muratbuffalo.blogspot.com/2014/10/facebooks-software-architecture.html

HTH

从RDBMS检索用户朋友数据的数据是不可能的,这些数据在一个固定的时间超过5亿的数据,所以Facebook使用散列数据库(没有SQL)实现了这个数据,他们打开了名为Cassandra的数据库。

所以每个用户都有自己的密钥和朋友细节排队; 要知道cassandra的作品如何看待这个:

http://prasath.posterous.com/cassandra-55

最近2013年6月的一篇文章详细解释了从关系数据库到具有某些数据types关联的对象的过渡。

https://www.facebook.com/notes/facebook-engineering/tao-the-power-of-the-graph/10151525983993920

有一个更长的论文可在https://www.usenix.org/conference/atc13/tao-facebook's-distributed-data-store-social-graph

你正在寻找外键。 基本上你不能在数据库中有一个数组,除非它有自己的表。


示例模式:

    用户表
        用户ID PK
        其他数据
    朋友表
         userID  -  FK到表示拥有朋友的用户的表。
         friendID  -  FK到用户的表格表示朋友的用户ID 

它是一种graphics数据库: http : //components.neo4j.org/neo4j-examples/1.2-SNAPSHOT/social-network.html

它与关系数据库无关。

Google forgraphics数据库。

请记住,数据库表被devise为垂直增长(更多行),而不是水平增长(更多列)

可能存在一个表,其存储具有字段'user_id','frnd_id'的朋友用户关系,称为“frnd_list”。

无论何时用户将另一个用户添加为朋友,都会创build两个新行。

例如,假设我的id是'deep9c',并且添加了一个id为'akash3b'的用户作为我的朋友,然后在表“frnd_list”中创build了两个新值,分别为值('deep9c','akash3b')和(''akash3b ”, 'deep9c')。

现在当向特定用户显示friends列表时,一个简单的sql会这样做:“从frnd_list中selectfrnd_id,其中user_id =”其中是login用户的id(存储为会话属性)。

关于多对多表的性能,如果有2个32位整数连接用户ID,那么平均每个朋友200个朋友的200,000,000个用户的基本数据存储容量不到300GB。

显然,你需要一些分区和索引,而且你不会为所有的用户保存这些内容。