多线程下lrumap的操作经验

   前些时候用到了apache的Lrumap,用来维护N个用户的定购关系列表,大致是Lrumap<string,List<string>>后来测试的时候出现了一个很奇怪的问题,就是系统运行一段时间后会发现某些用户的某些定购关系在内存中不存在,但是数据库中却是有值的。开始的时候我怀疑用户名id（即map的key）所对应的List空掉了,最后想了很久发现应该是值缺失了一部分,而不是空掉了。


下边是一个经过抽象后的简单模型：

Map<String, List<String>> m = new LruMap<String, List<String>>; 
// 由于最新的apache 的common－collection3.2.1包中的lrumap是不同步的.
// 所以我想当然的对其进行了一次同步。
    boolean foo(value) { 
        List<String> list; 
        synchronized (m) { 
            list = m.get(uid); 
        } 
        if (list == null) { 
            list = getdataFormDatabase(); // 将其放在外边是由于这块可能非常慢,而并发又很严重,考虑到性能就放同步块外边了
            synchronized (m) { 
                m.put(uid, list); 
            } 
            return list.contains(value); 
        } else { 
            return list.contains(value); // 问题出现在这里,返回的是false,实际上应该为true
        } 
    } 

    foo(uid, value) { 
        List<String> list; 
        synchronized (m) { 
            list = m.get(uid); 
        } 
        if (list == null) { 
            list = getDataFromDatabase(); // 理由同上
            list.add(value); 
            synchronized (m) { 
                m.put(uid,list); 
            } 
        } else { 
            list.add(value); 
        } 
    }  

如果并发经验比较丰富的大牛一眼就会看出问题所在,
不过我开始的时候一直是认为用户id对应的List没有同步才导致的值丢失,就出现了调用foo（value）方法返回false.当然了.这里list肯定也是需要同步的.但是问题的根源我后来想了很久发现还不是在于这个list没有同步。

问题应该出现在对 getDatafromDb（）操作上.这个放到同步块外边会导致后边的put（uid,list）产生问题。

