缓存同步策略重构

简述一下CommonTemplate(http://www.commontemplate.org)的模板工厂每次获取模板的过程如下：

检查内存缓存中是否存在，
若不存在，则检查持久化缓存中是否存在，
若还不存在，则重新解析模板并将模板压入内存缓存及持久化缓存，
若存在，则检查是否需要热加载，
若需要热加载，则对比文件是否已更改，
若已更改，则重新解析模板并将模板压入内存缓存及持久化缓存，
返回模板

因为很多检测点，开始整个过程都被同步执行了，

和huangyh讨论时，
他提出，如果去掉同步，会出现什么？
总结是：
一、在并发下，同一模板会多次被解析和缓存，
二、非同步缓存容器保存时可能出错，

讨论后发现：
第一种影响对程序的正确性没什么影响的，只是“觉得”多次解析和缓存会影响性能，
而实际上，这些影响性能比同步块对引擎活性的影响要小很多，
即然如此，那只要保证缓存容器自身是线程安全的，就没必要同步整个获取过程。

缓存容器采用的是策略模式，
引擎留出的SPI是：org.commontemplate.config.Cache接口，重构后：
第一种方式：
在Cache接口的文档中声明，Cache的实现者都必须线程安全，即自行实现同步。
第二种方式：
引擎在调用Cache之前，使用装饰器模式统一外包装实现同步。
第三种方式：
结合上面两种方式，再加一个是否需要外部同步的标识性接口，引擎基于此判断是否需要外部同步。

评论

20 楼 javatar 2007-11-29  

Java并发实践上有一个案例，和这里的缓存有几分相似，
有一个很耗时的运算需要缓存其计算结果，采用备忘录模式实现，如：

public interface Computable<A, V> {
    V compute(A arg) throws InterruptedException;
}

public class ExpensiveFunction
        implements Computable<String, BigInteger> {
    public BigInteger compute(String arg) {
        // 假设这里非常耗时...
        return new BigInteger(arg);
    }
}

备忘录缓存方案一：

public class Memoizer1<A, V> implements Computable<A, V> {
    @GuardedBy("this")
    private final Map<A, V> cache = new HashMap<A, V>();
    private final Computable<A, V> c;

    public Memoizer1(Computable<A, V> c) {
        this.c = c;
    }

    public synchronized V compute(A arg) throws InterruptedException {
        V result = cache.get(arg);
        if (result == null) {
            result = c.compute(arg);
            cache.put(arg, result);
        }
        return result;
    }
}

这里备忘录的整个compute过程被同步，相当于我最原始的低效方案，


备忘录缓存方案二：

public class Memoizer2<A, V> implements Computable<A, V> {
    private final Map<A, V> cache = new ConcurrentHashMap<A, V>();
    private final Computable<A, V> c;

    public Memoizer2(Computable<A, V> c) { this.c = c; }

    public V compute(A arg) throws InterruptedException {
        V result = cache.get(arg);
        if (result == null) {
            result = c.compute(arg);
            cache.put(arg, result);
        }
        return result;
    }
}

将线程安全性委给cache，注：这个方案的cache用了ConcurrentHashMap，它是线程安全的。相当于huangyh提出的全部不同步。

备忘录缓存方案三：

public class Memoizer3<A, V> implements Computable<A, V> {
    private final Map<A, Future<V>> cache
            = new ConcurrentHashMap<A, Future<V>>();
    private final Computable<A, V> c;

    public Memoizer3(Computable<A, V> c) { this.c = c; }

    public V compute(final A arg) throws InterruptedException {
        Future<V> f = cache.get(arg);
        if (f == null) {
            Callable<V> eval = new Callable<V>() {
                public V call() throws InterruptedException {
                    return c.compute(arg);
                }
            };
            FutureTask<V> ft = new FutureTask<V>(eval);
            f = ft;
            cache.put(arg, ft);
            ft.run(); // call to c.compute happens here
        }
        try {
            return f.get();
        } catch (ExecutionException e) {
            throw launderThrowable(e.getCause());
        }
    }
}

他给出的第三种方案和leadyu的差不多，使用Future(相当上一帖的Entry)封装，因为这里资源获取过程不固定(通用方案)，所以使用了Callable进行回调资源获取过程(求值)，
这个方案的 if (f == null) 不安全，特殊性可能会进行多次运算，下面的方案四解决这个问题。

备忘录缓存方案四（最终方案）：

public class Memoizer<A, V> implements Computable<A, V> {
    private final ConcurrentMap<A, Future<V>> cache
        = new ConcurrentHashMap<A, Future<V>>();
    private final Computable<A, V> c;

    public Memoizer(Computable<A, V> c) { this.c = c; }

    public V compute(final A arg) throws InterruptedException {
        while (true) {
            Future<V> f = cache.get(arg);
            if (f == null) {
                Callable<V> eval = new Callable<V>() {
                    public V call() throws InterruptedException {
                        return c.compute(arg);
                    }
                };
                FutureTask<V> ft = new FutureTask<V>(eval);
                f = cache.putIfAbsent(arg, ft);
                if (f == null) { f = ft; ft.run(); }
            }
            try {
                return f.get();
            } catch (CancellationException e) {
                cache.remove(arg, f);
            } catch (ExecutionException e) {
                throw launderThrowable(e.getCause());
            }
        }
    }
}

19 楼 javatar 2007-11-28  

再重构：

private final ReloadController reloadController;

private final TemplateSourceComparator templateSourceComparator;

private final Cache cache;

private static final class Entry {
	
	Entry() {}
	
	private Object resource = null;

	Object get() {
		return resource;
	}
	
	void set(Object template) {
		this.resource = template;
	}

}

private Template cache(String name, String encoding) 
		throws IOException, ParseException {
	
	Entry entry = null;
	
	// 先进行一次无锁读取，此过程不调用任何有副作用(修改状态)的函数，也不调用任何耗时操作
	if (reloadController == null 
			|| ! reloadController.shouldReload(name)) { // 不需要热加载时才进行
		entry = (Entry)cache.get(name);
		if (entry != null) {
			Template template = (Template)entry.get();
			if (template != null)
				return template;
		}
	}
	
	// 缓存总锁，锁定各条目的获取
	synchronized(cache){
		entry = (Entry)cache.get(name); // 这里必需重新读取
		if(entry == null){ 
			entry = new Entry(); 
			cache.put(name, entry); 
		}
		assert(entry != null); // 后验条件
	}
	
	// 单条目锁，锁定资源获取过程
	synchronized (entry) {
		Template template = (Template)entry.get();
		if (template == null) { // 不存在，解析加载
			TemplateSource templateSource = load(name, encoding);
			template = parse(templateSource);
			entry.set(template);
		} else { // 已存在，检查热加载
			if (reloadController != null && reloadController.shouldReload(name)) { // 是否需要检查热加载
				TemplateSource templateSource = load(name, encoding);
				if (templateSourceComparator != null 
						&& templateSourceComparator.isModified(template, templateSource)) { // 比较是否已更改
					template = parse(templateSource);
					entry.set(template);
					return template;
				}
			}
		}
		assert(template != null); // 后验条件
		return template;
	}
}

18 楼 leadyu 2007-11-27  

上面第9第10行可以去掉，多余了。

引用

而且上面还有一个问题，就是热加载。每次访问都去load一下是不行的，load是一个秒级操作，对于系统级的组件来说（比如common template or JSP）这是绝对不能接受的。

我暂时收回这句话，呵呵，下午翻了翻，Tomcat5 的代码，只要option的getDeployment开关打开，也就是在开发模式下，他每次servlet的访问都去编译java文件，编译class文件，new新的ClassLoader,加载新的servlet。汗。。。神阿，你不要这样，怎么你也这么搞？搞得我以为你有什么绝招，翻了半天你的代码。----to Tomcat

如果不在开发模式下，JSP他不更新。但是有一点他应该是优化了，他记录下来了资源的路径，直接加载，省去了查找了开销，应该来说查找的开销会比读文件多数倍，特别是项目文件多的时候。我觉得，CommonTemplate有时间的话也可以这么做，在TemplateLock里面记录path信息，应该不叫TemplateLock，应该改成
ResorceEntry。

不知道weblogic的ChangeWareClassLoader是不是也是这样？

17 楼 javatar 2007-11-27  

leadyu 写道

2）保证需要加载资源时，其他访问线程可以先等着，不要也去加载，浪费CPU和IO操作，load是非常慢的一个操作。

嗯，这是个问题，看来预读时要避开IO读写等耗时操作才行。

如果没有热加载问题，进行预读是很好的想法，如：

...

    TemplateLock templateLock = (TemplateLock)templateCache.get(name);   
    if (templateLock != null && templateLock.getTemplate() != null) {
        return templateLock.getTemplate()
    }

...

另外，IO操作出现在第10行，而不是第9行，因为：
上面的load是回调TemplateSourceLoader接口的loadTemplateSource()，
TemplateSourceLoader.loadTemplateSource通常不是真的去加载数据，而是简单的创建表示信息，
以FileTemplateSourceLoader为例，当调用loadTemplateSource时，只是将new File()包装成TemplateSource返回，并没有打开流，应该不会有大的性能消耗。
当调用TemplateSource的getReader()或getLastModified()才有可能打开流或读取内容，
也就是第10行：templateSourceComparator.isModified(template, templateSource)) 可能出现大的性能消耗，isModified可能比的是最后修改时间，也可能是全文对比，要看TemplateSourceComparator接口的具体实现，但不管怎么样，即然要拿到文件的实际信息，此时总会有IO操作。

