Schaalbare genoomanalyse met NoSQLdatabases

Schaalbare genoomanalyse met NoSQLdatabases Brecht Gosselé

Thesis voorgedragen tot het behalen van de graad van Master of Science in de ingenieurswetenschappen: computerwetenschappen, hoofdspecialisatie Gedistribueerde systemen Promotor: Prof. dr. R. Wuyts Assessor: Prof. dr. ir. Y. Berbers, Prof. dr. M.-F. Moens Begeleider: Prof. dr. R. Wuyts

Academiejaar 2014 – 2015

c Copyright KU Leuven

Zonder voorafgaande schriftelijke toestemming van zowel de promotor als de auteur is overnemen, kopi¨eren, gebruiken of realiseren van deze uitgave of gedeelten ervan verboden. Voor aanvragen tot of informatie i.v.m. het overnemen en/of gebruik en/of realisatie van gedeelten uit deze publicatie, wend u tot het Departement Computerwetenschappen, Celestijnenlaan 200A bus 2402, B-3001 Heverlee, +32-16327700 of via e-mail [email protected]. Voorafgaande schriftelijke toestemming van de promotor is eveneens vereist voor het aanwenden van de in deze masterproef beschreven (originele) methoden, producten, schakelingen en programma’s voor industrieel of commercieel nut en voor de inzending van deze publicatie ter deelname aan wetenschappelijke prijzen of wedstrijden.

Voorwoord Graag had ik mijn promotor, tevens begeleider, bedankt voor de aangename en vlotte samenwerking en de goede, nuttige raad doorheen het academiejaar. Daarnaast ben ik ook de andere medewerkers van het lab en Janssen Pharmaceutica dankbaar voor hun hulp en feedback. Ook mijn zussen verdienen een pluim (naar keuze) voor hun advies bij de biologische delen van dit werk. Tot slot ben ik mijn ouders veel verschuldigd voor de nimmer aflatende steun, niet enkel tijdens het afgelopen jaar. Meer dan eens hebben jullie me met de voeten op de grond en de neus uit de wind gezet; zonder jullie was het me niet gelukt. Merci vielmal! Brecht Gossel´e

i

Inhoudsopgave Voorwoord

i

Inhoudsopgave

ii

Samenvatting

iv

1 Inleiding 1.1 Algemene context . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Probleemstelling case study: GEMINI . . . . . . . . . . . . . . . . . 1.3 Contributies en resultaten . . . . . . . . . . . . . . . . . . . . . . . .

1 1 2 3

2 Achtergrond genoomanalyse 2.1 Biologische achtergrond . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 DNA sequencing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Voorbeeldvraagstukken genoomanalyse . . . . . . . . . . . . . . . . .

5 5 7 8

3 GEMINI overzicht 3.1 Database schema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Inladen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3 Querying . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9 9 11 13

4 Achtergrond datastores 4.1 Concepten . . . . . . . . . . . . . . 4.2 NoSQL-klassen . . . . . . . . . . . 4.3 NoSQL: vergelijkende studie . . . . 4.4 Achtergrond datastores: conclusie .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

17 18 21 22 29

5 Cassandra als databank voor GEMINI 5.1 Keuze database . . . . . . . . . . . . . 5.2 Dataschema . . . . . . . . . . . . . . . 5.3 gemini load . . . . . . . . . . . . . . 5.4 gemini query . . . . . . . . . . . . . . 5.5 Conceptueel ontwerp: conclusie . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

31 31 32 38 38 41

6 Cassandra & GEMINI: implementatie 6.1 gemini load met Cassandra . . . . . . . . . . . . . . . . . . . . . . 6.2 gemini query met Cassandra . . . . . . . . . . . . . . . . . . . . . . 6.3 Implementatie: conclusie . . . . . . . . . . . . . . . . . . . . . . . . .

43 43 44 51

7 Evaluatie

53

ii

. . . .

Inhoudsopgave 7.1 7.2 7.3

Functionele vereisten: testing . . . . . . . . . . . . . . . . . . . . . . Niet-functionele vereisten: benchmarking . . . . . . . . . . . . . . . Evaluatie: conclusie . . . . . . . . . . . . . . . . . . . . . . . . . . .

53 54 64

8 Future work

67

9 Conclusie

69

Bibliografie

81

iii

Samenvatting Technologische en wetenschappelijke vooruitgang in de bioinformatica heeft de kost om DNA te sequencen en te analyseren de afgelopen jaren exponentieel naar beneden gedreven. Allerhande onderzoeksinitiatieven zorgen dan ook voor een explosie aan genoomdata, die steeds sneller, effici¨enter en doortastender geanalyseerd dienen te worden. Gelijkaardige ontwikkelingen in de webwereld hebben geleid tot de NoSQLen NewSQL-systemen, die een schaalbaar alternatief trachten te bieden voor klassieke relationele databanken. Deze masterproef bestudeert 6 NoSQL- en NewSQL-systemen en hun mogelijke toepassingen in de context van de genoomanalyse. Specifiek werd er gekeken naar GEMINI, een tool om met behulp van een verrijkte SQL-syntax variaties in de genomen van grote populaties te onderzoeken die gebruikt wordt door bijvoorbeeld medewerkers van pharmaceutische bedrijven als Janssen Pharmaceutica. Om GEMINI beter te laten schalen naar grote datasets, besloten we de onderliggende SQLite-databank te vervangen door Apache Cassandra. We stellen een nieuw dataschema voor GEMINI voor, dat samen met een nieuw querymechanisme in de client-code de beperkte queryfunctionaliteit van Cassandra omzeilt en zo de oorspronkelijke functionaliteit van GEMINI behoudt. Het nieuwe dataschema introduceert duplicatie van gegevens, maar is, in tegenstelling tot het originele datamodel, uitbreidbaar wanneer nieuwe iteraties van biologische experimenten nieuwe genoomdata opleveren. We hebben dit ontwerp ook ge¨ımplementeerd, om de performantie te kunnen vergelijken met de originele SQLite-versie van GEMINI. Het resultaat is een systeem dat als gevolg van die duplicatie van gegevens tot 10x trager genoomdata inlaadt, maar dankzij het querymechanisme tot 150x sneller ingewikkelde queries kan uitvoeren dan de originele SQLite-versie van GEMINI.

iv

Hoofdstuk 1

Inleiding 1.1

Algemene context

Wetenschappelijke vooruitgang heeft ervoor gezorgd dat de kost om genomen te sequencen het afgelopen decennium exponentieel gedaald is, sinds 2008 zelfs aan een hogere snelheid dan de evolutie volgens de wet van Moore [41]. Dit is duidelijk zichtbaar op de grafiek in figuur 1.1. In allerhande soorten biologisch, medisch en pharmaceutisch onderzoek worden dan ook genomen van meer en meer organismen ontleed (cf. sequenced in het Engels) en dit genereert enorme hoeveelheden data. Ter illustratie: de whole genome sequencing pipeline van het Broad Institute [40], een referentie in het veld, genereert bij het sequencen van 1 volledig menselijk genoom in de orde van 3TB aan tussentijdse data. Het eindresultaat is 50 GB gecomprimeerde data voor 1 menselijk genoom bij 50x coverage (een maat voor de resolutie [39]). Naarmate genomen van miljoenen mensen en andere levende wezens geanalyseerd en opgeslagen worden, vereist deze evolutie steeds betere schaalbaarheid, responstijd, en parallellisering voor de opslag en verwerking van deze data. Een logische stap is om deze problemen aan te pakken met grote verdeelde computersystemen, zogenaamde high performance computing systems (kortweg: HPC) of supercomputers. Het Exascience Life Lab van imec, Intel, Janssen Pharmaceutica en de 5 Vlaamse universiteiten verricht specifiek onderzoek naar de toepassing van supercomputers om technologische processen in de levenswetenschappen, waaronder genoomsequencing, te versnellen [37][38]. Levenswetenschappen zijn echter allerminst het enige vakgebied dat geconfronteerd wordt met sterk stijgende datahoeveelheden: de snel toegenomen populariteit van webdiensten als sociale netwerken zadelde webservice-leveranciers op met een gelijkaardige explosie aan data. Om deze zogenaamde Big Data [46] adequaat te beheren, volstaan traditionele relationele DBMS niet meer. Daarom hebben grote webbedrijven zoals Google, Amazon en Facebook nieuwe opslagtechnieken ontwikkeld die voldoen aan de vereisten qua incrementele schaalbaarheid, lage responstijden en hoge beschikbaarheid [3]. Dit heeft vele zogenaamde NoSQL (’Not only SQL’) databases voortgebracht, die het rigide relationele datamodel inruilen voor betere 1

1. Inleiding schaalbaarheid en gemakkelijkere distributie van de data. Daarnaast is er ook de recentere opkomst van NewSQL-systemen: deze trachten de schaalbaarheid, distributie en fouttolerantie van NoSQL-systemen te combineren met het relationele datamodel en de bijhorende SQL-query interface en sterke garanties op gebied van concurrency en consistentie.

Figuur 1.1: Evolutie van de prijs om een genoom te sequencen sinds 2001 [41]

1.2

Probleemstelling case study: GEMINI

Een concreet voorbeeld van genoomanalyse-infrastructuur die door de hierboven beschreven sequencing-boom tegen haar grenzen botst, is GEMINI. Op vraag van Janssen Pharmaceutica bestudeert deze thesis als case study deze genoomanalysetool. GEMINI (van GEnome MINIng) is een software-framework voor flexibele analyse van genetische variaties in grote datasets van genomen, ontwikkeld aan de University of Utah [50]. Deze datasets aan genomen bevatten informatie over de genetische variants - d.w.z. stukken van genen zoals deze in het genoomsequencingproces waargenomen worden, van meerdere proefpersonen (ook: samples). GEMINI vertrekt daarbij van VCF(Variant Call Format)-bestanden: dit zijn tekstbestanden die informatie over het gesequencete DNA van de samples bevatten, op het niveau van individuele variants. GEMINI laadt deze gegevens in in een database, voegt allerlei annotaties 2

1.3. Contributies en resultaten toe met bijkomende informatie van enkele vermaarde onderzoeksinstituten, en biedt dan de mogelijkheid queries uit te voeren op deze databank in een verrijkte, op maat gemaakte SQL-syntax. GEMINI laat de gebruiker ook toe zelfgedefinieerde annotaties toe te voegen aan de variants. De huidige operationele versie van GEMINI draait op de eenvoudige SQL-databank SQLite, maar deze laat op gebied van schaalbaarheid en performantie te wensen over. De gewenste schaalbaarheid ligt in 2 dimensies: enerzijds het aantal variants in de dataset, en anderzijds het aantal samples wier DNA in de dataset geanalyseerd wordt. Bij toenemend aantal samples of variants duurt zowel het inladen van de genoomdata in de databank voor als het queryen tijdens effectief gebruik te lang om gebruiksvriendelijk te zijn. Het inladen van de genoomdata uit VCF-files is, enigszins contra-intu¨ıtief, geen eenmalige of zeldzame operatie: de huidige productieversie van GEMINI laat niet toe om na het inladen nog samples of variants toe te voegen, met als gevolg dat bij elke iteratie van een genetisch of biologisch experiment die nieuwe informatie oplevert, de volledige dataset opnieuw ingeladen dient te worden. Ook het incrementeel kunnen toevoegen van variants en samples aan de gegevensset is dus een aandachtspunt bij het onderzoek naar mogelijke verbeteringen voor GEMINI. Een eerste oplossing om de performantie te verhogen was om over te schakelen op PostgreSQL, en hiervan is intussen al met succes een eerste versie ge¨ımplementeerd. Het resultaat is een verhoging van de querysnelheden van 5 tot 20x, zonder verregaande optimalisaties. De verwachtingen zijn echter ook hier dat PostgreSQL op langere termijn niet zal kunnen schalen naar datasets van (honderd)duizenden genomen. Naar de toekomst toe is het dus noodzakelijk uit kijken naar andere technologie¨en en types databanken om GEMINI ook bruikbaar te maken voor grootschaligere experimenten.

1.3

Contributies en resultaten

De contributies in dit eindwerk zijn drievoudig: een vergelijkende studie van 6 NoSQLen NewSQL-systemen, een ontwerp om het datamodel en de functionaliteiten van GEMINI over te dragen van SQLite naar een NoSQL-systeem als Apache Cassandra, en een daadwerkelijke implementatie van GEMINI met een onderliggende Cassandradatabase. Onze implementatie is tot 10x trager dan de originele versie van GEMINI bij het inladen van genoomdata, maar biedt wel een uitbreidbaar dataschema, waardoor dit slechts een eenmalige kost is. Bij het queryen is onze implementatie dankzij een effici¨enter query-mechanisme tot 150x sneller dan de originele versie van GEMINI, vooral voor de ingewikkeldere query-features die GEMINI onderscheiden van een standaard databank. Dit verslag is verder opgebouwd als volgt: een algemene introductie tot genoomanalyse (2) en GEMINI (3), een literatuurstudie over NoSQL- en NewSQL-systemen (4), een conceptueel ontwerp van GEMINI in combinatie met een Cassandra-databank 3

1. Inleiding (5), een implementatie (6) en evaluatie van dit ontwerp (7), een bespreking van mogelijke verdere onderzoekspistes en een conclusie.

4

Hoofdstuk 2

Achtergrond genoomanalyse Omdat deze thesis binnen het vakgebied van de genoomanalyse ligt, volgt in dit hoofdstuk een beknopte inleiding in de wereld van DNA, genomen, genen en aanverwanten, met speciale aandacht voor het DNA van de mens.

2.1

Biologische achtergrond

Desoxyribonucle¨ınezuur, kortweg DNA, is de chemische stof die als belangrijkste drager van erfelijke informatie dient in alle levende wezens. DNA bestaat uit twee spiraalvormige, rond elkaar gewikkelde strengen, ook gekend als een dubbele helix. Die twee strengen zijn elk lange ketens van chemische bouwblokken, de nucleotiden, die op hun beurt elk opgebouwd zijn uit 3 delen: een fosfaatgroep, een suikergroep en ´e´en van 4 mogelijke nucleotidebasen. De 4 nucleotidebasen zijn adenine (A), thymine (T), guanine (G) en cytosine (C). De twee strengen zijn aan elkaar gekoppeld door paren van die basen. Er komen slechts 2 verschillende baseparen voor: AT en GC [31] [24]. Het genoom duidt op de volledige set DNA van een organisme. Het menselijk genoom bestaat uit 3 miljard baseparen. Het grootste deel van DNA bevindt zich in lichaamscellen in de vorm van chromosomen. Menselijke cellen bijvoorbeeld tellen 46 chromosomen, die in 23 paren voorkomen. Genen liggen op de chromosomen en bestaan uit ´e´en of meerdere DNA-sequenties die de informatie encoderen voor de productie van ´e´en of meerdere prote¨ınen. De deeltjes binnen een gen die effectief die informatie encoderen, heten exonen; de exonen uit alle genen samen worden aangeduid met de term exoom en zijn goed voor ongeveer 1.5% van het totale DNA [25]. Genen kunnen verschillende invullingen hebben: sommige genen hebben verschillende vormen die op dezelfde positie op het chromosoom liggen, allelen genaamd. Organismen zoals de mens hebben voor elk gen 2 allelen, ´e´en overge¨erfd van elke ouder. Zulke organismen worden ook diplo¨ıde genoemd. Zijn die twee allelen gelijk, dan is het organisme homozygoot voor het gen in kwestie, anders is het heterozygoot. 5

2. Achtergrond genoomanalyse Het genotype is de specifieke combinatie van allelen die samen het DNA van ´e´en individueel organisme vormen, m.a.w. de chemische invulling van het DNA. Daartegenover staat het fenotype, dat duidt op de waarneembare fysieke eigenschappen van een levend wezen. Dat kunnen zeer uiteenlopende eigenschappen zijn, gaande van haar- en oogkleur tot het al dan niet lijden aan een bepaalde erfelijke aandoening. Figuur 2.1 toont een voorbeeld van de bovenstaande concepten.

Figuur 2.1: Een sequentie uit het DNA van 2 personen. De sequentie ligt op dezelfde locatie op het chromosoom bij beide personen, maar verschilt 1 nucleotide tussen de twee personen. De sequentie is dus een single nucleotide polymorphism of variant. Beide personen hebben ook twee allelen voor de variant. Persoon A is homozygoot, persoon B heterozygoot [2]. Een laatste essentieel biologisch concept is een variant of single-nucleotide polymorphism (kortweg SNP of snip). Dit zijn korte sequenties DNA die tussen verschillende individuen in een populatie slechts op exact 1 basepaar verschillen [1]. In populaties kan voor een variant een referentie en een alternatief allel geobserveerd worden. Diplo¨ıde organismen kunnen dus ofwel: • Homozygoot voor het referentie allel zijn, wanneer het genotype bestaat uit 2x het referentie-allel. 6

2.2. DNA sequencing • Homozygoot voor het alternatief allel zijn, wanneer het genotype bestaat uit 2x het alternatieve allel. • Heterozygoot zijn, wanneer het genotype bestaat uit 1x het referentie-allel en 1x het alternatieve allel. Variants zijn zeer belangrijk voor analyse van erfelijke aandoeningen: een nauwe overerving van zowel bepaalde variants als een bepaald fenotype kan de mogelijke locatie van een gen dat een aandoening veroorzaakt reduceren tot een regio op een chromosoom van slechts enkele gensequenties. Die kunnen dan nader onderzocht worden op hun structuur en functie om te bepalen welk gen verantwoordelijk is voor het gemuteerde fenotype. Relevante vragen voor biologen zijn dus welke variants voorkomen bij alle (of veel) individuen met eenzelfde fenotype, en nadien welke variants allemaal in dezelfde regio liggen op een chromosoom. Zoals later (zie 3) uitgebreid aan bod komt, biedt GEMINI ook queries om dit soort vragen te beantwoorden.

2.2

DNA sequencing

DNA sequencing is het bepalen van de exacte sequentie van nucleotidebasen in een streng DNA. De vandaag meest gebruikte sequencingmethode genereert reads van 125 opeenvolgende nucleotiden, en miljarden reads tegelijkertijd. Om de segmenten horende in ´e´en langer stuk DNA aan elkaar te kunnen linken, is het nodig vele overlappende segmenten te lezen, die vervolgens met elkaar gealigneerd worden. Elke nucleotide moet dus meerdere keren gelezen worden om een goede nauwkeurigheid van het uiteindelijke resultaat te bekomen. De depth van een nucleotide, of bij uitbreiding een groter stuk DNA, is het aantal keren dat een nucleotide gelezen werd tijdens het sequencingproces. De coverage is de gemiddelde depth over de hele DNAstreng die gesequenced werd en dus een maat voor de resolutie en nauwkeurigheid van het sequencingproces. De uiteindelijke sequencedata worden vaak opgeslagen in SAM-files (of BAM, het binaire equivalent) en het is op basis hiervan dat variant calling gebeurt: het bepalen welk genotype een proefpersoon precies heeft voor een variant. De resultaten van het variant-callingproces worden opgeslagen in VCF-bestanden (Variant Call Format). Het VCF-formaat bevat naast meta-informatie een lijn voor elke geobserveerde variant, met daarin optioneel informatie over het genotype van ´e´en of meerdere proefpersonen. In onderzoek naar het DNA van proefpersonen is ook nog andere informatie van tel dan enkel hun genotypes: gegevens als het geslacht of fenotype van proefpersonen kunnen uiterst relevant zijn voor onderzoek naar bijvoorbeeld genetische ziektes. In experimenten die het DNA van meerdere proefpersonen analyseren, is het ook bijzonder interessant de onderlinge verwantschappen tussen de proefpersonen te kennen. Samen met de genotype-informatie is het dan mogelijk erfelijkheidspatronen in de genoomdata te bestuderen. Informatie over de proefpersonen zit niet in VCF-files, maar kan gespecifieerd worden in pedigree-files (PED-files). 7

2. Achtergrond genoomanalyse

2.3

Voorbeeldvraagstukken genoomanalyse

Deze sectie schetst kort een voorbeeld van de soort analyses die biologen maken met behulp van tools zoals GEMINI, en de extra informatie die ze hiervoor nodig hebben. Biologen kunnen bijvoorbeeld ge¨ınteresseerd zijn in: • Variants die gelinkt zijn met bepaalde aandoeningen. Van sommige variants is hun correlatie met erfelijke aandoeningen reeds bekend en die informatie kan in annotaties samengevat worden. Zo kent GEMINI bijvoorbeeld de volgende annotaties: – is somatic: variants kunnen somatisch verworven mutaties zijn. Dit zijn mutaties die na de bevruchting optreden en later tot kanker of andere ziekten kunnen leiden. – clinvar disease name: de naam van de aandoening waarvoor de variant relevant is. • Variants die vaak voorkomen in specifieke populaties. Zo kent GEMINI bijvoorbeeld de aaf 1kg afr-annotatie, die de allel-frequentie (de frequentie waarmee een allel in een populatie voorkomt) in het genotype van proefpersonen van Afrikaanse origine uit het 1000 Genomes project voorstelt. • Variants die op een bepaalde positie in het DNA liggen. Zoals aangehaald in 2.1, proberen biologen de oorzaak van aandoeningen te beperken tot een zo klein mogelijke regio in het DNA. Daarvoor is het nuttig te kunnen zoeken naar variants die op een specifiek chromosoom binnen een bepaald bereik van startposities liggen. • Variants waarvoor bepaalde proefpersonen een bepaald genotype hebben. Zo kan het interessant zijn te zoeken naar variants die voorkomen in het DNA van proefpersonen met een aandoening (i.e. waarvoor die homozygoot zijn voor het referentie-allel), terwijl ze niet voorkomen in het DNA van gezonde personen. Dit kan kleinschalig gebeuren, door bijvoorbeeld de genotypes van een kind en zijn ouders te vergelijken, of op grotere schaal door een volledige populatie van proefpersonen te bestuderen.

8

Hoofdstuk 3

GEMINI overzicht GEMINI is een applicatie voor de flexibele analyse van genoomdata van populaties van menselijke individuen. Deze sectie gaat dieper in op de belangrijkste features en het onderliggende datamodel van GEMINI in zijn oorspronkelijke vorm [50][51].

3.1

Database schema

GEMINI importeert genetische variants en genotypes van alle gesampelde individuen (ook ’samples’) vanuit een VCF file in een relationele database. Daarnaast kan extra informatie over de samples, zoals geslacht, fenotype en onderlinge verwantschappen, meegegeven worden in een PED-file (van pedigree) om latere analyse te vergemakkelijken. Figuur 3.1 schetst een overzicht van de structuur van GEMINI. Elke variant in een input VCF file wordt uitvoerig geannoteerd na automatische vergelijking met bestaande of door de gebruiker gedefinieerde genoom-annotatiebestanden. De geannoteerde variants vormen de rijen van de hoofdtabel van de database, de variants-tabel. Deze tabel bevat ook voor elke variant informatie over elke sample, zoals diens genotype en de kwaliteit en diepte van de meting voor de variant in kwestie. In de SQLite-versie van GEMINI wordt dit opgeslagen als een gecomprimeerde array per variant, 1 voor elke sample-eigenschap: zo is er een gt type-kolom met arrays met de genotypes, en een gt depth-kolom met arrays met de diepte van de meting van elke sample voor elke variant. Figuur 3.2 toont een voorbeeld van de variants-tabel met 1 kolom van het binary array-type, namelijk de gts-kolom. Samen met de samples-tabel, die voor elke sample zaken als het geslacht, fenotype en familierelaties bijhoudt, ligt de variants-tabel aan de basis van de uitgebreide query-mogelijkheden die GEMINI biedt. Daarnaast zijn er nog tabellen zoals de variant impacts- en gene detailed-tabellen die respectievelijk extra informatie over de variants en het menselijk genoom bevatten. Deze informatie komt in het eerste geval eveneens uit de annotatiebestanden, en in het tweede uit tekstbestanden met referentie-informatie over het menselijk genoom die GEMINI, indien gewenst, mee inlaadt.

9

3. GEMINI overzicht

10

Figuur 3.1: Een overzicht van GEMINI’s schema [50]

3.2. Inladen

