Performance and Scalability with Redis NoSQL Database

Introduction

Hibernate is a great technology, it frees developers from the pain of database schema creation and the maintenance of object-relational mapping code. They are free to create rich domain models quickly and easily! But with this simplicity comes a hidden danger, these highly normalised data models may mirror the problem domain accurately giving you a warm fuzzy feeling, but under load they are unlikely to perform or scale well!

In this article I present a scenario where the Redis NoSQL database was used to complement a rich domain model in MySQL to achieve dramatic performance improvements and near linear scalability.

The Problem

We have a social networking site for meeting new people, the homepage is a News-Feed, the News-Feed consists of News-Items of different types. News Item types include but are not limited to:

• Someone Likes you.
• A Match, (you both like each other).
• Someone Viewed you.
• A New Member matching your criteria.
• An Upload by someone you like.
• etc etc

The News-Feed looks like this:

The News-Feed is the aggregate of all the different types of News-Items sorted by their timestamp.

Additionally we want to be able to filter on just one News Item type, e.g. show a list of just one News Item type such as Who Likes Me.

And above all, this has got to be fast, really fast, it’s a homepage after all and our users expect a near instantaneous response.

The Relational database trap

MySql (Percona) is our authoritative datastore, as a relational database it brings a lot of advantages with it. We used Hibernate to build this system, and on top of that we used Spring Roo to generate our domain entities (Domain Driven Design). This gave us huge advantages in speed of development, we pretty much drove the creation of the domain layer by writing Roo script and Hibernate took care of the data access layer. Roo even helped us by generating some simple starting point finders in JPQL.

After this, we pretty much had a one-to-one mapping between a News Item and a relational database table sitting underneath, it looked something like this:

It seemed pretty straight forward, especially when we had no site traffic, to create these News-Items by pulling them out of the database with a straightforward SQL Select statement.

We modified the JPQL a little to include some JOINs to filter certain records out etc, and functionally it worked well. 

For the aggregate News-Feed, the easiest way forward was to issue several bounded database queries, combine the results and sort by timestamp in the application. We knew it wasn’t too pretty but this was a minimum viable product, we had no traffic and were keen to get this product out into the real world!

To our delight the site was well received and we watched Google Analytics intently as traffic numbers rapidly grew. Pretty soon we needed to scale…

Vertical Scaling will only get you so far.

A bit of poking around with New Relic confirmed what we initially suspected, the performance bottle necks were centred around the data tier. Optimisation wouldn’t be immediate, so to buy time we threw more hardware at it, aka vertical scaling. This is an acceptable short term approach, hardware scaling including provisioning greater memory and faster IO usually makes stuff quicker, but eventually you will hit a ceiling and in the meantime you’ll be spending far more cash on hardware than you’d like. It was time to address the data tier…

Optimising the Data Tier

Relational query optimisation shouldn’t really be left until you have a problem before being addressed. There’s a lot you can do with the sql explain statement and you’ll get tremendous insight into the operation of your queries if you do. Engineering queries and database indexes to mirror each other will in most cases yield orders of magnitude performance improvements with large datasets. With Hibernate you should also analyse the fetch strategies between objects to minimise n+1 problems. Furthermore, compared to re-architecture or database denormalisation, these are comparatively cheap exercises in terms of developer time and buy you a lot of scalability. I’ve written more about this here.

Other ways to scale a relational database.

If you’ve exhausted the avenues suggested above there are other ways of scaling a relational datastore. Firstly consider database read-replicas. These work fantastically well where there’s a strong read bias on your database load, which is the pattern you see on most web apps. Most sites see 90%+ of their DB queries just being fetches, and for sites like StackOverflow or Wikipedia I’d say it’s probably 99%+. Database sharding is also another valuable technique to consider for very large datasets, I won’t discuss it here.

Recap

Optimising our queries and the clever use of SQL Joins bought us well over 10X performance gains with our current hardware and dataset. However we could foresee that this approach wasn’t going to scale well for the News-Feed going forward. We were also aware that we were not the first to travel this path. Our site has a lot in common with giants such as Facebook, Twitter and Tumblr. All have a News-Feed type user interface backed by an authoritative relational datastore, and all needed to find an alternative approach to solve their scalability problem once and for all. We took the time to research the architectural approaches used by these sites and the information made public by them was of great inspiration to us.

Redis to the Rescue

Redis is so much more than just another NoSQL database. It’s capabilities go far beyond a simple key/value datastore, sure it can operate like this, but it’s true strength lies in it’s ability to store and manipulate data structures at mind-blowing speed. Redis natively supports Lists, Sets and SortedSets. These data structures allow you to logically bundle data together in a data structure within a Redis database. A data structure can then referenced within Redis by a unique key that you define.

Choosing a Redis Data Structure

At first glance it appeared that the Redis List structure would be ideal for our holding our News-Items. Lists maintain insertion order and could work well as a fast backing store for us. However the SortedSet structure seemed an even better fit for our solution. Sets maintain exclusivity of their elements, but the SortedSet also orders it’s elements according to an associated numerical score. It quickly occurred to us that using our News-Item timestamp as the score would result in Redis handling our time-series ordering for us.

To save space in Redis, and to avoid unnecessary duplication of data we decided that the values we’d store in Redis would be ID references to data stored authoritatively elsewhere. These id references could later be resolved by consulting a separate Lookup Service in our service oriented architecture (SOA).

As I’ve mentioned above, our News-Feed consists of News-Items of many different types. We need to be able to distinguish between these types as they are retrieved from Redis, so we devised a simple protocol for storing byte streams in Redis:

Note: We actually support over 10 NewsItem types, but we’ll stick with these 3 to demonstrate our concepts.

