Design de banco de dados do Facebook?

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.

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.

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

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:

• TAO: armazenamento de dados distribuídos do Facebook para o gráfico social
• TAO: O poder do gráfico .

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:

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.

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.

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

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

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

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

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

Esta publicação recente de junho de 2013 detalha a transição dos bancos de dados de relacionamento para objetos com associações para alguns tipos de dados.

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

Há um artigo mais longo disponível em https://www.usenix.org/conference/atc13/tao-facebook's-distributed-data-store-social-graph

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

É um tipo de banco de dados de gráficos: http://components.neo4j.org/neo4j-examples/1.2-SNAPSHOT/social-network.html

Não está relacionado aos bancos de dados relacionais.

Google para bancos de dados gráficos.

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

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.

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