16 楼 leadyu 2007-11-27  

这样不行，锁得的就是Load方法，还放在外面无锁预读，不是白锁了吗？（见上第9行），虽然说，两个线程同时Load没问题，只要Put的时候同步一下get就可以了，但是，大并发下，多个线程，同时Load一个资源，做同样的比较，不是太浪费了吗？这样锁得目的，两个：1）是保证线程安全，因为无法知道parse语法分析时会不会涉及一些共享资源
2）保证需要加载资源时，其他访问线程可以先等着，不要也去加载，浪费CPU和IO操作，load是非常慢的一个操作。


而且上面还有一个问题，就是热加载。每次访问都去load一下是不行的，load是一个秒级操作，对于系统级的组件来说（比如common template or JSP）这是绝对不能接受的。

15 楼 javatar 2007-11-27  

是否应像jindw那样加入无锁预读？那就需要两次热加载检查，如：

private Template cache(String name, String encoding)    
        throws IOException, ParseException {   

	// 先进行一次无锁读取，此过程不调用任何有副作用(修改状态)的函数
	TemplateLock templateLock = (TemplateLock)templateCache.get(name);
	if (templateLock != null && templateLock.getTemplate() != null) {
		Template template = templateLock.getTemplate();
		if (reloadController != null && reloadController.shouldReload(name)) { // 是否需要检查热加载
			TemplateSource templateSource = load(name, encoding);
			if (templateSourceComparator != null && templateSourceComparator.isModified(template, templateSource)) { // 比较是否已更改
				template = null;
			}
		}
		if (template != null)
			return template;
	}

    // 工厂锁，锁定模板锁   
    synchronized(factoryLock) {   
        TemplateLock templateLock = (TemplateLock)templateCache.get(name); // 此处应保持重新读取
        // 同上帖...
    }   
       
    // 模板锁，锁定模板获取过程   
    synchronized (templateLock) {   
        // 同上帖...
    }   
}

