Full text search met Lucene op Azure

CLOUD

Roy de Boer en Freek Paans

Full text search met Lucene op Azure Lucene is een full text search engine, oorspronkelijk geschreven in Java. Het biedt mogelijkheden om grote hoeveelheden tekst efficiënt te doorzoeken. In dit artikel beschrijven we onze ervaringen met het inzetten van Lucene.NET (een populaire .NET port van Lucene) binnen een Azure-omgeving, de cloud-oplossing van Microsoft. Azure stelt namelijk een aantal specifieke eisen aan de architectuur van een applicatie, die ook van invloed zijn op de Lucene implementatie. We stellen daartoe een dergelijke architectuur voor en onderzoeken een aantal karakteristieken hiervan. Bij dit artikel hoort een voorbeeldproject, waarin we de publieke domein boeken van gutenberg.org doorzoekbaar maken. In dit voorbeeldproject passen we de voorgestelde architectuur toe. Daarnaast kan dit project ook als basis dienen om zelf verder met Lucene op Azure te experimenteren. Het project is te vinden op https://github.com/infi-nl/lucene-azure. We zullen nu beginnen met een korte review van de Lucene API, waarna we ingaan op de Azure-specifieke uitdagingen. Vervolgens tonen we een mogelijke implementatie en sluiten af met een analyse van de operationele karakteristieken van die implementatie. Lucene Vroeger was het gebruikelijk om informatie te zoeken aan de hand van sleutelwoorden in een kaartenbak. Dit was beter dan niets, maar met de komst van zoekmachines is het gebruikelijk geworden om informatie te zoeken op basis van willekeurige tekstfragmenten. Dit concept staat bekend als full text search. Mocht je zelf full text search willen aanbieden om applicatie-specifieke informatie doorzoekbaar te maken, dan bieden veel databases daar standaard mogelijkheden voor. Als die mogelijkheid er echter niet is, zoals in Azure SQL Database, dan bestaan er ook externe componenten die dit kunnen, zoals Lucene. Dit is een populaire keuze voor Java-projecten, en wordt onder andere gebruikt door Solr en ElasticSearch. Daarnaast is het project inmiddels ook naar .NET geport, deze port gebruiken we voor dit artikel. Lucene Document Waar binnen een relationele database een record de kleinste eenheid van opslag is, is dat binnen Lucene een Document. Dit is een datastructuur waarmee je de te doorzoeken data in één of meerdere velden kunt onderbrengen. Naast deze zelf te definiëren velden, houdt Lucene ook een intern ID bij voor elk document. Dit ID zullen we later terugzien bij het ophalen van resultaten. Zo maken we in het voorbeeldproject per boek een document aan, met daarin de volgende velden: Gutenberg ID, titel, publicatiedatum op Gutenberg, taal, auteur en de volledige tekst van het boek. Dit maakt het mogelijk om bijvoorbeeld specifiek op Gutenberg ID of taal te zoeken.

IndexReader en IndexWriter Lucene slaat alle documenten op in de zogenoemde index. Net als bij bijvoorbeeld een relationele database zorgt de index ervoor dat er efficiënt gezocht kan worden. Het uitlezen van en wegschrijven naar deze index wordt respectievelijk door de classes IndexReader en IndexWriter verzorgd. Deze classes zijn ontworpen met multithreaded applicaties in het achterhoofd: een enkele instantie kan worden gedeeld tussen alle threads binnen de applicatie zonder dat je zelf voor synchronisatie hoeft te zorgen. In verband met performance en geheugengebruik wordt geadviseerd om met één instantie per applicatie te werken. In ieder geval kan de fysieke index maar door één IndexWriter tegelijkertijd worden bewerkt. In het algemeen is de geïndexeerde informatie, en zo ook de Lucene index, aan verandering onderhevig. IndexReader detecteert wijzigingen niet automatisch. De wijzigingen worden pas zichtbaar na het aanmaken van een nieuwe instantie. Hoe we hier mee omgaan, laten we verderop in het artikel ook zien. Query en IndexSearcher Zoekopdrachten binnen Lucene worden gëencapsuleerd in een Query object. Een dergelijk object is op meerdere manieren te verkrijgen, bijvoorbeeld via de QueryParser class die een tekstuele query zoals titel:max AND auteur: mult* vertaalt naar een Query. Maar er is bijvoorbeeld ook de TermQuery. De Query kan vervolgens door de Search methode van de class IndexSearcher worden uitgevoerd. Dit levert een op relevantie gesorteerde lijst met Lucene Document ID’s op. IndexSearcher is net als IndexReader en IndexWriter threadsafe, waardoor één instantie per applicatie voldoende is. Directory Toegang tot de fysieke index wordt geregeld door implementaties van de abstract class Directory, zoals bijvoorbeeld FSDirectory of RAMDirectory (die de index respectievelijk op het filesystem of in RAM opslaan). Tot zover de review van de Lucene API. We gaan nu verder in op de Azure-specifieke uitdagingen.

