Ontwerp en evaluatie van profiel-gebaseerde synthetische databanken

Ontwerp en evaluatie van profiel-gebaseerde synthetische databanken Mathias De Loore, Willem Delbare

Promotor: prof. dr. ir. Lieven Eeckhout Begeleiders: Stijn Polfliet, Frederick Ryckbosch Masterproef ingediend tot het behalen van de academische graad van Master in de ingenieurswetenschappen: computerwetenschappen

Vakgroep Elektronica en Informatiesystemen Voorzitter: prof. dr. ir. Jan Van Campenhout Faculteit Ingenieurswetenschappen en Architectuur Academiejaar 2011-2012

Ontwerp en evaluatie van profiel-gebaseerde synthetische databanken Mathias De Loore, Willem Delbare

Promotor: prof. dr. ir. Lieven Eeckhout Begeleiders: Stijn Polfliet, Frederick Ryckbosch Masterproef ingediend tot het behalen van de academische graad van Master in de ingenieurswetenschappen: computerwetenschappen

Vakgroep Elektronica en Informatiesystemen Voorzitter: prof. dr. ir. Jan Van Campenhout Faculteit Ingenieurswetenschappen en Architectuur Academiejaar 2011-2012

iv

Toelating tot bruikleen De auteur geeft de toelating deze eindverhandeling voor consultatie beschikbaar te stellen en delen ervan te kopiëren voor eigen gebruik. Elk ander gebruik valt onder de strikte beperkingen van het auteursrecht; in het bijzonder wordt er gewezen op de verplichting de bron uitdrukkelijk te vermelden bij het aanhalen van resultaten uit deze eindverhandeling. Gent, 4 juni 2012

v

Overzicht Kernwoorden: Web 2.0, Relational Databases, Synthetic databases, Synthetic workloads Met de opkomst van Web 2.0 applicaties ontstaan er nieuwe uitdagingen op het gebied van serverbeheer. De zogenaamde cloud-applicaties bewaren hun data niet langer op de desktop, maar worden ondersteund door centrale datacenters. Om persistentie te voorzien in een Web 2.0 applicatie wordt vaak beroep gedaan op een relationele database.

Probleemstelling Een grote uitdaging voor ontwikkelaars is het onderhoud van de applicatie. Er moeten geregeld aanpassingen gebeuren aan de onderliggende software of aan de applicatie zelf. Hoe kan een ontwikkelaar testen of de applicatie blijft werken wanneer de omgeving verandert? En hoe weten we wat de invloed hiervan is op de responstijd?

Oplossingsmethode In deze masterproef zullen we met behulp van een statistisch profiel van een relationele database een synthetische database bouwen die zich in een testomgeving hetzelfde gedraagt als de originele database uit de productieomgeving. Indien we hierin slagen zou het mogelijk zijn om automatisch representatieve testomgevingen te synthetiseren. Deze kunnen gebruikt worden om aanpassingen aan de applicatie, database of hardware te evalueren. Het type verandering dat we hiermee kunnen evalueren in de testomgeving zijn de typische veranderingen die zich voordoen in de productieomgeving van een Web 2.0 toepassing zoals sociale netwerken en online bedrijfsapplicaties. Om de oplossing te valideren konden we gebruik maken van een database die door een bekende Web 2.0 toepassing wordt gebruikt. Uit de experimentele resultaten bleek dat het inderdaad mogelijk is om met behulp van een statistisch profiel van een database een representatieve testomgeving op te bouwen.

Design and evaluation of profile-based synthetic databases Mathias De Loore, Willem Delbare Supervisor(s): Lieven Eeckhout, Stijn Polfliet, Frederick Ryckbosch Abstract— This article presents a profile-based approach to generating synthetic test environments for relational databases. To create such an environment a statistical profile is extracted from a production database. Next, a synthetic database is created based on this profile. This technique was validated using part of a database used in a well-known Web 2.0 application. In conclusion, this technique is useful for automatically generating synthetic test environments to evaluate changes to a database system and its environment. Keywords— Web 2.0, Relational Databases, Synthetic databases, Synthetic workloads

I. I NTRODUCTION I th the increasing number of Web 2.0 applications new challenges arise for developers managing the underlying infrastructure. Cloud applications no longer store their data on the client device, but store it in a remote datacenter. The device used by the client could be a laptop, smartphone or tablet. The advantages are numerous: the application is not dependent on operating systems or hardware, there is no installation process, no need for back-ups and no client-side updates are necessary. Relational databases are often used to deliver persistence in Web 2.0 applications. The database usually plays a big role in the performance of the application and will be a crucial factor as the application scales up to thousands or even millions of users.

W

II. P ROBLEM DESCRIPTION One of the challenges for the developers consists of dealing with changes in the application or the underlying software. Examples are security updates, new versions of the Database Management Software, Operating System upgrades,... Companies will be interested to see how these changes affect latency. Amazon claims [1] to lose 1% in sales for every 100ms of extra latency. Google claims [2] traffic to their search page drops by 20% for every 0.5 extra seconds of latency. We conclude that developers will be interested to learn more about the impact that changes have on latency. Finally, the developer is also interested in ensuring the application will keep working in a changing environment. III. DATABASEBENCHMARKS Currently, commercial databasebenchmarks such as TPC [3] or OSDB [4] can be used to evaluate hardware or software changes. In a normal workflow, one would compare the performance before and after changes and then decide whether or not to bring the change into the production environment. The downside to this workflow is that there is no guarantee the application will still work with these new changes. Furthermore, the workload executed by the benchmark might be very different from the application workload. Therefore, gains in latency

predicted by a standard benchmark might not translate well to the real application. IV. S YNTHETIC WORKLOADS Previous research into synthetic workloads was done in [5]. In this paper the workload of an offline application is compiled into a statistical profile. The profile contains details about the instruction mix in the program. Synthetic workloads have the advantage of being faster and more accurate than standard commercial benchmarks. Another great feature is their anonymous nature. The same technique was used in [6] on a higher level language (C in this case). The same advantages of synthetic benchmarks apply in this case. V. P RESENTED SOLUTION In this thesis we will try to use a statistical profile to synthesize a test environment that behaves just like the original database. The advantages of synthetic workloads are now translated to a database context. A first advantage is that these test environments can be easily manipulated and can be used to verify the impact of hardware or software changes to the application environment. This is important because small changes can have a huge impact on latency to end-users. Because the statistical profile is easy to manipulate we could also see what happens when the database scales up to different sizes. These are the typical changes that happen in the production environment of a Web 2.0 application such as social network websites and online business applications. Another advantage is the anonymous nature and the small size of the statistical profile. In the next section we will explain the basic process of creating a statistical profile. Afterwards we explain how to create a synthetic database from this profile. We then validate this synthetic database and present our conclusions in the final sections. VI. G ENERATING THE STATISTICAL PROFILE To generate a statistical profile of a relational database we first extract the structural information. This includes table names, column names and data types, but also index and constraint information. In the next step we will create an independent statistical profile for each column. The precise information that is extracted will depend on the data type of the column. For example, for the VARCHAR data type we will extract a histogram to model the typical length of strings in the column. In the final step, the relations between tables are extracted by using foreign keys. Some database schemes do not contain any explicit information about foreign keys. For example, when using MyISAM, no explicit foreign keys can be used. To solve this problem we

introduce a clustering algorithm to detect foreign keys in a relational database. The algorithm clusters columns based on name similarity, value ranges and data types. In each cluster a Primary key is elected and all other columns in the cluster become foreign keys. Finally, this information is saved to the statistical profile. The final profile contains the structural information for each table, statistical information about each column and information about the foreign key relations between tables. VII. B UILDING THE SYNTHETIC DATABASE The synthetic database must have statistical properties that closely match the properties in the profile. The database is constructed one table at a time. The inserted values are randomly generated using the statistical profiles saved for each column. The result is a database roughly the size of the original database. Special care needs to be taken when inserting data in columns that reference other tables (foreign keys). The algorithm we used makes sure that tables are generated in such an order that this is not a problem. VIII. VALIDATING THE SOLUTION To validate our solution we had access to a small partition of a well-known Web 2.0 application. Our experimental results show that the synthetic databases we created are indeed representative test environments. In figure 1 we can see that 90% of queries have an execution time on the synthetic database that does not differ more than 25% from the original execution time. We show how the synthetic database can be useful by giving two example use cases. In the first use case we change the Storage engine used by the database and in the second use case we alter the cache size. In both cases the impact on performance was similar in both environments. IX. C ONCLUSIONS Our results show that it is indeed possible to generate representative test environments for relational databases using a statistical profile. We validated this by introducing changes to both the original and synthetic environment. In both cases we used the statistical profile to successfully predict the impact on latency. This means the profile-based technique can be a great tool to assist in maintaining Web 2.0 applications. Other advantages of this approach are the easy manipulation of the statistical profile, the low impact of the extraction on the production environment and the anonymous nature of the synthetic database. X. E XTENSIONS In the future a cloud-service could be built using the previous concepts. Developers could use the service to create statistical profiles of their databases. These profiles could be uploaded and used to automatically generate synthetic test environments. The test environments can be manipulated in scale and could be used to test the impact of software and hardware changes before bringing these changes into the production environment. We can take this one step further by looking beyond the database aspect of Web 2.0 applications. The performance of cache servers could be taken into account, and even the HTTP traffic from the end-user to the webservers. By using the technique of statistical

Fig. 1 P ERFORMANCE OF THE SYNTHETIC DATABASE

profiles it might be possible to synthesize a test environment for the entire infrastructure of a modern Web 2.0 application. R EFERENCES [1] Liddle J. Amazon found every 100ms of latency cost them 1% in sales, 2008. http://blog.gigaspaces.com/2008/08/27/amazon-found-every-100msof-latency-cost-them-1-in-sales/ [2] Linden G. Marissa Mayer at Web 2.0: http://glinden.blogspot.com/2006/11/ marissa-mayer-at-web-20.html, 2006. [3] TPC. Transaction processing performance council: http://www.tpc.org/, 2012. [4] OSDB. The open source database benchmark: http://osdb.sourceforge.net/, 2012. [5] Joshi A., Eeckhout L., Bell Jr. R., and K. John L. Distilling the essence of proprietary workloads into miniature benchmarks. ACM Trans. Archit. Code Optim., 5(2):10:1–10:33, September 2008. [6] Van Ertvelde L. and Eeckhout L. Benchmark synthesis for architecture and compiler exploration. In 2010 IEEE International symposium on Workload Characterization (IISWC 2010), pages 106–116. IEEE, 2010.

viii

Inhoudsopgave 1 Inleiding

2

2 Probleemstelling

5

3 State of the art 3.1 Databasebenchmarks . . . . . . . . . . . . . . . . . 3.2 Synthetische werklasten . . . . . . . . . . . . . . . 3.2.1 Synthetische benchmarks en energieverbruik 3.2.2 Werklasten op datacenter niveau . . . . . . 3.3 (De)-anonimisatie van databases . . . . . . . . . . . 3.4 Relatie met eigen werk . . . . . . . . . . . . . . . .

. . . . . .

7 7 8 8 9 9 10

4 Oplossing 4.1 Overzicht raamwerk . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

11 12

5 Extractie databaseprofiel 5.1 Overzicht . . . . . . . . . . . . . . . . . . . . . . . . 5.2 Inhoud van het statistisch profiel . . . . . . . . . . . 5.2.1 Databaseschema . . . . . . . . . . . . . . . . 5.2.2 Statistisch profiel van kolomdata . . . . . . . 5.2.3 Statistisch profiel van relaties tussen tabellen . 5.3 Automatisch ophalen van het statistisch profiel . . . . 5.4 Conclusie . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . .

14 14 14 14 16 19 25 25

. . . . . .

26 26 26 26 28 28 28

. . . . . .

. . . . . .

. . . . . . .

. . . . . .

. . . . . . .

. . . . . .

. . . . . . .

. . . . . .

. . . . . . .

. . . . . .

. . . . . . .

. . . . . .

. . . . . . .

. . . . . .

. . . . . . .

. . . . . .

. . . . . . .

. . . . . .

. . . . . . .

. . . . . .

. . . . . . .

. . . . . .

. . . . . . .

6 Genereren van de synthetische database 6.1 Synthetische databases . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.2 Opbouw synthetische database . . . . . . . . . . . . . . . . . . . . . . . . 6.2.1 Algoritme voor het invullen van data volgens kolomtype . . . . . 6.2.2 Algoritme voor de volgordebepaling van het invullen van tabellen 6.2.3 Verdere optimalisaties . . . . . . . . . . . . . . . . . . . . . . . . 6.2.4 Foutafhandeling . . . . . . . . . . . . . . . . . . . . . . . . . . . .

INHOUDSOPGAVE

ix

6.2.5

6.3

Algoritme voor het genereren van Foreign key waarden voor Integer type kolommen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.2.6 Oplossen van conflicten bij het invullen van de tabellen . . . . . . . Genereren van synthetische query log . . . . . . . . . . . . . . . . . . . . .

7 Validatie 7.1 Query trace afspelen en opmeting van prestatie . . . . . 7.1.1 Afspelen met behulp van uniforme interarrivaltijd 7.1.2 Invloed van externe factoren . . . . . . . . . . . . 7.1.3 Afspelen met behulp van Poisson interarrivaltijd . 7.2 Manuele prestatieanalyse . . . . . . . . . . . . . . . . . 7.2.1 Vergelijking van resultatenset . . . . . . . . . . . 7.2.2 Invloed van query plan . . . . . . . . . . . . . . . 7.2.3 Opvragen query plan in MySQL . . . . . . . . . . 7.3 Automatisering prestatieanalyse . . . . . . . . . . . . . . 8 Experimentele resultaten 8.1 Originele testset . . . . . . . . . . . . . . . . 8.2 Werkwijze prestatievaststelling . . . . . . . . . 8.3 Bovengrens prestatievergelijking . . . . . . . . 8.4 Prestatievergelijking in testomgeving . . . . . 8.5 Invloeden van fragmentatie op uitvoeringstijd 8.5.1 Fragmentatie op bestandsniveau . . . . 8.5.2 Fragmentatie op diskniveau . . . . . . 8.6 Experimentele invloed van Poisson interarrival 8.7 Invloed van databaseschaling op prestatie . . . 8.7.1 Prestatie bij gebruik kleinere database 8.7.2 Prestatie bij gebruik grotere database . 8.8 Invloed van query cache . . . . . . . . . . . . 8.9 Invloed van storage engine MyISAM/InnoDB

. . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . tijden op de . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . prestatie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . .

. . . . . . . . . . . . .

29 31 33

. . . . . . . . .

35 35 35 36 36 37 37 38 39 40

. . . . . . . . . . . . .

41 41 42 42 43 45 45 46 47 49 49 52 54 54

9 Conclusies

61

Bibliografie

63

Lijst van figuren

65

1

Tabel van afkortingen en symbolen DBMS

