Performance – When do I start worrying?

A common problem of the application designers is to predict when they need to start worrying about the Architectural/System improvements on their application. Do I need to add more resources? If yes, then how long before I am compelled to do so? The question is not only when but also what. Should I plan to implement a true caching layer on top of my application or do I need to shard my database. Do I need to move to a distributed search infrastructure and if yes when ! Essentially we try to find out the functionalities of the application that will become critical over time.  The reasons that a nice working functionality becomes critical over time are mainly two –

1. Volume – The data is increasing over time, so some queries that work pretty well now become inefficient over time.
2. Concurrency – The traffic has increased and simultaneous usage has made the system inefficient.

The problem definition hence becomes to find out critical pieces of inefficiencies in the presence of future data and future traffic.

The performance tools like loadrunner don’t look suitable for this job. They certainly work well to find points of inefficiencies from a black box perspective but you are the owner of your own application. You can do better ! Moreover, these performance tools will help at the testing phase but not so much in the planning phase. Here we will not focus on end to end performance but the most critical part of it – The efficiency to retrieve the result for the queries (from the Backend perspective), simply because we want to estimate not tune. After going through the rest of the post, you may ask – do I need to do these modeling or make an educated guess or simple calculations of the future data and performance. Don’t let this post mislead you, you must do that if you can. Any quick, handy, estimated result is certainly gold. Moreover, a mathematical model will work far superior than any simulated model, but  unfortunately, in most cases, it may be quite difficult to do so.

Now, if you are writing your own performance tool, a big question is – will you write a tool that will emulate users similar to loadrunner and start hitting the application and keep running on the stage server in real time ? That may be a bigger and more resource consuming project than the application itself ! Well, you won’t have to. The concept of the proposed performance tool is based on Discrete Event Simulation(DES). The badly sketched picture below aims at describing the steps.

Modeling Users/Traffic : The first step is to model the user behavior, for example – how many users of the application are 1) heavily active 2) moderately active 3) one time visitors. You also have a growth rate of users (actual or projected). The users come and browse through pages (read actions) and make certain actions (write actions). If you have structured the application well, the user action simulation (using the model classes) should not be a difficult job. The above three partitioning of users is just an example. Since you know your application best, you can make your own models and categorizations.

Events :  The above actions are events in the context of DES. Each event triggers another event after a time span. If you have to choose the next event from a set of n events, use some analysis and put a probability on each of them. The time interval of next event can be chosen randomly with mean sitting at the average time between clicks. Those values will be different for different categories of the above user categories. You will also have to put a period to the return of those user types and again choose randomly (at run time) between the typical values. To model growth rate, introduce another event which adds a calculated amount of users with fixed periodicity. If there are other sources of write actions like a crawler, add suitable events for them.

Simulation: Now since we have modeled the future traffic and events, we need to bootstrap it with the current average load which is pretty simple. Note that, Unlike, a thousand thread load generator, it is a single threaded simulator and it jumps to the head of the event queue without waiting for the real time to elapse. This is depicted pictorially below. You may skip most of the read queries (from actual firing) and just focus on writing a parametrized write queries, which will be adding simulated data. For most cases, you will be able to emulate the system run of few days in few hours.

A list of DES tools that might help is given here.

Inference: After the end of the simulation, you have a snapshot of the simulated future data and a load profile containing sets of concurrent events (read actions). The concurrent events are defined by the set of events occurring within a time span in the load profile. By varying the window, you can over/under approximate the actual concurrent load. Simply by looking at the events, a lot of insights can be derived of the future behavior. Now a simple multi-threaded query executor can fire up these queries simultaneously for the peak window and see the response of each query is acceptable or not under concurrent load. You can better predict the type of improvements that is suitable for the specific application by looking at the events and the responses. For starters –

• Are they locking on some bottleneck ? (distributed instance of that module?)
• If a significant chunk of queries are actually the same ? (caching?)
• How many of queries are independent of each other ? (replication, sharding?)

By running the simulation repeatedly for few days at each stretch, and doing the analysis after each run, you can also get an idea about when the application will start to become critical and by when it will break down completely. Again, it will not be accurate to the calendar date but on a high level – is it weeks/months/years?

I have kept this post procedural for simplicity but all parts are not a must have and may not be or can’t be followed exactly. If you can project the current load profile to future and just use this method to add data, such optimizations might lead to quicker estimation and hence always preferable. Whatever you need to do, you must do to get these estimations as quick as possible and as close to the reality as possible. The blog started with the question, “when do i start worrying? ”  – Well If you have stopped, then probably you are going out of business as well.

The Art of Slicing Data

