Apache LRU算法问题分析解决
UDL(United Data Load)是公司开发用于通用数据加载工具，支持抽取设置、作业定义并提供页面监控等功能，在某一项目中中多次出现了UDL作业调度出现问题，由于该问题隐藏得较深，分析解决花了较多的精力，现把经验总结共享给大家。
1. 问题现象
问题一般是UDL运行3-5天才出现，出现错误现象是固定的，后台抛出如下异常(红色部分是下面分析的切入点)：
1 2011-10-08 01:05:00,078 [] ERROR - 作业：DELETE_F_TABLE_ALL_WORKID运行过程中发生不可预知的错误，当前作业在本次调度中终止运行,发生不可预知的错误，这通常是基础信息配置有误，或运行环境异常导致，等原因，请根据错误提示信息，检查错误原因 [URuntimeJob:runJob]
2 java.lang.IllegalStateException: Entry.next=null, data[removeIndex]=resoft.udl.schedule.JobKey@600a5e7d=false previous=resoft.udl.schedule.JobKey@74a3b4ef=false key=resoft.udl.schedule.JobKey@fb09e543 value=true size=150 maxSize=150 Please check that your keys are immutable, and that you have used synchronization properly. If so, then please report this to commons-dev@jakarta.apache.org as a bug.
3 at org.apache.commons.collections.map.LRUMap.reuseMapping(LRUMap.java:300)
4 at org.apache.commons.collections.map.LRUMap.addMapping(LRUMap.java:266)
5 at org.apache.commons.collections.map.AbstractHashedMap.put(AbstractHashedMap.java:283)
6 at resoft.udl.jetlValidate.logicValidate.validator.ValidatorFactory.setJobOver(ValidatorFactory.java:57)
7 at resoft.udl.job.URuntimeJob.runJob(URuntimeJob.java:389)
8 at resoft.udl.job.URuntimeJob.execute(URuntimeJob.java:132)
9 at org.quartz.core.JobRunShell.run(JobRunShell.java:202)
10 at edu.emory.mathcs.backport.java.util.concurrent.ThreadPoolExecutor.runWorker(ThreadPoolExecutor.java:987)
11 at edu.emory.mathcs.backport.java.util.concurrent.ThreadPoolExecutor$Worker.run(ThreadPoolExecutor.java:528)
12 at java.lang.Thread.run(Thread.java:595)
2 java.lang.IllegalStateException: Entry.next=null, data[removeIndex]=resoft.udl.schedule.JobKey@600a5e7d=false previous=resoft.udl.schedule.JobKey@74a3b4ef=false key=resoft.udl.schedule.JobKey@fb09e543 value=true size=150 maxSize=150 Please check that your keys are immutable, and that you have used synchronization properly. If so, then please report this to commons-dev@jakarta.apache.org as a bug.
3 at org.apache.commons.collections.map.LRUMap.reuseMapping(LRUMap.java:300)
4 at org.apache.commons.collections.map.LRUMap.addMapping(LRUMap.java:266)
5 at org.apache.commons.collections.map.AbstractHashedMap.put(AbstractHashedMap.java:283)
6 at resoft.udl.jetlValidate.logicValidate.validator.ValidatorFactory.setJobOver(ValidatorFactory.java:57)
7 at resoft.udl.job.URuntimeJob.runJob(URuntimeJob.java:389)
8 at resoft.udl.job.URuntimeJob.execute(URuntimeJob.java:132)
9 at org.quartz.core.JobRunShell.run(JobRunShell.java:202)
10 at edu.emory.mathcs.backport.java.util.concurrent.ThreadPoolExecutor.runWorker(ThreadPoolExecutor.java:987)
11 at edu.emory.mathcs.backport.java.util.concurrent.ThreadPoolExecutor$Worker.run(ThreadPoolExecutor.java:528)
12 at java.lang.Thread.run(Thread.java:595)
2. 问题分析
跟踪了UDL代码 ValidatorFactory.java中setJobOver方法
1 private static Map isJobOverMap = new LRUMap(100);
2 public static void setJobOver(String jobid, String date, boolean isTaskJobOver) {
3 isJobOverMap.put(new JobKey(jobid, date), Boolean.valueOf(isTaskJobOver));
4 }
2 public static void setJobOver(String jobid, String date, boolean isTaskJobOver) {
3 isJobOverMap.put(new JobKey(jobid, date), Boolean.valueOf(isTaskJobOver));
4 }
在LRUMap.java 调用的代码如下(红色为抛出异常点)：
1 protected void reuseMapping(LinkEntry entry, int hashIndex, int hashCode, Object key, Object value) {
2 try {
3 int removeIndex = hashIndex(entry.hashCode, data.length);
4 HashEntry[] tmp = data; // may protect against some sync issues
5 HashEntry loop = tmp[removeIndex];
6 HashEntry previous = null;
7 while (loop != entry && loop != null) {
8 previous = loop;
9 loop = loop.next;
10 }
11 if (loop == null) {
12 throw new IllegalStateException(
13 ……
14 }
2 try {
3 int removeIndex = hashIndex(entry.hashCode, data.length);
4 HashEntry[] tmp = data; // may protect against some sync issues
5 HashEntry loop = tmp[removeIndex];
6 HashEntry previous = null;
7 while (loop != entry && loop != null) {
8 previous = loop;
9 loop = loop.next;
10 }
11 if (loop == null) {
12 throw new IllegalStateException(
13 ……
14 }
从获取的日志结合出错现象分析，出错可能有如下几个方面：
- 网络问题 由于网络中断造成数据库连接出现中断，但该问题出现比较有规律，实际情况出现的可能性很小，初步排除；
- 数据库连接超时时间 数据库连接时间设置不足引起连接被注销，通过后面设置数据库连接超时来看，并不是该问题造成的，可以排除；
- 使用LRU算法出错 所谓LRU是Least Recently Used最近最少使用算法，主要是防止使用内存过大，造成内存溢出的一种方法，在编程中主要用于存放使用即可抛弃的对象。UDL存放作业是否完成的状态，有可能出现存放状态的对象被挤出内存情况，造成获取状态时无法找到，这个问题可能性较大，作为后面分析的重点；
- 线程同步问题 由于Apache中LRU算法是非线程安全的，LRU中存放对象达到最大数量调用LRU算法reuse内存空间，由于非线程安全可能出现两个进程同时操作一个内存区域造成错误，可能性非常大；
从更深入了解客户现场定义的作业将近100多个，设置LRU的最大数量为150，这样在运行一段时间后达到了LRU设置的最大数量，此时将调用LRU算法进行内存清理、替换，出现如上问题。
3. 问题解决
通过问题分析，我们大致清楚了LRU算法及线程同步是解决问题的方法，提出了两个解决方案：
- 不使用LRU算法，通过手工管理作业生命周期
- 在代码中加入线程同步的代码
对比两个方案第一种方案会比较彻底，但改动较大，第二种方案比较简单，故先采用第二种方案，红色部分为修改。
1 public static void setJobOver(String jobid, String date,
2 boolean isTaskJobOver) {
3
4 synchronized (isJobOverMap) {
5 isJobOverMap.put(new JobKey(jobid, date), Boolean.valueOf(isTaskJobOver));
6 }
7 }
2 boolean isTaskJobOver) {
3
4 synchronized (isJobOverMap) {
5 isJobOverMap.put(new JobKey(jobid, date), Boolean.valueOf(isTaskJobOver));
6 }
7 }
通过如上修改解决了问题。
4. 需要注意
通过以上问题和代码分析解决了隐藏较深的一个Bug，可以借鉴的经验有：
- 慎用LRU算法，最好存放使用即抛弃对象不存在问题；对于存放需要维护的对象时，最好不使用，存在需休眠对象被清除的风险；
- 特别要注意线程安全问题，需进行同步。