Design de banco de dados do Facebook?

133

Eu sempre me perguntei como o Facebook projetou a relação de usuário do amigo <->.

Eu acho que a tabela de usuários é algo como isto:

user_email PK
user_id PK
password 

Eu imagino a tabela com os dados do usuário (sexo, idade, etc. conectados via e-mail do usuário, eu diria).

Como ele conecta todos os amigos a esse usuário?

Algo assim?

user_id
friend_id_1
friend_id_2
friend_id_3
friend_id_N 

Provavelmente não. Porque o número de usuários é desconhecido e será expandido.

Marin
fonte
13
Existe uma página de engenharia do Facebook que contém muito desse tipo de informação, mas não exatamente o que você está perguntando. Você pode perguntar lá e ver se consegue obter uma resposta. facebook.com/FacebookEngineering
John Meagher
1
Google graph database. Com certeza não é um RDBMS.

Respostas:

90

Mantenha uma tabela de amigos que detenha o UserID e, em seguida, o UserID do amigo (vamos chamá-lo de FriendID). Ambas as colunas seriam chaves estrangeiras de volta para a tabela Usuários.

Exemplo um pouco útil:

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)

Exemplo de uso:

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

Isso mostrará que Bob é amigo de Jon e Joe e que Jon também é amigo de Joe. Neste exemplo, assumiremos que a amizade é sempre de duas maneiras; portanto, você não precisaria de uma linha na tabela como (2,1) ou (3,2) porque elas já estão representadas na outra direção. Para exemplos em que a amizade ou outras relações não são explicitamente bidirecionais, você também precisa ter essas linhas para indicar o relacionamento bidirecional.

TheTXI
fonte
8
pense em como isso é ineficiente - você precisa fazer uma consulta disjuntiva nas colunas do tempo de pesquisa duplicado de muitos para muitos, em média.
Anthony Bishopric
2
Pessoalmente, eu não gostaria que esses dois campos fizessem uma chave primária composta. Uma chave única, absolutamente. O índice agrupado nessa chave exclusiva, definitivamente. Mas eu também colocaria algum tipo de identidade não composta como a PK com um índice não clusterizado. Isso permitiria que outras tabelas que precisam de um "amigo relação ID" FK facilmente amarrar a esta mesa e vários gatilhos pode disparar a cascata de eventos da friending, defriending, etc.
Jesse C. Slicer
1
Ele disse que o Facebook tem cerca de 1'000'000'000 usuários. Se o usuário médio tiver 100 amigos, isso significa que a tabela conterá 100'000'000'000 linhas. Particionamento MySQL?
veidelis
Esqueça essa abordagem. Se você receber uma quantidade séria de usuários, definitivamente ficará muito lento. Veja minha resposta e tente compará-la você mesmo. Fiz alguns testes comparativos com 10.000 usuários e 2,5 milhões de conexões de amizade, e o resultado foi decepcionante. Se você administra uma pequena comunidade, ela funcionará bem, mas há problemas de desempenho a serem considerados.
burzum
7
você pode ter certeza de que o facebook não usa um RDBMS para isso, é de conhecimento geral que eles, o twitter e todos os outros que precisam executar consultas como essa usam um banco de dados gráfico de algum sabor. existem pelo menos 69 pessoas que nunca trabalharam em nenhum tipo de escala ou que não sabem fazer matemática em escala.
51

Dê uma olhada no seguinte esquema do banco de dados, com engenharia reversa por Anatoly Lubarsky :

Esquema do Facebook

Brad Larson
fonte
7
Este é um diagrama de classe, e não um esquema de banco de dados
Suco de limão
2
Então, cada "Usuário" teria um banco de dados dedicado? Como o acima? Como isso funcionaria? Por exemplo, quando o usuário fizer logon cheques FB para ver se é um usuário válido + Pass e, em seguida, se for facebook válida irá redirecioná-los para lá do banco de dados que, em seguida, exibe tudo, desde o banco de dados acima
James111
Nesta loja, apenas as informações relacionadas ao usuário, estou procurando especificamente pelo Post e seu público?
Waseem Ahmad Naeem
47

