Update HBO Kennisbank

De afgelopen weken hebben we gewerkt aan HBO Kennisbank. De release hiervan moet nog plaatsvinden, maar graag laten we alvast zien wat er is toegevoegd. Tot op heden was niet duidelijk zichtbaar welke hoge scholen bij HBO kennisbank zijn aangesloten. Daar komt nu verandering in.

HBO Kennisbank

Wat wij hebben gedaan is het filter uitgebreid. Alle deelnemende scholen worden bovenaan in alfabetische volgorde getoond met daarbij de vermelding hoeveel artikelen er beschikbaar zijn. De technische verbetering zit hem met name in het anders tonen van de organisatiefacetten.

Daarnaast hebben we ook de bestaande software bijgewerkt. We zorgen er graag voor dat onze klanten kunnen profiteren van de nieuwste functionaliteiten en prestaties die gerealiseerd zijn in andere projecten gebaseerd op dezelfde software componenten.

 

Multi-threaded expert search with Lucene

Lucene’s high-level search API parallelizes search automatically, achieving superb performance.

The low-level expert API does not do that.  Here is a solution to parallelize custom search. It is Open Source.

Introduction

The Open Source search engine Lucene has evolved into a very smart and efficient search tool.  It offers both high level search interfaces as well as low-level (expert) interfaces. If you pass it an Executor, the high-level interface (API) automatically enables all the CPU’s in a server to work on your queries as fast as possible.  The results are downright fantastic.  For quite large data sets and quite complicated queries, you will get results in milliseconds.

Concurrency and the expert interface

However, the low-level API does not put all your cores to work automatically.  That means that as soon as queries become more complicated and you have to use the low-level API, it runs slower.  That is not a problem as long as you limit the number of documents to, say, 10,000,000. Most functionality like sorting and facets still runs in a few 100 of milliseconds. But when you have many more documents and when you must support many concurrent queries, the help of more CPU’s would be very nice.

Before I introduce our solution, a quick word about the so-called expert API and the problem with it.

How the low-level API works: Collector

The main work of any search engine consists of intersecting, intersecting and yet more intersecting. Lucene’s low-level expert API gives a programmer access to the inner loop that performs the intersecting. Lucene has a hook that, regardless of what intersection algorithm it uses (zip, gallop, bisect, skip lists, and so on, look for “integer intersection algorithms”), it calls your code as soon as it determines a document is in the set defined by your query.

The hook consists of an interface called Collector, that has a method collect().  When you pass an object that supports this interface, Lucene will call collect() for each result.  This method must be very short, small and fast, since Lucene will call it many, many times.

The problem is that the search methods that accept a Collector do not enable threads and leave all but one of your CPU’s idle.  There is a good reason for that.

The problem with Collectors

The Collector interface is inherently thread-unsafe.  The reason for this is the way the setNextReader() method on Collector works. Internally, Lucene maintains an index composed of tens of segments each containing a subset of the complete index.  During search, Lucene tells the collector that a new segment starts and that the following calls to collect() are in the context of this segment.  All but the most trivial Collectors need to remember this context and this is why the Collector is unsuitable for multi-threading.  What if two threads call setNextReader() with different arguments?

Using Lucene’s internal segmenting to divide the work is quite natural. Indeed, the high-level API divides the work based on segments.  What if custom Collectors could also use this?

SuperCollector and SubCollector

We designed two new interfaces that are much like the Collector, but just different enough to support multi-threaded search for any operation.  The first is SuperCollector.  It basically replaces Collector in the call to search().  So instead of (pseudocode):

searcher.search(query, filter, collector)

we use:

searcher.search(query, filter, supercollector)

That’s all.

The SuperCollector creates subCollectors that are thread-safe:

subcollector = supercollector.subCollector(...)

The new search() method calls the method subCollector() for as many threads it wants to create. SubCollector is almost identical to Collector.  If fact, it is a subclass of Collector. It supports the setNextReader() and setScorer() methods and of course collect() and it adds only one more method:

subcollector.complete()

The thread executing the search calls complete() after it is finished. Some collectors do most of their work during collect() calls, but others just collect data for post-processing later.  Such collectors can put time-consuming post-processing in the complete() method so that it executes in parallel as well.

Encapsulating existing code

The nasty thing about the Collector API is that once you start using it, the simple parts of your query, that used to be automatically parallelized by Lucene, will now be single-threaded as well. Therefore we also need to create Super/SubCollectors for simple queries.

Simple queries are queries with results sorted on score or on a field value. The parallelization is spread across the Lucene code. We found it and encapsulated it as follows:

  1. Some code in the search method at lines 450-456 and lines 535-547 creates the threads.  We replace this code with one generic piece in search().
  2. Code for creating the TopFieldCollector at line 535 for sorting on a field while the case for sorting on score is degelated to SearcherCallableNoSort which will delegate further until a TopScoreDocCollector is finally created at line 490. We encapsulate this in specific subCollector() methods.
  3. Code for merging the results at lines 460-471 (sort on score) and at lines 550-559 (sort on field). We encapsulate this in SuperCollector.