还有没有更好的方式？
如果没问题，准备下一个版本加入。

14 楼 javatar 2007-11-25  

发布了新版本0.7.3：http://www.commontemplate.org

采用了leadyu的方式，使用外包装分级锁。
org.commontemplate.engine.TemplateFactoryImpl 的相关代码：

private final Cache templateCache; // 策略传入

private final ReloadController reloadController; // 策略传入

private final TemplateSourceComparator templateSourceComparator; // 策略传入

private final Object factoryLock = new Object();

private static final class TemplateLock {
	
	TemplateLock() {}
	
	private Template template = null;

	Template getTemplate() {
		return template;
	}
	
	void setTemplate(Template template) {
		this.template = template;
	}

}

private Template cache(String name, String encoding) 
		throws IOException, ParseException {

	TemplateLock templateLock = null;

	// 工厂锁，锁定模板锁
	synchronized(factoryLock) {
		templateLock = (TemplateLock)templateCache.get(name);
		if(templateLock == null){ 
			templateLock = new TemplateLock(); 
			templateCache.put(name, templateLock); 
		}
		assert(templateLock != null); // 后验条件
	}
	
	// 模板锁，锁定模板获取过程
	synchronized (templateLock) {
		Template template = templateLock.getTemplate();
		if (template == null) { // 不存在，解析加载
			TemplateSource templateSource = load(name, encoding);
			template = parse(templateSource);
			templateLock.setTemplate(template);
		} else { // 已存在，检查热加载
			if (reloadController != null && reloadController.shouldReload(name)) { // 是否需要检查热加载
				TemplateSource templateSource = load(name, encoding);
				if (templateSourceComparator != null && templateSourceComparator.isModified(template, templateSource)) { // 比较是否已更改
					template = parse(templateSource);
					templateLock.setTemplate(template);
					return template;
				}
			}
		}
		assert(template != null); // 后验条件
		return template;
	}
}

