How did they do it: FB prijatelji mojih prijatelja

[cvele]

Nesto od jutros razmisljam... fejsbuk ima zanimljiv feature da mozes da setujes politiku privatnosti tako da prijatelji tvojih prijatelja mogu da vide tvoje slike/updejtove sta god.

Pretpostavimo da mora da postoji tabela korisnika (users) koja primera radi izgleda ovako:

userid | username
------------------
1 | pera
------------------
2 | zika
------------------
3 | mika

i relaciona tabela za prijatelje (user_friends):

userid | friendid
----------------
1 | 2
----------------
2 | 1
----------------
2 | 3
----------------
3 | 2
(znaci pera i zika su se medjusobno dodali u prijatelje, a mika je prijatelj sa zikom dok nije prijatelj sa perom)

Takodje recimo da postoji tabela sa nekim sadrzajem(content) na koji je setovana opcija privatnosti da mogu da ga vide prijatelji i prijatelji prijatelja:

id | userid | content
-----------------------
1 | 1 | lepa brena
(dakle pera je postavio sadrzaj lepa brena)

Dakle imamo situaciju da se korisnik mika ulogovao i otisao na stranicu na kojoj se prikazuje sav sadrzaj koji on moze da vidi.
Mika moze da vidi "lepa brena" jer je prijatelj sa Zikom koji je prijatelj sa Perom. Znaci on je prijatelj prijatelja Pere.

Prva stvar koja bi trebalo da se uradi je spajanje users sa user_friends kako bi dobili Mikine prijatelje, pa onda opet spajanje istih tabela gde bi videli sve prijatelje Mikinih prijatelja (u ovom potskupu je i Pera). Pri svemu tome skup koji se napravi mora da bude distinct. Znajuci da u proseku FB korisnici imaju 150-250 prijatelja (licni zakljucak) dolazimo do situacije eksponencijalnog rasta ovog skupa prijatelja, nad kojim je distinct operacija veoma skupa. Kada uzmemo jos da to treba da spojimo sa sadrzajem, tebelom koja je znatno veca od skupa prijatelja i njihovih prijatelja (pod pretpostavkom da je svaki clan ostavio vise sadrzaja nego sto je ostavio prijatelja), dolazimo do jednog uzasno skupog upita.

Ipak ova operacija na FB ne deluje toliko skupa, tako da mi se cini da su to resili na pametniji nacin nego sto je ovaj moj.

Ima li neko ideju kako ?

[robi-bobi]

interesantno pitanje
na prvu loptu, pomislih na view tabele, i/ili trigere, t.j. deo upita da se odradi pre nego sto ti zatreba da pokazes korisniku sta su prijatelji njegovih prijatelja dodali
ali ovo je skup i nepraktican pristup kad imas dosta korisnika
opet, ne znam sta bi trece moglo biti

[kodi]

sudeci po FQL dokumentaciji postoji tabela

http://wiki.developers.facebook.com/index.php/Friendlist_member_(FQL)

i individualne tabele:
http://wiki.developers.facebook.com/index.php/Friendlist_(FQL)

ja kad sam to prvi put video, zbunio sam se jer ispada da oni imaju tih friendlist tabela isto koliko i usera....

to mozda funkcionise tako sto je odradjen sharding pa su od 0-10k u jednoj bazi .. 10-20k u drugoj.. ali i da jeste tako opet je to MNOGO tabela
mada opet, fb je poznat po tome sto ima tonu servera...

[ivanhoe]

mislim da nema potrebe da se to cuva u tabelama, moguce je napraviti i kesirati nizove prijatelja-od-prijatelja za svakog usera, ili vec nekakve matrice id-jeva na osnovu kojih mozes brzo da filtriras recorde... ti se podaci menjaju samo kad neko iz liste doda/izbrise prijatelja, a i tada ne mora da se rebilduje cela lista, nego se samo azurira izmena..

[cvele]

Nemoj FQL da uzimas kao referencu kako izgledaju njihove tabele, to je samo nadjezik koji oni parsaju i pomocu njega prave prave upite koji pricaju sa bazom.

Sto se tice cuvanja u matrici, to mi deluje kao jos skuplja stvar.
Ako si mislio da se cuva u fajlovima, mozes da zamislis kolike heldove oni moraju da drze u memoriji u svakom trenutku ? :) Cak i ako izdelis liste po nekoj logici, to je sumanuto :)

Edit:
Ajde da pretpostavimo da se ne plase skupih upita ili slicnih operacija, koliko jak taj klaster treba da bude da bi bio u stanju da sve to opsluzi? Da li je logicno da facebook od pre ~4-5god moze sebi da priusti takvu masineriju ?

[srdjan]

Ivanovo resenje sa kesiranjem ima smisla...

Tvoj problem se sastoji iz 4 dela:

1. select liste mojih prijatelja -> A (1 kesirana struktura)
2. select liste prijatelja od mojih prijatelja -> B (100 kesiranih struktura)
3. union C = A + B
4. select content WHERE user IN C

Problem su #3 i #4, tj. treba da resis UNION (izbacis duplikate) a mozda i ne moras...

Struktura prijatelja treba biti takva da je trazenje/umetanje/brisanje brzo (neka stabla mi se javljaju)

[Eniac]

pogledaj na netu o FOAF-u mislim da FB koristi taj koncept

[cvele]

Na brzinu sam bacio oko na foaf, ali oni se ni ne trude da daju odgovor na ovaj problem.

[jablan]

