Good day, colleagues!

Today I will tell you about how, without making a large number of changes in the application, to improve its performance. It will be about our small "bike" [1], designed to replace memcache in some cases.

The article is written according to my report “The circle of deception or the use of standard protocols for non-standard things” [2] on DevConf'12 .

Introduction

Recently, we have already talked about the architecture of the mobile advertising network Plus1 WapStart . If you have not read, you can read the link.
')
We are constantly engaged in monitoring "bottlenecks" in our application . And at one fine moment for us the logic of choosing a banner became such a bottleneck. The matter was complicated by the fact that over the years of the application, our code has acquired a large number of poorly documented business logic. And, as you understand, rewriting from scratch was not possible for obvious reasons.

The logic of choosing a banner can be divided into 3 stages:

1. Identify the characteristics of the query
2. Selection of suitable banners.
3. Cutoffs at runtime.

The stage number 1 turned out to be problematic for us. And the trouble came from no one was waiting for - from

Usually, we have all the data needed to determine the characteristics of the query in the cache and only a small percentage of the requests fall on the base.


But in the case when India comes to us, we have practically nothing in the cache and 70-90% of requests go to the database. This delivers certain problems and we give the banner a little slower than we would like.


And here we got the idea how to solve the problem of the speed of return of the banner.

Project "Fish": an idea

The idea can be expressed quite simply: we must always respond from memory. A request has arrived, we are polling the repository for the availability of data, if there is data - we immediately give an answer. Otherwise, we add the request data to the filling queue and respond with an empty response, not waiting for the data to appear.

Due to the fact that we use memcache for caching, it was decided to use its protocol to implement the designated idea.

Project "Fish": the first iteration

The implementation is fairly standard. There is a set of workers that accept connections (their number is configurable). Workers are accessing the repository for data. The repository gives the answer. In the case when there is no data, we add the request to the queue. In addition, there is a separate filling stream that takes requests from the queue and asks for information about them from the library. The resulting data is added to the repository.

The library can be any. In our case, it requests data from the database.

We changed the application logic so that the characteristics of the request are taken from our cache (a key is generated from the request and we ask for the get key_with_request_characteristics ). In this configuration, everything worked fine except for a few problems.

Problems and solutions

First, we faced the problem of deleting data. When the limit on the allocated memory was reached, the storage began to be cleaned. All existing data was viewed, the TTL was checked and, if necessary, the data was deleted. At this point, there were delays in the response due to the fact that the deletion is a blocking operation. We decided it is quite simple: we introduced limits on the size of the data to be deleted. By varying this parameter, we were able to minimize the loss in speed at the time of cleaning.

The second problem was the presence of a large amount of duplicate data in the repository (the same characteristics may correspond to slightly different queries). We have come up with the following improvement to solve it.

Project “Fish”: iteration two

In general, the picture remains the same , with the exception of two functional units that we added to the library.

The first is Normalizer . We normalize all requests (we bring to a standard look). And in the repository we are looking for data using the normalized key.

As I wrote above, a key is generated from the request. The key is composite. For ourselves, we decided to sort the parts of this key in lexicographical order.

The second is Hasher . It is used to compare data. Now we do not add the same data to the repository twice.

If earlier we stored a key-value pair, now we store keys and data separately. There is a one-to-many relationship between keys and data (one data can correspond to a set of keys).

And again, everything seems to be fine, but again we are faced with the problem of deleting data.

Problems and solutions

Removal is performed according to the following algorithm. We are looking for among the keys those that are already outdated and delete them. Then we check the data if there are such for which there are no keys left - we delete them.

Due to the specifics we get a large number of small keys. It takes a lot of time to check them all (even before the set limit for deletion) (for us and a few tenths of a second is a lot).

The solution here seems to me quite obvious. We added an index at the time of adding the key. If it is necessary to delete data, we go around the keys at a given index and delete them up to the limit, thereby minimizing the time consumption.

In addition to the deletion problem, there is still a “first request problem” - we respond with an empty request when there is no data. It is from the first version, but for us it is permissible and we do not plan to solve it in the near future.

Conclusion

For us, putting "fish" into battle allowed us to minimize the cost of rewriting the code. The application logic has not changed much, we just began to poll another cache. And now in the case of rare requests, we respond quickly and confidently.

This is certainly not the latest implementation (it can be considered an alpha), we are working on improving performance and related tasks. But now the code can be viewed on GitHub [3]. The project was named swordfishd [1]. In the same place you can find our other products sent to the mercy of open-source.

Links

1. Project "Fish"
2. Presentation of the report
3. Wapstart github