下边来简单说明一下我认为的问题所在（各位大牛可以看看是否如此）

 synchronized (m) { 
            list = m.get(uid); // 步骤1
        } 
        if (list == null) { 
            list = getdataFormDatabase(); // 步骤2
            synchronized (m) { 
                m.put(uid, list); //问题出在这里
            } 

首先, 假设我们现在有2个线程（线程1,和线程2）,先后获得m的使用权通过了步骤1,这样两个线程都会执行步骤2,好了,问题开始了。
线程1顺利执行完成 getdatafromdb的操作, 获取了listA数据,此时数据是完整的。并且再次获取了m的使用权,将其put进入map中, 此时线程2也顺利提取完成获得了另外一个listB。他准备将自己的listB也put进map。

当当当,这个时候线程3突入闯入进来, 并且获取了m的使用权,执行了步骤3,发现内存有值了（listA）,于是顺利执行了步骤4。

 synchronized (m) { 
            list = m.get(uid); // 步骤3
        } 
        if (list == null) { 
            list = getDataFromDatabase(); 
            list.add(value); 
            synchronized (m) { 
                m.put(uid,list); 
            } 
        } else { 
            list.add(value);  // 步骤4  
        } 

 
其实本来listA的内容跟listB一样, 但是由于线程3的干扰,listA的内存中有了一个新的值.但是线程3执行完成后走掉了, 线程2终于轮到m的使用权,并且将listB重新put进入map,顶替掉了listA。悲剧就这样产生了.

假设之后再也不出现这种情况（我们实际系统中理论上是不会产生一个用户id同时执行foo这2个方法的）,而且这个id又一直没有被lrumap清理掉, 就会导致内存值永久的缺失了一个值。就会出现之前的问题 了。

  问题找是找到了.怎么解决呢？

  估计最简单的是增大同步块,将getdatafromdb的操作一起都同步了就没问题了。不过考虑到性能（因为系统会对这个lrumap有非常高的并发操作.大部分都是想执行get操作）,这个一同步，外部很多线程都会被阻塞.系统估计就差不多down掉了。

   后来想到了CAS（compare and swap貌似是一个原子操作）.大概修改思路类似于cas,就是put之前再次看看是否已经有线程put值进去了。不多说,看代码大家就明白了。

    boolean foo(value) { 
        List<String> original; 
        synchronized (m) { 
            original = m.get(uid); 
        } 
        if (original == null) { 
            original = getdataFormDatabase(); // 这里返回的list是 同步的 list 
            List<String> modifys = null; 
            synchronized (m) { 
                modifys = m.get(uid); 
                if (modifys != null) { 
                    // saysomething here but no need to addall here; 
                } else { 
                    m.put(uid, original); 
                } 
            } 
            if (modifys != null) { 
                if (original.size > modifys.size) { 
                    modifys.addAll(original); // 尽量减少一次addAll操作,因为addall在数据量很大的情况下也是性能瓶颈,当然我这里数据量撑死了1w,不过为了那么一点点性能,还是判断一下
                } 
                return modifys.contains(value); 
            } 
            return original.contains(value); 
        } else { 
            return original.contains(value); 
        } 
    }

基本的原则是,只要某个uid的list被put过一次,之后就只能修改这个list而不会被新的put操作给替换掉。

同理,添加的操作也做对应的修改：

foo(uid, value) { 
        List<String> original; 
        synchronized (m) { 
            original = m.get(uid); 
        } 
        if (original == null) { 
            original = getDataFromDatabase(); // 这里返回的list是 同步的 list 
            original.add(value); 
            List<String> modifys = null; 
            synchronized (m) { 
                modifys = m.get(uid); 
                if (modifys != null) { 
                    // saysomething here but no need to addall here; 
                } else { 
                    m.put(uid, original); 
                } 
            } 
            if (modifys != null) { 
                if (original.size > modifys.size) { 
                    modifys.addAll(original); 
                } 
                modifys.add(value); 
            } else { 
                original.add(value); 
            } 
        } else { 
            original.add(value); 
        } 
}

修改完成之后, 还没有经过实际的检验, 不过这个put操作 可能引起list值缺失的情况我倒是通过几个多线程测试例子验证了。的确会发生这种情况，不过现在怎么看这个修改怎么都觉得不太优雅。不知道大牛门有没有更好的方法。

高并发的对象控制还是需要很多经验的。 我们最近做了不少多线程的代码， 确实不同程序员反应出来的经验差异很的。 要控制线程安全， 不是那么简单的事情， 特别是你处要注意锁与性能的问题。 如果不考虑性能， 处处有LOCK也行。。。。

我觉的你是简单问题复杂化了，在我看来，这个错误最简单的修正方式就是扩大锁的范围，在没有明确测试之前怎么能确定一定有性能上的问题呢？况且从数据库加载数据这一操作也只是一次调用。采用cas方式不一定能带来性能提升，但是代码复杂度的提升倒是显而易见。

的确.之前也写了不少多线程方面的代码,感觉并发控制不是那么困难, 但是经此一役,发现自己还差很远.呵呵.

因为我这个系统的业务比较复杂,中间掺杂了很多特殊的业务处理都是非常耗时的(包括一次远程ice调用和若干个无法避免的数据库写操作)所以对这个查询的性能(即模型中第一个用于判断的foo方法)要求必须稳定而且是尽量能越小越好,  我大概在测试环境的服务器上测试了一下,这块getDatafromDb的时间消耗很不稳定（因为测试环境跑了很多其他服务,应用服务器和db的负载很不稳定.所以这个测试结果也只能大略参考一下）。性能主要看数据库当时负载,查询的结果集大小等因素.从1ms到10＋ms不等. 虽然getDatafromdb对一个用户而言只会执行一次(不考虑lru),但是
在高并发的情况下,这块的性能表现可能就很不稳定了.很有可能是时快时慢. 所以我认为, 令可增加程序的复杂度,也
需要尽量保证其稳定性。对我这里map的get和put操作来说,string作为key应该可以保证其性能。（按照之前做过map的get和put性能测试来看还是很理想的）