Pri svemu tome skup koji se napravi mora da bude distinct.
Čemu ovaj distinct? Nigde se ne traži konkretna lista prijatelja drugog nivoa, već samo upit da li se konkretan korisnik nalazi u toj listi nekog drugog korisnika.

Sve u svemu, meni ovaj JOIN uopšte ne izgleda kao neka svemirski skupa operacija (videti da li postoji korisnik koji ima i Miku i Peru među prijateljima).

[marinowski]

Ako je istina da svaki korisnik u proseku ima oko 200 prijatelja, to znači da svaki korisnik u proseku ima 200 * 200 prijatelja od prijatelja.

To je 40.000 podataka po korisniku, što znači 40.000 integer brojeva po korisniku, što nije strašno za keširanje. Naročito što je u realnom svetu ta brojka mnogo manja, iz dva razloga:

1. Obično se radi o krugu prijatelja, tako da je vrlo često prijatelj tvog prijatelja i tvoj prijatelj, pa se radi o mnogo manjoj brojci od 40.000

2. Ovo treba da se primeni samo na one koji su uključili ovu opciju, a tih je sigurno vrlo malo.

Ovi podaci se ne menjaju često, jedino ako neko nekome postane, ili prestane biti prijatelj.

Pročitao sam par interesantnih tekstova o facebooku ispod haube, npr o njegovom skalabilnom log sistemu koji je otišao u open source (http://highscalability.com/product-scribe-facebooks-scalable-logging-system)(!), te o pametnijem iskoristavanju memcacheda (http://highscalability.com/strategy-facebook-tweaks-handle-6-time-many-memcached-requests).

Memcached inace svakome preporucujem. Spasao me je dosta puta.

[cvele]

1. Obično se radi o krugu prijatelja, tako da je vrlo često prijatelj tvog prijatelja i tvoj prijatelj, pa se radi o mnogo manjoj brojci od 40.000
&@jablan zato i trazis da je neko distinct.

Inace tih 40000 je samo deo upita, previse ste uprostili.

Znaci imas stranu na kojoj ti se izlistavaju downloadi. I pravis query da bi izlistao recimo 20 zadnjih downloada koje odredjeni korisnik moze da vidi. To je u najboljem slucaju 20*200*200.

Inace pre nego sto se db ogranici na tih 40k (da uzmemo jednostavniji slucaj), mora da se uradi distinct na joinu izmedju user_friends i users, a distinct nemoze da se radi ne potskupu.


2. Ovo treba da se primeni samo na one koji su uključili ovu opciju, a tih je sigurno vrlo malo.
Ta opcija je po defaultu.

[cvele]

@marin thanks za fb log nisam cuo za to

[jablan]

&@jablan zato i trazis da je neko distinct.
Izvini, ja još uvek ne kapiram što si zapeo za taj distinct?

jablan=# select * from korisnici;
id | ime
----+------
1 | pera
2 | mika
3 | zika
4 | laza
(4 rows)

jablan=# select * from slike;
id | korisnik_id | ime
----+-------------+---------
1 | 1 | slika 1
2 | 2 | slika 2
(2 rows)

jablan=# select * from prijatelji ;
korisnik_1 | korisnik_2
------------+------------
1 | 2
1 | 3
2 | 4
2 | 1
3 | 1
4 | 2
(6 rows)

I sad Laza hoće da vidi Perinu sliku_1:

jablan=# select count(*) from prijatelji p1 inner join prijatelji p2 on p1.korisnik_1 = p2.korisnik_1 and p1.korisnik_2 = 1 and p2.korisnik_2 = 4;
count
-------
1
(1 row)

Count > 0, može, count = 0 ne može i gotovo.

Kakav distinct, kakvi bakrači...

[filmil]

А можда за тај део посла користе објектно-оријентисану базу података?

ф

[marinowski]

2. Ovo treba da se primeni samo na one koji su uključili ovu opciju, a tih je sigurno vrlo malo.
Ta opcija je po defaultu.

Eh, slep od ociju, nisam video ovo. Izgleda da sam i dalje slep:

Znaci imas stranu na kojoj ti se izlistavaju downloadi.

Gde je ova stranica?

Na updatima ja uvek vidim samo update od mojih prijatelja, ili update od prijatelja prijatelja ako je neki od mojih prijatelja komentarisao. Dakle, sve su to akcije direktnih prijatelja. Ako vidis na svojim updatima nekoga ko nije tvoj prijatelj, pogledaj link, uvek je ovog tipa:
s.php?k=100000080&id=xxxx

dakle, to je link koji pokazuje da je to prijatelj tvog prijatelja, a ne tvoj prijatelj.

Inace, facebook cacheira sve zivo, cak i fotografije. Tako da verujem da cacheira i ove veze. Sta je cacheirati par integera ako se cacheiraju tolike fotografije:

http://www.bytebot.net/blog/archives/2008/06/25/how-facebook-serves-pictures

[ivanhoe]

Sto se tice cuvanja u matrici, to mi deluje kao jos skuplja stvar.
Ako si mislio da se cuva u fajlovima, mozes da zamislis kolike heldove oni moraju da drze u memoriji u svakom trenutku ? :) Cak i ako izdelis liste po nekoj logici, to je sumanuto :)


Naravno da nisam mislio na fajlove, mislio sam na memcache. FB ima iza sebe desetine hiljada memcache servera, i oni zaista sumanuto mnogo toga kesiraju. Memcache je idealan za taj posao jer je distribuiran pa nema potreba da dupliras bilo sta od podataka, nego za svakog korisnika zapamtis samo jednom celu listu. To ti je realno u vecini slucajeva ispod 100KB podataka po coveku, to nije nista za FB infrastrukturu.