TL; DR:

Eles usam uma arquitetura de pilha com gráficos em cache para tudo acima da parte inferior do MySQL da pilha.

Resposta longa:

Eu mesmo fiz algumas pesquisas porque estava curioso para saber como eles lidam com sua enorme quantidade de dados e os pesquisam rapidamente. Vi pessoas reclamando sobre scripts de redes sociais personalizados ficando lentos quando a base de usuários cresce. Depois que fiz alguns testes comparativos com apenas 10.000 usuários e 2,5 milhões de conexões de amigos - nem mesmo tentando me preocupar com permissões de grupos, curtidas e publicações no mural -, rapidamente percebi que essa abordagem é falha. Por isso, passei algum tempo pesquisando na Web sobre como fazê-lo melhor e me deparei com este artigo oficial do Facebook:

Eu realmente recomendo que você assista à apresentação do primeiro link acima antes de continuar lendo. É provavelmente a melhor explicação de como o FB funciona nos bastidores que você pode encontrar.

O vídeo e o artigo mostram algumas coisas:

  • Eles estão usando o MySQL na parte inferior de sua pilha
  • Acima do banco de dados SQL, há a camada TAO que contém pelo menos dois níveis de armazenamento em cache e usa gráficos para descrever as conexões.
  • Não consegui encontrar nada sobre qual software / banco de dados eles realmente usam para seus gráficos em cache

Vamos dar uma olhada nisso, as conexões de amigos estão no canto superior esquerdo:

insira a descrição da imagem aqui

Bem, este é um gráfico. :) Não diz como construí-lo no SQL, existem várias maneiras de fazê-lo, mas este site possui uma boa quantidade de abordagens diferentes. Atenção: Considere que um banco de dados relacional é o que é: pensa-se armazenar dados normalizados, não uma estrutura de gráfico. Portanto, não terá um desempenho tão bom quanto um banco de dados gráfico especializado.

Considere também que você precisa fazer consultas mais complexas do que apenas amigos de amigos, por exemplo, quando deseja filtrar todos os locais em torno de uma determinada coordenada de que você e seus amigos gostam. Um gráfico é a solução perfeita aqui.

Não sei dizer como construí-lo para que ele tenha um bom desempenho, mas exige claramente algumas tentativas, erros e comparações.

Aqui está o meu teste decepcionante para apenas encontrar amigos de amigos:

Esquema do banco de dados:

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;

Consulta de amigos de amigos:

(
        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
    )

Eu realmente recomendo que você crie alguns dados de amostra com pelo menos 10k registros de usuários e cada um deles tenha pelo menos 250 conexões de amigos e execute essa consulta. Na minha máquina (i7 4770k, SSD, 16gb RAM), o resultado foi ~ 0,18 segundos para essa consulta. Talvez possa ser otimizado, não sou um gênio do banco de dados (sugestões são bem-vindas). No entanto, se isso for linear, você já terá 1,8 segundos para apenas 100 mil usuários, 18 segundos para 1 milhão de usuários.

Isso ainda pode parecer bom para ~ 100k usuários, mas considere que você acabou de buscar amigos de amigos e não fez nenhuma consulta mais complexa como " exibir apenas postagens de amigos de amigos + fazer a verificação de permissão se sou permitido ou NÃO para ver alguns deles + faça uma subconsulta para verificar se eu gostei de algum deles ". Você deseja deixar o banco de dados fazer a verificação se você gostou de uma postagem ou não, ou terá que fazer isso no código. Considere também que essa não é a única consulta executada e que você tem mais de um usuário ativo ao mesmo tempo em um site mais ou menos popular.

Acho que minha resposta responde à pergunta de como o Facebook projetou o relacionamento de amigos muito bem, mas lamento não poder dizer como implementá-lo de uma maneira que funcione rapidamente. Implementar uma rede social é fácil, mas garantir que ela tenha um bom desempenho claramente não é - IMHO.

Comecei a experimentar o OrientDB para fazer consultas de gráficos e mapear minhas bordas para o banco de dados SQL subjacente. Se eu fizer isso, escreverei um artigo sobre isso.