Example: TopFieldSuperCollector

Here are the results for applying the encapsulation outlined above to the way Lucene’s default TopFieldCollector works.  These are the important steps:

First, the TopDocsSuperCollector creates the proper SubCollector when search() asks for it:

TopFieldSubCollector
createSubCollector() {
    return new TopFieldSubCollector(...);
}

The search continues as normal.  Lucene calls collect() for each result found, but this happens in a thread.  The TopFieldSubCollector simply delegates to a standard Lucene TopFieldCollector.

The search signals completion of the segment by calling complete(), which simply delegates again:

void complete() {
    this.topdocs = this.delegate.topDocs()
}

Finally, the merge happens when the application asks for the result by calling topDocs():

TopDocs topDocs(int start) {
    for (TopFieldSubCollector sub : super.subs) {
        // merge results from subcollectors
    }
    return topDocs
}

What next?

The concept above has been implemented for simple search and shows very much speed-up.  We now have to create Super- and SubCollectors for the other functions we use:

  1. for sorting by relevance: TopDocsCollector
  2. for calculating facets: FacetCollector
  3. for creating trees of collectors: MultiCollector
  4. for de-duplicating results: DeDupCollector
  5. for query-time join: KeyCollector and ScoreCollector

For each of them we are working out the design and then we will add them. I will post the results when we are done.

Meanwhile, you can follow the code here: Meresco Lucene.

Debian Jessie

Met enige regelmaat worden voor Debian, de Linux distributie in gebruik bij Seecr, updates uitgebracht. Eind dit jaar staat er weer een nieuwe versie klaar van Debian; Debian Jessie. Eén van de verbeteringen is een nieuwe versie van de virtualisatie software.

De verbeteringen in de virtualisatie software zijn het gevolg van continue nieuwe ontwikkelingen gedragen door de open source community. Zij zorgen ervoor dat er nieuwe features ontwikkeld worden, fouten worden opgelost en de performance optimaal blijft.

Wij zijn graag goed voorbereid. Nieuwe versies willen we graag snel en zonder problemen kunnen migreren. Daarom zijn we al gestart met de voorbereidingen. Na het afronden van deze werkzaamheden zijn we voorbereid op de nieuwe versie van Debian en zijn kwaliteit en continuïteit gewaarborgd.

Kort samengevat bestaan de voorbereidingen uit:

  • het kunnen creëren van een virtuele machine waarin de nieuwe versie van Debian wordt geinstalleerd;
  • het aanmaken van een repository zodat software pakketten snel en zonder problemen geinstalleerd kunnen worden;
  • de benodigde tooling aan te passen die onze software ontwikkeling en deployment tot een gestroomlijnd proces maken.

 

 

 

Relevante zoekresultaten door middel van ranking

Het is bijna traditie in de bibliotheekwereld dat er (eindeloos) wordt getweakt aan allerlei ranking-parameters. Dit is echter een doodlopende weg, daarom heeft de NBC+ een topic rank en een static rank geïntroduceerd.

Topic rank
Topic ranking heeft alles te maken met de functionele/technische integratie van verschillende types objecten in één search engine. De NBC+ beschikt over verschillende soorten objecten zoals boeken, muziek, krantenartikelen, evenementen e.d. De uitdaging is om het ene object niet dominanter te laten zijn dan het andere. Miljoenen krantenartikelen kunnen eenvoudig honderden events overschaduwen.

Dit is opgelost door te denken over objecten alsof ze een relevantie hebben ten opzichte van een onderwerp (de topic rank). Daarmee wordt afgestapt van de traditionele gedachte dat hoe vaker de zoekterm in een object voorkomt, hoe hoger de score (term frequentie) is. Dit geeft een goede basis voor de volgende stap, de static rank.

Met een topic rank ontstaat een ranking met een technische waarheid. De algoritmes vinden een bepaalde relevantie en hebben daarin op een bepaalde manier altijd gelijk. Zo vinden deze algoritmes bij de zoekopdracht “tirza” verschillende groepen resultaten die allemaal even relevant zijn (boek “Tirza” van Grunberg, serie jeugdboeken met Tirza in de hoofdrol, etc). Maar collectiebeheerders willen soms bepaalde resultaten meer onder de aandacht brengen.

Static rank
De oplossing hiervoor is een static rank. Dit is een aparte index met hierin een rank voor elk object. Deze rank wordt statisch bepaald aan de hand van verschillende eigenschappen van het object of simpelweg volgens de wens van de beheerder. Bij het zoeken kan deze ranking worden meegenomen om de resultaten, na de toepassingen van de topic rank, te herwegen.

