ARC Cache算法

ARC(Adaptive Replacement Cache)是一种适应性Cache算法, 它结合了LRU与LFU。 LRU(Least recently used) 其核心思想是:假设刚visit的item,很有可能在未来被revisit 丢弃最近最少访问的items 通常用双链表实现 tips: redis并没有这样做,因为这样每个key至少会多出两个指针。 redis采用的是一种近似LRU,基本思想是随机取出一些key,形成一个小的POOL,然后在pool中采用LRU策略(相关源码:redis/src/evict.c) 缺点:忽略了frequency, 不适合大规模扫描等情况 LRU有一系列变种,比如LRU2, 2Q, LIRS等。 LFU(Least-frequently used) 其核心思想是:假设visit次数越多的item,很有可能在未来被revisit 适应大规模扫描 对热点友好 缺点:忽略了recency, 可能会积累不再使用的数据 tips: redis4.0开始支持了LFU,例如volatile-lfu, allkeys-lfu配置选项 ARC 整个Cache分成两部分,起始LRU和LFU各占一半,后续会动态适应调整partion的位置(记为p) 除此,LRU和LFU各自有一个ghost list(因此,一共4个list) 每次,被淘汰的item放到对应的ghost list中(ghost list只存key), 例如:如果被evicted的item来自LRU的部分, 则该item对应的key会被放入LRU对应的ghost list 第一次cache miss, 则会放入LRU 如果cache hit, 如果LFU中没有,则放入LFU 如果cache miss, 但在ghost list中命中,这说明对应的cache如果再大一丁点儿就好了: 如果存在于LRU ghost list, 则p=p+1;否则存在于LFU ghost list, p=p-1….

水坑装水问题

题目在这里: 原文:http://qandwhat.apps.runkite.com/i-failed-a-twitter-interview/ 译文:http://blog.jobbole.com/50705 起初也是想到先求Max,这需要一次遍历;然后从左边到Max,同时右边到Max,这次遍历一共包含两个子遍历。因此一共是两次遍历。 历史总是惊人的相似,一次遍历的方法我也是早上躺在床上完成的:比较左指针和右指针指向的值,选取大的做为Max, 同时不停的移动指针,如果碰到更大的Max,调整基准即可。 这道题目没有什么高深的算法,但思维的过程还是挺有趣的。