magazine voor software development 5

CLOUD

Uitdagingen op Azure Om Lucene te gebruiken op Azure moet je rekening houden met een aantal uitgangspunten van Azure: • In een Azure-omgeving moet je elk logisch onderdeel van je systeem op minimaal twee nodes draaien om aanspraak te kunnen maken op de SLA van 99.95% beschikbaarheid. Zo zul je minimaal twee nodes van je web- of worker-roles nodig hebben. • Binnen de Azure-rollen heb je te maken met een transient harddisk. Dat wil zeggen dat bestanden die je wegschrijft op het lokale filesystem niet durable zijn; als Azure de node re-imaged krijg je weer een “kaal” filesystem. Aangezien Azure dit op willekeurige tijden doet, moet je hier rekening mee houden bij het ontwikkelen van je applicatie. Voor het gebruik van Lucene heeft dit een aantal implicaties. Een request als GET /Search?q=foo+bar komt namelijk op een willekeurige web-node uit. De node in kwestie zal toegang moeten hebben tot de fysieke index om het request af te kunnen handelen. In een dergelijke multi-node situatie zijn er twee voor de hand liggende opties voor de locatie van de index: ofwel het lokale filesystem, ofwel een shared storage, in het geval van Azure bijvoorbeeld de Windows Azure Blob Storage. De oplossing met het lokale filesystem is vrij complex omdat je zelf de index op de diverse nodes gesynchroniseerd moet houden. Je loopt dan al snel tegen situaties aan waar je gebruik moet maken van gedistribueerde transacties om de indices consistent te houden. Een ander probleem is het initialiseren van een kale node, bijvoorbeeld omdat een node wordt toegevoegd, of een bestaande node opnieuw wordt ge-imaged. In dergelijke situaties moet je de index herbouwen, wat afhankelijk van de grootte een tijdrovende klus kan zijn. We hebben daarom gekozen voor de oplossing waar we de index delen via een shared storage. Hierbij zullen de indices wel altijd in-sync zijn. Er kleeft echter ook een nadeel aan: elke node moet updates kunnen doorvoeren op de index, terwijl er maar één actieve Index Writer kan zijn. In principe regelt Lucene deze synchronisatie zelf via locking, maar nodes moeten hierdoor op elkaar wachten. Hierdoor kunnen de responsetijden oplopen en kunnen er uiteindelijk zelfs time-outs optreden.

In dit schema valt op dat er twee Indexer nodes zijn (waar het Indexer proces op draait), dit is nodig vanwege de Azure SLA voorwaarden. We leggen later uit hoe we zorgen dat er slechts één actief is. We zullen nu de geschetste architectuur verder uitwerken en onderzoeken. Implementatie Er zijn twee aspecten waar een wezenlijk verschil ontstaat tussen deze architectuur en een single-node situatie: het doorvoeren van updates en het verversen van de IndexReader. Omdat ons artikel specifiek gaat over Lucene op Azure zullen we deze aspecten verder uitdiepen. Index updates Een update op de index bestaat uit twee stappen: allereerst wordt de gewenste update gequeued door een web-node, waarna hij wordt gedequeued en aan de index wordt toegevoegd door het Indexer proces. Het queuen gebeurt, in pseudocode, als volgt: Book book = …; Queue queue = …; queue.Enqueue(Serialize(book));

Dit probleem is op te lossen door één proces aan te wijzen dat alle writes doet. Andere nodes geven dan hun gewenste wijzigingen door aan dit proces. In onze implementatie noemen we dit proces de Indexer, en communiceren we de updates via een queue. Nadeel van deze oplossing is wel dat je eventual consistency introduceert: na een write zal het even duren voordat deze zichtbaar is op elke node. De tijd tussen het doorgeven van een wijziging en het daadwerkelijk zichtbaar worden op een web-node noemen we de update-latency.