Burzum
fonte
então .. você já chegou a escrever o artigo?
FlowUI. SimpleUITesting.com
1
Não, estou muito ocupada além de fazer programação e não tive tempo e disposição para fazê-lo. A resposta aqui contém tudo o que você precisa saber se deseja implementar associações de amigos com bom desempenho. Armazene em cache as listas de amigos por usuário ou mapeie seu banco de dados relacional em partes ou a coisa toda em um gráfico e consulte o banco de dados do gráfico. Você pode usar o OrientDB ou o Neo4j para isso. Eu adoraria escrever meu próprio software de rede social de código aberto, mas há muitas outras coisas a fazer também. Faça o que fizer: faça benchmarks. :)
burzum 15/04
Ainda não. Mas a documentação do OrientDB explica as conexões dos amigos e tudo o mais pode ser modelado quando os conceitos básicos forem compreendidos. orientdb.com/docs/2.1/Tutorial-Working-with-graphs.html Se você deseja usar um banco de dados relacional como base, basta adicionar algum código nos retornos de chamada "após salvar" e "após excluir" para atualizar seu gráfico DB (que você usaria para ler dados). Se você não tiver esses retornos de chamada implementá-los, acho que quase todos os tipos de implementações e estruturas ORM têm algo parecido. Na verdade, o OrientDB também pode armazenar documentos.
burzum
1
então .. você já chegou a escrever o artigo?
Connor Gurney
1
Ainda não, mas fazemos algo semelhante no trabalho: mapeamos nossos dados relacionais para um índice do Elastic Search, como escrevi no meu comentário antes, é simplesmente uma questão de obter os dados que você deseja armazenar no índice ou gráfico após uma determinada ação (afterSave () / afterDelete () retorno de chamada no nosso caso) e, em seguida, atualizando o índice ou gráfico. Bem simples? :) A propósito, o mesmo poderia ser feito com as listas de amigos, não importa se você as armazena no ES, em um gráfico ou em um cache baseado em memória (desde que você tenha RAM suficiente). Realmente não é difícil, a parte difícil é fazer a coisa toda crescer quando você crescer.
burzum
32

Minha melhor aposta é que eles criaram uma estrutura gráfica . Os nós são usuários e "amizades" são arestas.

Mantenha uma tabela de usuários, mantenha outra tabela de arestas. Em seguida, você pode manter os dados sobre as bordas, como "dia em que se tornaram amigos" e "status aprovado" etc.

belgariontheking
fonte
40
Tenho a sensação de que você terá que explicar isso um pouco mais para algumas pessoas aqui.
TheTXI
4
Penso que uma pergunta mais interessante seria como manter uma estrutura tão grande (estamos falando de 200 milhões de nós e bilhões de arestas) de uma maneira que possa ser facilmente pesquisada e atualizada.
Dirk Vollmar
1
@divo: uso inteligente de índices e partições.
belgariontheking
20

Provavelmente é um relacionamento de muitos para muitos:

FriendList (tabela)

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

EDITAR

A tabela de usuários provavelmente não possui user_email como PK, possivelmente como uma chave exclusiva.

usuários (tabela)

user_id PK
user_email
password
Nathan Koop
fonte
4
Embora isso certamente faça mais sentido, eu acho que o desempenho seria horrível, considerando quantos usuários o Facebook tem e quantos amigos cada usuário do Facebook tem.
21715 Kevin Kevin Pang
17

Dê uma olhada nestes artigos que descrevem como o LinkedIn e o Digg são criados:

Há também "Big Data: pontos de vista da equipe de dados do Facebook" que podem ser úteis:

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

Além disso, há este artigo que fala sobre bancos de dados não relacionais e como eles são usados ​​por algumas empresas:

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

Você verá que essas empresas estão lidando com data warehouses, bancos de dados particionados, cache de dados e outros conceitos de nível superior do que a maioria de nós nunca lida diariamente. Ou pelo menos, talvez não saibamos o que sabemos.

Existem muitos links nos dois primeiros artigos que devem fornecer mais informações.

