DevProTalk

DevProTalk (http://www.devprotalk.com/index.php)
-   SQL baze podataka - Sponzor: Baze-Podataka.net (http://www.devprotalk.com/forumdisplay.php?f=10)
-   -   How did they do it: FB prijatelji mojih prijatelja (http://www.devprotalk.com/showthread.php?t=7061)

cvele 05. 02. 2009. 11:44

How did they do it: FB prijatelji mojih prijatelja
 
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 05. 02. 2009. 12:48

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 05. 02. 2009. 13:14

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 05. 02. 2009. 15:02

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 05. 02. 2009. 15:53

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 05. 02. 2009. 16:20

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 05. 02. 2009. 17:52

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

cvele 05. 02. 2009. 20:18

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

jablan 05. 02. 2009. 23:27

Citat:

Originalno napisao cvele (Napišite 65802)
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 06. 02. 2009. 00:34

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.


Vreme je GMT +2. Trenutno vreme je 23:36.

Powered by vBulletin® Verzija 3.6.8
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
Copyright © DevProTalk. All Rights Reserved.

Mišljenja, saveti, izjave, ponude ili druge informacije ili sadržaji nastali na Sajtu su vlasništvo onoga ko ih je kreirao, a ne DevProTalk.com, tako da ne morate da se oslanjate na njih.
Autori poruka su jedini odgovorni za ovakve sadržaje. DevProTalk.com ne garantuje tačnost, kompletnost ili upotrebnu vrednost informacija, stavova, saveta ili datih izjava. Ne postoje uslovi pod kojima bi mi bili odgovorni za štetu ili gubitak koji je posledica bilo čijeg oslanjanja na nepouzdane informacije, ili bilo kakve informacije nastale kroz komunikaciju između registrovanih članova.
Web sajt može sadržavati linkove na druge web sajtove na Internetu ili neke druge sadržaje. Ne kontrolišemo niti podržavamo te druge web sajtove, niti smo pregledali bilo kakve sadržaje na takvim sajtovima. Mi nećemo biti odgovorni za legalnost, tačnost ili prikladnost bilo kog sadržaja, oglasa, proizvoda, usluga ili informacije lociranim na ili distribuiranih kroz druge web sajtove, niti za bilo kakvu štetu nastalu kao posledica takvih informacija. DevProTalk.com drži i čuva druga prava vlasništva na web sajtu. Web sajt sadrže materijale zaštićene copyright-om, zaštitne znakove i druge informacije o pravu vlasništva ili softver. Članovi mogu poslatu informacije zaštićene pravima vlasništva njihovih nosilaca i ona ostaju zaštićena bez obzira da li su oni koji prenose te informacije to naveli ili ne. Osim informacija koje su u javnom vlasništvu ili za koje dobijete dozvolu, nemate pravo da kopirate, modifikujete ili na bilo koji način menjate, objavljujete, prenosite, distribuirate, izvršavate, prikazujete ili prodajte bilo koju informaciju zaštićenu pravima vlasništva. Slanjem informacija ili sadržaja na bilo koji deo DevProTalk.com, Vi automatski dozvoljavate i predstavljate garanciju da imate pravo da dozvolite DevProTalk.com ili članovima DevProTalk.com bespovratnu, kontinualnu, neograničenu, globalnu dozvolu da koriste, kopiraju, izvršavaju, prikazuju i distribuiraju takve informacije i sadržaje i da iz takvih sadžaja koriste bilo koji deo u bilo koje svrhe, kao i pravo i dozvolu da koriste gore navedene sadržaje. Svi zaštitni znakovi (trademarks), logotipi, oznake usluga, firme ili imena proizvoda koji se pominju na ovom web sajtu su vlasništvo kojim raspolažu njihovi vlasnici.