Facebook数据库设计？

Question

我一直想知道Facebook如何设计朋友< - >用户关系.

我认为用户表是这样的:

user_email PK
user_id PK
password 

我用用户的数据(性别,年龄等通过用户电子邮件连接,我会假设)来计算表格.

它是如何将所有朋友连接到此用户的？

像这样的东西？

user_id
friend_id_1
friend_id_2
friend_id_3
friend_id_N 

可能不是.因为用户数量未知并且将会扩展.

Answer 1

保持一个朋友表,其中包含UserID,然后是朋友的UserID(我们将其称为FriendID).两列都是返回Users表的外键.

一些有用的例子:

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

这将表明Bob是Jon和Joe的朋友,Jon也是Joe的朋友.在这个例子中,我们假设友谊总是两种方式,因此你不需要表中的一行,如(2,1)或(3,2),因为它们已经在另一个方向上表示.对于友谊或其他关系不是明确双向的示例,您还需要使用这些行来指示双向关系.

Answer 2

看看下面的数据库架构,由Anatoly Lubarsky反向设计:

Answer 3

TL; DR:

他们使用带有缓存图形的堆栈架构,用于堆栈MySQL底部以上的所有内容.

答案很长:

我自己做了一些研究,因为我很好奇他们如何处理大量数据并快速搜索.我看到人们抱怨定制社交网络脚本在用户群增长时变得缓慢.在我用一万个用户和250万个朋友连接做了一些基准测试后- 甚至没有试图打扰组权限和喜欢和壁挂帖 - 很快就发现这种方法存在缺陷.所以我花了一些时间在网上搜索如何做得更好,并发现这篇官方的Facebook文章:

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

我真的建议你在继续阅读之前观看上面第一个链接的演示.这可能是FB在你能找到的幕后工作方式的最佳解释.

视频和文章告诉你一些事情:

• 他们在堆栈的最底层使用MySQL
• 在 SQL DB 上方有TAO层,它至少包含两个级别的缓存,并使用图形来描述连接.
• 我找不到他们实际用于缓存图表的软件/数据库的任何内容

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

嗯,这是一张图.:)它没有告诉你如何在SQL中构建它,有几种方法可以做到这一点,但这个网站有很多不同的方法.注意:考虑到关系数据库是它的原因:它被认为存储标准化数据,而不是图形结构.因此它不会像专门的图形数据库那样好.

还要考虑你必须做更复杂的查询,而不仅仅是朋友的朋友,例如当你想要过滤你和朋友的朋友喜欢的给定坐标周围的所有位置时.图表是这里的完美解决方案.

我不能告诉你如何构建它以便它会表现良好但它显然需要一些试验和错误以及基准测试.

这是我失望的测试只是朋友的朋友的调查结果:

数据库架构:

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
    )

我真的建议你创建一些包含至少10k用户记录的示例数据,每个用户记录至少有250个朋友连接,然后运行此查询.在我的机器上(i7 4770k,SSD,16GB RAM),该查询的结果是~0.18秒.也许它可以被优化,我不是数据库天才(欢迎提出建议).但是,如果这是线性的,那么对于100k用户来说已经是1.8秒,对于100万用户来说已经是18秒.

对于~10万用户来说,这听起来可能听起来很好但是考虑到你只是抓住了朋友的朋友并且没有做任何更复杂的查询,例如" 只显示朋友的朋友的帖子+如果我允许或不允许,请进行权限检查看到他们中的一些+做一个子查询来检查我是否喜欢他们中的任何一个 ".如果您已经或不喜欢帖子,或者您必须在代码中执行操作,您想让数据库进行检查.还要考虑这不是您运行的唯一查询,并且您在一个或多或少受欢迎的网站上同时拥有多个活动用户.

我认为我的答案回答了Facebook如何很好地设计他们的朋友关系的问题,但很抱歉我无法告诉你如何以一种快速工作的方式实现它.实现社交网络很容易,但确保它表现良好显然不是 - 恕我直言.

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

Answer 4

我最好的选择是他们创建了一个图形结构.节点是用户,"友谊"是边缘.

保留一个用户表,保留另一个边缘表.然后,您可以保留有关边缘的数据,例如"他们成为朋友的日子"和"已批准的状态"等.

Answer 5

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

朋友列表(表)

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

编辑

用户表可能没有user_email作为PK,但可能作为唯一键.

用户(表)

user_id PK
user_email
password

Answer 6

看看这些描述LinkedIn和Digg如何构建的文章:

• http://hurvitz.org/blog/2008/06/linkedin-architecture
• http://highscalability.com/scaling-digg-and-other-web-applications

还有"大数据:来自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

您将看到这些公司正在处理数据仓库,分区数据库,数据缓存和其他更高级别的概念,而不是我们大多数人每天都不会处理的问题.或者至少,也许我们不知道我们这样做.

前两篇文章中有很多链接可以为您提供更多的见解.

更新10/20/2014

Murat Demirbas写了一篇摘要

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

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

HTH

Answer 7

对于用户朋友数据来说,不可能从RDBMS中检索数据,这些数据在一个固定的时间内超过5亿,因此Facebook使用哈希数据库(没有SQL)实现了这一点,并且他们开源了名为Cassandra的数据库.

因此每个用户都有自己的密钥和队列中的朋友详细信息; 要知道cassandra的工作方式:

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

Answer 8

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

它与关系数据库无关。

谷歌图数据库。

Answer 9

2013年6月的这篇文章详细介绍了从关系数据库到具有某些数据类型关联的对象的转换.

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上找到

Answer 10

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

示例模式:

    Users Table
        userID PK
        other data
    Friends Table
        userID   -- FK to users's table representing the user that has a friend.
        friendID -- FK to Users' table representing the user id of the friend