Caching data in web applications. Using memcached

Yuri Krasnoshchek (Delphi LLC, Dell)

I'll tell you a little about caching. Caching is, in general, not very interesting, you take it and cache it, so I’ll tell you about memcached, quite intimate details.


')
About caching, let's start by asking you to develop a factory for the production of rhomonium torsometers. This is a standard task, the main thing is to make a boring person and say: "Well, we will apply a standard scheme for the development of a factory."

In general, it is closer to factory production, i.e. where did the problem go from? The factory works very quickly, it produces our torsyometers. And to calibrate each device, you need a pure romonium, which you have to fly somewhere far away and, accordingly, while we are in the process of extracting this omonium, the devices lie uncalibrated, and, in fact, all production stops. Therefore, we are building a warehouse near the factory. But it is not free.



Go to the terminology. Just for us to talk about caching in one language there is a fairly well-established terminology.



The source is called origin ; warehouse volume, i.e. cache size - cache size ; when we go to the warehouse for a sample of the desired form, and the storekeeper issues what we asked for - this is called cache hit , and if he says: “There is no such thing”, this is called cache miss .



The data - our omonium - has freshness , literally - it is freshness. Fresheness is used everywhere. Once the data loses its natural freshness, they become stale data .



The process of validating data for validity is called validation , and the moment when we say that the data is invalid, and throwing it out of stock is called invalidation .



Sometimes such an insulting situation happens when we don’t have enough space, but we’d better keep a fresh omonium, so we find the oldest one by some criteria and throw it away. This is called eviction .



The scheme is such that from our browser to the backend there is a mass of links in the chain. Question: where to cache? In fact, it is necessary to cache absolutely everywhere. And whether you like it or not, the data will be cached, i.e. rather, the question is how can we influence it?



First you need to find good data for caching. Due to the fact that we are doing some kind of cache, we have one more intermediate link in the chain, and it is not necessary that the cache speeds up something. If we pick up the data badly, then, at best, it will not affect the speed, and at worst, it will also slow down the process of the entire production, the entire system.

It makes no sense to cache data that changes frequently. You need to cache data that is used frequently. The size of the data matters, i.e. if we decide to cache a blu-ray movie in memory, it's great, we will quickly get it out of memory, but, most likely, we will have to transfer it later over the network, and it will be very slow. Such a large amount of data is not commensurate with the speed of delivery, i.e. we have no reason to keep such data in memory. We can keep the disk, but we need to compare the speed.

By the way, you can google “programming latencies”. There, the site is very well given all the standard delays, for example, the access speed in the CPU cache, the sending speed of the Round Trip package in the data center. And when you design, you pretend something, it is good to look, it shows very clearly what time it takes and compared to what it takes.

These are ready-made recipes for caching:



This is the relevant HTTP Headers:



I'll tell you a little about some, but, in general, you should read about it. Basically, the only thing on the web is how we can influence caching — this is by correctly installing these headers.



Expires used before. We set freshness for our data, we literally say: “Everything, this content is valid until such a number”. And now this header should be used, but only as a fallback, because there is a newer header. Again, this chain is very long, you can get on some kind of proxy that only this header, Expires, understands.

The new header, which is now responsible for caching, is Cache-Control:



Here you can immediately specify both freshness, and the validation mechanism, and invalidation mechanism, indicate whether it is public data or private, how to cache them ...

By the way, no-cache is very interesting. By name, it is obvious that we say: cache everywhere, please cache as much as you like, if we say no-cache. But every time when we use some data from this content, for example, we have a form, and we submit in this form, we say that in any case, all your cached data is not relevant, you need to recheck them.

If we want, in general, to turn off caching for content, then we say "no-store":



These “no-cache”, “no-store” are very often used for forms of authentication, i.e. we don’t want to cache unauthenticated users so that it’s not strange that they don’t see too much or there’s no misunderstanding. And, by the way, about this Cache-Control: no-cache ... If, say, the Cache-Control header is not supported, then its behavior can be simulated. We can take header Expires and set the date to some past.

These all headers, including even Content-Length, are relevant for the cache. Some cache proxies may simply not even cache if there is no Content-Length.

Actually, we come to memcached, to the cache on the side of the backend.



