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/...st_member_(FQL)

i individualne tabele:
http://wiki.developers.facebook.com/...riendlist_(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]

Originalno napisao cvele

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(!), te o pametnijem iskoristavanju memcacheda.

Memcached inace svakome preporucujem. Spasao me je dosta puta.