Web应用场景下缓存参数的数学模型

 缓存是Web应用中重要的工具，基于最终一致性原理的缓存机制避免了Web应用中耗时操作的调用，比如数据库操作，Rest Http Service调用等。缓存提高了接口响应速度，提高了Web应用的并发量和吞吐量。

        目前常用的缓存工具有缓存中间件（Redis和Memcached）和本地缓存（Google Guava），虽然工具各异，但是都需要调整一些类似的缓存参数。本文讨论这些参数和cache命中率之间的公式关系，以便在调整这些参数时能够有所依据。

假设与推导

       我们希望请求尽量被Cache所处理，而尽量少的通过复杂业务逻辑，因此有了缓存命中率r的概念，并希望r越大越好：

缓存命中率r=被Cache处理的请求数/总请求数

在讨论r之前做两个基本假设：

• 假设Cache是Key-Value类型的，每个Key对应一个Value，并且Key都是离散值
• 假设每个请求到达Cache对应唯一的key，并且请求是完全随机的

       在各种Cache工具中，可能影响r的主要参数包括两个：

• Cache所允许的最大key数量（设为n）
• Cache中Key-Value的过期时间（设为t）

       在业务场景中还有两个参数会影响到r：

• 单位时间应用接受的总请求数（设为A）
• 业务场景下Cache中Key可能的所有取值数量（即Key取值空间，设为m）

假设m>=n，我们考虑一个过期时间t内的缓存命中率：

其中At为过期时间t内的总请求数。

       未命中的请求数包括两部分：

1. 由于过期导致请求不命中，在一个过期时间内，缓存中所有的key都会并且仅会过期一次，相应key的请求将不命中，这部分的数量设为w
2. 由于m>n导致的请求不在缓存中，即缓存空间有限导致无法存下所有的key导致请求不命中，这部分的数量为(1-n/m)*(At-w)，其中(At-w)为排除了因过期未命中的请求外的总请求

由此可得： 

从最后化简得到的结果我们很容易看出：

n/m是假设没有过期时间，仅仅由于缓存空间不足以存下所有的key所得的缓存命中率

1-w/At是假设缓存空间无限，而仅仅由于超时所得的缓存命中率

       最终的缓存命中率正是这两个因素单独得到的命中率相乘。我们可以进一步得到单位时间内未命中的请求数量fails模型：

       我们的最终目的是让fails尽量小，因为每增加一个未命中的请求就意味着为数据库或者其他基础服务增加了一份压力，而提高缓存命中率r本质上也是为了降低fails，因此下面分析中只关注fails模型。

       Fails中的w比较讨厌，w代表一个超时周期内Cache超时的key数量。w是一个不确定的值，和概率有关，当n<m时，有可能一个key都不超时，也就是说每个key都在超时之前被替换算法替换（因为n<m），而替换之后的新key是不可能超时的（注意在一个超时周期内）；w还有一个上界n，即Cache被填满，n个key都超时，但是超时之后新替换进来的key不会再超时（还是在一个超时周期内）。因此有0=<w<=n，由于r中的1-w/At>=0，因此需要约束n<=At,进一步可得：

        fails_up即为fails的上确界，在fails_up中只有我们熟悉的参数，我们只要努力减小fails_up，就能保证真实的fails相应减小。最终问题转化为求fails_up(m,n,t)函数在两个约束条件下获得最小值时m,n,t的值的问题。这个问题是纯高数问题，可以自己求一下fails_up各个变量的偏导数找一下驻点，这里不再展开，下面对这些变量定性的分析一下。

分析

       首先n代表cache空间，n对于fails_up是一个二次函数，是有最小值点的，这时n=At/2，看来Cache空间并不是越大越好。但是不要忘了m>=n这个约束，一般情况下At/2是大于m的（至少丛林的各个接口请求都是这种情况），这时At/2这个最小值点是取不到的，n的最优取值就是n=m。

       再来看下m，m是fails_up的增函数，m需要尽量的小，也就是说我们要压缩key的取值空间。比如我们的key可能只有一个字段cityID，即城市ID，Value可能是这个城市的一些信息，这时key的取值个数就有600多个。为了压缩key我们可以将所有城市信息一次获取到，key只有唯一的取值，对应的Value为cityID的映射表或者包含cityID的城市信息集合，这样就将key的取值范围压缩了600多倍。此外，如果m是一个很小的值，那么n也可以轻松和m相等。

       实际上，从命中率r的公式中可以看出n/m是很重要的，因为r的另一个因子1-w/At往往可以很高，比如达到98%，但是如果n/m很低的话也是没用的，n/m只有50%的话，1-w/At再高，r依然不到50%。因此应尽量让n=m。方法可以是上段提到的降低m，如果m实在将不下来，而且m又很大，建议使用集群缓存系统，如Redis，本地缓存将不再适用。

       超时时间t就不用多解释了，当然是越大越好，关键就看需求能容忍多大的过期时间了。

       虽然单位时间访问量A我们无法控制，但最后还是讨论一下A。我们想知道当A突增时会如何，比如说A变成2A。这时考察fails_up，当n<m时，可得2fails(A)>fails(2A)，也就是说访问量翻倍并不会造成fails的翻倍。

       当n=m时，我们发现fails_up=m/t，这是一个在参数确定时和A无关的常量，也就是说当n=m时，无论访问量多大，fails是有常数上限的，这就为什么当你缓存中的key取值空间就一两个值，无论访问量多大，你的后台服务请求量都是个位数。这也再次印证了压缩key取值空间的重要性（当然，这时把t从1分钟调整到1天，效果也应该是十分显著的O(∩_∩)O）。

结论

       综合上述模型和分析，缓存参数调整顺序如下：

1. 尽量降低缓存key的取值空间
2. 增大缓存空间上限，使其能够容纳所有的key的取值
3. 如果key取值范围太大，建议使用集群缓存（如Redis）而非本地缓存
4. 完成上述工作后尽量增大过期时间