Figuur 3.2: Een voorbeeld van de variants-tabel. Ten laatste zijn er nog enkele kleine tabellen met meta-informatie, zoals de resources-tabel die de gebruikte annotatie-files bevat, en de version-tabel die bijhoudt door welke versie van GEMINI de data ingeladen is. Een belangrijke troef van GEMINI en z’n datamodel is de flexibiliteit die het laat naar de gebruiker. Zo kan de gebruiker zelfgedefinieerde annotatie-files gebruiken, en zelf kolommen toevoegen aan de PED-files met informatie over de samples. Deze extra informatie zal GEMINI automatisch in de resp. variants- en samples-tabel opnemen en kan de gebruiker later ook doorzoeken.

3.2

Inladen

Het inladen van de data uit VCF-bestanden is een computationeel intensieve operatie, enerzijds omwille van de grootte van deze bestanden (al gauw meerdere gigabytes, in gecomprimeerd formaat), en anderzijds omdat alle variants geannoteerd moeten worden. Om het proces te versnellen, biedt GEMINI de mogelijkheid het werk te paralleliseren door het VCF-bestand te comprimeren, op het gecomprimeerde bestand een index te defini¨eren, hiermee het gecomprimeerde bestanden in stukken op te splitsen en zo het werk te verdelen. Dit kan over meerdere processoren binnen 1 computer zijn, maar via de IPython-interface ook over volledige clusters van computers [53]. Het inladen van genoomdata in GEMINI verloopt in vier opeenvolgende stappen. De eerste en de laatste lopen op ´e´en processor in de hoofdthread van GEMINI, stappen 2 en 3 kunnen allebei op meerdere processoren tegelijkertijd lopen. Figuur 3.3 vat het proces samen. 1. In de eerste van de vier stappen controleert GEMINI de input-files en splitst deze over het aantal door de gebruiker gespecifieerde processoren. Met behulp 11

3. GEMINI overzicht

Figuur 3.3: Een overzicht van het loading proces in GEMINI.

van de bgzip [45] en grabix [55] tools comprimeert GEMINI de meegegeven VCF-file, definieert hier een index op en splitst het gecomprimeerde bestand vervolgens in blokken. Elke processor krijgt zo’n blok toegewezen en werkt hiermee verder in stappen 2 - 3. De overige input (i.e. de PED-file), verdeelt GEMINI niet. Omdat het aantal samples in de PED-file vaak vele malen kleiner is dan het aantal variants in de VCF-file, is het inladen van de samples-tabel verwaarloosbaar vergeleken met het inladen en annoteren van de variantstabel. 2. In stap 2 initialiseert GEMINI de databank, maakt de nodige tabellen aan en laadt de samples-informatie in. GEMINI haalt de namen van de samples uit de VCF-file en vult die aan met informatie uit de PED-file. Indien er geen PED-file voorhanden is, initialiseert GEMINI de samples-tabel met default-waarden voor de kolommen zoals sex en phenotype. Indien het inladen op meerdere processoren verloopt, cre¨eert elke processor een eigen databank en voert hierin de sample-informatie in. 3. In stap 3 voert GEMINI de variants in in de databank. GEMINI haalt de variants ´e´en voor ´e´en uit de VCF-file, annoteert ze met informatie uit de geselecteerde annotatiebronnen en voegt ze toe aan de variants-tabel. Eens 12

3.3. Querying de variants-tabel volledig gevuld is, indexeert GEMINI de tabellen in de databank. In het parallelle scenario werkt elke processor in deze stap op zijn eigen deel van de input VCF-file. 4. Stap vier is enkel nodig wanneer de gegevens met meerdere processoren ingeladen zijn. Alle processoren hebben immers een eigen SQLite-database aangemaakt en die moeten nog allemaal samengevoegd worden tot ´e´en geheel. Dit gebeurt dan ook in stap 4. Een belangrijke kanttekening bij het inladen van genoomdata is dat de huidige versie van GEMINI met SQLite niet toelaat variants of samples toe te voegen aan een reeds bestaande databank. Bij elke iteratie van een biologisch experiment die nieuwe gegevens oplevert, zit er dus niets anders op dan de volledige dataset inclusief de nieuwe gegevens opnieuw in te laden. Dit betekent dat de performantie van het inladen extra belangrijk is.

3.3

Querying

GEMINI laat de gebruiker toe de opgeslagen genoomdata te doorzoeken. Enerzijds via gewone SQL-queries, maar omdat het onderzoeken van individuele genotypes van cruciaal belang is in het onderzoek naar ziektes en SQL standaard niet de individuele genotypes in array-kolommen kan opvragen, biedt GEMINI bovendien een verrijkte SQL-syntax. Zo laat het de gebruiker toe via filters en wildcards de gewenste genotype-eigenschappen en samples te specifi¨eren.

3.3.1

Sample-filters/-wildcards

In SQL SELECT-statements kan de gebruiker met een filter van de vorm column.sample of een wilcard van de vorm (column).(wildcard) uitdrukken welke genotypekolommen van welke samples hij/zij wilt zien. Wanneer de gebruiker ge¨ınteresseerd is in bijvoorbeeld het genotype van Jan, wordt dit: SELECT gt types.Jan FROM variants Als de gebruiker de diepte van de genotypes alle samples van vrouwelijke proefpersonen wil zien, wordt dit: SELECT (gt depths).(sex = ’female’). GEMINI vertaalt de wildcard automatisch naar een query op de samples-tabel, en kan vervolgens voor alle samples die aan de voorwaarden voldoen, de waarde uit de gevraagde kolom tonen. 13

3. GEMINI overzicht

3.3.2

Genotype-filters/-wildcards

Om beperkingen op te leggen aan de variants waarin hij/zij ge¨ınteresseerd is, kan de gebruiker SQL WHERE-clausules uitbreiden met zogenaamde genotype filters. Is de gebruiker bijvoorbeeld enkel ge¨ınteresseerd in variants waarvoor John heterozygoot is en Alex alles behalve heterozygoot is, kan dit met: $ gemini query -q ”SELECT * FROM variants”\ --gt-filter ”gt types.John == HET and gt types.Alex != HET” Vaak is het de bedoeling om eenzelfde beperking op te leggen aan meerdere samples. Op bovenstaande manier wordt dit voor een toenemend aantal samples al snel monnikenwerk. Om dit te verhinderen, zijn er genotype-wildcards van volgend formaat: (column).(sample wildcard).(gt wildcard rule).(rule enforcement). • column Staat voor de genotype kolom waarop de beperking slaat. • sample wildcard Een wildcard om aan te duiden voor welke samples de beperking moet gelden. Analoog met de eerder vermelde sample wildcards. • gt wildcard rule De beperking op de genotype kolom. • rule enforcement Duidt aan hoeveel van de geselecteerde samples aan de opgelegde gt wildcard rule moeten voldoen. Dit kan all, any, none, of count zijn. Alle variants opvragen waarvoor alle mannelijke proefpersonen heterozygoot zijn, gaat bijvoorbeeld met: $ gemini query -q "SELECT * FROM variants"\ --gt-filter"(gt types).(sex = ’male’).(=HET).(all)" Alle variants opvragen waarvoor minstens 1 bruinharig individu een genotype van diepte minstens 100 heeft, met: $ gemini query -q "SELECT * FROM variants"\ --gt-filter"(gt depths).(hair colour = ’brown’).(>=100).(any)" Alle variants opvragen waarvoor minder dan 10 individu¨en een genotype met diepte minder dan 50 hebben, met: $ gemini query -q "SELECT * FROM variants"\ --gt-filter"(gt depths).(*).(=HET).(count < 10)" Al de bovenstaande filters kunnen met elkaar gecombineerd worden, evenals met gewone WHERE-clausules op de andere kolommen van de variants-tabel. 14

3.3. Querying

3.3.3

--show-samples

GEMINI biedt ook de mogelijkheid, bij een query op de variants-tabel, voor elke variant die aan de gestelde eisen voldoet, de namen van alle samples weer te geven die voor gegeven variant homozygoot of heterozygoot zijn. Dit gebeurt door de --show-samples flag mee te geven aan het query commando.

15

Hoofdstuk 4

Achtergrond datastores Sinds de jaren ’70 zijn zogenaamde relational database management systems (kortweg RDBMS) de voornaamste technologie voor de grootschalige opslag van gegevens. Ze zijn gestoeld op 2 belangrijke principes, namelijk het relationele datamodel [15] en de gestructureerde querytaal SEQUEL, beter gekend als SQL [10]. De architectuur van vele RDBMS is nog steeds gebaseerd op de eerste implementatie van een dergelijk systeem, namelijk het IBM onderzoeksproject System R [5], ook uit halverwege de jaren ’70 [57]. System R is ontworpen voor destijds relevante hardwarekarakteristieken en productvereisten: business data processing via een command line interface, en dit op computersystemen met trage processoren, kleine werk- en schijfgeheugens maar relatief grote bandbreedte tussen de schijfopslag en het werkgeheugen. Dit leidde tot een aantal architecturale features die nog steeds terug te vinden zijn in hedendaagse RDBMS: • Disk-geori¨enteerde opslag- en indexstructuren • Multithreading om latency op te vangen • Concurrency-controlemechanismen op basis van locking • Log-gebaseerd herstel van fouten Ondanks gigantische technologische vooruitgang op gebied van hardware en sterk gediversifieerde gebruiksscenario’s, is er sinds hun ontstaan 40 jaar geleden weinig drastisch veranderd aan het concept van de RDBMS en zijn deze systemen de werkpaarden van de industrie geworden op het vlak van dataopslag. Beginnende in de jaren 2000 groeide in de IT-wereld dan ook het besef dat de rigide one size fits all -aanpak van RDBMS voor vele moderne toepassingen achterhaald dreigde te geraken. Met grote opkomende spelers uit de web-industrie zoals Google, Amazon en Facebook aan het roer leidde dit tot de opkomst van de NoSQL-beweging. NoSQL staat, in tegenstelling tot wat de naam doet vermoeden, voor Not only SQL en omvat een waaier van uiteenlopende alternatieve gegevensopslagsystemen die elk in bepaalde specifieke opzichten meerwaarde trachten te bieden ten opzichte van 17

4. Achtergrond datastores het klassieke relationele systemen. In tegenstelling tot de ’Zwitsers zakmes’-aanpak van RDMBS, leggen ze zich toe op zeer gespecialiseerde toepassingsdomeinen en proberen daarin relationele systemen te overtreffen. Vaak betekent dit dat NoSQL systemen vele voor hun doel onnodig geachte features van SQL systemen achterwege laten, of afzwakken. Een goed voorbeeld hiervan zijn de ACID-eigenschappen uit het relationele model die in vele NoSQL-systemen gereduceerd zijn tot zogenaamde BASE-eigenschappen (op het verschil tussen beide komt sectie 4.1.2 nog uitgebreid terug). De reden waarom web-spelers overstapten op NoSQL-systemen of er zelf ontwierpen, is voornamelijk dat deze geschikter zijn voor de enorme hoeveelheden data die dergelijke bedrijven sinds de opkomst van Web 2.0 moeten verwerken. NoSQL-systemen staan er om bekend horizontaal en incrementeel te schalen naar gigantische datasets: door eenvoudigweg servers toe te voegen aan de cluster onder de databank, en niet door bestaande servers up te graden (i.e. verticaal schalen), kan een cluster vlot meegroeien met de dataset. Bovendien draaien NoSQL-systemen doorgaans op goedkope commodity hardware, dus standaard servers, in plaats van dure gespecialiseerde databankservers. Goedkope doordeweekse servers laten toe om zowel kost- als energie-effici¨enter redundantie en dus ook fouttolerantie in te bouwen en zo de zeer hoge vereiste beschikbaarheid te garanderen [4]. NoSQL-systemen zijn bijgevolg grootschalige, gedistribueerde systemen, met bijhorende mechanismen om data ten eerste op te splitsen en te verspreiden (ook: partitioneren of sharden) en ten tweede te repliceren over de cluster. Replicatie heeft meerdere doelen: verhoogde bedrijfszekerheid, load balancing en verhoogde doorvoer in lees-intensieve toepassingen.

4.1

Concepten

Deze sectie belicht de belangrijkste begrippen in verband met NoSQL-databanken en contrasteert waar nodig met gelijkaardige concepten in het klassieke traditionele model.

4.1.1

Partitionering

Gezien de grote datahoeveelheden en gedistribueerde setting van NoSQL is het een noodzaak data in de databank te verspreiden. Er bestaan meerdere strategie¨en om de entries in een databank (dit kunnen rijen, documenten, simpele values,. . . zijn) over de nodes in een cluster te verdelen. Ten eerste is er het onderscheid tussen horizontaal en verticaal partitioneren: bij horizontaal schalen, ook sharding genoemd, wordt een entry niet gefragmenteerd, maar in zijn geheel toegewezen aan een node, op basis van een op de entry gedefinieerde key. De meeste NoSQL-datastores implementeren een versie van horizontaal partitioneren. Verticaal partitioneren stamt uit het relationele model, en betekent het splitsen van grote tabellen in meerdere kleinere tabellen. Binnen het horizontaal partitioneren bestaan 2 voorname methodes [34]: 18

4.1. Concepten • Range partitioning: elke server is verantwoordelijk voor een bepaald bereik van key-waarden. Deze methode leent zich uitstekend tot het verwerken van range queries, gezien opeenvolgende keys vaak op eenzelfde node zullen liggen. Er is echter ook een belangrijk nadeel met deze aanpak verbonden: ze kan leiden tot load-balanceringsproblemen en hot spots. Wanneer een applicatie bijvoorbeeld de gegevens in volgorde van hun key-waarden verwerkt, zal de werklast steeds bij dezelfde servers geconcentreerd liggen. Een ander nadeel is dat een centrale routing server de mapping van de ranges van keys naar nodes moet bijhouden, die dan client requests naar de juiste nodes door kan sturen. Dit introduceert een mogelijke flessenhals in het systeem. • Consistent hashing: zoals de naam doet vermoeden, gebeurt de partitie in dit geval op basis van een hash van de key van entries. De output van de hash-functie wordt als een ring beschouwd en alle nodes krijgen een willekeurige waarde of positie toegewezen op deze ring. Een entry wordt dan toegewezen door via de hash van zijn key zijn positie in de ring te bepalen en vervolgens de ring klokwijs te bewandelen tot de eerste node met positie groter dan de positie van de entry. Het voordeel van consistent hashing is dat de positie van een object zeer snel berekend kan worden en dat hier geen centraal bewaarde mapping voor nodig is. Bovendien is het toevoegen van nodes zeer eenvoudig: enkel de buren van een nieuwe node op de ring merken dit, waardoor weinig entries verplaatst moeten worden. Een belangrijk nadeel is dat consistent hashing range queries bemoeilijkt, gezien opeenvolgende entries nu verspreid kunnen liggen over verschillende nodes. Een techniek die vaak gepaard gaat met consistent hashing is het gebruik van virtual nodes om load-balancing te verbeteren: elke fysieke node in de cluster krijgt meerdere posities toegewezen op de ring, en is zo verantwoordelijk voor meerdere virtuele nodes. Dit zorgt voor een betere verdeling van de entries over de nodes, gezien entries niet per se uniform over de ring verdeeld liggen. Bovendien moeten niet alle fysieke nodes verantwoordelijk zijn voor evenveel virtuele nodes: het systeem kan meer virtuele nodes toewijzen aan performantere fysieke nodes en zo rekening houden met heterogeniteit in de fysieke infrastructuur. Bovendien zal, bij het falen van een fysieke node, zijn opgeslagen last eerlijk verspreid worden tussen de overgebleven fysieke nodes. Omgekeerd zal een nieuwe node wanneer hij toetreedt tot de cluster van alle andere fysieke nodes ongeveer evenveel last overnemen [34][23].

4.1.2

Consistentie

Consistentie van database-transacties betekent dat transacties de databank in een consistente staat achterlaten: alle data die een applicatie kan zien, is een consistente momentopname van de databank [54]. Traditionele RDBMS bieden vaak transacties met de zogenaamde ACID-eigenschappen [35]: • Atomicity: Elke transactie gebeurt ofwel volledig, ofwel helemaal niet. 19

4. Achtergrond datastores • Consistency: Elke transactie laat de databank in consistente staat achter. • Isolation: Elke transactie verloopt volledig ge¨ısoleerd van elke andere transactie, ze be¨ınvloeden elkaar dus op geen enkele manier. • Durability: Eens voltrokken, blijft elke transactie duurzaam bewaard in de databank, ook in het geval van stroomonderbrekingen, crashes of fouten. Zoals Eric Brewer stelde in zijn bekende CAP-theorema [8], is het in een gedistribueerd systeem niet eenvoudig zowel consistentie, availability als tolerantie voor partities te bereiken en zijn 2 van die 3 eigenschappen het hoogst haalbare1 . Ook in NoSQL-systemen, die vaak gedistribueerd van aard zijn, is het garanderen van consistentie geen triviale opgave. Afhankelijk van de gehanteerde schrijfstrategie is het mogelijk dat verschillende knopen in de cluster verschillende versies van data zien, als updates nog niet in de volledige cluster doorgekomen zijn. Daarom is er het onderscheid tussen strikte en uiteindelijke (”eventual ”) consistentie: strikte consistentie is de gekende vorm waarin updates onmiddellijk zichtbaar zijn op alle nodes in de cluster, en dus ook naar bovenliggende applicaties toe. In het geval van uiteindelijke consistentie garandeert het systeem enkel dat na verloop van tijd alle nodes in de cluster dezelfde, up-to-date versie van de data zullen zien. NoSQL-systemen bieden dan ook vaak de BASE-eigenschappen, een zwakkere versie van de ACID-garanties: • Basically available: Het systeem is onder quasi alle omstandigheden beschikbaar. • Soft state: Het systeem verkeert niet altijd in een consistente staat • Eventually consistent: Na verloop van tijd zal het systeem in een gekende staat verkeren. Vele NoSQL-systemen stellen de gebruiker echter niet voor een voldongen feit bij de keuze tussen strikte en uiteindelijke consistentie: dankzij zogenaamde quora kan de gebruiker zelf configureren welke consistentie het systeem levert. Door leesen schrijfquora in te stellen, kan de gebruiker tunen hoeveel replica’s respectievelijk moeten returnen bij een schrijfopdracht, en het welslagen van een schrijfopdracht moeten bevestigen. Op deze manier kan de gebruiker zelf een trade-off maken tussen snel lezen, schrijven en de behaalde consistentie. Bovendien zal de gebruiker, wanneer de som van het lees- en schrijfquorum groter is dan de replicatiefactor van de cluster, steeds de meest recente versie van gegevens zien, wat hetzelfde betekent als onmiddellijke, strikte consistentie.

4.1.3

Storage layout

Ook op het gebied van hoe ze gegevens zowel op schijf als in het geheugen opslaan, verschillen NoSQL-systemen van elkaar. Sommigen hanteren de gebalanceeerde 1

Brewer kwam hier zelf 12 jaar later op terug, stellende dat mits goede omgang met partities het toch mogelijk is een trade-off van alle drie te bereiken [7].

20

4.2. NoSQL-klassen B-bomen die ook vele RDBM-systemen gebruiken. Anderen, in navolging van Google Bigtable, doen beroep op zogenaamde log-structured merge trees[49][11]. In deze strategie worden updates niet onmiddellijk naar schijf geschreven: de data wordt in werkgeheugen aangepast en de update wordt op schijf gelogd. Wanneer er genoeg updates in geheugen gebeurd zijn, worden deze allemaal tegelijkertijd naar schijf geschreven. Dit kan sequentieel gebeuren, en vermijdt zo vele random writes, wat de schrijfdoorvoer ten goede komt.

4.2

NoSQL-klassen

NoSQL databanken zijn er in verschillende soorten en kunnen op basis van hun datamodel in een aantal categorie¨en onderverdeeld worden: • Key-Value stores zijn vergelijkbaar met dictionaries en mappen unieke keys op values. Deze values zijn voor de databank volledig betekenisloze byte-arrays en de enige manier om ze op te vragen, is via de bijhorende key. Voor zeer eenvoudige toepassingen resulteert dit in hoge lees- en schrijf-throughput, maar meer geavanceerde features zoals indexing, queries, en het modelleren van relaties binnen de data zijn hierdoor niet mogelijk[36][34]. • Columnar stores zijn gebaseerd op het datamodel dat Google’s Bigtable heeft ge¨ıntroduceerd en slaan data op in een spaarse, gedistribueerde, persistente en multidimensionele gesorteerde map[11]. In het geval van Bigtable zijn dit drie dimensies: row key, column key en een timestamp. Bigtable is voorzien op de enorme hoeveelheden data die Google op dagelijkse basis verwerkt en de hiervan afgeleide columnar stores staan dan ook bekend om hun uitstekende schaalbaarheid. De goede schaalbaarheid en fouttolerantie van Bigtable is ook deels toe te schrijven aan het onderliggende gedistribueerde file systeem, Google File System [32]. Andere innovaties uit Bigtable zijn onder andere het gebruik van log-structured merge trees (zie 4.1.3) en Bloom filters: een effici¨ent probabilistisch mechanisme om te voorspellen of een object in een verzameling zit (in dit geval, of een key in een tabel ligt, wat het aantal nodeloze table scans beduidend kan inperken) [48]. Omdat net als in Key-Value stores het systeem hier de opgeslagen data niet interpreteert, is het modelleren van relaties niet op een effici¨ente manier mogelijk. Dit wordt overgelaten aan de bovenliggende applicatie [36]. • Document stores bewaren data als key-value paren en encapsuleren deze in documenten. Values kunnen van een brede waaier aan types zijn, zoals geneste documenten, lijsten of scalars. De namen van attributen kunnen dynamisch gespecifieerd worden tijdens runtime en moeten geen vooraf vastgelegd schema volgen[9]. Dit is geschikt voor het modelleren van ingewikkelde datastructuren. Vele document stores gebruiken het JSON-bestandsformaat (of een daarvan afgeleide vorm). In tegenstelling tot columnar stores, zijn de waarden in documenten niet betekenisloos voor het document store systeem en het is dus mogelijk hier indexen op te defini¨eren en queries op uit te voeren [36]. 21

4. Achtergrond datastores • Graph databases: zoals de naam doet vermoeden, stammen ze uit grafentheorie en maken ze gebruik van grafen als datamodel. Ze zijn uitermate geschikt om sterk verweven data te beheren, van bronnen zoals sociale netwerken of location based services. Hiervoor doen ze beroep op effici¨ente mechanismen om grafen te doorlopen waar andere systemen kostelijke operaties als recursieve joins gebruiken[36]. De term NewSQL slaat op een verzameling systemen die ambi¨eren het klassieke relationele datamodel te combineren met de schaalbaarheid, distributie en fouttolerantie van NoSQL systemn. Hoewel ze allen de gebruiker het relationele model en SQL-achtige query mogelijkheden bieden, verschillen NewSQL stores onderling grondig, afhankelijk van de onderliggende architectuur. Zo zijn er onder meer systemen die gebouwd zijn bovenop bestaande NoSQL databanken, en andere die alle data in main memory opslaan[34].

4.3

NoSQL: vergelijkende studie

Op de vraag of NoSQL en NewSQl-systemen al dan niet geschikt zijn om het genoomanalyseproces schaalbaarder te maken, bestaat geen eenvoudig antwoord. Gezien de grote diversiteit in de beschikbare gegevensopslagsystemen, zullen sommige systemen onvermijdelijk beter geschikt zijn dan andere, of beter geschikt voor andere aspecten van de genoom-analyse pipeline. Een vergelijkende studie van NoSQL- en NewSQL-systemen dringt zich dus op. Deze sectie bekijkt 6 systemen in meer detail en licht toe hoe ze van pas zouden kunnen komen in de genoomanalyse.

4.3.1

Methodologie

Omwille van het enorme aanbod aan NoSQL en NewSQL systemen was een exhaustieve studie niet haalbaar. Deze vergelijkende studie behandelt de populairste datastores in een aantal relevante categorie¨en, namelijk document stores, columnar stores en NewSQL stores. Key-value stores en graph databases komen niet aan bod, aangezien hun datamodellen niet geschikt zijn voor de toepassing in kwestie. De uiteindelijke selectie werd gemaakt volgens criteria vergelijkbaar met die in [34], met de ranking van DB-Engine Ranking [56] als maat voor de populariteit.

22

J

J

Concurrency controle

Open-source?

J

Single-row transacties (ACID mogelijk), OCC met MVCC voor grootschaligere operaties

Tabel 1: Een overzicht van de vergeleken datastores en hun features.

J

Rij-niveau atomiciteit, CAS

