Implementing an autosuggest servicePosted on by Joaquin Perez
We recently hit a milestone: serving the whole set of desktop traffic for flights autosuggest. This new service was added to the previously running autosuggest for Hotels and Car Hire.
Before we created this service, we knew that one of our main objectives as a squad would be to establish a unique model/architecture for the autosuggest service that could be applied to all of the Skyscanner verticals. Taking ownership of autosuggest for flights implied many challenges and new data. It also required a growth in infrastructure and the ability to support 15 times the current requests per second.
Here’s how we did it.
Autosuggest: reliability, stability, predictability
Autosuggest is in many cases the first entry point to our services. Normally the first thing a user does is search for a place to fly, stay or maybe rent a car. A service like this must include at least the following features: reliability, stability, and predictability. These three properties should help the user to find what s/he is looking for, or at least suggest to them the most likely results based on their input.
Building our autosuggest service includes at least three main different stages. Firstly, we need to generate the entities (cities, airports, hotels, streets…) and the links between them. Secondly, we have to store this data in a way that will allow us to search and retrieve the results using partial, prefixed, or fuzzy matches. Finally we create an endpoint to query this data. We assign a value of relevance to all of our entities based on the user query and add some other magic to supply the user with the best possible subset of results for a specific query.
How we obtain or generate this data is out of scope of this post, but we are currently looking to index all the world’s cities, airport or streets, including synonyms for some entities and translations for the different supported locales.
Next, I’ll try to explain the rest of the process based on the current deployed architecture.
The autosuggest stack is based mainly in Jetty, Solr and a lot of Java code, besides which we use an in-house key value mapstore called Kraken, which is written in C++. The first entry point to our service is a Jetty-based handler that we call ‘distributor’. This endpoint currently supports more than 200 requests per second and is able to scale horizontally. This service is responsible for the entire logic happening when a user submits a query, until a Json, CSV or XML response is returned including the ranking of entities more suitable for their specific query.
This logic includes submitting the request to our repositories of entities (Solrs), combining the obtained results, filtering, reordering the results, prettifying these results, and finally returning them in the requested output format.
All the entities are indexed using Solr (http://lucene.apache.org/solr/), which is a framework specifically indicated for text retrieval. In order to give our users the most accurate suggestions for their queries, we index our data in a way that allows us to find partial matches. In addition, we support different names for the same unique entity, as for example happens with New York or NYC. Supporting different literals to identify the same entity allow us to increase our coverage capacity, which from the user point of view implies more clever suggestions for different inputs.
We create different indexes based on the pair language/entity_type, which means we have different indexes for cities, hotels, streets, regions, and points of interest (airports, monuments, etc.) for each one of the supported locales. In summary, as we currently support 31 different locales with five different types of entities, we’ve built 31 * five indexes. That’s 155 indexes, which as you have probably realised already, means a lot of dedicated infrastructure for this service.
Obviously performance is a must in an autosuggest service; there is nothing worse from a user-experience perspective than a service of this type with a lot of lagging. For instance, our requirement for the flights vertical is replying in less than 20ms (currently as an average we are doing it in less than 10ms). This means the first requirement is putting everything in memory; we don’t want to search in any secondary storage, a consequence of which is that we must keep indexes as small as possible to be sure they fit completely in RAM. In order to achieve this we need to use an external key map store. This alternative storage contains all the necessary data to build a response understandable by the user, but which it is not required to be indexed.
The Kraken service, as mentioned before, is our in-house key value storage, developed and maintained by us. This storage service guarantees constant performance – on average, Kraken is able to return the related values for a key under 4ms when requested from the same datacentre.
In order to increase the availability and fault-tolerance of our services, all this architecture is duplicated in each datacentre and replicated across all datacenters.
Learning to Fly
Moving our Flights autosuggest from the old to the new version implied a significant number of changes in our side, which I will try to explain below.
The first step was to import all the necessary literals from the flights database; this data included the airports names, IATA codes and in addition the cities where these airports are located. All these literals can be found in the different supported locales by Skyscanner. Once we acquired these literals we indexed them, allowing a type of search similar to the one presented in the Hotels or Car Hire services. In addition to importing the literals, we included the ranking of each city and airports of the country when available. This ranking applies an order to some of the entities for each market by popularity, which means that for instance for the UK market the most popular search term is ‘United Kingdom’, followed by the city of London.
The second step was to mimic the old autosuggest endpoint API. This allowed us to send the same request to both versions, simply by changing the parameter version and therefore we could support exactly the same syntax and semantic as the former autosuggest service.
At this point we were able to deploy an alpha version. After this deployment we were in the position of measuring the quality of our system. To measure how good the responses of this new version were, we launched 100 queries for each locale and compared the results obtained by both versions to check if the results were good enough for this new implementation. Finally, after some iterations improving the quality of the data and adjusting the scoring system, we achieved a system which satisfied the established criteria.
After a lot of work we are happy to say that the objective was achieved; our autosuggest is in place for the three main Skyscanner verticals, without affecting conversion rate measures for flights, which was the main purpose before starting this task.
Now, we are in the position of increasing the quality of this service, trying to give the best possible suggestion to any user input. It’s worth emphasising the magnitude of the challenge we tackled, and it is testament to these improvements that we’ve seen a real increase in the number and speed of autosuggest requests since.