淘先锋技术网

首页 1 2 3 4 5 6 7
一种习以为常的缓存写法:

IF value in cached THEN
  return value from cache
ELSE
  compute value
  save value in cache
  return value
END IF 

看上去逻辑无比正确,但实际上会造成2种问题:

1、这种方法是不线程安全的。

2、产生数值写入重复,造成错误的数据。

如下图,在线程1执行计算数值的过程中,线程2也进入数据检查,将多次写入数据,程序非常危险。

 

 

演示错误代码:

    //最容易产生的错误写法,先读取缓存,读不到就写缓存
    public Long getNumber(final long index) {
        if (cache.containsKey(index)) {
            return cache.get(index);
        }
        
        final long value = getNumber(index - 1) + getNumber(index - 2);
        cache.put(index, value);
        return value;
    }

 

1、传统的解决办法,使用重入锁 (getNumberByLock 方法)或者同步锁(getNumberBySynchroniz 方法)。

代码

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.Future;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

public class NaiveCacheExample {

    private final Map<Long, Long> cache = new HashMap<>();
    private Object o=new Object();
    Lock lock =new ReentrantLock();
    
    public NaiveCacheExample() {
        cache.put(0L, 1L);
        cache.put(1L, 1L);
    }
    
    //最容易产生的错误写法,先读取缓存,读不到就写缓存
    public Long getNumber(final long index) {
        if (cache.containsKey(index)) {
            return cache.get(index);
        }
        
        final long value = getNumber(index - 1) + getNumber(index - 2);
        cache.put(index, value);
        return value;
    }

    //使用折返锁,使读写同步
    public Long getNumberByLock(final long index) {       
        long value =0;
        try {
            lock.lock();           
            if (cache.containsKey(index)) {
                return cache.get(index);
            }
            value = getNumberByLock(index - 1) + getNumberByLock(index - 2);
            cache.put(index, value);
            return value;
        }
        catch (Exception e)
        {}
        finally
        {
            lock.unlock();
        }
         
        return 0l;
    }
    
    //使用同步,使读写同步
    public Long getNumberBySynchroniz(final long index) {
        synchronized (o)
        {
        long value =0;
        try {
            if (cache.containsKey(index)) {
                return cache.get(index);
            }
            value = getNumberBySynchroniz(index - 1) + getNumberBySynchroniz(index - 2);
            cache.put(index, value);
            return value;
        }
        catch (Exception e)
        {}
        finally
        {
        
        }
        }
        return 0l;
    }


    public static void main(final String[] args) {
       
        NaiveCacheExample naiveCacheExample =new NaiveCacheExample();
        
        Thread threadA =new Thread(new Runnable()
        {
            @Override
            public void run() {
                System.out.println(naiveCacheExample.getNumberBySynchroniz(1000));                
            }
            
        }
        ,"Thread-A");
        threadA.start();
        
        final Thread threadB = new Thread(new Runnable() {
          public void run() {
              System.out.println(naiveCacheExample.getNumberBySynchroniz(1000));
          }
        }, "Thread-B");
        threadB.start();
        

    }
}

 

 

2、一个更好的缓存算法可以用 Callable 和 Future 。 缓存的值将存储在一个实例 ConcurrentMap 中 ,ConcurrentMap 是线程安全的。

代码:

import java.util.concurrent.Callable;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentMap;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.Future;
import java.util.concurrent.FutureTask;

public class GenericCacheExample<K, V> {

    private final ConcurrentMap<K, Future<V>> cache = new ConcurrentHashMap<>();

    private Future<V> createFutureIfAbsent(final K key, final Callable<V> callable) {
        Future<V> future = cache.get(key);
        if (future == null) {
            final FutureTask<V> futureTask = new FutureTask<V>(callable);
            future = cache.putIfAbsent(key, futureTask);
            if (future == null) {
                future = futureTask;
                futureTask.run();
            }
        }
        return future;
    }

    public V getValue(final K key, final Callable<V> callable) throws InterruptedException, ExecutionException {
        try {
            final Future<V> future = createFutureIfAbsent(key, callable);
            return future.get();
        } catch (final InterruptedException e) {
            cache.remove(key);
            throw e;
        } catch (final ExecutionException e) {
            cache.remove(key);
            throw e;
        } catch (final RuntimeException e) {
            cache.remove(key);
            throw e;
        }
    }

    public void setValueIfAbsent(final K key, final V value) {
        createFutureIfAbsent(key, new Callable<V>() {
            @Override
            public V call() throws Exception {
                return value;
            }
        });
    }

}

 

参考博客:

http://www.javacreed.com/how-to-cache-results-to-boost-performance/