November 29, 2016 at 10:03Caches for Dummies
- Tutorial
Cache through the eyes of the "teapot":
Cache is an integrated system. Accordingly, at different angles, the result can lie both in the real and in the imaginary region. It is very important to understand the difference between what we are waiting for and what we really have.
Let's scroll through the full circle of situations.
Tl; dr: When adding a cache to the architecture, it is important to clearly recognize that the cache can be a means of destabilizing the system under load. See the end of the article.
Imagine that we have access to a database that returns exchange rates. We ask rates.example.com/?currency1=XXX¤cy2=XXX and in response we get the plain text value of the course. For example, every 1000 queries to the database cost 1 euro cent for us.
So, now we want to show the dollar to euro exchange rate on our website. To do this, we need to get a course, so on our website we create an API wrapper for convenient use:
For example, like this:
And in the templates in the right place, insert something like:
(well, or even
Naive implementation does the simplest thing you can think of: it asks for a remote system from each user and uses the answer directly. This means that now every 1000 views by users of our page cost us a penny more. It would seem - pennies. But the project is growing, we already have 1,000 regular users who visit the site every day and view 20 pages each, and this is already 6 euros per month, which turns the site from free to completely comparable to the fee for the cheapest dedicated virtual servers.
Here comes His Majesty Cash
Why do we need to ask a course for each user for each page update, if for people this information, in general, is not needed so often? Let's just limit the refresh rate to, for example, once every 5 seconds. Users, moving from page to page, will still see a new number, and we will pay 1,000 times less.
No sooner said than done! Add a few lines:
This is the most important aspect of the cache: storing the last result .
And voila! The site again becomes almost free for us ... Until the end of the month, when we discover an account for 4 euros from an external system. Of course, not 6, but we expected much greater savings!
Fortunately, the external system allows you to see the accruals, where we see bursts of 100 or more requests every exactly 5 seconds during peak attendance.
This is how we got to know the second important aspect of the cache: query deduplication . The fact is that as soon as the value is out of date, between checking whether the result is in the cache and saving the new value, all incoming requests actually execute the request to the external system at the same time.
In the case of memcache, this can be implemented, for example, like this:
And finally, consumption was equal to expected - 1 request in 5 seconds, costs were reduced to 2 euros per month.
Why 2? There were 6 without caching for thousands of people, but we cached everything, but it decreased only 3 times? Yes, it was worth calculating early ... 1 time in 5 seconds = 12 per minute = 72 per hour = 576 per working day = 17 thousand per month, and not everyone goes on schedule, there are strange people looking in late at night ... So it turns out, in there is one peak instead of hundreds of calls, and in quiet time - as before, the request for almost every call passes. But still, even in the worst case, the bill should be 31 × 86400 ÷ 5 = 5.36 euros.
So we met with another facet: the cache helps , but does not eliminate the load.
However, in our case, people come into the project and leave and at some point start complaining about the brakes: the pages freeze for a few seconds. And sometimes in the morning the site does not respond at all ... Viewing the site’s console shows that sometimes additional instances are launched in the afternoon. At the same time, the speed of query execution drops to 5-15 seconds per request - because of what this happens.
Exercise for the reader: look carefully at the previous code and find the reason.
Yes Yes Yes. Of course, this is in the branch
By the way, this rake is by no means just a cache, it is a common aspect of distributed locks: it is important to release locks and have timeouts in order to avoid deadlocks. If we added "?" generally without a lifetime, everything would freeze at the very first error of communication with an external system. Unfortunately, memcache does not provide good ways to create distributed locks, using a full-fledged database with row-level locks is better, but it was just a lyrical digression, necessary simply because they stepped on this rake.
So, we fixed the problem, but nothing has changed: the brakes still occasionally started. What is noteworthy, they coincided in time with a newsletter from an external system about technical works ...
Come on now ... Let's take a brief break and recount what we have gathered now, what the cache should be able to do:
Have you noticed? The cache should provide points 1-2 for an error case! Initially, this seems obvious: you never know what happened, one request fell off, the next will update. Will it just happen if the next one also returns an error? And the next one? So we got 10 requests, the first one captured the lock, tried to get the result, fell off, left. The next one checks - so, there is no blocking, no value, go for the result. Broke off, left. And so for everyone. Well, stupidity! A good 10 came, one tried - everyone fell off. And let the next one try again!
Hence: the cache must be able to store a negative result for some time.. Our naive initial assumption essentially implies storing a negative result for 0 seconds (but transmitting this very negation to everyone who is already waiting for it). Unfortunately, in the case of Memcache, the implementation of zero latency is very problematic (I ’ll leave it as a homework for a nasty reader ; advice: use the CAS mechanism ; and yes, you can use Memcache and Memcached in AppEngine).
We will just add saving a negative value with 1 second of life:
It would seem, well now that ’s all, and you can calm down? No matter how. While we were growing, our beloved external service was also growing, and at some point sometimes it started to slow down and respond right away ... And what is remarkable - with it our website started to slow down too! And again for everyone! But why? We cache everything, in case of errors, we remember the error and thereby release everyone waiting at once, do not we?
... And here it is. Take a close look at the code again: the request to the external system will be executed as long as it allows
Well, instead of waiting, we can add a branch
No sooner said than done:
So, we won again: even if the external service slows down, it slows down no more than one page ... That is, as if the average response time was reduced, but users are still a bit unhappy.
Note: regular PHP writes sessions to files by default, blocking concurrent requests. To avoid this behavior, you can either pass the read_and_close parameter to session_start or force the session to be closed through session_close after all the necessary changes have been made; otherwise, not one page will slow down, but one user: since the script updating the value will block the session from opening with another request from the same user. When executed on AppEngine, session storage in memcache is enabled by default , that is, without locks, so the problem will not be so noticeable.
So, users are still unhappy (oh, these users!). Those who spend the most time on the site still notice these short hangs. And they are not at all happy with the fact that this rarely happens, and they simply are not lucky. We will have to make the requirement even more stringent for this case : no requests should wait for a response .
What can we do in this formulation of the question? We can:
In fact, maintaining data in an always hot state is a little more complicated task than just a few lines of PHP code, so for our simple case we will have to put up with the fact that some kind of request will be regularly “thought over” (important: not random, but some; that is, not random , but arbitrary ). The applicability of this approach is always important to try on the task!
So, our data provider is growing, but not all of its clients read the hub, and therefore they do not use the correct caching (if they use it at all) and at some point start issuing a huge number of requests, which makes the service feel bad, and occasionally he begins to answer not just slowly, but very slowly. Up to tens of seconds or more. Of course, users quickly found that you can press F5 or reload the page, and it appears instantly - only the page again began to run into free limits, as processes that simply awaited an external response but consumed our resources started to hang.
Among other side effects, cases of showing an obsolete course have become more frequent. [Hmm ... in general, imagine that we are not talking about our case, but about something more complicated, where obsolescence is visible with the naked eye :) in fact, even in the simple case there is sure to be a user who will notice such completely unobvious jambs ].
See what happens:
Of course, here we must set the timeout we need through
So let's summarize the subtotal. In the common sense, the cache:
In reality, however:
The cache assumes the “ephemerality” of the stored data, and therefore caching systems are free to handle the lifetime in general and the very fact of the request to save data:
Thus, simply applying the cache, we often lay a mine of pending action, which will certainly explode - but not now, but in the future, when the decision will cost much more. When calculating system performance, it is important to consider without considering the reduction in execution time from caching positive responses, otherwise we will improve the system’s behavior in a quiet time (when the cache hit ratio is maximum), and not during peak load / dependency overload (when cache poisoning usually occurs).
Consider the simplest case:
And under heavy load, our cache is poisoned, and requests are not cached for 5 seconds, but for 1 second only, which means that we have 2 requests constantly busy (one executes the first request, the second starts updating the cache in a second, while the first still works), and the remaining capacity for maintenance is reduced to 60 requests per second. That is, the effective capacity from (based on the average) 6000 requests per minute drops sharply to ~ 3600. Which means that if poisoning occurred at 5000 requests per minute, until the load drops from 5000 to 3000, the system is unstable. That is, any (even peak!) Surge in traffic can potentially cause long-term system instability.
This looks especially great when, after a newsletter with any new features, a wave of users arrives almost simultaneously. A kind of marketing habraeffect on a regular basis.
All this does not mean that the cache cannot be or is harmful to use! We will talk about how to properly apply the cache to improve system stability and how to recover from the aforementioned hysteresis loop in the next article, do not switch.
Cache is an integrated system. Accordingly, at different angles, the result can lie both in the real and in the imaginary region. It is very important to understand the difference between what we are waiting for and what we really have.
Let's scroll through the full circle of situations.
Tl; dr: When adding a cache to the architecture, it is important to clearly recognize that the cache can be a means of destabilizing the system under load. See the end of the article.
Imagine that we have access to a database that returns exchange rates. We ask rates.example.com/?currency1=XXX¤cy2=XXX and in response we get the plain text value of the course. For example, every 1000 queries to the database cost 1 euro cent for us.
So, now we want to show the dollar to euro exchange rate on our website. To do this, we need to get a course, so on our website we create an API wrapper for convenient use:
For example, like this:
$currency1, "currency2"=>$currency2));
$rate = @file_get_contents($api_host."?".$args);
if ($rate === FALSE) {
return $rate;
} else {
return (float) $rate;
}
}And in the templates in the right place, insert something like:
{{ get_current_rate("USD","EUR")|format(".2f") }} USD/EUR(well, or even
Naive implementation does the simplest thing you can think of: it asks for a remote system from each user and uses the answer directly. This means that now every 1000 views by users of our page cost us a penny more. It would seem - pennies. But the project is growing, we already have 1,000 regular users who visit the site every day and view 20 pages each, and this is already 6 euros per month, which turns the site from free to completely comparable to the fee for the cheapest dedicated virtual servers.
Here comes His Majesty Cash
Why do we need to ask a course for each user for each page update, if for people this information, in general, is not needed so often? Let's just limit the refresh rate to, for example, once every 5 seconds. Users, moving from page to page, will still see a new number, and we will pay 1,000 times less.
No sooner said than done! Add a few lines:
addServer("localhost", 11211);
$rate = $memcache->get($cache_key);
if ($rate) {
return $rate;
} else {
$api_host = "http://rates.example.com/";
$args = http_build_query(array("currency1"=>$currency1, "currency2"=>$currency2));
$rate = @file_get_contents($api_host."?".$args);
if ($rate === FALSE) {
return $rate;
} else {
$memcache->set($cache_key, (float) $rate, 0, 5);
return (float) $rate;
}
}
}This is the most important aspect of the cache: storing the last result .
And voila! The site again becomes almost free for us ... Until the end of the month, when we discover an account for 4 euros from an external system. Of course, not 6, but we expected much greater savings!
Fortunately, the external system allows you to see the accruals, where we see bursts of 100 or more requests every exactly 5 seconds during peak attendance.
This is how we got to know the second important aspect of the cache: query deduplication . The fact is that as soon as the value is out of date, between checking whether the result is in the cache and saving the new value, all incoming requests actually execute the request to the external system at the same time.
In the case of memcache, this can be implemented, for example, like this:
addServer("localhost", 11211);
while (true) {
$rate = $memcache->get($cache_key);
if ($rate == "?") {
sleep(0.05);
} else if ($rate) {
return $rate;
} else {
// Создаём запись, только один сможет это сделать, остальные уйдут спать
if ($memcache->add($cache_key, "?", 0, 5)) {
$api_host = "http://rates.example.com/";
$args = http_build_query(array("currency1"=>$currency1, "currency2"=>$currency2));
$rate = @file_get_contents($api_host."?".$args);
if ($rate === FALSE) {
return $rate;
} else {
$memcache->set($cache_key, (float) $rate, 0, 5);
return (float) $rate;
}
}
}
}
}And finally, consumption was equal to expected - 1 request in 5 seconds, costs were reduced to 2 euros per month.
Why 2? There were 6 without caching for thousands of people, but we cached everything, but it decreased only 3 times? Yes, it was worth calculating early ... 1 time in 5 seconds = 12 per minute = 72 per hour = 576 per working day = 17 thousand per month, and not everyone goes on schedule, there are strange people looking in late at night ... So it turns out, in there is one peak instead of hundreds of calls, and in quiet time - as before, the request for almost every call passes. But still, even in the worst case, the bill should be 31 × 86400 ÷ 5 = 5.36 euros.
So we met with another facet: the cache helps , but does not eliminate the load.
However, in our case, people come into the project and leave and at some point start complaining about the brakes: the pages freeze for a few seconds. And sometimes in the morning the site does not respond at all ... Viewing the site’s console shows that sometimes additional instances are launched in the afternoon. At the same time, the speed of query execution drops to 5-15 seconds per request - because of what this happens.
Exercise for the reader: look carefully at the previous code and find the reason.
Yes Yes Yes. Of course, this is in the branch
if ($rate === FALSE). If the external service returned an error, we did not release the lock ... In the sense that "?" and remained recorded, and everyone is waiting for it to become obsolete. Well this is easy to fix: if ($rate === FALSE) {
$memcache->delete($cache_key);
return $rate;
} else {By the way, this rake is by no means just a cache, it is a common aspect of distributed locks: it is important to release locks and have timeouts in order to avoid deadlocks. If we added "?" generally without a lifetime, everything would freeze at the very first error of communication with an external system. Unfortunately, memcache does not provide good ways to create distributed locks, using a full-fledged database with row-level locks is better, but it was just a lyrical digression, necessary simply because they stepped on this rake.
So, we fixed the problem, but nothing has changed: the brakes still occasionally started. What is noteworthy, they coincided in time with a newsletter from an external system about technical works ...
Come on now ... Let's take a brief break and recount what we have gathered now, what the cache should be able to do:
- remember the last known result;
- deduplicate queries when the result is still or is not already known;
- ensure correct unlocking in case of error.
Have you noticed? The cache should provide points 1-2 for an error case! Initially, this seems obvious: you never know what happened, one request fell off, the next will update. Will it just happen if the next one also returns an error? And the next one? So we got 10 requests, the first one captured the lock, tried to get the result, fell off, left. The next one checks - so, there is no blocking, no value, go for the result. Broke off, left. And so for everyone. Well, stupidity! A good 10 came, one tried - everyone fell off. And let the next one try again!
Hence: the cache must be able to store a negative result for some time.. Our naive initial assumption essentially implies storing a negative result for 0 seconds (but transmitting this very negation to everyone who is already waiting for it). Unfortunately, in the case of Memcache, the implementation of zero latency is very problematic (I ’ll leave it as a homework for a nasty reader ; advice: use the CAS mechanism ; and yes, you can use Memcache and Memcached in AppEngine).
We will just add saving a negative value with 1 second of life:
addServer("localhost", 11211);
while (true) {
$flags = FALSE;
$rate = $memcache->get($cache_key, $flags);
if ($rate == "?") {
sleep(0.05);
} else if ($flags !== FALSE) {
// Если ключа нет, тип не меняется, иначе будет число,
// и мы вернём любое значение из кэша, даже false.
return $rate;
} else {
if ($memcache->add($cache_key, "?", 0, 5)) {
$api_host = "http://rates.example.com/";
$args = http_build_query(array("currency1"=>$currency1, "currency2"=>$currency2));
$rate = @file_get_contents($api_host."?".$args);
if ($rate === FALSE) {
// Здесь мы можем задать отдельный срок жизни отрицательного значения
$memcache->set($cache_key, $rate, 0, 1);
return $rate;
} else {
$memcache->set($cache_key, (float) $rate, 0, 5);
return (float) $rate;
}
}
}
}
}It would seem, well now that ’s all, and you can calm down? No matter how. While we were growing, our beloved external service was also growing, and at some point sometimes it started to slow down and respond right away ... And what is remarkable - with it our website started to slow down too! And again for everyone! But why? We cache everything, in case of errors, we remember the error and thereby release everyone waiting at once, do not we?
... And here it is. Take a close look at the code again: the request to the external system will be executed as long as it allows
file_get_contents(). At the time the request is executed, everyone else waits, so every time the cache becomes obsolete, all threads wait for the main one to execute, and they will receive new data only when they arrive. Well, instead of waiting, we can add a branch
else{}to the condition aroundmemcache->add... True, it is probably worth returning the last known value, right? After all, we cache exactly then that we agree to receive outdated information if there is no fresh information; so, one more cache requirement: let it slow down no more than one request . No sooner said than done:
addServer("localhost", 11211);
while (true) {
$flags = FALSE;
$rate = $memcache->get($cache_key, $flags);
if ($rate == "?") {
sleep(0.05);
} else if ($flags !== FALSE) {
return $rate;
} else {
if ($memcache->add($cache_key, "?", 0, 5)) {
$api_host = "http://rates.example.com/";
$args = http_build_query(array("currency1"=>$currency1, "currency2"=>$currency2));
$rate = @file_get_contents($api_host."?".$args);
if ($rate === FALSE) {
// Мы не меняем последнее успешное значение, пусть смотрят на
// устарелые сведения. При желании, поведение можно изменить.
$memcache->set($cache_key, $rate, 0, 1);
return $rate;
} else {
// Ставим срок жизни бесконечным для _stale_ ключа, но можем и задать
// какой-нибудь большой: например, минуту, тем самым ограничив
// срок жизни устаревших сведений.
$memcache->set("_stale_".$cache_key, (float) $rate);
$memcache->set($cache_key, (float) $rate, 0, 5);
return (float) $rate;
}
} else {
// Если нет актуальных данных, и не мы их обновляем —
// вернём значение из копии данных, для которых не указан срок жизни.
// Если и их нет, то вернём false, что соответствует обычному поведению.
return $memcache->get("_stale_".$cache_key);
}
}
}
}So, we won again: even if the external service slows down, it slows down no more than one page ... That is, as if the average response time was reduced, but users are still a bit unhappy.
Note: regular PHP writes sessions to files by default, blocking concurrent requests. To avoid this behavior, you can either pass the read_and_close parameter to session_start or force the session to be closed through session_close after all the necessary changes have been made; otherwise, not one page will slow down, but one user: since the script updating the value will block the session from opening with another request from the same user. When executed on AppEngine, session storage in memcache is enabled by default , that is, without locks, so the problem will not be so noticeable.
So, users are still unhappy (oh, these users!). Those who spend the most time on the site still notice these short hangs. And they are not at all happy with the fact that this rarely happens, and they simply are not lucky. We will have to make the requirement even more stringent for this case : no requests should wait for a response .
What can we do in this formulation of the question? We can:
- Try to execute the " execution after response " tricks , that is, if we need to update the value, we register a handler that will do this after executing the rest of the script. It just depends on the application and the execution environment; the most reliable way is to use it
fastcgi_finish_request(), which requires server configuration via php-fpm (accordingly, it is not available for AppEngine). - Make an update in a separate thread (that is, execute
pcntl_fork()or run the script throughsystem()or somehow) - again, it can work for your server, sometimes it even works on some shared hosting services, where they are not very worried about security, but, of course, it won’t work on services with paranoid security, that is, AppEngine is not suitable. - Have a constantly running background process for updating the cache: the process should check at a given frequency whether the value in the cache is out of date, and if the life time is coming to an end, and the value was required during the life of the cache, it updates it. We will discuss this point a little later, when we get tired of our poor site with the exchange rate and move on to more fun stuff.
In fact, maintaining data in an always hot state is a little more complicated task than just a few lines of PHP code, so for our simple case we will have to put up with the fact that some kind of request will be regularly “thought over” (important: not random, but some; that is, not random , but arbitrary ). The applicability of this approach is always important to try on the task!
So, our data provider is growing, but not all of its clients read the hub, and therefore they do not use the correct caching (if they use it at all) and at some point start issuing a huge number of requests, which makes the service feel bad, and occasionally he begins to answer not just slowly, but very slowly. Up to tens of seconds or more. Of course, users quickly found that you can press F5 or reload the page, and it appears instantly - only the page again began to run into free limits, as processes that simply awaited an external response but consumed our resources started to hang.
Among other side effects, cases of showing an obsolete course have become more frequent. [Hmm ... in general, imagine that we are not talking about our case, but about something more complicated, where obsolescence is visible with the naked eye :) in fact, even in the simple case there is sure to be a user who will notice such completely unobvious jambs ].
See what happens:
- Request 1 came, there is no data in the cache, so we added the token '?' for 5 seconds and went for the course.
- After 1 second, request number 2 came, saw the marker '?', Returned data from the stale record.
- After 3 seconds, request number 3 came, saw the marker '?', Returned stale.
- After 1 second, the '?' Deprecated even though request 1 is still waiting for a response.
- After another 2 seconds, request number 4 arrived, there is no marker, adds a new marker and goes for the course.
- ...
- Request 1 received a response, saved the result.
- Request X came, received an actual answer from the cache of the 1st question (and when did you get that answer? At the time of the request, or the moment of the answer? - no one knows ...).
- Request number 4 received an answer, saved the result - and again it is not clear whether this answer was newer or older ...
Of course, here we must set the timeout we need through
ini_set("default_socket_timeout")or use it stream_context_create... So we come to another important aspect: the cache must take into account the time it took to get the values . There is no general solution for the behavior, but, as a rule, the caching time should be longer than the calculation time. If the calculation time exceeds the cache lifetime, the cache is not applicable . This is no longer a cache, but precomputations that should be stored in reliable storage. So let's summarize the subtotal. In the common sense, the cache:
- replaces most requests for an already known answer;
- limits the number of requests for expensive data;
- makes query time invisible to the user.
In reality, however:
- replaces some requests from the cache life window with stored values (the cache may be lost at any time, for example, due to lack of memory or extravagant requests);
- trying to limit the number of requests (but without special implementation of the limitation of the frequency of outgoing requests, it is really possible to provide only characteristics of the type "maximum 1 outgoing request at a time");
- the query execution time is visible only to some users (moreover, the “lucky ones” are by no means evenly distributed).
The cache assumes the “ephemerality” of the stored data, and therefore caching systems are free to handle the lifetime in general and the very fact of the request to save data:
- cache can be lost at any given time. Even our execution lock markers are '?' may be lost if, in parallel, another 10 thousand users walks around the site, all while saving something (often the time of the last visit to the site) in a session that lies on the same cache server; after the token is lost (“cache poisoned”), the next request will again begin the process of updating the value in the cache;
- the faster the request is executed on the remote system, the less requests will be deduplicated in case of cache poisoning.
Thus, simply applying the cache, we often lay a mine of pending action, which will certainly explode - but not now, but in the future, when the decision will cost much more. When calculating system performance, it is important to consider without considering the reduction in execution time from caching positive responses, otherwise we will improve the system’s behavior in a quiet time (when the cache hit ratio is maximum), and not during peak load / dependency overload (when cache poisoning usually occurs).
Consider the simplest case:
- We look at the system in a calm state, and we see an average execution time of 0.05 seconds.
- Conclusion: 1 process can serve 20 requests per second, which means that for 100 requests per second, 5 processes are enough.
- But only if the request update time increases to 2 seconds, it turns out:
- 1 process is busy updating (within 2 seconds);
- during these 2 seconds, we have only 4 processes available = 80 requests per second.
And under heavy load, our cache is poisoned, and requests are not cached for 5 seconds, but for 1 second only, which means that we have 2 requests constantly busy (one executes the first request, the second starts updating the cache in a second, while the first still works), and the remaining capacity for maintenance is reduced to 60 requests per second. That is, the effective capacity from (based on the average) 6000 requests per minute drops sharply to ~ 3600. Which means that if poisoning occurred at 5000 requests per minute, until the load drops from 5000 to 3000, the system is unstable. That is, any (even peak!) Surge in traffic can potentially cause long-term system instability.
This looks especially great when, after a newsletter with any new features, a wave of users arrives almost simultaneously. A kind of marketing habraeffect on a regular basis.
All this does not mean that the cache cannot be or is harmful to use! We will talk about how to properly apply the cache to improve system stability and how to recover from the aforementioned hysteresis loop in the next article, do not switch.