Database Management System zoals bijvoorbeeld MySQL, PostgreSQL, ... Storage Onderliggend systeem dat de data wegschrijft en uitleest voor het Engine DBMS zoals MyISAM of InnoDB IMDB Internet Movie Database (http://www.imdb.com) Sharding Database sharding is een techniek waarbij grote databases in partities verdeeld worden over een aantal servers. Bij deze techniek is er nooit data die gerepliceerd wordt over verschillende servers (”shared-nothing”). Op die manier kan men zeer hoge prestaties en schaalbaarheid behalen. IAT Interarrival tijd

2

Hoofdstuk 1 Inleiding Met de opkomst van Web 2.0 applicaties ontstaan er nieuwe uitdagingen op het gebied van serverbeheer. De zogenaamde cloud-applicaties bewaren hun data niet langer op de desktop, maar worden ondersteund door centrale datacenters. Het toestel dat de klanten gebruiken kan een laptop zijn, maar ook een telefoon of tablet. Het voordeel voor de klanten is dat dit soort diensten onafhankelijk is van besturingssystemen of hardware. Bovendien moet de klant niet zelf instaan voor installatie, back-up of onderhoud van de software. Het probleem voor de ontwikkelaars wordt nu om de software schaalbaar te houden.

Databases Om persistentie te voorzien in een Web 2.0 applicatie wordt vaak beroep gedaan op een relationele database. Dit soort databases spelen dus een grote rol in de doorsnee Web 2.0 applicatie. De database zal meestal een van de grootste bottlenecks zijn wanneer het aantal gebruikers toeneemt. Met de jaren zijn er heel wat uiteenlopende technieken bedacht om dit op te vangen.

Probleemstelling Een andere uitdaging voor ontwikkelaars bestaat uit het onderhoud van de applicatie. Er moeten geregeld aanpassingen gebeuren aan de onderliggende software of aan de applicatie zelf. Soms wil men deze aanpassingen bewust introduceren, in andere gevallen is men verplicht om een nieuwe beveiligingsupgrade uit te voeren om de veiligheid van het systeem te kunnen garanderen. Hoe kan een ontwikkelaar testen of de applicatie blijft werken wanneer de omgeving verandert? Bovendien zijn er nog andere factoren van belang voor een

HOOFDSTUK 1. INLEIDING

3

succesvolle Web 2.0 applicatie. Zo blijkt uit [1] dat de responstijd van groot belang is om gebruikers tevreden te houden. Voor Amazon vertaalt zich dit in 1% verlies in verkoopcijfers voor elke extra 100ms die bij de responstijd geteld wordt. Google ondervindt een verlies van 20% in bezoekersaantallen voor elke additionele 500ms responstijd. De ontwikkelaar is dus ook sterk ge¨ınteresseerd in de impact van veranderingen op de responstijd.

Overzicht oplossing In deze masterproef zullen we met behulp van een statistisch profiel van een relationele database een synthetische database bouwen die zich in een testomgeving hetzelfde gedraagt als de originele database uit de productieomgeving. Hierdoor wordt het mogelijk om de impact van aanpassingen aan de productieomgeving te voorspellen. Aanpassingen aan de applicatie kunnen immers een enorme weerslag hebben op de interactie met de database. Bovendien zouden we kunnen simuleren wat er gebeurt indien de database dubbel zo groot, of tien keer groter wordt, of wat er gebeurt indien een nieuwe versie van het databasesysteem ge¨ıntegreerd wordt. Het type verandering dat we hiermee opvangen en kunnen evalueren in de testomgeving zijn dus de typische veranderingen die zich voordoen in de productieomgeving van een moderne Web 2.0 toepassing zoals sociale netwerken en online bedrijfsapplicaties.

Extractie databaseprofiel Nadat de volledige structuurinformatie beschikbaar is zal van elke kolom een statistisch profiel gemaakt worden. Afhankelijk van het datatype van de kolom zullen verschillende acties moeten ondernomen worden. In een laatste stap zullen we onderlinge relaties tussen de tabellen in kaart proberen brengen. Hiervoor hebben we eerst alle informatie over de foreign keys nodig. Omdat die vaak niet aanwezig is in het databaseschema, hebben we enkele technieken ontwikkeld om ze te detecteren.

Genereren van de synthetische database Een synthetische database is een database die zo waarheidsgetrouw mogelijk aanleunt bij een bepaalde originele database. Ze wordt opgebouwd aan de hand van een statistisch profiel dat zo compact mogelijk de statistische eigenschappen van de originele database bevat. Met behulp van deze statistieken zullen we alle tabellen één voor één construeren

HOOFDSTUK 1. INLEIDING

4

en opvullen met data. Het eindresultaat is een database die dezelfde grootte heeft, maar random data bevat die veel statistische eigenschappen heeft van de originele database.

Validatie Om de werking van het statistisch model te valideren beschikken we over een database die door een bekende Web 2.0 toepassing wordt gebruikt. De validatie zal gebeuren door veranderingen aan te brengen in de originele database en de synthetische database. Indien de veranderingen dezelfde impact op de prestatie veroorzaken kunnen we de synthetische database een representatieve testomgeving noemen.

5

Hoofdstuk 2 Probleemstelling Bedrijven die instaan voor het beheer van grote databases staan voor vele uitdagingen bij het verder uitbreiden van hun infrastructuur. Zo zijn er problemen met koeling, energieverbruik, netwerktoegang, redundantie, ... Een ander probleem specifiek voor grote applicatiedatabases is het opzetten van representatieve testomgevingen. Indien een groot databasecenter voor productiedoeleinden wordt gebruikt, is het vaak niet meer mogelijk of praktisch om representatieve testomgevingen op te bouwen die het databasecenter simuleren. Deze kunnen nodig zijn om de invloed te testen van software updates aan de besturingssystemen, aan de database software of aan de bedrijfsapplicaties zelf. Het kan ook interessant zijn om alternatieve hardwareconfiguraties te evalueren. Specifiek voor een database omgeving kan men ge¨ınteresseerd zijn in wat er gebeurt indien een nieuwe versie van het DBMS gebruikt wordt, indien een andere storage engine wordt gebruikt, indien het gebruik van caching wordt gewijzigd, ... Dit soort veranderingen kan men niet zonder risico doorvoeren in een productieomgeving. Ten eerste is het niet eenvoudig om te beoordelen of de aanpassingen de prestatie goed of slecht be¨ınvloed hebben en bovendien is het zelfs mogelijk dat de applicatie niet meer of slechts gedeeltelijk werkt na de aanpassing. Samengevat kan een representatieve testomgeving een antwoord bieden op de volgende vragen die in een Web 2.0 toepassing vaak voorkomen: Hoe verandert de responstijd van de applicatie bij het introduceren van veranderingen? Blijft de applicatie werken met een nieuwe versie van de onderliggende software? Blijft de applicatie werken na het toevoegen van nieuwe hardware?

HOOFDSTUK 2. PROBLEEMSTELLING

6

Een voor de hand liggende oplossing voor dit probleem in de context van databases zou zijn om de volledige database te kopiëren naar een testomgeving. Dit brengt echter enkele problemen met zich mee: Negatieve invloed op responstijden Ten eerste zal het kopiëren van de volledige productiedatabase een verstoring van de prestatie veroorzaken voor de applicatie, omdat dit veel extra netwerkverkeer en I/O opdrachten vereist. Voor de gebruikers van de applicatie kan dit onaangenaam zijn. Ten tweede is het niet meer mogelijk om de database te delen over lange afstand om de testomgeving ergens anders op te zetten. Het verzenden van de gehele database over internet zou vaak veel te lang duren. Sommige databases zullen immers vele Terabytes groot zijn, zodat dit vaak gewoon niet mogelijk zal zijn. Privacy en bedrijfsgevoelige informatie blootgesteld Het wordt moeilijk om de tests door een derde partij te laten uitvoeren omdat de databases over het algemeen persoonlijke gegevens bevat van klanten. Dit laatste probleem heeft geen kant-en-klare oplossing. Het is niet eenvoudig om de database manueel af te zoeken naar gevoelige informatie en die handmatig te anonimiseren. Via statistische analyse kan men er immers soms nog in slagen om gevoelige informatie zoals de identiteit van een gebruiker te achterhalen uit een database die gedeeltelijk geanonimiseerd is. Geen manipulatie van testomgeving mogelijk Ten derde maakt het statistisch profiel van de database het mogelijk om een testomgeving te bouwen die gelijkaardig is aan de productieomgeving, maar we zouden evengoed een testomgeving kunnen maken die kleiner of groter is, of die qua structuur licht afwijkt. Dit is niet mogelijk wanneer men de database gewoonweg kopieert uit de productieomgeving.

7

Hoofdstuk 3 State of the art In dit hoofdstuk wordt onderzoek gedaan naar aanverwant werk. Er wordt onder andere gekeken naar bestaande databasebenchmarks. Daarna wordt het gebruik van synthetische werklasten op microinstructieniveau bekeken. Deze techniek wordt ook toegepast op hogere niveau programmeertalen. Daarna kijken we naar de relatie tussen synthetische benchmarks en energieverbruik. Vervolgens bekijken we werklasten op niveau van datacenters en hebben we het over de anonimisatie van databases. Tenslotte kijken we hoe ons werk gerelateerd kan worden aan het bestaande werk.

3.1

Databasebenchmarks

In een grote productieomgeving kan men gebruik maken van bestaande databasebenchmarks voor databases zoals TPC [2] of OSDB [3]. Om de beslissing te maken om over te stappen naar een nieuwe versie van de onderliggende software kan men een benchmark laten lopen op een server met de oude software en met de nieuwe software. Daarna kan de prestatie vergeleken worden en maakt men op basis van de prestatiewinst een besluit om deze software al dan niet te integreren in de productieomgeving. Het nadeel hiervan is dat men geen garanties heeft dat de eigen applicatie nog volledig zal werken, maar ook dat men geen idee heeft of de prestatiewinst opgemeten met de benchmark zich ook zal vertalen naar een prestatiewinst in de productieomgeving. De specifieke werklast van de productieomgeving kan er immers helemaal anders uitzien dan die van de benchmark. Om de tests zelf uit te voeren kan een databasebeheerder ervoor kiezen om een externe partij in te huren die hierin gespecialiseerd is, of om zelf een commerciële of open-source benchmark te laten lopen in een eigen omgeving. Deze benchmarks zullen waarschijnlijk niet representatief zijn voor de eigen applicatie. In het beste geval wordt een eigen benchmark

HOOFDSTUK 3. STATE OF THE ART

8

suite opgesteld, maar ook dit vergt veel tijd en expertise.

3.2

Synthetische werklasten

Onderzoek hiernaar werd gedaan in Distilling the Essence of Proprietary Workloads into ” Miniature Benchmarks” [4]. In dit onderzoek wordt de workload van een (offline) applicatie die aangeboden wordt aan de processor statistisch in kaart gebracht en wordt een synthetische benchmark gemaakt die gelijkaardig is aan de originele toepassing qua prestatie en energieverbruik. Het voordeel van de synthetische benchmarks is dat men veel sneller en accurater evaluaties kan uitvoeren dan mogelijk is met algemene benchmarks. De benchmarks kunnen ook gebruikt worden door chipontwikkelaars, omdat het ze toegang geeft tot benchmarks die alle trekken vertonen van de real-world applicaties waarop de benchmarks gebaseerd zijn. In een uitbreiding op onze masterproef zouden we ook een volledig synthetische workload kunnen opmaken voor de database, wat alle voordelen met zich meebrengt van synthetische benchmarks. De workload bevindt zich dan niet op microinstructieniveau, maar op database query niveau. De techniek die in de paper van Joshi et al. werd gebruikt werd ook al toegepast op hogere niveau-talen in plaats van op microinstructieniveau. In Benchmark Synthesis for ” Architecture and Compiler Exploration” [5] wordt beschreven hoe synthetische benchmarks kunnen gemaakt worden in een hogere niveau taal (C in dit geval). Ook hier blijven de voordelen van de synthetische benchmarks gelden: er wordt geen propriëtaire informatie over de applicatie vrijgegeven, het is mogelijk om de synthetische benchmarks sneller uit te voeren en tot dezelfde conclusies te komen, ...

3.2.1

Synthetische benchmarks en energieverbruik

We hebben de voordelen van synthetische benchmarks opgesomd en hebben opgelijst in welke situaties ze kunnen gebruikt worden. Op gebied van energieverbruik zijn er nog enkele interessante toepassingen. In Automated Microprocessor Stressmark Generation” [6] ” wordt met behulp van synthetische benchmarks achterhaald welke instructiemix en geheugentoegangspatronen de hoogste energie vereisen voor een bepaalde microarchitectuur. De resultaten die gevonden worden kunnen helpen bij het schatten van de maximale energie en koeling vereisten die nodig zijn bij het ontwerpen van een processor en zijn packaging, cooling en energietoevoer. Op datacenter niveau kan dit grote voordelen opleveren zoals uitgelegd in Power Provisioning for a Warehouse-sized Computer” [7]. Als men kan voor” spellen hoeveel het piekverbruik is van de bestaande hardware in een datacenter kan men


9

zonder al te groot risico blijven uitbreiden zolang die onder de bestaande capaciteit van de energietoevoer blijft. Het ’nameplate’-verbruik dat door de hardwaremakers wordt meegegeven blijkt weinig nuttig bij het inschatten van energieverbruik aangezien dit meestal veel te hoog wordt geschat. Deze onbenutte energiecapaciteit kan beter benut worden voor verdere uitbreiding. De synthetische maximum-energie benchmarks (of stressmarks) blijken weer een aantal voordelen te bieden over de bestaande (handgecodeerde) stressmarks. Zo wordt het mogelijk om een bepaalde workload aan de hand van een aantal microarchitectuur-onafhankelijke kenmerken te definiëren en daarna te evalueren op verschillende architecturen en criteria. In SWEEP: Evaluating Computer System Energy Efficiency using Synthetic Workloads” ” [8] wordt een raamwerk voorgesteld om synthetische benchmarks te genereren met bepaalde eigenschappen gerelateerd aan energieverbruik. Het raamwerk wordt daarna gebruikt om de energie-efficiëntie van een aantal commerciële systemen te evalueren. Men besluit dat de energie-efficiëntie van een systeem ook sterk afhankelijk is van de gepresenteerde workload. De synthetische benchmarks blijken dus ook op gebied van energie een handige tool voor ontwerpers van microarchitecturen.

3.2.2

Werklasten op datacenter niveau

Op hoger niveau kan dit betekenen dat men in datacenters mogelijks beter werkt met een mix van verschillende types machines, waarbij sommige machines een meer energieefficiënte oplossing hebben voor een bepaald type workload. Andere pogingen om emulaties mogelijk te maken van volledige datacenters werden voorgesteld in Data Center Workload ” Monitoring, Analysis, and Emulation” [9]. Hier ligt de focus op het opmeten van resource verbruik, het opslaan en filteren van de data en het afspelen van een opgemeten werklast. Het type datacenter waarover men hier spreekt wordt gebruikt voor algemene doeleinden zoals multimedia rendering, data analyse of andere applicaties.

3.3

(De)-anonimisatie van databases

In 2006 gaf Netflix, een grote online video uitleendienst, zijn Prize dataset weg via internet. Deze dataset bevat geanonimiseerde data over de kijkers en hun voorkeuren. Er werd een prijs weggegeven aan het team dat het beste algoritme kon verzinnen dat er in slaagde om een voorspelling te maken over welke films iemand graag zou zien. In een paper beschrijven Narayanan A. & Shmatikov V. [10] hoe ze erin slagen om de dataset gedeeltelijk te deanonimiseren met behulp van beperkte kennis over een bepaald individu. Het wordt


10

mogelijk om bepaalde gebruikers te identificeren met behulp van data die ze achterlaten op andere publieke websites (zoals IMDB). Op deze manier zou mogelijks gevoelige data vrijgegeven kunnen worden. Er werd al veel onderzoek gedaan om dergelijke problemen te voorkomen. Een voorbeeld hiervan is het k-anonimity algoritme, waarbij het de bedoeling is een persoon niet onderscheidbaar te maken van k-1 andere personen. [11] We besluiten dat het belangrijk is om data te beschermen en dat het niet eenvoudig is om een hele database handmatig te anonimiseren. Zelfs als dit gebeurd is kan men niet garanderen dat er geen persoonlijke data meer kan blootgelegd worden.

3.4

Relatie met eigen werk

Bij onze masterproef gaan we specifiek kijken naar Web 2.0 applicaties waar factoren zoals de responstijd naar eindgebruikers toe en het energieverbruik van groot belang zijn. In plaats van een statistisch profiel op te stellen van een microinstructiestroom, zullen we een statistisch profiel opstellen van de database die gebruikt wordt in de applicatie. Op die manier kunnen we een representatieve testomgeving opbouwen. Als uitbreiding hierop kunnen later ook de queries die aangeboden worden aan de synthetische database opgebouwd worden aan de hand van een statistisch profiel. Op het einde van dit document stellen we een systeem voor dat in staat zou zijn om de productieomgeving van een hele Web 2.0 applicatie synthetisch na te bootsen. Met behulp van een dergelijke synthetische omgeving is het eenvoudiger om inzicht te krijgen in de verschillende workloads en waar die aangeboden wordt. Op die manier kunnen we de mogelijke winsten op gebied van energie-efficiëntie op schaal van een datacenter evalueren.

11

Hoofdstuk 4 Oplossing Om de gestelde problemen op te lossen werd er tijdens deze masterproef een raamwerk ontwikkeld om een synthetische database te genereren op basis van een bestaande database. In eerste instantie wordt er een statistisch profiel opgesteld. Dit profiel bevat alle informatie die nodig is om een synthetische database aan te maken. De voordelen hiervan zijn de volgende: Invloed op de productieomgeving: Opbouwen van een statistisch profiel heeft weinig invloed op de productieomgeving, ze kan eventueel zelfs opgebouwd worden aan de hand van een steekproef. Op die manier moet slechts een zeer klein deel van de database bevraagd worden. Gevoelige informatie: Garantie dat geen persoonlijke gegevens vrijkomen wanneer het statistisch profiel wordt vrijgegeven aan een derde partij. Geringe grootte: Het statistisch profiel kan klein genoeg zijn om via internet te versturen. Het is niet nodig om Terabytes aan data door te sturen. Een synthetische database met statistische eigenschappen kan opgebouwd worden in een ’testfabriek’ aan de andere kant van de wereld op korte tijd. Manipulatie: Het statistisch profiel kan gemakkelijk worden gemanipuleerd. Op die manier kan men de testomgeving op ingrijpende manier veranderen mocht dat gewenst zijn (bijvoorbeeld om een schaalwijzigingen te introduceren). Dit is niet mogelijk als we gewoon een kopie nemen van de productiedatabase. Automatisering: Het gebruik van de synthetische database kan verder uitgebreid worden om het opzetten van een testomgeving volledig te automatiseren.

HOOFDSTUK 4. OPLOSSING

12

Synthetische werklasten: De techniek kan mogelijks ook uitgebreid worden om een profiel op te bouwen van query trace logs. Mogelijks kan hij zelfs uitgebreid worden om ook HTTP verkeer te modelleren. Deze genieten dan ook alle bovenstaande voordelen.

4.1

Overzicht raamwerk

We stellen een raamwerk voor dat het opbouwen van een synthetische database automatiseert. Om het raamwerk op te bouwen gaan we te werk in 3 stappen: 1. Extractie databaseprofiel: in deze stap wordt een statistisch profiel gemaakt van de originele database. Het profiel bevat de databasestructuur en metadata die de inhoud van de kolommen beschrijft. Ook de onderlinge relaties tussen tabellen wordt opgeslagen in het profiel. 2. Genereren van de synthetische database: in deze stap wordt op basis van het profiel een synthetische databank aangemaakt die dezelfde statistische eigenschappen heeft als de originele database. 3. Validatie: in deze stap gaan we na in welke mate de synthetische database qua prestatie gelijkaardig is aan de originele database. Om deze experimenten uit te voeren beschikken we over een deel van een database uit een bekende Web 2.0 toepassing. In de volgende 3 hoofdstukken worden deze 3 stappen één voor één uitgediept. In hoofdstuk 5 wordt verteld wat het databaseprofiel uiteindelijk allemaal zal bevatten en hoe het databaseprofiel wordt verkregen voor verschillende datatypes. In het daaropvolgende hoofdstuk wordt uitgelegd wat een synthetische database nu precies is en hoe ze wordt opgesteld met behulp van de output van stap 1. We brengen de moeilijkheden en

Figuur 4.1: De stappen die we doorlopen bij opbouwen van het raamwerk

HOOFDSTUK 4. OPLOSSING

13

beperkingen in kaart. In hoofdstuk 7 gaan we na hoe goed de statistische eigenschappen van de originele en de synthetische database overeenkomen door het uitvoeren van prestatietests. In hoofdstuk 8 worden de experimentele resultaten voorgelegd en in hoofdstuk 9 sluiten we af met onze conclusies.

14

Hoofdstuk 5 Extractie databaseprofiel 5.1

Overzicht

Nadat de volledige structuurinformatie beschikbaar is zal van elke kolom een statistisch profiel gemaakt worden. Afhankelijk van het datatype van de kolom zullen verschillende acties moeten ondernomen worden. In sectie 5.2.2 geven we meer informatie vinden over de collectie van statistieken per datatype. In een laatste stap zullen we onderlinge relaties tussen de tabellen in kaart proberen brengen. Hiervoor hebben we eerst alle informatie over de foreign keys nodig. Omdat die vaak niet aanwezig is in het databaseschema, hebben we enkele technieken ontwikkeld om ze te detecteren. Hierop gaan we in detail in sectie 5.2.3.

5.2 5.2.1

Inhoud van het statistisch profiel Databaseschema

Het schema bevat de structuur van elke individuele tabel. Dit omvat de namen en datatypes van elke kolom, maar ook relaties tussen tabellen, constraints, informatie over primary keys, unique keys en indices. Sommige database-implementaties voorzien speciale commando’s die deze taak vereenvoudigen. In MySQL databases kan het commando ’SHOW CREATE TABLE’ gebruikt worden om de exacte SQL-statement te verkrijgen die een tabel opbouwt met een identieke structuur. Dit commando houdt ook rekening met indices, primary keys, velden die automatisch worden ge¨ıncrementeerd en unique constraints. Indien deze tools niet voorzien zijn, kan een meer algemene aanpak gebruikt worden: data uit de metadatabase opvragen.

HOOFDSTUK 5. EXTRACTIE DATABASEPROFIEL

15

Figuur 5.1: Voorbeeld van een databaseprofiel: van elke tabel in de database wordt de structuur bijgehouden en voor elke kolom wordt afhankelijk van het datatype de minima, maxima en/of een histogram bijgehouden. In het geval van een foreign key wordt er een histogram over die foreign key bijgehouden.

Men kan bijvoorbeeld alle indices van tabel ’ab’ opvragen met behulp van het commando: ’SHOW INDEX FROM ab’. Deze commando’s zijn vaak database-specifiek. Sommige van de gebruikte commando’s zijn immers enkel beschikbaar in MySQL. Business logica vervat in het databaseschema Het databaseschema bevat naast de namen van de tabellen en kolommen ook hier en daar nog andere gegevens. Zo omvat het ook de waarden die voor ENUM velden kunnen worden ingevuld en kan het ook commentaar bevatten van ontwikkelaars. Als een derde partij inzage heeft in dit schema kan dit een deel van de business logica blootleggen. Men kan voorspellen wat de zwakke en sterke punten van de applicatie zullen zijn en dit is mogelijks ongewenst. Dit kan verder ingedekt worden door ook de tabelnamen, kolomnamen en vaste data van ENUM sets en dergelijke te vervangen door random data. Een belangrijk gevolg hiervan is dat de query log dan ook volledig aangepast moet worden, zoniet zullen zich fouten voordoen. Indien er na de analyses specifieke opmerkingen zijn over bepaalde tabellen en kolommen, kan via de mapping van de geanonimiseerde kolomnamen op de echte kolomnamen gemakkelijk nagegaan worden over dewelke het precies gaat. Dit is een uitbreiding die gemakkelijk kan toegevoegd worden.


5.2.2

16

Statistisch profiel van kolomdata

Naast het databaseschema wordt voor elke kolom apart extra statistische data opgeslagen die zal helpen bij het opbouwen van de synthetische database. We beschrijven hieronder voor elk datatype welke informatie opgezocht en opgeslagen wordt. Datatype: CHAR Een CHAR kolom bevat tekstvelden van een vaste, vooraf gedefinieerde lengte. Veel voorkomende waarden voor de lengte zijn meestal kleiner dan 10, aangezien dit datatype meestal wordt gebruikt om codes op te slaan (zoals landcodes). Naast de lengte zullen we ook het aantal unieke waarden opslaan. Eens we deze 2 eigenschappen hebben, weten we genoeg om de kolom volledig op te bouwen met random data die zodanig gelijkaardig is dat ze bij prestatietests niet onderscheidbaar zal zijn van de kolom in de originele tabel. Het is belangrijk hierbij op te merken dat er in de praktijk bij Web 2.0 toepassingen in de database nauwelijks stringvergelijkingen zullen uitgevoerd worden, omdat alle opzoekingen via de (snellere) indices verlopen. Datatype: TEXT Dit datatype bevat meestal inhoud die door gebruikers zelf is ingegeven. We kunnen er dus van uitgaan dat deze bijna altijd uniek zal zijn en het is dus bijgevolg niet nuttig om het aantal unieke waarden op te vragen. Aangezien enkel de lengte hier van belang is, zullen we enkel daarvan een histogram opstellen. Een text datatype kan een lengte hebben die zeer groot wordt. Hierdoor moeten we de verschillende lengtes op een speciale manier opslaan. We kunnen immers niet gewoon elke verschillende lengte opslaan. We zullen een histogram met een aantal bins opstellen om deze data compact voor te stellen. Het aantal bins ligt vast in het raamwerk, maar voor sommige toepassingen zal het nodig zijn om het aantal bins dynamisch te maken, of om de bins dynamisch te schalen, zodat er meer bins zijn in regio’s waar meer waarden voorkomen. Dit kan het aantal benodigde queries, en de uitvoeringstijd van die queries sterk doen stijgen. Gecombineerd met het feit dat de lengte van text-kolommen opvragen relatief lang duurt in vergelijking met andere opvragingen, leek het ons dus geen goed idee om de bins dynamisch te maken.


17

Datatype: VARCHAR Varchar types kunnen vergeleken worden met text types, maar met een vaste vooraf gedefinieerde maximale lengte. Ze worden ook anders opgeslagen op de harde schijf. Wat ons model betreft kunnen we ze op dezelfde manier behandelen als TEXT datatypes. Ook hier gaan we ervan uit dat het om grotendeels unieke waarden gaat (met al dan niet toevallig dezelfde waarden voor sommige rijen) en dat we dus enkel een histogram van de lengtes van de kolomwaarden nodig hebben. Datatype ENUM Het ENUM datatype bevat voor elke rij één waarde uit een vaste set waarden. Een praktijkvoorbeeld van een ENUM is een kolom die het geslacht bijhoudt. De set van mogelijke waarden kan dan bestaan uit: mannelijk, vrouwelijk of onbekend. Het is vanzelfsprekend dat dit datatype betere prestaties biedt dan het VARCHAR type om het geslacht bij te houden. Waar mogelijk gebruikt men dus best dit datatype. Bij dit datatype wordt de originele waardenset bewaard in het statistisch profiel alsook de verdeling van het voorkomen van elke waarde. In ons voorbeeld zouden we dus de waarden mannelijk, vrouwelijk en onbepaald bijhouden. De verdeling van die waarden heeft natuurlijk als resultaat dat het percentage mannen en vrouwen zichtbaar is. Dit is het zwakste punt in onze implementatie vanuit anonimisatie-standpunt, maar is op te lossen zoals al werd besproken in sectie 5.2.1. We slaan ook het aantal lege waarden op, aangezien dat ook altijd in een enum-kolom kan ingevuld worden. Ook is het de standaard waarde indien er geprobeerd wordt om een waarde in te vullen die niet in de gedefinieerde set van waarden zit. Datatype SET Het SET datatype bevat voor elke rij een aantal waarden uit een vaste set waarden. Ook hier wordt de volledige originele waardenset opgeslagen. De implicaties hiervan werden voorheen uitgelegd (in sectie 5.2.1). Dit datatype kan verder op een gelijkaardige manier behandeld worden als het ENUM-datatype. Datatype DATE Het DATE veld in MySQL houdt een datum bij tot op het niveau van één dag (bijvoorbeeld van de vorm ’2006-05-01’). Het is dus belangrijk dat we te weten komen wat de vroegste en laatste datum is die we tegenkomen in deze kolom. Om dit op te vragen kunnen we


18

eenvoudigweg het minimum en maximum van deze kolom ophalen. Er wordt dus een uniforme verdeling van de kolomwaarden binnen deze grenzen verondersteld. Voor dit datatype volgt de verdeling van de waarden uit het aantal waarden en het bereik, dus er moeten geen extra waarden bijgehouden worden. Er wordt nog 1 extra waarde bijgehouden om ondersteuning te hebben voor nul-waarden. (0000-00-00) Datatype TIMESTAMP / DATETIME De waarden van beide types zien er hetzelfde uit: de waarde is een datum, tot op secondeniveau (bijvoorbeeld ’2006-05-01 12:00:01’). Intern slaan we deze waarden op als Long values in Java die het aantal seconden sinds 1 januari 1970 aanduiden, en bij het opvragen van die waarden wordt terug een timestamp getoond. Net zoals bij date-kolommen zullen we een extra percentage bijhouden voor de nul-waarde. (0000-00-00 00:00:00). Wat het formaat van de waarden betreft zijn TIMESTAMP en DATETIME gelijk, het verschil zit hem in de range die ze ondersteunen, die bij DATETIME veel kleiner is. [12] Voor ons maakt dit niet veel uit, aangezien we de minimale en maximale waarde gaan ophalen, en de eigenlijke mogelijke range van de kolom ons niet interesseert. Datatype FLOAT Dit datatype houdt vlottende komma-getallen bij in de MySQL database. Het volstaat in dit geval om de minimale en maximale waarden bij te houden. De verdeling van de waarden van deze kolommen zal immers weinig invloed hebben op de prestatie, ook omdat dit type niet zo vaak gebruikt wordt. Er wordt geen histogram bijgehouden. Datatype INTEGER Dit vaak voorkomende datatype houdt een geheel getal bij. We bespreken hier enkel het geval waarbij deze kolom gebruikt wordt om gewone getallen bij te houden. Het geval waarbij deze kolom gebruikt wordt als primary key of foreign key zullen we later beschouwen. Voor dit datatype wordt zoals bij het FLOAT datatype een minimale en maximale waarde opgeslagen. Een histogram wordt enkel opgeslagen als het om een foreign key gaat. Invloed op productieomgeving tijdens extractie Momenteel zal het opvragen van de statistische data op de productiedatabase queries veroorzaken die een relatief lange uitvoertijd hebben. Zo worden onder andere de histogram-


19

men volledig opgebouwd met behulp van één SQL query (om niet voor elke bin een query uit te moeten voeren). Deze ene query kan wel beduidende invloed hebben op de prestatie tijdens de uitvoering. Een mogelijke verdere optimalisatie kan erin bestaan om dit histogram op te bouwen aan de hand van een steekproef van de volledige data. Zo vermijden we dat hele tabellen moeten ingelezen worden, maar nemen we wel het risico dat het statistisch profiel minder accuraat is. Omdat dit voorlopig niet echt van belang is, zullen we hier verder niet op ingaan.

5.2.3

Statistisch profiel van relaties tussen tabellen

Bij het bevragen van tabellen spelen foreign keys vaak een grote rol, en dus zullen ze ook een grote invloed hebben op de prestatie van onze synthetische database. Daarom willen we de relaties tussen de tabellen zo goed mogelijk modelleren. Figuur 5.2 bevat een voorbeeld van wat we willen bereiken.


20

Figuur 5.2: Voorbeeld van anonimisatie: we starten met een gewone database, waarbij we zien dat Alice 3 foto’s heeft en Bob 1. Het histogram van die relatie zien we rechts. Onze bedoeling is dat histogram zo goed mogelijk na te bootsen. In de eerste stap wordt de algemene data geanonimiseerd. In de 2e stap gaan we ook de foreign keys anonimiseren. Dit gebeurt aan de hand van de nieuwe primary keys van de tabel Users, en we zorgen ervoor dat het histogram gelijk blijft.

Detectie van relaties tussen tabellen Vaak is niet alle informatie over interne relaties rechtstreeks beschikbaar. Zo is het mogelijk dat de programmeur van een applicatie een bepaalde kolom van een tabel als foreign key gebruikt, maar dit niet expliciet aangeeft in het databasesysteem. Dit komt bovendien zeer vaak voor, omdat de standaard storage engine van MySQL (MyISAM) geen foreign keys ondersteunt. Deze soort relatie zal spijtig genoeg dus niet worden opgevangen worden door gewoonweg het databaseschema te inspecteren. We stellen twee algoritmes voor om ook deze relaties op te sporen.


21

Detectie op basis van query trace log Indien we een trace log krijgen die queries bevat die uitgevoerd werden op de database, kunnen we deze analyseren en uit de verschillende JOIN-operaties die uitgevoerd worden tussen verschillende tabellen kunnen we gemakkelijk de verbanden tussen kolommen vaststellen, zoals in volgend voorbeeld: SELECT * FROM fotos INNER JOIN users ON users.UserId = fotos.userId WHERE users.name = ’Bob’ Hier zien we dat de tabel ’fotos’ samengevoegd wordt met de tabel ’users’ op het veld userId. Hieruit kunnen we concluderen dat er een link is tussen die 2 kolommen. Later zullen we dan moeten kijken aan de hand van het databaseschema en de inhoud van de database welke kolom de verwijzing bevat (foreign key) en welke kolom de waarde bevat waarnaar wordt verwezen (primary key). Deze methode is bijzonder handig indien de query trace log waarmee tests uitgevoerd worden samen met het databaseprofiel beschikbaar is. In dat geval kan die trace log onmiddellijk gebruikt worden om die relaties vast te leggen, die bij het testen van belang zullen zijn. Deze vorm van detectie is ge¨ımplementeerd in het raamwerk, maar op onze testset bracht deze methode niets op. Onze testdatabase maakt immers gebruik van sharding, waardoor er geen gebruik gemaakt wordt van JOINs. Sharding1 zorgt er voor dat data waarnaar verwezen wordt mogelijks niet lokaal aanwezig is en bijgevolg kan er geen JOINoperatie uitgevoerd worden met die data. Het gevolg is dat er in 1 query naar niet meer dan 1 tabel gerefereerd wordt. Hierdoor kunnen we met behulp van deze techniek geen bruikbare informatie halen uit onze query log. Hierna stellen we een andere methode voor die betere resultaten oplevert. Detectie op basis van statistische informatie en clustering Clustering is een manier om uit alle kolommen diegene te halen waarvan de naam en/of waarden sterk op elkaar lijken. Die kolommen worden dan ondergebracht in een cluster. De bedoeling is om kolommen te groeperen die met grote waarschijnlijkheid naar elkaar verwijzen. Die clusters van kolommen bevatten dan de foreign keys en de primary keys waarnaar we op zoek zijn. Elke cluster kan 2 of meer kolommen bevatten uit verschillende tabellen, maar soms ook meerdere kolommen uit dezelfde tabel. Eens de clusters vastliggen, moeten we in elke 1

Zie de verklarende woordenlijst voor meer uitleg over sharding


22

cluster precies één kolom kiezen die gebruikt zal worden als primary key. Het is die kolom waarnaar alle andere kolommen in de cluster verwijzen. Hoe weten we nu welke kolom uit de cluster de primary key is? Deze kolom is meestal (onderdeel van) de primary key in zijn tabel, maar een meer robuuste methode om deze kolom te kiezen is om die kolom te kiezen die het meeste waarden heeft, en waarvan de waarden bovendien uniek zijn. Het clusteren zelf gebeurt op basis van 3 eigenschappen van de kolommen, die hieronder in detail worden besproken. De 3 eigenschappen worden voor elke kolom vergeleken met elke andere kolom, en de scores hiervan worden opgeslagen. Vervolgens worden de scores via een gewogen gemiddelde samengebracht tot een eindscore. Indien de eindscore van twee kolommen zich boven een bepaalde drempelwaarde bevindt, dan zullen de kolommen samengenomen worden in een cluster. Het voordeel van het gewogen gemiddelde is dat de gewichten door de gebruiker kunnen meegegeven worden. In een bepaalde database kan één van de drie eigenschappen immers meer uitgesproken zijn dan in een andere database en op die manier kan de gebruiker hierop inspelen en betere resultaten verkrijgen bij het automatisch clusteren. Hieronder lijsten we de drie eigenschappen op: Eigenschap 1: Clustering op basis van naamgeving Kolommen die naar elkaar verwijzen zullen vaak dezelfde naam hebben of een naam die sterk op elkaar gelijkt (bijvoorbeeld userid” en from userid”). Kolommen waarvan de naam sterk op elkaar lijkt ” ” zullen een grotere kans hebben om in dezelfde cluster terecht te komen. Eigenschap 2: Clustering op basis van datatype Kolommen met verschillende datatypes zullen bijna nooit naar elkaar verwijzen. De waarden van bijvoorbeeld VARCHAR en INT kolommen zullen immers onder normale omstandigheden sterk verschillend zijn. Ook het bereik van de kolom kan ons informatie geven: de kans dat een TINYINT (van -128 tot 127) naar een INT (van -2147483648 tot 2147483647) verwijst is zeer klein, omdat de ene kolom veel minder waarden kan bevatten dan de andere. Omdat het in de praktijk bijna altijd INT kolommen zijn die als foreign keys gebruikt worden hebben we ervoor geopteerd ons tot die kolommen te beperken. Ook in onze test-database was dit het geval. Een mogelijke uitbreiding zou wellicht de CHAR-kolomtypes zijn, omdat die ook efficiënt gebruikt kunnen worden als foreign keys, zoals bijvoorbeeld voor de 2-letterige landcodes (BE, NL) Eigenschap 3: Clustering op basis van value ranges Als laatste eigenschap kijken we ook naar de waarden die de kolommen bevatten. In databases waarbij bovenstaande


23

eigenschappen niet sterk naar voor komen (bijvoorbeeld omdat er geen consistente naamgeving werd gebruikt), kan deze eigenschap het clusteren toch tot een goed einde brengen. Van elke kolom wordt opgezocht in de originele database wat de minimale en maximale waarden zijn die voorkomen. Aan de hand van deze 2 waarden kunnen we inschatten hoeveel twee kolommen overlappen. Hoe dichter de minimale en maximale waarden van kolommen bij elkaar liggen, hoe hoger hun score wordt. Manuele verificatie van clusters Nadat de clusters zijn gevormd, is er nog een manuele verificatie nodig. Hierbij krijgt de gebruiker in een grafische gebruikersinterface een lijst van alle clusters te zien. De gebruiker kan op elke cluster doorklikken om een gedetailleerd overzicht te zien van alle kolommen die de cluster bevat en de eigenschappen van die kolommen. De kolommen die niet in clusters opgedeeld zijn, worden apart weergegeven of kunnen manueel ondergebracht worden in een bestaande cluster. Omzetting van clusters naar foreign keys Nadat de gebruiker alle clusters heeft gecontroleerd, wordt de omzetting naar foreign keys uitgevoerd. Hiervoor moeten we één van de kolommen binnen de cluster aanduiden als primary key, en de anderen dan foreign keys maken die verwijzen naar die primary key. Er kunnen zich verschillende gevallen voordoen: Als slechts één van de kolommen in een cluster de primary key van een tabel is, duiden we deze aan als primary key van de cluster. Dit zou het meest voorkomende geval moeten zijn, maar dat bleek niet het geval in onze database. Als meerdere kolommen primary keys zijn van tabellen, zullen we daar één uit kiezen. Dit is bijvoorbeeld mogelijk als er een tabel opgesplitst werd (bijvoorbeeld om gevoelige data zoals creditcard-gegevens van een gebruiker in een aparte tabel op te slaan)

Indien deze methoden nog geen primary key van de cluster aangebracht hebben, zullen we die kolom kiezen die het grootste aantal unieke waarden bevat. In principe moet dit de juiste keuze zijn, aangezien de kolom die de primary key is waarden kan bevatten waarnaar nog niet verwezen wordt door foreign keys, maar omgekeerd kan een foreign key niet verwijzen naar onbestaande rijen. Het aantal unieke waarden in een primary key zal dus steeds groter dan of gelijk zijn aan het aantal unieke waarden van een foreign key.


24

Figuur 5.3: Voorbeeld van clustering: op basis van naam en datatype kunnen de 3 bovenste kolommen samengenomen worden. Als we ook de range bekijken zien we een verband tussen de kolommen AlbumId en Id.

Opslag van relaties tussen tabellen in het databaseprofiel Histogram van foreign keys Eens de foreign keys bekend zijn met behulp van de bovenstaande methodes, worden er histogrammen opgesteld die de multipliciteit van de relaties in kaart brengen. Een voorbeeld: als een gebruiker in de originele database gemiddeld 100 foto’s heeft, en maximaal 1.000, zullen wij ervoor zorgen dat dit in de synthetische database ook het geval is, tot op zekere nauwkeurigheid. Dit is mogelijk omdat deze informatie vervat zit in het histogram van de multipliciteit van de relatie. Momenteel gebruiken we voor dit histogram een maximum van 20.000 uniform verdeelde bins. Detectie van cyclische sleutels Een belangrijke moeilijkheid die we ondervonden bij het clusteren was de vorming van cyclische sleutels. Wat zijn cyclische sleutels? Dit kan gemakkelijk ge¨ıllustreerd worden aan de hand van het kip of ei” probleem: als tabel A ” een kolom heeft die naar een kolom van tabel B verwijst, en tabel B heeft een kolom die naar een andere kolom van tabel A verwijst, hebben we cyclische foreign keys. Aangezien we in ons algoritme tabel per tabel zullen invullen creëert dit een moeilijkheid. Welke kolom wordt eerst ingevuld? De verwijzing kan in geen geval gelegd worden omdat de andere rij nog niet bestaat. Dit is een fenomeen dat normaal gezien niet vaak voorkomt in een database (omdat het redundante informatie introduceert) en daarom bieden we er ook geen support voor. Het is mogelijk dat sommige databases dit soort foreign keys wel gebruiken. In dat geval zal een meer geavanceerd algoritme moeten gebruikt worden om de tabellen op te vullen. Een meer geavanceerd algoritme kan bijvoorbeeld achteraf, wanneer de tabellen ingevuld zijn met data, een cyclische foreign key aanmaken.


5.3

25

Automatisch ophalen van het statistisch profiel

Om de eerste stap te automatiseren hebben we een extractietool gemaakt in Java. De tool kan lokaal op de productiedatabase server gedraaid worden of vanop een computer die SSH toegang kan verkrijgen tot de databaseserver. Eens de connectie met de databaseserver is opgezet kan het databaseschema van de originele database opgehaald worden.

5.4

Conclusie

In dit hoofdstuk werd de extractie van het databaseprofiel beschreven. We slagen erin om de structuur van de database in kaart te brengen en op te slaan. Verder bevat het profiel ook nog metadata voor elke kolom. De precieze metadata hangt af van het datatype van de kolom. Tenslotte bevat het profiel ook informatie over de relaties tussen tabellen. Aangezien die vaak niet zomaar voorhanden zijn werd een algoritme voorgesteld dat erin slaagt om de relaties tussen de tabellen automatisch bloot te leggen. De extractie van het databaseprofiel is hiermee voltooid.

26

Hoofdstuk 6 Genereren van de synthetische database 6.1

Synthetische databases

Een synthetische database is een database die zo waarheidsgetrouw mogelijk aanleunt bij een bepaalde originele database. Ze wordt opgebouwd aan de hand van een statistisch profiel dat zo compact mogelijk de statistische eigenschappen van de originele database bevat. Met behulp van deze statistieken zullen we alle tabellen één voor één construeren en opvullen met data. Het eindresultaat is een database die dezelfde grootte heeft, maar random data bevat die de statistische eigenschappen heeft van de originele database.

6.2 6.2.1

Opbouw synthetische database Algoritme voor het invullen van data volgens kolomtype

Opvulling van string-kolomtypes: CHAR, VARCHAR, TEXT In MySQL zal de inhoud van een string slechts een invloed hebben op de uitvoeringstijd als er echt in de string zelf moet gekeken worden. Dit is het geval als de functie LIKE, NOT LIKE, of CONTAINS (op een slechte manier) wordt gebruikt. In onze toepassing was dit echter bijna nooit het geval. Dat is logisch, omdat het niet wenselijk is om 1 miljoen strings te vergelijken elke keer we een naam opzoeken in de database. Er kan immers gebruik gemaakt worden van indices die bij een opzoeking op dergelijke grote tabel nodig zijn om een goede prestatie te kunnen garanderen. Zo hebben we vastgesteld dat

HOOFDSTUK 6. GENEREREN VAN DE SYNTHETISCHE DATABASE

27

zo goed als alle kolommen waarop gezocht werd een index hadden. Op die manier wordt een goede prestatie gegarandeerd voor grote tabellen. Het gevolg hiervan is dat we om het even welke random strings kunnen gebruiken om in te vullen in de string-type velden. We hebben ervoor gekozen om bij alle string-kolomtypes een willekeurige sequentie van alfanumerieke tekens in te vullen. In het geval van CHAR-datatypes zal de ingevulde string steeds van dezelfde lengte zijn. Bij TEXT-velden heeft de (vaak lange) lengte een grote invloed op de grootte van de database, omdat deze velden meestal de grootste in een database zijn. Om de grootte van de originele database zo goed mogelijk te kunnen benaderen zullen we teksten van een bepaalde lengte invullen volgens het histogram dat we hebben opgesteld. Het invullen van VARCHAR-kolommen verloopt analoog aan het invullen van TEXT-velden. Opvulling van ENUM-kolomtypes Hierbij zullen we een van de mogelijke waarden kiezen die ingevuld waren in de originele database. De kans dat een bepaalde waarden wordt gekozen bepalen we aan de hand van de verdeling in de originele database. Opvulling van SET-kolomtypes De implementatie van dit type verloopt analoog aan het ENUM-datatype Opvulling van DATE-kolomtypes Bij een date zullen we de lege datum (0000-00-00) evenveel trachten te laten voorkomen als in de originele database. Voor de andere velden zullen we een willekeurige datumwaarde uit de originele range nemen. Opvulling van TIMESTAMP-kolomtypes Verloopt analoog aan het DATE datatype, maar dan met uren, minuten en seconden inbegrepen. Opvulling van FLOAT-kolomtypes Hierbij vullen we een willekeurige waarde tussen het minimum en maximum van de originele database in.


28

Opvulling van INTEGER-kolomtypes Dit is het belangrijkste datatype, omdat de meeste velden waarop gezocht wordt van dit type zijn. In het geval dat dit veld geen foreign key is, zal net zoals bij FLOAT-velden een willekeurige waarde tussen minimum en maximum gekozen worden. Indien het wel een foreign key betreft gaan we op een speciale manier te werk die we in sectie 6.2.5 in detail zullen bespreken.

6.2.2

Algoritme voor de volgordebepaling van het invullen van tabellen

De tabellen worden één voor één opgevuld zodanig dat tabellen die foreign keys bevatten pas ingevuld worden na de tabellen waarnaar ze refereren. Op die manier is de benodigde data voor de huidige tabel steeds beschikbaar. Hierbij zorgt een cyclische sleutel er voor dat het algoritme vast raakt, vandaar dat we dit niet toelaten. De lijst met tabellen wordt overlopen tot alle tabellen ingevuld zijn, en per iteratie wordt nagekeken of nieuwe tabellen ingevuld waren. Indien er na 1 iteratie van de overblijvende tabellen geen enkele tabel ingevuld werd, zit het algoritme vast in een oneindige lus door een cyclische sleutel en zal de applicatie een foutmelding geven en stoppen.

6.2.3

Verdere optimalisaties

Een belangrijke optimalisatie bestaat erin om het updaten van indices uit te schakelen in het databasesysteem, zoniet worden na elke INSERT-operatie alle indices onnodig aangepast. Wanneer de tabel volledig is ingevuld schakelen we het herbouwen van de indexen terug aan. Het eerste deel van een INSERT-query is steeds hetzelfde voor een bepaalde tabel en bevat alle velden. Deze string maken wordt op voorhand gegenereerd zodat deze opnieuw gebruikt kan worden voor elke query. Oorspronkelijk werden meerdere INSERT-operaties in batch uitgevoerd in 1 query, maar dit was niet houdbaar omdat het afhandelen van fouten te complex werd. Bovendien was de prestatiewinst door deze optimalisatie verwaarloosbaar.

6.2.4

Foutafhandeling

De volgende maatregelen worden getroffen indien een fout gemeld wordt. Indien het een waarschuwing betreft wordt geen actie uitgevoerd. (dit kan voorkomen als we een lege string in een ENUM veld invoegen). Indien dit niet het geval is, zal het bijna altijd


29

een conflict zijn dat zich voordoet op één van de unique of primary constraints. Meestal is dit door toeval, en wordt er opnieuw geprobeerd met nieuwe waarden. Soms kan het echter voorkomen dat de fout zich blijft herhalen, omdat alle mogelijke (of een groot aantal) combinaties van waarden reeds gebruikt zijn. De oplossing die we hiervoor ge¨ımplementeerd hebben bespreken we in sectie 6.2.6.

6.2.5

Algoritme voor het genereren van Foreign key waarden voor Integer type kolommen

De oorspronkelijke implementatie van het framework haalde telkens de benodigde waarden op, maar dit vertraagde het invullen, en data die we ingevuld hebben later weer ophalen leek ons niet de optimale werkwijze. Daarom zijn we overgestapt naar een betere methode: de foreign key waarden die zullen worden gebruikt lokaal in het geheugen opslaan. Dit maakte het invullen van tabellen soms dubbel zo snel, in totaal gaf het een speedup factor van ongeveer 10 %. Een mogelijk risico hierbij was het geheugengebruik, maar uit tests bleek dat zeer goed mee te vallen, omdat we de foreign keys als primitieve longs in Java kunnen opslaan. Voor een kolom van onze grootste tabel (2.5 miljoen rijen) was er slechts 17 MB geheugen nodig. Aangezien er slechts een twintigtal kolommen zijn waarnaar er verwezen wordt, is er dus geen gevaar, zelfs bij het maken van grotere databases. Bij het invullen van een tabel die foreign keys bevat zullen we eerst bepalen welke foreign key-waarden we in de foreign key-kolommen zullen plaatsen. Dit doen we aan de hand van een algoritme dat snel een willekeurige deelverzameling uit de verzameling van waarden van de tabel waarnaar verwezen wordt kan halen. Hieronder de drie mogelijke scenario’s en hun oplossingsmethodes in het framework: 1. Er zijn meer unieke foreign keys nodig dan er unieke primary key waarden zijn. Dit zal nooit voorkomen na juiste toepassing van het clustering algoritme, omdat we als primary kolom die kolom kiezen met het grootste aantal unieke waarden. 2. Er zijn beduidend minder foreign keys nodig dan er primary keys zijn. In dit geval vertrekken we van een lege set foreign keys en zullen we telkens een willekeurige waarde uit de lijst van de kolom waarnaar verwezen wordt selecteren. Na verificatie dat we deze waarde niet al toegevoegd hebben aan onze set van foreign keys, voegen we ze toe aan de set. 3. Er zijn iets minder foreign keys nodig dan er primary keys zijn. In dit geval gaan we starten van een kloon van de waarden van de kolom waarnaar verwezen wordt, en


30

daar dan willekeurig elementen eruit verwijderen. Uit tests bleek dat het optimale punt om methode 2 of methode 3 te gebruiken allesbehalve in het midden lag: methode 3 bleek maar sneller te werken wanneer we meer dan 96 tot 98 procent van de foreign keys ophaalden (bij tests met tussen de 200.000 en 1.000.000 foreign keys). De reden hiervoor is omdat in Java een lijst herbouwd moet worden nadat er een element uit verwijderd werd. Een mogelijke optimalisatie hierbij is het gebruiken van een gelinkte lijst in plaats van een gewone lijst, maar methode 2 bleek zo efficiënt dat dit ons niet nodig leek. Hieronder wordt verder uitgelegd hoe deze methode nog verbeterd kan worden. Verdere optimalisaties Eens we de lijst hebben van foreign keys die we gaan gebruiken, gaan we op voorhand bepalen hoeveel keer elke foreign key mag voorkomen. Dit doen we door een tweede lijst, de aantallenlijst aan te maken van dezelfde lengte als de eerste lijst, met daarin het aantal keer dat deze sleutels voorkomen. Deze aantallen zullen we bepalen aan de hand van het histogram van de foreign keys dat we hebben opgesteld. Bij elke vraag naar een anonieme waarde zullen we dan 1 van die waarden teruggeven. Wanneer de query succesvol verlopen is, zullen we het betreffende item in de aantallenlijst met 1 verminderen. Deze methode heeft een belangrijk nadeel. Doordat we random een waarde uit de lijst met unieke waarden selecteren, zullen waarden die minder moeten voorkomen snel opgebruikt zijn en op het einde zal het programma steeds dezelfde waarde proberen invullen. Als er in de tabel nu meerdere foreign keys zijn en er een unique constraint bestaat op die kolommen, zal het programma steeds op dezelfde unique constraint botsen. Om dit te vermijden moeten we dus zorgen dat tijdens het invullen van de tabel een foreign key-waarde een kans heeft om gekozen te worden die ook proportioneel is aan zijn voorkomen. Op die manier wordt de volgorde beter gespreid en is het makkelijker om de constraints te vervullen. Dit vereistte iets meer geheugen, maar deze methode bleek uiteindelijk sneller dan onze eerste (minder correcte) methode. Foutafhandeling Indien er tijdens het invullen van een tabel meerdere fouten voorkomen, en we foreign keys aan het invullen zijn, gaan we gaan kijken of er nog genoeg verschillende foreign keys beschikbaar zijn. Het is immers mogelijk dat de verzameling van foreign keys zo klein is geworden dat er steeds sleutels gekozen worden die al in de database zitten. Dit kan in het


31

geval van een unique constraint ervoor zorgen dat er geen rijen meer ingevuld raken. Om die reden zal dan de verzameling van foreign keys gereset worden. In de praktijk proberen we dit steeds te vermijden en zal dit bijna nooit gebeuren als de methodes uit de volgende paragraaf gebruikt worden.

6.2.6

Oplossen van conflicten bij het invullen van de tabellen

Het belangrijkste probleem waarop we botsten bij het invullen van de tabellen was het schenden van UNIQUE en PRIMARY constraints. Vaak werkt het invullen van willekeurige waarden niet goed omdat er strenge UNIQUE constraints zijn. Het oplossen van deze problemen op een zeer algemene manier was erg complex. Onze oplossing is als volgt. We beginnen met alle kolommen op de hoogte te brengen van het aantal waarden dat zal worden ingevuld. Daarna gaan we alle auto-increment velden overlopen en bij enkele deze auto-increment eigenschap uitschakelen. De reden hiervoor is omdat een auto-increment eigenschap niet bindend is: deze kan overschreven worden. Dit was ook het geval in veel tabellen van onze database, en dus moeten we zorgen dat dit ook zo is in de synthetische database. Hierna begint de stap waarin we gaan kijken waar er conflicten kunnen optreden door UNIQUE of PRIMARY constraints. Hiervoor zullen we alle UNIQUE en PRIMARY keypools overlopen, en degene eruit pikken die de hoogste kans hebben op conflicten. Dit doen we door het aantal mogelijke waarden te vergelijken met het aantal waarden dat we moeten invullen. Nu we de juiste kolommen kennen gaan we ook na of die kans groot genoeg is om ons zorgen te maken. Indien dit het geval is, gaan we in een modus die we de UNIQUE-veilige modus noemen. Een voorbeeld hiervan is te zien in figuur 6.1. We duiden 1 van de kolommen aan als ’wortelkolom’, dit is degene waarvan de waarden meest zullen variëren. Van de andere kolommen halen we alle mogelijke waarden op, en die waarden voegen we dan samen in een lijst, via een kruisproduct. Voor 2 kolommen die respectievelijk 20 en 3000 verschillende waarden hebben, levert ons dat een lijst van 20x3000 entries op. Bij het invullen zullen we dan één voor één willekeurige waarden uit die lijst nemen, en indien de lijst meer dan half leeg is wordt ze gereconstrueerd om voldoende willekeurigheid te garanderen. Om dit algoritme goed te kunnen laten werken is het noodzakelijk dat gelijke waarden van de wortelkolom na elkaar worden ingevuld, ook als die een foreign key is. Om te bewijzen dat de volgorde waarin records ingevoegd worden nauwelijks van invloed is op de opgemeten prestatie werd volgende test uitgevoerd. De originele databank werd record voor record gekopieerd naar een nieuwe database. Daarna werd op deze nieuwe


32

Figuur 6.1: Voorbeeld van de Unique-veilige modus: we zien dat bij het invullen van de tabel, er een zeer grote kans is op conflicten tussen het veld UserId en de velden InteresseId en Geslacht. Wanneer er bijvoorbeeld een gebruiker al 990 keer is ingevuld, is de kans dat we een combinatie van InteresseId en Geslacht kiezen die nog niet voorkomt: (1002-990)/1002 = 1,1%. We zullen dus gemiddeld 90 keer opnieuw moeten proberen om tot een van die combinaties te komen. Om die reden zullen we die 1000 UserId’s na elkaar invullen en een lijst bijgehouden worden van welke InteresseId’s en Geslachten er al ingevuld zijn.

database een prestatietest uitgevoerd. In een volgende stap werd de originele databank opnieuw record voor record gekopieerd, maar deze keer werden de records in willekeurige volgorde gekopieerd naar de nieuwe database. Opnieuw werd een prestatietest uitgevoerd. De prestatie bleek nagenoeg gelijk voor beide gevallen. Dit komt grotendeels omdat bijna alle queries gebaseerd zijn op het gebruik van indices. Er zijn bijna geen queries te vinden die een tabel volledig zullen overlopen. Bijgevolg heeft de volgorde van records een verwaarloosbare invloed op de prestatie. Uiteraard is het mogelijk dat het aantal mogelijke waarden van de niet-wortelkolom kolommen erg groot wordt. Als het totaal aantal mogelijke waarden van die kolommen groter is dan 200.000, zullen we toch niet in de veilige modus gaan. Dit levert geen problemen op, aangezien er slechts grote kans op conflicten is als er een klein aantal mogelijke waarden is. In eerste instantie hadden we dit enkel ge¨ımplementeerd voor de PRIMARY kolommen, maar bij sommige tabellen bleken UNIQUE constraints veel strenger te zijn dan de PRIMARY constraint. In principe zou zo een systeem uitgebreid kunnen worden naar alle mogelijke UNIQUE constraints, maar voor onze toepassing was dit niet nodig.


6.3

33

Genereren van synthetische query log

Om de prestatie te testen van onze database beschikken we over een query trace log, die een groot aantal queries bevat (8379 in totaal). Omdat de synthetische database enkel willekeurige data bevat, is het niet langer mogelijk om gewoonweg dezelfde trace log af te spelen. Als er gezocht wordt naar data in een bepaalde kolom zal die data hoogstwaarschijnlijk niet eens meer in die kolom zitten. Om dit probleem op te lossen, worden de queries voor uitvoering aangepast. We kijken op welke kolommen er gezocht wordt, en de waarden vervangen we door waarden die echt bestaan in de database. Uiteraard is het soms mogelijk dat er waarden gezocht wordt die niet in de database zitten, maar omdat dit meestal niet het geval zal zijn, hebben we ervoor gekozen de waarden altijd te vervangen. Het is immers niet mogelijk zomaar de originele trace log afspelen op de originele server om te kijken hoeveel rijen er teruggegeven worden. Indien het aantal teruggegeven rijen in de trace log aanwezig zou zijn, kan die informatie wel gebruikt worden om dit uit te breiden. We bieden support voor het aanpassen van zo goed als alle verschillende soorten queries die op één tabel van toepassing zijn, hieronder enkele voorbeelden van het type queries dat zal moeten aangepast worden. In onderstaande queries zullen telkens de numerieke waarden aangepast moeten worden. SELECT DELETE SELECT UPDATE INSERT

* FROM users WHERE userid != ’1234’; FROM users WHERE userid = ’1234’; * FROM users WHERE userid IN (1234, 2345, ’3456’); users SET name=’alice’ WHERE userid=’1234’ (DELAYED) INTO users (’userid’, ’id’) VALUES (’1234’, ’0’);

In het geval van een INSERT slaan we de waarden die in de tabel ingevoegd werden op. Indien er later voor die tabel op die waarde wordt gezocht, zullen we die vervangen door de waarde die we ingevoegd hebben. Opmerkingen Het kiezen van een vervangingswaarde wordt willekeurig gedaan. Wel is het belangrijk op te merken dat we kiezen uit de lijst van unieke waarden, en niet uit de volledige (nietunieke) waardenset. Dit heeft tot gevolg dat waarden die veel voorkomen geen grotere kans gekozen te worden hebben dan waarden die minder voorkomen. We hebben voor deze methode gekozen omdat we ervan uit gaan dat alle waarden dezelfde kans hebben


34

om opgezocht te worden (onafhankelijk van hoeveel keer die erin zit). Als dezelfde waarde meerdere keren wordt opgezocht in de trace log omdat ze zeer populair is, zal deze ook steeds door dezelfde waarde vervangen worden. De kans bestaat nu dat we een waarde die weinig voorkomt vervangen door een waarde die zeer veel voorkomt, waardoor de query op de synthetische database een stuk langer zal duren dan op de originele database, omdat die meer resultaten moet teruggeven. Ook is het omgekeerde geval mogelijk, op de originele database wordt een query uitgevoerd die zeer veel rijen teruggeeft, en op de synthetische database slechts een paar. Dit effect werd in ons geval wel wat beperkt omdat er nooit meer dan 500 rijen opgevraagd werden. Een bijkomend probleem doet zich voor wanneer er meerdere voorwaarden in het WHERE-gedeelte van de query zitten, zoals volgend voorbeeld illustreert, het betreft hier een tabel met foto’s die van een bepaalde gebruiker zijn, en een bepaald type hebben. SELECT * FROM fotos WHERE userid=1 AND type=’landschap’ Als de gebruiker met userid 1 in de originele database enkel maar foto’s heeft van het type ’landschap’, kunnen we deze eigenschap niet garanderen in de synthetische database wegens de verregaande randomisatie. Om dit toch te kunnen bereiken zouden we moeten bijhouden welke gebruiker wat soort foto’s heeft, en dus correlaties tussen kolommen opslaan. Dit probleem wordt snel complex, niet alleen omdat het kwadratisch is (alle kolommen moeten met alle andere kolommen vergeleken worden), maar ook omdat voor elke kolomwaarde apart gekeken moet worden wat de verdeling is van de andere kolommen. Dit zou er dus voor zorgen dat de grootte van ons statistisch profiel met meerdere grootteordes stijgt, en ook voor een deel teniet doen aan de anonimisatie. Het is dus niet eenvoudig om zonder voorkennis van de resultaten van queries te garanderen dat queries op de synthetische database gelijkaardige resultaten teruggeven. Gemiddeld gezien over vele queries zal dit wel ongeveer gelijk lopen zodat trends in prestatie nog steeds duidelijk zullen zijn.

35

Hoofdstuk 7 Validatie 7.1

Query trace afspelen en opmeting van prestatie

Om het succes van de synthetische database gebaseerd op een statistisch profiel te verifiëren zullen we een kopie van een database gebruiken uit een echte productieomgeving. Hiervan maken we met behulp van onze tools een statistisch profiel. Daarna maken we een synthetische database aan op basis van dit bestand. Tenslotte vergelijken we de responstijden van de originele queries op de originele database met de responstijden van de synthetische queries op de synthetische database.

7.1.1

Afspelen met behulp van uniforme interarrivaltijd

In de meest eenvoudige tests zullen we de volledige query log afspelen met een tussenpauze van 10 ms per query. Als een query langer dan 10 ms duurt, wordt er gewacht tot de query is afgelopen om de volgende query af te voeren. Zo vermijden we dat er al te veel contentie wordt veroorzaakt door overlappende queries. We noteren hierbij dat het meestal niet mogelijk is om volledig te vermijden dat queries overlappen in de tijd. Zo zullen sommige INSERT queries direct de controle teruggeven aan degene die de query uitvoerde en zal het lijken alsof de query werd uitgevoerd. In de realiteit wordt de query pas later in de achtergrond afgerond. Dit is perfect mogelijk, omdat de data die net werd ingevoegd mogelijks niet direct nodig is. Het gevolg van dit soort gedrag is dat er dus wel contentie kan optreden zonder dat de applicatie dit expliciet introduceert.

HOOFDSTUK 7. VALIDATIE

36

Figuur 7.1: Schema van onze serveropstelling: Server A doet de timing, en voert de queries uit op server B, die de database bevat.

7.1.2

Invloed van externe factoren

Om de prestatievergelijking goed uit te voeren moeten we ervoor zorgen dat externe factoren zoals hardware en software geen invloed uitoefenen op de resultaten. We zorgden ervoor dat de tests altijd uitgevoerd worden op dezelfde machines, zowel voor originele als synthetische database. Op die manier kan de hardware-keuze geen invloed meer hebben op de testresultaten. Verder zullen we ook invloeden van cache proberen wegwerken door het leegmaken van de MySQL query cache en het leegmaken van de disk caches in Linux. Volgende commando’s werden hierbij gebruikt: Leegmaken MySQL query cache: RESET QUERY CACHE Leegmaken Linux disk cache: umount van het bestandssysteem, daarna mkfs om een nieuw bestandssysteem aan te maken, daarna mount om het nieuwe bestandssysteem te gebruiken

Om de invloed van overlappende queries te bestuderen introduceren we hierna het gebruik van Poisson interarrivaltijden.

7.1.3

Afspelen met behulp van Poisson interarrivaltijd

Om een echte productieomgeving verder te evenaren, zullen we de queries afspelen met behulp van een Poisson interarrival proces. De tussentijden tussen 2 queries zijn telkens exponentieel verdeeld. Als gevolg hiervan zullen queries soms afgespeeld worden wanneer vorige queries nog aan het uitvoeren zijn. Het Poisson interarrival proces zal ervoor zorgen dat er soms meerdere queries zeer kort na elkaar moeten uitgevoerd worden, terwijl er op


37

andere momenten relatief langere tussenpauzes worden ingelast. Dit is meer vergelijkbaar met wat er in een echte databaseomgeving gebeurt. Doordat queries in deze opstelling vaak zullen overlappen in de tijd zal er meer contentie optreden bij het uitvoeren van de queries. De uitvoeringen van de queries zullen elkaar meer en meer negatief be¨ınvloeden naarmate er meer contentie is. Hierdoor zal waarschijnlijk ook de variantie van de responstijden verhogen omdat de interactie van queries met elkaar onvoorspelbaar wordt. In een Poisson proces komen de queries toe met een rate van lambda. De interarrivaltijdtijd is exponentieel gedistribueerd met dezelfde parameter lambda. Hoe groter de lambda wordt, hoe kleiner de gemiddelde tijd tussen twee queries en hoe groter de contentie zal worden. In hoofdstuk 8 stellen we de resultaten voor die de voorgaande stellingen in verband met uitvoeringstijden experimenteel bevestigen.

7.2

Manuele prestatieanalyse

Om de resultaten van de prestatietests te analyseren, zullen we verschillende visualisaties gebruiken. Het doel is altijd om te zien hoeveel en welk type queries zich correct gedragen en welke niet. Met correct gedrag bedoelen we een query die een uitvoeringstijd op de originele database heeft die statistisch niet onderscheidbaar is van de uitvoeringstijd op de synthetische database. Wanneer dit niet zo is moeten we de oorzaak hiervan gaan zoeken. Aangezien er zeer veel verschillende factoren zijn in een databaseomgeving is het niet altijd eenvoudig om onmiddellijk een oorzaak aan te wijzen. Vaak zullen meerdere experimenten nodig zijn om de precieze oorzaken te isoleren. Bij de analyse van de resultaten werden naast het vergelijken van de uitvoeringstijden, ook volgende methodes en tools gebruikt:

7.2.1

Vergelijking van resultatenset

Ook de grootte van de resultatenset is belangrijk. Indien er in de database gezocht wordt naar gebruikers die aan een bepaald criterium voldoen, en er worden 50 gebruikers teruggegeven, maar op de synthetische database zijn dat er 20, of 0, of 100, dan zal dat zijn invloed hebben op de responstijd. De oorzaak hiervan kan zijn door het random karakter van de data, maar als er op grote schaal een trend in de verkeerde richting is kan dit op deze manier gedetecteerd en eventueel opgelost worden.


7.2.2

38

Invloed van query plan

Het query plan dat opgesteld wordt door het database management systeem heeft een grote invloed op de uitvoeringstijd van de query. Het queryplan bevat immers het stappenplan dat MySQL zal doorlopen om een antwoord te geven op de query. Zo staat hierin beschreven welke indices gebruikt zullen worden bij de uitvoering. Dit heeft dus grote invloed op het totaal aantal keren dat het systeem zal moeten lezen in het bestandssysteem en dus op de uitvoeringstijd. Indien het queryplan op de originele database anders is dan op de synthetische database zal de uitvoeringstijd waarschijnlijk drastisch verschillen. Afwijkingen ten gevolge van indexkeuze Hoe kan het nu dat dit queryplan niet identiek is op de database die qua structuur volledig identiek is? Het antwoord is dat het queryplan ook afhankelijk is van de data die zich op dat moment in de database bevindt. Als een bepaalde tabel bijvoorbeeld meer dan 1 index bevat zal MySQL bij sommige queries moeten kiezen tussen de twee indices. Soms is het mogelijk om beide te gebruiken bij de optimalisatie van een query. De keuze tussen de twee is gebaseerd op statistieken die worden verzameld en opgebouwd tijdens het gebruik van de database. De precieze details zijn afhankelijk van de storage engine die gebruikt wordt. Door MyISAM wordt voor elke index het aantal unieke waarden van de index opgeslagen, wat een idee geeft over de grootte van de index. Als deze statistiek niet gelijkaardig is op de twee databases kan het zijn dat in sommige gevallen een andere index gekozen wordt in de synthetische database, en dus een ander queryplan wordt opgesteld. Dit veroorzaakt een groot verschil in uitvoeringstijd. Dit zou echter niet mogen, omdat het statisch profiel deze eigenschappen goed modelleert voor de meeste gevallen. Dit was dus een manier om te verifiëren dat ons profiel de correcte statistische eigenschappen had. Indexkeuzemechanisme In welke gevallen schiet het model nu tekort? Soms zullen indices meerdere kolommen van de tabel beslaan. Hetzelfde mechanisme blijft behouden, de keuze tussen twee indices die kunnen gebruikt worden zal nog steeds gemaakt worden met behulp van deze statistieken. Deze statistiek is nu echter niet zomaar een statistiek meer die iets vertelt over één specifieke kolom, maar over meerdere kolommen tegelijk. De correlatie tussen meerdere kolommen zal hier dus een grote invloed op hebben. Deze tweede orde statistieken worden niet opgenomen in ons databaseprofiel. Dit zou het profiel veel complexer maken doordat de correlatie tussen alle kolommen van tabel in acht genomen moet worden (en eigenlijk ook


39

met kolommen van de gerelateerde tabellen). Dit zou explosief veel rekenkracht en data vereisen voor grotere tabellen. Opvangmechanisme Gelukkig komt dit slecht gedrag enkel voor wanneer een tabel meerdere indices heeft die beiden meerdere kolommen beslaan, maar die ook kolommen gemeenschappelijk hebben. Eventueel zouden we dit kunnen opvangen door enkel voor de kolommen die in de indices voorkomen een correlatiestatistiek te berekenen en die op te nemen in het databaseprofiel.

7.2.3

Opvragen query plan in MySQL

Om het query plan in MySQL te analyseren kan men het EXPLAIN commando gebruiken. Dit commando geeft voor elke query weer hoeveel rijen waarschijnlijk zullen gelezen moeten worden om het resultaat te bekomen, en ook welke indices al dan niet zullen gebruikt worden bij het uitvoeren. We geven een voorbeeld: EXPLAIN SELECT COUNT(*) FROM 1_NOTIFICATIONS WHERE userID = 51182087 AND isdeleted = ’NO’ AND isvisited = ’NO’; Deze query vraagt vermoedelijk het aantal ongelezen meldingen op van een bepaalde gebruiker. De EXPLAIN query geeft volgende resultaten terug op de originele database: Mogelijke sleutels: PRIMARY, idx_userid_isdeleted_isvisited_dateadd, idx_isdeleted, idx_isvisited_datevisited Gekozen sleutel: idx_userid_isdeleted_isvisited_dateadd Gebruikte sleutellengte: 6 bytes

Voor de synthetische database geeft de EXPLAIN query volgende resultaten: Mogelijke sleutels: PRIMARY, idx_userid_isdeleted_isvisited_dateadd, idx_isdeleted, idx_isvisited_datevisited Gekozen sleutel: PRIMARY Gebruikte sleutellengte: 4 bytes


40

In dit geval, dat gelukkig niet vaak voorkomt, werd de verkeerde sleutel gekozen. De reden voor de afwijkende keuze is het afwijken van tweede orde statistieken. In dit geval wordt in de synthetische databank de voorkeur gegeven aan de PRIMARY sleutel. De resterende kolommen worden daarna sequentieel gefilterd. Als de gebruiker nog niet veel meldingen heeft gekregen kan dit ook efficiënt zijn. In de originele database wordt de sleutel idx_userid_isdeleted_isvisited_dateadd gebruikt. Deze sleutel bevat ook een datum veld, dit deel van de sleutel wordt niet gebruikt. Dit kunnen we zien aan de hand van de gebruikte sleutellengte (4 bytes voor de userID int + 1 byte voor de boolean isdeleted + 1 byte voor de boolean isvisited). Als de gebruiker veel meldingen heeft zal deze methode sneller zijn. De meeste gebruikers zullen waarschijnlijk na verloop van tijd veel meldingen hebben, omdat de meldingen niet verwijderd worden. Als er op deze shard (of partitie) van de database veel nieuwe gebruikers zitten kan het dus zijn dat de eerste methode wordt gekozen. Na verloop van tijd zal de tweede methode de bovenhand krijgen en automatisch verkozen worden.

7.3

Automatisering prestatieanalyse

Om bovenstaande analysemethodes niet manueel te moeten uitvoeren voor elke query moesten ze geautomatiseerd worden. Het opslaan van de resultaten set werd ingebouwd in de prestatietesttool. Op deze manier is het eenvoudig om na te gaan of er op dit niveau iets mis gaat bij bepaald types queries. Vervolgens werd ook de query plan analyse geautomatiseerd door in een aparte tool het query plan op te vragen van de alle queries in de trace log op de originele database en op de synthetische database. Daarna wordt automatisch een tabel opgesteld die de query bevat, alsook de indices die gebruikt worden bij beide databases. De gevallen waar de indices niet overeenkomen zijn ook hier eenvoudig op te sporen.

41

Hoofdstuk 8 Experimentele resultaten 8.1

Originele testset

De testset bestaat uit een gedeeltelijk (manueel) geanonimiseerde database uit de productieomgeving van een Web 2.0 toepassing met meer dan 90 miljoen gebruikers. Om de database schaalbaar te houden werd een sharding systeem ingevoerd waarbij gebruikers aan de hand van hun gebruikersnummer ingedeeld worden bij een bepaalde server. De data van een gebruiker wordt daarna op die server opgeslagen. Bij dit systeem is het niet mogelijk om JOINs uit te voeren omdat niet alle data lokaal beschikbaar is. Deze logica wordt dus verplaatst naar applicatieniveau. Dit zorgt er ook voor dat de native foreign keys van InnoDB (in MySQL) niet zomaar meer kunnen gebruikt worden, omdat data waarnaar gerefereerd wordt mogelijks niet lokaal aanwezig is. Verschillende gebruikers die naar elkaar refereren, kunnen immers op een ander deel van de database zitten. Het resultaat is dat er geen foreign keys aangegeven worden in het databaseschema. Alle foreign keys moeten dus met een van onze voorgestelde algoritmes gevonden worden, namelijk via clustering. Om de prestatie te testen van onze database beschikken we over een query trace log die een groot aantal queries (rond de 9000) bevat. Deze werden opgeslagen in een productieomgeving met behulp van de query logging functionaliteit in MySQL. Alle database requests van de webservers naar de databaseserver in deze productieomgeving konden dus worden opgevangen. De traces werden bekomen door het afspelen van echte productiewerklasten.

HOOFDSTUK 8. EXPERIMENTELE RESULTATEN

8.2

42

Werkwijze prestatievaststelling

Om de prestatie op te meten werd de query trace log telkens afgespeeld vanop een aparte replayserver. Een tweede server bevat de originele en de synthetische database. De volledige trace log wordt eerst afgespeeld op de originele database, daarna op de synthetische database. Het afspelen van een volledige trace log zullen we vanaf nu een ’run’ noemen. Tussen twee runs op dezelfde database moet de database worden gereset naar zijn originele status aangezien er ook destructieve queries gebeuren (zoals UPDATE, DELETE, INSERT). Er wordt ook gezorgd dat de MySQL query cache en Linux disk caches tussen twee runs leeggemaakt worden. In onze laatste implementatie werd een originele database gebruikt van 3,3 GB met 104 tabellen. De extractie van het databaseschema, de distributie van de kolomdata en informatie van de relaties tussen de tabellen duurt ongeveer 10 minuten. Het genereren van de synthetische database duurt ongeveer 1 uur. Dit is aanvaardbaar omdat het slechts één keer moet gebeuren om een bruikbare testomgeving te maken. Het resetten van de testdatabase (door middel van bestanden kopiëren) tussen twee testruns duurt immers maar twee minuten.

8.3

Bovengrens prestatievergelijking

Grafiek 8.1 toont op de X-as de procentuele afwijking van de uitvoeringstijd van de queries op de synthetische omgeving tegenover de uitvoeringstijd op de originele omgeving. Op de Y-as wordt getoond welke percentage van de queries in onze volledige query log minder dan het percentage op de X-as afwijken. Om een bovengrens te bepalen van de prestatie die we kunnen behalen met onze synthetische database speelden we de originele trace log herhaaldelijk af op de originele database. Door deze verschillende runs met elkaar te vergelijken kunnen we een bovengrens bepalen. Deze is afhankelijk van de natuurlijke variatie die zich voordoet bij het afspelen van de originele trace log. Op de grafiek zien we dat meer dan 95% van de queries minder dan 25% afwijkt in uitvoeringstijd op de synthetische omgeving. Iets minder dan 5% van de queries zal dus van nature een grote variantie vertonen. Hier moet rekening mee gehouden worden bij het evalueren van de uitvoeringstijd op de synthetische database.


43

Figuur 8.1: Bovengrens prestatiebenadering

8.4

Prestatievergelijking in testomgeving

Op grafiek 8.2 vergelijken we de bovengrens van de vorige sectie met de resultaten die we bekomen als we de uitvoeringstijd vergelijken tussen de originele en de synthetische database. De rode lijn is nog steeds de bovengrens, de blauwe lijn is de prestatievergelijking


44

met onze synthetische database.

Figuur 8.2: Bovengrens en huidig resultaat

Uit de grafiek kunnen we besluiten dat hier ongeveer 90% van de queries minder dan 25% afwijkt in uitvoeringstijd als we de originele en synthetische database vergelijken. Deze afwijking is te verwachten en is aan verschillende factoren te wijten, die in de volgende sectie besproken worden.


45

Factoren die bijdragen aan afwijking uitvoeringstijd Eén van de factoren is de opmerking die voorheen al gemaakt werd, namelijk dat de synthetische query log niet meer volledig dezelfde resultaten kan opleveren als de originele query log. Een andere belangrijke factor is de invloed van het query plan (meer informatie hierover in sectie 7.2.3). Onder andere het feit dat er geen tweede orde statistieken worden opgenomen in ons model kan ervoor zorgen dat sommige queries met behulp van een andere index worden uitgevoerd. Dit heeft uiteraard als gevolg dat de uitvoeringstijd afwijkt. Een laatste factor is de natuurlijke variatie van de uitvoeringssnelheid. De bovengrens die we berekenden maakte duidelijk dat 5% van de queries in onze testset van nature reeds een grote afwijking vertonen in uitvoeringssnelheid. In de sectie hierna zullen we ook de invloed van fragmentatie in het systeem onderzoeken.

8.5

Invloeden van fragmentatie op uitvoeringstijd

Om ons ervan te verzekeren dat er geen andere factoren invloed hadden op de afwijkingen die aanwezig zijn in voorgaande resultaten hebben we ook op lager niveau nagekeken of er verschillen zijn tussen de originele database en de synthetische database die wordt opgebouwd puur op basis van het statistisch profiel.

8.5.1

Fragmentatie op bestandsniveau

In eerste instantie zouden we verwachten dat de originele database op bestandsniveau meer fragmentatie zou vertonen. Deze tabel is immers over maanden of jaren heen opgebouwd, en er zijn vaak ook DELETE en UPDATE operaties gebeurt op deze tabel. Deze operaties kunnen mogelijks fragmentatie in het bestand veroorzaken en de prestatie be¨ınvloeden. MyISAM zorgt er echter voor dat dit nauwelijks gebeurt (er zijn hier verschillende mechanismes voor). Een ander probleem is dat MyISAM de indices van een tabel in een apart bestand bijhoudt. Ook dit bestand kan gefragmenteerd raken. Beide types fragmentatie worden echter opgelost door het aanroepen van het OPTIMIZE commando. We stelden echter vast dat onze testdatabase uit een productieomgeving nauwelijks last had van dit type fragmentatie. Dit is eenvoudig vast te stellen voor een tabel door de metadata op te vragen:


46

SELECT TABLE_SCHEMA, TABLE_NAME, CONCAT(ROUND(data_length / ( 1024 * 1024 ), 2), ’MB’) DATA, CONCAT(ROUND(data_free / ( 1024 * 1024 ), 2), ’MB’) FREE FROM information_schema.TABLES WHERE TABLE_SCHEMA NOT IN (’information_schema’,’mysql’) AND Data_free < 0; Deze query geeft de tabellen terug waarbij fragmentatie op bestandsniveau aanwezig is. In onze testdatabase was dit slechts voor enkele tabellen het geval, en bij die tabellen was de fragmentatie zeer minimaal (minder dan 1% van de grootte van de tabel en index). Dit resultaat wijst erop dat de tabellen waarschijnlijk automatisch geoptimaliseerd werden met één van de herstelmechanismen. We beschouwen dit type van fragmentatie dus niet verder.

8.5.2

Fragmentatie op diskniveau

Buiten fragmentatie op bestandsniveau, kan een bestand zelf ook gefragmenteerd raken op diskniveau. De fragmentatie van een bestand kan eenvoudig opgevraagd worden met het programma filefrag. Dit programma geeft weer in hoeveel niet-continue blokken het bestand zich bevindt op de harde schijf. Om die globale fragmentatie in kaart te brengen hebben we een script geschreven dat beide databases inlaadt, en daarna voor alle tabelbestanden en indexbestanden van de originele en synthetische database de fragmentatiestatus opvraagt met behulp van filefrag. De resultaten toonden aan dat vele kleinere tabellen niet gefragmenteerd waren, maar de grotere tabellen (met honderdduizenden rijen) waren soms gefragmenteerd in verschillende stukken. Vele grotere tabellen uit onze testset hebben ook meerdere indices gedefinieerd over meerdere kolommen. Hierdoor worden de indexbestanden zelf ook enkele honderden MB groot. Bijgevolg waren ook die indexbestanden vaak gefragmenteerd, als het om grotere tabellen ging. Een vergelijking tussen de twee databases wees uit dat bijna alle tabellen waarvan de indexbestanden (.MYI) of databestanden (.MYD) enkele honderden MB’s of groter waren, anders gefragmenteerd werden in de synthetische database (meer of minder continue fragmenten dan in de originele database). Hoe weten we nu of deze afwijking in fragmenten ook een afwijking in uitvoeringstijd veroorzaakt? We kunnen eenvoudig opmeten in hoeveel fragmenten een bepaald bestand gefragmenteerd is. Het is echter niet eenvoudig om bij het wegschrijven van een bestand te kiezen in hoeveel fragmenten het moet worden opgedeeld. Het is ook niet eenvoudig


47

om een bestand dat al op de schijf staat achteraf opzettelijk te fragmenteren. Het zou eventueel mogelijk zijn om een eigen bestandssysteem te schrijven dat bepaalde bestanden telkens op een bepaalde manier wegschrijft (in x aantal fragmenten). Deze fragmentatieinformatie kan dan worden opgenomen in het statistisch profiel. Dit zou ons echter veel te ver brengen, dus we besloten een eenvoudig experiment op te zetten om uit te maken of fragmentatie op schrijfniveau significante verschillen kan veroorzaken in uitvoeringstijd. Het experiment bestaat erin de effecten van fragmentatie in zowel de originele als de synthetische database uit te schakelen, door voor elke run op een aparte partitie een nieuw bestandssysteem te maken. Daarna wordt de database opgebouwd op dit bestandssysteem. Het gevolg hiervan is dat de fragmentatie exact dezelfde is in beide databases. We hebben scripts gemaakt om deze taak te automatiseren. Daarna werd ook geverifieerd met behulp van filefrag dat de fragmentatie dezelfde was in beide databases. Uiteindelijk, na het uitvoeren van verschillende runs bleek dat het uitschakelen van de invloed van fragmentatie nauwelijks invloed had op de verschillen in uitvoeringstijden. Aangezien de invloed van deze factor in vergelijking met andere factoren verwaarloosbaar is, zullen we er verder geen onderzoek naar doen.

8.6

Experimentele invloed van Poisson interarrival tijden op de prestatie

Grafiek 8.3 toont de prestatie bekomen in deel 8.7 met de rode lijn (Uniforme afspeeltijd). We vergelijken in deze grafiek de prestatie met het geval waarin een Poisson interarrivaltijd wordt gebruikt bij het afspelen van de query log. De blauwe lijn geeft de prestatie weer wanneer de gemiddelde interarrivaltijd 10 ms is. Voor de gele lijn is de gemiddelde interarrivaltijd 5 ms. We zorgen ervoor dat op zowel originele als synthetische database de tijden hetzelfde zijn, door te starten met eenzelfde random seed. We zien dat de prestatiemeting afwijkt als we 2 runs met elkaar vergelijken (1 op de originele database en 1 op de synthetische database, zoals hier gebeurt). Dit komt omdat door contentie de queries nog veel meer contentie veroorzaken door een sneeuwbaleffect en sommige queries uitzonderlijk lang zullen duren. Hierdoor zal de uitvoeringstijd veel minder voorspelbaar worden. Dit zal echter niet alleen in de synthetische omgeving zo zijn, maar ook in de originele omgeving. In beide omgevingen wordt de variantie van de uitvoeringstijd veel hoger en bijgevolg zullen 2 individuele runs niet minder vergelijkbaar worden.


48

Figuur 8.3: Variatie in afspeelinterval

Aangezien de uitvoeringstijden niet meer gelijk lopen, maar de variantie van de uitvoeringstijd in beide omgevingen veel groter wordt, kan het zijn dat de uitvoeringstijden in individuele runs wel verschillen, maar dat zij niet statistisch significant verschillen omwille van de grotere variantie. Om deze hypothese te testen zullen we telkens 10 runs laten lopen op de originele database en 10 runs op de synthetische database. Daarna definiëren we voor elke query twee omgevingen. Eén omgeving wordt gedefinieerd aan de hand van de cijfers van de tests op de originele database en één op basis van de cijfers van de andere tests. Een omgeving wordt vastgelegd door het gemiddelde van de 10 runs en de spreiding. De spreiding is gelijk aan de T-waarde in de T-test van Student maal de standaardafwijking van de 10 waarden. De omgeving wordt nu gedefinieerd door als minimumwaarde het gemiddelde


49

min de spreiding te nemen, en als maximumwaarde het gemiddelde plus de spreiding. Om de T-waarde te weten voor deze tweezijdige T-test kiezen we als confidentie niveau 99.5%. Het aantal vrijheidsgraden is gelijk aan het aantal metingen (10) + 1. De gebruikte T-waarde wordt dus 3.106. We zullen besluiten dat de uitvoeringstijden van twee queries niet statistisch significant afwijken indien hun omgevingen overlappen. We voeren deze test nu drie keer uit. Eenmaal voor de uniforme IAT, eenmaal voor de Poisson IAT met gemiddelde IAT 10 ms, en als laatste voor de Poisson IAT met gemiddelde 2 ms. In onderstaande tabel worden de resultaten gepresenteerd. Uniforme IAT 92% niet statistisch afwijkend Poisson IAT (lambda = 10 ms) 88% niet statistisch afwijkend Poisson IAT (lambda = 2 ms) 95% niet statistisch afwijkend Wanneer de IAT Poisson verdeeld is blijft het aantal statistisch afwijkende queries ongeveer gelijk. Wanneer de queries sneller na elkaar worden afgespeeld, verhoogt de variantie zodanig dat de meeste uitvoeringstijden op de synthetische database niet meer statistisch onderscheidbaar zijn van de uitvoeringstijden op de originele database.

8.7

Invloed van databaseschaling op prestatie

Het is interessant om na te gaan wat er gebeurt indien we een kleinere of grotere database opbouwen aan de hand van een statistisch profiel van de originele database. De volgende grafieken tonen de uitvoeringstijd op de originele database op de X-as en de uitvoeringstijd op de synthetische database op de Y-as.

8.7.1

Prestatie bij gebruik kleinere database

Op grafieken 8.4 en 8.5 zien dat voor een kleinere database de uitvoeringstijd op de synthetische database kleiner wordt. Voor sommige queries verandert er weinig. De meeste queries die de tabel niet lineair scannen (bijvoorbeeld aan de hand van indices) zullen niet sterk be¨ınvloed worden door de schaling. Ook queries die in ieder geval al weinig resultaten teruggeven zullen minder last van deze invloed hebben. Het gebruik van een kleinere synthetische database kan dus nuttig zijn en vergelijkbare resultaten geven, afhankelijk van het type werklast dat wordt aangeboden.


Figuur 8.4: Vergelijking met databasegrootte 50%

50


51

Figuur 8.5: Vergelijking met databasegrootte 10%

We zien dat de uitvoeringstijd op de synthetische database toch veel kleiner wordt voor een groot aantal queries. Waar er bij de database met normale grootte langs beide kanten uitschieters zijn, en een groot deel van de queries een kleinere (en gelijkaardige) uitvoeringstijd hebben, zien we nu dat er enkel uitschieters op de originele database zijn. Een kleinere database zal deze eigenschap dus niet meer goed modelleren. Het zou echter


52

wel mogelijk zijn om een werklast te verzinnen die toch nog goed presteert met een kleinere database. Op deze manier kunnen we voorspellen welke queries goed blijven presteren bij een grotere database en welke niet.

8.7.2

Prestatie bij gebruik grotere database

Wanneer we een grotere database opbouwen aan de hand van het statistisch profiel van de originele database, stellen we vast dat de uitvoeringstijd op de synthetische database omhoog gaat bij een aantal queries. Bij de queries waar dit niet zo is, gebeurt de opzoeking over het algemeen aan de hand van indices. Daar moet voor een dubbel zo grote database vaak slechts 1 extra operatie moet worden uitgevoerd. Grafiek 8.6 geeft ons een voorbeeld van een grotere database.


53

Figuur 8.6: Databasegrootte 200%

We besluiten dat het in sommige situaties nuttig kan zijn om de grootte van de synthetische database te manipuleren. Een interessante toepassing hiervan is om te weten te komen welke queries gevoelig zijn aan de grootte van de database. Concreet zou een Web 2.0 toepassing die nog niet veel gebruikers heeft (en dus nog niet veel data) hiervan gebruik kunnen maken om op voorhand te weten welke queries geoptimaliseerd zullen moeten worden.


8.8

54

Invloed van query cache

In deze laatste tests zullen we de testomgeving voor de synthetische database automatisch wijzigen om een andere query cache grootte te gebruiken. Deze test is zeer gemakkelijk automatisch uit te voeren in de synthetische testomgeving, men kan gewoon aangeven welke cachegroottes er getest moeten worden, en hoeveel keer er getest moet worden. Dit alles is mogelijk enkel op basis van het statistisch profiel en de query log. In onderstaande tabel tonen we de gemiddelde uitvoeringstijd van de queries op de synthetische database met en zonder query cache. Om de resultaten te valideren tonen we ook de resultaten hiervan op de originele database met en zonder cache. Gemiddelde uitvoeringstijd Gemiddelde uitvoeringstijd Synthetische database Originele database (validatie) 0 MB (geen cache) 0.35 ms 0.33 ms 32 MB (default) 0.31 ms 0.29 ms We kunnen hieruit besluiten dat het gebruik van de query cache slechts 10% verschil verbetering in prestatie veroorzaakt. Dit komt waarschijnlijk omdat de query cache ook voor heel wat overhead zorgt. Niet alleen moet de query cache bij elke query geraadpleegd worden, maar indien er inserts of updates gebeuren moet de relevante data in de query cache worden gewist. Wanneer vooral select operaties gebeuren zal de query cache een goede invloed hebben op de prestatie, maar wanneer er een mix is van insert en select operaties zal dat al heel wat minder worden. Het kan ook goed zijn om tijdens de levensduur van een applicatie de afweging om al dan niet een kleinere of grotere (of geen) query cache te gebruiken opnieuw te evalueren, omdat veranderingen aan de applicatie en andere workload verdeling en andere interactie met de cache kunnen veroorzaken. Het statistisch database profiel en profiel van de werklast krijgen op die manier een tijdsdimensie.

8.9

Invloed van storage engine MyISAM/InnoDB

Als laatste validatietest zullen we een vergelijking maken van de uitvoeringstijden op InnoDB en MyISAM. InnoDB is een database die ACID compliant is, wat onder andere wil zeggen dat de database de geldigheid van transacties garandeert. Een belangrijk verschil tussen InnoDB en MyISAM is dat je bij InnoDB veel parameters moet instellen om tot een goed prestatie te komen, terwijl ja bij MyISAM met de standaard parameters meestal al goede resultaten krijgt. Wij hebben InnoDB gebruikt met de volgende instellingen:


55

innodb_log_buffer_size = 8MB innodb_log_file_size = 5MB innodb_buffer_pool_size = 512MB Grafiek 8.7 toont de uitvoeringstijd van queries op zowel MyISAM als InnoDB. Er dient opgemerkt te worden dat de queries die langer dan 1 ms duurden slechts ongeveer 8% van het totale aantal queries zijn. Bij de queries die korter dan 1 ms duurden stelden we namelijk vast dat het gebruik van de storage engine niet veel verschil maakte. Bij de queries die langer dan 1 ms duurden zien we wel een duidelijk verschil: InnoDB zorgt voor meer tragere queries in vergelijking met MyISAM. Dit kunnen we toewijzen aan de ACID overhead van InnoDB. Dankzij deze test kunnen we dus aantonen dat migreren naar InnoDB in het geval van deze database geen goed idee is voor de uitvoeringstijd van sommige queries, tenzij bepaalde eigenschappen van InnoDB nodig zijn (InnoDB is onder andere ook meer resistent tegen falen). Validatie Om deze validatietest uit te voeren zullen we nu ook de originele database omzetten om gebruik te maken van de InnoDB storage engine. We merken op uit grafiek 8.8 dat we zeer vergelijkbare resultaten krijgen. We hadden dit resultaat dus ook kunnen bekomen enkel met behulp van het statistisch profiel van de database en onze tools zoals hierboven. Om onderstaande resultaten te bekomen moesten we de originele database die in productie gebruikt werd omvormen met behulp van de ALTER table commando’s. De uitvoertijd voor de omzetting is zeer traag op een normale productieomgeving (enkele tientallen uren voor onze database van 3 GB) en dus niet praktisch.


Figuur 8.7: Vergelijking MyISAM en InnoDB op synthetische database

56


Figuur 8.8: Vergelijking MyISAM en InnoDB op originele database

57

58

Mogelijke toepassing Een directe toepassing van dit systeem is het opbouwen van testomgevingen voor Web 2.0 applicaties. Dit systeem zou als een cloud-service kunnen aangeboden worden. Het voordeel voor ontwikkelaars is dat ze niet zelf moeten investeren in een testomgeving die representatief is voor hun productieomgeving. Men moet ook geen tijd investeren in anonimisatie van de data aangezien het statistisch profiel de data voldoende verhult. Bovendien moeten er geen grote hoeveelheden data overgezet worden naar een andere locatie. Het zou mogelijk zijn om voor de klant een kleine applicatie te voorzien die het statistisch profiel van zijn database in kaart brengt. Dit profiel is vele malen kleiner dan de database zelf (minder dan 1 MB voor een database van 3,3 GB). Om een test uit te voeren met de cloud-service moet men enkel dit profiel uploaden. Men bouwt vervolgens een synthetische database aan de hand van het profiel. Indien men een snelle test wil doen kan een kleinere synthetische database opgebouwd worden. Men zou ook een optie kunnen voorzien om een synthetische database te bouwen die enkele malen groter is, maar toch dezelfde statistische eigenschappen heeft als de originele database. Op die manier zou men kunnen voorspellen hoe de prestatie van de applicatie in de toekomst zal evolueren wanneer de database groter wordt. Dit zou een handige tool kunnen zijn voor bedrijven met een nieuwe Web 2.0 applicatie die nog niet veel gebruikers heeft, maar snel kan aangroeien. Bovendien zou het mogelijk zijn om snel automatische tests te doen met nieuwe versies van de database software, andere storage engines, verschillende partitioneringsalgoritmes, ... Volledig synthetische werklast Eén van de openstaande puntjes hierbij is het feit dat de klant ook een query log zou moeten voorzien om dit mogelijk te maken. Dit is mogelijk via de query logging functionaliteit van MySQL. Echter, sommige storage engines zoals InnoDB houden ook informatie bij in het informatie schema van de database over het type queries dat uitgevoerd werd op elke tabel. Het zou interessant zijn om aan de hand van deze informatie zelf een volledig synthetische query log op te bouwen. Bovendien kan deze synthetische query log ook geparametriseerd


59

worden. Zo zou de eindgebruiker per test kunnen aangeven wat de verdeling moet zijn van INSERT, UPDATE en SELECT queries. Het zou zelfs mogelijk zijn om aan te geven op welke kolommen het meest gezocht moet worden om zeer gerichte stresstests uit te voeren. Het volledige concept Dit soort automatische testomgevingen kan van grote waarde zijn voor bedrijven die een in-house Web 2.0 toepassing onderhouden. De database is immers één van de belangrijkste onderdelen van dit soort toepassingen en is bovendien ook vaak één van de bottlenecks. We moeten ons echter niet beperken tot het modelleren en simuleren van de database. Kunnen we ook andere onderdelen van een typische Web 2.0 omgeving modelleren? Andere onderdelen omvatten onder andere cache servers (Memcached is hiervoor een populaire keuze, onder andere Facebook maakt hiervan gebruik zoals beschreven in [13] en [14]), dynamische webservers (zoals Apache), maar ook webservers die statische content afleveren (zoals Lighttpd), load balancers, firewalls, maar eventueel ook externe webservices waarop vertrouwd wordt. Enkele stappen verder Een volledig uitgewerkte applicatie zou de Web 2.0 omgeving van de buitenste tot de binnenste laag kunnen modelleren en simuleren. De buitenste laag simuleren zou omvatten dat het HTTP verkeer wordt afgespeeld naar een load balancer of webserver. Ook voor dit HTTP verkeer zou een statistisch profiel kunnen opgemaakt worden. Aan de hand van dit HTTP-profiel zou een synthetische HTTP request log kunnen gemaakt en afgespeeld worden. Dit profiel zou dan informatie omtrent timing en pagina’s omvatten. Het zou zelfs eenvoudig zijn om dit profiel op te stellen aan de hand van een interface met bestaande logging software zoals Google Analytics, deze software weet immers alles over de requests die gebeuren op een website. Eventueel kan deze data nog aangevuld worden met custom logging software. Meerwaarde voor ontwikkelaars In eerste instantie kan men zien of de applicatie effectief nog werkt na het aanbrengen van de wijzigingen waarin men ge¨ınteresseerd is. Daarnaast kan men ook nog zien of de wijzigingen prestatiewinst met zich meebrengen of net niet. Als uitbreiding hierop zou men in de cloud-testomgeving ook nog energiemetingen kunnen uitvoeren om bij de geautomatiseerde tests ook nog informatie over het verschil in energieverbruik weer te


60

geven. Een nieuw type hardware kan mogelijks interessant zijn omdat het minder energie verbruikt en de latentie ongeveer gelijk houdt.

61

Hoofdstuk 9 Conclusies In deze sectie sluiten we af met een opsomming van de experimentele resultaten die het raamwerk van de synthetische database valideren. Daarna bespreken we de praktische toepassingen. We ronden af met enkele mogelijk uitbreidingen. Validatie van het raamwerk Uit prestatie analyses met onze synthetische database blijkt dat het mogelijk is om een representatieve testomgeving op te bouwen voor een relationele database op basis van een statistisch profiel. Het statistisch profiel bevat informatie over de structuur van de database, informatie over de data in de individuele kolommen en informatie over de relaties tussen de tabellen. Er zijn geen tweede orde correlatiestatistieken verwerkt in het model. In onze tests gebruikten we een database uit een bekende Web 2.0 applicatie. In 90% van de gevallen bleek de uitvoeringstijd van een query op de synthetische database binnen de 25% te liggen van de uitvoeringstijd op de originele database. Praktische toepassingen Met de synthetische database is het mogelijk om voorspellingen te doen die representatief zijn voor de productieomgeving. Met behulp van de software die we hebben opgebouwd is het mogelijk om een statistisch profiel op te bouwen van een MySQL database zonder de prestatie van de productieomgeving sterk te be¨ınvloeden. Bovendien is het statistisch profiel dat geproduceerd wordt voor een database van 104 tabellen met ongeveer 3,3 GB aan data minder dan 1 MB groot. Het statistisch profiel kan dus gemakkelijk gedeeld worden met derden en bevat ook geen onthullende informatie meer over de gebruikers van de applicatie. Een ander deel van onze software maakt aan de hand van een statistisch

HOOFDSTUK 9. CONCLUSIES

62

profiel een synthetische database met bepaalde eigenschappen. We kunnen een database opbouwen die precies hetzelfde is, maar eventueel kunnen we ook een kleinere of grotere database maken, of een database die een andere storage engine gebruikt. We kunnen ook evalueren wat er gebeurt wanneer andere versies van de database software gebruikt wordt of andere instellingen gebruikt worden. Mogelijke uitbreidingen In de toekomst zou hierrond een cloud-service kunnen gebouwd worden die voor Web 2.0 ontwikkelaars testomgevingen opzet. De klanten zouden enkel het statistisch profiel van hun database moeten doorsturen en daarna kunnen tests volautomatisch verlopen. Op die manier kan men snel evalueren of nieuwe ontwikkelingen of mogelijkheden op gebied van databases een goede aanwinst zouden zijn in de productieomgeving. Het hoeft echter niet te stoppen bij het database aspect van de Web 2.0 toepassing. In een latere fase zou ook verkeer naar cache servers gemodelleerd kunnen worden, alsook het HTTP verkeer van en naar de gebruikers van de Web 2.0 toepassing zelf. Met de juiste informatie vervat in de statistische profielen zouden we in staat zijn om de gehele productieomgeving van een Web 2.0 toepassing automatisch na te maken.

63

Bibliografie [1] Liddle J. Amazon found every 100ms of latency cost them 1% in sales: http://blog.gigaspaces.com/2008/08/27/amazon-found-every-100ms-of-latencycost-them-1-in-sales/, 2008. [2] TPC. Transaction processing performance council: http://www.tpc.org/, 2012. [3] OSDB. The open source database benchmark: http://osdb.sourceforge.net/, 2012. [4] Joshi A., Eeckhout L., Bell Jr. R., and K. John L. Distilling the essence of proprietary workloads into miniature benchmarks. ACM Trans. Archit. Code Optim., 5(2):10:1– 10:33, September 2008. [5] Van Ertvelde L. and Eeckhout L. Benchmark synthesis for architecture and compiler exploration. In 2010 IEEE International symposium on Workload Characterization (IISWC 2010), pages 106–116. IEEE, 2010. [6] Joshi A., Eeckhout L., K. John L., and Isen C. Automated microprocessor stressmark generation. In HPCA, pages 229–239. IEEE Computer Society, 2008. [7] Fan X., Weber W., and Barroso L. Power provisioning for a warehouse-sized computer. SIGARCH Comput. Archit. News, 35(2):13–23, June 2007. [8] Du Bois K., Schaeps T., Polfliet S., Ryckbosch F., and Eeckhout L. Sweep: evaluating computer system energy efficiency using synthetic workloads. In Proceedings of the 6th International Conference on High Performance and Embedded Architectures and Compilers, HiPEAC ’11, pages 159–166, New York, NY, USA, 2011. ACM. [9] Moore J. and Chase J. Data center workload monitoring, analysis, and emulation. In in Eighth Workshop on Computer Architecture Evaluation using Commercial Workloads, 2005.

BIBLIOGRAFIE

64

[10] Narayanan A. and Shmatikov V. Robust de-anonymization of large sparse datasets. In Proceedings of the 2008 IEEE Symposium on Security and Privacy, SP ’08, pages 111–125, Washington, DC, USA, 2008. IEEE Computer Society. [11] Sweeney L. k-anonymity: A model for protecting privacy. International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, 10(5):557–570, 2002. [12] The date, datetime, and timestamp types: http://dev.MySQL.com/doc/refman/5. 5/en/datetime.html. [13] Saab P. Scaling memcached at facebook, 2008. [14] Thiessen R. The secret sauce of sharding, 2011. [15] Eeckhout L. Geavanceerde computerarchitectuur. In Geavanceerde computerarchitectuur, September 2010.

65

Lijst van figuren 4.1

De stappen die we doorlopen bij opbouwen van het raamwerk . . . . . . .

12

5.1 5.2 5.3

Voorbeeld van een databaseprofiel . . . . . . . . . . . . . . . . . . . . . . . Voorbeeld van anonimisatie . . . . . . . . . . . . . . . . . . . . . . . . . . Voorbeeld van clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . .

15 20 24

6.1

Voorbeeld van de Unique-velige modus . . . . . . . . . . . . . . . . . . . .

32

7.1

Schema van onze serveropstelling . . . . . . . . . . . . . . . . . . . . . . .

36

8.1 8.2 8.3 8.4 8.5 8.6 8.7 8.8

Bovengrens prestatiebenadering . . . . . . . . . . . . . . . Bovengrens en huidig resultaat . . . . . . . . . . . . . . . . Variatie in afspeelinterval . . . . . . . . . . . . . . . . . . . Vergelijking met databasegrootte 50% . . . . . . . . . . . . Vergelijking met databasegrootte 10% . . . . . . . . . . . . Databasegrootte 200% . . . . . . . . . . . . . . . . . . . . Vergelijking MyISAM en InnoDB op synthetische database Vergelijking MyISAM en InnoDB op originele database . .

43 44 48 50 51 53 56 57

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

Ontwerp en evaluatie van profiel-gebaseerde synthetische databanken

Recommend Documents