Applicatie kan optimistische (met CAS) of pessimistische concurrency controle implementeren

Atomische single document operaties, anders 2-phase commit; Concurrent reads, exclusive writes (lock op DB niveau)

Strikt

Configureerbaar

Partitioning

Primair & secundair, LSM-tree

Configureerbaar

Range-partitioning m.b.v. shard key

Query optimizatie

Primair & secundair, LSM-tree

HDFS

Consistentie

memcached

Query optimizer, shard-keys om distributed queries te versnellen

Indexing

Cassandra File System (HDFS compatibel)

Binnen cluster: strikt; tussen meerdere clusters: uiteindelijk

Primair & secundair, B-tree

Primaire & secundaire op elk attribuut, B-tree

Storage

J

Vertrouwt op onderliggende storagelaag

Vertrouwt op onderliggende storagelaag

Default niet, maar mogelijk

Partition pruning met partition key

Primair & secundair

HDFS of HBase

Masterloos

Master-slave of multi-master, asynchrone replicatie

Range-partitioning

Standaard Unix & Windows FS’s

Standaard FS’s, 16MB document limiet

Distributie

Masterloos, asynchrone replicatie

SQL-92, MapReduce

SQL on top of Hadoop

Cloudera Impala

Geen querytaal (Hive via workaround), Java API, MapReduce

Consistent hashing (of range-partitioning)

Multi-master, asynchrone replicatie

Master-slave, asynchrone replicatie

Querying & API

CQL, rijke API, MapReduce

Wide columnar store

Hashing function

N1QL, memcached API, MapReduce

Propri¨etaire taal, dynamische queries via JS, rijke API, MapReduce

Wide columnar store

HBase

Bloom filter

Document-store (JSON)

Document-store (BSON)

Type

Cassandra

Bloom filter

CouchBase Server

MongoDB

J

ACID + data access geserializeerd en uitgevoerd in single-threaded omgeving

Strikt

Consistent hashing

Queries in stored procedures gepland at compile time

Primair & secundair. Hash- & tree-indexes

Main memory

Masterloos, updates simultaan uitgevoerd op alle replicas.

SQL-92, Java stored procedures, rijke API, MapReduce

In-memory relational NewSQL

VoltDB

4. Achtergrond datastores Deze ranglijst tracht populariteit te meten op basis van enkele parameters, zoals aantal vermeldingen op websites, algemene interesses volgens Google Trends, frequentie van technische discussies op fora zoals StackOverflow, vacatures i.v.m. de technologie en vermeldingen in professionele profielen op sites zoals LinkedIn. De resulterende selectie bestaat uit de document stores MongoDB en CouchBase Server, wide columnar stores Cassandra en HBase en NewSQL database VoltDB. Er bestaat al een uitbreiding van de DNA sequencing pijplijn die het ExaScience Life Lab gebruikt om MongoDB databanken als in- en/of uitvoer te gebruiken voor de pijplijn. Dit maakt MongoDB uiteraard nog relevanter. Ten laatste werd ook NewSQL query engine Cloudera Impala in de studie betrokken wegens expliciete interesse van onderzoekers in het eerder vernoemde lab. Deze 6 systemen vergeleken we vervolgens op een aantal voor high performance computing relevante eigenschappen zoals indexeringsmechanismen, interfaces naar de gebruiker en API’s, distributiestrategie, concurrency controle en consistentiemodel. Tabel 4.3.1 geeft een overzicht weer van de bestudeerde systemen.

4.3.2

Document stores

MongoDB MongoDB slaat gegevens op in BSON (binary JSON) documenten. Het systeem biedt krachtige ondersteuning voor indices, vooral door de mogelijkheid om secundaire indices van een brede waaier van types te defini¨eren op alle attributen, zoals in het relationele model. Deze indices zijn gebouwd op B-trees [47]. Om denormalizatie te bevorderen, kunnen documenten geneste documenten en arrays bevatten. Zo zijn joins ook overbodig in de query taal. De bestandsgrootte is beperkt tot 16 MB, om te voorkomen dat ´e´en enkel document buitensporig veel RAM of bandbreedte opeist. Om grotere bestanden te bewaren, kan het ingebouwde GridFS (dat integenstelling tot wat de naam doet vermoeden, geen volwaardig file system is) automatisch bestanden opsplitsen in kleinere delen en deze delen als aparte documenten bewaren, zonder dat de gebruiker zich hierom moet bekommeren. MongoDB biedt API’s in zeer vele programmeertalen en de functionaliteit om het equivalent van SQL WHERE-clausules te defini¨eren als javascript uitdrukkingen. MongoDB vertaalt deze vervolgens naar een eigen, interne en afgeschermde query taal [34]. De query optimizer van MongoDB verwerkt queries en kiest voor elke query een zo effici¨ent mogelijk uitvoeringsplan gegeven de beschikbare indices. Deze plannen worden gecached als er meerdere goede alternatieven zijn en kunnen geherevalueerd worden naarmate de gegevensset in de databank evolueert. Qua consistentie laat MongoDB de keuze tussen uiteindelijke en strikte consistentie. Strikte consistentie is mogelijk door ofwel enkel te lezen van de master node (die de meest up-to-date versie van de data heeft) of na schrijfopdrachten te wachten tot alle replica’s bevestigd hebben alvorens verder te gaan. De eerste optie introduceert een bottleneck bij het lezen van data, de tweede verhoogt de latentie van schrijfopdrachten. 24

4.3. NoSQL: vergelijkende studie MongoDB repliceert data asynchroon en partitioneert in ranges: nodes zijn verantwoordelijk voor ranges van keys. Dit zorgt voor snelle range queries, maar kan hotspots en load-balancingproblemen veroorzaken. Dankzij een master-slave structuur kan MongoDB updates gemakkelijk naar de juiste replica’s doorverwijzen. Op het gebied van concurrency controle biedt MongoDB atomiciteit binnen documenten en reader-writer locks. Bij schrijfopdrachten de databank locken heeft een zware impact op de performantie in scenario’s waar veel geschreven moet worden. Kortom, MongoDB bewaart BSON-bestanden op een zeer toegankelijke manier met flexibele query- en indexeringsmechanismes. De concurrency- en consistentiemodellen daarentegen vertonen enkele nadelen. Couchbase Server Couchbase, het resultaat van de fusie tussen CouchDB en Membase, slaat gegevens op in JSON documenten. Het hanteert het memcached protocol om een gedistribueerde cache te bieden en is bedoeld voor zeer interactieve toepassingen met hoge vereisten op gebied van latentie [34][17]. De JSON documenten kunnen genest zijn en kunnen doorzocht worden met een uitgebreide, SQL-achtige taal, N1QL (op het moment van schrijven is dit wel nog steeds een developer preview, uitgebracht in januari 2015) [19]. Net als MongoDB kunnen primaire en secundaire indices gedefinieerd worden en zijn deze gestoeld op B-trees [18]. Binnen ´e´en cluster zijn transacties strikt consistent, maar tussen meerdere clusters slechts uiteindelijk consistent. CouchBase biedt gebruikers de keuze tussen optimistische (m.b.v. compare-and-swap) en pessimistische (m.b.v. ’finegrained locking’) concurreny controle. Dankzij zijn flexibele datamodel, caching en concurrency controle, past CouchBase goed voor toepassingen die snelle en intensieve interactieve vergen tussen gebruiker en data.

4.3.3

Columnar stores

Cassandra Cassandra werd oorspronkelijk ontwikkeld voor intern gebruik bij Facebook maar is later als Apache opensourceproject publiekelijk beschikbaar gemaakt. Het combineert het columnaire datamodel van Google’s Bigtable systeem (zie 4.2) met de architectuur en distributiestrategie van Amazons DynamoDB. Het is gericht op flexibele, quasipermanent beschikbare opslag van zeer grote datasets op goedkope standaardhardware, met daarenboven hoge througput voor schrijfopdrachten zonder effici¨entie bij leesopdrachten op te offeren [6]. Sinds zijn ontstaan is Cassandra wel op enkele vlakken afgeweken van het Bigtablemodel [44], in die zin dat het nu tabellen en composite columns biedt, evenals een eigen query taal, CQL [20]. CQL vertoont op het gebied van syntax en functionaliteit sterke gelijkenissen met SQL, maar is toch sterk beperkt. Zo biedt het bijvoorbeeld 25

4. Achtergrond datastores geen JOIN-clausule, en zijn WHERE-clausules aan sterke voorwaarden onderhevig. Cassandra moedigt het samen bewaren van gegevens die samen opgevraagd worden sterk aan en ondersteunt denormalizatie met features zoals collection types. Cassandra heeft indexeringsmechanismes en implementeert deze met log-structured merge trees, met hogere schrijfthroughput als gevolg. Ook biedt Cassandra net als Google Bigtable Bloom filters. Om lineair in het aantal ingeschakelde nodes te kunnen schalen naar zeer grote datasets, opereert Cassandra op een volledig hi¨erarchieloze wijze. Vanuit het perspectief van het CAP-theorema, spitst Cassandra zich toe op availability en partition tolerance, ten koste van onmiddellijke consistentie. Het consistentieniveau kan wel per query door de gebruiker bepaald worden, zoals later verduidelijkt wordt. Hoge beschikbaarheid en tolerantie voor fouten bereikt Cassandra door asynchroon data te repliceren over verschillende nodes, met consistent hashing en virtuele nodes om frequent komen-en-gaan en incrementeel toevoegen van nodes op te vangen. Het aantal replica’s kan de gebruiker zelf kiezen. Bovendien voorziet Cassandra ook interdatacenterreplicatie, om zelfs het falen van volledige datacenters op te vangen [23] [43] [44]. Bij lees- en schrijfopdrachten kan de gebruiker een quorum specifi¨eren. Hoewel Cassandra met uiteindelijke consistentie voor ogen ontworpen werd, is onmiddellijke consistentie mits een juiste keuze van de quorum dus ook een optie. Op het gebied van concurrency controle garandeert Cassandra atomiciteit binnen rijen en serializeerbare lightweight transactions, eigenlijk compare-and-set functionaliteit, voor grotere operaties. Samengevat biedt Cassandra redelijk flexibele datamodellering met (licht beperkte) query- en indexeringsmechanismen via de CQL-interface. Het sterkste punt is echter dat Cassandra incrementeel schaalt naar enorme datasets, dankzij uitvoerige replicatie- en foutverwerkingsfeatures. HBase Apache HBase is een opensource datastore gebaseerd op Google Bigtable, die draait bovenop het Hadoop Distributed File System (HDFS) in plaats van het Google File System (GFS). Sinds z’n lancering heeft HBase verschillende secundaire indexeringsmechanismes verworven. Die zijn ook gebaseerd op LSM trees en daarnaast biedt ook HBase Bloom filters [6][29]. HBase heeft een Java API, maar zonder SQL-achtige geavanceerde querytaal. Hierbij moet wel opgemerkt worden dat een omweg via Apache Hive, een ander data-opslag en -analyseproject [27], en de bijhorende querytaal HiveQL dit probleem kan verhelpen. Dankzij de HDFS-fundering can HBase vlot fungeren als in- en output voor MapReduce taken. HBase partitioneert data net als Bigtable in ranges en repliceert gegevens op ofwel master-slave of multi-master wijze. Leesopdrachten worden echter niet gedistribueerd: er is slechts 1 server die instaat voor elke rij. De replica’s zijn enkel bestemd voor het herstellen van fouten. 26

4.3. NoSQL: vergelijkende studie De sterke punten van HBase zijn de sterke consistentie, een rariteit in de NoSQLwereld, en het concurrency-model: ACID transactions binnen rijen en optimistische, multi-version concurrency controle voor grootschaligere operaties [28][34][6]. Kort samengevat laat HBase gebruikers toe flexibel data te modelleren en is het systeem vooral nuttig wanneer het startpunt een dataset in HDFS is en MapReducecompatibiliteit een prioriteit is. HBase schaalt goed naar zeer grote datasets en beschikt over uitstekende concurrency- en consistentie-eigenschappen.

4.3.4

NewSQL

VoltDB VoltDB is een relationele, gedistribueerde in-memory databank, die als doel heeft de garanties van klassieke SQL-stores te koppelen met de schaalbaarheid van NoSQLsystemen, en bovendien aan zeer hoge snelheden te functioneren [58]. VoltDB bewaart gegevens in het traditionele relationele model, maar gerepliceerd en gepartitioneerd (met consistent hashing) over verschillende nodes [34]. De data is doorzoekbaar via een groeiende subset van SQL-92 [61]. Queries worden bij voorkeur gedefinieerd als stored procedures in Java, met daarin ingebed de SQL-uitdrukkingen. Gezien de queries op voorhand gekend moeten zijn, leent VoltDB zich dus ook niet optimaal tot flexibele ad-hoc queries. VoltDB ondersteunt primaire en secundaire indices en laat de gebruiker de keuze tussen hash- en boomindices [59]. VoltDB plant en optimaliseert de queries in stored procedures offline tijdens het compileren [60]. Omdat VoltDB volledig op RAM geheugen vertrouwt, is het duur om te schalen naar datavolumes in de grootorde van meerdere petabytes, maar VoltDB kan data exporteren naar andere, meer geschikte databanksystemen zoals columnaire NoSQL systemen. Vooral op het gebied van concurrency controle onderscheidt VoltDB zich van andere systemen: transacties voldoen aan de ACID-eigenschappen en worden simultaan op alle replica’s uitgevoerd. Het geheugen is in blokken verdeeld, die elk statisch toegewezen zijn aan ´e´en enkele, single-threaded core. Een globale controller serializeert alle transacties waarbij meerdere nodes betrokken zijn tot een sequentie van enkelvoudige transacties en voegt die in in de transaction queues van de betrokken nodes. Op deze manier maakt VoltDB locking en latching technieken overbodig. De durability uit ACID bereikt VoltDB door op regelmatige basis snapshots van de databank in het geheugen te nemen en deze op schijf op te slaan. Kort samengevat is VoltDB een relationele databank in main memory die schaalt tot relatief grote datasets, met zeer snelle SQL-query-capaciteiten en ACIDtransacties. Het is bijgevolg meer geschikt voor rekenintensieve toepassingen die niet overdreven veel data verwerken, maar wel zeer lage latentie vereisen. 27

4. Achtergrond datastores Cloudera Impala Cloudera Impala is een gedistribueerde SQL-machine die draait bovenop de Hadoopstack, ofwel op HDFS of op HBase [42]. Ze is specfiek bedoeld voor analytisch gebruik, met een focus op het leveren van real-time query-capaciteiten eerder dan op hoge throughput bij schrijfopdrachten. Opgeslagen data is toegankelijk via een subset van SQL-92. Impala’s architectuur is bijna perfect symmetrisch gedistribueerd: alle nodes voeren hetzelfde impalad-proces uit, dat de belangrijkste databankfunctionaliteiten verzorgt. Elke node kan als startpunt fungeren voor een query en zal vervolgens de query in kwestie co¨ ordineren. Twee processen lopen daarentegen op ´e´en enkele (niet noodzakelijk dezelfde) node in de cluster; zij staan in voor boekhoudkundige taken en doorgeven van wijzingen aan metadata doorheen de cluster [13]. In tegenstelling tot voorgaande opties partitioneert Impala rijen niet automatisch. De gebruiker krijgt wel de keuze hiertoe, voor in het geval de hoeveelheid gegevens hierom zou vragen [14]. Impala beschikt over een zeer effici¨ente I/O-laag die schijf- en CPU-gebruik te allen tijde hoog houdt, wat resulteert in aanzienlijk snellere prestaties dan andere SQL-on-Hadoop oplossingen zoals Apache Hive [26]. Het inherente nadeel is echter dat de volledige dataset moet passen in het totale werkgeheugen van de cluster waarin Impala draait. Dit beperkt enigszins de grootte van datasets die Impala kan verwerken, ondanks de schaalbaarheid van de onderliggende Hadooplaag. Omwille van z’n analytische doeleinden heeft Impala geen uitvoerige mechanismes voor concurrency controle, maar vertrouwt hiervoor op het onderliggende opslagsysteem. Gezien de uitstekende concurrency-eigenschappen van HBase vormt dit niet noodzakelijk een probleem. Samengevat is Impala een querymachine die HBase of HDFS aanvult met uitgebreide en performante analytische SQL-queryfunctionaliteit. Impala is wel nog niet geschikt voor de allergrootste datasets.

4.3.5

Vergelijkende studie: conclusie

Deze sectie bestudeerde 6 datastores, 2 van de populairste in 3 verschillende categorie¨en, en vergeleek ze met elkaar op een aantal eigenschappen relevant voor HPC toepassingen. Columnaire stores als Cassandra en HBase zijn geschikt om gigantische datasets op te slaan op een robuuste en performante manier, en zouden kunnen dienen om de informatie uit reeds gesequencete genomen op te slaan. MongoDB blinkt uit dankzij een uitgebreide API, flexibele datamodel, en query- in indexeringsmechanismen. Het beschikt niet over even goede schrijfeigenschappen als de columnaire systemen, maar is desondanks een sterke kandidaat voor de opslag van grote datasets zoals genomen. VoltDB en CouchBase Server bieden lage latency bij lees- en schrijfopdrachten, zij het op kleinere datasets, maar lenen zich dus goed tot het bewaren van snel evoluerende tussentijdse gegevens in de sequencing pipeline. Tot slot is Cloudera Impala geschikt voor situaties waar snelle, mogelijks ingewikkelde leesqueries eerder dan schrijfqueries op grote datasets vereist zijn. Ook Impala is 28

4.4. Achtergrond datastores: conclusie dus eerder geschikt voor de analyse van al gesequencete genomen, maar op kleinere schaal dan de columnaire NoSQl-databanken.

4.4

Achtergrond datastores: conclusie

Dit hoofdstuk schetst de belangrijkste technologische achtergrond van deze thesis op het gebied van databanksystemen. NoSQL en NewSQL kunnen, dankzij hun afkomst uit de webwereld, geschikt zijn om om te gaan met de grote hoeveelheden data die de bioinformatica met zich meebrengt. Na een toelichting van enkele essenti¨ele begrippen zoals consistentie, partitionering en storage layout, kwam een vergelijkende studie van 6 NoSQL en NewSQL-systemen aan bod, met specifieke aandacht voor hoe elk van deze systemen van toepassing kan zijn in de genoomanalysepijplijn.

29

Hoofdstuk 5

Cassandra als databank voor GEMINI Dit hoofdstuk belicht aan de hand van een case-study de conceptuele uitwerking van een schaalbare tool voor genoomanalyse. De case-study in kwestie is een versie van GEMINI die werkt met een Cassandra i.p.v. SQLite databank. Achtereenvolgens komen een motivatie voor de keuze voor Cassandra, de nodige aanpassingen aan het dataschema van GEMINI en de nodige aanpassingen aan GEMINI zelf om de inlaaden querying-functionaliteit van GEMINI te behouden, aan bod.

5.1 5.1.1

Keuze database Vereisten

Zoals beschreven in [3] bewaart GEMINI de data over genetische varianten en proefpersonen in enkele zeer grote tabellen. Een eerste vereiste voor een database is dus om deze tabulaire data goed te kunnen voorstellen en beheren. Omdat de nadruk van dit onderzoek specifiek ligt op het schaalbaar maken van de applicatie, gebeurt dit bij voorkeur d.m.v. automatische verspreiding over verschillende nodes in een cluster. Omdat GEMINI meerdere processoren of zelfs computers kan gebruiken bij het inladen van de gegevens uit VCF-bestanden, zijn goede concurrency-controle en hoge schrijfthroughput eveneens belangrijk. Na het inladen van de VCF bestanden voert GEMINI enkel nog leesqueries uit, dus zijn de belangrijkste verdere vereisten voor een database hoge leesthroughput, goede querymogelijkheden en indexeringsmechanismes die ook op een performante manier de verrijkte SQL-syntax van GEMINI ondersteunen. Ten laatste is een Python-API ook nuttig, gezien GEMINI in Python ge¨ımplementeerd is. 31

5. Cassandra als databank voor GEMINI

5.1.2

Keuze

De uiteindelijke keuze voor een databank viel op Apache Cassandra. Van de systemen besproken in [4.3] heeft Cassandra veruit de meest interessante architectuur qua schaalbaarheid en bovendien verwachten we dat het columnaire model zich goed leent tot het modelleren van de tabellen in de oorspronkelijke versie van GEMINI, wat we dan ook experimenteel zullen valideren. Vergeleken met het andere columnaire systeem in de vergelijkende studie, HBase, heeft Cassandra uitgebreidere query-mogelijkheden. Vergeleken met MongoDB, dat sterker staat op het gebied van querying en indexing heeft Cassandra het voordeel dat het flexibeler is voor concurrent schrijven naar de databank. Bovendien blijkt uit eerdere experimenten met MongoDB binnen het lab dat MongoDB niet space-effici¨ent BSON-documenten kan uitbreiden. In het geval van een incrementele versie van GEMINI, waar na verloop van tijd genoominformatie van extra proefpersonen ingeladen moet worden, leidt dit tot fragmentatie. Cassandra daarentegen kan eenvoudig het schema van tabellen aanpassen en naar behoefte extra kolommen en rijen toevoegen.

5.2

Dataschema

Het datamodel van Apache Cassandra vertoont enkele sterke verschillen met het relationele datamodel. Dit vereist enkele grondige aanpassingen aan het database schema van GEMINI. In deze sectie komen de belangrijkste eigenschappen van Cassandra aan bod, hun gevolgen voor de belangrijkste database-functionaliteiten, en een conceptuele schets van benodigde aanpassingen aan het onderliggende dataschema van GEMINI.

5.2.1

Datamodel Cassandra

Zoals eerder vermeld bewaart Cassandra de cellen in een tabel als een 2 dimensionele map van enerzijds een per rij gedefinieerde primary key, en de naam van een kolom. De inhoud van cellen die niet in de primary key van een rij liggen, heeft voor Cassandra geen enkele betekenis. Die primary key bestaat uit 2 delen: het eerste is de partition key, deze bestaat uit minstens 1 kolom en de (gehashte) waarde hiervan bepaalt via het consistent-hashing mechanisme op welke partitie in de cluster de rij terechtkomt. Het tweede, optionele, deel is de clustering key, en bepaalt in welke volgorde rijen met dezelfde partition key op 1 node bewaard worden. Dit is standaard in oplopende volgorde. Gezien Cassandra in essentie een grote map is, is de effici¨entste manier om rijen op te vragen uit een tabel eenvoudig de hash te berekenen van de primary key om vervolgens de passende rijen te returnen. De inhoud van kolommen buiten de primary key is ook volledig betekenisloos voor Cassandra en het individueel en iteratief inspecteren van cellen druist om performantieredenen in tegen de principes van Cassandra. Bij gevolg zijn de query-mogelijkheden eerder beperkt: zonder 32

5.2. Dataschema het defini¨eren van indices is het in WHERE-clausules enkel mogelijk beperkingen op te leggen aan kolommen in de primary key, en dan nog zo dat de bedoelde rijen binnen 1 partitie liggen, en opeenvolgend opgeslagen zijn. Daarom moet er een gelijkheidsbeperking opgelegd worden aan de volledige partition key, en mogen er zowel gelijk- als ongelijkheidsbeperkingen opgelegd worden aan de kolommen in de clustering key, maar enkel op voorwaarde dat de voorgaande kolom in de clustering key ook met een gelijkheidsbeperking gespecifieerd is. Op deze manier kan Cassandra queries zeer snel uitvoeren door ze a.d.h.v. de hash van de partition key naar een juiste node te routeren, en vervolgens via de overige opgegeven kolommen de locatie van de juiste rijen te berekenen (die omwille van de clustering allemaal op elkaar volgend opgeslagen zijn). Dit gebeurt zonder de waarden van individuele cellen te bekijken, maar dus enkel door het berekenen van een simpele hashfunctie. Range-queries zijn dus enkel mogelijk op kolommen in de clustering key en het is niet mogelijk !=-beperkingen te gebruiken in WHERE-clausules. Bovendien laat Cassandra enkel toe beperkingen met elkaar te combineren via conjuncties, dus niet via OR- of NOT-operatoren. Een uitzondering op dit laatste is de IN-operator: op deze manier kan de gebruiker meegeven in welke set van waarden een bepaalde kolom moet liggen, maar dit is ook enkel mogelijk op de laatste kolom in de partition key of de laatste kolom in de clustering key (maar weer op voorwaarde dat de voorgaande kolommen reeds beperkt zijn). Cassandra laat toe om indices op kolommen te defini¨eren, maar die zijn niet bijzonder nuttig. Ze laten enkel gelijkheidsbeperkingen toe (dus geen range-queries) en bovendien raadt Datastax (die een enterprise-versie van Cassandra bouwen) het gebruik van indices op kolommen met zowel een zeer lage als een zeer hoge kardinaliteit af, dit omdat in het eerste geval de index tabel zal bestaan uit zeer weinig zeer lange rijen voor elk van de ge¨ındexeerde waarden en in het tweede geval Cassandra bij een query op de ge¨ındexeerde kolom door zeer veel verscheidene waarden zal moeten zoeken om een klein aantal resultaten te vinden [22].

