Traffic Server Web Cache替换算法分析(二)

来源：http://blog.chinaunix.net/uid-23242010-id-147989.html

本章主要描述TrafficServer中ram cache设计方案。TrafficServer在内存中维护了一个ram cache，用来保存用户频繁访问的热点文件或数据，以避免磁盘查找慢的问题。TS在刚开源的时候，ram cache的设计只是一个简单的LRU算法，后来，John Plevya针对各个web cache替换算法的优缺点，提出了CLFUS算法，并根据该算法设计与实现了一个新的ram cache，新的ram cache同时支持内容压缩与解压缩[1][2]。

数据结构(这里将无关的内容都删去了)：

1. //data代表的就是用户请求访问的内容，宏LINK生成指向下一个节点的指针，比如this->hash_link.next指向的就
2. //是下一个RamCacheCLFUSEntry，TS提供了一套接口通过LINK将RamCacheCLFUSEntry组成一个linked list
   
3. struct RamCacheCLFUSEntry {
4.      LINK(RamCacheCLFUSEntry, lru_link);
5.      LINK(RamCacheCLFUSEntry, hash_link);
6.      Ptr
7. };

1. //这个类提供了从ram cache中读取或者写入用户请求的url的内容，其中get负责读，put负责写
   
2. struct RamCacheCLFUS : public RamCache {
3.      int get(INK_MD5 *key, Ptr
4.      int put(INK_MD5 *key, IOBufferData *data, uint32_t len, bool copy = false, uint32_t auxkey1 = 0, uint32_t auxkey2 = 0);
5. 
   
6.      // private
7.      DList(RamCacheCLFUSEntry, hash_link) *bucket;
8.      Que(RamCacheCLFUSEntry, lru_link) lru[2];
9.      uint16_t *seen;
10.      void resize_hashtable();   //bucket是可以动态扩展大小的
    
11. };

CLFUS算法涉及的有以下几个数据结构：
(1)基于开放链表法实现的散列表RamCacheCLFUS::bucket。
对于用户请求的url页面，CLFUS首先会对其进行hash映射到bucket中某个linked list，然后在该linked list顺序查找。
     
(2)Cached List，对应于RamCacheCLFUS::lru[0]。
cached list保存TS认为属于热点的url页面，当用户请求的url属于cached list中时，CLFUS从cached list中直接取出返回给用户。
     
(3)History List，对应于RamCacheCLFUS::lru[1]。
history list保存用户请求的不在bucket中的url页面，history list中的页面可以根据替换规则替换掉cached list中某个页面。
cached list与history list逻辑上都属于lru list。bucket中的元素有一部分在cached list中，有一部分在history list中。CLFUS通过bucket找到RamCacheCLFUSEntry对象，再根据对象中的bit位来确定该对象是在cached list还是history list中，避免了直接从cached list或者history list中顺序查找时间复杂度高的问题。

(4)Seen Hash，对应于RamCacheCLFUS::seen。在文章(一)中提到，如果一个用户请求的url是第一次访问时候，LRU/2以及2Q算法都不会直接将请求的内容放入cache中。这里Seen Hash起的是相似的作用，如果用户请求的页面只被请求过一次，则CLFUS将该页面的标识保存在seen hash中，在该页面第二次被访问时，通过seen hash可以判断出该页面是第一次还是第二次被访问。

RamCacheCLFUS::get伪代码算法分析：

1. if X is in cached list then
2.      move X to the tail of cached list, and return the data in X
3. else if X is in history list then
4.      move X to the tail of history list
5.      "cache miss"
6. else
7.      "cache miss"
8. end if

RamCacheCLFUS::put伪代码算法分析：

1. if X is in cached list then
2.     move X to the tail of cached list, and update its data
3. else if X is in history list then
4.     if cached list has room to place X then
5.         insert X to the tail of cached list, and update its data
6.     else
7.         create list V
8.         do                  
   
9.             pop one page Y from cached list
10.             //simulate the aging algorithm, for avoiding cache pollution 
11.             pop one page Z from history list
12.             if HIT_VALUE(Z) is not greater than 1 then
    
13.                 delete Z
14.             else 
15.                 let the HIT_VALUE(Z) with 1, and reinserted Z to the tail of history list   
    
16.             end if
17.             //end
    

1.             if CACHE_VALUE(X) is greater than CACHE_VALUE(Y) then 
   
2.                 push it to V
3.             else 
   
4.                 insert X to the tail of history list and update its data, return
5.             end if
   
6.         util cached list has enough room for placing X
7.         end do
   
8.         for(Z in V)
9.             if cached list has room for both Z and X, then 
   
10.                 reinsert Z to the tail of cached list
11.                 insert X to the tail of cached list, and update its data
12.             end if
13.         end for
    
14.      else // X is neither in history list nor in cached list
15.         //judge X is or not first accessed by seen hash
    
16.         if X is first accessed and history list has no room for it, then
17.             save the record of X in seen hash
18.         else
19.             insert X to the tail of history list
20.         end if
21.      end if
22. end if
    
23. 
    
24. CACHE_VALUE = hits/(size + overhead)   //similar to GDFS algorithm

参考文献：
[1] https://cwiki.apache.org/TS/ramcache.html
[2] https://issues.apache.org/jira/browse/TS-120