Sharding, is a common way of distributing database load. Simply explaining sharding – if a database contains the data of X users and getting overloaded (due to large size), it is divided in to two databases (two shards) each containing the data of X/2 users. So, with all probabilities, the load will be distributed evenly between the two databases. Note that, when the application has 2X users, each of these databases runs in to the same problem and need to be mutated in to two again. So in a way, the scaling is linear. My intention behind this post is – Since we are taking the pain to divide a single convenient database to two (or multiple), is there a possible sharding strategy which will perform better than the linear scaling in performance?. Of course, if this better strategy (if any) would apply to all type of applications (like caching), we would not have been discussing this here. Thus, while reading the post, please mark the inherent assumptions.

As we proceed, we will encounter nothing new, but the terminologies we are familiar with – Archiving, Caching etc. The more I think about it, the difference between these terminologies blur. Statistically, for a typical application, 5% of the data is used 95% of the times and 95% of the data is used only 5% of times. The reason is simple in the context of web applications – they typically display items in reverse chronological order, which is obvious. Now given this, let’s see if slicing the data by time can give us better benefit than linear scaling. Please note the assumptions stated above in which we are trying to find a better solution. If your application does not fall in to the above pattern, it might not be a good solution for you.

With the above background, let’s consider dividing the data in to two parts. One is the Active Shard with recent 5% of data (both entities and relationships) and the other one with Archive Shard with 95% of data. Any query of the application is expected to get results from the Active shard and if required calls the Archived Shard for further result. For example, data for the first page an application is in the active shard and the subsequent pages are in the Archived Shard. It may be required to query both shards at the same time and merge the result set.

By above, what we have achieved is that we are directing 95% of the queries to the shard that has 5% (1/20th) of data as opposed to linear sharding (1/2 of the data). If you have agreed with me peacefully so far, may be you are not paying attention! I have assumed that the recent 5% of data is the exact 5% of data where 95% queries will be going. Though the data is reverse chronologically sorted, the assumption might be incorrect for some cases. Again, go back and think through if splitting the data by recent 5% will be a good approximation for your application. May be the recent 5% data per user is a good start ! Anyways, moving forward, an obvious question is what about the 5% of the queries that are getting fired over a shard that has 95% of data! Will the 10th page of my application will take for ever to load?

The answer to the above is that since now there are fewer queries on the large Archived Shard (both read and write), different set of database optimizations can come in to play and again it is a different but relatively simple design problem. Possible solutions can be –

• Cache – Putting a caching layer (like memcache) before the Archived database. Since there are fewer selects and updates, a relatively high timeout can be set on the cache expiry. Even strict timeout cache (in case of updates) will work good since there will be fewer updates
• Database optimization – Both shards here need to be optimized in different ways. Optimize the Active shard for low sort, read buffer, higher threads (Example: for Mysql look here). Optimize the Archive shard for high sort, read buffer but fewer threads. Several other things like Query Cache in case of Mysql will offer significant value on Archived database as number of updates are less (the query cache will remain valid for long).
• Pre-Calculation – Since number of updates are less on the Archived Shard, a lot of functions can be pre-calculated. For example, if a query is accessing a large result set sorted by some parameter and accesses the data not in the first few items (limit 10000,100), it results in a performance issue. In fact its a wel-known DOS (denial of service) attack. In our current design, this data is probably going to lie in the archived shard. Since updates are less, the data can be pre-paginated easily. I am thinking of posting a detailed design of the same later. On the similar lines, more efficient methods can be devised to exploit the slow update characteristics on the Archived Shard.

The above illustrations of 2 shards can be extended by partioning the Archived shard in to multiple Archived shards.  The readers may extend the thought to create their own hybrid sharding strategy. Several directions on optimizations can also evlove. For example, if an entity is created in ith shard out of n time sliced shards, then all relationships exist only from ith shard to the nth shard, hence any query requesting for the relationships of that entity need not be fired to the shards from 0 to i-1. There are of course pros and cons to the given approach and a traditional approach. I will leave that up to the readers to analyze in the context of their problem in hand.

Basics of Architecting

If all the specifications were given at the time of building an application, there should not be an excuse for a bad design. However, in the context of web application development, life is not so simple. Your product goes through iterations that changes the basic principles for which the application was initially designed. Every time, of course, you can’t start from scratch. The changes that you make to incorporate the new iterations often leads to sub-optimal designs.

The key principles to remember for a designer are as follows –

• Understand your application better. Every application is different from each other at the same time may have some basic patterns in behaviour that others have. Don’t adopt to the best practices blindly but do analyze them critically in your context.
• Plan ahead. Assume possible changes in applications, traffic to grow beforehand and start incorporating necessary changes to handle them in your design.
• Bring out Abstraction and Automaton. Abstractions speed up the development process while Automaton reduces errors.
• Validation of designs is a must. If there are non-trivial aspects of the design, validate them before going in to development cycles.
• Design your system for faults. Remove single point failures. Design it in a such a way that the application can remain in downgraded mode in the presence of these faults. Ensure data integrity the least.
• For any releases that incorporates considerable design changes, have a back up plan before hand. Never assume that the live system will behave the exact way the test systems did.