Web Cache替换算法分析(一)

      对于一个高性能服务器软件来说，cache层的设计好坏直接影响着系统性能。
      web caching与传统操作系统中cache的区别：
      (1)HTTP协议支持整个文件的传输，因此一个web cache只有缓存了整个文件才能满足用户的请求。
      (2)在web cache中保存的文件大小可以是不同的，而CPU和磁盘缓存处理的是统一大小的页面。
      一个web cache性能的好坏可以通过两个参数来衡量：
      (1)file hit ratio=cache命中的文件数/用户请求的文件数
      (2)byte hit ratio=cache命中的页面的字节数/用户请求的页面的字节总数
      这两个参数越高，都意味着更多的用户请求的页面在cache中命中并返回，而避免了磁盘访问速度慢的问题。
      设计一个web cache主要需要考虑：
      (1)用户请求的内容是否应该cache
      (2)如果需要保存，应该替换掉其中的哪个页面
      (3)在web请求中，存在correlated reference现象，在某段时间用户会频繁地请求某个文件，而在这段时间后这个文件就很少再被访问，如果一个文件被频繁访问后，过了一段时间才被再次访问，而cache不能提供很好的策略及时将该文件替换出去，我们称local reference现象导致cache脏问题(cache pollution)。
      cache替换算法的比较：
      OPT算法，也称为clairvoyant replacement algorithm。当一个页面需要被cache而导致已保存的内容需要替换出去时，OPT算法会将cache中某个将来最长时间内都不会被访问的页面替换出去。很明显，该算法只是理论上的一种理想化算法，实际应用中设计的算法都是该算法的近似算法。
      LRU算法，least recently used algorithm。该算法维护一个lru list，当某个请求的页面需要cache时，从list的头部删除掉一个节点，并将该页面插入到list的尾部。如果用户请求的是list中已有的某个页面，则将该页面移至list的尾部。LRU算法的缺点是它没有考虑文件访问的一些规律，有时候会表现出很低的性能，尤其是在数据库系统中，通常数据都有访问模式可循，这时候使用LRU算法不能够充分利用这些规律，在有些情况下可能会出现LRU将一个用户访问次数多的文件从lru list中替换出来，而插入一个用户访问次数低的文件，引起cache pollution问题。
      LRU/k[1]是LRU的改进算法，该算法提议应该针对文件第k次访问时距离现在的时间跨度来确定是否cache，目前，主要使用的是LRU/2。这个算法的主要思想是说不能仅仅依靠一次访问就决定一个文件应该cache。LRU/2算法在实现时使用的数据结构是优先级队列，时间复杂度为O(nlogn)。为了能够解决cache pollution的问题，LRU/2有两个参数是需要调参的：(1)correlated reference period，在一个correlated reference period时间段内，多次文件访问只算作一次，这样可以避免cache pollution的问题，当某个文件在一个period时间内多次访问后，经历一段时间才再次进行访问，这时候这个保存在cache中的文件会在一个period时间段过后更新为一个低的优先级。(2)retained information period。这个时间段是当一个文件从cache中删除后它的访问历史记录会在一个period时间段内保存。
      Simplified 2Q[2]算法维护了两个数据结构，A1和Am，其中A1为fifo队列，Am为一个lru list。当一个文件第一次请求访问时，文件加入到A1中，当文件再次被请求访问时，算法认为该文件可能是一个host内容，并将其从A1移至Am。具体算法流程如下：

if p is on the Am queue
then
    
    put p on the front of the Am queue
else if p is on the A1 queue
then
    
    remove p from the A1 queue
    
    put p on the front of the Am queue
else /*first access we know about concerning p, find a free page slot for p*/
    
    if there are free page slots available
    
    then
        
        put p in a free page slot
    
    else if A1's size is above a (tunable) threshold
        
        delete from the tail of A1
        
        put p in the freed page slot
    
    else
        
        delete from the tail of Am
        
        put p in the freed page slot
    
    end if
    
    put p on the front of the A1 queue