5.2.2

Databaseschema GEMINI

Zoals blijkt uit bovenstaande beschrijving van het datamodel van Cassandra, leent het systeem zich niet goed tot ad-hoc querying: het is niet mogelijk op een performante manier zomaar aan willekeurige kolommen in een tabel voorwaarden op te leggen en deze voorwaarden met elkaar te combineren. Dit betekent dat bij het ontwerpen van het databaseschema al rekening gehouden moet worden met de queries die achteraf op de data mogelijk moeten zijn. Omdat het soort queries dat een tabel ondersteunt sterk samenhangt met de keuze van de primary key van de tabel en GEMINI meerdere, uiteenlopende soorten queries op elke tabel vereist, zal dit onvermijdelijk leiden tot duplicatie van data. De belangrijkste queries die ondersteund moeten worden in GEMINI, zijn de volgende: • Queries op de variants-tabel die genotype-eigenschappen van specifieke proefpersonen opvragen, al dan niet met behulp van sample-wildcards. Het moet ook 33

5. Cassandra als databank voor GEMINI mogelijk zijn voorwaarden op te leggen aan de genotypes van proefpersonen, met genotype-filters en -wildcards. • Normale SQL-achtige queries op arbitraire kolommen van de variants- en samples-tabellen. • Queries op JOINs van tabellen. De documentatie van GEMINI heeft het in dit geval vooral over JOINs tussen enerzijds de gene detailed- of gene summarytabellen en anderzijds de variants- of variant impacts-tabellen [52]. Deze drie vraagstukken komen achtereenvolgens aan bod in deze sectie. In deze sectie komen meerdere schematische voorstellingen van databanktabellen voor. Om de leesbaarheid te verhogen, zijn hierin de namen van kolommen uit de partition key steeds in het groen en van kolommen uit de clustering key in het rood weergegeven. variants-tabel vs. genotype-informatie Het belangrijkste vraagstuk is hoe de genotype-kolommen uit het oorspronkelijke relationele model in Cassandra op te slaan. Hier zijn enkele opties voor: • Collection columns Cassandra biedt zogenaamde collection types, zoals sets, lists of maps. Dit is vergelijkbaar met de bestaande implementatie in SQLite (buiten dat ze in Cassandra niet als binary blobs bewaard worden). Het nadeel is echter dat deze collections niet meer dan 65536 (216 ) entries kunnen bevatten, wat het hele nut van de migratie naar Cassandra, namelijk verhoogde schaalbaarheid, teniet zou doen. • Super-variants-tabel Een andere mogelijkheid is de variants-tabel uit te breiden met een kolom voor elke genotype-eigenschap van elke sample. Deze aanpak heeft als voornaamste voordeel dat de kolommen met genotypeeigenschappen van specifieke samples zonder omwegen uit de variants-tabel gehaald kunnen worden. Dit is vooral van belang voor de in (3) beschreven sample-filters. Bovendien kan Cassandra tot 2 miljard cellen opslaan op 1 partitie, dus vormt het grote aantal kolommen dat dit model met zich meebrengt, geen probleem.

variant id

ref

alt

...

gt types.alex

gt types.john

...

gt depths.alex

gt depths.john

Het nadeel is echter dat het onmogelijk is ad-hoc queries te defini¨eren op genotype-eigenschappen van willekeurige samples zonder het gebruik van secundaire indices. Elke query die in een WHERE-clausule andere kolommen of samples betrekt, vereist om de hierboven beschreven redenen een andere keuze van de primary key om effici¨ent de juiste rijen te kunnen opzoeken. Beschouw 34

...

5.2. Dataschema bijvoorbeeld deze twee queries: $ gemini query -q ”SELECT * FROM variants”\ --gt-filter ”gt types.john == HET and gt depths.alex > 100” $ gemini query -q ”SELECT * FROM variants”\ --gt-filter ”gt types.john == HET and gt depths.tim > 75” De eerste vereist als primary key ((gt types.john),(gt depths.alex)), terwijl de tweede ((gt types.john),(gt depths.tim)) vereist. Beide eisen zijn niet verzoenbaar, wat betekent dat hier twee verschillende tabellen met dezelfde data, maar andere primary keys nodig zijn. • genotype-tabellen Een derde optie is een variants-tabel zonder genotypeinformatie, gecombineerd met een tabel voor elke eigenschap van de genotypes van de samples, met een rij voor elke (variant, sample). Bijvoorbeeld: – Een variants by samples gt-tabel met als primary key ((sample name, gt type), (variant id)). De primary key is zo gekozen dat alle variants waarvoor een sample eenzelfde genotype heeft, bij elkaar op 1 node liggen, zodat deze gemakkelijk opgevraagd kunnen worden. Hetzelfde was mogelijk geweest met enkel sample name als partition key, maar met de bovenstaande, granulairdere partition key zijn de variants beter over de cluster verspreid. Bovendien houdt het vanuit een semantisch oogpunt geen steek range queries uit te voeren op de gt type-kolom, dus moet deze niet per se in de clustering key staan. De variant id-kolom ten slotte maakt enkel deel uit van de primary key om deze uniek te maken voor elk tupel (variant, sample, genotype).

sample name

genotype

variant id

– Een variants by samples gt depth-tabel met als primary key ((sample name), (gt depth, variant id)). Omdat range queries op de gt depth-kolom wel een vereiste zijn, moeten alle variants voor eenzelfde sample volgens gt depth geclusterd, en dus gerangschikt staan. Vandaar dat de gt depthkolom in dit geval in de clustering key, en niet in de partition key staat. Voor de rest is de keuze van de primary key volledig analoog met die in de variants by samples gt-tabel. sample name

gt depth

variant id

– Vergelijkbare tabellen voor de overige genotype-eigenschappen. 35

5. Cassandra als databank voor GEMINI Het grote voordeel van deze aanpak is dat het, dankzij de keuze van de primary key, zeer eenvoudig is variants op te vragen waarvoor het genotype van ´e´en sample aan specifieke gelijkheids- of ongelijkheidsvoorwaarden voldoet. Het nadeel van dit schema is drieledig: ten eerste scheidt het de informatie over de genotypes van samples van de andere informatie over de variants. Dit betekent dat, om deze samen weer te geven, een JOIN van de variants-tabel met een genotype-tabel nodig is, en Cassandra biedt zoals geweten geen JOINs. Ten tweede is het onmogelijk om met een sample-filter voor meerdere samples de genotypes tegelijkertijd op te vragen, en ten laatste is het onmogelijk in een query voorwaarden op te leggen aan de genotypes van meerdere samples. • Super-variants-tabel + genotype-tabellen Een vierde mogelijke strategie is de combinatie van de tweede en de derde optie. Dit leidt tot nog meer dataduplicatie, maar bewaart wel de mogelijkheid om zowel genotype-informatie van willekeurige samples op te vragen door middel van de sample-filters als de variants-tabel te doorzoeken met, dankzij gt-filters en -wildcards, beperkingen op de genotypes van specifiek gekozen samples. De uiteindelijke keuze is gevallen op de laatste optie, omdat die het meest van de 4 de queryfunctionaliteiten van GEMINI ondersteunt. Zoals hierboven beschreven blijft het zelfs met dit dataschema niet voor de hand liggend alle in GEMINI mogelijke queries uit te voeren, en zal door het ontbreken van JOINs en de layout van de genotype-tabellen het combineren van beperkingen op de genotypes van meerdere samples nog extra aanpassingen vergen. Hier gaan secties 5.4 en 6.2 uitvoerig op in. variants-, samples-tabel vs. arbitraire queries Een tweede belangrijk vraagstuk is hoe de variants- en samples-tabellen zo te ontwerpen dat ze ook op andere, arbitraire kolommen effici¨ent doorzoekbaar zijn. Om queries op kolommen te ondersteunen die logisch gezien enkel met gelijkheden beperkt zullen worden, zoals chrom of respectievelijk sex, zou het in theorie volstaan op deze kolommen een secundaire index te defini¨eren. Dit is eenvoudig bij de creatie van de tabel, veroorzaakt geen duplicatie van data en is zeer rechttoe rechtaan bij het queryen, maar heeft zoals hierboven vermeld onvoorspelbare performantie afhankelijk van de kardinaliteit van de kolommen. Bovendien werkt dit mechanisme niet voor kolommen die vaker met ongelijkheidsbeperkingen gequeried zullen worden, zoals depth, start, of in het geval van de samples-tabel (hypothetisch, deze tabellen zitten niet standaard in GEMINI) leeftijd of generatie. Een aanpak die in beide gevallen op een voorspelbare en betrouwbare manier werkt, is om net als voor de genotype-informatie extra hulptabellen te defini¨eren, met een specifiek gekozen primary key die de gewenste query mogelijk maakt. Deze oplossing zorgt natuurlijk voor veel gedupliceerde data, maar heeft als voordeel dat ze ´e´en coherente en performante aanpak van het probleem mogelijk maakt. Bij het opstellen van deze hulptabellen moet goed overwogen worden welke vaakgebruikte queries een eigen hulptabel vereisen en verdienen. Minder frequente, uitgebreidere 36

5.2. Dataschema queries, kunnen mits een goede keuze van de basishulptabellen immers gesplitst worden in subqueries op deze basishulptabellen. Hetzelfde mechanisme dat voor de gt-filters en -wildcards uitgebreide queries zal uitvoeren is ook hier van toepassing. Dit zal natuurlijk minder effici¨ent zijn dan een aangepaste hulptabel voor de uitgebreide, originele query, maar laat toe de gegevensduplicatie enigszins binnen de perken te houden. Voorbeelden van zulke basishulptabellen zijn: • Een variants by chrom start-tabel, die het eenvoudig maakt alle varianten op te zoeken die op een bepaald chromosoom binnen een range van startposities liggen. De primary key is in dit geval: ((chrom), (start, variant id)). chrom

start

variant id

• Een variants by gene-tabel, die het eenvoudig maakt alle varianten binnen ´e´en gen op te zoeken. De primary key is in dit geval: ((gene), (variant id)). gene

variant id

• Een samples by sex-tabel, die het eenvoudig maakt alle samples van een bepaald geslacht op te vragen. De primary key is in dit geval: ((sex), (sample name)). sex

sample name

De enige soort queries die onze implementatie niet ondersteunt, zijn pure rangequeries, zoals: SELECT * FROM variants WHERE start > 123456 Zoals eerder beschreven in 5.2 laat het datamodel van Cassandra dit niet toe: het is op basis van de query onmogelijk een primary key te bepalen van de rijen in het resultaat om zo een set opeenvolgende rijen uit de tabel in kwestie op te vragen. Een mogelijke oplossing is om een hulptabel te defini¨eren met als partition key een kolom met beperkte kardinaliteit, zoals chrom (de mens heeft slechts 46 chromosomen, zie 2) en als clustering column de kolom waarop range queries nodig zijn, in dit geval start. In de client code kan bovenstaande range query dan vertaald worden naar 46 range queries die voor elk chromosoom de variant binnen de bepaalde range opvragen. JOINs Zoals eerder aangehaald, biedt Cassandra geen JOINs in de bijhorende querytaal CQL. In de plaats moedigt Cassandra het materializen van JOINs aan, namelijk het samen bewaren van gegevens die samen opgevraagd zullen worden. Dit leidt 37

5. Cassandra als databank voor GEMINI tot de denormalizatie t.o.v. relationele dataschema’s, die ontworpen zijn om zo opslageffici¨ent mogelijk alle data voor te stellen en zwaar inzetten op JOINs om gegevens uit verschillende tabellen met elkaar te combineren. GEMINI biedt de gebruiker ook de optie verschillende tabellen samen te doorzoeken m.b.v. JOINs. Enkele voorbeelden zijn: SELECT FROM WHERE

SELECT FROM WHERE

v . chrom , v . gene , g . t r a n s c r i p t m i n s t a r t , g . t r a n s c r i p t m a x e n d , g . synonym , g . r v i s p c t , v . impact v a r i a n t s v , gene summary g v . chrom = g . chrom AND v . gene = g . gene AND v . i m p a c t s e v e r i t y= ’HIGH ’ v . gene , g . t r a n s c r i p t s t a t u s , g . t r a n s c r i p t , v . impact variant impacts v , gene detailed g v . t r a n s c r i p t = g . t r a n s c r i p t AND v . gene = g . gene AND v . gene = ’SCNN1D ’ AND v . i m p a c t s e v e r i t y != ’LOW’

Dankzij het hierboven beschreven query-mechanisme is het echter niet nodig alle tabellen die met elkaar gejoind zouden kunnen worden, ook effectief samen op te slaan in 1 tabel. Door alweer juist gekozen hulptabellen te defini¨eren, kunnen het reeds uitgelegde datamodel en query-mechanisme ook hier van dienst zijn. Om de eerste van de twee queries uit bovenstaand voorbeeld uit te voeren, is dan bijvoorbeeld een tabel nodig die het mogelijk maakt alle variants met een bepaalde impact severity op te vragen (bvb. variants by impact severity), en een tweede tabel die toelaat alle genen uit gene detailed op te vragen voor een bepaalde waarde van de gene en chrom kolommen (bvb. gene detailed by gene chrom). De gewenste variants kunnen opgehaald worden uit de variants by impact severity-tabel en vervolgens kunnen via de gene detailed by gene chrom alle gewenste kolommen uit de variants- en gene detailed-tabellen geselecteerd worden. Een analoge redenering gaat op voor de tweede voorbeeldquery en bij uitbreiding ook voor de andere voor GEMINI relevante JOINs [52].

5.3

gemini load

Het inladen van de genoomdata in de GEMINI-databank is conceptueel erg eenvoudig: elke lijn uit een VCF-file komt overeen met een variant en dus een rij in de variantstabel (en de bijhorende hulptabellen), elke lijn in een PED-file met een sample en dus een rij in de samples-tabel (en de bijhorende hulptabellen). Het inladen kan bovendien versneld worden door de text-input te verdelen over verschillende cores en deze in parallel de data te laten invoeren.

5.4

gemini query

Het uitvoeren van de gewoonlijke GEMINI-queries tegen een Cassandra-databank vergt enkele ingrijpende aanpassingen ten opzichte van de SQLite-versie van Cassandra. Het doel is natuurlijk deze aanpassingen zoveel mogelijk te verbergen voor 38

5.4. gemini query de gebruiker, wat ook in grote mate gelukt is. In deze sectie komt achtereenvolgens aan bod hoe ingewikkelde queries gesplitst worden in eenvoudige subqueries, hoe de resultaten hiervan vervolgens gecombineerd worden en wat dit betekent voor de meest geavanceerde feature van GEMINI, namelijk de genotype-filters en -wildcards.

5.4.1

Splitsing in subqueries

Zoals beschreven in 5.2, kan Cassandra enkel effici¨ent queries uitvoeren die beperkingen opleggen aan de kolommen in de primary key van een tabel, en dit ook slechts onder bepaalde voorwaarden. Bovendien is de enige logische operator die Cassandra ondersteunt om beperkingen te combineren, de conjunctie. Om arbitraire queries en WHERE-clausules te ondersteunen, kan GEMINI niet zoals in de SQLite-versie de WHERE-clausule zomaar onveranderd aan Cassandra doorgeven. Beschouw, ter illustratie, volgende query: SELECT chrom, start, subtype FROM variants WHERE chrom = ’chromX’ AND start > 5600 AND gene = ’gene A’. Deze query valt uiteen in 2 subqueries: een eerste om uit de variants by chrom starttabel alle variants op te vragen die voldoen aan de voorwaarde chrom = ’chromX’ AND start > 5600 en een tweede om uit de variants by gene-tabel alle variants die voldoen aan gene = ’gene A’ op te vragen. Deze subqueries zullen uit de hulptabellen enkel de primary keys opvragen van de rijen die aan de voorwaarden voldoen, in dit geval de variant id van de variants. De overige opgevraagde kolommen, chrom, start, subtype moeten achteraf met deze primary keys opgehaald worden uit de variants-hoofdtabel.

5.4.2

Combineren subqueries

De subqueries zullen elk een verzameling primary keys van rijen als resultaat opleveren. Het is dan zaak deze verzamelingen met set-operaties te combineren tot de finale verzameling primary keys van rijen die aan de query voldoen. De nodige set-operatie hangt af van de oorspronkelijke query. Zo zal het eindresultaat van een conjunctie van subqueries de doorsnede van de resultaatverzamelingen van de subqueries zijn. In het geval van een disjunctie is dit de unie van de resultaatverzamelingen, en in het geval van een negatie van een subquery is dit het verschil tussen de oorspronkelijke verzameling (voor de query) en de resultaatverzameling van de query. Om bijvoorbeeld alle varianten te vinden die niet op een bepaald gen x liggen, moet het verschil bepaald worden tussen de verzameling van alle varianten en de verzameling van alle varianten die op gen x liggen. Tabel 5.1 vat dit samen voor 2 subqueries p en r, hun respectievelijke resultaatverzamelingen res(p) en res(r) en een initi¨ele verzameling rijen I. 39

5. Cassandra als databank voor GEMINI Query p AND r p OR r NOT p

Resultaat res(p) ∩ res(r) res(p) ∪ res(r) I \ res(p)

Tabel 5.1: De verschillende manieren om subqueries met elkaar te combineren.

5.4.3

Ophalen finaal resultaat

Met het resultaat van de subqueries, namelijk de primary keys van alle rijen uit de oorspronkelijk gevraagde (hoofd)tabel die voldoen aan de query, is het eenvoudig het eindresultaat van de query te bepalen. Er is nog ´e´en query nodig die voor alle rijen de gevraagde kolommen opvraagt uit de hoofdtabel. Ook hier is er een mogelijkheid om door parallellisatie het proces te versnellen: de verzameling primary keys kan over meerdere processoren verdeeld worden, die dan elk een deel van het eindresultaat voor hun rekening nemen.

5.4.4

Genotype-filter wildcards

Ter herinnering, de structuur van een genotype-filter wildcard: (genotype column).(sample wildcard).(gt wildcard rule).(rule enforcement) Het uitvoeren en evalueren van deze wildcards is conceptueel niet erg ingewikkeld: het volstaat de sample wildcard te evalueren en vervolgens voor elk van de resulterende samples een subquery op te stellen op de voor genotype column relevante hulptabel van de variants-tabel. Hoe deze subqueries met elkaar gecombineerd moeten worden, hangt af van de gegeven rule enforcement: • Een all-wildcard leidt tot de conjunctie van alle subqueries. • Een any-wildcard leidt tot de disjunctie van alle subqueries. • Een none-wildcard leidt tot de conjunctie van de negaties van alle subqueries. • count-wildcards vallen niet zomaar met set-algebra te evalueren: bij het combineren van de resultaten van alle subqueries moet voor elke variant geteld worden in de resultaatverzameling van hoeveel subqueries hij voorkomt. Nadien kan GEMINI eenvoudig op basis van deze tellingen de varianten bepalen die aan de count-regel voldoen. Dit betekent dat weer veel werk van de databank naar GEMINI zelf verschuift. Een mogelijke manier om dit leed te verzachten is, gezien de goede concurrencyeigenschappen van NoSQL-systemen als Cassandra, om de subqueries in parallel te evalueren in plaats van sequentieel. 40

5.5. Conceptueel ontwerp: conclusie

5.5

Conceptueel ontwerp: conclusie

Bij wijze van gevalstudie voor schaalbare genoomanalyse hebben we een versie van GEMINI draaiende op Apache Cassandra ontworpen. Cassandra droeg onze voorkeur uit omwille van een uitstekende reputatie qua schaalbaarheid, een flexibele datamodel dat goed bij GEMINI past en een gemakkelijk te gebruiken querying API. Voor de omzetting van SQLite naar Cassandra waren enkele aanpassingen aan het ontwerp van GEMINI nodig: vooral aan het databaseschema en het queryingmechanisme, in mindere mate aan de loading-functionaliteit. Hoofdstuk 6 bespreekt de praktische implementatie van dit ontwerp.

41

Hoofdstuk 6

Cassandra & GEMINI: implementatie Dit hoofdstuk beschrijft de praktische realisatie van een versie van GEMINI draaiende op Cassandra in de plaats van SQLite, verderbouwend op het ontwerp uit hoofdstuk 5. De implementatie is gebaseerd op versie 0.1.11 van GEMINI, 2.1.4 van Apache Cassandra en versie 2.5.1 van de Python driver voor Cassandra, ontwikkeld door DataStax [21]. De volledige implementatie is te vinden op GitHub1 .

6.1

gemini load met Cassandra

Het inladen van genoomdata met GEMINI in Cassandra gebeurt in twee stappen. De reden voor die opsplitsing is dat een klein deel van het inladen en initialiseren van de databank slechts 1 keer moet gebeuren (wegens ´e´en centrale databank) en gezien de geringe tijdsduur niet effici¨ent op te splitsen valt, en dus niet gebaat is bij het paralleliseren over meerdere processoren. In de eerste en kleinste stap van de twee initialiseert GEMINI de databank, maakt de nodige tabellen aan en laadt de samples-informatie in. In tegenstelling tot de SQLite-versie van GEMINI (zie 3.2) gebeurt dit slechts ´e´en keer, ongeacht het aantal beschikbare processoren, en v´oo´r het eventueel opsplitsen van de input over meerdere processoren. In deze fase worden ook de extra, aan de samples-tabel verbonden tabellen zoals samples by sex en samples by phenotype aangemaakt en gevuld, evenals de resources-, gene detailed-, gene summary- en version-tabellen. In de tweede fase gebeurt het leeuwendeel van het werk: het inladen van de variants-informatie uit de (verplicht meegegeven) VCF-file. Net als de oorspronkelijke versie van GEMINI verspreidt deze implementatie met behulp van bgzip [45] en grabix [55] de VCF-input eerlijk over alle beschikbare processoren. Het is ook in deze fase dat GEMINI de aan de variants-tabel verwante tabellen zoals variants by samples gt type, variants by samples gt depth en variants by chrom start opvult. Alle cores of nodes in de cluster, voeren recht1

https://github.com/bgossele/geminicassandra

43

6. Cassandra & GEMINI: implementatie streeks rijen in in ´e´en en dezelfde tabel in de Cassandra-databank. Omdat Cassandra atomiciteit binnen rijen garandeert en alle workers strikt disjuncte sets van variants invoeren in het systeem, is er geen enkel risico op conflicten. De grootste verandering ten opzichte van de SQLite-implementatie van GEMINI is dat in het parallelle gedeelte, alle workers naar dezelfde databank kunnen schrijven. Het samenvoegen van de resultaten van de verschillende processoren (het gemini merge-commando) kan de Cassandra-implementatie volledig overslaan. De Cassandra-implementatie van GEMINI moet in tegenstelling tot de SQLite-versie ook niet meer afzonderlijk de databank indexeren.

6.2 6.2.1

gemini query met Cassandra Splitsing in subqueries