Again, we can cache in different ways, i.e. we got some data from the database, do something in the code with them, but, in fact, this is a cache, we just got them to reuse it many times. We can use in the code some component, framework. This component is needed for caching, because we need to have reasonable limits on our product. It all starts with the fact that some kind of engineer comes and says: "Explain to me the requirements for your product." And you have to tell him that this will be so much RAM, so much disk space, such a predicted amount of growth for the application ... Therefore, if we cache something, we want to have limitations. Suppose the first constraint we can easily provide is the number of items in the cache. But if we have elements of different sizes, then we want to close it with frames of a fixed amount of memory. Those. we say any cache size is the most important limit, the most important boundary. We use a library that can do this thing.



Well, or we use a separate caching service, generally stand-alone. Why do we need some kind of separate caching service? Most often, the backend is not something monolithic, one process. We have some disparate processes, some scripts, and if we have a separate caching service, then the entire backend infrastructure can see this cache, use data from it. It's great.

The second point is that we have the opportunity to grow. For example, we put one service, we are running out of cash, we put another service. Naturally, this is not free, i.e. “And today we decided to scale” cannot happen. It is necessary to plan such things in advance, but a separate caching service provides such an opportunity.



The cache still gives us availability practically for free. Suppose we have some data in the cache, and we are trying to get this data from the cache. We have something somewhere falls, and we pretend that nothing has fallen, we give the data from the cache. It may, at this time, be re-lifted somehow, and there will be even availability.

Actually, we got to memcached. Memcached is a typical noSQL.



Why is noSQL for caching good?

By structure. We have a regular hash table, i.e. we get low latency. In the case of memcached and similar key-value storage, this is not just low latency, but in big-O notation, we have the complexity of most operations - it is a constant of one. And therefore we can say that we have some kind of temporary constraint. For us, for example, the request takes no more than 10 ms., I.e. you can even negotiate a contract based on these latency. It's good.

Most of the time we cache anything - pictures mixed with CCS with JS, some fragments of forms of the primer, something else. It is not clear what data, and the key-value structure allows you to store it quite easily. We can start a notation that we have an account.300.avatar - this is a picture, and it works there. 300 is the account ID in our case.

The important moment is that the storage code itself is simplified if we have key-value noSQL, because the worst thing that can happen is that we somehow corrupt or lose data. The less code that works with data, the less chance of spoiling, so a simple cache with a simple structure is good.



About memcached key-value. You can specify expiration with data. Work is supported in a fixed amount of memory. You can set 16-bit flags with a value arbitrarily - they are transparent to memcached, but more often you will work with memcached from some client, and most likely, this client has already captured these 16 bits for itself, i.e. he uses them somehow. There is such an opportunity.

memcached can work with wiki support; when we run out of space, we push out the oldest data, add the newest ones. Or we can say: “Do not delete any data”, then when adding new data it will return an error out of memory - this is the “-M” checkbox.



There is no structured uniform documentation for memcached, it is best to read the protocol description. Basically, if you type the memcached protocol on Google, this will be the first link. The protocol describes not only the formats of commands - sending, what we send, what comes in response ... It describes that this command, it will behave like this and that, that is, there are some corner cases.

Short on commands:



get - get data;

set / add / delete / replace - how we write this data, ie:

• set is to save, add new or replace,
  
• add is only to add if there is no such key
  
• delete - delete;
  
• replace - replace only if there is such a key, otherwise - an error.
  

It is in an environment where we have a shard. When we have a cluster, this does not guarantee us any consistency. But with one instance, consistency can be supported by these commands. More or less, you can build such constraints.

prepend / append - this is what we take and in front of our data we insert some piece or after our data we insert some piece. They are not very efficiently implemented inside memcached, i.e. you will still be allocated a new piece of memory, functionally, there is no difference between them and set .

We can save the data, specify some kind of expiration and then we can touch this data with the touch command, and we extend the life specifically for this key, i.e. he will not go away.

There are increment and decrement commands - incr / decr . It works as follows: you store a number as a string, then it says incr and you give it a value. It summarizes. Decrement is the same, but subtracts. There is an interesting point, for example, 2 - 3 = 0, from the point of view of memcached, i.e. it automatically handles underflood, but it does not allow us to make a negative number, in any case, zero will return.