Statisch maar wel dynamisch
De beheerder kan heel specifiek aan de hand van allerlei mogelijke wensen de ranking doorvoeren. Boeken scoren bijvoorbeeld iets hoger, net als recente objecten en alle Nederlandstalige dingen. Het is ook mogelijk om de hoeveelheid door bibliotheken aangeschafte exemplaren te laten meewegen of eenvoudigweg de bron. Ook de leeftijd (van de doelgroep) kan als rank worden meegenomen.

In de NBC+ is deze static rank voor aangesloten partijen afzonderlijk te configureren. Elke bibliotheek kan er zelf invulling aan geven. In die zin is ook de static rank dynamisch, het kan zonder meer worden aangepast en de resultaten zijn direct zichtbaar.

Deze twee-traps ranking draait nu proef en zal in oktober in productie gaan.

Geen verrassingen meer…

Vandaag vindt er een nieuwe release van het NBC+ Zoekplatform plaats. In deze release zit onder andere de nieuwe feature: verkrijgbaarheid. Deze feature is nog in testfase, maar we willen hier alvast graag meer over vertellen.

Verwijzing naar bron zoekresultaat
Een zinvolle search engine zal gebruikers altijd moeten leiden naar de bron van het zoekresultaat. Bij internet search engines is dat eenvoudigweg naar een webpagina. Bij de NBC+ kunnen dat ook verwijzingen zijn naar bijvoorbeeld onderstaande services:

  • reserveren (eigen bibliotheek)
  • aanvragen (landelijk)
  • downloaden e-book
  • inzien (betaald/online)
  • inzien op locatie
  • inzien online + abonnement
  • streaming (preview)

Als je bijvoorbeeld op zoek bent naar een boek zijn er vaak meerdere mogelijkheden om het boek te kunnen verkrijgen. Wij hebben een methode ontwikkeld die de verwijzingen naar alle services mogelijk maakt. Per zoekresultaat wordt op gestructureerde wijze aangegeven wat de opties zijn. Dit hebben we bereikt met (een uitbreiding op) de “Document Availability Information API” (DAIA), zoals ontwikkeld in het Gemeinsamen Bibliotheksverbund.

Geen verrassingen meer voor de gebruiker
Met deze feature is het in de zoekresultaten nu direct zichtbaar waar je naar toe wordt doorverwezen met daarbij de informatie wat die verwijzing inhoudt. Geen verrassingen meer voor de gebruiker wat er bij volgende stap kan worden verwacht. In één oogopslag zijn alle mogelijkheden tot verkrijgbaarheid zichtbaar per zoekresultaat.

 

 

Multi-threading and optimizing speed-up (Infographic)

Below is an #infographic about how a multi-threaded application in general behaves, including text balloons with suggestions about where to look for improvements.

I created it because I wanted to explain to a colleague what I did to improve Lucene’s faceting performance using 16 CPU cores.

I hope it speaks for itself.

Infographic about Multi-threading

Infographic about Analyzing and Optimizing Multi-threading (and why you don’t see linear speed-up in most practical cases)

Perfecte match met XFS

Bij toeval hebben we ontdekt dat XFS  een perfecte match is met de door ons recent ontwikkelde SequentialStorage. XFS is een file system dat we al jaren gebruiken, maar dat het zo’n goede combinatie is, hadden we van tevoren niet verwacht.

Laatst constateerden we in Gustos, ons systeem voor Continubeheer, een fikse toename van diskverbruik die niet in verhouding stond met de toename van de data. Om dit te kunnen verklaren, zijn we in het file system gedoken.

We hebben ontdekt dat XFS  bestanden herkent waar veel naar wordt geschreven. Bij die bestanden wordt extra aaneengesloten ruimte gereserveerd. De gereserveerde ruimte wordt door de standaard tooling aangegeven als zijnde ‘in gebruik’. Na onderzoek en de juist tool de goede vraag te stellen, kwamen we erachter dat XFS tijdig de gereserveerde ruimte automatisch weer vrijgeeft als er een ruimtetekort ontstaat. Goed geregeld!

SequentialStorage
Dat XFS de ruimte weer vrijgeeft, is wat wij willen voorkomen. Die ruimte werkt juist in het voordeel met SequentialStorage. Dit onderwerp is de moeite waard om een apart technisch artikel aan te wijden. Maar kort samengevat hebben we SequentialStorage ontwikkeld omdat we vaak tussen systemen dezelfde stroom data in dezelfde volgorde moeten ophalen. Door alle records achter elkaar op te slaan, is het haalbaar om data snel en sequentieel op te leveren.

Als wij weer signaleren dat de disk vol dreigt te lopen, weten wij wat ons te doen staat.  Wij geven XFS graag de ruimte.