Om zoals in het voorbeeld uit 5.4.1 dynamisch beslissingen over het splitsen in subqueries te kunnen maken, is het nodig de WHERE-clausule te inspecteren en hieruit de benodigde hulptabellen voor de subqueries te identificeren. Om dit proces te vereenvoudigen, hanteert deze implementatie een licht gewijzigde querysyntax: beperkingen die binnen 1 hulptabel liggen, kunnen nog steeds met elkaar gecombineerd worden met het AND-keyword, maar beperkingen die niet binnen eenzelfde hulptabel liggen, moeten met de &&, || of NOT-operatoren van elkaar gescheiden worden. Zo kan GEMINI bij het parsen van de WHERE-clausule deze onmiddellijk opsplitsen in subqueries en voor elk van deze subqueries de nodige hulptabel bepalen. Beschouw wederom volgende query: SELECT chrom, start, subtype FROM variants WHERE chrom = ’chromX’ AND start > 5600 AND gene = ’gene A’. In de aangepaste syntax wordt dit: SELECT chrom, start, subtype FROM variants WHERE chrom = ’chromX’ AND start > 5600 && gene = ’gene A’. Dit vereist uiteraard dat de gebruiker op de hoogte is van welke hulptabellen er bestaan. Gebruikers moeten sowieso weten op welke kolommen ze queries kunnen defini¨eren, en bijgevolg ook welke hulptabellen er bestaan. Bovendien bestaat het doelpubliek van GEMINI uit onderzoekers die het programma intensief gebruiken en dus voldoende gelegenheden hebben om dergelijke aanpassingen snel onder de knie te krijgen. Een andere optie is de syntax onveranderd te laten en uit de in de WHERE-clausule vermelde kolommen benodigde hulptabellen af te leiden. Die aanpak heeft als voordeel dat de interface naar de gebruiker niet verandert, maar gezien nog steeds enkel queries mogelijk zijn op kolommen uit de hoofdtabel waarvoor hulptabellen bestaan, is achterwaartse compatibiliteit hiermee nog niet verzekerd. Daarbovenop levert 44

6.2. gemini query met Cassandra ze ook nieuwe problemen op, zoals: welke combinatie van hulptabellen is het best wanneer sommige kolommen in meerdere hulptabellen voorkomen? Dergelijke vraagstukken neigen naar query-optimization en zijn een interessant onderwerp voor verder onderzoek. De gebruiker dient er ook rekening mee te houden dat Cassandra range-queries enkel onder strikte voorwaarden ondersteunt, namelijk (zoals eerder uitgelegd) enkel op clustering columns en enkel wanneer de voorgaande kolommen in de clustering key met gelijkheden beperkt zijn. Dit impliceert dat er slechts een range query op 1 kolom in een tabel mogelijk is. Daarnaast biedt Cassandra ook geen !=-operator. Dit euvel valt te verhelpen door een !=-clausule om te zetten naar een gelijkheidsbeperking en die vervolgens te negeren. Een clausule als phenotype != 2 wordt dan NOT (phenotype = 2). Dit vereist dat de !=-clausule een aparte subquery vormt. Het uiteindelijke algoritme om de geschikte hulptabel te selecteren op basis van de kolommen en gebruikte operatoren in een subquery, gebruikt de metadata van de Cassandra-cluster om alle hulptabellen voor een gegeven hoofdtabel op te vragen, en vervolgens aan de hand van de kolommen in de primary keys van de kandidaathulptabellen de geschikte eruit te kiezen. GEMINI encapsuleert de subqueries in query expressions: een set Pythonklassen die, ge¨ınspireerd door algebra¨ısche datatypes uit functionele talen zoals Haskell, alle mogelijke GEMINI-queries kunnen voorstellen (zie ook figuur 6.1). Die bevatten alle informatie die GEMINI nodig heeft om de queries te evalueren. De Basic expression stelt een eenvoudige query op een Cassandra-tabel voor. Tijdens het parsen van de WHERE-clausule zal GEMINI de subqueries inkapselen in Basic expressions en die, afhankelijk van de gehele query, nesten in AND -, OR of/en NOT expressions. De GT wildcard expression stelt op een effici¨ente manier genotype-filter wildcards voor (zie 6.2.4). De volgende paragraaf bespreekt in detail de aangeboden evaluate- en can prune-functies.

6.2.2

Combineren subqueries

Uit performantie-overwegingen is het een logische keuze de resultaten van subqueries op de hulptabellen te bewaren in een set datatype. Zo kunnen de benodigde set-operaties gebruik maken van de in Python ingebouwde set-operaties en zo veel effici¨enter verlopen dan wanneer de resultaten in bijvoorbeeld lists bewaard worden. Het enige nadeel van sets t.o.v. lists is dat de implementatie geen garanties biedt over in welke volgorde rijen in het eindresultaat zullen voorkomen. Dit weegt niet op tegen de tijdswinst, en bovendien biedt Cassandra zelf (in de algemeen aangeraden consistent hashing-partitionering) geen enkele garantie over in welke volgorde het rijen opslaat. Bij het evalueren van query expressions komt uiteindelijk meer kijken dan enkel set-operaties. De belangrijkste reden hiervoor is dat, zoals in 5.4.2 reeds beschreven, 45

6. Cassandra & GEMINI: implementatie

Figuur 6.1: De query expressions waarmee alle queries gemodelleerd worden. Het session-argument van de evaluate-functie is een actieve verbinding met de Cassandra-cluster. om een NOT expression te kunnen evalueren, alle kandidaatrijen gekend moet zijn, en dus meegegeven aan de evaluate-functie. Die extra informatie komt ook bij het evalueren van andere types van query expression goed van pas. • Het evalueren van Basic expressions gebeurt niet zo rechttoe rechtaan als de naam doet vermoeden. De evaluate-functie bouwt een CQL-query op, op basis van een gegeven WHERE-clausule, de relevante tabel en de gevraagde kolom uit die tabel. Wanneer er een zinvolle verzameling kandidaatrijen (de starting set) meegegeven is, wordt die als IN-clausule aan de WHERE-clausule toegevoegd. Zo zoekt Cassandra enkel in rijen die effectief in aanmerking komen om aan de globale query te voldoen. Een voorwaarde om die optimalisatie te kunnen toepassen, is dat de WHERE-clausule geen ongelijkheidsbeperkingen mag bevatten (vandaar de can prune-functie). def evaluate ( s e l f , socket , s t a r t i n g s e t ) : query = ”SELECT %s FROM %s ” % \ ( s e l f . SELECT column , s e l f . t a b l e ) i f s e l f . w h e r e c l a u s e != ” ” : query += ” WHERE %s ” % s e l f . w h e r e c l a u s e i f s e l f . c a n p r u n e ( ) and not s t a r t i n g s e t == ” ∗ ” : i n c l a u s e = ” , ” . j o i n (map( s t r , s t a r t i n g s e t ) ) query += ” AND %s IN (%s ) ” % \ ( s e l f . SELECT column , i n c l a u s e ) r e t u r n r o w s a s s e t ( s o c k e t . e x e c u t e ( query ) ) def can prune ( s e l f ) : r e t u r n not any ( op i n s e l f . w h e r e c l a u s e \

46

6.2. gemini query met Cassandra f o r op i n [ ”<” , ”>” ] )

• Om een AND expression te evalueren is het strikt genomen nodig beide leden van de uitdrukking te evalueren en vervolgens de doorsnede te nemen van de resultaten. Als ´e´en van de twee leden van de uitdrukking echter in staat is om dankzij een CQL IN-clausule enkel naar rijen te zoeken die effectief in aanmerking komen om aan de globale query te voldoen, is het mogelijk om die operatie aan Cassandra over te laten. Als het rechterlid kan prunen, dan kan GEMINI de resultaatverzameling van het linkerlid als starting set meegeven bij de evaluatie van het rechterlid, en omgekeerd. Wanneer geen van beide kunnen prunen, moet GEMINI uiteraard nog steeds zelf de doorsnede berekenen. def evaluate ( s e l f , session , s t a r t i n g s e t ) : if

s e l f . r i g h t . can prune ( ) : temp = s e l f . l e f t . e v a l u a t e ( s e s s i o n , s t a r t i n g s e t ) r e t u r n s e l f . r i g h t . e v a l u a t e ( s e s s i o n , temp ) e l i f s e l f . l e f t . can prune ( ) : temp = s e l f . r i g h t . e v a l u a t e ( s e s s i o n , s t a r t i n g s e t ) r e t u r n s e l f . l e f t . e v a l u a t e ( s e s s i o n , temp ) else : temp = s e l f . l e f t . e v a l u a t e ( s e s s i o n , s t a r t i n g s e t ) r e t u r n temp & s e l f . r i g h t . e v a l u a t e ( s e s s i o n , temp )

• In het geval van een OR expression is er geen andere mogelijkheid dan eenvoudigweg het linker- en rechterlid te evalueren, beide met als starting set de starting set van de OR expression zelf, en vervolgens de unie van de resultaten te berekenen. • Ook in het geval van een NOT expression is er geen andere optie dan de bodyuitdrukking te evalueren en vervolgens het complement van de starting set en het resultaat te bepalen. Als de gegeven starting set gelijk is aan "*", d.w.z. alle rijen in de oorspronkelijke tabel, zit er ook niets anders op dan die nog eerst allemaal op te vragen. Dit kan, gezien het grote aantal rijen, een zeer kostelijke operatie zijn. De implementatie maakt er echter nuttig gebruik van dat de primary key van de variants-tabel, variant id, een natuurlijk getal is uit de verzameling [1..N ] (met N het aantal variants). Zo kan GEMINI gewoon het totaal aantal variants opvragen en dan zelf alle variant ids genereren zonder die allemaal uit Cassandra te hoeven opvragen. def evaluate ( s e l f , session , s t a r t i n g s e t ) : s t a r t i n g s e t == ’ ∗ ’ : c o r r e c t s t a r t i n g s e t = r o w s a s s e t ( s e s s i o n . execute (\ ”SELECT %s FROM %s ” % ( s e l f . SELECT column , s e l f . t a b l e ) ) ) else : correct starting set = starting set if

return c o r r e c t s t a r t i n g s e t − \ s e l f . body . e v a l u a t e ( s e s s i o n , c o r r e c t s t a r t i n g s e t )

47

6. Cassandra & GEMINI: implementatie Een optimalisatie die voor alle query expressions geldt is dat in het geval van een lege starting set, GEMINI de hele evaluatie kan overslaan. Dit bespaart een overtollige round-trip naar de Cassandra-databank. Voor alle soorten query expressions behalve de Basic expression geldt ook dat ze kunnen prunen, ongeacht de aard van hun subqueries. In het geval dat hun subqueries een Basic expression bevatten die niet kan prunen, zal de subquery in kwestie dit zelf afhandelen bij de evaluatie.

6.2.3

Ophalen finaal resultaat

Eens de primary keys van de rijen gekend zijn die voldoen aan de query, rest er enkel nog de gevraagde kolommen uit de hoofdtabel op te vragen uit de hoofdtabel. Voor deze laatste query op de hoofdtabel gebruikt onze implementatie de CQL IN-clausule om de primary keys te specifi¨eren. Omdat een GEMINI-query al snel meerdere tienduizenden rijen oplevert, is het niet aangeraden die allemaal in ´e´en gigantische IN-clausule op te vragen, om timeouts te vermijden. Het is dus zaak de verzameling primary keys in kleinere batches op te splitsen. Die batches kunnen dan ook over meerdere processoren verdeeld worden om zo een hogere leesthroughput te bereiken. Het enige nadeel van de parallellisatie is dat de verschillende processen niet meer effici¨ent naar eenzelfde output kunnen schrijven. Onze implementatie laat elke processor naar een apart bestand schrijven, die dan achteraf eventueel met elkaar geconcateneerd kunnen worden.

6.2.4

Genotype-filter wildcards

Gegeven het bovenstaande query-mechanisme is de meest voor de hand liggende manier om genotype-filter wildcards te implementeren, ze op te splitsen in subqueries voor elke sample die aan de voorwaarden in de sample wildcard voldoet, en die subqueries te combineren met een keten van geneste query expressions afhankelijk van de gegeven rule enforcement. Zo wordt een all-wildcard een keten van geneste AND expressions en een any-wildcard een keten van geneste OR expressions. nonewildcards vereisen eerst dat de subqueries in NOT expressiond ingebed worden, die vervolgens allemaal in een keten van geneste AND expressions gecombineerd worden. Het is moeilijker count-wildcards tot dergelijke expressions om te vormen. Die vergen een aparte strategie, die later aan bod komt. Deze aanpak is vergelijkbaar met wat er in de SQLite- en PostgresQL-versies van GEMINI gebeurt: in SQLite vormt GEMINI de wildcards om tot lange Pythonexpressions die uiteindelijk voor elke variant met de Python eval()-functie ge¨evalueerd worden. Dit uiteraard omdat de genotype-kolommen bestaan uit binary blobs die voor de SQLite-databank geen enkele betekenis hebben. De PostgreSQL-versie van GEMINI pakt het slimmer aan en vormt de wildcards om tot lange SQL WHEREclausules en laat zo het evaluatiewerk over aan de databank, met de bemerking dat de PostgreSQL-versie count-wildcards vooralsnog niet ondersteunt omdat dit niet rechtstreeks in SQL vertaald kan worden. In dit opzicht lijkt de Cassandra-implementatie op de SQLite-implementatie, gezien 48

6.2. gemini query met Cassandra de client, niet de databank, het meeste werk verricht. Zoals in de conceptuele uitleg van de oplossing aangehaald, kan de evaluatie van genotype-wildcards effici¨enter verlopen door de evaluatie van de subqueries in parallel uit te voeren op meerdere processoren. Dit hebben we ook daadwerkelijk ge¨ımplementeerd, door introductie van een nieuw type query expression, namelijk de GT wildcard expression. Bij evaluatie zal die de namen van alle samples die aan de sample wildcard voldoen, verdelen over het aantal processoren dat de gebruiker meegeeft, elke processor een tussenresultaat laten berekenen, de resultaten opvragen en samenvoegen m.b.v. de gekende setalgebra. Om het werk effici¨ent over verschillende processoren te verdelen en alle benodigde informatie te communiceren, maakt de implementatie gebruik van zogenaamde subprocesses, die elk hun eigen verbinding openen met de Cassandra-cluster, en interprocess-communicatiemechanismen uit de Python multiprocessing-API [30]. f o r i in range ( s e l f . n r c o r e s ) : p a r e n t c o n n , c h i l d c o n n = Pipe ( ) conns . append ( p a r e n t c o n n ) p = P r o c e s s ( t a r g e t=e v a l ( t a r g e t r u l e + ’ q u e r y ’ ) , \ a r g s =( c h i l d c o n n , s e l f . column , c o r r e c t e d r u l e , \ c o r r e c t s t a r t i n g s e t , s e l f . db contact points , s e l f . keyspace ) ) p r o c s . append ( p ) p. start () #S p l i t names i n chunks and communicate t o p r o c s f o r i in range ( s e l f . n r c o r e s ) : n = l e n ( s e l f . names ) b e g i n = i ∗ s t e p + min ( i , n % s e l f . n r c o r e s ) end = b e g i n + s t e p i f i < n % s e l f . nr cores : end += 1 conns [ i ] . send ( s e l f . names [ b e g i n : end ] ) #C o l l e c t r e s u l t s f o r i in range ( s e l f . n r c o r e s ) : r e s u l t s . append ( conns [ i ] . r e c v ( ) ) conns [ i ] . c l o s e ( ) f o r i in range ( s e l f . n r c o r e s ) : procs [ i ] . join ()

all-, any- en none-wildcards vereisen voor het samenvoegen van de resultaten van de verschillende subprocesses geen grote aanpassingen aan de sequenti¨ele evaluatiestrategie van wildcards. Omdat deze oplossingswijze er zich uitstekend toe leent af te wijken van het stramien van de geneste query expressions (immers, er is maar 1 GT wildcard expression voor alle samples), is het makkelijker de count-wildcards te implementeren: elk subprocess voert subqueries uit voor de samples waarvoor het verantwoordelijk is en telt voor elke variant hoe vaak hij in de resultaatverzamelingen van de subqueries voorkomt. Die informatie stuurt het subprocess terug naar zijn 49

6. Cassandra & GEMINI: implementatie parent-process in een Python dictionary, met een map van variant ids naar het resultaat van de telling. d e f c o u n t q u e r y ( conn , f i e l d , c l a u s e , i n i t i a l s e t ) : names = conn . r e c v ( ) results = dict () f o r name i n names : query = ’ ’ ’SELECT v a r i a n t i d FROM v a r i a n t s b y s a m p l e s %s \ WHERE sample name = ’% s ’ AND %s %s ’ ’ ’ \ % ( f i e l d , name , f i e l d , c l a u s e ) if

i n i t i a l s e t != ” ∗ ” and not any ( op i n c l a u s e f o r op i n [ ”<” , ”>” ] ) : i n c l a u s e = ” , ” . j o i n (map( s t r , i n i t i a l s e t ) ) query += ” AND v a r i a n t i d IN (%s ) ” % i n c l a u s e

v a r i a n t s = r o w s a s s e t ( e x e c u t e ( query ) ) results = add row to count dict ( results , variants ) conn . send ( r e s u l t s ) conn . c l o s e ( ) def add row to count dict ( res dict , variants ) : f o r var i n v a r i a n t s : i f not var i n r e s d i c t : r e s d i c t [ var ] = 1 else : r e s d i c t [ var ] += 1 return r e s d i c t

Het parent-process kan vervolgens de tellingen voor alle variants van alle subprocesses bij elkaar optellen, en met gebruik van de Python eval-functie alle variants die aan de count-filter voldoen, bepalen. Let wel, bij het opstellen van de uiteindelijke dictionary met de tellingen voor de varianten, moet het parent-process voor alle varianten in de starting set, een entry voorzien, met defaultwaarde 0. Zoniet zullen varianten waarvoor geen enkele sample aan de gt wildcard rule voldoet, niet in het resultaat voorkomen, en count-filters als (count < x), (count <= x) (voor arbitraire, positieve x) of (count == 0) die variants onterecht niet in hun resultaat weergeven. i f t a r g e t r u l e == ’ count ’ : r e s d i c t = {x : 0 f o r x i n c o r r e c t s t a r t i n g s e t } for s u b r e s u l t d i c t in r e s u l t s : f o r var , count i n s u b r e s u l t d i c t . i t e r i t e m s ( ) : r e s d i c t [ var ] += count i f invert count : t o t a l = l e n ( s e l f . names ) f o r v a r i a n t , count i n r e s d i c t . i t e r i t e m s ( ) : r e s d i c t [ v a r i a n t ] = t o t a l − count r e s = s e t ( [ v a r i a n t f o r v a r i a n t , count i n r e s d i c t . i t e r i t e m s ( ) \ i f e v a l ( s t r ( count ) + s e l f . count comp ) ] )

50

6.3. Implementatie: conclusie De correct starting set in bovenstaande code is de traditionele starting set, maar ge¨evalueerd in het geval dit de volledige verzameling variants (de wildcard "*") is, en gegoten in een datatype geschikt voor shared-memory access. De invert count-flag geeft aan of de gt wildcard rule een negatie is. Gezien Cassandra geen !=-clausules ondersteunt, moet GEMINI in dit geval het complement van de gt wildcard rule in kwestie bepalen en vervolgens de resulterende telling aftrekken van het totaal aantal samples. Een eenvoudig voorbeeld: bij het evalueren van volgende wildcard (gt type).(*).(!=HET).(count > 100) zal GEMINI eerst voor elke variant bepalen hoeveel samples w´el heterozygoot zijn, alvorens dit getal af te trekken van het totaal aantal samples en op dit resultaat de (count > 100)-filter toe te passen.

6.3

Implementatie: conclusie

De implementatie van het ontwerp beschreven in hoofdstuk 5 vergt vooral ingrijpende wijzigingen aan het queryingmechanisme van GEMINI: ons ontwerp analyseert queries at runtime, splitst WHERE-clausules en genotype-filters en -wildcards op in meerdere subqueries tegen de Cassandra databank, combineert de resultaten van die subqueries tot een coherent resultaat met behulp van set-arithmetiek en haalt vervolgens de gevraagde kolommen op uit de hoofdtabel in kwestie. De evaluatie van de subqueries en het ophalen van het finale resultaat kunnen in parallel gebeuren op meerdere processoren om het gehele proces sneller te laten verlopen. Aan het mechanisme om genoominformatie in te laden in GEMINI verandert er minder. Ook die taak kan dankzij Cassandra eenvoudig geparalleliseerd worden, door meerdere processoren los van elkaar een disjunct deel van de data in te laten laden, rechtstreeks in dezelfde Cassandra databank.

51

Hoofdstuk 7

Evaluatie 7.1

Functionele vereisten: testing

Onze implementatie van GEMINI in combinatie met Cassandra ondersteunt de belangrijkste features van GEMINI (zie 3), op een paar uitzonderingen na: • Inladen genoominformatie: GEMINI met Cassandra ondersteunt dezelfde input (i.e. VCF-, PED-, en annotatiefiles) als GEMINI met SQLite. Enkel door de gebruiker zelf gedefinieerde annotatiebestanden zijn nog niet ondersteund, maar dit is perfect analoog met de voorgedefinieerde bestanden en werd slechts uit tijdgebrek niet ge¨ımplementeerd. • Querying van genoominformatie: GEMINI met Cassandra behoudt de queryfunctionaliteit van de SQLite-implementatie, inclusief de uitgebreide SQLsyntax zoals genotype-filters en -wildcards en sample-wildcards. De enige soort queries die onze implementatie niet ondersteunt, zijn pure range queries. Dit kan ook opgelost worden met een workaround in de client-code (zie 5.2.2), die wij echter niet ge¨ımplementeerd hebben. • Voorts biedt GEMINI nog vele andere tools voor zeer specifieke genetische onderzoeksdoeleinden. We hebben die niet nader bestudeerd, maar gezien ze allen voortbouwen op de queryfunctionaliteit, hebben we de basis er wel voor gelegd. Dankzij de uitgebreide verzameling unit-tests van GEMINI hebben we de laaden queryfunctionaliteiten ook grondig kunnen testen en het correct functioneren van onze implementatie kunnen bewijzen. We hebben hiervoor 82 unit-tests uit de standaard meegeleverde unit-tests van GEMINI gebruikt, die onze implementatie allemaal doorstaat. Daarnaast hebben we de standaard unit-tests voor queries met genotype-wildcards nog herhaald met meerdere cores, om specifiek het parallellisatiemechanisme van onze implementatie te testen. Ook deze tests waren allemaal succesvol. 53

7. Evaluatie

7.2

Niet-functionele vereisten: benchmarking

Gezien onze implementatie de gewenste functionaliteit biedt, rest nog de vraag of ze ook, zoals beoogd, beter schaalt naar grote genoomdatasets. Om dit te evalueren hebben we onze versie van GEMINI onderworpen aan een reeks benchmarkingtests en vervolgens de executietijd van zowel het inladen als doorzoeken van genoominformatie met GEMINI gemeten. Ter vergelijking hebben we ook de prestaties van de SQLiteversie van GEMINI gemeten voor dezelfde tests.

Testomgeving Voor de experimenten gebruikten we, in samenspraak met de domeinexperten van Janssen Pharmaceutica, de publiek beschikbare genoomdata van het 1000 Genome project [16]. Die datasets bevatten enkel de VCF-files, niet de sample-informatie van de proefpersonen. Om toch de hele featureset te kunnen testen, hebben we willekeurig een geslacht en fenotype aan de samples toegekend. Specifiek hebben we 4 verschillende VCF-files (in reeds gezipte toestand, vandaar de bestandsextensie) gebruikt: • s 1092.vcf.gz van 1.8 GB met 494328 variants van 1092 samples. • m 1092.vcf.gz van 3.0 GB met 855166 variants van 1092 samples. • l 1092.vcf.gz van 6.7 GB met 1882663 variants van 1092 samples. • s 2504.vcf.gz van 1.2 GB met 7081600 variants van 2504 samples. De experimenten hebben we uitgevoerd op de cluster van het lab, bestaande uit nodes met elk 2 Intel X5660-processoren (6 cores, 12 (hyper)threads, dus 12 cores en 24 threads per node), 96 GB RAM en 500 GB schijfruimte. GEMINI met SQLite draaide steeds in zijn geheel op 1 zo’n node, GEMINI met Cassandra hebben we afhankelijk van experiment tot experiment op 1 of 2 nodes uitgevoerd, met daarnaast een Cassandra-cluster die draaide op 3 tot 10 nodes, weer afhankelijk van het experiment.

Structuur In de volgende paragraaf zullen we ´e´en voor ´e´en de experimenten en hun resultaten bespreken, te beginnen met de performantietesten van het inladen van gegevens, vervolgens de queries en ten slotte een meting van de impact van de duplicatie in ons dataschema. We zullen daarbij deze structuur hanteren: 1. Opzet van het experiment. Wat meet het experiment precies? 2. Omstandigheden: precieze input, commando, gebruikte infrastructuur. 3. Resultaten 4. Bespreking 54

7.2. Niet-functionele vereisten: benchmarking

7.2.1

Experiment 1: gemini load met Cassandra vs. SQLite

