分享下银行招开发人员的第一轮题目

wangbo1118

Bessy 发表于 2014-8-9 00:12
噢，是你说“cache中找不到”，能解释一下为什么要把记录Key(x)移除cahce 么？ ...

我觉得就像piddock回帖里面说的
“你不能指望这个信息一年时间都保存在cache里面，应该放在数据库里面。”

就是cache只是保存一部分数据，提高效率，他有个失效的机制，不管是ttl还是LRU

这个例子中，既然它已经到时间失效了，那就把它释放了啊，可以释放内存资源啊

你说后面可能会再被用到，但是这个再被用到，谁都不好说会不会发生啊，所以必须有个策略，按照这个策略来吧

wangbo1118

piddock 发表于 2014-8-8 23:43
我的理解是x的key还在，x在hashmap中的value被更新了。所以锁定key(x)应该没问题。 ...

恩，这个例子中，我也觉得x被更新了

还有，这里你们讨论的锁把我搞晕了


ConcurrentHashMap本身自己的访问已经多线程安全了，在我自己写的Cache类的put、get方法层面，我还需要考虑加synchronized或者其他锁机制吗？

袋鼠玳

不用再加锁了

gongey

开始了 bob

wangbo1118

gongey 发表于 2014-8-9 16:37
开始了 bob

yeah 好眼力

Bessy

wangbo1118 发表于 2014-8-9 00:30
我觉得就像piddock回帖里面说的
“你不能指望这个信息一年时间都保存在cache里面，应该放在数据库里面。 ...

没人要在cache保存一年的信息吧， 也许piddock想这样，他一定会有他的道理的。

我的例子是“就如，银行账户1年过期。1过一年了，用户来存一万元钱。钱进入银行系统了，然后你把他的账户删除了， 因为过期了，是么？ ”

有2个方案：1， 删除现在的，立刻再建新的账户对象， 删除和新建都需要层层审批（类似JVM要求清空和新建）
                  2， update现有的，把新的信息更新。避免层层审批。

我选2.节省资源，不删除后在建立相同的东西。
                  

Bessy

wangbo1118 发表于 2014-8-9 00:33
恩，这个例子中，我也觉得x被更新了

还有，这里你们讨论的锁把我搞晕了

“ConcurrentHashMap本身自己的访问已经多线程安全了，在我自己写的Cache类的put、get方法层面，我还需要考虑加synchronized或者其他锁机制吗？”

我们选用ConcurrentHashMap就已经在考虑锁了。为什么不选，Hashtable, 或synchronized Hashmap？

同样的道理，我们要考虑锁在ConcurrentHashMap里让粒度更细。

wangbo1118

Bessy 发表于 2014-8-9 18:55
“ConcurrentHashMap本身自己的访问已经多线程安全了，在我自己写的Cache类的put、get方法层面，我还需要 ...

没有考虑同步的代码片段如下：

public class CacheImpl implements  ICache{
   
    private ConcurrentHashMap<Object, Record> cache = new ConcurrentHashMap<Object, Record>();
   
    public void put(Object key, Object value, int ttl) {
        cache.put(key, new Record(value, ttl));
    }
    public Object get(Object key){
        Record rec = (Record)cache.get(key);
        if( rec == null)
            return null;
        if(rec.isExpired()){
            cache.remove(key);
            return null;
        }
        return rec.getValue();
    }
    public Object remove(Object key) {
        return cache.remove(key);
    }
}

-------------------------------------------------------
Record类存放value和ttl（内部转为过期时间了）

这里似乎put 、get、remove三个方法要放在synchronized(this)里，不然get执行了三行，这个时候切换到另外一个线程，put进去了内容，然后再切换回来，rec对象实例里面是老的内容，可能是过期的时间，一判断，过期了，然后会把之前put进去的内容删除了。。


但是如果都加上synchronized(this)，觉得效率又下来不少，如果还有一个线程在定期的删，估计这个cache挺忙的

不知道有更好的办法没？

wangbo1118

