凌鹰电面挂经

面的system and infra，面完就知道挂了，昨天收到拒信，说Concurrency and Multi-Threading没答好

开头互相介绍，然后开始做题，大概有这些Process vs Thread，Context switch in thread and process，Wha

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

种情况，希望有知道的大佬提供一些想法

顺便吐槽一下，这个coordinator实在是太不专业了，周五早上面试，周四下午5点才发来confirmation，本来都以为取消了

Anyway，求大米

谢谢分享。关于followup 2我提一点想法抛砖引玉：
1 首先我觉得访问DataSource（在实际情况里就是访问数据库）的主要问题不是慢而是并发的压力。
    比如有一个key的读请求很多，那么这个key一旦被更新，缓存被失效，如果此时所有的缓存get请求
    都变成一个数据库的读请求，会对数据库造成过大的压力(所谓缓存雪崩)。

2 不知道楼主是怎么回答锁的问题。这类缓存一般会对锁shard，比如用hash值mod 64，减少竞争。

3 解决这个问题我有两个思路
   i.  当get请求发现key不存在或失效时，本线程先拿（sharded)锁，然后执行从DataSource载入数据
       的操作。这样即使有大量线程get同一个key，也只产生了一个数据库请求。数据库请求完成后释放这个锁，
       然后其他线程被unblock，就可以从缓存里读数据了。如果线设计成异步的接口，比如c++可以返回一个
       std::shared_future，由读数据库的线程来set。

   ii. 另一个常见的技巧是租约，这样不但可以协调同一个进程的get请求，还能用于不同进程乃至机器。做法是
       读数据库给缓存更新的时候需要请求一个token，同一时间只能有一个token。拿不到token的话，还可以
       考虑返回一个stale值，由应用决定接不接受。

1. package easy;
   
2. 
   
3. import java.util.*;
   
4. import java.util.concurrent.Semaphore;
   
5. import java.util.concurrent.locks.Lock;
   
6. import java.util.concurrent.locks.ReentrantLock;
   
7. 
   
8. public class RetainBestCache<K, T extends Rankable> {
   
9.     int entriesToRetain;
   
10.     private Map<K, T> cache;
    
11.     private TreeMap<Long, Set<K>> rankingKeySetMap;
    
12.     Semaphore semaphore;
    
13.     DataSource<K,T> ds;
    
14. 
    
15.     /* Constructor with a data source (assumed to be slow) and a cache size */
    
16.     public RetainBestCache(DataSource<K,T> ds, int entriesToRetain) {
    
17.         cache = new HashMap<>();
    
18.         rankingKeySetMap = new TreeMap<>();
    
19.         this.ds = ds;
    
20.         this.entriesToRetain = entriesToRetain;
    
21.         semaphore = new Semaphore(entriesToRetain);
    
22.     }
    
23.     /* Gets some data. If possible, retrieves it from cache to be fast. If the data is not cached,
    
24.      * retrieves it from the data source. If the cache is full, attempt to cache the returned data,
    
25.      * evicting the T with lowest rank among the ones that it has available
    
26.      * If there is a tie, the cache may choose any T with lowest rank to evict.
    
27.      */
    
28.     public T get(K key) {
    
29.         //implement here
    
30.         if(cache.containsKey(key)){
    
31.             return cache.get(key);
    
32.         }
    
33.         return fetchFromDS(key);
    
34.     }
    
35. 
    
36.     private T fetchFromDS(K key){
    
37.         if(cache.size() >= entriesToRetain){
    
38.             evitLowestRank();
    
39.         }
    
40.         T object = ds.get(key);
    
41.         try{
    
42.             semaphore.acquire();
    
43.             cache.put(key, object);
    
44.             long score = object.getRank();
    
45.             if(!rankingKeySetMap.containsKey(score)){
    
46.                 rankingKeySetMap.put(score, new HashSet<>());
    
47.             }
    
48.             rankingKeySetMap.get(score).add(key);
    
49.         }
    
50.         catch (InterruptedException e){
    
51. 
    
52.         }
    
53.         finally {
    
54.             semaphore.release();
    
55.         }
    
56.         return object;
    
57.     }
    
58. 
    
59.     private void evitLowestRank(){
    
60.         Map.Entry<Long, Set<K>> entry = rankingKeySetMap.firstEntry();
    
61.         K key = entry.getValue().iterator().next();
    
62.         entry.getValue().remove(key);
    
63.         cache.remove(key);
    
64.         if(entry.getValue().size() == 0){
    
65.             rankingKeySetMap.remove(entry.getKey());
    
66.         }
    
67.     }
    
68. }
    
69.     /*
    
70.      * For reference, here are the Rankable and DataSource interfaces.
    
71.      * You do not need to implement them, and should not make assumptions
    
72.      * about their implementations.
    
73.      */
    
74.     public interface Rankable {
    
75.         /**
    
76.          * Returns the Rank of this object, using some algorithm and potentially
    
77.          * the internal state of the Rankable.
    
78.          */
    
79.         long getRank();
    
80.     }
    
81.     public interface DataSource<K, T extends Rankable> {
    
82.         T get(K key);
    
83.     }

复制代码

从DataSource拿值会不会是应该加一个读写锁， 因为如果大量的请求是读的话 可以使用读写锁 这样可以做到大量的读请求可以同时获得锁而不是被block 只有当写操作发生的时候才会block住 如果还是太慢可以lock by bucket 这样写的时候也不是block所有 不知道面试官是不是这个意思

同面试前一天下午三四点才收到确认

看来做backeend/infra 并发很重要。

我的想法是用Semaphore 优化

用semaphore 不行，最好还是lock，因为semaphore的话比如你有先把cache塞满了然后又开了很多个thread进去的话就有问题了。我觉得还是一个一个thread 跑最好，然后我感觉第二个follow up的意思就是要你在synchronize lock 之前把value 从ds里面拿出来而已， 这样的话你就可以concurrently 从ds里面拿东西while nonblocking，不知道说的对不对