Opzet Het doel van dit experiment is te meten hoe snel GEMINI genoomdata kan inladen in een Cassandra-databank, en dit te vergelijken met de originele SQLite-versie van GEMINI. Van de SQLite-versie hebben we de totale tijd gemeten, evenals de tijd die GEMINI nodig heeft om de rijen in te laden in de aparte chunk-databases en de tijdsduur van het merge-proces hierna. Van onze implementatie hebben we de ook de totale tijdsduur gemeten, en bovendien elke thread per batch van 50 variants laten loggen hoe lang het invoeren van zo’n batch duurde, om een beter zicht te krijgen op de throughput. Bovendien hebben we voor onze implementatie gemeten hoe lang specifiek het invoeren van de variants in de variants-tabel duurt, maar ook hoe lang het invoeren van de genotype-data in de genotype-hulptabellen (dit zijn er 4) duurt. Omstandigheden We hebben de genoomdata uit de s 1092, m 1092 en l 1092-files ingeladen in een Cassandra-cluster met 10 nodes en replicatiefactor 3. GEMINI met Cassandra maakte gebruik van 24 threads, verdeeld over 2 nodes. GEMINI met SQLite draaide op 24 threads, op ´e´en node. Resultaten Cassandra

SQLite

Dataset

Throughput [variants/s]

Throughput [variants/s]

s m l s

23.71 ± 1.75 23.88 ± 1.78 22.83 ± 1.92 N.v.t. (timeout)

165.20 ± 1.15 223.57 ± 4.35 211.53 ± 1.50 174.83 ± 0.51

1092 1092 1092 2504

Tabel 7.1: Vergelijking van de throughput bij het laden tussen Cassandra en SQLite, voor verschillende genoomdatasets. De Cassandra-implementatie is gemiddeld ongeveer 10x trager.

55

7. Evaluatie Cassandra (per batch van 50 variants) Dataset

INSERT variants [s]

INSERT genotypes [s]

Tot. duur batch [s]

s m l s

2.06 ± 1.19 2.22 ± 0.61 2.44 ± 1.26 N.v.t. (timeout)

45.23 ± 4.10 45.70 ± 3.80 46.95 ± 4.46 N.v.t. (timeout)

50.91 ± 4.36 51.55 ± 3.83 52.92 ± 4.55 N.v.t. (timeout)

1092 1092 1092 2504

Tabel 7.2: Meetresultaten voor de duur van het inladen van genoomdata in Cassandra bij variabele grootte van de genoomdataset. De gemeten tijden zijn gemiddeldes over 24 threads.

SQLite Dataset

Chunks laden [s]

Chunks mergen [s]

Totaal [s]

Equiv. batch [s]

s m l s

2440.47 ± 7.46 2945.62 ± 44.90 6879.86 ± 40.39 33171.10 ± 31.61

551.95 ± 18.44 880.89 ± 34.47 2021.01 ± 35.17 7333.99 ± 83.69

2992.41 ± 20.92 3826.51 ± 76.88 8900.86 ± 63.32 40505.9 ± 118.30

7.26 5.37 5.67 6.86

1092 1092 1092 2504

Tabel 7.3: Meetresultaten voor de runtime van het inladen van genoomdata in SQLite bij variabele grootte van de genoomdataset. De vierde kolom is de gemiddelde tijd die ´e´en thread (v.d. 24) nodig heeft om 50 variants in te voeren, equivalent met de totale duur voor een batch zoals in tabel 7.2.

Bespreking Het inladen van de genoomdata verloopt in de orde van 10x sneller in de originele versie van GEMINI dan de Cassandra-versie. Dit is voornamelijk te wijten aan twee factoren: ten eerste moet GEMINI met Cassandra gigantische veel rijen invoeren dankzij het nieuwe datamodel. De hulptabellen met gegevens over de genotypes van elke sample per variant hebben #variants ∗ #samples rijen, wat zelfs voor de kleinste dataset al oploopt tot om en bij de 500 miljoen rijen. Uit de metingen in tabel 7.2 blijkt ook duidelijk dat het vullen van deze tabellen het meeste tijd in beslag neemt: zo’n 90% van het totale laadproces. Met de bedenking erbij dat voor elke 50 variants, 4 ∗ 50 ∗ 1092 rijen worden ingevoerd, en dit door 24 threads tegelijkertijd, haalt onze implementatie in deze setup voor deze hulptabellen een schrijfthroughput van in de orde van 100000 writes/s. Bovendien varieert de throughput nauwelijks met toenemende grootte (in variants) van de ingevoerde dataset. Ten tweede draait de SQLite-versie volledig lokaal op ´e´en node, en loopt dus geen vertraging op door netwerkcommunicatie. De metingen van het inladen in SQLite (tabel 7.3) tonen dat het merge-proces een niet verwaarloosbare fractie van het totale proces in beslag neemt. Onze implementa56

7.2. Niet-functionele vereisten: benchmarking tie in Cassandra kan deze stap volledig overslaan, maar zoals hierboven beschreven, weegt dit voordeel niet door in de eindafrekening tussen SQLite en Cassandra. De laatste kolom in tabel 7.3 is de gemiddelde tijd die ´e´en GEMINI-thread erover deed om 50 variants in SQLite in te voeren. Dit is equivalent met de totale duur van een batch in Cassandra in tabel 7.2, en duurt in SQLite ongeveer 10x minder lang. Een belangrijke bemerking bij de snelheid van het inladen is dat het datamodel van onze implementatie, in tegenstelling tot de SQLite-implementatie, uitbreidbaar is: het is niet nodig elke keer extra genoomdata beschikbaar is, de volledige dataset opnieuw in te laden. Hoewel onze implementatie trager is, zou dit een eenmalige kost moeten zijn. Het inladen in Cassandra verliep tijdens de experimenten niet zonder horten of stoten: af en toe traden timeouts op in de INSERT-queries, die altijd opgevangen konden worden door dezelfde query opnieuw te proberen (desnoods meerdere keren). Er zijn twee uitzonderingen die niet zomaar hersteld konden worden. Ten eerste het invoeren van zeer lange (strings van 10000’en of 100000’en karakters) genotypes in de variants by samples gts-tabel en ten tweede het invoeren van variants uit de s 2504-dataset in de variants-tabel. Van de eerste soort komen er exact 5549 voor in de s 1092-dataset (op ongeveer 500 miljoen genotypes van samples), 3233 in de m 1092-dataset (op meer dan 900 miljoen genotypes) en 14902 in de l 1092-dataset (op 2 miljard genotypes), die steevast voor een error bij het inladen zorgen. Fouten van de tweede soort, in de dataset met 2504 samples, traden op omwille van de zeer lange INSERT-queries, met kolommen voor de verschillende genotypeeigenschappen van elke sample. Dit impliceert een sterke beperking op het aantal samples in de dataset. Wij hebben dit niet verder onderzocht, maar geloven dat hier zeker oplossingen voor te vinden zijn in toekomstig onderzoek. De SQLiteimplementatie voerde de s 2504-dataset probleemloos in.

7.2.2

Experiment 2: Schaalbaarheid gemini load met grootte Cassandra-cluster

Opzet Dit experiment bestudeert de invloed van de grootte van het Cassandra-cluster op de duur van het inladen van genoomdata. We hebben wederom de duur van het inladen van elke batch van 50 variants gemeten, met daarin nog een opsplitsing tussen de tijd nodig voor het invoeren van de variants in de variants-tabel en het invoeren van samplegenotypes in 4 hulptabellen van de variants-tabel. Omstandigheden We hebben de performantie gemeten voor de s 1092-dataset, in Cassandra-clusters van 5, 7, 10 en 12 nodes. GEMINI draaide op 24 threads verspreid over 2 nodes.

57

7. Evaluatie Resultaten # Nodes

INSERT variants [s]

INSERT genotypes [s]

Throughput [vars/s]

5 7 10 12

2.44 ± 1.38 1.98 ± 1.12 2.06 ± 1.19 2.29 ± 1.29

54.54 ± 4.51 49.30 ± 3.77 45.23 ± 4.10 44.26 ± 4.32

19.93 ± 1.46 21.97 ± 1.55 23.71 ± 1.75 24.08 ± 1.85

Tabel 7.4: Meetresultaten voor de duur van het inladen van genoomdata in Cassandra bij variabele grootte van de Cassandra-cluster. De gemeten tijden zijn de waarden voor ´e´en batch van 50 variants, gemiddeld over 24 threads; de throughput is voor alle 24 threads opgeteld.

Bespreking De totale throughput stijgt merkbaar bij toenemende grootte van de cluster. Dit laat zich vooral merken bij het invoegen van de genotypes van de samples: gezien dit per batch veel meer writes inhoudt (1092x meer) dan het invoeren van de variants in de variants-tabel, laat het effect zich hier meer voelen. Bij stijging van 10 naar 12 nodes treedt er verzadiging op en stijgt de throughput niet meer zo drastisch als bij de overstap van 5 naar 7 of van 7 naar 10 nodes. Bij 10 nodes is de totale schrijfbandbreedte al voldoende groot en ligt de bottleneck weer bij GEMINI, eerder dan bij Cassandra.

7.2.3

Experiment 3: gemini query met Cassandra vs. SQLite

Opzet Het doel van dit experiment is de executietijd van verschillende relevante queries in GEMINI te vergelijken van de Cassandra- en SQLite-implementaties. Daarvoor hebben we 7 queries geselecteerd die de volledige queryingfunctionaliteit van GEMINI bestrijken en bovendien representatief zijn voor de queries die biologen in GEMINI uitvoeren. De gebruikte queries zijn gebaseerd op de documentatie van GEMINI en hun relevantie is afgetoetst bij onze contactpersoon bij Janssen Pharmaceutica. Omstandigheden We hebben de runtime van onderstaande 8 queries gemeten op de s 1092.vcf-dataset op een Cassandra-cluster van 9 nodes met replicatiefactor 3 en van queries 1, 4 en 8 op de m 1092.vcf-dataset op een Cassandra-cluster van 10 nodes met replicatiefactor 3. Ter vergelijking voerden we dezelfde queries ook uit met de SQLite-versie van GEMINI. Onze implementatie van GEMINI hebben we alle 24 beschikbare threads op ´e´en node laten gebruiken. De SQLite-versie van GEMINI biedt geen opties om queries parallel of op een andere manier sneller te laten verlopen, dit is dus snelste 58

7.2. Niet-functionele vereisten: benchmarking configuratie. Voor de Cassandra-versie van GEMINI hebben we zowel gemeten hoe lang het uitvoeren van de subqueries als het totale proces duurt, voor de SQLite-versie enkel de totale duur. 1. Query 1 Deze query dient om de performantie van eenvoudige queries op de kolommen van een tabel zoals de variants-tabel te meten. g e m i n i query −q ”SELECT chrom , s t a r t , end , p i FROM v a r i a n t s \ WHERE = ’ t s ’ \ and c a l l r a t e >= 0 . 9 5 ”

2. Query 2 Deze query dient ook om de performantie van eenvoudige queries op de kolommen van de variants-tabel te meten. g e m i n i query −q ”SELECT chrom , s t a r t FROM v a r i a n t s \ WHERE chrom = ’ chr22 ’ and s t a r t > 16000000 \ and s t a r t <= 18000000 ”

3. Query 3 Deze query dient om de performantie van een eenvoudige genotypefilter te meten, met de disjuncte combinatie van voorwaarden op het genotype van 2 proefpersonen. g e m i n i query −q ”SELECT chrom , s t a r t , end , r e f , a l t , gene FROM v a r i a n t s ” \ −−gt− f i l t e r ” g t t y p e s . HG00239 == HET | | g t t y p e s . NA19377 == HOM REF”

4. Query 4 Deze query dient om de performantie van een eenvoudige genotypefilter te meten, met de conjuncte combinatie van voorwaarden op het genotype van 2 proefpersonen. g e m i n i query −q ”SELECT chrom , s t a r t , end , r e f , a l t , gene FROM v a r i a n t s ” \ −−gt− f i l t e r ” g t t y p e s . HG00239 == HET && g t t y p e s . NA19377 == HOM REF”

5. Query 5 Deze query dient om de performantie van een eenvoudige genotypefilter te meten, met de negatie van een voorwaarde op het genotype van 1 sample. g e m i n i query −q ”SELECT chrom , s t a r t , end , r e f , a l t , gene FROM v a r i a n t s ” \ −−gt− f i l t e r ” g t t y p e s . HG00239 != HET”

6. Query 6 Deze query dient om de performantie van een eenvoudige genotypewildcard te meten, die alle variants zoekt waarvoor alle geaffecteerde (fenotype = 2) samples niet homozygoot voor het referentie-allel zijn. g e m i n i query −q ”SELECT chrom , s t a r t , end , r e f , a l t , gene FROM v a r i a n t s ” \ −−gt− f i l t e r ” [ g t t y p e s ] . [ phenotype = = ’ 2 ’ ] . [ ! = HOM REF ] . [ a l l ] ”

7. Query 7 Deze query dient om de performantie van een combinatie van genotypewildcards te meten, die alle variants zoekt waarvoor alle geaffecteerde (fenotype = 2) samples wel homozygoot voor het referentie-allel zijn en bovendien de depth van de variant call voldoende hoog is. 59

7. Evaluatie g e m i n i query −q ”SELECT chrom , s t a r t , end , r e f , a l t , gene FROM v a r i a n t s ” \ −−gt− f i l t e r ” [ g t t y p e s ] . [ phenotype == ’2 ’].[== HOM REF ] . [ a l l ] && \ [ g t d e p t h s ] . [ phenotype = = ’ 2 ’ ] . [ > = 2 0 ] . [ a l l ] ”

8. Query 8 Deze query dient om de performantie van een combinatie van genotypewildcards te meten, die alle variants zoekt waarvoor alle geaffecteerde (fenotype = 2) samples niet homozygoot voor het referentie-allel zijn en bovendien de depth van de variant call voor maximum 9 samples lager dan 20 is. Het is een minder restricitieve versie van query 7. g e m i n i query −q ”SELECT chrom , s t a r t , end , r e f , a l t , gene FROM v a r i a n t s ” \ −−gt− f i l t e r ” [ g t d e p t h s ] . [ phenotype = = ’ 2 ’ ] . [ < 1 0 ] . [ count <= 2 0 ] && \ [ g t t y p e s ] . [ phenotype = = ’ 2 ’ ] . [ ! = HOM REF ] . [ a l l ] ”

Resultaten Cassandra Query Query Query Query Query Query Query Query

1 2 3 4 5 6 7 8

SQLite

# Resultaten

Subqueries [s]

Totaal [s]

Totaal [s]

339819 15588 447392 15218 463148 1802 0 5

6.34 ± 0.13 1.62 ± 0.38 8.75 ± 0.07 8.74 ± 0.10 1.90 ± 0.06 219.63 ± 4.24 109.67 ± 1.12 353.30 ± 1.68

443.46 ± 6.85 40.37 ± 2.40 573.85 ± 3.78 43.19 ± 1.20 593.12 ± 5.09 237.22 ± 4.55 109.67 ± 1.12 367.29 ± 2.08

148.4 ± 1.06 2.53 ± 0.02 8428.81 ± 30.31 8412.17 ± 36.02 8405.53 ± 29.26 8404.66 ± 24.28 8513.17 ± 132.52 8448.35 ± 19.25

Tabel 7.5: Meetresultaten voor de executietijd van queries op de s 1092-dataset in Cassandra en SQLite.

Cassandra Query 1 Query 4 Query 8

SQLite

# Resultaten

Subqueries [s]

Totaal [s]

Totaal [s]

579823 26964 3

22.12 ± 0.54 26.32 ± 0.22 1276.65 ± 13.88

742.11 ± 6.25 88.60 ± 1.71 1305.21 ± 11.29

252.40 ± 2.19 14553.05 ± 73.92 14611.31 ± 71.27

Tabel 7.6: Meetresultaten voor de executietijd van queries op de m 1092-dataset in Cassandra en SQLite.

Bespreking Uit het resultaat voor query 1 en 2 blijkt dat GEMINI met Cassandra voor eenvoudige queries op de variants-tabel het grootste deel van de totale executietijd besteed 60

7.2. Niet-functionele vereisten: benchmarking aan het ophalen van het finale resultaat. GEMINI met SQLite moet hiervoor niet over het netwerk communiceren en is duidelijk sneller. Queries 3, 4 en 5 tonen dat de evaluatie van genotype-filters in GEMINI met Cassandra grootteordes sneller verloopt dan met SQLite: ongeacht de grootte van het resultaat zal SQLite ´e´en voor ´e´en alle variants overlopen, de binaire genotypekolommen decomprimeren en de filter als een Python-eval-statement evalueren. GEMINI met Cassandra komt ervan af met een beperkt aantal (gelijk aan het aantal clausules in de filter) subqueries die elk slechts een subset van het totale variants teruggeven, en moet enkel de resultaten hiervan nog combineren. De totale kost hangt hier duidelijk samen met de kardinaliteit van het resultaat, waar die in het SQLite afhangt van het totale aantal variants. Queries 6, 7 en 8 tonen dat ook de evaluatie van genotype wildcards significant sneller verloopt met een Cassandra-database dan met een SQLite-database. Het evalueren van de subqueries duurt bij deze queries duidelijk langer dan in de eenvoudige genotype-filters van queries 4 & 5, maar het zijn er dan ook beduidend meer. Er zijn 566 samples met fenotype 2, wat betekent dat elke wildcard zich vertaalt naar 566 subqueries. Het verschil in uitvoeringstijd tussen query 7 en 8 kan verklaard worden door de kardinaliteit van het resultaat van het linkerlid van de respectievelijke conjuncties: het linkerlid van query 7 geeft 0 variants terug, waardoor de evaluatie van het rechterlid overgeslagen kan worden. Het linkerlid van query 8 levert daarentegen een niet-ledige verzameling van variants op, waardoor het rechterlid wel ge¨evalueerd dient te worden. Dit kost opnieuw 566 subqueries. Voor de grotere m 1092-dataset tekent zich een gelijkaardig scenario af: bij query 1 is onze implementatie trager dan GEMINI met SQLite, en besteedt onze versie veruit de meeste tijd aan het ophalen van de finale resultaten. Bij query 4 is er in dit geval zelfs een speedup van 150x waar te nemen tegenover SQLite, bij query 8 ondanks de complexe wildcard-evaluatie nog steeds een speedup van meer dan 10x.

7.2.4

Experiment 4: Schaalbaarheid gemini query bij parallellisatie GEMINI

Opzet Het doel van dit experiment is te onderzoeken of de querysnelheid meeschaalt wanneer GEMINI geparallelliseerd wordt over meerdere threads. We bestuderen het effect van parallellisatie bij zowel het ophalen van het finale resultaat van queries als bij het evalueren van subqueries van genotype-wildcards. Omstandigheden Voor dit experiment hebben we query 1 en 8 uit experiment 3 (7.2.3) hergebruikt: query 1 omwille van de grootte van het resultaat, query 8 omwille van de duur van de evaluatie van de genotype wildcard. We hebben de uitvoeringstijd voor de twee queries gemeten bij uitvoering van GEMINI met 4, 8, 12, 16 en 24 threads. De 61

7. Evaluatie Cassandra-cluster, met de s 1092-dataset, bestond uit 9 nodes, met replicatiefactor 3. Resultaten Query 1

Query 8

# Threads

Subqueries [s]

Totaal [s]

Subqueries [s]

Totaal [s]

4 8 12 16 24

6.32 ± 0.07 6.22 ± 0.05 6.21 ± 0.09 6.25 ± 0.07 6.34 ± 0.13

1850.51 ± 60.21 949.67 ± 1.95 679.06 ± 3.37 562.33 ± 6.50 443.46 ± 6.85

1298.77 ± 8.52 699.02 ± 1.46 544.42 ± 2.09 440.64 ± 0.83 353.30 ± 1.68

1313.82 ± 9.00 713.44 ± 1.63 558.84 ± 2.61 454.98 ± 1.03 367.29 ± 2.08

Tabel 7.7: Meetresultaten voor de executietijd van GEMINI-queries in een Cassandra-databank, voor een variabel aantal gebruikte threads.

Bespreking Uit de resultaten voor query 1 blijkt dat de runtime van eenvoudige queries met een resultaat met hoge kardinaliteit lineair afneemt met het aantal gebruikte threads. Gezien de evaluatie van de subqueries (in dit geval slechts 1) niet geparallelliseerd wordt, is er hierin weinig verschil te merken. Het verschil in de totale executietijd is dus volledig toe te schrijven aan verhoogde doorvoer bij het opvragen van de resultaten. Bij query 8 is er een gelijkaardige duidelijke daling van de executietijd merkbaar. Het valt niet eenduidig te zeggen in welke mate dit toe te schrijven is aan een verhoogde leesdoorvoer, dan wel aan parallellisatie van de vele set-operaties die nodig zijn om de resultaten van de subqueries te parallelliseren. Vermoedelijk spelen beide een rol.

7.2.5

Experiment 5: Schaalbaarheid gemini query met grootte Cassandra-cluster

Opzet In dit experiment willen we onderzoeken hoe de grootte van de gebruikte Cassandracluster de performantie van queries be¨ınvloedt. We verwachten een hogere leesthroughput en daardoor een positief effect op zowel het ophalen van het finale resultaat als bij het concurrent evalueren van meerdere subqueries. Omstandigheden Voor dit experiment hebben we query 1 en 8 uit experiment 3 (7.2.3) hergebruikt: query 1 omwille van de grootte van het finale resultaat, query 8 omwille van de vele subqueries die in parallel ge¨evalueerd worden. We meetten de executietijd bij 62

7.2. Niet-functionele vereisten: benchmarking het doorzoeken van de s-dataset in een Cassandra-cluster van 5, 7, 9 en 11 nodes. GEMINI benutte in dit experiment 24 threads. Resultaten Query 1

Query 8

# Nodes

Subqueries [s]

Totaal [s]

Subqueries [s]

Totaal [s]

5 7 9 11

6.22 ± 0.39 6.19 ± 0.09 6.34 ± 0.13 6.43 ± 0.07

549.01 ± 6.03 484.47 ± 11.67 443.46 ± 6.85 363.32 ± 5.83

531.97 ± 3.04 513.28 ± 1.08 353.30 ± 1.68 373.85 ± 0.91

547.30 ± 3.19 527.26 ± 1.27 367.29 ± 2.08 388.49 ± 0.96

Tabel 7.8: Meetresultaten voor de executietijd van GEMINI-queries voor variabele grootte van de Cassandra-cluster.

Bespreking Voor query 1 is er een duidelijke daling van de queryduur merkbaar. Gezien de grootte van het resultaat van query 1 heeft die alle baat bij een verhoogde leesthroughput: de duur van het evalueren van de query evolueert niet met de grootte van de cluster, de duur van het ophalen van de finale 339819 rijen wel. Query 8 verloopt ook sneller bij toenemend aantal nodes in de cluster, maar het effect is niet zo drastisch als bij query 1. Van 9 naar 11 nodes is er zelfs een stijging merkbaar. De minder uitgesproken stijging van de snelheid valt te verklaren door het lagere aantal (sub)queries dat gebeurt tijdens het evalueren van query 8 dan tijdens het ophalen van het resultaat van query 1. Query 8 voert 556 subqueries uit, terwijl query 1 per 50 rijen (van de 339819) een query zal uitvoeren. Dit bevestigt de hypothese dat de evaluatie van query 8 eerder CPU- dan I/O-bound is.

7.2.6

Experiment 6: Impact dataduplicatie

Opzet Het doel van dit experiment is de impact van de dataduplicatie in het dataschema van ons ontwerp te bestuderen. Daarvoor hebben we de gebruikte schijfgrootte van de Cassandra-databanken voor enkele genoomdatasets vergeleken met de grootte van de overeenkomstige SQLite-databanken. Omstandigheden We hebben de grootte van de Cassandra-databases per node vergeleken voor de s 1092-, m 1092 en l 1092-datasets. We gebruikten een Cassandra-cluster van 12 nodes met replicatiefactor 3. In onderstaande resultaten is de replicatiefactor weggerekend. 63

7. Evaluatie Resultaten Cassandra

SQLite

Dataset

# Variants

Per node [GB]

Totaal [GB]

Totaal [GB]

s 1092 m 1092 l 1092

494328 855166 1882663

3.88 ± 0.14 6.67 ± 0.25 14.92 ± 0.91