Het verwerken van de update ziet er dan zo uit: IndexWriter writer = …; Queue queue = …; Message message = queue.Dequeue(); Book book = Deserialize(message.Body); writer.AddDocument(ToLuceneDocument(book));

Een ander probleem is dat de index niet op het lokale filesystem leeft en de daarom benodigde netwerktoegang tot de shared storage extra latency zal opleveren. Dit probleem zou je kunnen verzachten door de index lokaal te cachen. Lucene leent zich hier goed voor omdat updates incrementeel te downloaden zijn. Beide oplossingen voor de genoemde problemen worden geïmplementeerd door de vrij beschikbare component AzureDirectory (http://azuredirectory.codeplex.com). Dit is een implementatie van de Lucene Directory die de index opslaat op de Blob Storage. Bovendien wordt de index ook in een cache op het lokale filesystem bijgehouden. Een complete oplossing zou er dan zo uit kunnen zien:

6

MAGAZINE

writer.Commit(); message.Complete(); De call naar Message.Complete wordt gedaan omdat er gewerkt wordt met een peek-lock pattern. Dit voorkomt verlies van berichten bij fouten tijdens de verwerking. Het is dan wel belangrijk om Message.Complete pas na writer.Commit aan te roepen. Azure Service Bus Queues biedt deze peek-lock semantiek en gebruiken we dan ook in onze implementatie. De API’s van Lucene en de Service Bus bieden beide mogelijkheden tot batchverwerking. Wanneer er meerdere berichten beschikbaar zijn

CLOUD

in de queue kunnen deze in één keer worden verwerkt. Zoals we straks laten zien heeft dit invloed op de performance. De batch size noemen we B. Dat ziet er dan zo uit: IndexWriter writer = …; Queue queue = …; int batchsize = …; Message[] messages = queue.ReceiveBatch(batchsize); foreach (var message in messages) { AddMessageToIndex(writer, message); } writer.Commit(); queue.CompleteBatch(messages); Bij het bepalen van de batch size kijken we naar de verwerkingssnelheid van de Indexer en naar de update-latency :

function GetIndexWriter() { Directory directory = Ö; while (true) { try { return new IndexWriter (directory); } catch (LockObtainFailedException) { Sleep(Ö); } } } De LockObtainFailedException treedt op wanneer een Indexer-node al een IndexWriter open heeft op de index. Met deze constructie kan er dus altijd maar één Indexer-node berichten verwerken. Verversen van de IndexReader Voor het lezen van de index implementeren we een IndexReader singleton: class IndexReaderSingleton { static _indexReader = new IndexReader(..) static GetInstance() { return _indexReader; } }

We zien dat een batch size van minder dan B=200 berichten de verwerkingssnelheid beperkt. Voor batch sizes groter dan 200 neemt de verwerkingssnelheid niet meer toe. De optimale verwerkingssnelheid is dus te bereiken door de batch size op minimaal B=200 berichten te stellen.

Als er updates plaatsvinden op de index worden deze pas zichtbaar als we een nieuwe IndexReader openen. We hebben voor een strategie gekozen waarbij de IndexReader periodiek, dus elke x seconden, opnieuw geopend wordt. Dit zorgt er dus voor dat we elke x seconden een verse IndexReader hebben. We noemen die periode de verversperiode R. Het verversen gaat dan als volgt: class IndexReaderSingleton { … static Refresh() { _indexReader = new IndexReader(…); } } Schedule.Every(x seconden, IndexReaderSingleton.Refresh) We hebben voor de overzichtelijkheid synchronisatie- en lockingoverwegingen buiten beschouwing gelaten.

We hebben ook gekeken hoe de update-latency zich bij verschillende aanvoersnelheden v (updates per seconde) gedraagt: We zien dat er voor batch sizes groter dan 175 berichten geen significant verschil in update-latency is bij deze aanvoersnelheden. We zien ook dat rond de 100 updates per seconde verzadiging van de queue plaatsvindt en dat de latencies daardoor oplopen. Dit strookt met de observaties met betrekking tot de verwerkingssnelheid. Een laatste overweging bij implementatie is de Azure SLA: het proces dat schrijft zal ook dubbel uitgevoerd moeten worden, maar er mag slechts één IndexWriter tegelijkertijd actief zijn. Dit lossen we op door het synchronisatiemechanisme van Lucene te gebruiken:

Een nadeel van deze oplossing is dat we steeds een compleet nieuwe IndexReader openen, wat potentieel duur is. We benutten daarom de Reopen()-methode van de IndexReader, deze methode vult de door de huidige IndexReader geladen data aan met nieuw beschikbare informatie. class IndexReaderSingleton { static Refresh() { _indexReader = _indexReader.Reopen(); } } Voor het uitvoeren van zoekopdrachten hebben we tot slot de IndexSearcher nodig. Deze heeft een afhankelijkheid op de IndexReader en daarom laten we de lifecycle van de IndexSearcher samenlopen met die van de IndexReader.

magazine voor software development 7

CLOUD

class IndexSearcherSingleton { static _indexReader = new IndexReader(Ö) static indexSearcher = new IndexSearcher(_indexReader); static Refresh() { IndexReader newReader = _indexReader.Reopen(); if (newReader == _indexReader) { return; } _indexReader = newReader; indexSearcher = new IndexSearcher(_indexReader) } static GetInstance() { return _indexSearcher; } }

We maken hierbij gebruik van het feit dat _indexReader.Reopen zichzelf teruggeeft als de index onveranderd is. Een zoekopdracht neemt dan de volgende vorm aan: IndexSearcher indexSearcher = IndexSearcherSingleton.GetInstance(); string userQuery = …; Query query = new QueryParser(…).parse(userQuery); TopDocs topDocs = indexSearcher.Search(query, …); TopDocs bevat dan de lijst met de meest relevante Lucene Document ID’s. Dan moeten we nog een keuze maken voor de waarde van de verversperiode R. Om dit te bepalen bekijken we hoe de updatelatency hierdoor beïnvloed wordt bij verschillende aanvoersnelheden v.

We zien dat de verversperiode geen significante invloed heeft op de hoeveelheid gedownloade data. Overigens zijn de duidelijke stappen in de grafiek toe te schrijven aan het index merge proces van Lucene. Dit proces optimaliseert de fysieke index door onder andere data samen te voegen. Deze samengevoegde data staat dan niet in de cache, en moet dus in zijn geheel gedownload worden. De initiële download is 465 MB, wat ruwweg overeenkomt met de grootte van de index op de Blob Storage, 425 MB. Er blijkt dus dat een verversperiode van 2500 ms voor alle onderzochte aanvoersnelheden resulteert in een update-latency van lager dan 4 seconden. Daarbij levert dit ten opzichte van langere verversperiodes geen groot verschil op in traffic naar de Blob Storage. We hebben echter het gebruik van systeemresources niet gemeten en kunnen ons voorstellen dat er problemen kunnen ontstaan bij korte verversperiodes, vooral wanneer je het opruimen van de IndexReader en IndexSearcher overlaat aan de garbage collector. Dit lichten we hieronder verder toe. Dispose versus GC In bovenstaande implementatie laten we het opruimen van de oude IndexReader en IndexSearcher over aan de garbage collector.Dit kan ervoor zorgen dat sommige resources (zoals files) onnodig lang geopend blijven. Als dit een probleem blijkt kun je ervoor kiezen om de Dispose()-methodes van IndexSearcher en IndexReader aan te roepen na gebruik. Pas echter op: meerdere threads kunnen een reference hebben naar deze objecten en Dispose() mag pas aangeroepen worden nadat alle threads hebben aangegeven klaar te zijn met hun reference. Een methode om dit te doen is het gebruik van reference counting. Een mogelijke implementatie hiervan tonen we in het voorbeeldproject. Operationele karakteristieken Als laatste zijn we geïnteresseerd in de operationele eigenschappen van deze oplossing. We kijken daarvoor naar enkele omgevingsparameters: wat is de invloed van het aantal gebruikers op de zoeksnelheid, en wat is de invloed van het aantal documenten op de update-latency.

We zien dat de aanvoersnelheid in de gevallen v=0, v=10, v=20 updates per seconde geen significante invloed heeft op de updatelatency bij verschillende verversperiodes. Voor een aanvoersnelheid van v=50 updates per seconde zie je een hogere latency voor verversperiodes kleiner dan 2000 ms, dan voor 2500 ms. We hebben dit verder niet onderzocht. Daarnaast zien we dat de update-latency in de overige gevallen lineair schaalt met de verversperiode. Een tweede overweging is de interactie met de Blob Storage. We hebben daarom gemeten hoeveel data er vanaf de Blob Storage gedownload wordt per web-node, uitgezet tegen de tijd. Tijdens deze meting was de aanvoersnelheid 75 updates per seconde:

8

MAGAZINE

CLOUD

We hebben gemeten hoe de zoekperformance schaalt met het aantal zoekende gebruikers (gesimuleerd met meerdere threads) bij twee verschillende indexgroottes N (aantal documenten in de index). We doen dit door te zoeken op willekeurige zoektermen en de 10 meest relevante resultaten op te vragen: We zien dat een concurrency tot 25 threads per node in beide gevallen een zoeklatency van minder dan 100 ms oplevert. Bij 100.000 documenten is er nog ruimte voor hogere concurrency bij gelijke zoeklatency. Voor 1.000.000 documenten is dit echter niet het geval; daar loopt de zoeklatency snel op. Het aantal concurrent zoekopdrachten dat je per node kunt bedienen wordt dus beperkt door de indexgrootte.

Dit hebben we verder niet onderzocht. De updatedoorvoersnelheid van 100 updates per seconde is in onze gevallen toereikend geweest. We hebben daarom niet onderzocht of we deze nog hoger konden krijgen. De Indexer lijkt wel moeilijker uit te schalen omdat er maar één Indexer actief kan zijn. Deze eigenschappen maken dat wij Lucene een geschikte oplossing vinden voor het aanbieden van full text search in een Azure-omgeving. In de praktijk zetten wij de geschetste oplossing met succes in binnen meerdere projecten. We zijn hierbij niet tegen grote verrassingen aangelopen en zullen Lucene blijven overwegen voor nieuwe projecten. •

Roy de Boer

Tenslotte onderzoeken we hoe de update-latency zich gedraagt bij verschillende indexgroottes. Hiertoe meten we de update-latency als functie van het aantal documenten in de index N, bij verschillende aanvoersnelheden v.

Roy de Boer ([email protected]) is één van de oprichters van Infi. Naast een voorliefde voor C#, en de oneindige tocht naar elegant softwareontwerp, is hij ook nogal enthousiast over OS X en FreeBSD.

Freek Paans Freek Paans ([email protected]) werkt als technisch directeur bij Infi. Hij houdt zich voornamelijk bezig met het optimaliseren van het softwareontwikkeltraject binnen Infi, maar typt ook nog actief mee aan verschillende projecten. Verder vindt hij het leuk om na te denken over vrijwel elk vraagstuk in de softwareontwikkeling: van low-level performancewerk tot teamorganisatie tot conceptontwikkeling. Freek is ook te vinden op twitter onder @FreekPaans.

Het blijkt dat het aantal documenten in de index geen significante invloed heeft op de update-latency. Daarnaast is de gemeten ondergrens van de update-latency 2.0 s. Conclusie We hebben de Lucene API in het kort geïntroduceerd en de problemen om deze op Azure in te zetten uiteengezet. Vervolgens hebben we een architectuur die deze problemen oplost voorgesteld en de karakteristieken hiervan doorgemeten. We hebben de volgende observaties gedaan voor een implementatie die gebruik maakt van Azure Service Bus voor queueing en Azure Blob Storage voor persistent storage voor de index: • De zoeklatency is bij indices tot 1.000.000 documenten en een concurrency van 25 threads minder dan 100 ms. • De indexgrootte heeft een duidelijke invloed op de zoeklatency: grote indices hebben in het algemeen een hogere latency en beperken bovendien de concurrency per node ten opzicht van kleinere indices. • De indexgrootte heeft geen significante invloed op de updatelatency. • We kunnen tot 100 updates per seconde op de index doorvoeren, hiervoor is wel een batch size van minimaal 200 berichten vereist. • Bij een verversperiode van 2.5 s zien we een update-latency van 4 seconden. • De traffic van de Blob Storage wordt niet significant beïnvloed door de verversperiode. Lucene op Azure is daarmee binnen onze projecten een schaalbare oplossing gebleken. Binnen een node vinden wij de performance van Lucene acceptabel en je ziet bovendien ook lineair gedrag bij het bijschakelen van web-nodes. Uiteindelijk zal de Blob Storage waar de index op staat mogelijk een bottleneck worden.

1

We gebruiken in de metingen documenten tussen de 0 en 3 kb. Mocht je meer vragen hebben over de meetmethode dan kun je deze per mail aan ons stellen.

TIP:

Downloaden SDN Magazines Op de site van SDN vind je niet alleen een archief van alle magazines, het is ook mogelijk om de magazines te downloaden: www.sdn.nl/magazine.

magazine voor software development 9