Social bookmarking architectuur

[T.T.]

Ik ben bezig met het ontwerpen van een Delicious-achtige bookmarksite. Mensen kunnen hun bookmarks dus online bewaren en taggen. Dit taggen gebeurt zodat bookmarks later teruggevonden kunnen worden, voor het vinden van gerelateerde onderwerpen en nog vele andere doelstellingen.

Het probleem is nu echter: hoe ontwerp je de backend van een sociale tagging website die goed schaalt naar 1+ miljoen mensen? Het feit dat in mijn geval bookmarks worden getagged maakt natuurlijk niet echt uit. Het zouden net zo goed foto's/video's/enz kunnen zijn. Wanneer ik foto's noem, denken velen al snel aan Flickr. Flickr heeft echter een ander model dan Delicious voor het taggen (en dat maakt het ontwerp van de database een stuk eenvoudiger).

Het onderscheid tussen Delicious en Flickr is belangrijk en wordt in de literatuur wel omschreven met:

[...] broad folksonomy as one that "has many people tagging the same object and every person can tag the object with their own tags" (= del.icio.us). A narrow taxonomy has fewer people tagging and there is only one of each tag applied (= flickr).

Mijn probleem is dus niet hoe je een delicious-kloon ontwerpt. Dat kan iedereen met een beetje verstand wel. Het ontwerpen van een schaalbaar systeem is echter veel moeilijker.

Stel ik gebruik een database-ontwerp dat gebaseerd is op het volgende:

Dit is afkomstig van de website: http://tagschema.com/blogs/tagschema/
Iedere user kan meerdere tags hebben (en omgekeerd) iedere tag kan geassocieerd zijn met meerdere links enz enz.

Een vereenvoudigde voorstelling van het probleem:
Stel nu dat je 1 miljoen gebruikers hebt, stel dat iedereen 200 bookmarks heeft en dat elke bookmark gemiddeld 5 tags heeft. De centrale tabel in het bovenstaande figuur komt dan op 1M x 200 x 5 = 1 miljard rijen! Ik denk dat MySQL dat niet leuk vindt.

Het idee voor die centrale tabel was dat queries als 'gegeven lid X en tag Y, wat zijn de links Z' eenvoudiger uitgevoerd konden worden door middel van SELECTs op 1 tabel. Redundante informatie dus, om de zoekresultaten te versnellen. Met 1 miljard rijen lijkt me dat echter niet bijzonder praktisch?


Even kort samengevat:
1. Hoe gaat MySQL om met een tabel van 1 miljard rijen? Ik ga ervan uit dat er geen Indexen meer hoeven worden toegevoegd na de ontwerpfase.
2. Indien 1 miljard te veel is: twee opties. Optie 1: weglaten tabel en zoekresultaten opbouwen van andere tabellen. Optie 2: partitioneren van tabel?
3. Moet ik (meer) de-normaliseren? Graag tips in dit geval. Ik heb al afgeleide informatie zoals de counts opgeslagen.
4. Is een database wel een goede methode voor een tagging systeem? De maker van delicious heeft ooit opgemerkt dat tagging heel slecht mapt naar relationele databases. Ik denk dat hij dit heeft gezegd vanwege problemen zoals 1 miljard rijen. Ik ben bijzonder geïnteresseerd in mensen die zoektechnologie hebben toegepast op tag-systemen. Denk hierbij aan Nutch/Lucene. Google geeft elke seconde vele resultaten over veel grotere datasets, dus misschien is een database niet de beste methode. Iemand ervaring met de MapReduce-methode? Toepasbaar voor dit probleem?
5. Zou een andere database dan MySQL 4.1 (zoals 5) of PostgreSQL (partial indexing) behulpzaam zijn voor mij?
6. Stel dat ik MySQL 4.1 blijf gebruiken en dat ik de centrale tabel laat wegvallen. Dan houd ik nog steeds flinke tabellen over voor de relaties. Hoe zou ik dit kunnen partitioneren naar meerdere databases?

[ Voor 4% gewijzigd door T.T. op 25-11-2006 06:09 ]

[GX]

Misschien sla ik de plank mis; maar het idee van normalisatie is toch bijvoorbeeld ook schaalbaarheid? De centrale tabel haalt dat m.i. juist helemaal weg; die tabel gaat inderdaad problemen veroorzaken naarmate hij groeit en een reden om hem te behouden zie ik niet daar je de informatie toch al hebt in sneller te doorzoeken tabellen.

[MMUilwijk]

Wellicht kun je gaan kijken naar multidimensionaal modelleren. Deze techniek wordt veelvuldig toegepast bij Datawarehouses waarbij 1 miljard rijen absoluut geen uitzonderingen zijn. Je krijgt dan een structuur waarbij inderdaad "centrale tabellen" worden gebruikt om dimensies (de context) aan elkaar te knoppen i.c.m. met feiten over die combinaties. Echter, dit is vooral voordelig als je in 95% van je queries op die knooppunten gebruikt maakt van SELECT queries.

[T.T.]

GX schreef op zaterdag 25 november 2006 @ 10:25:
Misschien sla ik de plank mis; maar het idee van normalisatie is toch bijvoorbeeld ook schaalbaarheid?

Nou, volledige normalisatie is vaak juist niet goed voor schaalbaarheid. Denk bijvoorbeeld aan een forum: als je alles volledig zou normaliseren dan zou je bijvoorbeeld nergens opslaan hoeveel topics er in totaal zijn. Dan zou je elke keer alle topics moeten tellen om te kunnen beantwoorden hoeveel topics er in totaal zijn. Juist wat denormalisatie kan goed zijn voor schaalbaarheid.

De centrale tabel haalt dat m.i. juist helemaal weg; die tabel gaat inderdaad problemen veroorzaken naarmate hij groeit en een reden om hem te behouden zie ik niet daar je de informatie toch al hebt in sneller te doorzoeken tabellen.

Ja, centrale tabel gaat fout zoals ik zelf ook aangaf. Het idee erachter is dat je een soort 'feiten'-tabel opbouwt voor queries die je snel wilt beantwoorden. Ik denk echter dat het niet zal schalen en daarom is er een andere oplossing nodig.

MMUilwijk schreef op zaterdag 25 november 2006 @ 15:42:
Wellicht kun je gaan kijken naar multidimensionaal modelleren. Deze techniek wordt veelvuldig toegepast bij Datawarehouses waarbij 1 miljard rijen absoluut geen uitzonderingen zijn. Je krijgt dan een structuur waarbij inderdaad "centrale tabellen" worden gebruikt om dimensies (de context) aan elkaar te knoppen i.c.m. met feiten over die combinaties. Echter, dit is vooral voordelig als je in 95% van je queries op die knooppunten gebruikt maakt van SELECT queries.

Klinkt interessant, daar zal ik meer informatie over opzoeken. Datawarehousing weet ik weinig vanaf.

[ Voor 23% gewijzigd door T.T. op 25-11-2006 16:26 ]

[whoami]

Een datawarehouse is zowiezo een ander soort 'databank' dan een OLTP DB. Een datawarehouse is zowiezo gedenormaliseerd, omdat het eerder historische informatie bevat waar geen mutaties meer op hoeven te gebeuren; een datawarehouse kan je dus zo optimaliseren voor het ophalen van gegevens. Denormalisatie hoeft daar dus geen probleem te zijn.

[T.T.]

Ja, OLAP en OLTP hebben verschillende doelstellingen en kunnen dus anders geoptimaliseerd worden. Ik denk dat OLAP niet direct toepasbaar is voor mij, maar wellicht de Nutch/MapReduce aanpak wel?