46.54 80.07 179.09

1.3 1.9 4.6

Tabel 7.9: Grootte in GB van de Cassandra- en SQLitedatabanken voor verschillende genoomdatasets. Replicatie is niet meegerekend voor de Cassandra-databases.

Bespreking De impact van de gegevensduplicatie in ons dataschema is duidelijk groot: vergeleken met de overeenkomstige SQLite-databanken, zijn de Cassandra-databanken vele malen groter, zelfs zonder replicatie in rekening te brengen. Wat ook meespeelt, is dat in SQLite alle genotype-gegevens in gecomprimeerd formaat bewaard worden, terwijl die in Cassandra gedecomprimeerd en bovendien meerdere keren (1 keer in de variants-tabel, 1 keer in de genotype-hulptabellen van de variants-tabel) opgeslagen worden. Er blijkt ook een lineair verband te zijn tussen de grootte van de Cassandra-databank en het aantal opgeslagen variants (bij constant aantal samples). Praktisch gezien is de hoge vereiste schijfruimte van onze implementatie geen onoverkomelijk probleem: schijfruimte is in 2015 goedkoop genoeg om gemakkelijk naar meerdere terabytes te schalen. De 500GB waarover elk van de nodes in de cluster van het lab beschikken, is naar hedendaagse normen - zeker voor een HPC-systeem - aan de lage kant. De nieuwe nodes die binnen afzienbare tijd aan de cluster toegevoegd zullen worden, beschikken bijvoorbeeld al over meerdere terabytes schijfopslag.

7.3

Evaluatie: conclusie

In dit hoofdstuk hebben we ons ontwerp voor een schaalbare genoomanalysetool op basis van GEMINI en Apache Cassandra getest en experimenteel gevalideerd. Met behulp van de unit-tests van de originele implementatie van GEMINI hebben we bewezen dat onze Cassandra-implementatie op een correcte wijze de belangrijkste features van GEMINI, namelijk het inladen van genoomdata en die met een verrijkte SQL-syntax doorzoeken, ondersteunt. Daarnaast hebben we ook de performantie van onze implementatie gemeten door ze aan een reeks benchmarks te onderwerpen en de resultaten hiervan te vergelijken met de prestaties van de SQLite-versie van GEMINI. Bij het inladen van genoomdata is de SQLite versie een grootteorde sneller dan onze implementatie, voornamelijk door de grote dataduplicatie in ons ontwerp. Dankzij 64

7.3. Evaluatie: conclusie de uitbreidbaarheid van ons ontwerp is dit echter een eenmalige kost. Uit onze experimenten blijkt ook dat de duplicatie van gegevens in ons dataschema en het ongecomprimeerd opslaan van de genotype-informatie ervoor zorgen dat onze implementatie ettelijke malen meer schijfruimte vereist dan de oorspronkelijke SQLite-implementatie. Het uitvoeren van eenvoudige SQL-queries verloopt ook sneller in de SQLite-implementatie, omdat deze niet over het netwerk moet communiceren om de resultaten op te halen. Complexere queries met beperkingen op de genotypes van samples verlopen echter 1 tot 2 grootteordes sneller in onze implementatie: waar GEMINI in SQLite alle variants ´e´en voor ´e´en moet overlopen, kan GEMINI met Cassandra met enkele specifieke subqueries de kandidaat-variants opvragen en ze met set-operaties combineren tot het juiste resultaat. We hebben ook de invloed van parallellisatie en de grootte van de gebruikte Cassandracluster op de performantie van onze implementatie onderzocht. Hieruit blijkt dat zowel het inladen als queryen van genoomdata baat heeft bij een groter Cassandracluster. Het queryen verloopt ook bijna lineair sneller naarmate meer threads worden gebruikt, zowel voor CPU- als I/O-intensieve queries.

65

Hoofdstuk 8

Future work Deze thesis biedt nog vele perspectieven voor verder onderzoek. Eerst en vooral is er nog werk om van onze implementatie van GEMINI met Cassandra een afgewerkt product te maken: enkele features uit de oorspronkelijke GEMINI met SQLite kunnen nog toegevoegd worden. De eerste prioriteit is hierbij het gebruiken van custom annotations. Daarnaast kan het querymechanisme van onze implementatie nog verfijnd worden: SQL-JOINs zijn nog niet ge¨ımplementeerd en het opstellen en parsen van queries gebeurt nu op een vrij eenvoudige manier, terwijl door het strategischer kiezen van de volgorde van subqueries wellicht nog veel aan performantie gewonnen kan worden. Het ultieme doel hierbij is een dynamische query-planner zoals vele RDBMs en sommige NoSQL-systemen die ook kennen. Bovendien moet het mogelijk zijn de GEMINI queries intelligenter te parsen en op te splitsen in subqueries zodat de originele syntax van GEMINI volledig hersteld kan worden. Een andere feature die ons ontwerp nog gebruiksvriendelijker zou maken, is een tool om automatisch nieuwe hulptabellen te defini¨eren en op te stellen. Zo kan de gebruiker zelf kiezen welke kolommen uit de basistabellen van GEMINI doorzocht kunnen worden. Een laatste verbetering zou het realiseren van een incrementeel uitbreidbare versie van GEMINI zijn: vanuit Janssen Pharmaceutica is de vraag groot naar een versie van GEMINI waarin nieuwe genoomdata ingeladen kan worden zonder de reeds aanwezige gegevens opnieuw mee in te moeten laden. Cassandra laat toe het dataschema te wijzigen en ons ontwerp staat hier dan ook open voor. Dit zou een waarlijke killer feature zijn die de tekortkomingen van onze implementatie op het gebied van inladen van genoomdata grotendeels zou kunnen compenseren. Dan rest er nog de vraag of andere systemen niet geschikter zijn voor deze toepassing dan Cassandra: tijdens ons onderzoek hebben we ondervonden dat het datamodel van Cassandra restrictief is op het gebied van queries. We hebben dit in onze implementatie grotendeels kunnen verhelpen door zelf een extra query-engine bovenop Cassandra te bouwen, maar andere systemen bieden deze functionaliteit al van begin af aan. Zo zou het interessant zijn dezelfde denkoefening nog eens te maken met het eerder besproken Cloudera Impala, dat veel uitgebreidere query67

8. Future work functionaliteit biedt. Ook het verder bewandelen van de PostgreSQL-piste, zoals de ontwikkelaars van GEMINI reeds kort gedaan hebben, lijkt interessant. Systemen als CitusDB [12] bouwen bijvoorbeeld een parallelle database bovenop PostgreSQL en bieden veel perspectieven voor schaalbare query-processing. Een laatste, specifiek op genoomanalyse gerichte, Big Data-systeem is de Google Genomics-API[33] die genoomanalyse-tools gebaseerd op Google’s data-analysetools aanbiedt als cloud-service. Een nadeel hieraan is dat farmaceutische bedrijven uit concurrentie- en security-overwegingen niet geneigd zullen zijn hun gegevens uit handen te geven, maar anderzijds biedt dit natuurlijk wel de van Google gekende schaalbaarheid en performantie op maat gemaakt voor de bio-informatica.

68

Hoofdstuk 9

Conclusie De kost om DNA te sequencen is de afgelopen 15 jaar drastisch gedaald, met een boom in de bioinformatica tot gevolg. Nu genomen van steeds meer organismen almaar sneller ontleed kunnen worden, stelt dit hoge eisen aan de technologische infrastructuur om al de hieruitvolgende genoomdata op te slaan en effici¨ent te verwerken. De belangrijkste bekommernissen zijn schaalbaarheid naar enorme datasets en snelle, interactieve analyse van diezelfde datasets. Om een gelijkaardige explosieve groei van datahoeveelheden op te vangen, hebben webbedrijven het afgelopen decennium de NoSQL- en NewSQL-datastores ge¨ıntroduceerd: gegevensopslagsystemen die elk in verschillende aspecten afwijken van het traditionele relationele databankmodel om beter te schalen naar grote datahoevelheden in de diverse toepassingsgebieden van webbedrijven. In dit eindwerk hebben we onderzocht hoe NoSQL- en NewSQL-technologie¨en van nut kunnen zijn in het genoomanalyseproces. We hebben eerst een vergelijkende studie van 6 verschillende NoSQL- en NewSQL-systemen uitgevoerd en voor elk van deze systemen ingeschat voor welk aspect van het genoomanalyseproces ze nuttig kunnen zijn. Sommige systemen, zoals Apache Cassandra, bleken geschikt voor de grootschalige opslag en analyse van reeds ontlede genomen, andere, zoals Cloudera Impala, voor uiterst gedetailleerde en performante analyse van kleinere datasets, en nog andere, zoals VoltDB, eerder voor de opslag en performante verwerking van snel veranderende data in de sequencing-pijplijn zelf. Deze kennis hebben we toegepast op de genoomanalysetool GEMINI: een softwareframework dat onderzoekers toelaat genoomdata van grote populaties proefpersonen in een SQLite-database in te laden, die met zeer uiteenlopende gegevens over het menselijk genoom te annoteren, en hier vervolgens uitgebreide queries in een verrijkte SQL-syntax op uit te voeren. Om GEMINI beter te laten schalen naar grotere datasets hebben wij een ontwerp voorgesteld met een onderliggende Apache Cassandra- i.p.v. SQLite-databank, met een aangepast, incrementeel uitbreidbaar dataschema en een querymechanisme in de applicatielaag om de oorspronkelijke functionaliteit van GEMINI te bewaren. We hebben dit ontwerp ook ge¨ımplementeerd, en experimenteel aangetoond dat het ten opzichte van de originele SQLite-versie van GEMINI veel gedupliceerde data 69

9. Conclusie bevat, daardoor ook tot 10x trager genoomdata inlaadt, maar voor queries op grote datasets vaak sneller is dan de originele versie. Voor complexe queries zoals die in onderzoek naar erfelijke ziektes bijvoorbeeld voorkomen, is onze implementatie zelfs consequent en tot 150x sneller dan de originele versie van GEMINI. Uit dit eindwerk kunnen we besluiten dat er zeker een punt te maken valt voor NoSQL- en NewSQL-technologie¨en in de genoomanalyse. Ons concreet ontwerp voor GEMINI met Cassandra biedt, ondanks enkele beperkingen, perspectieven, en naarmate de bioinformatica er in de nabije toekomst verder op vooruitgaat, zal de vraag naar gelijkaardige oplossingen enkel toenemen. Het laatste woord over dit onderwerp is dan ook nog bijlange niet gesproken.

70

Bijlagen

71

1

A survey on NoSQL and NewSQL datastores Brecht Gossel´e

Abstract—Advances in bioinformatics have driven down the cost of genome sequencing dramatically over the past years. This raises the question how to efficiently and flexibly handle and store the large amount of data this process generates. Similar developments in web technology have spawned numerous NoSQL and NewSQL datastores in the last decade, which offer robust, highly scalable distributed storage and flexible data modelling. This paper reviews 6 such datastores and compares them on characteristics relevant to high performance computing in general and bioinformatics more specifically.

I. I NTRODUCTION Scientific progress has caused the cost of genome sequencing to drop at an exponential rate over the past decade and a half, even outpacing Moore’s law since 2008 [28]. Because in all sorts of biological, medical and pharmaceutical research, more and more genomes are being sequenced, the amount of generated data increases rapidly. For instance, the whole genome sequencing pipeline of the Broad Institute [27], a reference in the field, generates in the order of 3 TB of intermediary data when sequencing a single human genome. Also, when sequenced with 50x mean coverage (denoting the average number of times a base has been read during the process [26]) a single human genome takes 50 GB to store in compressed format1 , so as this scales to genomes of millions of people and other organisms, storage and processing requirements become ever more demanding in terms of scalability, latency and concurrency. A logical evolution has been to tackle these problems with high performance computing systems. The Exascience Life Lab of imec, Intel, Janssen Pharmaceutica and 5 Flemish universities, actively researches the application of supercomputers for accelerating the processing of whole genome sequences [25] [24]. Increasing popularity of web services such as social networks has caused a similar explosion of data for web companies. To handle this so-called Big Data [32] in an adequate way, traditional relational DBMS no longer suffice. Therefore, large web companies such as Google and Amazon have developped new storage solutions that meet the demands for high and incremental scalability, low latency and high availability [1]. This has spawned many so called NoSQL (’Not only SQL’) databases, which loosen the rigid relational datamodel in favour of better scaling and easier distribution of the data. NoSQL datastores come in multiple flavours and can be divided in a few categories based on the datamodel they use: • Key-value stores: much like dictionaries and associative maps, these map unique keys to values. Values are uninterpreted byte arrays, and the only way to access them is 1 This information was gathered during conversations with researchers at the Exascience Life Lab

by their key. This means modeling relations and complex structures between data, rich querying and indexing is not possible [23] [22]. • Columnar stores: based on the datamodel pioneered by Google’s BigTable, these store data in ”a sparse, distributed, persistent multidimensional sorted map” [5]. In BigTable’s case this is a map of row key, column key and a timestamp. In this way, multiple versions of the data can be stored in chronological order. Because the system doesn’t interpret the data, relationships can’t be modeled. This is left to application logic [23]. • Document stores: these store data as key-value pairs encapsulated in documents. Values can be of a wide variety of types, such as nested documents, lists or scalar values. Attribute names can be dynamically specified at runtime and need not adhere to a fixed schema [4]. This is well suited for modelling complex data structures. Many document stores use the JSON-fileformat (or some derived form). In contrast to columnar stores, the values in documents are not opaque to the system and can thus be queried and indexed [23]. • Graph databases: as the name suggests, these originate from graph theory and use graphs as their data model. They are especially useful to manage highly interconnected data coming from sources such as social networks or location based services, replacing costly operations like recursive joins with efficient graph traversals [23]. The term NewSQL data stores is being used to classify a set of solutions that aim to combine the scalability, distribution and fault tolerance of NoSQL stores with the relational data model. Though they all use the relational model and supply SQL-querying capacities, NewSQL stores vary greatly under the hood, depending on the architecture they are built on [22]. This paper proceeds first by elaborating on the methodology used to select and compare the chosen databases and then by reviewing each of the six datastores in detail. II. M ETHODOLOGY Because of the enormous choice of NoSQL and NewSQL datastores, an exhaustive study wasn’t feasible. This survey reviews the most popular datastores in a few relevant categories, namely document stores, wide columnar stores and NewSQL stores. Key-value stores and graph databases were not taken into consideration, as their respective data models are not suited for the application at hand. A selection was then made based on similar criteria as in [22], following the ranking of DB-Engine Ranking [39] as an indicator of popularity.

Consistent hashing

Configurable

N1QL, memcached API, MapReduce

Multi-master, asynchronous replication Standard Unix & Windows FS’s Primary & secondary, B-tree

memcached

Hashing function Within cluster: strong; within multiple clusters: eventual Application can implement optimistic (using CAS) or pessimistic concurrency control Y

Proprietary language, dynamic queries with JS, rich API, MapReduce

Master-slave, asynchronous replication

Standard FS’s, 16MB document limit

Primary & secondary on every attribute, B-tree

Query optimizer, shard-keys to speed up distributed queries

Range partitioning based on shard key

Configurable

Atomic single document operations, otherwise 2-phase commit; Concurrent reads, exclusive writes (lock on DB level)

Y

Querying & API

Distributed

Storage

Indexing

Query optimization

Partitioning

Consistency

Concurrency control

Open-source?

Y

Single-row transactions (ACID possible), OCC with MVCC for wider scope operations

Strong

Range-partitioning

Bloom filter

Primary & secondary, LSM-tree

Y

Relies on underlying storage layer

Relies on underlying storage layer

By default not, but possible

Partition pruning using partition key

Primary & secondary

HDFS or HBase

Masterless

Master-slave or multi-master, asynchronous replication. HDFS

SQL-92, MapReduce

SQL on top of Hadoop

Cloudera Impala

No query language (Hive via workaround), Java API, MapReduce

Wide columnar store

HBase

Table 1: An overview of the compared datastores and their features

Y

Row-level atomicity, CAS

Bloom filter

Primary & secondary, LSM-tree

Cassandra File System (HDFS compatible)

Masterless, asynchronous replication

CQL, rich API, MapReduce

Wide columnar store

Document-store (JSON)

Document-store (BSON)

Type

Cassandra

CouchBase Server

MongoDB

Y

ACID + data access serialized and executed in single-threaded environment

Strong

Consistent hashing

Queries in stored procedures planned at compile time

Primary & secondary. Hash& tree-indexes

Main memory

Masterless, updates executed on all replicas at the same time.

SQL-92, Java stored procedures, rich API, MapReduce

In-memory relational NewSQL

VoltDB

3

This ranking tries to measure popularity based on a few parameters, such as the number of mentions on Web sites, general interest according to Google Trends, frequency of technical discussions on the Web, number of job listings, and number of professional profiles in which the systems are mentioned. The resulting selection consists of the document stores MongoDB and CouchBase Server, wide columnar stores Cassandra and HBase and NewSQL database VoltDB. There already exists an extension of the DNA sequencing pipeline used in the ExaScience Life Lab that allows for using MongoDB databases as input and/or output targets, making MongoDB even more relevant [8]. Lastly, NewSQL query engine Cloudera Impala was also taken into consideration because of explicit interest from researchers in the aforementioned lab. These 6 systems were then compared on characteristics relevant to high performance computing, such as indexing mechanisms, client interfaces to the data, distribution strategy, concurrency control and consistency models. III. D OCUMENT STORES A. MongoDB MongoDB stores data in BSON (binary JSON) documents. It has powerful indexing support, with the ability to define secondary indexes of a wide array of types on all attributes, much like in the traditional relational model. These are implemented using B-trees [34]. To aid with denormalization, the documents can contain embedded documents and arrays, thus obviating the need for joins in the query language. The document size is limited to 16 MB, to help ensure that a single document cannot take up excessive amounts of RAM or bandwidth. To store and retrieve larger files, the built-in tool GridFS (which is not an actual file system) can split up files in smaller chunks and store these chunks as separate documents [33]. MongoDB offers API’s in many languages and the functionality to define the equivalent of SQL WHEREclauses as javascript expressions. These are then translated to MongoDB’s proprietary internal querying language [22]. The MongoDB query optimizer processes queries and chooses the most efficient plan for a query given the available indexes. These plans are cached if there are multiple viable options and can be reevaluated as the data evolves [35]. The consistency of MongoDB is configurable. Strong consistency can be attained in two ways: setting the connection to read-only from the master node (which has the most up-to-date version of the data), or forcing a write to succeed only after all replicas have acknowledged it. The former degrades the scaling ability of read requests, the latter the latency of write requests [22]. Data is replicated asynchronously using range-partitioning: nodes are responsible for ranges of keys. This speeds up range queries, but can create hotspots and load-balancing issues. To route updates to the right replicas, MongoDB operates in a master-slave setting. For concurrency control, MongoDB offers single-document atomicity and implements reader-writer locks. Having to lock on writes severely impacts performance in write-intensive

scenarios. As a wrap-up, MongoDB stores BSON-files accessible through many API’s with flexible querying and indexing techniques, but its concurrency and consistency model have some drawbacks. B. CouchBase Server CouchBase, result of the merger of CouchDB and Membase, stores data in JSON documents. It uses the memcached protocol for distributed caching and is intended for highly interactive applications with low-latency requirements [22] [9]. The JSON documents can be nested and are queryable through a SQL-like language, N1QL (note: the most recent version at the time of writing, released in March 2014, is still a developer preview) [11]. Primary and secondary indexes can be defined on the data and are implemented using B-trees [10]. Within one cluster, transactions are strongly consistent, but between multiple clusters only eventually consistent. Couchbase lets clients choose between optimistic (using compare-and-swap) and pessimistic (using ’finegrained locking’) concurrency control. With its flexible data modelling, caching and concurrency control, Couchbase is a good fit for applications requiring fast and intensive interaction between client and data. IV. C OLUMNAR STORES A. Cassandra Apache Cassandra, originally developped at Facebook but later open-sourced, combines the data-model of Google’s BigTable system with the architecture and distribution strategy of Amazon’s DynamoDB. It is intended for flexible, highlyavailable storage of very large datasets, running on cheap commodity hardware and offering high write throughput while not sacrificing read efficiency [30]. Since its inception Cassandra has however diverged slightly from the BigTable data model. It now provides tables and composite columns -much like in a conventional schema, and comes with its own query language, CQL [31]. CQL resembles SQL in many ways, albeit with some restrictions. For instance, it doesn’t feature the JOIN clause [13]. It strongly encourages physically collocating data that will be queried together, and supports denormalization with features such as collection types. Cassandra has primary and secondary indexing mechanisms and implements these - like BigTable [5], using log-structured merge trees (or LSM trees). These allow for deferring updates and flushing them to disk in batches as soon as enough have accumulated, thus reducing disk I/O. This greatly benefits write throughput [37] [38] [30]. Cassandra, like BigTable, also offers Bloom filters [36]. These are an efficient probabilistic mechanism to predict whether an item is in a set (in this case, whether a key is in a table) and can thus significantly reduce unnecessary table scans [30].

4

In order to scale linearly in the number of nodes to very large datasets, Cassandra operates in a fully masterless fashion. In terms of the CAP-theorem, it focusses on availability and partition-tolerance, rather than immediate consistency (though the user has control over the level of consistency, as will be explained) [3]. High availability and partition tolerance are achieved through asynchronous replication of rows over several nodes in the cluster, using consistent hashing and virtual nodes to handle high churn and incremental addition of nodes [16] [30] [31]. The amount of replicas can be chosen by the client. Furthermore, Cassandra provides cross-datacenter replication to cope with entire datacenter failures. On reads and writes, the client can specify the desired quorum, that is the number of replicas that acknowledge the operation. Although Cassandra was built with eventual consistency in mind, strong consistency can be obtained by choosing the quorum larger than the number of replicas [22]. In terms of concurrency control, Cassandra supports atomicity for single-row operations and serializable lightweight transactions, essentially a compare-and-set functionality for larger operations [15]. Being an open-source project, Cassandra is freely available, but there is an enterprise version with extra features such as integration with the data processing engine Apache Spark and the distributed search platform Apache Solr, for complex analytical and search tasks [14] [12] [44] [19]. In conclusion, Cassandra offers flexible data-modeling with decent querying and indexing support through its CQLinterface and scales incrementally to vast datasets, thanks to its extensive replication and failure-handling features. B. HBase Apache HBase is an open source datastore using Google BigTable’s datamodel, but running on top of the Hadoop Distributed File System (HDFS) instead of the Google File System (GFS). Since its launch, HBase has adopted several secondary indexing mechanisms. For indexing, HBase also uses LSM trees [2] [38], and it also provides Bloom filters [21]. HBase comes with a Java API but without an SQL-like advanced querying language, though a workaround via Apache Hive, another data warehousing and analytics project [18], and its query language HiveQL is possible. Because of its HDFS underpinnings it can easily function as both input and output for MapReduce jobs. HBase partitions data in ranges like BigTable and replicates updates in master-slave or multi-master fashion. Read-requests are not distributed however, as rows are only serviced by one server. The replicas are intended solely for failure recovery. The strong points of HBase are its strong consistency, which is rare among NoSQL-stores, and its concurrency model: ACID-compliant single row transactions and optimistic multi-version concurrency control for wider scope operations [20] [22] [2]. In conclusion, HBase allows users to flexibly model

