Some time ago, when I was working on caching infrastructure for an application, I encountered an issue I'd like to give my two cents about.
Say, we have an interface like this one:
The semantics of the interface is rather not important, but its implementations are. Say, we've implemented it by a component "SpammingAnswerFinder", which interrogates a database or webservice -- in other words, in some sense it does a non-trivial and/or rather expensive operation. The nature of the "findAnswer" method's results allows them to be cached, so we'll do it by annotating the SpammingAnswerFinder's "findAnswer" method as @Cacheable (the annotation's parameters are ommited for the sake of brevity):
Let's now inject "spammingAnswerFinder" component into another component -- say, KnowledgeBase -- the purpose of which is to answer questions:
If the collection "questions" happens to contain some logically equal questions then, despite of the "spammingAnswerFinder" component's method "findAnswer" being annotated as @Cacheable, we might get into the situation where two or more threads invoking the "findAnswer" method with the same question would encounter a cache-miss which would make the Spring's caching machinery to invoke the target "findAnswer" method multiple times (actually, times the number of the encountered cache-misses). This is the standard behavior of non-blocking cache, and in the most cases it is what we need, but in certain situations it might appear as non-desirable (as I've described above -- for example, we have a method performing a rather expensive task or, in general, a task that we want to perform as less times as possible).
NB: [Of course, in the example above we can deal with the duplicates' overhead right in the client code (in the KnowledgeBase class) by obtaining a stream of distinct items and then reducing it into the result map. But this is just that example. What I did really mean is a component with some cacheable method and that method being invoked from different threads, with some of the invocations leading to generation of the same cache key.]
To avoid the standard behavior, we need synchronized "compute-if-absent" semantics (or, in more general terms, atomic "check-then-act"):
Since the version 4.3 of Spring the annotation @Cacheable has an option "sync" (by default set to "false") which, if being set to "true", does exactly that. But, as it's said in the documentation, the "sync" option is just a hint and whether it's being supported or not is a matter of implementation. The Ehcache implementation in the spring-context-support module, which under the hood uses Ehcache 2.x, does not support this feature. So, what are the options left (besides the ones with using a proper implementation with support of "sync" feature)? To mark the @Cacheable target method as synchronized? It won't help -- in this case, the threads looking for the same key in the cache will just encounter a cache-miss concurrently and then the invocations of the target method will be performed in a synchronized manner and still get the cache filled (and the unwanted task performed) more than once -- this is due to the fact that the cache-miss is happening earlier in the Spring cache facility and the actual target method's invocation is just a consequence of it.
We can solve the problem by the following way: create a new proxy-component over the target one (which uses caching) and mark desired methods (at which we want to have the atomic computeIfAbsent semantics) as synchronized. Thus, at any given moment of time only one thread can access the method aspected on caching, so there won't be such cases with simultaneous cache-misses and multiple target method's invocations.
And this is for the KnowledgeBase component:
However, the solution has some drawbacks of synchronized methods:
-- the method "findAnswer" is now pure sequental (that is, even if we ask entirely different questions) and can't be utilized in the truly parallel fashion;
-- opportunity for starvation, i.e. when the thread which is currently performing the task to fill the cache could stuck for some reason, thus preventing other threads to invoke the desired method.
-- high lock contention, and it gets even worse if all the desired target methods are being guarded by the same lock (i.e. if we have 10 target methods and just wrap them into the corresponding proxy methods marked as synchronized then all the 10 methods are now sequential in respect to each other as each of them is locked with 'this' reference of the proxy instance). So, if you really need to synchronize more than one cacheable target method then at least do it using different locks (providing the generated cache keys for the methods don't overlap -- otherwise you might want to synchronize them using the same lock).
Another way to avoid the problem might be to use somewhat similar to the lock striping technique. It greatly improves concurrency in comparison to the one-lock synchronization. Ideally, we want to lock on something that resembles a cache key which would be used by the cache framework to find a relevant cache entry. It doesn't need to be the key itself, but something that has the similar functional dependency from the arguments that making up the cache key. The idea here is to use some kind of algorithm that will give the very same lock object for the same arguments. By the notion of "very same" I mean that it must be the same object on the heap, not just any equal -- otherwise, you will be locking on two different locks. At first, I was thinking that for a sole String argument, like in the example above, the object returned by String.intern() would do just fine, and that Strings in general might be particularly delightful in this regard -- the literals are pooled right away and the interned ones are pooled on the fly, giving you a built-in mechanism for obtaining "the very same" objects. But it's not that simple -- interned strings are garbage-collectible as well, so at two different points of time there might be two different String objects for the same literal. Instead, we could maintain an array of locks (i.e. java.util.concurrent.locks.ReentrantLock) of some length N, calculate some hash value of the target method's arguments and then calculate the index of the lock as hash (mod N). Also, further improving concurrency, we could use several such lock arrays -- by one for each target method. This solution looks ugly indeed (or, to put it more politically correct, adds some complexity to the code), but it is a tradeoff.
----------
P.S.
Also, in a code snippet above I've printed the following line:
I advise you to be aware of the usage of potentially blocking methods (like the "findAnswer" one) in parallel streams, as it might cause exhaustion (starvation) of the common fork-join pool's worker threads (or whatever fork-join pool the parallelStream()'s tasks are being invoked in) due to all them being blocked somewhere inside such methods, or even worse -- the starvation-deadlock, which happens when methods are spawning asynchronous subtasks (i.e. via CompletableFuture *async methods providing the current executor), sending it to the same bounded thread pool as they are in (for the unbounded thread pools this problem does not arise) and then joining on those subtasks, so there might be a case when all worker threads block in .join() forever because the pool has no more workers to execute the spawned subtasks.
For more information on this topic, see such articles as
Java Parallel Streams Are Bad for Your Health!
Think Twice Before Using Java 8 Parallel Streams
ManagedBlocker
Say, we have an interface like this one:
The semantics of the interface is rather not important, but its implementations are. Say, we've implemented it by a component "SpammingAnswerFinder", which interrogates a database or webservice -- in other words, in some sense it does a non-trivial and/or rather expensive operation. The nature of the "findAnswer" method's results allows them to be cached, so we'll do it by annotating the SpammingAnswerFinder's "findAnswer" method as @Cacheable (the annotation's parameters are ommited for the sake of brevity):
Let's now inject "spammingAnswerFinder" component into another component -- say, KnowledgeBase -- the purpose of which is to answer questions:
If the collection "questions" happens to contain some logically equal questions then, despite of the "spammingAnswerFinder" component's method "findAnswer" being annotated as @Cacheable, we might get into the situation where two or more threads invoking the "findAnswer" method with the same question would encounter a cache-miss which would make the Spring's caching machinery to invoke the target "findAnswer" method multiple times (actually, times the number of the encountered cache-misses). This is the standard behavior of non-blocking cache, and in the most cases it is what we need, but in certain situations it might appear as non-desirable (as I've described above -- for example, we have a method performing a rather expensive task or, in general, a task that we want to perform as less times as possible).
NB: [Of course, in the example above we can deal with the duplicates' overhead right in the client code (in the KnowledgeBase class) by obtaining a stream of distinct items and then reducing it into the result map. But this is just that example. What I did really mean is a component with some cacheable method and that method being invoked from different threads, with some of the invocations leading to generation of the same cache key.]
To avoid the standard behavior, we need synchronized "compute-if-absent" semantics (or, in more general terms, atomic "check-then-act"):
Since the version 4.3 of Spring the annotation @Cacheable has an option "sync" (by default set to "false") which, if being set to "true", does exactly that. But, as it's said in the documentation, the "sync" option is just a hint and whether it's being supported or not is a matter of implementation. The Ehcache implementation in the spring-context-support module, which under the hood uses Ehcache 2.x, does not support this feature. So, what are the options left (besides the ones with using a proper implementation with support of "sync" feature)? To mark the @Cacheable target method as synchronized? It won't help -- in this case, the threads looking for the same key in the cache will just encounter a cache-miss concurrently and then the invocations of the target method will be performed in a synchronized manner and still get the cache filled (and the unwanted task performed) more than once -- this is due to the fact that the cache-miss is happening earlier in the Spring cache facility and the actual target method's invocation is just a consequence of it.
We can solve the problem by the following way: create a new proxy-component over the target one (which uses caching) and mark desired methods (at which we want to have the atomic computeIfAbsent semantics) as synchronized. Thus, at any given moment of time only one thread can access the method aspected on caching, so there won't be such cases with simultaneous cache-misses and multiple target method's invocations.
And this is for the KnowledgeBase component:
However, the solution has some drawbacks of synchronized methods:
-- the method "findAnswer" is now pure sequental (that is, even if we ask entirely different questions) and can't be utilized in the truly parallel fashion;
-- opportunity for starvation, i.e. when the thread which is currently performing the task to fill the cache could stuck for some reason, thus preventing other threads to invoke the desired method.
-- high lock contention, and it gets even worse if all the desired target methods are being guarded by the same lock (i.e. if we have 10 target methods and just wrap them into the corresponding proxy methods marked as synchronized then all the 10 methods are now sequential in respect to each other as each of them is locked with 'this' reference of the proxy instance). So, if you really need to synchronize more than one cacheable target method then at least do it using different locks (providing the generated cache keys for the methods don't overlap -- otherwise you might want to synchronize them using the same lock).
Another way to avoid the problem might be to use somewhat similar to the lock striping technique. It greatly improves concurrency in comparison to the one-lock synchronization. Ideally, we want to lock on something that resembles a cache key which would be used by the cache framework to find a relevant cache entry. It doesn't need to be the key itself, but something that has the similar functional dependency from the arguments that making up the cache key. The idea here is to use some kind of algorithm that will give the very same lock object for the same arguments. By the notion of "very same" I mean that it must be the same object on the heap, not just any equal -- otherwise, you will be locking on two different locks. At first, I was thinking that for a sole String argument, like in the example above, the object returned by String.intern() would do just fine, and that Strings in general might be particularly delightful in this regard -- the literals are pooled right away and the interned ones are pooled on the fly, giving you a built-in mechanism for obtaining "the very same" objects. But it's not that simple -- interned strings are garbage-collectible as well, so at two different points of time there might be two different String objects for the same literal. Instead, we could maintain an array of locks (i.e. java.util.concurrent.locks.ReentrantLock) of some length N, calculate some hash value of the target method's arguments and then calculate the index of the lock as hash (mod N). Also, further improving concurrency, we could use several such lock arrays -- by one for each target method. This solution looks ugly indeed (or, to put it more politically correct, adds some complexity to the code), but it is a tradeoff.
----------
P.S.
Also, in a code snippet above I've printed the following line:
I advise you to be aware of the usage of potentially blocking methods (like the "findAnswer" one) in parallel streams, as it might cause exhaustion (starvation) of the common fork-join pool's worker threads (or whatever fork-join pool the parallelStream()'s tasks are being invoked in) due to all them being blocked somewhere inside such methods, or even worse -- the starvation-deadlock, which happens when methods are spawning asynchronous subtasks (i.e. via CompletableFuture *async methods providing the current executor), sending it to the same bounded thread pool as they are in (for the unbounded thread pools this problem does not arise) and then joining on those subtasks, so there might be a case when all worker threads block in .join() forever because the pool has no more workers to execute the spawned subtasks.
For more information on this topic, see such articles as
Java Parallel Streams Are Bad for Your Health!
Think Twice Before Using Java 8 Parallel Streams
ManagedBlocker
Комментариев нет:
Отправить комментарий