在搜索引擎(SE)里BS一般对结果作CACHE，同时OS也会对倒排拉链作CACHE，也就是系统CACHE。这样可控性不强，可以考虑把两层CACHE都由BS控制，这样又带来一个问题，怎么分配两种CACHE的大小(之前也有这个问题，只是很难控制，所以就不管了)。实践中的做法，是不停地调整两者的比例，然后测试效果。这种方法的问题在于，单次测试代价很大，而解的空间很大，这样很难找到最优解。现在一般是默认，中间有一个最优解，然后向两边递减，这样搜索中间的最优解会比较容易。实际上解不一定是这样分布的。另外，这两层CACHE是互相影响的，比如某个QUERY的TERM都CACHE住了，再CACHE这个QUERY的RESULT意义就不大了；如果某个TERM的大部分QUERY的RESULT都CACHE住了，再CACHE这个TERM意义也不大了。所以很可能单纯地分配两者大小比例的方法，不能得到最优解。

    简化一下问题，假设CACHE的目的只是为了节省IO，不涉及RANK策略的计算；每个QUERY RESULT的大小是相同的，因为有截断，可以认为都只CACHE住第一页；单个TERM或者RESULT所占空间远小于总的可用内存，这样是为了避免背包问题的优化；每个QUERY的调用次数是事先已统计出来的，这样每个TERM需要读的次数也是已知的；每个TERM的长度是已知的，这样也可以计算出每CACHE住一个TERM或者RESULT在IO上的收益

    所以只需要有一个确定的选取，比如选了哪些TERM，哪些QUERY，就可以算出这个组合能节省多少IO。直接枚举，那肯定是不行的，数量量太大了。可以用贪心法，优先选取(IO收益/占用内存空间)最大的TERM或者QUERY，这样肯定也不是最优解，因为这样忽略了TERM跟QUERY的互相干扰

    原先想用网络流求解一下，但是想了很久没办法构图。有可能这个问题就是NPC的。想证明NPC，一时也没头绪应该把它归纳到哪个问题。

建议继续学习：

1. Buffer和cache的区别是什么？    (阅读：6737)
2. 谈冷热数据    (阅读：5584)
3. Linux操作系统中内存buffer和cache的区别    (阅读：5242)
4. 学习：一个并发的Cache    (阅读：4853)
5. 关于Linux的文件系统cache    (阅读：4645)
6. Twitter架构图(cache篇)    (阅读：4588)
7. 什么是P问题、NP问题和 NPC问题    (阅读：4246)
8. 详解MyISAM Key Cache(前篇)    (阅读：4005)
9. 7个示例科普CPU Cache    (阅读：3975)
10. [squid] 过期时间在 60 秒内 squid 不 Cache 的问题    (阅读：3850)