Bessy 发表于 2014-8-9 17:38
没人要在cache保存一年的信息吧， 也许piddock想这样，他一定会有他的道理的。

我的例子是“就如，银行 ...

银行账户不会一年过期吧，一年里面放cache，这样可以快速查到你账户的内容，如果超过一年，cache就没有了，就是查的慢一点，你要存钱，他要到后台数据库查到你的资料，然后再放入cache，然后帮你存好

因为不是建立新账户，所以不涉及审批啊

piddock

wangbo1118 发表于 2014-8-9 19:20
没有考虑同步的代码片段如下：

public class CacheImpl implements  ICache{

有个想法，可能不成熟。
是否可以将你的Value和ttl合并成为一个New_Value对象（ttl作为New_Value对象中的一个成员属性），这样直接用ConcurrentHashMap就可以了，应该无需考虑get、put和remove之间的同步问题了。

wangbo1118

piddock 发表于 2014-8-9 20:33
有个想法，可能不成熟。
是否可以将你的Value和ttl合并成为一个New_Value对象（ttl作为New_Value对象中 ...

恩，我也考虑了这个方法

你说的意思是不是把isExpire()这样的逻辑写在你说的New_Value里面啊

然后New_Value.getValue()的时候New_Value这个类负责考虑是不是过期，如果过期返回null

但是还有一个逻辑，就是如果过期的话，需要删掉cache中的内存，这个步骤如果不同步好，可能就把正常的新put进去的内容删掉了

因为get出来可能是线程1在执行，然后就轮到线程2去put一样key的内容，等到put完了，再轮到线程1执行判断出get出来的内容过期了，这个时候再去删除，就是删除刚刚put进去的内容了。。

piddock

wangbo1118 发表于 2014-8-9 20:55
恩，我也考虑了这个方法

你说的意思是不是把isExpire()这样的逻辑写在你说的New_Value里面啊

你想的太仔细了，很佩服啊。

实在不行的话，参照CurrentHaspMap源代码写个Cache类，就不用这么捉襟见肘了，当然这是个馊主意。

Bessy

wangbo1118 发表于 2014-8-9 19:20
没有考虑同步的代码片段如下：

public class CacheImpl implements  ICache{

写的很好， 2个地方与你理解不同。

1.   需求没有提Put 方法，和value参数？ 只提到了Key和ttl，map 的value是ttl。      而且Put 函数用的是Segment lock.应该改成行锁。

2.  我理解， 如果ttl没过期应该更新为最近访问时间，而不是等着过期。

我更倾向于这个问题接近于Apache Mina 的ExpiringMap (http://svn.apache.org/repos/asf/ ... il/ExpiringMap.java)
主要用到以下几个概念。

package org.apache.mina.util;
* A map with expiration.  This class contains a worker thread that will
* periodically check this class in order to determine if any objects
* should be removed based on the provided time-to-live value.
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.CopyOnWriteArrayList;
import java.util.concurrent.locks.ReadWriteLock;
import java.util.concurrent.locks.ReentrantReadWriteLock;

Bessy

这类concurrency cache 在， LinkedIn 的cassandra 和 google 的 guava 也有类似实现。用的方法都相似。

wangbo1118

Bessy 发表于 2014-8-9 21:22
写的很好， 2个地方与你理解不同。

1.   需求没有提Put 方法，和value参数？ 只提到了Key和ttl，map 的v ...

谢谢你提供的reference，我看了下这个程序

关于理解的差异，你整理的挺清晰，不过第一点我没完全看懂

Put 函数用的是Segment lock.应该改成行锁。

具体是什么 意思怎么做啊？（这个segment lock指的是ConcurrentHashMap的segment lock吧？）

关于第二点，我看了程序，理解你的意思了

你的意思是：
如果没过期就更新访问时间，ttl根据最后访问时间来算。
换句话说，只有在ttl时间里没有被访问到，才会被请出缓存。


这个地方我一下子还不是马上能接受，我要再想想。


但是我看了他们的程序，我觉得同步的问题也依然存在 啊，我copy出来一段你们看看：

-----------------------------------------------------------------------------------------
        public V put(K key, V value) {
                ExpiringObject answer = delegate.put(key, new ExpiringObject(key,
                                value, System.currentTimeMillis()));
                if (answer == null) {
                        return null;
                }

                return answer.getValue();
        }

        public V get(Object key) {
                ExpiringObject object = delegate.get(key);

                if (object != null) {
                        object.setLastAccessTime(System.currentTimeMillis());

                        return object.getValue();
                }

                return null;
        }

-----------------------------------------------------------------------------------------

线程1执行get方法，执行到
                        object.setLastAccessTime(System.currentTimeMillis());
这行，切换到线程2，线程2执行put方法（put的key就是线程1get用 的key，value换了一个），然后再切换到线程1，这个时候返回的值不就不对了吗？

wangbo1118

Bessy 发表于 2014-8-9 21:22
写的很好， 2个地方与你理解不同。

1.   需求没有提Put 方法，和value参数？ 只提到了Key和ttl，map 的v ...

我还发现，这个类的处理过期里面，是遍历容器的，这样的话，代价不小吧。。


                private void processExpires() {
                        long timeNow = System.currentTimeMillis();

                        for (ExpiringObject o : delegate.values()) {

                                if (timeToLiveMillis <= 0) {
                                        continue;
                                }

                                long timeIdle = timeNow - o.getLastAccessTime();

                                if (timeIdle >= timeToLiveMillis) {
                                        delegate.remove(o.getKey());

                                        for (ExpirationListener<V> listener : expirationListeners) {
                                                listener.expired(o.getValue());
                                        }
                                }
                        }
                }

wangbo1118

piddock 发表于 2014-8-9 20:33
有个想法，可能不成熟。
是否可以将你的Value和ttl合并成为一个New_Value对象（ttl作为New_Value对象中 ...

我在想，还需要一个线程去删除过期的缓存

因为条件里面说：

1，这个key是 广泛分布于keyspace的，所以他们重复用的概率并不算太高吧（我的理解）
2. 这个key可能没有被用到

结合这两个条件，我觉得会有一定量的记录，被放进缓存了，之后也没用到，而且之后一样key的内容进来的可能性不大或者间隔会非常长，这样就会导致内存用的量缓慢上升到不可接受的程度


所以，我觉得需要一个线程去清理过期记录

可以保持的时候将key和过期时间保存在treeMap或者treeSet里，这样每次读可以读先过期的那头，一直读到不过期的记录就可以停了

当然，也可以让这个线程一直遍历整个cache

我目前在想那种更好一点

sslovedandan

thanks for sharing

很明显

佩服，还在讨论

flier

感谢分享，很有用

wangbo1118

发下第一道题我写的代码，大家参考讨论下吧：

public interface ICache {
    public void put(Object key, Object value, int ttl);
    public Object get(Object key);
}

/////////////////////////////////////////////////////////////////////////////////////////////////

public class Record {
   
    public Record(Object v, int ttl){
        setValue(v);
        setTTL(ttl);
    }
    public Object getValue() {
        return value;
    }
    public void setValue(Object value) {
        this.value = value;
    }
    public long getExpiretime() {
        return expiretime;
    }
    public void setTTL(int ttl) {
        this.expiretime = System.currentTimeMillis() + 1000 * ttl;
    }
    public boolean isExpired(){
        return System.currentTimeMillis() >= expiretime;
    }
    @Override
    public String toString() {
        return value.toString() + " | expire time: " + expiretime + "; ";
    }
    private Object value = null;
    private long expiretime = 0;
}

/////////////////////////////////////////////////////////////////////////////////////////////////


public class ExpiringObject implements Comparable<ExpiringObject> {

    public ExpiringObject(Object k, int ttl) { // time to live is ttl, unit: seconds
        key = k;
        expiretime = System.currentTimeMillis() + ttl * 1000;
    }

    public boolean equal(Object k) {
        if (key == null){
            return false;
        }
        return key.equals(k);
    }

    @Override
    public int compareTo(ExpiringObject e) {
        long v = this.expiretime - e.expiretime;
        if (v > 0)
            return 1;
        if (v < 0)
            return -1;
        else
            return 0;
    }

    public boolean isExpired() {
        if (System.currentTimeMillis() > this.expiretime)
            return true;
        else
            return false;
    }

    @Override
    public String toString() { // for test/debug purpose
        return key.toString() + " | TTL: " + expiretime + "; ";
    }

    public Object getKey() {
        return key;
    }
   
    private Object key = null;
    private long expiretime = System.currentTimeMillis();


}

wangbo1118

前面是接口和实体类，主要是下面这个类：


import java.util.TreeSet;
import java.util.concurrent.ConcurrentHashMap;

import com.cba.bobwang.cache.ExpiringObject;
import com.cba.bobwang.cache.ICache;
import com.cba.bobwang.cache.Record;

/***********************************
* This class implement ICache interface
* a Expirer Thread will be created when constructing the CacheImpl instance
* the Expirer Thread will periodically check/clear the expired records to release the memory
*
* @author Bob Wang
*
*/
public class CacheImpl implements  ICache{
       
        // container for cache
        protected ConcurrentHashMap<Object, Record> cache = new ConcurrentHashMap<Object, Record>();
        // sorted container for the Expirer thread to periodically check&clear expired records
        protected TreeSet<ExpiringObject> expiringObjects = new TreeSet<ExpiringObject>();
        // default interval to clear expired records, unit: seconds
        protected int DEFAULT_INTERVAL = 10;       
       
        public CacheImpl(){
                Expirer expirer = new Expirer(this, DEFAULT_INTERVAL);
                new Thread(expirer).start();
        }
       
        public void put(Object key, Object value, int ttl) {
                synchronized(this){
                        cache.put(key, new Record(value, ttl));
                }
                expiringObjects.add(new ExpiringObject(key, ttl));
        }
        public Object get(Object key){
                synchronized(this){
                        Record rec = (Record)cache.get(key);
                        if( rec == null)
                                return null;
                        if(rec.isExpired()){
                                cache.remove(key);
                                return null;
                        }
                        return rec.getValue();
                }
        }
       
       
        public class Expirer implements Runnable {
                long interval = 10000;
                ICache cache = null;

                public Expirer(ICache c, int intervalSec){
                        cache = c;
                        interval = intervalSec * 1000;
                }
                @Override
                public void run() {

                        ExpiringObject eo = null;
                       
                        while(true){
                                try {
                                        Thread.sleep(interval);
                                } catch (InterruptedException e) {
                                        e.printStackTrace();
                                }
                                if(!expiringObjects.isEmpty())
                                        eo = expiringObjects.first();
                                else
                                        eo = null;
                                while( eo != null && eo.isExpired() ){
                                        cache.get(eo.getKey());
                                        expiringObjects.remove(eo);
                                       
                                        if(!expiringObjects.isEmpty())
                                                eo = expiringObjects.first();
                                        else
                                                eo = null;
                                }
                        }

                }

        }
}

wangbo1118

写了个main跑个简单测试

public class CacheTestMain {

        public static void main(String[] args) throws InterruptedException {
                CacheImpl cache = new CacheImpl();
                cache.put("Alice",         "value1", 10);
                cache.put("Bob",         "value2", 5);
                cache.put("Chris",         "value3", 15);
                cache.put("David",         "value4", 8);
                cache.put("Eric",         "value5", 12);
               
               
                Thread.sleep(1000);
               
                System.out.println("--------------Time:1s---------------" );
               
                /*
                 * first round, after 1s
                 * all the values are there
                 */
               
                print(cache);
               
                System.out.println("--------------Time:6s---------------" );
               
                /*
                 * second round, after 6s
                 * Bob's record is cleared from cache since its ttl is 5s
                 * in this round, Alice & David have been updated
                 * 8s & 11s start from 6s point
                 */
                Thread.sleep(5000);
                print(cache);
                cache.put("Alice",         "new_value1", 8);
                cache.put("David",         "new_value4", 11);
               
               
                System.out.println("--------------Time:11s---------------" );
               
                /*
                 * third round, after 11s
                 * originally, Alice & David should been cleared
                 * BUT, they had been updated in the last round,
                 * So, we can see them with new value in this round
                 */
                Thread.sleep(5000);
                print(cache);
               
                System.out.println("--------------Time:16s---------------" );
               
                /*
                 * 4th round, after 16s
                 * all expired/cleared except David, becasue it had been updated at 6s with 11s ttl
                 * 11 + 6 = 17 s , so it will expired 1s later.
                 */
               
                Thread.sleep(5000);
                print(cache);
               
                System.out.println("-------------END----------------" );
               
               
        }
        public static void print(CacheImpl cache){
                System.out.println("Alice \t| \t" + cache.get( "Alice" ));
                System.out.println("Bob \t| \t" + cache.get( "Bob" ));
                System.out.println("Chris \t| \t" + cache.get( "Chris" ));
                System.out.println("David \t| \t" + cache.get( "David" ));
                System.out.println("Eric \t| \t" + cache.get( "Eric" ));
        }

}

Bessy

wangbo1118 发表于 2014-8-9 23:07
谢谢你提供的reference，我看了下这个程序

关于理解的差异，你整理的挺清晰，不过第一点我没完全看懂

" object.setLastAccessTime(System.currentTimeMillis());
这行，切换到线程2，线程2执行put方法（put的key就是线程1get用 的key，value换了一个），然后再切换到线程1，这个时候返回的值不就不对了吗？"

看setLastAccessTime的实现用的 ReadWriteLock

多线程的put 方法要用putifabsent+futuretaskt替代

Bessy

wangbo1118 发表于 2014-8-9 23:12
我还发现，这个类的处理过期里面，是遍历容器的，这样的话，代价不小吧。。

代价不小，但相同的需求， 暂时没有比这代价小的方法。

你的方法“可以保持的时候将key和过期时间保存在treeMap或者treeSet里，这样每次读可以读先过期的那头，一直读到不过期的记录就可以停了” 代价更大。

treemap,treeset都无法保证并发下的Atomicity, Visibility 还有Ordering。用java实现红黑树的多线程并发？应该还没有人能做出一个可用的程序。还要同时保证和concurrentHashmap的一致性。 直接可以开个公司买这个cache了。

Bessy

wangbo1118 发表于 2014-8-10 01:39
发下第一道题我写的代码，大家参考讨论下吧：

public interface ICache {

谢谢分享。 写的很好。一点小建议，就是基本功需要提高一点点，否则影响代码的可读性。举个简单的函数
    public int compareTo(ExpiringObject e) {
        long v = this.expiretime - e.expiretime;
        if (v > 0)
            return 1;
        if (v < 0)
            return -1;
        else
            return 0;
    }

1.为什么需要这个函数？
2..没有e==null的判断?
3. 用一行 return Integer.compare(this.expiretime, e.expiretime) 就可以了， LZ写7行。

wangbo1118

Bessy 发表于 2014-8-10 08:46
代价不小，但相同的需求， 暂时没有比这代价小的方法。

你的方法“可以保持的时候将key和过期时间保存在 ...

这个TreeSet我实现的时候，没有考虑并发，里面的数据也没有和cache里面完全同步，如果不同步的时候（cache里面已经没了，但是treeSet里面还有），就让清理线程Expirer再去多删除一次


假设清理线程interval的时间是十几秒的话，好像基本还是挺稳定的啊

你觉得呢

wangbo1118

Bessy 发表于 2014-8-10 09:16
谢谢分享。 写的很好。一点小建议，就是基本功需要提高一点点，否则影响代码的可读性。举个简单的函数
   ...

这个函数是让treeSet用来比较ExpiringObject 对象进行排序的
的确应该判断下null吧
用Long.compare函数的确更好


谢谢指出和建议，特别是这种精益求精的精神！

cpc_1115

现实生活中第一反应就是用现成的lib或者reactive programming like akka

wangbo1118

有没有人讨论第二个题目呢？