ATUALIZAÇÃO 20/10/2014

Murat Demirbas escreveu um resumo de

  • TAO: armazenamento de dados distribuídos do Facebook para o gráfico social (ATC'13)
  • F4: sistema de armazenamento BLOB quente do Facebook (OSDI'14)

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

HTH

Adrian J. Moreno
fonte
9

Não é possível recuperar dados do RDBMS para dados de amigos do usuário para dados que ultrapassam mais de meio bilhão em um tempo constante; portanto, o Facebook implementou isso usando um banco de dados de hash (sem SQL) e eles abriram o banco de dados chamado Cassandra.

Portanto, todo usuário tem sua própria chave e os detalhes dos amigos em uma fila; para saber como funciona o cassandra, veja isso:

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

user362541
fonte
Muito interessante, obrigado meu amigo. Quando eles mudaram para cassandra do sql? você sabe?
Marin
1
Esteja ciente: os Espaços Posterosos estão mortos ... então o link.
TechNyquist
5

Você está procurando chaves estrangeiras. Basicamente, você não pode ter uma matriz em um banco de dados, a menos que tenha sua própria tabela.


Esquema de exemplo:

    Tabela Usuários
        userID PK
        outros dados
    Tabela de amigos
        ID do usuário - FK para a tabela de usuários que representa o usuário que tem um amigo.
        friendID - Tabela FK para usuários que representa o ID do usuário
Malfist
fonte
5
Por que os votos negativos? Pelo menos deixe alguém saber por que você votou contra ele.
Sasha Chedygov 17/06/09
3
@reak: Por quê? Todo o conceito de votação neste site é para que o voto seja anônimo. Por que você sente que malfist tem direito a alguma coisa?
GEOCHET
4
Especialmente quando é uma resposta válida e é ecoado pelas outras respostas (embora eu não copiar a partir deles, quando eu respondi, lá onde há respostas)
Malfist
4
@TheTXI: Eu acho que comentários sobre votos negativos são uma cortesia, especialmente sobre respostas que obviamente não os merecem, mas também concordo que os comentários não devem ser obrigatórios.
Robert S.
2
As pessoas que votam anonimamente em respostas não óbvias são aquelas que temem que seu raciocínio superficial seja exposto se deixem um comentário explicando um voto negativo.
Vinayak
1

Lembre-se de que as tabelas de banco de dados foram projetadas para aumentar verticalmente (mais linhas), não horizontalmente (mais colunas)

Neil N
fonte
24
NUNCA SE ESQUEÇA! Meu pai morreu porque uma tabela de banco de dados que havia crescido muito verticalmente para suas colunas. Vou sentir sua falta, pai.
belgariontheking
1
hmm, por que o voto negativo? E o comentário acima deste não faz sentido.
217 Neil N
2
Não, o comentário não faz sentido. Parece que alguém tentou ser engraçado, então não se importe.
Dirk Vollmar
0

Em relação ao desempenho de uma tabela muitos-para-muitos, se você tiver 2 ints de 32 bits vinculando IDs de usuário, seu armazenamento de dados básico para 200.000.000 de usuários, com média de 200 amigos, será um pouco menos de 300 GB.

Obviamente, você precisaria de algum particionamento e indexação e não manterá isso na memória para todos os usuários.

Cade Roux
fonte
0

Provavelmente existe uma tabela que armazena a relação de usuário do amigo <->, digamos "frnd_list", com os campos 'user_id', 'frnd_id'.

Sempre que um usuário adiciona outro usuário como amigo, duas novas linhas são criadas.

Por exemplo, suponha que meu ID seja 'deep9c' e eu adicione um usuário com o ID 'akash3b' como meu amigo; em seguida, duas novas linhas serão criadas na tabela "frnd_list" com valores ('deep9c', 'akash3b') e ('akash3b ',' deep9c ').

Agora, ao mostrar a lista de amigos para um usuário específico, um sql simples faria isso: "selecione frnd_id de frnd_list em que user_id =" onde está o ID do usuário conectado (armazenado como um atributo da sessão).

deep9c
fonte