Recently I came across an interesting programming problem I want to
share with you. In short this post discusses thread-safe and fast java
implementation of a cache for some special case.
To give you some background, this problem arose in scope of my pet project PUNKSearch
(local network indexer and searcher based on Lucene
).
PUNKSearch shows online/offline status of the hosts displayed in search
results. These statuses are cached for several minutes to avoid “dogpile effect
”
on remote hosts and increase overall responsiveness of the application.
Cache is organized as HashMap for which keys are IPs and values are
pairs of Date and Boolean wrapped in some extra object named HostStatus.
The Date is used to determine if we need to refresh the status for the
host and Boolean defines whatever host is online. Obtaining status is a
Slow Process (timeout usually is 5 seconds).
Since PUNKSearch is a web application this cache must be thread-safe.
Another property we want it to have is speed. Locking the whole cache
for the period some thread tries to determine if a host is online is no
way.
Lets try to construct such a cache.
Try 1: The simple not thread-safe implementation (cache renewal is dropped for the sake of clearness
)
01
|
class
MapCacheSimpleFastBroken {
|
03
|
private
Map<String, Object> cache =
new
HashMap<String, Object>();
|
04
|
private
SlowProcess slowProcess =
new
SlowProcess();
|
06
|
public
Object get(String key) {
|
07
|
Object value = cache.get(key);
|
09
|
value = slowProcess.get(key);
|
10
|
cache.put(key, value);
|
This class obviously not thread-safe. What can we do to make it thread-safe? Of course, make the method “synchronized”!
Try 2: The simple thread-safe implementation (cache renewal is dropped for the sake of clearness
)
01
|
class
MapCacheSimpleSlowSafe {
|
03
|
private
Map<String, Object> cache =
new
HashMap<String, Object>();
|
04
|
private
SlowProcess slowProcess =
new
SlowProcess();
|
06
|
public
synchronized
Object get(String key) {
|
07
|
Object value = cache.get(key);
|
09
|
value = slowProcess.get(key);
|
10
|
cache.put(key, value);
|
This implementation is thread-safe
, good. But it is extremely slow
!
How can we avoid locking the whole cache object? What if we lock only
required portion of the map? The map key in particular. Lets try.
Try 3: The fine-grained want-to-be thread-safe implementation (cache renewal is dropped for the sake of clearness
)
01
|
class
MapCacheTrickyFastBroken {
|
03
|
private
Map<String, Object> cache =
new
HashMap<String, Object>();
|
04
|
private
SlowProcess slowProcess =
new
SlowProcess();
|
05
|
private
static
final
Object STUB =
new
Object();
|
07
|
public
Object get(String key)
throws
InterruptedException {
|
10
|
synchronized
(cache) {
|
11
|
Object value = cache.get(key);
|
12
|
if
(value !=
null
&& value != STUB) {
|
14
|
}
else
if
(value ==
null
) {
|
18
|
for
(String cacheKey : cache.keySet()) {
|
19
|
if
(cacheKey.equals(key)) {
|
28
|
Object value = cache.get(key);
|
32
|
value = slowProcess.get(key);
|
33
|
cache.put(key, value);
|
This implementation seems to be ok. We lock the whole map for a short
period of time to verify if we have required object in the cache and
possibly modify the map. If the object was not found we put a stub into
the map to sync against its key later.
Bad news. This implementation has a serious flaw. Can you find it? Look
under the cut for the explanation and the correct implementation.
Indeed, the Try 3 is broken. Assume two threads want to obtain an object for the same key “foo”.
Now imagine first thread has left the 33 line and the second thread just
fall into “else” branch at the line 14 (i.e. it is at the line 15 now).
Obviously the second thread drops all that hard work done by the first
thread and have to call the slow process again. Not good. Additionally
notice the crap we have at lines 18-23 to obtain the key object. What we
can do to avoid these 2 issues? Lets try.
Last Try: The fine-grained thread-safe implementation (cache renewal is dropped for the sake of clearness
)
01
|
class
MapCacheTrickyFastSafe {
|
03
|
private
ConcurrentHashMap<String, Object> cache =
new
ConcurrentHashMap<String, Object>();
|
04
|
private
Map<String, String> keys =
new
HashMap<String, String>();
|
05
|
private
SlowProcess slowProcess =
new
SlowProcess();
|
06
|
private
static
final
Object STUB =
new
Object();
|
08
|
public
Object get(String key)
throws
InterruptedException {
|
11
|
synchronized
(cache) {
|
12
|
Object value = cache.putIfAbsent(key, STUB);
|
13
|
if
(value !=
null
&& value != STUB) {
|
15
|
}
else
if
(value ==
null
) {
|
24
|
Object value = cache.get(key);
|
28
|
value = slowProcess.get(key);
|
29
|
cache.put(key, value);
|
Obviously, we added the “keys” map to search for required lock object quickly. This solves that crap 18-23 lines of Try 3.
What about thread safety? It is putIfAbsent
() method of ConcurrentHashMap
which helps us a lot.
The method is equal to the following code snippet (except that the action is performed atomically
):
1
|
if
(!map.containsKey(key))
|
2
|
return
map.put(key, value);
|
Finally, we have fast and thread-safe cache implementation!
Please note, however, all implementations lack renewal of cached objects
and this was done by intention for this post. Moreover, implementations
suffer from memory leak. Can you see it? That simple — all distinct
keys create respective objects in cache and that objects never dropped
from the cache (may be replaced, yes). So the map is growing constantly.
For the production implementation one may want to implement periodical
cleanup of the map from very old objects using TimerTask or as side
effect of the get() method call.
I hope this post was not extra boring and more than that I hope the
last try is indeed thread-safe :) Have I missed something? Let me know
;)
分享到:
相关推荐
php5.5.25 TS版本(Thread-Safe-VC9-X86)
NET多线程程序中不再需要多次拷贝粘贴InvokeRequired
赠送jar包:transmittable-thread-local-2.12.1.jar; 赠送原API文档:transmittable-thread-local-2.12.1-javadoc.jar; 赠送源代码:transmittable-thread-local-2.12.1-sources.jar; 赠送Maven依赖信息文件:...
从PHP5.2.10版本开始(现在有PHP5.2.10和5.3两个版本),有None-Thread Safe与Thread Safe两种版本的可供选择,这两种版本有何不同,作为使用者来说又应该如何选择呢?下面聚友将为您讲述。
一个java线程安全的单例模式:饥饿模式和延迟加载
Thread-safe. All APIs for config is thread-safe. Batteries included. Support sources from JSON, XML, YAML, HOCON, TOML, properties, map, command line and system environment out of box. Cascading. ...
赠送jar包:transmittable-thread-local-2.12.2.jar; 赠送原API文档:transmittable-thread-local-2.12.2-javadoc.jar; 赠送源代码:transmittable-thread-local-2.12.2-sources.jar; 赠送Maven依赖信息文件:...
translation - Implementing-a-Thread-Safe-Queue-using-Condition-Variables实现一个线程安全队列原链接: 翻译: Scott Gu源代码:多线程代码需要一次又一次面对的一个问题是,如何把数据从一个线程传到另一个县城...
/thread-619-1-1.html
基于线程安全的基于时间的LRU缓存用法克隆存储库。 mkdir build cd build cmake .. make -j $(nproc -all) 使用共享库。
赠送jar包:transmittable-thread-local-2.12.1.jar; 赠送原API文档:transmittable-thread-local-2.12.1-javadoc.jar; 赠送源代码:transmittable-thread-local-2.12.1-sources.jar; 赠送Maven依赖信息文件:...
RT-Thread-OTA 用户手册 ,在使用rt-thread的时候,可以查阅并使用,包含了在线升级的基本功能,和其他功能的描述
php-7.2.3-Win32-VC15-x86 Thread Safe 官网下载的,单独PHP
rt-thread-nano-3.1.3,RT-Thread微内核,包含STM32的移植程序及应用程序,以及线程、队列、事件的应用
Java-Thread-Affinity,将Java线程绑定到给定的内核.zip
RingQueuethread-safe Ring queue. 线程安全的环形队列.
thread_safe.rar
rt-thread-master
RT-THREAD最新编程指南