October 27, 2008 at 08:37Atomic operations and counters in memcached
A series of posts on “Web, Caching, and Memcached” continues. In the first and second posts, we talked about memcached, its architecture, possible applications, choosing a caching key and memcached clustering .
Today we will talk about:
The next post will be devoted to the problem of simultaneously rebuilding caches.
As such, all single memcached requests are atomic (due to its single-threaded and correct internal locks in the multi-threaded case). This means that if we execute the get request, we will get the key values as someone wrote it to the cache, but certainly not a mixture of the two records. However, each operation is independent, and we cannot guarantee, for example, the correctness of such a procedure in a competitive access situation from several parallel processes:
If this code is executed multiple frontends simultaneously, it may happen that the value of the x key is not to increase n times, as we have conceived and to a lower value (a classic race condition , race condition ). Of course, this approach is unacceptable to us. The classic answer to this situation is the use of synchronization primitives (semaphores, mutexes, etc.), but they are not in memcached. Another solution to the problem is to implement more complex operations that replace the non-atomic get / set sequence.
Memcached has a couple of operations to solve this problem:
It should be further noted that any lock in memcached must be fine-grained, that is, it should affect as few objects as possible, since the main task of the server in any case is to provide effective cache access to as many parallel processes as possible.
Memcached can be used not only for storing caches of samples from backends, not only for storing user sessions (which was mentioned at the beginning of the article), but also for a task that is difficult to solve without memcached - the implementation of counters working in real time . That is, we are faced with the task of showing the current value of the counter at a given point in time, if we fold the requirement of "real time", this can be realized through logging and subsequent analysis of the accumulated logs.
Let's look at a few examples of such counters, how they can be implemented, and what problems are possible.
Let there be some objects in our project (for example, photos, videos, articles, etc.) for which we must show the number of views in real time. The counter should increase with each view. The easiest option is to update the field in the database each time it does not work, because there are a lot of views and the database will not withstand such a load. We can implement accurate and accurate collection of viewing statistics, their accumulation, and periodic analysis, which ends with updating the counter in the database (for example, once per hour). However, the task remains of showing the current number of views.
Consider the following possible solution. Frontend at the time of viewing the object forms the name of the counter key in memcached, and tries to perform the operation
It should be noted that the above scheme is not entirely correct: there is a race condition in it. If two frontends simultaneously access the counter, simultaneously detect its absence, and do two set operations, we will lose one view. This can be considered not very critical, since the process of accumulating statistics will restore the correct value. If necessary, you can use locks in memcached, which will be discussed below. Or, implement counter initialization through an operation
There is another kind of counter that can hardly be implemented without memcached or a similar solution: it is an online counter. We see such counters on a large number of sites, but first of all it is necessary to determine what exactly we mean by “online”. Let us want to calculate how many unique sessions (users) have accessed our site in the last 5 minutes. The uniqueness of a user’s treatment with this session for 5 minutes can be tracked by saving the time of the last counted treatment in the session, if more than 5 minutes have passed, this means a new (unique) treatment.
Thus, we distinguish in memcached six keys with names such as,
When the next minute arrives, the key will become the current modifiable key
Such a counter can be built on fewer keys. The minimum possible for this scheme are two keys: one is updated, the value of the other is displayed, then after 5 minutes the counters are swapped, while the one that has just been updated is reset. In the given scheme with many keys, a certain “smoothing” is provided, which provides a smoother change in the counter in case of a sharp influx or outflow of visitors.
Today we will talk about:
- atomic operations in memcached;
- implementations of view counters and online.
The next post will be devoted to the problem of simultaneously rebuilding caches.
Atomic operations in memcached
As such, all single memcached requests are atomic (due to its single-threaded and correct internal locks in the multi-threaded case). This means that if we execute the get request, we will get the key values as someone wrote it to the cache, but certainly not a mixture of the two records. However, each operation is independent, and we cannot guarantee, for example, the correctness of such a procedure in a competitive access situation from several parallel processes:
- Get the value of the key "x" (
$x = get x). - Increment the value of the variable by one (
$x = $x + 1). - Writing a new variable value to memcached (
set x = $x).
If this code is executed multiple frontends simultaneously, it may happen that the value of the x key is not to increase n times, as we have conceived and to a lower value (a classic race condition , race condition ). Of course, this approach is unacceptable to us. The classic answer to this situation is the use of synchronization primitives (semaphores, mutexes, etc.), but they are not in memcached. Another solution to the problem is to implement more complex operations that replace the non-atomic get / set sequence.
Memcached has a couple of operations to solve this problem:
incr/decr(increment and decrement). They provide atomic increase (or, correspondingly, decrease) of the integer value of the key existing in memcached. Additional operations are also atomic : append/ prepend, which allow you to add data to the beginning or end of the key value, also operations addand replacethat allow you to set the key value only if it did not exist before, or vice versa, can be considered atomic . Replace the value of an existing key. Another variant of atomic operations will be discussed in the section on implementing locks using memcached.It should be further noted that any lock in memcached must be fine-grained, that is, it should affect as few objects as possible, since the main task of the server in any case is to provide effective cache access to as many parallel processes as possible.
Counters in memcached
Memcached can be used not only for storing caches of samples from backends, not only for storing user sessions (which was mentioned at the beginning of the article), but also for a task that is difficult to solve without memcached - the implementation of counters working in real time . That is, we are faced with the task of showing the current value of the counter at a given point in time, if we fold the requirement of "real time", this can be realized through logging and subsequent analysis of the accumulated logs.
Let's look at a few examples of such counters, how they can be implemented, and what problems are possible.
View counter
Let there be some objects in our project (for example, photos, videos, articles, etc.) for which we must show the number of views in real time. The counter should increase with each view. The easiest option is to update the field in the database each time it does not work, because there are a lot of views and the database will not withstand such a load. We can implement accurate and accurate collection of viewing statistics, their accumulation, and periodic analysis, which ends with updating the counter in the database (for example, once per hour). However, the task remains of showing the current number of views.
Consider the following possible solution. Frontend at the time of viewing the object forms the name of the counter key in memcached, and tries to perform the operation
incr(increment) over this key. If the execution was successful, this means that the corresponding key is in memcached, we counted the view, we also received a new counter value (as a result of the operation incr), which we can show to the user. If the operation incrreturned an error, then the counter key is not currently in memcached, we can choose the number of views from the database as the initial value, increase it by one, and perform the set operation, setting the new counter value. In subsequent scans, the key will already be in memcached, and we will simply increase its value with incr.It should be noted that the above scheme is not entirely correct: there is a race condition in it. If two frontends simultaneously access the counter, simultaneously detect its absence, and do two set operations, we will lose one view. This can be considered not very critical, since the process of accumulating statistics will restore the correct value. If necessary, you can use locks in memcached, which will be discussed below. Or, implement counter initialization through an operation
add, processing its result.Online Counter
There is another kind of counter that can hardly be implemented without memcached or a similar solution: it is an online counter. We see such counters on a large number of sites, but first of all it is necessary to determine what exactly we mean by “online”. Let us want to calculate how many unique sessions (users) have accessed our site in the last 5 minutes. The uniqueness of a user’s treatment with this session for 5 minutes can be tracked by saving the time of the last counted treatment in the session, if more than 5 minutes have passed, this means a new (unique) treatment.
Thus, we distinguish in memcached six keys with names such as,
c_0, c_1, c_2, ...,c_5. The current variable key we will consider a counter with a number equal to the remainder of dividing the current minute by 6 (in the figure this is the key c_4). We will increase it with the help of the incr operation for the treatment of each session unique for 5 minutes. If it incrreturns an error (there is no counter yet), set its value to 1 with set, be sure to specify a lifetime of 6 minutes. Onlayner counter value will be the sum of all the keys except the current (in the figure the keys c_0, c_1, c_2, c_3and c_5). When the next minute arrives, the key will become the current modifiable key
c_5, while its previous value will disappear (since it was created 6 minutes ago with a lifetime of the same 6 minutes). The counter value will be the sum of keys cс_0by c_4, i.e. the key value just calculated will с_4already start to be taken into account in the displayed counter value. Such a counter can be built on fewer keys. The minimum possible for this scheme are two keys: one is updated, the value of the other is displayed, then after 5 minutes the counters are swapped, while the one that has just been updated is reset. In the given scheme with many keys, a certain “smoothing” is provided, which provides a smoother change in the counter in case of a sharp influx or outflow of visitors.
