|
SQL baze podataka - Sponzor: Baze-Podataka.net MySQL, MSSQL, Oracle, Access, ODBC. Ako imate problem brže i preciznije ćete dobiti odgovor ako priložite strukturu tabela ili skript koji kreira tabele i puni ih test podacima umesto što to problem opisujete samo rečima. Sponzor: Baze-Podataka.net - Blog o bazama podataka |
|
Alati teme | Način prikaza |
|
05. 02. 2009. | #1 |
Banned
Knowledge base
Datum učlanjenja: 01.07.2005
Poruke: 1.598
Hvala: 206
140 "Hvala" u 89 poruka
|
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 ? |
05. 02. 2009. | #2 |
expert
Grand Master
|
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 |
05. 02. 2009. | #3 |
133t
Master
|
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... |
05. 02. 2009. | #4 |
Ivan Dilber
Sir Write-a-Lot
|
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..
__________________
Leadership is the art of getting people to want to do what you know must be done. |
05. 02. 2009. | #5 |
Banned
Knowledge base
Datum učlanjenja: 01.07.2005
Poruke: 1.598
Hvala: 206
140 "Hvala" u 89 poruka
|
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 ? |
06. 02. 2009. | #6 |
Ivan Dilber
Sir Write-a-Lot
|
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.
__________________
Leadership is the art of getting people to want to do what you know must be done. |
05. 02. 2009. | #7 |
xyz
Grand Master
Datum učlanjenja: 25.10.2006
Poruke: 893
Hvala: 87
346 "Hvala" u 163 poruka
|
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) |
05. 02. 2009. | #9 |
Banned
Knowledge base
Datum učlanjenja: 01.07.2005
Poruke: 1.598
Hvala: 206
140 "Hvala" u 89 poruka
|
Na brzinu sam bacio oko na foaf, ali oni se ni ne trude da daju odgovor na ovaj problem.
|
05. 02. 2009. | #10 |
VD IT Direktora
Invented the damn thing
Datum učlanjenja: 08.06.2005
Lokacija: Beograd
Poruke: 2.118
Hvala: 503
1.307 "Hvala" u 282 poruka
|
Č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). Poslednja izmena od jablan : 05. 02. 2009. u 23:33. |
|
|
Slične teme | ||||
Tema | Početna poruka teme | Forum | Odgovori | Poslednja poruka |
slanje iphone-a iz USA u Srbiju - pomoc prijatelja oko detalja pliz! | logoholik | Opušteno | 3 | 23. 04. 2010. 17:49 |
DPT nedostupan sa mojih IPova | misk0 | Obaveštenja, predlozi i pitanja | 5 | 30. 05. 2008. 14:06 |