The Inbox Model

Using a NoSQL database for anything other than key/value based cache (the origins of Memcached) requires a developer to think about data in a fundamentally different way. With a relational database you model real world data into relational tables, with a NoSQL store the developer needs to consider instead the data structure that lends itself most closely to how that data will be required by the application. 

In our case we are building an Inbox of News-Items specific to a user. In effect we are pre-calculating the News-Items that will appear in a user’s inbox before they even request that data. It is this Inbox approach that enables Internet giants such a Twitter and Facebook to serve up your timeline with blistering speed at immense scale.

Our News-Feed Inbox

With reference to the above protocol, creating a Redis SortedSet for each User’s News-Feed would look something like this:

This works great for the News-Feed view, but remember above I said we also had the requirement to filter down to a single News-Item type, e.g. so we could just show News-Item types for who Likes You etc. Retrieving just the values starting with R (likes you) is not possible in Redis, there is no Structured Query Language to fall back upon! 

This highlights one of the shortcomings of NoSQL databases that one has to keep in mind, if you want to cut and slice data according to criteria you may not have even thought of yet then RDBMS wins every time. With NoSQL you need to anticipate your data views or queries in advance and have a structure to match.

Given the above structure, in order to extract just the R values we’d need to fetch all values and filter the values in the application. Whilst this is certainly possible, it isn’t particularly efficient for the database or the application and makes features like pagination especially difficult.

Redis Set Union

Fortunately there’s a graceful solution to this. Redis offers powerful Set manipulation features including intersection and union operations. After writing some proof of concept code we decided that the best approach would be for each user to have an Inbox per News-Item type; we could then perform union operations within Redis to construct the News-Feed on demand. It looks like this:

To create the News-Feed we then instruct Redis to perform a union operation combining the Inboxes we specify. This is a very flexible approach, for some application views we may want to union almost all Inboxes and for others we may just union together a couple of Inboxes. 

The resulting Union operation on the above Inboxes would produce a SortedSet looking like this:

Union Performance

Initially we were concerned that these union operations would be computationally expensive for Redis and therefore slow, but in our proof of concept code we observed that Redis was able to union 20 Inboxes each containing hundreds of entries within single digit millisecond times. 

The resulting SortedSets were of course automatically sorted by Redis according to our timestamp based scores. This allowed us to retrieve subsections of the resulting structure based on the score thus making implementation of user interface features like pagination and lazy-load a breeze.

System Architecture

Putting the above into context, here’s how the News-Feed system architecture looks:

• Every thing you see here with the exception of Redis itself and the Message Bus is written in Java Spring.
• It’s a Service Oriented Architecture (SOA) with services defined as a set of interfaces.
• The logical flow starts at the top of the diagram, with various events, usually as a result of user actions resulting in the creation or modification of domain entities.
• The Business Logic Services communicate these actions to the Event Publisher which maps them to concrete classes within the Event hierarchy, these event objects are suitable for transport over the Message Bus.
• The Message Bus is asynchronous and provides guaranteed delivery of messages passed to it. It’s a fire-and-forget operation for the Event Publisher and decouples event publication from event consumption and the processing that follows.
• The Message Bus provides opportunity for multiple subscribers to consume the events it carries. The Redis Fanout Service subscriber is responsible for populating our Redis database, but we may add other subscribers to fulfil other purposes such as providing push style notifications to apps etc.
• The Redis Fanout Service consumes Message Bus events and fans them out to Redis. The ‘fanout’ terminology arises because a single event may result in multiple redis entries, e.g. a Match (mutual like) event will result in a Match entry being added to the Redis inboxes of both the users involved in the match.
• Redis Fanout Service creates an object of the RedisItem class hierarchy for each required redis entry.
• RedisItem subclasses encapsulate our Redis storage protocol introduced earlier. RedisItems have the capability to produce a byte stream representing themselves suitable for insertion into Redis or indeed to construct themselves once retrieved from Redis.
• Redis Service completely abstracts the Redis database from the rest of the system. It uses Spring Data Redis to simplify Redis interactions and enable us to code with familiar Java constructs and collections instead of native Redis commands.
• Redis Service is able to accept batches of RedisItems for storage and uses pipelining to submit multiple storage requests in a single I/O cycle thus achieving very significant performance gains.
• Redis Service provides a concise set of finder methods for querying Inboxes, results are returned as RedisItems. There are also automatic mechanisms here for fault detection, robustness and inbox reconstruction should a state inconsistency be detected.
• News Service is an example of a service that wishes to retrieve the contents of the Redis database, it is invoked by an MVC controller as a direct consequence of a user request. It may retrieve further information by consulting the authoritative Lookup Service, and produces ViewDTOs.
• The Lookup Service generally returns domain entities from their IDs. This provides opportunity to resolve these from a Level2 cache, there are many swappable options here ranging from EHCache, Memcached, another Redis database or some other datagrid. Only a cache miss results in load on the relational database.
• ViewDTOs are suitable for passing to the View of the MVC or can instead create a JSON representation for passing to a client such as an app.

Conclusion

This architecture allows us to satisfy client News-Feed requests within single-digit millisecond server execution times. In effect we are using the Redis as a sophisticated cache to serve precomputed result sets to individual users. However, our approach is only made possible by Redis’ native support for data structures combined with it’s breakneck speed with large datasets. User requests are resolved from Redis and are never synchronously blocked waiting for complex SQL queries to complete. This also opens the possibility of serving the results of more computationally intense queries such a recommendations, which would not be possible within an acceptable timeframe with a synchronous query. Furthermore, this approach scales in a linear fashion, Redis retrieval times remain near constant regardless of the dataset size.