The only command with which you can create some consistency is cas (this is the atomic operation compare and swap). We compare two values, if these values ​​are the same, then we replace the data with new ones. The value we are comparing is a global counter inside
memcached, and each time we add data there, this counter is incremented, and our key-value pair gets some value. Using the gets command, we get this value and then in the cas command we can use it. This team has all the same problems that ordinary atoms have, i.e. You can make a lot of raise conditionals interesting, especially since memcached has no guarantees on the order of command execution.

Have memcached key "-C" - it turns off the cas . Those. what's happening? This counter disappears from the key-value pair, if you add the key "-C", then you save 8 bytes, because it is a 64-bit counter on each value. If your values ​​are small, the keys are small, then this can be a significant savings.

How to work with memcached effectively?



She is designed to work with multiple sessions. Sets are hundreds. Those. starts from hundreds. And the fact is that in terms of RPS - request per second - you will not squeeze much out of memcached using 2-3 sessions, i.e. in order to swing it, you need a lot of connections. Sessions should be long-playing, because the creation of a session inside memcached is a rather expensive process, so you hooked once and that's all, this session should be held.

Requests need to batch'it, i.e. we have to send requests in batches. For the get-command, we have the opportunity to transfer a few keys, this should be used. Those. we say get and key-key-key. For the rest of the teams there is no such possibility, but we can still do batch, i.e. we can form a request from ourselves, locally, on the client side using several commands, and then send this request entirely.

memcached is multithreaded, but it is not very well multithreaded. It has a lot of locks inside, rather ad-hoc, so more than four threads cause very strong content inside. I don’t need to believe, it’s necessary to recheck everything myself, it’s necessary to do some experiments on a live system, but a very large number of threads will not work. It is necessary to play, to pick up some optimal number with the key "-t".

memcached supports UDP. This is the patch that was added to memcached by facebook. The way Facebook uses memcached - they make all the sets, i.e. all modification of data on TCP, and get they make over UDP. And it turns out, when the amount of data is substantially large, then UDP gives a serious gain due to the fact that the packet size is smaller. They manage to pump more data through the grid.

I told you about incr / decr - these commands are ideal for storing backend statistics.



Statistics in HighLoad is an irreplaceable thing, i.e. you can’t understand what, how, where a specific problem comes from, if you don’t have statistics, because after half an hour of work “the system behaves strangely” and that’s all ... To add specifics, for example, every thousandth query will be sent, we need some kind of then statistics. The more statistics there are, the better. And even, in principle, in order to understand that we have a problem, we need some kind of statistics. For example, the backend gave a page for 30 ms, started over 40, it is impossible to distinguish with a glance, but with us the performance sank by a quarter - this is terrible.

Memcached also supports statistics by itself, and if you already use memcached in your infrastructure, then memcached statistics is part of your statistics, so you need to look in there, you need to look there to understand whether the backend is using the cache correctly, or if it caches data well .

The first is that each team has hits and misses. When we turned to the cache, and gave us the data, I got a hit on this command. For example, we made the delete key, we will have delete hits 1, so for each command. Naturally, it is necessary that hits be 100%, there is no misses at all. Must watch. Suppose we can have a very high miss ratio. The most banal reason - we just climb the wrong data. There may be such an option that we allocated little memory for the cache, and we constantly reuse the cache, i.e. we added some data, added, added, at some moment there the first data fell out of the cache, we got behind it, they are no longer there. We climbed after the others, they are not there either. And it is spinning like this. Those. it is necessary either to reduce the load on memcached from the backend side, or you can increase the amount of memory that we allow to use with the “-m” parameter.

Evictions is a very important moment. The situation I am talking about will be visible from the fact that the evictions rate will be very high. This is the quantity when the valid data is not exploded, i.e. they are fresh, good are thrown out of the cache, we then have a growing number of evictions.

I said that you need to use batch'i. How to choose batch size? There is no silver bullet, it is necessary to select it experimentally. Everything depends on your infrastructure, on the network you use, on the number of instances and other factors. But when we have a very large batch ... Imagine the situation that we are performing a batch, and all the other things are standing and waiting until the batch is executed. This is called starvation - fasting, i.e. when the rest of the team go hungry and wait until one fatty one is fulfilled. To avoid this, there is a mechanism inside memcached that interrupts the execution of batch by force. It is implemented quite rudely, there is a key “-R”, which says how many teams can execute one connection in a row. By default, this value is 20. And you, when you look at the statistics, if your conn_yields stat is somehow very high, it means that you use batch more than memcached can chew, and it has to forcefully switch the context of this connection. Here you can either increase the size of the batch with the “-R” key, or not use such batch from the backend.



