M2mobi - Verbeterde graph computations binnen MariaDB
Alle blogs

Verbeterde graph computations binnen MariaDB

Bij M2mobi maken we al langere tijd gebruik van MariaDB als database voor de backend systemen van een aantal van onze grootste apps. Een van de redenen waarom we hebben gekozen voor MariaDB, is vanwege haar ondersteuning voor zogeheten ‘pluggable storage engines’. Deze pluggable storage engines vergroten de veelzijdigheid van onze databases en bieden dus meer mogelijkheden. Een van deze meer gespecialiseerde storage engines is OQGRAPH, waarmee we simpel gezegd onze data kunnen weergeven als een graaf. Na enige tijd te hebben gewerkt met OQGRAPH, zagen we enkele mogelijkheden ter verbetering en besloten we deze te aan MariaDB bij te dragen.

Graph databases

Het belangrijkste doel van een database is het opslaan en behouden van gegevens. Zogeheten ‘General-purpose databases’ zijn over het algemeen gericht op veel voorkomende use-cases om een goede performance te leveren. Echter, als we meer inzicht hebben in onze data kunnen we beter op deze data optimaliseren en meer uit een database systeem halen. ‘Special-purpose databases’ geven dergelijke optimalisaties, zoals betere prestaties, meer betrouwbaarheid of een betere compressie van data.

Met de pluggable storage engines van MariaDB kunnen we special-purpose database functionaliteiten implementeren in een general-purpose database systeem. Een voorbeeld van zo’n pluggable storage engine die we bij M2mobi gebruiken is OQGRAPH. In tegenstelling tot de meeste storage engines, wordt er feitelijk geen data opgeslagen, maar wordt de opgeslagen data op een andere manier weergeven. In het geval van OQGRAPH wordt deze data weergeven als een graaf.

Stel, we hebben een vereenvoudigd sociaal netwerk met gebruikers die relaties met elkaar kunnen hebben. Die relaties zou je in een database kunnen opslaan, zodat je bijvoorbeeld gemakkelijk een lijst met ‘vrienden’ kunt terugvinden. Maar, wat als je ‘vrienden van vrienden’ wilt opzoeken? Of je wilt weten via welke mensen twee gebruikers met elkaar verbonden zijn?

Dit is waar ‘graph computation’ om de hoek komt kijken. Met OQGRAPH kunnen we een graaf maken van de relaties tussen verschillende gebruikers en er vervolgens algoritmen op los laten. Een ‘shortest path’ algoritme zou bijvoorbeeld een lijst kunnen weergeven van personen die twee gebruikers met elkaar verbinden. Een ‘breadth first’ algoritme zou juist weer een lijst kunnen weergeven van alle vrienden van vrienden van een gebruiker.

Er bestaan al special-purpose databanken die dit soort acties kunnen uitvoeren, echter hebben we dan te maken met verschillende systemen. In het geval van OQGRAPH kunnen we al deze acties uitvoeren binnen één systeem, wat een snellere en gemakkelijkere weg biedt om te komen tot hetzelfde eindresultaat.

Verbeteringen

We hebben OQGRAPH inmiddels binnen meerdere projecten gebruikt en zagen in de loop der tijd meerdere mogelijkheden voor verbetering. Het voordeel van het werken met een ‘open source’ software (zoals MariaDB) is dat we daadwerkelijk de code kunnen bekijken en zelf verbeteringen kunnen implementeren. Die gelegenheid grepen we maar al te graag aan en deelden onze verbeteringen. Onlangs zijn deze verbeteringen geaccepteerd en beschikbaar als onderdeel van toekomstige releases van MariaDB.

We leggen deze verbeteringen uit aan de hand van ons eerder genoemde voorbeeld van een sociaal netwerk. OQGRAPH biedt een zogeheten ‘gerichte graaf’. Stel, je hebt een ‘vrienden’ relatie tussen gebruiker A en B. Dit betekent dat er een relatie bestaat tussen gebruiker A en B, en ook tussen gebruiker B en A. Laten we aannemen dat als gebruiker A gebruiker B toevoegt als vriend, er wel een relatie van gebruiker A naar B bestaat, maar niet van gebruiker B naar A (dit is min of meer de manier waarop cirkels in Google+ werken). Dit resulteert in het gegeven dat de lijst met vrienden van gebruiker A anders zal zijn dan de lijst met gebruikers die gebruiker A als vriend hebben.

Dit laatste is een voorbeeld van een vraag die beantwoord kan worden met een eerste verbetering die we hebben doorgevoerd - eigenlijk een bugfix. Deze is vrijgegeven als onderdeel van MariaDB 10.0.33, 10.1.29, 10.2.10 en 10.3.3.

De tweede verbetering waar we aan werkten biedt een nieuw algoritme voor OQGRAPH waarmee we sneller zogeheten ‘leaves’ (bladeren) vinden. In ons voorbeeld van een sociaal netwerk zouden dit gebruikers zijn die andere gebruikers als vriend hebben toegevoegd, maar zelf geen vrienden hebben. Ook kunnen dit gebruikers zijn die vrienden hebben toegevoegd, maar geen van deze andere gebruikers hebben hen ook als vriend toegevoegd. Met behulp van het ‘leaves’ algoritme kun je snel vaststellen of een aanwezige relatie van een gebruiker voldoet aan een van deze criteria. Deze verbetering werd uitgebracht als onderdeel van MariaDB 10.3 en 10.3.3.

Tot slot

Hoewel het enige tijd duurde voordat onze verbeteringen werden geaccepteerd, was het leuk om samen te werken met de MariaDB en OQGRAPH-teams en kijken we er naar uit dit weer te doen.

 

Lees meer #technologie blogposts

Deel dit artikel

Andere artikelen