DevProTalk

Forumi IT profesionalaca
web development, web design, e-business, SEO


Idite nazad   DevProTalk > Web development i web aplikacije > SQL baze podataka - Sponzor: Baze-Podataka.net
Beach Wedding Dresses - Looking for the Wedding Dress? Here, 1dress.co.uk stunning collection of beach wedding dresses is just what you are looking for.
charles wang

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

Odgovori
 
Alati teme Način prikaza
Staro 05. 02. 2009.   #1
cvele
Banned
Knowledge base
 
Avatar cvele
 
Datum učlanjenja: 01.07.2005
Poruke: 1.598
Hvala: 206
140 "Hvala" u 89 poruka
cvele ima spektakularnu aurucvele ima spektakularnu auru
Default 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 ?
cvele je offline   Odgovorite uz citat
Staro 05. 02. 2009.   #2
robi-bobi
expert
Grand Master
 
Avatar robi-bobi
 
Datum učlanjenja: 05.10.2005
Lokacija: Sofia, Bulgaria
Poruke: 805
Hvala: 222
862 "Hvala" u 68 poruka
robi-bobi ima spektakularnu aururobi-bobi ima spektakularnu aururobi-bobi ima spektakularnu aururobi-bobi ima spektakularnu aururobi-bobi ima spektakularnu aururobi-bobi ima spektakularnu aururobi-bobi ima spektakularnu auru
Pošaljite poruku preko Skype™ za robi-bobi
Default

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
robi-bobi je offline   Odgovorite uz citat
Staro 05. 02. 2009.   #3
kodi
133t
Master
 
Avatar kodi
 
Datum učlanjenja: 08.01.2006
Lokacija: Beograd
Poruke: 714
Hvala: 16
37 "Hvala" u 28 poruka
kodi is on a distinguished road
Pošaljite ICQ poruku za kodi
Default

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...
__________________
kodi je offline   Odgovorite uz citat
Staro 05. 02. 2009.   #4
ivanhoe
Ivan Dilber
Sir Write-a-Lot
 
Avatar ivanhoe
 
Datum učlanjenja: 18.10.2005
Lokacija: Bgd
Poruke: 5.320
Hvala: 104
1.941 "Hvala" u 579 poruka
ivanhoe je ime poznato svimaivanhoe je ime poznato svimaivanhoe je ime poznato svimaivanhoe je ime poznato svimaivanhoe je ime poznato svimaivanhoe je ime poznato svimaivanhoe je ime poznato svimaivanhoe je ime poznato svimaivanhoe je ime poznato svimaivanhoe je ime poznato svimaivanhoe je ime poznato svima
Pošaljite poruku preko Skype™ za ivanhoe
Default

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.
ivanhoe je offline   Odgovorite uz citat
Staro 05. 02. 2009.   #5
cvele
Banned
Knowledge base
 
Avatar cvele
 
Datum učlanjenja: 01.07.2005
Poruke: 1.598
Hvala: 206
140 "Hvala" u 89 poruka
cvele ima spektakularnu aurucvele ima spektakularnu auru
Default

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 ?
cvele je offline   Odgovorite uz citat
Staro 05. 02. 2009.   #6
srdjan
SYS 64738
Grand Master
 
Avatar srdjan
 
Datum učlanjenja: 25.10.2006
Lokacija: Preko Morače
Poruke: 893
Hvala: 87
346 "Hvala" u 163 poruka
srdjan ima spektakularnu aurusrdjan ima spektakularnu aurusrdjan ima spektakularnu aurusrdjan ima spektakularnu auru
Default

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)
__________________
mookieapp.com
mobile app for you and your dog
srdjan je offline   Odgovorite uz citat
Staro 05. 02. 2009.   #7
Eniac
troll mode
Wrote a book
 
Avatar Eniac
 
Datum učlanjenja: 06.09.2006
Lokacija: Beograd
Poruke: 1.034
Hvala: 56
69 "Hvala" u 46 poruka
Eniac će postati "faca" uskoro
Pošaljite ICQ poruku za Eniac Pošaljite poruku preko MSN za Eniac Pošaljite poruku preko Skype™ za Eniac
Default

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

eniax.net - malo pišem
@eniac - puno tvitujem
Eniac je offline   Odgovorite uz citat
Staro 05. 02. 2009.   #8
cvele
Banned
Knowledge base
 
Avatar cvele
 
Datum učlanjenja: 01.07.2005
Poruke: 1.598
Hvala: 206
140 "Hvala" u 89 poruka
cvele ima spektakularnu aurucvele ima spektakularnu auru
Default

Na brzinu sam bacio oko na foaf, ali oni se ni ne trude da daju odgovor na ovaj problem.
cvele je offline   Odgovorite uz citat
Staro 05. 02. 2009.   #9
jablan
VD IT Direktora
Invented the damn thing
 
Avatar jablan
 
Datum učlanjenja: 08.06.2005
Lokacija: Beograd
Poruke: 2.118
Hvala: 503
1.263 "Hvala" u 282 poruka
jablan je pravi dragi kamenjablan je pravi dragi kamenjablan je pravi dragi kamenjablan je pravi dragi kamenjablan je pravi dragi kamenjablan je pravi dragi kamenjablan je pravi dragi kamenjablan je pravi dragi kamenjablan je pravi dragi kamen
Default

Citat:
Originalno napisao cvele Pogledajte poruku
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).

Poslednja izmena od jablan : 05. 02. 2009. u 23:33.
jablan je offline   Odgovorite uz citat
Staro 06. 02. 2009.   #10
marinowski
Igor Marinović
Expert
 
Avatar marinowski
 
Datum učlanjenja: 09.06.2005
Lokacija: Palić
Poruke: 549
Hvala: 31
39 "Hvala" u 17 poruka
marinowski is on a distinguished road
Pošaljite ICQ poruku za marinowski
Default

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.
__________________
marinowski.com
marinowski je offline   Odgovorite uz citat
"Hvala" marinowski za poruku:
Odgovori


Alati teme
Način prikaza

Pravila pisanja
Možete ne započinjati nove teme
Možete ne slati odgovore
Možete ne slati priloge
Možete ne izmeniti svoje poruke
vB kôd je Uključen
Smajliji su Uključen
[IMG] kod je Uključen
HTML kôd je Isključen
Pogledajte forum

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


Vreme je GMT +2. Trenutno vreme je 05:24.


Blogodak - Domaci blogovi na jednom mestu Caught in a web - web dev blog
Powered by vBulletin® Verzija 3.6.8
Copyright ©2000 - 2017, 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.