I also said that memcached discards the oldest data from memory. So, I lied. In fact, it is not. Inside memcached has its own memory manager to work effectively with this memory to eject these atoms. It is designed in such a way that we have slabs (literally "stub"). This is a well-established term in programming memory managers for a piece of memory, i.e. we just have some big piece of memory, which, in turn, is divided into pages. Pages inside memcached by MB, so you can not create there data "key-value" of more than one MB. This is a physical limitation - memcached cannot create data more than one page. And, as a result, all the pages are beaten by chunks, this is what you see in the picture at 96, 120 - they are of a certain size. Those. chunks of 96 MB, then 120 bits, with a factor of 1.25, from 32 to 1 MB.Within this piece there is a doubly linked list. When we add some new value, memcached looks at the size of this value (this is the key + value + expiration + flags + system information that memcached is needed (about 24-50 bytes)), chooses the size of this chunk and adds our doubly-connected list data. She always adds data to the head. When we access some data, memcached removes them from the doubly linked list and again throws it in the head. Thus, the data that is little used, crawl in the tail, and eventually they are deleted.

If we don’t have enough memory, then memcached will start removing memory from the end. The list recently used mechanism works within one chunk, i.e. these lists are allocated for a certain size, it is not a fixed size - this is the range from 96 to 120 will fall into the 120th chunk, etc. We can’t influence this mechanism from the memcached side, only from the backend side we need to select this data.



You can see the statistics for these slabs. The easiest way to watch memcached statistics is that the protocol is completely text-based, and we can Telnet to connect, type stats, Enter, and it will dump the “sheet”. Similarly, we can type stats slabs, stats items - this is basically similar information, but stats slabs gives a picture that is more blurred in time, there are such stats - what happened, what happened during the entire period while memcached worked, and stat items - there is more about what we have now, how much is what. In principle, both of these things need to look, we must take into account.



Here we are getting close to scaling. Naturally, we installed another memcached server - great. What do we do? Somehow you have to choose. Either we, on the client side, decide which server to join and why. If we have availability, then everything is simple - we wrote it down there, we wrote it down here, we read it from somewhere, it doesn’t matter, you can use Round Robin as you wish. Either we set up some kind of broker, and for the backend we get that it looks like a memcached instance, but actually a cluster is hidden behind this broker.

What is a broker used for? To simplify the backend infrastructure. For example, we need to transport servers from a data center to a data center, and all clients should know about it. Or we can do a hack behind this broker, and for the backend everything will pass transparently.

But latency is growing. 90% of requests are network round trip, i.e. memcached inside it processes the request for ms - this is very fast, and data travels over the network for a long time. When we have a broker, we have another link, i.e. still longer. If the client immediately knows which cluster of memcached he should go to, then he will get the data quickly. And, actually, how does the client know which cluster of memcached to go to? We take, consider the hash from our key, take the remainder of dividing this hash by the instance number in memcached and go to this cluster - the simplest solution.

But we have added another cluster to the infrastructure, which means that now we need to crash the entire cache, because it has become inconsistent, not valid, and to recount everything again - this is bad.



For this there is a mechanism - consistent hashing ring. Those.what are we doing? We take hash values, all possible hash values, for example int32, take all possible values ​​and place it as if on the watch face. So.we can configure - say, hashes from such and such go to this cluster. We configure rangie and configure clusters that are responsible for these range. Thus, we can shuffle the server as you like, i.e. we will need to change this ring in one place, regenerate it, and the servers, clients or router, broker - they will have a consistent idea of ​​where the data lie.

I would also like to say a little about data consistency. As soon as we have a new link, as soon as we cache somewhere, we have duplicate data. And we have a problem so that this data is consistent. Because there are many such situations - for example, we write data to the cache - local or remote, then we go and write this data to the database, at this moment the base drops, we have lost connection with the base. In fact, according to logic, we do not have this data, but at the same time, customers read them from the cache - this is a problem.

memcached is poorly suited to the consistancy of some solutions, This is more of an availability solution, but at the same time, there are some possibilities with a cas'om to do something about it.

Contacts

" Cachelot@cachelot.io
" http://cachelot.io/

— HighLoad++ Junior .

- HighLoad.Guide — , , , . 30 . !

— " - ", , HighLoad++ Junior .