你知道5分钟法则和10字节法则么?

如果一条数据每5分钟被访问一次,那么它应该常驻在内存中。类似的,如果想存储只有0和1两个值的标志位,相比于将8个标志位打包为1个字节,将1个标志位单独存储为1个字节是更节约的选择。

本文参考 Jim Gary(图灵奖得主)于1987年发表的论文:The 5 minute rule for trading memory for disc accesses and the 10 byte rule for trading memory for CPU time | ACM SIGMOD Record

5分钟法则

如果数据在磁盘上,需要加载到内存进行读写,这是需要钱和时间的。在某些特殊情况下,由于磁盘读写耗时长因此数据常驻在内存上,但数据常驻在内存上是不经济的行为,因此什么时候数据需要常驻内存是一个值得思考的问题。一个好的建议是:

5分钟法则:每5分钟访问一次的数据应当记录在内存中。

注意5分钟并不是一成不变的,20年前可能是5秒钟法则,20年后有可能是5小时法则,确切的数据依赖于硬件的价格比率,这里使用1986年的价格数据进行论证,标准如下:

  • 磁盘:支持每秒15次的随机访问,价格为15k,因此每秒访问一次该磁盘的代价为1k(1k/a/s,a为access),若支持该磁盘额外计算和通道代价为1k/a/s,则该磁盘访问代价为2k/a/s。
  • 内存:大小为1MB的内存,价格为5k,因此该内存的存储代价为5/KB。

如果记录1KB数据到内存中,能够节省1a/s的磁盘访问,相当于花费的代价从2K变成了5,即便是节省0.1a/s的磁盘访问,也是从200的代价变成了5,这是很划算的。如此可以计算,当数据的访问频率在0.0025a/s(每秒访问0.0025次,即400秒访问1次),是划算到不划算的分界点。

因此,如果一条1KB的数据,访问频率大于400秒1次,就应该存储在内存中,反之应该存储在磁盘中。五分钟法则便是这个意思(用5分钟近似400秒,具体几分钟不重要,主要是描述这个计算方式)。对于更小的数据,盈亏分界点会更大一些,对于更大的数据,盈亏分界点会更小一些。

如果数据的大小超过了单次磁盘传输数据块的大小,例如100KB数据会分成25个4KB大小的数据传输。因此这种情况下100KB的数据按照4KB来计算盈亏分界点,为0.01a/s(100秒访问1次)。

公式推导

一个更正式的推导为:

  • RI:访问数据的预期间隔,单位second/access。
  • M:记录1字节数据到内存的代价,单位dollor/byte。
  • A:每秒一次磁盘访问的成本,单位dollor/access/second。
  • B:数据的大小,单位byte。
  • Bmax:最大磁盘传输块大小,单位byte。

假设B < Bmax,记录数据到内存能节省的代价为:

\[\frac{A}{RI} – M \times B \]

当等式为0,即盈亏分界点,RI的值为:

\[RI = \frac{A}{M \times B} \]

当 A = 2000,M = 0.005,如下图所示为 RI = f(B) 的函数图像。带入 B = 1000, 可以得出 RI = 400s/a, 即 0.0025a/s。

image.png

应用分析

通过一个案例说明5分钟法则的实际应用,客户想将数据库中的所有数据记录到内存中,该数据库有50万条记录,每条记录大约1KB,因此整个数据库约有500MB大小,通过5分钟法则来证明采用内存磁盘混合存储是一个更好的设计。

该应用的事务很简单,几乎所有的事务都只是访问单条记录,需要1秒的响应时间。每个事务占用40ms的CPU和30ms的磁盘。整个应用的最大负荷为600tps(每秒600个事务)。

全内存的设计中,大概需要36个TXP处理器,每个处理器对应16MB的内存。以及两个磁盘存储整个数据库、索引和程序。由于所有数据记录在内存中,大部分时间磁盘是空闲的。

根据5分钟法则,只有访问间隔小于5分钟的数据才应该记录在内存中。并且Hoelshken发现,3%的数据占据了全部访问次数的80%(和二八定律差不多)。统计表明对于600TPS的最大负荷,在50万条记录中,只有30000条记录会在5分钟内被访问2次,并且这6%的数据占全部访问次数的96%。

如果将这6%的数据记录到内存中,每秒的磁盘访问次数会从600降低到24(600*4%)次。存储数据的两个磁盘可以轻松撑起24tps的负荷。这样的设计可以节省470MB(500-500*4%)的内存和6个处理器。任何应用程序的数据访问都可以使用这个逻辑计算磁盘和内存的最佳大小。

5分钟法则还适用于虚拟内存管理,例如每2分钟访问一个虚拟内存页面(一般4KB),那么该页面就应该记录在内存中,因此一个好的时钟页面置换算法应该有足够的内存在峰值负载下保证每分钟能轮转一次,或者能够检测hot页面(比如一个2分钟的窗口),并对hot页面有特殊的处理。

10字节法则

另一个问题是,什么情况下使用内存资源来节约计算资源(cpu)更划算?或者相反的,牺牲一些计算资源来节省一些内存?这个问题在编写代码时表现为通过展开循环来保存一些数据,或用额外的指令从字节中提取某个比特。

类似于5分钟法则,假设内存成本为5/KB,每秒执行一条指令的成本为0.05,这和10字节的内存成本一致,因此就有了10字节法则:

10字节法则:10字节的内存资源的成本和每秒执行1条指令的计算资源的成本相等。

公式推导

一个更正式的推导为:

  • I:新的设计可以减少的程序的指令的数量。
  • F:指令执行的频率,单位1/second。
  • S:新的设计增加了多少内存,单位byte。

I*F指新的设计总共省去的指令数量,如果新的设计增加了执行的指令,那么I*F的值为负数。根据10字节法则,总节省成本为:

\[I \times F – \frac{S}{10} \]

如果它是一个很大的正数,就说明新的设计节约了很大的成本。

应用分析

例如有如下程序有三个指令,该程序每秒被调用1000次。

1. 加载一个字节,该字节存储了8个flag,对应8个比特
2. 利用位掩码获取其中一个flag
3. 判断这个flag的值
  • 如果一个flag使用一个字节来存储,那么这个程序就不需要指令2,整个程序只需要两个指令,则表示每秒节约了1000次指令的执行。
  • 根据10字节法则,节约1000次指令每秒的计算资源,相当于节省了10000字节的内存资源。
  • 如果一个flag使用一个字节来存储,意味着需要8倍的内存资源,如果总共需要处理100个flag,意味着内存需求从12个字节变成了100个字节,多了88个字节(论文是88,所以不要纠结12*8=96的问题了)。
  • 牺牲了88字节的内存资源,节约了1000次指令每秒的计算资源,也就是10000字节的内存资源,因此净节省为10000-88=9912的内存资源, 投入回报比约为1:100,是非常划算的改变。

带入公式为:I = 1,F = 1000,S = 88,1*1000 – 88/10 = 991.2。

总结

这些规则背后的思想是权衡经济成本评估设计决策的方法,随着硬件性价比的改变,这些规则也会改变。在未来,5分钟法则可能变成5小时法则,10字节法则可能变为100字节法则。

张贴在2