13 楼 nihongye 2007-11-24  

jindw 写道

nihongye 写道

思路挺好，代码有问题。
syn..(globalLock)
syn..(resourceLock ){
之间未同步。不用同步块的形式

恩，只是我想：两个块之间还需要同步吗？

第一个同步块确保取到资源对应的唯一锁。
第二个同步块确保同一的资源不产生多个实例。

再第二个同步块里还有一次读取操作，我还没想到需要在两块之间同步的理由。

不用，是我搞错了：）

12 楼 jindw 2007-11-24  

nihongye 写道

思路挺好，代码有问题。
syn..(globalLock)
syn..(resourceLock ){
之间未同步。不用同步块的形式

恩，只是我想：两个块之间还需要同步吗？

第一个同步块确保取到资源对应的唯一锁。
第二个同步块确保同一的资源不产生多个实例。

再第二个同步块里还有一次读取操作，我还没想到需要在两块之间同步的理由。

11 楼 nihongye 2007-11-24  

Quake Wang 写道

javatar 写道

Quake Wang 写道

4. 若已更改，清除缓存中对于的这个Key，并且跳到第一步
5. 若不存在，重新解析模板并将模板压入缓存

第5步会不会出现并发修改异常？

这依赖于Cache的实现，成熟的Cache解决方案都会在put方法内部解决并发问题。

正解。内存缓存，用一个同步的HashMap就可以了，譬如继承LinkedHashMap，重写方法removeEldestEntry便可以实现一个LRU策略的Map，够成熟。

10 楼 nihongye 2007-11-24  

我想错了

9 楼 QuakeWang 2007-11-24  

javatar 写道

Quake Wang 写道

4. 若已更改，清除缓存中对于的这个Key，并且跳到第一步
5. 若不存在，重新解析模板并将模板压入缓存

第5步会不会出现并发修改异常？

这依赖于Cache的实现，成熟的Cache解决方案都会在put方法内部解决并发问题。

8 楼 javatar 2007-11-24  

Quake Wang 写道

A. 内存缓存及持久化缓存不应该作为2种缓存，缓存在哪里应该由Cache的实现者处理，而不是Cache的使用者就提前设计好的，比如Ehcache，OSCache都提供了基于内存和文件系统持久化的缓存。

这个肯定，引擎只会留出一个Cache的SPI，不会决定什么内存缓存和持久化缓存，
上面说的只是现在内置的Cache实现：持久化缓存包装内存缓存(Decorator方式)，他们都实现了Cahce接口，只是组成了链，可以被替换掉。

Quake Wang 写道

4. 若已更改，清除缓存中对于的这个Key，并且跳到第一步
5. 若不存在，重新解析模板并将模板压入缓存

第5步会不会出现并发修改异常？

7 楼 huangyh 2007-11-23  

jindw 的策略不错．呵呵

6 楼 QuakeWang 2007-11-23  

有2点想法：
A. 内存缓存及持久化缓存不应该作为2种缓存，缓存在哪里应该由Cache的实现者处理，而不是Cache的使用者就提前设计好的，比如Ehcache，OSCache都提供了基于内存和文件系统持久化的缓存。

B. 作为模板语言的解析结果缓存，可以不加同步，我觉得这一点要求也不是必须的：

javatar 写道

在Cache接口的文档中声明，Cache的实现者都必须线程安全，即自行实现同步。

比如我用非线程安全的HashMap来实现一个简单的内存缓存，获取缓存模板方法改成失效清除的策略：
1. 检查缓存中是否存在
2. 若存在，则检查是否需要热加载
3. 若需要热加载，则对比文件是否已更改
4. 若已更改，清除缓存中对于的这个Key，并且跳到第一步
5. 若不存在，重新解析模板并将模板压入缓存
6. 返回模板

5 楼 jindw 2007-11-23  

leadyu 写道

javatar 写道

楼上两位好想法！
。。。。

用Resource包装，主要为了保证entity和lock的缓存策略一致性，避免，一个存在一个不存在。

因为lock集合也必须有缓存策略，不能无限增大

leadyu
现在的想法已经更加完善了

不过，lock集合我认为就不需要缓存策略了，区区一个简单对象，由他去把。

4 楼 leadyu 2007-11-23  

javatar 写道

楼上两位好想法！

按单实例分别开锁，可以减少很大同步面，且缓存容器可以不同步。

leadyu将template包装成Resource，再拿Resource作为锁
jindw将锁放在一个集合内，用同一个key却取锁，与template完全分离

哪一种会更有优势？

那是否可以直接用template(被缓存对象)本身作为锁？

用Resource包装，主要为了保证entity和lock的缓存策略一致性，避免，一个存在一个不存在。

因为lock集合也必须有缓存策略，不能无限增大

3 楼 javatar 2007-11-23  

楼上两位好想法！

按单实例分别开锁，可以减少很大同步面，且缓存容器可以不同步。

leadyu将template包装成Resource，再拿Resource作为锁
jindw将锁放在一个集合内，用同一个key却取锁，与template完全分离

哪一种会更有优势？

那是否可以直接用template(被缓存对象)本身作为锁？
看来是不行，template在锁之前不存在。

2 楼 jindw 2007-11-23  

var res = getResoure(key);
if(res){
  return res;
}


sych(globalLock){
  var resourceLock = requireLock(key);
}
sych(resourceLock ){
  res = getResoure(key);
  if(res){
    return res;
  }
  res = buildResoure(key);
  putResoure(key,res);
  return res;
}

这样如何？

1 楼 leadyu 2007-11-23  

可以以资源对象为锁对象进行同步，可以参考Tomcat的WebAppClassLoader的加载实现：

static final Object lock=new Object();
		
Resource entity=null;
entity=cache.get(name);
if(entity!=null)return entity;

sychonize(lock){

	entity=cache.get(name);

	if(entity==null){
		entity=new Resource();
		cache.put(name,entity);
	}

}

sychonize(entity){
         if(entity!=null && entity.getResource()!=null)return entity;

	Template template=load();
	entity.setResource(template);

}

这样应该是安全的，大家再看看有没更好的写法