data and is especially useful when there is already a HDFS dataset and when MapReduce compatibility is a priority. It scales well to very large datasets and features excellent concurrency control and strong consistency. V. N EW SQL A. VoltDB VoltDB is a relational in-memory distributed database, aiming to couple the guarantees of classical SQL-stores with the scaling of NoSQL systems while performing at very high speeds [40]. VoltDB stores data in the traditional relational model, but replicated and partitioned (using consistent hashing) over several nodes [22]. The data is queryable through a (growing) subset of SQL-92 [43]. Queries are preferably defined as stored procedures written in Java, in which the SQL statements are embedded. VoltDB supports primary and secondary indexing, and gives the user the choice between hash- and tree-indexes [41]. VoltDB plans and optimizes queries in stored procedures optimized at compile time [42]. Relying entirely on DRAM makes it expensive to scale to petabyte scale datavolumes, but VoltDB can export data to other, more suited DMBSs such as columnar NoSQL stores. In terms of concurrency control, VoltDB supports full ACID-transactions which execute simultaneously on all replicas. Main memory is divided into chunks and these are statically assigned to individual, single-threaded cores. A global controller serializes all multi-node transactions to a sequence of single-node transactions and inserts those into the transactions queues of the respective nodes. In this way, VoltDB obviates the need for locking and latching techniques. In short, VoltDB provides relational in memory storage for relatively large datasets, with very fast SQL-query capacities and ACID transactions. It is thus more suited for compute intensive applications that don’t work on exorbitantly large data volumes but require very low latency. B. Cloudera Impala Cloudera Impala is a distributed SQL-engine running on top of the Hadoop stack, either on HDFS or HBase [29]. It is intended specifically for analytical use, focussing on delivering real-time querying capacities and not on high-throughput on writes. Data is accessible through a subset of SQL-92. Impala’s architecture is almost perfectly symmetrically distributed: all nodes execute the same impalad-process, which is responsible for the main database functionality. Queries can be sent to any node which will then function as coordinator for the specific query. There are however two processes that run on only one (not necessarily the same) node in the cluster, performing bookkeeping tasks and relaying metadata changes through the cluster [6]. Contrary to the options discussed before, Impala doesn’t partition rows by default. It does give the user the possibility to partition data should the data size call for it [7].

5

Impala has a highly efficient I/O-layer keeping disk- and CPUutilization high at all times, resulting in considerably faster performance than other SQL-on-Hadoop solutions such as Apache Hive [17]. However, this comes with the drawback that the working set of a query has to fit in the aggregate physical memory of the cluster it runs on. This puts some restrictions on the size of datasets processable with Impala, not fully using the scaling capacity of the underlying Hadoop layer. Because of its analytical purposes, Impala doesn’t have extensive concurrency control features, relying instead on the underlying storage layer. With HBase’s excellent concurrency control features, this doesn’t necessarily pose a problem. VI. C ONCLUSIONS In recent years, progress in microbiology and bioinformatics has driven down the cost of DNA-sequencing. As DNA of more and more organisms is being sequenced, the question arises to make this process ever more efficient and to store the generated data in a scalable, performant and accessible way. This study has focused on NoSQL and NewSQL datastores to be used in both the sequencing pipeline as in the storage and analysis of the results. These solutions offer elastic scalability, flexible data modelling, good behavior in a distributed setting and resilience to failures. Specifically, this paper has reviewed 6 different datastores, 2 of the most popular ones in three categories, and compared them on a selection of properties relevant to HPC applications. Columnar stores like Apache Cassandra and HBase are well suited to the task of storing extremely large datasets in a reliable and performant way, and could handle the storage of already sequenced genomes. MongoDB sets itself apart with its extensive API, flexible data modeling, querying and indexing features. It doesn’t have quite the write-handling capacities of the columnar stores, but is nevertheless a strong candidate for storing very large datasets such as the sequenced genomes. VoltDB and CouchBase Server offer low latency on reads and writes, albeit (especially VoltDB) on smaller datasets, but would thus be very useful for storing rapidly changing intermediate data in the sequencing pipeline. Lastly, Cloudera Impala lends itself well to situations where fast read, but not write queries on large datasets are required. R EFERENCES [1] Jason Baker, Chris Bond, James C Corbett, JJ Furman, Andrey Khorlin, James Larson, Jean-Michel L´eon, Yawei Li, Alexander Lloyd, and Vadim Yushprakh. Megastore: Providing scalable, highly available storage for interactive services. In CIDR, volume 11, pages 223–234, 2011. [2] Dhruba Borthakur, Jonathan Gray, Joydeep Sen Sarma, Kannan Muthukkaruppan, Nicolas Spiegelberg, Hairong Kuang, Karthik Ranganathan, Dmytro Molkov, Aravind Menon, Samuel Rash, et al. Apache hadoop goes realtime at facebook. In Proceedings of the 2011 ACM SIGMOD International Conference on Management of data, pages 1071–1080. ACM, 2011. [3] Eric A Brewer. Towards robust distributed systems. In PODC, page 7, 2000. [4] Rick Cattell. Scalable sql and nosql data stores. ACM SIGMOD Record, 39(4):12–27, 2011.

[5] Fay Chang, Jeffrey Dean, Sanjay Ghemawat, Wilson C Hsieh, Deborah A Wallach, Mike Burrows, Tushar Chandra, Andrew Fikes, and Robert E Gruber. Bigtable: A distributed storage system for structured data. ACM Transactions on Computer Systems (TOCS), 26(2):4, 2008. [6] Cloudera. Cloudera impala components. http://www.cloudera. com/content/cloudera/en/documentation/core/latest/topics/impala components.html. Accessed on 6/12/2014. [7] Cloudera. Cloudera impala partitioning. http://www.cloudera. com/content/cloudera/en/documentation/cloudera-impala/v1/latest/ Installing-and-Using-Impala/ciiu partitioning.html. Accessed on 03/12/2014. [8] Pascal Costanza. elprep-mongo. https://github.com/ExaScience/ elprep-mongo. Accessed on 25/11/2014. [9] Couchbase. About couchbase server. http://www.couchbase.com/ nosql-databases/about-couchbase-server. Accessed on 16/11/2014. [10] Couchbase. Couchbase compaction process. http://blog.couchbase.com/ compaction-magic-couchbase-server-20. Accessed on 26/11/2014. [11] Couchbase. Couchbase n1ql language reference. http://docs.couchbase. com/developer/n1ql-dp4/n1ql-intro.html. Accessed on 6/04/2014. [12] DataStax. Analyzing data using spark. http://www.datastax.com/ documentation/datastax enterprise/4.5/datastax enterprise/spark/ sparkTOC.html. Accessed on 15/11/2014. [13] DataStax. Cassandra query language (cql) v3.1.7. http://cassandra. apache.org/doc/cql3/CQL.html. Accessed on 15/11/2014. [14] DataStax. Getting started with solr in datastax enterprise. http://www.datastax.com/documentation/datastax enterprise/4.5/ datastax enterprise/srch/srchIntro.html. Accessed on 15/11/2014. [15] DataStax. Lightweight transactions. http://www.datastax.com/ documentation/cassandra/2.0/cassandra/dml/dml ltwt transaction c. html. Accessed on 15/11/2014. [16] Giuseppe DeCandia, Deniz Hastorun, Madan Jampani, Gunavardhan Kakulapati, Avinash Lakshman, Alex Pilchin, Swaminathan Sivasubramanian, Peter Vosshall, and Werner Vogels. Dynamo: amazon’s highly available key-value store. In ACM SIGOPS Operating Systems Review, volume 41, pages 205–220. ACM, 2007. [17] Avrilia Floratou, Umar Farooq Minhas, and Fatma Ozcan. Sql-onhadoop: Full circle back to shared-nothing database architectures. Proceedings of the VLDB Endowment, 7(12), 2014. [18] Apache Foundation. Apache hive. https://hive.apache.org/. Accessed on 06/12/2014. [19] Apache Foundation. Apache solr. http://lucene.apache.org/solr/. Accessed on 02/12/2014. [20] Apache Foundation. Hbase acid semantics. http://hbase.apache.org/ acid-semantics.html. Accessed on 15/11/2014. [21] Apache Foundation. Hbase schema design. http://hbase.apache.org/ book/perf.schema.html. Accessed on 26/11/2014. [22] Katarina Grolinger, Wilson A Higashino, Abhinav Tiwari, and Miriam AM Capretz. Data management in cloud environments: Nosql and newsql data stores. Journal of Cloud Computing: Advances, Systems and Applications, 2(1):22, 2013. [23] Robin Hecht and S Jablonski. Nosql evaluation. In International Conference on Cloud and Service Computing, 2011. [24] Charlotte Herzeel, Pascal Costanza, Wolfgang De Meuter, and Thomas J. Ashby. Resolving load balancing issues in bwa on numa multicore architectures. In Proceedings of the 10th International Conference on Parallel Processing and Applied Mathematics PPAM. Springer, 2013. [25] imec. Exascience life lab. http://www2.imec.be/be en/research/ life-sciences/exascience-life-lab.html. Accessed on 02/12/2014. [26] Broad Institute. Coverage. https://www.broadinstitute.org/crd/wiki/ index.php/Read coverage. Accessed on 05/12/2014. [27] Broad Institute. Human whole genome sequencing. http://www.broadinstitute.org/scientific-community/science/platforms/ genomics/human-whole-genome-sequencing. Accessed on 02/12/2014. [28] Wetterstrand KA. Dna sequencing costs: Data from the nhgri genome sequencing program (gsp). http://www.genome.gov/sequencingcosts/. Accessed on 19/11/2014. [29] Marcel Kornacker and Justin Erickson. Cloudera impala. http://blog.cloudera.com/blog/2012/10/ cloudera-impala-real-time-queries-in-apache-hadoop-for-real/. Accessed on 15/11/2014. [30] Avinash Lakshman and Prashant Malik. Cassandra: a decentralized structured storage system. ACM SIGOPS Operating Systems Review, 44(2):35–40, 2010. [31] Avinash Lakshman, Prashant Malik, and Jonathan Ellis. Facebook’s cassandra paper, annotated and compared to apache cassandra 2.0. http://www.datastax.com/documentation/articles/cassandra/ cassandrathenandnow.html. Accessed on 15/11/2014.

6

[32] John R Mashey. Big data and the next wave of infrastress. In Computer Science Division Seminar, University of California, Berkeley, 1997. [33] MongoDB. Mongodb gridfs. http://docs.mongodb.org/manual/core/ gridfs/. Accessed on 6/12/2014. [34] MongoDB. Mongodb indexes. http://docs.mongodb.org/manual/core/ indexes-introduction/. Accessed on 15/11/2014. [35] MongoDB. Mongodb query plans. http://docs.mongodb.org/manual/ core/query-plans/. Accessed on 16/11/2014. [36] James K Mullin. A second look at bloom filters. Communications of the ACM, 26(8):570–571, 1983. [37] Patrick O’Neil, Edward Cheng, Dieter Gawlick, and Elizabeth O’Neil. The log-structured merge-tree (lsm-tree). Acta Informatica, 33(4):351– 385, 1996. [38] Russell Sears and Raghu Ramakrishnan. blsm: a general purpose log structured merge tree. In Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data, pages 217–228. ACM, 2012. [39] solid IT. Db-engine ranking. http://www.db-engines.com/en/ranking. Accessed on 15/11/2014. [40] Michael Stonebraker and Ariel Weisberg. The voltdb main memory dbms. IEEE Data Eng. Bull., 36(2):21–27, 2013. [41] VoltDB. Voltdb indexes. http://mockdocs.voltdb.com/UsingVoltDB/ ddlref createindex.php. Accessed on 8/12/2014. [42] VoltDB. Voltdb query plans. http://docs.voltdb.com/PerfGuide/ ChapExecPlans.php. Accessed on 8/12/2014. [43] VoltDB. Voltdb technical overview. Whitepaper, 2010. [44] Matei Zaharia, Mosharaf Chowdhury, Michael J Franklin, Scott Shenker, and Ion Stoica. Spark: cluster computing with working sets. In Proceedings of the 2nd USENIX conference on Hot topics in cloud computing, pages 10–10, 2010.

Schaalbare genoomanalyse https://github.com/bgossele/geminicassandra

B. Gosselé Prof. Dr. R. Wuyts

Exascience Life Lab

Bibliografie [1] B. Alberts, A. Johnson, J. Lewis, M. Raff, K. Roberts, P. Walter, et al. Molecular biology of the cell. Garland Science, New York, 5, 2007. [2] Anonymous. Chromosome clipart. http://www.clker.com/ clipart-single-chromosome-4.html, 2015. Accessed on 25/05/2015. [3] J. Baker, C. Bond, J. C. Corbett, J. Furman, A. Khorlin, J. Larson, J.-M. L´eon, Y. Li, A. Lloyd, and V. Yushprakh. Megastore: Providing scalable, highly available storage for interactive services. In CIDR, volume 11, pages 223–234, 2011. [4] L. A. Barroso, J. Dean, and U. Holzle. Web search for a planet: The google cluster architecture. Micro, Ieee, 23(2):22–28, 2003. [5] M. W. Blasgen, M. M. Astrahan, D. D. Chamberlin, J. Gray, W. King, B. G. Lindsay, R. A. Lorie, J. W. Mehl, T. G. Price, G. R. Putzolu, et al. System r: An architectural overview. IBM systems journal, 20(1):41–62, 1981. [6] D. Borthakur, J. Gray, J. S. Sarma, K. Muthukkaruppan, N. Spiegelberg, H. Kuang, K. Ranganathan, D. Molkov, A. Menon, S. Rash, et al. Apache hadoop goes realtime at facebook. In Proceedings of the 2011 ACM SIGMOD International Conference on Management of data, pages 1071–1080. ACM, 2011. [7] E. Brewer. Cap twelve years later: How the”rules”have changed. Computer, 45(2):23–29, 2012. [8]

E. A. Brewer. Towards robust distributed systems. In PODC, page 7, 2000.

[9] R. Cattell. Scalable sql and nosql data stores. ACM SIGMOD Record, 39(4):12– 27, 2011. [10] D. D. Chamberlin and R. F. Boyce. Sequel: A structured english query language. In Proceedings of the 1974 ACM SIGFIDET (now SIGMOD) workshop on Data description, access and control, pages 249–264. ACM, 1974. [11] F. Chang, J. Dean, S. Ghemawat, W. C. Hsieh, D. A. Wallach, M. Burrows, T. Chandra, A. Fikes, and R. E. Gruber. Bigtable: A distributed storage system for structured data. ACM Transactions on Computer Systems (TOCS), 26(2):4, 2008. 81

Bibliografie [12] CitusData. Citusdb. https://www.citusdata.com/. Accessed on 28/05/2015. [13] Cloudera. Cloudera impala components. http://www.cloudera.com/content/ cloudera/en/documentation/core/latest/topics/impala_components. html. Accessed on 6/12/2014. Cloudera impala partitioning. http://www.cloudera.com/ [14] Cloudera. content/cloudera/en/documentation/cloudera-impala/v1/latest/ Installing-and-Using-Impala/ciiu_partitioning.html. Accessed on 03/12/2014. [15] E. F. Codd. A relational model of data for large shared data banks. Communications of the ACM, 13(6):377–387, 1970. [16] . G. P. Consortium et al. An integrated map of genetic variation from 1,092 human genomes. Nature, 491(7422):56–65, 2012. [17] Couchbase. About couchbase server. http://www.couchbase.com/ nosql-databases/about-couchbase-server. Accessed on 16/11/2014. [18] Couchbase. Couchbase compaction process. http://blog.couchbase.com/ compaction-magic-couchbase-server-20. Accessed on 26/11/2014. [19] Couchbase. Couchbase n1ql language reference. http://docs.couchbase.com/ developer/n1ql-dp4/n1ql-intro.html. Accessed on 6/04/2014. [20] DataStax. Cassandra query language (cql) v3.1.7. http://cassandra.apache. org/doc/cql3/CQL.html. Accessed on 15/11/2014. Python cassandra driver. http://datastax.github.io/ [21] Datastax. python-driver/index.html, 2015. Accessed on 13/05/2015. [22] Datastax. When to use an index. http://docs.datastax.com/en/cql/3.0/ cql/ddl/ddl_when_use_index_c.html, 2015. Accessed on 02/04/2015. [23] G. DeCandia, D. Hastorun, M. Jampani, G. Kakulapati, A. Lakshman, A. Pilchin, S. Sivasubramanian, P. Vosshall, and W. Vogels. Dynamo: amazon’s highly available key-value store. In ACM SIGOPS Operating Systems Review, volume 41, pages 205–220. ACM, 2007. [24] N. Education. Scitable by nature education. scitable, 2015. Accessed on 14/05/2015.

http://www.nature.com/

[25] L. Eisenstadt. What is exome sequencing. http://www.broadinstitute.org/ blog/what-exome-sequencing, 2010. Accessed on 14/05/2015. [26] A. Floratou, U. F. Minhas, and F. Ozcan. Sql-on-hadoop: Full circle back to shared-nothing database architectures. Proceedings of the VLDB Endowment, 7(12), 2014. 82

Bibliografie [27] A. Foundation. 06/12/2014.

Apache hive.

https://hive.apache.org/.

Accessed on

[28] A. Foundation. Hbase acid semantics. http://hbase.apache.org/ acid-semantics.html. Accessed on 15/11/2014. [29] A. Foundation. Hbase schema design. http://hbase.apache.org/book/perf. schema.html. Accessed on 26/11/2014. [30] P. S. Foundation. multiprocessing - process-based threading interface. https: //docs.python.org/2/library/multiprocessing.html, 2015. Accessed on 15/04/2015. [31] Genome.gov. A brief guide to genomics. http://www.genome.gov/18016863, 2015. Accessed on 14/05/2015. [32] S. Ghemawat, H. Gobioff, and S.-T. Leung. The google file system. In ACM SIGOPS operating systems review, volume 37, pages 29–43. ACM, 2003. [33] Google. Google genomics. https://cloud.google.com/genomics/. Accessed on 28/05/2015. [34] K. Grolinger, W. A. Higashino, A. Tiwari, and M. A. Capretz. Data management in cloud environments: Nosql and newsql data stores. Journal of Cloud Computing: Advances, Systems and Applications, 2(1):22, 2013. [35] T. Haerder and A. Reuter. Principles of transaction-oriented database recovery. ACM Computing Surveys (CSUR), 15(4):287–317, 1983. [36] R. Hecht and S. Jablonski. Nosql evaluation. In International Conference on Cloud and Service Computing, 2011. [37] C. Herzeel, P. Costanza, W. De Meuter, and T. J. Ashby. Resolving load balancing issues in bwa on numa multicore architectures. In Proceedings of the 10th International Conference on Parallel Processing and Applied Mathematics PPAM. Springer, 2013. [38] imec. Exascience life lab. http://www2.imec.be/be_en/research/ life-sciences/exascience-life-lab.html. Accessed on 02/12/2014. [39] B. Institute. Coverage. https://www.broadinstitute.org/crd/wiki/index. php/Read_coverage. Accessed on 05/12/2014. [40] B. Institute. Human whole genome sequencing. http://www. broadinstitute.org/scientific-community/science/platforms/ genomics/human-whole-genome-sequencing. Accessed on 02/12/2014. [41] W. KA. Dna sequencing costs: Data from the nhgri genome sequencing program (gsp). http://www.genome.gov/sequencingcosts/. Accessed on 19/11/2014. 83

Bibliografie [42] M. Kornacker and J. Erickson. Cloudera impala. http://blog.cloudera.com/blog/2012/10/ cloudera-impala-real-time-queries-in-apache-hadoop-for-real/. Accessed on 15/11/2014. [43] A. Lakshman and P. Malik. Cassandra: a decentralized structured storage system. ACM SIGOPS Operating Systems Review, 44(2):35–40, 2010. [44] A. Lakshman, P. Malik, and J. Ellis. Facebook’s cassandra paper, annotated and compared to apache cassandra 2.0. http://www.datastax.com/ documentation/articles/cassandra/cassandrathenandnow.html. Accessed on 15/11/2014. [45] H. Li. bgzip - block compression/decompression utility. http://samtools. sourceforge.net/tabix.shtml#5, 2009. Accessed on 09/04/2015. [46] J. R. Mashey. Big data and the next wave of infrastress. In Computer Science Division Seminar, University of California, Berkeley, 1997. [47] MongoDB. Mongodb indexes. http://docs.mongodb.org/manual/core/ indexes-introduction/. Accessed on 15/11/2014. [48] J. K. Mullin. A second look at bloom filters. Communications of the ACM, 26(8):570–571, 1983. [49] P. O’Neil, E. Cheng, D. Gawlick, and E. O’Neil. The log-structured merge-tree (lsm-tree). Acta Informatica, 33(4):351–385, 1996. [50] U. Paila, B. A. Chapman, R. Kirchner, and A. R. Quinlan. Gemini: Integrative exploration of genetic variation and genome annotations. PLoS Comput Biol, 9(7):e1003153, 07 2013. [51] U. Paila, B. A. Chapman, R. Kirchner, and A. R. Quinlan. Gemini documentation. http://gemini.readthedocs.org/en/latest/, 2015. Accessed on 26/03/2015. [52] U. Paila, B. A. Chapman, R. Kirchner, and A. R. Quinlan. Querying the gene tables. http://gemini.readthedocs.org/en/latest/content/ querying.html#querying-the-gene-tables, 2015. Accessed on 07/05/2015. [53] F. P´erez and B. E. Granger. IPython: a system for interactive scientific computing. Computing in Science and Engineering, 9(3):21–29, May 2007. [54] D. R. Ports, A. T. Clements, I. Zhang, S. Madden, and B. Liskov. Transactional consistency and automatic management in an application data cache. In OSDI, volume 10, pages 1–15, 2010. [55] A. Quinlan. grabix - a wee tool for random access into bgzf files. https: //github.com/arq5x/grabix, 2012. Accessed on 09/04/2015. 84

Bibliografie [56] solid IT. Db-engine ranking. http://www.db-engines.com/en/ranking. Accessed on 15/11/2014. [57] M. Stonebraker, S. Madden, D. J. Abadi, S. Harizopoulos, N. Hachem, and P. Helland. The end of an architectural era: (it’s time for a complete rewrite). In Proceedings of the 33rd International Conference on Very Large Data Bases, VLDB ’07, pages 1150–1160. VLDB Endowment, 2007. [58] M. Stonebraker and A. Weisberg. The voltdb main memory dbms. IEEE Data Eng. Bull., 36(2):21–27, 2013. Voltdb indexes. http://mockdocs.voltdb.com/UsingVoltDB/ [59] VoltDB. ddlref_createindex.php. Accessed on 8/12/2014. [60] VoltDB. Voltdb query plans. http://docs.voltdb.com/PerfGuide/ ChapExecPlans.php. Accessed on 8/12/2014. [61] VoltDB. Voltdb technical overview. Whitepaper, 2010.

85

KU Leuven Faculteit Ingenieurswetenschappen

2014 – 2015

Fiche masterproef Student: Brecht Gossel´e Titel : Schaalbare genoomanalyse met NoSQL- databases Engelse titel: Scalable genome analysis with NoSQL databases UDC : 681.3 Korte inhoud : Vooruitgang in de bioinformatica heeft DNA-sequencing de afgelopen jaren fors goedkoper gemaakt. Dit verhoogt de vraag naar effici¨ente en flexibele opslag en verwerking van de grote hoeveelheid gegevens die dit proces genereert. Gelijkaardige ontwikkelingen in de websector hebben geleid tot NoSQL- en NewSQL-systemen die robuuste, schaalbare gedistribueerde opslag en flexibele modellering van data bieden. Deze masterproef bestudeert 6 zulke systemen en hun mogelijke toepassingen in de genoomanalyse. We stellen ook een ontwerp en implementatie voor een genoomanalysetool voor, gericht op flexibele analyse van genetische variatie in grote populaties m.b.v. een verrijkte SQL-syntax. Ons ontwerp is gebaseerd op GEMINI, en vervangt met het oog op schaalbaarheid de oorspronkelijke onderliggende SQLite-databank door Apache Cassandra. Dankzij een nieuw datamodel en aangepast querymechanisme in de client-code, bereikt onze implementatie tot 150x hogere snelheden bij het queryen, ten koste van duplicatie en een hogere initi¨ele laadtijd van gegevens. Advances in bioinformatics have driven down the cost of genome sequencing dramatically over the past years, raising the question how to efficiently and flexibly handle and store the large amount of data this process generates. Similar developments in web technology have spawned NoSQL and NewSQL datastores, which offer robust, highly scalable distributed storage and flexible data modelling. This master’s thesis reviews 6 such datastores and their possible applications to bioinformatics. We also propose a design and implementation of a genome analysis tool aimed at flexible analysis of genetic variation in large populations with an enriched SQL-syntax. Our design is based on GEMINI, replacing the original underlying SQLite-database with Apache Cassandra for the sake of scalability. Leveraging a new datamodel and custom client-side querymechanism, our implementation achieves up to 150x faster querying than the original version of GEMINI, at the cost of duplication and slower initial loading of data. Thesis voorgedragen tot het behalen van de graad van Master of Science in de ingenieurswetenschappen: computerwetenschappen, hoofdspecialisatie Gedistribueerde systemen Promotor : Prof. dr. R. Wuyts Assessor : Prof. dr. ir. Y. Berbers, Prof. dr. M.-F. Moens Begeleider : Prof. dr. R. Wuyts