end if

      Simplified 2Q算法有一个缺点，就是它不能解决correlated reference带来的cache pollution问题。
      2Q[2]是simplified 2Q算法的改进，它试图在达到LRU/2算法性能的同时，降低时间复杂度，并且减少调参。针对correlated reference现象，2Q算法将A1分成了两个队列，A1in和A1out。以下是算法流程：

//If there is space, we give it to X
//If there is no space, we free a page //slot to make root for page X
reclaimfor(page X)
begin
    
    if there are free page slots then
        
        put X into a free page slot
    
    else if(|A1in| > Kin)
        
        page out the tail of A1in, call it Y, add identifier of Y to the head of A1out
            
        if(|A1out| > Kout)
                
            remove identifier of Z from the tail of A1out
            
end if
            
put X into the reclaimed page slot
    
else
        
page out the tail of Am, call it Y
        
//do not put it on A1out;it hasn't been
        
//accessed for a while
        
put X into the reclaimed page slot
    
end if
end


On accessing a page X:
begin
    if X is in Am then
        move X to the head of Am
    else if(X is in A1out) then
        reclaimfor(X)
       
add X to the head of Am
    else if(X is in A1in)   // do nothing
    else  // X is in no queue
        reclaimfor(X)
        add X to the head of A1in
    end if
end

      从算法流程可以看出，当一个新文件被访问时候，2Q会首先将它放入A1in中，在随后的多次访问中都认为是correlated reference，所以如果文件在A1in中，2Q不更新任何信息。A1in中内容删除后会放入A1out中，只有A1out中的内容被访问时2Q才认为该文件是热访问文件，并将其放入Am中。
      在代理服务器中，经HTTP等协议访问的文件大小，次数都是在设计web cache时需要考虑的事情。GDS算法考虑使用文件的大小，GDF算法考虑使用文件访问频率，而GDFS算法[3]综合考虑了这两个参数。这三种算法都考虑使用了一种优化的aging mechanism，以避免cache pollution。GDS算法能够得到很好的byte hit ratio，但file hit ratio不是很好，而GDF算法能够得到很好的file hit ratio，但byte hit ratio不是很好，GDFS[5]算法尝试在二者之间平衡。GDFS使用优先级队列保存文件，并通过公式(1)：

在插入文件或者替换文件时候更新文件的优先值。这里Pr(f)指一个文件的优先值，Fr(f)为文件访问的频率，Size(f)为文件大小，Clock是为了解决cache pollution而引入的一个参数，GDFS算法给出了一种更新每个文件Clock的方法。公式(1)与我们通常直观理解也比较吻合，文件访问次数越多的文件，应该越热，并且文件如果比较大，应该不cache，将空间让给更多访问热度高的小文件。公式(2)是公式(1)的改进，尝试对Fr(f)与Size(f)加上权重：

      实验结果表明，降低文件大小的权重或者增加文件访问次数的权重都会使cache替换算法的性能达到更优，同时提高file hit ratio和byte hit ratio。
      小结
      (1)LRU算法和Simplified 2Q算法都会导致cache pollution，而LRU/k，2Q以及GDFS都不会产生cache pollution。
      (2)LRU/k与GDFS算法使用了一个优先级队列，时间复杂度相对较高。而2Q与LRU/k都没有考虑web cache中访问文件本身具有的特征。
      下一章可以看到，TS中的CLFUS算法综合考虑了这些算法的优缺点。
      一些英文原文术语定义：

correlated reference: A common occurrence is for a page receive many references for a short period of time, then no references for a long time

参考文献：
[1] E.J. O'Neil, P.E. O'Neil, and G. Weikum. The lru-k page replacement algorithm for database disk buffering. 
[2] Theodore Johnson, Dennis Shasha. 2Q: A Low Overhead High Performance Buffer Management Replacement Algorithm. 
[3] Ludmila Cherkasova, Gianfranco Ciardo. Role of Aging, Frequency, and Size in Web Cache Replacement Policies.